2026-07-22T12:14:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8531 2024-03-06T10:42:18Z ddc:004 open_access

Approximation Algorithms for Scheduling with Resource and Precedence Constraints Demirci, Gökalp Hoffmann, Henry Kim, David H. K. scheduling resource precedence weighted completion time 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(logn)-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(logn)-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(logm logn)-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gökalp Demirci and Henry Hoffmann and David H. K. Kim 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.25 urn:nbn:de:0030-drops-85319 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.25 eng https://creativecommons.org/licenses/by/3.0/legalcode