Dang, Chuangyin; Kang, Liying Batch-processing scheduling with setup times. (English) Zbl 1058.90026 J. Comb. Optim. 8, No. 2, 137-146 (2004). Summary: 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=+\infty\), 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. Cited in 3 Documents MSC: 90B35 Deterministic scheduling theory in operations research 68W25 Approximation algorithms Keywords:scheduling; batching; approximation algorithm PDFBibTeX XMLCite \textit{C. Dang} and \textit{L. Kang}, J. Comb. Optim. 8, No. 2, 137--146 (2004; Zbl 1058.90026) Full Text: DOI