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 | |
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 |
---|---|
Providence Health Care | 33669TC |
Icelandic Centre for Research | 120032011, 152679-051 |
Fondo Nacional de Desarrollo Científico y Tecnológico | CZ.02.1.01/0.0/0.0/15_003/0000466, ANR-15-CE40-0015, 11140566 |
European Regional Development Fund |
Keywords
- Mixed-criticality
- Packing
- Scheduling