可拆分恒速机排序问题的一个近似算法  

An approximate algorithm for the uniform machine scheduling problem with job splitting property

作　　者：郑秋亚[1,2] 申尊焕[3] 王维琼[1] 

机构地区：[1]长安大学理学院,陕西西安710064 [2]西安电子科技大学理学院,陕西西安710071 [3]西安电子科技大学经济管理学院,陕西西安710071

出　　处：《广西大学学报（自然科学版）》2011年第2期274-278,共5页Journal of Guangxi University（Natural Science Edition）

基　　金：国家自然科学基金资助项目(60974082);中央高校基本科研业务费专项基金资助项目(CHD2010JC101)

摘　　要：为缩短工件的完工时间,研究目标为极小化最大完工时间的可拆分恒速机排序问题。在这个问题中,对工件拆分方式进行了限制,要求尽量少拆分工件,且拆分后子工件长度不小于给定阀值。该问题是NP难的。借助LPT算法的思想,提出了一个近似算法。多个实例的数值结果表明,本文算法可行、性能良好,能获得好的近似最优解。In order to shorten the completion time of the workpiece,a uniform machine scheduling problem with job splitting property to minimize makespan is studied in this paper.The machine scheduling problem,where the size of each section is restricted to be no smaller than a given threshold value,and the number of spited parts should be as small as possible,is a NP-hard problem.An approximate algorithm is developed to solve this problem based on the LPT algorithm.Experimental results show that the proposed algorithm obtains good performance,and results in a good approximate optimum solution.

关 键 词：算法 完工时间 排序 拆分 恒速机 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]