Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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

Identifikátory výsledku

  • Kód výsledku v 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>

  • Nalezeny alternativní kódy

    RIV/00216305:26220/21:PU139924

  • Výsledek na webu

    <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>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

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

  • Popis výsledku v původním jazyce

    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.

  • Název v anglickém jazyce

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

  • Popis výsledku anglicky

    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.

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • CEP obor

  • OECD FORD obor

    20202 - Communication engineering and systems

Návaznosti výsledku

  • Projekt

  • Návaznosti

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2021

  • Kód důvěrnosti údajů

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

Údaje specifické pro druh výsledku

  • Název periodika

    Applied Sciences

  • ISSN

    2076-3417

  • e-ISSN

  • Svazek periodika

    11

  • Číslo periodika v rámci svazku

    4

  • Stát vydavatele periodika

    CH - Švýcarská konfederace

  • Počet stran výsledku

    16

  • Strana od-do

    1921

  • Kód UT WoS článku

    000632101900001

  • EID výsledku v databázi Scopus

    2-s2.0-85101967299