基于蚁群算法的柔性作业车间问题求解

何奔洋

（福州大学 经济与管理学院，福建 福州 350111）

0 引言

随着科技的不断发展，社会环境也逐渐变得复杂多变，随之而来的是产品的差异化与顾客需求的个性化逐渐地增强。对生产企业来说，制造的产品也从单一品种大批量向多品种小批量逐渐演变。对于这种变化，传统的生产调度方式已难以适应，故柔性作业车间调度已逐渐成为生产企业提升经济效益的重要手段之一。柔性作业的调度方式通过对资源的合理分配及利用，从而达到目标最优值，能够减少资源浪费，更好地适应如今的社会需求环境，故此，对于柔性作业车间调度问题的研究也显得十分必要。赵诗奎等对作业车间调度问题的模型及求解算法进行了总结，并对作业车间调度问题的发展前景进行了展望[1]，王凌等则对分布式车间调度问题的优化算法进行了分析与总结[2]，张亚明对柔性制造生产方式进行了深入的讨论[3]，李爱平等则针对零件族为对象对柔性生产线进行了设计与优化[4]，余璇等提出了混合遗传禁忌搜索算法对多目标柔性作业车间调度问题进行了求解[5]，何东东搭建了柔性作业车间调度问题模型并以改进遗传退火算法求解[6]，李涛等以卷烟制丝的生产为例对柔性制造技术进行实际应用[7]。

蚁群算法是通过模拟蚂蚁觅食的一种优化算法，最早应用于TSP问题的解决，后被应用于各项优化问题的求解中。因此，基于以上研究，本文引入了蚁群算法对柔性作业车间的调度问题进行求解，以柔性作业车间调度问题中最大完工时间的最小化为目标，搭建了优化模型，并引入了实例，验证了模型的适用性及蚁群算法在求解柔性作业车间调度问题的可行性。

1 模型建立

1.1 问题描述

柔性作业车间调度问题可以描述为：有m个进行加工的器械，共n个零件待加工。第i个零件的工序数为qi且qi＞1，对于相同零件的工序加工顺序有要求；每道工序至少可由一个机器进行生产，并且同一道工序经不同的机器加工时间也不同；不同的零件之间的工序可以不同。通过灵活地调度资源，以进行对各道工序的加工顺序、加工机器的合理分配，从而实现工序最大加工时间最小的目标，以提升效率减少成本。

1.2 模型分析

在对工序的时间和资源进行分配及安排时，常常会遇到许多现实问题，因此，为了令模型更加地贴近实际，模型需满足以下约束条件：

（1）任一工序可用的加工机器数大于一；

（2）同一时刻每个加工器械仅可加工一道工序；

（3）每个零件的任一工序仅可加工一次，且同一时刻仅可由一个机器加工；

（4）每道工序开始加工后必须加工完成，不可中断；

（5）每个零件的不同工序间存在顺序要求，不同零件的工序间不存在顺序要求。

模型主要参数包括：

Fij：工序Oij加工完成的时间

Fijk：工序Oij在机器Mk上结束加工的时间

Bijk：工序Oij在机器Mk上开始加工的时间

pijk：工序Oij在机器Mk上的加工时间

1.3 模型建立

根据上述分析，建立工序最大完工时间的最小值优化函数为：

由上即为优化模型，其中：公式（1）为目标函数，表示求所有的零件中最大的工序加工时间的最小值；公（2）表示的是工艺约束，即每个零件的各个工序必须按照顺序进行加工；式（3）表示每道工序由一台机器加工且仅可加工一次，且开始加工后必须加工直至完成不可中断；式（4）为同一加工机器在同一时间仅可加工一道工序。

2 算法设计

本文使用蚁群算法对问题进行求解。蚁群算法是通过模拟蚂蚁觅食的生物行为，根据蚂蚁走过的每条支路的长短等因素来计算支路上信息素的浓度，并根据信息素浓度的大小来计算选择该支路的概率，并以轮盘赌的方式决定是否接受此解，从而在全局范围内搜索满意解。本文算法流程如图1所示。

图1 算法流程图

蚁群算法首先进行各参数的初始化，随后蚂蚁随机选择觅食路径，并在路径上留下分泌的信息素，信息素浓度与路径的长短成反比，同时信息素会挥发。后续蚂蚁进行搜索时会根据信息素的浓度选择路径，信息素浓度更高的路径会有更大的概率被选中。随着搜寻蚂蚁数量的不断增多，信息素的浓度会逐渐增高，最终搜索出最优的方案。

3 实验计算

3.1 算例数据

为验证优化模型及算法的实用性，引入了算例对模型及算法进行仿真比较。表1中给出了6个零件以及10个加工机器的实例。其中包括了每个零件的各道工序的可加工的机器及不同机器上的加工时间。每列工序下左列为该道工序可进行加工的机器设备，右列为不同机器上的加工时间，每道工序均有至少一个机器进行加工，每个零件具有6道不同的工艺。

表1 零件加工实例

3.2 算法参数设置

对于本文所使用的蚁群算法，需要事先设置算法初始参数，参数设置如表2所示。

表2 算法参数设置

3.3 实验结果

本文采用MATLAB编程求解。通过求解得到最优解为47min，可得到最小工时为47min的甘特图，最优解甘特图如图2所示。根据甘特图进行结果分析可得到，机器平均利用率为44.1%，其中机器1与机器10利用率最低，仅为6.4%，利用率远低于平均利用率，而利用率最高的机器4与机器5则高达80.9%，最高机器利用率和最低机器利用率之间相差较大。所以在日常生产加工过程中，企业可针对利用率低的机器1和机器10进行改善，解决其利用率过低的问题，提高资源利用率。同时对于利用率较高的机器4和机器5需要做好日常维护，防止其因为使用过度而出现损坏等现象。

图2 最优解甘特图

由图3，给出了蚁群算法求解结果的目标函数优化曲线。由图可见，目标函数迭代至第10代即可得到最优值，从最初的54min下降至最优解47min，显示了良好的收敛效果。通过优化模型优化后，加工总耗时相较优化前降低了13.0%，显示了良好的优化效果，由此可见本文模型可以大幅度减少生产作业中柔性调度的完工时间，对柔性作业车间调度问题有良好的优化效果。并从实例中可看出，蚁群算法在计算中表现良好，能够有效地求解出最优解，并可适用于柔性作业车间调度问题的模型求解中，在解决柔性作业车间调度问题中具有较强的实用性。

图3 算法迭代图

生产力不断发展，社会也不断地进步，单品种大批量制造中常用的调度方式已出现灵活度差、难以适应强个性化需求等种种问题，柔性作业车间调度的方式逐渐成为主流。本文基于此根据实际情况设立了约束条件，以完工实际最小化为优化目标搭建了整数规划模型。采用了蚁群算法对模型进行求解，并为验证模型和算法的实用性和应用价值引入实例进行仿真对比。从结果中可以看出，本文所设计的算法及搭建的模型具有较好的优化效果及收敛性，可作为生产柔性调度作业问题中的优化求解工具。在今后的生产作业优化中也具有较大的实用性，可根据具体情况灵活求解不同问题，具有较高的使用价值。