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

Ken C.K. Fong; Minming Li; Yungao Li; Sheung Hung Poon; Weiwei Wu; Yingchao Zhao

doi:10.1007/978-3-319-55911-7_18

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

Ken C.K. Fong, Minming Li, Yungao Li, Sheung Hung Poon, Weiwei Wu, Yingchao Zhao

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

We study the following scheduling problem on a single processor. We are given n jobs, where each job j_i has an integer release time r_i, processing time p_i as well as deadline d_i. 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(n³) dynamic programming algorithm for the case of agreeable deadlines with d_i ≤ d_j whenever r_i < r_j 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.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
Editors	Gerhard Jager, Silvia Steila, T.V. Gopal
Publisher	Springer Verlag
Pages	247-259
Number of pages	13
ISBN (Print)	9783319559100
DOIs	https://doi.org/10.1007/978-3-319-55911-7_18
Publication status	Published - 2017
Externally published	Yes
Event	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, Switzerland Duration: 20 Apr 2017 → 22 Apr 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10185 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
Country/Territory	Switzerland
City	Bern
Period	20/04/17 → 22/04/17

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-55911-7_18

Cite this

Fong, K. C. K., Li, M., Li, Y., Poon, S. H., Wu, W., & Zhao, Y. (2017). Scheduling tasks to minimize active time on a processor with unlimited capacity. In G. Jager, S. Steila, & T. V. Gopal (Eds.), Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings (pp. 247-259). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-55911-7_18

Fong, Ken C.K. ; Li, Minming ; Li, Yungao et al. / Scheduling tasks to minimize active time on a processor with unlimited capacity. Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. editor / Gerhard Jager ; Silvia Steila ; T.V. Gopal. Springer Verlag, 2017. pp. 247-259 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a4e9851e472844049d2fad6ceb283ecd,

title = "Scheduling tasks to minimize active time on a processor with unlimited capacity",

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

author = "Fong, \{Ken C.K.\} and Minming Li and Yungao Li and Poon, \{Sheung Hung\} and Weiwei Wu and Yingchao Zhao",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 ; Conference date: 20-04-2017 Through 22-04-2017",

year = "2017",

doi = "10.1007/978-3-319-55911-7\_18",

language = "English",

isbn = "9783319559100",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "247--259",

editor = "Gerhard Jager and Silvia Steila and T.V. Gopal",

booktitle = "Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings",

address = "Germany",

}

Fong, KCK, Li, M, Li, Y, Poon, SH, Wu, W & Zhao, Y 2017, Scheduling tasks to minimize active time on a processor with unlimited capacity. in G Jager, S Steila & TV Gopal (eds), Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10185 LNCS, Springer Verlag, pp. 247-259, 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, Bern, Switzerland, 20/04/17. https://doi.org/10.1007/978-3-319-55911-7_18

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, Proceedings. ed. / Gerhard Jager; Silvia Steila; T.V. Gopal. Springer Verlag, 2017. p. 247-259 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185 LNCS).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Fong, Ken C.K.

AU - Li, Minming

AU - Li, Yungao

AU - Poon, Sheung Hung

AU - Wu, Weiwei

AU - Zhao, Yingchao

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

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

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

UR - https://www.scopus.com/pages/publications/85018379889

U2 - 10.1007/978-3-319-55911-7_18

DO - 10.1007/978-3-319-55911-7_18

M3 - Conference contribution

AN - SCOPUS:85018379889

SN - 9783319559100

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 247

EP - 259

BT - Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings

A2 - Jager, Gerhard

A2 - Steila, Silvia

A2 - Gopal, T.V.

PB - Springer Verlag

T2 - 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017

Y2 - 20 April 2017 through 22 April 2017

ER -

Fong KCK, Li M, Li Y, Poon SH, Wu W, Zhao Y. Scheduling tasks to minimize active time on a processor with unlimited capacity. In Jager G, Steila S, Gopal TV, editors, Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Springer Verlag. 2017. p. 247-259. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-55911-7_18

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this