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

^*Corresponding author for this work

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

3 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 JÄGER, Silvia STEILA, T.V. GOPAL
Publisher	Springer, Cham
Pages	247-259
Number of pages	13
Edition	1
ISBN (Electronic)	9783319559117
ISBN (Print)	9783319559100
DOIs	https://doi.org/10.1007/978-3-319-55911-7_18
Publication status	Published - 21 Mar 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

Bibliographical note

The work described in this paper was partially supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. UGC/FDS11/E04/15 and Project No. CityU 11268616).

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. JÄGER, S. STEILA, & T. V. GOPAL (Eds.), Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Proceedings (1 ed., pp. 247-259). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10185 LNCS). Springer, Cham. 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 JÄGER ; Silvia STEILA ; T.V. GOPAL. 1. ed. Springer, Cham, 2017. pp. 247-259 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3b5d79a4c0d44776a8f5f1ae077cf9c9,

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 = "The work described in this paper was partially supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. UGC/FDS11/E04/15 and Project No. CityU 11268616). ; 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 ; Conference date: 20-04-2017 Through 22-04-2017",

year = "2017",

month = mar,

day = "21",

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

pages = "247--259",

editor = "Gerhard J{\"A}GER and Silvia STEILA and T.V. GOPAL",

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

edition = "1",

}

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 JÄGER, S STEILA & TV GOPAL (eds), Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Proceedings. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10185 LNCS, Springer, Cham, 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 JÄGER; Silvia STEILA; T.V. GOPAL. 1. ed. Springer, Cham, 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: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › 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 - The work described in this paper was partially supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. UGC/FDS11/E04/15 and Project No. CityU 11268616).

PY - 2017/3/21

Y1 - 2017/3/21

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 - http://www.scopus.com/inward/record.url?scp=85018379889&partnerID=8YFLogxK

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

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

M3 - Conference paper (refereed)

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 - JÄGER, Gerhard

A2 - STEILA, Silvia

A2 - GOPAL, T.V.

PB - Springer, Cham

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 JÄGER G, STEILA S, GOPAL TV, editors, Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Proceedings. 1 ed. Springer, Cham. 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

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this