Abstract
In this paper, we investigate a single machine problem with actual time-dependent learning effect considering unequal release times, where the objective is to minimize the total completion time. At first, a mathematical model of the problem was formulated, which was verified to be effective by ILOG CP (a constraint programming tool provided by ILOG). Then a branch-and-bound algorithm incorporating with two dominance properties and two lower bounds was developed to obtain solutions for small size problems. However, since this problem is NP-hard, two tabu search algorithms combined with dominance rules, called TSDR, were proposed for solving problems with large number of jobs. The experimental results demonstrated that the proposed branch-and-bound algorithm had a better performance than CP in small size problems. The TSDR algorithms can also obtain optimal solutions for some situations in small problems. In addition, the proposed TSDR algorithms outperformed the benchmark algorithms in the literature and the advantage became more obvious with the number of jobs increasing.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ahmadizar F, Hosseini L (2012) Bi-criteria single machine scheduling with a time-dependent learning effect and release times. Appl Math Model 36(12):6203–6214
Badiru AB (1992) Computational survey of univariate and multivariate learning curve models. IEEE Trans Eng Manage 39(2):176–188
Ben-Daya M, Al-Fawzan M (1998) A tabu search approach for the flow shop scheduling problem. Eur J Oper Res 109(1):88–95
Biskup D (1999) Single-machine scheduling with learning considerations. Eur J Oper Res 115(1):173–178
Chung Y-H, Tong L-I (2011) Makespan minimization for m-machine permutation flowshop scheduling problem with learning considerations. Int J Adv Manuf Technol 56(1–4):355–367
Della Croce F, Narayan V, Tadei R (1996) The two-machine total completion time flow shop problem. Eur J Oper Res 90(2):227–237
Dessouky MM (1998) Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness. Comput Ind Eng 34(4):793–806
Duran Toksarı M (2011) A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs. Comput Oper Res 38(9):1361–1365
Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13(5):533–549
González MA, Vela CR, González-Rodríguez I, Varela R (2013) Lateness minimization with tabu search for job shop scheduling problem with sequence dependent setup times. J Intell Manuf 24(4):741–754
Grabowski J, Wodecki M (2004) A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Comput Oper Res 31(11):1891–1909
Kang Q, Zhou MC, An J, Wu Q (2013) Swarm intelligence approaches to optimal power flow problem with distributed generator failures in power networks. IEEE Trans Autom Sci Eng 10(2):343–353
Kuo W-H, Yang D-L (2006) Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. Eur J Oper Res 174(2):1184–1190
Lee W-C, Wu C-C, Liu M-F (2009) A single-machine bi-criterion learning scheduling problem with release times. Expert Syst Appl 36(7):10295–10303
Lee W-C, Wu C-C, Hsu P-H (2010) A single-machine learning effect scheduling problem with release times. Omega 38(1):3–11
Lenstra JK, Rinnooy Kan A, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrete Math 1:343–362
Mosheiov G, Sidney JB (2003) Scheduling with general job-dependent learning curves. Eur J Oper Res 147(3):665–670
Ng C, Wang J-B, Cheng TE, Liu L (2010) A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs. Comput Oper Res 37(1):83–90
Pezzella F, Merelli E (2000) A tabu search method guided by shifting bottleneck for the job shop scheduling problem. Eur J Oper Res 120(2):297–310
Solimanpur M, Elmi A (2011) A tabu search approach for group scheduling in buffer-constrained flow shop cells. Int J Comput Integr Manuf 24(3):257–268
Tayebi Araghi M, Jolai F, Rabiee M (2014) Incorporating learning effect and deterioration for solving a sdst flexible job-shop scheduling problem with a hybrid meta-heuristic approach. Int J Comput Integr Manuf 27(8):733–746
Wang J-B, Wang M-Z (2013) Solution algorithms for the total weighted completion time minimization flow shop scheduling with decreasing linear deterioration. Int J Adv Manuf Technol 67(1–4):243–253
Wu C-C, Liu C-L (2010) Minimizing the makespan on a single machine with learning and unequal release times. Comput Ind Eng 59(3):419–424
Wu C-C, Hsu P-H, Chen J-C, Wang N-S (2011a) Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times. Comput Oper Res 38(7):1025–1034
Wu C-C, Hsu P-H, Chen J-C, Wang N-S, Wu W-H (2011b) Branch-and-bound and simulated annealing algorithms for a total weighted completion time scheduling with ready times and learning effect. Int J Adv Manuf Technol 55(1–4):341–353
Wu W-H, Cheng S-R, Wu C-C, Yin Y (2012) Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations. J Intell Manuf 23(5):1985–1993
Wu W-H, Xu J, Wu W-H, Yin Y, Cheng I-F, Wu C-C (2013) A tabu method for a two-agent single-machine scheduling with deterioration jobs. Comput Oper Res 40(8):2116–2127
Yang D-L, Kuo W-H (2007) Single-machine scheduling with an actual time-dependent learning effect. J Oper Res Soc 58(10):1348–1353
Acknowledgments
The authors are very grateful to the Editor-in-Chief and the anonymous reviewers for their constructive comments that have further helped to improve the quality of this paper. This work was supported by the National Natural Science Foundation of China (Nos. 71171184/71201151/71433003), the China Postdoctoral Science Foundation (No. 2015M581707), the Jiangsu Planned Projects for Postdoctoral Research Funds(No. 1501006B), the Fundamental Research Funds for the Central Universities (No. 2014B18814).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zheng, C., Chen, H. & Xu, R. Tabu search algorithms for minimizing total completion time on a single machine with an actual time-dependent learning effect. Nat Comput 18, 287–299 (2019). https://doi.org/10.1007/s11047-016-9539-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-016-9539-4