Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times
This article studies online scheduling of equal length jobs with precedence constraints on m parallel batching machines. The jobs arrive over time. The objective is to minimise the total weighted completion time of jobs. Denote the size of each batch by b with b = in the unbounded batching and b in the bounded batching. For the unbounded batching version, we provide an online algorithm with a best possible competitive ratio of m, where m is the positive solution of m+1 - = 1. The algorithm is also best possible when the jobs have identical weights. For the bounded batching version with identical weights of jobs, we provide an online algorithm with a competitive ratio of 2.
online scheduling precedence constraints parallel batch