Document Open Access Logo

Approximation Algorithms for Scheduling with Resource and Precedence Constraints

Authors Gökalp Demirci, Henry Hoffmann, David H. K. Kim

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2018.25.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • scheduling
  • resource
  • precedence
  • weighted completion time

Metrics

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

Cite As Get BibTex

Gökalp Demirci, Henry Hoffmann, and David H. K. Kim. Approximation Algorithms for Scheduling with Resource and Precedence Constraints. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.25

Author Details

Gökalp Demirci
Henry Hoffmann
David H. K. Kim

References

  1. John Augustine, Sudarshan Banerjee, and Sandy Irani. Strip packing with precedence constraints and strip packing with release times. In Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '06, pages 180-189, New York, NY, USA, 2006. ACM. Google Scholar
  2. Abbas Bazzi and Ashkan Norouzi-Fard. Towards tight lower bounds for scheduling problems. In Proceedings of the 23rd Annual European Symposium on Algorithms, ESA'15, volume 9294, page 118. Springer, 2015. Google Scholar
  3. Fabián A. Chudak and David B. Shmoys. Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '97, pages 581-590, Philadelphia, PA, USA, 1997. Society for Industrial and Applied Mathematics. Google Scholar
  4. Jr. E. G. Coffman, M. R. Garey, D. S. Johnson, and R. E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4):808-826, 1980. Google Scholar
  5. M. R. Garey and R. L. Grahams. Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4:187-200, 1975. Google Scholar
  6. R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G.Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287-326, 1979. Discrete Optimization II. Google Scholar
  7. Ronald L Graham. Bounds for certain multiprocessing anomalies. Bell Labs Technical Journal, 45(9):1563-1581, 1966. Google Scholar
  8. Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research, 22(3):513-544, 1997. Google Scholar
  9. Klaus Jansen, Marten Maack, and Malin Rau. Approximation schemes for machine scheduling with resource (in-)dependent processing times. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 1526-1542, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. Google Scholar
  10. Peter Kogge, Keren Bergman, Shekhar Borkar, Dan Campbell, William Carlson, William Dally, Monty Denneau, Paul Franzon, William Harrod, Jon Hiller, Sherman Karp, Stephen Keckler, Dean Klein, Robert Lucas, Mark Richards, Al Scarpelli, Steven Scott, Allan Snavely, Thomas Sterling, R. Stanley Williams, Katherine Yelick, Keren Bergman, Shekhar Borkar, Dan Campbell, William Carlson, William Dally, Monty Denneau, Paul Franzon, William Harrod, Jon Hiller, Stephen Keckler, Dean Klein, Peter Kogge, R. Stanley Williams, and Katherine Yelick. Exascale computing study: Technology challenges in achieving exascale systems, 2008. Google Scholar
  11. Shi Li. Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS '17, 2017. Google Scholar
  12. Alix Munier, Maurice Queyranne, and Andreas Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. In Integer Programming and Combinatorial Optimization, IPCO '98, 1998. Google Scholar
  13. Martin Niemeier and Andreas Wiese. Scheduling with an orthogonal resource constraint. In 10th Workshop on Approximation and Online Algorithms (WAOA2012), number EPFL-CONF-181146, 2012. Google Scholar
  14. Maurice Queyranne and Andreas S. Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. SIAM J. Comput., 35(5):1241-1253, 2006. Google Scholar
  15. Maurice Queyranne and Maxim Sviridenko. Approximation algorithms for shop scheduling problems with minsum objective. Journal of Scheduling, 5(4):287-305, 2002. Google Scholar
  16. Vivek Sarkar, Saman Amarasinghe, Dan Campbell, William Carlson, Andrew Chien, William Dally, Elmootazbellah Elnohazy, Mary Hall, Robert Harrison, William Harrod, Kerry Hill, Jon Hiller, Sherman Karp, Charles Koelbel, David Koester, Peter Kogge, John Levesque, Daniel Reed, Robert Schreiber, Mark Richards, Al Scarpelli, John Shalf, Allan Snavely, and Thomas Sterling. Exascale software study: Software challenges in extreme scale systems, 2009. DARPA IPTO Study Report for William Harrod. Google Scholar
  17. Ola Svensson. Conditional hardness of precedence constrained scheduling on identical machines. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC '10, pages 745-754, New York, NY, USA, 2010. ACM. Google Scholar
  18. ExaOSR Team. Exascale operating systems and runtime software report. Online document, URL: https://science.energy.gov/~/media/ascr/pdf/research/cs/Exascale%20Workshop/ExaOSR-Report-Final.pdf.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact