中国机械工程第18卷第1期2007年1月上半月
基于混合遗传算法的动态车间调度系统的研究
鞠全勇朱剑英
南京航空航天大学,南京,210016
摘要:分析了生产工艺计划与车间调度系统的集成原理,提出将CAPP模块与基于周期和事件驱动的滚动窗口调度有机地相结合,从而实现工序分段设计的CAPP系统和基于周期和事件驱动的滚动窗口再调度策略的生产调度系统的集成。在建立集成模型的基础上,对算法进行研究,把简单遗传算法(SGA)和模拟退火算法(SA)有机结合,使算法优化机制融合和优化结构互补,形成高效的混合遗传算法,使集成系统能适应连续加工过程中复杂的环境变化并高效地完成实时处理,减少突发事件造成的工序大范围的重新设计。实例验证了系统的可行性和有效性。
关键词:生产调度;混合遗传算法;CAPP;集成模型中图分类号:U692.4 文章编号:1004—132X(2007)01—0040—04StudyontheSystemofDynamicJobShopSchedulingBasedonCombinedGeneticAlgorithm
JuQuanyongZhuJianying
NanjingUniversityofAeronauticsandAstronautics,Nanjing,210016Abstract:Theintegrationprinciplesofprocessplanningandjobshopschedulingwasanalyzed,whichcombinedCAPPmodulewithdynamicrollingwindowsschedulingbasedonperiodandevent-driven.Ithasbeenrealizedthattheintegrationoftwosystems.OneistheCAPPsysteminwhichtheprocedureisdesignedbysubsection.Theotherisjobshopschedulingwithdynamicrollingwindowsscheduling.Underthefoundationofsettingupintegrationmodule,thesimplegeneticalgorithmwasimprovedbycombininggeneticalgorithmwithsimulatedannealing.Ahighefficiencymixedgeneticalgorithmwasproposed.So,theintegratedsystemcanadapttocontinuousprocessinginachangingenvironmentandfinishthedisposalintime,andreducingredesignofprocessplanninginlargescaleduetooutburstevents.System’sfeasibilityandvaliditywasvalidatedbyanexample.
Keywords:jobshopscheduling;combinedgeneticalgorithm;CAPP;integrationmodule
0 引言
为适应当今的制造环境,实现计算机集成制造,实施企业资源管理,必须将从产品设计到车间控制的各种各样的制造功能模块进行集成。其中,
收稿日期:2005—10—13
基金项目:国家自然科学基金资助项目(59990470)
CAPP决定了零件的制造加工路线,在工程设计和
产品制造之间起到“桥梁”作用,是计算机集成制造
系统中的关键。生产调度是生产制造系统的另一功能模块,它负责将制造资源分配给由工艺加工计划所决定的零件加工工序,以满足加工性能指标。因此,调度受到工艺加工计划和制造资源的双重制约。如果工艺加工计划不与生产调度进行集成,那
参考文献:
[1] 刘飞,雷琦,宋豫川.网络化制造的内涵及研究发展
opmentSystems[J].Computer-aidedDesign,2001,33(7):545Ο559.
[5] BullingerHJ,WarschatJ,FischerD.RapidProd2
uctDevelopment-anOverview[J].ComputersinIndustry,2000,42(2/3):99Ο108.
(编辑 张 洋)
作者简介:杨煜俊,男,1980年生。广东工业大学机电工程学院讲师、博士。研究方向为PDM、CAPP、信息集成。陈新度,男,
1967年生。广东工业大学机电工程学院副教授。陈 新,男,1960年生。广东工业大学机电工程学院教授、博士研究生导师。
趋势[J].机械工程学报,2003,39(8):1Ο6.
[2] HelanderMG,JiaoJianxin.ResearchonE-prod2
uctDevelopment(ePD)forMassCustomization[J].Technovation,2002,22(11):717Ο724.
[3] TangDunbing,EversheimW,SchunG.ANew
GenerationofCooperativeDevelopmentParadigmintheToolandDieMakingBranch:StrategyandTechnology[J].RoboticsandComputer-integratedManufacturing,2004,20(4):301Ο311.
[4] SimonS,StevenJF,WalidK.AFoundationfor
InteroperabilityinNext-generationProductDevel2
万 立,男,1963年生。华中科技大学机械科学与工程学院教授、博士研究生导师。
・40・
基于混合遗传算法的动态车间调度系统的研究———鞠全勇朱剑英
么计算机集成制造就不能有效地工作。由于生产车间环境的变化,大约有30%的工艺加工计划在实施时需更改[1],这些更改往往只由调度人员进行,没有专业工艺人员参加,势必造成加工质量与加工效率的下降。
无论是工艺加工计划的制定,还是生产调度,都必须在各自一个很大的解空间中进行最优解的搜寻。如果一个经优化的工艺加工计划在生产调度时并没有被遵循,那么就不可能产生最优的生产结果。将工艺加工计划和生产调度进行集成,寻优就可以在一个统一的解空间进行,这样不仅可以为两者的集成构造一个统一的基础,而且可省去大量重复性的工作[2],这对提高生产效率和缩短生产周期具有重要影响。
合起来,采用了工序分段设计的CAPP系统和扩展事件再调度策略的生产调度系统的集成。如图1所示,ERP系统根据生产订单,将任务交由CAD系统设计后,由CAPP系统根据静态资源生成多条
1 生产工艺与调度系统集成的研究
将工艺加工计划和生产调度进行集成的思想是近20年才形成的。Nasr等[3]针对具有可选择工艺加工路线的生产车间,提出了两种算法来求解平均流动时间最小的调度。选择机床设备的同时也决定了工艺加工路线。Zhang[4]探讨了将工艺加工计划和生产调度进行集成的问题,提出了一个基于分布式工艺加工计划概念上的集成工艺计划模型。这个集成系统由三个模块组成:工艺加工计划模块、生产调度模块和决策判断模块。从有关文献可以分析得出,常见的集成方案主要有以下三种[4]:非线性工艺规划(nonlinearprocessplanning,NLPP)、闭环工艺规划(closed-loopprocessplan2ning,CLPP)和及时工艺规划(just-in-timeprocessplanning,JTPP)。非线性工艺规划需要生成所有可能的工艺规划,所以当规模较大时会出现组合爆炸问题,导致很难在可以接受的时间内得到满意的解。闭环工艺规划较好地考虑到车间的实时资源状态,但由于对实时状态的数据处理速度要求很快,如果每次调度都全部进行一次工艺路线的生成和工序设计,则实时性也不易做到。及时工艺规划采用分层处理的思想,符合人脑的思维习惯,但这种方法缺乏从整体上用CAPP生成的工艺规划来集成生产调度,局限于过分低层的作业规划。这些集成模型的最大不足在于没有把CAPP和PPC(productionplanningandcontrol)的集成问题放在工厂控制结构中进行系统研究[5]。
图1 集成系统框图
较为宏观的可行工艺路线,制造执行系统则根据交
货期、车间制造资源等动态信息,进行生产任务的分派与调度,即运用混合遗传算法(GASA)找出当前最优工艺路线。然后根据工序分段设计思想和再调度周期T,只对当前周期T内的工序进行详细设计,剩余工序等待在以后的再调度周期内进行详细设计[6]。生产调度模块主要针对再调度周期内的工序按照一定的调度策略和混合遗传算法进行生产调度,同时监测事件的发生并对之进行分类,然后将分类信息传给集成系统控制模块。集成控制模块主要起协调和控制作用。当接到突发事件后,根据不同的事件类型控制系统执行不同的CAPP子模块,使之进行工艺计划的调整,并控制
车间调度模块,根据调整的工艺路线完成对再调度周期内工序的调度。
3 基于周期和事件驱动的滚动窗口调度
为了解决车间动态环境下的调度问题,本文采用基于周期和事件驱动的滚动窗口技术来实现生产调度[7]。周期驱动适合资源的静态再调度,而事件驱动适合资源经常变化的动态再调度。当某一突发事件(新的紧急事件到达、交货期紧急提前、关键设备发生故障、关键设备修复或其他事件)出现时,立即进行再调度,否则采用周期性的再调度。
滚动窗口调度策略中的优化区间是工件窗口,即将工件分成三个集合[8]:可得工件集、窗口工件集和已加工完成工件集。如图2所示,当一个工件
・41・
2 生产工艺与车间调度系统集成模型
本文从生产一线实际情况出发,将CAPP模块与基于周期和事件驱动的滚动窗口调度有机地结
中国机械工程第18卷第1期2007年1月上半月
的到达时间已知时,该工件加入可得工件集,并等待进入窗口工件集。当一个工件的所有工序完毕后,该工件从窗口工件集进入已完成加工工件集。当有突发事件产生或到达预定调度周期时刻,即根据生产状况预先确定的时间间隔,就可把可得工件集和窗口工件集中未加工结束的工件集中起来,重新选择工件进入窗口工件集。工件进入窗口工件集的依据就是工件加工的紧迫度值(交货期与生产周期的比值)。
k=0。
(4)判断算法收敛准则是否满足。若是,转步
骤(12);否则令i=0,转步骤(5)。
(5)随机选择染色体与种群中的最优染色体进行交叉运算,产生两个新染色体。若新染色体目标值优于c*,则更新c*和最优调度;否则保持
c和最优调度。令i=i+1。
*
(6)若i(7)保留原始种群和新产生的所有染色体中Pn个最佳个体。
(8)对所有个体进行变异操作,保留Pn个最
佳个体作为SA的初始种群,并及时更新c*和最
图2 工件在各工件集中的流动
工件进入窗口工件集后,即可用混合遗传算法
进行优化调度,以确定在当前时间段处于窗口零件集中零件的最优调度。
优调度。
(9)对种群中的各个个体均进行定步长抽样的模拟退火操作,以概率min(1,exp(-Δ/tk))接受后代,及时更新c*和最优调度,其中Δ为新的染色体目标函数值之差。(10)令k=k+1,然后进行退温操作,tk=λtk-1,λ∈(0,1),并返回步骤(4)。
(11)输出该次仿真所得的最优解。再次进行优化否。若是,则转步骤(2);否则转步骤(12)。
(12)输出多次优化的统计结果,并结束算法。
4 结合遗传算法和模拟退火算法的混合遗传算法(GASA)
为使集成系统适应连续加工过程中复杂的环境变化,并高效地完成实时处理,车间调度算法的可行性和效率起着关键作用。尽管常用的遗传算法(GA)具有种群并行搜索能力,在总体上把握了进化的方向,但其局部搜索能力较差,容易出现早熟现象。算法混合的思想是提高GA搜索效率和搜索质量的有效手段,如在GA中嵌入局部搜索算法则能改善其局部搜索能力,嵌入基于知识的启发式方法则能将一些问题相关的信息融入到GA的全局搜索中,进而增强GA的整体搜索能力[9]。
本文提出了结合遗传算法(GA)和模拟退火算法(SA)的混合遗传算法(GASA),将两种算法有机结合,可形成优化机制的融合和优化结构的互补。对两种算法进行混合,有利于丰富优化过程中的搜索行为,增强全局和局部意义下的搜索能力和效率。此外,SA算法采用串行优化结构,而GA算法采用群体并行搜索,两者相结合,能够使SA成为并行SA算法,提高其优化性能;同时,SA作为一种自适应变概率的变异操作,增强和补充了GA的进化能力。
混合遗传算法(GASA)的算法流程如下:(1)初始化算法参数(种群数目Pn、退温速率λ、迭代次数m等)。
(2)根据基于操作的编码规则随机产生初始种群。
(3)解码计算各染色体对应调度的目标值,令最优值c*为当前种群中最优染色体的评价值,
・42・
5 应用实例与结果分析
某生产车间有四种不同类型的零件Ji(i=1,2,3,4);每一零件的批量是5个,且加工工序都是3道,每道工序均有3种选择方式。各种零件的
到达时刻分别为60、80、95和100。这里研究的动态环境有:在时刻18,第4种类型的零件突然到达;在时刻25,第2台机床损坏;在时刻31,第2种类型的零件订货期从80提前到65;在时刻40,第2台机床被修复。各类零件的加工时间及
上下料时间如表1所示,不同类型的各个零件的到达时间见表2。
表1
加工时间/上下料时间表
零
工序机床1机床2机床3机床4机床5机床6上料下料件零1-1件1-2
1
1-3
21345
3
4
6
4
13
9
6
1
37
94
53
39
512
334
55
277
11
4
2
4
0.20.10.20.10.40.30.30.20.40.30.40.30.30.20.30.20.30.20.40.30.40.30.50.4
零2-1件2-2
2
2-3
零3-1件3-2
3
3-3
零4-1件4-2
4
4-3
基于混合遗传算法的动态车间调度系统的研究———鞠全勇朱剑英
表2
零件号
11(A)12(B)13(C)14(D)15(E)
零件的到达时间表
到达时间
232151026
到达时间
819282035
零件号
21(F)22(G)23(H)24(I)25(J)
零件号
31(K)32(L)33(M)34(N)35(O)
到达时间
42801317
零件号
41(P)42(Q)43(R)44(S)45(T)
到达时间
2024291634
数为100;交叉率为016;变异率为0105;退温速率λ取019;循环迭代次数为100。经计算机运算,这批零件的最终加工完毕时刻为98135,而且没有零件发生延误。图3中用“XX”标识机床2在加工这道工序过程中发生了故障,集成系统立即进行重新调度,安排这道工序到其他机床上加工。此后机床2无法加工任何零件,直到40时刻,机床2被修复,集成系统重新优化工艺与调度,实现生产周期的最短。如采用传统的静态调度算法,加工过程中一旦发生机床故障等情况,不仅会造成生产周期加长,甚至生产线停工。调度Gantt图如图3所示。
注:15(E)表示第1类零件中的第5个零件,后图中用“E”来表示,如E2表示第1类零件中的第5个零件的第2道工序。
依上述算法,采用的分派规则是SPT和EDD(earliestduedate)。调度的评价指标是综合考虑最短生产周期(makespan)和最少延误时间(tardiness)。遗传算法的主要参数如下:种群个
图3工序和机床的分配
[5] 吴德中,严隽琪,金烨,等.CAPP与PPC集成研究
仿真结果表明,基于混合遗传算法基础之上
的生产工艺与动态调度集成系统,可以高效地完成连续加工过程中复杂的环境变化和实时处理,减少突发事件造成的工序大范围的重新设计,与传统静态优化调度相比,优越性明显。该集成模型有很强的可扩展性,完全可以应用到更多生产资源(如机器人、运行小车等)受制约的情况。
参考文献:
[1] DetandJ,KruthJP,KampenaersJ.AComputer
AidedProcessPlanningSystemthatIncreasestheFlexibilityofManufacturing[R].IPDES(EspiritProject2590)Workshop,1992.
[2] WeiTan.IntegrationofProcessPlanningand
Scheduling———AReview[J].JournalofIntelligentManufacturing,2000,11:51Ο63.
[3] NasrN,ElsayedEA.JobShopSchedulingwithAl2
ternativeMachines[J].InternationalJournalofProductionResearch,1990,28(9):1595Ο1609.[4] ZhangH.IPPM-APrototypetoIntegrateProcess
PlanningandJobShopSchedulingFunctions[J].AnnalsofCIRP,1993,42(1):513Ο518.
现状与进展[J].上海交通大学学报,1999,33(7):
912Ο916.
[6] LeeH,KimSS.IntegrationofProcessPlanning
andSchedulingUsingSimulationBasedGeneticAl2gorithms[J].590.
[7] ChurchL,UzsoyR.AnalysisofPeriodicandEvent
-drivenReschedulingPoliciesinDynamicShops[J].theInternationalJournalofComputerIntegrat2edManufacturing,1992,5(3):153Ο163.
[8] 孙志峻.智能制造系统车间生产优化调度[D].南
TheInternationalJournalofAd2
vancedManufacturingTechnology,2001(18):586Ο
京:南京航空航天大学,2002.
[9] 王凌.车间调度及其遗传算法[M].北京:清华大学
出版社,2003.
(编辑 张 洋)
作者简介:鞠全勇,男,19年生。南京航空航天大学机电学院博士研究生。主要研究方向为智能制造系统。发表论文10余篇。朱剑英,男,1936年生。南京航空航天大学机电学院教授、博士研究生导师。
・43・
