Batch-processing scheduling with setup times

Batch-processing scheduling with setup times

0.00 Avg rating0 Votes
Article ID: iaor20043603
Country: Netherlands
Volume: 8
Issue: 2
Start Page Number: 137
End Page Number: 146
Publication Date: Jun 2004
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: batching
Abstract:

The problem is to minimize the total weighted completion time on a single batch-processing machine with set-up 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 infinite 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.

Reviews

Required fields are marked *. Your email address will not be published.