IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v45y2023i4d10.1007_s10878-023-01025-6.html
   My bibliography  Save this article

Due date assignment single-machine scheduling with delivery times, position-dependent weights and deteriorating jobs

Author

Listed:
  • Lei Pan

    (Xi’an Jiaotong University)

  • Xinyu Sun

    (Xi’an Jiaotong University)

  • Ji-Bo Wang

    (Shenyang Aerospace University)

  • Li-Han Zhang

    (Shenyang Aerospace University)

  • Dan-Yang Lv

    (Shenyang Aerospace University)

Abstract

This article studies the single-machine scheduling problem with due date assignments, deteriorating jobs, and past-sequence-dependent delivery times. Under three assignments (i.e., common, slack, and different due dates), the goal is to determine a feasible sequence and due dates of all jobs in order to minimize the weighted sum of earliness, tardiness, and due date costs of all jobs, where the weight is not related to the job but to the position in which some job is scheduled. Through a series of optimal properties, efficient and fast polynomial time algorithms are designed for solving the studied scheduling problem with three due date assignments.

Suggested Citation

  • Lei Pan & Xinyu Sun & Ji-Bo Wang & Li-Han Zhang & Dan-Yang Lv, 2023. "Due date assignment single-machine scheduling with delivery times, position-dependent weights and deteriorating jobs," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-16, May.
    • Handle: RePEc:spr:jcomop:v:45:y:2023:i:4:d:10.1007_s10878-023-01025-6
    DOI: 10.1007/s10878-023-01025-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-023-01025-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/s10878-023-01025-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. Ying Chen & Xiaole Ma & Guiqing Zhang & Yongxi Cheng, 2023. "On optimal due date assignment without restriction and resource allocation in group technology scheduling," Journal of Combinatorial Optimization, Springer, vol. 45(2), pages 1-19, March.
    2. 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.
    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. Xiaoyun Xiong & Dujuan Wang & T.C. Edwin Cheng & Chin-Chia Wu & Yunqiang Yin, 2018. "Single-machine scheduling and common due date assignment with potential machine disruption," International Journal of Production Research, Taylor & Francis Journals, vol. 56(3), pages 1345-1360, February.
    5. 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.
    6. Xinyu Sun & Xin-Na Geng & Tao Liu, 2020. "Due-window assignment scheduling in the proportionate flow shop setting," Annals of Operations Research, Springer, vol. 292(1), pages 113-131, September.
    7. Du-Juan Wang & Yunqiang Yin & Shuenn-Ren Cheng & T.C.E. Cheng & Chin-Chia Wu, 2016. "Due date assignment and scheduling on a single machine with two competing agents," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1152-1169, February.
    8. Koulamas, Christos & Kyparisis, George J., 2010. "Single-machine scheduling problems with past-sequence-dependent delivery times," International Journal of Production Economics, Elsevier, vol. 126(2), pages 264-266, August.
    9. Yongjian Yang & Guangqiang Yin & Chunyu Wang & Yunqiang Yin, 2022. "Due date assignment and two-agent scheduling under multitasking environment," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2207-2223, November.
    10. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    11. 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.
    12. Shi-Sheng Li & Ren-Xia Chen & Qi Feng & Cheng-Wen Jiao, 2019. "Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 957-971, October.
    13. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zheng Liu & Ji-Bo Wang, 2024. "Single-Machine Scheduling with Simultaneous Learning Effects and Delivery Times," Mathematics, MDPI, vol. 12(16), pages 1-20, August.
    2. Xuyin Wang & Weiguo Liu, 2024. "Optimal Different Due-Date Assignment Scheduling with Group Technology and Resource Allocation," Mathematics, MDPI, vol. 12(3), pages 1-17, January.
    3. 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.
    4. Oğuzhan Ahmet Arık, 2024. "Optimal policies for minimizing total job completion times and deviations from common due dates in unrelated parallel machine scheduling," OPSEARCH, Springer;Operational Research Society of India, vol. 61(3), pages 1654-1680, September.
    5. Rong-Rong Mao & Yi-Chun Wang & Dan-Yang Lv & Ji-Bo Wang & Yuan-Yuan Lu, 2023. "Delivery Times Scheduling with Deterioration Effects in Due Window Assignment Environments," Mathematics, MDPI, vol. 11(18), pages 1-18, September.
    6. Yurong Zhang & Xi Wang & Li-Han Zhang & Xue Jia & Ji-Bo Wang, 2024. "Different due-window assignment scheduling with deterioration effects," Journal of Combinatorial Optimization, Springer, vol. 48(5), pages 1-21, December.

    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. Baruch Mor & Gur Mosheiov, 2021. "Minmax due-date assignment on a two-machine flowshop," Annals of Operations Research, Springer, vol. 305(1), pages 191-209, October.
    2. Hongyu He & Yanzhi Zhao & Xiaojun Ma & Zheng-Guo Lv & Ji-Bo Wang, 2023. "Branch-and-Bound and Heuristic Algorithms for Group Scheduling with Due-Date Assignment and Resource Allocation," Mathematics, MDPI, vol. 11(23), pages 1-14, November.
    3. 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.
    4. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    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. 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).
    7. Baruch Mor, 2022. "Minmax common flow-allowance problems with convex resource allocation and position-dependent workloads," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 79-97, January.
    8. 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.
    9. Dujuan Wang & Yugang Yu & Huaxin Qiu & Yunqiang Yin & T. C. E. Cheng, 2020. "Two‐agent scheduling with linear resource‐dependent processing times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(7), pages 573-591, October.
    10. Byung-Cheon Choi & Myoung-Ju Park, 2020. "Scheduling two projects with controllable processing times in a single-machine environment," Journal of Scheduling, Springer, vol. 23(5), pages 619-628, October.
    11. Shisheng Li & T.C.E. Cheng & C.T. Ng & Jinjiang Yuan, 2017. "Two‐agent scheduling on a single sequential and compatible batching machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 628-641, December.
    12. 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.
    13. 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.
    14. Shesh Narayan Sahu & Yuvraj Gajpal & Swapan Debbarma, 2018. "Two-agent-based single-machine scheduling with switchover time to minimize total weighted completion time and makespan objectives," Annals of Operations Research, Springer, vol. 269(1), pages 623-640, October.
    15. Li-Han Zhang & Dan-Yang Lv & Ji-Bo Wang, 2023. "Two-Agent Slack Due-Date Assignment Scheduling with Resource Allocations and Deteriorating Jobs," Mathematics, MDPI, vol. 11(12), pages 1-12, June.
    16. 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.
    17. Yi-Chun Wang & Si-Han Wang & Ji-Bo Wang, 2023. "Resource Allocation Scheduling with Position-Dependent Weights and Generalized Earliness–Tardiness Cost," Mathematics, MDPI, vol. 11(1), pages 1-11, January.
    18. Zong-Jun Wei & Li-Yan Wang & Lei Zhang & Ji-Bo Wang & Ershen Wang, 2023. "Single-Machine Maintenance Activity Scheduling with Convex Resource Constraints and Learning Effects," Mathematics, MDPI, vol. 11(16), pages 1-21, August.
    19. 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.
    20. Maliheh Ganji & Rahmat Rabet & Seyed Mojtaba Sajadi, 2022. "A new coordinating model for green supply chain and batch delivery scheduling with satisfaction customers," Environment, Development and Sustainability: A Multidisciplinary Approach to the Theory and Practice of Sustainable Development, Springer, vol. 24(4), pages 4566-4601, April.

    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:jcomop:v:45:y:2023:i:4:d:10.1007_s10878-023-01025-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.