空间调度问题的非线性规划分析求解方法

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