基于模拟退火算法的MTS型实木家具生产调度优化研究

■康友冰，王张恒，孙德林 Kang Youbing & Wang Zhangheng & Sun Delin

(中南林业科技大学材料科学与工程学院，湖南长沙，410004）

MTS型实木家具企业作为一种典型的家具生产企业，产品种类繁多，且制作工艺复杂，导致家具生产调度和生产控制的难度较大。随着家具更新换代的速度不断加快，实木家具产品的生命周期越来越短，这对家具生产调度提出了更高的要求。同时，由于交货期不断的缩短，进一步加大了家具企业生产调度的难度[1]。我国家具企业经过多年的努力，装备水平已经逐渐赶上发达国家，但在生产调度理论和实践经验方面还存在着较大的差距,企业中仍普遍存在着生产随意性较大、生产调度不够科学以及作业排序混乱等问题。

目前国内外，遗传算法和蚁群等智能优化算法已经被运用于解决家具生产调度问题，并且取得了一定的成果。例如：吕玉翠[2]利用启发式算法对板式家具的生产调度问题进行求解，优化了板式家具生产调度。丁传让[3]研究了基于蚁群算法的家具生产调度方法，使家具生产调度的效率得到了很大的提升；沈国锋[4]利用遗传算法对美式家具的生产调度方法进行了优化研究，提升了生产调度的效率。模拟退火算法(Simulated Annealing, SA)是模仿金属退火过程的一种高效的启发式优化算法，基本思想是在一个固定的温度下，算法会从一个状态随机的搜索到另一个状态，然后由不断变化的概率值来判断当前解是否为最优解，随着温度的不断下降直到降低到一个最低温度，搜索过程将会以概率1停留到最优解。模拟退火算法具有很强的全局优化性能和鲁棒性，它的搜索方式简单有效，既避免了数值算法的高计算量和蚁群算法收敛速度慢的缺点，又避免了遗传算法局部搜索算法过早收敛于局部最优解的缺点[5]。根据实木家具的生产特点，模拟退火算法的原理与实木家具生产调度问题的优化过程极为相似。

■图1 待加工产品实物图

因此，为了解决MTS型家具企业存在着生产随意性较大、生产调度不够科学以及作业排序混乱等问题。本文将模拟退火算法运用到MTS型实木家具生产调度问题中，利用秒表计时法和综合类比法获得产品的加工工时，并采用python软件进行仿真实验，以最小化最大完工时间为目标函数进行优化，利用模拟退火算法找到一种科学的生产调度方法，以提高MTS型实木家具生产调度的合理性、科学性和秩序性。

1 实木家具生产调度产品加工工时的测定方法

实木家具产品的加工工时是模拟退火算法进行生产调度优化的数据基础，产品的加工工时是指利用各种技术来确定合格工人按作业标准完成产品某一工序所需要的时间[6]。MTS型实木家具企业产品的加工工时的测定，一般采用秒表计时法和综合类比法两种方法结合的方式进行。

（1）秒表计时法

秒表计时法是根据家具生产现场作业的内容，以自主设计的表格为基础，用秒表进行计时，将获得的数据记录在表格中，每个产品的工序工时需重复计时多次，计算出平均值，但工人进行图纸校核、划线、调机以及产品零件的待料等其他操作时，不计入加工时间内[7]。

（2）综合类比法

综合类比法是指以家具产品的加工单元为中心，采用统计方法将相同或者类似的加工单元归类，总结出加工工时表。在掌握家具产品的加工工序和动作分解的基础上，利用加工工时表组合出产品工序的标准工时。综合类比法主要用于加工特点具有相似性的类似家具产品和类似的工序[8]。

■图2 模拟退火算法进化折线图

2 基于模拟退火算法的MTS型家具生产调度优化

2.1 MTS型家具企业生产调度问题模型描述

MTS型家具生产调度的模式是基于生产库存，由设计、销售和生产等部门共同确定下一个生产周期所需要生产家具产品的类型和数量。根据这个特点，MTS型家具企业生产调度问题可以总结为作业车间调度问题（Job shop scheduling problem ,以下简称JSP），即整个家具加工系统有N个产品等待加工，一共有M个加工工序，需要M个加工机器，各工序的加工时间和每个产品的加工工序顺序已确定，每个产品必须严格按照给定的顺序加工[9-11]。生产调度优化的最终目标是确定N个产品的加工顺序，在满足所有约束条件的情况下使得完成所有加工工序的总加工时间最短。综上所述，可以将MTS型家具企业JSP问题的约束条件描述为：

（1）家具零部件的每道工序必须在固定的机器上加工；

（2）当家具零件的前一道工序加工完成之后才能继续下一道工序；

（3）某个时刻某个机器只能加工一个家具零部件；

（4）某个零部件在某个时刻只能在一台机器设备上加工；

（5）产品的工序顺序和加工时间已知；

（6）N个产品在确定加工顺序时具有相同的优先级。

2.2 基于数学模型的生产调度问题求解

2.2.1 MTS型实木家具生产调度数学模型

在不考虑插单的情况下，企业在接受多个同等重要的订单时，需要根据订单合理进行生产调度，面临如何进行订单的排序才能使生产车间在最少的时间内加工完全部产品。因此，将MTS型家具企业作业车间生产调度问题的优化目标设为最小化最大完工时间。达到这个目标只需要找到最后一台机器的完工时间最小值。令G为此数学模型的目标函数，(i，j)表示作业i的第j个工序。Sij和Eij分别表示(i，j)的加工起始时刻和加工时间[12-13]。Ck为第k台机器的完工时间，则问题的数学模型如下：

■图3 优化前后的生产调度甘特图对比

公式①为目标函数，使最迟完工的机器加工时间最短；公式②表示1个作业只能在加工完成前一道工序后才可以加工后一道工序；公式③表示每个零件开始加工第1道工序的起始加工时刻大于或等于0。

2.2.2 算法的伪代码编写

根据问题的数学模型，利用PyCharm Community Edition 2021.2.2软件进行算法代码的编写，需要设置的参数包括：最大温度、最小温度、链长、冷却耗时，由于模拟退火算法对参数的设置没有明确的规定，通过已有文献[14]对不同参数组合的研究，确定优化参数如表1所示。

表1 模拟退火算法的最优参数

2.2.3 实例分析

某新中式家具公司木工生产车间接到了来自设计部的6个产品需要加工，如图1所示，分别是A、B、C、D、E、F。

根据生产工序，这6个产品分别要经过下料、刨光、砂光、开榫、钻孔和铣型等加工工序，分别用编号1、2、3、4、5、6表示[15]。利用秒表计时法和综合类比法得出了各产品的加工工时如表2所示。

表2 产品加工用时表（单位：分钟）

根据各产品的加工时间和机器，对每个产品的每道工序进行编号处理，编号（m,n）中m代表当前的工序必须要在第m台机器上加工，n表示当前的工序的加工时间，加工时间的单位为1，机器的作业编号从1开始。例：产品X[（m1，n1）（m2，n2）（m3，n3）……（mx，ny）] ，根据上述编号的规则构建相应的矩阵。

产品A[（1，11）（2，24）（3，29）（4，12）（5，22）（6，29）]

产品B[（1，16）（2，29）（3，32）（4，19）（5，27）（6，28）]

产品C[（1，9）（2，18）（3，25）（4，16）（5，16）（6，18）]

产品D[（1，12）（2，34）（3，27）（4，18）（5，25）（6，26）]

产品E[（1，14）（2，25）（3，26）（4，11）（5，19）（6，21）]

产品F[（1，10）（2，26）（3，24）（4，17）（5，13）（6，19）]

根据矩阵，在此生产实例中共有36道工序。假如按照传统的排序方法，共有720种不同的排序方法，企业安排合理的生产调度的工作量极大[16-17]。鉴于模拟退火算法在组合优化问题中具有良好的表现，利用模拟退火算法对上述实例进行生产调度优化[18-19]。

2.2.4 仿真实验与结果分析

根据表1和表2，进行仿真实验，从图2中可以看出算法在进化到13代以后，最优解趋近于极值，说明此时得到了最优解。程序的运行结果输出值包括best_x和best_y，其中best_x代表产品的最优加工顺序，即为A-B-D-C-E-F, best_y表示最小化最大完工时间，即产品的最小化最大完工时间为254min。

利用CAD软件输出了最优排序方案的生产调度甘特图，通过甘特图可以清楚地看到最优的加工顺序、每件产品的加工进程和某道工序的设备空闲时间。为了验证模拟退火算法对MTS型家具生产调度的科学性，将模拟退火算法仿真实验的排序结果（图2b）与该实木家具车间实际采用的一般经验法所得排序结果（图2a）对比，通过图中的数据可以得出，模拟退火算法得到的排序方案的最小完工时间为254min，相比于一般经验法得出的排序方法的用时减少了23min，整体的生产效率提升了8.3%。通过以上对结果的比较分析，证明了模拟退火算法在求解MTS家具企业JSP问题的可行性和有效性。

上述仿真实验的样本数量为6件，在实际生产中样本的数量会成倍增加，而且不同的产品加工时间也会产生巨大的变化。基于一般经验法生产调度的难度会进一步增加，而模拟退火算法只需要在新产品的打样期间记录各工序所花费的加工工时，将其汇编成带有加工机器编号和加工时间的矩阵，再转换成计算机语言输入到模拟退火算法的程序中，即可得出最优的生产排序方法，具有广泛的适用性。

3 结语

生产调度问题是实木家具企业生产过程中的重点问题，科学合理的生产调度对提高企业生产效率具有重要影响。家具产品排序是家具生产调度的核心，利用智能优化算法可以高效地解决此类组合优化问题。根据MTS型实木家具企业的生产数据，利用模拟退火算法程序输出了最优的排序方法，证实了模拟退火算法在解决MTS型实木家具企业生产调度问题的可行性，企业管理人员可以参考该方法得到的结果制定生产调度方案，可以有效地缩短产品的总加工时间，提高产品的生产效率。