Scheduling with uncertain processing times in mixed-criticality systems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00332277" target="_blank" >RIV/68407700:21230/19:00332277 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21730/19:00332277
Result on the web
<a href="https://doi.org/10.1016/j.ejor.2019.05.038" target="_blank" >https://doi.org/10.1016/j.ejor.2019.05.038</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ejor.2019.05.038" target="_blank" >10.1016/j.ejor.2019.05.038</a>
Alternative languages
Result language
angličtina
Original language name
Scheduling with uncertain processing times in mixed-criticality systems
Original language description
Many scheduling problems that can be identified inside safety-critical applications, such as in autonomous cars, tend to be mixed-critical. Such scheduling problems consider tasks to have different criticalities depending on the safety levels (activation of brakes vs. activation of air-conditioning). The biggest challenge in those scheduling problems arises from the uncertainty of processing times as it disturbs the predictability of the system and thus makes the certification of the system difficult. To overcome this uncertainty, we model the tasks to have multiple processing times concerning their criticality. This approach converts these scheduling problems into a deterministic scheduling with alternative processing times. Here, we study an NP-hard single machine scheduling problem with makespan minimization, where the non-preemptive tasks can have multiple processing times. To solve the problem, we propose an approximation algorithm, a novel mixed-integer linear programming block formulation, and an efficient exact branch-and-price decomposition for two criticality levels. Furthermore, we demonstrate that the optimal schedules are represented as trees, which enables to formulate an exact algorithm for the problem with three criticality levels. The efficiency of the proposed method is demonstrated for difficult problem instances with up to 1000 tasks. The experimental evaluation demonstrates that our algorithms have improved the results of the best-known method by nearly two orders of magnitude.
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
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
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
European Journal of Operational Research
ISSN
0377-2217
e-ISSN
1872-6860
Volume of the periodical
279
Issue of the periodical within the volume
3
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
17
Pages from-to
687-703
UT code for WoS article
000481560600002
EID of the result in the Scopus database
2-s2.0-85068037622