一种基于混合鲸鱼群算法求解柔性作业车间调度的方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109784603A(43)申请公布日2019.05.21(21)申请号201811359927.9(22)申请日2018.11.15(71)申请人长安大学地址710064陕西省西安市雁塔区南二环路中段(72)发明人蔡宗琰栾飞李富康(74)专利代理机构西安弘理专利事务所61214代理人韩玙(51)Int.Cl.G06Q10/06(2012.01)G06N3/00(2006.01)权利要求书3页说明书8页附图3页(54)发明名称一种基于混合鲸鱼群算法求解柔性作业车间调度的方法(57)摘要本发明公开了一种基于混合鲸鱼群算法求解柔性作业车间调度的方法，首先定义柔性作业车间调度的编码方式为两段式随机键编码，然后采用转换机制进行映射转换；定义适应度函数求解总加工时间最短为优化目标；然后采用鲸鱼群算法，对柔性作业车间调度问题中的参数以及鲸鱼种群初始化，初始化分为随机生成工序的排序方案和采用改进遗传算法的遗传变异方式生成与工序排序方案对应的较优的机器分配方案，进而产生较优的初始种群；计算各调度方案的适应度值，寻找并保留最好的调度解；最后输出最优的调度解及其对应的适应度函数值，即为所求最优调度方案，本发明解决了现有柔性作业车间调度问题中表现出的求解精度不高、收敛速度较慢的问题。CN109784603ACN109784603A权利要求书1/3页1.一种基于混合鲸鱼群算法求解柔性作业车间调度的方法，其特征在于，具体按照以下步骤实施：步骤1、定义柔性作业车间调度的编码方式为两段式随机键编码，然后采用转换机制进行映射转换；步骤2、定义适应度函数，以求解总加工时间最短为优化目标；步骤3、采用鲸鱼群算法，对柔性作业车间调度问题中的参数以及鲸鱼种群初始化，首先对鲸鱼群算法中个体位置变量元素的上下界ε、声源强度ρ0、当前迭代次数t、最大迭代次数M参数进行设定；种群初始化分为两步进行，第一步随机生成工序的排序方案，第二步采用改进遗传算法的遗传变异方式生成与工序排序方案对应的较优的机器分配方案，进而产生较优的初始种群；步骤4、计算各调度方案的适应度值，寻找并保留最好的调度解S*；步骤5、输出最优的调度解S*及其对应的适应度函数值，S*即为所求最优调度方案。2.根据权利要求1所述的一种基于混合鲸鱼群算法求解柔性作业车间调度的方法，其特征在于，所述步骤1中转换机制具体按照以下步骤实施：a、调度方案向个体位置的转换：i)机器选择：按照下式将工序可选机器集中序号转换成个体位置向量元素值：x(i)＝[2m/(s(i)-1)](n(i)-1)-m,s(i)≠1其中：x(i)表示个体位置向量的第i个元素；s(i)表示元素i对应工序可以选择的机器个数；n(i)∈[1,s(i)]表示选定机器在可选机器集里面的序号。如果s(i)＝1，则x(i)在[-m,m]内任意取值。ii)工序排序：首先生成[-m,m]内的一组随机数，并按升序排列ROV规则为每个随机数赋予一个唯一的ROV值，使每个ROV值对应一个工序，然后根据工序的编码顺序对ROV值进行重排，重排后的ROV值所对应的随机数顺序即为个体位置向量中各元素的值。b、个体位置向量向调度方案的转换：i)机器选择：按照所述a中调度方案向个体位置的转换中的公式的逆操作执行，由此获得机器的编号：ii)工序排序：首先使每一个元素编号对应一个唯一的编码中的工序顺序及位置元素，然后根据ROV规则对位置元素进行升序排列，此时的ROV值对应元素编号进而构造工序排序方案；3.根据权利要求2所述的一种基于混合鲸鱼群算法求解柔性作业车间调度的方法，其特征在于，所述步骤2具体按照以下步骤实施：步骤2.1、柔性作业车间调度的问题模型FJSP描述如下：假设M为加工设备的数量，N为待加工工件数量，P为工序数，I为所有设备的集合；Ieg代表工件e的第g道工序的可用设备集合，Je为工件e的工序数，x为所有工件的加工次序，Segk表示工件e的第g道工序在设备k上加工的开始时间；Eegk为工件e的第g道工序在设备k上的加工结束时间；Tegk为工件e的第g道工序在设备k上的持续加工时间，且k∈Ieg则有Eegk2CN109784603A权利要求书2/3页＝Segk+Tegk；Ep表示最后工序的完工时间；MS表示所有工件的最后完工时间；当工件i的第j道工序和工件e的第g道工序在同一台设备上执行，若工序j先于工序g加工时，Qijeg＝1，否则Qijeg＝0；若工件e的第g道工序在机床k上加工，则Xegk＝1，否则Xegk＝0；若某FJSP共有S种可能的加工顺序，要求总的作业时间最短的加工排序，先求取每个加工顺序x(x∈{1,...,S})对应的作业时间；显然，顺序x中最后加工工序的完工时间即所有工件的最后