李奇¹杨涛²

1.浙江大学工程师学院，浙江杭州310015；2.杭州海康威视科技有限公司，浙江杭州310000；

摘要：本文介绍了生产排程的发展过程和目前计算机智能算法实现的排程优化过程。根据SMT生产实际情况，建立排程的数学模型，运用遗传算法建立起优化模型，实现SMT生产排程的优化改进，最终用MATLAB验证其有效性。

关键词：SMT排程；遗传算法

1 引言

电子制造的行业大规模发展已经有近30年了。电子产品的生产加工过程中，SMT（Surface Mounted Technology，表面贴装技术）车间的加工环节是生产系统的核心部分，其加工价值在整个电子加工价值中占相当的大比重。早期的电子制造订单都是品种少、批量大，生产排配比较简单固定。随着社会发展，人们对产品的需求越来越多样化，因此产品定制化会越来越多，制造订单结构趋于小批量、多品种，对应的生产线配置也随之增多。

SMT生产排程原来依靠生管人员排程经验和简单的excel表格来进行，随着智能制造不断推进，生产过程智能化越来越深入，生产排程原来的模式和现代化的生产管理、精益理念是背道而驰的。面对产品多样化、定制化、小批量的订单结构变化，如何提升生产设备利用的效率，如何使生产环节衔接更紧密有序？

2生产排程方法的发展

生产排程是将生产任务分配到生产资源的一个过程。排程是将各生产任务重新排序，通过生产顺序和设备选择的优化，减少等待时间、平衡机器和工人的负荷，其目的是使产能得到优化，生产效率得到提高，实现生产快速交付。

运筹学、工程技术等领域科学专家的非常重视生产排程、调度的研究，科学家们将运筹学中的动态规划、决策分析等方法用于解决了调度和优化问题。业内通常认为调度理论研究开始于Conway R W，Maxwell W L，Miller A（1967）三人的调度研究^[1]，因此他们三人被称为该理论的奠基人。

20世纪70年代，科学家们开始注重调度复杂性问题的研究，Fischer M J（1972）提出了用于研究算法有效性和计算复杂度理论^[2]。Cook S（1971）在研究中指出很多调度问题是NP （Non-deterministic Polynomial，多项式复杂程度的非确定性）完全问题^[3]。20世纪70年代后期，作为应用数学的一门学科，经典调度理论逐渐成熟，但是经典理论和实际调度依然存在一些明显的偏差。

20世纪80年代初，科学家开始着力于解决实际调度问题，标志着调度研究从理论向应用的转变。以解决实际调度问题为目的人工智能、实时智能等智能调度方法应运而生。

由于产品结构定制化需求的大量增加，原来的模式是不够灵活的，解决制造系统调度作业灵活性已经成为一个严重的问题。张顺堂等（2020）面向多品种小批量的生产也构建了敏捷制造计划和控制系统体系，并通过这样的优化，使公司的生产效率有了明显改善^[4]。

3遗传算法及应用

随着调度理论研究的不断深入，排程优化也出现了很多新的方法。徐俊刚等(2004)研究中总结了常用的求解方法有数学规划法、启发式搜索法、系统仿真法、人工智能法、技术智能法、包括遗传算法的实时智能方法等^[5]。

遗传算法GA（Genetic Algorithm）是具备自组织、自适应以及自学习的一种全局搜索优化算法，其具鲁棒性和并行搜索能力非常出色。刘丹（2020）在研究中指出实际生产计划排程优化是用扩展排列编码的方式来调整零件加工顺序以及分配加工设备，通过染色体子代的不断交叉、变异和择优选择，最终获得偏移总量最小的排列组合^[6]。遗传算法过程如图1所示。

目前遗传算法和其他算法融合，以获取更快更优的结果。黄夏宝等（2020）^[7]、高勃等（2021）^[8]都有提出了一种遗传算法与模拟退火算法相结合的方案，解决了产品柔性分批和批量调度的问题。陈应飞等（2021）运用遗传算法结合粒子群优化算法、模拟退火算法，加快了算法的收敛速度，并获取更优的结果^[9]。张长泽等（2020）研究了基于模糊生产环境的模糊加工时间和模糊交货期综合问题，建立了以完工时间、平均满意度以及最小满意度作为的多目标函数^[10]等。

图1遗传算法过程

4 SMT生产排程数学模型建立

SMT生产的PCBA（printed circuit board assembly，装配印刷电路板）具有T（TOP）面和B(BOTTOM)面、阴阳板（即T面和B面交叉排布，也可视为两面拼版的一种特殊情况）和单面板三种形式。目前贴片机都是双轨，有多种生产模式可选择，如图2所示：双轨都生产B面再切换双轨同时生产T面的BB&TT-S生产模式，两条轨道分别生产B面和T面的B&T-I或类似的B&T-S生产模式。

图2SMT生产模式

本研究基于以下几项假设：

1)所有生产订单都是符合交付时间的订单；

2)生产线切换产品所需要的换线时间为固定值；

3)生产线上的设备生产过程中无机器故障发生；

本研究基于以下几项前提条件：

1)机器同一时间只能生产一个订单；

2)不同的生产线可以有不同的线型配置；

3)同款的产品在不同配置的生产线有着不同的加工时间；

4)不同的产品有不同的加工时间；

5)同款产品在同种生产线上可以采用多种生产模式；

6)单个订单只能采用一种生产模式；

7)不同订单的同款产品可以选择不同生产线、不同生产模式；

8)订单不可分割，一个订单只能在一条生产线上连续生产；

9)不同的生产模式在订单切换时需要额外的切换时间；

本研究目标是单位时间内产能最高，因此只要整体加工时间最少，其单位的产能就最大，所以可以将目标转化为总加工时间最小化。充分考虑SMT的生产工艺、工序等实际情况，得出数学模型目标函数：

产品数、生产线配置、生产线数量、生产模式、工序、订单为六个变量，当变量不断增大时，该问题变量呈几何倍数扩大，靠传统求解方法得到最优解非常困难。该模型是约束混合规划问题，属于

NP-Hard问题，需要采用智能优化算法来求解。

5 SMT排程遗传算法优化

遗传算法模拟了基因遗传的现象，从初始种群经过类似遗传的选择、交叉和变异，生成相对更适应的种群，多轮迭代后得到最适应环境的种群，即得到问题的相对最优解。

遗传算法运算流程的简易框架如图3所示，遗传算法主要运算过程包括七步：编码、初始化群体、适应度值评价、选择、交叉、变异、终止条件判断终止迭代。最后得到的最优解就是进化过程中产生的最大适应度个体。

图3遗传算法简易框架图

建立SMT排程遗传算法模型

1）遗传算法编码

SMT的排程为多线体、多模式结合组成的排程问题，本次研究在编码时采用双层编码规则。先根据给出基础信息中任务数量来建立编码的位数；双层基因分别包括两个信息：订单任务排序和订单选择的方案。第一层表示订单任务排序；第二层表示每个订单选择的方案，由于每个订单方案选择包括生产线配置、生产模式。

2）初始种群函数

本研究采用随机生成的方式获取初始种群，是最常用的方法，即初始解第一层是随机生成订单的安排顺序，第二层是随机生成选择的方案。

3）适应度函数

将总加工时间最小化作为适应度函数，设总加工时间为，适应度函数即表示为

4）选择函数

使用锦标赛方式进行选择，即从种群中随机采样s个个体（采样是有放回的），然后选择最优的那个个体进入下一代，只有当个体的适应度值优于剩余s-1个竞争者时才能赢得锦标赛。

5）交叉算子

通过随机产生两个基因中的两个位置，并将两个从大到小排列，确定变化位置后，把第二个父代相同编号的位置替换给第一个父代，把第一个父代相同编号的位置替换给第二个父代。对于实数排列组合编码的第一层编码，交叉选择的是子路径交叉；对于第二层编码，交叉使用的是洗牌交叉。

6）变异算子

第一层通过概率选择插入或者交换变异的操作，第二层采用高斯变异（Gaussian Mutation）。高斯变异操作是运用符合均值、方差的正态分布中的随机数值来替换原基因。

7）生成下一代函数

采用保留菁英取代法（elite preserve strategy），即将父代中合适度值高者保留一部分，其余的部分则由子代新染色体中合适度值较高者取代形成新一代的染色体。

8）停止准则

设计最大运行时间设置成无限大，只考虑迭代代数设置值，到运算到设置值之后停止。

本次研究基础数据基于Y公司电装车间一天生产排程。车间具备9条SMT生产线（2条XT3+1线体，7条1+1线体），3种生产模式（BB&TT-S、B&T-I和B&T-S生产模式），对应模式生产时工序B和工序T切换所需时间不同，基于28种生产产品种类和42个订单数为基础数据。

生产排程在未优化的情况下，最大排程时间为90340s，具体排程见图4。

图4 小批量生产排程（未优化）示意

图5小批量生产排程（遗传算法优化后）示意

由此可见，对于小批量生产遗传算法的优化效果非常明显。

6总结

本文针对电装SMT生产自动排程优化课题提出了解决方法，为SMT生产排程提供一种可推广借鉴的优化方式，不仅可为电子制造企业的排程优化打下数字化基础，也能为其他行业的生产排程起到一定的参考作用。本研究采用遗传算法作为优化算法，但其存在早熟和陷入局部极小点等问题，后续可以研究如粒子群优化算法、模拟退火算法或多种算法相结合的模式来优化，以改善算法缺陷，提高可靠性、准确度和计算速度。

参考文献：

[1]Conway R W，Maxwell W L，Miller A . Theory of Scheduling[J]. Addison-Wesley Publishing Co. Reading， Mass.-London-Don Mills，Ont. 1967.

[2]    Fischer M J . Complexity of Computer Computations[M]. Plenum Press，1972.

[3]    Cook S . The complexity of theorem-proving procedures.[C]. Proc Acm Symposium on the Theory of Computation. 1971.

[4]    张顺堂，胡鹏.面向敏捷生产的多品种小批量生产排程模型研究[J].现代制造技术与装备，2020，56(11)：203-208.

[5]    徐俊刚，戴国忠，王宏安. 生产调度理论和方法研究综述[J]. 计算机研究与发展， 2004， 41(002)：257-267.

[6]    刘丹.基于遗传算法的定制化高端地下装备关键生产瓶颈工序排程优化[J].制造业自动化，2020，42(05)：151-156.

[7]    黄夏宝，杨立熙，傅光炎.PCBA柔性作业车间等量分批调度问题研究[J].制造业自动化，2020，42(09)：89-94.

[8]    高勃，孙嘉玉，李学汉，赵宏军，王颖.面向智能工业的柔性装配批量调度优化策略[J].制造业自动化，2021，43(06)：57-62.

[9]    陈应飞，彭正超，胡晓兵，李彦儒.基于改进模拟退火-遗传算法的FMS生产排程优化分析[J].机械，2021，48(02)：7-16.

[10] 张长泽，李引珍，尹胜男，裴骁.多目标模糊柔性作业车间调度问题优化[J].科学技术与工程，2020，20(03)：1099-1106.