存在多工序同時結束的多車間逆序綜合調度算法

謝志強,郭 禾,蘇文秀,辛 宇,楊 靜

(1.哈爾濱理工大學計算機科學與技術學院,哈爾濱150080;2.哈爾濱工程大學 計算機科學與技術學院,哈爾濱150001)

0 引 言

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

在產品從單車間到多車間的加工調度過程中,不僅需要考慮工序遷移和車間負載均衡的問題,而且需要考慮同時結束的工序中存在相同加工設備的問題。針對正序調度過程需多次遷移虛擬工序造成操作復雜和設備資源浪費的問題,本文提出存在多工序同時結束的多車間逆序綜合調度算法。該算法將多組虛擬工序單獨分批次逆序調度,確定各個批次的調度順序,設計逆序車間確定策略來確定每個工序的加工車間,最后,采用首次適應調度策略確定一般工序的開始加工時間,并設計逆序同時開始策略確定每組虛擬工序組的逆序開始加工時間。該算法不僅實現了存在多工序同時結束特殊約束的單件復雜產品從單車間到多車間調度加工的轉變,而且解決了存在特殊約束的多車間調度中產品盡早完工和遷移次數較少的問題。最后,通過實例調度對本文算法進行了說明分析。

1 問題描述

單件復雜產品在多車間綜合調度的過程中,工序間不僅存在一般的約束關系,而且部分工序間還存在需要同時結束約束的特殊約束關系。為了使產品的加工和裝配盡早完工,本文設計了逆序調度方法,將產品虛擬加工樹逆序后多車間綜合調度的約束關系如下:

(1)在同一時間里,一道工序只能被一臺機器加工且一臺機器只能加工一道工序。

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

(3)每個車間的各個機器上后續工序需在前續工序加工完畢后開始加工。

(4)有同時結束特殊約束的工序逆序后要求同時開始加工。

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

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

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

對于一個有N個工序的單件復雜產品在M臺機器上加工的問題(其中N個工序中有n組需同時結束的工序,M臺設備分布在不同地域的m個不同車間里),由約束條件分析可知使產品加工盡早完工的數學模型為:

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

由于該問題是多車間逆序加工問題且存在需同時結束的特殊約束條件,為了縮短工序遷移次數,保證各個車間的負載均衡,使產品總的加工時間減少,需要增加約束條件:

式中:V為加工產品的虛擬遷移次數;T w和T w′為不同車間上產品工序的總的加工時間;S wij和S w′i′j′為有同時結束特殊約束的產品工序的逆序開始加工時間。式(5)表示逆序調度過程中工序的虛擬遷移次數盡可能少;式(6)表示各個車間上工序的總加工時間差盡可能小;式(7)表示存在同時結束特殊約束的工序逆序同時開始加工。

2 問題分析與策略設計

2.1 問題分析與相關概念

關于存在同時結束特殊工序的問題,考慮到工序間的特殊約束條件,若采用正序整體調度的方式,為保證特殊工序的約束條件需多次移動特殊工序,導致操作復雜且設備資源空閑。若使用逆序調度策略,并且將特殊工序單獨分離加工,可避免特殊工序的移動,達到操作簡單且產品完工時間縮短的目的。

關于多車間調度問題,需要考慮產品的緊前、緊后工序不在同一車間加工產生工序遷移,導致產品加工出現額外等待的情況,為了減少產品的完工時間,必須控制遷移次數。針對多工序同時結束的多車間調度,相較于單車間,增加了同組虛擬產品可以存在在多車間相同設備上加工的情況,需要對多組虛擬工序組的調度多加考慮,以保證產品在滿足特殊約束的情況下完工時間較短。

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

分析產品工序的屬性信息,采用逆序調度后,定義相關概念如下:

定義1 虛擬工序:工序屬性中p≠0的工序。

定義2 一般工序:工序屬性中p＝0的工序。

定義3 虛擬工序組p:工序屬性中p≠0且p值相等的工序。

定義4 虛擬工序組p前續工序:在確定虛擬工序組p后根據工序間約束關系,循環查找緊前工序直到緊前工序為虛擬工序或緊前工序已定義所得到的所有工序。

定義5 虛擬遷移:加工過程中出現一個逆序緊前工序需要向多個其緊后工序所在加工車間遷移的情況。

設m個車間中設備集合分別為E1,E2,…,E i,其中i＝1,2,…,m。定義相關概念如下:

定義6 對稱設備資源集Es:在m個車間中共同存在的設備資源構成的集合。即Es＝E1∩E2∩…∩E m,若交集為空,則無對稱資源設備。

定義7 非對稱設備資源集Ens:在m個車間中每個車間中單獨存在與其他車間無重復的設備的資源構成的集合。即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 局部對稱設備資源集Els:在m個車間中部分車間存在的相同設備資源構成的集合。即Els＝(E1∪E2∪…∪E m)－Es－Ens。

2.2 逆序分批次調度策略

由于對存在多工序同時結束的產品采用一般正序調度需要多次調整虛擬工序的開始加工時間,導致設備資源空閑且加工周期延長。考慮到同時結束的工序逆序調度后只需同時開始即可,不僅操作簡單,而且避免了工序移動導致的設備資源空閑,所以本文設計逆序分批次調度策略,具體步驟如下:

(1)輸入產品全部工序的屬性信息(不包括工序加工車間信息,需要計算得知),將所有工序逆序處理,即將工序屬性信息中緊前工序集與緊后工序信息交換。例如:q5|e2|4|2|(q2,q4)|q7逆序處理后工序屬性信息為q5|e2|4|2|q7|(q2,q4),表示虛擬工序組2中工序q5在2設備加工4個工時,工序q5的緊前工序為q7,緊后工序有q2和q4。

(2)遍歷工序屬性信息,得到p＝1時的所有工序,即虛擬工序組1,將虛擬工序組1單獨劃分。根據虛擬工序組1中工序屬性信息和定義4確定虛擬工序組1前續工序,并將其單獨劃分。得到虛擬工序組1和虛擬工序組1前續工序。

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

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

為方便理解,特舉例說明逆序分批次調度策略。例如圖1所示的產品A,方框內產品工序屬性信息表示為:工序名/加工設備名/加工時間/是否虛擬工序。逆序分批次調度策略的具體過程如下:將產品A的虛擬加工工藝樹中所有工序的緊前、緊后關系取反;遍歷虛擬加工工藝樹,得到p＝1的工序為A4和A6;根據定義4查找得到虛擬工序A4和A6的前續工序集為{A1,A3};遍歷虛擬加工工藝樹,得到p＝2的工序為A8、A9和A11;根據定義4查找得到虛擬工序A8、A9和A11的前續工序集為{A5};最后剩余工序為A2,A7,A10,A12。因為產品A中有2組虛擬工序組,所以最后分批次得到5部分工序集,見表1。

圖1 產品A的加工工藝樹Fig.1 Process tree of product A

表1 產品A逆序分批次調度結果Table 1 Reverse batch scheduling result of product A

2.3 確定工序調度順序

單件復雜產品的虛擬工藝樹中都存在一條關鍵路徑,優先加工關鍵路徑上的工序可以使產品橫向上工序能更好地并行調度,而且使產品縱向上的后序工序可以更多地與其他工序并行調度,故本文采用逆序動態關鍵路徑調度策略。當動態關鍵路徑策略不能確定工序調度順序時,即有兩個或多個工序有相同的路徑長度時,優先加工用時較短的工序,可以使后續工序獲得較早的加工時間,使后續工序充分并行調度,所以本文同時采用逆序短用時策略。

對存在多工序同時結束的單件復雜產品,在設計逆序分批次調度策略后,考慮到虛擬工序組p前續工序和剩余工序為多個虛擬的加工工藝樹,故采用上述策略確定各個部分的調度順序,以確保工序間的并行調度和縮短各部分虛擬產品的完工時間。而虛擬工序組p是存在同時結束特殊要求的工序,即逆序后要求同時開始加工的工序,若多車間中同組虛擬工序存在加工設備相同的情況,則其不能在同一車間加工,增加了虛擬工序車間確定的復雜性,每組虛擬工序組的調度順序可隨機。對圖1中產品A虛擬加工樹設計逆序分批次調度策略后,確定調度順序見表2。

表2 產品A各部分調度順序Table 2 Scheduling order of parts of product A

2.4 逆序車間確定策略

對單件復雜產品的工序屬性信息分析可知,可以構造一個虛擬的樹狀產品加工工藝樹,所有的葉子節點工序的屬性信息無緊前工序,根節點工序無緊后工序,其余節點工序屬性信息中有一個或多個緊前工序,有且僅有一個緊后工序。設計逆序分批次調度策略后,各個工序屬性信息發生變化,原工序屬性信息中緊前工序集變為逆序后工序屬性信息中的緊后工序集,原工序屬性信息中的緊后工序變為逆序后工序屬性信息中的緊前工序,根節點工序無緊前工序,所有葉子節點工序無緊后工序。分析m個車間中M臺設備的屬性,判斷M臺設備分別為對稱設備資源集Es、非對稱設備資源集Ens、局部對稱設備資源集Els。

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

(1)輸入產品工序信息,設計逆序分批次調度策略確定各部分調度工序,然后確定各部分工序的調度順序。

(2)按調度順序取出工序,判斷該工序所需加工設備,若屬于非對稱設備資源集Ens,則將該工序放入非對稱設備所在車間加工,繼續判斷該工序緊前工序所在車間,若為同一車間則工序虛擬遷移數Vr不變,轉步驟(8);若不在同一車間,則虛擬遷移數Vr＋＋,轉步驟(8)。

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

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

(5)為保證車間負載均衡選擇加工時間少的車間調整加工該工序且虛擬遷移數Vr＋＋,轉步驟(8)。

(6)若該工序所需加工設備屬于對稱設備資源集Es,轉步驟(4);否則轉步驟(7)。

(7)若該工序為一般工序,轉步驟(8);否則判斷該工序加工設備是否已加工同組虛擬工序,若已加工,則轉步驟(5),否則轉步驟(8)。

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

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

按A1,A3,A4,A6,A5,A8,A9,A11,A2,A12,A7,A10順序依次取出工序確定車間,工序A1需在設備M2上加工,M2∈Els,因為A1是根節點工序,逆序無緊前工序,可任選一車間a或b加工,選擇車間b加工;工序A3需在設備M1上加工,M1∈Es,工序A3的緊前工序A1在車間b加工,故A3在車間b加工且Vr＝0;工序A4需在設備M3上加工,M3∈Ens,確定工序A4在車間c加工,工序A4的緊前工序A1在車間b加工,故Vr＝1;以后各個工序處理方式相同,最后得到產品A的工序屬性如圖2所示,虛擬遷移數Vr＝4。

圖2 確定產品A工序加工車間Fig.2 Determine machining workshop of the product A

2.5 逆序同時開始策略

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

圖1所示產品A虛擬加工工藝樹,確定調度順序為A1,A3,A4,A6,A5,A8,A9,A11,A2,A12,A7,A10,按序確定開始加工時間,A1開始加工時間為0,A3開始加工時間為1,A4和A6的開始加工時間為3,全部工序得到開始加工時間后則產品加工完畢。

3 算法詳細設計

根據以上分析和策略設計,為了實現存在多工序同時結束的多車間綜合調度目標,算法流程圖如圖3所示,算法的具體步驟如下:

(1)輸入產品工序信息和多車間設備信息。

(2)根據定義6、定義7、定義8確定對稱設備資源集Es、非對稱設備資源集Ens、局部對稱設備資源集Els;按逆序分批次調度策略將產品工序緊前、緊后關系取反;定義循環變量i＝1。

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

(4)令工序屬性p＝i,遍歷工藝樹得到虛擬工序組p,并記錄其虛擬工序個數為v p。

(5)根據定義4確定虛擬工序組p前續工序,并按逆序動態關鍵路徑策略和逆序短用時策略確定調度順序加入備選工序集。

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

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

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

(9)若M q∈Ens,將工序q放入對應的車間設備加工;否則轉步驟(11)。

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

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

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

(13)調整放入可加工車間中加工用時少的車間加工工序q。

(14)虛擬遷移數Vr＋＋,轉步驟(17)。

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

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

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

(17)若工序q的屬性p＝0,則工序q為一般工序,按首次適應調度策略確定工序q的開始加工時間,從備選工序集中刪除已調度工序,轉步驟(20);否則工序q為虛擬工序,v＋＋,轉步驟(18)。

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

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

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

(21)將剩余一般工序按逆序動態關鍵路徑策略和逆序短用時策略確定調度順序并放入備選工序集中。

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

(23)輸出逆序調度甘特圖,結束。

4 算法復雜度分析

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

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

(2)逆序動態關鍵路徑策略和逆序短用時策略:根據文獻[5],對N－N n個一般工序確定調度順序的比較次數為(N－N n)(N－N n－1),故時間復雜度為O(N)2。

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

(4)確定開始加工時間:對N－N n個一般工序,根據文獻[5]采用首次適應調度策略確定開始加工時間復雜度為O(N－N n)2;對于虛擬工序組n,得到每個虛擬工序緊前工序結束時間需操作x n次,判斷最晚結束時間需x n－1次,確定虛擬工序組n開始加工時間2x n－1次。故確定N n個虛擬工序的開始加工時間需操作(2x1－1)＋(2x2－1)＋…＋(2x n－1)＝2N n－n次,時間復雜度為O(N)。

由上述分析可知,存在多工序同時結束的多車間逆序綜合調度算法的時間復雜度不超過3次多項式。

5 實例分析與對比

5.1 調度實例

上述算法設計目的具有普遍意義,不以具體實例為對象,而為了幫助讀者進一步理解,本文以圖4為例做詳細說明。

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

調度產品H的具體過程如下:

圖4 產品H加工工藝樹Fig.4 Process tree of product H

首先,將各個工序間約束關系取反,根據工序屬性確定虛擬工序組1為{H 3,H 8},根據定義4確定虛擬工序組1前續工序為{H1,H4};依次確定虛擬工序組2為{H9,H11,H13},虛擬工序組2前續工序為{H5,H6},虛擬工序組3為{H18,H21,H23,H27},虛擬工序組3前續工序為{H12,H14,H16,H17,H19},剩余工序為{H2,H7,H10,H15,H20,H22,H24,H25,H26}。

然后,將虛擬工序組1前續工序按逆序動態關鍵路徑策略和逆序短用時策略確定調度順序為{H1,H4},依次確定工序加工車間,工序H1需加工設備為M4,M4為非對稱設備資源集Ens中設備,確定H1在車間b加工,無緊前工序不存在虛擬遷移,按首次適應調度策略確定開始加工時間為0;工序H4需加工設備為M3,M3為局部對稱設備資源集Els中設備,H4緊前工序為H1在車間b加工,該車間可加工H4,確定H4在車間b加工,無虛擬遷移,按首次適應調度策略確定開始加工時間為1。將虛擬工序組1{H3,H8}中工序確定加工車間,工序H3需加工設備為M1,M1為對稱設備資源集Es中設備,H3緊前工序H1在車間b加工,確定H3在車間b加工;工序H8需加工設備為M2,M2為局部對稱設備資源集Els中設備,H8緊前工序為H4在車間b加工,該車間不可加工工序H8,計算M2所在車間a和車間c加工用時相等,故可任選一車間調度,確定H8在車間a加工,H8存在虛擬遷移,Vr＝Vr＋1;得到H3和H8的緊前工序H1和H4的加工結束時間為1和2,按逆序同時開始策略確定虛擬工序組1的開始加工時間為2。

重復上述步驟依次確定,虛擬工序組2前續工序的調度順序為{H6,H5},加工車間分別為車間c和車間b,開始加工時間均為4;虛擬工序組2為{H9,H11,H13},加工車間依次分別為車間b、車間c和車間a,開始加工時間均為5;虛擬工序組3前續工序的調度順序為{H12,H14,H17,H16,H19},加工車間分別為車間a、車間a、車間c、車間b和車間a,開始加工時間分別為3、3、6、7和6;虛擬工序組3為{H18,H21,H23,H27},加工車間分別為車間a、車間b、車間c和車間c,開始加工時間均為8。

最后,確定剩余工序的調度順序為{H7,H10,H22,H25,H26,H2,H15,H20,H24},加工車間分別為車間c、車間c、車間b、車間a、車間a、車間b、車間b、車間a和車間c,開始加工時間依次分別為4、6、8、7、5、2、7、6和8。圖5為根據逆序調度結果確定的正序調度甘特圖,可知產品完工時間為11工時。由算法調度過程可知,產品工序間的虛擬遷移次數是5次。

圖5 產品H的調度甘特圖Fig.5 Gantt chart of product H

5.2 對比分析

為了充分說明本文算法較優,下面介紹基于正序調度的算法。其主要思想與逆序調度的區別在車間確定和虛擬工序組開始加工時間。其中,確定車間策略是:判定該工序加工設備是否屬于Ens,若是,則確定該工序放入對應的非對稱設備車間,判斷該工序和其緊前工序加工車間確定Vr;若不是,則繼續判定該工序加工設備是否屬于Els,若是,則按該工序緊前工序加工車間從多到少依次判斷可加工即放入該車間加工,不可加工則放入對應可加工車間加工并判斷Vr;若不是,則該工序加工設備屬于Es,放入其緊前工序加工車間最多的車間加工,若無緊前工序或無法通過緊前工序加工車間確定則根據車間均衡選擇加工車間加工。每組虛擬工序組的開始加工時間調度策略可參考文獻[18]。最后,調度文本實例得到甘特圖,如圖6所示。

圖6 對比算法調度結果甘特圖Fig.6 Gantt chart of scheduling result by using contrast algorithm

將圖5與圖6對比可以看出,采用本文算法產品完成時間為11工時,遷移次數為5次,采用基于正序的調度算法的產品完成時間為13工時,遷移次數為8次。之所以本文算法效果更好,是因為逆序調度可以更好地設計多組多工序逆序同時開始,減少設備資源空閑和調整工序,使操作更加簡單實用,并且逆序調度比正序調度車間確定策略更容易實現,減少了工序的遷移。

6 結 論

(1)逆序分批次調度策略減少了整體調度產生的設備資源占用問題。

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

(3)逆序同時開始策略簡單方便地實現了工序間的特殊約束,減少了工序調整。

[1]李京生,王愛民,唐承統,等.基于動態資源能力服務的分布式協同調度技術[J].計算機集成制造系統,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]周鑫,馬躍,胡毅.求解車間作業調度問題的混合遺傳模擬退火算法[J].小型微型計算機系統,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]葉寒鋒,李占山,陳超.基于具有自適應與自學習能力的粒子群優化算法的車間調度算法[J].吉林大學學報:理學版,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]趙詩奎,方水良.基于工序編碼和鄰域搜索策略的遺傳算法優化作業車間調度[J].機械工程學報,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]謝志強,楊靜,周勇,等.基于工序集的動態關鍵路徑多產品制造調度算法[J].計算機學報,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]曾強,楊育,王小磊,等.基于多規則設備分配及工序排序的FJSP多目標集成優化方[J].計算機集成制造系統,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]謝志強,桂忠艷,楊靜.基于設備驅動和實質路徑的動態并行綜合柔性調度算法[J].機械工程學報,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]謝志強,周含笑,于潔,等.基于設備驅動的綜合柔性調度沖突調解算法[J].北京理工大學學報,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]陶辛陽,夏唐斌,奚立峰.基于健康指數的預防性維護與多目標生產調度聯合優化建模[J].上海交通大學學報,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]謝志強,周含笑,桂忠艷,等.基于擬關鍵路徑的二車間綜合調度算法[J].計算機科學,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]謝志強,鄭付萍,朱天浩.兩車間可調度工序均衡處理的綜合調度算法[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]謝志強,于潔,陳德運,等.基于鄰域渲染的二車間綜合調度算法[J].機械工程學報,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]朱天浩,謝志強,鄭付萍.存在多工序同時結束的綜合調度算法[J].計算機應用研究,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.