Scheduling on Parallel-batch Machines with Rejection and Resource Matching
摘要
We consider two scheduling problems with rejection and resource matching on m identical parallel-batch machines. A job is either rejected with a rejection cost or accepted for processing. Accepted jobs are processed on parallel-batch machines with a batch capacity of b. There are multiple kinds of resources, one of which could be matched with an accepted job. Each accepted job must consume exactly one kind of resource and each kind of resource can be consumed by at most one accepted job. Job’s processing time may be different when it consumes a different kind of resource. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection cost of the rejected jobs. When the batch capacity is bounded, we give two approximation algorithms with worst case ratios mb and \(2-\frac{1}{mb}\) , respectively. When the batch capacity is unbounded, we give a polynomial time optimal algorithm.