Treffer: Nested Active-Time Scheduling
Title:
Nested Active-Time Scheduling
Authors:
Contributors:
Nairen Cao and Jeremy T. Fineman and Shi Li and Julián Mestre and Katina Russell and Seeun William Umboh
Publisher Information:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Publication Year:
2022
Collection:
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics )
Subject Terms:
Document Type:
Fachzeitschrift
article in journal/newspaper<br />conference object
File Description:
application/pdf
Language:
English
Relation:
Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.36
DOI:
10.4230/LIPIcs.ISAAC.2022.36
Availability:
Accession Number:
edsbas.84A21858
Database:
BASE
Weitere Informationen
The active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to g jobs during each timestep. The goal in the active-time problem is to minimize the number of active steps, i.e., timesteps in which at least one job is scheduled. In this way, the active time models parallel scheduling when there is a fixed cost for turning the machine on at each discrete step. This paper presents a 9/5-approximation algorithm for a special case of the active-time scheduling problem in which job windows are laminar (nested). This result improves on the previous best 2-approximation for the general case.