基于遗传算法的rms车间排产优化方法 ic algorithm based on optimi...

倪梦妃 刘国华

文章编号： 2095-2163（2018）03-0041-05中图分类号： 文献标志码： A

摘要： 关键词： dyeing and finishing workshops based on genetic algorithm

（School of Computer Science and Technology， Donghua University， Shanghai 201620， China）

Abstract： The advanced planning and scheduling problem， referred to as APS， is a typical NP-hard problem. In the dyeing and finishing industry， some research results have been made on the production of the dye VAT， but no fruit has been reported on the automatic production of the workshop. In order to solve production scheduling problem of the dyeing workshop， this paper first analyzes and describes the problems， then establishes a mathematical model，meanwhile combined with genetic algorithm， the solution method is proposed. This method could obtain a relatively optimal solution， and conduct the experiment through actual production scheduling task to verify the efficiency of the method. The experimental results show that compared with the artificial production scheduling， scheduling efficiency of using the algorithm has been greatly improved.

Key words：

基金項目：

作者简介：

收稿日期： 引言

随着现代信息技术的不断发展，各行各业都在引进电子信息化来提高行业工作效率。纺织行业作为中国劳动密集度较高的传统行业，毫无例外地受到时下信息化时代所带来的浪潮冲击，面临着巨大挑战的同时，也伴随着潜在机遇。纺织业中印染行业的技术改造是重点对象之一，国家在技术开发和科技投入方面都出台了有关的扶持政策，致力于使国内的印染行业不论是在质量、或是在效率方面都能够得到全面的改善，进而提高该行业的整体竞争实力[1]。

染整车间的排产工作通常由专业人员根据生产任务单凭经验来完成，但其结果却存在很多问题。问题之一就是人工排产工作量大，耗费大量时间。问题之二是生产过程经常会出现无法预料的意外导致排产结果无效，需要进行二次排产调整。问题之三是专业人员虽然对生产流程的排产调度上具备着高度认知与丰富处理经验，但是人工排产在结果上却难以达到最优化，不能充分、有效地切实发挥机台的工作能力与运行效率。

由于排产调度是一个典型的NP难问题，学界也已在寻求近似最优解方面取得了一定成果。如Nasr等人在1990年提出了2种启发式方法，以确定n个作业/m台机器问题的有效调度，并为每个操作提供了可选的机床路线[2]。Palmer在1996年开发了一种基于模拟退火（SA）的方法[3]。陈昌领等通过对单生产多目的的批处理过程建立短期调度混合整数规划模型，并引入启发式规则来求得包含多个同种订单的调度相对最优解[4-5]。目前，针对染整行业的排产问题，现已推出的设计解决方案就是染缸排产[6-8]，但是对于车间的自动排产研究还未见到有关文献发表。

本文在对排产调度问题进行分析和建立数学模型的基础上，结合遗传算法提出染整车间自动排产方法，提高车间生产效率和机台利用率，实现效率和利益的最大化。

1问题描述和数学模型

染整车间生产过程中的工序操作包括翻缝、打底、拉幅打卷、轧光、拉幅、烘培、丝光、烧毛、水洗、退浆、印花和蒸化，相应的工序对应机台。排产调度受生产任务单型号规格、所需布长、生产流程链的差异和机台车速等因素的影响。

问题描述在确保交期内生产完成的情况下，有n个生产任务单n1，n2，…，nn要在2～m个机台上进行生产，机台编号分别为m1，m2，…，mm，机台对应生产工序。每个生产任务单有对应的生产流程链，每道工序加工时间确定，求出相对最优加工批次进行生产且保证机台满负荷工作，减少机台的刷车、切换次数。

本文的数学模型遵循以下约定：

（1）同一个生产任务单按流程链顺序生产，但是不同生产任务单之间不存在流程先后约束。

（2）一个机台只能接收一个生产任务单，且工序一旦开始不能停止。

（3）通过生产任务单中的布长信息和机台车速信息求得每个生产任务单的加工时间。

（4）所有生产任务单都能按时完成，中途不会发生异常，如车速突然减慢、布料卡住等问题。

本文中，将给出如下数学符号含义设定：

N为生产任务单总数；M为机台总数；i为生产任务单编号（i=1，2，3，…， N）；j为机台编号（j=1，2，3，…，M）；ki为对于每一个生产任务单都有对应的生产流程链，ki表示编号为i的生产任务单工序数量；Oi是一个长度为ki的序列，表示生产任务单在机台上的加工序列；Pkm是一个max{ki}*N的二维矩阵，表示编号为i的生产任务单需要在对应编号的机台上加工，即生产任务单机台加工路线；Tkm是一个max{ki}*M的二维矩阵，表示编号为n的生产任务单在Pkm对应的机台上所需的加工时间，工序加工时间的数学运算形式如式（1）所示：工序加工时间=生产任务单布长机台车速（1）至此，可以分析推得本次研究中的数学模型描述如下：

Mnm是一个N*M的二维矩阵，表示编号为j的机台加工对应编号的生产任务单，即最后所需的结果表示为机台生产任务单加工路线；Skm是一个max{ki}*M的二维矩阵，表示编号为n的生产任务单在Pkm对应的机台上开始加工时间。

预先假设机台生产任务单加工路线确定，求得在该路线基础上的生产任务单工序的开始加工时间，不断变换加工路线求出满足目标函数式（2），即对应最快完工时间的那个生产任务单就是排产结果。由此，可得数学公式如下：Smin=min （∑Skm（2）2遗传算法应用

本文结合生产实际情况和对问题的分析，在上述数学模型的基础上，提出基于遗传算法的染整车间排产调度方法。

遗传算法在设计过程中，通常会分解为如下研究内容要点，分别是：染色体编码、初代种群初始化、交叉操作、变异操作、选择操作和评价函数。以及遗传算法所需的遗传参数，如种群大小、交叉概率、变异概率和种群最大迭代次数在算法启动前均已确定。这里，可展开研究论述如下。

2.1染色体编码方式

染色体为一个二维矩阵，矩阵行数为机台编号，矩阵中基因表示为生产任务单编号，整个染色体表示为各生产任务单在机台上的生产序列，对应数学模型中的Mnm，如例1的M22和M2' 2'是2个比较简单直观的染色体，具体如下：

例1M22 =12

12 M2' 2' =21

21

该染色体是一个完整的生产流程序列，M22 （0，j）（j=0，1）表示编号为1的机台上依次生产编号为1，2的生产任务单， M22 （1， j）（j=0，1）表示编号为2的机台上一次生产编号为1，2的生产任务单。且该染色体清晰明确，也不需要进行解码。

在染色体编码方式确定的情况下，随机选取20例個体产生初代种群。研究中，种群染色体基因是机台上加工生产任务单的顺序，所有只要是生产任务单编号范围内的就合法，因此将无需额外判断产生的个体是否可行，只需将随机选取的个体加入到种群即可。

对个体的评价是先根据机台加工路线求得每个生产任务单的每道工序的开始时间。然后在知道开始时间的基础上再求得整个加工过程最迟完工时间，这个时间就是个体的评分score。

2.2交叉操作

对染色体基因进行交叉操作时，由于此处选取的2个父个体在交叉过后无法保证每一例个体在结束后子串的基因值一致而引发致破坏个体稳定性的后果，产生非法解。如例2的M22和M22，如果产生以下交换就是非法解，研究对其展示如下：

例2染色体非法交叉操作非法解：M22 = 22

12M2' 2' = 11

21所以为了保证染色体的可行性与稳定性，需要在同一机台上设计实现基因之间的交叉。

正确交叉为：如果交叉点为0和1之间，上述2个父个体M22和M2' 2'产生的孩子个体为21

12。这样产生的孩子个体的机台加工序列还是合法的，是可行解。

2.3变异操作

与交叉操作类似，如果随机将染色体中基因变异成基因可取范围内的其它值，会破坏染色体的稳定性，并且产生非法解。例如将M22 = 12

12随机选择一个基因进行变异，产生22

12个体，就是非法解。所以为了保证染色体的稳定性，可采用如下方式来构建变异操作，设计步骤流程可表述如下。

（1）依据变异概率确定需要产生的子代个体的个数。

（2）随机选择种群中的某一个体作为变异个体。

（3）随机产生一个在机台数量范围之内的随机数表示选取的一个机台。

（4）再产生2个在机台加工数量范围之内的随机数作为同机台等基因的变异点，将2个变异点的基因进行互换，产生新的子代个体。

（5）重复步骤（2）～（4），直至产生所有子代个体。

2.4选择操作

选择操作采用轮盘赌选择法，同时进一步结合了精英保存策略。

设有种群Pop，种群大小为pop_size，首先假设精英个体是第一个，种群中染色体个体Mi的适应度评分score为scorei，由式（3）计算可得每一个体的适应度值fi，也就是可得到如下计算公式：fi=1.0scorei（3）在遍历计算的过程中，与精英个体进行比较得到种群精英个体，并且计算群体所有染色体个体适应度之和为：F=∑pop_sizei=1fi（4）这就形成了pop_size个区间为：[0，f1F][f1+f2F]...[∑popsize-1i=1fiF，1]再对种群进行遍历，首先产生0～1之间的随机数，保存第一个符合随机数在区间之内的个体，直至选出全部所需染色体个体形成新的种群，同时保存最好的个体，即精英个体。

2.5终止条件

当迭代次数超过给定值后，算法停止运行，此时得到的最优解就是排产调度所需的相对最优排产方式。

3实验验证及结果分析

本实验根据某纺织厂染整车间的真实情况，经过分析建模后选取如下机台和生产任务单进行实验验证。现有7个机台，分别为烧毛机、退浆机、丝光机、打底机、印花机、轧光机和蒸化机，对应的编号为1、2、3、4、5、6、7；另有5个生产任务单顺次编号为1、2、3、4、5需要进行加工生产，设计中的生产流程链已确定，转换为加工序列分别为：O1={2，1，3，4，5，6}，O2={1，2，3，6}，O3={1，3，4}，O4={3，4，5，6，7}，O5={3，4，5，6，7}。从加工序列可知，每一个生产任务单的生产工序数量为k1=6，k2=4，k3=3，k4=5，k5=5，由上述情况可得max{ki}=6，为此从生产任务单属性和机台属性求得工序加工时间T65和生产任务机台加工路线P65。运算得到结果数值为：

8.413.518.724.029.4从排产结果可知完成生产需要39.4 h，加工甘特图如图1所示。甘特图中，p（i， j）表示编号为j的生产任务单在编号为i的机台上进行加工生产。

将上述情况输入到遗传算法程序中，种群大小为20，交叉概率0.3，变异概率0.1，最大迭代次数为1 000，算法运行得到相对最优排产序列M57，一并得到每个生产任务单每道工序的开工时间S75。算法结果数值为：M57 = 321

4.19.214.419.725.1加工甘特圖如图2所示。甘特图中，p（j，i）表示编号为i的生产任务单在编号为j的机台上进行加工生产。

通过算法可得近似最优排产方式，该排产结果的生产时间为30.6 h，相比人工排产结果的最终耗时39.4 h，求解速度更快，生产效率更高，机台利用率更趋理想。并且随着生产任务单的增多，排产组合会爆炸式上升，此时人工排产与算法排产的效率差异也将更为明显。

4结束语

在信息化时代，传统纺织行业需要紧跟时代潮流，并迫切需要提升企业生产效率，为此本文研究提出了基于遗传算法的染整车间排产方法，求得染整车间排产相对最优序列，通过实验验证和结果分析可知该方法实现了生产效率和利益相对最大化。

参考文献

[1] 曹学军. 我国印染行业现状及发展趋势[J]. 印染，2002（5）：39-42.

[2] NASR N， ELSAYED E A. Job shop scheduling with alternative machines[J]. International Journal of Production Research， 1990，28（9）：1595-1609.

[3]PALMER G J. A simulated annealing approach to integrated production scheduling[J]. Journal of Intelligent Manufacturing，1996，7（3）：163-176.

[4] 陈昌领，刘长龄，袁德成，等. 单阶段多产品批处理过程的短期调度1.基本模型的建立[J]. 信息与控制，2002，31（2）：106-111.

[5] 陈昌领，冯晓东，邵惠鹤. 单生产线序贯多目的批处理过程短期调度的MILP建模[J]. 系统仿真学报，2001，13（S1）：69-71.

[6] 戴智杰，宋执环，宋春跃. 基于遗传算法的浸染生产排缸策略[J]. 运筹与管理，2006，15（2）：149-153.

[7] 莫丰勇，郝平，杨马英. 基于遗传算法的拉动式浸染生产动态排产策略[J]. 计算机应用，2008，28（S2）：97-99.

[8] 莫丰勇. 印染企业浸染生产排产优化问题研究及系统设计[D]. 杭州：浙江工业大学，2008.

[9] LAOBOONLUR P ，HODGSON T J，THONEY K A. Production scheduling in a knitted fabric dyeing and finishing process[J]. The Journal of The Textile Institute，2006，97（5）：391-399.

[10]PINEDO M L. Scheduling： Theory， algorithms， and systems [M]. 2nd ed. New Jersey，USA： Prentice-Hall Inc， 2001.