Match-up scheduling of mixed-criticality jobs: maximizing the probability of jobs execution

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00316499" target="_blank" >RIV/68407700:21230/17:00316499 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/17:00316499

Výsledek na webu

<a href="https://doi.org/10.1016/j.ejor.2017.03.054" target="_blank" >https://doi.org/10.1016/j.ejor.2017.03.054</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejor.2017.03.054" target="_blank" >10.1016/j.ejor.2017.03.054</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Match-up scheduling of mixed-criticality jobs: maximizing the probability of jobs execution

Popis výsledku v původním jazyce

This paper deals with a mixed-criticality scheduling problem: each job has a criticality level depending on its importance. In addition, each job has a finite set of possible processing times, and a known probability for each of them. Every job must be processed between its release date and its deadline. Moreover, each job has a weight corresponding to its payoff. This problem has applications in single machine scheduling of real time embedded systems scheduling, production and operating theaters. We propose a model that takes all the possible processing times of a job into account. An offline multilevel schedule is computed such that safety rules are satisfied, in every situation. This is achieved by allowing the rejection of low criticality jobs when higher criticality jobs need longer processing time, at runtime. The runtime schedule is matched-up again with the offline schedule after such deviations from the offline schedule. The offline multilevel schedule optimizes a non-regular criterion aiming to maximize the average weighted probability of jobs execution (i.e., the total expected payoff). Such a problem is strongly NP-hard. We first study the problem where the sequence of jobs is fixed: we show its complexity and provide a MILP formulation. For the case with two levels of criticality, we provide a dynamic programming algorithm. Finally, we propose a Branch and Bound method for the general problem (i.e., without a fixed job sequence).

Název v anglickém jazyce

Match-up scheduling of mixed-criticality jobs: maximizing the probability of jobs execution

Popis výsledku anglicky

This paper deals with a mixed-criticality scheduling problem: each job has a criticality level depending on its importance. In addition, each job has a finite set of possible processing times, and a known probability for each of them. Every job must be processed between its release date and its deadline. Moreover, each job has a weight corresponding to its payoff. This problem has applications in single machine scheduling of real time embedded systems scheduling, production and operating theaters. We propose a model that takes all the possible processing times of a job into account. An offline multilevel schedule is computed such that safety rules are satisfied, in every situation. This is achieved by allowing the rejection of low criticality jobs when higher criticality jobs need longer processing time, at runtime. The runtime schedule is matched-up again with the offline schedule after such deviations from the offline schedule. The offline multilevel schedule optimizes a non-regular criterion aiming to maximize the average weighted probability of jobs execution (i.e., the total expected payoff). Such a problem is strongly NP-hard. We first study the problem where the sequence of jobs is fixed: we show its complexity and provide a MILP formulation. For the case with two levels of criticality, we provide a dynamic programming algorithm. Finally, we propose a Branch and Bound method for the general problem (i.e., without a fixed job sequence).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/EE2.3.30.0034" target="_blank" >EE2.3.30.0034: Podpora zkvalitnění týmů výzkumu a vývoje a rozvoj intersektorální mobility na ČVUT v Praze</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

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 periodika

European Journal of Operational Research

ISSN

0377-2217

e-ISSN

1872-6860

Svazek periodika

262

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

14

Strana od-do

46-59

Kód UT WoS článku

000402494700005

EID výsledku v databázi Scopus

2-s2.0-85017406350