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

^*此作品的通讯作者

City University of Hong Kong
Southeast University, Nanjing
Universiti Teknologi Brunei
Caritas Institute of Higher Education

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

4 引用（Scopus）

摘要

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.

源语言	英语
主期刊名	Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
编辑	T.V. Gopal, Gerhard Jager, Silvia Steila
出版商	Springer Verlag
页	247-259
页数	13
ISBN（印刷版）	9783319559100
DOI	https://doi.org/10.1007/978-3-319-55911-7_18
出版状态	已出版 - 2017
已对外发布	是
活动	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, 瑞士期限: 20 4月 2017 → 22 4月 2017

出版系列

姓名	Lecture Notes in Computer Science
卷	10185 LNCS
ISSN（印刷版）	0302-9743
ISSN（电子版）	1611-3349

会议

会议	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
国家/地区	瑞士
市	Bern
时期	20/04/17 → 22/04/17

访问文件

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

其它文件与链接

链接到 Scopus 的出版物

引用此

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. 在 T. V. Gopal, G. Jager, & S. Steila (编辑), Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings (页码 247-259). (Lecture Notes in Computer Science; 卷 10185 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-55911-7_18

@inproceedings{dd59cf4271124380ab639a2738387c32,

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 = "英语",

isbn = "9783319559100",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "247--259",

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

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

address = "德国",

}

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. 在 TV Gopal, G Jager & S Steila (编辑), Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Lecture Notes in Computer Science, 卷 10185 LNCS, Springer Verlag, 页码 247-259, 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, Bern, 瑞士, 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 等.
Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. 编辑 / T.V. Gopal; Gerhard Jager; Silvia Steila. Springer Verlag, 2017. 页码 247-259 (Lecture Notes in Computer Science; 卷 10185 LNCS).

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

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

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 - 会议稿件

AN - SCOPUS:85018379889

SN - 9783319559100

T3 - Lecture Notes in Computer Science

SP - 247

EP - 259

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

A2 - Gopal, T.V.

A2 - Jager, Gerhard

A2 - Steila, Silvia

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. 在 Gopal TV, Jager G, Steila S, 编辑, Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Springer Verlag. 2017. 页码 247-259. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-55911-7_18

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

摘要

出版系列

会议

访问文件

其它文件与链接

指纹

引用此