A Genetic Programming Learning Approach to Generate Dispatching Rules for Flexible Shop Scheduling Problems
- Author(s)
- Roland Braune, Frank Benda, Karl Franz Dörner, Richard Hartl
- Abstract
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(s)
- Department of Business Decisions and Analytics, Department of Accounting, Innovation and Strategy, Research Network Data Science
- External organisation(s)
- Christian Doppler Research Association
- Journal
- International Journal of Production Economics
- Volume
- 243
- No. of pages
- 13
- ISSN
- 0925-5273
- DOI
- https://doi.org/10.1016/j.ijpe.2021.108342
- Publication date
- 01-2022
- Peer reviewed
- Yes
- Austrian Fields of Science 2012
- 102001 Artificial intelligence, 101015 Operations research, 502028 Production management
- Keywords
- ASJC Scopus subject areas
- Economics and Econometrics, Business, Management and Accounting(all), Industrial and Manufacturing Engineering, Management Science and Operations Research
- Portal url
- https://ucris.univie.ac.at/portal/en/publications/a-genetic-programming-learning-approach-to-generate-dispatching-rules-for-flexible-shop-scheduling-problems(f5ec7b0e-838d-42c9-8ddb-6f3df9e9e182).html