Competitive ratios for preemptive and non-preemptive online scheduling with nondecreasing concave machine cost

Yiwei Jiang, Jueliang Hu, Longcheng Liu, Yuqing Zhu, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

We consider an online scheduling problem where jobs arrive one by one and each job must be irrevocably scheduled on the machines. No machine is available initially. When a job arrives, we either purchase a new machine to process it or schedule it for processing on an existing machine. The objective is to minimize the sum of the makespan and the total cost of all the purchased machines. We assume that the total machine cost function is concave in the number of purchased machines. Considering both non-preemptive and preemptive variants of the problem, we prove that the competitive ratio of any non-preemptive or preemptive algorithm is at least 1.5. For the non-preemptive variant, we present an online algorithm and show that its competitive ratio is 1.6403. For the preemptive variant, we propose an online algorithm and show that its competitive ratio is 1.5654. We further prove that both competitive ratios are tight.
Original languageEnglish
Pages (from-to)128-141
Number of pages14
JournalInformation Sciences
Volume269
DOIs
Publication statusPublished - 10 Jun 2014

Keywords

  • Competitive ratio
  • Concave function
  • Machine cost
  • Online algorithm
  • Scheduling

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Theoretical Computer Science
  • Software
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Cite this