Multi-Agent Model based on Tabu Search for the Permutation Flow Shop Scheduling Problem

General information

Authors:
Hafewa BARGAOUI, Olfa BELKAHLA DRISS

DOI:
10.14201/ADCAIJ2014382737

Volume:
Regular Issue 3 (1), 2014

Keywords:

Scheduling; Permutation flow shop; Tabu Search; Multi-agent system

The objective of this work is to present a distributed approach for the problem of finding a minimum makespan in the permutation flow shop scheduling problem. The problem is strongly NP-hard and its resolution optimally within a reasonable time is impossible. For these reasons we opted for a Multi-agent architecture based on cooperative behaviour allied with the Tabu Search meta-heuristic. The proposed model is composed of two classes of agents: Supervisor agent, responsible for generating the initial solution and containing the Tabu Search core, and Scheduler agents which are responsible for the satisfaction of the constraints under their jurisdiction and the evaluation of all the neighborhood solutions generated by the Supervisor agent. The proposed approach has been tested on different benchmarks data sets and results demonstrate that it reaches high-quality solutions.

References

A computational study of the permutation flow shop problem based on a tight lower bound. Computers & Operations Research 32, pp. 1831–47 ( 2005)

A. Jain, B. Rangaswamy et S. Meeran : Job shop neighborhoods and move evaluation strategies, Department of Applied Physics, Electronic and Mechanical Engineering, University of Dundee, Dundee, Scotland, 2000.

Campbell H.G., Dudek R.A., Smith M.L. A heuristic algorithm for the n job, m machine sequencing problem. Management Science 16 (10), pp. B630- B637 (1970)

Dannenbring D.G. An evaluation of flow shop sequencing heuristics. Management Science 23(1), pp. 1174-82 (1977)

Deroussi L, Gourgand M, Norre S. Une adaptation efficace des mouvements de Lin et Kernighan pour le flow-shop de permutation. 8éme Conférence Internationale de MOdélisation et SIMulation: MOSIM, Hammamet, Tunisie (2010)

Dong, X.; H. Huang; P. Chen. An improved NEH-based heuristic for the permutation flow shop problem. Computers & Operations Research. 35(12), pp. 3962-68 (2008)

Ekşioğlu B, Ekşioğlu S.D, Jain P. A tabu search algorithm for the flow shop scheduling problem with changing neighborhoods. Computers & Industrial Engineering, Vol 54(1) pp. 1-11( 2008)

Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman; (1979)

Glover F. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 13, pp. 533-49 (1986)

Graham, R.L., E. Lawler, J.K. Lenstra, A. Rinnooy Kan. Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics 5, pp. 236-87 (1979)

Johnson, S.M. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1, pp. 61-68. (1954)

Liu, Y.F.; Liu, S.Y. A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing 13.13( 3), pp. 1459-1463(2013)

Nawaz M, Enscore Jr. EE, Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA: The International Journal of Management Science 11 (1): 91–95 (1983)

Reeves C, Yamada T. Genetic algorithms, path relinking and the flowshop sequencing problem. Evolutionary Computation 6, pp. 45–60, (1998)

Ruiz R., Stützle T. A simple and effective iterated greedy algorithm for the permutation flow shop scheduling problem. European Journal of Operational Research 177, pp. 2033-49 (2007)

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

Taillard, E. Some efficient heuristic methods for the flowshop sequencing problem. European Journal of Operational Research, Vol. 47, pp. 65-74. (1990)

Tseng F.T., Stafford Jr. E.F., Gupta J.N.D. An empirical analysis of integer programming formulations for the permutation flowshop. OMEGA, The International Journal of Management Science 32 (4):285–93, 2004.

Ying K.C.; Liao C.J. An ant colony system for permutation flow-shop sequencing. Computers & Operations Research 31:791–801, 2004

How to cite item?