不同生产方式下的随机调度方案研究

不同生产方式下的随机调度方案研究

0主要的计算方法公司在生产过程中的优化计划已成为提高公司生产效率的中心问题。在实际生产中,当加工时间不确定、机器故障等随机事件发生时,如何优化随机流水车间调度问题(StochasticFlowShopSchedulingProblem,SFSSP)已成为企业关注的焦点。确定性情况下的流水车间调度问题通常假设:①任务的每道工序的加工时间确定且已知;②交货期为确定值;③机器连续可用;④无突发订单。松弛其中的一项假设就会产生新的调度问题。文献以最小化完工时间(Makespan)为目标,研究了加工时间服从指数分布的2台机器流水车间调度问题;文献把文献的算法扩展到解决多机SFSSP问题。同时,机器突发故障会严重影响调度方案的有效实施,也是生产调度领域的一个研究热点。文献研究带有随机机器故障的流水车间调度问题,但规模限制在2台机器;文献同时考虑随机加工时间和随机机器故障2种随机因素,把带有随机故障的多机SFSSP分为一系列无故障调度问题,然后采用已有的无故障算法求解;文献对近几年随机调度问题的相关研究进行了综述。但是,以上对带有机器故障的SFSSP问题的研究都局限于一类生产车间,即机器一旦开始加工便持续运转到故障发生或所有生产任务结束。实际生产过程中,不同的生产车间,甚至同一个生产车间往往存在不同的机器工作方式:①机器一旦开始加工便持续运转到故障发生或所有生产任务结束;②机器只在加工任务时才运转。因此,对于不同机器工作方式下的故障应采用不同的规则。本文对此展开研究,探讨了不同机器工作方式下性能指标Cmax期望值的计算方法、故障计算规则及其对性能指标的影响,并进行分析比较;针对加工时间随机且机器随机故障、目标函数为最小化最大完工时间(Makespan)的SFSSP问题进行了研究,提出了不同流水车间随机调度的3种方法,采用启发式规则和遗传算法相结合的方法确定加工任务的最优排序。1机器的排列时间,有以下几种基本概念假定m台机器加工n个不同类型的任务,每个任务有m道工序,以相同的顺序在m台机器上加工,并且每个任务在每台机器上只加工一次;在同一时间,每台机器只能加工处理一个工序,某工序只能在一个机器上加工处理;任务的每道工序在每台机器上的加工时间为随机变量,机器故障发生时刻和修复时间也是随机变量,且它们都服从指数分布expλ,其期望1/λ为服从均匀分布的随机变量。相关参数的定义如下:m—机器总数;n—待加工任务总数;si—排在第i个位置的任务,i=1,2,…,n;S—任务排列集合,S={s1,s2,…,sn};p(i,j)—任务i在第j机器上的加工时间,相互独立的随机变量,i=1,2,…,n,j=1,2,…,m;Bj—机器j的连续可用时间,即机器j从开始(或修复后重新)运转到下次发生故障期间的运转时间,随机变量j=1,2,…,m;Rj—机器j的故障修复时间,随机变量j=1,2,…,m;t(i,j)—任务i在机器j上的开始加工时刻;c(i,j)—任务i在机器j上的完工时刻;c(i)—任务i在最后一台机器上的加工完成时刻;Cmax—所有任务的最大完成时刻;EX—随机变量X的期望值,例如,Ep(i,j)表示加工时间的期望值。当仅考虑加工时间随机时,对应于排列S的各个任务在每台机器上的完成时间描述如下:t(s1,1)=0;Ec(s1,1)=t(s1,1)+Ep(s1,1);Ec(s1,j)=Ec(s1,j-1)+Ep(s1,j-1),j=2,3,…,m;Ec(si,1)=Ec(si-1,1)+Ep(si-1,1),i=2,3,…,n;Ec(si,j)=max{Ec(si,j-1),Ec(si-1,j)}+Ep(si-1,j),i=2,3,…,n,j=2,3,…,m;Ec(si)=Ec(si,m),i=1,2,…,n。至于当每道工序的加工时间随机且机器故障随机时,对应于排列S的各个任务在每台机器上的完成时间将在第2章中详述。目标是最小化最大完工时间,即minECmax=max{Ec(si)|i=1,2,…,n}=Ec(sn)。以最小化最大完工时间(ECmax)为目标的SFSSP调度问题就是确定n个任务的加工顺序S*={s1,s2,…,sn},使得ECmax最小,其最优结果记作EC*max,即S*=arg{EC*max}。2机器的工序故障期望计算为合理地计算故障发生的期望时刻和相应的目标值ECmax,设计了3类计算规则,用以计算不同机器工作方式下的故障发生时刻,并计算任务i(i=1,2,…,n)在机器j(j=1,2,…,m)上的完工时间期望值。假设一个任务正在机器上加工时机器出现故障,修好后,被故障中断的任务的工序在原来已加工的基础上继续加工,其计算规则如下:假定在初始时刻,所有机器可用,且任务可以加工,有:t(s1,1)=0,Ec(s1,1)=t(s1,1)+Ep(s1,1);Et(si,j)=max{Ec(si-1,j),Ec(si,j-1)},i=2,3,…,n,j=2,3,…,m。情况1机器从加工第一个任务开始运转,一直运转到故障发生或所有任务结束,任意时刻都可能发生故障。机器j的故障时刻期望值为机器j的开机时刻期望值Et(s1,j)(或上次故障修复的时刻)与机器连续可用时间期望值EBj之和,j=1,2,…,m。任务i(i=1,2,…,n)在机器j(j=1,2,…,m)上的完工时间期望值计算如下:如图1所示,若故障发生在EA时刻,if(Ec(si-1,j)<=EAandEc(si,j-1)>EA)Ec(si,j)=Et(si,j)+Ep(si,j)+max{Et(si,j),EA+ERj}-Et(si,j)=max{Et(si,j),EA+ERj}+Ep(si,j);endif其中,如果max{Et(si,j),EA+ERj}=Et(si,j),说明故障可以在机器正常闲置时间内修好,因此这种故障不会影响生产。若故障发生在EB时刻,if(t(si,j)<=EBandEt(si,j)+Ep(si,j)>EB)Ec(si,j)=Et(si,j)+Ep(si,j)+ERj;endif这种故障导致任务i的第j道工序的完成时间后延Rj。情况2机器从加工第一个任务开始运转,一直运转到故障发生或所有任务结束,且机器只有在加工过程中才可能发生故障。当机器j的故障时间期望值存在于非加工时间区间[Ec(si-1,j),Ec(si,j-1)]上时,令故障时刻期望值等于Et(si,j),由此保证机器在非加工时间内不会出现故障,即不存在图1中的EA类故障时刻;当不属于区间[Ec(si-1,j),Ec(si,j-1)]时,机器的故障时刻期望值计算规则同情况1。任务i(i=1,2,…,n)在机器j(j=1,2,…,m)上的完工时间期望值计算方法如下:Lettemp=min{Ec(si-1,j),Et(si,j)};if(temp<=EBandEt(si,j)+Ep(si,j)>EB)Ec(si,j)=Et(si,j)+Ep(si,j)+ERj;endif情况3机器只在加工任务时才运转,且机器故障时刻仅与总的加工磨损时间有关,机器故障只可能发生在图1中的EB类时刻点。容易理解,机器j(j=1,2,…,m)的累计工作时间达到机器连续可用时间EBj时,所对应的时刻就是一个期望发生的故障时刻。任务i(i=1,2,…,n)在机器j(j=1,2,…,m)上的完工时间期望值计算方法如下:不失一般性,假设时刻EB是机器j的第x次故障点,把上一次(第x-1次)机器j发生故障时正在其上加工的任务的号码记作Q,令aj=∑k=Q+1,Q+2,…,Q+i-1Ep(sk,j),bj=∑k=Q+1,Q+2,…,Q+iEp(sk,j),j=1,2,…,m;if(aj<=EBandbj>EB)Ec(si,j)=Et(si,j)+Ep(si,j)+ERj;endif根据上述3种情况计算得到的Ec(si,j),可求得任务i(i=1,2,…,n)的完工时间为Ec(si)=Ec(si,m),且Ecmax=Ec(sn)。由此可见,对于具有相同期望连续可用时间EBj(j=1,2,…,m)的机器,不难发现:(1)情况3的机器j(j=1,2,…,m)故障间隔时间最大因为情况3中的机器只在有任务时才运转,没有任务时停止。(2)情况3的EC*max最小因为故障间隔时间越大,任务被中断的概率越小,故障对性能指标ECmax的影响越小。因此,对于其他两种情况,情况3的EC*max最小。(3)情况1中机器故障影响EC*max增大的程度比情况2中小情况1能够在机器的正常空闲时间内修好或修理EA类故障,若故障可以在机器正常空闲时间内修理好,则该故障对生产不造成影响,可以忽略不计。而情况2则把EA类故障后移变为EB类故障,修理时间完全占用机器的正常工作时间。显然,情况1机器故障影响EC*max增大的可能性比情况2小。由此得出如下性质:EC*max(情况3)≤EC*max(情况1)≤EC*max(情况2)。3启发式规则与智能优化相结合一般情况下,以最大完工时间Cmax为性能指标,机器数≥3的流水车间调度已经是NP难题,机器数的增加会加剧算法的复杂性。精确求解的方法只能局限于小规模问题,实际应用价值不大。启发式规则与智能优化相结合的方法能在较短的时间内求解大规模问题的近优解。针对具有随机机器故障且加工时间随机的SFSSP,本文采用启发式规则和遗传算法相结合的方法,确定所有任务的最优加工排序。(1)任务号的生成采用自然数编码。用一段顺序码表示任务处理的优先级顺序,如3-1-2,数字表示任务号,排在最前的任务优先级最高。初始种群由两部分生成,一部分随机产生,另一部分按照经典NEH排序规则生成(NEH被认为是至今最好的多项式构造型算法)。产生的初始种群随机生成排序,使种群具有多样性,且搜索结果必然优于已知的NEH排序。(2)调度排序是当机器正常工作时间的一个重要误直接把目标值ECmax作为适应值。目标值不仅与任务的排序有关,而且受随机的加工时间和机器故障影响,好的调度排序能够把这些随机因素对目标值的影响降到最小,例如故障发生在机器正常空闲时间内且可以在正常空闲时间内修复时,这种故障不影响生产。(3)遗产活动选择操作采用锦标赛选择策略,交叉操作采用双位置次序交叉,变异操作采用互换变异(SWAP)。(4)精英保留和新种群保留种群数量为一个定值N,采用精英保留与随机选择相结合的策略。把父代和子代放到一起,统一评估。选择其中目标值较小的M(1≤M<N)个个体无条件地保留到新种群里,即精英保留;然后从所有个体中随机选取N-M个体进入新种群,从而在保留较好个体加快收敛速度的同时又不失种群的多样性。(5)终止条件设定最大迭代代数为n×m。4最优调度方案选取用VisualC++6.0编程实现上述算法,对随机变量服从指数分布的情况进行实验。实验中,机器数分别取3,7,10,任务数分别取7,20,50,100。每道工序的加工时间和每台机器的故障等随机变量服从指数分布expλ时,其期望1/λ服从均匀分布。任意时刻,一台或多台机器都有可能发生故障。随机加工时间、故障周期和修复时间期望的取值范围如表1所示。遗传算法中,取种群规模为20,交叉概率为0.6,变异概率为0.1。根据表1中每种机器数与任务数的组合情况,对情况1～情况3和不考虑故障情况的流水车间调度分别运行20次,随机产生20组初始数据,计算结果取平均值(EC∗max¯¯¯¯¯¯¯¯¯¯)(ECmax*¯),并给出各自的标准方差(如表2)。在表2中,j为机器号,p(*,j)为每个任务在机器j上的随机加工时间。20次随机计算中最小的EC*max(限于篇幅,仅列出3台机器、7个任务的排序结果)对应的最优排序结果如表3所示。实验结果给出了3种不同情况下最优调度排序的EC∗max¯¯¯¯¯¯¯¯¯¯ECmax*¯值(如表2)及其部分排序结果(如表3),表明了带有机器故障的流水车间最优调度方案与不考虑故障情况下的结果不同,且不同生产方式下流水车间的最优调度方案也各不相同。这是因为,某工序正在相应的机器上加工时,若机器发生故障并在一定时间范围内修复,这个过程可以看作是延长了被中断任务的该道工序的加工时间,而任务的各个工序加工时间的长短直接影响其在最优排序中的位置,因此,考虑机器故障的最优调度方案与无故障情况下的结果是不同的。机器随机故障且加工时间不确定是生产中经常发生的事情,显然,不考虑故障的调度方案已经不能有效地指挥生产。同时,表2中的计算结果表明,EC∗max¯¯¯¯¯¯¯¯¯¯ECmax*¯(情况3)≤EC∗max¯¯¯¯¯¯¯¯¯¯3)≤ECmax*¯(