1、第16卷第6期2010年6月計算機集成制造系統ComputerIntegratedManufacturingSystems文章編號:1006-5911(2010)06-1273-07空間調度問題的非線性規劃分析求解方法張志英,陳潔(同濟大學機械工程學院,上海200092)摘要:場地平均時空利用率,并以此為目標,、。研究了模型在其他特殊空間調度問題中的適用性。驗證,結果表明,。關鍵詞:空間調度;數學模型;船舶建造:AprogrammingapproachforspatialschedulingproblemZHANGZhi2ying,CHENJie(SchoolofMechanicalEngin

2、eering,TongjiUniversity,Shanghai200092,China)Keywords:spatialscheduling;nonlinearprogramming;averagespatiotemporalutilizationratio;mathematicalmod2els;shipbuilding0引言調度問題一般都是基于時間考慮的,即對n個工件在m臺機器上的加工過程。調度算法主要為各工件分配在各機器上的開始加工時間,并使某些性能達到最優1。但在船舶建造過程中,由于船體分段重,生產時使用的放置設備(如工作平臺)昂貴且需占用很大的作業空間,而作業空間通常很有限,成為生

3、產中的瓶頸。因此,船體建造調度問題除需解決一般車間生產的調度問題外,還需重點考慮分段在工作平臺的空間布置問題。這種同時考慮時間和空間的調度問題稱為空間調度問題2。目前,對于空間調度問題的研究主要集中在啟發式規則和智能優化算法方面。Lee等提出了基于船體形狀的啟發式規則方法解決分段空間調度問題3;Baek等為船舶建造工藝調度開發了基于資源平衡的啟發式算法4;Park等提出了解決船體涂裝作業的空間調度算法5。然而,這些算法都是基于經驗和特殊工況環境下提出的,如場地的形狀和布局、船體結構形狀等,具有很強的針對性,實用性不強。智能優化方面,如Min和Li等利用遺傳算法求解船體裝配空間布局優化的動態調度

4、問題627;Ranjan等應用遺傳算法和最左最下原則實現船舶分段空間調度8。但上述方法都將空間利用率作為主要優化指標,將時間收稿日期:2009207214;修訂日期:2009209204。Received14July2009;accepted04Sep.2009.基金項目:國家自然科學基金資助項目(70872076)。Foundationitem:ProjectsupportedbytheNationalNaturalScienceFoundation,China(No.70872076).第6期張志英等:空間調度問題的非線性規劃分析求解方法1273和空間分開考慮,假設條件與實際生產環境有一定

5、差距,產生的調度方案難以有效應用。由于空間調度問題的復雜性和NP2hard特性,幾乎不可能利用運籌學方法建立數學模型對大規模問題進行優化求解,目前在這方面的研究也較少。針對小規模空間調度問題,Piyush等在同時考慮時間和空間相互變化的情況下,利用混合整數規劃(MixedIntegerProgramming,MIP)方法對船體分段空間調度問題進行了建模9;期,而縮短造船周期的前提是提高關鍵資源特別是空間資源的利用率,這兩者之間相互聯系、不可分割,既不能為了縮短周期而不顧空間資源的沖突與承載力,也不能為了提高空間資源利用率而忽略交貨期等時間因素。因此,針對多場地有未完工分段的空間調度問題,考慮到

6、場地生產周期和場地利用率的綜合優化,本文提出了場地平均時空利用率(AverageSpatiotemporalRatio,ASUR)指標。2,5,可將考慮時間因素而1所示(圖中假設場地和分段為矩形)。鄭俊麗等提出了以分段批次時空利用率為基礎的空間調度方法10211。但上述方法只針對單場地無未完工分段的情況,有一定的應用局限性。Koh等對大分段空間調度問題進行建模并用遺傳算法進行求解,然該方法考慮了未完工分段情況,布局12。,未完工到下一個調度周期,調度過程中需要考慮未完工分段情況。而且實際調度中存在多場地作業情況,單場地和多場地之間的空間調度屬于非加和關系,多場地的空間調度問題不能完全通過單場地

7、的空間調度得到。本文以平均時空周轉率最大化為目標,運用非線性規劃方法對多場地有未完工分段的船體分段空間調度問題進行建模,并結合船廠實際數據對模型的正確性進行了驗證。基于以上思想,構建ASUR指標:定義1有場地j,其面積為Sj、生產周期為Tj,由其場地面積Sj和生產周期Tj共同構成的容積定義為Vj,則Vj=Sj×Tj。(1)1問題描述與解決方法111問題描述其中:Tj指在一個調度計劃周期內,場地j內所有分段都完工的時刻與該期調度開始時刻之間的時間;Vj表示場地j在制造期Tj內的加工能力。定義2有待調度分段i,其在場地上的投影面積為si,加工時間為ti,由其投影面積si和加工時間ti共同

8、構成的容積定義為vi,則(2)vi=si×ti。其中vi表示分段i在加工時間ti內要占用的場地容積。定義3有未完工分段g,其在場地上的投影面積為sg,剩余加工時間為tg,由其投影面積sg和剩余加工時間tg共同構成的容積定義為vg,則vg=sg×tg。(3)在船舶分段建造中,多場地有未完工的船舶分段空間調度問題普遍存在。一般可描述為:以船舶分段為研究對象,作業場地為工作平臺,在多場地有未完工分段的情況下,確定待調度分段的開始加工時間以及場地布局位置,從而達到生產周期和場地空間利用率的綜合優化。需要解決的問題有:待調度分段的開始加工時間;待調度分段的空間位置;待調度分段的放置方

9、向。空間調度結果可表示為A=i,xi,yitifi,lxi,其中:fi為分段i布置的場地,xi和yi為i布置點坐標;ti表示分段的開始加工時間;lxi表示分段的放置方向,若lxi=1,表示分段i的長度方向與場地x的方向平行,否則垂直(假設分段只有兩個放置方向)。112解決方法11211場地平均時空利用率其中vg表示未完工分段g在剩余加工時間tg內要占用的場地容積。定義4R是一個綜合考慮時間和空間的優化指標,用來評價各場地的加工能力平均被利用的情況。假設有M塊場地,場地上共有G個未完工分船舶建造中擴大造船總量的關鍵是縮短造船周1274計算機集成制造系統第16卷段,現將N個待調度分段在M個場地上進

10、行加工,則M假設:(1)分段和場地的形狀均為矩形。根據圖1建R=Nvi+jGvgj=16V。(4)立空間調度的三維模型,具體如下:場地j長度為Lj,寬度為Wj,場地左下角為坐標原點,以長度方向為X軸、寬度方向為Y軸、豎直方向為時間Z軸構建三維坐標系。矩形分段i水平布置于場地上,若長邊pi平行于X軸時,lxi為1;若長邊pi平行于Y軸時,lxi為0。(2),不受其他,。()、對稱分段需同時開,不考慮物料。(4)非空間資源(如人員、設備等)充分,不考慮場地工作負荷平衡問題。212非線性規劃模型建立R指標建立在所調度場地的整體加工能力之上,相對于其他空間調度指標有以下優點:(1)考慮場地上未完工分段

11、對場地加工能力的影響。(2)單一指標(如加工時間最短、場地利用率最高等)只是從一維的角度對空間調度問題進行評價;而R進行評價,空間的關聯特性。(3)設或算法下提出的,如文獻9是建立在單場地無未完工分段的基礎上,文獻10和文獻11針對分批調度策略;R是基于實際生產中普遍存在的多場地和有未完工分段情況提出的,基本上能夠被不同的背景、策略下的空間調度問題所采用,如設G=0時,R指標可以應用到無未完工分段的情況下,M=1時,R指標適用于單場地情況。11212空間調度模型中的干涉問題對于分段在場地上放置的位置干涉問題,本文借鑒裝箱問題的處理方法13214。如圖2所示,分段1在分段2左側,若要求兩分段在X

12、方向上不相交,則必須滿足條件x1+l1x2。空間調度問題不同于裝箱問題,它在滿足空間資源約束的前提下更多關注時間優化目標。因此,空間調度問題在時間軸方向上不僅不能有效干涉沖突,還要滿足如交貨期等時間資源約束。2非線性整數規劃模型211空間調度假設考慮到船舶分段建造過程中的實際情況,在分析分段幾何和制造工藝特性的基礎上,進行如下基于以上對多場地有未完工分段的空間調度問題的假設,建模如下:(1)索引索引包括:i,k表示待調度分段索引;j表示場地索引;ij表示待調度分段i與場地j之間的位置關系索引;ik表示待調度分段i和待調度分段k之間的位置關系索引;jg表示場地j上未完工分段g的索引;ijg表示待

13、調度分段i和未完工分段jg的位置關系索引;sr表示分段r必須在分段s完成之后才能開始;fh表示分段f和分段h對稱;xi表示待調度分段i是否平行X軸索引。(2)參數具體參數包括:N為待調度分段總數;M為場地總數;G為未完工分段總數;(pi,qi,ti)表示待調度分段i的長、寬以及分段的加工時間,piqi,i=1,2,N;(pjg,qjg,tjg)表示場地j上未完成分段g沿x軸和y軸方向的長度和剩余加工時間,g=1,2,G;第6期張志英等:空間調度問題的非線性規劃分析求解方法1275(Lj,Wj)表示場地j的長和寬,j=1,2,M;(xjg,yjg,0)表示場地j上分段g的左下前坐標;ESTi表示

14、待調度分段i的最早開始加工時間;DDi表示待調度分段i的交貨時間。(3)連續變量lik+rik+bik+fik+uik+vikSij+Skj-1foralli,k,ji<k,j=1(12)(13)6mSij=1foralli,Sij(xi+pilxi+qi(1-lxi)xjg+M(1-lijg)邊續變量包括:Tj表示場地j的生產周期;(xi,yi,zi)表示待調度分段i的參考點。(4)0-1變量0-1變量包括:lik/lijg表示若分段i在分段k/jg的左邊則為foralli,jg,xjg+pjgSijxi+M(1-rig)foralli,g,(14)(15)Sij(yi+i(1-lxi

15、)+ilyjg+M(1-bijg)i,(16)(17)qjgSiM(-fijg)foralli,jg,tjgSijzi+M(1-vijg)foralli,jg,xi+pilxi+qi(1-lxi)Lj+M(1-sij)(18)(19)(20)(21)(22)(23)(24)(25)(26)(27)(28)1,反之為0;rik/rijg表示若分段i在分段k/g1,反之為0;bik/bijgk/jgforalli,j,yi+qilxi+pi(1-lxi)Wj+M(1-sij)1,反之為0;fik/fijgi在分段k/jg的前面則為foralli,j,zi+tiTj+M(1-sij)foralli,

16、j,tjgTjforalljg,j,zi+tiDDiforalli,ziESTiforalli,zs+tszrforall(sr),zf=zhforall(fh),Sij,lxi,lij,rij,bij,fij,uij,vij,lijg,rijg,bijg,fijg,vijg=0or1,xi,yi,zi0。1,反之為0;uik表示若分段i比分段k先開始加工則為1,反之為0;vik/vijg表示若分段k/jg比分段i先開始加工則為1,反之為0;lxi表示若分段i的長平行于x軸則為1,反之為0;sij表示若分段i放在場地j上為1,反之為0。多場地有未完工分段的空間調度數學模型如下:該模型是以場地平

17、均時定利用(R)最大化為目maxNpiqiti+Gpjgqjgtjgj=16LM。(5)標。約束(6)約束(12)表示若分段i,k在同一場地內,分段放置位置不允許重合;約束(13)表示分段一旦被放置其位置即被鎖定,加工完成后才能移出;約束(14)(18)表示待調度分段的放置位置不能同場地上的未完工分段的位置交叉;約束(19)約束(22)表示分段不能超過場地邊界;約束(23)表示分jWjTjforalli,ki<k,xk+pklxk+qk(1-lxk)xi+M(1-rik)(6)(7)(8)(9)(10)foralli,ki<k,yi+pi(1-lxi)+qilxiyk+M(1-bi

18、k)段不允許拖期;約束(24)表示分段必須在所需資源到達后才能開始加工;分段工藝上的加工優先度用分段的實際加工時間來體現,約束(25)表示分段r必須在分段s加工完成之后才能開始加工;為減少在制品庫存,對稱分段同時開始,如約束(26);約束(28)是非負約束。foralli,ki<k,yk+pk(1-lxk)+qklxkyi+M(1-fik)foralli,ki<k,zi+tizk+M(1-uik)foralli,ki<k,zk+tkzi+M(1-vik)foralli,ki<k,若分段的空間調度問題中有W對分段有加工優先關系、B對對稱分段,則以上模型共有3N(N+M)+

19、(11)MN(N-1)+G(N+1)+W+B個約束,21276計算機集成制造系統第16卷M+N(3N+5G+M+1)個變量,其中0-1變量有NX(3N+5G+M+1)個,連續變量有M+3N個,模型求解的時間復雜度為O(n3)。以上模型可用如LINGO,CPLEX等商業軟件進行求解,一般地,求貨時間;未完工分段的數量、尺寸、放置位置和需加工時間;場地的數量和尺寸;輸入分段之間的優先級和對稱關系。實際輸入數據如表1表3所示。表1待調度分段數據分段n1n2n3n5n7n8ESTi/dDDi/dpi/mqi/mti/m解時間與模型規模呈正向關系。213非線性整數規劃模型在其他特殊調度問題中的應用對模型

20、進行修改,可以使其應用到其他特殊的分段空間調度問題。如調度前場地上沒有未完工分段即場地為空,則對原模型進行如下修改:增加0-1變量nj(當場地j被利用時為1,反之為0),刪除變量lijg,rijg,bijg,fijg和vijg;(00102211(18)及(23),增加約束:目標函數改為:i1Nijjallj;i1Npiqii/j=16mLjWjTjnj)。若n9n10分段在非空的單場地上進行空間調度,在前述模型調整的基礎上:刪除0-1變量Sij;刪除約束(14)和約束(15),將約束(13)右側變為1,約束(19)約束(21)右側分別變為L,M和T;目標函數改為:max(表2未完工分段數據分

21、段g1g2g3xig/myjg/mzjg/dpjg/mqjg/mtjg/d場地j1j2j2j1j10000141250000011221i=16NpiqitiLWT)。對n個工件、m臺機器的車間調度問題,負荷可看作每臺機器上工件的總加工時間。在船體分段的空間調度中,分段相當于工件,場地相當于機器,其負荷可以用每個場地上被分段占用的總容積來表示。若需考慮各場地之間的負荷均勻,可以在原模型的基礎上,如對于場地j,k,增加約束|(+i=0g4g5表3場地數據場地j1j2長/m4242寬/m42426Npiqitisijg=06Gpjgqjgtjg)-(i=06Npiqitisik+g=06Gpkgq

22、kgtkg)|A(A為非負常數);場地的負荷也可簡化地從其生產通過運行可確定待調度分段的放置場地、放置位置、放置方向和實際開始加工時間(如表4),得到場地生產周期,如表5所示。表4多場地有未完工分段空間調度結果分段n1xiyizilxi周期方面考慮,則約束變為|Tj-Tk|A(A為非負常數)。3實驗驗證與分析評價311實驗論證與結果場地j2j2j2j2j1j2j100021021101001n2n3n4n5n6n7為驗證所建模型的正確性,以上海某大型船廠2個月計劃期內的曲面分段建造過程為例,利用LINGO1110軟件,在處理器為1166Hz,內存為1GB的計算機上進行求解。結合生產實際,設模型

23、最長運行時間為1h。實驗輸入參數包括:待調度分段的數量和尺寸、加工時間、最早加工時間、交第6期張志英等:空間調度問題的非線性規劃分析求解方法續表41277n8n9n1000281208R=63193%221000j1j1j1表5場地生產周期場地j1j2空間調度的實用性,本文結合實際數據分別對上述三種情況進行驗證。模型的輸入待調度分段數均為10個,設定軟件最長運行時間為1h。表6為運行時間限定為1h時四種空間調度問題的運行結果,表中“解的狀態”項為運用LINGO軟件全局最優求解器求解的結果。在限制時間內,解的狀態與約束條件數量、約束變量以及輸入數據整齊度等有關。表6值/%長/m4242寬/m42

24、42生產周期/d1522無未完工分段值/%局部最優解的狀態局部最優全局最優加工信息,也能得到場地的生產信息,45中可知,場地j1個待調度分段;j2,上面同樣將布置5。工作人員、。從表4可知,場地平均時空利用率為63193%,高于當前實際生產中的數據30%50%。312其他數值實驗分析11936512760148從表6可知,本文提出的模型能成功應用到上述空間調度問題的四種情況中,且都獲得了較優的運行結果:ASUR值均超過60%,高于船廠實際數據;單場地有未完工空間調度問題和多場地無未完工調度問題的ASUR值達到全局最優解,這不僅準確求解了問題,也能為其他算法評價提供幫助。通過改變輸入數據,如改變

25、待調度分段數量、待調度分段尺寸和待調度分段松弛時間等參數,對模型進行多次數值實驗,得出以下結論:(1)在限制時間(1h)內,模型可解的規模有限。模型約束條件越多,在限定時間內獲得的場地平均利用率越低,當約束條件超過1000個時,限定的運行時間內場地時空平均利用率低于50%,當約束條件超過1750個時,模型不能得到可行解。因此,本模型適用于小規模空間調度問題的優化求解,對于大規模空間調度問題,可考慮結合問題分解策略,將原問題分解轉化成多個中小規模的調度子問題后進行求解。(2)當分段尺寸較小時,場地平均時空利用率較高。因為分段尺寸較小時,能更好地利用場地“容積”,這與三維裝箱問題得到的結論相似13

26、。(3)當分段松弛時間較小時,場地平均時空利用率較低。因為松弛時間較小時,分段在時間軸方向上的變量搜索區域減少,雖然能減少求解時間,但場地平均利用率一般較低。313模型在其他空間調度問題中的實驗與分析4空間調度問題的求解分析對于小規模空間調度問題,可以利用本模型運用商業軟件直接進行準確求解,但由于空間調度問題的復雜性和NP2hard特性,對于大規模問題幾乎不可能利用運籌學方法建立數學模型進行優化求解。但大規模生產調度算法與小規模調度算法并不沖突,前者往往利用后者作為子算法。后續研究將在本文所提模型的基礎上,結合大規模空間調度問題的特點,從縮小問題規模和降低求解難度兩個方面進行探索。(1)縮小問

27、題規模縮小問題規模方面,主要是運用基于問題分解方法。時間和空間資源是影響空間調度問題的兩個主要因素,根據這兩個因素,通過單一分解或綜合分解,將大規模空間調度問題分解為若干規模較小的子問題,利用本模型通過商業軟件直接求解。(2)降低求解難度降低求解難度方面,主要是在本文模型的基礎上通過拉格朗日松弛/分解法,通過松弛某些強約束(如允許分段延遲交貨),或引入變量的硬拷貝分解問題,使得問題容易求解。在實際分段調度中還可能存在以下幾種情況:單場地有未完工分段;多場地無未完工分段;單場地無未完工分段。為驗證模型對以上特殊分段5結束語本文提出的空間調度非線性整數規劃模型,以1278計算機集成制造系統第16卷

28、場地平均時空利用率為評價指標,考慮分段加工工藝以及交貨時間等要求。通過實例驗證,本文所提模型不僅能精確地解決造船業普遍存在的多場地有未完工分段的空間調度問題,而且也能成功地應用到其他幾種典型情況下的空間調度問題中,具有良好的實用性和可拓展性。后續研究將在本文模型的基礎上,從縮小問題規模和降低求解難度兩個方面,對大規模空間調度問題進行研究。參考文獻:1WANGLing.ShopschedulingwithgeneticalgorithmsBeijing:TsinghuaUniversityPress,2003(in).spatiallayoutplanningC/Proceedingsofthe

29、4thInterna2tionalConferenceonMachineLearningandCybernetics.Washington,D.C.,USA:IEEE,2005:361223617.8RANJANV,DUCKYY.DynamicspatialblockarrangementschedulinginshipbuildingindustryusinggeneticalgorithmC/Proceedingsofthe3rdIEEEInternationalConferenceonIndustrialInformatics.Washington,D.C.,USA:IEEE,2005:

30、4442449.9PIYUSHR,RAJIVKS.andheuristicapproachesforsolvingthespatialschedulingC/Proceedingsofthe37thComputersandIndustrial:,2007:20223.10J,JIANGZhibin,etal.Aspatio2algorithmminimizingmakespanJ.ofShanghaiJiaotongUniversity,2009,43(4):6632668(inChinese).鄭俊麗,陳峰,江志斌,等,縮短最大完工凌.車間調度及其遺傳算法M.:學出社,2003.2LEEJK

31、,LEEJKH,schedulingsystemsforDaewoo:DASprojectJ.EuropeanJournalofResearch,1997,97(2):3802395.3LEEKJ,LEEJK,CHOISY.Aspatialschedulingsystemanditsapplicationtoshipbuilding:DAS2CURVEJ.ExpertSystemswithApplications,1996,10(3/4):3112324.4BAEKTH,CHUNGKH,PARKJC.Astudyontheappli2cationofresourcelevelingheuristicforshiperectionschedulingJ.IEInterfaces,1999,12(3):3542361.5PARKC,CHUNGKH,PARKJC,etal.Aspatialschedu2lingapplicationattheblockpaintshopinshipbuilding:theHYPOSprojectJ.ProductionPlanning&Control,2002,13(4):3