IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v26y2023i2d10.1007_s10951-022-00754-6.html
   My bibliography  Save this article

Equitable scheduling on a single machine

Author

Listed:
  • Klaus Heeger

    (Algorithmics and Computational Complexity, Faculty IV, TU Berlin)

  • Danny Hermelin

    (Ben-Gurion University of the Negev)

  • George B. Mertzios

    (Durham University)

  • Hendrik Molter

    (Ben-Gurion University of the Negev)

  • Rolf Niedermeier

    (Algorithmics and Computational Complexity, Faculty IV, TU Berlin)

  • Dvir Shabtay

    (Ben-Gurion University of the Negev)

Abstract

We introduce a natural but seemingly yet unstudied variant of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. The novelty of our new variant lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least $$k \le m$$ k ≤ m days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of m days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results.

Suggested Citation

  • Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    • Handle: RePEc:spr:jsched:v:26:y:2023:i:2:d:10.1007_s10951-022-00754-6
    DOI: 10.1007/s10951-022-00754-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-022-00754-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-022-00754-6?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. Hermelin, Danny & Pinedo, Michael & Shabtay, Dvir & Talmon, Nimrod, 2019. "On the parameterized tractability of single machine scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 273(1), pages 67-73.
    2. Edmund Burke & Michael Pinedo, 2019. "Journal of scheduling (2019)," Journal of Scheduling, Springer, vol. 22(1), pages 1-2, February.
    3. Vincent T’kindt & Lei Shang & Federico Della Croce, 2020. "Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 764-775, April.
    4. Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2000. "A Time-Oriented Branch-and-Bound Algorithm for Resource-Constrained Project Scheduling with Generalised Precedence Constraints," Management Science, INFORMS, vol. 46(10), pages 1365-1384, October.
    5. S. S. Panwalkar & M. L. Smith & A. Seidmann, 1982. "Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem," Operations Research, INFORMS, vol. 30(2), pages 391-399, April.
    6. Danny Hermelin & Dvir Shabtay & Nimrod Talmon, 2019. "On the parameterized tractability of the just-in-time flow-shop scheduling problem," Journal of Scheduling, Springer, vol. 22(6), pages 663-676, December.
    7. Tianyu Wang & Odile Bellenguez-Morineau, 2019. "The Complexity of Parallel Machine Scheduling of Unit-Processing-Time Jobs under Level-Order Precedence Constraints," Journal of Scheduling, Springer, vol. 22(3), pages 263-269, June.
    8. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2011. "The Price of Fairness," Operations Research, INFORMS, vol. 59(1), pages 17-31, February.
    9. Kerem Bülbül & Safia Kedad-Sidhoum & Halil Şen, 2019. "Single-machine common due date total earliness/tardiness scheduling with machine unavailability," Journal of Scheduling, Springer, vol. 22(5), pages 543-565, October.
    10. de Weerdt, Mathijs & Baart, Robert & He, Lei, 2021. "Single-machine scheduling with release times, deadlines, setup times, and rejection," European Journal of Operational Research, Elsevier, vol. 291(2), pages 629-639.
    11. Mosheiov, Gur & Yovel, Uri, 2006. "Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs," European Journal of Operational Research, Elsevier, vol. 172(2), pages 528-544, July.
    12. Uttarayan Bagchi & Robert S. Sullivan & Yih-Long Chang, 1987. "Minimizing Mean Squared Deviation of Completion Times About a Common Due Date," Management Science, INFORMS, vol. 33(7), pages 894-906, July.
    13. J. Michael Moore, 1968. "An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs," Management Science, INFORMS, vol. 15(1), pages 102-109, September.
    14. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    15. Lenstra, J. K. & Rinnooy Kan, A. H. G., 1980. "Complexity results for scheduling chains on a single machine," European Journal of Operational Research, Elsevier, vol. 4(4), pages 270-275, April.
    16. René Bevern & Rolf Niedermeier & Ondřej Suchý, 2017. "A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack," Journal of Scheduling, Springer, vol. 20(3), pages 255-265, June.
    17. William L. Maxwell, 1970. "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," Management Science, INFORMS, vol. 16(5), pages 295-297, January.
    18. José R. Correa & Andreas S. Schulz, 2005. "Single-Machine Scheduling with Precedence Constraints," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 1005-1021, November.
    19. J. K. Lenstra & A. H. G. Rinnooy Kan, 1978. "Complexity of Scheduling under Precedence Constraints," Operations Research, INFORMS, vol. 26(1), pages 22-35, February.
    20. Nikhil Bansal & Tracy Kimbrel & Maxim Sviridenko, 2006. "Job Shop Scheduling with Unit Processing Times," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 381-389, May.
    21. Renhua Li & Leonie U Hempel & Tingbo Jiang, 2015. "A Non-Parametric Peak Calling Algorithm for DamID-Seq," PLOS ONE, Public Library of Science, vol. 10(3), pages 1-12, March.
    22. Matthias Bentert & René Bevern & Rolf Niedermeier, 2019. "Inductive $$k$$ k -independent graphs and c-colorable subgraphs in scheduling: a review," Journal of Scheduling, Springer, vol. 22(1), pages 3-20, February.
    23. Shabtay, Dvir & Arviv, Kfir & Stern, Helman & Edan, Yael, 2014. "A combined robot selection and scheduling problem for flow-shops with no-wait restrictions," Omega, Elsevier, vol. 43(C), pages 96-107.
    24. Jérôme Lang & Jörg Rothe, 2016. "Fair Division of Indivisible Goods," Springer Texts in Business and Economics, in: Jörg Rothe (ed.), Economics and Computation, edition 1, chapter 0, pages 493-550, Springer.
    Full references (including those not matched with items on IDEAS)

    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. Danny Hermelin & Dvir Shabtay & Chen Zelig & Michael Pinedo, 2022. "A general scheme for solving a large set of scheduling problems with rejection in FPT time," Journal of Scheduling, Springer, vol. 25(2), pages 229-255, April.
    2. 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.
    3. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    4. Danny Hermelin & Shlomo Karhi & Michael Pinedo & Dvir Shabtay, 2021. "New algorithms for minimizing the weighted number of tardy jobs on a single machine," Annals of Operations Research, Springer, vol. 298(1), pages 271-287, March.
    5. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    6. Dvir Shabtay, 2023. "A new perspective on single-machine scheduling problems with late work related criteria," Annals of Operations Research, Springer, vol. 322(2), pages 947-966, March.
    7. Timkovsky, Vadim G., 2003. "Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity," European Journal of Operational Research, Elsevier, vol. 149(2), pages 355-376, September.
    8. D. Prot & O. Bellenguez-Morineau, 2018. "A survey on how the structure of precedence constraints may change the complexity class of scheduling problems," Journal of Scheduling, Springer, vol. 21(1), pages 3-16, February.
    9. Hermelin, Danny & Kubitza, Judith-Madeleine & Shabtay, Dvir & Talmon, Nimrod & Woeginger, Gerhard J., 2019. "Scheduling two agents on a single machine: A parameterized analysis of NP-hard problems," Omega, Elsevier, vol. 83(C), pages 275-286.
    10. 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.
    11. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    12. Vincent T’kindt & Federico Della Croce & Mathieu Liedloff, 2022. "Moderate exponential-time algorithms for scheduling problems," 4OR, Springer, vol. 20(4), pages 533-566, December.
    13. Ma, Ran & Guo, Sainan, 2021. "Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 290(1), pages 57-67.
    14. Mosheiov, Gur & Oron, Daniel & Shabtay, Dvir, 2021. "Minimizing total late work on a single machine with generalized due-dates," European Journal of Operational Research, Elsevier, vol. 293(3), pages 837-846.
    15. Huynh Tuong, Nguyen & Soukhal, Ameur, 2010. "Due dates assignment and JIT scheduling with equal-size jobs," European Journal of Operational Research, Elsevier, vol. 205(2), pages 280-289, September.
    16. 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.
    17. Tzafestas, Spyros & Triantafyllakis, Alekos, 1993. "Deterministic scheduling in computing and manufacturing systems: a survey of models and algorithms," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 35(5), pages 397-434.
    18. Markó Horváth & Tamás Kis, 2020. "Polyhedral results for position-based scheduling of chains on a single machine," Annals of Operations Research, Springer, vol. 284(1), pages 283-322, January.
    19. Gordon, Valery & Proth, Jean-Marie & Chu, Chengbin, 2002. "A survey of the state-of-the-art of common due date assignment and scheduling research," European Journal of Operational Research, Elsevier, vol. 139(1), pages 1-25, May.
    20. Lushchakova, Irene N., 2000. "Minimizing functions of infeasibilities in a two-machine flow shop," European Journal of Operational Research, Elsevier, vol. 121(2), pages 380-393, 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:jsched:v:26:y:2023:i:2:d:10.1007_s10951-022-00754-6. 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.