可拆分平行机排序问题的一个启发式算法  

A Heuristic Algorithm for Parallel Machine Scheduling Problem with Job Splitting Property

作　　者：郑秋亚[1,2] 刘三阳[1] 杨尊袍[3] 

机构地区：[1]西安电子科技大学理学院,陕西西安710071 [2]长安大学理学院,陕西西安710064 [3]空军工程大学理学院,陕西西安710051

出　　处：《空军工程大学学报（自然科学版）》2010年第4期84-88,共5页Journal of Air Force Engineering University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60574075)

摘　　要：为缩短工件的完工时间,将极小化最大完工时间的平行机排序问题作为研究目标。在此问题中,允许同一工件拆分成多个子工件在不同的机器上同时加工,同一工件的任何2个子工件不可在同一台机器上加工。与以往研究不同,对工件的拆分方式进行了限制,即工件拆分后所得子工件的长度不能小于给定的阀值,且工件拆分次数尽量少,这是一个NP难问题。借助于LPT算法的思想,提出了一个求解该问题的启发式算法,实现了工件的自动拆分和工件到机器上的自动分配。通过多个实例对文中算法进行了测试,数值结果表明:该算法可行、稳定性良好,适用于工件拆分方式具有类似限制的平行机排序问题的方案决策。An identical parallel machine scheduling problem with job splitting to minimize makespan is studied to decrease the completion time of the job.In this problem,each job can be split into sections,which can be processed in parallel on different machines.There is at most one part of each job on a machine.Different from researches in the scheduling literatures,there is a restriction for the split,i.e.the size of each split section cannot be smaller than a given value and the splitting actions should be kept as less as possible in the number of times.For this NP-hard problem,a heuristic algorithm is developed based on the LPT algorithm.Using the algorithm,job is split and assigned automatically.The performance of the algorithm is evaluated through a number of numerical instances.The results show that the algorithm is feasible and fine in stability.This algorithm can be applied to solving parallel machine scheduling problem,in which the split has the similar restriction.

关 键 词：启发式算法 最大完工时间 排序 拆分 平行机 

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