nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Heuristics in Permutation GOMEA for Solving the Permutation Flowshop Scheduling Problem

verfasst von : G. H. Aalvanger, N. H. Luong, P. A. N. Bosman, D. Thierens

Erschienen in: Parallel Problem Solving from Nature – PPSN XV

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

The recently introduced permutation Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) has shown to be an effective Model Based Evolutionary Algorithm (MBEA) for permutation problems. So far, permutation GOMEA has only been used in the context of Black-Box Optimization (BBO). This paper first shows that permutation GOMEA can be improved by incorporating a constructive heuristic to seed the initial population. Secondly, the paper shows that hybridizing with job swapping neighborhood search does not lead to consistent improvement. The seeded permutation GOMEA is compared to a state-of-the-art algorithm (VNS4) for solving the Permutation Flowshop Scheduling Problem (PFSP). Both unstructured and structured instances are used in the benchmarks. The results show that permutation GOMEA often outperforms the VNS4 algorithm for the PFSP with the total flowtime criterion.

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 Heavy-Tailed Mutation Operators in Single-Objective Combinatorial Optimization

Nächstes Kapitel On the Performance of Baseline Evolutionary Algorithms on the Dynamic Knapsack Problem

Aalvanger, G.: Incorporating domain knowledge in permutation gene-pool optimal mixing evolutionary algorithms. Master’s thesis. Utrecht University, The Netherlands (2017). https://dspace.library.uu.nl/handle/1874/353005

Bosman, P.A., Luong, N.H., Thierens, D.: Expanding from discrete Cartesian to permutation gene-pool optimal mixing evolutionary algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 637–644. ACM (2016)

Ceberio, J., Irurozki, E., Mendiburu, A., Lozano, J.A.: Extending distance-based ranking models in estimation of distribution algorithms. In: 2014 IEEE Congress on Evolutionary Computation, CEC, pp. 2459–2466, July 2014

Costa, W.E., Goldbarg, M.C., Goldbarg, E.G.: New VNS heuristic for total flowtime flowshop scheduling problem. Expert Syst. Appl. 39(9), 8149–8161 (2012)CrossRef

Jarboui, B., Eddaly, M., Siarry, P.: An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems. Comput. Oper. Res. 36, 2638–2646 (2009)MathSciNetCrossRef

Liu, J., Reeves, C.R.: Constructive and composite heuristic solutions to the \({\rm p}|| {\rm \sum } {C_i}\) scheduling problem. EJOR 132(2), 439–452 (2001)CrossRef

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

Tasgetiren, M.F., Pan, Q.-K., Suganthan, P.N., Chen, A.H.-L.: A discrete artificial bee colony algorithm for the permutation flow shop scheduling problem with total flowtime criterion. In: Proceedings of the IEEE World Congress on Computational Intelligence, WCCI-2010, pp. 137–144. IEEE (2010)

Thierens, D., Bosman, P.A.: Optimal mixing evolutionary algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 617–624 (2011)

10.

Watson, J.-P., Barbulescu, L., Whitley, L.D., Howe, A.E.: Contrasting structured and random permutation flow-shop scheduling problems. INFORMS J. Comput. 14(2), 98–123 (2002)MathSciNetCrossRef

11.

Xu, X., Xu, Z., Gu, X.: An asynchronous genetic local search algorithm for the permutation flowshop scheduling problem with total flowtime minimization. Expert Syst. Appl. 38, 7970–7979 (2011)CrossRef

Titel: Heuristics in Permutation GOMEA for Solving the Permutation Flowshop Scheduling Problem
verfasst von: G. H. Aalvanger
N. H. Luong
P. A. N. Bosman
D. Thierens
Verlag: Springer International Publishing
Buch: Parallel Problem Solving from Nature – PPSN XV
Print ISBN: 978-3-319-99252-5

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

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-99253-2_12

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"

Premium Partner