Discovering Heuristics And Metaheuristics For Job Shop Scheduling From Scratch Via Deep Reinforcement Learning

Downloadstatistik des Dokuments (Auswertung nach COUNTER):

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

Zeitraum, für den die Download-Zahlen angezeigt werden:

Jahr: 
Monat: 

Summe der Downloads: 1.062




Kleine Vorschau
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

Verteilung der Downloads über den gewählten Zeitraum:

Herkunft der Downloads nach Ländern:

Pos. Land Downloads
Anzahl Proz.
1 image of flag of Germany Germany 350 32,96%
2 image of flag of United States United States 194 18,27%
3 image of flag of Russian Federation Russian Federation 118 11,11%
4 image of flag of China China 66 6,21%
5 image of flag of No geo information available No geo information available 27 2,54%
6 image of flag of Iran, Islamic Republic of Iran, Islamic Republic of 24 2,26%
7 image of flag of Netherlands Netherlands 20 1,88%
8 image of flag of Ireland Ireland 17 1,60%
9 image of flag of India India 16 1,51%
10 image of flag of Canada Canada 15 1,41%
    andere 215 20,24%

Weitere Download-Zahlen und Ranglisten:


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.