Batch-Processing Scheduling with Setup Times |
| |
Authors: | Chuangyin Dang Liying Kang |
| |
Affiliation: | (1) Department of Mathematics, Shanghai, University, Shanghai, China;(2) Department of of Manufacturing Engineering and Engineering Managment, City Universtity of Hong Kong, Kowloon, Hong Kong |
| |
Abstract: | 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. |
| |
Keywords: | scheduling batching approximation algorithm |
本文献已被 SpringerLink 等数据库收录! |
|