部分工件必须不误工的误工排序问题

排序论中使误工工件的个数为最少的单台机器排序问题,称为误工问题,是排序论中最基本的问题之一.1973年,Sidney研究在工件的一个子集T中的工件必须不误工的条件下,使误工工件的个数为最少的误工排序问题1｜T｜∑Uj,并且给出该问题复杂性为O(n log n)的多项式算法--Sidney算法.本文把Sidney 算法改写成比较简洁的算法1,1)步骤1:设E 0=T,J－E 0=｛j1,j2,…,jm｝,j1＜j2＜…＜jm,m=n-｜T｜,令k=1:2)步骤2:若k=m+1,算法终止,(Em,J－Em)就是最优排序:若k＜m+1,转入步骤3:3)步骤3:设Fk=Ek-1∪{jk},计算Ek如下:如果Fk是不误工子集,令Ek=Ek-1∪{jk}:否则,如果Fk不是不误工子集,令Ek+Fk\{jr}.其中工件jr的加工时间为pr=max{pi｜ji∈Fk\T}.Ek中的工件是按EDD序排列.k=k+1,转入步骤2.并用数学归纳法证明算法1产生的排序是该误工问题的最优解.     

两个多重目标排序问题的多项式时间算法 （运筹学与控制论）

多目标排序是排序论的一个重要分支,在解决经济、管理、工程、军事、社会等领域出现的复杂问题中起着越来越重要的作用。本文研究以误工个数∑Uj为第1目标,∑wjCj或者∑wjTj为第2目标的多重目标排序问题,分别给出了这两个问题在不误工工件集不改变下工件加工时间和权重满足反一致性条件(pi≤pjwi≥wj)时复杂性为O(nlogn)的多项式时间算法:对于排序问题1│(pi≤pj)(wi≥wj)│(∑wjCj/E),选取排序最后一个工件k满足条件:pk/wk=max{pi/wi│i∈M∪L};对于排序问题1│(pi≤pj)(wi≥wj)│(∑wjTj/E),选取排序最后一个工件k满足:1)若M为空集,pk/wk=max{pi/wi│i∈L};2)若M非空,任意选取k∈M。其中L是误工工件集,M是放在最后不误工的工件的集合。最后,证明了这两个算法可以得到相应问题的最优解。