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.