IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v235y2015i1p319-33610.1007-s10479-015-1993-3.html
   My bibliography  Save this article

Approximability of scheduling problems with resource consuming jobs

Author

Listed:
  • Péter Györgyi
  • Tamás Kis

Abstract

The paper presents new approximability results for single machine scheduling problems with jobs requiring some non-renewable resources (like raw materials, energy, or money) beside the machine. Each resource has an initial stock and additional supplies over time. A feasible schedule specifies a starting time for each job such that no two jobs overlap in time, and when a job is started, enough resources are available to cover its requirements. The goal is to find a feasible schedule of minimum makespan. This problem is strongly NP-hard. Recently, the authors of this paper have proposed a PTAS for the special case with a single non-renewable resource and with a constant number of supply dates, as well as an FPTAS for the special case with two supply dates and one resource only. In this paper we prove APX-hardness of the problem when the number of resources is part of the input, and new polynomial time approximation schemes are devised for some variants, including (1) job release dates, and more than one, but constant number of resources and resource supply dates, and (2) only one resource, arbitrary number of supply dates and job release dates, but with resource requirements proportional to job processing times. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • Péter Györgyi & Tamás Kis, 2015. "Approximability of scheduling problems with resource consuming jobs," Annals of Operations Research, Springer, vol. 235(1), pages 319-336, December.
    • Handle: RePEc:spr:annopr:v:235:y:2015:i:1:p:319-336:10.1007/s10479-015-1993-3
    DOI: 10.1007/s10479-015-1993-3
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-015-1993-3
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-015-1993-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Alexander Grigoriev & Martijn Holthuijsen & Joris van de Klundert, 2005. "Basic scheduling problems with raw material constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(6), pages 527-535, September.
    2. Evgeny Gafarov & Alexander Lazarev & Frank Werner, 2014. "Approximability results for the resource-constrained project scheduling problem with a single type of resources," Annals of Operations Research, Springer, vol. 213(1), pages 115-130, February.
    3. Slowinski, Roman, 1984. "Preemptive scheduling of independent jobs on parallel machines subject to financial constraints," European Journal of Operational Research, Elsevier, vol. 15(3), pages 366-373, March.
    4. E. L. Lawler, 1973. "Optimal Sequencing of a Single Machine Subject to Precedence Constraints," Management Science, INFORMS, vol. 19(5), pages 544-546, January.
    5. Lisa Fleischer & Michel X. Goemans & Vahab S. Mirrokni & Maxim Sviridenko, 2011. "Tight Approximation Algorithms for Maximum Separable Assignment Problems," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 416-431, August.
    6. Gafarov, Evgeny R. & Lazarev, Alexander A. & Werner, Frank, 2011. "Single machine scheduling problems with financial resource constraints: Some complexity results and properties," Mathematical Social Sciences, Elsevier, vol. 62(1), pages 7-13, July.
    7. Christoph Ambühl & Monaldo Mastrolilli & Nikolaus Mutsanas & Ola Svensson, 2011. "On the Approximability of Single-Machine Scheduling with Precedence Constraints," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 653-669, November.
    8. Briskorn, Dirk & Choi, Byung-Cheon & Lee, Kangbok & Leung, Joseph & Pinedo, Michael, 2010. "Complexity of single machine scheduling subject to nonnegative inventory constraints," European Journal of Operational Research, Elsevier, vol. 207(2), pages 605-619, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    2. Susumu Hashimoto & Shinji Mizuno, 2021. "A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource," Journal of Scheduling, Springer, vol. 24(3), pages 259-267, June.
    3. Péter Györgyi & Tamás Kis, 2019. "Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints," Journal of Scheduling, Springer, vol. 22(6), pages 623-634, December.
    4. Györgyi, Péter & Kis, Tamás, 2017. "Approximation schemes for parallel machine scheduling with non-renewable resources," European Journal of Operational Research, Elsevier, vol. 258(1), pages 113-123.
    5. Davari, Morteza & Ranjbar, Mohammad & De Causmaecker, Patrick & Leus, Roel, 2020. "Minimizing makespan on a single machine with release dates and inventory constraints," European Journal of Operational Research, Elsevier, vol. 286(1), pages 115-128.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Györgyi, Péter & Kis, Tamás, 2017. "Approximation schemes for parallel machine scheduling with non-renewable resources," European Journal of Operational Research, Elsevier, vol. 258(1), pages 113-123.
    2. Péter Györgyi & Tamás Kis, 2019. "Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints," Journal of Scheduling, Springer, vol. 22(6), pages 623-634, December.
    3. Davari, Morteza & Ranjbar, Mohammad & De Causmaecker, Patrick & Leus, Roel, 2020. "Minimizing makespan on a single machine with release dates and inventory constraints," European Journal of Operational Research, Elsevier, vol. 286(1), pages 115-128.
    4. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    5. Susumu Hashimoto & Shinji Mizuno, 2021. "A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource," Journal of Scheduling, Springer, vol. 24(3), pages 259-267, June.
    6. Oron, Daniel & Shabtay, Dvir & Steiner, George, 2015. "Single machine scheduling with two competing agents and equal job processing times," European Journal of Operational Research, Elsevier, vol. 244(1), pages 86-99.
    7. Wu, Xianyi & Zhou, Xian, 2008. "Stochastic scheduling to minimize expected maximum lateness," European Journal of Operational Research, Elsevier, vol. 190(1), pages 103-115, October.
    8. Enrique Gerstl & Gur Mosheiov, 2020. "Single machine scheduling to maximize the number of on-time jobs with generalized due-dates," Journal of Scheduling, Springer, vol. 23(3), pages 289-299, June.
    9. Ramachandra, Girish & Elmaghraby, Salah E., 2006. "Sequencing precedence-related jobs on two machines to minimize the weighted completion time," International Journal of Production Economics, Elsevier, vol. 100(1), pages 44-58, March.
    10. Bachtenkirch, David & Bock, Stefan, 2022. "Finding efficient make-to-order production and batch delivery schedules," European Journal of Operational Research, Elsevier, vol. 297(1), pages 133-152.
    11. Rubing Chen & Jinjiang Yuan, 2020. "Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices," 4OR, Springer, vol. 18(2), pages 177-196, June.
    12. Reha Uzsoy & Chung‐Yee Lee & Louis A. Martin‐Vega, 1992. "Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(3), pages 369-388, April.
    13. Anna Arigliano & Gianpaolo Ghiani & Antonio Grieco & Emanuela Guerriero, 2017. "Single-machine time-dependent scheduling problems with fixed rate-modifying activities and resumable jobs," 4OR, Springer, vol. 15(2), pages 201-215, June.
    14. Adam Kasperski & Paweł Zieliński, 2019. "Risk-averse single machine scheduling: complexity and approximation," Journal of Scheduling, Springer, vol. 22(5), pages 567-580, October.
    15. Lingfa Lu & Liqi Zhang, 2017. "Online Single Machine Scheduling to Minimize the Maximum Starting Time," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(05), pages 1-9, October.
    16. Jiang, Xiaojuan & Lee, Kangbok & Pinedo, Michael L., 2021. "Ideal schedules in parallel machine settings," European Journal of Operational Research, Elsevier, vol. 290(2), pages 422-434.
    17. Zhichao Geng & Jiayu Liu, 0. "Single machine batch scheduling with two non-disjoint agents and splitable jobs," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-22.
    18. Cheng, T. C. E. & Ng, C. T. & Yuan, J. J. & Liu, Z. H., 2005. "Single machine scheduling to minimize total weighted tardiness," European Journal of Operational Research, Elsevier, vol. 165(2), pages 423-443, September.
    19. Alessandro Agnetis & Dario Pacciarelli & Andrea Pacifici, 2007. "Multi-agent single machine scheduling," Annals of Operations Research, Springer, vol. 150(1), pages 3-15, March.
    20. Christian L. Cesar & Peter G. Jessel, 1992. "Real‐time task scheduling with overheads considered," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 247-264, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:235:y:2015:i:1:p:319-336:10.1007/s10479-015-1993-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.