蚁群算法在板式家具生产调度中的应用

陈星艳，陶 涛，戴向东，黄艳丽，钱筱楠，郝绍平，王 迅，詹秀丽，吕 宙

(1.中南林业科技大学，湖南长沙 410004；2.农林生物质绿色加工技术国家地方联合工程研究中心，湖南长沙 410004；3.木竹资源高效利用省部共建协同创新中心，湖南长沙 410004）

在当前日益激烈的市场竞争环境下，家具企业的生产仍然面临着生产计划随意性大、凭经验调度生产、生产成本较高等阻碍家具企业发展的一些难题[1-2]。

蚁群算法作为一种人工智能算法，具有较强的鲁棒性和适应性，许多学者将其应用到一类典型组合优化问题中，其中包括生产调度问题，并获得了较好的效果。这为解决家具企业提高生产效率和降低生产成本难题提供了新思路，新方法。本文针对典型的几类生产调度问题，介绍应用蚁群算法求解这些调度问题的研究现状，主要从算法改进策略等方面进行总结分析，将蚁群算法应用于家具生产调度中，以完工时间最小为优化目标，提出进行调度优化编排的基本步骤，这些工作可以为后续研究提供求解思路。

1 蚁群算法在生产调度中的应用

1.1 生产调度类型

车间调度问题是指在一定的时间内，对资源进行分配，并满足某些特定的性能指标而对生产任务进行排序。一般地，在m台设备上，对n个工件的加工进行调度安排，可以将其分成以下几类：作业车间调度问题（JSP）、流水车间调度问题（FSP）和开放式车间调度问题（OSP）[3]。随着生产系统规模的扩大和生产方式的多元化，实际的生产调度问题常常以由若干种基本调度类型组合而成的形式呈现，具有随机和动态的特性[4]。

在作业车间调度问题中，已知工件的加工路径和完工时间，确定每台机器上的工件加工次序，以使其达到优化加工性能指标的目的，指标包括总完工时间最小等，这是一种复杂的多约束组合优化问题，应用蚁群算法时，一般将其转换成为在解构造图中找寻最佳路径问题[5]。

传统加工系统中的产品数量规模大，品类少，随着柔性制造技术的快速发展，传统的工艺规划逐渐演变为柔性工艺规划，由此出现了作业车间调度问题的扩展——柔性作业车间调度问题（FJSP），加入了机器选择环节，使得其中的某一道工序可以在多台机器上进行加工，某一台机器可以处理多个类型的工艺任务[6-7]，提高了求解难度，也更加符合现代生产实际。因此，对这一问题进行研究，比传统作业车间调度问题更具实际意义。

流水车间调度问题是一类特殊的生产调度问题，与作业车间调度不同，其每个工件按一定的顺序进行加工，它是在作业车间调度的基础上，使得工件通过的加工路线得到统一，通常用于大批量生产或具有连续生产布局的车间。与作业车间调度问题相比，流水车间调度问题求解难度更小。

基于以上特点分析，以及根据制造业的传统生产特性，本文选取作业车间调度、柔性作业车间调度、流水车间调度作为对象，论述蚁群算法在生产调度中的应用现状。

1.2 研究总结和分析

笔者分析了近十年来国内学者采用蚁群算法分析生产调度问题的百余篇文献资料，选取其中的代表性文章，总结出算法特点，如表1所示。

表1 国内学者分析生产调度问题的蚁群算法特点总结

可以发现，对于应用在生产调度问题上的蚁群算法的改进思路通常是在启发式函数中加入生产过程中的优先条件，约束规则等，大多研究内容的研究重点从启发式函数，信息素更新，状态转移规则等方面来对传统蚁群算法进行算法机制的改良，从而在收敛速度慢、易至局部最优的方面得到了改进。

同时加入最大最小蚂蚁系统、精英蚁群[22]、自适应调节策略、分布估计算法[10]等形成更为有效的、性能更好的蚁群算法。总结上述文献可以得出：

（1）多数研究对传统车间调度问题进行了探讨，而柔性作业车间调度问题的研究也越来越受到重视，针对更为复杂的求解过程，通常根据分步法，采取轮盘赌等方法完成机器分配的柔性处理，将其简化为经典作业车间调度问题求解。

（2）流水车间的研究相对较少，时间多集中于十几年前，近几年在考虑复杂工况的混流车间的研究在增多。

（3）使用单个优化算法对于问题的求解效果相对较差，将多个优化方法组合使用是未来研究的重点方向。

（4）在当前的个性化定制环境下，关于在智能制造平台中的生产调度问题研究文献较少，客户化定制时代的多品种小批量的生产调度问题也在引起关注。个性化定制模式下的制造模式给生产系统的柔性与物料的多样性带来了更大挑战。因此，在建模时，需将现有模型所不能涵盖的地方加以完善和扩展，例如内外干扰因素、通用工艺与个性工艺之间的区别与界定[23]。

（5）绝大多数针对生产调度问题的蚁群算法研究集中在分析证明改进算法的求解有效性，很少有针对行业的生产制造系统调度的某个具体问题设计一个算法流程框架，从问题特性，从参数选取、节点确定和约束导入来具体分析，切入标准蚁群算法过程的融合点，用于指导生产实践。从行业角度出发，考虑实际问题，例如在化工行业中，半成品的存放时间不宜过长，而在同一设备上进行相邻连续加工的产品性能差别也不能过大等[7]，这是一个重要的研究方向。

基于以上的分析，本文将研究重点集中在建立一个针对家具行业生产调度的蚁群算法模式，从而在后续研究中帮助相关具体问题能够得以优化。

2 在家具生产调度中构建蚁群算法的基本模式

2.1 家具企业生产调度现状

以板式定制家具产品为例，产品种类和零部件种类繁多，通常采用“订单组批+批量生产+订单分拣”的生产模式进行生产，通过揉单生产以实现原材料的利用率最大化，加工完成后再按订单进行分拣，以减少库存、提高效率、降低成本。目前，板式定制家具企业整体自动化程度低，现场作业车间较为混乱、管理水平低下[24]，多数情况下，采用静态排产的方式，只将产线的生产能力和交货时间作为考虑因素，或以人工干预为主，因此车间生产计划无科学规律可循，设备综合效率OEE(Overall Equipment Effectiveness)过低，增加了不必要的作业等待时间，延长了产品交付周期，降低企业的生产效率。主要是以下两个方面：

（1）由于多样化的订单数量占比大，造成了计划调度困难，容易产生漏单、重单等问题。

（2）生产计划的精细性不强，生产车间没有明确的生产指示，如果遇到紧急情况，比如紧急插单、补单，生产计划不能及时调整[25-27]。

通过蚁群算法可对以上问题进行相应解决：

（1）订单组批

利用蚁群算法，以聚类完成后所有类别的材料种类总数最少为目标，对同一天交货的订单进行聚类分析，从而减少家具生产时机器调整总时间，提高企业生产效率。

（2）矩形件排样

利用蚁群算法，以开料工序原材料利用率最大化为目标，对原料板材的下料方式进行分析，从而优化板件的排样问题，提高批次的原材料利用率。

（3）生产作业排产

利用蚁群算法，以批次订单生产总时间最小化为目标，对板式定制家具车间调度方式进行分析，从而有效分配设备资源，提高车间生产效率，得到科学的生产计划方式。

2.2 构建适用的家具生产调度模型

家具生产调度问题可以描述为：有m个可进行加工的设备，共n个有特定加工路线的零部件待加工[28]，已知每个零部件的完工时间，且不同工序之间有一定的先后次序，每道工序可用不同的机器进行处理，但是根据设备的性能，加工时间也会随之变化。通过对资源的灵活安排，选择机器来处理每道工序，并明确每个工件的开工时间和完工时间，从而在最短的时间内完成全部的工作，从而提升效率减少成本。采取单个模型，描述整个复杂的调度集成问题，将对问题的求解步骤拆分成为产品分批、设备指派、批次排序三个连续阶段，再进行蚁群算法的设计，对每个阶段进行优化，最后使得所有家具产品总加工流程时间最短。

家具企业的实际排产过程与蚁群算法即蚂蚁在城市间寻址觅食的过程有许多相似之处（表2）。因此，采用蚁群算法对家具零件加工排产过程进行研究时，可将其加工过程转化为蚁群的觅食方式，再进一步建立家具零件加工工序排产调度的蚁群算法模型。

表2 家具零件加工工序的生产调度和蚁群算法的相似性

根据以上建立板式家具车间调度数学模型：

目标函数为总的加工时间最短。其表达式为:

其中，MS为所有板件的最后完工时间，MPk为所有板件在机器k上的完工时间。

约束条件具体为：

（1）顺序约束: 具有相同工艺要求的工件在相邻工序之间的加工次序是开料、封边、排钻、包装。其表达式为：

该式表示板件i的第j道工序必须在j-1工序道工序结束后进行，比如板件在封边工序完成之后，排钻工序才能开始。其中Eijk为板件i的第j道工序在机器上的完工时间，mijk为板件i的第j道工序在机器k上的加工时间，k=1,2,...,M。

（2）资源约束: 同一机器k开始加工一个任务的时间，需要在上一个加工任务完成后才能进行，即电子开料锯，柔性封边机、六面钻、包装线上只能加工一项任务。其表达式为:

该式表示在任意给定时间内，机器k无法同时处理两个不同的板件或两道不同的工序。其中Eegk为板件e的第g道工序在机器k上的完工时间，EijM为板件i的第j道工序在相应的机器k上的完工时间，megk为板件e的第g道工序在机器k上的加工时间。

2.3 制定基本算法步骤

设定各参数，确定蚂蚁数量m1，m2，m3。

步骤1 产品分批：

根据家具产品中包含的零件数量，划分若干任务并形成任务集，生成蚂蚁a1，依据随机原则，选择一个任务作为游历的第一个节点，并规定已游历节点禁忌表。在此基础上，按照状态转移规则，从任务集中选取节点，并进行重复选取，直到蚂蚁a1遍历了全部的任务节点。

步骤2 生成批次序列并对批次进行调度：

Ⅰ、指派初始工序设备。初始化各设备的可用能力，形成设备集，生成蚂蚁a2，从设备集合中选取设备，设置已游历批次禁忌表，更新设备能力信息，重复选择设备，直到蚂蚁经历全部批次节点，获得最终设备分配方案。

Ⅱ、对各设备进行批次排序。按照前一步的设备指派方案，对每台设备的加工批次进行统计，从设备集中取出设备，并计算该设备上所有批次的加工开始时间和加工完成时间，以工序的加工时间为蚂蚁的遍历路径长度，加工时间越长，节点信息素浓度越低，这时就需要更新蚁群算法的信息素浓度。

步骤3 获取搜索到的调度结果：

判断是否满足终止算法条件，最终以最短完工时间最小的路径为最终的搜索结果，据此得到生产调度结果。

3 结语

本文通过总结蚁群算法应用于生产调度问题研究现状，分析出了不同调度类型的算法运用特点、优化算法在求解过程中的优缺点以及求解方式与手段，提出将蚁群算法应用到板式家具生产车间调度问题是可行的，然后针对家具企业构建基于蚁群算法的生产优化调度基本模式。

蚁群算法作为一种新型的仿生式智能算法，将其应用在生产调度方面时，在理论改进、模型优化、变量与实际约束映射应用等方面都是一个长久的研究内容，未来蚁群算法在各个领域将会展现出强大的生命力和具有广阔的发展前景。