English

运筹学学报

• 运筹学 • 上一篇    下一篇

带学习效应的两台平行机时间表长问题

朱征露1  鲁习文1,*   

  1. 1. 华东理工大学理学院, 上海 200237
  • 收稿日期:2016-08-07 出版日期:2018-03-15 发布日期:2018-03-15
  • 通讯作者: 鲁习文 E-mail: xwlu@ecust.edu.cn
  • 基金资助:

    国家自然科学基金(No. 11371137)

Minimizing makespan on two parallel machines with learning effects

ZHU Zhenglu1 LU Xiwen1,*   

  1. 1. School of Science, East China University of Science and Technology, Shanghai 200237, China
  • Received:2016-08-07 Online:2018-03-15 Published:2018-03-15

PDF

319

摘要：

研究机器带学习效应, 目标函数为时间表长的两台平行机排序问题, 问题是NP-难的. 首先建立了求解该问题最优解的整数规划模型. 其次, 基于模拟退火算法给出了该问题的近似算法SA, 并证明了该算法依概率1 全局收敛到最优解. 最后, 通过数值模拟对所提出的算法进行了性能分析. 数值模拟结果表明, 近似算法SA可以达到最优值的99%, 准确度高, 算法较有效.

关键词: 学习效应, 平行机, 模拟退火算法, 整数规划, 数值模拟

Abstract:

The scheduling problem with learning effects on two parallel machines is considered in the paper. The objective is to minimize the makespan. First, we discuss the NP-hardness of this problem. Next, we establish the integer programming model to find the optimal solution. Then, based on the simulated annealing algorithm, we propose an approximation algorithm SA and prove that the algorithm SA converges to global optimal solution with probability 1. Finally, we analyze the performance of the algorithm SA by numerical simulation. The results of numerical simulation show that the algorithm SA can reach 99% of the optimal value, it is an effective algorithm for the problem.

Key words: learning effects, parallel machines, simulated annealing algorithm, integer programming, numerical simulation