基于禁忌搜索的平行機多工廠供應鏈調度

蔣大奎 李 波

天津大學，天津，300072

0 引言

對于一些大型裝備制造項目，裝備制造企業需要多個零部件加工廠為總裝工廠提供裝配部件。企業普遍采用的項目實施流程為：企業總部將工件分配給多個零部件加工廠，并要求在指定期限內完成工件生產并送至總裝工廠，各個零部件加工廠需要在指定期限內以最低的生產和運輸成本完成總部分配的任務。由于總部與零部件加工廠存在著不同的資源約束和決策目標，當各部門獨立決策時，難以實現企業整體利益最大化。如何通過對工件分配、工件生產和運輸調度協同優化以降低企業內部供應鏈成本，成為這類企業關注的熱點問題。

為了有效地解決這類問題，供應鏈調度問題（supply chain scheduling）被提出，并受到廣泛關注。供應鏈調度問題將排序理論應用于供應鏈管理，對生產調度和分批發送2個階段的問題集成研究，從具體操作層面使用確定性模型研究供應鏈問題［1］。文獻［2－4］分別研究了單機器和平行機單工廠供應鏈調度問題，但并沒有考慮訂單運輸時間和車輛裝載能力約束。針對上述研究的不足，文獻［5－8］提出了啟發式算法以求解考慮訂單運輸時間和車輛裝載能力約束的單機器和平行機單工廠供應鏈調度問題。對供應鏈中有多個工廠的情況，由于需要考慮訂單分配，問題的復雜性明顯增加。Chen等［9］研究了單機器作業環境下的多工廠供應鏈調度問題，證明了問題是NP難題，并設計了啟發式算法。蔣大奎等［10］將文獻［9］中的客戶數量擴展為多個，并設計了混合禁忌搜索算法進行求解。在多工廠供應鏈調度問題中，目前尚沒有關于工廠為平行機作業環境的相關研究報道［11］。

針對零部件加工廠普遍為平行機作業的特點，本文提出一類平行機多工廠供應鏈調度問題，為該問題設計了一種基于向量組編碼結構的禁忌搜索算法，并通過仿真實驗驗證了平行機多工廠供應鏈調度的優越性和本文禁忌算法的有效性。

1 問題描述及最優性條件

1.1 問題描述

本文的問題描述如下：某企業在不同地理位置共有m個零部件加工廠，零部件加工廠集合記作M＝｛1，2，…，m｝。每個零部件加工廠i的加工環境為具有ri臺相同的機器，在任意時刻，每臺機器只能加工一個工件。計劃期內企業需要加工n個工件（訂單），工件集合記作N＝｛1，2，…，n｝，每個工件僅需在一臺機器上加工一次。工件j在工廠i的加工時間為pij，加工成本為cij。工件加工后按批次發送給總裝工廠，每個批次最多發送b個工件。工廠i發送一個批次的運輸時間為ti，運輸成本為fi。所有工件必須在交貨期限D內送至總裝工廠。企業需要將工件分配給各個零部件加工廠、安排工件在各臺機器上的加工順序以及對如何分批發送工件進行決策，通過制定集成調度方案（以下簡稱方案）以使完成所有工件的生產和運輸總成本最小。為方便，將本文問題簡記為P。問題P的結構如圖1所示。

圖1 平行機多工廠供應鏈調度問題結構圖

為方便表達，本文采用三參數法（δ，σ，φ）描述一個方案，其中參數δ表示一個訂單分配子方案，它指定了每個工件的加工工廠；參數σ表示δ給定下的一個生產調度子方案，它指定了加工每個工件的機器及加工順序；參數φ表示σ給定下的一個分批運輸子方案，它指定了工廠的發送批次數、每批次的發送時間及工件所在的發送批次。

1.2 最優性條件

定理1 對于問題P，存在具有以下性質的最優調度：

（1）同一個工廠加工任何2個工件之間沒有空閑。

（2）每一批工件的發送均發生在該批工件中的某一個工件的加工完成時間。

（3）每個工廠加工的所有工件按加工完成順序進行發送。

記集合Ni（σ）為生產調度子方案σ指定的由工廠i加工的工件集合，Ni（σ）中工件數量為ni（σ）。

定理2 當δ和σ給定時，問題P具有一個最優的分批運輸子方案φ＊。將每個集合Ni（σ）中的所有工件分成yi個批次發送，yi的計算公式為

其中，第一個批次發送ni（σ）－（yi－1）b個工件，其余的yi－1個批次均發送b個工件。

定理1的結論顯然成立，定理2的證明見文獻［11］的定理7。

通過上述定理，問題得到簡化。簡化后問題的決策變量為xijk＝1，即工件j由工廠i的第k臺機器加工，否則為0；yi為工廠i發送的批次數。

借鑒文獻［9］單機器多工廠供應鏈調度問題的數學模型，問題P的混合整數規劃模型可以表示為

其中，目標函數式（1）的第一項表示完成所有工件的生產總成本，第二項為運輸總成本；約束式（2）表示各機器加工的工件必須在交貨期限內完成；約束式（3）表示每個工件的加工需求均要得到滿足，且只能由一臺機器加工；約束式（4）為發送批次的約束。

2 禁忌搜索算法設計

禁忌搜索算法（taboo search algorithm，TS）作為一種求解全局優化問題的智能優化算法，廣泛應用于NP－hard組合優化問題的近似求解［12－13］。針對問題特點，本文設計了一種基于向量組編碼結構的禁忌搜索算法及3種鄰域操作。

2.1 編碼結構

圖2 6個工件的2個雙機器工廠的向量組

2.2 初始解

初始解的生成步驟如圖3所示。

圖3 生成初始解的流程圖

2.3 鄰域操作

若當前解為不可行解，本文設計了塊結構鄰域操作以搜索可行解；若當前解為可行解，本文設計了插入、交換2種鄰域操作以搜索鄰域中更優的解。

2.3.1 塊結構操作

塊結構操作由Nowicki等［14］首先提出，并廣泛應用于生產調度問題。本文設計了一種塊結構鄰域操作以處理當前解為不可行解的情況，塊結構鄰域操作的具體步驟如下：

（1）記當前解中違反交貨期限約束的機器在向量組中對應的向量為Vak，從Vak中任選一個元素A。

（2）在向量組中任選一個向量Vbl，Vak≠Vbl，在向量Vbl中任選一個元素B。將元素A從Vak中取出，并插入到元素B前面或將元素A與元素B交換。

（3）記向量Vak中由工件組成的集合為Na，向量Vbl中由工件組成的集合為Nb，分別判斷以下2個公式是否成立：

若均成立，則執行步驟（4）；否則，塊結構操作得到的解為不可行解，塊結構操作終止。

（4）由向量組得到訂單分配子方案δ′和生產調度子方案σ′，由定理2得到分批運輸子方案φ′，新的方案（δ′，σ′，φ′）生成，塊結構操作完成。

2.3.2 插入操作和交換操作

插入操作通過將向量組中某個向量的元素插入到其他向量中，以得到新的訂單分配子方案δ′和生產調度子方案σ′，再由定理2得到新的分批運輸子方案φ′。

交換操作通過交換2個不同向量中的元素，以得到新的訂單分配子方案δ′和生產調度子方案σ′，再由定理2得到新的分批運輸子方案φ′。

借助德國卡爾蔡司偏光顯微鏡觀察C/C試樣的金相結構.在MM-W1型立式萬能摩擦磨損試驗機上進行摩擦磨損試驗(見圖1).C/C試樣的對磨銷為40Gr鋼,硬度HRC45,規格為Φ5.5 mm×10 mm,表面粗糙度Ra0.8μm.

2.4 禁忌規則和終止條件

本文算法的禁忌規則為：如果向量Vik中的工件j移動到其他向量中，則在接下來的λ代中不允許工件j被移回到向量Vik。如果經過鄰域操作得到比當前解更好的解，則不管該鄰域操作是否被禁忌，都采用該鄰域作為當前鄰域。終止條件為達到預先設定的迭代次數μ。

2.5 算法框架

禁忌搜索算法框架如圖4所示。

3 獨立決策策略

本文設計了獨立決策下總部的訂單分配問題模型和各零部件加工廠的生產運輸集成調度問題模型。

3.1 訂單分配問題模型

為了縮短項目周期，總部以完成所有工件的時間最小化為決策目標。對于該訂單分配問題，本文作以下假設：

（1）工廠為機器作業環境，工廠i加工工件j的加工時間為pij／ri。

圖4 禁忌搜索算法框架

（2）每個加工完成的工件單獨運送。

訂單分配問題的決策變量為zij＝1，即工件j由工廠i加工，否則zij為0。其訂單分配問題的數學模型為

其中，式（6）是目標函數，用于尋找在所有可行訂單分配方案中完成所有工件加工所需時間最短的訂單分配方案；約束式（7）表示每個工廠必須在交貨期限前完成工件的加工；約束式（8）表示每個工件的加工需求均要得到滿足，且只能分配給一個工廠。

3.2 生產運輸集成調度問題模型

經過訂單分配，工廠i需要加工的工件集合記為Ni。每個工廠i對生產和運輸進行集成調度，以實現交貨期限內完成Ni中所有工件的生產運輸總成本最小化。生產運輸集成調度的決策變量與1.2節中模型的決策變量相同。每個工廠i的生產運輸集成調度問題模型為

其中，式（10）是目標函數，為工廠i的生產和運輸總成本最小化；約束式（11）表示工廠i的每臺機器加工的工件必須在交貨期限內完成；約束式（12）表示分配給工廠i的每個工件的加工需求均要得到滿足，且只能由工廠i的一臺機器加工；約束式（13）為對工廠i發送批次的約束。

4 仿真實驗及分析

4.1 算例

10個零部件加工廠為總裝工廠提供500個工件，每個運輸批次最多可發送6個工件，交貨期限為1200。為了避免具體算例對算法性能可信度的影響，本文通過隨機方式生成以下數據，每個零部件加工廠擁有的機器數服從均勻分布［2，5］，各零部件加工廠到總裝工廠的運輸時間和運輸成本均服從均勻分布［100，1000］，工件在各零部件加工廠的加工時間服從均勻分布［10，100］，加工成本服從均勻分布［100，500］。

4.2 結果及分析

為了驗證平行機多工廠供應鏈調度策略優于獨立決策策略，本文對2種不同策略進行比較，2種策略均使用CPLEX 12.2求解。同時為了驗證本文禁忌算法的有效性，本文分別使用本文禁忌算法和CPLEX 12.2對算例進行求解。本文禁忌算法通過Visual C＋＋2005實現，并使用C＋＋標準模板庫。PC為 AMD Athlon（tm）Ⅱ X2 245，4GB RAM。表1為本文禁忌算法的參數設置。

表1 參數設置

針對10組隨機算例，分別運算10次。2種不同決策的比較結果如表2所示，2種不同求解方法的比較結果如表3所示。

表2 2種不同決策策略的比較結果

表3 兩種不同求解方法的比較結果

由表2可知，平行機多工廠供應鏈調度策略完成所有工件花費的時間僅比獨立決策多約26，但生產運輸總成本卻降低了40%左右。原因為：獨立決策時各部門的決策目標不一致，導致了企業的整體利益的損失。供應鏈調度決策在交貨期限允許的情況下，以延長較短的交貨時間為代價，大幅度地降低了供應鏈的運作成本，體現了平行機多工廠供應鏈調度策略的優越性。

由表3可知，本文禁忌算法得到的平均結果與CPLEX得到的最優解的偏差僅約3%，但卻節省了90%以上的運算時間。同時，CPLEX對10個不同算例的計算時間差異較大，標準差為44.09，而本文禁忌算法的平均計算時間標準差僅為0.34。因此，本文禁忌算法能夠在較短且穩定的時間內得到滿意的結果。

5 結論

（1）本文針對大型裝備制造企業內部供應鏈的特點，提出了一類平行機多工廠供應鏈調度問題，給出了解的最優性條件，并建立了問題的數學模型。

（2）根據解的特點，提出了一種向量組編碼結構，并設計了禁忌搜索算法及塊結構、插入、交換3種鄰域操作。

（3）通過仿真實驗驗證了平行機多工廠供應鏈調度策略的優越性和本文禁忌算法的有效性。

［1］柏孟卓，陳峰，唐國春.供應鏈管理中生產和運輸集成的排序問題［J］.工業工程與管理，2007，12（5）：47－50.

［2］Hall N G，Potts C N.Supply Chain Scheduling：Batching and Delivery［J］.Operations Research，2003，51（4）：566－584.

［3］Hall N G，Potts C N.The Coordination of Scheduling and Batch Deliveries［J］.Annual of Operations Research，2005，135（1）：41－64.

［4］Averbak I，Xue Zhihui.On－line Supply Chain Scheduling Problems with Preemption［J］.European Journal of Operational Research，2007，181（1）：500－504.

［5］Pundoor G，Chen Zhilong.Scheduling a Production－distribution System to Optimize the Tradeoff between Delivery Tardiness and Total Distribution Cost［J］.Naval Research Logistics，2005，52（6）：571－589.

［6］Chen Zhilong，Pundoor G.Integrated Order Scheduling and Packing［J］.Production and Operations Management，2009，18（6）：672－692.

［7］Chen Zhilong，Vairaktarakis G L.Integrated Scheduling of Production and Distribution Operations［J］.Management Science，2005，51（4）：614－628.

［8］陳榮軍，唐國春.平行機的供應鏈排序［J］.系統科學與數學，2010，30（2）：274－282.

［9］Chen Zhilong，Pundoor G.Order Assignment and Scheduling in a Supply Chain［J］.Operations Research，2006，54（3）：555－572.

［10］蔣大奎，李波.基于混合禁忌搜索算法的供應鏈排序問題［J］.機械工程學報，2011，47（20）：53－59.

［11］Chen Zhilong.Integrated Production and Outbound Distribution Sheduling：Review and Extensions［J］.Operations Research，2010，58（1）：130－148.

［12］Armentano V A，Shiguemoto A L，Lokketangen A.Tabu Search with Path Relinking for an Integrated Production－ distribution Problem ［J］.Computers ＆ Operations Research，2011，38（8）：1199－1209.

［13］潘全科，朱劍英.一類解決Job shop問題的禁忌搜索算法［J］.中國機械工程，2006，17（5）：536－539.

［14］Nowicki E，Smutanicki C.A Fast Taboo Search Algorithm for the Job－shop Problem［J］.Management Science，1996，42（6）：797－813.