nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Distributed Tabu Searches in Multi-agent System for Permutation Flow Shop Scheduling Problem

verfasst von : Olfa Belkahla Driss, Chaouki Tarchi

Erschienen in: Hybrid Artificial Intelligent Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we propose a distributed multi-agent approach to solve the permutation flow shop scheduling problem for the objective of minimizing the makespan. This approach consists of two types of agents that cooperate to find a solution for this problem. A mediator agent who is responsible for generating the initial solution with NEHT heuristic, and scheduler agents, each applying a tabu search to refine a specific sequence of jobs which differs from those of other agents. Computational experiments confirm that our approach provides good results equal to or better than the ones given by other approaches with which we have made comparisons.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Trading-off Accuracy vs Energy in Multicore Processors via Evolutionary Algorithms Combining Loop Perforation and Static Analysis-Based Scheduling

Nächstes Kapitel Content Based Image Retrieval for Large Medical Image Corpus

Battiti, R., Protasi, M.: Reactive search, a history-sensitive heuristic for max-sat. J. Exp. Algorithmics JEA 2(2) (1997)

Bargaoui, H., Driss, O.B.: Multi-Agent Model based on Tabu Search for the Permutation Flow Shop Scheduling Problem. Advances in Distributed Computing and Artificial Intelligence. Springer International Publishing, Switzerland (2001)

Campbell, H.G., Dudek, R.A., Smith, M.L.: A heuristic algorithm for the n job, m machine sequencing problem. Manage. Sci. 16(10), B630–B637 (1970)CrossRefMATH

Dong, X., Huang, H., Chen, P.: An improved NEH-based heuristic for the permutation flow shop problem. Comput. Oper. Res. 35(12), 3962–3968 (2008)CrossRefMATH

Daouas, T., Ghedira, K., Muller, J.P.: How to schedule a flow shop plant by agents. In: Applications of Artificial Intelligence in Engineering, Computational Mechanics, pp. 73–80 (1995)

Deroussi, et al.: New effective neighborhoods for the permutation flow shop problem. Research report LIMOS/RR-06-09 (2006)

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

Duvivier, D.: Etude de l’hybridation des métaheuristiques, application à un problème d’ordonnancement de type job shop, Université du Littorial côté d’opale (2000)

Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13, 533–549 (1986)CrossRefMATHMathSciNet

10.

Grabowski, J., Wodecki, M.: A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion. Comput. Oper. Res. 31, 1891–1909 (2004)CrossRefMATHMathSciNet

11.

Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 236–287 (1979)

12.

Hajinejada, D., Salmasib, N., Mokhtari, R.: A fast hybrid particle swarm optimization algorithm for flow shop sequence dependent group scheduling problem. Scientia Iranica 18(3), 759–764 (2011)CrossRef

13.

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

14.

Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Res. Logistics Q. 1, 61–68 (1954)CrossRef

15.

Ladhari, T., Haouari, M.: A computational study of the permutation flow shop problem based on a tight lower bound. Comput. Oper. Res. 32, 1831–1847 (2005)CrossRef

16.

Li, X., Yin, M.: A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem. Scientia Iranica 19(6), 1921–1935 (2012)CrossRef

17.

Liu, Y.F., Liu, S.Y.: A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Appl. Soft Comput. 13(3), 1459–1463 (2013)CrossRef

18.

Mazure, B., Saïs, L., Grégoire, E.: Boosting complete techniques thanks to local search methods. Ann. Math. Artif. Intell. 22(3–4), 319–331 (1998)CrossRefMATH

19.

Nagano, M.S., Ruiz, R., Lorena, L.A.N.: A constructive genetic algorithm for permutation flowshop scheduling. Comput. Ind. Eng. 55, 195–207 (2008)CrossRef

20.

Nawaz, M., Enscore, E.E., Ham, I.: A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA Int. J. Manage. Sci. 11(1), 91–95 (1983)CrossRef

21.

Reeves, C., Yamada, T.: Genetic algorithms, path relinking and the flowshop sequencing problem. Evol. Comput. 6(1), 45–60 (1998)CrossRef

22.

Yellanki, S.: Simulated Annealing Approach to Flow Shop Scheduling (2013)

23.

Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64(2), 278–285 (1993)CrossRefMATH

24.

Taillard, E.: Some efficient heuristic methods for the flowshop sequencing problem. Eur. J. Oper. Res. 47, 65–74 (1990)CrossRefMATHMathSciNet

25.

Tseng, F.T., Stafford Jr., E.F., Gupta, J.N.D.: An empirical analysis of integer programming formulations for the permutation flowshop. OMEGA Int. J. Manage. Sci. 32(4), 285–293 (2004)CrossRef

26.

Zobolas, G.I., Tarantilis, C.D., Ioannou, G.: Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. University of Economics and Business (2008)

Titel: Distributed Tabu Searches in Multi-agent System for Permutation Flow Shop Scheduling Problem
verfasst von: Olfa Belkahla Driss
Chaouki Tarchi
Verlag: Springer International Publishing
Buch: Hybrid Artificial Intelligent Systems
Print ISBN: 978-3-319-19643-5

Electronic ISBN: 978-3-319-19644-2

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-19644-2_58

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"