Abstract
In the real-world situations, uncertain events commonly occur and cause disruption of normal scheduled activities. Consideration of uncertain events during the scheduling process helps the organizations to make strategies for handling the uncertainties in an effective manner. Therefore, in the present paper, unexpected machine breakdowns have been considered during scheduling of jobs in a flexible job-shop environment. The objective is to obtain lowest possible makespan such that robust and stable schedules are produced even if an unexpected machine breakdown occurs. The robust and stable schedules may help to decrease the costs associated with unexpected machine failures. The present work uses a two-stage teaching-learning-based optimization (2S-TLBO) method to solve flexible job-shop scheduling problem (FJSP) under machine breakdown. In the first stage, the primary objective of makespan is optimized without considering any machine breakdown. In the second stage, a bi-objective function considering robustness and stability of the schedule is optimized under uncertainty of machine breakdowns. In order to incorporate the machine breakdown data to basic FJSP, a non-idle time insertion technique is used. In order to generate effective robust and stable predictive FJSP schedules, a rescheduling technique called modified affected operations rescheduling (mAOR) is used. The Kacem’s and Brandimarte’s benchmark problems have been solved and compared with other algorithms available in the literature. Results indicate that TLBO outperforms other algorithms by generating superior robust and stable predictive schedules. Statistical analysis is carried out to test the significance difference of the results obtained by TLBO with other algorithms.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bagheri A, Zandieh M, Mahdavi I, Yazdani M (2010) An artificial immune algorithm for the flexible job-shop scheduling problem. Future Gener Comput Syst 26:533–541
Buddala R, Mahapatra SS (2016) An effective teaching learning based optimization for flexible job shop scheduling. In Electr Electron Optim Tech (ICEEOT), Int Conf 3087–3092 IEEE
Gao J, Sun L, Gen M (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Oper Res 35:2892–2907
Gao KZ, Suganthan PN, Pan QK, Chua TJ, Cai TX, Chong CS (2016) Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. J Intell Manuf 27:363–374
Li X, Gao L (2016) An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. Int J Prod Econ 174:93–110
Liouane N, Saad I, Hammad S, Borne P (2007) Ant systems & local search optimization for flexible job shop scheduling production. Int J Comput Commun Control 2:174–184
Rahmati SHA, Zandieh M (2012) A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem. Int J Adv Manuf Tech 58:1115–1129
Singh MR, Mahapatra SS (2016) A quantum behaved particle swarm optimization for flexible job shop scheduling. Comput Ind Eng 93:36–44
Wang L, Zhou G, Xu Y, Wang S, Liu M (2012) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Tech 60:303–315
Wu X, Wu S (2017) An elitist quantum-inspired evolutionary algorithm for the flexible job-shop scheduling problem. J Intell Manuf 28:1441–1457
Xing LN, Chen YW, Wang P Zhao QS, Xiong J (2010) A knowledge-based ant colony optimization for flexible job shop scheduling problems. Appl Soft Comput 10:888–896
Yuan Y, Xu H, Yang J (2013) A hybrid harmony search algorithm for the flexible job shop scheduling problem. Appl Soft Comput 13:3259–3272
Zhang G, Gao L, Shi Y (2011) An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Syst Appl 38:3563–3573
Pinedo, M. (2008) Scheduling: theory, algorithms and systems
Deng Q, Gong G, Gong X, Zhang L, Liu W, Ren Q (2017) A bee evolutionary guiding nondominated sorting genetic algorithm II for multiobjective flexible job-shop scheduling. Comput Intell Neurosci 2017:1–20. https://doi.org/10.1155/2017/5232518
Karthikeyan S, Asokan P, Nickolas S, Page T (2015) A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems. Int J Bio-Inspired Comput 7:386–401
Kemmoe-Tchomte S, Lamy D, Tchernev N (2017) An effective multi-start multi-level evolutionary local search for the flexible job-shop problem. Eng Appl Artif Intell 62:80–95
Li JQ, Pan QK, Liang YC (2010) An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 59:647–662
Li JQ, Pan QK, Tasgetiren MF (2014) A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl Math Model 38:1111–1132
Perez MA, Raupp FM (2016) A Newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem. J Intell Manuf 27:409–416
Singh MR, Singh M, Mahapatra SS, Jagadev N (2016) Particle swarm optimization algorithm embedded with maximum deviation theory for solving multi-objective flexible job shop scheduling problem. Int J Adv Manuf Tech 85:2353–2366
Xia W, Wu Z (2005) An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 48:409–425
Xing LN, Chen YW, Yang KW (2009a) Multi-objective flexible job shop schedule: design and evaluation by simulation modeling. Appl Soft Comput 9:362–376
Xing LN, Chen YW, Yang KW (2009b) An efficient search method for multi-objective flexible job shop scheduling problems. J Intell Manuf 20:283–293
Subramaniam V, Raheja AS (2003) mAOR: a heuristic-based reactive repair mechanism for job shop schedules. Int J Adv Manuf Techn 22:669–680
Ourari S, Berrandjia L, Boulakhras R, Boukciat A, Hentous H (2015) Robust approach for centralized job shop scheduling: sequential flexibility. IFAC-PapersOnLine 48:1960–1965
Vieira GE, Herrmann JW, Lin E (2003) Rescheduling manufacturing systems: a framework of strategies, policies, and methods. J Scheduling 6:39–62
Chaari T, Chaabane S, Aissani N, Trentesaux D (2014) Scheduling under uncertainty: survey and research directions. In Adv Logist Transport (ICALT), 2014 Int Conf 229–234 IEEE
He W, Sun D, Liao X (2013) Applying novel clone immune algorithm to solve flexible job shop problem with machine breakdown. J Inf Comput Sci 10:2783–2797
Liu N, Abdelrahman MA, Ramaswamy S (2007a) A complete multiagent framework for robust and adaptable dynamic job shop scheduling. IEEE Trans Syst Man Cybern Part C Appl Rev 37:904–916
Liu H, Abraham A, Grosan C (2007b) A novel variable neighborhood particle swarm optimization for multi-objective flexible job-shop scheduling problems. In Digital Inf Manage 2007 ICDIM'07. 2nd Int Conf 1:138–145 IEEE
Bidot J, Vidal T, Laborie P, Beck JC (2009) A theoretic and practical framework for scheduling in a stochastic environment. J Scheduling 12(3):315–344
Xiong J, Xing LN, Chen YW (2013) Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns. Int J Prod Econ 141:112–126
Wu SD, Storer RH, Pei-Chann C (1993) One-machine rescheduling heuristics with efficiency and stability as criteria. Comput Oper Res 20:1–14
Goren S, Sabuncuoglu I (2009) Optimization of schedule robustness and stability under random machine breakdowns and processing time variability. IIE Trans 42:203–220
Jensen MT (2001) Improving robustness and flexibility of tardiness and total flow-time job shops using robustness measures. Appl Soft Comput 1:35–52
Al-Hinai N, ElMekkawy TY (2011) Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. Int J Prod Econ 132:279–291
Wang K, Choi SH (2012) A decomposition-based approach to flexible flow shop scheduling under machine breakdown. Int J Prod Res 50:215–234
Al-Hinai N, ElMekkawy TY (2012) Solving the flexible job shop scheduling problem with uniform processing time uncertainty. World Acad Sci, Eng Tech 64:996–1001
Chiang, W Y, Fox MS (1990) Protection against uncertainty in a deterministic schedule. In Fourth Int Conf Expert Syst Prod Oper Manage South California, USA 17:
Dalfard VM, Mohammadi G (2012) Two meta-heuristic algorithms for solving multi-objective flexible job-shop scheduling with parallel machine and maintenance constraints. Comput Math Appl 64:2111–2117
Mouelhi-Chibani W, Pierreval H (2010) Training a neural network to select dispatching rules in real time. Comput Ind Eng 58:249–256
Zbib N, Pach C, Sallez Y, Trentesaux D (2012) Heterarchical production control in manufacturing systems using the potential fields concept. J Intell Manuf 23:1649–1670
Cowling PI, Ouelhadj D, Petrovic S (2004) Dynamic scheduling of steel casting and milling using multi-agents. Prod Plann Control 15:178–188
Gao KZ, Suganthan PN, Tasgetiren MF, Pan QK, Sun QQ (2015) Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion. Comput Ind Eng 90:107–117
Wu LH, Chen X, Chen XD, Chen QX (2009) The research on proactive-reactive scheduling framework based on real-time manufacturing information. In Mater Sci Forum 626:789–794 Trans Tech Publ
Li W, Cao J (1995) Stochastic scheduling on a single machine subject to multiple breakdowns according to different probabilities. Oper Res Lett 18:81–91
Kasap N, Aytug H, Paul A (2006) Minimizing makespan on a single machine subject to random breakdowns. Oper Res Lett 34:29–36
Allahverdi A (1995) Two-stage production scheduling with separated set-up times and stochastic breakdowns. J Oper Res Soc 46:896–904
Allahverdi A (1996) Two-machine proportionate flowshop scheduling with breakdowns to minimize maximum lateness. Comp Oper Res 23:909–916
Allahverdi A, Mittenthal J (1994) Two-machine ordered flowshop scheduling under random breakdowns. Math Comput Modell 20:9–17
Allahverdi A, Mittenthal J (1998) Dual criteria scheduling on a two-machine flowshop subject to random breakdowns. Int Trans Oper Res 5:317–324
Alcaide D, Rodriguez-Gonzalez A, Sicilia J (2002) An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns. Eur J Oper Res 140:384–398
Alcaide D, Rodriguez-Gonzalez A, Sicilia J (2005) A heuristic approach to minimize expected makespan in open shops subject to stochastic processing times and failures. Int J Flex Manuf Syst 17:201–226
Luh PB, Chen D, Thakur LS (1999) An effective approach for job-shop scheduling with uncertain processing requirements. IEEE Trans Rob Autom 15:328–339
Lei D (2011) Scheduling stochastic job shop subject to random breakdown to minimize makespan. Int J Adv Manuf Tech 55:1183–1192
Ahmadi E, Zandieh M, Farrokh M, Emami SM (2016) A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms. Comput Oper Res 73:56–66
Park J, Mei Y, Nguyen S, Chen G, Zhang M (2017). Investigating the generality of genetic programming based hyper-heuristic approach to dynamic job shop scheduling with machine breakdown. In Australasian Conf Artif Life Comput Intell 301–313 Springer
Zandieh M, Khatami AR, Rahmati SH (2017) Flexible job shop scheduling under condition-based maintenance: improved version of imperialist competitive algorithm. Appl Soft Comput 58:449–464
El Khoukhi F, Boukachour J, Alaoui AE (2017) The “dual-ants colony”: a novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance. Comput Ind Eng 106:236–255
Jensen MT (2003) Generating robust and flexible job shop schedules using genetic algorithms. IEEE Trans Evol Comput 7:275–288
Singh MR, Mahapatra SS, Mishra R (2014) Robust scheduling for flexible job shop problems with random machine breakdowns using a quantum behaved particle swarm optimisation. Int J Serv Oper Manage 20:1–20
Nouiri M, Bekrar A, Jemai A, Trentesaux D, Ammari AC, Niar S (2017) Two stage particle swarm optimization to solve the flexible job shop predictive scheduling problem considering possible machine breakdowns. Comput Ind Eng 112:595–606
Rao RV, Savsani VJ, Vakharia DP (2011) Teaching–learning-based optimization: a novel method for constrained mechanical design optimization problems. Comput Aided Des 43:303–315
Xu Y, Wang L, Wang SY, Liu M (2015) An effective teaching–learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time. Neurocomputing 148:260–268
Xie Z, Zhang C, Shao X, Lin W, Zhu H (2014) An effective hybrid teaching–learning-based optimization algorithm for permutation flow shop scheduling problem. Adv Eng Softw 77:35–47
Keesari HS, Rao RV (2014) Optimization of job shop scheduling problems using teaching-learning-based optimization algorithm. Opsearch 51:545–561
Baykasoglu A, Hamzadayi A, Köse SY (2014) Testing the performance of teaching–learning based optimization (TLBO) algorithm on combinatorial problems: flow shop and job shop scheduling cases. Inf Sci 276:204–218
Shen JN, Wang L, Zheng HY (2016) A modified teaching–learning-based optimisation algorithm for bi-objective re-entrant hybrid flowshop scheduling. Int J Prod Res 54:3622–3639
Buddala R, Mahapatra SS (2018) An integrated approach for scheduling flexible job-shop using teaching–learning-based optimization method. J Ind Eng Int 1–12. https://doi.org/10.1007/s40092-018-0280-8
Buddala R, Mahapatra SS (2017) Improved teaching–learning-based and JAYA optimization algorithms for solving flexible flow shop scheduling problems. J Ind Eng Int 14:555–570. https://doi.org/10.1007/s40092-017-0244-4
Ho NB, Tay JC (2004) GENACE: an efficient cultural algorithm for solving the flexible job-shop problem. In Evolutionary computation, 2004. CEC2004. Congress on 2004 (Vol. 2, pp. 1759–1766). IEEE
Palacios JJ, González MA, Vela CR, González-Rodríguez I, Puente J (2015) Genetic tabu search for the fuzzy flexible job shop problem. Comput Oper Res 54:74–89
Abumaizar RJ, Svestka JA (1997) Rescheduling job shops under random disruptions. Int J Prod Res 35:2065–2082
Kacem I, Hammadi S, Borne P (2002a) Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans Syst Man Cybern Part C Appl Rev 32:1–13
Kacem I, Hammadi S, Borne P (2002b) Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math Comput Simul 60:245–276
Dong YH, Jang J (2012) Production rescheduling for machine breakdown at a job shop. Int J Prod Res 50:2681–2691
Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41:157–183
Jiang Z, Zuo L, Mingcheng E (2014) Study on multi-objective flexible job-shop scheduling problem considering energy consumption. J Ind Eng Manage 7:589–604
Acknowledgements
The authors express hearty thanks to the editor(s) and anonymous reviewers of IJAMT for their careful reading and suggestions in improving the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Buddala, R., Mahapatra, S.S. Two-stage teaching-learning-based optimization method for flexible job-shop scheduling under machine breakdown. Int J Adv Manuf Technol 100, 1419–1432 (2019). https://doi.org/10.1007/s00170-018-2805-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-018-2805-0