Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875863 | Theoretical Computer Science | 2017 | 8 Pages |
Abstract
We consider the online (over time) scheduling problem of minimizing the makespan on m unbounded parallel-batch machines, in which jobs in the same batch have to be pairwise compatible. Compatibility is a symmetric binary relation, which is represented by an interval compatibility graph. The processing time of a batch is equal to the maximum processing time of the jobs in it, and all jobs in the same batch start and finish at the same time. For this problem, firstly, we show that there exists no online algorithm with a competitive ratio less than 2. Then we provide an online algorithm with a competitive ratio 2+mâ1m+1, which is optimal for the case m=1. When all jobs have the same processing times, we also give an optimal online algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Qian Wang, Ji Tian, Ruyan Fu, Xiangjuan Yao,