Minimizing makespan in batch machine scheduling

Minimizing makespan in batch machine scheduling

0.00 Avg rating0 Votes
Article ID: iaor20053067
Country: Germany
Volume: 39
Issue: 2
Start Page Number: 155
End Page Number: 174
Publication Date: Feb 2004
Journal: Algorithmica
Authors: ,
Abstract:

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 Rmax 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 + kk+2Bk+1m2 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.

Reviews

Required fields are marked *. Your email address will not be published.