论文部分内容阅读
排序是指在一定的约束条件下分配有限的资源于时间空间去完成多项任务使得一个或者多个目标达到理想或最优.排序的好坏直接影响着生产商成本的高低和利润的大小.因此,排序论对提高效率、科学决策、资源的开发与配置等方面都起到重要的作用.在排序论中,人们把任务统称为“工件”,而把资源统称为“机器”.本学位论文主要研究了若干新型排序问题的计算复杂性.在第二章中,我们研究了 GDD或ADD假设下的单机排序.在GDD假设下,工期按照EDD顺序进行排列,并按照工件完工时间的递增顺序连续分配给工件使得第i个工期分配给第i个完工的工件.而在ADD假设下,工期在分配给工件时是相互独立的.我们证明了两个历史遗留问题1|GDD|∑(Ei+Ti)和1|ADD|∑(Ei+Ti)都是常数界不可近似的.我们的证明也意味着这两个问题都是一元NP-困难的.此外,我们还证明了历史遗留问题1|GDD|∑wiTi是一元NP-困难的.在第三章中,我们研究了单机上工件有位置限制的Pareto排序.首先,我们修正了历史文献中的推理错误.然后,对问题1｜σ[Jj]≤kj,prec|#(fmax,gmax),我们给出一个O(n4)-时间算法,其中“σ[Jj]≤ kj”表示工件Jj只能在前kj个位置上进行加工,“prec”表示工件的序约束限制.我们进一步证明了双代理排序问题l｜σ[Jj]≤kj,pre｜#(fmaxA,gmaxB)在O(nA3nB+nAnB3)时间内可解.在第四章中,我们研究了工件可自由下线的无界平行分批排序,其中可自由下线工件意味着每个工件的完工时间等于包含这个工件的批的开工时间与该工件的加工时间之和.首先,我们证明了问题p-batch(+∞)|drop-line,rj|Lmax是二元NP-困难的.此外,我们证明了,对每个γ∈{fmax,∑fj｝,问题p-batch(+∞)｜drop-line,rj|γ在伪多项式时间内可解,并且当工件实例有常数个不同的加工时间或常数个不同的到达时间时,该问题在多项式时间内可解.在第五章中,我们研究了工件有一致的到达时间和加工时间的无界平行分批排序.我们考虑两种类型的工件:批工件和自由下线工件.对批工件而言,每个工件的完工时间等于包含这个工件的批的完工时间.对双指标问题p-batch(+∞)|β*,(rj,pj)-agreeable|#(Cmax,fmax),其中 β*∈ {batch,drop-line},我们给出一个O(n3log（rmax+∑pj))-时间算法和一个O(n4)-时间算法.对单指标问题p-batch(+∞)|β*,(rj,pj)-agreeable|∑ wjUj,其中β*∈ {batch,drop-line},我们证明了该问题是二元NP-困难的,并给出了一个伪多项式时间算法和一个全多项式时间近似方案.在第六章中,我们研究了单台平行批机器上最小化最大完工时间的双代理排序,其中工件是批工件,有各自的到达时间和线性退化的加工时间.目标函数是,在代理B的最大完工时间不超过给定上界的条件下,最小化代理A的最大完工时间.Tang等人[144]对该排序模型给出了系统的研究.特别地,他们对下面四个问题给出了多项式时间算法.在第一个问题中,批容量无界且两个代理兼容.在第二个问题中,批容量有界,两个代理不兼容，A-工件有一个固定数目的正常加工时间,并且B-工件有一个相同的到达时间.在第三个问题和第四个问题中,批容量有界,两个代理兼容,并且工件的到达时间和正常加工时间是一致的或者反一致的.在这一章中,我们证明了他们对这四个问题给出的算法都是无效的.我们对第一个问题给出了一个新的多项式时间算法并且证明了其他三个问题都是二元NP-困难的.我们进一步对批容量有界,两个代理不兼容,并且A-工件和B-工件各有一个相同的到达时间的这种情形,给出了一个伪多项式时间算法.最后,我们对批容量无界且两个代理不兼容的情形,给出了一个强多项式时间算法.