PARALLEL MACHINES SCHEDULING WITH MACHINE SHUTDOWNS

Authors
HWANG HC CHANG SY
Citation
Hc. Hwang et Sy. Chang, PARALLEL MACHINES SCHEDULING WITH MACHINE SHUTDOWNS, Computers & mathematics with applications (1987), 36(3), 1998, pp. 21-31
Citations number
4
Categorie Soggetti
Mathematics,"Computer Science Interdisciplinary Applications",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications (1987) → ACNP
ISSN journal
08981221
Volume
36
Issue
3
Year of publication
1998
Pages
21 - 31
Database
ISI
SICI code
0898-1221(1998)36:3<21:PMSWMS>2.0.ZU;2-A
Abstract
We study the nonpreemptive parallel machines scheduling problem where some of the machines are planned to be shutdown. We apply LPT algorith m to the problem and analyze its performance. Our analysis shows that the makespan of the LPT schedule is bounded by twice the optimum makes pan if no more than half of the machines are allowed to be shutdown si multaneously. We also show that this bound is tight by constructing a worst-case example. (C) 1998 Elsevier Science Ltd. All rights reserved .