基于禁忌搜索的平行機(jī)多工廠供應(yīng)鏈調(diào)度

蔣大奎 李 波

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

0 引言

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

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

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

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

1.1 問(wèn)題描述

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

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

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

1.2 最優(yōu)性條件

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

（1）同一個(gè)工廠加工任何2個(gè)工件之間沒(méi)有空閑。

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

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

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

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

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

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

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

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

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

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

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

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

圖2 6個(gè)工件的2個(gè)雙機(jī)器工廠的向量組

2.2 初始解

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

圖3 生成初始解的流程圖

2.3 鄰域操作

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

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

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

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

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

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

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

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

2.3.2 插入操作和交換操作

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

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

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

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

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

2.5 算法框架

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

3 獨(dú)立決策策略

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

3.1 訂單分配問(wèn)題模型

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

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

圖4 禁忌搜索算法框架

（2）每個(gè)加工完成的工件單獨(dú)運(yùn)送。

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

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

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

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

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

4 仿真實(shí)驗(yàn)及分析

4.1 算例

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

4.2 結(jié)果及分析

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

［1］柏孟卓，陳峰，唐國(guó)春.供應(yīng)鏈管理中生產(chǎn)和運(yùn)輸集成的排序問(wè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］陳榮軍，唐國(guó)春.平行機(jī)的供應(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)鏈排序問(wèn)題［J］.機(jī)械工程學(xué)報(bào)，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］潘全科，朱劍英.一類(lèi)解決Job shop問(wèn)題的禁忌搜索算法［J］.中國(guó)機(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.