DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.36

Nested Active-Time Scheduling

Authors: Nairen Cao, Jeremy T. Fineman, Shi Li, Julián Mestre, Katina Russell, and Seeun William Umboh

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

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

Cite as

Nairen Cao, Jeremy T. Fineman, Shi Li, Julián Mestre, Katina Russell, and Seeun William Umboh. Nested Active-Time Scheduling. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ISAAC.2022.36,
  author =	{Cao, Nairen and Fineman, Jeremy T. and Li, Shi and Mestre, Juli\'{a}n and Russell, Katina and Umboh, Seeun William},
  title =	{{Nested Active-Time Scheduling}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.36},
  URN =		{urn:nbn:de:0030-drops-173214},
  doi =		{10.4230/LIPIcs.ISAAC.2022.36},
  annote =	{Keywords: Scheduling algorithms, Active time, Approximation algorithm}
}

Search Results

Documents authored by Russell, Katina

Nested Active-Time Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message