Unrelated parallel machine scheduling with resource dependent processing times

Grigoriev, A. and Sviridenko, M. and Uetz, M.J. (2006) Unrelated parallel machine scheduling with resource dependent processing times. In: Integer Programming and Combinatorial Optimization, 11th International IPCO Conference, 8-10 June, 2005, Berlin, Germany.

PDF
Restricted to UT campus only: Request a copy
200Kb

Abstract:	We consider unrelated parallel machine scheduling problems with the objective to minimize the schedule makespan. In addition to its machine-dependence, the processing time of any job is also dependent on the usage of a scarce renewable resource. An amount of $k$ units of that resource, e.g. workers, can be distributed over the jobs in process, and the more of that resource is allocated to a job, the smaller its processing time. The model generalizes the classical unrelated machine scheduling problem, adding a resource-time tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos, the difference lying in the fact the resource is renewable and not a total budget constraint. We use a two-phased LP rounding technique to assign resources to jobs and jobs to machines. Combined with Graham's list scheduling, we thus prove the existence of a $(4+2\sqrt{2})$ -approximation algorithm. We show how our approach can be adapted to scheduling problems with dedicated machines as well, with an improvement of the performance bound to $(3+2\sqrt{2})$ . Moreover, we derive a lower bound of 2 for the employed LP-based analysis, and we prove a (3/2)-inapproximability result.
Item Type:	Conference or Workshop Item
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/62218
Official URL:	http://dx.doi.org/10.1007/11496915_14
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page