Online scheduling of two uniform machines to minimize total completion times

P. Liu; Xiwen Lu

doi:10.3934/jimo.2009.5.95

Article Contents

2009, Volume 5, Issue 1: 95-102. Doi: 10.3934/jimo.2009.5.95

This issue Previous Article Analysis of bullwhip effect in supply chains with heterogeneous decision models Next Article A tandem queueing system with applications to pricing strategy

Online scheduling of two uniform machines to minimize total completion times

P. Liu^1, and
Xiwen Lu^1,

1.
Department of Mathematics, East China University of Science and Technology, Shanghai 200237

Received: December 31, 2007

Revised: August 31, 2008

Published: December 2008

Abstract Related Papers Cited by

Abstract

In this paper, we study the online scheduling problem on two uniform machines with speeds 1 and $s \geq 1$, in which jobs are arriving over time. We consider both the preemptive and the non-preemptive machine environments. We first present a 2.618-competitive algorithm for the non-preemptive setting with the objective to minimize the total completion times. In the preemptive setting with the objective to minimize the total weighted completion times, we give an online algorithm which has a competitive ratio of 2.

Keywords:

Scheduling; Uniform machine; Online algorithm; Competitive ratio.

Mathematics Subject Classification: 90B35, 90C27.

Citation:

Article Metrics

HTML views() PDF downloads(108) Cited by(0)

Online scheduling of two uniform machines to minimize total completion times

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

Online scheduling of two uniform machines to minimize total completion times

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content