Affordable Access

Download Read

Machine scheduling with resource dependent processing times.



Math. Program., Ser. B (2007) 110:209–228 DOI 10.1007/s10107-006-0059-3 FULL LENGTH PAPER Machine scheduling with resource dependent processing times Alexander Grigoriev · Maxim Sviridenko · Marc Uetz Received: 28 June 2005 / Accepted: 18 July 2006 / Published online: 12 December 2006 © Springer-Verlag 2006 Abstract Weconsidermachine scheduling onunrelatedparallelmachineswith the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algo- A. Grigoriev · M. Uetz (B) Maastricht University, Quantitative Economics, P.O. Box 616, 6200 MD Maastricht, The Netherlands e-mail: [email protected] A. Grigoriev e-mail: [email protected] M. Sviridenko IBM T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, USA e-mail: [email protected] 210 A. Grigoriev et al. rithm for bin packing.We finally derive inapproximability results for two special cases, and discuss tightness of

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times
Downloaded <100 times