基于遗传算法的印染协同管理调度问题研究

武治含 刘国华 盛守祥 王国栋 王力民

摘 要：部门间协同化程度低是制约印染企业生产效率提高的因素，为了解决该问题，本文提出了一种印染协同管理调度方法。通过对印染生产业务流程的分析，确定协同管理调度问题的数学模型，并利用遗传算法求得问题的近似最优解。在本文的遗传算法中，个体采用基于序列的编码方式，交叉操作采用互换交叉的方式，变异操作采用逆转变异方式。实验结果表明，本文提出的方法可以有效地提高资源利用率，缩短订单完工时间。

关键词： 印染生产;协同管理调度;遗传算法

文章编号： 2095-2163（2019）03-0142-04 中图分类号： TP311.5 文献标志码： A

0 引 言

中国纺织、轻工业等行业的信息化程度较低[1-2]，导致部门间协同信息匮乏。印染业作为纺织业的重要分支之一，面对竞争白热化带来的新变局，迫切需要寻求技术上的突破，提高协同管理水平，从而提升产业竞争力。

目前印染企业部门间的协同化程度低，任务顺序均由部门主管统筹安排或线性执行。这种生产模式导致各部门的信息时效性差，异步协同工作难以充分展开，资源的最优利用也仍停留在理论上。长此以往，必将导致人力物力资源的极大浪费、生产效率低下，同时产业竞争力也不高。

针对人为协同管理调度资源利用率低的问题，Steenhuisen等人[3]于2009年提出了协同调度的概念，所谓的协同调度，即当一个复杂的任务须经由多个部门的协同运作时，亟需制定一个切实可行的计划，使得每个部门协同有效地完成子任务，从而保证总任务顺利交付。在国内很多领域，也已经陆续见到相关的问题研究，例如，冯霞等人[4]研发了基于多目标遗传算法的模型用于求解机场运输工作的协同调度问题;陈鹏慧等人[5]提出了一种基于遗传算法的协同调度方法，用于解决机器人的协同调度问题。而在印染业，研究者的关注重心多是聚焦在生产车间调度[6-7]方面。在印染生产的业务协同管理方面的研究迄今为止仍不多见。研究可知，协同管理调度属于常见的组合优化问题，近年来国内外学者就求解该问题进行了大量的实验。目前比较通用的方法有模拟退火法[8]、遗传算法[9-10]、粒子群算法[11]、蚁群算法、人工神经网络等。其中，遗传算法作为时下解决调度问题效率较高、通用性较好的一种启发式算法，具有求解过程简洁，收敛性好，近优解质量高的特点[12]。综上论述可知，本文在对印染生产协同管理问题研究的基础上，利用遗传算法，提出了印染协同管理调度方法。本文对此拟做研究论述如下。

1 问题描述与建模

印染企业的印染业务流程描述如下：业务员接收訂单后，根据生产需求创建订单，订单审核通过后，将依次经历原料采购、打样生产、质检以及运输等环节，以上步骤将整个流程拆分成多个业务。本文将通过调度算法研究来使各部门协同处理多个订单的作业时间最短。

1.1 问题描述

已知一个生产订单集合O={Oi|i=1，2，...，n}，一个业务集合P={Pj|j=1，2，...，m}，对于O中的任意一个元素Oi，均要经过k（k≤m）个有序的业务处理，且各生产订单对应的业务运行时间为已知。求业务部门处理订单的顺序，确保在规定时间内近似最优、资源利用率最高地完成全部订单。

生产订单与业务约束关系及对应业务的处理时间见表1。例如，O1订单的对应的业务序列为P1-P2-P4-P6。

1.2 问题建模

本文数学模型遵循的约束条件的释义说明可分述如下：

（1） 业务部门同一时刻只能处理某个订单中的相应业务。

（2）各订单对应的订单业务有严格的执行顺序，且各订单之间逻辑独立，互不影响。

（3）业务必须由特定的业务部门来完成，并且前一项业务完成后才能处理后续业务。

（4）业务处理时间已知，不随业务处理顺序或订单执行顺序的改变而改变。

（5）业务执行期间，直到结束不会进行其他任务。

结合约束条件，根据表1中的数据形式，对本文研究的协同管理调度问题进行数学建模，对此可表述为：

研究中，设n表示订单数，m表示全部订单对应业务数中的最大值，数组orderProject[n][m]表示n个订单分别对应的业务序列，即，订单业务约束关系数组;数组projectTime[n][m]表示n个订单业务序列分别对应的业务执行时间;P[m][n]表示m个业务部门对应的订单处理顺序;T[n][m]表示n个订单业务序列中各个业务的开始运行时间。

对于n个订单，每个订单最多涉及m个业务的协同管理调度问题，令TMax表示完成所有订单所需的最大完工时间，则求取TMax最小的目标函数可写作如下数学形式：

其中，M为种群个体数，Ti表示订单在某一种处理顺序下，全部订单的最大完成时间，即：

2 基于遗传算法的求解方法

遗传算法在研究染色体编码方式时，需要考虑最突出的个体特征，从而确定编码方式。个体的编码方式，将直接影响算法后续步骤以及算法性能。而在得到编码方式后，则根据个体特点进一步确定适应度函数、选择方法、交叉与变异方式，以及初始种群大小、交叉变异概率、迭代次数等。本文对此将给出探讨详述如下。

2.1 编码

本文的研究目标是获取订单的最优处理顺序。基于此，本文采用基于序列的编码方式[13]对个体进行编码。染色体的基因数为所有订单全部业务数之和，用订单序号表示对应订单。染色体序列由订单序号组成，且同一订单序号的出现次数为该订单对应的业务数。

采用基于序列的编码方式对表1中的数据进行编码，编码后的一条染色体为：[2 2 1 2 1 2 1 1 2]。其中，序号2出现了5次，表示订单O2对应着5个业务。

2.2 解码

由于订单业务有着严格的执行顺序，订单序号第几次出现即表征该订单的第几个业务。结合表1数据可知，染色体序列[2 2 1 2 1 2 1 1 2]中第一个基因2表示订单O2的首道工序P5，同理，序列中第五个基因1则表示订单O1中的第二道工序P2。

故而，由染色体序列结合数组orderProject[n][m]便可判断出当前处于几号订单的几号业务。

2.3 适应度值计算

适应度值的大小关系到个体的优劣判断。本文的适应度值为完成全部订单所需最大时间的倒数，即1/Ti（i=1，2，...，M）。最大完工时间越短，适应度值越高，个体的生存几率就越大。

订单业务根据染色体序列从左到右依次开始执行，结合数组orderProject[n][m]以及projectTime[n][m]可知，当前订单业务是几号订单的几号业务，并且该业务的执行时间亦已知。选取该业务之前一个业务的完成时间或者处理该业务的业务部门的最近空闲时间这二者中的较大值，作为该业务的开始时间。综上方法就可求得每个业务的开始工作时间与完工时间。不断更新Ti，使Ti为目前所需的最大完工时间。直到全部订单被处理完毕，求得的1/Ti即为该个体的适应度值，记为fi （i=1，2，...，M）。

2.4 选择

选择的设计是基于优胜劣汰的原则，从当前的种群中选出优异的染色体作为交叉变异执行的个体。本文采用轮盘赌选择法结合精英策略进行个体选择。

计算种群个体的适应度值之和∑fi （i=1，2，...，M）。研究推得个体选择概率的计算公式为：

由式（3），可得个体的选择概率为个体适应度值除以种群内全部染色体适应度之和。

接下来，计算∑pi，并且在[0，1]区间内产生随机数r，如果r∈（∑pi-1，∑pi]，则个体vi被选中。

将选中的个体作为交叉操作与变异操作的候选个体。

2.5 交叉

本文采用基于序列的编码方式，个体序列顺序的交换并不影响订单业务的执行顺序，故本文采用互换基因的方式[14]进行交叉操作（交叉概率Pc=0.9）。记染色体长度为L。互换交叉操作如图1所示。具体步骤如下。

（1）产生一个在[1，L]之间的随机数r1。

（2）记录C1、C2染色体中r1位置的基因值分别为c1、c2。

（3）互换C1、C2中r1位置的基因值。

（4）在C2中找到c1第一次出现的位置，记为g2，在C1中找到c2第一次出现的位置，记为g1。

（5）互换g1、g2位置的基因值。

（6）返回新的染色体C1'、C2'。

当r1的值为2时，交叉后的染色体如图2所示。

由于交叉后的个体只改变了订单开始时间，订单间业务逻辑互不影响。故而求得的解仍为可行解。

2.6 变异

为了防止种群陷入局部最优解，保护优良基因，本文采用了逆转变异的方法（变异概率Pm=0.05）进行染色体变异。具体过程如下。

在[1，L]之间产生2个随机数l1、l2，且要求这2个随机数不等。交换这2个位置上的基因，生成新的个体。例如基因数为6的个体，取2个随机数l1、l2分别为2与4，互换第二位与第四位的基因，形成新个体。设计变换过程如图3所示。

由于个体序列顺序的交换并不影响订单业务的执行顺序，故由此变异方法得到的变异个体仍是可行解。

2.7 终止条件

若遗传算法代码运行时间超过设定时间或迭代次数达到给定次数，则停止运行，得到的结果则为协同管理调度问题的近似最优解。

3 实验结果

结合某印染车间的实际业务流程进行试验。已知有标号分别为O1～O5的5个订单，其中包括的项目业务如下：原料采购、原料质检、打样、制定生产工艺、订单生产、成品质检、成品入库与运输，分别记为1、2、3、4、5、6、7、8。订单与业务对应的约束关系orderProject[5][8]见表2，对应的业务执行时间数据projectTime[5][8]见表3。

利用上述实验数据运行算法，计算得出订单最短完成时间（49 h）、各业务开始时间数组T[5][8]。本文遗传算法的运行参数为：初始种群大小100，Pc为0.9，Pm为0.05，迭代次数为1 000。协同管理调度结果如图4所示。在图4中，定义了O（i）： t的模式，其中i表示订单号，t表示业务开始时间。

根据实验结果甘特图可得，订单处理顺序明确，任务分工合理。算法调度管理下的业务时间节点清晰，部门工作效率与资源利用率得到有效提高。当订单量大时，协同管理调度算法的优势就更加明显。在生产实践中，企业可将算法结果与工作日程结合，得出各部门的任务时间安排表，提高部门执行力与各部门间的沟通时效性。

4 结束语

面对日趋激烈的竞争环境，纺织印染行业必须紧跟时代潮流，提升产业信息化水平。本文提出的基于遗传算法的印染协同管理调度方案契合实际生产需求，对提高业务协同运作效率以及提升产业竞争力起到了积极重要的推动作用。随着研究的深入，用于解决部门协同合作的算法将会具有更加广阔的应用前景，算法的求解速度和近似最优解的质量也将得到不断地提升与完善。

参考文献

[1]贺正楚，潘红玉. 德国“工業4.0”与“中国制造2025”[J]. 长沙理工大学学报（社会科学版），2015，30（3）：103-110.

[2]李瑞萍. 中国印染行业发展现状及未来趋势[J]. 染料与染色，2015，52（2）：52-62.

[3]STEENHUISEN J R， WITTEVEEN C. Plan decoupling of agents with qualitatively constrained tasks[J]. Multiagent and Grid Systems， 2009， 5（4）： 357-371.

[4]冯霞，任子云. 基于遗传算法的加油车和摆渡车协同调度研究[J]. 交通运输系统工程与信息，2016，16（2）：155-163.

[5]陈鹏慧，蔡琼，彭华顺. 基于遗传算法的多移动机器人协同调度方案[J]. 微型电脑应用，2016，32（7）：34-38.

[6]张洪业，金刚，王宇新. 微粒群算法在印染企业车间调度中的研究应用[J]. 计算机工程与应用，2009，45（21）：245-248.

[7]张国辉. 柔性作业车间调度方法研究[D]. 武汉：华中科技大学，2009.

[8]LI W  D，MCMAHON C A.  A simulated annealing-based optimization approach for integrated process planning and scheduling[J]. International Journal of Computer Integrated Manufacturing，2007，20（1）：80-95.

[9]席裕庚，柴天佑，恽为民. 遗传算法综述[J]. 控制理论与应用，1996，13（6）：697-708.

[10]PANDEY H M， CHAUDHARY  A， MEHROTRA D. A comparative review of approaches to prevent premature convergence in GA[J]. Applied Soft Computing Journal， 2014（24）：1047-1077.

[11]王万良，赵澄，熊婧，等. 基于改进蚁群算法的柔性作业车间调度问题的求解方法[J]. 系统仿真学报，2008，20（16）：4326-4329.

[12]马永杰，云文霞. 遗传算法研究进展[J]. 计算机应用研究，2012，29（4）：1201-1206，1210.

[13]姜迪刚，叶尚辉. 基于遗传算法的车间作业调度[J]. 西安電子科技大学学报，2001，28（2）：207-210.

[14]曾强，邓敬源，张进春，等. 多工作日历下流水作业调度遗传优化方法[J]. 计算机工程与应用，2019，55（4）：238-247.