Data-driven Algorithm for Scheduling with Total Tardiness

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00340436" target="_blank" >RIV/68407700:21230/20:00340436 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/20:00340436

Výsledek na webu

<a href="https://doi.org/10.5220/0008915300590068" target="_blank" >https://doi.org/10.5220/0008915300590068</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5220/0008915300590068" target="_blank" >10.5220/0008915300590068</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Data-driven Algorithm for Scheduling with Total Tardiness

Popis výsledku v původním jazyce

In this paper, we investigate the use of deep learning for solving a classical N P-hard single machine scheduling problem where the criterion is to minimize the total tardiness. Instead of designing an end-to-end machine learning model, we utilize well known decomposition of the problem and we enhance it with a data-driven approach. We have designed a regressor containing a deep neural network that learns and predicts the criterion of a given set of jobs. The network acts as a polynomial-time estimator of the criterion that is used in a singlepass scheduling algorithm based on Lawler's decomposition theorem. Essentially, the regressor guides the algorithm to select the best position for each job. The experimental results show that our data-driven approach can efficiently generalize information from the training phase to significantly larger instances (up to 350 jobs) where it achieves an optimality gap of about 0.5%, which is four times less than the gap of the state-of-the-ar t NBR heuristic.

Název v anglickém jazyce

Data-driven Algorithm for Scheduling with Total Tardiness

Popis výsledku anglicky

In this paper, we investigate the use of deep learning for solving a classical N P-hard single machine scheduling problem where the criterion is to minimize the total tardiness. Instead of designing an end-to-end machine learning model, we utilize well known decomposition of the problem and we enhance it with a data-driven approach. We have designed a regressor containing a deep neural network that learns and predicts the criterion of a given set of jobs. The network acts as a polynomial-time estimator of the criterion that is used in a singlepass scheduling algorithm based on Lawler's decomposition theorem. Essentially, the regressor guides the algorithm to select the best position for each job. The experimental results show that our data-driven approach can efficiently generalize information from the training phase to significantly larger instances (up to 350 jobs) where it achieves an optimality gap of about 0.5%, which is four times less than the gap of the state-of-the-ar t NBR heuristic.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2020

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ů

Název statě ve sborníku

Proceedings of the 9th International Conference on Operations Research and Enterprise Systems

ISBN

978-989-758-396-4

ISSN

2184-4372

e-ISSN

—

Počet stran výsledku

10

Strana od-do

59-68

Název nakladatele

SciTePress - Science and Technology Publications

Místo vydání

Porto

Místo konání akce

Valletta

Datum konání akce

22. 2. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000558347400005