Full Text

Turn on search term navigation

© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

Abstract

In this paper we introduce the draft of a new graph-based algorithm for optimization of scheduling problems. Our algorithm is based on the Generalized Lifelong Planning A* algorithm, which is usually used for path planning for mobile robots. It was tested on the Job Shop Scheduling Problem against a genetic algorithm’s classic implementation. The acquired results of these experiments were compared by each algorithm’s required time (to find the best solution) as well as makespan. The comparison of these results showed that the proposed algorithm exhibited a promising convergence rate toward an optimal solution. Job shop scheduling (or the job shop problem) is an optimization problem in informatics and operations research in which jobs are assigned to resources at particular times. The makespan is the total length of the schedule (when all jobs have finished processing). In most of the tested cases, our proposed algorithm managed to find a solution faster than the genetic algorithm; in five cases, the graph-based algorithm found a solution at the same time as the genetic algorithm. Our results also showed that the manner of priority calculation had a non-negligible impact on solutions, and that an appropriately chosen priority calculation could improve them.

Details

Title
Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm
Author
Stastny, Jiri 1   VIAFID ORCID Logo  ; Skorpil, Vladislav 2   VIAFID ORCID Logo  ; Balogh, Zoltan 3   VIAFID ORCID Logo  ; Klein, Richard 4 

 Institute of Automation and Computer Science, Brno University of Technology, 616 69 Brno, Czech Republic; [email protected]; Department of Informatics, Mendel University in Brno, 613 00 Brno, Czech Republic 
 Department of Telecommunications, Brno University of Technology, 616 00 Brno, Czech Republic; [email protected] 
 Computer Science Department, Constantine the Philosopher University in Nitra, 949 74 Nitra, Slovakia; [email protected] 
 Institute of Automation and Computer Science, Brno University of Technology, 616 69 Brno, Czech Republic; [email protected] 
First page
1921
Publication year
2021
Publication date
2021
Publisher
MDPI AG
e-ISSN
20763417
Source type
Scholarly Journal
Language of publication
English
ProQuest document ID
2534618187
Copyright
© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.