Abstract
In this paper, flexible job shop scheduling problem with machine breakdown is of concern. Considering that there is a limitation in improving robust and stable performance of rescheduling with a single strategy, an approach with multi-strategies is proposed to make the scheduling more robust and stable. First, in prescheduling, a new idle time insertion strategy is put forward. In this new policy, idle time equal to repair time is inserted into an appropriate position of each machine according to the machine's breakdown nature. Second, route changing strategy combined with right-shift policy is proposed to keep the rescheduling as stable and robust as possible. In this policy, whether to right shift or route change is dependent on the cost of archiving robustness and stability. Based on the two strategies, new algorithms dealing with idle time insertion, right-shift scheduling, and route changing scheduling are designed. The computational results show the effectiveness of the new strategies and new algorithms compared with other strategies.
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
Rahmati Seyed Habib A, Zandieh M (2012) A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem. Int J Adv Manuf Technol 58(9–12):1115–1129
Amir R, Saeed M (2011) Dynamic flexible job shop scheduling with alternative process plans: an agent-based approach. Int J Adv Manuf Technol 54(9–12):1091–1107
Moradi E, Fatemi Ghomi SMT, Zandieh M (2010) An efficient architecture for scheduling flexible job-shop with machine availability constraints. Int J Adv Manuf Technol 51(1–4):325–339
Al-Hinai N, ElMekkawy TY (2011) An efficient hybridized genetic algorithm architecture for the flexible job shop scheduling problem. Flex Serv Manuf J 23(1):64–85
Lei D (2011) Scheduling stochastic job shop subject to random breakdown to minimize makespan. Int J Adv Manuf Technol 55(9–12):1183–1192
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(2):279–291
Kamoun H, Sriskandarajah C (1993) The complexity of scheduling jobs in repetitive manufacturing systems. Eur J Oper Res 70(3):350–364
Kutanoglu E, Sabuncuoglu I (2001) Routing-based reactive scheduling policies for machine failures in dynamic job shops. Int J Prod Res 39(14):3141–3158
Cowling PI, Johansson M (2002) Using real time information for effective dynamic scheduling. Eur J Oper Res 139(2):230–244
Shafaei R, Brunn P (1999) Workshop scheduling using practical (inaccurate) data—part 2: an investigation of the robustness of scheduling rules in a dynamic and stochastic environment. Int J Prod Res 37(18):4105–4117
Wu SD, Storer RH, Chang PC (1993) One-machine rescheduling heuristics with efficiency and stability as criteria. Comput Oper Res 20(1):1–14
Goren S, Sabuncuoglu I (2009) Optimization of schedule robustness and stability under random machine breakdowns and processing time variability. IIE Trans 42(3):203–220
Alvarez-Valdes R, Fuertes A, Tamarit JM (2005) A heuristic to schedule flexible job-shop in a glass factory. Eur J Oper Res 165(2):525–534
Wang S, Yu J (2010) An effective heuristic for flexible job-shop scheduling problem with maintenance activities. Comput Ind Eng 59(3):436–447
Mehta SV, Uzsoy R (1999) Predictable scheduling of a single machine subject to breakdowns. Int J Comput Int Manuf 12(1):15–38
O'Donovan R, Uzsoy R, McKay KN (1999) Predictable scheduling of a single machine with breakdowns and sensitive jobs. Int J Prod Res 37(18):4217–4233
Fang J, Xi Y (1997) A rolling horizon job shop rescheduling strategy in the dynamic environment. Int J Adv Manuf Technol 13(3):227–232
Mehta SV, Uzsoy RM (1998) Predictable scheduling of a job shop subject to breakdowns. IEEE Trans Robot Aotom 14(3):365–378
Holthaus O (1999) Scheduling in job shops with machine breakdowns and experimental study. Comput Ind Eng 36(1):137–162
Subramaniam V, Raheja AS (2003) mAOR: a heuristic-based reactive repair mechanism for job shop schedules. Int J Adv Manuf Technol 22(9–10):669–680
NA Masruroh, KL Poh (2007) A Bayesian network approach to job-shop rescheduling. International Conference on Industrial Engineering and Engineering Management IEEM : 1098–1102
Yongmei Hu, Fu Yanan, Jia Lei (2007) An algorithm of job shop rolling scheduling based on singular rough sets. Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, Vol 2, Proceedings: 221–225
Suwa HS (2007) Capability of cumulative delay based reactive scheduling for job shops with machine breakdowns. Comput Ind Eng 53(1):63–78
Zandieh M, Adibi MA (2010) Dynamic job shop scheduling using variable neighborhood search. Int J Prod Res 48(8):2449–2458
Mikkel T. Jensen (2001) Robust and flexible scheduling with evolutionary computation. PhD Dissertation, Department of Computer Science, University of Aarhus, Denmark
Kamrul Hasan SM, Sarker R, Essam D (2011) Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns. Int J Prod Res 49(16):4999–5015
Szelke E, Kerr R (1994) Knowledge-based reactive scheduling. Prod Plan Contr 5(2):124–145
Kacem I, Hammadi S, Borne P (2002) Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans Syst Man Cybern 32(1):1–13
Mattfeld DC (1996) Evolutionary search and the job shop: investigations on genetic algorithms for production scheduling. Physica-Verlag, Heidelberg
A Yahyaoui, N Fnaiech, F Fnaiech (2009) New shifting method for job shop scheduling subject to invariant constraints of resources availability. 35th Annual Conference of IEEE Industrial Electronics: 3211–3216
Kacem I, Hammadi S, Brone P (2002) Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math Comput Simul 60(3–5):245–276
Mesghouni K, Hammadi S, Borne P (1997) Evolution programs for job-shop scheduling. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Orlando, Florida, vol. 1: 720–725
Lee DY, DiCesare F (1994) FMS scheduling flexible manufacturing systems using Petri nets and heuristic search. IEEE Trans Robot Autom 10(2):123–132
Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41(3):157–183
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
He, W., Sun, Dh. Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies. Int J Adv Manuf Technol 66, 501–514 (2013). https://doi.org/10.1007/s00170-012-4344-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-012-4344-4