基于遗传算法的纺纱车间计划调度优化策略研究

2021-04-23章国政

纺织报告 2021年2期

章国政

（经纬纺织机械股份有限公司中央研究院，北京 100176）

纺纱生产车间计划调度就是根据需求，合理分配产线及相应的生产制造资源，达到合理利用产品制造资源、提高企业经济效益的目的。当前，大部分纺纱企业在制作生产计划时，主要还是依靠人工计算的方式来进行，存在工作强度大、应对变化的能力弱且调度结果不一定最优的问题。研究发现，大部分纺纱企业的车间生产过程有以下特点：（1）所有的生产都是以订单为驱动；（2）工序之间存在定台供应的情况，可以生产线的形式来表示；（3）对于细纱工序，以翻改品种次数最少为优选策略；（4）整体车间生产计划需要以所有订单都能准时交付为目标。考虑以上因素，可以制作出纺纱车间生产计划调度模型，利用遗传算法求解，得到订单排产计划的优化方案。

1 计划调度优化算法介绍

1.1 遗传算法原理概述

遗传算法是模拟达尔文进化论自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。在初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化，产生越来越好的近似解，在每一代，根据问题中个体的适应度大小选择个体，并借助自然遗传学的遗传算子，进行组合交叉和变异，产生代表新解集的种群。这个过程将导致种群像自然进化一样的后生代种群，比前代更适应环境，末代种群中的最优个体，对应作为问题近似的最优解。遗传算法的具体流程如图1所示。

图1 遗传算法流程

1.2 计划调度优化算法流程

1.2.1 订单元素与遗传算法元素的对应关系

模拟自然界优胜劣汰的进化现象，将搜索问题转化为遗传问题，把可能的解转为一个向量—染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解[1]。订单元素与遗传算法元素的对应关系如表1所示。

表1 订单元素与遗传算法元素的对应关系

1.2.2 算法步骤

第一步：构造目标函数GeneticAlgorithm，确定输入、输出变量。输入变量为：遗传进化迭代次数M、种群规模N、变异概率Pm、每一代中保持不变的数目Parent、批次信息List、设备配置信息；输出变量为：最优完工时间Zp、各批次分配的生产线BatchLine、各批次各工序的开始时间Begin、各批次各工序的结束时间End、各批次各工序的输入次数Input、各批次各工序的输出次数Output。

第二步：随机产生初始种群farm并计算适应度函数[2]。在群体farm中，每一个染色体为随机产生的一组生产调度方案。

第三步：将染色体根据适应度函数进行排序，保留最优的Parent个解。

第四步：交叉。在种群中，选择两个父代染色体进行交叉方式和交叉点的随机选择，产生两个新的子代染色体，并将新旧染色体组合成新的种群，即在随机产生的众多生产调度方案中，选择两个父代方案进行交叉。交叉的具体操作是将两个调度方案中的工件和工序相关信息进行交换，然后产生两个新的子代方案[3]。

第五步：变异。在种群中，随机选择要变异的基因，产生新的染色体，以避免局部收敛的情况发生，即通过随机的方法，产生新的生产调度方案。

第六步：重复第三步到第五步，直到适应度函数收敛，产生最优解。

1.3 计划调度优化模型构建

纺织企业的生产任务是以订单为基础，因此，研究从订单出发构建模型的方法，并设计相应算法[4]。

首先，当纺织企业在短期内接到不同订单时，要对订单的加工需求进行分类，按照不同订单中相同的加工种类进行生产，订单中的每一个品种即为一个任务单。例如，纺织车间有3条生产线。企业在短期内收到3条订单：订单一包括A、B、C 3种类型的纺织品，订单二包含A、C两种纺织品，订单三包含B、C两种纺织品。在生产时，将所有订单的各种纺织品随机分配生产线，并随机确定同一生产线上各批次加工的先后顺序。不同任务单的加工顺序需要服从生产计划的安排[5]。

其次，结合纺织厂现行的生产方式，将每一“任务单”分解成不同“批次”进行生产安排。

最后，算法将以满足生产最晚交付时间情况下的最小化完成时间为目标进行优化计算。

具体数学语言描述为：在企业收到的某个订单当中，有i种纱织品（细纱），这i种纱织品分为i批次进行生产，各种批次的总量为Ni，这里的总量以细纱机的最后输出为标准。i批次的纺织品依次经过7道工序，分别为清梳联、预并条、条并卷、精梳、末并、粗纱、细纱[6]。调度的目标是最小化最长完工时间，目标函数为：