存在設備時間限制的兩個企業協同的綜合調度算法

謝志強 裴莉榕

(哈爾濱理工大學計算機科學與技術學院 哈爾濱 150080)

1 前言

隨著工業經濟的發展，建設高水平開放式區域協同創新體系成為工業經濟發展的重中之重。企業協同隨之成為企業發展必須解決的問題。企業之間通過信息共享，從而實現加工任務在合作車間之間的相互協調和交換，從而相互代為完成加工任務，使企業更大限度地完成一些不能獨立完成的任務，最大限度地減少設備空閑時間，提高設備的使用率，提升企業收益，擴大企業規模。為此，協同加工更符合現階段生產需求。關于車間調度問題的研究，從車間類型分析，分為流水車間[1]和作業車間[2]。從車間數目分析，分為單車間和多車間[3]。從加工設備屬性分析，分為柔性車間[4–6]和非柔性車間。從目標數量分析，分為單目標和多目標[7–9]。隨著產品復雜度變高，單車間制造已經無法滿足現階段的需求。為此，在單車間調度的基礎上，眾多學者對多車間以及分布式車間制造進行了深入的研究，并取得了相應的成果[10–15]。

以上這些研究都是將產品分化成零部件，將零部件進行分批次加工，加工完成后再進行組裝，屬于流水線工程，并沒有考慮針對于單件復雜產品加工時，工序之間存在約束關系，將加工和裝配并行進行，從而實現縮短加工時間以及減少加工成本，提升產品的生產效率。于是，謝志強等人[16–19]提出了一系列綜合調度問題。關于綜合調度問題的研究，從產品角度分析，包含一般產品綜合調度問題和特殊產品綜合調度問題。一般產品綜合調度問題又分為單產品綜合調度問題、多產品小批量綜合調度問題。特殊產品綜合調度問題分為工序緊密銜接調度問題和工序非緊密銜接調度問題。以上對于綜合調度的研究大部分為單一企業內部車間問題，也就是一個企業內工件在單個車間或多個車間進行加工引發的一系列問題。文獻[20]提出的基于混合教學優化算法的多車間協作綜合調度，雖然提出了車間協作問題，但只考慮多車間設備集的交集部分且對于遷移問題的考慮固定且單一，并沒有實質上的解決車間協作的問題。而針對企業車間協同問題研究較少，企業協同主要是分為兩種，一種是自有加工企業設備使用時間存在限制，導致加工任務不能如期完成；另一種是存有特殊工序在特殊設備上進行加工，自有加工企業缺少該工序所需加工設備。上述兩種情況使得自有加工企業都必須尋求其他加工企業進行輔助加工，從而完成加工任務。而在實際生產過程中，由于加工設備的定期維護會出現設備的正常使用時間存在極大的限制。因此，提出的存在設備時間限制的兩個企業協同的綜合調度算法即是針對企業車間協同問題中自有加工企業設備使用時間存在限制的綜合調度問題進行進一步的分析和研究。設計加工任務分配策略保證了自有加工企業獲得更多的收益，設計原加工企業工序車間選擇策略和協同選擇策略，在考慮到運輸問題并滿足交貨期的前提下選取獲得收益更大的協同加工企業。經過實例分析，該算法可以更好地解決加工企業由于設備使用時間的限制并帶有交貨期和收益的企業車間協同綜合調度問題。

2 問題描述分析

綜合調度問題既不僅考慮了產品的加工問題，同時也考慮了產品的裝配問題。在實際的生產中，通過企業之間的信息共享，實現產品加工任務在合作車間之間的相互協調和交換，相互代為完成任務。協同加工不僅能夠減少設備空閑時間，提高設備的使用率，同時能夠提升企業的經濟效益并增大企業收益。協同加工通常是由兩種情況引起的，一種是自有加工企業設備使用時間存在限制，導致加工任務不能在交貨期內完成；另一種是存有特殊工序需要在特殊設備上進行加工，自有加工企業不存在該工序所需加工設備，這兩種情況使得自有加工企業都必須尋求其他加工企業輔助加工，從而完成加工任務。協同加工以往的模式是將企業任務信息，設備信息等所有信息集中處理，進行資源優化。但是這種方式數據量過于龐大并且在處理數據的過程中由于冗長的環節致使企業信息泄露對企業造成不可估量的損失。為此，提出存在設備時間限制的兩個企業協同的綜合調度算法需要滿足以下要求：

(1)訂單共享中心的任務不強制分配給各加工企業，各加工企業可自由選擇。

(2)各加工企業提交協同意向后，并不表示合作達成。需要協同分配中心確定并簽訂合作達成意向書后，方可證明合作成功。

(3)任務共享中心中的任務會隨時更新，但達成協議的任務不可毀約，協議達成立刻生效。

(4)因兩個加工企業間協同任務引起的運輸費用，由兩個加工企業協商決定分配比例。

(5)現以最理想的模式分析，運輸所消耗的時間和成本固定且模式單一，不會受到外界環境影響。

(6)由于是協同合作，所以各加工企業不可能存在無限制的加工，各加工企業車間設備加工有時限。

(7)各協同加工企業達成協議之后，必須按照其限定時間內完成加工，不受其他因素影響。

(8)各加工企業設備屬性值均在正常范圍內，不會出現超負載或損壞等問題。

(9)各加工企業設備為非柔性設備，加工工序和設備型號為一對一的關系。

(10)企業內部各加工工序在各設備間移動所消耗的時間和費用存在且固定不變。

(11)加工工序之間存在工藝約束，必須在其緊前工序全部加工完成后方可加工。

(12)設備在加工過程中不存在臨時插入，必須加工完當前工序方可加工下一道工序。

(13)產品加工完成之后，直接送往管理中心，運輸費用由自有加工企業承擔。

利用數學的方式描述該調度問題，對所有相關的變量進行如下定義：

J表示所有工序即工序集，單件復雜產品存在n道工序，J=J1,J2,···,Jn。

B表示所有加工車間即車間集，共存在L個車間，B=B1, B2,···,BL。

存在設備時間限制的兩個企業協同的綜合調度算法的目標函數可定義為

其中，式(1)表示自有加工企業在該任務中獲得的最終收益。式(2)表示的是交貨期約束。式(3)和式(4)分別表示自有加工企業和協同加工企業的收益約束，各參數含義如表1所示。

表1 各參數含義

3 算法詳細設計

近年來由于協同算法的提出，如何在保證商業信息安全的前提下，將不同區域內的加工企業建立合作并合理地分配加工任務，使企業獲得更多的收益成了解決問題的關鍵，且該算法不受企業規模所影響。其主要步驟如下：

(1)需要自有加工企業將邊際收益較低的任務或是不可獨立完成的任務發送到任務共享中心。

(2)設備存在閑置的企業根據任務共享中心的信息提出協同意向及自身加工車間現況以及物流等信息。

(3)協同分配中心將各加工企業的協同意向進行合并處理，整理出方案列表，并反饋給自有加工企業。

(4)自有加工企業根據方案列表中的信息，選取心儀的方案，并確定合作意向，并將合作意向反饋給協同分配中心。

(5)協同分配中心確定雙方合作意向達成。并回到步驟(2)，直至所有任務最終分配完畢。

3.1 加工任務拆分策略

為了保證自有加工企業能夠獲得更多的收益，需要將加工任務盡可能多的分配給自有加工企業進行加工，因此，需要將加工任務進行有效分解并設計了加工任務分配策略。加工任務分配策略主要分為初始拆分和拆分調整兩大步驟，以圖1加工樹為例對其進行初始拆分。節點信息為工序號/設備號/加工時長(h)。

圖1中箭頭所指方向為該工序的緊后工序，以往的計算路徑長度的方式都是從根節點開始，計算根節點到該節點的路徑長度為該節點的路徑長度值。采用逆向思維方式進行剪枝從而生成初始拆分樹，具體步驟如下：

圖1 加工樹例1

(1)輸入加工樹中各節點信息。

(2)標記各節點層數。加工樹共有C層，根節點層數為1，依次遞增，最后1層層數為C，按層遍歷加工樹。

(3)判斷該工序是否有緊前工序，若不存在緊前工序跳到步驟(4)。若存在緊前工序跳到步驟(5)。

(4)計算各工序路徑長度，路徑長度=max{緊前工序路徑長度+當前工序加工時長}。

(5)標記各工序路徑長度。

(6)判斷加工樹中是否存在未標記工序，若是轉到步驟(3)，若否轉到步驟(7)。

(7)按后序遍歷的方式將加工樹中路徑長度小于設備時限的工序進行剪枝。

(8)建立虛擬根節點，將剪枝下的工序重新構建成一棵加工樹，即初始拆分樹。

按照初始拆分的步驟，首先逆向計算各工序的路徑長度，并進行標記，如圖2所示。以工序J8為例，工序J8存在3個緊前工序，最大緊前工序路徑長度與自身加工時間加和結果為J8的路徑長度。以加工時長為13作為設備加工時限，將所有路徑長度小于13的工序和子樹進行剪枝。帶虛線的工序為被剪掉的工序。

將圖2中虛線圈出的工序進行剪枝，然后建立虛擬跟節點，構建拆分樹，生成初始拆分樹，如圖3所示。

圖2 標記加工樹

圖3 初始拆分樹

在實際調度過程中設備總時長會受工序中關系約束和遷移約束影響且加工設備存在時間限制，所以首次拆分后產生的初始拆分樹在實際操作過程中，并不一定能夠滿足時間限制約束。因此需要對拆分樹中的工序進行調整，在對初始拆分樹進行微調整的過程中，需要對樹中各工序確定加工車間。判斷是否存在超時工序，若存在超時的工序，將超時工序從拆分樹中刪除，并添加到協同加工樹中。由于初始拆分樹是從自有加工工藝樹剪枝后合成的，所以存在純葉子節點，即該工序不存在緊前工序且優先級值為1。

3.2 原加工企業車間選擇策略

可調度工序存在緊前工序和緊后工序，由于存在多個車間且每個車間包含的加工設備型號不一致，將所有設備統一在一起，計算各型號設備個數，存在個數為1的設備，標記為特殊設備，當存在工序加工設備為特殊設備時，標記Di=1，否則為0。用二進制形式標記各工序加工設備所在車間，假設，存在3個車間B1,B2,B3，車間B1包含設備D1,D2,D4，車間B2包含設備D2,D3，車間B3包含設備D3,D4，工序i可以在設備D3上加工。則用二進制表示為011。若其緊后工序i+1所用設備為D2，則用二進制表示為110，將兩者進行“&”運算得出結果為010，可以確定可共用車間為B2。工序車間選擇具體步驟如下：

(1)將初始拆分樹中非純葉子節點的各工序信息輸入。

(2)用二進制形式標記各工序加工設備所在車間，并對在特殊設備上加工的工序標記Di=1。

(4)建立虛擬加工工序，模擬工序遷移情況，并計算工序在其加工設備所在車間的最早開始時間，若最早開始時間相同轉到步驟(5)，若最早開始時間不相同，選取最早開始時間最早的車間，轉到步驟(8)。

(5)查看該工序緊后工序二進制值進行“&”運算，確定結果為1的車間，并記錄車間數CB。

(6)判斷CB值是否為1。若為1，將該工序安排在該加工車間，轉到步驟(8)，若不為1，轉到步驟(7)。

(7)判斷不同車間內該工序所需設備上的空閑時間段，選取空閑時間段小的車間。

(8)將該工序從工序集中刪除，判斷工序集是否為空，若工序集為空，輸出甘特圖，轉到步驟(9)，若工序集不為空，轉到步驟(3)。

(9)將補入集中純葉子節點輸入，查找空閑時間段，利用考慮無縫拉伸的多設備緊湊優化調度策略將純葉子工序插入。

(10)判斷插入后是否超時，若不超時，轉到步驟(11)，若超時，轉到步驟(12)。

傳統制造業習慣于在遇到管理問題時，通過成立專門應對部門的方法來解決，這就導致各個層級的管理部門越來越多，組織機構錯綜復雜，管理權限界定不明確，往往老的問題還沒有解決，新的衍生問題又浮出水面。

(11)輸出該工序。

(12)從補入集中刪除該工序，判斷補入集是否為空，若為空，轉到步驟(13)，若不為空，轉到步驟(9)。

(13)輸出甘特圖，結束。

3.3 協同車間選擇策略

對于每個企業來說，可以將邊際效益低或無法獨自加工完成的任務發送到共享中心中尋找協同企業進行加工合作，掙取對應收益，而自身獲取收益的高低則是選擇合作伙伴的關鍵。由此，對于協同任務的分析變得尤為重要。加工樹經過拆分后生成自有加工企業加工的拆分加工樹，而其余部分為協同加工企業加工的協同加工樹。為了使自有加工企業在滿足交貨期的前提下，獲取最大的收益，需要對協同加工樹分析，確定協同加工企業所需設備的最低要求，以及在存在運輸問題的情況下，加工任務能夠在交貨期內完成。主要從以下4個點進行分析，設備型號、協同車間最大加工時間、設備數、收益。詳細流程圖如圖4所示。

圖4 協同選擇策略流程

(1)設備型號是根據協同加工樹中各節點信息確定協同車間需要的設備型號。

(2)協同車間最大加工時間是根據各企業之間的實際地理位置建立數據庫，確定運輸時間Tv以及協同車間到管理中心的時間Tm，由于拆分樹已知，且在拆分樹調整過程中便可得到對應的甘特圖，從而得到原加工車間加工時間To，利用公式Ts= TQ–(To+Tv+Tm)，得到協同車間最大加工時間Ts。

(3)設備數是假定同型號設備數目為Dw=1，w表示型號標號，以協同車間最大加工時間Ts為時間限制，調用拆分樹調整算法對協同加工樹進行分析，標記存在延遲的工序，判斷是否存在工序加工時間超過Ts。對超過Ts工序及其緊前工序集中發生延遲的工序時長進行分析，尋找對應型號設備并將設備數目加1，輸出各型號設備數。假定工序J1的緊前工序為J2,J3，工序J2的緊前工序為J4，存在3種型號設備D1,D2,D3。

假定工序調度后的甘特圖如圖5中下半部分，虛線為時間線，當工序J1超時，首先判斷超時工序是否為延遲工序。J1為延遲工序。增加該工序所用設備，重新調度判斷是否超時，圖例中剛好未超時。假若重新調節后工序仍然超時，判斷其緊前工序集中工序所在設備是否需要增加，如圖6所示。J1仍為超時，查詢延遲時間最大設備，增加該設備數，新調度判斷是否超時，直到不存在超時工序或不存在延遲時間。

圖5 協同加工樹調度甘特圖

圖6 增加設備后對比甘特圖

(4) 收益是由于各車間情況基本確定，且對應的運輸情況也已知，便可以獲得相關費用信息，利用公式R=Ro–(Fo+αFv+Fm)確定不同企業協同合作下的收益，最終以收益最大值為協同加工企業。

4 實例分析

算法可以用于復雜的單產品，為了便于理解，實例用較為簡單的產品工藝樹進行分析。模擬其中數據并以圖7所示加工樹為實例，圖中工序信息為工序號、設備號、加工時長。從葉子節點開始，逆向計算各工序路徑長度，假定以時長20 h為限，對加工樹進行剪枝，如圖8所示。

圖7 加工樹實例

圖8 標記加工樹

構建虛擬根節點，將剪枝下的樹和節點中不存在緊后工序的節點與根節點建立連接，如圖9所示。

圖9 初始拆分樹

從根節點開始，正序計算各工序路徑長度并標記其層數，不存在緊前工序的節點為葉子節點。將不存在緊前工序且層數為1 的純葉子節點即{J7,J15,J16}放入補入集。如圖10所示，深灰色填充的工序為純葉子節點。將除純葉子節點以外的葉子節點工序放入工序集。虛線畫出的節點為葉子節點。

圖10 標記初始拆分樹

得到工序集{J28,J27,J26,J24,J23,J22,J21,J20,J18,J9}，路徑值最大工序為J20，路徑長度為19，加工設備為D4，設備對應工序備選集為{J27,J20}，最大層數工序為J27，輸出J27，設備D4為特殊設備，將工序J27安排在車間B2中，記錄開始時間和結束時間(0 ,2)，將J27從工序集合備選集中刪除，產生新葉子節點工序J19，設備為D3，將工序J19加入工序集，工序J20未輸出，備選集中工序為{J20}，個數為1，直接分配J20車間為B2，記錄開始時間和結束時間(2,7)，將J20從工序集和備選集中刪除，備選集中工序個數為0。不斷更新循環得到的甘特圖如圖11所示。輸入補入集工序{J7,J15,J16}，工序J7所用設備為D2，工序(J15,J16)所用設備為D3，利用無縫拉伸的多設備緊湊優化調度思想，將工序{J7,J15,J16}按加工時長依次插入，插入后未發生超時，插入后甘特圖如圖12所示。

圖11 初始拆分樹調度發生超時甘特圖

圖12 純葉子節點插入后對比甘特圖

文獻[17]中涉及交貨期問題，但針對的是多產品小批量問題，基于此，假定產品優先級為1，遷移時間同表2所示，閾值仍為20，利用文獻[17]中的算法調度后的甘特圖如圖13所示。通過計算可知，算法在閾值內可加工20道工序，加工總時長為85.8 h，而文獻[17]中的算法在閾值內可加工14道工序，加工總時長為65.8 h，相差6道工序和20 h。對比結果可得，算法對于求解加工企業設備使用時間存在限制并帶有交貨期和收益的企業車間協同綜合調度問題能夠得到優良結果。說明了算法的有效性，相較已有文獻[12]中的算法具有一定的優越性。針對協同加工樹進行分析確定加工設備型號。經過調節后，最終形成的協同加工樹，協同加工樹仍然需要4種型號設備D1,D2,D3,D4，利用長路徑、層優先和短用時策略對協同加工樹進行調度，形成圖14所示甘特圖。

表2 企業內部設備遷移信息 (h)

圖13 文獻[17]調度甘特圖

圖14 協同加工樹調度甘特圖

假定交貨期TQ=60，利用協同選擇策略發現存在3家企業符合要求，時間未超過交貨期，由于圖例較為簡單，恰好未存在延遲工序且不存在超時現象，故不存在可增加設備，只需考慮運輸問題。假定3家符合條件的協同企業P1,P2,P3，相關信息如表3所示。

表3 協同加工企業相關信息

假定α取值為0.5(具體取值根據實際合約情況決定)，Ro=150,Fo=50,To=19.6。利用公式R=Ro–(Fo+αFv+Fm)和TQ=To+Ts+Tv+Tm計算得到如下結果：R1=80.0, T1=54.9, R2=82.25,T2=56.5, R3=81.91, T3=58。由此可以看出，在未超過交貨期的前提下，盈利最多的是P2，故選擇協同加工企業P2進行合作。

5 結束語

(1) 相比以往的研究，本文首次提出解決兩個企業車間協同合作問題的方法，通過對比收益值能夠更加直觀反應企業收益。較比單一多車間加工與單一分布式車間加工的加工方式，協同加工合作能為加工企業取得更多的盈利。

(2) 將工序在多車間遷移問題和產品在兩車間的運輸問題以具體數值進行分析，提高了結果準確性。

因此，提出的存在設備時間限制的兩個企業協同的綜合調度算法，可以更好解決加工企業設備使用時間存在限制并帶有交貨期和收益的企業車間協同綜合調度問題，使企業更大限度地完成一些不能獨立完成的任務，最大限度地減少設備空閑時間，提高設備的使用率，提升企業收益，擴大企業規模。對企業協同綜合調度問題的進一步研究具有一定的意義。