A Reinforcement Learning Approach for Scheduling Problems with Improved Generalization through Order Swapping
The scheduling of production resources (such as associating jobs to machines) plays a vital role for the manufacturing industry not only for saving energy, but also for increasing the overall efficiency. Among the different job scheduling problems, the Job Shop Scheduling Problem (JSSP) is addressed...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-04-01
|
| Series: | Machine Learning and Knowledge Extraction |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2504-4990/5/2/25 |
| _version_ | 1797593694197514240 |
|---|---|
| author | Deepak Vivekanandan Samuel Wirth Patrick Karlbauer Noah Klarmann |
| author_facet | Deepak Vivekanandan Samuel Wirth Patrick Karlbauer Noah Klarmann |
| author_sort | Deepak Vivekanandan |
| collection | DOAJ |
| description | The scheduling of production resources (such as associating jobs to machines) plays a vital role for the manufacturing industry not only for saving energy, but also for increasing the overall efficiency. Among the different job scheduling problems, the Job Shop Scheduling Problem (JSSP) is addressed in this work. JSSP falls into the category of NP-hard Combinatorial Optimization Problem (COP), in which solving the problem through exhaustive search becomes unfeasible. Simple heuristics such as First-In, First-Out, Largest Processing Time First and metaheuristics such as taboo search are often adopted to solve the problem by truncating the search space. The viability of the methods becomes inefficient for large problem sizes as it is either far from the optimum or time consuming. In recent years, the research towards using Deep Reinforcement Learning (DRL) to solve COPs has gained interest and has shown promising results in terms of solution quality and computational efficiency. In this work, we provide an novel approach to solve the JSSP examining the objectives generalization and solution effectiveness using DRL. In particular, we employ the Proximal Policy Optimization (PPO) algorithm that adopts the policy-gradient paradigm that is found to perform well in the constrained dispatching of jobs. We incorporated a new method called Order Swapping Mechanism (OSM) in the environment to achieve better generalized learning of the problem. The performance of the presented approach is analyzed in depth by using a set of available benchmark instances and comparing our results with the work of other groups. |
| first_indexed | 2024-03-11T02:13:05Z |
| format | Article |
| id | doaj.art-048fa23215094339b2d0795371f431fe |
| institution | Directory Open Access Journal |
| issn | 2504-4990 |
| language | English |
| last_indexed | 2024-03-11T02:13:05Z |
| publishDate | 2023-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Machine Learning and Knowledge Extraction |
| spelling | doaj.art-048fa23215094339b2d0795371f431fe2023-11-18T11:22:05ZengMDPI AGMachine Learning and Knowledge Extraction2504-49902023-04-015241843010.3390/make5020025A Reinforcement Learning Approach for Scheduling Problems with Improved Generalization through Order SwappingDeepak Vivekanandan0Samuel Wirth1Patrick Karlbauer2Noah Klarmann3ScaliRo GmbH, Eduard-Rüber-Straße 7, 83022 Rosenheim, GermanyFaculty of Management and Engineering, Rosenheim Technical University of Applied Sciences, Hochschulstraße 1, 83024 Rosenheim, GermanyFaculty of Management and Engineering, Rosenheim Technical University of Applied Sciences, Hochschulstraße 1, 83024 Rosenheim, GermanyFaculty of Management and Engineering, Rosenheim Technical University of Applied Sciences, Hochschulstraße 1, 83024 Rosenheim, GermanyThe scheduling of production resources (such as associating jobs to machines) plays a vital role for the manufacturing industry not only for saving energy, but also for increasing the overall efficiency. Among the different job scheduling problems, the Job Shop Scheduling Problem (JSSP) is addressed in this work. JSSP falls into the category of NP-hard Combinatorial Optimization Problem (COP), in which solving the problem through exhaustive search becomes unfeasible. Simple heuristics such as First-In, First-Out, Largest Processing Time First and metaheuristics such as taboo search are often adopted to solve the problem by truncating the search space. The viability of the methods becomes inefficient for large problem sizes as it is either far from the optimum or time consuming. In recent years, the research towards using Deep Reinforcement Learning (DRL) to solve COPs has gained interest and has shown promising results in terms of solution quality and computational efficiency. In this work, we provide an novel approach to solve the JSSP examining the objectives generalization and solution effectiveness using DRL. In particular, we employ the Proximal Policy Optimization (PPO) algorithm that adopts the policy-gradient paradigm that is found to perform well in the constrained dispatching of jobs. We incorporated a new method called Order Swapping Mechanism (OSM) in the environment to achieve better generalized learning of the problem. The performance of the presented approach is analyzed in depth by using a set of available benchmark instances and comparing our results with the work of other groups.https://www.mdpi.com/2504-4990/5/2/25Job Shop SchedulingProduction SchedulingReinforcement LearningMarkov Decision ProcessgeneralizationIndustry 4.0 |
| spellingShingle | Deepak Vivekanandan Samuel Wirth Patrick Karlbauer Noah Klarmann A Reinforcement Learning Approach for Scheduling Problems with Improved Generalization through Order Swapping Machine Learning and Knowledge Extraction Job Shop Scheduling Production Scheduling Reinforcement Learning Markov Decision Process generalization Industry 4.0 |
| title | A Reinforcement Learning Approach for Scheduling Problems with Improved Generalization through Order Swapping |
| title_full | A Reinforcement Learning Approach for Scheduling Problems with Improved Generalization through Order Swapping |
| title_fullStr | A Reinforcement Learning Approach for Scheduling Problems with Improved Generalization through Order Swapping |
| title_full_unstemmed | A Reinforcement Learning Approach for Scheduling Problems with Improved Generalization through Order Swapping |
| title_short | A Reinforcement Learning Approach for Scheduling Problems with Improved Generalization through Order Swapping |
| title_sort | reinforcement learning approach for scheduling problems with improved generalization through order swapping |
| topic | Job Shop Scheduling Production Scheduling Reinforcement Learning Markov Decision Process generalization Industry 4.0 |
| url | https://www.mdpi.com/2504-4990/5/2/25 |
| work_keys_str_mv | AT deepakvivekanandan areinforcementlearningapproachforschedulingproblemswithimprovedgeneralizationthroughorderswapping AT samuelwirth areinforcementlearningapproachforschedulingproblemswithimprovedgeneralizationthroughorderswapping AT patrickkarlbauer areinforcementlearningapproachforschedulingproblemswithimprovedgeneralizationthroughorderswapping AT noahklarmann areinforcementlearningapproachforschedulingproblemswithimprovedgeneralizationthroughorderswapping AT deepakvivekanandan reinforcementlearningapproachforschedulingproblemswithimprovedgeneralizationthroughorderswapping AT samuelwirth reinforcementlearningapproachforschedulingproblemswithimprovedgeneralizationthroughorderswapping AT patrickkarlbauer reinforcementlearningapproachforschedulingproblemswithimprovedgeneralizationthroughorderswapping AT noahklarmann reinforcementlearningapproachforschedulingproblemswithimprovedgeneralizationthroughorderswapping |