IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v66y2019i7p582-595.html
   My bibliography  Save this article

Single‐machine scheduling with deadlines to minimize the total weighted late work

Author

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

Abstract

We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP‐hard even if all the jobs have a unit weight, (ii) the problem is binary NP‐hard and admits a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.

Suggested Citation

  • 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.
    • Handle: RePEc:wly:navres:v:66:y:2019:i:7:p:582-595
    DOI: 10.1002/nav.21869
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21869
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21869?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
    ---><---

    References listed on IDEAS

    as
    1. A. Federgruen & H. Groenevelt, 1986. "Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques," Management Science, INFORMS, vol. 32(3), pages 341-349, March.
    2. Xin Chen & Malgorzata Sterna & Xin Han & Jacek Blazewicz, 2016. "Scheduling on parallel identical machines with late work criterion: Offline and online cases," Journal of Scheduling, Springer, vol. 19(6), pages 729-736, December.
    3. Jianfeng Ren & Yuzhong Zhang & Guo Sun, 2009. "The Np-Hardness Of Minimizing The Total Late Work On An Unbounded Batch Machine," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 26(03), pages 351-363.
    4. Potts, C. N. & Van Wassenhove, L. N., 1983. "An algorithm for single machine sequencing with deadlines to minimize total weighted completion time," European Journal of Operational Research, Elsevier, vol. 12(4), pages 379-387, April.
    5. 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.
    6. Koulamas, Christos & Kyparisis, George J., 2001. "Single machine scheduling with release times, deadlines and tardiness objectives," European Journal of Operational Research, Elsevier, vol. 133(2), pages 447-453, January.
    7. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    8. Almiñana, M. & Escudero, L.F. & Landete, M. & Monge, J.F. & Rabasa, A. & Sánchez-Soriano, J., 2010. "WISCHE: A DSS for water irrigation scheduling," Omega, Elsevier, vol. 38(6), pages 492-500, December.
    9. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    10. 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.
    11. W. A. Horn, 1974. "Some simple scheduling algorithms," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 21(1), pages 177-185, March.
    12. Marc E. Posner, 1985. "Minimizing Weighted Completion Times with Deadlines," Operations Research, INFORMS, vol. 33(3), pages 562-574, June.
    13. 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.
    14. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    15. Jinjiang Yuan, 2017. "Unary NP-hardness of minimizing the number of tardy jobs with deadlines," Journal of Scheduling, Springer, vol. 20(2), pages 211-218, April.
    16. H. W. Kuhn, 2005. "The Hungarian method for the assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(1), pages 7-21, February.
    17. 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.
    18. 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.
    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. Xinyu Sun & Tao Liu & Xin-Na Geng & Yang Hu & Jing-Xiao Xu, 2023. "Optimization of scheduling problems with deterioration effects and an optional maintenance activity," Journal of Scheduling, Springer, vol. 26(3), pages 251-266, June.
    2. 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.
    3. 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.
    4. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    5. 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.

    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. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    2. 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.
    3. 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.
    4. 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.
    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. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    12. 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).
    13. Xin Chen & Malgorzata Sterna & Xin Han & Jacek Blazewicz, 2016. "Scheduling on parallel identical machines with late work criterion: Offline and online cases," Journal of Scheduling, Springer, vol. 19(6), pages 729-736, December.
    14. Yuan Zhang & Jinjiang Yuan & Chi To Ng & Tai Chiu E. Cheng, 2021. "Pareto‐optimization of three‐agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 68(3), pages 378-393, April.
    15. Györgyi, Péter & Kis, Tamás, 2020. "A common approximation framework for early work, late work, and resource leveling problems," European Journal of Operational Research, Elsevier, vol. 286(1), pages 129-137.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. 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.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:66:y:2019:i:7:p:582-595. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.