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

Minimizing makespan on two parallel machines with learning effects

作　　者：朱征露 鲁习文[1] 

机构地区：[1]华东理工大学理学院,上海200237

出　　处：《运筹学学报》2018年第1期55-66,共12页Operations Research Transactions

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

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

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

分 类 号：O221.7[理学—运筹学与控制论]