论文部分内容阅读
组合最优化是运筹学的重要组成部分.排序是组合最优化的一个重要分支.分批排序是现代排序中的热门研究课题之一.在分批排序中，我们将n个工件分成若干个批在一台或多台机器上一起加工.每一批中所有工件的完工时间等于该批中最后一个工件的完工时间，并且每批开始加工前都有一个相同的安装时间. 根据批的加工时间定义的不同将分批排序分为两种类型:平行分批排序和继列分批排序.在平行分批排序中，每一批的加工时间是该批中所有工件的加工时间的最大者;在继列分批排序中，每一批的加工时间是该批中所有工件的加工时间之和. 本文研究单机分批排序相关问题，旨在对工件具有相同工期的各种问题确定他们的计算复杂性.本文的主要结果如下: 排序问题1|p-batch，b=∞，dj=d|∑wjUj在多项式O(n)时间可解. 排序问题1|p-batch，b=∞，dj=d|∑wjTj在多项式O(n3logn)时间可解. 排序问题1|p-batch，b＜n，dj=d|∑wjUj在拟多项式min{O(nbP)，O(nbW)}时间可解. 排序问题1|p-batch，b＜n，dj=d|∑wjTj是二元意义下NP-困难的. 排序问题1|s-batch，b=∞，dj=d|∑wjUj在拟多项式O(nd)时间可解. 排序问题1|s-batch，b＜n，dj=d|∑wjUj在拟多项式min{O(nbP)，O（nbW）}时间可解. 排序问题1|s-batch，b＜n，dj=d|∑Tj在多项式O(nb2+nlogn)时间可解. 排序问题1|s-batch，b＜n，dj=d|∑Tj在多项式O(nb+nlogn)时间可解. 排序问题1|s-batch，b＜n，pj=p，dj=d|∑wjTj在多项式O(nb+nlogn)时间可解.