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.


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).