柔性作业车间多目标动态调度模型及算法研究

柔性作业车间多目标动态调度模型及算法研究

0动态调度研究存在的问题生产计划是先进制造领域研究的基础和重要问题。其主要任务是确定相关设备中零件的加工顺序和加工时间，并确保所选生产目标的最佳数量。其中,柔性作业车间调度问题(FlexibleJob-shopSchedulingProblem,FJSP)因为突破了机器约束和加工工艺路线固定的限制,每道工序可在一台或多台调度机器上加工,加工过程有多条工艺路线可供选择,相比传统的作业车间调度更接近生产实际,所以生产中较广泛地采用。然而,实际柔性作业车间调度常会发生机器故障、来料延迟和紧急插单等不确定因素,此时就需要考虑在上述情况发生时进行柔性作业车间动态调度的问题。NELSON等在1977年最早提出了动态调度问题,它将动态调度过程分成多个连续的静态区间,然后对上述调度区间进行优化以达到每个区间内最优,从而适应动态环境,但他们只研究了单目标问题,且未对调度性能及影响调度性能的因素进行分析。张超勇研究了原材料延期到达、加工和装配延误、紧急工件加入等情况下的动态调度,但主要针对传统非柔性车间调度问题进行研究,未考虑工艺路线的柔性化和机器资源的可选性,同时也缺乏对影响调度性能的因素进行分析。潘全科研究了待加工工件的选取原则和再调度周期的确定方法,但对动态调度执行流程描述的不够清晰,也未分析所提方法的调度性能和影响调度性能的因素。BRANLE研究了工件随机达到的动态调度,以合并早期空闲时间的方法来提高调度性能,但未考虑机器故障和周期性再调度问题,且以合并早期空闲时间的方法对提高调度性能较为有限。LIU使用工件选取规则缩短工序加工的空闲时间,以达到提高调度性能的目标,但未考虑工艺路线的柔性化和机器资源的可选性,且主要针对单目标调度问题。吴秀丽在未考虑机器故障和周期性再调度情况下,研究了面向交货期性能最优的柔性作业车间动态调度问题,且未对影响调度性能的因素进行分析。GEORGE研究了考虑机器故障和加工路径可选的车间动态调度,并以作业平均延迟和平均加工成本对调度性能进行评估,但未考虑加工任务临时变动和周期性再调度时的情形,同时也缺乏对影响调度性能因素的分析。ADIBI研究了工件随机到达和机器故障等动态事件的处理,并以最小化加工时间和工件延期对调度性能进行评估,却未分析影响调度性能的因素;同时,也未考虑周期性再调度、工艺路线的柔性化以及机器资源的可选性等约束条件。FATTAHI研究了考虑新机器加入、新工件到达和工件处理时间变化的柔性车间动态调度,却未考虑机器故障和周期性再调度;同时,以最小化完工时间度量调度的有效性,评价目标较为单一;以偏差来度量调度的稳定性后未对影响调度性能的因素进行分析。GHOLAMI在未考虑周期性再调度、工艺路线的柔性化和机器资源的可选性的情况下,研究了机器故障的柔性车间动态调度,并分析了不同故障参数对调度的影响,但缺乏对影响动态调度性能因素的全面研究。基于上述分析,针对工艺路线柔性化和机器资源可选情况下的柔性生产车间,本文以最小化工件的拖期惩罚和和最小化最大完工时间为目标,在考虑机器故障、加工任务临时变动及周期性再调度等动态生产环境的基础上,建立了柔性作业车间多目标动态调度模型;然后,结合滚动窗口再调度技术,提出了基于周期和事件驱动的自适应多目标柔性动态调度算法,并分析了机器故障发生方式和交货期变更等扰动因素及再调度周期窗口的大小对调度性能的影响,以此确定影响生产进度的主要因素,从而科学地指导实际生产。1现状及约束和约束条件柔性作业车间动态调度问题描述为:n个工件{J1,J2,…,Jn}在m台机器{M1,M2,…,Mm}上加工,任一工件Ji由一系列加工先后顺序确定的工序{Oij,j∈(1,2,…,ni)}组成,ni表示加工工件Ji的工序总数,Mij表示可以加工工件i的第j道工序的机器集合Mij⊆{1,2,…,M},(1≤i≤n,1≤j≤ni),工序Oij可使用Mij中的任一机器加工,加工时间随所选择机器的不同而不同。然而,工件生产加工过程中常存在机器故障、加工任务临时变动及周期性再调度等问题。因此,本文正是基于上述问题,为每道工序选择最合适的机器,确定每台机器上各工件工序的最佳加工顺序及开工时间,使工件生产周期和拖期惩罚等性能指标达到最优。为使研究更具可操作性,本文设定以下假设条件:(1)所有机器设备零时刻都可用。(2)工序在可供选择的机器上的加工时间已确定。(3)出现再调度时,不受影响的正在加工的工序继续加工,直到本工序完成。本文从实际生产出发,分别从生产周期和拖期惩罚两个方面建立优化目标。生产周期用工件的最小化最大完成时间f1度量,拖期惩罚用f2度量。f1=min{max(Ci|i=1,2,…,n)};(1)f2=min(n∑i=1Τi)=min(n∑i=1βi×max(0,Ci-Di));(2)f2=min(∑i=1nTi)=min(∑i=1nβi×max(0,Ci−Di));(2)F=f1+βf2。(3)工件Ji的完工时间为Ci,交货期为Di,如果Ci>Di,则工件Ji受到拖期惩罚,工件Ji的单位拖期Ti的惩罚系数为βi(i=1,2,…,n)。在加工过程中,柔性作业车间多目标动态调度还须满足以下约束条件:Cijk-Ci(j-1)g≥Pijk+Lijk+Uijk,j≠1,Xijk=1;(4)Cijk-Pijk≥Lijk+Uijk;(5)∑kXijk=1,k∈Μij‚∀i,j;(6)∑kXijk=1,k∈Mij‚∀i,j;(6)Cijk-Cabk≥Pijk+Lijk+Uijk,Yabijk=1,Xijk=1,Xabk=1;(7)式中:Cijk为工件i的第j道工序在机器k上的完成时间;Pijk为工件i的第j道工序在机器k上的加工时间;Lijk为工件i的第j道工序在机器k上的装载时间;Uijk为工件i的第j道工序在机器k上的卸载时间;Xijk为工件i的第j道工序在机器k上的加工的判别条件,如果是,则Xijk=1,否则Xijk=0;Yabijk为机器k上加工工序b和j的顺序判别条件,如果工件a的工序b先于工件i的工序j在机器k上加工,则Yabijk=1,否则Yabijk=0;STijk表示工件i第j道工序在机器k上的开始加工时间。其中:式(4)表示工件i的第j道工序必须在第j-1道工序完成后才能开始;式(5)表示工件i的第j道工序在机器k上加工时间不为负;式(6)表示工件i的第j道工序只能选择在可选机器集合中的一台机器上加工;式(7)表示任一确定时刻,机器k不能同时加工任意两个不同的工件,也不能同时加工任意两道不同的工序;式(8)～式(9)表示工件i的第j道工序完成时间约束。上述目标函数、假设和约束条件可保证动态调度结果的可行性和有效性,为生产活动提供技术支持。然而,动态调度问题除了要证明调度的可行性和有效性以外,还需要求解偏差度来验证调度的稳定性。偏差度是静态调度和再调度两种方案中加工周期之差的绝对值与动态调度加工周期之比。ST和ST′分别表示静态调度与再调度方案加工周期。Deviation=|ST-ST′|/ST′。(10)2车间的调度计划,应根据分配高度确定车间生产动态调度是将车间生产看成一个动态过程,工件依次进入待加工状态等待加工,一旦所需资源得到满足就进入加工状态,接受系统加工,同时完成加工的工件又不断离开。而静态调度则认为所有工件的信息和车间状态都是明确的,一旦调度计划确定,车间就按计划生产。与静态调度比较,动态调度不仅需要考虑初始状态,还需要考虑工件交货期改变及机器故障等多种突发事件、急件或计划工件不断加入等动态因素。由此可知,动态调度与静态调度最大的不同就在于动态调度不但能适应动态的加工环境,而且当发生机器故障、工件交货期改变等突发事件时,可以迅速地做出响应,对加工工件实施再调度,以适应变化了的生产环境。鉴于此,本文提出了柔性作业车间多目标动态调度问题,并设计了下述调度策略:动态调度窗口规划、动态调度实施的类型选择及动态调度算法设计。2.1工件的再调度控制实现动态调度首先要定义工件集,标注工件的处理状态。本文将所有工件分成未加工工件集SU、待加工工件集Sa、正在加工工件集SW和己完成工件集SC四个子集。调度开始前,所有工件信息都保存在未加工工件集中,随着生产准备工作的完成,根据工件的优先级别选择一定数量的工件调入待加工工件集等待加工,如果能够加工该工件工序的机器设备资源得到释放,则立即将该工件从待加工工件集转入正在加工工件集;如果某一时刻正在加工某工件的设备出现故障,则立即启动一次再调度,将该工件连同该时刻保存到待加工工件集中,等同待加工工件,享有优先安排加工的机会,当故障机器完成维护后,将该工件从待加工工件集转入到正在加工工件集,直到该工件所有工序加工完成以后,将该工件从正在加工工件集转入到己完成工件集;当一个再调度周期到来时,从未加工工件集中选择一定数量的工件调入待加工工件集中,与待加工工件集里原先剩余的工件一起进行下一轮调度优化。2.2事件与周期驱动的混合再调度动态调度有事件驱动再调度、周期性再调度和基于周期与事件驱动的混合再调度三种类型。事件驱动调度是指当出现一个使系统状态发生变化的事件时立即进行再调度。在车间的生产加工过程中存在着各种突发事件,为及时应对这些突发事件,必须立即进行调度。周期性再调度是每隔一段生产周期进行一次再调度。在每个生产周期开始前进行再调度,当生产周期开始后按调度结果执行。周期性再调度使生产保持一定的稳定性,是实际生产中采用最多的调度方法。事件驱动再调度能处理突发事件,但对未来事件缺乏预见能力,没有整体的概念,周期性再调度可提高生产的稳定性,但无法处理突发事件。事件与周期驱动的混合再调度综合了两者的优点,既可以较好地响应实际的动态环境,又能保持一定的稳定性,因此本文重点研究基于事件和周期驱动的混合再调度,其流程如图1所示。上述流程描述为:在调度过程中,当有机器故障、工件交货期改变等事件发生时,实施一次再调度;当一个再调度周期ΔT结束时,启动一次再调度,即将加工完成的工件迁出工件调度窗口,修改可利用设备项,将交货期提前的工件或待加工的工件迁入工件调度窗口,使调度窗口中工件的数目保持一定的平衡,并对调度窗口中的工件实施再调度;当又有再调度事件发生时,重复上述过程,直到全部工件加工完成。在考虑基于事件和周期驱动的混合再调度策略的情况下,为实现本文所提出的柔性多目标作业车间动态调度的整体目标最优,同时保证每批进入调度窗口中的工件取得最优值,目标函数(式(3))可描述为:minY=maxk∈SΜ(Τk-ts,x)+βi∑i∈Sxmax(0,Ci-Di);(11)minY=maxk∈SM(Tk−ts,x)+βi∑i∈Sxmax(0,Ci−Di);(11)Τk=tkr+∑j∈Κxk(Ρjk+Ljk+Ujk)+ts,x;(12)Tk=tkr+∑j∈Kxk(Pjk+Ljk+Ujk)+ts,x;(12)ts,x+1=mini∈Sx(te+ts,x+ΔΤ)ts,x+1=mini∈Sx(te+ts,x+ΔT)。(13)2.3染色体的机器编码及其加工自适应多目标柔性动态调度算法(AdaptiveMulti-ObjectiveFlexibleDynamicSchedulingAlgorithm,AMOFDSA)操作流程如图2所示,具体步骤如下:步骤1初始化调度次数x=0,开始调度的时间ts,x=0,给定窗口中工件的最大数目W,并初始化Sa,SW,SC,SU。步骤2对当前工件窗口中的工件实施以下操作:(1)初始化STk=ts,x和进化代数t=0。(2)实施染色体编码,产生初始种群P(popsize)。编码是实施优化的首要和关键问题,目前已经提出了基于工序、优先表、工件对关系、工件、完成时间、优先规则、非连接图、机器和随机键9种JSSP编码方法,但上述方法均属单一编码方式,在求解多目标柔性车间动态调度优化问题时,存在编码困难和解码繁琐的问题。为此,本文设计了基于工序与加工机器相融合的两层编码方法。第一层采用基于工序的表达法进行编码,即给所有同一工件的工序指定相同的符号,然后根据它们在给定染色体中出现的顺序加以解释。如在3×3问题中,假设给定的染色体为,其中1代表工件j1,2代表工件j2,3代表工件j3,因为每个工件有三道工序,所以每个工件在一个染色体中刚好出现三次。第二层是该工件的相应工序所使用的机器编号,如工序Oij的机器编码为可以加工Oij的机器集合Mij中的任一机器。图3即为一个染色体样例,其中工件3的第1道工序在机器集合M31中的任一台机器上加工,工件2的第1道工序在机器集合M21中的任一台机器上加工,工件2的第2道工序在机器集合M22中的任一台机器上加工,依次类推。这种两层编码方式能满足工艺路线柔性化和机器资源可选的约束条件,任意基因串的置换排列始终代表一种可行的操作程序,总能保证产生可行调度。此外,它具有编码空间小、避免死锁、半Lamarckian特性和2类解码复杂性等特点。(3)如果t≺T,则从种群中取出第Z(1≤Z≤popsize)个染色体并转入(4)。若t=T,则输出Fi和窗口中工件的最终调度结果,转步骤3。(4)从可用机器集Mij中为工件i的第j道工序选择合适的机器k,选择的原则是在不与其他工件加工过程冲突的情况下,选择具有最短加工时间的机器,以保证工件满足交货期要求。(5)如果是工件i第1道工序,则按照式(8)计算工件i的第1道工序在所选机器k上的加工时间,如果非第1道工序,则令工件i的第j+1道工序开始时间等于工件i的第j道工序的完成时间,按照式(9)计算第j+1道工序的加工时间,直到工件i的所有工序都已经加工完成后,按照式(3)计算出工件i的适应度值。Ρi=Fi/popsize∑i=1FiPi=Fi/∑i=1popsizeFi(14)ΡC={ΡC1-(ΡC1-ΡC2)(f-favg)fmax-favgf≥favg,ΡC1f＜favg。(15)(8)自适应变异操作。变异率的自适应调整公式为:步骤3在按照步骤2的调度逻辑加工的过程中,实时判断是否发生扰动、再调度周期时刻是否到来。如果出现扰动,判断是由于机器故障引起的还是由于工件交货期变更引起的:如果机器发生了故障,则立即启动一次再调度,取消机器该时刻工件工序的加工,计算该工序的剩余加工时间,将该工序连同该时刻及剩余加工时间保存到待加工工件集中,等同待加工工件,享有优先安排加工的机会,当故障机器完成维护后,将该工件从待加工工件集转入到正在加工工件集进行加工,直到该工件所有的工序加工完成;如果此刻工件交货期发生变更,则立即启动一次再调度,判断该工件是否加工完成:如果已经加工完成,则继续执行其他工件的加工;如果未完成,则在保证目标函数式(3)较优的前提下,优先安排该工件的加工。如果此时刻一个再调度周期到来,则立即启动一次再调度,从未加工的工件集中选择一定数量的工件调入待加工工件集中,与待加工工件集中原先剩余的工件一起进行下一轮调度优化,如果此时还未到再调度周期则进入周期再调度等待状态,直到再调度周期时刻到来时开始实施周期再调度。总之,出现机器故障、工件交货期改变等事件就启动一次再调度,当再调度周期时刻到来时,同样需要启动一次再调度,转步骤4。步骤4及时更新信息,将已经完成的工件从SW中迁出放到SC中;将工件从待加工工件集Sa中迁入工件调度窗口SW中,使调度窗口中工件的数目保持一定的平衡。如果所有工件都已加工完成,则输出动态调度结果,否则,转步骤3。其中:W为工件窗口中的最大工件数;t为进化代数;STk为机器k可以开始加工的时间。在式(15)和式(16)中:fmax为群体中最大的适应度值,favg为每代群体的平均适应度值,f表示交叉的两个个体中较大的适应度值,f*表示要变异的个体的适应度值。2.4周期调度时间间隔相关参数描述如下:minfinishT为n个工件中的最小完成时间;minindex为对应该工件在群体中的索引指数;T_item为周期调度时间间隔;T_count为周期调度次数;Mark_TorE为周期或事件驱动的标志;α为足够大的正整数;due_date(i)=γ为工件i的交货期改变到γ时刻;T_event1,T_event2,T_event3分别为机器故障时刻、故障修复时刻和工件交货期更改时刻。2.5faut4.fact以机器故障为例,说明当有机器故障事件发生时如何实施再调度。相关参数描述如下:TT为工件job_id的第procedure_id(job_id)个工序的机器开始加工时间;T_item为周期调度时间间隔;fault_machine(1)、fault_machine(2)、fault_machine(3)分别为故障机器标志、故障发生时刻和故障修复时刻;num_procedure为每个工件的工序数目;individul为染色体;job_id为工件标志;procedure_id(job_id)为工件job_id的工序标志;machine_id为机器标志。3动态调度周期对再调度加工周期的影响以某公司的柔性制造单元动态调度为例进行仿真,制造单元共有3台加工设备,加工10类典型零件,每类零件又包括3道工序,零件类型、交货期,加工时间等信息如表1所示。卸载时间和安装时间都为2s,根据合同拖期惩罚条款和实际生产状况取拖期完成惩罚系数β=1,群体规模为100,再调度周期ΔT=50s,最大进化代数T=100,交叉率计算参数PC1=0.9,PC2=0.6;变异率计算参数PM1=0.1,PM2=0.001;生产过程中考虑以下扰动:①机器1在时刻70出现故障,时刻90修复;②在时刻120工件10的交货期由原来的250提前到时刻180。经计算得到函数值变化曲线图、最佳的静态调度甘特图和动态调度甘特图如图4～图6所示。由图4～图6可知,随着进化代数的增加,函数最小值和平均值逐渐稳定,在不考虑扰动因素和再调度周期的情况下,静态调度输出甘特图的加工周期是212s,在考虑再调度周期、机器故障、交货期提前的情况下,动态调度输出甘特图的加工周期是217s。如果没有实施动态调度,则由图5可知,在时刻70,工件7的第2道工序的加工被暂停,同时造成工件2的第2道工序的加工延迟,必然造成加工周期远大于动态调度加工周期217s,可见动态调度在扰动出现时能大幅缩短加工周期。由图6可知,在工件加工的整个过程中共发生了3次事件再调度、5次周期再调度和2次扰动事件完成再调度。为验证算法性能,本文所提算法与文献所提的多目标遗传算法(Multi-ObjectiveGeneticAlgorithms,MOGA)进行对比分析,文献算法参数设置如下:再调度周期ΔT=50,群体规模为100,最大进化代数为100,交叉率为0.9,变异率为0.1。两种算法分别运行20次,输出结果如表2所示。由输出结果可以看出,AMOFDSA在解优化的程度上都有很大的优越性。为全面认识扰动因素和再调度周期对动态调度性能的影响,通过变更再调度周期窗口的大小、机器故障发生方式和工件交货期来研究动态调度性能的变化。在每种扰动状态下,分别运行程序20次,得到的研究结果如表3所示。表中故障机器(1:70-90)表示机器1在时刻70发生故障、在时刻90修复;交货期变更(10:250-180)表示工件10的交货期由时刻250提前到时刻180,依次类推;¯f1和¯f2表示程序运行20次得到的平均加工周期和平均拖期惩罚;ˉt表示程序运行20次的平均时间消耗。由表3可知,在相同的ΔT和机器故障方式下,工件交货期变更从(10:250-180),(9:195-160)到(6:160-150)的过程中,平均加工周期不断变长,偏差度、平均拖期惩罚和平均时间消耗不断提高,这种变化说明交货期较短的工件的交货期变更扰动对动态调度性能有重要影响;在相同的ΔT和工件交货期变更方式下,故障机器从(1:70-90),(2:70-90)到(3:70-90)变化的过程中,平均加工周期整体趋势不断变长,偏差度、平均拖期惩罚和平均时间消耗不断提高,这种变化说明加工任务比较均匀的机器(图4中机器3上的工件加工时间比较均匀)的故障扰动对动态调度性能有重要影响;在相同的故障机器和工件交货期变更方式下,ΔT从50～100变化的过程中,平均时间消耗呈现降低趋势,平均加工周期、偏差度及平均拖期惩罚出现不稳定现象,这种变化说明对该问题应该存在一个合适的再调度周期,可以有效提高机器利用率,从而对动态调度性能产生重要影响。4未来研究方向本文采用多目标柔性动态调度算法,基于周期和事件驱动的混合再调度策略,对柔性作业车间多目标动态调度进行了研究,得到以下结论:(1)基于工序与加工机器的两层染色体编码方法,可实现加工工序与该工序可选机器集合对应关系的编码,能够同时优化FJSP中的工艺路线和加工顺序。(2)与静态调度相比,动态调度能够跟踪车间加工环境的变化,从而对加工过程中发生的突发事件迅速做出反应。(3)基于周期与事件驱动的混合再调度同时具有事件驱动再调度和周