范飛龍，李 翔，2

（1.廣東工業(yè)大學(xué)廣東省計算機集成制造系統(tǒng)重點實驗室，廣東廣州 510006；2湖南省湘南學(xué)院物理與電子信息工程系，湖南郴州 423000）

基于仿真的FFS設(shè)備能力優(yōu)化配置*

范飛龍1，李 翔1，2

（1.廣東工業(yè)大學(xué)廣東省計算機集成制造系統(tǒng)重點實驗室，廣東廣州 510006；2湖南省湘南學(xué)院物理與電子信息工程系，湖南郴州 423000）

首先，以制造系統(tǒng)的最小總投資成本為目標(biāo)函數(shù)、系統(tǒng)的平均產(chǎn)出率為約束條件構(gòu)建設(shè)備能力優(yōu)化配置問題的數(shù)學(xué)模型。其次，鑒于該數(shù)學(xué)模型中約束條件的數(shù)學(xué)表達式難以用決策變量（設(shè)備數(shù)量）的封閉形式加以描述的難題，運用eM-plant軟件搭建仿真平臺進而計算出系統(tǒng)的平均產(chǎn)出率。然后，運用分支定界法精確求解CCP問題。最后，通過對實例的求解分析驗證求解方法的實用性和有效性。

設(shè)備能力優(yōu)化配置（CCP）；仿真；分支定界法

0 引言

目前而言，個性化的客戶訂單和及時化的交貨期嚴重困擾并制約著定制型裝備制造企業(yè)的生存發(fā)展。為了在競爭激烈的市場環(huán)境下獲取盡可能多的客戶訂單，訂單交貨期已上升到與產(chǎn)品報價同等重要的地位[1]。為了能夠及時響應(yīng)個性化的訂單，企業(yè)通常購買大量具備復(fù)合型、智能型等現(xiàn)代特征的加工設(shè)備。然而現(xiàn)實情況是，企業(yè)領(lǐng)導(dǎo)層制定購買設(shè)備的決策時，經(jīng)常只是憑借經(jīng)驗而缺乏足夠的理論依據(jù)。如此一來，通常會發(fā)生如下兩種現(xiàn)象：其一，設(shè)備產(chǎn)能過剩，即是現(xiàn)有的設(shè)備加工能力大于客戶需求，使得加工設(shè)備的閑置率提高、利用率降低，從而造成資金的浪費；其二，設(shè)備產(chǎn)能不足，即是現(xiàn)有的設(shè)備加工能力難以滿足客戶需求，客戶的訂單便無法及時交付，甚至影響到企業(yè)的信譽度。

文獻[2]將制造系統(tǒng)最優(yōu)化問題總結(jié)為三類，即在滿足系統(tǒng)性能約束指標(biāo)下實現(xiàn)加工設(shè)備總投資額的最小化、在滿足優(yōu)先投資預(yù)算下使系統(tǒng)的某項指標(biāo)最優(yōu)化、將制造系統(tǒng)拆分成若干制造單元并以此來改善制造系統(tǒng)總體性能。文獻[3]研究訂貨型車間的任務(wù)投放問題，對有限緩存無阻塞的情形進行仿真，并對每道工序有一臺或多臺加工設(shè)備的兩級Flow Shop問題進行了探討。文獻[4]研究確定性環(huán)境下連續(xù)需求的能力優(yōu)化配置問題，以實現(xiàn)設(shè)備配置成本的最小化為目標(biāo)，以滿足生產(chǎn)需求為約束條件，提出了一種排序決策方法，用分枝定界方法和啟發(fā)式方法對能力配置問題進行求解。文獻[5]研究工業(yè)企業(yè)的設(shè)備能力優(yōu)化配置問題，以收集、分析以及整理生產(chǎn)實際數(shù)據(jù)為基礎(chǔ)，建立仿真模型，通過分析仿真結(jié)果尋找生產(chǎn)瓶頸。文獻[6]基于車輛能力規(guī)劃系統(tǒng)，將能力優(yōu)化配置問題轉(zhuǎn)換成一個受時間窗約束的車輛路徑規(guī)劃問題并進行仿真建模，并使用禁忌搜索算法對模型進行求解。

仿真法是在一系列近乎真實的假設(shè)和前提下，求解制造系統(tǒng)的性能指標(biāo)。針對約束函數(shù)無法用決策變量的封閉形式加以表達的難題，可以使用狀態(tài)空間分解法或者擴展近似法等方法加以解決。本文擬采用分支定界算法求解CCP問題，考慮到近似算法可能對最終結(jié)果產(chǎn)生影響，求解約束性能指標(biāo)時使用仿真法。

1 數(shù)學(xué)描述

1.1 條件假設(shè)及目標(biāo)函數(shù)

本文從企業(yè)的實際情況抽象出一個單種類產(chǎn)品多級FFS典型制造系統(tǒng)模型，具體如圖1所示。該車間有多道加工工序，且每級設(shè)備前設(shè)置一個公共緩沖區(qū)（有限容量）。

圖1 定制型裝備柔性流水車間排隊網(wǎng)通用模型

在數(shù)學(xué)模型建立前，先作如下假設(shè)：

①同類型設(shè)備的單價相同；

②工件以“泊松流”的方式到達制造系統(tǒng)；

③產(chǎn)品的加工工藝已知；

④設(shè)備的加工時間服從負指數(shù)分布，且彼此之間相互獨立；

⑤工件之間彼此相互獨立；

⑥一臺設(shè)備僅能同時加工一個工件；

⑦各節(jié)點緩存（buffer）容量有限。

1.2 數(shù)學(xué)模型

CCP問題的主要研究內(nèi)容是在企業(yè)現(xiàn)有的資源條件下，以系統(tǒng)的平均產(chǎn)出率作為約束條件，對加工設(shè)備優(yōu)化配置以使設(shè)備總成本最小化。該優(yōu)化問題的數(shù)學(xué)模型表述如下：

對模型（1）的各個參數(shù)作如下定義：

xi：表示制造系統(tǒng)第i級設(shè)備的數(shù)量；ci：表示制造系統(tǒng)第i級設(shè)備的單價；：表示制造系統(tǒng)總設(shè)備成本；：表示制造系統(tǒng)的平均產(chǎn)出率；Θ*：表示制造系統(tǒng)的預(yù)設(shè)產(chǎn)能；?：表示隨機元。

不難得出CCP問題的特點：（1）約束函數(shù)表達式難以用設(shè)備數(shù)量的封閉形式表達；（2）該問題是隨機整數(shù)規(guī)劃問題。特點1加大了求解模型的難度，為了能夠有效地求解系統(tǒng)的平均產(chǎn)出率，本文使用eM-plant軟件搭建仿真平臺來計算模型的約束指標(biāo)。根據(jù)特點（2），本文擬采用分支定界法。

2 設(shè)備能力優(yōu)化配置仿真建模

2.1 仿真模型建立

采用eM-Plant仿真軟件（Tecnomatix Plant Simulation8.2）搭建仿真實驗平臺，硬件配置如下：雙核CPU 2.0GHz，2G內(nèi)存，如圖2所示。

仿真系統(tǒng)由四個制造單元組成，工件均在訂單源產(chǎn)生。工件首先根據(jù)第一級加工設(shè)備前的緩存堵塞狀況判斷工件進入緩存（B1），或者根據(jù)加工設(shè)備的狀態(tài)判斷是否進入加工設(shè)備加工，如果第一級緩存（B1）已滿，且第一級各加工設(shè)備上均有工件，則由訂單源產(chǎn)生的工件進入Buffer0（無限容量）。表示訂單源，服從泊松分布；表示緩存，其大小可根據(jù)實際需要進行靈活調(diào)整；表示加工設(shè)備，每級設(shè)備的數(shù)量可根據(jù)優(yōu)化配置的結(jié)果不斷進行調(diào)整；用來獲取穩(wěn)定狀態(tài)下的平均產(chǎn)出率。

圖2 Tecnomatix Plant Simulation8.2仿真系統(tǒng)

2.2 分支定界法

前人經(jīng)常使用分支定界算法求解線性整數(shù)規(guī)劃（Linear Integer Programming，ILP）問題，目前求解ILP問題的軟件大多以分支定界算法為其核心思想，如LINDO Xpress-MP、、CPLEX等等[7]。一般ILP問題p0的數(shù)學(xué)模型表述如下：

其中，c∈Rn，A∈Rm×n，b∈Rm，x為決策變量。

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

圖3 分支定界法求解步驟

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

圖4 分支定界求解示意圖

即二級系統(tǒng)每級的設(shè)備數(shù)量分別為n1和n2，該設(shè)備組合向量（n1，n2）是可行解。在對其進行優(yōu)化配置時，首先分成3支，即（n1-1,n2）、（n1,n2-1）和（n1-1,n2-1），判斷三者是否均為可行解，如果均是可行解，則選擇是制造系統(tǒng)總成本最?。╪1-1,n2-1）的一支作為較優(yōu)解繼續(xù)進行分支，同時將（n1-1,n2）、（n1,n2-1）所對應(yīng)的目標(biāo)函數(shù)值作為上界；如果三者均為不可行解，則（n1，n2）即為最優(yōu)解，如果（n1-1,n2） 和 （n1,n2-1） 是可行解，（n1-1,n2-1）不是可行解，則將（n1-1,n2-1）所對應(yīng)的目標(biāo)函數(shù)值作為下界，同時從（n1-1,n2）和（n1,n2-1）選擇目標(biāo)函數(shù)值最小的一支繼續(xù)分解，另一支所對應(yīng)的目標(biāo)函數(shù)值作為上界。以此類推，直至找到最優(yōu)解（ni,nj），此時（ni,nj）的所有分支均是不可行解。

3 算例分析

3.1 算例數(shù)據(jù)

針對CCP問題的具體特征，本文構(gòu)建的算例主要包括工件到達率（λ）、設(shè)備類型、設(shè)備數(shù)量（ni）、設(shè)備單價（ci）等信息。具體如表1所示。

表1 初始參數(shù)設(shè)定

另外，在求解CCP問題時，應(yīng)該首先確定系統(tǒng)各級的buffer容量，即各級設(shè)備前公共緩沖區(qū)的容量。具體如表2所示。

表2 buffer容量設(shè)定

另外，由表1得知系統(tǒng)平均產(chǎn)出率為0.9。一般而言，真實的設(shè)備產(chǎn)出率與無限緩存下系統(tǒng)的平均產(chǎn)出率之間的關(guān)系比例值為0.9，即Θ*=0.9× 0.9=0.81。

CCP問題的算例需遵守如下規(guī)則：

（1）各級設(shè)備的加工能力之和原則

表3 CCP問題優(yōu)化前后對比

式子（1）表示各級設(shè)備的加工能力之和(μi×ni)應(yīng)大致相等，式子（2）表示各級設(shè)備的加工能力之和(μi×ni)應(yīng)呈“倒喇叭形”且略大于工件到達率(λ)。由表1知， μ4×n4=1.17、μ3×n3=1.10、 μ2≥n2=1.02、 μ1×n1=0.96、 λ= 0.90。不難看出，從加工能力原則看，算例是合理的。

圖5 優(yōu)化前、后設(shè)備數(shù)量變化圖

（2）各級緩沖區(qū)的容量原則

前面工序被阻塞的概率比后面大，對緩沖區(qū)容量進行設(shè)置時，前面緩沖區(qū)容量需大于（或等于）后面的緩沖區(qū)容量，即B4+n4≤B3+n3≤B2+n2≤B1+n1。 由 表 1知 ，B4+n4=18 、 B3+n3=18 、 B2+n2=33 、B1+n1=46。不難看出，從緩沖區(qū)容量原則看，算例也是合理的。

3.2 結(jié)果對比與分析

由表3知，優(yōu)化前、后設(shè)備組合向量分別為：Xf=（12，17，11，13）T、Xa=（12，16，10，12）T。為了形象地描述優(yōu)化的效果，本文運用直方圖表示優(yōu)化前、后各級設(shè)備數(shù)量的變化，具體如圖5所示。

第一、二、三、四級設(shè)備分別減少了0、1、1、1臺，共降低成本253萬元。系統(tǒng)的平均產(chǎn)出率也得到一定程度的優(yōu)化，優(yōu)化前平均產(chǎn)出率為0.897，比系統(tǒng)預(yù)設(shè)產(chǎn)能超出了9.7%；優(yōu)化后平均產(chǎn)出率為0.837，比系統(tǒng)預(yù)設(shè)產(chǎn)能超出了3.2%。

由表3知，優(yōu)化后的各級產(chǎn)能分別為：μ4×n4=1.08、 μ3×n3=1.00、 μ2≥n2=0.96、μ1×n1=0.96；各級緩沖區(qū)容量： B4+n4=34、B3+n3=32、B2+n2=17、B1+n1=17。所以，優(yōu)化后的結(jié)果是合理的。

4 結(jié)束語

本文首先根據(jù)問題特征建立數(shù)學(xué)模型，然后使用仿真法求解數(shù)學(xué)模型的約束性能指標(biāo)，并在此基礎(chǔ)上使用分支定界算法精確求解CCP問題，具有一定的工程價值。美中不足的是本文所使用的分支定界算法的核心——分支原則沒有產(chǎn)生高效的分支策略，在后續(xù)的研究中，筆者著重于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］陳田，陳慶新，毛寧，等.具有兩道工序的柔性同序加工車間任務(wù)投放策略［J］.工業(yè)工程，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］于戰(zhàn)科，倪明放，汪澤焱，等.整數(shù)線性規(guī)劃的改進分支定界算法［J］.計算機應(yīng)用，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年生，河南人，碩士研究生。研究領(lǐng)域：制造系統(tǒng)設(shè)計優(yōu)化。

(編輯：阮 毅)

*湖南省湘南學(xué)院院級重點教改項目

2014－04－01