Scheduling with Batching: Two Job Types


In this paper we present an algorithm for the 2-weight batching problem: given n_1 jobs with weight w_1, and n_2 jobs with weight w_2, all having processing time p, and given a batch setup time , 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(n^0.5 logn) when p and are fixed; previously, the fastest known algorithm for this problem had running time 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.

Download Information

Click on the following title to view and download the paper in PostScript format.

Scheduling with Batching: Two Job Types (14 pages, 145 KB)
Dorit S. Hochbaum and D. Landy. Discrete Applied Math, 72, 99-114, (1997).