薛 梅

淮北師范大學(xué)1.經(jīng)濟(jì)與管理學(xué)院;2.信息學(xué)院，安徽淮北，235000

1 問(wèn)題的提出

資源最優(yōu)配置問(wèn)題一直是企業(yè)關(guān)注的重點(diǎn)，合理的資源配置不僅可以大大提高生產(chǎn)效率，還可以提高企業(yè)的顧客服務(wù)水平。如何高效地配置供應(yīng)鏈資源，現(xiàn)已成為供應(yīng)鏈調(diào)度理論亟待解決的問(wèn)題。2003年,Hall等[1]首次介紹了供應(yīng)鏈調(diào)度的概念，以?xún)?yōu)化供應(yīng)鏈成本和配送時(shí)間為目標(biāo)，構(gòu)建動(dòng)態(tài)規(guī)劃算法，解決由一個(gè)供應(yīng)商和多個(gè)顧客組成的供應(yīng)鏈協(xié)同調(diào)度問(wèn)題。Li等[2]研究了單機(jī)環(huán)境下半成品、成品的運(yùn)輸與生產(chǎn)協(xié)同調(diào)度問(wèn)題。張維存等[3]研究了原材料采購(gòu)、生產(chǎn)和配送的調(diào)度模型，以最小化完工時(shí)間為優(yōu)化目標(biāo)，設(shè)計(jì)改進(jìn)人工蜂群算法，證實(shí)了算法的有效性。蔣大奎等[4]探討了平行機(jī)環(huán)境下的訂單指派問(wèn)題，通過(guò)設(shè)計(jì)的混合優(yōu)化算法優(yōu)化了最小化提前期和成本加權(quán)和的目標(biāo)。軒華[5]考慮了運(yùn)輸能力有限的動(dòng)態(tài)混合流水車(chē)間調(diào)度問(wèn)題，采用改進(jìn)拉格朗日松弛算法對(duì)問(wèn)題求解，結(jié)果證明其有效。黃小曼[6]研究了差異分批調(diào)度問(wèn)題，設(shè)計(jì)生產(chǎn)、庫(kù)存和配送的調(diào)度優(yōu)化方案，提出近似算法以實(shí)現(xiàn)最小化企業(yè)成本和制造時(shí)間跨度的目標(biāo)。Naso等[7]從混凝土調(diào)度案例中歸納模型，研究了混凝土計(jì)劃、生產(chǎn)與運(yùn)輸調(diào)度問(wèn)題，提出啟發(fā)式算法有效解決JIT問(wèn)題。劉春來(lái)[8]考慮了由一個(gè)制造商、多個(gè)中間商和多個(gè)顧客組成的供應(yīng)鏈問(wèn)題，其中中間商位于不同地理位置。以最小化總成本為目標(biāo)，設(shè)計(jì)了基于遺傳算法的啟發(fā)式方法，驗(yàn)證了算法的合理性。陳榮軍等[9]考慮了由一個(gè)制造商和一個(gè)顧客組成的兩級(jí)供應(yīng)鏈，研究了按照工件最大送貨時(shí)間和平均送貨時(shí)間為排序規(guī)則的同類(lèi)平行機(jī)調(diào)度問(wèn)題，基于動(dòng)態(tài)規(guī)劃構(gòu)造了多項(xiàng)式時(shí)間近似算法，分析了算法的性能比。Borumand等[10]同樣考慮由一個(gè)供應(yīng)商和一個(gè)客戶(hù)組成的兩級(jí)供應(yīng)鏈，以最小化總延遲工件數(shù)和生產(chǎn)成本為目標(biāo)，設(shè)計(jì)改進(jìn)遺傳算法(GA-VIKOR)，通過(guò)與其他算法的比較證實(shí)了算法的有效性。Hamid等[11]研究了多目標(biāo)供應(yīng)鏈優(yōu)化問(wèn)題，分別以最小化成本和庫(kù)存為目標(biāo)，提出了IENS算法，并證實(shí)其有效。Sajede等[12]研究了由一個(gè)制造商和兩類(lèi)不同需求的客戶(hù)組成的供應(yīng)鏈，一類(lèi)客戶(hù)在支付延遲交付費(fèi)用前提下同意接受延遲交付，而另一類(lèi)不同意，以最小化成本為目標(biāo)，設(shè)計(jì)了改進(jìn)遺傳算法和蟻群算法，說(shuō)明算法的可行性和滿(mǎn)意性。薛梅等[13]研究了單機(jī)調(diào)度問(wèn)題，設(shè)計(jì)改進(jìn)離散粒子群算法優(yōu)化制造時(shí)間。

綜上所述，傳統(tǒng)調(diào)度模型大多只考慮單機(jī)，忽略了半成品工件生產(chǎn)與運(yùn)輸對(duì)企業(yè)生產(chǎn)效率和成本的影響。本文以同類(lèi)平行機(jī)為背景，研究半成品工件的運(yùn)輸與生產(chǎn)以及成品工件的運(yùn)輸問(wèn)題，通過(guò)對(duì)工件進(jìn)行排序、分批，設(shè)計(jì)批次分配和運(yùn)輸調(diào)度方案，以最小化制造跨度時(shí)間為優(yōu)化目標(biāo)，提出改進(jìn)離散粒子群算法，一定程度上提高生產(chǎn)效率，減少企業(yè)交付時(shí)間。

2 問(wèn)題描述和數(shù)學(xué)模型

2.1 問(wèn)題描述

圖1展現(xiàn)了一個(gè)供應(yīng)商和一個(gè)客戶(hù)組成的二層供應(yīng)鏈。供應(yīng)商有w個(gè)分布在不同地理位置的倉(cāng)庫(kù)，每個(gè)倉(cāng)庫(kù)都有充足的半成品工件，工件是由各自的尺寸Sj和加工時(shí)間pj共同決定的。倉(cāng)庫(kù)只有一輛運(yùn)載工具，假定往返時(shí)間是固定的，記為T(mén)={T1,T2,…,Tk}。供應(yīng)商擁有多臺(tái)同類(lèi)平行機(jī)，即可以同時(shí)加工多個(gè)工件的機(jī)器。機(jī)器容量與供應(yīng)商運(yùn)載車(chē)輛容量一樣，均為B，假設(shè)所有工件的尺寸均不大于B?？蛻?hù)向供應(yīng)商訂購(gòu)n個(gè)工件，工件集合記為J={J1,J2,…,Jn}?？蛻?hù)一旦下訂單，供應(yīng)商便開(kāi)始處理訂單。首先需要從倉(cāng)庫(kù)里選擇n個(gè)半成品工件運(yùn)輸?shù)焦S，然后經(jīng)過(guò)加工運(yùn)輸給客戶(hù)。

圖1 兩級(jí)供應(yīng)鏈生產(chǎn)與運(yùn)輸協(xié)同調(diào)度模型

2.2 數(shù)學(xué)模型

模型存在如下假設(shè)：

①所有機(jī)器和車(chē)輛在零時(shí)刻有效；

②倉(cāng)庫(kù)的運(yùn)載車(chē)輛有容量限制，每次只能運(yùn)輸一個(gè)工件；供應(yīng)商僅有一輛運(yùn)載工具

③工件加工過(guò)程不存在強(qiáng)占操作，即一旦批次開(kāi)始加工，除非加工結(jié)束，否則不允許將工件從該批次中剝離；

④有一個(gè)充分大的緩存區(qū)，即加工完成的批次可以暫時(shí)放在緩存區(qū)；

模型的符號(hào)和含義說(shuō)明：

參數(shù)：W,倉(cāng)庫(kù)的數(shù)量；k,倉(cāng)庫(kù)的序號(hào)；n,工件總數(shù)；j,工件序號(hào)，j=1,2,…,n;m,機(jī)器序號(hào)；l,工件批次總數(shù)，[n/B]≤l≤n；i,批次序號(hào)，i=1,2,…,l;Pb,批次bi的加工時(shí)間，等于批次中加工時(shí)間最長(zhǎng)的數(shù)值；Rj,工件j到達(dá)機(jī)器的時(shí)間；T′,運(yùn)載車(chē)輛在供應(yīng)商和客戶(hù)之間的來(lái)回運(yùn)輸時(shí)間。為了方便描述，將裝卸載時(shí)間統(tǒng)一計(jì)算到運(yùn)輸時(shí)間中。

決策變量：xjim,若工件j屬于第i個(gè)批次并且被機(jī)器m加工，則xjim=1，否則xjim=0；S1im,批次bi在機(jī)器m上的開(kāi)始加工時(shí)間；C1im,批次bi在機(jī)器m上的完工時(shí)間；S2im,機(jī)器m上的批次bi的出發(fā)時(shí)間；C2im,機(jī)器m上的批次bi的到達(dá)時(shí)間；Cmax,制造跨度時(shí)間，即最后一個(gè)工件到達(dá)客戶(hù)的時(shí)間。

本文的模型描述如下：

MinimizeCmax

(1)

(2)

(3)

(4)

S1im≥max{Rj×xjim}

(5)

S1im≥C1(i-1)m,i=1,2,…,l

(6)

C1im=S1im+Pb,i=1,2,…,l

(7)

S2im≥C1im,i=1,2,…,l

(8)

S2im≥C2(i-1)m+T’/2,i=1,2,…,l

(9)

Cmax≥C2im,i=1,2,…,l

(10)

式(1)表示優(yōu)化的目標(biāo)是最小化總跨度時(shí)間；式(2)說(shuō)明一個(gè)工件只屬于一個(gè)批次；式(3)說(shuō)明任意批次中所有工件的尺寸之和不能超過(guò)機(jī)器容量；式(4)表示分配時(shí)沒(méi)有工件被落下；式(5)和式(6)表示批次只有在機(jī)器有效的時(shí)候才可以加工；式(7)表示任意批次加工結(jié)束時(shí)間等于批次開(kāi)始加工時(shí)間加上該批次的加工時(shí)間；式(8)和式(9)表示批次加工完成且運(yùn)輸工具有效的時(shí)候才可以被運(yùn)輸；式(10)表示整個(gè)跨度時(shí)間的性質(zhì)。

3 離散粒子群算法及其改進(jìn)算法

3.1 離散粒子群算法

1997年Kennedy和Eberhart為解決離散問(wèn)題，提出了離散粒子群算法(BinaryParticleSwarmOptimization，BPSO)，該算法中粒子的編碼是由一個(gè)多維向量表示的，它的下一代位置是由個(gè)體歷史最優(yōu)位置和群體最優(yōu)位置共同決定。算法的速度更新公式依然采用PSO速度公式，即

(11)

Sig(vij)=1/(1+exp(-vij))

(12)

粒子通過(guò)式(13)改變位置：

(13)

式(11)-(13)中，w為慣性系數(shù)，c1和c2分別為認(rèn)知系數(shù)和社會(huì)系數(shù)，r1、r2和rand均表示[0,1]的隨機(jī)小數(shù)。通過(guò)數(shù)值模擬發(fā)現(xiàn)，當(dāng)Vij∈[-5,5]時(shí)，xij會(huì)有一定的變換概率，因此取Vmax=5是一個(gè)相對(duì)較為合理的值。

3.2 編碼方案及初始化

由模型可知，所有倉(cāng)庫(kù)在零時(shí)刻開(kāi)始無(wú)空閑地運(yùn)輸半成品工件，直到供應(yīng)商處的工件數(shù)達(dá)到訂單數(shù)，這樣便可以得到每個(gè)倉(cāng)庫(kù)運(yùn)送工件的數(shù)量。由于優(yōu)化目標(biāo)是最小化跨度時(shí)間，因此先到必然先安排生產(chǎn)(FCFS)，故可以獲得工件排序和對(duì)應(yīng)的倉(cāng)庫(kù)號(hào)。采用0-1編碼，用Xn維向量表示工件組批方案。數(shù)值1和前面的0組成一批，第n維數(shù)值均取1。如表1給出了一個(gè)實(shí)例，假設(shè)n=10,W=5,T={10,16,24,6,30}。將工件隨機(jī)分成4個(gè)批次(圖2)。由于機(jī)器有容量限制，提出BU(Batch Update)規(guī)則對(duì)存在的不可行解進(jìn)行修正，過(guò)程描述如下：

表1 10個(gè)工件排序例子

圖2 工件隨機(jī)組批示例

對(duì)于任意批次bi，如果bi容量大于B，則對(duì)該批次進(jìn)行如下處理：

如果|bi|-B+|bi+1|≤B，那么選擇第一運(yùn)輸階段最晚到達(dá)機(jī)器的工件J*，將J*歸入到批次bi+1中。否則在j+1位置重新插入新批次，將工件J*歸入批次bi+1中。然后將J*從批次bi中移除。

3.3 粒子適應(yīng)度值的計(jì)算

適應(yīng)度值是制造跨度時(shí)間。如表2給出了一組初始解。假設(shè)B=10，根據(jù)BU規(guī)則得到修正解，分批結(jié)果見(jiàn)表3。

表2 解的修正情況

表3 工件組批結(jié)果示例

根據(jù)模型可知，還需要將批次分配到機(jī)器上進(jìn)行處理。由于批次有不同的到達(dá)時(shí)間，為了優(yōu)化制造跨度時(shí)間，將按照先到達(dá)先安排處理(firstcomefirstserved,FCFS)規(guī)則分配批次。根據(jù)表1和表4給出的實(shí)例，可以得到分批結(jié)果，見(jiàn)表5。再利用FCFS規(guī)則對(duì)批次進(jìn)行分配，結(jié)果如圖3。

任務(wù)績(jī)效會(huì)受到樂(lè)觀希望、奮發(fā)進(jìn)取以及自信勇敢的事務(wù)型心理資本的積極影響，任務(wù)績(jī)效會(huì)受到堅(jiān)韌頑強(qiáng)的正向影響，但是這一影響并不顯著；針對(duì)工作績(jī)效來(lái)講，事務(wù)性心理資本各個(gè)維度能夠發(fā)揮明顯的正向影響，其中在工作奉獻(xiàn)方面，奮發(fā)進(jìn)取的影響較大；而從人際促進(jìn)方面，堅(jiān)韌頑強(qiáng)、樂(lè)觀希望、自信勇敢等具有積極影響。

圖3 2個(gè)機(jī)器情況下批次分配示例

表4 10個(gè)工件調(diào)度例子

表5 工件組批和批次到達(dá)時(shí)間

3.4 改進(jìn)算法

BPSO算法多次迭代后會(huì)導(dǎo)致粒子搜索能力下降。故本文提出改進(jìn)離散粒子群算法(縮記為PMs-MBPSO)，引入交叉和變異因子，有效解決算法早熟問(wèn)題。因優(yōu)化目標(biāo)是最小化制造時(shí)間，故交叉操作是將粒子按照適應(yīng)度值從小到大排序，選擇前20%的粒子隨機(jī)兩兩進(jìn)行交叉，產(chǎn)生相應(yīng)的子代，然后用子代取代父代。每維隨機(jī)產(chǎn)生0或1，如果數(shù)值等于1，則將該維數(shù)值互換，否則不互換，如圖4。

圖4 交叉操作實(shí)例

變異操作是在粒子改變位置的過(guò)程中，增加編碼數(shù)值的不確定性。變異概率以適應(yīng)度值為基準(zhǔn)，公式如下：

(14)

(14)式中，fmin指全局極值，favg指平均值，f指當(dāng)前粒子的適應(yīng)度值，P1=0.1，P2=0.01。每個(gè)粒子生成[0,1]間的隨機(jī)小數(shù)，并將其與Pm進(jìn)行比較，如果小于Pm，則粒子變異，否則不變異，如圖5。

圖5 變異操作實(shí)例

面向問(wèn)題的離散粒子群算法和改進(jìn)離散粒子群算法的流程圖如下圖6和圖7所示：

圖6 PMs-BPSO算法流程圖

圖7 PMs-MBPSO算法流程圖

4 數(shù)值模擬與結(jié)果分析

4.1 參數(shù)取值

本文用隨機(jī)產(chǎn)生算例的方法，將PMs-MBPSO算法與PMs-BPSO算法、PMs-GA算法進(jìn)行比較。為了測(cè)試算法的有效性和滿(mǎn)意性，將從5個(gè)維度考慮算例規(guī)模：工件數(shù)量J，工件加工時(shí)間Pj，工件尺寸Sj，機(jī)器數(shù)M和倉(cāng)庫(kù)數(shù)W，具體取值情況見(jiàn)表6。

表6 參數(shù)取值情況

4.2 結(jié)果分析

參數(shù)設(shè)置：初始染色體數(shù)為100，交叉概率Pc=0.8，變異概率Pm=0.1。粒子種群數(shù)為100，Vmin=-5，Vmax=-5，初始化速度公式Vij=Vmin+rand*(Vmax-Vmin)，c1=c2=2，w=0.5+rand/2。仿真算例均在VisualC#2010平臺(tái)下實(shí)現(xiàn)，以迭代300次作為算法終止條件。

根據(jù)表6取值可得24種不同規(guī)模的算例，用M(a)J(b)p(c)s(d)W(e)表示，其中a、c、d、e∈{1,2}，b∈{1,2,3}。用最好值、最差值和平均值進(jìn)行比較，分別用best、worst和average標(biāo)記。為描述算法改進(jìn)程度，定義改進(jìn)率IA來(lái)體現(xiàn)PMs-MBPSO算法相較于其他兩個(gè)算法的改進(jìn)情況，見(jiàn)式(15)。

(15)

其中A代表PMs-BPSO和PMs-GA算法，值越大表明改進(jìn)效果越好，具體情況見(jiàn)表7和表8。

表7 2個(gè)機(jī)器情況下PMs-MBPSO算法改進(jìn)結(jié)果

表8 4個(gè)機(jī)器情況下PMs-MBPSO算法改進(jìn)結(jié)果

由表7和表8可知，PMs-MBPSO的最好值全部?jī)?yōu)于其他兩種算法，最差值也幾乎都優(yōu)于PMs-GA算法的最好值。隨著工件數(shù)量的增加導(dǎo)致解空間呈指數(shù)增長(zhǎng)，使得三種算法的搜索能力均有所下降，但PMs-MBPSO相對(duì)于PMs-BPSO和PMs-GA算法而言具備明顯的優(yōu)勢(shì)。這說(shuō)明隨著工件規(guī)模的增多，PMs-MBPSO具有較好的魯棒性。對(duì)于J1類(lèi)，PMs-MBPSO的改進(jìn)程度較差，這是由于工件規(guī)模較小，解空間較小，三種算法都能在固定的迭代次數(shù)中找到近似的最好值。

半成品工件的運(yùn)輸-生產(chǎn)-運(yùn)輸多階段調(diào)度問(wèn)題常常存在于像鋼鐵企業(yè)這類(lèi)生產(chǎn)過(guò)程非常復(fù)雜、生產(chǎn)工藝要求較高的企業(yè)。而本文提出的改進(jìn)離散粒子群算法在一定程度上可以縮短產(chǎn)品制造時(shí)間，提高企業(yè)生產(chǎn)效率，降低生產(chǎn)成本。

5 結(jié) 語(yǔ)

本文考慮了同類(lèi)平行機(jī)背景下，分布在不同地理位置的工件的生產(chǎn)與運(yùn)輸協(xié)同調(diào)度問(wèn)題。在生產(chǎn)能力和運(yùn)輸能力均有限的情況下，構(gòu)建調(diào)度模型，針對(duì)問(wèn)題特點(diǎn)，提出改進(jìn)離散粒子群算法。采用FCFS規(guī)則把批次分配到同類(lèi)平行機(jī)上，并對(duì)迭代過(guò)程中產(chǎn)生的不可行解利用BU規(guī)則進(jìn)行修正。通過(guò)仿真實(shí)驗(yàn)將PMs-MBPSO和PMs-BPSO、PMs-GA進(jìn)行比較，結(jié)果表明PMs-MBPSO算法的滿(mǎn)意性。這表明針對(duì)本文的調(diào)度模型，PMs-MBPSO算法能夠大大提高資源配置效率，對(duì)于供應(yīng)商而言不僅可以節(jié)約時(shí)間，還可以減少產(chǎn)品提前期，更快速地將產(chǎn)品運(yùn)輸給客戶(hù)，從而獲得顧客滿(mǎn)意，這對(duì)于企業(yè)的運(yùn)營(yíng)管理有著極重要的意義。

在后續(xù)的研究中，可以從兩個(gè)方面進(jìn)行，一是改變優(yōu)化的目標(biāo)，如考慮優(yōu)化供應(yīng)商總成本，最大延誤工件數(shù)，或者兩者的加權(quán)和等；二是改變生產(chǎn)特點(diǎn)，如考慮機(jī)器的惡化效應(yīng)和工人的學(xué)習(xí)效應(yīng)等。