An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities

作者：Fu, Ruyan; Tian, Ji; Li, Shisheng; Yuan, Jinjiang^*

来源：Journal of Combinatorial Optimization, 2017, 34(4): 1187-1197.

DOI：10.1007/s10878-017-0139-8

• Online scheduling
• Batch machine
• Compatibility
• Competitive ratio

We consider the online (over time) scheduling on a single unbounded parallel-batch machine with job processing time compatibilities to minimize makespan. In the problem, a constant alpha > 0 is given in advance. Each job J(j) has a normal processing time p(j). Two jobs J(i) and J(j) are compatible if max{p(i), p(j)} <= (1 + alpha) . min{p(i), p(j)}. In the problem, mutually compatible jobs can form a batch being processed on the machine. The processing time of a batch is equal to the maximum normal processing time of the jobs in this batch. For this problem, we provide an optimal online algorithm with a competitive ratio of 1 + beta(alpha), where beta(alpha) is the positive root of the equation (1 + alpha)x(2) + alpha x = 1 + alpha .

• 出版日期2017-11
• 单位中国矿业大学（北京）; 中原工学院; 郑州大学