基于Plant Simulation 的混合流水线车间调度仿真

2021-03-25高珂婷

软件导刊 2021年3期

高珂婷

（天津工业大学计算机科学与技术学院，天津 300380）

0 引言

混合流水线车间调度问题（Hybrid Flow shop Schedul⁃ing Problem，HFSP）是一个典型的NP-hard 难题，其结合了传统的Flow shop 调度问题和多机并行分配问题，故其解决方案更加复杂。

遗传算法（Genetic Algorithm，GA）作为一种自组织、自适应、自学习的全局搜索算法［1］，具有很强的鲁棒性和并行搜索能力，可以防止陷入局部最优。利用仿真软件通过构建仿真模型计算调度问题的目标函数值可以免去构建复杂的数学模型，直观地观察到车间流水线最优的调度路线，实现最小化最大完工时间与总生产成本等目标。

近年来，学者们对混线排序问题的研究不断深入。一部分文献利用仿真软件对该问题进行优化，如文献［2］利用仿真软件建立混流装配线的物料配送系统仿真模型，对物料系统进行优化；文献［3］针对某军工车间的生产任务进行排产仿真，得到合理的作业规划；文献［4］参考企业提供的实际参数及条件，在不同优化目标下利用仿真软件进行对比分析，提出最佳措施；文献［5］针对供应链库存管理提出一种仿真优化方法作为过程控制策略。还有一部分文献结合相关算法对该问题进行优化，如文献［6］提出最优家族遗传算法解决了超大规模车间调度效率低的问题；文献［7］针对实时生产系统提出一种调度算法和启发式方法，使生产线上的零件使用率保持恒定；文献［8］用GA 求解混流装配线排序问题，在求解速度方面表现良好；文献［9］将GA 与局部优化程序相结合，用于生成针对流水线平衡问题的多种解决方案，提高了执行速度；文献［10］采用改进粒子群优化生成系统中的管理参数，并借助仿真软件很好地解决了装配线平衡问题。

综上所述，对于车间调度问题的求解可以结合仿真方法和遗传算法，该方法具有很好的通用性［11］。针对HFSP这一复杂问题，本文以Plant Simulation 作为仿真建模工具，建立实例中的车间流水线调度模型，再用遗传算法（GA）结合SPT 规则进行仿真优化，调度目标是最小化Makespan（最大加工完成时间），最后通过Plant Simulation仿真平台上的优化结果验证其有效性［12］。

1 问题描述

混合流水线车间调度问题可描述为：n 个工件在一台或多台机床上通过m 道工序完成加工，各道工序的加工时间已知［13］，如图1 所示。

Fig.1 HFSP scheduling problem图1 HFSP 调度问题

一般混合流水线车间调度问题有如下假设：①在加工过程中，所有工件只能在一台机器上加工；②下一道工序必须在上一道工序结束后才能开始进行；③各工序的加工设备可独立完成全部工件的加工；④每个工件必须完成该工序的操作后才能开始下一道工序；⑤工件位置按一定优先级排列，位置越靠前越早开始加工；⑥若遇到工件的同一道工序恰好需要在同一台机器上完成，则后一个工件必须等前一个工件加工完成后再进行加工［14］。

2 遗传算法

2.1 染色体编码

通常古典生产车间调度问题共有8 种染色体编码方式，本文采用基于矩阵的实数编码方式作为染色体编码方式。对于n 个工件、m 台机器的问题，可构造M×N 矩阵［15］：

其中j=1，2，…，m，i=1，2，…，n，aji表示第i个工件的第j道工序，该实数取值区间为［1，M(j)+1］［16］，M(j) 为第j道工序包含的机器数，整数部分表示所在工序的机器号，小数部分表示加工优先级。如a21=3.1，a22=3.8，a24=3.4，表示工件1、2、4 的M2工序均使用编号为3 的机器，而由于3.1＜3.4＜3.8，故加工次序为工件1/工件4/工件2。除第一道工序按上述编码规则对工件进行排序外，后面的工序应加入一定的优先规则，本文采取最短作业时间（Shortest Process⁃ing Time，SPT）规则。

2.2 适应度函数

遗传算法基因被选择遗传的机会取决于所组成的染色体适应度大小［17］，如何使适应度函数与求解对象有效匹配是检验遗传算法有效性的关键。对于HFSP 问题，求解目标为Makespan 的最小值，所以采用Cmax的倒数作为适应度函数。n 个工件经过m 道工序，其中染色体pop｛i｝在每道工序上花费的时间为Cmax=max1≤i≤n{ }Ci，则适应度函数表示为：

2.3 选择算子

采用遗传算法将适应度值高的个体遗传到下一代，即对种群进行优胜劣汰。本文选择轮盘赌，其基本思想是：每个个体被选中的概率与其适应度值成正比，即值越大，被选择的概率越高，反之亦然。染色体i被选中遗传到下一代的概率为：

其中，i=（1，2，…，n），n为种群大小，Fi为染色体i的适应度值。

2.4 交叉算子

对于HFSP 问题，由于排序在编码中的唯一性，如果采用简单交叉方法，会出现非法解，故这里使用部分映射交叉法（Partially Mapping Crossover，PMX）以避免该问题的产生，从而使解更有效。具体步骤描述为：①随机产生两个交叉点，在两个染色体中的两点之间交换基因；②若交换后的片段与交叉点外的基因不冲突，保留；③若存在冲突，则在交换基因集合中利用部分映射寻找替换基因，产生新个体。

PMX 具体过程如图2 所示。

Fig.2 PMX specific process图2 PMX 具体过程

2.5 变异算子

在序号编码方式下，基因有两种突变方式：一种是互联变异，即在序列中随机选择两个基因，交换其在染色体上的位置后形成新的后代个体，如个体［1，2，3，4，5，6，7，8，9］，随机选择2、8，交换后的个体为［1，8，3，4，5，6，7，2，9］。另一种是逆转变异，即将在染色体中随机选择的两点间基因段进行逆转，如个体［1，2，3，4，5，6，7，8，9］，随机选择2、5，逆转后的个体为［1，2，5，4，3，6，7，8，9］。本文选择互联变异方式［18］。

3 案例仿真分析

3.1 Plant Simulation

Plant Simulation 平台是Siemens 公司研发的一款仿真软件，可用于优化生产线及生产物流过程。其特点主要体现在面向对象的动态系统建模过程、模块化和多层次的建模单元、图形化和对象化的并行仿真环境、多类型接口、多种工具集成等方面［19］。

3.2 仿真模型

在本案例中，整个车间由9 台设备（M1，M2，…，M9）加工12 个工件（J1，J2，…，J12），所有工件所需加工时间如表1所示［20］。

Table 1 All workpiece processing time表1 所有工件加工时间单位：h

在Plant Simulation 平台中模拟建立本案例的车间制造模型，如图3 所示。仿真部分包括区域1、3、4，GA 模块位于区域2，其中区域1 中的Start 对象自动生成区域4 中的模型，Jobs 对象存放由GA 模块产生的某个体；区域3 中SUB_FSP 数据子层存放机床M1-M9对各个工件的加工时间，Result_Table 表存放个体仿真结果；区域2 中GAWizard和GASequence 为软件自带的遗传算法优化工具。

在GAWizard 模块中设置种群规模为20，种群大小为15，在GASequence 模块中设置交叉概率为0.8，变异概率为0.1。在Start 方法中，全局变量AssignRule 为2，通过GA 运算优化排程，得到优化结果如图4 所示（彩图扫OSID 码可见）。

Fig.3 Workshop manufacturing simulation model图3 车间制造仿真模型

Fig.4 GA+SPT ranking results图4 GA+SPT 排优结果

Fig.5 GA+FIFS ranking results图5 GA+FIFS 排优结果

从图4（横坐标代表种群代数，纵坐标代表适应值）可以看出，随着遗传代数的增加，运算结果逐渐趋于最优化，红线代表每次进化过程中种群的最优排程方案，蓝线代表最差排程方案，绿线是二者的平均值。采用SPT 调度规则在第12 代种群之后收敛到最佳个体，实现最优的排序方式，工件加工顺序为4-11-2-1-7-12-5-9-3-6-10-8，得到最优适应度值25。与图5 中GA 结合FIFS 规则的结果相比，改进算法可以更快地找到最优方案，再运行MyGantt 方法得到最优排序结果甘特图，如图6 所示（彩图扫描OSID码可见），得到Makespan=25min，相比文献［20］的最优结果缩短了4min。