Summary: Mathematical Programming manuscript No.
(will be inserted by the editor)
Alexander Grigoriev · Maxim Sviridenko · Marc Uetz
Machine scheduling with resource dependent
Received: date / Revised version: date
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
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 for the scheduling problem. 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 algorithm for bin packing.