@inproceedings{fa675d51f40640bd916a9fe9141c97c4,
title = "Brief Announcement: Nested Active-Time Scheduling",
abstract = "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. 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.",
keywords = "Scheduling algorithms",
author = "Nairen Cao and Fineman, \{Jeremy T.\} and Shi Li and Juli{\'a}n Mestre and Katina Russell and Umboh, \{Seeun William\}",
note = "Publisher Copyright: {\textcopyright} 2022 Owner/Author.; 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022 ; Conference date: 11-07-2022 Through 14-07-2022",
year = "2022",
month = jul,
day = "11",
doi = "10.1145/3490148.3538554",
language = "English",
series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",
publisher = "Association for Computing Machinery",
pages = "381--383",
booktitle = "SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures",
address = "United States",
}