Effective Design of the Simulated Annealing Algorithm for the Flowshop Problem with Minimum Makespan Criterion

• Autorzy: Hurkała J. , Hurkała A.
• Języki publikacji: EN

Abstrakty

EN

In this paper we address the n-job, m-machine flowshop scheduling problem with minimum completion time (makespan) as the performance criterion. We describe an efficient design of the Simulated Annealing algorithm for solving approximately this NP-hard problem. The main difficulty in implementing the algorithm is no apparent analogy for the temperature as a parameter in the flowshop combinatorial problem. Moreover, the quality of solutions is dependent on the choice of cooling scheme, initial temperature, number of iterations, and the temperature decrease rate at each step as the annealing proceeds. We propose how to choose the values of all the aforementioned parameters, as well as the Boltzmann factor for the Metropolis scheme. Three perturbation techniques are tested and their impact on the solutions quality is analyzed. We also compare a heuristic and randomly generated solutions as initial seeds to the annealing optimization process. Computational experiments indicate that the proposed design provides very good results - the quality of solutions of the Simulated Annealing algorithm is favorably compared with two different heuristics.

Słowa kluczowe

EN

flowshop; heuristics; makespan; simulated annealing

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2012
• Tom: nr 2
• Strony: 92--98
• Opis fizyczny: Bibliogr. 17 poz., tab.

Twórcy

autor

Hurkała J.

autor

Hurkała A.

• Institute of Control and Computation Engineering, Warsaw University of Technology, Nowowiejska st 15/19, 00-665 Warsaw, Poland,

Bibliografia

• [1] M. R. Garey, “The complexity of flowshop and jobshop scheduling”, Math. Oper. Res., vol. 1, no. 2, pp. 117–129, 1976.
• [2] H. G. Campbell, R. A. Dudek and M. L. Smith, “A heuristic algorithm of the n-job, m-machine sequencing problem”, Manag. Sci., vol. 16, pp. 630–637, 1970.
• [3] M. Nawaz, E. Enscore Jr, and I. Ham, “A heuristic algorithm for the m-machine, n-job flowshop sequencing problem”, OMEGA Int. J. Manag. Sci., vol. 11, pp. 91–95, 1983.
• [4] F. A. Ogbu and D. K. Smith, “The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem”, Comput. Oper. Res., vol. 17, no. 3, pp. 243–253, 1990.
• [5] J. Hurkała and A. Hurkała, “Effective design of the simulated annealing algorithm for the flowshop problem with minimum makespan criterion”, in 9th Int. Conf. Decision Support Telecomm. Inform. Society DSTIS 2011 , Warsaw, Poland, 2011.
• [6] M. Wodecki and W. Bożejko, “Solving the flow shop problem by parallel simulated annealing”, LNCS, vol. 2328, pp. 597–600, 2006.
• [7] E. Taillard, “Some efficient heuristic methods for flow shop sequencing”, Eur. J. Oper. Res., vol. 47, pp. 65–74, 1990.
• [8] J. Grabowski and J. Pempera, “New block properties for the permutation flow-shop problem with application in TS”, J. Oper. Res. Soc., vol. 52, pp. 210–220, 2001.
• [9] E. Nowicki, “The permutation flow shop with buffers: a tabu search approach”, Eur. J. Oper. Res., vol. 116, pp. 205–219, 1999.
• [10] E. Nowicki and C. Smutnicki, “A fast tabu search algorithm for the permutation flowshop problem”, Eur. J. Oper. Res., vol. 91, pp. 160–175, 1996.
• [11] C. R. Reeves, “A genetic algorithm for flowshop sequencing”. Comput. Oper. Res., vol. 22, pp. 5–13, 1995.
• [12] C. R. Reeves and T. Yamada, “Genetic algorithms, path relinking, and the flowshop sequencing problem”, Evol. Comput., vol. 6, no. 1, pp. 230–234, 1998.
• [13] S. R. Hejazi and S. Saghafian, “Flowshop-scheduling problems with makespan criterion: a review”, Int. J. Prod. Res., vol. 43, no. 14, pp. 2895–2929, 2005.
• [14] S. Kirkpatrick, C. D. Gellat and M. P. Vecchi, “Optimization by simulated annealing”, Science, vol. 220, pp. 671–680, 1983.
• [15] V. ˇCern´y, “Thermodynamical approach to travelling salesman problem: An efficient simulation algorithm”. J. Optim. Theory Appl., vol. 45, pp. 41–51, 1985.
• [16] C. Koulamas, S. R. Antony, and R. Jaen, “A survey of simulated annealing applications to operations research problems”, Omega, vol. 22, no. 1, pp. 41–56, 1994.
• [17] E. Taillard, “Benchmarks for basic scheduling problems”, Eur. J. Oper. Res., vol. 64, pp. 278–285, 1993.