混合流水车间调度问题的分布估计算法

混合流水车间调度问题的分布估计算法

0混合模型优化方法混合融资流程规划问题（hybridflexrundproceduralprocedural模型，hfsp）具有很强的设计背景。广泛应用于化工、冶金、纺织、机械、半夏、物流、建筑和造纸领域。hfsp可分为大量生产、制造、设备制造、传输和合成过程中的规划问题、网络服务和集装箱运输能力等。HFSP是传统的流水车间调度与并行机调度的综合,具有更大的求解难度,即使是两阶段HFSP也是NP-hard问题。因此,HFSP的研究具有重要的学术意义和应用价值。传统的HFSP按并行机类型可分为三类:(1)相同并行机HFSP,即每一阶段上同一工件在任意一台并行机器上的加工时间相同;(2)均匀并行机HFSP,即每一阶段上同一工件在任意一台并行机器上的加工时间与该台机器的加工速度成反比;(3)不相关并行机HFSP,即每一阶段上同一工件在任意两台并行机器上的加工时间互不相关,而取决于工件与机器的匹配程度。本文讨论相同并行机混合流水车间调度问题(HybridFlow-shopSchedulingProblemwithIdenticalParallelMachine,HFSP-IPM)。早期HFSP-IPM的求解方法主要是精确算法和启发式方法。精确算法在理论上能得到最优解,但其计算时间难以接受,通常只适于小规模问题。启发式方法可在较短时间内构造解,但难以保证质量。随着计算智能的发展,近些年求解HFSP-IPM的智能方法得到了研究。文献提出一种结合启发式规则的遗传算法(GeneticAlgorithm,GA),以解决第一阶段机器的分配和排序问题,从第二阶段起采用先到先加工的方法进行排序,进而生成可行调度。文献提出两种模拟退火(SimulatedAnnealing,SA)方法,采用不同的分配规则对工件在机器上进行分配,同时提出了一种计算解下界的方法。文献提出一种基于局部和全局信息素评价的蚁群算法(AntColonyOptimization,ACO),并采用串行调度策略进行求解。文献提出一种基于克隆选择原则和亲和力的人工免疫系统(ArtificialImmuneSystem,AIS)算法求解HF-SP-IPM,随后文献提出了一种改进的GA,在更短的计算时间内得到了更好的优化结果。文献将量子旋转门与免疫算法结合,提出了量子免疫算法(Quantum-inspiredImmuneAlgorithm,QIA)。分布估计算法(EstimationofDistributionAlgorithm,EDA)是一种新颖的基于统计学习理论的群体进化算法,近些年得到了广泛的研究和发展。PBIL(populationbasedincrementallearning)是最早的EDA模型,随后按模型的复杂度和变量间的相互关系相继提出了变量无关EDA、双变量相关EDA及多变量相关EDA。目前,EDA已在特征选择、癌症分类、模式匹配、神经网设计、护理调度、结构设计、故障评判、混沌控制和路径规划等问题上得到了研究与应用。文献针对不相关并行机HFSP的特征设计了特定的解码方法,并提出了一种分布估计算法。HFSP-IPM与不相关并行机HFSP在特征上有差异,不相关并行机HFSP中每阶段的同一工件在不同机器上的加工时间与机器相关,文献针对不相关并行机HFSP的特征设计的特定解码方法和算法无法有效求解HFSP-IPM。因此,本文针对HFSP-IPM设计改进的启发式解码规则,提出一种混合解码方法,设计描述问题解空间分布的概率模型及其更新机制,进而提出一种有效的EDA,最后通过数值仿真和算法比较验证算法的有效性。1混合动力车间的规划1.1第1道工序加工时间记Ji为工件序号,i=1,2,…,n,n为工件总数;mj为每一阶段的机器数,j=1,2,…,S,S为阶段总数;ti,j为工件Ji第j道工序的加工时间;si,j为工件Ji第j道工序的开始加工时间;ei,j为工件Ji的第j道工序的加工完成时间;Ci为工件Ji的加工完毕时间;Cmax=max{C1,C2,…,Cn}为最大完成时间。1.2工件加工和工序HFSP-IPM可描述为:n个工件在流水线上进行S个阶段的加工,各阶段至少有一台机器且至少有一个阶段存在并行机,同一阶段上各机器加工同一工件的加工时间均相同,在每一阶段各工件均要完成一道工序,但各工件的每道工序可在相应阶段上的任意一台机器上加工,已知工件各道工序的处理时间,要求确定所有工件的排序以及每一阶段上机器的分配情况,使得最大完工时间(Cmax)最小。HFSP-IPM通常假设:工件一旦开始加工便不可中断;一台机器同一时刻只能加工一个工件;一个工件同一时刻只能在一台机器上加工;工件可在每阶段的任意一台机器上加工。图1给出了问题的一个图例。1.3hfsp-ipm多阶段并行调度算法HFSP-IPM的数学模型描述如下:其中:式(1)为调度性能指标;式(2)确保每个优先级的位置只能对应一个工件;式(3)确保每个工件只有一个优先级位置;式(4)表示任一阶段每个工件只能在一台机器上加工;式(5)表示同一阶段上的工序完成时间和开始时间的关系;式(6)表示同一工件不同工序间的先后制约关系;式(7)表示同一阶段调度排列中排位越靠前的工件开始处理的时间越早;式(8)表示同一阶段分配在同一机器上的工件排位靠后的工件必须等靠前的工件加工完毕后才可进行加工,当处于不同位置的工件不在同一阶段的同一机器上加工时L为一个大数,以保证不等式恒成立。一方面,因为HFSP-IPM属于NP-hard问题,随着工件数和阶段数的增加,问题的解空间迅速增大,所以需要高效的求解方法;另一方面,HFSP-IPM存在多阶段并行机加工的特点和特殊工艺约束,需要有效的解码策略来产生具体调度方案。因此,研究解决HFSP-IPM的有效算法很有价值,而有效的编码解码策略和高效的求解方法尤为关键。2概率模型更新EDA是一种新型的基于概率模型的群体进化算法,它不采用传统GA的交叉和变异操作,而是从群体宏观的角度建立一个概率模型描述解在空间的分布,采用统计学习手段更新概率模型的参数,使其可以表征解空间中优良解所在的区域,然后对概率模型随机采样产生新种群,进而实现种群的进化。标准EDA的流程如下:步骤1初始化种群。步骤4随机采样生成新群体。步骤5判断终止条件是否满足。若满足,则输出优化结果;否则,转步骤2。可见,概率模型是EDA的核心,EDA通过概率模型及其更新来描述解分布以及种群的整体进化趋势。根据具体问题的不同,需设计合适的概率模型及其更新机制。3hfsp-ipmeda的解3.1工件号的排列种群中每一个体对应问题的一个解,个体采用排列编码,长度为n,即取所有工件序号的排列作为一个个体,工件号在排列中的位置表示其在第一阶段的加工顺序。例如,对于有4个工件的问题,个体{2,3,1,4}表示在加工的第一阶段这4个工件的加工顺序依次为2,3,1,4。3.2hfsp的解码过程对于一个编码排列,按照机器分配规则依次将所有工件分配到各阶段的机器上,形成一个可行调度并计算目标值,该过程称为解码。HFSP的解码过程可分为工件的排序和机器的分配两部分。针对HFSP-IPM的特点,本文提出了两种不同的解码规则,分别是改进的置换解码(improvedPermutationScheduling,iPS)和改进的排列解码(improvedListScheduling,iLS),进而提出了一种混合解码方式。3.2.1fam规则的计算iPS的工件排序方面,每个阶段严格按照编码确定工件安排的先后顺序,即各阶段工件的排列顺序均相同。机器分配方面,首先要判断工件Ji在阶段j上第k台机器上的最早允许加工时间ak,然后选择ak值最小的机器作为Ji的加工机器。原有的最先空闲机器(FirstAvailableMachine,FAM)规则认为,最早允许加工时间为机器k的释放时间rk和Ji在阶段j-1上的完成时间Ci,j-1之间的最大值,即ak=max(rk,Ci,j-1),其中Ci,0=0。图2a为某3工件2阶段问题编码序列{1,2,3}所对应的甘特图,其中1-1表示工件1在第一阶段的操作,以此类推。在所有工件第一阶段的加工完毕后,第二阶段首先将工件1分配在机器3上加工。接下来,在确定工件2的机器分配时,FAM规则判断a3=7,a4=2,因此选择机器4加工工件2,最终解码的目标值为8。但是,若将工件2安排在工件1之前在机器3上加工,则最终的解码目标值为7,如图2b所示。记r′k为机器k上Ci,j-1之后的空闲间隔大于ti,j的间隔开始时间,选择ak=min(rk,r′k)值最小的机器进行加工,可以在一定范围内改进解码质量。对于最早允许加工时间相同的机器,FAM规则随机选择其中一台机器进行加工,显然这种规则无法保证编码与目标值一一对应,也无法保证解的质量。图3a为某4工件2阶段问题编码序列为{1,2,3,4}所对应的甘特图。第二阶段的机器分配过程中,工件3在机器3和机器4上的最早允许加工时间相同。若选择机器3加工工件3,则工件4在机器4上加工,最终解码的目标值为8;若选择机器4加工工件3,在分配工件4的加工机器时,由于机器3的释放时间更早,最终解码的目标值为7,如图3b所示。因此,对于ak相等的机器,选择ak-rk值最小的机器进行加工,可以最大限度地保证工序的紧凑性,从而可以在一定范围内改进解码质量。基于以上分析,提出如下iPS规则:步骤2根据各工件在编码序列中的顺序,依次计算ak=min(rk,r′k),选择ak值最小的机器作为Ji的加工机器,更新工件Ji在第j阶段上的加工完成时间及机器k的释放时间;若存在多台ak值最小的机器,则选择ak-rk值最小的机器进行加工。步骤3j=j+1。步骤4重复步骤2~步骤3,直到所有阶段加工完成。3.2.2确定剩余加工时间与置换解码规则相比,排列编码的区别是工件排序部分。原有的排列解码规则采用如下策略:第一阶段(j=1)按照编码确定工件安排的先后顺序,后续阶段基于先到先加工方式确定操作序列,即对于j(j>1)阶段的所有工件,按照前一阶段的完成时间排定顺序,前阶段先完成的先加工,若几个工件在前一阶段的完成时间相同,则随机确定这些工件的加工顺序。通过实验仿真分析发现,剩余加工时间越长的工件,对于总的完工时间影响越大,将其先加工可以在一定范围内改进解码质量。图4a是10工件5阶段问题实例甘特图的一部分,其中第三阶段工件4和工件9的完工时间相同,工件4的剩余加工时间为15,工件9的剩余加工时间为14。若第四阶段先加工工件9,则总的完工时间为70;若先加工工件4,则总的完工时间为69,如图4b所示。基于以上分析,提出如下iLS规则:步骤1根据各工件在编码序列中的顺序,选择rk值最小的机器作为Ji的加工机器,更新工件Ji在第一阶段上的加工完成时间及机器k的释放时间rk;j=2。步骤2根据各工件在第j-1阶段的完成时间确定其在第j阶段的加工顺序,先完成的工件先加工;若存在完成时间相同的工件,则选择剩余加工时间长的工件先加工;若它们的剩余加工时间也相同,则随机选择一个工件先加工。步骤3根据各工件的加工顺序依次计算ak=min(rk,r′k),选择ak值最小的机器作为Ji的加工机器,更新工件Ji在第j阶段上的加工完成时间及机器k的释放时间rk;若存在多台ak值最小的机器,则选择ak-rk值最小的机器进行加工。步骤4j=j+1。步骤5重复步骤2~步骤4,直到所有阶段加工完成。3.2.3混合解码方式iPS和iLS两种解码规则都是实现编码序列到调度方案的映射,但二者并无包含关系,因此可提出一种混合解码方式,即对于一个确定的编码序列,分别采用iPS和iLS规则解码,然后选择最大完工时间早的调度方案,相应的完工时间作为调度指标值。3.3初始种群的增加为了尽可能获得解空间的分布信息以构建概率模型,必须保证初始种群的分散性,因此,算法采用随机初始化的方法产生Psize个个体作为初始种群,并根据混合解码方式计算各个体的目标值。3.4工件号的确定EDA通过采样概率模型产生新种群,因此一个合适的概率模型可以帮助EDA获得良好的性能。在此采用一个n×n维的随机矩阵P表示解空间分布的概率模型,其中pij表示工件j在解的第i位上或之前出现的概率,即在第一阶段的加工顺序不晚于i的概率。矩阵P从数值上反映不同工件的加工优先关系:对于若干优良解构成的群体,pij越大,表示工件j在第i位上或之前出现的频率越大,说明该工件提早加工会提升解的质量。算法选择初始种群中目标值最小的SPsize个个体作为优势群体,并基于优势群体初始化随机矩阵P。用pij(l)表示第l次迭代中随机矩阵P的元素,算法按如下方式初始化随机矩阵P:其中Isij(l)是如下定义的示性函数:可见,算法根据初始种群中优势群体在解空间中的分布来初始化概率模型。在随后的每次迭代中,基于随机矩阵P进行采样产生新群体。在产生一个新个体时,从第1位到第n位顺序采样,确定每个位置的工件号。对于待确定的第i个位置,采用轮盘赌的方式选择一个工件号,工件j被选择的概率为pij。由于已选择的工件j不能在i之后的位置出现,令pkj(k>i)=0。如此反复,直至产生Psize个新个体。为了使概率模型尽可能准确地表示解空间的分布及群体的进化趋势,采样产生新种群之后,算法选择目标值最小的SPsize个个体作为优势群体,并基于优势群体采用如下增量学习的方法更新随机矩阵P,其中α(0<α<1)为学习速率。3.5概率模型更新根据上述设计,给出求解HFSP的EDA流程,如图5所示。可见,算法根据概率模型采样生成新种群,并基于新种群中的优势群体更新概率模型。本文设置最大进化代数作为算法的终止条件。3.6概率模型的计算复杂度采样概率模型产生新个体时,按照轮盘赌方式依次采样产生n个位置的工件号,其计算复杂度为O(n2)。考虑种群规模,产生新种群的复杂度为O(n2Psize)。选择优势群体更新概率模型时,对种群中个体快速排序的计算复杂度为O(PsizelogPsize),更新矩阵P的计算复杂度为O(n(SPsize+n))。综上所述,算法关键操作复杂度与工件数的平方成正比,因此EDA的计算复杂度并不大。4混合解码规则在其他问题上的性能对比在此选取国际上的标准测试问题进行性能测试,并与AIS、GA和QIA等代表性算法进行比较。问题规模从10工件5阶段到15工件10阶段不等,且并行机的数量也不完全相同。例如,j10c5a2问题表示是10个工件、5阶段a类问题之一。EDA的参数设置如下:种群规模Psize=25,优势群体SPsize=5,学习速率α=0.1,最大进化代数为1000。与文献[12-14]相同,算法独立运行10次,得到Cmax的最优值及其相对问题下界的百分偏差如表1~表4所示。从表1~表4可见,对于部分问题EDA所得的最佳调度只能通过iLS规则或iPS规则生成,其余大部分问题的两种解码规则均能生成最佳调度。这表明iLS规则和iPS规则不能互相替代,也说明本文所提混合解码方式是有效的。另外,从表1~表4可见,EDA的性能优于其他三种现有算法。对于10工件5阶段问题,EDA与GA性能相当,求解12个c类和d类问题时EDA的性能优于QIA,求解c3问题时EDA的性能优于AIS;对于10工件1