Detail publikace

Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm

ŠŤASTNÝ, J. ŠKORPIL, V. BALOGH, Z. KLEIN, R.

Originální název

Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

Genetic algorithms; graph-based algorithm; Job Shop Scheduling Problem; optimization

Autoři

ŠŤASTNÝ, J.; ŠKORPIL, V.; BALOGH, Z.; KLEIN, R.

Vydáno

22. 2. 2021

Nakladatel

MDPI

Místo

Basel, Switzerland

ISSN

2076-3417

Periodikum

Applied Sciences - Basel

Ročník

11

Číslo

4

Stát

Švýcarská konfederace

Strany od

1

Strany do

16

Strany počet

16

URL

https://www.mdpi.com/2076-3417/11/4/1921/htm

Plný text v Digitální knihovně

http://hdl.handle.net/11012/196375

BibTex

@article{BUT170162,
  author="Jiří {Šťastný} and Vladislav {Škorpil} and Zoltán {Balogh} and Richard {Klein}",
  title="Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm",
  journal="Applied Sciences - Basel",
  year="2021",
  volume="11",
  number="4",
  pages="1--16",
  doi="10.3390/app11041921",
  issn="2076-3417",
  url="https://www.mdpi.com/2076-3417/11/4/1921/htm"
}