Machine scheduling with resource dependent processing times
Grigoriev, A. and Sviridenko, M. and Uetz, M.J. (2007) Machine scheduling with resource dependent processing times. Mathematical programming, 110 (1). pp. 209228. ISSN 00255610
PDF Restricted to UT campus only: Request a copy 298Kb 
Abstract:  We consider machine scheduling on unrelated parallel machines with 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 timeresource 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 4approximation algorithm. We also show how to tune our approach to yield a 3.75approximation 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 algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.

Item Type:  Article 
Copyright:  © 2007 Springer 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/62046 
Official URL:  http://dx.doi.org/10.1007/s1010700600593 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 245841