On-line scheduling with a monotonous subsequence constraint

Kelin Luo; Yinfeng Xu; Huili Zhang; Wei Luo

doi:10.1007/978-3-319-59605-1_17

On-line scheduling with a monotonous subsequence constraint

Kelin Luo
, Yinfeng Xu
, Huili Zhang
, Wei Luo

School of Management

Xi'an Jiaotong University
University of California at Berkeley

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

Abstract

In this paper, we study a new on-line scheduling problem that each server has to process a monotonous request subsequence. The customer requests are released over-list, and the operator has to decide whether or not to accept the current request and arrange it to a server immediately. The goal of this paper is to find a strategy which accepts the maximal requests. When the number of servers k is less than that of the request types m, we give several lower bounds for this problem. Also, we present the optimal strategy for k = 1 and k = 2 respectively.

Original language	English
Title of host publication	Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings
Editors	Frances Rosamond, Mingyu Xiao
Publisher	Springer Verlag
Pages	187-195
Number of pages	9
ISBN (Print)	9783319596044
DOIs	https://doi.org/10.1007/978-3-319-59605-1_17
State	Published - 2017
Event	11th International Frontiers of Algorithmics Workshop, FAW 2017 - Chengdu, China Duration: 23 Jun 2017 → 25 Jun 2017

Publication series

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

Conference

Conference	11th International Frontiers of Algorithmics Workshop, FAW 2017
Country/Territory	China
City	Chengdu
Period	23/06/17 → 25/06/17

Keywords

Competitive analysis
Monotonous subsequence
On-line algorithm
Scheduling

Access to Document

10.1007/978-3-319-59605-1_17

Cite this

Luo, K., Xu, Y., Zhang, H., & Luo, W. (2017). On-line scheduling with a monotonous subsequence constraint. In F. Rosamond, & M. Xiao (Eds.), Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings (pp. 187-195). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10336 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-59605-1_17

Luo, Kelin ; Xu, Yinfeng ; Zhang, Huili et al. / On-line scheduling with a monotonous subsequence constraint. Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings. editor / Frances Rosamond ; Mingyu Xiao. Springer Verlag, 2017. pp. 187-195 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4228edb2981546d2a5488be098c87d1f,

title = "On-line scheduling with a monotonous subsequence constraint",

abstract = "In this paper, we study a new on-line scheduling problem that each server has to process a monotonous request subsequence. The customer requests are released over-list, and the operator has to decide whether or not to accept the current request and arrange it to a server immediately. The goal of this paper is to find a strategy which accepts the maximal requests. When the number of servers k is less than that of the request types m, we give several lower bounds for this problem. Also, we present the optimal strategy for k = 1 and k = 2 respectively.",

keywords = "Competitive analysis, Monotonous subsequence, On-line algorithm, Scheduling",

author = "Kelin Luo and Yinfeng Xu and Huili Zhang and Wei Luo",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 11th International Frontiers of Algorithmics Workshop, FAW 2017 ; Conference date: 23-06-2017 Through 25-06-2017",

year = "2017",

doi = "10.1007/978-3-319-59605-1\_17",

language = "英语",

isbn = "9783319596044",

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

publisher = "Springer Verlag",

pages = "187--195",

editor = "Frances Rosamond and Mingyu Xiao",

booktitle = "Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings",

}

Luo, K, Xu, Y, Zhang, H & Luo, W 2017, On-line scheduling with a monotonous subsequence constraint. in F Rosamond & M Xiao (eds), Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10336 LNCS, Springer Verlag, pp. 187-195, 11th International Frontiers of Algorithmics Workshop, FAW 2017, Chengdu, China, 23/06/17. https://doi.org/10.1007/978-3-319-59605-1_17

On-line scheduling with a monotonous subsequence constraint. / Luo, Kelin; Xu, Yinfeng; Zhang, Huili et al.
Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings. ed. / Frances Rosamond; Mingyu Xiao. Springer Verlag, 2017. p. 187-195 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10336 LNCS).

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

TY - GEN

T1 - On-line scheduling with a monotonous subsequence constraint

AU - Luo, Kelin

AU - Xu, Yinfeng

AU - Zhang, Huili

AU - Luo, Wei

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

PY - 2017

Y1 - 2017

N2 - In this paper, we study a new on-line scheduling problem that each server has to process a monotonous request subsequence. The customer requests are released over-list, and the operator has to decide whether or not to accept the current request and arrange it to a server immediately. The goal of this paper is to find a strategy which accepts the maximal requests. When the number of servers k is less than that of the request types m, we give several lower bounds for this problem. Also, we present the optimal strategy for k = 1 and k = 2 respectively.

AB - In this paper, we study a new on-line scheduling problem that each server has to process a monotonous request subsequence. The customer requests are released over-list, and the operator has to decide whether or not to accept the current request and arrange it to a server immediately. The goal of this paper is to find a strategy which accepts the maximal requests. When the number of servers k is less than that of the request types m, we give several lower bounds for this problem. Also, we present the optimal strategy for k = 1 and k = 2 respectively.

KW - Competitive analysis

KW - Monotonous subsequence

KW - On-line algorithm

KW - Scheduling

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

U2 - 10.1007/978-3-319-59605-1_17

DO - 10.1007/978-3-319-59605-1_17

M3 - 会议稿件

AN - SCOPUS:85021719501

SN - 9783319596044

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

SP - 187

EP - 195

BT - Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings

A2 - Rosamond, Frances

A2 - Xiao, Mingyu

PB - Springer Verlag

T2 - 11th International Frontiers of Algorithmics Workshop, FAW 2017

Y2 - 23 June 2017 through 25 June 2017

ER -

Luo K, Xu Y, Zhang H, Luo W. On-line scheduling with a monotonous subsequence constraint. In Rosamond F, Xiao M, editors, Frontiers in Algorithmics - 11th International Workshop, FAW 2017, Proceedings. Springer Verlag. 2017. p. 187-195. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-59605-1_17

On-line scheduling with a monotonous subsequence constraint

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this