IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i23p3085-d691679.html
   My bibliography  Save this article

The Due Date Assignment Scheduling Problem with Delivery Times and Truncated Sum-of-Processing-Times-Based Learning Effect

Author

Listed:
  • Jin Qian

    (College of Science, Northeastern University, Shenyang 110819, China)

  • Yu Zhan

    (College of Science, Northeastern University, Shenyang 110819, China)

Abstract

This paper considers a single-machine scheduling problem with past-sequence-dependent delivery times and the truncated sum-of-processing-times-based learning effect. The goal is to minimize the total costs that comprise the number of early jobs, the number of tardy jobs and due date. The due date is a decision variable. There will be corresponding penalties for jobs that are not completed on time. Under the common due date, slack due date and different due date, we prove that these problems are polynomial time solvable. Three polynomial time algorithms are proposed to obtain the optimal sequence.

Suggested Citation

  • Jin Qian & Yu Zhan, 2021. "The Due Date Assignment Scheduling Problem with Delivery Times and Truncated Sum-of-Processing-Times-Based Learning Effect," Mathematics, MDPI, vol. 9(23), pages 1-14, November.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:23:p:3085-:d:691679
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/23/3085/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/23/3085/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Cheng, T.C.E. & Wu, Chin-Chia & Chen, Juei-Chao & Wu, Wen-Hsiang & Cheng, Shuenn-Ren, 2013. "Two-machine flowshop scheduling with a truncated learning function to minimize the makespan," International Journal of Production Economics, Elsevier, vol. 141(1), pages 79-86.
    2. Liu, Ming & Wang, Shijin & Chu, Chengbin, 2013. "Scheduling deteriorating jobs with past-sequence-dependent delivery times," International Journal of Production Economics, Elsevier, vol. 144(2), pages 418-421.
    3. 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.
    4. Qian, Jin & Lin, Hexiang & Kong, Yufeng & Wang, Yuansong, 2020. "Tri-criteria single machine scheduling model with release times and learning factor," Applied Mathematics and Computation, Elsevier, vol. 387(C).
    5. Chin-Chia Wu & Du-Juan Wang & Shuenn-Ren Cheng & I-Hong Chung & Win-Chin Lin, 2018. "A two-stage three-machine assembly scheduling problem with a position-based learning effect," International Journal of Production Research, Taylor & Francis Journals, vol. 56(9), pages 3064-3079, May.
    6. 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.
    7. Gang Li & Mei-Ling Luo & Wen-Jie Zhang & Xiao-Yuan Wang, 2015. "Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation," International Journal of Production Research, Taylor & Francis Journals, vol. 53(4), pages 1228-1241, February.
    8. Lin-Hui Sun & Kai Cui & Ju-hong Chen & Jun Wang, 2016. "Due date assignment and convex resource allocation scheduling with variable job processing times," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3551-3560, June.
    9. S-J Yang & D-L Yang, 2012. "Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(11), pages 1508-1515, November.
    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. Hongyu He & Yanzhi Zhao & Xiaojun Ma & Yuan-Yuan Lu & Na Ren & Ji-Bo Wang, 2023. "Study on Scheduling Problems with Learning Effects and Past Sequence Delivery Times," Mathematics, MDPI, vol. 11(19), pages 1-19, September.
    2. Pedro Palominos & Mauricio Mazo & Guillermo Fuertes & Miguel Alfaro, 2025. "An Improved Marriage in Honey-Bee Optimization Algorithm for Minimizing Earliness/Tardiness Penalties in Single-Machine Scheduling with a Restrictive Common Due Date," Mathematics, MDPI, vol. 13(3), pages 1-29, January.

    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. Ji-Bo Wang & Bo Cui & Ping Ji & Wei-Wei Liu, 2021. "Research on single-machine scheduling with position-dependent weights and past-sequence-dependent delivery times," Journal of Combinatorial Optimization, Springer, vol. 41(2), pages 290-303, February.
    2. Wu, Yu-Bin & Wan, Long & Wang, Xiao-Yuan, 2015. "Study on due-window assignment scheduling based on common flow allowance," International Journal of Production Economics, Elsevier, vol. 165(C), pages 155-157.
    3. Hongyu He & Mengqi Liu & Ji-Bo Wang, 2017. "Resource constrained scheduling with general truncated job-dependent learning effect," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 626-644, February.
    4. 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.
    5. 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.
    6. Zheng-Guo Lv & Li-Han Zhang & Xiao-Yuan Wang & Ji-Bo Wang, 2024. "Single Machine Scheduling Proportionally Deteriorating Jobs with Ready Times Subject to the Total Weighted Completion Time Minimization," Mathematics, MDPI, vol. 12(4), pages 1-15, February.
    7. Geng, Zhichao & Yuan, Jinjiang, 2023. "Single-machine scheduling of multiple projects with controllable processing times," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1074-1090.
    8. Zhongyi Jiang & Fangfang Chen & Xiandong Zhang, 2022. "Single-machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 116-139, January.
    9. Wenjuan Fan & Jun Pei & Xinbao Liu & Panos M. Pardalos & Min Kong, 2018. "Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning," Journal of Global Optimization, Springer, vol. 71(1), pages 147-163, May.
    10. Jin Qian & Yu Zhan, 2022. "The Due Window Assignment Problems with Deteriorating Job and Delivery Time," Mathematics, MDPI, vol. 10(10), pages 1-16, May.
    11. Wang, Sheng-yao & Wang, Ling & Liu, Min & Xu, Ye, 2013. "An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 145(1), pages 387-396.
    12. Shaojun Lu & Jun Pei & Xinbao Liu & Xiaofei Qian & Nenad Mladenovic & Panos M. Pardalos, 2020. "Less is more: variable neighborhood search for integrated production and assembly in smart manufacturing," Journal of Scheduling, Springer, vol. 23(6), pages 649-664, December.
    13. Vincent T’kindt & Federico Della Croce & Mathieu Liedloff, 2024. "Moderate exponential-time algorithms for scheduling problems," Annals of Operations Research, Springer, vol. 343(2), pages 753-783, December.
    14. 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.
    15. Shaojun Lu & Jun Pei & Xinbao Liu & Panos M. Pardalos, 2020. "Robust parallel-batching scheduling with fuzzy deteriorating processing time and variable delivery time in smart manufacturing," Fuzzy Optimization and Decision Making, Springer, vol. 19(3), pages 333-357, September.
    16. Cheng, Shuenn-Ren, 2014. "Some new problems on two-agent scheduling to minimize the earliness costs," International Journal of Production Economics, Elsevier, vol. 156(C), pages 24-30.
    17. Pei, Jun & Liu, Xinbao & Fan, Wenjuan & Pardalos, Panos M. & Lu, Shaojun, 2019. "A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers," Omega, Elsevier, vol. 82(C), pages 55-69.
    18. 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.
    19. Xingong Zhang & Win-Chin Lin & Chin-Chia Wu, 2022. "Rescheduling problems with allowing for the unexpected new jobs arrival," Journal of Combinatorial Optimization, Springer, vol. 43(3), pages 630-645, April.
    20. Bai, Danyu & Tang, Mengqian & Zhang, Zhi-Hai & Santibanez-Gonzalez, Ernesto DR, 2018. "Flow shop learning effect scheduling problem with release dates," Omega, Elsevier, vol. 78(C), pages 21-38.

    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:gam:jmathe:v:9:y:2021:i:23:p:3085-:d:691679. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.