同類平行機生產運輸協(xié)同調度問題研究

薛 梅

淮北師范大學1.經濟與管理學院;2.信息學院，安徽淮北，235000

1 問題的提出

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

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

2 問題描述和數學模型

2.1 問題描述

圖1展現(xiàn)了一個供應商和一個客戶組成的二層供應鏈。供應商有w個分布在不同地理位置的倉庫，每個倉庫都有充足的半成品工件，工件是由各自的尺寸Sj和加工時間pj共同決定的。倉庫只有一輛運載工具，假定往返時間是固定的，記為T={T1,T2,…,Tk}。供應商擁有多臺同類平行機，即可以同時加工多個工件的機器。機器容量與供應商運載車輛容量一樣，均為B，假設所有工件的尺寸均不大于B?？蛻粝蚬逃嗁弉個工件，工件集合記為J={J1,J2,…,Jn}?？蛻粢坏┫掠唵?，供應商便開始處理訂單。首先需要從倉庫里選擇n個半成品工件運輸到工廠，然后經過加工運輸給客戶。

圖1 兩級供應鏈生產與運輸協(xié)同調度模型

2.2 數學模型

模型存在如下假設：

①所有機器和車輛在零時刻有效；

②倉庫的運載車輛有容量限制，每次只能運輸一個工件；供應商僅有一輛運載工具

③工件加工過程不存在強占操作，即一旦批次開始加工，除非加工結束，否則不允許將工件從該批次中剝離；

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

模型的符號和含義說明：

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

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

本文的模型描述如下：

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)化的目標是最小化總跨度時間；式(2)說明一個工件只屬于一個批次；式(3)說明任意批次中所有工件的尺寸之和不能超過機器容量；式(4)表示分配時沒有工件被落下；式(5)和式(6)表示批次只有在機器有效的時候才可以加工；式(7)表示任意批次加工結束時間等于批次開始加工時間加上該批次的加工時間；式(8)和式(9)表示批次加工完成且運輸工具有效的時候才可以被運輸；式(10)表示整個跨度時間的性質。

3 離散粒子群算法及其改進算法

3.1 離散粒子群算法

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

(11)

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

(12)

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

(13)

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

3.2 編碼方案及初始化

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

表1 10個工件排序例子

圖2 工件隨機組批示例

對于任意批次bi，如果bi容量大于B，則對該批次進行如下處理：

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

3.3 粒子適應度值的計算

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

表2 解的修正情況

表3 工件組批結果示例

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

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

圖3 2個機器情況下批次分配示例

表4 10個工件調度例子

表5 工件組批和批次到達時間

3.4 改進算法

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

圖4 交叉操作實例

變異操作是在粒子改變位置的過程中，增加編碼數值的不確定性。變異概率以適應度值為基準，公式如下：

(14)

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

圖5 變異操作實例

面向問題的離散粒子群算法和改進離散粒子群算法的流程圖如下圖6和圖7所示：

圖6 PMs-BPSO算法流程圖

圖7 PMs-MBPSO算法流程圖

4 數值模擬與結果分析

4.1 參數取值

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

表6 參數取值情況

4.2 結果分析

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

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

(15)

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

表7 2個機器情況下PMs-MBPSO算法改進結果

表8 4個機器情況下PMs-MBPSO算法改進結果

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

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

5 結 語

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

在后續(xù)的研究中，可以從兩個方面進行，一是改變優(yōu)化的目標，如考慮優(yōu)化供應商總成本，最大延誤工件數，或者兩者的加權和等；二是改變生產特點，如考慮機器的惡化效應和工人的學習效應等。