個(gè)性化定制車(chē)間生產(chǎn)與物流協(xié)同調(diào)度研究

葛艷紅,李書(shū)珍,李文鋒

(武漢理工大學(xué) 交通與物流工程學(xué)院,湖北 武漢 430063)

個(gè)性化定制作為新一代智能制造模式下企業(yè)的重要轉(zhuǎn)型方向[1],與傳統(tǒng)的離散制造模式相比,由于客戶(hù)訂單產(chǎn)生時(shí)間的不確定性及種類(lèi)的多樣性,對(duì)車(chē)間內(nèi)調(diào)度方案的及時(shí)性與有效性提出更高要求。

現(xiàn)有離散車(chē)間調(diào)度方案主要分為3種:預(yù)反應(yīng)式調(diào)度、前攝性調(diào)度與完全反應(yīng)式調(diào)度。完全反應(yīng)式調(diào)度又分為生產(chǎn)資源控制(Machine control,MC)型與物流資源控制(Vehicle control,VC)型。個(gè)性化定制車(chē)間場(chǎng)景動(dòng)態(tài)變化,前2種調(diào)度模式很難滿(mǎn)足個(gè)性化定制對(duì)生產(chǎn)組織及時(shí)性與靈活性的需求,因此現(xiàn)有研究大多針對(duì)完全反應(yīng)式調(diào)度展開(kāi),即將車(chē)間內(nèi)加工單元、自動(dòng)導(dǎo)引運(yùn)輸車(chē)(Automated guided vehicle,AGV)等設(shè)備模擬成獨(dú)立的智能體,基于智能設(shè)備所具有的感知、交互、分析、決策以及執(zhí)行能力,自組織完成訂單加工過(guò)程。例如,Wang等[2]將討價(jià)還價(jià)博弈理論應(yīng)用于各智能體之間的協(xié)商機(jī)制中;朱云飛等[3]、劉科等[4]、胡曉輝等[5]從不同的角度對(duì)合同網(wǎng)機(jī)制進(jìn)行改進(jìn),簡(jiǎn)化了任務(wù)分配流程;陳鳴等[6]在合同網(wǎng)基礎(chǔ)上,引入智能體過(guò)濾機(jī)制,提升系統(tǒng)的動(dòng)態(tài)調(diào)度效果;Zhang等[7]基于博弈理論搭建了云制造模式下的智能體調(diào)度框架;Qu等[8]在同時(shí)考慮云制造與物聯(lián)網(wǎng)的特征下,改變?nèi)蝿?wù)觸發(fā)方式,創(chuàng)新提出基于生產(chǎn)與物流協(xié)同的動(dòng)態(tài)調(diào)度方法。縱觀現(xiàn)有生產(chǎn)與物流協(xié)同調(diào)度的研究文獻(xiàn)發(fā)現(xiàn):現(xiàn)有完全反應(yīng)式調(diào)度研究主要集中于智能體之間通信機(jī)制的研究上,對(duì)基于智能體局部信息感知能力的優(yōu)化車(chē)間調(diào)度方案的研究較少;物流對(duì)象大多為單載量AGV,忽略了多載量AGV較強(qiáng)的任務(wù)執(zhí)行能力對(duì)調(diào)度方案的影響。徐云琴等[9]基于車(chē)間AGV的邊際效應(yīng)進(jìn)行研究,發(fā)現(xiàn)AGV數(shù)量在一定程度上影響調(diào)度方案的整體作用效果。為進(jìn)一步研究車(chē)間內(nèi)物流運(yùn)輸能力對(duì)調(diào)度方案的有效性影響,本文采用多載量AGV,針對(duì)當(dāng)前個(gè)性化定制車(chē)間中完全反應(yīng)式調(diào)度模式難以保證訂單交貨期的問(wèn)題,基于車(chē)間內(nèi)生產(chǎn)、物流過(guò)程協(xié)同,提出一種新的訂單排產(chǎn)方案,同時(shí)搭建基于多載量AGV特性的代價(jià)評(píng)估機(jī)制,采用改進(jìn)的粒子群編碼算法進(jìn)行求解。對(duì)本文方案與已有的2種完全反應(yīng)式方案在交貨期控制、加工單元利用率、車(chē)間功率等方面進(jìn)行比較分析,以期提升訂單交貨期的可控性與實(shí)現(xiàn)車(chē)間資源優(yōu)化利用。

1 基于生產(chǎn)與物流協(xié)同的訂單排產(chǎn)方案

1.1 排產(chǎn)方案調(diào)度指標(biāo)

(1)訂單交貨期。企業(yè)對(duì)交貨期的準(zhǔn)確預(yù)測(cè)與按時(shí)交付是企業(yè)信譽(yù)的關(guān)鍵,延期將造成客戶(hù)流失、經(jīng)濟(jì)損失等無(wú)法逆轉(zhuǎn)的負(fù)面影響。同時(shí),若訂單提前加工完成,需將產(chǎn)品放至庫(kù)存區(qū),占用車(chē)間庫(kù)存資源。因此企業(yè)無(wú)論采用何種調(diào)度方法,均應(yīng)最大程度保證產(chǎn)品的交貨期,同時(shí)對(duì)在制品的加工進(jìn)度進(jìn)行嚴(yán)格控制,減少產(chǎn)品的庫(kù)存時(shí)間。根據(jù)文獻(xiàn)[10]對(duì)訂單交貨期的研究,采用訂單提前/拖期指標(biāo)評(píng)估訂單的排產(chǎn)方案效果

(1)

(2)資源配置效果。從企業(yè)資源和效益角度考慮,個(gè)性化定制模式的關(guān)鍵在于提高車(chē)間資源利用率,降低單個(gè)產(chǎn)品的分?jǐn)偝杀?。加工單元的利用率指?biāo)

(2)

(3)車(chē)間功率。功率是調(diào)度方案效果綜合評(píng)估指標(biāo)。產(chǎn)品加工過(guò)程中,智能體速度與功率之間具有一定的相關(guān)性。功率包括車(chē)間內(nèi)所有加工單元與AGV的總功率

(3)

1.2 排產(chǎn)方案具體流程

個(gè)性化訂單產(chǎn)生后,按照產(chǎn)品工序間的連續(xù)性,采用“插空”的調(diào)度思想,盡可能在已有加工任務(wù)基礎(chǔ)上,最大化利用加工單元的空閑時(shí)間,提高設(shè)備利用率。新調(diào)度方案具有如下特點(diǎn):

(1)當(dāng)系統(tǒng)中存在多個(gè)處于未加工狀態(tài)的訂單時(shí),根據(jù)調(diào)度指標(biāo),對(duì)比訂單的執(zhí)行代價(jià),選擇最優(yōu)訂單插入,且每次只插入1個(gè)訂單;

(2)訂單實(shí)際插入的時(shí)間為協(xié)同制造鏈?zhǔn)讉€(gè)加工單元的當(dāng)前任務(wù)結(jié)束時(shí)刻,在該時(shí)刻之前,按照調(diào)度指標(biāo),智能體對(duì)該時(shí)刻所有可插入訂單進(jìn)行評(píng)估,產(chǎn)生最優(yōu)的訂單并插入;

(3)計(jì)算訂單的執(zhí)行代價(jià)時(shí),考慮插入該產(chǎn)品的所有工序后系統(tǒng)增加的代價(jià);

(4)新訂單的調(diào)度方案基于各智能體間協(xié)同交互、自主決策形成。訂單排產(chǎn)上,領(lǐng)導(dǎo)者(Leader)負(fù)責(zé)與其它各智能體交互,完成生產(chǎn)與物流協(xié)同調(diào)度方案的制訂。訂單產(chǎn)線(xiàn)中Leader的選擇采用

(4)

式中:CPfree(j)代表加工單元剩余的計(jì)算資源;CPmax代表加工單元總計(jì)算資源。

與計(jì)算機(jī)中資源占用情況類(lèi)似,加工單元的資源使用情況為加工單元實(shí)時(shí)狀態(tài)統(tǒng)計(jì)數(shù)值,選擇剩余計(jì)算資源最多的加工單元為該訂單產(chǎn)線(xiàn)Leader。產(chǎn)線(xiàn)Leader是生產(chǎn)、物流系統(tǒng)交互協(xié)同的紐帶,負(fù)責(zé)協(xié)調(diào)生產(chǎn)模塊與物流模塊。

圖1 新訂單產(chǎn)生后智能體的交互流程圖

圖2 加工單元新任務(wù)插入方法示意圖

2 多載量AGV代價(jià)評(píng)估機(jī)制

本文提出的個(gè)性化訂單的排產(chǎn)框架中,制訂每道工序加工計(jì)劃時(shí)均需考慮物流模塊反饋結(jié)果,物流系統(tǒng)的效率對(duì)訂單加工進(jìn)度產(chǎn)生直接影響,物流調(diào)度系統(tǒng)研究至關(guān)重要。

2.1 AGV自適應(yīng)評(píng)估模型

為實(shí)現(xiàn)AGV資源的合理配置,當(dāng)物流任務(wù)產(chǎn)生時(shí),采用合理的代價(jià)評(píng)估機(jī)制,選擇代價(jià)最小的AGV來(lái)執(zhí)行此任務(wù)。研究中做如下假設(shè):

(1)在AGV容量約束允許的范圍內(nèi),AGV同時(shí)可執(zhí)行多個(gè)物流任務(wù);

(2)不考慮在制品裝載、卸載過(guò)程,裝載、卸載時(shí)間合并到在制品在加工單元間的運(yùn)輸時(shí)間中;

(3)每輛AGV具有自己的運(yùn)輸任務(wù)隊(duì)列;

(4)初始狀態(tài)下,AGV可能存在正在執(zhí)行的物流任務(wù),初始位置不固定;

(5)不考慮AGV的路徑?jīng)_突與電量約束。

函數(shù)定義見(jiàn)式(5)～式(17),符號(hào)定義見(jiàn)表1。目標(biāo)函數(shù)

F=mintd

(5)

(6)

(7)

(8)

(9)

(10)

xi,jti+ti,j-tj≤0 (i,j)∈R

(11)

(12)

cj≤tj≤bjj∈N

(13)

ti?tn+ii∈{P∪D′}

(14)

xi,j(Qi+qi-Qj)=0 (i,j)∈R

(15)

Qi≤Qi∈N

(16)

(17)

式(5)為本次調(diào)度目標(biāo),希望物流任務(wù)完成時(shí)間最小;式(6)、式(7)定義多物流網(wǎng)絡(luò)結(jié)構(gòu);式(8)表示各端點(diǎn)的出度等于入度;式(9)定義每個(gè)物流任務(wù)只能被執(zhí)行1次;式(10)定義同一任務(wù)裝載和交付為同一個(gè)AGV。式(11)～(14)定義任務(wù)時(shí)間約束,表示根據(jù)AGV已有任務(wù)的加工作業(yè)時(shí)間安排,AGV訪問(wèn)每個(gè)任務(wù)節(jié)點(diǎn)的時(shí)間必須在時(shí)間窗[bi,ci]內(nèi),以保證調(diào)度的正常執(zhí)行。對(duì)于等待執(zhí)行的物流任務(wù),AGV負(fù)責(zé)完成同一任務(wù)的裝載、卸載過(guò)程,裝載任務(wù)節(jié)點(diǎn)的訪問(wèn)時(shí)間在卸載任務(wù)節(jié)點(diǎn)時(shí)間之前。式(15)～(17)定義AGV負(fù)載約束,考慮AGV自身負(fù)載約束,AGV運(yùn)行負(fù)載不能超過(guò)其額定最大負(fù)載。

表1 AGV調(diào)度算法符號(hào)定義表

2.2 AGV自適應(yīng)評(píng)估方法

多載量AGV調(diào)度的復(fù)雜性與車(chē)間場(chǎng)景的動(dòng)態(tài)性,對(duì)算法求解速度與精度都提出了較高要求。對(duì)AGV現(xiàn)有調(diào)度算法進(jìn)行分析比較,考慮粒子群算法較快的計(jì)算速度與較強(qiáng)的適應(yīng)能力,符合AGV調(diào)度求解需求,因此選用粒子群算法作為多載量AGV自適應(yīng)調(diào)度方案的求解方法。粒子在迭代過(guò)程中根據(jù)粒子個(gè)體極值與群體極值進(jìn)行自身位置、速度的變更。更新過(guò)程中的速度、位置變化規(guī)律如下

(18)

(19)

2.2.1 編碼與解碼

假設(shè)AGV有n個(gè)等待執(zhí)行的物流任務(wù),其裝載點(diǎn)的集合為P={1,2,…,n},卸載點(diǎn)的任務(wù)集合為D′={n+1,n+2,…,2n}。對(duì)于第i個(gè)等待運(yùn)輸?shù)奈锪魅蝿?wù),i表示AGV執(zhí)行該任務(wù)裝載操作時(shí)的任務(wù)編號(hào),其中i∈P,n+i表示AGV執(zhí)行該任務(wù)的裝載卸載的任務(wù)編號(hào),(n+i)∈D′,即i和n+i共同表示同一任務(wù)的裝載、卸載過(guò)程。n和2n代表當(dāng)前新產(chǎn)生的物流任務(wù)編號(hào)。初始狀態(tài)下,AGV上存在正在執(zhí)行的物流任務(wù),其任務(wù)序列設(shè)為D={2n+1,…,2n+h},其中h為初始狀態(tài)下AGV上正在執(zhí)行的在制品數(shù)量,可知此時(shí)AGV系統(tǒng)中共有2n+h個(gè)任務(wù)需要被執(zhí)行。

考慮到AGV已有物流順序與約束的良好匹配性,基于新物流任務(wù)與AGV已有任務(wù)的相似度、AGV自身裝載、卸載間的先后順序,對(duì)每個(gè)參與競(jìng)爭(zhēng)的AGV采用如圖3所示的編碼方式。

圖3 粒子群算法編碼方式示意圖

對(duì)處于等待運(yùn)輸狀態(tài)的物流任務(wù),必須嚴(yán)格遵守先裝載、再卸載的操作流程。因此,算法在產(chǎn)生初始種群時(shí),每一個(gè)物流任務(wù)必須保證其裝載任務(wù)編號(hào)所對(duì)應(yīng)的任務(wù)次序小于卸載任務(wù)編號(hào)對(duì)應(yīng)的任務(wù)次序,即AGV先執(zhí)行裝載過(guò)程,再執(zhí)行卸載過(guò)程,保證AGV執(zhí)行任務(wù)的合理性,生成合理的粒子種群。粒子群算法的解碼過(guò)程如圖4所示。

圖4 粒子群算法解碼過(guò)程示意圖

2.2.2 算法步驟

根據(jù)粒子群算法的尋優(yōu)思想,每個(gè)粒子的速度和位置變化過(guò)程中,逐步向算法的最優(yōu)值靠攏。每個(gè)粒子經(jīng)過(guò)1次循環(huán)后,得出當(dāng)前搜索情況下的最優(yōu)解,更新當(dāng)前最優(yōu)解與全局最優(yōu)解。按照粒子飛翔規(guī)則,進(jìn)行位置與速度的迭代。如此循環(huán),直至找到算法迭代范圍內(nèi)的最優(yōu)解。算法的具體步驟為:

(1)初始化算法相關(guān)系數(shù),包括上下界、速度、位置等;

(2)采用改進(jìn)的編碼方式、參數(shù)粒子的初始種群;

(3)對(duì)種群中粒子的速度進(jìn)行更新;

(4)計(jì)算粒子適應(yīng)度值,根據(jù)對(duì)比結(jié)果,對(duì)全局最優(yōu)與局部最優(yōu)值更新;

(5)判斷是否達(dá)到終止條件,若沒(méi)有完成迭代次數(shù),則返回步驟(3);

(6)輸出算法求解結(jié)果,對(duì)算法結(jié)果進(jìn)行評(píng)估。

2.3 單載量與多載量AGV效果對(duì)比

為證明多載量AGV在個(gè)性化定制車(chē)間中的優(yōu)越性,結(jié)合本文提出的個(gè)性化車(chē)間制造過(guò)程中生產(chǎn)、物流的協(xié)同調(diào)度方案,對(duì)比分析多載量AGV自評(píng)估機(jī)制的有效性。具體的車(chē)間布局參數(shù)與訂單的加工參數(shù)如表2、表3所示。為保證訂單出現(xiàn)時(shí)間的隨機(jī)性,采用訂單出現(xiàn)間隔為[20,10,30]的三角分布模型,隨機(jī)訂單的出現(xiàn)時(shí)間為[0,17,36,55,79]。定義在制品的質(zhì)量為[1,1.5,1,1.5,1],AGV的最大載重為3。改進(jìn)的粒子群算法與遺傳算法性能對(duì)比如圖5所示,單載量AGV與多載量AGV的調(diào)度效果如圖6、圖7所示，AGVn,n表示正在運(yùn)輸?shù)漠a(chǎn)品編號(hào)。

表2 產(chǎn)品工序表

表3 AGV在加工單元間行駛時(shí)間表

圖5 算法性能對(duì)比圖

圖6 采用單載量AGV的調(diào)度方案圖

根據(jù)圖5可知,采用改進(jìn)粒子群算法的性能比遺傳算法的收縮速度快,算法尋優(yōu)能力較強(qiáng)。如圖7所示,AGV2同時(shí)執(zhí)行J4與J5的出庫(kù)任務(wù),體現(xiàn)多載量AGV較高的任務(wù)執(zhí)行能力。根據(jù)2種方案調(diào)度甘特圖以及相應(yīng)的統(tǒng)計(jì)結(jié)果分析,結(jié)合個(gè)性化定制的場(chǎng)景特性,采用多載形式的AGV能提高調(diào)度系統(tǒng)效率,節(jié)省物流環(huán)節(jié)的作業(yè)成本。同時(shí),由于生產(chǎn)、物流環(huán)節(jié)的高度耦合性,物流系統(tǒng)效率提升對(duì)加工單元利用率、加工功率降低等方面帶來(lái)積極影響,訂單的完工時(shí)間大幅度降低。

圖7 采用多載量AGV調(diào)度方案圖

3 調(diào)度方案實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證本文提出調(diào)度方案的應(yīng)用效果,基于eM-plant仿真平臺(tái),根據(jù)benchmarks實(shí)驗(yàn)數(shù)據(jù)[12],設(shè)置了4種個(gè)性化定制車(chē)間。車(chē)間環(huán)境信息見(jiàn)表4～8,車(chē)間布局如圖8所示?；?0組訂單數(shù)據(jù)對(duì)本文提出的調(diào)度方案與2種完全反應(yīng)式調(diào)度方案進(jìn)行仿真對(duì)比,實(shí)驗(yàn)結(jié)果如圖9所示。

表4 AGV在布局1中行駛時(shí)間矩陣表

表5 AGV在布局2中行駛時(shí)間矩陣表

表6 AGV在布局3中行駛時(shí)間矩陣表

表7 AGV在布局4中行駛時(shí)間矩陣表

圖8 仿真環(huán)境4種類(lèi)型車(chē)間布局圖

圖9 3種調(diào)度方案結(jié)果對(duì)比圖

根據(jù)圖9可知,本文提出的排產(chǎn)方案在訂單提前/拖期代價(jià)、加工單元利用率、功率方面具有明顯優(yōu)勢(shì),與MC、VC 2種調(diào)度策略相比,本文方案中加工單元平均利用率提升9.75%和11.97%,調(diào)度優(yōu)勢(shì)明顯。為進(jìn)一步說(shuō)明對(duì)比效果,采用配對(duì)樣本T檢驗(yàn)3種調(diào)度方案性能指標(biāo)差異的顯著性。Sig.值(或p值)代表2種方案的顯著性水平。一般情況下,假設(shè)的顯著性水平不超過(guò)0.05,即若2種方案對(duì)比結(jié)果的Sig.值小于0.05,則具有明顯的差異。對(duì)比結(jié)果如表8所示。

表8 3種調(diào)度方案配對(duì)樣本T檢驗(yàn)結(jié)果表

4 結(jié)束語(yǔ)

本文針對(duì)個(gè)性化訂單特性,改進(jìn)了完全反應(yīng)式調(diào)度機(jī)制,提出了基于生產(chǎn)與物流協(xié)同的實(shí)時(shí)訂單排產(chǎn)方案。采用“插空”思想,最大化保證了產(chǎn)品交貨期,提升了加工單元利用率,降低了單個(gè)訂單的分?jǐn)偝杀尽；诙噍d量AGV特性,搭建了物流模塊中物流任務(wù)代價(jià)評(píng)估機(jī)制,并采用改進(jìn)粒子群算法求解。對(duì)比單載量AGV與多載量AGV的調(diào)度效果,采用多載量AGV的情況下,調(diào)度方案優(yōu)勢(shì)較明顯。同時(shí),根據(jù)仿真結(jié)果可知,本文方案與現(xiàn)有完全反應(yīng)式調(diào)度方法相比,在提前/拖期代價(jià)、加工單元利用率、最小完工時(shí)間等方面具有顯著性差異,證明了本文調(diào)度方案的有效性。