IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v322y2025i2p467-479.html
   My bibliography  Save this article

Single-machine preemptive scheduling with assignable due dates or assignable weights to minimize total weighted late work

Author

Listed:
  • Chen, Rubing
  • Dong, Xinyu
  • Yuan, Jinjiang
  • Ng, C.T.
  • Cheng, T.C.E.

Abstract

In this paper we study single-machine preemptive scheduling to minimize the total weighted late work with assignable due dates or assignable weights. For the problem with assignable due dates, we show that it is binary NP-hard, solvable in pseudo-polynomial time, and solvable in polynomial time when all the jobs have agreeable processing times and weights. For the problem with assignable weights, we show that it is solvable in polynomial time. For the problem with assignable due dates and assignable weights, we show that it is binary NP-hard, solvable in pseudo-polynomial time, and solvable in polynomial time when all the jobs have the same processing times.

Suggested Citation

  • Chen, Rubing & Dong, Xinyu & Yuan, Jinjiang & Ng, C.T. & Cheng, T.C.E., 2025. "Single-machine preemptive scheduling with assignable due dates or assignable weights to minimize total weighted late work," European Journal of Operational Research, Elsevier, vol. 322(2), pages 467-479.
    • Handle: RePEc:eee:ejores:v:322:y:2025:i:2:p:467-479
    DOI: 10.1016/j.ejor.2024.11.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724008610
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.11.010?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. Justkowiak, Jan-Erik & Kovalev, Sergey & Kovalyov, Mikhail Y. & Pesch, Erwin, 2023. "Single machine scheduling with assignable due dates to minimize maximum and total late work," European Journal of Operational Research, Elsevier, vol. 308(1), pages 76-83.
    2. 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.
    3. Yunqiang Yin & Jianyou Xu & T. C. E. Cheng & Chin‐Chia Wu & Du‐Juan Wang, 2016. "Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 172-183, March.
    4. 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.
    5. Shabtay, Dvir & Steiner, George & Zhang, Rui, 2016. "Optimal coordination of resource allocation, due date assignment and scheduling decisions," Omega, Elsevier, vol. 65(C), pages 41-54.
    6. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    7. Shabtay, Dvir & Mosheiov, Gur & Oron, Daniel, 2022. "Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work," European Journal of Operational Research, Elsevier, vol. 303(1), pages 66-77.
    8. M. Y. Kovalyov & C. N. Potts & L. N. van Wassenhove, 1994. "A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work," Mathematics of Operations Research, INFORMS, vol. 19(1), pages 86-93, February.
    9. 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.
    10. Shi-Sheng Li & Ren-Xia Chen, 2022. "Minimizing total weighted late work on a single-machine with non-availability intervals," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1330-1355, September.
    11. 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.
    12. C. N. Potts & L. N. Van Wassenhove, 1992. "Single Machine Scheduling to Minimize Total Late Work," Operations Research, INFORMS, vol. 40(3), pages 586-595, June.
    13. Janiak, Adam & Janiak, Władysław A. & Krysiak, Tomasz & Kwiatkowski, Tomasz, 2015. "A survey on scheduling problems with due windows," European Journal of Operational Research, Elsevier, vol. 242(2), pages 347-357.
    14. Chen, Rubing & Geng, Zhichao & Lu, Lingfa & Yuan, Jinjiang & Zhang, Yuan, 2022. "Pareto-scheduling of two competing agents with their own equal processing times," European Journal of Operational Research, Elsevier, vol. 301(2), pages 414-431.
    15. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    16. Rubing Chen & Yuan Gao & Zhichao Geng & Jinjiang Yuan, 2023. "Revisit the scheduling problem with assignable or generalized due dates to minimize total weighted late work," International Journal of Production Research, Taylor & Francis Journals, vol. 61(22), pages 7630-7648, November.
    17. Blazewicz, Jacek & Pesch, Erwin & Sterna, Malgorzata & Werner, Frank, 2005. "The two-machine flow-shop problem with weighted late work criterion and common due date," European Journal of Operational Research, Elsevier, vol. 165(2), pages 408-415, September.
    18. Shi-Sheng Li & Jin-Jiang Yuan, 2020. "Single-machine scheduling with multi-agents to minimize total weighted late work," Journal of Scheduling, Springer, vol. 23(4), pages 497-512, August.
    19. Sang, Yao-Wen & Wang, Jun-Qiang & Sterna, Małgorzata & Błażewicz, Jacek, 2023. "Single machine scheduling with due date assignment to minimize the total weighted lead time penalty and late work," Omega, Elsevier, vol. 121(C).
    20. A. M. A. Hariri & C. N. Potts & L. N. Van Wassenhove, 1995. "Single Machine Scheduling to Minimize Total Weighted Late Work," INFORMS Journal on Computing, INFORMS, vol. 7(2), pages 232-242, May.
    21. Cheng, T. C. E. & Gupta, M. C., 1989. "Survey of scheduling research involving due date determination decisions," European Journal of Operational Research, Elsevier, vol. 38(2), pages 156-166, January.
    22. Wang, Du-Juan & Yin, Yunqiang & Xu, Jianyou & Wu, Wen-Hsiang & Cheng, Shuenn-Ren & Wu, Chin-Chia, 2015. "Some due date determination scheduling problems with two agents on a single machine," International Journal of Production Economics, Elsevier, vol. 168(C), pages 81-90.
    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. Sang, Yao-Wen & Wang, Jun-Qiang & Sterna, Małgorzata & Błażewicz, Jacek, 2023. "Single machine scheduling with due date assignment to minimize the total weighted lead time penalty and late work," Omega, Elsevier, vol. 121(C).
    2. Shabtay, Dvir & Mosheiov, Gur & Oron, Daniel, 2022. "Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work," European Journal of Operational Research, Elsevier, vol. 303(1), pages 66-77.
    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. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    5. 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.
    6. Shi-Sheng Li & Ren-Xia Chen, 2022. "Minimizing total weighted late work on a single-machine with non-availability intervals," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1330-1355, September.
    7. Shi-Sheng Li & Jin-Jiang Yuan, 2020. "Single-machine scheduling with multi-agents to minimize total weighted late work," Journal of Scheduling, Springer, vol. 23(4), pages 497-512, August.
    8. 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.
    9. Chen, Xin & Liang, Yage & Sterna, Małgorzata & Wang, Wen & Błażewicz, Jacek, 2020. "Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date," European Journal of Operational Research, Elsevier, vol. 284(1), pages 67-74.
    10. Malgorzata Sterna & Kateryna Czerniachowska, 2017. "Polynomial Time Approximation Scheme for Two Parallel Machines Scheduling with a Common Due Date to Maximize Early Work," Journal of Optimization Theory and Applications, Springer, vol. 174(3), pages 927-944, September.
    11. Chen, Xin & Miao, Qian & Lin, Bertrand M.T. & Sterna, Malgorzata & Blazewicz, Jacek, 2022. "Two-machine flow shop scheduling with a common due date to maximize total early work," European Journal of Operational Research, Elsevier, vol. 300(2), pages 504-511.
    12. Justkowiak, Jan-Erik & Kovalev, Sergey & Kovalyov, Mikhail Y. & Pesch, Erwin, 2023. "Single machine scheduling with assignable due dates to minimize maximum and total late work," European Journal of Operational Research, Elsevier, vol. 308(1), pages 76-83.
    13. Rubing Chen & Jinjiang Yuan & C.T. Ng & T.C.E. Cheng, 2019. "Single‐machine scheduling with deadlines to minimize the total weighted late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 582-595, October.
    14. Yunqiang Yin & Jianyou Xu & T. C. E. Cheng & Chin‐Chia Wu & Du‐Juan Wang, 2016. "Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 172-183, March.
    15. Phosavanh, Johnson & Oron, Daniel, 2025. "Minimizing the number of late jobs and total late work with step-learning," European Journal of Operational Research, Elsevier, vol. 321(3), pages 734-749.
    16. Chen, Rubing & Geng, Zhichao & Lu, Lingfa & Yuan, Jinjiang & Zhang, Yuan, 2022. "Pareto-scheduling of two competing agents with their own equal processing times," European Journal of Operational Research, Elsevier, vol. 301(2), pages 414-431.
    17. Jiang, Yiwei & Wu, Mengjing & Chen, Xin & Dong, Jianming & Cheng, T.C.E. & Blazewicz, Jacek & Ji, Min, 2024. "Online early work scheduling on parallel machines," European Journal of Operational Research, Elsevier, vol. 315(3), pages 855-862.
    18. Yuan Zhang & Jinjiang Yuan, 2019. "A note on a two-agent scheduling problem related to the total weighted late work," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 989-999, April.
    19. Ruyan He & Jinjiang Yuan, 2020. "Two-Agent Preemptive Pareto-Scheduling to Minimize Late Work and Other Criteria," Mathematics, MDPI, vol. 8(9), pages 1-18, September.
    20. Ruyan He & Jinjiang Yuan & C. T. Ng & T. C. E. Cheng, 2021. "Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work," Journal of Combinatorial Optimization, Springer, vol. 41(2), pages 504-525, February.

    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:eee:ejores:v:322:y:2025:i:2:p:467-479. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.