TY - JOUR
T1 - Preemptive scheduling with availability constraints to minimize total weighted completion times
AU - Wang, Guoqing
AU - Sun, Hongyi
AU - Chu, Chengbin
PY - 2005/1
Y1 - 2005/1
N2 - In this paper we study the problem of scheduling n jobs on a single machine with availability constraints. The objective is to minimize total weighted job completion times. We show that the problem is NP-hard in the strong sense. Then we consider two intractable special cases, namely, proportional weight case, and single availability constraint case. We propose two heuristics for these cases and analyze their worst-case error bounds. © 2005 Springer Science + Business Media, Inc.
AB - In this paper we study the problem of scheduling n jobs on a single machine with availability constraints. The objective is to minimize total weighted job completion times. We show that the problem is NP-hard in the strong sense. Then we consider two intractable special cases, namely, proportional weight case, and single availability constraint case. We propose two heuristics for these cases and analyze their worst-case error bounds. © 2005 Springer Science + Business Media, Inc.
UR - http://www.scopus.com/inward/record.url?scp=15244362679&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-15244362679&origin=recordpage
U2 - 10.1007/s10479-004-5032-z
DO - 10.1007/s10479-004-5032-z
M3 - RGC 21 - Publication in refereed journal
SN - 0254-5330
VL - 133
SP - 183
EP - 192
JO - Annals of Operations Research
JF - Annals of Operations Research
IS - 1-4
ER -