Abstract
The problem of scheduling stochastic job shop subject to breakdown is seldom considered. This paper proposes an efficient genetic algorithm (GA) for the problem with exponential processing time and non-resumable jobs. The objective is to minimize the stochastic makespan itself. In the proposed GA, a novel random key representation is suggested to represent the schedule of the problem and a discrete event-driven decoding method is applied to build the schedule and handle breakdown. Probability stochastic order and the addition operation of exponential random variables are also used to calculate the objective value. The proposed GA is applied to some test problems and compared with a simulated annealing and a particle swarm optimization. The computational results show the effectiveness of the GA and its promising advantage on stochastic scheduling.
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
Li W, Cao J (1995) Stochastic scheduling on a single machine subject to multiple breakdown 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 separate setup 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. Comput Oper Res 23:909–916
Allahverdi A, Mittenthal J (1994) Two-machine ordered flowshop scheduling under breakdown. Math Comput Modell 20:9–17
Allahverid 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 (2006) 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, Cheng D, Thakur LS (1999) An effective approach for job shop scheduling with uncertain processing requirements. IEEE Trans Robot Autom 15:328–339
Singer M (2000) Forecasting policies for scheduling a stochastic due date job shop. Int J Prod Res 38(15):3623–3637
Ginzburg DG, Gonik A (2002) Optimal job-shop scheduling with random operations and cost objectives. Int J Prod Econ 76:147–157
Tavakkoli-Moghaddam R, Jolai F, Vaziri F, Ahmed PK, Azaron A (2005) A hybrid method for solving stochastic job shop scheduling problem. Appl Math Comput 170:185–206
Lei DM, Xiong HJ (2007) An efficient evolutionary algorithm for multi-objective stochastic job shop scheduling. In: Proceedings of International Conference on Machine Learning and Cybernetics. pp. 867–872
Lei DM, Xiong HJ (2008) Job shop scheduling with stochastic processing time through genetic algorithm. In: Proceedings of International Conference on Machine Learning and Cybernetics, Kunming, China. pp. 941–946
Gu JW, Gu XS, Gu MZ (2009) A novel parallel quantum genetic algorithm for stochastic job shop scheduling. J Math Anal Appl 355:63–81
Gu JW, Gu MZ, Cao CW, Gu XS (2010) A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. Comput Oper Res 37:927–937
Cai XQ, Wang LM, Zhou X (2007) Single-machine scheduling to stochastically minimize maximum lateness. J Sched 10:293–301
Lei DM (2010) A genetic algorithm for flexible job shop scheduling with fuzzy processing time. Int J Prod Res 48:2995–3013
Gao J, Gen M, Sun LY (2006) Scheduling jobs and maintenance in flexible job shop with a hybrid genetic algorithm. J Intell Manuf 17:493–507
Lei DM, Wu ZM (2006) Crowding-measure-based multi-objective evolutionary algorithm for Job shop scheduling. Int J Adv Manuf Technol 30(1–2):112–117
Goldberg DE, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. In: Rawlins G (ed) Foundations of genetic algorithms. Morgan Kaufmann, San Mateo
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680
Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, Perth, WA, Australia. pp 1942–1948
Lei DM (2008) A Pareto archive particle swarm optimization for multi-objective job shop scheduling. Comput Ind Eng 54:960–971
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lei, D. Scheduling stochastic job shop subject to random breakdown to minimize makespan. Int J Adv Manuf Technol 55, 1183–1192 (2011). https://doi.org/10.1007/s00170-010-3151-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-010-3151-z