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

Single-machine scheduling with the learning effect of processing time and the deterioration effect of delivery time for prefabricated components

Author

Listed:
  • Na Li

    (Qingdao University of Technology)

  • Ran Ma

    (Qingdao University of Technology)

  • Yuzhong Zhang

    (Qufu Normal University)

Abstract

In the production scheduling of prefabricated components, a scheduling model considering the learning effect of processing time and the deterioration effect of delivery time in this paper is provided. More precisely, it asks for an assignment of a series of independent prefabricated jobs that arrived over time to a single machine for processing, and once the execution of a job is finished, it will be transported to the destination. The information of each prefabricated job including its basic processing time $$b_{j}$$ b j , release time $$r_j$$ r j , and deterioration rate $$e_j$$ e j of delivery time is unknown in advance and is revealed upon the arrival of this job. Moreover, the actual processing time of prefabricated job $$J_j$$ J j with learning effect is $$p_{j}=b_{j}(a-b t)$$ p j = b j ( a - b t ) , where a and b are non-negative parameters and t denotes the starting time of prefabricated job $$J_j$$ J j , respectively. And the delivery time of prefabricated job $$J_j$$ J j is $$q_{j}=e_{j}C_{j}$$ q j = e j C j . The goal of scheduling is to minimize the maximum time by which all jobs have been delivered. For the problem, we first analyze offline optimal scheduling and then propose an online algorithm with a competitive ratio of $$2-bb_{\min }$$ 2 - b b min . Furthermore, the effectiveness of the online algorithm is demonstrated by numerical experiments and managerial insights are derived.

Suggested Citation

  • Na Li & Ran Ma & Yuzhong Zhang, 2025. "Single-machine scheduling with the learning effect of processing time and the deterioration effect of delivery time for prefabricated components," Journal of Combinatorial Optimization, Springer, vol. 49(3), pages 1-26, April.
  • Handle: RePEc:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01271-w
    DOI: 10.1007/s10878-025-01271-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-025-01271-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-025-01271-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. Yuan Yuan & Yan Lan & Ning Ding & Xin Han, 2022. "A PTAS for non-resumable open shop scheduling with an availability constraint," Journal of Combinatorial Optimization, Springer, vol. 43(2), pages 350-362, March.
    2. Mosheiov, Gur, 2001. "Scheduling problems with a learning effect," European Journal of Operational Research, Elsevier, vol. 132(3), pages 687-693, August.
    3. 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.
    4. Liu, Ming & Chu, Chengbin & Xu, Yinfeng & Zheng, Feifeng, 2010. "An optimal online algorithm for single machine scheduling with bounded delivery times," European Journal of Operational Research, Elsevier, vol. 201(3), pages 693-700, March.
    5. Jun Pei & Bayi Cheng & Xinbao Liu & Panos M. Pardalos & Min Kong, 2019. "Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time," Annals of Operations Research, Springer, vol. 272(1), pages 217-241, January.
    6. Qiulan Zhao & Jinjiang Yuan, 2020. "Bicriteria scheduling of equal length jobs on uniform parallel machines," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 637-661, April.
    7. Ma, Ran & Tao, Jiping & Yuan, Jinjiang, 2016. "Online scheduling with linear deteriorating jobs to minimize the total weighted completion time," Applied Mathematics and Computation, Elsevier, vol. 273(C), pages 570-583.
    8. Biskup, Dirk, 1999. "Single-machine scheduling with learning considerations," European Journal of Operational Research, Elsevier, vol. 115(1), pages 173-178, May.
    9. 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.
    10. Stanisław Gawiejnowicz, 2020. "A review of four decades of time-dependent scheduling: main results, new topics, and open problems," Journal of Scheduling, Springer, vol. 23(1), pages 3-47, February.
    11. Jaber, Mohamad Y. & Guiffrida, Alfred L., 2004. "Learning curves for processes generating defects requiring reworks," European Journal of Operational Research, Elsevier, vol. 159(3), pages 663-672, December.
    12. Dong, Yachao & Maravelias, Christos T., 2021. "Terminal inventory level constraints for online production scheduling," European Journal of Operational Research, Elsevier, vol. 295(1), pages 102-117.
    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. Heuser, Patricia & Letmathe, Peter & Vossen, Thomas, 2025. "Skill development in the field of scheduling: A structured literature review," European Journal of Operational Research, Elsevier, vol. 321(3), pages 697-716.
    2. Zhe Zhang & Xiaoling Song & Huijun Huang & Yong Yin & Benjamin Lev, 2022. "Scheduling problem in seru production system considering DeJong’s learning effect and job splitting," Annals of Operations Research, Springer, vol. 312(2), pages 1119-1141, May.
    3. 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.
    4. Heuser, Patricia & Tauer, Björn, 2023. "Single-machine scheduling with product category-based learning and forgetting effects," Omega, Elsevier, vol. 115(C).
    5. Anzanello, Michel J. & Fogliatto, Flavio S. & Santos, Luana, 2014. "Learning dependent job scheduling in mass customized scenarios considering ergonomic factors," International Journal of Production Economics, Elsevier, vol. 154(C), pages 136-145.
    6. Xingong Zhang & Guangle Yan & Wanzhen Huang & Guochun Tang, 2011. "Single-machine scheduling problems with time and position dependent processing times," Annals of Operations Research, Springer, vol. 186(1), pages 345-356, June.
    7. Frederik Ferid Ostermeier & Jochen Deuse, 2024. "Modelling forgetting due to intermittent production in mixed-model line scheduling," Flexible Services and Manufacturing Journal, Springer, vol. 36(2), pages 503-532, June.
    8. Hamta, Nima & Fatemi Ghomi, S.M.T. & Jolai, F. & Akbarpour Shirazi, M., 2013. "A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect," International Journal of Production Economics, Elsevier, vol. 141(1), pages 99-111.
    9. 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.
    10. G Mosheiov & J B Sidney, 2005. "Note on scheduling with general learning curves to minimize the number of tardy jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(1), pages 110-112, January.
    11. 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.
    12. Ji-Bo Wang & Ming-Zheng Wang, 2011. "Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects," Annals of Operations Research, Springer, vol. 191(1), pages 155-169, November.
    13. 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.
    14. Matan Atsmony & Baruch Mor & Gur Mosheiov, 2024. "Single machine scheduling with step-learning," Journal of Scheduling, Springer, vol. 27(3), pages 227-237, June.
    15. Cheng, T. C. E. & Ding, Q. & Lin, B. M. T., 2004. "A concise survey of scheduling with time-dependent processing times," European Journal of Operational Research, Elsevier, vol. 152(1), pages 1-13, January.
    16. Koulamas, Christos & Gupta, Sushil & Kyparisis, George J., 2010. "A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times," European Journal of Operational Research, Elsevier, vol. 205(2), pages 479-482, September.
    17. Wang, Xiuli & Edwin Cheng, T.C., 2007. "Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 178(1), pages 57-70, April.
    18. 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).
    19. Kuo, Wen-Hung & Yang, Dar-Li, 2006. "Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1184-1190, October.
    20. Gordon, Valery S. & Strusevich, Vitaly A., 2009. "Single machine scheduling and due date assignment with positionally dependent processing times," European Journal of Operational Research, Elsevier, vol. 198(1), pages 57-62, 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:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01271-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.