蔣大奎 李 波

天津大學(xué)，天津，300072

0 引言

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

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

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

1 問題描述及最優(yōu)性條件

1.1 問題描述

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

圖1 平行機多工廠供應(yīng)鏈調(diào)度問題結(jié)構(gòu)圖

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

1.2 最優(yōu)性條件

定理1 對于問題P，存在具有以下性質(zhì)的最優(yōu)調(diào)度：

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

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

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

記集合Ni（σ）為生產(chǎn)調(diào)度子方案σ指定的由工廠i加工的工件集合，Ni（σ）中工件數(shù)量為ni（σ）。

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

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

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

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

借鑒文獻［9］單機器多工廠供應(yīng)鏈調(diào)度問題的數(shù)學(xué)模型，問題P的混合整數(shù)規(guī)劃模型可以表示為

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

2 禁忌搜索算法設(shè)計

禁忌搜索算法（taboo search algorithm，TS）作為一種求解全局優(yōu)化問題的智能優(yōu)化算法，廣泛應(yīng)用于NP－h(huán)ard組合優(yōu)化問題的近似求解［12－13］。針對問題特點，本文設(shè)計了一種基于向量組編碼結(jié)構(gòu)的禁忌搜索算法及3種鄰域操作。

2.1 編碼結(jié)構(gòu)

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

2.2 初始解

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

圖3 生成初始解的流程圖

2.3 鄰域操作

若當前解為不可行解，本文設(shè)計了塊結(jié)構(gòu)鄰域操作以搜索可行解；若當前解為可行解，本文設(shè)計了插入、交換2種鄰域操作以搜索鄰域中更優(yōu)的解。

2.3.1 塊結(jié)構(gòu)操作

塊結(jié)構(gòu)操作由Nowicki等［14］首先提出，并廣泛應(yīng)用于生產(chǎn)調(diào)度問題。本文設(shè)計了一種塊結(jié)構(gòu)鄰域操作以處理當前解為不可行解的情況，塊結(jié)構(gòu)鄰域操作的具體步驟如下：

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

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

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

若均成立，則執(zhí)行步驟（4）；否則，塊結(jié)構(gòu)操作得到的解為不可行解，塊結(jié)構(gòu)操作終止。

（4）由向量組得到訂單分配子方案δ′和生產(chǎn)調(diào)度子方案σ′，由定理2得到分批運輸子方案φ′，新的方案（δ′，σ′，φ′）生成，塊結(jié)構(gòu)操作完成。

2.3.2 插入操作和交換操作

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

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

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

2.4 禁忌規(guī)則和終止條件

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

2.5 算法框架

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

3 獨立決策策略

本文設(shè)計了獨立決策下總部的訂單分配問題模型和各零部件加工廠的生產(chǎn)運輸集成調(diào)度問題模型。

3.1 訂單分配問題模型

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

（1）工廠為機器作業(yè)環(huán)境，工廠i加工工件j的加工時間為pij／ri。

圖4 禁忌搜索算法框架

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

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

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

3.2 生產(chǎn)運輸集成調(diào)度問題模型

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

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

4 仿真實驗及分析

4.1 算例

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

4.2 結(jié)果及分析

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

表1 參數(shù)設(shè)置

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

表2 2種不同決策策略的比較結(jié)果

表3 兩種不同求解方法的比較結(jié)果

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

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

5 結(jié)論

（1）本文針對大型裝備制造企業(yè)內(nèi)部供應(yīng)鏈的特點，提出了一類平行機多工廠供應(yīng)鏈調(diào)度問題，給出了解的最優(yōu)性條件，并建立了問題的數(shù)學(xué)模型。

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

（3）通過仿真實驗驗證了平行機多工廠供應(yīng)鏈調(diào)度策略的優(yōu)越性和本文禁忌算法的有效性。

［1］柏孟卓，陳峰，唐國春.供應(yīng)鏈管理中生產(chǎn)和運輸集成的排序問題［J］.工業(yè)工程與管理，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］陳榮軍，唐國春.平行機的供應(yīng)鏈排序［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，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］蔣大奎，李波.基于混合禁忌搜索算法的供應(yīng)鏈排序問題［J］.機械工程學(xué)報，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.