IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v78y2018icp21-38.html
   My bibliography  Save this article

Flow shop learning effect scheduling problem with release dates

Author

Listed:
  • Bai, Danyu
  • Tang, Mengqian
  • Zhang, Zhi-Hai
  • Santibanez-Gonzalez, Ernesto DR

Abstract

In a real-world assembly environment, the components of a product arrive at a plant over time. Works-in-process are assembled into end-products by following an identical processing route. When a worker at a particular stage repeatedly handles similar tasks and gains the knowledge to execute a task efficiently, the processing time for later tasks is shortened significantly. This assembly process can be described as the flow shop learning effect scheduling problem with release dates, in which the learning effect is dependent on position. The objective is to minimize one of three different criteria, namely, makespan, total completion time and total quadratic completion time. This scheduling problem is formulated as a mixed integer programming (MIP) model. For small-scale problems, a branch and bound (B&B) algorithm with an efficient branching rule is proposed to obtain optimal solutions. The MIP model and the B&B algorithm provide key evidence for academic research. For large-scale problems, the asymptotic optimality of a class of shortest processing time available (SPTA)-based heuristics is proven in terms of probability limit. The convergence property indicates that an SPTA-based heuristic can serve as an optimal schedule under the industrial setting, where thousands of tasks are typically executed on a set of machines. Extensive numerical experiments demonstrate the effectiveness of the proposed algorithms.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:jomega:v:78:y:2018:i:c:p:21-38
    DOI: 10.1016/j.omega.2017.10.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048316309434
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2017.10.002?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. Li, Gang & Wang, Xiao-Yuan & Wang, Ji-Bo & Sun, Lin-Yan, 2013. "Worst case analysis of flow shop scheduling problems with a time-dependent learning effect," International Journal of Production Economics, Elsevier, vol. 142(1), pages 98-104.
    2. Koulamas, Christos & Kyparisis, George J., 2007. "Single-machine and two-machine flowshop scheduling with general learning functions," European Journal of Operational Research, Elsevier, vol. 178(2), pages 402-407, April.
    3. 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.
    4. Glock, C. H. & Jaber, M. Y. & Zolfaghari, S., 2012. "Production planning for a ramp-up process with learning in production and growth in demand," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 57818, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    5. Lee, Wen-Chiung & Wu, Chin-Chia & Hsu, Peng-Hsiang, 2010. "A single-machine learning effect scheduling problem with release times," Omega, Elsevier, vol. 38(1-2), pages 3-11, February.
    6. J-B Wang & Z-Q Xia, 2005. "Flow-shop scheduling with a learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(11), pages 1325-1330, November.
    7. Grosse, E. H. & Glock, C. H. & Müller, Seb., 2015. "Production economics and the learning curve: A Meta-Analysis," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 74127, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    8. Biskup, Dirk, 1999. "Single-machine scheduling with learning considerations," European Journal of Operational Research, Elsevier, vol. 115(1), pages 173-178, May.
    9. Glock, C. H. & Jaber, M. Y., 2013. "A multi-stage production-inventory model with learning and forgetting effects, rework and scrap," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 59034, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    10. Lai, Peng-Jen & Lee, Wen-Chiung, 2011. "Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects," Omega, Elsevier, vol. 39(5), pages 467-471, October.
    11. Grosse, E. H. & Glock, C. H. & Jaber, M. Y., 2013. "The effect of worker learning and forgetting on storage reassignment decisions in order picking systems," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62648, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    12. Wang, Ji-Bo, 2007. "Single-machine scheduling problems with the effects of learning and deterioration," Omega, Elsevier, vol. 35(4), pages 397-402, August.
    13. Grosse, E. H. & Glock, C. H., 2015. "The effect of worker learning on manual order picking processes," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 69316, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    14. Homa Amirian & Rashed Sahraeian, 2015. "Augmented ε-constraint method in multi-objective flowshop problem with past sequence set-up times and a modified learning effect," International Journal of Production Research, Taylor & Francis Journals, vol. 53(19), pages 5962-5976, October.
    15. Grosse, Eric H. & Glock, Christoph H. & Müller, Sebastian, 2015. "Production economics and the learning curve: A meta-analysis," International Journal of Production Economics, Elsevier, vol. 170(PB), pages 401-412.
    16. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Research on permutation flow shop scheduling problems with general position-dependent learning effects," Annals of Operations Research, Springer, vol. 211(1), pages 473-480, December.
    17. 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.
    18. Grosse, E. H. & Glock, C. H., 2013. "An experimental investigation of learning effects in order picking systems," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 58990, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    19. Lee, Wen-Chiung & Wu, Chin-Chia, 2004. "Minimizing total completion time in a two-machine flowshop with a learning effect," International Journal of Production Economics, Elsevier, vol. 88(1), pages 85-93, March.
    20. 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.
    21. 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.
    22. Grosse, Eric H. & Glock, Christoph H., 2015. "The effect of worker learning on manual order picking processes," International Journal of Production Economics, Elsevier, vol. 170(PC), pages 882-890.
    23. Jaber, M. Y. & Glock, C. H., 2013. "A learning curve for tasks with cognitive and motor elements," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 59707, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    24. Cathy H. Xia & George J. Shanthikumar & Peter W. Glynn, 2000. "On the Asymptotic Optimality of the SPT Rule for the Flow Shop Average Completion Time Problem," Operations Research, INFORMS, vol. 48(4), pages 615-622, August.
    25. C-C Wu & Y Yin & S-R Cheng, 2013. "Single-machine and two-machine flowshop scheduling problems with truncated position-based learning functions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(1), pages 147-156, January.
    26. Chung, Chia-Shin & Flynn, James & Kirca, Omer, 2002. "A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems," International Journal of Production Economics, Elsevier, vol. 79(3), pages 185-196, October.
    27. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Some results of the worst-case analysis for flow shop scheduling with a learning effect," Annals of Operations Research, Springer, vol. 211(1), pages 481-490, December.
    28. Glock, C. H. & Jaber, M. Y., 2013. "Learning effects and the phenomenon of moving bottlenecks in a two-stage production system," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62486, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    29. P Chen & C-C Wu & W-C Lee, 2006. "A bi-criteria two-machine flowshop scheduling problem with a learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(9), pages 1113-1125, September.
    30. J-B Wang & M-Z Wang, 2012. "Worst-case analysis for flow shop scheduling problems with an exponential learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(1), pages 130-137, January.
    31. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    32. Xu, Zhiyong & Sun, Linyan & Gong, Juntao, 2008. "Worst-case analysis for flow shop scheduling with a learning effect," International Journal of Production Economics, Elsevier, vol. 113(2), pages 748-753, June.
    33. Janiak, Adam & Rudek, RadosLaw, 2010. "A note on a makespan minimization problem with a multi-ability learning effect," Omega, Elsevier, vol. 38(3-4), pages 213-217, June.
    34. T.C. Cheng & Guoqing Wang, 2000. "Single Machine Scheduling with Learning Effect Considerations," Annals of Operations Research, Springer, vol. 98(1), pages 273-290, December.
    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. Basso, Franco & Guajardo, Mario & Varas, Mauricio, 2020. "Collaborative job scheduling in the wine bottling process," Omega, Elsevier, vol. 91(C).
    2. Heuser, Patricia & Tauer, Björn, 2023. "Single-machine scheduling with product category-based learning and forgetting effects," Omega, Elsevier, vol. 115(C).
    3. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    4. Kasper, T.A. Arno & Land, Martin J. & Teunter, Ruud H., 2023. "Towards System State Dispatching in High‐Variety Manufacturing," Omega, Elsevier, vol. 114(C).

    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 & Tauer, Björn, 2023. "Single-machine scheduling with product category-based learning and forgetting effects," Omega, Elsevier, vol. 115(C).
    2. Lee, Wen-Chiung & Chung, Yu-Hsiang, 2013. "Permutation flowshop scheduling to minimize the total tardiness with learning effects," International Journal of Production Economics, Elsevier, vol. 141(1), pages 327-334.
    3. Lee, Wen-Chiung & Wu, Chin-Chia & Hsu, Peng-Hsiang, 2010. "A single-machine learning effect scheduling problem with release times," Omega, Elsevier, vol. 38(1-2), pages 3-11, February.
    4. 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.
    5. Lai, Peng-Jen & Lee, Wen-Chiung, 2011. "Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects," Omega, Elsevier, vol. 39(5), pages 467-471, October.
    6. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Research on permutation flow shop scheduling problems with general position-dependent learning effects," Annals of Operations Research, Springer, vol. 211(1), pages 473-480, December.
    7. Jaber, M.Y. & Peltokorpi, J. & Glock, C.H. & Grosse, E.H. & Pusic, M., 2021. "Adjustment for cognitive interference enhances the predictability of the power learning curve," International Journal of Production Economics, Elsevier, vol. 234(C).
    8. 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.
    9. Li, Gang & Wang, Xiao-Yuan & Wang, Ji-Bo & Sun, Lin-Yan, 2013. "Worst case analysis of flow shop scheduling problems with a time-dependent learning effect," International Journal of Production Economics, Elsevier, vol. 142(1), pages 98-104.
    10. J-B Wang, 2010. "Single-machine scheduling with a sum-of-actual-processing-time-based learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 172-177, January.
    11. Jian-You Xu & Win-Chin Lin & Yu-Wei Chang & Yu-Hsiang Chung & Juin-Han Chen & Chin-Chia Wu, 2023. "A Two-Machine Learning Date Flow-Shop Scheduling Problem with Heuristics and Population-Based GA to Minimize the Makespan," Mathematics, MDPI, vol. 11(19), pages 1-21, September.
    12. Wang, J.-B. & Ng, C.T. & Cheng, T.C.E. & Liu, L.L., 2008. "Single-machine scheduling with a time-dependent learning effect," International Journal of Production Economics, Elsevier, vol. 111(2), pages 802-811, February.
    13. Wen-Hung Wu & Yunqiang Yin & T C E Cheng & Win-Chin Lin & Juei-Chao Chen & Shin-Yi Luo & Chin-Chia Wu, 2017. "A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(2), pages 111-120, February.
    14. Radosław Rudek, 2012. "Scheduling problems with position dependent job processing times: computational complexity results," Annals of Operations Research, Springer, vol. 196(1), pages 491-516, July.
    15. 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.
    16. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Some results of the worst-case analysis for flow shop scheduling with a learning effect," Annals of Operations Research, Springer, vol. 211(1), pages 481-490, December.
    17. 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.
    18. Zhang, Jun & Liu, Feng & Tang, Jiafu & Li, Yanhui, 2019. "The online integrated order picking and delivery considering Pickers’ learning effects for an O2O community supermarket," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 180-199.
    19. Cheng, Bayi & Zhu, Huijun & Li, Kai & Li, Yongjun, 2019. "Optimization of batch operations with a truncated batch-position-based learning effect," Omega, Elsevier, vol. 85(C), pages 134-143.
    20. 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.

    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:eee:jomega:v:78:y:2018:i:c:p:21-38. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.