工件具有权重和服务等级约束的平行批在线排序算法

Parallel-batch online scheduling algorithm for workpieces with weight and service level constraints

探讨两台机器上工件具有权重和服务等级约束的平行批在线排序问题。根据工件和机器的特性,有相应的等级约束。工件只能在服务等级不高于自身等级的机器上加工。工件按时在线释放,具有权重和相同的加工时间。机器可以平行批处理工件,在不超过批容量的情形下,多个工件可以用一台机器在一批中同时进行加工。目标函数是最小化所有工件的最大加权完工时间。讨论该问题的时间在线排序算法,给出了在线算法竞争比的下界,并设计了与下界√5+1/2匹配的最好可能的在线算法。

This paper is about the problem of parallel-batch online scheduling on two machines with a grade of service constrains and weight.According to the characteristics of the workpieces and machine,there are corre-sponding level constraints.A workpiece can be processed by a machine if and only if its grade is not higher than that of the machine.Workpieces are released over time,with weight and same processing time.Machines can process jobs in parallel batches,and multiple jobs can be processed simultaneously in a batch using a single ma-chine,without exceeding the batch capacity.The objective is to minimize the maximum weighted completion.The lower bound of the competition ratio of online algorithms is discussed,and the best possible online algorithm is designed to match the lower bound√5+1/2.