Online algorithms for scheduling on batch processing machines with interval graph compatibilities between jobs

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 − 1 m + 1, which is optimal for the case m = 1. When all jobs have the same processing times, we also give an optimal online algorithm.

Authors

• Qian Wang
• Ji Tian
• Ruyan Fu
• Xiangjuan Yao

Keywords

• Online scheduling
• Batch machine
• Compatibility graph
• Competitive ratio