Heuristic algorithms for scheduling on uniform parallel machines with heads and tails  

作　　者：Kai Li Shanlin Yang 

机构地区：[1]School of Management,Hefei University of Technology,Hefei 230009,P.R.China [2]Key Laboratory of Process Optimization and Intelligent Decision-making,Ministry of Education,Hefei University of Technology,Hefei 230009,P.R.China

出　　处：《Journal of Systems Engineering and Electronics》2011年第3期462-467,共6页系统工程与电子技术(英文版)

基　　金：supported by the National Natural Science Foundation of China (70871032;90924021;70971035);the National High Technology Research and Development Program of China (863 Program) (2008AA042901);Anhui Provincial Natural Science Foundation (11040606Q27)

摘　　要：This paper considers the uniform parallel machine scheduling problem with unequal release dates and delivery times to minimize the maximum completion time.For this NP-hard problem,the largest sum of release date,processing time and delivery time first rule is designed to determine a certain machine for each job,and the largest difference between delivery time and release date first rule is designed to sequence the jobs scheduled on the same machine,and then a novel algorithm for the scheduling problem is built.To evaluate the performance of the proposed algorithm,a lower bound for the problem is proposed.The accuracy of the proposed algorithm is tested based on the data with problem size varying from 200 jobs to 600 jobs.The computational results indicate that the average relative error between the proposed algorithm and the lower bound is only 0.667%,therefore the solutions obtained by the proposed algorithm are very accurate.This paper considers the uniform parallel machine scheduling problem with unequal release dates and delivery times to minimize the maximum completion time.For this NP-hard problem,the largest sum of release date,processing time and delivery time first rule is designed to determine a certain machine for each job,and the largest difference between delivery time and release date first rule is designed to sequence the jobs scheduled on the same machine,and then a novel algorithm for the scheduling problem is built.To evaluate the performance of the proposed algorithm,a lower bound for the problem is proposed.The accuracy of the proposed algorithm is tested based on the data with problem size varying from 200 jobs to 600 jobs.The computational results indicate that the average relative error between the proposed algorithm and the lower bound is only 0.667%,therefore the solutions obtained by the proposed algorithm are very accurate.

关 键 词：SCHEDULING parallel machine UNIFORM release date/head delivery time/tail. 

分 类 号：TH186[机械工程—机械制造及自动化]