Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm
Open Access
- 22 February 2021
- journal article
- research article
- Published by MDPI AG in Applied Sciences
- Vol. 11 (4), 1921
- https://doi.org/10.3390/app11041921
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.Keywords
This publication has 26 references indexed in Scilit:
- Feature-based initial population generation for the optimization of job shop problemsJournal of Zhejiang University SCIENCE C, 2010
- An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffersComputers & Operations Research, 2008
- Clonal Selection Based Memetic Algorithm for Job Shop Scheduling ProblemsJournal of Bionic Engineering, 2008
- An Effective PSO and AIS-Based Hybrid Intelligent Algorithm for Job-Shop SchedulingIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2008
- A very fast TS/SA algorithm for the job shop scheduling problemComputers & Operations Research, 2008
- A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problemEuropean Journal of Operational Research, 2007
- Use of an Artificial Immune System for Job Shop SchedulingLecture Notes in Computer Science, 2003
- A revised simulated annealing algorithm for obtaining the minimum total tardiness in job shop scheduling problemsInternational Journal of Systems Science, 2000
- Some new results on simulated annealing applied to the job shop scheduling problemEuropean Journal of Operational Research, 1999
- Applying tabu search to the job-shop scheduling problemAnnals of Operations Research, 1993