基于產(chǎn)品交貨期約束的合作關(guān)系優(yōu)化模型

基于產(chǎn)品交貨期約束的合作關(guān)系優(yōu)化模型

1ve構(gòu)建中的合作伙伴選擇與優(yōu)化問題有助于快速制造的實施，可以通過不同地理位置的公司之間的合作來實施。為了獲得市場機遇，實現(xiàn)產(chǎn)品快速發(fā)展，一些制造公司之間成立了一個動態(tài)聯(lián)盟，即虛擬公司（威斯）。在威斯克，每個核心公司之間有著加強合作的合作知識、信息和技術(shù)交流的能力，充分發(fā)揮各自的優(yōu)勢和創(chuàng)造能力，在最短的時間內(nèi)以最低的投資完成產(chǎn)品的設(shè)計和制造過程，并快速市場引導(dǎo)產(chǎn)品。在VE構(gòu)建中,合作伙伴的選擇是一個關(guān)鍵的問題,它直接關(guān)系到VE的成敗.在VE合作伙伴選擇與優(yōu)化中,必須權(quán)衡各方面因素,如成本、質(zhì)量、交貨期和風(fēng)險等,對潛在的候選企業(yè)進行全面考察,從中選出最優(yōu)化的伙伴組合.因此,在近幾年的VE研究中,許多學(xué)者都在探索合作伙伴的選擇與優(yōu)化問題.由于合作伙伴選擇需要考慮多方面因素,文獻采用分層次比較法選優(yōu),考慮實際問題中的不確定因素,提出了一種新的模糊規(guī)劃方法用于VE構(gòu)建中的合作伙伴選擇.文獻考慮了制造和運輸費用,通過網(wǎng)絡(luò)優(yōu)化模型,提出了一種有效算法,但由于問題的復(fù)雜性,沒有考慮時間的約束.合作伙伴的選擇對VE的運行風(fēng)險也是考察候選伙伴的一個因素.文獻提出了基于風(fēng)險的VE合作伙伴選擇問題,并采用遺傳算法進行求解.文獻采用分支定界法求解VE合作伙伴選擇問題,考慮了項目的拖期懲罰,其優(yōu)化目標(biāo)是總成本最低.文獻指出,高質(zhì)量的產(chǎn)品是進入市場的先決條件,對許多企業(yè)來說,除高質(zhì)量外,成本和時間是競爭的關(guān)鍵.文獻提出了VE構(gòu)建中基于成本和時間的合作伙伴選擇優(yōu)化問題,給出了一個兩階段求解算法.第一階段通過一個多項式的精確算法求得最早完成時間的解,保證了解的可行性;第二階段以最早完成時間作為可行初始解,利用一個啟發(fā)式算法對解進行改進,最終使得在完成時間的約束下制造成本最小.本文在文獻研究的基礎(chǔ)上,采用遺傳算法對問題進行求解.2企業(yè)核心能力對ve構(gòu)建的意義每種產(chǎn)品的生產(chǎn)都需要經(jīng)過產(chǎn)品設(shè)計、物料采購和生產(chǎn)制造的過程,而在生產(chǎn)制造過程中,每一道工序都需要相應(yīng)的生產(chǎn)資源(機器設(shè)備和工作人員等),這些構(gòu)成了企業(yè)的核心能力.核心能力是企業(yè)一組先進技術(shù)和資源的和諧組合,是響應(yīng)機遇、參與競爭所依賴的能力.對于大而全的企業(yè),依靠自身的核心能力足以完成產(chǎn)品的設(shè)計、物料采購、生產(chǎn)制造以及產(chǎn)品銷售全過程.面對市場的快速變化以及對產(chǎn)品的需求由少品種、大批量向多品種、少批量甚至個性化的轉(zhuǎn)變,這種大而全的企業(yè)顯然無法應(yīng)對這種市場需求的轉(zhuǎn)型,因此,VE應(yīng)運而生.在VE構(gòu)建中,盟主首先將生產(chǎn)任務(wù)分成若干子任務(wù),然后與潛在的合作伙伴協(xié)商,以獲得必要的伙伴選擇信息.2.1任務(wù)之間的相關(guān)關(guān)系制造任務(wù)的分解需要考慮資源的利用、生產(chǎn)計劃和質(zhì)量控制等因素,根據(jù)產(chǎn)品生產(chǎn)所需的核心能力類型進行任務(wù)分解.各任務(wù)之間的先后順序關(guān)系由產(chǎn)品生產(chǎn)工藝決定.2.2心能力類型和生產(chǎn)時間VE構(gòu)建過程中,盟主通過計算機網(wǎng)絡(luò)發(fā)布招標(biāo)信息,招標(biāo)信息中給出所需核心能力類型、生產(chǎn)時間等信息.每個任務(wù)可能包含若干個子任務(wù).投標(biāo)者對其中某一任務(wù)進行投標(biāo)時,須根據(jù)能力需求計劃確定完成任務(wù)的時間段,在投標(biāo)時申明任務(wù)的最早開始時間、所需要的制造時間以及完成該項任務(wù)所需費用.2.3模型設(shè)計原則根據(jù)招標(biāo)和投標(biāo)過程中所獲得的信息,以及各任務(wù)的先后順序,可建立描述伙伴選擇的數(shù)學(xué)模型.由于各潛在合作伙伴的地理位置不同,在建模中,除了要考慮各潛在伙伴在投標(biāo)中提供的制造費用、最早開始時間、制造時間外,還要估算出物料或半成品的運輸時間和運輸費用.現(xiàn)給出符號如下:I={1,2,…,m}——任務(wù)(節(jié)點)編號;Ti——任務(wù)i,i=1,2,…,m;Tij——任務(wù)i中的子任務(wù)j;Fi={fi1,fi2,\:,fiki}——任務(wù)Ti的投標(biāo)者的集合,其中:ki表示任務(wù)Ti的投標(biāo)者數(shù)量;fir∈{0,1}:1,投標(biāo)者fir被選中完成任務(wù)Ti;0,投標(biāo)者fir未被選中,r=1,2,…,ki;i=1,2,…,m.cir——投標(biāo)者fir對任務(wù)Ti所投的制造費用;wirjh——將候選者fir所完成的任務(wù)Ti的物料(或半成品)送到fjh的費用,其中i≠j,j是i的緊后節(jié)點;Eijr——投標(biāo)者fir對子任務(wù)Tij所投的最早開時間;pijr——投標(biāo)者fir對子任務(wù)Tij所投的制造時間;Dijr——在虛擬企業(yè)構(gòu)建過程中確定的由投標(biāo)者fir完成子任務(wù)Tij的計劃開始時間;sirjh——將候選者fir所完成的任務(wù)Ti的物料(或半成品)送到fjh所需的時間,其中i≠j,j是i的緊后節(jié)點;Dc——產(chǎn)品交貨期.按照J(rèn)IT(JustInTime)理念,提前生產(chǎn)和滯后生產(chǎn)都是不可取的,提前生產(chǎn)會導(dǎo)致庫存增加,而滯后生產(chǎn)不能滿足客戶需求,失去信譽或商機.因此,本文考慮虛擬企業(yè)構(gòu)建中合作伙伴的選擇原則是在滿足產(chǎn)品交貨期的前提下,使制造費用和運輸費用的總和最小.這一問題可以用下面的0-1型整數(shù)規(guī)劃模型描述:minJ=m∑i=1m∑j=1ki∑r=1kj∑h=1wirjhδ(fir,fjh)+m∑i=1ki∑r=1cirfir,j是i的緊后節(jié)點.(1)s.t.ki∑r=1fir=1,fir∈Fi,i=1,2,\:,m;(2)fir∈{0,1},fir∈Fi,i=1,2,\:,m,r=1,2,\:,ki;(3)Dijr≥Dnhd+pnhd+sndir,?j,h,i是n的緊后節(jié)點?子任務(wù)Τnh先于子任務(wù)Τij,fir=1,fnd=1,fir∈Fi,fnd∈Fn;(4)Dijr≥Eijr,?j,fir=1,fir∈Fi,i=1,2,\:,m;(5)(Dmjr+pmjr)≤Dc,?j,fmr=1,fmr∈Fm.(6)minJ=∑i=1m∑j=1m∑r=1ki∑h=1kjwirjhδ(fir,fjh)+∑i=1m∑r=1kicirfir,j是i的緊后節(jié)點.(1)s.t.∑r=1kifir=1,fir∈Fi,i=1,2,\:,m;(2)fir∈{0,1},fir∈Fi,i=1,2,\:,m,r=1,2,\:,ki;(3)Dijr≥Dnhd+pnhd+sndir,?j,h,i是n的緊后節(jié)點?子任務(wù)Tnh先于子任務(wù)Tij,fir=1,fnd=1,fir∈Fi,fnd∈Fn;(4)Dijr≥Eijr,?j,fir=1,fir∈Fi,i=1,2,\:,m;(5)(Dmjr+pmjr)≤Dc,?j,fmr=1,fmr∈Fm.(6)式中,δ(fir,fjh)∈{0,1}:1,當(dāng)fir=1,fjh=1時;0,其他.目標(biāo)函數(shù)(1)為制造費用和運輸費用的總和,約束(2)表示對每一任務(wù)必須從候選伙伴中選出其中一個,且只能選擇一個加入虛擬企業(yè)中,約束(4)和(5)保證任務(wù)的先后順序約束,約束(6)是交貨期約束.3遺傳計算方法的設(shè)計由于計算的復(fù)雜性,對上述數(shù)學(xué)模型直接求解有相當(dāng)?shù)碾y度,為此,采用遺傳算法進行求解.3.1任務(wù)5生成fmxm由上述問題描述可知,對于任務(wù)Ti共有ki個候選伙伴,需要從中選出一個,且只能選擇一個,因此采用自然數(shù)據(jù)串編碼方式最為簡單,即x=[x1x2\:xm]?(7)x=[x1x2\:xm]?(7)其中,1≤xi≤ki,i=1,2,…,m.編碼(7)可解碼為:f1x1=1,f2x2=1,\:,fmxm=1,即,xi表示對于任務(wù)Ti選擇第xi個候選伙伴.例如染色體編碼為[23516435]表示對任務(wù)T1,選擇f12=1,對任務(wù)T2,選擇f23=1,…,對T8,選擇f85=1.3.2cost、完成時間節(jié)點為搜索滿足交貨期約束下,制造費用和運輸費用的總和(即總費用)最低的VE合作伙伴組合,對應(yīng)每一染色體編碼需要計算出總費用cost和完成時間CT,cost計算公式如下:cost=m∑i=1m∑j=1wixi,jxjδ(fixi,fjxj)+m∑i=1cixifixi,(8)cost=∑i=1m∑j=1mwixi,jxjδ(fixi,fjxj)+∑i=1mcixifixi,(8)式中:δ(fixi,fjxj)∈{0,1}:1,j是i的緊后節(jié)點;0,其他.CT根據(jù)解碼結(jié)果和約束條件(4)、(5)計算.3.3適應(yīng)度函數(shù)設(shè)計由于目標(biāo)函數(shù)為最小值問題,故定義適應(yīng)度函數(shù)為:fit(cost)=1-cost-costmincostmax-costmin?(9)fit(cost)=1?cost?costmincostmax?costmin?(9)其中,cost為由公式(8)計算出的對應(yīng)某一染色體編碼制造費用和運輸費用的總和(總費用),costmin為總費用的最小估算值,costmax為總費用的最大估算值,costmin和costmax適當(dāng)取值,使0<fit(cost)<1.總費用cost越小,適應(yīng)度fit越大,該染色體被選中可能性就越大.3.4數(shù)目和分子步驟設(shè)種群大小為popsize,種群中所有個體都是隨機產(chǎn)生的,其算法如下:步驟1初始化,設(shè)數(shù)組k=[k1k2…km],其中ki表示對任務(wù)Ti的候選伙伴數(shù)目(i=1,2,…,m),令j=0,進入步驟2.步驟2j=j+1,若j>popsize,轉(zhuǎn)入步驟5,否則,進入步驟3.步驟3令i=0,子步驟3.1:i=i+1,若i>m,轉(zhuǎn)入步驟4,否則,進入子步驟3.2;子步驟3.2:產(chǎn)生(0,1)之間的隨機數(shù)p,進入子步驟3.3;子步驟3.3:xi=「p*ki?,轉(zhuǎn)向子步驟3.1.步驟4種群中第j個染色體popj=x,轉(zhuǎn)向步驟2.步驟5種群ΡΟΡ=[pop1pop2?poppopsize]?結(jié)束.3.5個體被入選的可能性初始種群生成以后,按照基本遺傳算法就是對種群進行遺傳操作,即選擇、交叉、變異,經(jīng)過設(shè)定的最大進化代數(shù)后停止.其中選擇采用輪盤賭法,適應(yīng)度高個體的被選中的可能性大;交叉采用單點交叉法.基本遺傳算法通常得不到十分滿意的搜索性能.對于本文提出的問題采用基本遺傳算法存在兩方面的不足:第一,本文提出合作伙伴的選擇原則是在滿足產(chǎn)品交貨期的前提下,使總費用(cost)最小,按照公式(9)給出的適應(yīng)度函數(shù)搜索的結(jié)果不能保證滿足產(chǎn)品交貨期的約束;第二,采用基本遺傳算法搜索無論是最大適應(yīng)度還是平均適應(yīng)度都不甚理想,這一點在案例分析中得到了驗證.為此,本文采用改進遺傳算法.3.6改進的遺傳算法改進遺傳算法的基本思想是對種群中染色體進行過濾(染色體過濾法).首先計算出種群中每一個體所對應(yīng)的產(chǎn)品生產(chǎn)完成時間(CT),剔出CT大于交貨期的所有個體(即不可行染色體),再從剩余的個體中選出一些適應(yīng)度高的個體,其數(shù)量等于不可行染色體的數(shù)量.使這些個體在種群中復(fù)制一次,以保持種群大小不變.其優(yōu)點是,第一,種群中不再包含不可行染色體,從而保證搜索的結(jié)果滿足產(chǎn)品交貨期的約束;第二,用高適應(yīng)度的染色體取代不可行染色體,使得高適應(yīng)度染色體在種群中所占比例增大,從而使選擇操作中有更多的優(yōu)良個體被選中,提高了搜索性能.改進的遺傳算法操作如下:步驟1按照上述方法產(chǎn)生初始種群,種群大小為popsize,進入步驟2;步驟2令進化代數(shù)gen=0,設(shè)定交叉概率pc,變異概率pm,最大進化代數(shù)maxgen,進入步驟3;步驟3gen=gen+1,如果gen>maxgen轉(zhuǎn)入步驟11,否則進入步驟4;步驟4計算種群中每一個體所對應(yīng)的cost和CT,進入步驟5;步驟5將種群中每一個體所對應(yīng)的CT與交貨期Dc比較,若某個體對應(yīng)的CT>Dc則從種群中剔出該個體,剔出的個體數(shù)量為dnum,進入步驟6;步驟6按照公式(9)計算出種群中每個個體的適應(yīng)度,并從中選擇dnum個高適應(yīng)度的個體進行個體復(fù)制,以保證種群大小仍為popsize,進入步驟7;步驟7采用輪盤賭選擇法進行選擇操作,進入步驟8;步驟8隨機配對,按照概率pc單點交叉,交叉點隨機設(shè)置,進入步驟9;步驟9對個體的每一基因座,依變異概率pm指定其變異點,對每一指定的變異點的基因值由除該基因值以外的隨機產(chǎn)生的[1,ki]之間的數(shù)值代替,進入步驟10;步驟10尋找種群中最大適應(yīng)值maxfit和與之對應(yīng)的最小費用mincost,計算種群的平均適應(yīng)度avefit和平均費用avecost,轉(zhuǎn)向步驟3;步驟11計算結(jié)束.種群中適應(yīng)度最大的個體就是對應(yīng)成本最低的個體,對其解碼得到VE合作伙伴選擇的最優(yōu)組合.4任務(wù)3.2模架加工和原材料采購現(xiàn)以模具制造的例子來說明本文給出的遺傳算法的應(yīng)用.一個模具制造企業(yè)接了一個大型注塑模的訂單,它需要大型銑床和磨床加工模架,以及在模架上進行相關(guān)加工;需要精密數(shù)控機床加工型腔和型芯;需要大型注塑機進行試模.型腔和型芯由鑲塊組成,一些鑲塊先要用數(shù)控機床加工出初步外形,再用電火花加工成精確外形.該企業(yè)不具備所有這些資源,需要組織VE來完成.這項生產(chǎn)任務(wù)根據(jù)所需核心能力可以分解成下列制造任務(wù):任務(wù)1產(chǎn)品的三維造型、模具設(shè)計,包括型腔、型芯和電極的設(shè)計,需要有經(jīng)驗的模具設(shè)計人員和相關(guān)的CAD軟件包.任務(wù)2模架的設(shè)計、模架制造工藝設(shè)計、模架加工制造以及在模架上進行相關(guān)加工,需要大型銑床和磨床.任務(wù)3型腔和型芯的工藝設(shè)計,NC編程及鑲塊的粗加工,需要數(shù)控機床.任務(wù)4電極的工藝設(shè)計,NC編程和加工,需要精密NC機床.任務(wù)5鑲塊的電火花加工.任務(wù)6其他零部件的設(shè)計和制造、模具裝配,需要有經(jīng)驗的模具工人.任務(wù)7試模,需要大型注塑機.任務(wù)8根據(jù)試模結(jié)果進行修模,需要有經(jīng)驗的模具工人.如果某一任務(wù)需要原材料,那么原材料的采購包括在該任務(wù)中.任務(wù)之間的先后順序關(guān)系如圖1所示.公司決定任務(wù)1要由公司自己完成,其他的任務(wù)由合作伙