论文部分内容阅读
平行分批排序是重要的现代排序模型之一.其特点是多个工件可以放置在同一个工件批中同时进行加工，每个工件批的加工时间就等于该批中工件的最长加工时间.工件批中最多可以放置的工件数称为批容量，记为b.b=∞的情形称为无界模型，而b＜n的情形称为有界模型，其中n表示工件总数.传统的平行分批排序中假设同一批中的工件具有相同的开工时间和相同的完工时间.也就是说，如果工件批B的开工时间为S，加工时间为p，则工件批B中所有工件的开工时间均为S，完工时间均为S+p. 工件可自由下线的平行分批排序突破了传统的平行分批排序的假设，并对工件定义了新的完工时间.如果工件批B的开工时间为S，则工件批B中任一工件Jj的开工时间定义为S，而完工时间定义为S+pj，其中pj是工件Jj的加工时间.利用三参数表示法，工件可自由下线的平行分批排序问题可以表示为1|p-batch，b，rj，drop-line|γ. 工件可自由下线的平行分批排序在集装箱运输以及信息技术等领域都有着广泛的应用.然而，文献中对这一专题的研究才刚刚起步.本文在前人工作的基础上对工件可自由下线的平行分批排序问题的计算复杂性进行了研究.主要结果如下: 问题1|p-batch,b＜n，drop-line|∑Cj可以在O(nb(b-1))时间内求解. 在限制恰好分K=[n/b]个工件批的前提下，问题1|p-batch，b＜n，drop-line|∑Cj可以在O((nK-1)KlogK+nlogn）时间内求解. 问题1|p-batch，b＜n，drop-line，SPT|∑Cj可以在O(bn+nlogn)时间内求解. 问题1|p-batch，b=∞，rj((<))，drop-line|∑fj可以在O(n2P2)时间内求解，其中P=maxjrj+∑jpj. 问题1|p-batch，b=∞，rj((<))，drop-line|fmax可以在O(n3logP)时间内求解，其中P=maxjrj+∑jpj.