带机器准备时间的同类机调度问题的启发式算法  

Heuristic algorithm for uniform-machine scheduling with machine release times

作　　者：马英[1,2] 杨善林[1,2] 汤大为 

机构地区：[1]合肥工业大学管理学院,合肥230009 [2]过程优化与智能决策教育部重点实验室,合肥230009 [3]Manchester Business School,University of Manchester,Manchester M1 56PB,UK

出　　处：《系统工程理论与实践》2012年第9期2022-2030,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71101040);国家自然科学基金重点项目(71131002);安徽省自然科学基金(11040606Q27;1208085QG133)

摘　　要：研究了带机器准备时间的同类机最大完工时间调度问题,首先证明了工件互换的四个性质.进而提出了一种启发式算法,此算法以LPT算法得到的序列作为初始解,利用互换性质重复对最大完工时间最大和最大完工时间最小的两台机器上的工件进行交换,以提高解的质量.实验结果证明了此算法的有效性.This paper considers a problem of uniform-machine scheduling with machine release times to minimize makespan. Firstly, four properties of swapping jobs are proposed. Then, based on the properties, a heuristic algorithm is presented, which takes the LPT schedule as its initial solution and improves the solution by repeatedly swapping the jobs between two machines with the maximal and minimal makespan. Finally, computational results show that the presented heuristic is efficient and effective.

关 键 词：同类机调度 机器准备时间 LPT 

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