van Ekeris, T.; Meyes, R.; Meisen, T.: Discovering Heuristics And Metaheuristics For Job Shop Scheduling From Scratch Via Deep Reinforcement Learning. In: Herberger, D.; Hübner, M. (Eds.): Proceedings of the Conference on Production Systems and Logistics : CPSL 2021. Hannover : publish-Ing., 2021, S. 709-718. DOI:https://doi.org/10.15488/11231
Zusammenfassung: | |
Scheduling is the mathematical problem of allocating tasks to resources considering certain constraints. The goal is to achieve the best possible scheduling quality given a quality metric like makespan. Typical scheduling problems, including the classic Job Shop Scheduling Problem (JSP or JSSP), are NP-hard; meaning it is infeasible to use optimal solvers for big problem sizes. Instead, heuristics are frequently used to find suboptimal solutions in polynomial time, especially in real-world applications. Recently, Deep Reinforcement Learning (DRL) has also been applied to find solutions for planning problems like the JSP. In DRL, agents learn solution strategies for specific problem classes through the principle of trial and error. In this paper, we explore the connection between known heuristics and DRL: Heuristics always rely on features that can be extracted from the considered problem with low computational effort. We show that DRL agents, for which we limit the available observation to the underlying features of well-known heuristics, learn the behaviour of the more qualitative heuristics from scratch, while they do not learn the behaviour of less qualitative heuristics that would also be possible learning outcomes given the same feature as observation. Additionally, we motivate the use of DRL as a metaheuristic generator by training with the features of multiple basic heuristics. We show promising results that indicate that this learned metaheuristic finds better schedules in terms of makespan than any single simple heuristic – while only requiring simple computations in the time-critical solution phase and thus being faster than optimal solvers. | |
Lizenzbestimmungen: | CC BY 3.0 DE |
Publikationstyp: | BookPart |
Publikationsstatus: | publishedVersion |
Erstveröffentlichung: | 2021 |
Die Publikation erscheint in Sammlung(en): | Proceedings CPSL 2021 Proceedings CPSL 2021 |
Pos. | Land | Downloads | ||
---|---|---|---|---|
Anzahl | Proz. | |||
1 | Germany | 350 | 32,96% | |
2 | United States | 194 | 18,27% | |
3 | Russian Federation | 118 | 11,11% | |
4 | China | 66 | 6,21% | |
5 | No geo information available | 27 | 2,54% | |
6 | Iran, Islamic Republic of | 24 | 2,26% | |
7 | Netherlands | 20 | 1,88% | |
8 | Ireland | 17 | 1,60% | |
9 | India | 16 | 1,51% | |
10 | Canada | 15 | 1,41% | |
andere | 215 | 20,24% |
Hinweis
Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.