Competitive analysis of preemptive single-machine scheduling

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We give an online algorithm for minimizing the total weighted completion time on a single machine where preemption of jobs is allowed and prove that its competitive ratio is at most 1.57. © 2010 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)585-588
JournalOperations Research Letters
Volume38
DOIs
Publication statusPublished - 2010

Fingerprint

Total Weighted Completion Time
Competitive Analysis
Preemption
Single Machine Scheduling
Competitive Ratio
Online Algorithms
Single Machine
Scheduling
Single machine
Online algorithms
Competitive ratio
Competitive analysis
Single machine scheduling

Cite this

@article{acb60a861b684c498cf1bdd334ebe92c,
title = "Competitive analysis of preemptive single-machine scheduling",
abstract = "We give an online algorithm for minimizing the total weighted completion time on a single machine where preemption of jobs is allowed and prove that its competitive ratio is at most 1.57. {\circledC} 2010 Elsevier B.V. All rights reserved.",
author = "R.A. Sitters",
year = "2010",
doi = "10.1016/j.orl.2010.08.012",
language = "English",
volume = "38",
pages = "585--588",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",

}

Competitive analysis of preemptive single-machine scheduling. / Sitters, R.A.

In: Operations Research Letters, Vol. 38, 2010, p. 585-588.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Competitive analysis of preemptive single-machine scheduling

AU - Sitters, R.A.

PY - 2010

Y1 - 2010

N2 - We give an online algorithm for minimizing the total weighted completion time on a single machine where preemption of jobs is allowed and prove that its competitive ratio is at most 1.57. © 2010 Elsevier B.V. All rights reserved.

AB - We give an online algorithm for minimizing the total weighted completion time on a single machine where preemption of jobs is allowed and prove that its competitive ratio is at most 1.57. © 2010 Elsevier B.V. All rights reserved.

U2 - 10.1016/j.orl.2010.08.012

DO - 10.1016/j.orl.2010.08.012

M3 - Article

VL - 38

SP - 585

EP - 588

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

ER -