Scheduling with batching: Two job types

In this paper we present an algorithm for the 2-weight batching problem: given nl jobs with weight w(1), and n(2) jobs with weight w(2), all having processing time p, and given a batch setup time Delta, find a sequence of batches of jobs such that the weighted sum of the n = n(1) + n(2) job completion times is minimized. The algorithm has running time O(root n log n) when p and Delta are fixed; previously, the fastest known algorithm for this problem had running lime O(n). Various properties of optimal solutions are exploited to reduce the problem to one of finding the minimum entry in a certain matrix. Since this matrix has some strong structural properties, its minimum entry can be found in time that is a sublinear function of the matrix size.