基于產品交貨期約束的合作關系優化模型

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