单台机器成批加工最大延误问题的有效算法

在实际生产中，存在着大量成批加工的问题．即如何进行分批，以便使某一目标函数达到最优的问题． Ａｎｄｒｅｗ ｓ １９９５年的论文针对目标为最大延误的成批加工问题进行了分析和讨论，提出了一个寻找最优解的算法．虽然文章对一些特殊情况提出了减少计算量的措施，但文中的算法实质上仍然是基于枚举的指数算法．本文对该问题作了进一步的分析研究，发现了其内在的一些良好结构和性质，从而提出了一个求解它的多项式时间算法，计算量为 Ｏ（ｎ２）