Online scheduling with increasing subsequence serving constraint

Kelin Luo, Yinfeng Xu, Xin Feng

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review


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.
Original languageEnglish
Title of host publicationFrontiers in Algorithmics, FAW 2016
EditorsD. Zhu, S. Bereg
Place of PublicationCham
Number of pages10
ISBN (Electronic)978-3-319-39817-4
ISBN (Print)978-3-319-39816-7
Publication statusPublished - 2016
Externally publishedYes

Publication series

NameLecture Notes in Computer Science


  • Online scheduling
  • Increasing subsequence
  • Online strategy
  • Competitive ratio


Dive into the research topics of 'Online scheduling with increasing subsequence serving constraint'. Together they form a unique fingerprint.

Cite this