Preemptive scheduling of equal length jobs on two machines to minimize mean flow time

Lee A. Herrbach; Joseph Y.T. Leung

doi:10.1287/opre.38.3.487

Preemptive scheduling of equal length jobs on two machines to minimize mean flow time

Lee A. Herrbach, Joseph Y.T. Leung

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

15 Scopus citations

Abstract

We give an O(n log n) time algorithm to preemptively schedule n equal-length jobs with release times on two identical, parallel machines so as to minimize the mean flow time. The complexity of the general problem of minimizing the mean weighted flow time is also reviewed, both for nonpreemptive and preemptive scheduling.

Original language	English (US)
Pages (from-to)	487-494
Number of pages	8
Journal	Operations Research
Volume	38
Issue number	3
DOIs	https://doi.org/10.1287/opre.38.3.487
State	Published - 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science Applications
Management Science and Operations Research

Access to Document

10.1287/opre.38.3.487

Cite this

@article{3fdbd1c96eba43b880105c4c9535d544,

title = "Preemptive scheduling of equal length jobs on two machines to minimize mean flow time",

abstract = "We give an O(n log n) time algorithm to preemptively schedule n equal-length jobs with release times on two identical, parallel machines so as to minimize the mean flow time. The complexity of the general problem of minimizing the mean weighted flow time is also reviewed, both for nonpreemptive and preemptive scheduling.",

author = "Herrbach, {Lee A.} and Leung, {Joseph Y.T.}",

year = "1990",

doi = "10.1287/opre.38.3.487",

language = "English (US)",

volume = "38",

pages = "487--494",

journal = "Operations Research",

issn = "0030-364X",

publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

number = "3",

}

TY - JOUR

T1 - Preemptive scheduling of equal length jobs on two machines to minimize mean flow time

AU - Herrbach, Lee A.

AU - Leung, Joseph Y.T.

PY - 1990

Y1 - 1990

N2 - We give an O(n log n) time algorithm to preemptively schedule n equal-length jobs with release times on two identical, parallel machines so as to minimize the mean flow time. The complexity of the general problem of minimizing the mean weighted flow time is also reviewed, both for nonpreemptive and preemptive scheduling.

AB - We give an O(n log n) time algorithm to preemptively schedule n equal-length jobs with release times on two identical, parallel machines so as to minimize the mean flow time. The complexity of the general problem of minimizing the mean weighted flow time is also reviewed, both for nonpreemptive and preemptive scheduling.

UR - http://www.scopus.com/inward/record.url?scp=0025434216&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025434216&partnerID=8YFLogxK

U2 - 10.1287/opre.38.3.487

DO - 10.1287/opre.38.3.487

M3 - Article

AN - SCOPUS:0025434216

SN - 0030-364X

VL - 38

SP - 487

EP - 494

JO - Operations Research

JF - Operations Research

IS - 3

ER -

Preemptive scheduling of equal length jobs on two machines to minimize mean flow time

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this