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