Minimizing makespan in batch machine scheduling
We study the scheduling of a set of n jobs, each characterized by a release (arrival) time and a processing time, for a batch processing machine capable of running at most B jobs at a time. We obtain an O(n log n)-time algorithm when B is unbounded. When there are only m distinct release times and the inputs are integers, we obtain an O(n(BRmax)m(-1)(2/m)(m-3))-time algorithm where R-max is the difference between the maximum and minimum release times. When there are k distinct processing times and m release times, we obtain an O(n log m + k(k+2)B(k+1)m(2) log m)-time algorithm. We obtain even better algorithms for m = 2 and for k = 1. These algorithms improve most of the corresponding previous algorithms for the respective special cases and lead to improved approximation schemes for the general problem.
makespan batch machine scheduling dynamic job arrival