Parallel machines scheduling with machine shutdowns

H. C. Hwang; S. Y. Chang

doi:10.1016/S0898-1221(98)00126-6

Parallel machines scheduling with machine shutdowns

H. C. Hwang
, S. Y. Chang

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

30 Citations (Scopus)

Abstract

We study the nonpreemptive parallel machines scheduling problem where some of the machines are planned to be shutdown. We apply LPT algorithm to the problem and analyze its performance. Our analysis shows that the makespan of the LPT schedule is bounded by twice the optimum makespan if no more than half of the machines are allowed to be shutdown simultaneously. We also show that this bound is tight by constructing a worst-case example.

Original language	English
Pages (from-to)	21-31
Number of pages	11
Journal	Computers and Mathematics with Applications
Volume	36
Issue number	3
DOIs	https://doi.org/10.1016/S0898-1221(98)00126-6
Publication status	Published - Aug 1998

Keywords

Longest Processing Time (LPT) algorithm
Machine shutdowns
Parallel machines scheduling

Access to Document

10.1016/S0898-1221(98)00126-6

Cite this

@article{0c9773ee8b6046009e11a69e2ad9ab09,

title = "Parallel machines scheduling with machine shutdowns",

abstract = "We study the nonpreemptive parallel machines scheduling problem where some of the machines are planned to be shutdown. We apply LPT algorithm to the problem and analyze its performance. Our analysis shows that the makespan of the LPT schedule is bounded by twice the optimum makespan if no more than half of the machines are allowed to be shutdown simultaneously. We also show that this bound is tight by constructing a worst-case example.",

keywords = "Longest Processing Time (LPT) algorithm, Machine shutdowns, Parallel machines scheduling",

author = "Hwang, \{H. C.\} and Chang, \{S. Y.\}",

year = "1998",

month = aug,

doi = "10.1016/S0898-1221(98)00126-6",

language = "English",

volume = "36",

pages = "21--31",

journal = "Computers and Mathematics with Applications",

issn = "1873-7668",

publisher = "Elsevier Ltd.",

number = "3",

}

TY - JOUR

T1 - Parallel machines scheduling with machine shutdowns

AU - Hwang, H. C.

AU - Chang, S. Y.

PY - 1998/8

Y1 - 1998/8

N2 - We study the nonpreemptive parallel machines scheduling problem where some of the machines are planned to be shutdown. We apply LPT algorithm to the problem and analyze its performance. Our analysis shows that the makespan of the LPT schedule is bounded by twice the optimum makespan if no more than half of the machines are allowed to be shutdown simultaneously. We also show that this bound is tight by constructing a worst-case example.

AB - We study the nonpreemptive parallel machines scheduling problem where some of the machines are planned to be shutdown. We apply LPT algorithm to the problem and analyze its performance. Our analysis shows that the makespan of the LPT schedule is bounded by twice the optimum makespan if no more than half of the machines are allowed to be shutdown simultaneously. We also show that this bound is tight by constructing a worst-case example.

KW - Longest Processing Time (LPT) algorithm

KW - Machine shutdowns

KW - Parallel machines scheduling

UR - https://www.scopus.com/pages/publications/0032136846

U2 - 10.1016/S0898-1221(98)00126-6

DO - 10.1016/S0898-1221(98)00126-6

M3 - Article

AN - SCOPUS:0032136846

SN - 1873-7668

VL - 36

SP - 21

EP - 31

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

IS - 3

ER -

Parallel machines scheduling with machine shutdowns

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this