Volume 2 Issue 1 pp. 155-166 Winter, 2011


A new effective heuristic method for the no-wait flowshop with sequence-dependent setup times problem


Daniella Castro Araújoa and Marcelo Seido Nagano


In this paper, we address the problem of scheduling jobs in a no-wait flowshop problem with sequence-dependent setup times with the objective of minimizing makespan. This problem is well-known for being nondeterministic polynomial-time hard, and small contribution to the problem has been made. We propose a new constructive heuristic named GAPH based on a structural property. The effectiveness of the structural property is crucial given that it is responsible for 100% of the success rate of the total problems tested. The computational results demonstrate that the proposed approach is superior than three of the best-know methods in the literature such as the twos by Bianco, Dell’Olmo and Giordani (INFOR Journal: 37 (1), 3-19, 1999) and TRIPS heuristic adapted for sequence-dependent setup times objective by Brown, Mcgarvey and Ventura (Journal of the Operational Research Society, 55 (6), 614-621, 2004) in terms of the solution quality and that it requires less computational effort.


DOI: 10.5267/j.ijiec.2010.05.003

Keywords: Scheduling, Heuristic, No-wait flowshop, Sequence-dependent setup Makespan
References

Aldowaisan, T. (2001). A new heuristic and dominance relations for no-wait flowshops with setups, Computers & Operations Research, 28 (6), 563-584.

Aldowaisan, T. & Allahverdi, A. (2003). New heuristics for no-wait flowshops to minimize make span, Computers & Operations Research, 30 (8), 1219-1231.

Allahverdi, A. & Aldowaisan, T. (2000). No-wait and separate setup three-machine flowshop with total completion time criterion, International Transactions in Operational Research,7 (3), 245-64.

Allahverdi, A. & Aldowaisan, T. (2001). Minimizing total completion time in a no-wait flowshop with sequence-dependent additive changeover times. Journal of the Operational Research Society, 52 (4), 449-462.

Allahverdi, A., Gupta, J.N.D. & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega. The international Journal of Management Science, 27 (2), 219-239.

Allahverdi, A., Ng, C.T., Cheng, T.C.E. & Kovalyov, M.Y. (2008). A survey of scheduling problems with setups times or costs. European Journal of Operational Research, 187 (3), 985-1032.

Allahverdi, A. & Soroush, H.M. (2008). The significance of reducing setup times/setup costs. European Journal of Operational Research, 187 (3), 978-984.

Bianco, L., Dell’Olmo, P. & Giordani, S. (1999). Flow shop no-wait scheduling with sequence-dependent setup times and release dates. INFOR Journal, 37 (1), 3-19.

Brown, S.I., Mcgarvey, R. & Ventura, J. A. (2004). Total flowtime and makespan for a no-wait m-machine flowshop with set-up times separated. Journal of the Operational Research Society, 55 (6), 614-621.

Eren, T. (2010). A bicriteria m-machine flowshop scheduling with sequence-dependent setup times. Applied Mathematical Modelling, 34 (2), 284-293.

Fink, A. & Voβ, S. (2003). Solving the continuos flow-shop scheduling problem by metaheuristics. European Journal of Operational Research, 151 (2), 400-414.

Framinan, J. M. & Nagano, M. S. (2008). Evaluating the performance for makespan minimisation in no-wait flowshop sequencing, Journal of Materials Processing Technology, 197 (1-3), 1-9.

Framinan, J.M., Nagano, M.S. & Moccellin, J.V. (2010). An efficient heuristic for total flowtime minimization in no-wait flowshops. International Journal of Advanced Manufacturing Technology, 46 (9-12), 1049-1057.

França, P. M., Tin Jr, G. & Buriol, L. S. (2006). Genetic algorithms for the no-wait flowshop sequencing problem with time restrictions. International Journal of Production Research, 44 (5), 939-957.

Grabowski, J., Pempera, J. (2007). The permutation flowshop problem with blocking. A tabu search approach, Omega. The International Journal of Management Science, 35 (3), 302-311.

Gupta, J. N. D. (1986). Flowshop schedules with sequence-dependent setup times. Journal of Operations Research Society of Japan, 29 (3), 206-219.

Hall, N. G. & Sriskandarajah, C. (1996). A survey of machine scheduling problems with block-ing and no-wait in process. Operations Research, 44 (3), 510-525.

Kumar, S., Bagchi, T. P. & Sriskandarajah, C. (2000). Lot streaming and scheduling heuristics for m-machine no-wait flowshops. Computers & Industrial Engineering, 38 (1), 149-172.

Pan, Q.-K., Tasgetiren, M.F. & Liang, Y.-C. (2008). A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers & Operations Research, 35 (9), 2807-2839.

Ruiz, R. & Allahverdi, A. (2007a). Some effective heuristics for no-wait flowshops with setup times to minimize total completion time. Annals of Operations Research, 156 (1), 143-171.

Ruiz, R. & Allahverdi, A. (2007b). A. No-wait flowshop with separate setup times to minimize maximum lateness. The International Journal of Advanced Manufacturing Technology, 35 (5-6), 551-565.

Ruiz, R., Maroto, C. & Alcaraz, J. (2005). Solving the flowshop scheduling problem with sequence-dependent setup times using advanced metaheuristics. European Journal of Operational Research, 165 (1), 34-54.

Ruiz, R. & Stützle, T. (2008). An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research, 187 (3), 1143-1159.

Shyu, S. J., Lin, B. M. T. & Yin, P. Y. (2004). Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time. Computers & Industrial Engineering, 47 (2-3), 181-193.

Stafford Jr, E. F. & Tseng, F. T. (1990). On the Srikar-Ghosh MILP model for the NxM SDST flowshop problem. International Journal of Production Research, 28 (10), 1817-1830.

Stafford Jr, E. F. & Tseng, F. T. (2002). Two models for a family of flowshop sequencing problems. European Journal of Operational Research, 142 (2), 282-293.

Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64 (2), 278-285.

Wang, C., Li, X. & Wang, Q. (2010). Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion. European Journal of Operational Research, 206 (1), 64-72.

Yaurima, V., Burtseva, L. & Tchernykh, A. (2009). Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers. Computers & Industrial Engineering, 56 (4), 1452-1463.