New lower and upper bounds for on-line scheduling

B. Chen; A. Vliet, van; G.J. Woeginger

doi:10.1016/0167-6377(94)90071-X

New lower and upper bounds for on-line scheduling

B. Chen, A. Vliet, van, G.J. Woeginger

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

72 Citations (Scopus)

11 Downloads (Pure)

Abstract

We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.

Original language	English
Pages (from-to)	221-230
Number of pages	10
Journal	Operations Research Letters
Volume	16
Issue number	4
DOIs	https://doi.org/10.1016/0167-6377(94)90071-X
Publication status	Published - 1994

Access to Document

10.1016/0167-6377(94)90071-X

Cite this

@article{3c95aef90ad642f28801dd1673a78887,

title = "New lower and upper bounds for on-line scheduling",

abstract = "We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.",

author = "B. Chen and {Vliet, van}, A. and G.J. Woeginger",

year = "1994",

doi = "10.1016/0167-6377(94)90071-X",

language = "English",

volume = "16",

pages = "221--230",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - New lower and upper bounds for on-line scheduling

AU - Chen, B.

AU - Vliet, van, A.

AU - Woeginger, G.J.

PY - 1994

Y1 - 1994

N2 - We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.

AB - We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.

U2 - 10.1016/0167-6377(94)90071-X

DO - 10.1016/0167-6377(94)90071-X

M3 - Article

SN - 0167-6377

VL - 16

SP - 221

EP - 230

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

New lower and upper bounds for on-line scheduling

Abstract

Access to Document

Fingerprint

Cite this