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

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

中圖分類號：TP301.6

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

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

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

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

1.1?問題描述

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

假設(shè)條件：1）原料和成品庫存量期初為0，且產(chǎn)能和庫存量無限;2）車輛型號、數(shù)量是確定的;3）生產(chǎn)準(zhǔn)備時(shí)間、成品裝卸時(shí)間忽略不計(jì);4）從0時(shí)刻開始運(yùn)輸物料;5）忽略運(yùn)輸時(shí)的交通狀態(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運(yùn)輸物料z的往返時(shí)間;ticm為產(chǎn)品i第c道工序在設(shè)備m上的加工時(shí)間;Vk為車輛k的容量。

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

決策變量?α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運(yùn)輸物料z′緊前于物料z，則其值為1，否則為0。ηkaz為若安排車輛k在第a次運(yùn)輸物料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ù)，表示所有訂單配送完成時(shí)間最大值的最小化;式（2）表示對成品i的配送量等于其訂單需求量;式（3）表示原料j的運(yùn)輸總量等于產(chǎn)品投產(chǎn)對該原料的需求量之和;式（4）表示所有的成品需求均進(jìn)行的投產(chǎn);式（5）表示工序開工時(shí)間取其上序完工時(shí)間和本工序設(shè)備上緊前工序完工時(shí)間中兩者的最大值;式（6）、（7）表示加工和運(yùn)輸任務(wù)的結(jié)束時(shí)間等于其開始時(shí)間加上任務(wù)執(zhí)行時(shí)間，也表示任務(wù)執(zhí)行過程不能中斷;式（8）表示第a次運(yùn)輸量不大于該車容量;式（9）表示在產(chǎn)品i投產(chǎn)時(shí)，原料j的累計(jì)運(yùn)輸量大于投產(chǎn)i對其需求量，即原料不能缺貨或斷流;式（10）表示成品i配送開始時(shí)間不早于其產(chǎn)出時(shí)間：式（11）表示車輛k的第a次運(yùn)輸開始時(shí)間不能早于其緊前運(yùn)輸任務(wù)的結(jié)束時(shí)間。

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í)行時(shí)刻未知;2）不同于VRP問題中的車輛資源是已知和確定的，IPPDS問題中采購和配送環(huán)節(jié)的車輛可用性均受對方調(diào)度結(jié)果影響，因而車輛的可用性是未知和變化的。所以，IPPDS問題的復(fù)雜性高于JSP和VRP，也強(qiáng)于將采購、生產(chǎn)、配送問題進(jìn)行兩兩聯(lián)合調(diào)度的問題。

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

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

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

3?改進(jìn)的人工蜂群算法

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

3.1?編碼設(shè)計(jì)

為實(shí)現(xiàn)資源（車輛和設(shè)備）與任務(wù)（采購、加工和配送）的匹配關(guān)系，采用二維實(shí)數(shù)矩陣編碼方式。首先，將加工任務(wù)與運(yùn)輸任務(wù)統(tǒng)一編碼（如式（12）所示），其中j表示原料編號，c表示工序編號，i表示成品編號; 再將資源統(tǒng)一編碼，其中k表示車輛編號，m表示設(shè)備編號;其次，矩陣中的實(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ù)，可以實(shí)現(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)次序和加工次序，并確定運(yùn)輸?shù)拈_始時(shí)間tSkaz和結(jié)束時(shí)間tEkaz，確定各工序的開始加工時(shí)間tSicm及結(jié)束時(shí)間tEicm。輸入產(chǎn)品需求量qi，運(yùn)輸時(shí)間tkz等相關(guān)參數(shù)，設(shè)當(dāng)前時(shí)刻t及前時(shí)刻t′為0，即t=t′=0，初始原料和產(chǎn)品庫存都為0，所有資源都為可用。進(jìn)入如下解碼過程：

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

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

Sj=Sj+Qkaj（13）

hi=hi+Qkai（14）

若設(shè)備m被占用且設(shè)備加工結(jié)束時(shí)間tEicm小于當(dāng)前時(shí)刻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是否運(yùn)輸完成：若沒有運(yùn)輸完成，記錄原料j的運(yùn)輸權(quán)值及運(yù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已安排的運(yùn)輸量。

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

選擇的權(quán)值可分為以下幾種情況：若運(yùn)輸原料的權(quán)值最大，選擇車輛k運(yùn)輸原料j，根據(jù)式（11）和式（7）計(jì)算原料運(yùn)輸?shù)拈_始時(shí)間、結(jié)束時(shí)間，根據(jù)式（18）確定原料j的運(yùn)輸量，根據(jù)式（19）更新原料j的已安排運(yùn)輸量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）計(jì)算此工序的開始時(shí)間tSi1m及結(jié)束時(shí)間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）計(jì)算此工序的開始時(shí)間tSicm及結(jié)束時(shí)間tEicm，當(dāng)c=Ii時(shí)，記錄成品的入庫時(shí)間為tλi=tEiIim。

若配送成品i的權(quán)值最大，安排車輛k配送成品i，根據(jù)式（22）計(jì)算成品配送的開始時(shí)間，進(jìn)一步根據(jù)式（8）計(jì)算成品配送的結(jié)束時(shí)間，根據(jù)式（23）確定成品i的運(yùn)輸量，根據(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)前時(shí)刻移動(dòng)到被執(zhí)行任務(wù)中最早完成的時(shí)刻t，即t={tEka*z，tEic*m}，利用式（27）對權(quán)值進(jìn)行更新，然后轉(zhuǎn)入步驟2。其中，a*，c*為t時(shí)刻已經(jīng)開始，但尚未完成的運(yùn)輸和加工任務(wù)序號。

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

上述基于工藝過程逐步生成可行調(diào)度方案過程中，重點(diǎn)針對1.2節(jié)中約束條件進(jìn)行設(shè)計(jì)。其中除式（5）～（7）直接在解碼過程直接應(yīng)用外，其他公式為便于解碼過程操作進(jìn)行了相應(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的物料選擇條件中進(jìn)行實(shí)現(xiàn)。

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

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

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

其中xzs∈（0，1）。

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

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

vzs=vzs+1（26）

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

3.5?算法步驟

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

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

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

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

步驟3?通過對應(yīng)的跟隨蜂種群尋優(yōu)，更新引領(lǐng)蜂。具體過程如下（e、u分別為引領(lǐng)蜂與跟隨蜂計(jì)數(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位置進(jìn)行解碼，得出適應(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由小到大進(jìn)行排序，得出最優(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。此時(shí)若Ne=1，則算法結(jié)束，并輸出最優(yōu)適應(yīng)值和最優(yōu)方案;若f′

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

4?應(yīng)用實(shí)例

4.1?IPPDS策略有效性分析

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

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

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

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

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

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

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

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

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

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

由圖6可知，相比IPDS策略，在IPPDS策略下，加工時(shí)間比IPDS策略提前了6h，配送時(shí)間提前了6.5h，總調(diào)度時(shí)間為21h，比IPDS策略縮短了30.95%，即6.5h，可以使客戶訂單更早地得到配送。若在增大物料需求量的情況下，將采購、生產(chǎn)、配送三個(gè)環(huán)節(jié)同時(shí)進(jìn)行調(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（各物料需求量及運(yùn)輸時(shí)間詳見表4，所用車輛詳見表5，成品的加工信息詳見表6）。在不同種群規(guī)模下，即N取20，40，60，…，500不同的值，對DABC運(yùn)行效果進(jìn)行測試。每組實(shí)驗(yàn)運(yùn)行10次后，取實(shí)驗(yàn)結(jié)果的平均值，并繪制出伴隨著種群規(guī)模變化的最優(yōu)結(jié)果平均值的變化趨勢、優(yōu)值方差的變化趨勢及算法運(yùn)行時(shí)間圖，如圖7～9所示，圖7中的縱坐標(biāo)反映了算法的優(yōu)化結(jié)果;圖9中的縱坐標(biāo)表示運(yùn)行的時(shí)間。

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

4.3?算法有效性驗(yàn)證

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

本文問題進(jìn)行求解。

為進(jìn)一步驗(yàn)證DABC的優(yōu)越性，再次利用基本的人工蜂群（ABC）算法對本文問題進(jìn)行求解，即將DABC與ABC、AGA兩種算法對比，測試數(shù)據(jù)分為小、中、大三種規(guī)模并隨機(jī)產(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。每種算法運(yùn)行10次，比較三種算法運(yùn)行的結(jié)果（見表7）。Z1、Z2、Z3列分別表示ABC、AGA、DABC運(yùn)行10次的平均值。GP1表示ABC與DABC之間的差值比，計(jì)算方式為GP1=（Z1-Z3）/Z1*100%。同理，GP2表示AGA與DABC之間的差值比，計(jì)算方式為GP2=（Z2-Z3）/Z2*100%。如果兩個(gè)比值是正數(shù)，說明DABC優(yōu)于ABC及AGA。

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

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

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

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

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

表格（有表名）

5?結(jié)語

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

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

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

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

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

參考文獻(xiàn) （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]李凱，周超，馬英. 考慮釋放時(shí)間的單機(jī)JIT調(diào)度問題[J]. 運(yùn)籌與管理， 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)和運(yù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]. 計(jì)算機(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]. 機(jī)械工程學(xué)報(bào)， 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.