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

摘要：

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

关键词：成批加工、延误时间、标准型分划、有效算法

所属期刊栏目：14

分类号：O212(概率论与数理统计)

资助基金：中国科学院资助项目19571074

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：439-444