文献类型：期刊文献

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

英文题名：Minimizing makespan on two parallel machines with learning effects

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

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

年份：2018

卷号：22

期号：1

起止页码：55

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

收录：CSTPCD;;北大核心:【北大核心2017】；CSCD:【CSCD2017_2018】；

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

语种：中文

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

外文关键词：learning effects, parallel machines, simulated annealing algorithm, inte-ger programming, numerical simulation

摘要：研究机器带学习效应,目标函数为时间表长的两台平行机排序问题,问题是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.