一种多组多组加工速度的随机界的讨论

一种多组多组加工速度的随机界的讨论

在实际应用中，有一些关于多组工人不同加工速度的机器的分类，这需要在机器上的安排，从第一个工作中的第一个过程到最终过程的最后一个过程的时间间隔最小。许多科学家对cmx进行了广泛的研究（见文献[1、2、3、4、5、6、7、8、9、10]。讨论了两组工人和三种机器（两组工人是工人，一台是通用机，并且专用机的速度不同，并且它们小于通用机的速度），并获得了严格的限制（t，t）。讨论了两组工人、两台专用机和两台通用机（专用机和通用机的速度相同），并获得了严格的限制：t（t）4.3）。讨论了两组工人、两台不同速度的专用机和两台相同速度的通用机（专用机的速度小于通用机），并获得了严格的限制：t（t）3）。讨论了两组工人、两台特殊机器和m-t通用机（专用机和通用机的速度相同）的情况，并获得了严格的限制：t（t）3）2级。讨论了两组工人、两组专用机和一组通用机（专用机和通用机的速度相同）的情况，并获得了严格的限制：t（t）21mm2-1m；讨论了两组专用机和一组通用机（专用机和通用机的速度相同）的情况，并提出了改进算法。为了解决n个工作场所和m个速度相同的机器的问题，提出了改进算法，并在实际应用了更好的应用。讨论了一组不同数量的工人和m的工人，以及新安装的机器。为了使用“第一休闲”标准，说明重新分配的改进算法。对于两组不同速度的专用机和速度相同的通用机，每组的速度小于通用机的速度，讨论了各组的工作方法和新安装速度之间的关系。本文在文献的基础上讨论了一种更为复杂的情形:有三组工件Lr={tri,i∈Ir},Ir={1,2,…,nr},r=1,2,3,nr为非负整数,tri代表工件并表示其绝对加工时间;有4台机器{Ml,l=1,2,3,4},其中M1、M2、M3分别为工件组L1、L2、L3的专用机,其加工速度均为1;M4为通用机,其加工速度也为1.假设工件之间是独立的,与加工次序无关,加工是不允许中断的,则问题为:将三组工件安排在4台机器上,使其最后完工的时间最小.当某个nr=0时,该问题已由秦成林、丁伟在中证明,利用一种改进的LPT算法,得到结果T/T*≤4/3,并且这个界是严格的.本文就三组工件、三台专用机、一台通用机且专用机与通用机速度相同的情形展开了讨论.在方法上,利用改进的LPT算法(见第1节),我们可得到结果(见第2节的定理2.1):T/T∗≤4/3,Τ/Τ*≤4/3,这样我们的结果推广了的结果.1mt-lpt算法与经典的LPT算法相对应,我们提出了一种改进的LPT算法,即M-LPT算法.本节主要讨论M-LPT算法的步骤和相关的重要性质.M-LPT算法首先对三个工件组按其总的加工时间的长短从大到小排序,假设用trk表示排序后的第r个工件组中的第k个工件;若工件trk先于tr′k′被分配,则记作trk≺tr′k′;若工件trk分配给机器Ml,则记作trk∈Ml;MTl(t)表示排序后工件t被安排之前各机器上的最后完工时间;MLl(t)表示工件t被安排之前各机器上的工件集合,并记Tr=∑i=1nrtri,r=1,2,3,MTl(t)=∑t′∈Ml,t′≺tt′,l=1,2,3,4,MLl(t)={t′|t′≺t,t′∈Ml},l=1,2,3,4.Τr=∑i=1nrtri,r=1,2,3,ΜΤl(t)=∑t′∈Μl,t′≺tt′,l=1,2,3,4,ΜLl(t)={t′|t′≺t,t′∈Μl},l=1,2,3,4.L=(L1,L2,L3)表示全体工件,|Lr|表示Lr中工件的个数,记|L|=|L1|+|L2|+|L3|.假定算法是按各组工件下标递增的次序将工件逐个分配到有关机器上去的,设Lr中第kr个工件以前的工件已被分配,工件trkr在等待分配,则称当前t1k1、t2k2、t3k3在候选.定义1.1在t1k1、t2k2、t3k3候选时,工件组Lr的“专用机可能承担的绝对加工时间(SMT)”为SMTr(kr)=Tr−∑tri∈M4,i<krtri,r=1,2,3.SΜΤr(kr)=Τr-∑tri∈Μ4,i<krtri,r=1,2,3.当某一组工件Lr为空集时,SMTr=SMTr(k)≡0,k为任一正整数.M-LPT算法的步骤:(1)预排序:使T3≤T2≤T1,tri≥tri+1,i=1,2,…,nr-1,r=1,2,3;(2)令kr=1,MTl(kr)=0,MLl(kr)=>,r=1,2,3,l=1,2,3,4;(3)用最大相对SMT法则选择工件.若r=min{r′|maxr′′=1,2,3SMTr′′(kr′′)},r=min{r′|maxr″=1,2,3SΜΤr″(kr″)},则trkr处于候选状态;(4)最早完工准则.在分配t∈Lr时,r=1,2,3.若MTr(t)≤MT4(t),则t∈Mr;若MTr(t)>MT4(t),则t∈M4.(5)若所有工件组都分配完毕,则结束;否则,转到(3),对其余工件按最大相对SMT法则和最早完工准则继续分配.下面给出M-LPT算法的性质.对于工件t用ST(t)表示其开始加工的时刻,CT(t)表示其完成加工的时刻.引理2.1(1)若t′,t″∈Ml,l=1,2,3,4,且t′≺t″,则CT(t′)≤ST(t″);(2)若t′,t″∈Lr,r=1,2,3,且t′≺t″,则CT(t′)-t′≤ST(t″);(3)若t∈Lr,r=1,2,3,则MTl(t)+t≥CT(t),l=r,4.证明由有关定义可得(略).引理2.2(1)若有t1p、t2q、t3u,使CT(t1p)=T,且t2q≺t1p,t3u≺t1p,则T2≥SMT2(q)>T,T3≥SMT3(u)>T.Τ2≥SΜΤ2(q)>Τ,Τ3≥SΜΤ3(u)>Τ.(2)若存在t1p、t2q、t3u,使CT(t2p)=T,且t1p≺t2q,t3u≺t2q,则T1≥SMT1(p)>T,T3≥SMT3(u)>T.Τ1≥SΜΤ1(p)>Τ,Τ3≥SΜΤ3(u)>Τ.(3)若存在t1p、t2q、t3u,使CT(t3u)=T,且t2q≺t3u,t1p≺t3u,则T1≥SMT1(p)>T,T2≥SMT2(q)>T.Τ1≥SΜΤ1(p)>Τ,Τ2≥SΜΤ2(q)>Τ.证明只证(1),可类似证(2)、(3).因t2q≺t1p,故可设t2q是在与t1s候选时当选的,其中s≤p.由算法知SMT2(q)>SMT1(s)‚SΜΤ2(q)>SΜΤ1(s)‚由SMT的性质可得T2>SMT2(q)>SMT1(s)≥SMT1(p),Τ2>SΜΤ2(q)>SΜΤ1(s)≥SΜΤ1(p),若t1p∈M1,因CT(t1p)=T,则MT1=T,于是T2≥SMT2(q)>SMT1(p)≥MT1=T;Τ2≥SΜΤ2(q)>SΜΤ1(p)≥ΜΤ1=Τ;若t1p∈M4,则由算法知MT1(t1p)+t1p>MT4(t1p)+t1p=T.ΜΤ1(t1p)+t1p>ΜΤ4(t1p)+t1p=Τ.因MT1≥MT1(t1p),故MT1+t1p>T.因CT(t1p)=T,故当i≥p+1时,t1i∈M1,于是SMT1(p)=MT1(t1p)+∑i≥pt1i=MT1(t1p)+t1p+∑i≥p+1t1i=MT1+t1p,SΜΤ1(p)=ΜΤ1(t1p)+∑i≥pt1i=ΜΤ1(t1p)+t1p+∑i≥p+1t1i=ΜΤ1+t1p,从而得T2>SMT2(q)>SMT1(p)>T.同理可证,当存在t3u,t3u≺t1p时,有T3≥SMT3(u)>T.引理2.3若L=(L1,L2,L3)满足下列条件之一:(1)存在t1p∈L1,CT(t1p)=T(L),n2,n3≥1,且{t2i|t2i∈M4,t2i≺t1p}=>与{t3j|t3j∈M4,t3j≺t1p}=>中至少有一个成立;(2)存在t2q∈L2,CT(t2q)=T(L),n1,n3≥1,且{t1k|t1k∈M4,t1k≺t2q}=>与{t3j|t3j∈M4,t3j≺t2q}=>中至少有一个成立;(3)存在t3u∈L3,CT(t3u)=T(L),n1,n2≥1,且{t1k|t1k∈M4,t1k≺t3u}=>与{t2i|t2i∈M4,t2i≺t3u}=>中至少有一个成立.则存在L′,使|L′|<|L|,且T(L′)/T*(L′)≥T(L)/T*(L).证明(1)中的情况A:若{t3j|t3j∈M4,t3j≺t1p}=>,可作L′1=L1,L′2=L2,L′3=>,L′=(L′1,L′2,L′3)则SMT3(L′)≡0,且L′1、L′2中工作顺序与L1、L2中前p个工件一致,故安排也一致,从而CT(L′|t1p)=CT(L|t1p)=T(L),因|L′|<|L|,故T*(L′)≤T*(L),从而得到T(L′)/T*(L′)≥T(L)/T*(L).(1)中的情况B:若{t2i|t2i∈M4,t2i≺t1p}=>,由于在公用机M4上,在t1p之前无L2中的工件,即在t1p之前L2中的工件均被安排在专用机M2上,所以可以作L′1=L1,L′2=L3,L′3=>,L′=(L′1,L′2,L′3),则SMT3(L′)≡0,同情形A一样,在L′中,L′1、L′2的工件安排顺序和机器位置与L中L1、L3的工件安排顺序和机器位置一致,从而仍有CT(L′|t1p)=CT(L|t1p)=T(L),因|L′|<|L|,故T*(L′)≤T*(L),所以同样得到T(L′)/T*(L′)≥T(L)/T*(L).同理可证(2)、(3)的情形.2tt3ul3本节讨论M-LPT算法在最差情况下的性能指标.定理2.1在M-LPT算法下,成立T/T*≤4/3.证明假设定理不成立,则可设存在如下意义上的最小反例L′:(1)T(L′)/T*(L′)>4/3;(2)凡使(1)成立的L′均满足|L′|≥|L|.以下分3种情况证明:1)存在t1p∈L1,使CT(t1p)=T;2)存在t2q∈L2,使CT(t2q)=T;3)存在t3u∈L3,使CT(t3u)=T.情况1):可设L3>0,否则由文献知,T/T*≤4/3,这与L′是最小反例相矛盾.可设{t2i|t2i∈M4,t2i≺t1p}=>和{t3j|t3j∈M4,t3j≺t1p}=>均成立,否则由引理2.3知存在L′,|L′|<|L|,且T(L′)/T*(L′≥T(L)/T*(L)>4/3,这与L′是最小反例相矛盾.不防设k=max{i|t2i∈M4,t2i≺t1p},显然k≥2,因为由算法知t21∈M2;同理可设v=max{u|t3u∈M4,t3u≺t1p},显然也有v≥2,因为由算法知t31∈M3.因为CT(t1p)=T,由引理2.1知MT1(t1p)+t1p≥CT(t1p)=T