纺织企业车间生产调度方法和遗传算法的研究与实现

张险峰

（嘉兴市建筑工业学校，浙江 嘉兴 314001

摘   要：在先代生产中，生产调度不仅是一个战术问题，它己经成为提升企业竞争力的一个战略。每个企业的车间工作调度问题都有自己的特性，是调度领域中极待解决的重要课题。因而，虽然对于生产调度问题的研究相对较多，同时在生产调度领域中关于建模方法、算法求解等问题的研究也比较多，但对于在非制造性的行业，特别是在纺织行业中生产调度问题的研究相对还是比较少。本文研究了纺织公司的生产车间调度，尤其是并行成套设备多批次的调度问题，针对该调度问题进行遗传算法设计，并以示例进行仿真。使得遗传算法能在纺织企业的生产调度中起到节约生产成本，提高企业效益的作用。

关键词:生产调度；Flow-shop调度；并行机调度；遗传算法

中图分类号：TP301.6         文献标识码：A

Textile Enterprises Workshop Production Scheduling Methods and Genetic Algorithm Research and Implementation

生产车间作业调度问题，就是根据需求合理分配产品制造资源，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间生产调度在企业生产经营活动中占有十分重要的地位，生产调度系统也是CIMS、ERP等系统中的重要组成部分，因此受到学术界和工业界的广泛xx。对它的研究具有很高的理论意义和实际意义。

生产调度问题一般可以描述为：针对某项可以分解的工作，在一定的约束条件下，如何安排其组成部分(操作)所占用的资源、加工时间及先后顺序，以获得产品制造时间或者成本等性能指标{zy}。生产调度问题主要集中在车间的计划与调度方面，许多学者作了大量研究，出了不少的研究成果。制造系统的生产调度是针对一项可分解的工作(如产品制造) ，探讨在尽可能满足约束条件(如交货期、工艺路线、资源情况)的前提下，通过 下达生产指令，安排其组成部分(操作)使用哪些资源、其加工时间及加工的先 后顺序，以获得产品制造时间或成本的{zy}化。在理论研究中，生产调度问题 常被称为排序问题或资源分配问题^[1]。

由上可见，生产车间调度问题在具体行业中的应用的研究问题。具有很强的针对性，对其的研究具有积极意义，而最为合适的分析方法则是采用遗传算法。

遗传算法(GA)是一种新的并行优化搜索方法。它是一种模仿生物群体进化过程的一种优化算法，给定一组初始解作为一个群体，通过选择、交又和变异等遗传操作来搜索{zy}解。

李国富(1998)^[2]用遗传算法对Job-shop零件排序问题进行优化搜索，并在算法中引进了一些新的思想，以有利于降低种群的规模，提高计算速度，改善优化结果。

1  纺织企业车间生产流程

纺织公司生产业务流程大致可描述为：接单-》产品设计-》采购计划-》生产计划-》染色-》纺纱-》织造-》坯布检验-》生修-》复检-》入库-》染整-》熟修-》成品检验-》成品入库-》成品包装-》装箱-》发货等，其中染色、纺纱、织造有自制及委外。

具体来说，纺织企业在接到订单后，经过前面的分析，可以确认具体的生产步骤。首先，先确认是否原有库存有与订单相符的坯布，有的话只要进行必要的改进，如：染色，后整理就可以达到要求；假如没有就看有没有库存纱线，进行生产流程设计，没有就要开始从精毛开始入手进行生产工艺单的制作，确认需要具体的精毛原材料，把原材料送到纺纱机进行纺纱，纺纱结束后根据订单需要，看看是否需要染色和合股，而且合股一般可能不只一次，不过我们这里主要根据大部分的订单需要，基本上是合股一次以下，假如合股一次以上，可能进行原材料的分离来解决。

我们在列出整个生产工序流程图的同时没有考虑出库和入库的过程，在后面的设置中我们通过增加每道工序的准备时间和完成时间来替代这个出入库流程。

通过前面研究的纺织企业生产问题，我们可以得到有一些特征：

①所有的生产都是以订单为驱动的；

②每个生产流程都有多台设备；

③有些工序可以省略。

④每个设定的流程路线基本都相同。

考虑以上的因素，我们可以看出有些类同于混合的Flow-Shop调度问题，我们可以在这个基础上进行必要的修改，用以适用凌龙纺织有限公司的生产调度要求。并建立了相应的数学优化模型，仿真结果很好的安排了定单的生产，且使得企业取得了较高的经济效益。

2  纺织企业车间生产模型的建立

遗传算法已经被成功地应用于求解流水车间调度问题^[4]：Ishibuchi H.研究了模糊交货期下的流水车间调度问题，黄宇纯等结合遗传算法和REAS启发式规则，求解Flow-shop调度问题，庞哈利和郑秉霖提出多阶段混合Flow-shop调度问题的遗传算法求解方法，张纪会等提出了基于GA的机器学习算法，用于动态调度中的知识获取。

Flow- shop调度问题一般可以描述为n个工件要在m台机器上加工，每个工件需要经过二道工序，每道工序要求不同的机器，n个工件在m台机器上的加工顺序相同。工件在机器上的加工时间是给定的。问题的目标是确定n个工件在每台机器上的{zy}加工顺序，使流程时间达到最小。

由于纺织企业在接到订单后，客户提出的是对具体产品的需求，而我们采用的流水线车间成组作业调度需要的是能确认在生产过程中具体需要多少批量的原材料。所以把订单生成具体的产品工艺单，得出所有订单需求的原材料，确定每个订单的原材料配置，同时把所有的分为具体的批量进行生产。也就是说把相同的生产要求成具体的批次，当然每个批次的量有一个{zd0}值，本论文就把批量能设的{zd0}值作为每批需要生产产品的最小单位。假如某个批次不足一个批量，我们也按照一个批量来实现。

纺织流水车间成组作业调度可以这样描述：N 批产品的原材料准备在M（大于2）套设备上加工，每批原材料都要依次经过这M套设备，也就是说我们设定每个工序对应一套设备，比如在纺纱车间，我们假定一批需要纺纱的原材料进入车间进行纺纱的过程就是该批原材料在整套纺纱设备加工。根据原材料加工的相似性，它们可以分为b 组；其中，组i 的原材料批量数是  ，组i中的第j批原材料用 标记；对于原材料批量 其在第k套设备上加工时间为 ；在任意一套设备上，如果前后相继加工的原材料批量不属于同组，则必须重新设置。为了考虑在具体生产流程中，原材料需要出入库的操作，还要准备设备的时间，我们统一设定为该批原材料在该套设备的准备时间，因此在组i第k套设备上的准备时间是 ；本章要研究的内容为：按照一定的规则将这些作业重新进行分组，组内作业排序、组间作业排序，并将重新分组排序后的产品批量按顺序排列在M套设备上使之满足目标函数－总流程时间。其数学模型如下：

表示第i组的流程时间（i=1,2,…,b） 那么 等于第i组内各原材料批量的完工时间之和，设 表示第i组的第j批原材料在第k套设备上的完工时间； 表示第i组的第j批原材料在第k套设备上加工的时间， 表示第i组的原材料在第k台设备上的准备时间。

总的流程时间F等于各组的完工时间之和，即：

               （1）

以总流程时间为优化目标，则目标函数可以表示如下：

        （2）

{zh1}得到模型：

  （3）

3   纺织企业车间生产模型遗传算法的实现

遗传算法实现的全部工作，包含了编码、适应度函数、遗传操作(交叉和变异)、选择方法和控制参数等几个方面。

编码

编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。在纺织车间中，生产是按照批次来划分的，我们可以把每个生产批次做为一个任务来完成，即{dy}批设定为任务1，第二批设定为任务2，…，依次类推。由于在加工的时候我们可以看到有部分批次的产品在印染工序是不需要的，所以我们分为两组，3、5、8、10 为一组，而1、2、4、6、7、9、11、12为另外一组进行仿真计算。我们可以得到编码为1、2、4、6、7、9、11、12、3、5、8、10，这样可以保证编码更为合理。

3.2适应度函数评价

遗传算法遵循自然界优胜劣汰的原则，在进行搜索中基本上不用外部信息，而用适应度表示个体的优劣，作为遗传算法操作的依据。适应度较高的个体遗传到下一代的概率就较大：而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数(Fitness Function)，适应度函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的{wy}依据^[5]。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。

{zy}化问题可分为两大类，一类为求目标函数的全局{zd0}值，这类问题最自然的想法就是将目标函数作为适应度函数。但是许多优化问题是求目标函数的全局最小值，而遗传算法的要求适应度函数取正值，而且适应度越大，个体越好。因此，在不少场合采用问题的目标函数作为个体的适应性度量时，必须将目标函数转化为求{zd0}值形式，而且保证适应度函数非负。一般可采用以下的方法进行转换：

3.3遗传操作

遗传操作是模拟自然界生物基因遗传的操作，它是群体水平上的个体操作，其作用是实现优胜劣汰，达到适应环境和自然的进化^[4-5]。在遗传算法中通常使用三个基本遗传操作算子：选择(Selection)、交叉(Crossover)、变异(Mutation)。

选择过程实质上就是优胜劣汰、适者生存的过程。通过选择可以构成新一代染色体，使那些适应性好的个体有更多机会保留下来，淘汰那些适应性差的个体。交叉是决定GA收敛性的核心操作，是最主要的遗传操作，它同时对两个染色体操作，组合二者的特性产生新的后代。我们看看纺织实例中的交叉操作：两父个体为

A= 1 2 3︱4 5 6︱7 8 9 10 11 12

B= 4 10 6︱7 11 12︱5 3 2 1 8 9

A，B交换匹配区域后

A’= 1 2 3︱7 11 12︱7 8 9 10 11 12

B’= 4 10 6︱4 5 6︱5 3 2 1 8 9

再进行替换

A”＝ 1 2 3︱7 11 12︱4 8 9 10 5 6

B”＝ 7 10 12︱4 5 6︱11 3 2 1 8 9

4   浙江凌龙纺织企业车间生产模型案例实现

在实际的生产过程中，由于客户需求的差别，有些批次的产品可能跳过某些工序。所以假如在处理的批次产品时，有些工序可以省略的时，我们设定该批次产品在这些工序的时间为0。同时考虑凌龙纺织公司的在具体生产过程中都是以半天为一个时间单位，我们假设半天的时间在我们的仿真中设定为1。

同时，考虑到工序时间在具体操作的时候，当准备时间不足半天时间也按半天的计算，加工时间不足半天同样按照半天时间来计算。我们为了尽可能满足公式（3）的模型，要求存在下面两个假设：

①企业库存场地无限大

在此条件下，可以不必考虑当提前完成订单且客户尚未提货时，保管成品所需付出的代价。从华茂的实际情况看来，是能够满足这个条件的。

②不考虑拖期情况

凌龙纺织在实际工作流程中，销售员在决定是否要与客户签订订单之前，需要通过调度员的审核，调度员会根据各个分厂当前的实际生产情况预测交货期，如果该预测值超出客户要求的交货期，则不会同意销售员签单。因此，在建模时，不必考虑拖期情况。

运用以上遗传算法求解批次为12的生产订单，参数设置为：种群规模n=50， =0.7， =0.01，先产生50个初始个体形成初始种群，通过运算，可以得到{zh0}解和{zh0}迭代数。

参考文献:

[1]李歧强.生产过程的智能决策与调度[D].浙江大学控制系,1998.

[2]李国富.一种基于遗传算法的Job Shop作业排序方法[J].宁波大学学报[理工版],1998,11(3),47.

[3]Holsapple C.W.,Varghese S. J.Ramakrishnan P. A genetics-based hybrid scheduler for generating static schedules in flexible manufacturing contexts.IEEE Trans on Systems,man and Cybernetics,1993,23(4),953.

[4]戴晓晖,李敏强,寇纪淞.遗传算法理论研究综述[J].控制与决策，2000,15 (3):263-269.

[5]吴云高.基于遗传算法的车间调度方法及其应用[D].浙江工业大学.