Minimizing flow time on a constant number of machines with preemption

N. Bansal

doi:10.1016/j.orl.2004.07.008

Minimizing flow time on a constant number of machines with preemption

N. Bansal

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

Abstract

We consider offline algorithms for minimizing the total flow time on O(1) machines where jobs can be preempted arbitrarily but migrations are disallowed. Our main result is a quasi-polynomial time approximation scheme for minimizing the total flow time. We also consider more general settings and give some hardness results.

Original language	English
Pages (from-to)	267-273
Journal	Operations Research Letters
Volume	33
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2004.07.008
Publication status	Published - 2005

Access to Document

10.1016/j.orl.2004.07.008

Cite this

@article{00f98719d4bc4f139a63379f030aa3ab,

title = "Minimizing flow time on a constant number of machines with preemption",

abstract = "We consider offline algorithms for minimizing the total flow time on O(1) machines where jobs can be preempted arbitrarily but migrations are disallowed. Our main result is a quasi-polynomial time approximation scheme for minimizing the total flow time. We also consider more general settings and give some hardness results.",

author = "N. Bansal",

year = "2005",

doi = "10.1016/j.orl.2004.07.008",

language = "English",

volume = "33",

pages = "267--273",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Minimizing flow time on a constant number of machines with preemption

AU - Bansal, N.

PY - 2005

Y1 - 2005

N2 - We consider offline algorithms for minimizing the total flow time on O(1) machines where jobs can be preempted arbitrarily but migrations are disallowed. Our main result is a quasi-polynomial time approximation scheme for minimizing the total flow time. We also consider more general settings and give some hardness results.

AB - We consider offline algorithms for minimizing the total flow time on O(1) machines where jobs can be preempted arbitrarily but migrations are disallowed. Our main result is a quasi-polynomial time approximation scheme for minimizing the total flow time. We also consider more general settings and give some hardness results.

U2 - 10.1016/j.orl.2004.07.008

DO - 10.1016/j.orl.2004.07.008

M3 - Article

SN - 0167-6377

VL - 33

SP - 267

EP - 273

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Minimizing flow time on a constant number of machines with preemption

Abstract

Access to Document

Fingerprint

Cite this