On Solving Non-preemptive Mixed-criticality Match-up Scheduling Problem with Two and Three Criticality Levels

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00322374" target="_blank" >RIV/68407700:21230/16:00322374 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/16:00322374

Výsledek na webu

<a href="https://arxiv.org/abs/1610.07384" target="_blank" >https://arxiv.org/abs/1610.07384</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On Solving Non-preemptive Mixed-criticality Match-up Scheduling Problem with Two and Three Criticality Levels

Popis výsledku v původním jazyce

In this paper, we study an NP-hard problem of a single machine scheduling minimizing the makespan, where the mixed-critical tasks with an uncertain processing time are scheduled. We show the derivation of F-shaped tasks from the probability distribution function of the processing time, then we study the structure of problems with two and three criticality levels for which we propose efficient exact algorithms and we present computational experiments for instances with up to 200 tasks. Moreover, we show that the considered problem is approximable within a constant multiplicative factor.

Název v anglickém jazyce

On Solving Non-preemptive Mixed-criticality Match-up Scheduling Problem with Two and Three Criticality Levels

Popis výsledku anglicky

In this paper, we study an NP-hard problem of a single machine scheduling minimizing the makespan, where the mixed-critical tasks with an uncertain processing time are scheduled. We show the derivation of F-shaped tasks from the probability distribution function of the processing time, then we study the structure of problems with two and three criticality levels for which we propose efficient exact algorithms and we present computational experiments for instances with up to 200 tasks. Moreover, we show that the considered problem is approximable within a constant multiplicative factor.

Druh

O - Ostatní výsledky

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/GA16-23509S" target="_blank" >GA16-23509S: Flexibilní rozvrhovací a optimalizační algoritmy pro distribuované systémy reálného času</a><br>

Návaznosti

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

Rok uplatnění

2016

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ů