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. 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.
    2. 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.
    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. 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.
    8. Biskup, Dirk, 2008. "A state-of-the-art review on scheduling with learning effects," European Journal of Operational Research, Elsevier, vol. 188(2), pages 315-329, July.
    9. Finke, Gerd & Gara-Ali, Ahmed & Espinouse, Marie-Laure & Jost, Vincent & Moncel, Julien, 2017. "Unified matrix approach to solve production-maintenance problems on a single machine," Omega, Elsevier, vol. 66(PA), pages 140-146.
    10. Kai-biao Sun & Hong-xing Li, 2009. "Some single-machine scheduling problems with actual time and position dependent learning effects," Fuzzy Information and Engineering, Springer, vol. 1(2), pages 161-177, June.
    11. 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.
    12. 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.
    13. 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.
    14. Aarabi, Fatemeh & Batta, Rajan, 2020. "Scheduling spatially distributed jobs with degradation: Application to pothole repair," Socio-Economic Planning Sciences, Elsevier, vol. 72(C).
    15. Frederik Ferid Ostermeier & Jochen Deuse, 2024. "A review and classification of scheduling objectives in unpaced flow shops for discrete manufacturing," Journal of Scheduling, Springer, vol. 27(1), pages 29-49, February.
    16. Qian, Jianbo & Steiner, George, 2013. "Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine," European Journal of Operational Research, Elsevier, vol. 225(3), pages 547-551.
    17. Oron, Daniel, 2016. "Scheduling controllable processing time jobs with position-dependent workloads," International Journal of Production Economics, Elsevier, vol. 173(C), pages 153-160.
    18. 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.
    19. Wang, Ji-Bo, 2007. "Single-machine scheduling problems with the effects of learning and deterioration," Omega, Elsevier, vol. 35(4), pages 397-402, August.
    20. 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.

    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.