基于仿真的FFS设备能力优化配置*

范飞龙，李 翔，2

（1.广东工业大学广东省计算机集成制造系统重点实验室，广东广州 510006；2湖南省湘南学院物理与电子信息工程系，湖南郴州 423000）

基于仿真的FFS设备能力优化配置*

范飞龙1，李 翔1，2

（1.广东工业大学广东省计算机集成制造系统重点实验室，广东广州 510006；2湖南省湘南学院物理与电子信息工程系，湖南郴州 423000）

首先，以制造系统的最小总投资成本为目标函数、系统的平均产出率为约束条件构建设备能力优化配置问题的数学模型。其次，鉴于该数学模型中约束条件的数学表达式难以用决策变量（设备数量）的封闭形式加以描述的难题，运用eM-plant软件搭建仿真平台进而计算出系统的平均产出率。然后，运用分支定界法精确求解CCP问题。最后，通过对实例的求解分析验证求解方法的实用性和有效性。

设备能力优化配置（CCP）；仿真；分支定界法

0 引言

目前而言，个性化的客户订单和及时化的交货期严重困扰并制约着定制型装备制造企业的生存发展。为了在竞争激烈的市场环境下获取尽可能多的客户订单，订单交货期已上升到与产品报价同等重要的地位[1]。为了能够及时响应个性化的订单，企业通常购买大量具备复合型、智能型等现代特征的加工设备。然而现实情况是，企业领导层制定购买设备的决策时，经常只是凭借经验而缺乏足够的理论依据。如此一来，通常会发生如下两种现象：其一，设备产能过剩，即是现有的设备加工能力大于客户需求，使得加工设备的闲置率提高、利用率降低，从而造成资金的浪费；其二，设备产能不足，即是现有的设备加工能力难以满足客户需求，客户的订单便无法及时交付，甚至影响到企业的信誉度。

文献[2]将制造系统最优化问题总结为三类，即在满足系统性能约束指标下实现加工设备总投资额的最小化、在满足优先投资预算下使系统的某项指标最优化、将制造系统拆分成若干制造单元并以此来改善制造系统总体性能。文献[3]研究订货型车间的任务投放问题，对有限缓存无阻塞的情形进行仿真，并对每道工序有一台或多台加工设备的两级Flow Shop问题进行了探讨。文献[4]研究确定性环境下连续需求的能力优化配置问题，以实现设备配置成本的最小化为目标，以满足生产需求为约束条件，提出了一种排序决策方法，用分枝定界方法和启发式方法对能力配置问题进行求解。文献[5]研究工业企业的设备能力优化配置问题，以收集、分析以及整理生产实际数据为基础，建立仿真模型，通过分析仿真结果寻找生产瓶颈。文献[6]基于车辆能力规划系统，将能力优化配置问题转换成一个受时间窗约束的车辆路径规划问题并进行仿真建模，并使用禁忌搜索算法对模型进行求解。

仿真法是在一系列近乎真实的假设和前提下，求解制造系统的性能指标。针对约束函数无法用决策变量的封闭形式加以表达的难题，可以使用状态空间分解法或者扩展近似法等方法加以解决。本文拟采用分支定界算法求解CCP问题，考虑到近似算法可能对最终结果产生影响，求解约束性能指标时使用仿真法。

1 数学描述

1.1 条件假设及目标函数

本文从企业的实际情况抽象出一个单种类产品多级FFS典型制造系统模型，具体如图1所示。该车间有多道加工工序，且每级设备前设置一个公共缓冲区（有限容量）。

图1 定制型装备柔性流水车间排队网通用模型

在数学模型建立前，先作如下假设：

①同类型设备的单价相同；

②工件以“泊松流”的方式到达制造系统；

③产品的加工工艺已知；

④设备的加工时间服从负指数分布，且彼此之间相互独立；

⑤工件之间彼此相互独立；

⑥一台设备仅能同时加工一个工件；

⑦各节点缓存（buffer）容量有限。

1.2 数学模型

CCP问题的主要研究内容是在企业现有的资源条件下，以系统的平均产出率作为约束条件，对加工设备优化配置以使设备总成本最小化。该优化问题的数学模型表述如下：

对模型（1）的各个参数作如下定义：

xi：表示制造系统第i级设备的数量；ci：表示制造系统第i级设备的单价；：表示制造系统总设备成本；：表示制造系统的平均产出率；Θ*：表示制造系统的预设产能；ς：表示随机元。

不难得出CCP问题的特点：（1）约束函数表达式难以用设备数量的封闭形式表达；（2）该问题是随机整数规划问题。特点1加大了求解模型的难度，为了能够有效地求解系统的平均产出率，本文使用eM-plant软件搭建仿真平台来计算模型的约束指标。根据特点（2），本文拟采用分支定界法。

2 设备能力优化配置仿真建模

2.1 仿真模型建立

采用eM-Plant仿真软件（Tecnomatix Plant Simulation8.2）搭建仿真实验平台，硬件配置如下：双核CPU 2.0GHz，2G内存，如图2所示。

仿真系统由四个制造单元组成，工件均在订单源产生。工件首先根据第一级加工设备前的缓存堵塞状况判断工件进入缓存（B1），或者根据加工设备的状态判断是否进入加工设备加工，如果第一级缓存（B1）已满，且第一级各加工设备上均有工件，则由订单源产生的工件进入Buffer0（无限容量）。表示订单源，服从泊松分布；表示缓存，其大小可根据实际需要进行灵活调整；表示加工设备，每级设备的数量可根据优化配置的结果不断进行调整；用来获取稳定状态下的平均产出率。

图2 Tecnomatix Plant Simulation8.2仿真系统

2.2 分支定界法

前人经常使用分支定界算法求解线性整数规划（Linear Integer Programming，ILP）问题，目前求解ILP问题的软件大多以分支定界算法为其核心思想，如LINDO Xpress-MP、、CPLEX等等[7]。一般ILP问题p0的数学模型表述如下：

其中，c∈Rn，A∈Rm×n，b∈Rm，x为决策变量。

一般的分支定界法求解步骤如图3所示。

图3 分支定界法求解步骤

为了更形象地描述本文所使用的分支定界算法，将分支示意图描述如图4所示。

图4 分支定界求解示意图

即二级系统每级的设备数量分别为n1和n2，该设备组合向量（n1，n2）是可行解。在对其进行优化配置时，首先分成3支，即（n1-1,n2）、（n1,n2-1）和（n1-1,n2-1），判断三者是否均为可行解，如果均是可行解，则选择是制造系统总成本最小（n1-1,n2-1）的一支作为较优解继续进行分支，同时将（n1-1,n2）、（n1,n2-1）所对应的目标函数值作为上界；如果三者均为不可行解，则（n1，n2）即为最优解，如果（n1-1,n2） 和 （n1,n2-1） 是可行解，（n1-1,n2-1）不是可行解，则将（n1-1,n2-1）所对应的目标函数值作为下界，同时从（n1-1,n2）和（n1,n2-1）选择目标函数值最小的一支继续分解，另一支所对应的目标函数值作为上界。以此类推，直至找到最优解（ni,nj），此时（ni,nj）的所有分支均是不可行解。

3 算例分析

3.1 算例数据

针对CCP问题的具体特征，本文构建的算例主要包括工件到达率（λ）、设备类型、设备数量（ni）、设备单价（ci）等信息。具体如表1所示。

表1 初始参数设定

另外，在求解CCP问题时，应该首先确定系统各级的buffer容量，即各级设备前公共缓冲区的容量。具体如表2所示。

表2 buffer容量设定

另外，由表1得知系统平均产出率为0.9。一般而言，真实的设备产出率与无限缓存下系统的平均产出率之间的关系比例值为0.9，即Θ*=0.9× 0.9=0.81。

CCP问题的算例需遵守如下规则：

（1）各级设备的加工能力之和原则

表3 CCP问题优化前后对比

式子（1）表示各级设备的加工能力之和(μi×ni)应大致相等，式子（2）表示各级设备的加工能力之和(μi×ni)应呈“倒喇叭形”且略大于工件到达率(λ)。由表1知， μ4×n4=1.17、μ3×n3=1.10、 μ2≥n2=1.02、 μ1×n1=0.96、 λ= 0.90。不难看出，从加工能力原则看，算例是合理的。

图5 优化前、后设备数量变化图

（2）各级缓冲区的容量原则

前面工序被阻塞的概率比后面大，对缓冲区容量进行设置时，前面缓冲区容量需大于（或等于）后面的缓冲区容量，即B4+n4≤B3+n3≤B2+n2≤B1+n1。 由 表 1知 ，B4+n4=18 、 B3+n3=18 、 B2+n2=33 、B1+n1=46。不难看出，从缓冲区容量原则看，算例也是合理的。

3.2 结果对比与分析

由表3知，优化前、后设备组合向量分别为：Xf=（12，17，11，13）T、Xa=（12，16，10，12）T。为了形象地描述优化的效果，本文运用直方图表示优化前、后各级设备数量的变化，具体如图5所示。

第一、二、三、四级设备分别减少了0、1、1、1台，共降低成本253万元。系统的平均产出率也得到一定程度的优化，优化前平均产出率为0.897，比系统预设产能超出了9.7%；优化后平均产出率为0.837，比系统预设产能超出了3.2%。

由表3知，优化后的各级产能分别为：μ4×n4=1.08、 μ3×n3=1.00、 μ2≥n2=0.96、μ1×n1=0.96；各级缓冲区容量： B4+n4=34、B3+n3=32、B2+n2=17、B1+n1=17。所以，优化后的结果是合理的。

4 结束语

本文首先根据问题特征建立数学模型，然后使用仿真法求解数学模型的约束性能指标，并在此基础上使用分支定界算法精确求解CCP问题，具有一定的工程价值。美中不足的是本文所使用的分支定界算法的核心——分支原则没有产生高效的分支策略，在后续的研究中，笔者着重于CCP问题的具体特征提出一种高效的分支策略。

［1］A.haskose，B G Kingsman，D worthington.Modelling flow and jobbing shops as a queueing network for work⁃load control［J］.International Journal of Production Economics，2002，78（3）：271-285.

［2］Bitran，G.R.，Morabito，R..An Overview of Trade-off Curves in Manufacturing System Design［J］.Produc⁃tion and Operations Management， 1999， 8（1）：56-75.

［3］陈田，陈庆新，毛宁，等.具有两道工序的柔性同序加工车间任务投放策略［J］.工业工程，2010，13（5）：69-74.

［4］Neebe，A.W.，Rao，M.R.Sequencing Capacity Ex⁃pansion Projects in Continuous Time［J］.Management Science，1986，32（11）：1467-1479.

［5］Eneyo，E.S.，Pannirselvam，G.P.The use of simula⁃tion in facility layout design：a practical consulting expe⁃rience［C］.1998.

［6］Loo，H.L.，et al.Vehicle capacity planning system：a case study on vehicle routing problem with time windows［J］.Systems， Man and Cybernetics， Part A： Sys⁃tems and Humans， IEEE Transactions on.2003，33（2）：169-178.

［7］于战科，倪明放，汪泽焱，等.整数线性规划的改进分支定界算法［J］.计算机应用，2011，31（2）：36-38.

Simulation-Based Capacity Configuration Optimization for Flexible Flow Shop

FAN Fei-long1，LI Xiang1，2
（1.Guangdong Provincial Key Laboratory of Computer Integrated Manufacturing System，Guangdong University of Technology，Guangzhou510006，China；2.Hunan Xiang Nan University Department of Physics&Electronic Information Engineering，Chenzhou423000，China）

First of all，construct the Mathematical model of capacity allocation optimization problem(capacity configuration problem，CCP)with the minimum total investment cost as objective function and the average output rate of the system as the constraint condition. Secondly，the mathematical expressions of constraint condition in this mathematical model is difficult to use closed form of the decision variables(equipment)to describe，the simulation platform is built up and then calculate the average output rate of the system by using Em-plant software.Then，using the branch and bound method to exactly solute of CCP problem.Finally，verify the practicality and effectiveness for solving method by solving the case analysis.

capacity configuration problem（CCP）；simulation；branch-and-bound algorithm

TP391 F406

：A

：1009－9492(2014)10－0016－04

10.3969/j.issn.1009-9492.2014.10.005

范飞龙，男，1987年生，河南人，硕士研究生。研究领域：制造系统设计优化。

(编辑：阮 毅)

*湖南省湘南学院院级重点教改项目

2014－04－01