IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v38y2010i1-2p3-11.html
   My bibliography  Save this article

A single-machine learning effect scheduling problem with release times

Author

Listed:
  • Lee, Wen-Chiung
  • Wu, Chin-Chia
  • Hsu, Peng-Hsiang

Abstract

In this paper, we investigate a single-machine problem with the learning effect and release times where the objective is to minimize the makespan. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 36 jobs, and the average error percentage of the proposed heuristic is less than 0.11%.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:jomega:v:38:y:2010:i:1-2:p:3-11
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305-0483(09)00002-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Wang, F. -K. & Lee, W., 2001. "Learning curve analysis in total productive maintenance," Omega, Elsevier, vol. 29(6), pages 491-499, December.
    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. 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.
    4. Reddy Dondeti, V. & Mohanty, Bidhu B., 1998. "Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs," European Journal of Operational Research, Elsevier, vol. 105(3), pages 509-524, March.
    5. Biskup, Dirk, 1999. "Single-machine scheduling with learning considerations," European Journal of Operational Research, Elsevier, vol. 115(1), pages 173-178, May.
    6. Mosheiov, Gur, 2001. "Scheduling problems with a learning effect," European Journal of Operational Research, Elsevier, vol. 132(3), pages 687-693, August.
    7. Wang, Ji-Bo, 2007. "Single-machine scheduling problems with the effects of learning and deterioration," Omega, Elsevier, vol. 35(4), pages 397-402, August.
    8. A Bachman & A Janiak, 2004. "Scheduling jobs with position-dependent processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(3), pages 257-264, March.
    9. 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.
    10. 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.
    11. Wu, Chin-Chia & Lee, Wen-Chiung, 2009. "A note on the total completion time problem in a permutation flowshop with a learning effect," European Journal of Operational Research, Elsevier, vol. 192(1), pages 343-347, January.
    12. 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.
    13. Nawaz, Muhammad & Enscore Jr, E Emory & Ham, Inyong, 1983. "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, Elsevier, vol. 11(1), pages 91-95.
    14. 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. Yang, Suh-Jenq & Yang, Dar-Li, 2010. "Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities," Omega, Elsevier, vol. 38(6), pages 528-533, December.
    2. 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.
    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. 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.
    5. 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.
    6. 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.
    7. Heuser, Patricia & Tauer, Björn, 2023. "Single-machine scheduling with product category-based learning and forgetting effects," Omega, Elsevier, vol. 115(C).
    8. 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.
    9. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    10. Chen, Xi & Thomas, Barrett W. & Hewitt, Mike, 2016. "The technician routing problem with experience-based service times," Omega, Elsevier, vol. 61(C), pages 49-61.
    11. 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.
    12. Enrique Gerstl & Gur Mosheiov, 2014. "Single machine just‐in‐time scheduling problems with two competing agents," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(1), pages 1-16, February.
    13. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    14. Pei, Jun & Liu, Xinbao & Fan, Wenjuan & Pardalos, Panos M. & Lu, Shaojun, 2019. "A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers," Omega, Elsevier, vol. 82(C), pages 55-69.
    15. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    16. Roohnavazfar, Mina & Manerba, Daniele & De Martin, Juan Carlos & Tadei, Roberto, 2019. "Optimal paths in multi-stage stochastic decision networks," Operations Research Perspectives, Elsevier, vol. 6(C).
    17. Turabieh, Hamza & Abdullah, Salwani, 2011. "An integrated hybrid approach to the examination timetabling problem," Omega, Elsevier, vol. 39(6), pages 598-607, December.
    18. Ruyan He & Jinjiang Yuan & C. T. Ng & T. C. E. Cheng, 2021. "Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work," Journal of Combinatorial Optimization, Springer, vol. 41(2), pages 504-525, February.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Dar-Li Yang & Wen-Hung Kuo, 2009. "Single-machine scheduling with both deterioration and learning effects," Annals of Operations Research, Springer, vol. 172(1), pages 315-327, November.
    12. Heuser, Patricia & Tauer, Björn, 2023. "Single-machine scheduling with product category-based learning and forgetting effects," Omega, Elsevier, vol. 115(C).
    13. 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.
    14. 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.
    15. 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).
    16. 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.
    17. Chang, Pei-Chann & Chen, Shih-Hsin & Mani, V., 2009. "A note on due-date assignment and single machine scheduling with a learning/aging effect," International Journal of Production Economics, Elsevier, vol. 117(1), pages 142-149, January.
    18. 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.
    19. 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.
    20. Jiang, Zhongyi & Chen, Fangfang & Kang, Huiyan, 2013. "Single-machine scheduling problems with actual time-dependent and job-dependent learning effect," European Journal of Operational Research, Elsevier, vol. 227(1), pages 76-80.

    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:38:y:2010:i:1-2:p:3-11. 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.