A Genetic Programming Learning Approach to Generate Dispatching Rules for Flexible Shop Scheduling Problems

Autor(en)
Roland Braune, Frank Benda, Karl Franz Dörner, Richard Hartl
Abstrakt

This paper deals with a Genetic Programming (GP) approach for solving flexible shop scheduling problems. The adopted approach aims to generate priority rules in the form of an expression tree for dispatching jobs. Therefore, in a list-scheduling algorithm, the available jobs can be ranked using the tree-based priority rules generated using GP.

These priority rules were tested on benchmark problem settings, such as those of Brandimarte and Lawrence, in a static and dynamic environment. The GP approaches were then applied to a special case based on the problem setting of an industrial partner. The goal of these approaches was to minimize the maximum completion time of all jobs, which is known as the makespan.

To reach this goal, we considered job assignment and machine sequencing decisions simultaneously in a single-tree representation and compared this single tree with a multi-tree approach, where the terminal sets (job- and machine-related) were strictly separated. This resulted in two parallel GP populations; they were used to first decide which job to choose and then which machine it should be assigned to. Furthermore, for both tree approaches, we implemented an iterative variant that stores recorded information of past schedules to achieve further improvements. Computational experiments revealed a consistent advantage compared to the existing advanced priority rules from the literature with considerably increased performance under the presence of unrelated parallel machines and larger instances in general.

Organisation(en)
Institut für Business Decisions and Analytics, Institut für Rechnungswesen, Innovation und Strategie, Forschungsverbund Data Science
Externe Organisation(en)
Christian Doppler Forschungsgesellschaft
Journal
International Journal of Production Economics
Band
243
Anzahl der Seiten
13
ISSN
0925-5273
DOI
https://doi.org/10.1016/j.ijpe.2021.108342
Publikationsdatum
01-2022
Peer-reviewed
Ja
ÖFOS 2012
102001 Artificial Intelligence, 101015 Operations Research, 502028 Produktionswirtschaft
Schlagwörter
ASJC Scopus Sachgebiete
Economics and Econometrics, Business, Management and Accounting(all), Industrial and Manufacturing Engineering, Management Science and Operations Research
Link zum Portal
https://ucris.univie.ac.at/portal/de/publications/a-genetic-programming-learning-approach-to-generate-dispatching-rules-for-flexible-shop-scheduling-problems(f5ec7b0e-838d-42c9-8ddb-6f3df9e9e182).html