Loading…
A novel approach to job scheduling applying deep reinforcement learning and neural network architectures of natural language processing
Oliveira Hitzges, Diego de
This master thesis presents a novel approach to Job Scheduling based on Deep Reinforcement Learning. It treats the Job Scheduling Problems of deterministically and non-preemptively scheduling on Unrelated Parallel Machines. These are allowed to be initially occupied and can be deactivated during the process. The objective is to minimize the sum of the makespan together with the weighted tardinesses of the Jobs and Machines. The problem structure is embedded into a Deep Reinforcement Learning environment. Policies are identified as scheduling algorithms. Any ensuing sequence of state-action pairs denotes a feasible schedule. The sum over their transition costs equals the respective scheduling costs. Each state is associated with an instance in which a Machine becomes unoccupied. The assignments of pending Jobs form the set of feasible actions, together with the decision to turn it off in case that there is at least one more Machine operating. A sophisticated Neural Network is presented that induces an estimation of the optimal policy, corresponding to a least-cost schedule. It is based on Natural Language Processing Architectures. The Jobs and Machines get processed as time series by an LSTM and subsequently encoded by a Transformer Encoder. An Action-Pointer Decoder then points to the feasible action estimated to be optimal. Consequently, the Neural Network is able to process any number of Jobs and Machines. It is trained and tested supervisedly by computing the scheduling costs for Job Scheduling Problems of 8 Jobs and 4 Machines. Applying it to unseen problems of the same conditions induces schedules that yield additional costs of 2.51\% relative to the optimal ones. When comparing it to standard heuristics on Job Scheduling Problems with up to 100 Jobs and 15 Machines, the Neural Network significantly outperforms for up to 100 Jobs and 10 Machines and vastly outperforms in the range of 3 to 8 Machines and up to 30 Jobs. Under these circumstances, applying a combinatorial scheduling algorithm in general results in average costs 20\% to 40\% higher than with the use of the Neural Network. Further Deep Reinforcement Learning based techniques are presented to enable the training of the Neural Network on higher numbers of Jobs.
Diese Masterarbeit stellt einen neuartigen Ansatz zum Job Scheduling basierend auf Deep Reinforcement Learning vor. Sie behandelt das Job Scheduling Problem, deterministisch und nicht-präemptiv auf unabhängigen, parallelen Maschinen zu planen. Diese können zu Beginn belegt sein und während des Prozesses deaktiviert werden. Das Ziel besteht darin, die Summe aus der Prozessdauer und den gewichteten Verspätungen von Jobs und Maschinen zu minimieren. Die Struktur des Problems wird in eine Deep Reinforcement Learning Umgebung eingebettet. Policies werden als Planungsalgorithmen identifiziert. Jede resultierende Sequenz von Zustands-Aktions-Paaren stellt einen durchführbaren Zeitplan dar. Die Summe der Übergangskosten entspricht den jeweiligen Planungskosten. Jeder Zustand entspricht einem Zeitpunkt, in dem eine Maschine unbesetzt und somit verfügbar wird. Die Zuweisung ausstehender Jobs auf diese Maschine bildet zusammen mit der Entscheidung, sie auszuschalten, falls mindestens eine weitere Maschine betrieben wird, die Menge der durchführbaren Aktionen. Es wird ein ausgefeiltes Neuronales Netzwerk vorgestellt, das eine Schätzung der optimalen Policy induziert, die einem kostenoptimalen Zeitplan entspricht. Das Netzwerk basiert auf Architekturen aus dem Bereich des Natural Language Processing. Jobs und Maschinen werden als Zeitreihen von einem LSTM verarbeitet und anschließend von einem Transformer Encoder codiert. Ein Action-Pointer Decoder „zeigt“ dann auf die durchführbare Aktion, die als optimal eingeschätzt wird. Folglich kann das Neuronale Netzwerk eine beliebige Anzahl von Jobs und Maschinen verarbeiten. Dieses wird trainiert, validiert und getestet, indem die Planungskosten für Job Scheduling Probleme mit 8 Jobs und 4 Maschinen explizit berechnet werden. Bei seiner Anwendung auf unbekannte Probleme unter denselben Bedingungen entstehen Zeitplanungen, die Zusatzkosten von 2,51\% erzeugen in Bezug auf die jeweiligen theoretischen Minimalkosten. Im Vergleich zu Standard-Heuristiken bei Job Scheduling Problemen mit bis zu 100 Jobs und 15 Maschinen übertrifft das Neuronale Netzwerk diese signifikant bei bis zu 100 Jobs und 10 Maschinen. Im Bereich von 3 bis 8 Maschinen und bis zu 30 Jobs überragt es diese sogar bei weitem. Unter diesen Bedingungen führt die Verwendung eines solchen kombinatorischen Planungsalgorithmus in der Regel zu 20\% bis 40\% höheren relativen Kosten. Weitere auf Deep Reinforcement Learning basierende Techniken werden vorgestellt, um das Training des Neuronalen Netzwerks auf größere Anzahlen von Jobs zu ermöglichen.
