The triangle scheduling problem

Christoph Dürr; Zdeněk Hanzálek; Christian Konrad; Yasmina Seddik; R.A. Sitters; Óscar C. Vásquez; Gerhard Woeginger

doi:10.1007/s10951-017-0533-1

The triangle scheduling problem

Christoph Dürr^*
, Zdeněk Hanzálek
, Christian Konrad
, Yasmina Seddik
, R.A. Sitters
, Óscar C. Vásquez
, Gerhard Woeginger

^*Corresponding author for this work

Amsterdam Business Research Institute

Research output: Contribution to Journal › Article › Academic › peer-review

205 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	305–312
Number of pages	8
Journal	Journal of Scheduling
Volume	21
Issue number	3
Early online date	18 May 2017
DOIs	https://doi.org/10.1007/s10951-017-0533-1
Publication status	Published - Jun 2018

Funding

This work is partially supported by PHC VAN GOGH 2015 Projet 33669TC, the Grants FONDECYT 11140566, ANR-15-CE40-0015, and by the Project AI and Reasoning CZ.02.1.01/0.0/0.0/15_003/0000466 as well as by the European Regional Development Fund. Christian Konrad is supported by Icelandic Research Fund Grants 120032011 and 152679-051.

Funders	Funder number
European Regional Development Fund
Fondo Nacional de Desarrollo Científico y Tecnológico	CZ.02.1.01/0.0/0.0/15_003/0000466, 11140566
Icelandic Centre for Research	120032011, 152679-051
Providence Health Care	33669TC
Agence Nationale de la Recherche	ANR-15-CE40-0015

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 8 Decent Work and Economic Growth

Keywords

Mixed-criticality
Packing
Scheduling

Access to Document

10.1007/s10951-017-0533-1

Dürr2018_TheTriangleSchedulingProblemFinal published version, 431 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

@article{08dcae5126ae4e41bc3465a390bc07a9,

title = "The triangle scheduling problem",

abstract = "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.",

keywords = "Mixed-criticality, Packing, Scheduling",

author = "Christoph D{\"u}rr and Zden{\v e}k Hanz{\'a}lek and Christian Konrad and Yasmina Seddik and R.A. Sitters and V{\'a}squez, \{{\'O}scar C.\} and Gerhard Woeginger",

year = "2018",

month = jun,

doi = "10.1007/s10951-017-0533-1",

language = "English",

volume = "21",

pages = "305–312",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - The triangle scheduling problem

AU - Dürr, Christoph

AU - Hanzálek, Zdeněk

AU - Konrad, Christian

AU - Seddik, Yasmina

AU - Sitters, R.A.

AU - Vásquez, Óscar C.

AU - Woeginger, Gerhard

PY - 2018/6

Y1 - 2018/6

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

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

KW - Mixed-criticality

KW - Packing

KW - Scheduling

UR - https://www.scopus.com/pages/publications/85019882359

UR - https://www.scopus.com/pages/publications/85019882359#tab=citedBy

U2 - 10.1007/s10951-017-0533-1

DO - 10.1007/s10951-017-0533-1

M3 - Article

AN - SCOPUS:85019882359

SN - 1094-6136

VL - 21

SP - 305

EP - 312

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 3

ER -

The triangle scheduling problem

Abstract

Funding

UN SDGs

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this