Optimal algorithms for semi-online machine covering on two hierarchical machines

Yong Wu, Edwin Tai Chiu Cheng, Min Ji

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

This paper investigates the semi-online machine covering problem on two hierarchical machines where the jobs are correspondingly classified into two hierarchical classes. The objective is to maximize the minimum machine load. We show that if we only know the size of the largest job, no algorithm with a bounded competitive ratio exists. So we consider the case where we know both the size and the class of the largest job. If we know the size of the largest job and that it belongs to the higher class, then an optimal algorithm with a (1+√2/2)-competitive ratio exists. If we know the size of the largest job and that it belongs to the lower class, we design an optimal algorithm with an α-competitive ratio, where α≈2.48119 is the largest root of the equation x3-2x2-2x+2=0. For the case where the total size of all the jobs is known in advance, we show that the competitive ratio of an optimal algorithm is 2.
Original languageEnglish
Pages (from-to)37-46
Number of pages10
JournalTheoretical Computer Science
Volume531
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • Competitive ratio
  • Hierarchy
  • Scheduling
  • Semi-online
  • Two machines

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this