On-line scheduling with monotone subsequence constraints

Kelin Luo (Corresponding author), Yinfeng Xu, Huili Zhang

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

In this paper, we study an on-line scheduling problem that is motivated by applications such as carpooling. The ride requests arrive on-line over-list and specify the service locations (among m locations). The goal is to determine a schedule that maximizes the number of satisfied requests using k servers. We consider two variants of the problem with respect to constraints on the service location: in the monotone service direction variant, the service locations of the requests assigned to a server must be monotonic; in the strict monotone service direction variant, the service locations must be strictly monotonic. We present lower bounds on the competitive ratio for both variants. For the monotone service direction variant, we give an optimal straightforward algorithm if k≥m and we prove that no deterministic on-line algorithm can achieve a constant competitive ratio if k<m. For the strict monotone service direction variant, we give a lower bound max⁡{ [Formula presented], 1} on the competitive ratio of barely deterministic algorithms if k>2, and a lower bound of max⁡{ [Formula presented], 1} if k≤2. We propose a Balanced Interval Algorithm for the strict monotone service direction variant if k>2 and report some numerical experiments to evaluate the efficiency of this algorithm.

Original languageEnglish
Pages (from-to)13-25
Number of pages13
JournalTheoretical Computer Science
Volume786
DOIs
Publication statusPublished - 27 Sep 2019
Externally publishedYes

Keywords

  • On-line scheduling
  • Competitive analysis
  • Monotone subsequence

Cite this