The triangle scheduling problem

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21730/18:00316501

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

The triangle scheduling problem

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

The triangle scheduling problem

Popis výsledku anglicky

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.

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

—

Návaznosti

R - Projekt Ramcoveho programu EK

Rok uplatnění

2018

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

Journal of Scheduling

ISSN

1094-6136

e-ISSN

1099-1425

Svazek periodika

21

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

8

Strana od-do

305-312

Kód UT WoS článku

000433520800003

EID výsledku v databázi Scopus

2-s2.0-85019882359