謝志強(qiáng),郭 禾,蘇文秀,辛 宇,楊 靜

(1.哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,哈爾濱150080;2.哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,哈爾濱150001)

0 引 言

傳統(tǒng)產(chǎn)品制造調(diào)度問(wèn)題是純加工調(diào)度和純裝配調(diào)度[1-3],為解決人們的個(gè)性化需求,文獻(xiàn)[4,5]提出了對(duì)單件復(fù)雜產(chǎn)品的加工和裝配一同處理的綜合調(diào)度方法。目前的研究成果主要包括一般綜合調(diào)度問(wèn)題[6]、柔性綜合調(diào)度問(wèn)題[7,8]、分布式調(diào)度研究[9-11]、多目標(biāo)調(diào)度研究[12-14]和兩車(chē)間綜合調(diào)度問(wèn)題[15-17]等。在實(shí)際生產(chǎn)過(guò)程中,調(diào)度問(wèn)題經(jīng)常存在一些特殊的調(diào)度約束,例如,在火箭的制造過(guò)程中,為了避免某些零件的質(zhì)量不符合要求,導(dǎo)致產(chǎn)品無(wú)法組裝,影響產(chǎn)品進(jìn)度,需要對(duì)特殊工序進(jìn)行匹配度檢測(cè)后進(jìn)行調(diào)度加工。如文獻(xiàn)[18]解決了存在單組多工序同時(shí)結(jié)束約束的單車(chē)間綜合調(diào)度問(wèn)題,為了盡早完工,采用對(duì)虛擬工序單獨(dú)調(diào)度并設(shè)計(jì)了相關(guān)策略,在多次比較各個(gè)虛擬工序的結(jié)束時(shí)間后遷移虛擬工序,以滿足同時(shí)結(jié)束的特殊約束,但其只在理論上進(jìn)行了簡(jiǎn)單研究并無(wú)實(shí)際操作意義與價(jià)值。為了進(jìn)一步提高產(chǎn)品生產(chǎn)效率并且使產(chǎn)品的加工能夠一般化,有必要對(duì)存在多工序同時(shí)結(jié)束的產(chǎn)品進(jìn)行大眾化、一般化的綜合調(diào)度研究,以及對(duì)存在多組多工序同時(shí)結(jié)束的單件復(fù)雜產(chǎn)品進(jìn)行多車(chē)間綜合調(diào)度研究。

在產(chǎn)品從單車(chē)間到多車(chē)間的加工調(diào)度過(guò)程中,不僅需要考慮工序遷移和車(chē)間負(fù)載均衡的問(wèn)題,而且需要考慮同時(shí)結(jié)束的工序中存在相同加工設(shè)備的問(wèn)題。針對(duì)正序調(diào)度過(guò)程需多次遷移虛擬工序造成操作復(fù)雜和設(shè)備資源浪費(fèi)的問(wèn)題,本文提出存在多工序同時(shí)結(jié)束的多車(chē)間逆序綜合調(diào)度算法。該算法將多組虛擬工序單獨(dú)分批次逆序調(diào)度,確定各個(gè)批次的調(diào)度順序,設(shè)計(jì)逆序車(chē)間確定策略來(lái)確定每個(gè)工序的加工車(chē)間,最后,采用首次適應(yīng)調(diào)度策略確定一般工序的開(kāi)始加工時(shí)間,并設(shè)計(jì)逆序同時(shí)開(kāi)始策略確定每組虛擬工序組的逆序開(kāi)始加工時(shí)間。該算法不僅實(shí)現(xiàn)了存在多工序同時(shí)結(jié)束特殊約束的單件復(fù)雜產(chǎn)品從單車(chē)間到多車(chē)間調(diào)度加工的轉(zhuǎn)變,而且解決了存在特殊約束的多車(chē)間調(diào)度中產(chǎn)品盡早完工和遷移次數(shù)較少的問(wèn)題。最后,通過(guò)實(shí)例調(diào)度對(duì)本文算法進(jìn)行了說(shuō)明分析。

1 問(wèn)題描述

單件復(fù)雜產(chǎn)品在多車(chē)間綜合調(diào)度的過(guò)程中,工序間不僅存在一般的約束關(guān)系,而且部分工序間還存在需要同時(shí)結(jié)束約束的特殊約束關(guān)系。為了使產(chǎn)品的加工和裝配盡早完工,本文設(shè)計(jì)了逆序調(diào)度方法,將產(chǎn)品虛擬加工樹(shù)逆序后多車(chē)間綜合調(diào)度的約束關(guān)系如下:

(1)在同一時(shí)間里,一道工序只能被一臺(tái)機(jī)器加工且一臺(tái)機(jī)器只能加工一道工序。

(2)每道工序必須在其緊前工序加工完畢后才可加工。

(3)每個(gè)車(chē)間的各個(gè)機(jī)器上后續(xù)工序需在前續(xù)工序加工完畢后開(kāi)始加工。

(4)有同時(shí)結(jié)束特殊約束的工序逆序后要求同時(shí)開(kāi)始加工。

(5)每個(gè)車(chē)間的機(jī)器是不完全相同的,每個(gè)工序可選擇在哪個(gè)車(chē)間加工。

(6)每個(gè)工序和其緊前工序若不在一個(gè)車(chē)間加工,則工序發(fā)生一次虛擬遷移。

(7)同組虛擬工序可在多車(chē)間中相同設(shè)備上加工。

對(duì)于一個(gè)有N個(gè)工序的單件復(fù)雜產(chǎn)品在M臺(tái)機(jī)器上加工的問(wèn)題(其中N個(gè)工序中有n組需同時(shí)結(jié)束的工序,M臺(tái)設(shè)備分布在不同地域的m個(gè)不同車(chē)間里),由約束條件分析可知使產(chǎn)品加工盡早完工的數(shù)學(xué)模型為:

式中:w表示m個(gè)車(chē)間中的一個(gè);i＝1,2,…,M;j＝1,2,…,N;S wij為w車(chē)間中i設(shè)備上第j道工序的開(kāi)始加工時(shí)間;T wij為w車(chē)間中i設(shè)備上第j道工序的連續(xù)加工時(shí)間;S xy為S ij的緊后工序。式(1)表示產(chǎn)品加工時(shí)間的目標(biāo)函數(shù);式(2)表示每一個(gè)工序盡可能早地開(kāi)始加工;式(3)表示逆序調(diào)度中同一車(chē)間同一設(shè)備上后續(xù)工序需在前續(xù)工序加工完畢后開(kāi)始加工;式(4)表示逆序調(diào)度中緊前工序加工完成后才能加工緊后工序。

由于該問(wèn)題是多車(chē)間逆序加工問(wèn)題且存在需同時(shí)結(jié)束的特殊約束條件,為了縮短工序遷移次數(shù),保證各個(gè)車(chē)間的負(fù)載均衡,使產(chǎn)品總的加工時(shí)間減少,需要增加約束條件:

式中:V為加工產(chǎn)品的虛擬遷移次數(shù);T w和T w′為不同車(chē)間上產(chǎn)品工序的總的加工時(shí)間;S wij和S w′i′j′為有同時(shí)結(jié)束特殊約束的產(chǎn)品工序的逆序開(kāi)始加工時(shí)間。式(5)表示逆序調(diào)度過(guò)程中工序的虛擬遷移次數(shù)盡可能少;式(6)表示各個(gè)車(chē)間上工序的總加工時(shí)間差盡可能小;式(7)表示存在同時(shí)結(jié)束特殊約束的工序逆序同時(shí)開(kāi)始加工。

2 問(wèn)題分析與策略設(shè)計(jì)

2.1 問(wèn)題分析與相關(guān)概念

關(guān)于存在同時(shí)結(jié)束特殊工序的問(wèn)題,考慮到工序間的特殊約束條件,若采用正序整體調(diào)度的方式,為保證特殊工序的約束條件需多次移動(dòng)特殊工序,導(dǎo)致操作復(fù)雜且設(shè)備資源空閑。若使用逆序調(diào)度策略,并且將特殊工序單獨(dú)分離加工,可避免特殊工序的移動(dòng),達(dá)到操作簡(jiǎn)單且產(chǎn)品完工時(shí)間縮短的目的。

關(guān)于多車(chē)間調(diào)度問(wèn)題,需要考慮產(chǎn)品的緊前、緊后工序不在同一車(chē)間加工產(chǎn)生工序遷移,導(dǎo)致產(chǎn)品加工出現(xiàn)額外等待的情況,為了減少產(chǎn)品的完工時(shí)間,必須控制遷移次數(shù)。針對(duì)多工序同時(shí)結(jié)束的多車(chē)間調(diào)度,相較于單車(chē)間,增加了同組虛擬產(chǎn)品可以存在在多車(chē)間相同設(shè)備上加工的情況,需要對(duì)多組虛擬工序組的調(diào)度多加考慮,以保證產(chǎn)品在滿足特殊約束的情況下完工時(shí)間較短。

同時(shí)考慮以上問(wèn)題,本文設(shè)計(jì)出一種綜合調(diào)度算法。為了便于工序按批次進(jìn)行調(diào)度,工序的屬性需要設(shè)置為:q i|e i|t i|p|F q|L q|w i,其中q i為工序名,e i為工序q i加工時(shí)所用的設(shè)備名,t i為工序q i的加工時(shí)間,p為特殊工序編號(hào)(p＝0表示為一般工序,p≠0且p值相同表示為同一組需同時(shí)結(jié)束的特殊工序,p＝1,2,…,n),F q為工序q i的緊前工序集,L q為工序q i的緊后工序,w i為工序q i加工的車(chē)間(w i是通過(guò)算法計(jì)算得出,并非已知)。例如:q5|e2|4|2|(q2,q4)|q7|w3表示第2組特殊工序中工序q5在3車(chē)間2設(shè)備加工4個(gè)工時(shí)(其中3車(chē)間為算法計(jì)算得知,其他為已知),工序q5的緊前工序有q2和q4,緊后工序?yàn)閝7。

分析產(chǎn)品工序的屬性信息,采用逆序調(diào)度后,定義相關(guān)概念如下:

定義1 虛擬工序:工序?qū)傩灾衟≠0的工序。

定義2 一般工序:工序?qū)傩灾衟＝0的工序。

定義3 虛擬工序組p:工序?qū)傩灾衟≠0且p值相等的工序。

定義4 虛擬工序組p前續(xù)工序:在確定虛擬工序組p后根據(jù)工序間約束關(guān)系,循環(huán)查找緊前工序直到緊前工序?yàn)樘摂M工序或緊前工序已定義所得到的所有工序。

定義5 虛擬遷移:加工過(guò)程中出現(xiàn)一個(gè)逆序緊前工序需要向多個(gè)其緊后工序所在加工車(chē)間遷移的情況。

設(shè)m個(gè)車(chē)間中設(shè)備集合分別為E1,E2,…,E i,其中i＝1,2,…,m。定義相關(guān)概念如下:

定義6 對(duì)稱(chēng)設(shè)備資源集Es:在m個(gè)車(chē)間中共同存在的設(shè)備資源構(gòu)成的集合。即Es＝E1∩E2∩…∩E m,若交集為空,則無(wú)對(duì)稱(chēng)資源設(shè)備。

定義7 非對(duì)稱(chēng)設(shè)備資源集Ens:在m個(gè)車(chē)間中每個(gè)車(chē)間中單獨(dú)存在與其他車(chē)間無(wú)重復(fù)的設(shè)備的資源構(gòu)成的集合。即Ens＝((E1－E2)∩(E1－E3)∩…(E1－E m))∪((E2－E1)∩(E2－E3)∩…(E2－E m))∪…∪((E m－E1)∩(E m－E2)∩…(E m－E m－1))。

定義8 局部對(duì)稱(chēng)設(shè)備資源集Els:在m個(gè)車(chē)間中部分車(chē)間存在的相同設(shè)備資源構(gòu)成的集合。即Els＝(E1∪E2∪…∪E m)－Es－Ens。

2.2 逆序分批次調(diào)度策略

由于對(duì)存在多工序同時(shí)結(jié)束的產(chǎn)品采用一般正序調(diào)度需要多次調(diào)整虛擬工序的開(kāi)始加工時(shí)間,導(dǎo)致設(shè)備資源空閑且加工周期延長(zhǎng)?？紤]到同時(shí)結(jié)束的工序逆序調(diào)度后只需同時(shí)開(kāi)始即可,不僅操作簡(jiǎn)單,而且避免了工序移動(dòng)導(dǎo)致的設(shè)備資源空閑,所以本文設(shè)計(jì)逆序分批次調(diào)度策略,具體步驟如下:

(1)輸入產(chǎn)品全部工序的屬性信息(不包括工序加工車(chē)間信息,需要計(jì)算得知),將所有工序逆序處理,即將工序?qū)傩孕畔⒅芯o前工序集與緊后工序信息交換。例如:q5|e2|4|2|(q2,q4)|q7逆序處理后工序?qū)傩孕畔閝5|e2|4|2|q7|(q2,q4),表示虛擬工序組2中工序q5在2設(shè)備加工4個(gè)工時(shí),工序q5的緊前工序?yàn)閝7,緊后工序有q2和q4。

(2)遍歷工序?qū)傩孕畔?得到p＝1時(shí)的所有工序,即虛擬工序組1,將虛擬工序組1單獨(dú)劃分。根據(jù)虛擬工序組1中工序?qū)傩孕畔⒑投x4確定虛擬工序組1前續(xù)工序,并將其單獨(dú)劃分。得到虛擬工序組1和虛擬工序組1前續(xù)工序。

(3)遍歷工序信息,依次得到虛擬工序組p和虛擬工序組p前續(xù)工序,其中p＝1,2,…,n。

(4)將虛擬工序組p和虛擬工序組p前續(xù)工序劃分為2n部分完畢后,剩余的工序劃分為單獨(dú)的一部分,共得到2n＋1的獨(dú)立部分工序集。

為方便理解,特舉例說(shuō)明逆序分批次調(diào)度策略。例如圖1所示的產(chǎn)品A,方框內(nèi)產(chǎn)品工序?qū)傩孕畔⒈硎緸?工序名/加工設(shè)備名/加工時(shí)間/是否虛擬工序。逆序分批次調(diào)度策略的具體過(guò)程如下:將產(chǎn)品A的虛擬加工工藝樹(shù)中所有工序的緊前、緊后關(guān)系取反;遍歷虛擬加工工藝樹(shù),得到p＝1的工序?yàn)锳4和A6;根據(jù)定義4查找得到虛擬工序A4和A6的前續(xù)工序集為{A1,A3};遍歷虛擬加工工藝樹(shù),得到p＝2的工序?yàn)锳8、A9和A11;根據(jù)定義4查找得到虛擬工序A8、A9和A11的前續(xù)工序集為{A5};最后剩余工序?yàn)锳2,A7,A10,A12。因?yàn)楫a(chǎn)品A中有2組虛擬工序組,所以最后分批次得到5部分工序集,見(jiàn)表1。

圖1 產(chǎn)品A的加工工藝樹(shù)Fig.1 Process tree of product A

表1 產(chǎn)品A逆序分批次調(diào)度結(jié)果Table 1 Reverse batch scheduling result of product A

2.3 確定工序調(diào)度順序

單件復(fù)雜產(chǎn)品的虛擬工藝樹(shù)中都存在一條關(guān)鍵路徑,優(yōu)先加工關(guān)鍵路徑上的工序可以使產(chǎn)品橫向上工序能更好地并行調(diào)度,而且使產(chǎn)品縱向上的后序工序可以更多地與其他工序并行調(diào)度,故本文采用逆序動(dòng)態(tài)關(guān)鍵路徑調(diào)度策略。當(dāng)動(dòng)態(tài)關(guān)鍵路徑策略不能確定工序調(diào)度順序時(shí),即有兩個(gè)或多個(gè)工序有相同的路徑長(zhǎng)度時(shí),優(yōu)先加工用時(shí)較短的工序,可以使后續(xù)工序獲得較早的加工時(shí)間,使后續(xù)工序充分并行調(diào)度,所以本文同時(shí)采用逆序短用時(shí)策略。

對(duì)存在多工序同時(shí)結(jié)束的單件復(fù)雜產(chǎn)品,在設(shè)計(jì)逆序分批次調(diào)度策略后,考慮到虛擬工序組p前續(xù)工序和剩余工序?yàn)槎鄠€(gè)虛擬的加工工藝樹(shù),故采用上述策略確定各個(gè)部分的調(diào)度順序,以確保工序間的并行調(diào)度和縮短各部分虛擬產(chǎn)品的完工時(shí)間。而虛擬工序組p是存在同時(shí)結(jié)束特殊要求的工序,即逆序后要求同時(shí)開(kāi)始加工的工序,若多車(chē)間中同組虛擬工序存在加工設(shè)備相同的情況,則其不能在同一車(chē)間加工,增加了虛擬工序車(chē)間確定的復(fù)雜性,每組虛擬工序組的調(diào)度順序可隨機(jī)。對(duì)圖1中產(chǎn)品A虛擬加工樹(shù)設(shè)計(jì)逆序分批次調(diào)度策略后,確定調(diào)度順序見(jiàn)表2。

表2 產(chǎn)品A各部分調(diào)度順序Table 2 Scheduling order of parts of product A

2.4 逆序車(chē)間確定策略

對(duì)單件復(fù)雜產(chǎn)品的工序?qū)傩孕畔⒎治隹芍?可以構(gòu)造一個(gè)虛擬的樹(shù)狀產(chǎn)品加工工藝樹(shù),所有的葉子節(jié)點(diǎn)工序的屬性信息無(wú)緊前工序,根節(jié)點(diǎn)工序無(wú)緊后工序,其余節(jié)點(diǎn)工序?qū)傩孕畔⒅杏幸粋€(gè)或多個(gè)緊前工序,有且僅有一個(gè)緊后工序。設(shè)計(jì)逆序分批次調(diào)度策略后,各個(gè)工序?qū)傩孕畔l(fā)生變化,原工序?qū)傩孕畔⒅芯o前工序集變?yōu)槟嫘蚝蠊ば驅(qū)傩孕畔⒅械木o后工序集,原工序?qū)傩孕畔⒅械木o后工序變?yōu)槟嫘蚝蠊ば驅(qū)傩孕畔⒅械木o前工序,根節(jié)點(diǎn)工序無(wú)緊前工序,所有葉子節(jié)點(diǎn)工序無(wú)緊后工序。分析m個(gè)車(chē)間中M臺(tái)設(shè)備的屬性,判斷M臺(tái)設(shè)備分別為對(duì)稱(chēng)設(shè)備資源集Es、非對(duì)稱(chēng)設(shè)備資源集Ens、局部對(duì)稱(chēng)設(shè)備資源集Els。

為了保證產(chǎn)品生產(chǎn)周期盡可能短,需要考慮產(chǎn)品工序在車(chē)間之間的遷移盡量少;為了使產(chǎn)品工序充分的并行調(diào)度,需要使各個(gè)車(chē)間的負(fù)載盡量均衡。考慮到以上因素,設(shè)計(jì)逆序車(chē)間確定策略,設(shè)虛擬遷移數(shù)用Vr＝0表示,具體步驟如下:

(1)輸入產(chǎn)品工序信息,設(shè)計(jì)逆序分批次調(diào)度策略確定各部分調(diào)度工序,然后確定各部分工序的調(diào)度順序。

(2)按調(diào)度順序取出工序,判斷該工序所需加工設(shè)備,若屬于非對(duì)稱(chēng)設(shè)備資源集Ens,則將該工序放入非對(duì)稱(chēng)設(shè)備所在車(chē)間加工,繼續(xù)判斷該工序緊前工序所在車(chē)間,若為同一車(chē)間則工序虛擬遷移數(shù)Vr不變,轉(zhuǎn)步驟(8);若不在同一車(chē)間,則虛擬遷移數(shù)Vr＋＋,轉(zhuǎn)步驟(8)。

(3)若該工序所需加工設(shè)備屬于局部對(duì)稱(chēng)設(shè)備資源集Els,繼續(xù)判斷該工序緊前工序所加工車(chē)間能否加工該工序(其中包括該工序緊前工序加工車(chē)間有無(wú)該工序加工設(shè)備和該工序緊前工序加工車(chē)間的該工序加工設(shè)備是否已加工與該工序同組的虛擬工序),若能,轉(zhuǎn)步驟(4),若不能,轉(zhuǎn)步驟(5);否則,轉(zhuǎn)步驟(6)。

(4)確定該工序在其緊前工序所在加工車(chē)間加工,轉(zhuǎn)步驟(7)。

(5)為保證車(chē)間負(fù)載均衡選擇加工時(shí)間少的車(chē)間調(diào)整加工該工序且虛擬遷移數(shù)Vr＋＋,轉(zhuǎn)步驟(8)。

(6)若該工序所需加工設(shè)備屬于對(duì)稱(chēng)設(shè)備資源集Es,轉(zhuǎn)步驟(4);否則轉(zhuǎn)步驟(7)。

(7)若該工序?yàn)橐话愎ば?轉(zhuǎn)步驟(8);否則判斷該工序加工設(shè)備是否已加工同組虛擬工序,若已加工,則轉(zhuǎn)步驟(5),否則轉(zhuǎn)步驟(8)。

(8)所有工序確定完畢則結(jié)束,否則轉(zhuǎn)步驟(2)。

為方便理解,對(duì)圖1所示產(chǎn)品A采用逆序車(chē)間確定策略確定所有工序加工車(chē)間,設(shè)有3個(gè)車(chē)間,車(chē)間a有設(shè)備M1、M2、M4,車(chē)間b有設(shè)備M1、M2,車(chē)間c有設(shè)備M1、M3。由定義6、定義7和定義8可知,M1屬于對(duì)稱(chēng)設(shè)備資源集Es,M2屬于局部對(duì)稱(chēng)設(shè)備資源集Els,M3和M4屬于非對(duì)稱(chēng)設(shè)備資源集Ens。

按A1,A3,A4,A6,A5,A8,A9,A11,A2,A12,A7,A10順序依次取出工序確定車(chē)間,工序A1需在設(shè)備M2上加工,M2∈Els,因?yàn)锳1是根節(jié)點(diǎn)工序,逆序無(wú)緊前工序,可任選一車(chē)間a或b加工,選擇車(chē)間b加工;工序A3需在設(shè)備M1上加工,M1∈Es,工序A3的緊前工序A1在車(chē)間b加工,故A3在車(chē)間b加工且Vr＝0;工序A4需在設(shè)備M3上加工,M3∈Ens,確定工序A4在車(chē)間c加工,工序A4的緊前工序A1在車(chē)間b加工,故Vr＝1;以后各個(gè)工序處理方式相同,最后得到產(chǎn)品A的工序?qū)傩匀鐖D2所示,虛擬遷移數(shù)Vr＝4。

圖2 確定產(chǎn)品A工序加工車(chē)間Fig.2 Determine machining workshop of the product A

2.5 逆序同時(shí)開(kāi)始策略

通過(guò)以上策略設(shè)計(jì)與應(yīng)用,確定了2n＋1個(gè)部分工序集和所有工序的加工車(chē)間屬性,針對(duì)n個(gè)虛擬工序組p前續(xù)工序組成的各部分工序集和剩余工序組成的工序集,為保證一般工序能夠在其車(chē)間設(shè)備上盡早開(kāi)始加工,可使用首次適應(yīng)調(diào)度策略[5]確定一般工序的開(kāi)始加工時(shí)間,而針對(duì)n組虛擬工序組p,為滿足其同時(shí)結(jié)束的特殊約束,本文設(shè)計(jì)逆序同時(shí)開(kāi)始策略確定虛擬工序的開(kāi)始加工時(shí)間,具體步驟如下:對(duì)n組虛擬工序組p(p＝1,2,…,n);從虛擬工序組1開(kāi)始,查找虛擬工序組1中工序的逆序緊前工序,比較各個(gè)緊前工序在其加工車(chē)間的結(jié)束加工時(shí)間,得到最晚的結(jié)束加工時(shí)間,以此時(shí)間點(diǎn)為虛擬工序組1中所有虛擬工序的開(kāi)始加工時(shí)間;重復(fù)以上步驟,直到n組虛擬工序組p全部確定開(kāi)始加工時(shí)間。

圖1所示產(chǎn)品A虛擬加工工藝樹(shù),確定調(diào)度順序?yàn)锳1,A3,A4,A6,A5,A8,A9,A11,A2,A12,A7,A10,按序確定開(kāi)始加工時(shí)間,A1開(kāi)始加工時(shí)間為0,A3開(kāi)始加工時(shí)間為1,A4和A6的開(kāi)始加工時(shí)間為3,全部工序得到開(kāi)始加工時(shí)間后則產(chǎn)品加工完畢。

3 算法詳細(xì)設(shè)計(jì)

根據(jù)以上分析和策略設(shè)計(jì),為了實(shí)現(xiàn)存在多工序同時(shí)結(jié)束的多車(chē)間綜合調(diào)度目標(biāo),算法流程圖如圖3所示,算法的具體步驟如下:

(1)輸入產(chǎn)品工序信息和多車(chē)間設(shè)備信息。

(2)根據(jù)定義6、定義7、定義8確定對(duì)稱(chēng)設(shè)備資源集Es、非對(duì)稱(chēng)設(shè)備資源集Ens、局部對(duì)稱(chēng)設(shè)備資源集Els;按逆序分批次調(diào)度策略將產(chǎn)品工序緊前、緊后關(guān)系取反;定義循環(huán)變量i＝1。

(3)若i＞n,轉(zhuǎn)步驟(21);否則轉(zhuǎn)步驟(4)。

(4)令工序?qū)傩詐＝i,遍歷工藝樹(shù)得到虛擬工序組p,并記錄其虛擬工序個(gè)數(shù)為v p。

(5)根據(jù)定義4確定虛擬工序組p前續(xù)工序,并按逆序動(dòng)態(tài)關(guān)鍵路徑策略和逆序短用時(shí)策略確定調(diào)度順序加入備選工序集。

(6)若備選工序集為空,轉(zhuǎn)步驟(7);不為空則轉(zhuǎn)步驟(8)。

(7)將虛擬工序組p隨機(jī)加入備選工序集。

(8)按序從備選工序集中選出工序,定義當(dāng)前工序q的加工設(shè)備為E q。

(9)若M q∈Ens,將工序q放入對(duì)應(yīng)的車(chē)間設(shè)備加工;否則轉(zhuǎn)步驟(11)。

(10)若工序q的緊前工序和工序q在同一車(chē)間加工,轉(zhuǎn)步驟(17);否則轉(zhuǎn)步驟(14)。

(11)若M q∈Els,轉(zhuǎn)步驟(12);否則轉(zhuǎn)步驟(15)。

(12)若工序q緊前工序所在車(chē)間可加工工序q,則轉(zhuǎn)步驟(15);否則轉(zhuǎn)步驟(13)。

(13)調(diào)整放入可加工車(chē)間中加工用時(shí)少的車(chē)間加工工序q。

(14)虛擬遷移數(shù)Vr＋＋,轉(zhuǎn)步驟(17)。

(15)確定工序q在其緊前工序所在車(chē)間加工。

圖3 算法流程圖Fig.3 Flow chart of algorithm

(16)若工序q的屬性p＝0,則轉(zhuǎn)步驟(17);否則判斷工序q的加工設(shè)備是否已加工同組虛擬工序,若是則轉(zhuǎn)步驟(13),若不是則轉(zhuǎn)步驟(17)。

(17)若工序q的屬性p＝0,則工序q為一般工序,按首次適應(yīng)調(diào)度策略確定工序q的開(kāi)始加工時(shí)間,從備選工序集中刪除已調(diào)度工序,轉(zhuǎn)步驟(20);否則工序q為虛擬工序,v＋＋,轉(zhuǎn)步驟(18)。

(18)若v＝v p,表示備選工序集中工序全部確定加工車(chē)間,轉(zhuǎn)步驟(19);否則轉(zhuǎn)步驟(8)。

(19)確定備選工序集中為虛擬工序組p,按逆序同時(shí)開(kāi)始策略確定開(kāi)始加工時(shí)間,令v＝0,從備選工序集中刪除已調(diào)度工序,i＋＋,轉(zhuǎn)步驟(3)。

(20)若i＞n,則轉(zhuǎn)步驟(22);否則轉(zhuǎn)步驟(6)。

(21)將剩余一般工序按逆序動(dòng)態(tài)關(guān)鍵路徑策略和逆序短用時(shí)策略確定調(diào)度順序并放入備選工序集中。

(22)若備選工序集為空,轉(zhuǎn)步驟(23);不為空則轉(zhuǎn)步驟(8)。

(23)輸出逆序調(diào)度甘特圖,結(jié)束。

4 算法復(fù)雜度分析

設(shè)產(chǎn)品共有N個(gè)工序,其中有n組虛擬工序(n組虛擬工序組共有N n個(gè)虛擬工序),在m間車(chē)間中的M臺(tái)設(shè)備上加工,設(shè)n組虛擬工序組工序數(shù)為x1,x2,…,x n,x1＋x2＋…＋x n＝N n。n組虛擬工序組前續(xù)工序個(gè)數(shù)為y1,y2,…,y n,分析如下:

(1)逆序分批次調(diào)度策略:將N道工序中的緊前、緊后關(guān)系取反,需要N次操作,逆序操作時(shí)間復(fù)雜度為O(N);遍歷加工工藝樹(shù),確定虛擬工序組1需要x1次,確定虛擬工序組1前續(xù)工序需要y1次,直到確定虛擬工序組n需要x n次,確定虛擬工序組n前續(xù)工序需要y n次,確定2n＋1部分需要每個(gè)節(jié)點(diǎn)訪問(wèn)一次,故時(shí)間復(fù)雜度為O(N)。

(2)逆序動(dòng)態(tài)關(guān)鍵路徑策略和逆序短用時(shí)策略:根據(jù)文獻(xiàn)[5],對(duì)N－N n個(gè)一般工序確定調(diào)度順序的比較次數(shù)為(N－N n)(N－N n－1),故時(shí)間復(fù)雜度為O(N)2。

(3)逆序車(chē)間確定策略:根據(jù)定義6、定義7、定義8確定設(shè)備種類(lèi)Es、Ens和Els個(gè)數(shù)分別為h1、h2和h3,由于工序加工設(shè)備已知,判斷設(shè)備屬于非對(duì)稱(chēng)設(shè)備資源集最多需要h1次,然后確定工序緊前工序是否在同一車(chē)間需比較1次,于是確定加工設(shè)備為非對(duì)稱(chēng)設(shè)備資源集設(shè)備的工序確定加工車(chē)間需要判斷h1＋1次。判斷工序加工設(shè)備屬于局部對(duì)稱(chēng)設(shè)備資源集最多需要h2次,確定緊前工序所在車(chē)間不可加工該工序最多需判斷M次,判斷虛擬遷移1次,于是確定加工設(shè)備為局部對(duì)稱(chēng)設(shè)備資源集設(shè)備的工序確定加工車(chē)間需要判斷h2M＋1次。判斷工序加工設(shè)備屬于對(duì)稱(chēng)設(shè)備資源集最多需要h3次,確定緊前工序所在車(chē)間加工需操作1次,于是確定加工設(shè)備為對(duì)稱(chēng)設(shè)備資源集設(shè)備的工序確定加工車(chē)間需要判斷h3＋1次。因此,N個(gè)工序全部確定加工車(chē)間最壞需要N(h2M＋1)次操作,h2＜M,故時(shí)間復(fù)雜度為O(NM2)。

(4)確定開(kāi)始加工時(shí)間:對(duì)N－N n個(gè)一般工序,根據(jù)文獻(xiàn)[5]采用首次適應(yīng)調(diào)度策略確定開(kāi)始加工時(shí)間復(fù)雜度為O(N－N n)2;對(duì)于虛擬工序組n,得到每個(gè)虛擬工序緊前工序結(jié)束時(shí)間需操作x n次,判斷最晚結(jié)束時(shí)間需x n－1次,確定虛擬工序組n開(kāi)始加工時(shí)間2x n－1次。故確定N n個(gè)虛擬工序的開(kāi)始加工時(shí)間需操作(2x1－1)＋(2x2－1)＋…＋(2x n－1)＝2N n－n次,時(shí)間復(fù)雜度為O(N)。

由上述分析可知,存在多工序同時(shí)結(jié)束的多車(chē)間逆序綜合調(diào)度算法的時(shí)間復(fù)雜度不超過(guò)3次多項(xiàng)式。

5 實(shí)例分析與對(duì)比

5.1 調(diào)度實(shí)例

上述算法設(shè)計(jì)目的具有普遍意義,不以具體實(shí)例為對(duì)象,而為了幫助讀者進(jìn)一步理解,本文以圖4為例做詳細(xì)說(shuō)明。

對(duì)圖4所示產(chǎn)品H虛擬加工樹(shù)進(jìn)行多車(chē)間調(diào)度,設(shè)有3個(gè)車(chē)間,分別是a車(chē)間、b車(chē)間、c車(chē)間,其中a車(chē)間有設(shè)備M1、M2和M3;b車(chē)間有設(shè)備M1、M3和M4;c車(chē)間有設(shè)備M1、M2和M5。根據(jù)定義6、定義7和定義8分析3個(gè)車(chē)間信息可得,對(duì)稱(chēng)設(shè)備資源集Es為{M1},非對(duì)稱(chēng)設(shè)備資源集Ens為{M4,M5},局部對(duì)稱(chēng)設(shè)備資源集Els為{M2,M3}。

調(diào)度產(chǎn)品H的具體過(guò)程如下:

圖4 產(chǎn)品H加工工藝樹(shù)Fig.4 Process tree of product H

首先,將各個(gè)工序間約束關(guān)系取反,根據(jù)工序?qū)傩源_定虛擬工序組1為{H 3,H 8},根據(jù)定義4確定虛擬工序組1前續(xù)工序?yàn)閧H1,H4};依次確定虛擬工序組2為{H9,H11,H13},虛擬工序組2前續(xù)工序?yàn)閧H5,H6},虛擬工序組3為{H18,H21,H23,H27},虛擬工序組3前續(xù)工序?yàn)閧H12,H14,H16,H17,H19},剩余工序?yàn)閧H2,H7,H10,H15,H20,H22,H24,H25,H26}。

然后,將虛擬工序組1前續(xù)工序按逆序動(dòng)態(tài)關(guān)鍵路徑策略和逆序短用時(shí)策略確定調(diào)度順序?yàn)閧H1,H4},依次確定工序加工車(chē)間,工序H1需加工設(shè)備為M4,M4為非對(duì)稱(chēng)設(shè)備資源集Ens中設(shè)備,確定H1在車(chē)間b加工,無(wú)緊前工序不存在虛擬遷移,按首次適應(yīng)調(diào)度策略確定開(kāi)始加工時(shí)間為0;工序H4需加工設(shè)備為M3,M3為局部對(duì)稱(chēng)設(shè)備資源集Els中設(shè)備,H4緊前工序?yàn)镠1在車(chē)間b加工,該車(chē)間可加工H4,確定H4在車(chē)間b加工,無(wú)虛擬遷移,按首次適應(yīng)調(diào)度策略確定開(kāi)始加工時(shí)間為1。將虛擬工序組1{H3,H8}中工序確定加工車(chē)間,工序H3需加工設(shè)備為M1,M1為對(duì)稱(chēng)設(shè)備資源集Es中設(shè)備,H3緊前工序H1在車(chē)間b加工,確定H3在車(chē)間b加工;工序H8需加工設(shè)備為M2,M2為局部對(duì)稱(chēng)設(shè)備資源集Els中設(shè)備,H8緊前工序?yàn)镠4在車(chē)間b加工,該車(chē)間不可加工工序H8,計(jì)算M2所在車(chē)間a和車(chē)間c加工用時(shí)相等,故可任選一車(chē)間調(diào)度,確定H8在車(chē)間a加工,H8存在虛擬遷移,Vr＝Vr＋1;得到H3和H8的緊前工序H1和H4的加工結(jié)束時(shí)間為1和2,按逆序同時(shí)開(kāi)始策略確定虛擬工序組1的開(kāi)始加工時(shí)間為2。

重復(fù)上述步驟依次確定,虛擬工序組2前續(xù)工序的調(diào)度順序?yàn)閧H6,H5},加工車(chē)間分別為車(chē)間c和車(chē)間b,開(kāi)始加工時(shí)間均為4;虛擬工序組2為{H9,H11,H13},加工車(chē)間依次分別為車(chē)間b、車(chē)間c和車(chē)間a,開(kāi)始加工時(shí)間均為5;虛擬工序組3前續(xù)工序的調(diào)度順序?yàn)閧H12,H14,H17,H16,H19},加工車(chē)間分別為車(chē)間a、車(chē)間a、車(chē)間c、車(chē)間b和車(chē)間a,開(kāi)始加工時(shí)間分別為3、3、6、7和6;虛擬工序組3為{H18,H21,H23,H27},加工車(chē)間分別為車(chē)間a、車(chē)間b、車(chē)間c和車(chē)間c,開(kāi)始加工時(shí)間均為8。

最后,確定剩余工序的調(diào)度順序?yàn)閧H7,H10,H22,H25,H26,H2,H15,H20,H24},加工車(chē)間分別為車(chē)間c、車(chē)間c、車(chē)間b、車(chē)間a、車(chē)間a、車(chē)間b、車(chē)間b、車(chē)間a和車(chē)間c,開(kāi)始加工時(shí)間依次分別為4、6、8、7、5、2、7、6和8。圖5為根據(jù)逆序調(diào)度結(jié)果確定的正序調(diào)度甘特圖,可知產(chǎn)品完工時(shí)間為11工時(shí)。由算法調(diào)度過(guò)程可知,產(chǎn)品工序間的虛擬遷移次數(shù)是5次。

圖5 產(chǎn)品H的調(diào)度甘特圖Fig.5 Gantt chart of product H

5.2 對(duì)比分析

為了充分說(shuō)明本文算法較優(yōu),下面介紹基于正序調(diào)度的算法。其主要思想與逆序調(diào)度的區(qū)別在車(chē)間確定和虛擬工序組開(kāi)始加工時(shí)間。其中,確定車(chē)間策略是:判定該工序加工設(shè)備是否屬于Ens,若是,則確定該工序放入對(duì)應(yīng)的非對(duì)稱(chēng)設(shè)備車(chē)間,判斷該工序和其緊前工序加工車(chē)間確定Vr;若不是,則繼續(xù)判定該工序加工設(shè)備是否屬于Els,若是,則按該工序緊前工序加工車(chē)間從多到少依次判斷可加工即放入該車(chē)間加工,不可加工則放入對(duì)應(yīng)可加工車(chē)間加工并判斷Vr;若不是,則該工序加工設(shè)備屬于Es,放入其緊前工序加工車(chē)間最多的車(chē)間加工,若無(wú)緊前工序或無(wú)法通過(guò)緊前工序加工車(chē)間確定則根據(jù)車(chē)間均衡選擇加工車(chē)間加工。每組虛擬工序組的開(kāi)始加工時(shí)間調(diào)度策略可參考文獻(xiàn)[18]。最后,調(diào)度文本實(shí)例得到甘特圖,如圖6所示。

圖6 對(duì)比算法調(diào)度結(jié)果甘特圖Fig.6 Gantt chart of scheduling result by using contrast algorithm

將圖5與圖6對(duì)比可以看出,采用本文算法產(chǎn)品完成時(shí)間為11工時(shí),遷移次數(shù)為5次,采用基于正序的調(diào)度算法的產(chǎn)品完成時(shí)間為13工時(shí),遷移次數(shù)為8次。之所以本文算法效果更好,是因?yàn)槟嫘蛘{(diào)度可以更好地設(shè)計(jì)多組多工序逆序同時(shí)開(kāi)始,減少設(shè)備資源空閑和調(diào)整工序,使操作更加簡(jiǎn)單實(shí)用,并且逆序調(diào)度比正序調(diào)度車(chē)間確定策略更容易實(shí)現(xiàn),減少了工序的遷移。

6 結(jié) 論

(1)逆序分批次調(diào)度策略減少了整體調(diào)度產(chǎn)生的設(shè)備資源占用問(wèn)題。

(2)逆序車(chē)間確定策略確定所有工序加工車(chē)間,減少了工序間的遷移。

(3)逆序同時(shí)開(kāi)始策略簡(jiǎn)單方便地實(shí)現(xiàn)了工序間的特殊約束,減少了工序調(diào)整。

[1]李京生,王愛(ài)民,唐承統(tǒng),等.基于動(dòng)態(tài)資源能力服務(wù)的分布式協(xié)同調(diào)度技術(shù)[J].計(jì)算機(jī)集成制造系統(tǒng),2012,18(7):1563-1574.Li Jing-sheng,Wang Ai-min,Tang Cheng-tong,et al.Distributed coordination scheduling technology based on dynamic manufacturing ability service[J].Computer Integrated Manufacturing Systems,2012,18(7):1563-1574.

[2]周鑫,馬躍,胡毅.求解車(chē)間作業(yè)調(diào)度問(wèn)題的混合遺傳模擬退火算法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(2):370-374.Zhou Xin,Ma Yue,Hu Yi.Mixed genetic algorithm and simulated annealing algorithm for solving job shop scheduling problem[J].Journal of Chinese Computer Systems,2015,36(2):370-374.

[3]葉寒鋒,李占山,陳超.基于具有自適應(yīng)與自學(xué)習(xí)能力的粒子群優(yōu)化算法的車(chē)間調(diào)度算法[J].吉林大學(xué)學(xué)報(bào):理學(xué)版,2014,52(1):93-97.Ye Han-feng,Li Zhan-shan,Chen Chao.Adaptive and self-learning pso-based algorithm for job shop scheduling problem[J].Journal of Jilin University(Science Edition),2014,52(1):93-97.

[4]趙詩(shī)奎,方水良.基于工序編碼和鄰域搜索策略的遺傳算法優(yōu)化作業(yè)車(chē)間調(diào)度[J].機(jī)械工程學(xué)報(bào),2013,49(16):160-169.Zhao Shi-kui,Fang Shui-liang.Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization[J].Journal of Mechanical Engineering,2013,49(16):160-169.

[5]謝志強(qiáng),楊靜,周勇,等.基于工序集的動(dòng)態(tài)關(guān)鍵路徑多產(chǎn)品制造調(diào)度算法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(2):406-412.Xie Zhi-qiang,Yang Jing,Zhou Yong,et al.Dynamic critical paths multi-product manufacturing scheduling algorithm based on operation set[J].Chinese Journal of Computers,2011,34(2):406-412.

[6]曾強(qiáng),楊育,王小磊,等.基于多規(guī)則設(shè)備分配及工序排序的FJSP多目標(biāo)集成優(yōu)化方[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(5):980-989.Zeng Qiang,Yang Yu,Wang Xiao-lei,et al.Integrated multi-objective optimization method for FJSP based on multiple rule machine assignment and job sequencing[J].Computer Integrated Manufacturing Systems,2011,17(5):980-989.

[7]謝志強(qiáng),桂忠艷,楊靜.基于設(shè)備驅(qū)動(dòng)和實(shí)質(zhì)路徑的動(dòng)態(tài)并行綜合柔性調(diào)度算法[J].機(jī)械工程學(xué)報(bào),2014,50(18):204-211.Xie Zhi-qiang,Gui Zhong-yan,Yang Jing.Dynamic parallel integrated flexible scheduling algorithm based on device driver and essential path[J].Journal of Mechanical Engineering,2014,50(18):204-211.

[8]謝志強(qiáng),周含笑,于潔,等.基于設(shè)備驅(qū)動(dòng)的綜合柔性調(diào)度沖突調(diào)解算法[J].北京理工大學(xué)學(xué)報(bào),2014,34(11):1151-1156.Xie Zhi-qiang,Zhou Han-xiao,Yu Jie,et al.Conflict mediation algorithm of the integrated flexible scheduling based on the device driver[J].Transactions of Beijing Institute of Technology,2014,34(11):1151-1156.

[9]Palmieri F,Buonanno L,Venticinque S,et al.A distributed scheduling framework based on selfish autonomous agents for federated cloud environments[J].Future Generation Computer Systems,2013,29(6):1461-1472.

[10]Oike S,Tanaka T,Zhu J,et al.Robust production scheduling using autonomous distributed systems[J].Key Engineering Materials,2012,516:166-169.

[11]Valilai O F,Houshmand M,et al.A collaborative and integrated platform to support distributed manufacturing system using a service-oriented approach based on cloud computing paradigm[J].Robotics and Computer-Integrated Manufacturing,2013,29(1):110-127.

[12]陶辛陽(yáng),夏唐斌,奚立峰.基于健康指數(shù)的預(yù)防性維護(hù)與多目標(biāo)生產(chǎn)調(diào)度聯(lián)合優(yōu)化建模[J].上海交通大學(xué)學(xué)報(bào),2014,48(8):1170-1174.Tao Xin-yang,Xia Tang-bin,Xi Li-feng.Health-index-based joint optimization of preventive maintenance and multi-attribute production scheduling[J].Journal of Shanghai Jiaotong University,2014,48(8):1170-1174.

[13]Dalfard V M,Mohammadi G.Two meta-heuristic algorithms for solving multi-objective flexible jobshop scheduling with parallel machine and maintenance constraints[J].Computers&Mathematics with Applications,2012,64(6):2111-2117.

[14]Marichelvam M K,Prabaharan T,Yang X S.A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems[J].IEEE Transactions on Evolutionary Computation,2014,18(2):301-305.

[15]謝志強(qiáng),周含笑,桂忠艷,等.基于擬關(guān)鍵路徑的二車(chē)間綜合調(diào)度算法[J].計(jì)算機(jī)科學(xué),2013,40(4):193-198.Xie Zhi-qiang,Zhou Han-xiao,Gui Zhong-yan,et al.Integrated scheduling algorithm of two workshops based on ACPM[J].Computer Science,2013,40(4):193-198.

[16]謝志強(qiáng),鄭付萍,朱天浩.兩車(chē)間可調(diào)度工序均衡處理的綜合調(diào)度算法[J].計(jì)算機(jī)工程,2014,40(1):295-304.Xie Zhi-qiang,Zheng Fu-ping,Zhu Tian-hao.Integrated scheduling algorithm with equalization processing of schedulable processes in two workshops[J].Computer Engineering,2014,40(1):295-304.

[17]謝志強(qiáng),于潔,陳德運(yùn),等.基于鄰域渲染的二車(chē)間綜合調(diào)度算法[J].機(jī)械工程學(xué)報(bào),2016,52(1):149-159.Xie Zhi-qiang,Yu Jie,Chen De-yun,et al.Integrated scheduling algorithm of two workshops based on the principle of the neighborhood rendering[J].Journal of Mechanical Engineering,2016,52(1):149-159.

[18]朱天浩,謝志強(qiáng),鄭付萍.存在多工序同時(shí)結(jié)束的綜合調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(10):2907-2911,2919.Zhu Tian-hao,Xie Zhi-qiang,Zheng Fu-ping.Integrated scheduling algorithm of multi-procedures ended together[J].Application Research of Computers,2013,30(10):2907-2911,2919.