×

Batch-processing scheduling with setup times. (English) Zbl 1058.90026

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.

MSC:

90B35 Deterministic scheduling theory in operations research
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI