极小化最大完工时间的单机分批加工问题(英文)

Minimizing Makespan in Single-Machine Batch Processing

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b<n) 个工件．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间．对于极小化最大完工时间问题,本文给出了一个多项式时间近似方案(PTAS)．该算法的总运行时间为O(n log n+C·n),C仅与精度∈有关．这一结果改进了已有的两个多项式时间近似方案．

We consider the problem of minimizing the maximum completion time （makespan） on a batch machine. In this problem, we axe given n jobs and a batch machine. Each job is characterized by a release time and a processing time. The batch machine can process up to b （b 〈 n） jobs as a batch simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch, jobs processed in the same batch have the same completion time, i.e., their common starting time plus the processing time of the batch. We present a polynomial time approximation scheme （PTAS） for this problem. The overall running time of our PTAS is O（nlogn ＋ C · n）, where C depends only on the accuracy ε. The result improves the previous two PTASs for the problem.