IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v48y2024i5d10.1007_s10878-024-01223-w.html
   My bibliography  Save this article

Different due-window assignment scheduling with deterioration effects

Author

Listed:
  • Yurong Zhang

    (Xi’an Polytechnic University)

  • Xi Wang

    (University of Nottingham)

  • Li-Han Zhang

    (Shenyang Aerospace University)

  • Xue Jia

    (Shenyang Aerospace University)

  • Ji-Bo Wang

    (Shenyang Aerospace University)

Abstract

This paper studies a due-window assignment scheduling problem with deterioration effects on a single-machine. Under different due-window assignment, i.e., the due-window of a job without any restriction, our goal is to make a decision on the optimal due-window and sequence of all jobs to minimize the weighted sum of earliness and tardiness, number of early and delayed, due-window starting time and size. We present properties of the optimal solutions, for some special cases, we prove that the problem can be solved in polynomial time. For the general case, we present a lower bound and an upper bound (i.e., a heuristic algorithm), then a branch-and-bound algorithm is proposed.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jcomop:v:48:y:2024:i:5:d:10.1007_s10878-024-01223-w
    DOI: 10.1007/s10878-024-01223-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-024-01223-w
    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-024-01223-w?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. 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.
    2. 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.
    3. Jun Pei & Xingming Wang & Wenjuan Fan & Panos M. Pardalos & Xinbao Liu, 2019. "Scheduling step-deteriorating jobs on bounded parallel-batching machines to maximise the total net revenue," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 70(10), pages 1830-1847, October.
    4. 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.
    5. 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.
    6. Cuixia Miao & Fanyu Kong & Juan Zou & Ran Ma & Yujia Huo, 2023. "Parallel-Machine Scheduling with Step-Deteriorating Jobs to Minimize the Total (Weighted) Completion Time," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 40(01), pages 1-13, February.
    7. 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.
    8. Pei, Jun & Pardalos, Panos M. & Liu, Xinbao & Fan, Wenjuan & Yang, Shanlin, 2015. "Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 244(1), pages 13-25.
    9. 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.
    10. Xinyu Sun & Xin-Na Geng, 2019. "Single-machine scheduling with deteriorating effects and machine maintenance," International Journal of Production Research, Taylor & Francis Journals, vol. 57(10), pages 3186-3199, May.
    11. T C E Cheng & L Kang & C T Ng, 2004. "Due-date assignment and single machine scheduling with deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(2), pages 198-203, February.
    12. D Oron, 2014. "Scheduling controllable processing time jobs in a deteriorating environment," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(1), pages 49-56, January.
    13. L-H Sun & L-Y Sun & J-B Wang, 2011. "Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 768-775, April.
    14. 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.
    15. B Alidaee & N K Womer, 1999. "Scheduling with time dependent processing times: Review and extensions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(7), pages 711-720, July.
    16. Cheng, T.C.E. & Yang, Suh-Jenq & Yang, Dar-Li, 2012. "Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity," International Journal of Production Economics, Elsevier, vol. 135(1), pages 154-161.
    17. Fei Teng & Si-Wen Luo & Dan-Yang Lv & Ji-Bo Wang, 2023. "Approaches to Solving Scheduling with Due-Window Assignment and Deterioration Effects," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 40(02), pages 1-18, April.
    18. Xue Jia & Dan-Yang Lv & Yang Hu & Ji-Bo Wang & Zhi Wang & Ershen Wang, 2022. "Slack Due-Window Assignment Scheduling Problem with Deterioration Effects and a Deteriorating Maintenance Activity," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 39(06), pages 1-16, December.
    19. Qing Yue & Guohua Wan, 2016. "Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(6), pages 872-883, June.
    20. J Liu & Y Wang & X Min, 2014. "Single-machine scheduling with common due-window assignment for deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(2), pages 291-301, February.
    21. Xinbao Liu & Shaojun Lu & Jun Pei & Panos M. Pardalos, 2018. "A hybrid VNS-HS algorithm for a supply chain scheduling problem with deteriorating jobs," International Journal of Production Research, Taylor & Francis Journals, vol. 56(17), pages 5758-5775, September.
    22. Xue Huang & Na Yin & Wei-Wei Liu & Ji-Bo Wang, 2020. "Common Due Window Assignment Scheduling with Proportional Linear Deterioration Effects," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 37(01), pages 1-15, January.
    23. Xingong Zhang & Wen-Hsiang Wu & Win-Chin Lin & Chin-Chia Wu, 2018. "Machine scheduling problems under deteriorating effects and deteriorating rate-modifying activities," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 69(3), pages 439-448, March.
    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. Xue Huang & Na Yin & Wei-Wei Liu & Ji-Bo Wang, 2020. "Common Due Window Assignment Scheduling with Proportional Linear Deterioration Effects," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 37(01), pages 1-15, January.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Min Kong & Xinbao Liu & Jun Pei & Panos M. Pardalos & Nenad Mladenovic, 2020. "Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines," Journal of Global Optimization, Springer, vol. 78(4), pages 693-715, December.
    8. 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.
    9. Yue, Qing & Zhou, Shenghai, 2021. "Due-window assignment scheduling problem with stochastic processing times," European Journal of Operational Research, Elsevier, vol. 290(2), pages 453-468.
    10. Kaining Shao & Wenjuan Fan & Zishu Yang & Shanlin Yang & Panos M. Pardalos, 2022. "A column generation approach for patient scheduling with setup time and deteriorating treatment duration," Operational Research, Springer, vol. 22(3), pages 2555-2586, July.
    11. 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.
    12. Yang, Dar-Li & Lai, Chien-Jung & Yang, Suh-Jenq, 2014. "Scheduling problems with multiple due windows assignment and controllable processing times on a single machine," International Journal of Production Economics, Elsevier, vol. 150(C), pages 96-103.
    13. Yunqiang Yin & Du-Juan Wang & T C E Cheng & Chin-Chia Wu, 2016. "Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(9), pages 1169-1183, September.
    14. Ming-Hui Li & Dan-Yang Lv & Yuan-Yuan Lu & Ji-Bo Wang, 2024. "Scheduling with Group Technology, Resource Allocation, and Learning Effect Simultaneously," Mathematics, MDPI, vol. 12(7), pages 1-21, March.
    15. 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.
    16. 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.
    17. 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.
    18. Hui Zhu & Min Li & Zhangjin Zhou & Yun You, 2016. "Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3475-3490, June.
    19. 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.
    20. 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.

    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:48:y:2024:i:5:d:10.1007_s10878-024-01223-w. 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.