一種多組多組加工速度的隨機(jī)界的討論

一種多組多組加工速度的隨機(jī)界的討論

在實(shí)際應(yīng)用中，有一些關(guān)于多組工人不同加工速度的機(jī)器的分類(lèi)，這需要在機(jī)器上的安排，從第一個(gè)工作中的第一個(gè)過(guò)程到最終過(guò)程的最后一個(gè)過(guò)程的時(shí)間間隔最小。許多科學(xué)家對(duì)cmx進(jìn)行了廣泛的研究（見(jiàn)文獻(xiàn)[1、2、3、4、5、6、7、8、9、10]。討論了兩組工人和三種機(jī)器（兩組工人是工人，一臺(tái)是通用機(jī)，并且專(zhuān)用機(jī)的速度不同，并且它們小于通用機(jī)的速度），并獲得了嚴(yán)格的限制（t，t）。討論了兩組工人、兩臺(tái)專(zhuān)用機(jī)和兩臺(tái)通用機(jī)（專(zhuān)用機(jī)和通用機(jī)的速度相同），并獲得了嚴(yán)格的限制：t（t）4.3）。討論了兩組工人、兩臺(tái)不同速度的專(zhuān)用機(jī)和兩臺(tái)相同速度的通用機(jī)（專(zhuān)用機(jī)的速度小于通用機(jī)），并獲得了嚴(yán)格的限制：t（t）3）。討論了兩組工人、兩臺(tái)特殊機(jī)器和m-t通用機(jī)（專(zhuān)用機(jī)和通用機(jī)的速度相同）的情況，并獲得了嚴(yán)格的限制：t（t）3）2級(jí)。討論了兩組工人、兩組專(zhuān)用機(jī)和一組通用機(jī)（專(zhuān)用機(jī)和通用機(jī)的速度相同）的情況，并獲得了嚴(yán)格的限制：t（t）21mm2-1m；討論了兩組專(zhuān)用機(jī)和一組通用機(jī)（專(zhuān)用機(jī)和通用機(jī)的速度相同）的情況，并提出了改進(jìn)算法。為了解決n個(gè)工作場(chǎng)所和m個(gè)速度相同的機(jī)器的問(wèn)題，提出了改進(jìn)算法，并在實(shí)際應(yīng)用了更好的應(yīng)用。討論了一組不同數(shù)量的工人和m的工人，以及新安裝的機(jī)器。為了使用“第一休閑”標(biāo)準(zhǔn)，說(shuō)明重新分配的改進(jìn)算法。對(duì)于兩組不同速度的專(zhuān)用機(jī)和速度相同的通用機(jī)，每組的速度小于通用機(jī)的速度，討論了各組的工作方法和新安裝速度之間的關(guān)系。本文在文獻(xiàn)的基礎(chǔ)上討論了一種更為復(fù)雜的情形:有三組工件Lr={tri,i∈Ir},Ir={1,2,…,nr},r=1,2,3,nr為非負(fù)整數(shù),tri代表工件并表示其絕對(duì)加工時(shí)間;有4臺(tái)機(jī)器{Ml,l=1,2,3,4},其中M1、M2、M3分別為工件組L1、L2、L3的專(zhuān)用機(jī),其加工速度均為1;M4為通用機(jī),其加工速度也為1.假設(shè)工件之間是獨(dú)立的,與加工次序無(wú)關(guān),加工是不允許中斷的,則問(wèn)題為:將三組工件安排在4臺(tái)機(jī)器上,使其最后完工的時(shí)間最小.當(dāng)某個(gè)nr=0時(shí),該問(wèn)題已由秦成林、丁偉在中證明,利用一種改進(jìn)的LPT算法,得到結(jié)果T/T*≤4/3,并且這個(gè)界是嚴(yán)格的.本文就三組工件、三臺(tái)專(zhuān)用機(jī)、一臺(tái)通用機(jī)且專(zhuān)用機(jī)與通用機(jī)速度相同的情形展開(kāi)了討論.在方法上,利用改進(jìn)的LPT算法(見(jiàn)第1節(jié)),我們可得到結(jié)果(見(jiàn)第2節(jié)的定理2.1):T/T?≤4/3,Τ/Τ*≤4/3,這樣我們的結(jié)果推廣了的結(jié)果.1mt-lpt算法與經(jīng)典的LPT算法相對(duì)應(yīng),我們提出了一種改進(jìn)的LPT算法,即M-LPT算法.本節(jié)主要討論M-LPT算法的步驟和相關(guān)的重要性質(zhì).M-LPT算法首先對(duì)三個(gè)工件組按其總的加工時(shí)間的長(zhǎng)短從大到小排序,假設(shè)用trk表示排序后的第r個(gè)工件組中的第k個(gè)工件;若工件trk先于tr′k′被分配,則記作trk?tr′k′;若工件trk分配給機(jī)器Ml,則記作trk∈Ml;MTl(t)表示排序后工件t被安排之前各機(jī)器上的最后完工時(shí)間;MLl(t)表示工件t被安排之前各機(jī)器上的工件集合,并記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中工件的個(gè)數(shù),記|L|=|L1|+|L2|+|L3|.假定算法是按各組工件下標(biāo)遞增的次序?qū)⒐ぜ饌€(gè)分配到有關(guān)機(jī)器上去的,設(shè)Lr中第kr個(gè)工件以前的工件已被分配,工件trkr在等待分配,則稱(chēng)當(dāng)前t1k1、t2k2、t3k3在候選.定義1.1在t1k1、t2k2、t3k3候選時(shí),工件組Lr的“專(zhuān)用機(jī)可能承擔(dān)的絕對(duì)加工時(shí)間(SMT)”為SMTr(kr)=Tr?∑tri∈M4,i<krtri,r=1,2,3.SΜΤr(kr)=Τr-∑tri∈Μ4,i<krtri,r=1,2,3.當(dāng)某一組工件Lr為空集時(shí),SMTr=SMTr(k)≡0,k為任一正整數(shù).M-LPT算法的步驟:(1)預(yù)排序:使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)用最大相對(duì)SMT法則選擇工件.若r=min{r′|maxr′′=1,2,3SMTr′′(kr′′)},r=min{r′|maxr″=1,2,3SΜΤr″(kr″)},則trkr處于候選狀態(tài);(4)最早完工準(zhǔn)則.在分配t∈Lr時(shí),r=1,2,3.若MTr(t)≤MT4(t),則t∈Mr;若MTr(t)>MT4(t),則t∈M4.(5)若所有工件組都分配完畢,則結(jié)束;否則,轉(zhuǎn)到(3),對(duì)其余工件按最大相對(duì)SMT法則和最早完工準(zhǔn)則繼續(xù)分配.下面給出M-LPT算法的性質(zhì).對(duì)于工件t用ST(t)表示其開(kāi)始加工的時(shí)刻,CT(t)表示其完成加工的時(shí)刻.引理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.證明由有關(guān)定義可得(略).引理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),可類(lèi)似證(2)、(3).因t2q?t1p,故可設(shè)t2q是在與t1s候選時(shí)當(dāng)選的,其中s≤p.由算法知SMT2(q)>SMT1(s)?SΜΤ2(q)>SΜΤ1(s)?由SMT的性質(zhì)可得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,故當(dāng)i≥p+1時(shí),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.同理可證,當(dāng)存在t3u,t3u?t1p時(shí),有T3≥SMT3(u)>T.引理2.3若L=(L1,L2,L3)滿(mǎn)足下列條件之一:(1)存在t1p∈L1,CT(t1p)=T(L),n2,n3≥1,且{t2i|t2i∈M4,t2i?t1p}=>與{t3j|t3j∈M4,t3j?t1p}=>中至少有一個(gè)成立;(2)存在t2q∈L2,CT(t2q)=T(L),n1,n3≥1,且{t1k|t1k∈M4,t1k?t2q}=>與{t3j|t3j∈M4,t3j?t2q}=>中至少有一個(gè)成立;(3)存在t3u∈L3,CT(t3u)=T(L),n1,n2≥1,且{t1k|t1k∈M4,t1k?t3u}=>與{t2i|t2i∈M4,t2i?t3u}=>中至少有一個(gè)成立.則存在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個(gè)工件一致,故安排也一致,從而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}=>,由于在公用機(jī)M4上,在t1p之前無(wú)L2中的工件,即在t1p之前L2中的工件均被安排在專(zhuān)用機(jī)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的工件安排順序和機(jī)器位置與L中L1、L3的工件安排順序和機(jī)器位置一致,從而仍有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算法在最差情況下的性能指標(biāo).定理2.1在M-LPT算法下,成立T/T*≤4/3.證明假設(shè)定理不成立,則可設(shè)存在如下意義上的最小反例L′:(1)T(L′)/T*(L′)>4/3;(2)凡使(1)成立的L′均滿(mǎn)足|L′|≥|L|.以下分3種情況證明:1)存在t1p∈L1,使CT(t1p)=T;2)存在t2q∈L2,使CT(t2q)=T;3)存在t3u∈L3,使CT(t3u)=T.情況1):可設(shè)L3>0,否則由文獻(xiàn)知,T/T*≤4/3,這與L′是最小反例相矛盾.可設(shè){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′是最小反例相矛盾.不防設(shè)k=max{i|t2i∈M4,t2i?t1p},顯然k≥2,因?yàn)橛伤惴ㄖ猼21∈M2;同理可設(shè)v=max{u|t3u∈M4,t3u?t1p},顯然也有v≥2,因?yàn)橛伤惴ㄖ猼31∈M3.因?yàn)镃T(t1p)=T,由引理2.1知MT1(t1p)+t1p≥CT(t1p)=T