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

Result code in 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>

Alternative codes found

RIV/68407700:21730/17:00316499

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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).

Czech name

—

Czech description

—

Type

J_imp - 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)

Project

<a href="/en/project/EE2.3.30.0034" target="_blank" >EE2.3.30.0034: Support of inter-sectoral mobility and quality enhancement of research teams at Czech Technical University in Prague</a><br>

Continuities

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

Publication year

2017

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

European Journal of Operational Research

ISSN

0377-2217

e-ISSN

1872-6860

Volume of the periodical

262

Issue of the periodical within the volume

1

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

14

Pages from-to

46-59

UT code for WoS article

000402494700005

EID of the result in the Scopus database

2-s2.0-85017406350