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