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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Scheduling on Parallel-batch Machines with Rejection and Resource Matching

  • Wenhua Li,
  • Liang Zhang,
  • Ran Lin,
  • Shisheng Li

摘要

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.