作業(yè)車間環(huán)境下的采購生產(chǎn)配送聯(lián)合調(diào)度模型

張維存 高蕊 張曼

摘 要：針對生產(chǎn)配送聯(lián)合調(diào)度（IPDS）模型較少考慮復(fù)雜生產(chǎn)環(huán)境以及采購環(huán)節(jié)的問題，建立了在作業(yè)車間環(huán)境下，以最小化訂單完成時間為目標(biāo)的采購生產(chǎn)配送聯(lián)合調(diào)度（IPPDS）模型，并采用改進的動態(tài)人工蜂群（DABC）算法進行求解。根據(jù)IPPDS問題的特征，首先，采用二維實數(shù)矩陣的編碼方式，實現(xiàn)任務(wù)（加工與運輸）與資源（設(shè)備與車輛）的匹配關(guān)系;其次，采用基于工藝過程的解碼方式，并在解碼過程中針對不同任務(wù)設(shè)計了滿足約束條件的方法，來保證解碼方案的可行性;最后，在算法過程中設(shè)計了引領(lǐng)蜂與跟隨蜂的動態(tài)協(xié)調(diào)機制和局部啟發(fā)式信息。通過實驗給出DABC適當(dāng)?shù)膮?shù)區(qū)間，對比實驗結(jié)果表明， IPPDS策略相較于分段調(diào)度和IPDS策略，調(diào)度時間分別縮短了35.59%和30.95%;DABC相較于人工蜂群（ABC）算法求解效果平均提升了2.54%，相對于改進的遺傳算法（AGA）求解效果平均提升了6.99%。因此，IPPDS策略能更快速地滿足客戶需求，而DABC算法既減少需設(shè)置的參數(shù)，又具有良好的探索和開發(fā)能力。

關(guān)鍵詞：作業(yè)車間調(diào)度;車輛調(diào)度;聯(lián)合調(diào)度;車輛共用;人工蜂群算法

中圖分類號：TP301.6

文獻標(biāo)志碼：A

Procurementproductiondistribution joint scheduling model in job shop environment

ZHANG Weicun*， GAO Rui， ZHANG Man

School of Economics and Management， Hebei University of Technology， Tianjin 300401， China

Abstract：

Aiming at the issue that the Integrated Production and Distribution Scheduling （IPDS） model rarely considers the complex production environment and procurement， the model of Integrated Purchase Production and Distribution Scheduling （IPPDS） with minimizing the order completion time in the job shop environment as target was established and the improved Dynamic Artificial Bee Colony （DABC） algorithm was used to solve the model. Based on characteristics of IPPDS， firstly， to realize the matching relationship between task （processing and transportation） and resource （equipment and vehicle）， a coding method of twodimensional real number matrix was adopted. Secondly， the decoding method based on the process was adopted， and the method to satisfy the constraints for different tasks were designed in the decoding process to ensure the feasibility of the decoding method. Finally， the dynamic coordination mechanism and local heuristic information of leading and following bees were designed in the process of the algorithm. Appropriate parameter intervals of DABC were obtained by experiments， and the experimental results show that： compared with piecewise scheduling and IPDS， IPPDS strategy has the scheduling time reduced by 35.59% and 30.95% respectively. DABC algorithm has the solution effect averagely improved by 2.54% compared with Artificial Bee Colony （ABC） algorithm， and averagely improved by 6.99% compared to the Adapted Genetic Algorithm （AGA）. Therefore， IPPDS strategy can meet customer requirements more quickly， and DABC algorithm not only reduces the parameters to be set， but also has good exploration and development ability.

Key words：

job shop scheduling; vehicle scheduling; joint scheduling; vehicle sharing; Artificial Bee Colony （ABC） algorithm

0?引言

隨著經(jīng)濟的快速發(fā)展和物質(zhì)產(chǎn)品的多樣化，如何高效滿足客戶個性化需求，提高企業(yè)在市場競爭中的信譽度和競爭力成為學(xué)術(shù)界和企業(yè)界關(guān)注的問題。從運作層面，將生產(chǎn)和配送進行聯(lián)合調(diào)度（Integrated Production and Distribution Scheduling， IPDS）為解決上述問題提供了一種有效的探索[1]。

目前，對IPDS問題的研究主要針對較為簡單的配送方式和生產(chǎn)環(huán)境： 李凱等[2]研究了直接配送的IPDS問題，時間窗等約束條件只有在簡單生產(chǎn)環(huán)境下才會考慮[3];劉玲等[4]、Li等[5]研究了單機情形的生產(chǎn)與配送聯(lián)合調(diào)度問題; Joo等[6]、Jiang等[7]研究了并行機情形的生產(chǎn)與配送聯(lián)合調(diào)度問題。也有學(xué)者將IPDS問題范圍進行拓展，從計劃層面對由供應(yīng)商、生產(chǎn)商、配送中心組成的多級供應(yīng)鏈進行建模和分析。Taxakis等[8]以供應(yīng)商的選擇、設(shè)施（工廠、配送中心、零售商等）數(shù)量和位置，分銷策略為變量，建立了一個多產(chǎn)品多階段的單周期供應(yīng)鏈網(wǎng)絡(luò)問題模型，并用遺傳算法進行求解;Jamili等[9]以配送時間及成本為目標(biāo)，建立了采購生產(chǎn)配送三階段物流調(diào)度模型。在IPDS的實踐中應(yīng)用方面，吳瑤等[10]為提高按訂單生產(chǎn)模式下易腐品的生產(chǎn)配送效率，構(gòu)建了以總配送成本最小和交付產(chǎn)品新鮮度最大為目標(biāo)的模型，設(shè)計了基于雙子串編碼的非支配排序遺傳算法進行求解; Kergosien等[11]以交付延遲時間最小為目標(biāo)，研究了化療制劑袋的IPDS問題; Ensafian等[12]構(gòu)建了血小板供應(yīng)鏈的采購生產(chǎn)配送魯棒優(yōu)化模型; Fu等[13]以金屬包裝行業(yè)為背景建立了具有時間窗約束的IPDS模型。

由于IPDS問題的復(fù)雜性，很多學(xué)者研究了其求解策略和求解方法。首先，其求解策略可歸納為分解和集成兩種。分解策略就是先分別求解生產(chǎn)排程和車輛調(diào)度問題各自的可行方案，再將兩者方案進行整合以滿足求解要求和約束條件。而集成策略就是針對生產(chǎn)排程和車輛調(diào)度建立統(tǒng)一的求解方案或模型，同時求出滿足各自問題特征的可行解。Viergutz等[3]指出：集成化策略的求解效果，特別是對于規(guī)模更大的測例，好于分解策略。其次，由于精確算法，如分支定界算法，只在少數(shù)的單機生產(chǎn)環(huán)境下的小規(guī)范測例情形表現(xiàn)良好[14]，因此IPDS求解方法更多采用啟發(fā)式或元啟發(fā)式算法。如改進的蟻群算法[15]、改進的遺傳算法[16]、文化基因算法[17]、迭代局部搜索[3]等。人工蜂群（Artificial Bee Colony， ABC）算法由于算法結(jié)構(gòu)簡單，對解空間的搜索和開發(fā)能力強，收斂速度快，其改進算法已成功應(yīng)用于生產(chǎn)調(diào)度問題[18]，但未見其應(yīng)用于IPDS的求解。

本文將IPDS拓展為采購生產(chǎn)配送聯(lián)合調(diào)度（Integrated Purchase Production and Distribution Scheduling， IPPDS）問題，并從運作層面在作業(yè)車間生產(chǎn)環(huán)境下對該問題進行建模。根據(jù)IPPDS問題特點，采用集成的求解策略利用改進的動態(tài)人工蜂群（Dynamic Artificial Bee Colony， DABC）算法尋求該問題可行、高效的求解方法，為該問題在更復(fù)雜生產(chǎn)環(huán)境下的應(yīng)用提供方法支持。

1?問題描述以及數(shù)學(xué)模型

1.1?問題描述

本文研究一類由J個供應(yīng)商、單個生產(chǎn)商和I個客戶構(gòu)成的IPPDS問題（如圖1所示），并設(shè)供應(yīng)商提供的原料及客戶訂購的產(chǎn)品各不相同。生產(chǎn)商期初接收到客戶下達的訂單Di（i=1，2，…，I），訂單Di需要成品i的數(shù)量為qi。生產(chǎn)商接收訂單后需從供應(yīng)商j（j=1，2，…，J）進行原料采購，每種原料又可以生產(chǎn)多種產(chǎn)品。生產(chǎn)商采用作業(yè)車間的生產(chǎn)方式，即I種產(chǎn)品在G臺設(shè)備上加工，每種產(chǎn)品有其自身的加工路徑，且各工序加工時間已知。成品產(chǎn)出后，若有可用車輛，則將成品配送給客戶，若無可用車輛，則暫放入成品庫等待配送。生產(chǎn)商有K輛容量Vk（k=1，2，…，K）的車輛，所有車輛既可運輸原料，又可運輸成品。求解目標(biāo)是選擇物料的運輸車輛，安排運輸順序，并確定產(chǎn)品投產(chǎn)及在各設(shè)備上的加工順序，使所有客戶訂單執(zhí)行時間（生產(chǎn)和運輸時間）最小。

假設(shè)條件：1）原料和成品庫存量期初為0，且產(chǎn)能和庫存量無限;2）車輛型號、數(shù)量是確定的;3）生產(chǎn)準(zhǔn)備時間、成品裝卸時間忽略不計;4）從0時刻開始運輸物料;5）忽略運輸時的交通狀態(tài)及設(shè)備故障等;6）同類型成品采用整批方式生成。

1.2?數(shù)學(xué)模型

參數(shù)說明?i（i=1，2，…，I）為成品編號; j（j=1，2，…，J）為原料編號;c（c=1，2，…，Ii）為工序編號;m（m=1，2，…，G）為設(shè)備編號;z（z=1，2，…，I，I+1，…，I+J）為物料統(tǒng)一編號;qi為客戶對成品i的需求量;uij為成品i對原料j的單位消耗量;k（k=1，2，…，K）為車輛編號;tkz為車輛k運輸物料z的往返時間;ticm為產(chǎn)品i第c道工序在設(shè)備m上的加工時間;Vk為車輛k的容量。

變量說明?a為運輸次序編號，a=1，2，…，A（A為任意大的自然數(shù)）;tSicm為產(chǎn)品i第c道工序在設(shè)備m上的開工時間;tEicm為產(chǎn)品i第c道工序在設(shè)備m上的完工時間;tSkaz為第a次由車輛k運輸物料z的開始時間;tEkaz為第a次由車輛k運輸物料z的結(jié)束時間;Qkaz為第a次車輛k運輸物料z的運輸量。

決策變量?αi為若安排產(chǎn)品i投產(chǎn)，其值為1，否則為0。βi′im為若設(shè)備m上產(chǎn)品i′緊前于產(chǎn)品i生產(chǎn)，則其值為1，否則為0。δz′zk為若車輛k運輸物料z′緊前于物料z，則其值為1，否則為0。ηkaz為若安排車輛k在第a次運輸物料z，其值為1，否則為0。

目標(biāo)函數(shù)

min（max{tEkaz}）（1）

約束條件：

qi=∑Aa=1∑Kk=1ηkai·Qkai（2）

∑Ii=1αi·uij·qi=∑Aa=1∑Kk=1ηkaj·Qkaj; j=1，2，…，J（3）

∑Ii=1αi=I（4）

tSicm=max{tEi（c-1）m′， βi′im·tEi′cm}（5）

tEicm=tSicm+ticm（6）

tEkaz=tSkaz+ηkaz·tkaz（7）

Qkaz≤Vk（8）

∑Kk=1ηkaj·Qkaj-∑Ii=1αi·qi·uij≥0; tEkaj≤tSi1m（9）

tSkai≥tEiIim（10）

tSkaz≥δz′zk·tEkaz′（11）

式（1）為目標(biāo)函數(shù)，表示所有訂單配送完成時間最大值的最小化;式（2）表示對成品i的配送量等于其訂單需求量;式（3）表示原料j的運輸總量等于產(chǎn)品投產(chǎn)對該原料的需求量之和;式（4）表示所有的成品需求均進行的投產(chǎn);式（5）表示工序開工時間取其上序完工時間和本工序設(shè)備上緊前工序完工時間中兩者的最大值;式（6）、（7）表示加工和運輸任務(wù)的結(jié)束時間等于其開始時間加上任務(wù)執(zhí)行時間，也表示任務(wù)執(zhí)行過程不能中斷;式（8）表示第a次運輸量不大于該車容量;式（9）表示在產(chǎn)品i投產(chǎn)時，原料j的累計運輸量大于投產(chǎn)i對其需求量，即原料不能缺貨或斷流;式（10）表示成品i配送開始時間不早于其產(chǎn)出時間：式（11）表示車輛k的第a次運輸開始時間不能早于其緊前運輸任務(wù)的結(jié)束時間。

2?問題及求解算法分析

IPPDS問題的復(fù)雜性體現(xiàn)在：1）不同于作業(yè)車間調(diào)度問題（Job shop Scheduling Problem，JSP）和車輛調(diào)度問題（Vehicle Routing Problem，VRP）均假定需完成任務(wù)在期初是可執(zhí)行，IPPDS中生產(chǎn)環(huán)節(jié)和配送環(huán)節(jié)需完成任務(wù)因采購和生產(chǎn)環(huán)節(jié)的調(diào)度結(jié)果不同而異，可執(zhí)行時刻未知;2）不同于VRP問題中的車輛資源是已知和確定的，IPPDS問題中采購和配送環(huán)節(jié)的車輛可用性均受對方調(diào)度結(jié)果影響，因而車輛的可用性是未知和變化的。所以，IPPDS問題的復(fù)雜性高于JSP和VRP，也強于將采購、生產(chǎn)、配送問題進行兩兩聯(lián)合調(diào)度的問題。

進一步分析，IPPDS問題的實質(zhì)仍是將車輛和設(shè)備資源在運輸和加工任務(wù)間分配的資源配置問題，且在配置過程中，需要滿足工藝約束、資源獨占約束、數(shù)量約束和時間約束。但相較于JSP和VRP問題，IPPDS不僅對資源和任務(wù)方面進行了拓展，更提高約束條件復(fù)雜性。如工藝約束不僅體現(xiàn)在生產(chǎn)環(huán)節(jié)加工任務(wù)在設(shè)備間的物流關(guān)系（式（5）），也體現(xiàn)為采購生產(chǎn)配送的整體物流關(guān)系（式（9）、（10））;資源獨占約束既體現(xiàn)在產(chǎn)品加工對設(shè)備資源的獨占性（式（5）），也體現(xiàn)為運輸任務(wù)對車輛資源的獨占性（式（11））;數(shù)量約束體現(xiàn)在訂單需求量對配送量（式（2））、配送量對生產(chǎn)量（式（4））、生產(chǎn)原料需求量對采購量（式（3））及資源量（式（8））的約束;時間約束既體現(xiàn)在加工環(huán)節(jié)（式（5），（6）），也體現(xiàn)在運輸環(huán)節(jié)（式（7）、（10）、（11））。

根據(jù)IPPDS問題特點，設(shè)計其求解思路是：1）基于資源任務(wù)匹配的權(quán)值矩陣（見3.1節(jié)）實現(xiàn)資源在任務(wù)間的配置，是求解問題的基礎(chǔ);2）基于工藝過程，依據(jù)權(quán)值矩陣，解碼出滿足約束條件的可行調(diào)度方案是求解問題的關(guān)鍵;3）利用改進的動態(tài)人工蜂群算法（DABC）實現(xiàn)高效、更優(yōu)的求解是求解方法可行的重要保證。

具體而言（如圖2所示），在求解IPPDS問題時，基于工藝過程，采用二維矩陣編碼方式實現(xiàn)資源與任務(wù)的匹配;通過解碼過程在滿足約束下選擇運輸任務(wù)的車輛，確定運輸次序，確定產(chǎn)品投產(chǎn)次序及各設(shè)備上加工次序，計算任務(wù)開始和結(jié)束時間;通過對人工蜂群算法中引領(lǐng)蜂與跟隨蜂協(xié)調(diào)機制和解碼過程的啟發(fā)式信息設(shè)計實現(xiàn)算法的高效、更優(yōu)求解。

3?改進的人工蜂群算法

為適應(yīng)IPPDS問題的求解特征，本文從算法編碼、解碼、初始權(quán)值的取值方式、啟發(fā)式信息和算法過程幾個方面對基本人工蜂群算法進行改進。下面分別對改進具體情況進行介紹。

3.1?編碼設(shè)計

為實現(xiàn)資源（車輛和設(shè)備）與任務(wù)（采購、加工和配送）的匹配關(guān)系，采用二維實數(shù)矩陣編碼方式。首先，將加工任務(wù)與運輸任務(wù)統(tǒng)一編碼（如式（12）所示），其中j表示原料編號，c表示工序編號，i表示成品編號; 再將資源統(tǒng)一編碼，其中k表示車輛編號，m表示設(shè)備編號;其次，矩陣中的實數(shù)元素值表示任務(wù)與資源對應(yīng)的優(yōu)先權(quán)值，權(quán)值元素所在的行對應(yīng)任務(wù)號，列對應(yīng)執(zhí)行任務(wù)的資源號;最后，通過比較權(quán)值的大小，并選擇權(quán)值最大者對應(yīng)的資源執(zhí)行相應(yīng)的任務(wù)，可以實現(xiàn)資源與任務(wù)的匹配順序。

Y=

Pe（1，1）Pe（1，2）…Pe（1，k）00…0

Pe（2，1）Pe（2，2）…Pe（2，k）00…0

Pe（j，1）Pe（j，2）…Pe（j，k）00…0

00…0Pe（i+1，k+1）Pe（i+1，k+2）…Pe（i+1，k+m）

00…0Pe（i+2，k+1）Pe（i+2，k+2）…Pe（i+2，k+m）

00…0Pe（i+c，k+1）Pe（i+c，k+2）…Pe（i+c，k+m）

Pe（j+c+1，1）Pe（j+c+1，2）…Pe（j+c+1，k）00…0

Pe（j+c+2，1）Pe（j+c+2，2）…Pe（j+c+2，k）00…0

Pe（j+c+i，1）Pe（j+c+i，2）…Pe（j+c+i，k）00…0

（12）

3.2?解碼過程

解碼過程依據(jù)資源與任務(wù)的優(yōu)先權(quán)值，在滿足約束的條件下，安排發(fā)車次序、產(chǎn)品投產(chǎn)次序和加工次序，并確定運輸?shù)拈_始時間tSkaz和結(jié)束時間tEkaz，確定各工序的開始加工時間tSicm及結(jié)束時間tEicm。輸入產(chǎn)品需求量qi，運輸時間tkz等相關(guān)參數(shù)，設(shè)當(dāng)前時刻t及前時刻t′為0，即t=t′=0，初始原料和產(chǎn)品庫存都為0，所有資源都為可用。進入如下解碼過程：

步驟1?更新任務(wù)和資源的狀態(tài)。

若車輛k被占用，且車輛的運輸結(jié)束時間tEkaz小于當(dāng)前時刻t，對車輛k進行卸載。若卸載的是原料j，記錄此次原料j的運輸量Qkaj，增加原料j被車輛k運輸?shù)拇螖?shù)vjk，以及此次原料入庫的時間tvjkj為tEkaz，并根據(jù)式（13）增加相應(yīng)原料庫存量Sj，車輛k變?yōu)榭捎?若卸載的是成品i，增加成品i被車輛k運輸?shù)拇螖?shù)vik，并根據(jù)式（14）更新已完成的訂單配送量hi，更新車輛k的狀態(tài)變?yōu)榭捎谩?/p>

Sj=Sj+Qkaj（13）

hi=hi+Qkai（14）

若設(shè)備m被占用且設(shè)備加工結(jié)束時間tEicm小于當(dāng)前時刻t，記錄設(shè)備m的工序Oic已經(jīng)完工，釋放加工設(shè)備m，更新其加工設(shè)備變?yōu)榭捎?若Oic是最后一道工序，由式（15）增加成品i的庫存量為Ri，并增加成品i被設(shè)備m加工的次數(shù)vim。

Ri=Ri+qi（15）

步驟2?構(gòu)建可調(diào)度任務(wù)集合Φ。

根據(jù)式（16）判斷原料j是否運輸完成：若沒有運輸完成，記錄原料j的運輸權(quán)值及運輸車輛k，將原料j放入可調(diào)度任務(wù)集合Φ; 否則，此任務(wù)不放入調(diào)度任務(wù)集合Φ。

∑Ii=1qi·uij-Lj≥0（16）

若原料j的當(dāng)前庫存量Sj能滿足尚未投產(chǎn)的產(chǎn)品i（即αi=0）首工序的投料需求，記錄成品i首工序的加工的權(quán)值及對原料j的需求量，將產(chǎn)品i首工序放入可調(diào)度任務(wù)集合Φ，否則，此任務(wù)不放入可調(diào)度任務(wù)集合Φ。

若非首工序Oic（c≠1）的緊前工序加工完成，記錄該工序Oic的加工權(quán)值，將其放入可調(diào)度任務(wù)集合Φ;否則，此任務(wù)不放入可調(diào)度任務(wù)集合Φ。

若成品i已入庫且根據(jù)式（17）判斷其未完成配送，記錄成品i被配送的權(quán)值，將其放入可調(diào)度任務(wù)集合Φ;否則，此任務(wù)不放入調(diào)度任務(wù)集合Φ。

qi-Li>0（17）

其中Lj、Li分別為原料j、成品i已安排的運輸量。

步驟3?若集合Φ為空，則執(zhí)行步驟5;否則從可調(diào)度任務(wù)集合Φ中選擇權(quán)值最大的調(diào)度任務(wù)執(zhí)行。

選擇的權(quán)值可分為以下幾種情況：若運輸原料的權(quán)值最大，選擇車輛k運輸原料j，根據(jù)式（11）和式（7）計算原料運輸?shù)拈_始時間、結(jié)束時間，根據(jù)式（18）確定原料j的運輸量，根據(jù)式（19）更新原料j的已安排運輸量Lj。

Qkaj=min{Vk，（∑Ii=1qi·uij-Lj）}（18）

Lj=Lj+Qkaj（19）

若成品i首工序的加工權(quán)值最大，安排此工序在設(shè)備m上加工（即αi=1），根據(jù)式（20）減少原料j的庫存量，根據(jù)式（21）和式（6）計算此工序的開始時間tSi1m及結(jié)束時間tEi1m。

Sj=Sj-qi·uij（20）

tSi1m=max{max{tvijj}， βi′im·tEi′cm}（21）

若非首工序Oic（c≠1）的加工權(quán)值最大，安排此工序在設(shè)備m上加工，根據(jù)式（5）和式（6）計算此工序的開始時間tSicm及結(jié)束時間tEicm，當(dāng)c=Ii時，記錄成品的入庫時間為tλi=tEiIim。

若配送成品i的權(quán)值最大，安排車輛k配送成品i，根據(jù)式（22）計算成品配送的開始時間，進一步根據(jù)式（8）計算成品配送的結(jié)束時間，根據(jù)式（23）確定成品i的運輸量，根據(jù)式（24）更新成品i的庫存量Ri。

tSkai=max{δz′zk·tEka′z′，tλi}（22）

Qkai=min{Vk， qi-Li}（23）

Ri=Ri-Qkai（24）

步驟4?令t′=t，將當(dāng)前時刻移動到被執(zhí)行任務(wù)中最早完成的時刻t，即t={tEka*z，tEic*m}，利用式（27）對權(quán)值進行更新，然后轉(zhuǎn)入步驟2。其中，a*，c*為t時刻已經(jīng)開始，但尚未完成的運輸和加工任務(wù)序號。

步驟5?若Φ為空，表示所有加工及運輸任務(wù)已經(jīng)完成，計算出調(diào)度任務(wù)的總時間，輸出調(diào)度方案。

上述基于工藝過程逐步生成可行調(diào)度方案過程中，重點針對1.2節(jié)中約束條件進行設(shè)計。其中除式（5）～（7）直接在解碼過程直接應(yīng)用外，其他公式為便于解碼過程操作進行了相應(yīng)的轉(zhuǎn)換。具體公式間對應(yīng)關(guān)系為：式（2）轉(zhuǎn)換為式（16）、（23），式（3）轉(zhuǎn)換為式（17）、（18），式（8）轉(zhuǎn)換為式（18）、（23），式（11）轉(zhuǎn)換為式（21）、（22），式（9）和（10）分別轉(zhuǎn)換為式（21）和（22）。另外，式（4）、（9）也在步驟2的物料選擇條件中進行實現(xiàn)。

3.3?初始權(quán)值的計算方式

為了使始初矩陣內(nèi)的權(quán)值之間能夠明顯差異化，在編碼時利用式（25）把（0，1）的隨機數(shù)轉(zhuǎn)化成一個（0，∞）的權(quán)值，以實現(xiàn)個體多樣性。

Pe（z，s）=ln（1+xzs）1-xzs（25）

其中xzs∈（0，1）。

3.4?啟發(fā)式信息的設(shè)計

為使求出的解空間更大，設(shè)計了對運輸及加工權(quán)值更新的啟發(fā)式信息，即任務(wù)被相應(yīng)資源執(zhí)行的次數(shù)。物料在被車輛k運輸一次或被設(shè)備m加工一次后，利用式（26）增加物料z被運輸或加工的次數(shù)vzs，同時根據(jù)式（27）更新一次優(yōu)先權(quán)值。

vzs=vzs+1（26）

Pe（z，s）=Pe（z，s）vzs+1（27）

3.5?算法步驟

算法運行前只需要設(shè)定唯一的參數(shù)是種群規(guī)模N，并令引領(lǐng)蜂規(guī)模Ne和跟隨蜂規(guī)模Nu均為N/2。將調(diào)度方案的目標(biāo)函數(shù)值f作為引領(lǐng)蜂和跟隨蜂的適應(yīng)值，通過算法進化得出f最小化的調(diào)度方案。初始時令f為任意最大值。之后進行以下過程：

步驟1?初始化引領(lǐng)蜂群。利用式（25）隨機生成Ne個權(quán)值Pe（z，s），作為引領(lǐng)蜂的初始位置，并解碼調(diào)度方案，根據(jù)式（1）計算目標(biāo)函數(shù)值作為引領(lǐng)蜂的適應(yīng)值fe。

步驟2?依據(jù)引領(lǐng)蜂適應(yīng)值，利用式（28）計算每只引領(lǐng)蜂分配的跟隨蜂數(shù)量Nue，

Nue=「（fe·Nu）/∑Nee=1fe（28）

步驟3?通過對應(yīng)的跟隨蜂種群尋優(yōu)，更新引領(lǐng)蜂。具體過程如下（e、u分別為引領(lǐng)蜂與跟隨蜂計數(shù)器，初值為0）：

3.1） 選定一只待更新的引領(lǐng)蜂xue。

3.2） 以引領(lǐng)蜂xue位置為指引，利用式（29）生成跟隨蜂xue位置，以使其在該引領(lǐng)蜂周圍搜索。

Pue（z，s）=Pe（z，s）·rnd（29）

其中rnd∈（0，1）。

3.3） 對跟隨蜂xue位置進行解碼，得出適應(yīng)值fu：若fu優(yōu)于引領(lǐng)蜂xe的適應(yīng)值fe，即fu

3.4） 若u=Nue，即引領(lǐng)蜂xe的跟隨蜂群全部搜索完成，轉(zhuǎn)入步驟3.5）;否則u=u+1，轉(zhuǎn)入步驟3.2）。

3.5） 若e=Ne，即引領(lǐng)蜂群全部更新完成，轉(zhuǎn)入步驟4;否則e=e+1，轉(zhuǎn)入步驟3.1）。

步驟4?將Ne只引領(lǐng)蜂按適應(yīng)值fe由小到大進行排序，得出最優(yōu)適應(yīng)值f′。

步驟5?比較最優(yōu)適應(yīng)值f′與全局最優(yōu)適應(yīng)值f。若f′≥f，將適應(yīng)值最差的引領(lǐng)蜂轉(zhuǎn)化為跟隨蜂，即Ne=Ne-1，且Nu=Nu+1。此時若Ne=1，則算法結(jié)束，并輸出最優(yōu)適應(yīng)值和最優(yōu)方案;若f′

上述算法過程中：一方面減少了參數(shù)設(shè)置，更便于應(yīng)用。另一方面，引領(lǐng)蜂與跟隨蜂既實現(xiàn)了各自分工（引領(lǐng)蜂在保留優(yōu)秀解的同時指引跟隨蜂搜索，而跟隨蜂以引領(lǐng)蜂為中心進行隨機搜索），又根據(jù)尋優(yōu)狀態(tài)進行角色轉(zhuǎn)換，更好進行全局和局部搜索。

4?應(yīng)用實例

4.1?IPPDS策略有效性分析

相較于IPPDS問題，對JSP和VPR的研究相當(dāng)于將采購、生產(chǎn)、配送環(huán)節(jié)分段調(diào)度，而在IPPDS策略中，將采購、生產(chǎn)、配送三者同時優(yōu)化，這樣可大幅縮短總調(diào)度時間。為說明IPPDS策略相較于分段調(diào)度策略的有效性，以運輸5種物料、加工6道工序為例進行說明。

某水果加工廠加工各種類型的水果，在期初接收到了3個客戶的訂單，客戶1需要20t的箱裝蘋果（z=1），客戶2需要15t的袋裝蘋果（z=2），客戶3需要20t的袋裝梨（z=3）。企業(yè)在接收客戶的這些訂單后，需要去果園采購35t的蘋果（z=6）以及20t的梨（z=7），每個訂單都需要經(jīng)過揀選和包裝兩道工序。物料的需求量及運輸時間如表1所示，所需用的車輛K1、K2相關(guān)信息如表2所示，3種訂單的加工信息如表3所示。

采用分段調(diào)度策略對問題進行求解，將調(diào)度結(jié)果以甘特圖的形式展現(xiàn)，如圖3所示。

在該分步調(diào)度的方案中，0到8.5時，是去果園采購水果的階段。待8.5時，所有水果采購結(jié)束，開始進行訂單的加工，加工形式采用作業(yè)車間調(diào)度的方式; 20.5時，所有訂單加工結(jié)束，開始進行訂單的配送; 29.5時，所有訂單配送結(jié)束，總的調(diào)度時間為29.5h。

為保證將新鮮的水果送到客戶手中，采用IPPDS策略對問題進行求解，為直觀表示，將調(diào)度結(jié)果用甘特圖表示，如圖4所示。

在IPPDS策略下，原料未運輸完成的情況下，就可以開始生產(chǎn)，加工未完成的情況下，就可以進行配送，實現(xiàn)了采購生產(chǎn)配送的同時調(diào)度。由圖4可知，相比分段調(diào)度策略，加工時間比分段調(diào)度策略提前了6h，配送時間提前了11.5h，總的調(diào)度時間縮短了35.59%，可以使客戶需求的訂單盡早地得到配送。

為了進一步證明IPPDS策略相較于IPDS策略的有效性，在上述例子的基礎(chǔ)上，增加2個客戶的需求，客戶4需要15t的箱裝橙子（z=4），客戶5需要15t的袋裝橙子（z=5），企業(yè)在接收客戶訂單后，需要去果園采購30t的橙子（z=8），并且需要增加運輸車輛K3，新增訂單同樣需要進行揀選和包裝兩道工序。新增物料的需求量及運輸時間如表1所示，新增車輛K3信息如表2所示，新增2種產(chǎn)品的加工信息如表3所示。

采用IPDS策略對該問題進行求解，將調(diào)度結(jié)果以甘特圖的形式展現(xiàn)，如圖5所示。

在該IPDS策略下，0到8.5時為去果園采購水果的階段;待8.5時，所有水果采購結(jié)束，開始進行產(chǎn)品加工，采用作業(yè)車間調(diào)度方式，在產(chǎn)品加工過程中，對已加工完成的部分產(chǎn)品進行配送，實現(xiàn)生產(chǎn)配送的聯(lián)合調(diào)度，在14.5時開始進行配送，27.5時，所有訂單配送完成，總的調(diào)度時間為27.5h。

為保證將新鮮的水果在更短時間內(nèi)送到客戶手中，采用IPPDS策略對問題進行求解，為直觀表示，將調(diào)度結(jié)果用甘特圖表示，如圖6所示。

由圖6可知，相比IPDS策略，在IPPDS策略下，加工時間比IPDS策略提前了6h，配送時間提前了6.5h，總調(diào)度時間為21h，比IPDS策略縮短了30.95%，即6.5h，可以使客戶訂單更早地得到配送。若在增大物料需求量的情況下，將采購、生產(chǎn)、配送三個環(huán)節(jié)同時進行調(diào)度效果更顯著。

4.2?DABC算法主要參數(shù)的確定

在DABC中，唯一需要確定的參數(shù)是種群規(guī)模N。為確定合適種群規(guī)模N，以原料j（j=1，2）、成品i（i=1，2，3）為例，其中原料J1可加工成品I1、I2，

原料J2可加工成品I3（各物料需求量及運輸時間詳見表4，所用車輛詳見表5，成品的加工信息詳見表6）。在不同種群規(guī)模下，即N取20，40，60，…，500不同的值，對DABC運行效果進行測試。每組實驗運行10次后，取實驗結(jié)果的平均值，并繪制出伴隨著種群規(guī)模變化的最優(yōu)結(jié)果平均值的變化趨勢、優(yōu)值方差的變化趨勢及算法運行時間圖，如圖7～9所示，圖7中的縱坐標(biāo)反映了算法的優(yōu)化結(jié)果;圖9中的縱坐標(biāo)表示運行的時間。

由圖7可見，N=250時，DABC求解的優(yōu)值曲線下降速率出現(xiàn)拐點;由圖8可見，N=240時，優(yōu)值的方差變化曲線出現(xiàn)拐點;由圖9可見，N=260時，算法的運行時間曲線出現(xiàn)拐點。因此建議N在240～260取值。

4.3?算法有效性驗證

劉玲等[4]用遺傳算法求解了單機器生產(chǎn)下多車輛運輸協(xié)同調(diào)度問題，本文考慮了作業(yè)車間情形下多車輛運輸協(xié)同調(diào)度問題。文獻[4]中考慮多車輛情況與本文考慮的多車輛情況類似，都是用多車輛運輸多種物料，只是文獻[4]中一輛車可以運輸多個客戶的訂單到客戶處，而本文問題是多輛車既運輸原料又運輸成品。正是由于兩者的相似性，利用文獻[4]中改進的遺傳算法（Adapted Genetic Algorithm， AGA）對

本文問題進行求解。

為進一步驗證DABC的優(yōu)越性，再次利用基本的人工蜂群（ABC）算法對本文問題進行求解，即將DABC與ABC、AGA兩種算法對比，測試數(shù)據(jù)分為小、中、大三種規(guī)模并隨機產(chǎn)生，物料種類由5種增加到12種，調(diào)度任務(wù)總數(shù)由11種增加到30種。設(shè)定三種算法的種群規(guī)模均為N=260， ABC的引領(lǐng)蜂的局部尋優(yōu)次數(shù)為20，循環(huán)次數(shù)為100，AGA的交叉概率pc=0.8，變異概率pm=0.1，循環(huán)次數(shù)為100。每種算法運行10次，比較三種算法運行的結(jié)果（見表7）。Z1、Z2、Z3列分別表示ABC、AGA、DABC運行10次的平均值。GP1表示ABC與DABC之間的差值比，計算方式為GP1=（Z1-Z3）/Z1*100%。同理，GP2表示AGA與DABC之間的差值比，計算方式為GP2=（Z2-Z3）/Z2*100%。如果兩個比值是正數(shù)，說明DABC優(yōu)于ABC及AGA。

從表7可以看出，10個測例的平均差值比分別為2.54%、6.999%，說明DABC運行出的優(yōu)值要優(yōu)于ABC及AGA;DABC有較優(yōu)的方差，且都小于ABC及AGA的方差，說明DABC運行結(jié)果比較穩(wěn)定。總體來看，DABC要優(yōu)于ABC及AGA。

通過比較可見DABC表現(xiàn)出更好的求解能力和求解穩(wěn)定性。究其原因主要有：1）調(diào)度問題是一類解空間離散的組合優(yōu)化問題，采用鄰域搜索的方式也很難得到問題最優(yōu)解，因為最優(yōu)值相同或相近的兩個個體，編碼值差別會很大，因此DABC中一方面引領(lǐng)蜂對優(yōu)秀個體進行保留，另一方法跟隨蜂在引領(lǐng)蜂周圍形成針對性的差異個體，提高了算法的探索-開發(fā)能力;2）采用的二維實數(shù)的編碼方式，有利于個體的進化計算，降低了算法實現(xiàn)和計算的復(fù)雜度，提高了算法運行效率;3）啟發(fā)式信息的設(shè)計也提高DABC搜索效果。下面就啟發(fā)式信息對算法求解效果影響進行分析。

4.4?啟發(fā)式信息有效性分析

為驗證啟發(fā)式信息的有效性，隨機生成5組測例，每組測例運行10次，并取結(jié)果平均值，比較去掉啟發(fā)式信息后的DABC（DABC0）與DABC的運行結(jié)果，種群規(guī)模均為N=260。運行結(jié)果詳見表8，其中Z4，Z5分別表示DABC0與DABC運行10次結(jié)果的平均值;GP3表示DABC與DABC0之間的差值比，計算方式為GP3=（Z4-Z5）/Z4*100%，如果該比值為正數(shù)，說明DABC要優(yōu)于DABC0。

從表8中可以看出，5個測例的平均差值比為15.008%，說明DABC的運行結(jié)果要優(yōu)于DABC0，說明了啟發(fā)式信息的有效性。其原因在于：物料每被運輸或加工一次，物料與其運輸車輛或加工設(shè)備組合的權(quán)值被更新一次，避免每次選擇車輛或設(shè)備時，只選擇某輛車或某臺設(shè)備，增加了解的多樣性。

表格（有表名）

5?結(jié)語

本文的IPPDS問題在考慮作業(yè)車間生產(chǎn)環(huán)境下，將采購生產(chǎn)配送進行聯(lián)合調(diào)度，是對IPDS問題的拓展和完善。DABC既減少了參數(shù)設(shè)置更便于應(yīng)用，又表現(xiàn)出良好的求解效果。具體而言，本文的研究表明：

1）相對于分階段的調(diào)度策略和IPDS策略，IPPDS策略可以大幅縮短了采購、生產(chǎn)、配送三個環(huán)節(jié)的總調(diào)度時間。

2）通過測例分析，改進的人工蜂群算法在使參數(shù)設(shè)置更簡單的同時，還使算法求解效果有更穩(wěn)定的參數(shù)設(shè)置區(qū)間。

3）通過對比分析，針對引領(lǐng)蜂跟隨蜂協(xié)調(diào)機制和啟發(fā)式信息而改進的DABC，對IPPDS問題求解表現(xiàn)出較好的求解效果，具有良好的探索開發(fā)能力。

IPPDS問題的解決，首先，從客戶角度，降低訂單的交貨期使客戶的需求及時得到滿足，可增強企業(yè)的信譽度。其次，對于企業(yè)角度，高效地對客戶的個性化需求進行采購、加工及配送，可降低企業(yè)運營成本，提高企業(yè)的競爭力。

參考文獻 （References）

[1]WANG D， GRUNDER O， EL MOUDNI A. Integrated scheduling of production and distribution operations： a review[J]. International Journal of Industrial & Systems Engineering， 2015， 19（1）： 94-122.

[2]李凱，周超，馬英. 考慮釋放時間的單機JIT調(diào)度問題[J]. 運籌與管理， 2016， 25（3）： 71-77. （LI K， ZHOU C， MA Y. Single machine JIT scheduling problem considering release time[J]. Operation Research and Management Science， 2016， 25（3）： 71-77.）

[3]VIERGUTZ C， KNUST S. Integrated production and distribution scheduling with lifespan constraints[J]. Annals of Operations Research， 2014， 213（1）：293-318.

[4]劉玲，李昆鵬，劉志學(xué). 生產(chǎn)和運輸協(xié)同調(diào)度問題的模型和算法[J]. 工業(yè)工程與管理， 2016， 21（2）： 86-91. （LIU L， LI K P， LIU Z X. Model and algorithm of production and transportation collaborative scheduling problem [J]. Industrial Engineering and Management， 2016， 21（2）： 86-91.）

[5]LI K， ZHOU C， LEUNG J Y T， et al. Integrated production and delivery with single machine and multiple vehicles[J]. Expert Systems with Applications， 2016， 57： 12-20.

[6]JOO C M， KIM B S. Rulebased metaheuristics for integrated scheduling of unrelated parallel machines， batches， and heterogeneous delivery trucks[J]. Applied Soft Computing， 2017， 53： 457-476.

[7]JIANG L， PEI J， LIU X， et al. Uniform parallel batch machines scheduling considering transportation using a hybrid DPSOGA algorithm[J]. The International Journal of Advanced Manufacturing Technology， 2017， 89（5/6/7/8）： 1887-1900.

[8]TAXAKIS K， PAPADOPOULOS C. A design model and a productiondistribution and inventory planning model in multiproduct supply chain networks[J]. International Journal of Production Research， 2016， 54（21）： 6436-6457.

[9]JAMILI N， RANJBAR M， SALARI M. A biobjective model for integrated scheduling of production and distribution in a supply chain with order release date restrictions[J]. Journal of Manufacturing Systems， 2016， 40： 105-118.

[10]吳瑤，馬祖軍，鄭斌. 有新鮮度限制的易腐品生產(chǎn)配送協(xié)同調(diào)度[J]. 計算機應(yīng)用， 2018， 38（4）： 1181-1188. （WU Y， MA Z J， ZHENG B. Integrated scheduling of production and distribution for perishable products with freshness limitations[J]. Journal of Computer Applications， 2018， 38（4）： 1181-1188.）

[11]KERGOSIEN Y， GENDREAU M， BILLAUT J C. A Benders decompositionbased heuristic for a production and outbound distribution scheduling problem with strict delivery constraints[J]. European Journal of Operational Research， 2017， 262（1）： 287-298.

[12]ENSAFIAN H， YAGHOUBI S. Robust optimization model for integrated procurement， production and distribution in platelet supply chain[J]. Transportation Research Part E： Logistics & Transportation Review， 2017， 103：32-55.

[13]FU L， ALOULOU M A， TRIKI C. Integrated production scheduling and vehicle routing problem with job splitting and delivery time windows[J]. International Journal of Production Research， 2017，55（20）：5942-5957.

[14]KARAOGLAN I， KESEN S E. The coordinated production and transportation scheduling problem with a timesensitive product： a branchandcut algorithm[J]. International Journal of Production Research， 2016， 55（2）：536-557.

[15]程八一，李明. 面向生產(chǎn)庫存配送的聯(lián)合調(diào)度問題及蟻群優(yōu)化算法[J]. 機械工程學(xué)報， 2015， 51（12）： 202-212. （CHENG B Y， LI M. Ant colony optimization for joint scheduling of production， inventory and distribution[J]. Journal of Mechanical Engineering， 2015， 51（12）： 202-212.）

[16]馬雪麗，王淑云，劉曉冰，等. 易腐食品二級供應(yīng)鏈生產(chǎn)調(diào)度與配送路線的協(xié)同優(yōu)化[J]. 工業(yè)工程與管理， 2017， 22（2）： 46-52. （MA X L， WANG S Y， LIU X B， et al. Integrated optimization of production scheduling and distribution for perishable food products in twoechelon supply chain[J]. Industrial Engineering and Management， 2017， 22（2）： 46-52.）

[17]DEVAPRIYA P， FERRELL W， GEISMAR N. Integrated production and distribution scheduling with a perishable product[J]. European Journal of Operational Research， 2017， 259（3）：906-916.

[18]PAN Q， WANG L， LI J， et al. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation[J]. Omega， 2014， 45：42-56.

This work is partially supported by the National Social Science Foundation of China （17BGL087）， the Project of Natural Science Youth Foundation of Colleges and Universities in Hebei Province （2011125）.

ZHANG Weicun， born in 1975， Ph. D.， associate professor. His research interests include intelligent optimization， industrial engineering.

GAO Rui， born in 1994， M. S. candidate. Her research interests include logistics and supply chain management.

ZHANG Man， born in 1993， M. S. candidate. Her research interests include logistics and supply chain management.