Flow-shop sequencing using hybrid simulated annealing
Tóm tắt
Simulated annealing (SA) heuristics have been successfully applied on a variety of complex optimization problems. This paper presents a new hybrid SA approach for the permutation flow-shop scheduling (FSS) problem. FSS is known to be NP-hard, and thus the right way to proceed is through the use of heuristics techniques. The proposed approach combines the characteristics of a canonical SA procedure together with features borrowed from the field of genetic algorithms (GAs), such as the use of a population of individuals and the use of a novel, non-standard recombination operator for generating solutions. The approach is easily implemented and performs near-optimal schedules in a rather short computation time. Experiments over multiple benchmarks test problems show that the developed approach has higher performance than that of other FSS meta-heuristic approaches, generating schedules of shorter makespans faster. The experiments include comparisons between the proposed hybrid model, a genetic algorithm, and two other standard simulated annealing approaches. The final solutions obtained by the method are within less than 1% in average from the optimal solutions obtained so far.
Tài liệu tham khảo
Ben-Daya, M. and Al-Fawzan, M. (1998) A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109, 88–95.
Cambell, H., Dudek, R. and Smith, M. (1970) A heuristic algorithm for the n-job, m-machine sequencing problem. Management Science, 16B, 630–637.
Dannenbring, D. (1977) An evaluation of flow shop sequencing heuristics. Management Science, 23, 1174–1182.
Dowsland, A. (1995) Simulated Annealing. In Modern Heuristics Techniques for Combinatorial Problems, Reeves, C. R. (ed.), Blackwell Scientific Publishers, Oxford, pp. 20–69.
Gupta, J. (1971) A functional heuristic algorithm for the flow shop scheduling problem. Operations Research Quarterly, 22, 39–47.
Holland, J. H. (1975) Adaptation in Natural and Artificial System: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The University of Michigan Press, Ann Arbor.
Ignall, E. and Schrage, L. E. (1965) Application of branch and bound technique to some flow-shop problem. Operations Research, 13, 400–412.
Ishibuchi, H., Misaki, S. and Tanaka, H. (1995) Modified simulated annealing algorithms for the flow shop sequencing problem. European Journal of Operational Research, 81, 388–398.
Johnson, S. M. (1954) Optimal two-and three stage production schedules with set up times included. Naval Research Logistics Quarterly, 1, 61–68.
Kirkpatrick, S., Gelatt, C. D., Jr. and Vecchi, M. P. (1983) Optimization by simulated annealing. Science, 220, 671–680.
Lundy, M. and Mees, A. (1986) Convergence of an annealing algorithm. Mathematical Programming, 34, 111–124.
Nawaz, M., Enscore, E. and Ham, I. (1983) A heuristic for the m-machine n-job flow shop sequencing problem. Omega, 11, 91–95.
Ogbu, F. A. and Smith, D. K. (1990) The application of the simulated annealing algorithm to the solution of the n/m/C max flow shop problem. Computers & Operations Research, 17(3), 243–253.
Osman, I. H. and Potts, C. N. (1989) Simulated annealing for permutation flow-shop scheduling. Omega, 17(6), 551–557.
Palmer, D. (1965) Sequencing jobs through a multi-stage process in the minimum total time-a quick method of obtaining a near optimum. Operations Research Quarterly, 16, 101–107.
Reeves, C. R. (1995) A genetic algorithm for flowshop sequencing. Computers and Operations Research, 22(1), 5–13.
Rinnooy Kan, A. H. G. (1976) Machine Scheduling Problems: Classification, Complexity and Computations, Martinus Nijhoff, The Hague.
Taillard, E. (1990) Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47, 65–74.
Taillard, E. (1993) Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285.
Tao, G. and Michalewicz, Z. (1998) Inver-over Operator for the TSP. Proc. of the 5th Parallel Problem Solving from Nature, T. Baeck et al. (eds.), Amsterdam, September 27–30, Springer-Verlag, Lecture Notes in Computer Science, pp. 803–812.
Tian, P., Ma, J. and Zhang, D.-M. (1999) Application of simulated annealing to the combinatorial optimization problem with permutation property: An investigation of generation mechanism. European Journal of Operational Research, 118, 81–94.