一种适用于工件离散制造的大规模生产调度方法转让专利

申请号 : CN202211109198.8

文献号 : CN115438970B

文献日 :

基本信息:

PDF:

法律信息:

相似专利:

发明人 : 张俊辉唐红涛刘广洋左林王磊李志勇

申请人 : 韶关液压件厂有限公司

摘要 :

本发明提供了一种适用于工件离散制造的大规模生产调度方法,该方法将鲸鱼优化算法与遗传算法混合后得到自适应多种群混合算法(HWOAGA),以此来对大规模生产调度问题进行求解,通过将种群总体划分为若干个不同类型的子种群来减少问题的复杂性,增加了子种群的多样性,避免了算法局部极小值的过早收敛,并对不同的子种群采用不同的进化策略,从而生成合理的调度方案,有利于订单的及时交付以及生产的精细化管控。

权利要求 :

1.一种适用于工件离散制造的大规模生产调度方法,其特征在于,包括以下步骤:S1、设置模型的运行环境;

S2、根据模型的运行环境,建立工件离散制造的大规模调度模型;

S3、根据建立的大规模调度模型,构建HWOAGA算法;

所述HWOAGA算法包括以下步骤:

S3a、读取工件的待加工信息,设置算法基本参数,所述算法基本参数包括种群规模以及最大迭代次数Max_It,然后转至步骤S3b;

S3b、随机得到初始化种群,然后转至步骤S3c;

S3c、计算种群适应度,得到最优解,然后转至步骤S3d;

S3d、判断是否符合终止条件,若符合则输出最优解,否则转至步骤S3e;

S3e、将初始化种群划分为若干个普通子种群,并根据初始化种群中的个体适应度,从初始化种群中选取若干个适应度排序靠后的个体组成劣等子种群,从初始化种群中选取若干个适应度排序靠前的个体组成优秀子种群,所述普通子种群、劣等子种群和优秀子种群中的个体数量相等,然后转至步骤S3f、S3g和S3h;

S3f、对普通子种群执行IWOA算法和遗传算法中的突变算子,以更新普通子种群中的个体位置;

S3g、依据系数向量 的绝对值,采用IWOA算法中的寻找猎物方式或环绕猎物方式,来对劣等子种群中的个体位置进行更新,然后转至步骤S3i;

S3h、先采用IWOA算法中的气泡网攻击方式,来对优秀子种群中的个体位置进行第一次更新,紧接着判断累计迭代次数是否超过预设值,若不超过则转至步骤S3k,若超过则接着对优秀子种群执行遗传算法的突变算子,以对优秀子种群中的个体位置进行第二次更新,然后转至步骤S3k;

S3i、对普通子种群和劣等子种群实现种群个体迁移策略,将普通子种群和劣等子种群中的最优个体替换普通子种群和劣等子种群中的最差个体,得到进化后的普通子种群和劣等子种群,然后转至步骤S3j;

S3j、合并进化后的普通子种群和劣等子种群,得到合并化种群;

S3k、将更新后的优秀子种群中的最优个体替换合并化种群中的最差个体,得到优化后种群,并将累计迭代次数加1,然后转至步骤S3c;

所述大规模调度模型满足以下公式:

其中,n为工件总数量;m为加工设备总数量;i,i’为工件编号,i,i’=1,2,…,n;j,j’为工件i的工序号,j,j’=1,2,…,s;k,h为加工设备编号,k,h=1,2,…,m;Oij为工件i的第j道工序;mij为工件i的第j道工序可选加工设备数量;N为一个足够大的正数;Sijk为Oij选择加工设备k的开始加工时间;Pijk为Oij选择加工设备k的加工时间;Tijk为Oij选择加工设备k的完工时间;Ci为每个工件Ji的完工时间;Xijk为0‑1变量;Yiji’j’k为0‑1变量;

所述IWOA算法包括工序部分和加工设备部分的编码操作以及解码操作;

所述工序部分和加工设备部分的编码操作均包括:采用FJSP的二层编码OSMA来对染色体进行编码;

所述工序部分的编码操作还包括:先生成[‑3,3]区间内的一组随机数并将其与工序排序向量对应,根据ROV规则为所有随机数赋值,然后根据工序编号对应的ROV元素对随机数进行重新排序,以构成一个个体位置元素;

所述加工设备部分的编码操作还包括:根据以下公式将工序已选加工设备序号转换为对应的个体位置向量元素,;

所述工序部分的解码操作包括:先给更新后的个体位置元素进行编号并使其对应工序编号,然后根据工序编号对应的ROV值来构造调度解;

所述加工设备部分的解码操作包括:根据以下公式推算得到加工设备对应编号,;

上述公式中, s(i)代表所选加工设备在可选加工设备集中的序号,w(i)为座头鲸个体位置向量的第i个元素,m(i)为元素i对应工序的可选加工设备个数,m表示加工设备总数量;

所述遗传算法中的突变算子包括轮盘赌选择操作、交叉操作以及变异操作,所述交叉操作包括工序部分和加工设备部分;

所述工序部分的交叉操作包括以下步骤:

T11、随机将工件集划分为两个非空的子集J1和J2;

T12、将P1包含在J1中的工件按照原有位置复制到C1,P2包含在J1中的工件按照原有位置复制到C2;

T13、将P2包含在J2中的工件按照原有顺序复制到C1,P1包含在J2中的工件按照原有顺序复制到C2;

其中,{P1,P2,...,Pn}表示经过编码操作以及解码操作后的工序部分所生成的父代染色体,{C1,C2,...,Cn}表示工序部分经过交叉操作后得到的子代染色体;

所述加工设备部分的交叉操作包括基于工件的加工设备交叉,以及均匀多点交叉;

所述基于工件的加工设备交叉包括以下步骤:

T211、根据OS基因串的算子交叉操作,改变MA基因串中对应的位置,得到父代基因串;

T212、随机选择两个进行交叉操作的工件,将PMA1中未选择到的基因复制到CMA1,将PMA2中未选择到的基因复制到CMA2,并保留其位置;

T213、将PMA1中选择到的基因复制到CMA2中,并保留其顺序;将PMA2中选择到的基因复制到CMA1中,并保留其位置;

所述均匀多点交叉包括以下步骤:

T221、根据OS基因串的算子交叉操作,改变MA基因串中对应的位置,得到父代基因串;

T222、随机生成长度与新MA父代基因串相等的二进制编码串,将PMA1中与二进制编码串的字符1所对应的基因复制到CMA1中,并保留其位置,将PMA2中与二进制编码串R的字符1所对应的基因复制到CMA2中,并保留其位置;

T223、将PMA1中其余的基因复制到CMA2中,并保留其顺序;PMA2中剩余的基因复制到CMA1中,并保留其顺序;

其中,{PMA1,PMA2,...,PMAn}表示将经过编码操作以及解码操作后的加工设备部分所生成的父代基因串,{CMA1,CMA2,...,CMAn}表示加工设备部分经过交叉操作后得到的子代基因串;

所述变异操作包括工序部分以及加工设备部分;

所述工序部分的变异操作包括互换变异和插入变异;

所述互换变异包括随机交换OS染色体中两个基因的位置;

所述插入变异包括随机将OS染色体中的某个基因插入到选定的位置中,其中,处于选定位置之前的基因保持不变,处于选定位置之后的基因依次顺延一个位置;

所述加工设备部分的变异操作包括以下步骤:

T31、录对工序编码执行变异操作所对应加工设备部分编码位置;

T32、判断执行变异操作之后所生成的解是否为可行解,若为可行解则加工设备部分编码则保持不变,否则转至步骤T33;

T33、对非法解进行修整,在该工序的可加工设备集中随机选择一个加工设备序号进行重新编码。

2.根据权利要求1所述的一种适用于工件离散制造的大规模生产调度方法,其特征在于,所述模型的运行环境包括:在零时刻,所有的工件均处于待加工的状态;

在零时刻,所有的加工设备均能够进行加工;

工件的加工过程不可被中断;

一台加工设备在同一时刻仅能够执行一道工序;

所有的工件的加工路线确定,且各个工件之间不存在优先级关系;

同一个工件的不同工序之间存在有先后执行顺序;

每道工序的执行时间均包含等待时间。

3.根据权利要求1所述的一种适用于工件离散制造的大规模生产调度方法,其特征在于,所述IWOA算法的非线性收敛因子 满足以下公式:;

其中,t为累计迭代次数,T为设置的最大迭代次数Max_It。

4.根据权利要求1所述的一种适用于工件离散制造的大规模生产调度方法,其特征在于,所述IWOA算法的惯性权重因子w满足以下公式:;

其中, 为w的最大值, 为w的最小值,t为累计迭代次数,T为设置的最大迭代次数Max_It, 表示当前鲸鱼的位置向量, 表示目前为止最好的鲸鱼位置向量,为系数向量, 表示鲸鱼和猎物之间的距离,b为用于定义螺旋线形状的常数,l为(−1,1)中的随机数, 表示随机选择的鲸鱼位置向量。

5.根据权利要求1所述的一种适用于工件离散制造的大规模生产调度方法,其特征在于,所述轮盘赌选择操作包括:每次从种群中选择n个体进行适应度排序,将适应度排序较前的个体进入交叉池,直至填满交叉池。

说明书 :

一种适用于工件离散制造的大规模生产调度方法

技术领域

[0001] 本发明涉及工件离散制造领域,具体为一种适用于工件离散制造的大规模生产调度方法。

背景技术

[0002] 某些特定的工件制造企业,例如液压缸制造企业,对我国制造业的高质量发展起着举足轻重的作用。而液压缸一般采用小批量、多品种的生产模式,且由于液压缸的调度规模大、工艺流程复杂,平均每天的订单量所提取的BOM表中的物料就多达数百件,导致传统的车间调度方案的参考价值较低,单凭计划员的经验对物料进行排产所生成的调度方案不一定合理,从而拖延订单的交付。此外,随着液压缸规格要求的变化,与之配套的零部件工艺规格也会随之变化,在实际的生产过程中,多种工艺规格会使得生产的精细化管控更为困难。

发明内容

[0003] 为克服现有技术的不足,本发明提供了一种适用于工件离散制造的大规模生产调度方法,能生成合理的调度方案,有利于订单的及时交付以及生产的精细化管控。
[0004] 本发明采用了以下的技术方案。
[0005] 一种适用于工件离散制造的大规模生产调度方法,包括以下步骤:
[0006] S1、设置模型的运行环境;
[0007] S2、根据模型的运行环境,建立工件离散制造的大规模调度模型;
[0008] S3、根据建立的大规模调度模型,构建HWOAGA算法;
[0009] 所述HWOAGA算法包括以下步骤:
[0010] S3a、读取工件的待加工信息,设置算法基本参数,所述算法基本参数包括种群规模以及最大迭代次数Max_It,然后转至步骤S3b;
[0011] S3b、随机得到初始化种群,然后转至步骤S3c;
[0012] S3c、计算种群适应度,得到最优解,然后转至步骤S3d;
[0013] S3d、判断是否符合终止条件,若符合则输出最优解,否则转至步骤S3e;
[0014] S3e、将初始化种群划分为若干个普通子种群,并根据初始化种群中的个体适应度,从初始化种群中选取若干个适应度排序靠后的个体组成劣等子种群,从初始化种群中选取若干个适应度排序靠前的个体组成优秀子种群,所述普通子种群、劣等子种群和优秀子种群中的个体数量相等,然后转至步骤S3f、S3g和S3h;
[0015] S3f、对普通子种群执行IWOA算法和遗传算法中的突变算子,以更新普通子种群中的个体位置;
[0016] S3g、依据系数向量 的绝对值,采用IWOA算法中的寻找猎物方式或环绕猎物方式,来对劣等子种群中的个体位置进行更新,然后转至步骤S3i;
[0017] S3h、先采用IWOA算法中的气泡网攻击方式,来对优秀子种群中的个体位置进行第一次更新,紧接着判断累计迭代次数是否超过预设值,若不超过则转至步骤S3k,若超过则接着对优秀子种群执行遗传算法的突变算子,以对优秀子种群中的个体位置进行第二次更新,然后转至步骤S3k;
[0018] S3i、对普通子种群和劣等子种群实现种群个体迁移策略,将普通子种群和劣等子种群中的最优个体替换普通子种群和劣等子种群中的最差个体,得到进化后的普通子种群和劣等子种群,然后转至步骤S3j;
[0019] S3j、合并进化后的普通子种群和劣等子种群,得到合并化种群;
[0020] S3k、将更新后的优秀子种群中的最优个体替换合并化种群中的最差个体,得到优化后种群,并将累计迭代次数加1,然后转至步骤S3c。
[0021] 进一步,所述模型的运行环境包括:
[0022] 在零时刻,所有的工件均处于待加工的状态;
[0023] 在零时刻,所有的加工设备均能够进行加工;
[0024] 工件的加工过程不可被中断;
[0025] 一台加工设备在同一时刻仅能够执行一道工序;
[0026] 所有的工件的加工路线确定,且各个工件之间不存在优先级关系;
[0027] 同一个工件的不同工序之间存在有先后执行顺序;
[0028] 每道工序的执行时间均包含等待时间。
[0029] 进一步,所述大规模调度模型满足以下公式:
[0030] ;
[0031] ;
[0032] ;
[0033] ;
[0034] ;
[0035] ;
[0036] ;
[0037] ;
[0038] ;
[0039] 其中,n为工件总数量;m为加工设备总数量;i,i’为工件编号,i,i’=1,2,…,n;j,j’为工件i的工序号,j,j’=1,2,…,s;k,h为加工设备编号,k,h=1,2,…,m;Oij为工件i的第j道工序;mij为工件i的第j道工序可选加工设备数量;N为一个足够大的正数;Sijk为Oij选择加工设备k的开始加工时间;Pijk为Oij选择加工设备k的加工时间;Tijk为Oij选择加工设备k的完工时间;Ci为每个工件Ji的完工时间;Xijk为0‑1变量;Yiji’j’k为0‑1变量。
[0040] 进一步,所述IWOA算法包括工序部分和加工设备部分的编码操作以及解码操作;
[0041] 所述工序部分和加工设备部分的编码操作均包括:采用FJSP的二层编码OSMA来对染色体进行编码;
[0042] 所述工序部分的编码操作还包括:先生成[‑3,3]区间内的一组随机数并将其与工序排序向量对应,根据ROV规则为所有随机数赋值,然后根据工序编号对应的ROV元素对随机数进行重新排序,以构成一个个体位置元素;
[0043] 所述加工设备部分的编码操作还包括:根据以下公式将工序已选加工设备序号转换为对应的个体位置向量元素,
[0044] ;
[0045] 所述工序部分的解码操作包括:先给更新后的个体位置元素进行编号并使其对应工序编号,然后根据工序编号对应的ROV值来构造调度解;
[0046] 所述加工设备部分的解码操作包括:根据以下公式推算得到加工设备对应编号,[0047] ;
[0048] 上述公式中, ,s(i)代表所选加工设备在可选加工设备集中的序号,w(i)为座头鲸个体位置向量的第i个元素,m(i)为元素i对应工序的可选加工设备个数,m表示加工设备总数量。
[0049] 进一步,所述IWOA算法的非线性收敛因子 满足以下公式:
[0050] ;
[0051] 其中,t为累计迭代次数,T为设置的最大迭代次数Max_It。
[0052] 进一步,所述IWOA算法的惯性权重因子w满足以下公式:
[0053] ;
[0054] ;
[0055] ;
[0056] 其中, 为w的最大值, 为w的最小值,t为累计迭代次数,T为设置的最大迭代次数Max_It, 表示当前鲸鱼的位置向量, 表示目前为止最好的鲸鱼位置向量, 为系数向量, 表示鲸鱼和猎物之间的距离,b为用于定义螺旋线形状的常数,l为(−
1,1)中的随机数, 表示随机选择的鲸鱼位置向量。
[0057] 进一步,所述遗传算法中的突变算子包括轮盘赌选择操作、交叉操作以及变异操作。
[0058] 进一步,所述轮盘赌选择操作包括:每次从种群中选择n个体进行适应度排序,将适应度排序较前的个体进入交叉池,直至填满交叉池。
[0059] 进一步,所述交叉操作包括工序部分和加工设备部分;
[0060] 所述工序部分的交叉操作包括以下步骤:
[0061] T11、随机将工件集划分为两个非空的子集J1和J2;
[0062] T12、将P1包含在J1中的工件按照原有位置复制到C1,P2包含在J1中的工件按照原有位置复制到C2;
[0063] T13、将P2包含在J2中的工件按照原有顺序复制到C1,P1包含在J2中的工件按照原有顺序复制到C2;
[0064] 其中,{P1,P2,...,Pn}表示经过编码操作以及解码操作后的工序部分所生成的父代染色体,{C1,C2,...,Cn}表示工序部分经过交叉操作后得到的子代染色体;
[0065] 所述加工设备部分的交叉操作包括基于工件的加工设备交叉,以及均匀多点交叉;
[0066] 所述基于工件的加工设备交叉包括以下步骤:
[0067] T211、根据OS基因串的算子交叉操作,改变MA基因串中对应的位置,得到父代基因串;
[0068] T212、随机选择两个进行交叉操作的工件,将PMA1中未选择到的基因复制到CMA1,将PMA2中未选择到的基因复制到CMA2,并保留其位置;
[0069] T213、将PMA1中选择到的基因复制到CMA2中,并保留其顺序;将PMA2中选择到的基因复制到CMA1中,并保留其位置;
[0070] 所述均匀多点交叉包括以下步骤:
[0071] T221、根据OS基因串的算子交叉操作,改变MA基因串中对应的位置,得到父代基因串;
[0072] T222、随机生成长度与新MA父代基因串相等的二进制编码串,将PMA1中与二进制编码串的字符1所对应的基因复制到CMA1中,并保留其位置,将PMA2中与二进制编码串R的字符1所对应的基因复制到CMA2中,并保留其位置;
[0073] T223、将PMA1中其余的基因复制到CMA2中,并保留其顺序;PMA2中剩余的基因复制到CMA1中,并保留其顺序;
[0074] 其中,{PMA1,PMA2,...,PMAn}表示将经过编码操作以及解码操作后的加工设备部分所生成的父代基因串,{CMA1,CMA2,...,CMAn}表示加工设备部分经过交叉操作后得到的子代基因串。
[0075] 进一步,所述变异操作包括工序部分以及加工设备部分;
[0076] 所述工序部分的变异操作包括互换变异和插入变异;
[0077] 所述互换变异包括随机交换OS染色体中两个基因的位置;
[0078] 所述插入变异包括随机将OS染色体中的某个基因插入到选定的位置中,其中,处于选定位置之前的基因保持不变,处于选定位置之后的基因依次顺延一个位置;
[0079] 所述加工设备部分的变异操作包括以下步骤:
[0080] T31、录对工序编码执行变异操作所对应加工设备部分编码位置;
[0081] T32、判断执行变异操作之后所生成的解是否为可行解,若为可行解则加工设备部分编码则保持不变,否则转至步骤T33;
[0082] T33、对非法解进行修整,在该工序的可加工设备集中随机选择一个加工设备序号进行重新编码。
[0083] 本发明的有益效果为:
[0084] 本发明提供了一种适用于工件离散制造的大规模生产调度方法,该方法将鲸鱼优化算法与遗传算法混合后得到自适应多种群混合算法(HWOAGA),以此来对大规模生产调度问题进行求解,通过将种群总体划分为若干个不同类型的子种群来减少问题的复杂性,增加了子种群的多样性,避免了算法局部极小值的过早收敛,并对不同的子种群采用不同的进化策略,从而生成合理的调度方案,有利于订单的及时交付以及生产的精细化管控。

附图说明

[0085] 为了更清楚地说明本发明实施例或现有技术中的技术方案,下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍,显而易见地,对于本领域普通技术人员来讲,在不付出创造性劳动的前提下,还可以根据这些附图获得其他的附图。
[0086] 图1为本实施例的HWOAGA算法的步骤流程图;
[0087] 图2为本实施例的3×4的柔性作业车间的调度问题的示意图;
[0088] 图3为本实施例的3×4FJSP问题的OSMA编码方案的示意图;
[0089] 图4为本实施例的工序排序向座头鲸个体位置转换的示意图;
[0090] 图5为本实施例的座头鲸个体位置向工序排序转换的示意图;
[0091] 图6为本实施例的工序部分的交叉操作示意图;
[0092] 图7为本实施例的加工设备交叉示意图;
[0093] 图8为本实施例的均匀多点交叉示意图;
[0094] 图9为本实施例的工序部分的变异操作示意图。实施方式
[0095] 附图仅用于示例性说明,不能理解为对本专利的限制;为了更好说明本实施例,附图某些部件会有省略、放大或缩小,并不代表实际产品的尺寸。
[0096] 对于本领域技术人员来说,附图中某些公知结构及其说明可能省略是可以理解的。下面结合附图和实施例对本发明的技术方案做进一步的说明。
[0097] 一种适用于工件离散制造的大规模生产调度方法,包括以下步骤:
[0098] S1、设置模型的运行环境;
[0099] S2、根据模型的运行环境,建立工件离散制造的大规模调度模型;
[0100] S3、根据建立的大规模调度模型,构建HWOAGA算法;
[0101] HWOAGA算法包括以下步骤:
[0102] S3a、读取工件的待加工信息,设置算法基本参数,算法基本参数包括种群规模以及最大迭代次数Max_It,然后转至步骤S3b;
[0103] S3b、随机得到初始化种群,然后转至步骤S3c;
[0104] S3c、计算种群适应度,得到最优解,然后转至步骤S3d;
[0105] S3d、判断是否符合终止条件,若符合则输出最优解,否则转至步骤S3e;
[0106] S3e、将初始化种群划分为若干个普通子种群,并根据初始化种群中的个体适应度,从初始化种群中选取若干个适应度排序靠后的个体组成劣等子种群,从初始化种群中选取若干个适应度排序靠前的个体组成优秀子种群,普通子种群、劣等子种群和优秀子种群中的个体数量相等,然后转至步骤S3f、S3g和S3h;
[0107] S3f、对普通子种群执行IWOA算法和遗传算法中的突变算子,以更新普通子种群中的个体位置;
[0108] S3g、依据系数向量 的绝对值,采用IWOA算法中的寻找猎物方式或环绕猎物方式,来对劣等子种群中的个体位置进行更新,然后转至步骤S3i;在本实施例中,若系数向量的绝对值小于1,则采用寻找猎物的方式,若系数向量 的绝对值大于1,则采用环猎物的方式;
[0109] S3h、先采用IWOA算法中的气泡网攻击方式,来对优秀子种群中的个体位置进行第一次更新,紧接着判断累计迭代次数是否超过预设值,若不超过则转至步骤S3k,若超过则接着对优秀子种群执行遗传算法的突变算子,以对优秀子种群中的个体位置进行第二次更新,然后转至步骤S3k;在本实施例中,预设值为算法基本参数中最大迭代次数Max_It的20%,如此,能够充分发挥优秀子种群中个体的寻优能力以及发掘劣等子种群中适应度较差个体的探索能力,有利于避免当前最优解不是全局最优解的情况发生;
[0110] S3i、对普通子种群和劣等子种群实现种群个体迁移策略,将普通子种群和劣等子种群中的最优个体替换普通子种群和劣等子种群中的最差个体,得到进化后的普通子种群和劣等子种群,然后转至步骤S3j;
[0111] S3j、合并进化后的普通子种群和劣等子种群,得到合并化种群;
[0112] S3k、将更新后的优秀子种群中的最优个体替换合并化种群中的最差个体,得到优化后种群,并将累计迭代次数加1,然后转至步骤S3c。
[0113] 优选的,模型的运行环境包括:
[0114] 在零时刻,所有的工件均处于待加工的状态;
[0115] 在零时刻,所有的加工设备均能够进行加工;
[0116] 工件的加工过程不可被中断;
[0117] 一台加工设备在同一时刻仅能够执行一道工序;
[0118] 所有的工件的加工路线确定,且各个工件之间不存在优先级关系;
[0119] 同一个工件的不同工序之间存在有先后执行顺序;
[0120] 每道工序的执行时间均包含等待时间。
[0121] 优选的,大规模调度模型满足以下公式:
[0122] (1)
[0123] (2)
[0124] (3)
[0125] (4)
[0126] (5)
[0127] (6)
[0128] (7)
[0129] (8)
[0130] (9)
[0131] 其中,公式(1)表示以最小化最大完工时间作为优化目标构建目标模型;公式(2)和(3)表示工件前后工序间的执行顺序约束,工件在完成前一道工序之后才能进入下一道工序;公式(4)表示单个工件的完工时间不能超过最大完工时间;公式(6)表示同一个工件的每道工序仅执行一次;公式(7)用于规定各个参数变量为正数;公式(8)表示,若工序Oij在加工设备k上加工,则Xijk=1,否则Xijk=0;公式(9)表示,若在加工设备k上的工序Oij先于Oi’j’,则Yiji’j’k=1,否则Yiji’j’k=1。
[0132] n为工件总数量;m为加工设备总数量;i,i’为工件编号,i,i’=1,2,…,n;j,j’为工件i的工序号,j,j’=1,2,…,s;k,h为加工设备编号,k,h=1,2,…,m;Oij为工件i的第j道工序;mij为工件i的第j道工序可选加工设备数量;N为一个足够大的正数;Sijk为Oij选择加工设备k的开始加工时间;Pijk为Oij选择加工设备k的加工时间;Tijk为Oij选择加工设备k的完工时间;Ci为每个工件Ji的完工时间;Xijk为0‑1变量;Yiji’j’k为0‑1变量。
[0133] 优选的,IWOA算法包括工序部分和加工设备部分的编码操作以及解码操作;
[0134] 工序部分和加工设备部分的编码操作均包括:采用FJSP的二层编码OSMA来对染色体进行编码;以如附图2所示的3×4的柔性作业车间的调度问题为例,其3×4FJSP问题的OSMA编码方案如附图3所示。
[0135] 工序部分的编码操作还包括:先生成[‑3,3]区间内的一组随机数并将其与工序排序向量对应,根据ROV规则为所有随机数赋值,然后根据工序编号对应的ROV元素对随机数进行重新排序,以构成一个个体位置元素,具体如附图4所示;
[0136] 加工设备部分的编码操作还包括:根据以下公式将工序已选加工设备序号转换为对应的个体位置向量元素,
[0137] ;
[0138] 工序部分的解码操作包括:先给更新后的个体位置元素进行编号并使其对应工序编号,然后根据工序编号对应的ROV值来构造调度解,具体如附图5所示;
[0139] 加工设备部分的解码操作包括:根据以下公式推算得到加工设备对应编号,[0140] ;
[0141] 上述公式中, ,s(i)代表所选加工设备在可选加工设备集中的序号,w(i)为座头鲸个体位置向量的第i个元素,m(i)为元素i对应工序的可选加工设备个数,m表示加工设备总数量。
[0142] 优选的,IWOA算法的非线性收敛因子 满足以下公式:
[0143] ;
[0144] 其中,t为累计迭代次数,T为设置的最大迭代次数Max_It。与传统的鲸鱼优化算法中的收敛因子相比,本实施例所提供的非线性收敛因子在算法的初期能够以较大的值来提供较强的全局搜索能力,避免算法过早地陷入局部最优解;并在算法迭代后期,以较小的值使得算法具有较强的局部探索能力,从而加快原始算法的收敛速度。
[0145] 优选的,为提高算法的寻优精度,本实施例的IWOA算法的惯性权重因子w满足以下公式:
[0146] ;
[0147] ;
[0148] ;
[0149] 其中, 为w的最大值, 为w的最小值,t为累计迭代次数,T为设置的最大迭代次数Max_It, 表示当前鲸鱼的位置向量, 表示目前为止最好的鲸鱼位置向量,为系数向量, 表示鲸鱼和猎物之间的距离,b为用于定义螺旋线形状的常数,l为(−1,1)中的随机数, 表示随机选择的鲸鱼位置向量。
[0150] 优选的,遗传算法中的突变算子包括轮盘赌选择操作、交叉操作以及变异操作。
[0151] 优选的,轮盘赌选择操作包括:每次从种群中选择n个体进行适应度排序,将适应度排序较前的个体进入交叉池,直至填满交叉池。
[0152] 优选的,交叉操作包括工序部分和加工设备部分;
[0153] 工序部分的交叉操作包括以下步骤:
[0154] T11、随机将工件集划分为两个非空的子集J1和J2;
[0155] T12、将P1包含在J1中的工件按照原有位置复制到C1,P2包含在J1中的工件按照原有位置复制到C2;
[0156] T13、将P2包含在J2中的工件按照原有顺序复制到C1,P1包含在J2中的工件按照原有顺序复制到C2;
[0157] 其中,{P1,P2,...,Pn}表示经过编码操作以及解码操作后的工序部分所生成的父代染色体,{C1,C2,...,Cn}表示工序部分经过交叉操作后得到的子代染色体;
[0158] 例如,给定两个父代染色体OS基因串分别为:P1=[3,2,1,4,2,1,3,4],P2=[1,2,4,2,1,3,3,4],然后划分工件集{1,2,3,4}为两个子集J1={1,2}和J2={3,4}。将P1包含在J1中的工件按照原有位置复制到C1,P2包含在J1中的工件按照原有位置复制到C2,结果如附图6(a);将P2包含在J2中的工件按照原有顺序复制到C1,P1包含在J2中的工件按照原有顺序复制到C2,结果见附图6(b)。
[0159] 加工设备部分的交叉操作包括基于工件的加工设备交叉,以及均匀多点交叉;需说明的是,本实施例在对MA基因串进行交叉之前,先根据OS基因串的交叉操作调整MA基因串的顺序,然后对MA基因串采用基于工件的加工设备交叉和均匀多点交叉的混合交叉方式,在交叉的过程中,针对上述两种交叉方法按照1:1的比例进行交叉操作。为了防止在交叉操作之后产生不可行解,当交叉后得到的加工设备号大于当前工序可选择的加工设备数时,在可选择的加工设备中选择加工时间最小的;
[0160] 例如,取两个OS父代基因串为:POS1=[3,2,1,4,2,1,3,4],POS2=[1,2,4,2,1,3,3,4];给定两个MA父代基因串为:PMA1=[2,3,1,4,2,3,3,1],PMA2=[3,2,1,4,2,2,3,1];根据POX算子所得到的两个子代基因串为:COS1=[4,2,1,3,2,1,3,4],COS2=[1,2,2,2,1,4,3,4],MA基因串随着OS基因串的交叉而变化,得到CMA1=[1,3,1,2,2,3,3,1],CMA2=[3,2,2,4,2,4,3,1]。
[0161] 基于工件的加工设备交叉包括以下步骤:
[0162] T211、根据OS基因串的算子交叉操作,改变MA基因串中对应的位置,得到父代基因串;
[0163] T212、随机选择两个进行交叉操作的工件,将PMA1中未选择到的基因复制到CMA1,将PMA2中未选择到的基因复制到CMA2,并保留其位置;
[0164] T213、将PMA1中选择到的基因复制到CMA2中,并保留其顺序;将PMA2中选择到的基因复制到CMA1中,并保留其位置;
[0165] 例如,根据POX算子所得到的两个MA父代基因:PMA1=[1,3,1,2,2,3,3,1],PMA2=[3,2,2,4,2,4,3,1],选择工件1、3进行交叉操作,结果如附图7所示.
[0166] 均匀多点交叉包括以下步骤:
[0167] T221、根据OS基因串的算子交叉操作,改变MA基因串中对应的位置,得到父代基因串;
[0168] T222、随机生成长度与新MA父代基因串相等的二进制编码串,将PMA1中与二进制编码串的字符1所对应的基因复制到CMA1中,并保留其位置,将PMA2中与二进制编码串R的字符1所对应的基因复制到CMA2中,并保留其位置;
[0169] T223、将PMA1中其余的基因复制到CMA2中,并保留其顺序;PMA2中剩余的基因复制到CMA1中,并保留其顺序;
[0170] 均匀多点交叉的具体实施方式如附图8所示;
[0171] 其中,{PMA1,PMA2,...,PMAn}表示将经过编码操作以及解码操作后的加工设备部分所生成的父代基因串,{CMA1,CMA2,...,CMAn}表示加工设备部分经过交叉操作后得到的子代基因串。
[0172] 优选的,变异操作包括工序部分以及加工设备部分;
[0173] 如附图9所示,工序部分的变异操作包括互换变异和插入变异;
[0174] 互换变异包括随机交换OS染色体中两个基因的位置;
[0175] 插入变异包括随机将OS染色体中的某个基因插入到选定的位置中,其中,处于选定位置之前的基因保持不变,处于选定位置之后的基因依次顺延一个位置;
[0176] 加工设备部分的变异操作包括以下步骤:
[0177] T31、录对工序编码执行变异操作所对应加工设备部分编码位置;
[0178] T32、判断执行变异操作之后所生成的解是否为可行解,若为可行解则加工设备部分编码则保持不变,否则转至步骤T33;
[0179] T33、对非法解进行修整,在该工序的可加工设备集中随机选择一个加工设备序号进行重新编码。
[0180] 显然,本发明的上述实施例仅仅是为清楚地说明本发明所作的举例,而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说,在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等,均应包含在本发明权利要求的保护范围之内。