一種多組多組加工速度的隨機界的討論

一種多組多組加工速度的隨機界的討論

在實際應用中，有一些關于多組工人不同加工速度的機器的分類，這需要在機器上的安排，從第一個工作中的第一個過程到最終過程的最后一個過程的時間間隔最小。許多科學家對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節(jié)),我們可得到結果(見第2節(jié)的定理2.1):T/T?≤4/3,Τ/Τ*≤4/3,這樣我們的結果推廣了的結果.1mt-lpt算法與經典的LPT算法相對應,我們提出了一種改進的LPT算法,即M-LPT算法.本節(jié)主要討論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處于候選狀態(tài);(4)最早完工準則.在分配t∈Lr時,r=1,2,3.若MTr(t)≤MT4(t),則t∈Mr;若MTr(t)>MT4(t),則t∈M4.(5)若所有工件組都分配完畢,則結束;否則,轉到(3),對其余工件按最大相對SMT法則和最早完工準則繼續(xù)分配.下面給出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本節(jié)討論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