Data-driven Algorithm for Scheduling with Total Tardiness
The result's identifiers
Result code in 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>
Alternative codes found
RIV/68407700:21730/20:00340436
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Data-driven Algorithm for Scheduling with Total Tardiness
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 9th International Conference on Operations Research and Enterprise Systems
ISBN
978-989-758-396-4
ISSN
2184-4372
e-ISSN
—
Number of pages
10
Pages from-to
59-68
Publisher name
SciTePress - Science and Technology Publications
Place of publication
Porto
Event location
Valletta
Event date
Feb 22, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000558347400005