LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times


Grigoriev, A. and Sviridenko, M. and Uetz, M.J. (2006) LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 28-30 August 2006, Barcelona, Spain.

Restricted to UT campus only
: Request a copy
Abstract:We consider a scheduling problem on unrelated parallel machines with the objective to minimize the makespan. In addition to its machine dependence, the processing time of any job is dependent on the usage of a scarce renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time. The more of the 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 by Shmoys and Tardos. On the basis of an integer linear programming formulation for (a relaxation of) the problem, we adopt a randomized LP rounding technique from Kumar et al. (FOCS 2005) in order to obtain a deterministic, integral LP solution that is close to optimum. We show how this rounding procedure can be used to derive a deterministic 3.75-approximation algorithm for the scheduling problem. This improves upon previous results, namely a deterministic 6.83-approximation, and a randomized 4-approximation. The improvement is due to the better LP rounding and a new scheduling algorithm that can be viewed as a restricted version of the harmonic algorithm for bin packing.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62212
Official URL:http://dx.doi.org/10.1007/11830924_15
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page