TY - GEN
T1 - Approximation algorithms for scheduling with a variable machine maintenance
AU - Luo, Wenchang
AU - Chen, Lin
AU - Zhang, Guochuan
PY - 2010
Y1 - 2010
N2 - In this paper, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and whose duration is a nondecreasing function of the starting time. We are asked not only to schedule the jobs but also the maintenance such that the total weighted job completion time is minimum. The problem is shown to be weakly NP-hard. In the case that the duration of the maintenance is a concave (and nondecreasing) function of its starting time, we provide two approximation algorithms with approximation ratio of 2 and at most 1 + √ 2/2 + , respectively.
AB - In this paper, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and whose duration is a nondecreasing function of the starting time. We are asked not only to schedule the jobs but also the maintenance such that the total weighted job completion time is minimum. The problem is shown to be weakly NP-hard. In the case that the duration of the maintenance is a concave (and nondecreasing) function of its starting time, we provide two approximation algorithms with approximation ratio of 2 and at most 1 + √ 2/2 + , respectively.
KW - Approximation algorithms
KW - Scheduling with maintenance
KW - Total weighted completion time
UR - http://www.scopus.com/inward/record.url?scp=79956309603&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-14355-7_22
DO - 10.1007/978-3-642-14355-7_22
M3 - Conference contribution
AN - SCOPUS:79956309603
SN - 3642143547
SN - 9783642143540
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 209
EP - 219
BT - Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings
T2 - 6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010
Y2 - 19 July 2010 through 21 July 2010
ER -