Document Type : Research Paper

Author

Abstract

In this paper hybrid flowshop scheduling problem where some jobs, not all, have to follow no-wait restriction (that is, the operations of that job must be processed with no stop) is examined. In the literature, all papers assume that all jobs of the shops have to follow no-wait restrictions. First, this paper mathematically formulates the problem with two different mixed integer linear models under proposed considerations. The models are evaluated using two performance measures of size complexity and computational complexity. The small instances of the problem are solved using commercial software of mathematical programming. To solve larger instances of problem, two solution algorithms have been developed. These two algorithms are based on imperialist competitive algorithm and simulated annealing. A comprehensive numerical experiment including small and large instances is conducted to evaluate the models and algorithms. The results show that the imperialist competitive algorithm outperforms simulated annealing

Keywords

Aldowaisan, T., Allahverdi, A., (2004). New heuristics for m-machine no-wait flowshop to minimize total completion time. Omega, 32, 345–352. Atashpaz-Gargari, E., Lucas, C., (2007) Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress, 4661–4670. Attar, S.F., Mohammadi, R., Tavakkoli-Moghaddam, M., (2011). A novel imperialist competitive algorithm to solve flexible flow shop scheduling problem in order to minimize maximum completion time, International Journal of Computer Applications, 28, 27-32. Chang, J.L., Gong, D.W., MA, X.P., (2007). A heuristic genetic algorithm for no-wait flowshop scheduling problem, Journal of China University of Mining and Technology, 17, 582–586. Chen, C., Neppalli, R., (1996). Genetic algorithms applied to the continuous flow shop problem. Computers and Industrial Engineering, 30, 919–929. Fink, A., Voß, S., (2003). Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research, 151, 400–414. Hall, N.C., Sriskandarajah, C.A., (1996). Survey of machine scheduling problems with blocking and no-wait in process, Operations Research, 44, 510–525. Giaro, K., (2001). NP-hardness of compact scheduling in simplified open and flow shops, European Journal of Operational Research, 130, 90–98. Goyal, S.K., Sriskandarajah, C., (1998). No-wait shop scheduling: Computational complexity and approximate algorithms, Operations Research, 25, 220–244. Laha, D., Sapkal, S.U., (2014). An improved heuristic to minimize total flow time for scheduling in them-machine no-wait flow shop, Computers and Industrial Engineering, 67, 36-43.
زمانبندی جریان کاری ترکیبی با وجود کارهای بدون انتظار... 55
Naderi, B., Salmasi, N., (2012). Permutation flowshops in group scheduling with sequence-dependent setup times, European Journal of Industrial Engineering, 6(2), 177-199. Naderi, B., Khalili, M., Khamseh, A.A., (2014). Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines, International Journal of Production Research, 52, 2667-2681. Nagano, M.S., da Silva, A.A., Lorena, L.A.N., (2014). An evolutionary clustering search for the no-wait flow shop problem with sequence dependent setup times, Expert Systems with Applications, 41, 3628-3633. Schuster, C.J., Framinan, J.M., Approximate procedure for no-wait job shop scheduling. Operations Research Letters, 31, 308–318. Rajendran, C., (1994). A no-wait flowshop scheduling heuristic to minimize makespan, Journal of the Operational Research Society, 45, 472–478. Röck, H., (1984). Some new results in flow shop scheduling, Mathematical Methods of Operations Research, 28, 1–16. Ruiz, R., Allahverdi, A., (2007). Some effective heuristics for no-wait flowshops with setup times to minimize total completion time, Annals of Operations Research, 156, 143–171. Pan, Q.K., Wang, L., Zhao, B.H., (2008). An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion, International Journal of Advanced Manufacturing Technology, 38, 778-786. Stafford, E.F., Tseng, F.T., Gupta, J.N.D., (2005). Comparative evaluation of MILP flowshop models, Journal of Operational Research Society, 56, 88–101. Tseng, F.T., Stafford, E.F., (2008). New MILP models for the permutation flowshop problem, Journal of the Operational Research Society, 59, 1373–1386.