同类机上工件实时到达在线排序问题  

Online Scheduling Problem for Jobs Arriving over Time on Related Machines

作　　者：马丽娜 李荣珩 

机构地区：[1]计算与随机数学教育部重点实验室 湖南师范大学数学与统计学院,湖南 长沙 沅陵县第一中学,湖南 怀化 [2]计算与随机数学教育部重点实验室 湖南师范大学数学与统计学院,湖南 长沙

出　　处：《运筹与模糊学》2019年第4期279-284,共6页Operations Research and Fuzziology

基　　金：本文得到湖南省教育厅重点课题(编号:16A126)资助。

摘　　要：同类机上工件实时到达的在线排序问题是给定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.

关 键 词：排序问题 相关平行机 LS算法 最坏性能比 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]