何建佳　徐福緣

[摘 要] 在傳統(tǒng)企業(yè)向供需網(wǎng)企業(yè)轉(zhuǎn)變過(guò)程中,作為SDN的一個(gè)供需流,其核心集中在對(duì)車間生產(chǎn)調(diào)度及物流配送的優(yōu)化上?針對(duì)這兩個(gè)問(wèn)題,基于木地板生產(chǎn)企業(yè)的現(xiàn)狀,本文引入了量子粒子群與模擬退火相結(jié)合的混合算法,以及一種求解物流系統(tǒng)的整合優(yōu)化模型與求解的啟發(fā)式算法分別對(duì)其進(jìn)行研究,具有一定的實(shí)用價(jià)值?

[關(guān)鍵詞] 企業(yè)供需網(wǎng);量子粒子群算法;整合優(yōu)化;啟發(fā)式算法

[中圖分類號(hào)]F270.7;F273.7[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]1673-0194(2009)03-0046-03

0 引 言

多功能開放型企業(yè)供需網(wǎng)(Supply and Demand Network with multi-function and opening characteristics for enterprises,SDN)是指以全球資源獲取?全球制造?全球銷售為目標(biāo),相關(guān)企業(yè)之間由于“供需流”的交互作用而形成的一種多功能的開放式的供需動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)[1]?因其具有網(wǎng)絡(luò)性?多功能性?開放性和動(dòng)態(tài)穩(wěn)定性等特性[1-2],近些年來(lái)日益受到學(xué)術(shù)界和企業(yè)界的關(guān)注?供需網(wǎng)理論符合了當(dāng)今環(huán)境對(duì)企業(yè)的要求,也符合當(dāng)今企業(yè)發(fā)展的需要?因此,積極推動(dòng)我國(guó)傳統(tǒng)企業(yè)向供需網(wǎng)企業(yè)的轉(zhuǎn)變對(duì)于企業(yè)成長(zhǎng)與發(fā)展?提高企業(yè)質(zhì)量及推動(dòng)我國(guó)市場(chǎng)經(jīng)濟(jì)的健康發(fā)展都具有十分重要的現(xiàn)實(shí)意義?推動(dòng)我國(guó)傳統(tǒng)企業(yè)向供需網(wǎng)企業(yè)的轉(zhuǎn)變,其前提條件要求供需網(wǎng)系統(tǒng)本身具有一定的穩(wěn)定性,這樣才能滿足供需網(wǎng)節(jié)點(diǎn)企業(yè)的多樣需求?而供需網(wǎng)穩(wěn)定性的首要基礎(chǔ)是供需網(wǎng)中供需流的穩(wěn)定性,只有供需流在一定時(shí)期內(nèi)處于穩(wěn)定態(tài)才能保障供需網(wǎng)的狀態(tài)穩(wěn)定?相對(duì)穩(wěn)定?波動(dòng)穩(wěn)定?動(dòng)態(tài)穩(wěn)定和有效穩(wěn)定,即供需網(wǎng)處于穩(wěn)定態(tài)?

基于此,筆者就供需網(wǎng)中供需流的穩(wěn)定性作出一些探索?本文主要基于供需流的初始流及過(guò)程流的優(yōu)化展開,當(dāng)前推動(dòng)我國(guó)傳統(tǒng)企業(yè)向供需網(wǎng)企業(yè)轉(zhuǎn)變的一個(gè)核心工作就是如何推動(dòng)我國(guó)加工?制造企業(yè)向供需網(wǎng)企業(yè)的轉(zhuǎn)變,而這類企業(yè)供需流的核心問(wèn)題就集中在車間生產(chǎn)調(diào)度及產(chǎn)品配送上,這直接影響著SDN企業(yè)與上游原料供貨商?各級(jí)分銷商?終端客戶的關(guān)系,從而誘發(fā)整個(gè)供需網(wǎng)系統(tǒng)的波動(dòng)?

1 SDN供需流的兩階段:調(diào)度與配送

作為供需網(wǎng)中的一個(gè)供需流,其核心主要涉及兩個(gè)階段(或說(shuō)問(wèn)題)——車間生產(chǎn)調(diào)度與物流配送?其中物流配送又涉及車輛調(diào)度問(wèn)題與車輛裝載問(wèn)題,二者相互影響?相互制約?就木地板生產(chǎn)企業(yè)而言,車間調(diào)度實(shí)際上構(gòu)成了一個(gè)典型的無(wú)等待流水車間調(diào)度(no-wait flow shop,NWFS)問(wèn)題,這是流程工業(yè)中常見的一類調(diào)度問(wèn)題?當(dāng)前基于蟻群算法[3]?離散粒子群算法[4]?禁忌搜索[5]等智能優(yōu)化算法雖已比較成功地應(yīng)用到NWFS的求解,但在實(shí)際應(yīng)用中還是會(huì)陷入局部最優(yōu)解,即出現(xiàn)不向最優(yōu)解方向進(jìn)化的早熟現(xiàn)象?基于此,在實(shí)踐的基礎(chǔ)上,本文采用量子粒子群與模擬退火相結(jié)合的混合算法對(duì)無(wú)等待流水車間調(diào)度進(jìn)行了研究?量子粒子群算法,由于其涉及的參數(shù)少,編程上更易于實(shí)現(xiàn),同時(shí)求解速度更優(yōu)[6];而模擬退火算法是一種屬于概率分布機(jī)制的優(yōu)化算法,在搜索的過(guò)程中有一種時(shí)變且最終趨于0的概率突跳性,可以有效地避免陷入局部最優(yōu)值最終趨于全局最優(yōu)[7]?

在物流配送上,學(xué)術(shù)界一般將車輛調(diào)度問(wèn)題(Vehicle Scheduling Problem,VSP)抽象為線路安排或車輛線路問(wèn)題,在其優(yōu)化求解上多采用啟發(fā)式算法?神經(jīng)網(wǎng)絡(luò)法?模擬退火算法等;在車輛裝載問(wèn)題(Vehicle Filling Problem,VFP)方面,一般將其視為三維裝箱問(wèn)題,理論上屬于NP-完全問(wèn)題,有限時(shí)間內(nèi)難以找到問(wèn)題的最優(yōu)解?同時(shí),對(duì)這一問(wèn)題的研究,往往基于對(duì)VSP或VFP問(wèn)題的單方面展開,而將VSP與VFP統(tǒng)一起來(lái)考慮的研究很少?顯然對(duì)于企業(yè)供需網(wǎng)而言,作為供需網(wǎng)中的一個(gè)供需流,VSP和VFP問(wèn)題是同等重要的兩個(gè)命題,二者相輔相成,缺一不可,一個(gè)環(huán)節(jié)出問(wèn)題勢(shì)必會(huì)影響另一個(gè)環(huán)節(jié),最終導(dǎo)致整個(gè)供需流的波動(dòng);同時(shí)這也與供需網(wǎng)的理念相違背,供需網(wǎng)強(qiáng)調(diào)的是整個(gè)系統(tǒng)的協(xié)同優(yōu)化?因此,將VSP與VFP 問(wèn)題統(tǒng)一起來(lái),對(duì)供需網(wǎng)的進(jìn)一步研究就顯得尤為重要?

2 車間調(diào)度的優(yōu)化

2. 1問(wèn)題描述

木地板生產(chǎn)企業(yè)的無(wú)等待流水車間調(diào)度可以描述為n個(gè)工件要在m臺(tái)機(jī)上加工完成,每個(gè)工件的加工順序相同,每臺(tái)機(jī)器加工的各工件的順序也相同,且已知對(duì)應(yīng)的加工的時(shí)間,一個(gè)工件一旦開始加工,其加工必須連續(xù)地完成,不允許等待?要求得到與工藝約束條件相容的工件加工順序,使得總的加工時(shí)間最短[8]?在調(diào)度中還要滿足以下假設(shè):

(1)每一個(gè)工件同一時(shí)刻只能在一臺(tái)機(jī)器上進(jìn)行加工;

(2)同一時(shí)刻每臺(tái)機(jī)器只能加工一個(gè)工件;

(3)不考慮工件加工的優(yōu)先權(quán);

(4)各工件必須按照工藝約束條件進(jìn)行加工?

與其他的調(diào)度相比,無(wú)等待流水車間調(diào)度相對(duì)比較簡(jiǎn)單,但是它仍舊是一個(gè)非常復(fù)雜和困難的組合優(yōu)化問(wèn)題?

2. 2基于混合量子粒子群算法的流程設(shè)計(jì)及描述

量子粒子群算法作為一種隨機(jī)搜索算法,在運(yùn)行接近結(jié)束時(shí)容易陷入局部最優(yōu),因此遇到復(fù)雜的調(diào)度問(wèn)題時(shí)就不能求得全局最優(yōu)解,模擬退火使用概率來(lái)避免陷入局部最優(yōu),將二者結(jié)合的算法的具體流程如下:

(1)初始化算法參數(shù)(種群數(shù)目?退溫速率?仿真次數(shù)?最大迭代次數(shù));

(2)隨機(jī)生成初始種群;

(3)計(jì)算各個(gè)個(gè)體對(duì)應(yīng)的調(diào)度的目標(biāo)值,種群中目標(biāo)值最小的微粒為gbest,每個(gè)微粒的自身位置為pbest;

(4)判斷算法是否到最大迭代次數(shù),若是,轉(zhuǎn)(8),否則轉(zhuǎn)(5);

(5)根據(jù)進(jìn)化方程產(chǎn)生成新的粒子;

(6)對(duì)種群中所有的個(gè)體均進(jìn)行定步長(zhǎng)抽樣的模擬退火操作,以概率min[1,exp(-Δ/tk)]接受后代,及時(shí)更新pbest 和gbest;

(7)然后進(jìn)行退溫操作tk=λ·tk,λ∈(0,1),并返回到(4);

(8)輸出該次仿真所得到的gbest;

(9)判斷是否再次進(jìn)行優(yōu)化,若是,轉(zhuǎn)(2),否則轉(zhuǎn)(10);

(10)輸出多次優(yōu)化的統(tǒng)計(jì)結(jié)果,并結(jié)束算法?

2. 3實(shí)例仿真

在此,為了測(cè)試算法的有效性,本文選擇了Car類調(diào)度問(wèn)題進(jìn)行仿真研究,在Car類調(diào)度問(wèn)題中粒子數(shù)為50,最大迭代次數(shù)為1 000,算例均進(jìn)行20次仿真,仿真統(tǒng)計(jì)結(jié)果見表1?

由表1的統(tǒng)計(jì)結(jié)果可知,在工件數(shù)比較小的調(diào)度中,量子粒子群算法和混合量子粒子群算法每次都可以求得最優(yōu)解?在機(jī)器數(shù)目多的調(diào)度中,也都能取得近似最優(yōu)解?從平均值來(lái)看,混合量子粒子群算法每次所取得的解要比粒子群算法取得的解要穩(wěn)定,由此也說(shuō)明了混合量子粒子群算法在搜索性能上具有更好的穩(wěn)定性?

3 物流配送系統(tǒng)整合優(yōu)化的基本思想

將VSP與VFP 問(wèn)題統(tǒng)一起來(lái),其求解的關(guān)鍵,在于完成首次貨物裝載計(jì)算的同時(shí),能隨時(shí)正確和完全地反映出裝載空間的變化情況(包括在各貨點(diǎn)因不斷進(jìn)行上貨或下貨而引起的空間動(dòng)態(tài)變化情況),且能得出新的配送裝載方案?因此,本文在基于有效空間的基礎(chǔ)上給出以下思路:優(yōu)先考慮VSP,在得出一個(gè)VSP的局部解之后,即進(jìn)行相應(yīng)的VFP求解,當(dāng)驗(yàn)證其滿足相應(yīng)的約束并可行后,再回到VSP上進(jìn)一步擴(kuò)展已有的局部解,爾后再進(jìn)行VFP求解?驗(yàn)證,如此反復(fù),直到所有問(wèn)題的解完?

在算法設(shè)計(jì)上,本文采用基于VSP & VFP整合優(yōu)化的啟發(fā)式算法實(shí)現(xiàn)①,該算法的主體結(jié)構(gòu)雖然還是分為VFP和VSP兩大部分,但相互間聯(lián)系密切,且互相影響?

3. 1算法流程

由于整合模型的求解難度極大,加之模型所涉及的動(dòng)態(tài)和不確定因素較多,故求解算法上分別在VSP和VFP的求解過(guò)程中特別設(shè)計(jì)了兩個(gè)人工調(diào)控接口,用人工干預(yù)的方法來(lái)靈活控制,以提高整合模型可行解的幾率和解的實(shí)際效果,具體如圖1所示?

3. 2程序設(shè)計(jì)

主程序主要基于Delphi 7.0配合桌面數(shù)據(jù)庫(kù)Paradox來(lái)編制,程序的數(shù)據(jù)結(jié)構(gòu)采用表結(jié)構(gòu),如:待裝貨物結(jié)構(gòu)表?已裝貨物結(jié)構(gòu)表?空間結(jié)構(gòu)表等?其主程序流程如圖2所示?

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

作為供需網(wǎng)的一個(gè)供需流,生產(chǎn)調(diào)度問(wèn)題以及物流系統(tǒng)中的多車場(chǎng)?多車型?非滿載?集送貨一體化配送模式廣泛的出現(xiàn)是當(dāng)前影響我國(guó)傳統(tǒng)企業(yè)向供需網(wǎng)企業(yè)轉(zhuǎn)變的一個(gè)重要因素,特別是對(duì)于像木地板生產(chǎn)這類企業(yè)而言,生產(chǎn)及物流的整合優(yōu)化對(duì)企業(yè)的成功轉(zhuǎn)化及轉(zhuǎn)化后的穩(wěn)定性顯得尤為重要?因此,在生產(chǎn)調(diào)度及物流系統(tǒng)中,建立一個(gè)有效的優(yōu)化模型并設(shè)計(jì)出相應(yīng)的算法有著十分重要的意義?

針對(duì)木地板生產(chǎn)企業(yè)的車間調(diào)度問(wèn)題,本文將量子粒子群與模擬退火算法相結(jié)合,充分發(fā)揮各自算法的優(yōu)勢(shì),并通過(guò)實(shí)例驗(yàn)證了混合量子粒子群算法解決無(wú)等待流水車間調(diào)度的可行性和有效性;針對(duì)物流配送問(wèn)題,采用整合優(yōu)化的思想?這對(duì)于有效整合供需網(wǎng)企業(yè)中的節(jié)點(diǎn)企業(yè)(如木地板企業(yè)合理整合二級(jí)分銷商等)?提高整個(gè)供需網(wǎng)的穩(wěn)定性等都具有重要意義?

主要參考文獻(xiàn)

[1] 徐福緣,何靜,等. 多功能開放型企業(yè)供需網(wǎng)及其支持系統(tǒng)研究——國(guó)家自然科學(xué)基金項(xiàng)目(70072020)回溯[J]. 管理學(xué)報(bào),2007,4(4):379-383.

[2] 徐福緣,何靜. 多功能開放型企業(yè)供需網(wǎng)初探[J]. 預(yù)測(cè),2002(6):19-22.

[3] 潘全科,趙寶華,等. 一類解決無(wú)等待流水車間調(diào)度問(wèn)題的蟻群算法[J]. 計(jì)算機(jī)集成制造系統(tǒng),2007,13(9):1801-1815.

[4] 潘全科,趙寶華,等. 無(wú)等待流水車間調(diào)度問(wèn)題的優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào),2008,31(7):1147-1154.

[5] 劉佳佳,李小平,等. 一個(gè)求解無(wú)等待流水調(diào)度的混合算法[J]. 自動(dòng)化技術(shù)與應(yīng)用,2006,25(4).

[6] 石錦風(fēng),馮斌,等. 用帶變異因子的QPSO算法解決Job-shop調(diào)度問(wèn)題[J]. 計(jì)算機(jī)工程與應(yīng)用,2008,44(8):49-52.

[7] 王凌. 車間調(diào)度及其遺傳算法[M]. 北京:清華大學(xué)出版社,2003:85-86,102-103.

[8] LIU B,WANG L,JIN Y H. An Effective Hybrid Particle Swarm Optimization for no-wait Flow Shop Scheduling[J]. The International Journal of Advanced Manufacturing Technology,2007,31(9/10):1001-1011.

①當(dāng)前流行的遺傳算法對(duì)單獨(dú)的車輛調(diào)度(VSP)求解效果雖比較滿意,但與對(duì)應(yīng)的車輛裝載問(wèn)題(VFP)結(jié)合顯得較為困難;同時(shí),盡管VFP部分具體應(yīng)用時(shí)一般也可以采用遺傳算法或啟發(fā)式算法等加以實(shí)現(xiàn)?但由于配送過(guò)程中車輛的貨物裝載情況是動(dòng)態(tài)變化的,因此,這些算法也不再適用?