论文部分内容阅读
组合最优化是运筹学中的一个经典且重要的分支.排序论是一类重要的组合优化问题，作为一门应用学科，在生产活动中发挥着巨大作用.分批排序(Batchscheduling)是其中一类发展迅速的新型排序.它最早出现在半导体集成电路制造的最后测试阶段.后来在其他生产过程，如冶金、电镀等都得到广泛应用. 本文研究工件具有相同加工时间的各种排序问题，主要结果分为两个部分: 单机平行分批排序问题 (1)对于排序问题1|p-batch，b＜n，pj=p|∑wjCj，给出了时间界为O(nlogn)的多项式时间算法. (2)对于排序问题1|p-batch,＜n，pj=p|Lmax，给出了时间界为O(nlogn)的多项式时间算法. (3)对于排序问题1|p-batch，b＜n，pj=p|∑Uj，我们同时给出了时间界分别为O(n2b)的两个多项式时间动态规划算法. (4)对于排序问题1|p-batch，b＜n，pj=p|∑wjUj，我们同时给出了时间界分别为O(nbP)和O(nbW)的两个拟多项式时间动态规划算法. (5)对于排序问题1|p-batch，b＜n，pj=p|∑Tj，给出了时间界为O(nlogn)的多项式时间算法. 单机继列分批排序问题 (6)对于排序问题1|s-batch，b=∞，pj=p|∑wjCj，存在多项式时间算法，时间界为O(n) (7)对于排序问题1|s-batch，b=∞，pj=p|Lmax，给出了时间界为O(n2)的动态规划算法. (8)对于排序问题1|s-batch，b=∞，pj=p|∑wjUj，给出了时间界为O(n2W)的动态规划算法. (9)对于排序问题1|s-batch，b＜n，pj=p|∑wjCj，存在多项式时间算法，时间界为O(n2b). (10)对于排序问题1|s-batch，b＜n，pj=p|Lmax，给出了时间界为O(n2b)的多项式时间动态规划算法. (11)对于排序问题1|s-batch，b＜n，pj=p|∑wjUj，给出了时间界为O(n2W)的多项式时间动态规划算法.