TY - JOUR
T1 - Batch-processing scheduling with setup times
AU - Dang, Chuangyin
AU - Kang, Liying
PY - 2004/6
Y1 - 2004/6
N2 - The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch, The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +∞, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.
AB - The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch, The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +∞, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.
KW - Approximation algorithm
KW - Batching
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=3042714524&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-3042714524&origin=recordpage
U2 - 10.1023/B:JOCO.0000031415.55216.2a
DO - 10.1023/B:JOCO.0000031415.55216.2a
M3 - 21_Publication in refereed journal
VL - 8
SP - 137
EP - 146
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 2
ER -