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

Online Scheduling Problem for Jobs Arriving over Time on Related Machines

摘要: 同类机上工件实时到达的在线排序问题是给定m台分别具有加工速度S₁，S_{2，···，}S_m的同类机器M₁，M_{2，···，}M_m及实时到达的工件序列L=﹛J₁，J_{2，···，}J_n﹜，目标函数是最小化机器的最大完工时间，本文研究了S₁=S₂=_···=S_m-1=1, S_m >1时同类机上工件实时到达的在线排序问题的LS算法，给出并证明了LS算法的最坏性能比。

Abstract: Online scheduling problem for jobs arriving over time is as follow. We are given m related machines M₁，M_{2，···，}M_m with the processing speed of S₁，S_{2，···，}S_m, respectively and a job list L=﹛J₁，J_{2，···，}J_n﹜arriving over time. The objective function is to minimize the maximum completion time of all machines. In this paper, LS algorithm is considered for online scheduling problem for jobs arriving over time under the assumption S₁=S₂=_···=S_m-1=1, S_m >1. The worst performance ratio of the LS algorithm is given and proved.