Scheduling tasks to minimize active time on a processor with unlimited capacity

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

2 Scopus Citations
View graph of relations

Author(s)

  • Yungao Li
  • Sheung-Hung Poon
  • Weiwei Wu
  • Yingchao Zhao

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation
Subtitle of host publication14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings
EditorsT.V. Gopal, Gerhard Jäger, Silvia Steila
Place of PublicationCham
PublisherSpringer 
Pages247-259
ISBN (Electronic)978-3-319-55911-7
ISBN (Print)978-3-319-55910-0
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)
Volume10185
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
PlaceSwitzerland
CityBern
Period20 - 22 April 2017

Abstract

We study the following scheduling problem on a single processor. We are given n jobs, where each job ji has an integer release time ri, processing time pi as well as deadline di. The processor can schedule an unlimited number of jobs at any time t. Our objective is to schedule the jobs together such that the total number of active time slots is minimized. We present an O(n3) dynamic programming algorithm for the case of agreeable deadlines with di ≤ dj whenever ri <rj or all jobs are big. In the general case, we present an online algorithm with competitive ratio 4 and show that our analysis is tight.

Citation Format(s)

Scheduling tasks to minimize active time on a processor with unlimited capacity. / Fong, Ken C.K.; Li, Minming; Li, Yungao et al.
Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings. ed. / T.V. Gopal; Gerhard Jäger; Silvia Steila. Cham: Springer , 2017. p. 247-259 (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues); Vol. 10185).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review