Semi-online scheduling with known partial information about job sizes on two identical machines

Qian Cao, Zhaohui Liu, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

In this paper we consider the semi-online scheduling problem with known partial information about job sizes on two identical machines, where all the jobs have processing times in the interval [p,tp] (p>0,t<1) and the maximum job size is tp. The objective is to minimize the makespan. For 1≤t<43 and t<2, we obtain lower bounds t+12 and 43 on the optimal solution, respectively, which match the upper bounds given by He and Zhang (1999) in [2]. For 43≤t<2, we prove that a lower bound on the optimal solution is max4t+43t+4,2tt+1 and design an algorithm with a competitive ratio equal to this lower bound.
Original languageEnglish
Pages (from-to)3731-3737
Number of pages7
JournalTheoretical Computer Science
Volume412
Issue number29
DOIs
Publication statusPublished - 1 Jul 2011

Keywords

  • Identical machines
  • Maximum job
  • Scheduling
  • Semi-online

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this