基于遗传算法的印刷装订作业调度优化方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN111985647A(43)申请公布日2020.11.24(21)申请号202010706827.X(22)申请日2020.07.21(71)申请人西安理工大学地址710048陕西省西安市碑林区金花南路5号(72)发明人廖开阳史丰收章明珠曹从军郑元林(74)专利代理机构西安弘理专利事务所61214代理人宁文涛(51)Int.Cl.G06N3/12(2006.01)G06Q10/04(2012.01)G06Q10/06(2012.01)G06Q50/04(2012.01)权利要求书2页说明书7页附图1页(54)发明名称基于遗传算法的印刷装订作业调度优化方法(57)摘要本发明公开了基于遗传算法的印刷装订作业调度优化方法，设置车间中各个工件每个步骤的加工时间，然后使用遗传算法将调度问题的解通过编码表示成染色体，最后生成初始染色体种群；计算初始种群中个体的适应度值，判断算法是否完成预设的迭代次数，若满足，选择适应度值好的染色体，输出最优的调度方案，若不满足，采用轮盘赌和精英保留策略的复合型选择方式，选择染色体，选择出染色体之后进行交叉和变异操作，形成新一代的个体，通过不断地交叉与变异过程进行染色体的迭代，生成新的种群；最后在生成的新的种群中选择适应度值好的染色体；本发明的方法可用于快速得出具体订单的调度分配方案，能够减少企业在调配设备上的时间，提升车间的工作效率，降低制造成本。CN111985647ACN111985647A权利要求书1/2页1.基于遗传算法的印刷装订作业调度优化方法，其特征在于，具体包括以下步骤：步骤1，设置车间中各个工件每个步骤的加工时间，然后使用遗传算法将调度问题的解通过编码表示成染色体，最后生成初始染色体种群；步骤2，根据步骤1中生成的染色体计算初始种群中个体的适应度值，判断算法是否完成预设的迭代次数，若满足，执行步骤5，否则继续执行步骤3；步骤3，采用轮盘赌和精英保留策略的复合型选择方式，根据经步骤2得到的适应度值选择染色体；步骤4，选择出染色体之后进行交叉和变异操作，形成新一代的个体，通过不断地交叉与变异过程进行染色体的迭代，生成新的种群；步骤5，在经步骤4生成的新的种群中选择适应度值好的染色体，最后输出最优的调度方案。2.根据权利要求1所述的基于遗传算法的印刷装订作业调度优化方法，其特征在于，所述步骤1中编码的具体过程为：采用十进制编码对工序顺序和设备编号进行编码，将一条染色体表示成工序基因和设备基因两个基因片段，然后将调度方案表示成染色体，最后生成初始染色体种群。3.根据权利要求1所述的基于遗传算法的印刷装订作业调度优化方法，其特征在于，所述步骤2中的具体技术内容包括：首先采用最大完工时间作为优化指标，建立数学模型如下：f(c)＝min1≤k≤m{max1≤i≤n{Cijk}}(1)Tijk≤Si(j-1)k(2)Tijk-Sijk＝Cijk(3)式中，i为工件的序号，j为工件i的加工工序序号，k为加工设备的编号，n为工件的数量，m为加工设备的数量，Cijk为工件i的第j道工序在设备k上的加工时间，Sijk为工件i的第j道工序在设备k上的开始时间，Tijk为工件i的第j道工序在设备k上的完工时间；然后采用适应度函数来计算初始染色体种群中个体的适应度值，利用倒数构造法进行适应度函数的构造，适应度函数表达式为：式中，f(x)为目标函数，C是一个保守估计值。4.根据权利要求1所述的基于遗传算法的印刷装订作业调度优化方法，其特征在于，所述步骤3中轮盘赌的具体内容为：假设种群的大小为M，其中每个个体i的适应度值为f，则任何一个个体被选择的概率为：式中，为种群中所有个体适应度值和，fi为被选中个体的适应度值(1-M)，Pi为被选中的概率。2CN111985647A权利要求书2/2页5.根据权利要求1所述的基于遗传算法的印刷装订作业调度优化方法，其特征在于，所述步骤3中经营策略的具体内容为：在迭代过程中第k代大小为M的种群Pk-{a1(k)，a2(k)，......，am(k)}，精英保留策略为：Fmax(k)＝max{F(a1(k))，F(a2(k))，......，F(am(k))}(7)Fmax(k+1)＝max{F(a1(t+1))，F(a2(t+2))，......，F(am(k+1))(8)式中，Fmax(k)为第k代种群中适应度值最好的个体，Fmax(k+1)为第k+1代种群中适应度值最好的个体，若Fmax(k)＞Fmax(k+1)，则将种群中适应度值最优的一部分精英个体保留，然后进化到下一代。6.根据权利要求1所述的基于遗传算法的印刷装订作业调度优化方法，其特征在于，所述步骤4中交叉的具体内容为：在染色体种群中选择两个染色体