The triangle scheduling problem
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F18%3A00316501" target="_blank" >RIV/68407700:21230/18:00316501 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21730/18:00316501
Result on the web
<a href="https://doi.org/10.1007/s10951-017-0533-1" target="_blank" >https://doi.org/10.1007/s10951-017-0533-1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10951-017-0533-1" target="_blank" >10.1007/s10951-017-0533-1</a>
Alternative languages
Result language
angličtina
Original language name
The triangle scheduling problem
Original language description
This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown that the Greedy algorithm solves the problem to optimality when the binary tree ratio of the input instance is at most 2. We also show that the problem is unary NP-hard for instances with binary tree ratio strictly larger than 2 and provide a quasi-polynomial time approximation scheme. The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
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
R - Projekt Ramcoveho programu EK
Others
Publication year
2018
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
Name of the periodical
Journal of Scheduling
ISSN
1094-6136
e-ISSN
1099-1425
Volume of the periodical
21
Issue of the periodical within the volume
3
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
8
Pages from-to
305-312
UT code for WoS article
000433520800003
EID of the result in the Scopus database
2-s2.0-85019882359