摘要
同类机上工件实时到达的在线排序问题是给定m台分别具有加工速度S1,S2,···,Sm的同类机器M1,M2,···,Mm及实时到达的工件序列L=﹛J1,J2,···,Jn﹜,目标函数是最小化机器的最大完工时间,本文研究了S1=S2=···=Sm-1=1, Sm 】1时同类机上工件实时到达的在线排序问题的LS算法,给出并证明了LS算法的最坏性能比。
Online scheduling problem for jobs arriving over time is as follow. Weare given m related machines M1,M2,···,Mm with the processing speed of S1,S2,···,Sm, respectively and a job list L=﹛J1,J2,···,Jn﹜arriving over time. The objectivefunction is to minimize the maximum completion time of all machines. In thispaper, LS algorithm is considered for online scheduling problem for jobsarriving over time under the assumption S1=S2=···=Sm-1=1, Sm >1. The worst performance ratio of the LS algorithm is given and proved.
出处
《运筹与模糊学》
2019年第4期279-284,共6页
Operations Research and Fuzziology
基金
本文得到湖南省教育厅重点课题(编号:16A126)资助。
