Automatic design of dispatching rules for static scheduling conditions
- PDF / 1,323,488 Bytes
- 26 Pages / 595.276 x 790.866 pts Page_size
- 107 Downloads / 226 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL ARTICLE
Automatic design of dispatching rules for static scheduling conditions Marko Ðurasević1
· Domagoj Jakobović1
Received: 23 September 2019 / Accepted: 7 August 2020 © Springer-Verlag London Ltd., part of Springer Nature 2020
Abstract Dispatching rules (DRs) represent heuristic methods designed for solving various scheduling problems. Since it is hard to manually design new DRs, genetic programming is used to design them automatically. Most DRs are designed in a way that they can be applied under dynamic conditions. On the other hand, static problems are usually solved using various metaheuristic methods. However, situations exist in which metaheuristics might not be the best choice for static problems. Such situations can occur when the schedule needs to be constructed quickly so that the system starts executing as soon as possible, or when it is possible that certain changes happen during the execution of the system. For these cases, DRs are more suitable since they execute faster and can adapt to dynamic changes in the system. However, as most research is focused on developing DRs for dynamic conditions, they would perform poorly under static conditions, since they would not use all the information that is available. Therefore, there is a need to enable automatic development of DRs suitable for static and offline conditions. The objective of this paper is to analyse several methods by which automatically generated DRs can be adapted for static and offline scheduling conditions. In addition to look-ahead and iterative DRs which were studied previously, this paper proposes new terminal nodes, as well as the application of the rollout algorithm to adapt DRs for static conditions. The performance and execution time of all methods are compared with the results achieved by automatically generated DRs for dynamic conditions and genetic algorithms. The tested methods obtain a wide range of results and prove to be competitive both in their performance and execution speed with other approaches. As such, they are a viable alternative to metaheuristics since they can be used in situations where metaheuristics could not, but can offer either a better execution time or even competitive results. Keywords Genetic programming · Dispatching rules · Look-ahead · Rollout heuristic · Iterative dispatching rules · Unrelated machines environment · Static conditions
1 Introduction Scheduling represents an important decision-making process which has found its application in various areas, like scheduling planes on runways [1, 2], scheduling in manufacturing and assembly lines [3], scheduling in wafer fabrication [4, 5] and production plants [6], scheduling resources in clouds [7], staff scheduling [8], multiprocessor scheduling [9], or scheduling for radiotherapy pre-treatment [10]. The goal of scheduling is to perform a mapping between available activities and a set of resources to obtain
& Marko Ðurasevic´ [email protected] 1
Faculty of Electrical Engineering and Com
Data Loading...
