多目标柔性作业车间调度方法研究

华中科技大学博士学位论文多目标柔性作业车间调度方法研究姓名：王晓娟申请学位级别：博士专业：工业工程指导教师：高亮;李培根2011-05-19摘摘摘摘要要要要制造业是国民经济的重要组成部分。实际生产中的优化问题通常是多属性的，一般是对多个目标的同时优化，而且各个目标之间通常是不一致的，比如产品质量和生产成本往往是两个互相冲突的目标。此外，加工时间、完工时间和产品交货期等通常都是不确定的参数，实际生产过程中还存在着一些不确定的干扰因素，比如机器故障、原材料延迟到达、紧急订单的插入或者订单取消等突发事件，人们迫切需要对实际生产中的车间调度问题进行深入和广泛的研究，以更好地指导生产。本文正是在这样的背景下，结合实际生产调度问题所面临的多目标、参数不确定和动态性，对多目标柔性作业车间调度问题及其扩展进行了研究，并取得了一些有意义的研究成果。本文首先对单目标的柔性作业车间调度进行研究。将遗传算法“适者生存”进化准则融入禁忌搜索算法，将遗传算法的全局搜索能力和禁忌搜索算法的局部搜索能力相结合，提出了混合遗传禁忌搜索算法解决单目标的柔性作业车间调度问题。在遗传算法进化过程中，针对柔性作业车间调度问题的特点，设计了一种扩展的基于工序的编码及其产生活动调度的解码机制，并根据染色体的结构提出有效的交叉操作，IPOX交叉操作和一种新多点交叉操作MPX。对于遗传算法进化过程中产生的个体，应用禁忌搜索算法进行改进。将Balas和Vazacopoulos提出的邻域结构扩展到柔性作业车间调度问题，设计了禁忌搜索算法的邻域结构。运用提出的混合遗传禁忌搜索算法求解基准测试问题并与其他方法进行比较，验证了算法的有效性。根据现实制造系统中关注较多的最大完工时间、平均流经时间、总拖期时间、机器总负荷、瓶颈机器负荷和生产成本等性能指标，建立了多目标柔性作业车间调度模型。在上述遗传算法的编码、交叉和变异等基本操作的基础上，提出了一种新的多目标遗传算法。在该多目标遗传算法里，采用了快速排序方法以提高算法构造Pareto最优解集的效率；采用了NSGA-II的精英保留策略，并针对NSGA-II在精英保留策略上的不足，引入了分布函数；此外，还采用了免疫和熵原理以维持进化种群的多样性。通过测试基准和模拟实际生产的算例，验证了算法的可行性和有效性；并利用层析分析法从一组Pareto最优解中选出最优妥协解。针对实际制造车间调度中，加工时间和交货期不确定的特点，本文结合模糊集的相关理论，建立了多目标模糊柔性作业车间调度模型。基于上述多目标遗传算法，求解了具有模糊加工时间和模糊交货期的多目标柔性作业车间调度问题，并通过算例测试，验证了算法的有效性。针对实际制造车间调度具有动态性的特点，提出了一种基于滚动窗口的动态调度优化策略，该策略采用基于周期和事件驱动的再调度机制将调度过程分成连续静态调度区间，在每个区间内用前面提出的多目标遗传算法进行优化调度。基于滚动窗口技术和多目标遗传算法，以交货期、最大流经时间、最大完工时间以及初始调度的偏离程度为性能指标进行同时优化。为了适应复杂多变的动态环境和保持生产的稳定性，提出了一种人机协同的调度机制。通过对算例进行测试，验证了该方法的可行性。在算法研究的基础上开发了多目标柔性作业车间调度原型系统，对原型系统的功能和效果进行了描述。最后，对全文所做的工作进行了总结，并对未来的研究方向进行了展望。关键词：柔性作业车间调度；多目标遗传算法；模糊集；动态调度AbstractAbstractAbstractAbstractManufacturingsectorisanimportantpartandthemainforceofnationaleconomy.However,severalobjectivesmustbeconsideredsimultaneouslyinthereal-worldproductionsituationandtheseobjectivesoftenconflictwitheachother.Foranenterprise,differentdepartmentshavedifferentexpectationsinordertomaximizetheirowninterests.Moreover,astheinternationalcompetitionbecomingmoreandmoreintenseandthegrowingofpersonalizedproductdemandbythemarket,processtime,completiontime,deliverytimeandsoonintherealproductionhavebeenunabletodescribeasdeterminedparametersastheywereusedtobe.Meanwhile,theremaybesomedynamicevents,suchasmachinemalfunction,latearrivalofrawmaterials,emergencyinsertionorcanceloforderandsoon.Inthissituation,peopleneedtoresearchonschedulingproblemsunderuncertaintyimmediatelyandwildlytoguidetherealproduction,notonlythetheorybutalsoitsapplication.Inthisbackground,combinedwiththeuncertainanddynamicoptimizationproblemsintherealplantandproduction,mainresearchofthisthesisisaboutmulti-objectiveflexiblejobshopschedulingproblem.Andsomemeaningfulconclusionsandresultsarepointedoutfromthisresearch.TheFlexibleJob-shopSchedulingProblem(FJSP)isanextensionoftheclassicaljob-shopschedulingproblem(JSP).Thispaperpresentsahybridgeneticalgorithmandtabusearch(GATS)whichincorporatestheprincipleof“thesurvivalofthefittest”fromgeneticalgorithm(GA)intotabusearch(TS)tosolvetheFJSP.AccordingtothecharacteristicsoftheFJSP,anextendedoperation-basedrepresentationwhichsimultaneouslydescribesthesequenceofoperationsandtheassignmentofoperationstomachinesisappliedtorepresentsolutionforGATS,andsolutionsareconstructedusingaprocedurethatgeneratesactiveschedules.Twoeffectivecrossoverandmutationoperatorsareproposedtoadapttothechromosomestructure.AfterindividualsofGAareobtained,TSisappliedtoimprovethesesolutions.TheneighborhoodstructuresofTSaredesignedbyextendingpropositionproposedbyBalasandVazacopoulostoFJSP.Thehybridalgorithmistestedonasetofstandardinstancetakenfromtheliteratureandcomparedwithotherapproaches.Thecomputationresultsvalidatetheeffectivenessoftheproposedalgorithm.Animprovedmulti-objectiveevolutionaryalgorithm(MOGA)isproposedforsolvingthemulyi-objectiveFJSP.Firstly,themulti-objectiveFJSPoptimizationmodelisputforward,whichthemakespan,themeanflow-time,totaltardiness,totalworkloadofmachines,workloadofthecriticalmachineandproductioncostwidelyconcernedincomplexmanufacturingsystemareconsidered.Inordertoensureconvergenceandthediversityofthesolutions,animprovednon-dominatedsortinggeneticAlgorithm(NSGA-II)isproposedandtheimmuneandentropyprincipleisusedtokeepthediversityofindividualsandovercometheproblemofprematureconvergence.TheproposedMOGAisevaluatedonsomerepresentativeinstancesandthecomparisonwithotherapproachesinthelatestpapersvalidatestheeffectivenessoftheproposedalgorithm.Finally,theanalytichierarchyprocess(AHP)approachisusedtoselectthesatisfiedsolution.Fortheundeterminedenvironment,fuzzysetisintroducedtosolvemulti-objectiveFJSPwithundeterminedprocessingtimeandduedate.BasedontheimprovedMOGAproposed,wesolvedthemulti-objectiveflexiblejobshopschedulingproblemwithfuzzyprocessingtimeandfuzzyduedate.Thecomputationalresultsvalidatetheeffectivenessoftheproposedalgorithm.MOGAbasedonrolling-horizonprocedurewasproposedtosolvethemulti-objectivedynamicFJSP.Inthisprocedure,periodicandeventdrivenreschedulingstrategieswereemployedandthedynamicschedulingproblemwasdecomposedintoaseriesofcontinualandstaticschedulingproblems,thentheimprovedMOGAwasappliedtooptimizeeachofthestaticschedulingproblems.Accordingtothecharacteristicsofthedynamicschedulingp