Job shop scheduling problem optimization by means of graph-based algorithm

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F62156489%3A43110%2F21%3A43919551" target="_blank" >RIV/62156489:43110/21:43919551 - isvavai.cz</a>

Alternative codes found

RIV/00216305:26220/21:PU139924

Result on the web

<a href="https://doi.org/10.3390/app11041921" target="_blank" >https://doi.org/10.3390/app11041921</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/app11041921" target="_blank" >10.3390/app11041921</a>

Result language

angličtina

Original language name

Job shop scheduling problem optimization by means of graph-based algorithm

Original language description

In this paper we introduce the draft of a new graph-based algorithm f or 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&apos;s classic implementation. The acquired results of these experiments were compared by each algorithm&apos;s required time (to find the best solution) as well as makespan. The comparison of these results showed that the proposed algorithm exhibited a promis-ing 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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

20202 - Communication engineering and systems

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2021

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Applied Sciences

ISSN

2076-3417

e-ISSN

—

Volume of the periodical

11

Issue of the periodical within the volume

4

Country of publishing house

CH - SWITZERLAND

Number of pages

16

Pages from-to

1921

UT code for WoS article

000632101900001

EID of the result in the Scopus database

2-s2.0-85101967299