多目标柔性车间调度方法

基于SPEA的多目标柔性作业车间调度方法王暋云1暋谭建荣2暋冯毅雄1暋李中凯11.浙江大学流体传动及控制国家重点实验室,杭州,3100272.浙江大学CAD&CG国家重点实验室,杭州,310027摘要:研究了多目标柔性作业车间调度问题,构建了以制造工期、加工成本及交货期为目标函数的柔性作业车间多目标调度模型,应用改进的强度Pareto进化算法(SPEA)进行求解。在该算法中,引入模糊C-均值聚类(FCM)加快外部种群的聚类过程。采用约束Pareto支配和双层编码策略,一次运行就能够求得Pareto最优解集,并利用模糊集合理论的方法得到Pareto解的优先选择序列和选出一个最优解。最后,将该方法应用于某机械公司车间调度中,验证了该方法的有效性和适应性。关键词:柔性车间调度问题;多目标优化;SPEA;多目标决策方法中图分类号:TH166暋暋暋文章编号:1004—132X(2010)10—1167—06Multi-objectiveFlexibleJob-shopSchedulingBasedonStrengthParetoEvolutionaryAlgorithmWangYun1暋TanJianrong2暋FengYixiong1暋LiZhongkai11.StateKeyLaboratoryofFluidPowerTransmissionandControl,ZhejiangUniversity,Hangzhou,3100272.StateKeyLaboratoryofCAD&CG,ZhejiangUniversity,Hangzhou,310027Abstract:TosolveFJSP,amulti-objectiveFJSPoptimizationmodelwassetup,concernedwithtime,costanddeliverysatisfaction.TheoptimalsolutionswereobtainedbyusingimprovedSPEA.TheSPEAwasimprovedbyintroducingthefuzzyC-meansclusteringalgorithmtoacceleratetheclusteringprocedurewithintheexternalpopulation.WiththeconstraintParetodominationconceptandthetwo-levelrepresentationschema,aParetooptimalsetcouldbeachievedinasinglerun.ThenthepreferencesequenceofParetosolutionswasachievedandasolutionwasextractedasthebestcompromiseonebasedonsettheory.Thefeasibilityandvalidityoftheproposedalgorithmhavebeenprovedbytheresultsinaworkshopscheduling.Keywords:flexiblejob-shopschedulingproblem(FJSP);multi-objectiveoptimization;strengthParetoevolutionaryalgorithm(SPEA);multi-objectivedecisionmakingmethod收稿日期:2009—06—23基金项目:国家863高技术研究发展计划资助项目(2007AA04Z190);国家自然科学基金资助项目(50505044,60573175)0暋引言作业车间的调度问题一直是生产管理及组合优化等领域的热点之一。传统的作业车间调度(Job-Shopschedulingproblem,JSP)的目标通常是求解一组工件的工序在一组机器上的分配。柔性作业车间调度问题(flexibleJob-Shopschedulingproblem,FJSP)是传统JSP的扩展,FJSP与JSP的不同之处在于:它假定工件的一个工序可以在不止一台机器上加工,从而增加了一个将每个工序分配到可以加工它的某个机器上的路径选择问题,使得FJSP成为比JSP更加复杂的一类组合优化问题。由于工件的工序具有多个可选择的加工路径,更加符合实际的生产环境,因此研究具有柔性路径的作业车间调度问题具有重要的理论价值和应用意义。传统的FJSP研究主要集中在单目标调度上,近年来多目标FJSP问题由于更贴近实际生产需求而引起了人们更多的关注。多目标FJSP问题扩大了最优调度的搜索空间,而且需要满足更多约束条件,从而导致问题更加复杂,具有复杂性、约束多样性等特点。目前多目标柔性作业车间调度已有不少的研究成果:文献[1]建立了制造周期最短、机器总负荷和关键机器负荷最小的多目标仿真模型;文献[2]提出了一种改进遗传算法,采用了一种新的GOR编码、新的分类选择算子和改进的优先操作交叉算子集成设计方法;文献[3]提出带瓶颈移动的混合遗传算法求解多目标FJSP;文献[4]应用粒子群算法和禁忌搜索法求解多目标FJSP;文献[5]提出采用粒子群和模拟退火混合算法求解多目标FJSP。其中不少多目标优化的处理方法是采用线性加权的方式将多目标优化问题转换为单目标问题。多目标优化问题的特征之一是其解往往不止一个,而是一组在多个目标之间折衷的均衡解,即通常所说的·7611·基于SPEA的多目标柔性作业车间调度方法———王暋云暋谭建荣暋冯毅雄等Pareto最优解。解多目标问题的关键是找到数量足够多且分布均匀的具有代表性的Pareto解。多目标进化算法采用模拟生物进化的交叉、组合、变异策略及基于适应度的选择机制,一次运行就能够得到分布均匀且逼近Pareto最优前沿。其中,强度Pareto进化算法(strengthparetoevolu灢tionaryalgorithm,SPEA)[6]在进化过程中保留了外部种群,能够有效控制Pareto前沿中个体的数量及其分布,但是在执行外部种群的缩减操作时,随着问题规模的增大,层次聚类方法的运算效率显著降低[7],而模糊C-均值聚类(fuzzyC-meansclustering,FCM)[8]方法能够快速获得指定数目的聚类中心,具有较高的聚类效率,因此,本文将模糊C-均值聚类改进SPEA算法应用于柔性作业车间的多目标调度中。在满足加工能力、加工顺序、加工机器等约束前提下,对加工时间、加工成本和提前/拖期惩罚值多项目标进行优化,并使用基于集合理论的Pareto集选优机制排除人工选优的不确定因素。最后,通过项目应用,证明了改进的SPEA算法可以有效解决多目标柔性车间调度问题。1暋问题描述多目标FJSP问题可以描述为:设存在M个工件,在N台机器上进行加工。每种工件Mi存在Ji道工序,工件的工序是预先确定的,每道工序可以在多台不同的机器上加工,在不同机器上各工件的工序加工时间和加工费用不同。设tijk为工件i的第j道工序在机器k上加工的时间,Sijk为工件i的第j道工序在机器k上开始加工时刻,Eijk为工件i的第j道工序在机器k上的完工时刻,Di为工件i的最晚交货期,D曚i为工件i的最早交货期,ri为工件i提前完工的惩罚系数,wi为工件i拖期完工的惩罚系数,Rijegk表示在机器k上工件i第j道工序和工件e第g道工序的加工先后顺序,Xijk为决策变量,表示工件i的第j道工序是否选择在机器k上加工,则有:Rijegk=1暋工件i第j道工序和工件e第g道工序在同一机器k上执行,若工序j先于工序g0{其他Xijk=1暋若工件i第j道工序在机器k上执行0{其他与传统的车间调度模型相比,FJSP模型增加了决策变量Xijk,即工件的工序可以选择在哪台机器上加工,该变量的增加提高了调度系统的应变能力,同时也大大增加了模型求解的复杂程度。调度目标是为每道工序选择最合适的机器,以及确定每台机器上各工件工序的最佳加工顺序,使系统的总优化目标达到最优。加工过程还要满足以下假设条件和约束条件:(1)假设条件。栙工序一旦进行不能中断;栚所有机器一开始均处于空闲状态,在零时刻,所有的工件都可被加工;栛不同工件的工序之间没有先后约束,工件之间具备相同的优先级;栜各工件的准备时间和移动时间一起计入加工时间。(2)约束条件。栙顺序约束———工艺要求的同一工件相邻工序间的加工顺序不能颠倒,即Eijk-Ei(j-1)k-tijk曒0(1)1j曑Ji暋暋Xijk=Xi(j-1)k=1栚资源约束———同一机器k上一个加工任务完成后才能开始另一个加工任务,即Eegk-Eijk-tegk曒0(2)Xijk=Xegk=1暋暋Rijegk=1本文中面向柔性作业车间的多目标优化调度考虑包含3个优化目标的优化目标集{T,C,D},T、C、D分别表示制造工期、加工成本和工件提前/拖期完工的惩罚值。其对应的优化模型如下:(1)工件的制造工期T最短minT=maxk=1,2,…,NPk(3)式中,T为所有工件的最后完工时间;Pk为所有工件在机器k上的完工时间。式(3)表示在机器k上的完工时间取决于在其上加工的所有工件中最后一个工件的完工时间。工件的制造工期包括工件的等待时间和工件的每道工序加工时间。每道工序加工时间Td包括工序的准备时间Tdp和工序的作业时间Tdj。准备时间Tdp包括准备专用工装夹具、安装调整工装夹具模具、检验时间等,工序的作业时间Tdj即机器加工工件的实际作业时间。工序的加工时间Td=Tdp+Tdj。(2)加工成本C最低minC=min暺Mi=1暺Jij=1暺Nk=1CijkXijk(4)其中,Cijk表示第i个工件的第j道工序在第k台机器上的加工成本。加工成本可由工序费用来表示,工序费用指的是仅与加工机器有关的费用,产品材料费用的增减与加工机器无关或关系较小,所以不在工序费用之中考虑。工序费用Cd可分为机器成本Cdm和人工成本Cdh,其中机器成本Cdm包括机器的准备成本Cdp和作业成本Cdj,Cdm=TdpCdpt+TdjCdjt,其中Cdpt、Cdjt分别表示机·8611·中国机械工程第21卷第10期2010年5月下半月器单位时间的准备费用和加工费用。人工成本Cdh=aTdjCdht,由于工序的作业时间Tdj与工人实际工作时间可能不一致,故设a为调整系数。由上可知工序费用Cd的计算公式为Cd=TdpCdpt+TdjCdjt+aTdjCdht(3)提前/拖期完工的惩罚值D最小minD=暺Mi=1[rimax(0,D曚i-EiJik)]+暺Mi=1[wimax(0,EiJik-Di)](5)通过工厂日历、订单交货期和车间加工情况分析确定每个工件的最早交货期时间D曚i和最晚交货期时间Di,同时根据工件的交货优先级确定不同工件的提前惩罚系数ri和拖期惩罚系数wi。2暋优化算法FJSP多目标优化包括多个相互冲突目标同时优化,为了权衡生产管理的需要,需要得到Pareto最优解集而不是一个优化解。传统处理此柔性车间多目标调度优化问题的方法是通过权值的设定将多目标优化问题转化为单目标优化问题来解决的。为了获得多目标优化问题的Pareto最优解集,就必须求解一系列的单目标优化问题。强度Pareto进化算法保留外部种群存储运算过程中的非支配个体,基于Pareto支配计算个体适应度,并使用聚类方法缩减外部种群的数量,能够获得包含指定数目个体且分布均匀的Pareto前沿。因此,本文以SPEA算法为基础,引入模糊C-均值聚类算法加快外部种群的聚类缩减过程,并结合基于集合理论的Pareto综合选优机制,形成FJSP多目标优化方法。2.1暋算法概述2.1.1暋强度Pareto进化算法SPEA由Zitzler等[6]于1998年提出,它采用了协同进化规则的适应度分配策略和基于Pare灢to支配关系的小生境机制,和其他多目标进化算法相比具有更强的优化能力。T(n)表示在规模为n的问题中算法基本操作重复执行的次数,f(n)是n的某个函数,T(