TR-2018-01
Approximation Algorithms for Scheduling with Resource and Precedence Constraints
Gökalp Demirci; Henry Hoffmann; David H. K. Kim. 7 January, 2018.
Communicated by Henry Hoffmann.
Abstract
We study non-preemptive scheduling problems on identical parallel machines and uniformly
related machines under both resource constraints and general precedence constraints between
jobs. Our first result is an O(log n)-approximation algorithm for the objective of minimizing
the makespan on parallel identical machines under resource and general precedence constraints.
We then use this result as a subroutine to obtain an O(log n)-approximation algorithm for the
more general objective of minimizing the total weighted completion time on parallel identical
machines under both constraints. Finally, we present an O(logmlog n)-approximation algorithm
for scheduling under these constraints on uniformly related machines. We show that these results
can all be generalized to include the case where each job has a release time. This is the first
upper bound on the approximability of this class of scheduling problems where both resource
and general precedence constraints must be satisfied simultaneously.
Original Document
The original document is available in PDF (uploaded 7 January, 2018 by
Henry Hoffmann).
