Online scheduling with increasing subsequence serving constraint

Kelin Luo, Yinfeng Xu, Xin Feng

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

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

Publication series

NameLecture Notes in Computer Science
Volume9711

Keywords

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

Cite this