@inbook{ac023c0bdb874910a5380c8407d1c7d9,
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 = "Online scheduling, Increasing subsequence, Online strategy, Competitive ratio",
author = "Kelin Luo and Yinfeng Xu and Xin Feng",
year = "2016",
doi = "10.1007/978-3-319-39817-4_14",
language = "English",
isbn = "978-3-319-39816-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "135--144",
editor = "D. Zhu and S. Bereg",
booktitle = "Frontiers in Algorithmics, FAW 2016",
address = "Germany",
}