﻿ 遗传算法在刹车片生产计划排产中的应用与实践
 计算机系统应用  2019, Vol. 28 Issue (4): 225-230 PDF

Application and Practice of Genetic Algorithm in Brake Pad Production Plan Scheduling
JIANG Peng, GAO Mei-Feng
School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, China
Abstract: The scheduling problem of the production plan is one of the main factors that affect the production efficiency of the workshop. A reasonable scheduling plan can efficiently use the existing production resources of the workshop, increase the production capacity of the workshop, and reduce production costs. Firstly, the production and operation status of the brake pad are analyzed in this study. The production scheduling mathematical model for the multi-types and variable batch production mode of hot-pressing workshop is established. Secondly, a Combined Mean-Genetic algorithm is designed to solve the scheduling mathematical model of hot-pressing workshop. Finally, the algorithm is verified by experimental simulation. The experimental results show that the Combined Mean-Genetic algorithm can well solve the scheduling problem of the current brake pad production plan.
Key words: brake pad production plan     scheduling     combined mean-genetic algorithm

1 问题描述

 图 1 刹车片生产主要流程

2 数学模型

(1)在车间开始排产前, 车间单个生产班次的订单已经生成, 且不再发生变化.

(2)在热压机进行生产时, 各种物料已经齐套, 不需要考虑物料齐套的运输问题.

(3)在产品开始热压前需要一定的准备时间ts, 来调整热压机生产参数和热压配套工具等, 这里认为每种产品准备时间是相同的且热压机在生产不同的产品前都需要准备时间.

(4)每台热压机在生产过程中是连续生产的, 生产过程中不会出现中断.

(5)每一种产品在开始热压前, 热压工艺已经确定, 在单个生产班次中不会发生变化.

(6)在单个生产班次内生产的产品是没有优先级的.

(7)一个产品只能在一台热压机上生产一次.

2.1 目标函数

i台热压机总的加工时间Ti为:

 ${T_i} = \sum\limits_{j = 1}^n {{t_j}*c(j,i)} + \sum\limits_{j = 1}^n {x(j,i){t_s},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} } i = 1,2,\cdots,m{\kern 1pt}$ (1)

 ${T_{\max }} = \mathop {\max }\limits_i {T_i},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 1,2,\cdots,m{\kern 1pt}$ (2)

 $\min ({T_{\max }})$ (3)
2.2 约束条件

(1)机器加工时间约束:

 ${T_i} \le {T_c},\begin{array}{*{20}{c}} {}&{i = 1,2, \cdots ,m} \end{array}$ (4)

(2)每种产品的总数量约束: 在单个班次内, 每种产品生产的数量应该等于该生产班次订单中每种刹车片的数量, 即

 $\sum\limits_{i = 1}^m {c(j,i)} = C_j^{\max },{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} j = 1,2, \cdots ,n$ (5)
3 基于联合均值-遗传算法(CMG)算法的排产方案设计

3.1 均值排产

(1)首先计算出单个生产班次内分配在每台热压机上理想的加工时间Tmean:

 ${T_{\rm{mean}}} = \sum\limits_{j = 1}^n {\frac{{{t_j} \times C_j^{\max }}}{m}} + {t_s}$ (6)

(2)根据Tmean计算出在该时间段内能够连续生产产品j的最大数量Pj:

 ${P_j} = \left\lceil {\frac{{({T_{\rm{mean}}} - {t_s})}}{{{t_j}}}} \right\rceil, \;\;j = 1,2,\cdots,n$ (7)

(3)Pj为在Tmean时间段中产品j在热压机连续生产的最大数量, 所以首先以Pj为指标进行均值排产.

 ${H_j} = \left\lfloor {\frac{{C_j^{\max }}}{{{P_j}}}} \right\rfloor,\;\;j = 1,2,\cdots,n$ (8)

 $\left\{ {\begin{array}{*{20}{l}} {{C_j} = {P_j} \times {H_j}}\\ {f = \displaystyle\sum\limits_{j = 1}^n {{H_j}} } \end{array}} \right.,\;\;\;{j = 1,2,\cdots,n}$ (9)
3.2 遗传算法排产

 ${C_{j - left}} = C_j^{\max } - {C_j},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} j = 1,2,\cdots,n$ (10)

 ${N_{\rm{left}}} = m - f$ (11)

(1)编码: 首先根据矩阵编码规则, 随机生成一个个体, 然后依照单个个体的编码规则, 随机生成一个种群. 单个矩阵的具体编码规则如下:

 $\begin{array}{*{20}{c}} {c(1,f + 1)}& \cdots &{c(1,m)}\\ \vdots & \ddots & \vdots \\ {c(n,f + 1)}& \cdots &{c(n,m)} \end{array}$

 $0 \le c(j,i) < \left\lceil {\frac{{{T_{\rm{mean}}} - {t_s}}}{{{t_j}}}} \right\rceil, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} i = 1,2,\cdots,m$ (12)

(2)选择: 按照概率Rg选出前Q个比较优秀的个体, 同时按概率Rb在除去前Q个体的种群中随机选择出比较差的个体. 由于是随机选择个体进入下一代, 无法具体控制下一代的种群数量, 因此本文设计的选择算子中的概率Rg具有一定的自适应性, 具体自适应规则为:

 ${R_g} = \left\{ {\begin{array}{*{20}{c}} {{R_1},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} S > IT}\\ {{R_2},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} S \le IT} \end{array}} \right.{\kern 1pt} {\kern 1pt}$ (13)

(3)交叉: 首先根据种群大小利用随机函数无放回的在种群中随机选取一对个体, 然后利用随机函数随机产生的交叉位置进行交叉, 最后重复上述过程, 直到整个种群全部完成交叉. 因为式(4)和式(5), 交叉时应该以矩阵的行为单位进行平行交叉, 即两个矩阵相同位置处的行进行互换. 以下为单次交叉的结果, 即随机选取的第j行个体进行了交叉.

 $\begin{array}{c} \begin{array}{*{20}{c}} {{c_s}(1,f + 1)}&{{c_s}(1,f + 2)}& \cdots &{{c_s}(1,m)}\\ {}& \vdots &{}&{}\\ {{c_x}(j,f + 1)}&{{c_x}(j,f + 2)}& \cdots &{{c_x}(j,m)}\;\;\Leftrightarrow \\ {}& \vdots &{}&{}\\ {{c_s}(n,f + 1)}&{{c_s}(n,f + 2)}& \cdots &{{c_s}(n,m)} \end{array} \begin{array}{*{20}{l}} {{c_x}(1,f + 1)}&{{c_x}(1,f + 2)}& \cdots &{{c_x}(1,m)}\\ {}&\vdots &{}&{}\\ {{c_s}(j,f + 1)}&{{c_s}(j,f + 2)}& \cdots &{{c_s}(j,m)}\\ {}& \vdots &{}&{}\\ {{c_x}(n,f + 1)}&{{c_x}(n,f + 2)}& \cdots &{{c_x}(n,m)} \end{array} \end{array}$

(4)变异: 首先使用概率Rb用来随机选取要进行变异的个体, 然后利用随机函数随机产生的变异位置进行变异. 同样因为式(4)和式(5), 变异的位置以行为单位.

(5)迭代: 综上4步, 在完成步骤(1)后, 通过循环按顺序反复进行(2)、(3)和(4)步骤, 通过Tmean值来动态控制迭代次数, 具体控制步骤如下:

 ${T_{\max }} \le {T_{\rm{mean}}} + {T_d}$ (14)
 $L \le {L_{\max }}$ (15)

4 仿真实验与分析

5 结束语

 [1] 王爱民. 制造执行系统(MES)实现原理与技术. 北京: 北京理工大学出版社, 2014. 11–21. [2] 蒋海峰. 多品种少批量生产线排产软件的设计与实现[硕士学位论文]. 大连: 大连理工大学, 2017. [3] 刘晨, 蒙丹花, 方玮宸, 等. 多品种小批量订单型企业生产调度优化. 包装工程, 2016, 37(11): 93-99. [4] 孟巧凤, 张林鍹, 董杰涛, 等. 混流柔性生产线排产优化. 计算机仿真, 2016, 33(7): 245-250. [5] 武韶敏, 胡晓兵, 王江武, 等. 改进遗传算法求解面向订单多目标排产问题. 机械设计与制造, 2018(3): 102-104, 108. [6] 金剑, 金钊, 祁跃东. 卷烟生产计划排产模型建立与优化. 计算机工程与应用, 2013, 49(18): 253-259. [7] 姚丽丽, 史海波, 刘昶, 等. 烟草排产中嵌入规则的遗传算法应用研究. 制造业自动化, 2011, 33(4): 89-93. [8] 王博. 液压缸基础零件制造车间MES的研究与设计[硕士学位论文]. 南京: 南京理工大学, 2017. [9] 吕文军. 基于BOM的柔性作业车间调度方法与信息系统研究[硕士学位论文]. 重庆: 重庆大学, 2016. [10] 王明星, 李利民. 改进的遗传算法在机加车间排产优化的研究. 制造业自动化, 2014, 36(8): 34-37, 48. [11] 张国庆, 刘永进, 梅中义. 改进的遗传算法在复合材料车间计划排产中的应用研究. 现代制造工程, 2010(7): 56-59. [12] 张超群, 郑建国, 钱洁. 遗传算法编码方案比较. 计算机应用研究, 2011, 28(3): 819-822. [13] 陆远, 尹建定. 智能制造车间设备动态能力分析技术研究. 机床与液压, 2018, 46(1): 1-6. [14] 李书全, 孙雪, 孙德辉, 等. 遗传算法中的交叉算子的述评. 计算机工程与应用, 2012, 48(1): 36-39. [15] 孙羽. 基于遗传算法的生产计划调度系统设计与实现[硕士学位论文]. 哈尔滨: 哈尔滨工业大学, 2016.