IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v121y2023ics0305048323000877.html
   My bibliography  Save this article

Single machine scheduling with due date assignment to minimize the total weighted lead time penalty and late work

Author

Listed:
  • Sang, Yao-Wen
  • Wang, Jun-Qiang
  • Sterna, Małgorzata
  • Błażewicz, Jacek

Abstract

We study a single machine scheduling problem with due date assignment for minimizing the total weighted lead time penalty and late work, where the lead time penalty is the excess of an assigned due date over a given lead time, and the late work is the part of a job executed after the assigned due date. For the problem with common due date assignment, we show that it is solvable in O(nlogn) time. For the problem with unrestricted due date assignment, we determine an optimal due date assignment for a given schedule, and transform the problem to an equivalent problem for minimizing the total ▪-shape function, where ▪ depicts the shape of the penalty function for a job in relation to its completion time. Furthermore, we show that the problem with unrestricted due date assignment is unary NP-hard by proving the unary NP-hardness of the equivalent problem, and study two special cases. For the case with identical lead times, we show that it is binary NP-hard by providing a dynamic programming algorithm. While for the case with identical processing times, we prove that it is solvable in O(n3) time. Finally, we study the problem of minimizing the total ▪-shape function, and show that its two special cases are binary NP-hard by proving that they are pseudo-polynomially solvable.

Suggested Citation

  • 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).
    • Handle: RePEc:eee:jomega:v:121:y:2023:i:c:s0305048323000877
    DOI: 10.1016/j.omega.2023.102923
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048323000877
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2023.102923?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. Baruch Mor & Dana Shapira, 2020. "Scheduling with regular performance measures and optional job rejection on a single machine," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 71(8), pages 1315-1325, August.
    2. 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.
    3. 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.
    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. Christos Koulamas & George Steiner, 2021. "New results for scheduling to minimize tardiness on one machine with rejection and related problems," Journal of Scheduling, Springer, vol. 24(1), pages 27-34, February.
    6. Yunqiang Yin & Du‐Juan Wang & Chin‐Chia Wu & T.C.E. Cheng, 2016. "CON/SLK due date assignment and scheduling on a single machine with two agents," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(5), pages 416-429, August.
    7. Baruch Mor & Gur Mosheiov, 2021. "A note on the single machine CON and CONW problems with lot scheduling," Journal of Combinatorial Optimization, Springer, vol. 42(2), pages 327-338, August.
    8. Kellerer, Hans & Rustogi, Kabir & Strusevich, Vitaly A., 2020. "A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date," Omega, Elsevier, vol. 90(C).
    9. Ming Liu & Shijin Wang & Feifeng Zheng & Chengbin Chu, 2017. "Algorithms for the joint multitasking scheduling and common due date assignment problem," International Journal of Production Research, Taylor & Francis Journals, vol. 55(20), pages 6052-6066, October.
    10. Nicholas G. Hall & Wieslaw Kubiak & Suresh P. Sethi, 1991. "Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date," Operations Research, INFORMS, vol. 39(5), pages 847-856, October.
    11. Alidaee, Bahram & Li, Haitao & Wang, Haibo & Womer, Keith, 2021. "Integer programming formulations in sequencing with total earliness and tardiness penalties, arbitrary due dates, and no idle time: A concise review and extension," Omega, Elsevier, vol. 103(C).
    12. Dvir Shabtay & George Steiner, 2007. "Optimal Due Date Assignment and Resource Allocation to Minimize the Weighted Number of Tardy Jobs on a Single Machine," Manufacturing & Service Operations Management, INFORMS, vol. 9(3), pages 332-350, March.
    13. Shabtay, Dvir, 2016. "Optimal restricted due date assignment in scheduling," European Journal of Operational Research, Elsevier, vol. 252(1), pages 79-89.
    14. Polyakovskiy, Sergey & M’Hallah, Rym, 2021. "Just-in-time two-dimensional bin packing," Omega, Elsevier, vol. 102(C).
    15. 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.
    16. 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.
    17. Enrique Gerstl & Gur Mosheiov, 2021. "The single machine CON problem with unavailability period," International Journal of Production Research, Taylor & Francis Journals, vol. 59(3), pages 824-838, February.
    18. Nicholas G. Hall & Marc E. Posner, 1991. "Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date," Operations Research, INFORMS, vol. 39(5), pages 836-846, October.
    19. 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.
    20. 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.
    21. Xin Chen & Sergey Kovalev & Małgorzata Sterna & Jacek Błażewicz, 2021. "Mirror scheduling problems with early work and late work criteria," Journal of Scheduling, Springer, vol. 24(5), pages 483-487, October.
    22. Jianzhong Du & Joseph Y.-T. Leung, 1990. "Minimizing Total Tardiness on One Machine is NP-Hard," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 483-495, August.
    23. Shlomo Karhi & Dvir Shabtay, 2018. "Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties," International Journal of Production Research, Taylor & Francis Journals, vol. 56(9), pages 3080-3096, May.
    24. 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.
    25. 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.
    26. 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.
    27. Shabtay, Dvir, 2010. "Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs," International Journal of Production Economics, Elsevier, vol. 123(1), pages 235-242, January.
    28. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    29. George Steiner & Rui Zhang, 2011. "Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries," Annals of Operations Research, Springer, vol. 191(1), pages 171-181, November.
    30. George Steiner & Rui Zhang, 2011. "Revised Delivery-Time Quotation in Scheduling with Tardiness Penalties," Operations Research, INFORMS, vol. 59(6), pages 1504-1511, December.
    31. 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.
    32. Koulamas, Christos, 2011. "A unified solution approach for the due date assignment problem with tardy jobs," International Journal of Production Economics, Elsevier, vol. 132(2), pages 292-295, August.
    33. 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.
    34. Yunqiang Yin & Yongjian Yang & Dujuan Wang & T.C.E. Cheng & Chin‐Chia Wu, 2018. "Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(5), pages 393-409, August.
    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. 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.
    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. 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.
    4. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    5. Oğuzhan Ahmet Arik, 2023. "A heuristic for single machine common due date assignment problem with different earliness/tardiness weights," OPSEARCH, Springer;Operational Research Society of India, vol. 60(3), pages 1561-1574, September.
    6. 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.
    7. Chen, Ke & Cheng, T.C.E. & Huang, Hailiang & Ji, Min & Yao, Danli, 2023. "Single-machine scheduling with autonomous and induced learning to minimize total weighted number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 309(1), pages 24-34.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Lin, Shih-Wei & Chou, Shuo-Yan & Ying, Kuo-Ching, 2007. "A sequential exchange approach for minimizing earliness-tardiness penalties of single-machine scheduling with a common due date," European Journal of Operational Research, Elsevier, vol. 177(2), pages 1294-1301, March.
    13. 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.
    14. Gerhard J. Woeginger, 2000. "When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 57-74, February.
    15. 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.
    16. 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.
    17. 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.
    18. Philip Kaminsky & Onur Kaya, 2008. "Scheduling and due‐date quotation in a make‐to‐order supply chain," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(5), pages 444-458, August.
    19. 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.
    20. Xin Chen & Sergey Kovalev & Małgorzata Sterna & Jacek Błażewicz, 2021. "Mirror scheduling problems with early work and late work criteria," Journal of Scheduling, Springer, vol. 24(5), pages 483-487, October.

    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:jomega:v:121:y:2023:i:c:s0305048323000877. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.