張惠煜，陳慶新，毛 寧

（廣東工業(yè)大學(xué) 廣東省計算機(jī)集成制造系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006）

0 引言

對于面向資源的工程訂貨生產(chǎn)型（Engineeringto-Order，ETO）制造企業(yè)，最大的難題就是定制化的產(chǎn)品訂單和緊迫的交貨期，因此保證交貨期往往是定制型制造企業(yè)的核心競爭力。合理優(yōu)化配置制造資源是制造系統(tǒng)高效運(yùn)行的前提，通過合理的產(chǎn)能配置，可以用較小的投入提高產(chǎn)品或部件的齊配套性、減少在制品庫存、縮短生產(chǎn)周期，從而降低生產(chǎn)成本、提高企業(yè)的核心競爭力和效益。相對于傳統(tǒng)的制造系統(tǒng)，在定制生產(chǎn)方式下進(jìn)行資源優(yōu)化配置具有如下特點(diǎn)：①制造系統(tǒng)的隨機(jī)不確定性（訂單到達(dá)、工序工時、返修報廢和設(shè)備故障等）；②系統(tǒng)產(chǎn)能和訂單的交貨期成為關(guān)鍵約束。因此，在配置系統(tǒng)資源時，必須建立隨機(jī)非線性規(guī)劃模型以保證系統(tǒng)產(chǎn)能和訂單交貨期，然而這些約束無法用決策變量（設(shè)備數(shù)量、緩存區(qū)容量等）的封閉形式描述。因此，難以采用傳統(tǒng)方法求解定制型制造系統(tǒng)的資源規(guī)劃模型。

關(guān)于基于排隊網(wǎng)理論（queuing network theory）的制造系統(tǒng)最優(yōu)設(shè)計問題，文獻(xiàn)［1］將制造系統(tǒng)能力配置問題（Capacity Configuration Problem，CCP）分為如下三類：①在滿足特定的系統(tǒng)性能指標(biāo)的條件下最小化生產(chǎn)總投資成本；②在滿足優(yōu)先的投資預(yù)算的條件下最優(yōu)化系統(tǒng)某項性能指標(biāo)；③將制造系統(tǒng)劃分為更小的生產(chǎn)單元以改善系統(tǒng)總體性能。文獻(xiàn)［2］基于排隊網(wǎng)模型研究了制造系統(tǒng)的單階段能力配置與變更決策問題，建立了一個滿足系統(tǒng)在制品總數(shù)約束的條件下最小化能力成本的數(shù)學(xué)模型。文獻(xiàn)［3-5］針對類似的制造系統(tǒng)設(shè)計需求，分別針對各種分布情況的排隊網(wǎng)描述，提出了相應(yīng)的資源優(yōu)化配置問題及其求解方法，并進(jìn)行了一定的理論分析。國內(nèi)學(xué)者對這一問題也有相關(guān)的研究成果，文獻(xiàn)［6］考慮了生產(chǎn)過程中不良品和廢品的發(fā)生情況，建立了生產(chǎn)系統(tǒng)的開Markov鏈排隊網(wǎng)絡(luò)模型，求出各項排隊運(yùn)行指標(biāo)，并對生產(chǎn)線進(jìn)行了資源優(yōu)化配置。文獻(xiàn)［7］根據(jù)對垃圾收集運(yùn)輸過程隨機(jī)動態(tài)特征的分析，提出一種以排隊論為基礎(chǔ)的轉(zhuǎn)運(yùn)站設(shè)備配置方法。文獻(xiàn)［8］建立了碼頭多船服務(wù)的并列式排隊網(wǎng)絡(luò)，探討了有限資源模式下多船之間的橋吊均衡分配問題。文獻(xiàn)［9］建立了制造系統(tǒng)中自動化生產(chǎn)車間的排隊網(wǎng)模型，通過仿真得到不同配置下的性能指標(biāo)，并以此為依據(jù)實(shí)現(xiàn)了資源的優(yōu)化配置。

如何獲得較精確的系統(tǒng)性能指標(biāo)值是求解CCP模型的首要問題。已有研究對于緩沖區(qū)容量有限的車間進(jìn)行排隊網(wǎng)建模分析時往往將整個車間作為一個排隊網(wǎng)絡(luò)系統(tǒng)，每個節(jié)點(diǎn)是獨(dú)立的隊列，根據(jù)輸入與輸出的關(guān)系求出每個隊列的邊際分布，并將其乘積作為整個車間排隊網(wǎng)模型的穩(wěn)態(tài)聯(lián)合分布。該方法忽略了節(jié)點(diǎn)之間的耦合作用，求解小規(guī)模系統(tǒng)時產(chǎn)生的偏差較小，可以忽略，但對于大規(guī)模系統(tǒng)則會產(chǎn)生嚴(yán)重的偏差。傳統(tǒng)的精確模型的方法雖然可以獲得系統(tǒng)的精確解，但隨著系統(tǒng)規(guī)模的擴(kuò)大，將導(dǎo)致維數(shù)災(zāi)而無法求解，文獻(xiàn)［10］提出基于狀態(tài)空間的分解法，該方法雖然也忽略了一些涉及多個節(jié)點(diǎn)之間的復(fù)雜關(guān)聯(lián)狀態(tài)，但節(jié)點(diǎn)間的狀態(tài)概率約束可以近似描述其耦合作用，因此可以獲得較精確的結(jié)果。然而，隨著排隊網(wǎng)規(guī)模的逐漸增加，其狀態(tài)空間的規(guī)模依舊很可觀，該方法求解大規(guī)模的排隊網(wǎng)模型依然有困難。

本文針對ETO 定制生產(chǎn)方式下柔性裝配線系統(tǒng)的能力配置問題，基于具有有限緩沖區(qū)的開排隊網(wǎng)絡(luò)建模方法，提出一種擴(kuò)展近似解法獲得系統(tǒng)性能指標(biāo)值，以建立系統(tǒng)設(shè)備配置優(yōu)化模型并設(shè)計啟發(fā)式算法進(jìn)行求解。

1 問題描述

1.1 柔性裝配生產(chǎn)系統(tǒng)模型

柔性裝配線生產(chǎn)系統(tǒng)工作時，進(jìn)入系統(tǒng)的不同類型工件根據(jù)不同加工路徑，通過物料自動搬運(yùn)傳送系統(tǒng)順次傳給不同加工設(shè)備、完成加工作業(yè)，到達(dá)裝配工作中心的兩個不同類型工件同時完成所需的裝配作業(yè)，裝配完成后的工件繼續(xù)完成后續(xù)加工作業(yè)，直至完工離開系統(tǒng)。在一個工作中心完工的工件，如果下一個工作中心的緩沖區(qū)已滿，則停留在原工作中心，而該工作中心無法對后續(xù)工件進(jìn)行加工，直至下一個工作中心正在加工的工件離開，這種狀態(tài)稱為阻塞（blocking），當(dāng)一個工作中心完成一個工件后無后續(xù)工件加工時，這種狀態(tài)稱為饑餓（starvation），這些影響因素降低了系統(tǒng)的生產(chǎn)效率。柔性裝配線的生產(chǎn)系統(tǒng)如圖1所示。該系統(tǒng)包含：①兩種類型的工件：零件a和零件b；②四個工作中心：粗車工作中心1（設(shè)備類A）、粗車工作中心2（設(shè)備類B）、裝配工作中心（設(shè)備類C）和精車工作中心（設(shè)備類D）。

裝配加工作業(yè)（assembly）中，零件不僅需要等待設(shè)備資源可用，還需要等待另一個零件的到達(dá)。若零件a已到達(dá)裝配工作中心且有設(shè)備空閑但零件b未到達(dá)，則裝配作業(yè)無法進(jìn)行，零件a需要等待、直至零件b到達(dá)后才能進(jìn)行裝配作業(yè)。

根據(jù)圖1所示的柔性裝配線生產(chǎn)系統(tǒng)，將其簡化為如圖2所示的具有有限緩沖區(qū)的三級開排隊網(wǎng)模型，其中：方框表示有限容量的緩沖區(qū)，圓圈表示加工設(shè)備，直線表示工件流，箭頭表示工件進(jìn)入或離開系統(tǒng)以及工作中心之間的轉(zhuǎn)移，粗車工作中心和精車工作中心分別由1個緩存區(qū)和1臺加工設(shè)備表示，裝配工作中心由2個緩存區(qū)和1臺加工設(shè)備表示，各個工作中心即為排隊網(wǎng)絡(luò)中的各個節(jié)點(diǎn)。

該模型滿足以下假設(shè)條件：

（1）不同類型工件到達(dá)系統(tǒng)的隨機(jī)過程均為泊松過程，到達(dá)率分別為λa和λb；

（2）各級節(jié)點(diǎn)的服務(wù)時間服從負(fù)指數(shù)分布，每臺設(shè)備的平均加工速率為μi（i=1，2，3）；

（3）各級節(jié)點(diǎn)包含的設(shè)備數(shù)量為ci（i=1，2，3），普通設(shè)備只能同時加工一個工件，而裝配設(shè)備上有兩個工件同時加工，且加工過程一旦開始就不可中斷；

（4）第一級節(jié)點(diǎn)和第三級節(jié)點(diǎn)都包含一個有限容量的緩沖區(qū)，而裝配節(jié)點(diǎn)包含兩個有限容量的緩沖區(qū)，分別存放不同類型的工件，每個緩沖區(qū)的最大容量為Ni（i=1，2，3），則節(jié)點(diǎn)容量為Ki=Ni+ci；

（5）各級節(jié)點(diǎn)的服務(wù)規(guī)則為“先到先服務(wù)（First in First Out，F(xiàn)IFO）”；

（6）系統(tǒng)阻塞機(jī)制為“服務(wù)后阻塞”，當(dāng)上一級節(jié)點(diǎn)有多個工件被下一級節(jié)點(diǎn)阻塞時，使用“先阻塞先服務(wù)”的規(guī)則。

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

考慮具有系統(tǒng)平均產(chǎn)出率（單位時間系統(tǒng)輸出完成品的平均數(shù)量）和平均生產(chǎn)周期（平均每個完成品在系統(tǒng)中停留的時間）雙重約束的柔性裝配線生產(chǎn)系統(tǒng)設(shè)備配置優(yōu)化問題，其目標(biāo)是優(yōu)化設(shè)備配置，從而最小化設(shè)備投資成本，滿足系統(tǒng)產(chǎn)能及訂單交貨期的要求。

定義如下參數(shù)：

pi為第i類設(shè)備采購單價，i=1，2，…，m；

xi為第i類設(shè)備配置數(shù)量，i=1，2，…，m；

X為設(shè)備配置向量，X=｛xi｝，i=1，2，…，m；

Y為緩沖區(qū)容量配置向量；

Θ為系統(tǒng)平均產(chǎn)出率；

Τ為系統(tǒng)平均生產(chǎn)周期；

P為設(shè)備投資成本。

基于系統(tǒng)模型的假設(shè)條件，該優(yōu)化問題的數(shù)學(xué)模型如下：

其中：式（1）表示優(yōu)化目標(biāo)，即最小化設(shè)備投資成本；式（2）表示平均產(chǎn)能約束，實(shí)際平均產(chǎn)出率Θ（X，Y）不小于目標(biāo)平均產(chǎn)出率α；式（3）表示平均生產(chǎn)周期約束，實(shí)際平均生產(chǎn)周期Τ（X，Y）不大于目標(biāo)平均生產(chǎn)周期β；式（4）表示緩沖區(qū)容量配置可根據(jù)設(shè)備配置獲得；式（5）表示各節(jié)點(diǎn)服務(wù)速率的方差不超過δ，以滿足生產(chǎn)線產(chǎn)能平衡的要求；式（6）表示X和Y為非負(fù)整數(shù)型向量，pi和xi為非負(fù)整數(shù)。

要獲得最小總投資成本P＊，則必須找到最優(yōu)的設(shè)備資源配置向量X＊，使得平均產(chǎn)能約束式（2）和平均生產(chǎn)周期約束式（3）同時成立。然而，目標(biāo)函數(shù)的優(yōu)化問題是一個非線性整數(shù)規(guī)劃問題，這是因?yàn)槠骄a(chǎn)能和平均生產(chǎn)周期約束無法用封閉形式表達(dá)，換言之，無法用函數(shù)形式描述設(shè)備配置與平均產(chǎn)能、平均生產(chǎn)周期之間的關(guān)系。因此，無法用傳統(tǒng)的非線性整數(shù)規(guī)劃方法求解雙重約束的資源優(yōu)化配置問題，為此，本文提出一種基于排隊網(wǎng)求解系統(tǒng)性能指標(biāo)的啟發(fā)式優(yōu)化算法進(jìn)行求解。

2 啟發(fā)式優(yōu)化方法

2.1 擴(kuò)展法求解系統(tǒng)性能指標(biāo)

對于具有裝配環(huán)節(jié)的排隊網(wǎng)系統(tǒng)，作業(yè)的同時性約束導(dǎo)致了工作中心之間的依賴性，使得對含裝配環(huán)節(jié)的系統(tǒng)進(jìn)行排隊網(wǎng)建模分析時比一般拓?fù)浣Y(jié)構(gòu)的系統(tǒng)更困難。如果將裝配工作中心看成一個由一系列輸入緩沖區(qū)構(gòu)成的系統(tǒng)，則只要至少有一個緩沖區(qū)為空，系統(tǒng)就處于“饑餓”狀態(tài)。

國內(nèi)學(xué)者對于裝配系統(tǒng)的建模分析都是將其簡化為一般的工作站，并沒有考慮作業(yè)的同時性約束，因此不能有效地求解具有裝配作業(yè)環(huán)節(jié)的生產(chǎn)系統(tǒng)［11-12］。對于很小規(guī)模的系統(tǒng)可采用Markov鏈模型［13］，但這種方法隨著系統(tǒng)的增大會導(dǎo)致維數(shù)災(zāi)害。對于較大規(guī)模的系統(tǒng)，國外學(xué)者多采用分解的近似方法，如兩站子系統(tǒng)（two-station subsystems）的分解方法，進(jìn)而應(yīng)用DDX（dallery-david-xie）算法進(jìn)行求解［14-15］，但求解結(jié)果的精確度仍有待提高。因此，本文基于文獻(xiàn)［16-17］的廣義擴(kuò)展法理論提出一種求解裝配環(huán)節(jié)的擴(kuò)展法，并與文獻(xiàn)［18］提出的分解法和仿真實(shí)驗(yàn)的結(jié)果進(jìn)行對比，以驗(yàn)證其有效性。

擴(kuò)展法是一種基于排隊論的近似求解方法，通過將系統(tǒng)的各個節(jié)點(diǎn)逐級分解出來，針對每個節(jié)點(diǎn)考慮該節(jié)點(diǎn)與其前繼節(jié)點(diǎn)和后續(xù)節(jié)點(diǎn)之間的耦合關(guān)系進(jìn)行分析，從而求解獲得系統(tǒng)性能指標(biāo)值。

（1）網(wǎng)絡(luò)重構(gòu)

裝配站工作時，兩個工件同時在設(shè)備上進(jìn)行加工，為解決該約束問題，將裝配站拆分為兩個具有同時工作約束的常規(guī)工作站，并與各自的緩存區(qū)組成兩個具有耦合約束的節(jié)點(diǎn)。通過裝配節(jié)點(diǎn)的拆分，將兩個工件裝配同時性的約束轉(zhuǎn)化為兩個子節(jié)點(diǎn)上的工件同時到達(dá)進(jìn)行加工以及同時完工而離開的約束。

首先，在每個有限容量的緩沖區(qū)前添加虛擬節(jié)點(diǎn)，用于處理到達(dá)工作中心但因緩存區(qū)滿而被阻塞的工件。如圖3所示為對分解后的兩個節(jié)點(diǎn)i和j進(jìn)行網(wǎng)絡(luò)重構(gòu)的排隊模型，在有限容量的節(jié)點(diǎn)i和j前分別添加虛擬節(jié)點(diǎn)hi和hj，節(jié)點(diǎn)模型為M／M／∞。

（2）參數(shù)估計

由排隊論M／M／c／K 模型理論可得，對于系統(tǒng)內(nèi)有c個服務(wù)窗、系統(tǒng)容量為K、顧客按強(qiáng)度為λ的泊松流到達(dá)系統(tǒng)，各窗口的獨(dú)立服務(wù)時間均服從強(qiáng)度為μ的負(fù)指數(shù)分布，其系統(tǒng)參數(shù)的穩(wěn)態(tài)公式如下：

（1）系統(tǒng)空閑的概率 當(dāng)ρ=λ／（cμ）≠1時，p0；當(dāng)ρ=1時，p0。

（3）平均排隊等待時間 當(dāng)ρ≠1 時，Wq=

以節(jié)點(diǎn)i為例，在不考慮裝配作業(yè)同時性約束的情況下進(jìn)行分析。

工件在節(jié)點(diǎn)（i-1）加工完成后到達(dá)節(jié)點(diǎn)i，若節(jié)點(diǎn)i前的緩存區(qū)容量已達(dá)到上限Ki，則工件將被堵塞，被堵塞的概率為PK，被堵塞的工件將重新回到虛擬節(jié)點(diǎn)hi，直至節(jié)點(diǎn)i有一個工件完工離開，被堵塞的工件進(jìn)入節(jié)點(diǎn)i的緩存區(qū)。因此，虛擬節(jié)點(diǎn)的作用是重新計算工件因堵塞而延遲到達(dá)工作站的有效到達(dá)率。

工件因堵塞重新回到虛擬節(jié)點(diǎn)hi的概率可以采用文獻(xiàn)［19］的擴(kuò)散技術(shù)（diffusion techniques）計算：

其中r1和r2是方程λ-（λ+μh+μi）x+μhx2=0的根，方程中，λe和λh分別為工件到達(dá)節(jié)點(diǎn)i的有效達(dá)到率及工件到達(dá)虛擬節(jié)點(diǎn)hi的速率。因此工件到達(dá)節(jié)點(diǎn)i的有效達(dá)到率λe=λi（1-PK）=λi-λh。

對于虛擬節(jié)點(diǎn)hi的服務(wù)速率μh，可以采用文獻(xiàn)［13］的更新理論（renewal theory）計算：

其中σ2為服務(wù)時間的方差。對于服務(wù)時間服從負(fù)指數(shù)分布的節(jié)點(diǎn)i，虛擬節(jié)點(diǎn)hi的服務(wù)時間也服從負(fù)指數(shù)分布，且μh=μi。

（3）依賴消除

由于工件被堵塞時會重新返回虛擬節(jié)點(diǎn)中等待，從而對工件到達(dá)節(jié)點(diǎn)i的速率形成依賴，需要按下式重新計算虛擬節(jié)點(diǎn)hi的服務(wù)速率：

工件到達(dá)節(jié)點(diǎn)i存在兩種狀態(tài)：①被堵塞的概率為PK；②不被堵塞的概率為（1-PK）。當(dāng)工件不被堵塞時，工件在設(shè)備上的加工時間為，當(dāng)工件被堵塞時，工件在設(shè)備上的加工時間為，因此，節(jié)點(diǎn)i的平均服務(wù)時間為，工件在節(jié)點(diǎn)i上的時間停留為W=Ws+Wq。

（4）結(jié)果計算

綜上所述，針對節(jié)點(diǎn)i建立如下方程組：

其中：式（7）～式（10）是虛擬節(jié)點(diǎn)反饋的方程組；式（12）和式（13）用于求解式（11），式中z為虛參數(shù)；式（14）為M／M／c／K 模型節(jié)點(diǎn)的阻塞概率表達(dá)式。因此，通過聯(lián)立方程組并迭代求解，可以獲得工件實(shí)際到達(dá)節(jié)點(diǎn)i的有效達(dá)到率λa=λe。同理，對于節(jié)點(diǎn)j也可以通過上述方法計算獲得工件的有效達(dá)到率λb=λ″e。

由于系統(tǒng)穩(wěn)定時應(yīng)達(dá)到統(tǒng)計平衡，即進(jìn)入速率應(yīng)等于離去速率，考慮裝配作業(yè)的同時性約束，工件在裝配工作中心加工的輸出速率O=min（λa，λb）。

因此，根據(jù)工件的加工路徑將系統(tǒng)的各個節(jié)點(diǎn)依次進(jìn)行擴(kuò)展分析，直至最后一個節(jié)點(diǎn)m，可以求得如下系統(tǒng)性能指標(biāo)值：

其中：λe（m）為系統(tǒng)最后一個節(jié)點(diǎn)m的有效輸出率；Wa（i）和Wb（i）分別為工件a和b在節(jié)點(diǎn)i（i=1，2，…，m）上的停留時間。

2.2 緩沖區(qū)容量配置方法

緩沖區(qū)的容量必須設(shè)置在一定范圍內(nèi)，如果設(shè)置過緊，則雖然可以減小車間的流水時間，但也會因頻繁阻塞而導(dǎo)致設(shè)備的利用率低，最終導(dǎo)致車間的產(chǎn)出率不理想；如果設(shè)置太松，則無法有效控制平均生產(chǎn)周期。由于本文優(yōu)化的目標(biāo)是設(shè)備配置，緩沖區(qū)容量的配置（向量Y）可采用以下方法近似獲得：采用無限Buffer的模型，根據(jù)設(shè)備配置（向量X）由M／M／c模型的穩(wěn)態(tài)公式計算出每個節(jié)點(diǎn)的平均排隊隊列長度，并以其兩倍的值作為節(jié)點(diǎn)緩沖區(qū)容量的上限。

M／M／c模型的平均排隊隊長

2.3 啟發(fā)式優(yōu)化算法

由于本文的目標(biāo)函數(shù)是一個非線性整數(shù)規(guī)劃問題，而且輸出率和平均生產(chǎn)周期都無法用一個封閉的數(shù)學(xué)方程式表達(dá)，在滿足預(yù)設(shè)系統(tǒng)輸出率和生產(chǎn)周期的情況下，采用啟發(fā)式規(guī)則優(yōu)化設(shè)備增加的配置方案。給出系統(tǒng)產(chǎn)出率和生產(chǎn)周期的計算方法以及緩沖區(qū)容量配置的方法后，就可以通過啟發(fā)式優(yōu)化方法對柔性裝配線生產(chǎn)系統(tǒng)的設(shè)備進(jìn)行優(yōu)化配置。

（1）啟發(fā)式規(guī)則 優(yōu)先增加采購價格較低的設(shè)備類臺數(shù)，增加多臺設(shè)備時，優(yōu)先增加采購總成本低的設(shè)備類組合，判斷其是否滿足約束條件，從而確定采購成本最低的設(shè)備增加方案，算法流程如圖4所示。

（2）算法流程

具體算法流程如下：

步驟1 按采購價格由低到高的順序優(yōu)先增加價格較低的設(shè)備類數(shù)量，每次增加1，判斷是否滿足生產(chǎn)線產(chǎn)能平衡的約束條件，若滿足，則執(zhí)行步驟2；否則增加采購價格較高的設(shè)備類數(shù)量，并判斷是否滿足生產(chǎn)線產(chǎn)能平衡的約束條件。

步驟2 根據(jù)設(shè)備配置方案計算緩沖區(qū)容量大小的配置。

步驟3 調(diào)用擴(kuò)展近似法求解系統(tǒng)平均產(chǎn)出率和生產(chǎn)周期，判斷是否滿足預(yù)設(shè)產(chǎn)出率和生產(chǎn)周期的約束條件，若滿足則確定該設(shè)備配置方案為有效方案；否則返回步驟1，直到遍歷增加所有設(shè)備類數(shù)量，搜索所有有效的設(shè)備配置方案。

步驟4 在所有有效方案中，以最小化設(shè)備總投資成本為目標(biāo)確定設(shè)備配置優(yōu)化方案。

本文設(shè)計的算法屬于枚舉型，即根據(jù)約束條件遍歷循環(huán)搜索符合條件的方案，通過比較目標(biāo)函數(shù)值確定最優(yōu)方案。該方法簡單易行，雖然效率較低，即從時間復(fù)雜度來說比較耗時，但是因?yàn)楸疚乃婕暗脑O(shè)備配置優(yōu)化問題屬于生產(chǎn)系統(tǒng)的設(shè)計問題而不是實(shí)時控制，所以消耗的時間仍在可接受范圍之內(nèi)。

3 算例分析

本文求解算例的操作系統(tǒng)環(huán)境為Microsoft win7，硬件環(huán)境為CPU 1.86GHz，2.00GB RAM，對于解析算法的軟件平臺采用MATLAB 2010b。

3.1 仿真模型

如圖5所示為在Tecnomatix Plant Simulation 8.2上建立的柔性裝配線生產(chǎn)系統(tǒng)仿真模型?；贛onte Carlo仿真理論，在大樣本的條件下，構(gòu)造統(tǒng)計估計量（系統(tǒng)平均產(chǎn)出率和平均生產(chǎn)周期）并計算采集的數(shù)據(jù)樣本，仿真實(shí)驗(yàn)每次運(yùn)行1 000d，并在95%的置信度下進(jìn)行20次獨(dú)立重復(fù)實(shí)驗(yàn)，最終計算系統(tǒng)性能指標(biāo)的均值。

3.2 算例1：擴(kuò)展法有效性驗(yàn)證

為驗(yàn)證本文所提近似解法的有效性，設(shè)置如表1所示的算例參數(shù)，其中緩沖區(qū)容量為根據(jù)2.2節(jié)方法計算的結(jié)果。分別應(yīng)用擴(kuò)展法、文獻(xiàn)［18］分解法和仿真法求解，并以仿真實(shí)驗(yàn)的結(jié)果作為衡量基準(zhǔn)進(jìn)行對比分析，實(shí)驗(yàn)結(jié)果對比如表2 所示，其中Dev.（Θ）和Dev.（Τ）分別為產(chǎn)出率和生產(chǎn)周期的相對偏差率。

表1 算例1的參數(shù)

表2 算例1的結(jié)果對比

由表2可以看出，增加系統(tǒng)某些節(jié)點(diǎn)設(shè)備的數(shù)量，并非一定能增加系統(tǒng)的產(chǎn)出率，而減少生產(chǎn)周期設(shè)備的數(shù)量決定了工件在此工作中心前的平均等待時間，設(shè)備數(shù)量越多，工件的平均等待時間越短，對于緩沖區(qū)需求的容量就越小。當(dāng)增加后級節(jié)點(diǎn)的設(shè)備數(shù)量、使后級節(jié)點(diǎn)的加工速率大于前級節(jié)點(diǎn)的加工速率時，系統(tǒng)的產(chǎn)出率略有增加，生產(chǎn)周期有明顯縮短，因此，合理地增加系統(tǒng)的設(shè)備數(shù)量，可以提高系統(tǒng)產(chǎn)出率并縮短生產(chǎn)周期。

與仿真結(jié)果對比，文獻(xiàn)［18］的分解法對于計算系統(tǒng)的平均產(chǎn)出率偏差均在6%～10%內(nèi)，本文的近似計算方法較充分地考慮了節(jié)點(diǎn)間的耦合作用，所產(chǎn)生的偏差平均值約為3%，由此可以看出本文的近似方法對于系統(tǒng)性能分析和計算具有更好的適應(yīng)性。

3.3 算例2：優(yōu)化算法案例分析

以圖1所示柔性裝配線生產(chǎn)系統(tǒng)為例，兩種類型零件（a和b）的任務(wù)投放速率（即工件達(dá)到率）分別為λa=0.85，λb=0.90，為提高生產(chǎn)車間產(chǎn)能、縮短產(chǎn)品的生產(chǎn)周期，要在車間新增設(shè)備，使系統(tǒng)的產(chǎn)出率不低于0.75，生產(chǎn)周期不超過17.00h。生產(chǎn)線產(chǎn)能平衡的要求為δ=0.1，車間設(shè)備的初始設(shè)置和基本參數(shù)如表3所示。

表3 算例2的設(shè)備初始設(shè)置及基本參數(shù)

根據(jù)2.3節(jié)的啟發(fā)式優(yōu)化算法，求得算例優(yōu)化的結(jié)果如表4所示。

表4 算例2的優(yōu)化結(jié)果示例

表4所示為滿足系統(tǒng)產(chǎn)出率、生產(chǎn)周期和產(chǎn)能平衡約束的設(shè)備配置方案。由表4可知，方案2為基于最小化設(shè)備總投資成本目標(biāo)下的最優(yōu)設(shè)備配置方案，裝配工作中心和精加工工作中心分別增加一臺設(shè)備，系統(tǒng)的產(chǎn)出率和生產(chǎn)周期都得到了明顯改善，可以滿足系統(tǒng)產(chǎn)能及訂單交貨期的要求，因此將方案2確定為最優(yōu)方案。

由此可以看出本文所提出的求解系統(tǒng)性能指標(biāo)值和設(shè)備配置優(yōu)化算法的合理性及有效性，這種方法可以推廣到較大規(guī)模的系統(tǒng)分析資源優(yōu)化配置。隨著系統(tǒng)規(guī)模的擴(kuò)大，雖然擴(kuò)展近似解法不受限制，但由于優(yōu)化算法采用遍歷的搜索方法，算例的工作量將變得更大。

4 結(jié)束語

本文針對具有系統(tǒng)產(chǎn)能（產(chǎn)出率）和產(chǎn)品交貨期（生產(chǎn)周期）雙重約束的設(shè)備配置優(yōu)化問題，以最小化設(shè)備投資成本為目標(biāo)建立了數(shù)學(xué)模型。由于目標(biāo)函數(shù)的優(yōu)化問題是一個隨機(jī)非線性整數(shù)規(guī)劃問題，建立了柔性裝配線生產(chǎn)系統(tǒng)的排隊網(wǎng)模型，應(yīng)用擴(kuò)展近似計算的方法求解系統(tǒng)性能指標(biāo)值，并提出一種啟發(fā)式優(yōu)化算法求解設(shè)備配置優(yōu)化方案。通過算例求解和結(jié)果分析，與仿真結(jié)果對比，擴(kuò)展近似法的計算系統(tǒng)性能指標(biāo)值具有較高的精確度，基于擴(kuò)展法求解性能指標(biāo)值的啟發(fā)式算法可以獲得合理的最優(yōu)設(shè)備配置方案，表明該方法可以應(yīng)用于求解較大規(guī)模的系統(tǒng)資源優(yōu)化配置問題。

本文計算緩沖區(qū)容量上限的方法是一種粗略的近似方法，實(shí)際上緩存區(qū)的配置優(yōu)化問題（Buffer Allocation Problem，BAP）［20-21］也是系統(tǒng)配置優(yōu)化的重點(diǎn)，今后將對BAP 與CCP 聯(lián)合優(yōu)化的問題進(jìn)行研究。

［1］BITRAN G R，MORABITO R.An overview of tradeoff curves in manufacturing system design［J］.Production and Operations Management，1999，8（1）：56-75.

［2］BITRAN G R，TIRUPATI D.Capacity planning in manufacturing networks with discrete options［J］.Annals of Operations Research，1989，17（1／2／3／4）：119-136.

［3］BRETTHAUER K M.Capacity planning in manufacturing and computer networks［J］.European Journal of Operational Research，1996，91（2）：386-394.

［4］BRETTHAUER K M，COTE M J.Nonlinear programming for multi-period capacity planning in a manufacturing system［J］.European Journal of Operational Research，1996，96（1）：167-179.

［5］BUSS A H，LAWRANCE S R，KROPP D H.Volume and capacity interaction in facility design［J］.IIE Transactions，1994，26（4）：36-49.

［6］ZHANG Yuxian，YU Ming，YE Bingbing.Optimum distribution of equipment resources in production line based on open queuing network［J］.Journal of Systems Science，2012，20（3）：75-78（in Chinese）.［張于賢，于 明，葉冰冰.基于開排隊網(wǎng)絡(luò)理論的生產(chǎn)線設(shè)備資源優(yōu)化配置［J］.系統(tǒng)科學(xué)學(xué)報，2012，20（3）：75-78.］

［7］PENG Xuya，LIU Changwei，LIU Guotao，et.al.Application of queuing theory in the optimal allocation of equipment in waste transfer station［J］.Journal of Chongqing University，2008，31（3）：237-241（in Chinese）.［彭緒亞，劉長瑋，劉國濤，等.排隊論在垃圾轉(zhuǎn)運(yùn)站設(shè)備優(yōu)化配置中的應(yīng)用［J］.重慶大學(xué)學(xué)報，2008，31（3）：237-241.］

［8］ZHANG Li.Research on equipment configuration optimization of container terminal based on queueing network theory［D］.Shanghai：Tongji University，2003（in Chinese）.［張 莉.基于排隊網(wǎng)絡(luò)理論的集裝箱碼頭設(shè)備配置優(yōu)化研究［D］.上海：同濟(jì)大學(xué)，2003.］

［9］WANG Xin.The Simulation and optimization of resource allocation in automation workshops［D］.Dalian：Dalian University of Technology，2011（in Chinese）.［王 欣.自動化生產(chǎn)車間資源配置仿真及優(yōu)化［D］.大連：大連理工大學(xué)，2011.］

［10］HASKOSE A，KINGSMAN B G，WORTHINGTON D.Modelling flow and jobbing shops as a queueing network for workload control［J］.International Journal of Production Economics，2002，78（3）：271-285.

［11］ZHANG Ping，PENG Shangxian.A study on the modelling of flexible system［J］.Journal of Tianjing University，1995，28（4）：450-456（in Chinese）.［張 平，彭商賢.柔性裝配系統(tǒng)的建模［J］.天津大學(xué)學(xué)報，1995，28（4）：450-456.］

［12］MENG Fanli，TAN Dalong，HUANG Xuemei.Research on buffer capacity in assembly system［J］，Computer Integrated Manufacturing Systems，2005，11（11）：1609-1615（in Chinese）.［孟凡力，談大龍，黃雪梅.裝配系統(tǒng)中緩沖區(qū)容量的研究［J］.計算機(jī)集成制造系統(tǒng)，2005，11（11）：1609-1615.］

［13］WILLIAM J S.Probability，Markov chains，queues and simulation：the mathematical basis of performance modeling［M］.Princeton，N.J.，USA：Princeton University Press，2009.

［14］MICHAEL M.Queueing-model based analysis of assembly lines with finite buffers and general service times［J］.Computers &Operations Research，2008，35（8）：2520-2536.

［15］AMIR A，HIDEKI K，KOSUKE K，MASATOSHI S.2006.Modelling complex assemblies as a queueing network for lead time control［J］.European Journal of Operational Research，174（1）：150-168.

［16］KERBACHE L，SMITH J M.The generalized expansion method for open finite queueing networks［J］.European Journal of Operational Research，1987，32（3）：448-461.

［17］SINGH A，SMITH J M.Buffer allocation for an integer nonlinear network design problem［J］.Computers and Operation Research，1997，24（5）：453-472.

［18］NUTTHAPOL A，CHAO X L.A decomposition approximation for assembly–disassembly queueing networks with finite buffer and blocking［J］.Annals of Operations Research，1999，87（0）：247-261.

［19］LABETOULLE J，PUJOLLE G.Isolation method in a network of queues［J］.IEEE Transactions on Software Engineering，1980，6（4）：373-381.

［20］ZHANG Huiyu，KANG Weicheng，MAO Ning，et al.Buffer optimization configuration method for customized manufacturing system［J］.Industrial Engineering Journal，2014，17（5）：85-92（in Chinese）.［張惠煜，康偉成，毛 寧，等.面向定制生產(chǎn)系統(tǒng)的緩沖區(qū)優(yōu)化配置方法［J］.工業(yè)工程，2014，17（5）：85-92.］

［21］LI Xiag，CHEN Qingxin，MAO Ning.Buffer allocation optimization of flow shop based on queueing network model［J］.Computer Integrate Manufacturing Systems，2014，20（4）：890-897（in Chinese）.［李 翔，陳慶新，毛 寧.基于排隊網(wǎng)模型的流水車間緩沖區(qū)容量優(yōu)化［J］.計算機(jī)集成制造系統(tǒng)，2014，20（4）：890-897.］