@inproceedings{9ca783f5d5ba40c6a8710bf6917fa6eb,
title = "Online scheduling with increasing subsequence serving constraint",
abstract = "This paper studies an online scheduling problem with increasing subsequence serving constraint. Customers requests are released over-list, and the operator has to decide whether or not to accept current request and arrange it to a server immediately. Each server has to process an increasing subsequence requests. There are two online scheduling problems in this paper. The first problem is to find a schedule which occupies the minimal servers if the operator accepts all requests. The second problem is to find a schedule which accepts the maximal requests if the operator has just one server. In this paper, we propose two optimal algorithms, Double-Greedy Algorithm and Partition Algorithm, for the above two problems, respectively.",
keywords = "Competitive ratio, Increasing subsequence, Online scheduling, Online strategy",
author = "Kelin Luo and Yinfeng Xu and Xin Feng",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 10th International Workshop on Frontiers in Algorithmics, FAW 2016 ; Conference date: 30-06-2016 Through 02-07-2016",
year = "2016",
doi = "10.1007/978-3-319-39817-4\_14",
language = "英语",
isbn = "9783319398167",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "135--144",
editor = "Sergey Bereg and Daming Zhu",
booktitle = "Frontiers in Algorithmics - 10th International Workshop, FAW 2016, Proceedings",
}