張惠煜，陳慶新，毛 寧，俞愛(ài)林+，李 翔,2，梁祖紅

(1.廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006；2.湘南學(xué)院 電子信息與電氣工程學(xué)院，湖南 郴州 423000)

0 引言

定制型制造企業(yè)中，定制需求使得產(chǎn)品種類多，不同種類產(chǎn)品的工藝需求往往存在差異，且具有多條可選的工藝路徑，因此車間規(guī)劃采用作業(yè)車間(job-shops)形式。制造系統(tǒng)生產(chǎn)過(guò)程中存在眾多不確定因素，如訂單到達(dá)時(shí)間、工序加工工時(shí)、工藝路線變化等，此外，還存在零件重入加工以及可能的返工返修等情形。隨機(jī)環(huán)境下，如何在制造系統(tǒng)中優(yōu)化配置有限的制造資源(設(shè)備、緩沖區(qū)容量等)，降低企業(yè)投資成本，同時(shí)提高車間生產(chǎn)能力、縮短生產(chǎn)提前期、提高訂單準(zhǔn)時(shí)交貨率，是制造企業(yè)建立智能工廠時(shí)迫切需要解決的問(wèn)題。

定制型企業(yè)的一個(gè)顯著特征就是具有訂單交貨期約束，因此生產(chǎn)周期是制造系統(tǒng)規(guī)劃設(shè)計(jì)的關(guān)鍵性能指標(biāo)。實(shí)際生產(chǎn)過(guò)程中，在制品(Work in Process, WIP)的排隊(duì)等待時(shí)間往往遠(yuǎn)大于其加工時(shí)間，而有限容量的緩沖區(qū)可以有效控制在制品的排隊(duì)隊(duì)列長(zhǎng)度及其等待時(shí)間，縮短生產(chǎn)周期，提高準(zhǔn)時(shí)交貨率。緩沖區(qū)配置問(wèn)題(Buffer Allocation Problem，BAP)是基于現(xiàn)有的車間資源，研究各個(gè)緩沖區(qū)最大容量的配置方案以獲得最優(yōu)的系統(tǒng)性能或投資方案。緩沖區(qū)容量設(shè)置得太低會(huì)降低系統(tǒng)的生產(chǎn)效率，設(shè)置得太高則無(wú)法起到調(diào)控系統(tǒng)生產(chǎn)周期的作用。

由于目標(biāo)函數(shù)以及約束條件通常為非線性函數(shù)，因此BAP是一類非線性整數(shù)規(guī)劃問(wèn)題。隨著系統(tǒng)規(guī)模的擴(kuò)大，每個(gè)緩沖區(qū)容量組合構(gòu)成的解空間規(guī)模也會(huì)隨著擴(kuò)大而導(dǎo)致維數(shù)災(zāi)問(wèn)題，BAP也是一類NP-hard組合優(yōu)化問(wèn)題[1-2]。同時(shí)，系統(tǒng)性能指標(biāo)是關(guān)于決策變量的非封閉函數(shù)，因此無(wú)法采用傳統(tǒng)非線性規(guī)劃中基于梯度的搜索算法求解此類BAP。目前，國(guó)外已有一些針對(duì)BAP研究的綜述文獻(xiàn)[3-6]，但這些文獻(xiàn)都只是針對(duì)串聯(lián)結(jié)構(gòu)的流水車間系統(tǒng)(flow-shops)。BAP可以分為3類：①初始優(yōu)化問(wèn)題，在滿足系統(tǒng)產(chǎn)能需求的約束下，最小化緩沖區(qū)總?cè)萘?；②雙重優(yōu)化問(wèn)題，在最大化系統(tǒng)產(chǎn)能的情況下，同時(shí)最小化緩沖區(qū)總?cè)萘浚虎劢M合優(yōu)化問(wèn)題，以最小化緩沖區(qū)總?cè)萘繛槟繕?biāo)，同時(shí)考慮其他指標(biāo)作為約束指標(biāo)或優(yōu)化變量，例如平均在制品數(shù)，平均生產(chǎn)周期等。

常用的BAP求解方法是由一種生成方法(generative method)和一種估算方法(evaluative method)通過(guò)迭代的方式進(jìn)行求解。生成方法主要包括枚舉法、動(dòng)態(tài)規(guī)劃法、搜索法(如梯度搜索算法、啟發(fā)式算法、智能算法等)；估算方法主要包括解析法和仿真法。針對(duì)隨機(jī)系統(tǒng)的解析法主要是基于排隊(duì)/排隊(duì)網(wǎng)理論(queuing/ queuing network theory)[7]，包括精確解法和近似解法。其中，雖然精確解法可以獲得精確解，但存在狀態(tài)空間維數(shù)災(zāi)問(wèn)題，因此對(duì)于復(fù)雜結(jié)構(gòu)的系統(tǒng)，一般采用近似解法或仿真法。仿真法雖然不存在維數(shù)災(zāi)問(wèn)題，并且可以獲得逼近精確的解，但是需要進(jìn)行多次重復(fù)獨(dú)立實(shí)驗(yàn)，運(yùn)行耗時(shí)長(zhǎng)，將極大地增加BAP求解算法的時(shí)間復(fù)雜度。相反地，解析法的算法運(yùn)行耗時(shí)則少得多，可以提高優(yōu)化求解效率。近期研究中，Smith和Cruz[1]，Smith[2]，Cruz等[8]，li等[9]，以及Nahas[10]基于排隊(duì)網(wǎng)絡(luò)(queuing network)[11]建立系統(tǒng)性能估算模型，并應(yīng)用于求解BAP優(yōu)化問(wèn)題。國(guó)內(nèi)也有少數(shù)學(xué)者研究制造系統(tǒng)的BAP，如，席少輝等[12]針對(duì)具有隨機(jī)批量?jī)?chǔ)運(yùn)環(huán)節(jié)的裝配生產(chǎn)系統(tǒng)，以最小化系統(tǒng)成本為目標(biāo)，建立了考慮在制品數(shù)量成本和運(yùn)輸車輛成本的緩存區(qū)容量配置優(yōu)化模型。李翔等[13]針對(duì)多級(jí)流水車間緩沖區(qū)容量?jī)?yōu)化設(shè)置問(wèn)題，建立了連續(xù)時(shí)間馬爾可夫鏈的排隊(duì)網(wǎng)模型計(jì)算系統(tǒng)的關(guān)鍵性能指標(biāo)，以任務(wù)拒絕率為約束條件，提出一種緩沖區(qū)容量?jī)?yōu)化的啟發(fā)式優(yōu)化算法。

優(yōu)化系統(tǒng)資源配置時(shí)，需要解決的首要問(wèn)題就是：如何快速、精確地計(jì)算出系統(tǒng)的性能指標(biāo)值(如產(chǎn)出率、在制品數(shù)、生產(chǎn)周期等)，這是判斷一個(gè)資源配置方案是否滿足預(yù)期要求(系統(tǒng)性能約束)的依據(jù)。然而，由于系統(tǒng)的性能指標(biāo)無(wú)法由決策變量描述為一個(gè)具有具體的、封閉表達(dá)式的函數(shù)，從而難以采用現(xiàn)有隨機(jī)規(guī)劃模型的求解方法。因此，求解這類隨機(jī)規(guī)劃模型的首要步驟是提出一種能夠快速求解具有較高精確度的系統(tǒng)性能指標(biāo)的求解方法。作為一種系統(tǒng)建模分析的數(shù)學(xué)工具，排隊(duì)網(wǎng)絡(luò)模型是將一個(gè)或一組制造資源作為節(jié)點(diǎn)，節(jié)點(diǎn)上任務(wù)的堆積作為隊(duì)列，節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系作為連邊，從而將整個(gè)生產(chǎn)系統(tǒng)描述為一個(gè)由若干節(jié)點(diǎn)耦合的網(wǎng)絡(luò)。進(jìn)而通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)的變化、節(jié)點(diǎn)連邊的變化，以及節(jié)點(diǎn)連邊間的相互作用對(duì)該模型進(jìn)行研究，分析、計(jì)算系統(tǒng)性能指標(biāo)值。

本文研究可重入作業(yè)車間的排隊(duì)網(wǎng)建模與緩沖區(qū)容量配置優(yōu)化方法，與前人研究相比的創(chuàng)新之處體現(xiàn)在：

(1)研究對(duì)象為具有反饋回環(huán)結(jié)構(gòu)、一般分布(general distribution)(指抽象化、一般化的分布，可以根據(jù)參數(shù)定義任意特定的分布類型，例如負(fù)指數(shù)分布、愛(ài)爾朗分布等)的到達(dá)間隔時(shí)間和加工時(shí)間模型的制造系統(tǒng)。

(2)優(yōu)化模型具有產(chǎn)出率和生產(chǎn)周期雙重約束。生產(chǎn)周期是制造系統(tǒng)規(guī)劃設(shè)計(jì)的關(guān)鍵性能指標(biāo)，即便生產(chǎn)系統(tǒng)具有充足的產(chǎn)能，如果生產(chǎn)周期無(wú)法滿足訂單交貨期要求，也不符合系統(tǒng)規(guī)劃需求。因此，需要在BAP中權(quán)衡產(chǎn)出率約束和生產(chǎn)周期約束。

在Weiss等[6]的綜述研究中，現(xiàn)有文獻(xiàn)的BAP模型都只考慮產(chǎn)出率約束或者緩沖區(qū)容量取值約束，所有考慮多個(gè)性能指標(biāo)的研究都是在目標(biāo)函數(shù)中為每個(gè)性能指標(biāo)添加相應(yīng)的系數(shù)。雖然將同一個(gè)性能指標(biāo)置于目標(biāo)函數(shù)或者約束條件屬于對(duì)偶問(wèn)題，但是在不考慮其他約束條件的情況下，將性能指標(biāo)置于目標(biāo)函數(shù)的模型可以求得最優(yōu)解，而考慮性能指標(biāo)閾值約束條件的模型則可能不存在最優(yōu)解。同時(shí)，在約束條件中權(quán)衡多個(gè)性能指標(biāo)求解的難度更大，因?yàn)榫哂卸嘀丶s束問(wèn)題構(gòu)成的可行域可能是非凸的。

為此，本文針對(duì)可重入作業(yè)車間，建立了具有任意拓?fù)浣Y(jié)構(gòu)、一般分布到達(dá)間隔時(shí)間和加工時(shí)間的有限緩沖區(qū)開(kāi)排隊(duì)網(wǎng)模型，提出一種近似求解方法，計(jì)算系統(tǒng)性能指標(biāo)值，并嵌入到Polyblock算法中，求解具有雙重約束的緩沖區(qū)容量?jī)?yōu)化配置問(wèn)題。

1 問(wèn)題描述

1.1 作業(yè)車間系統(tǒng)排隊(duì)網(wǎng)模型

如圖1所示為任意拓?fù)浣Y(jié)構(gòu)的開(kāi)式排隊(duì)網(wǎng)絡(luò)(open queuing network)，圖中方形表示緩沖區(qū)(排隊(duì)隊(duì)列)，圓形表示數(shù)控加工設(shè)備(服務(wù)臺(tái))，兩者組合表示工作站(節(jié)點(diǎn))。系統(tǒng)包含m個(gè)工作站，系統(tǒng)外工件可以通過(guò)各個(gè)節(jié)點(diǎn)到達(dá)系統(tǒng)，到達(dá)過(guò)程服從泊松過(guò)程，平均到達(dá)速率為λ0i(i=1,2,…,m)。加工設(shè)備的加工方式為單件加工，加工時(shí)間服從平均速率為μi的一般分布。工作站的服務(wù)規(guī)則為“先到先服務(wù)”。每個(gè)工件按照各自的工藝路徑在各個(gè)工作站上進(jìn)行加工，節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑概率為αij，節(jié)點(diǎn)之間的工件到達(dá)間隔時(shí)間服從一般獨(dú)立分布。每個(gè)工作站包含一個(gè)容量為Ni的緩沖區(qū)，加工完成的工件可以通過(guò)各個(gè)節(jié)點(diǎn)離開(kāi)系統(tǒng)，完工件由節(jié)點(diǎn)i離開(kāi)系統(tǒng)的概率為αi0。系統(tǒng)阻塞機(jī)制為“服務(wù)后阻塞”。根據(jù)Kendall記法，每個(gè)節(jié)點(diǎn)的排隊(duì)模型為GI/G/1/K模型[5]。

如圖2所示，工件流路徑的集合與排隊(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)存在映射關(guān)系，由節(jié)點(diǎn)之間的路徑概率可以定義任意結(jié)構(gòu)的網(wǎng)絡(luò)模型。工件的加工路線是通過(guò)路徑概率描述的，在一個(gè)工作站完成加工的工件將按照路徑概率隨機(jī)選擇下一道工序進(jìn)行加工，包括重新進(jìn)入其先前已接受過(guò)加工的工作站(即反饋結(jié)構(gòu))。

1.2 BAP優(yōu)化問(wèn)題數(shù)學(xué)模型

優(yōu)化模型如下，決策變量為系統(tǒng)緩沖區(qū)容量配置向量，即xi≡X，

(1)

s.t.

Θ(X)≥Θmin，

(2)

Τ(X)≤Τmax，

(3)

xi∈N+,?i。

(4)

其中:式(1)為優(yōu)化目標(biāo)，即求解最優(yōu)的緩沖區(qū)配置向量Xopt，從而最小化總緩沖區(qū)容量Z。同時(shí)，滿足式(2)的產(chǎn)出率約束，即平均產(chǎn)出率不小于Θmin，以及式(3)的生產(chǎn)周期約束，即平均生產(chǎn)周期不大于Τmax。由于Θ(X)和Τ(X)為非封閉的函數(shù)，需要根據(jù)排隊(duì)網(wǎng)模型進(jìn)行求解。

BAP優(yōu)化問(wèn)題的求解思路如圖3所示，首先建立可重入作業(yè)車間的排隊(duì)網(wǎng)模型，并提出速率迭代法，近似求解系統(tǒng)平均產(chǎn)出率和生產(chǎn)周期。然后將速率迭代法嵌入到Polyblock算法中求解BAP優(yōu)化模型，用于判斷優(yōu)化過(guò)程中決策變量是否滿足系統(tǒng)性能指標(biāo)約束，最后獲得系統(tǒng)緩沖區(qū)容量的最優(yōu)配置。

2 系統(tǒng)性能指標(biāo)估算方法

與無(wú)限容量緩沖區(qū)的排隊(duì)網(wǎng)模型相比，有限緩沖區(qū)開(kāi)排隊(duì)網(wǎng)模型(Open Queuing Network with Finite Buffer，OQN/FB)的求解難度大得多，這是因?yàn)榭赡馨l(fā)生的阻塞(blocking)現(xiàn)象使得系統(tǒng)節(jié)點(diǎn)之間存在強(qiáng)耦合關(guān)聯(lián)，所以一般不存在乘積形式解(product-form solutions)?，F(xiàn)有求解方法中，精確解法(exact solution method)[14]可以求解穩(wěn)態(tài)的精確解，但存在狀態(tài)空間的維數(shù)災(zāi)問(wèn)題。狀態(tài)空間分解法(decomposition of state space method)[15]可以獲得較為精確的近似解，但會(huì)隨著系統(tǒng)規(guī)模的增大而提高算法時(shí)間復(fù)雜度，且只適用于Markov模型(負(fù)指數(shù)分布)。廣義擴(kuò)展法(Generalized expansion method)[16-17]可以求解一般分布的排隊(duì)網(wǎng)模型，但只適用于前饋式(feed-forward)結(jié)構(gòu)模型。

對(duì)于具有任意結(jié)構(gòu)的OQN/FB模型，文獻(xiàn)[15-25]分別針對(duì)所研究的模型提出近似求解方法。其中，除了Haskose等[15]，Jun等[21]，Lee等[23]，其他學(xué)者都只考慮包含前饋式結(jié)構(gòu)的排隊(duì)網(wǎng)模型，且大都假設(shè)到達(dá)間隔時(shí)間和服務(wù)時(shí)間為負(fù)指數(shù)分布。對(duì)于考慮一般分布的OQN模型，主要存在參數(shù)分解法[26]、最大熵法[27]、廣義擴(kuò)展法[16-17]3類求解方法，然而它們分別只針對(duì)特定的模型，即無(wú)限容量緩沖區(qū)、反復(fù)服務(wù)阻塞機(jī)制、前饋式結(jié)構(gòu)。對(duì)于考慮反饋結(jié)構(gòu)的OQN/FB模型，只有少量文獻(xiàn)研究。Jun等[21]研究了Markov模型，通過(guò)分解和迭代的方式以子系統(tǒng)的排隊(duì)長(zhǎng)度分布為收斂準(zhǔn)則，但僅限于由兩個(gè)節(jié)點(diǎn)連接構(gòu)成的網(wǎng)絡(luò)。Lee等[23]研究了一類不考慮外部到達(dá)、且負(fù)指數(shù)服務(wù)時(shí)間的“飽和模型”。Haskose等[15]提出狀態(tài)空間分解法求解任意拓?fù)浣Y(jié)構(gòu)的排隊(duì)網(wǎng)模型，但只適用于負(fù)指數(shù)分布假設(shè)的Markov模型，且存在狀態(tài)空間的維數(shù)災(zāi)問(wèn)題。

綜上所述，現(xiàn)有文獻(xiàn)中，尚未發(fā)現(xiàn)研究具有反饋結(jié)構(gòu)，且到達(dá)間隔和服務(wù)時(shí)間均為一般分布的OQN/FB模型的報(bào)道。反饋工件流增強(qiáng)了節(jié)點(diǎn)輸入/輸出過(guò)程的相關(guān)性，使得系統(tǒng)不具有Markov性，這極大地提高了問(wèn)題的分析求解難度。

2.1 參數(shù)分解

首先，如圖4所示，本文將每個(gè)節(jié)點(diǎn)的輸入和輸出過(guò)程分為四個(gè)階段：合流過(guò)程(merging process)、阻塞過(guò)程(blocking process)、排隊(duì)過(guò)程(queuing process)和分流過(guò)程(splitting process)。其中，反饋過(guò)程可以分解為一個(gè)分流過(guò)程和一個(gè)合流過(guò)程。對(duì)于阻塞過(guò)程，在每個(gè)節(jié)點(diǎn)前添加一個(gè)虛擬節(jié)點(diǎn)h，用于容納被阻塞的工件，從而將整個(gè)系統(tǒng)網(wǎng)絡(luò)擴(kuò)展為一個(gè)Jackson網(wǎng)絡(luò)[16]。

(1)合流過(guò)程

合流是由不同源流到達(dá)的工件匯合為一個(gè)工件流輸入的過(guò)程。輸入到節(jié)點(diǎn)i的工件包含3部分：從系統(tǒng)外到達(dá)的工件、在系統(tǒng)內(nèi)從節(jié)點(diǎn)j到達(dá)的前饋流，以及從節(jié)點(diǎn)k到達(dá)的反饋流。由此可以計(jì)算節(jié)點(diǎn)i的輸入速率：

(5)

根據(jù)漸近法[26]，未考慮阻塞的情況下，節(jié)點(diǎn)i的輸入過(guò)程分布的平方變異系數(shù)(Square Coefficient of Variation, SCV)為：

(6)

(2)阻塞過(guò)程

阻塞是工件因目的節(jié)點(diǎn)滿而被阻的過(guò)程?；跀U(kuò)散近似原則[28]，節(jié)點(diǎn)i的阻塞概率近似計(jì)算公式為：

(7)

虛擬節(jié)點(diǎn)h的回返阻塞概率為

(8)

另外，基于更新理論[7]，在節(jié)點(diǎn)i上被阻塞工件的延遲時(shí)間與節(jié)點(diǎn)i上加工件的剩余加工時(shí)間具有相同的分布。因此，虛擬節(jié)點(diǎn)h的平均加工速率為：

(9)

最后，輸入到節(jié)點(diǎn)i的工件來(lái)自被阻塞的工件流和不被阻塞的工件流兩者之一，因此，節(jié)點(diǎn)i輸入過(guò)程分布的SCV為：

(10)

(3)排隊(duì)過(guò)程

排隊(duì)是工件在緩沖區(qū)中等待接受加工的過(guò)程。由虛擬節(jié)點(diǎn)擴(kuò)展的系統(tǒng)為Jackson網(wǎng)模型，因此，節(jié)點(diǎn)i輸出過(guò)程分布的SCV為：

(11)

(4)分流過(guò)程

分流是一個(gè)工件流根據(jù)路徑概率分解為多個(gè)工件流輸出的過(guò)程。由排隊(duì)理論可知，當(dāng)系統(tǒng)達(dá)到穩(wěn)態(tài)時(shí)，排隊(duì)系統(tǒng)的輸入和輸出是平衡的。因此，節(jié)點(diǎn)i的輸出速率為：

(12)

式中ρh=λh/μh。

最后，對(duì)于分流過(guò)程分解得到的各個(gè)工件流的更新時(shí)間分布，通過(guò)求解其幾何分布形式的隨機(jī)和(random sum)，即可獲得原工件流輸出過(guò)程的更新間隔時(shí)間分布。由此，節(jié)點(diǎn)i分流過(guò)程的SCV為：

(13)

(14)

2.2 速率迭代法

2.2.1 算法步驟

對(duì)于前饋式結(jié)構(gòu)的排隊(duì)網(wǎng)絡(luò)，可以根據(jù)工件流方向逐個(gè)節(jié)點(diǎn)計(jì)算相關(guān)的參數(shù)值傳遞到后續(xù)節(jié)點(diǎn)，從而獲得整個(gè)系統(tǒng)的性能指標(biāo)值。但是，對(duì)于后饋式結(jié)構(gòu)的排隊(duì)網(wǎng)絡(luò)，各節(jié)點(diǎn)輸入和輸出過(guò)程的反饋工件流速率是彼此未知的，因此只能通過(guò)迭代的方式進(jìn)行求解。本文提出一種兩層嵌套迭代方式的速率迭代法(Rate Iteration Method，RIM)，求解思路如圖5所示，主迭代(外循環(huán))處理反饋結(jié)構(gòu)，由如下方程組表示：

(15)

(16)

(17)

其中F為次迭代(內(nèi)循環(huán))，計(jì)算各個(gè)節(jié)點(diǎn)輸入/輸出過(guò)程分解的參數(shù)。

詳細(xì)步驟如下：

步驟1初始化。

步驟2迭代過(guò)程。

步驟3收斂檢驗(yàn)。

步驟4指標(biāo)計(jì)算。

2.2.2 收斂性分析

命題1速率迭代算法是可收斂的，因?yàn)闈M足如下條件：

證明由如下迭代過(guò)程：

另外，對(duì)于任意排隊(duì)模型，條件(2)恒成立。

證畢。

2.3 算例分析

本節(jié)設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)算例，分別研究了輸入過(guò)程分布類型的假設(shè)以及緩沖區(qū)容量對(duì)系統(tǒng)性能的影響，同時(shí)與仿真實(shí)驗(yàn)對(duì)比驗(yàn)證了算法的精確性。采用MATLAB軟件編寫(xiě)解析算法程序，并在Siemens Tecnomatix Plant Simulation(eM-Plant)軟件上建立離散事件仿真模型。

2.3.1 輸入過(guò)程分布類型的假設(shè)

在工作站加工時(shí)間服從負(fù)指數(shù)分布(SVC=1)的條件下，本文所考慮節(jié)點(diǎn)輸入過(guò)程分布為一般分布，節(jié)點(diǎn)模型為GI/M/1/K；而Haskose等[15]假設(shè)節(jié)點(diǎn)輸入過(guò)程服從負(fù)指數(shù)分布，節(jié)點(diǎn)模型為M/M/1/K。因此，本節(jié)考慮一個(gè)如圖1所示的由3節(jié)點(diǎn)構(gòu)成的任意拓?fù)浣Y(jié)構(gòu)的對(duì)稱模型(各節(jié)點(diǎn)外部到達(dá)率相等，輸出的路徑概率均等)，對(duì)比這兩種假設(shè)條件下的模型結(jié)果。如表1和表2中第1、2列所示，考慮兩組算例的緩沖區(qū)容量分別為Ni=1和Ni=3。每組包含5個(gè)算例，對(duì)應(yīng)的系統(tǒng)外工件到達(dá)率分別為：(a)0.705 3，(b)0.806 0，(c)0.906 8，(d)1.007 5，(e)1.108 3，每個(gè)節(jié)點(diǎn)的加工速率均為2。計(jì)算結(jié)果如表1和表2所示，其中，“Δ1/%”、“Δ2/%”和“Δ3/%”分別為精確解法、HASKOSE分解法、速率迭代法與仿真結(jié)果的相對(duì)偏差百分比。對(duì)于算例(d)和(e)，由于采用擴(kuò)散近似方法計(jì)算節(jié)點(diǎn)阻塞概率，速率迭代法只適用于工件流強(qiáng)度ρi<1的模型。

對(duì)比仿真結(jié)果，速率迭代法的計(jì)算結(jié)果比精確解法和HASKOSE分解法的計(jì)算結(jié)果所產(chǎn)生的偏差都要小得多。精確解法和HASKOSE分解法研究的模型均具有Markov性，節(jié)點(diǎn)之間的到達(dá)間隔時(shí)間分布均假設(shè)為負(fù)指數(shù)分布。實(shí)際上，工件的反饋過(guò)程使得節(jié)點(diǎn)的輸入過(guò)程甚至都不具有更新過(guò)程的特性，本文假設(shè)其為一般分布的更新過(guò)程也只是對(duì)實(shí)際問(wèn)題的近似分析。盡管如此，算例結(jié)果表明速率迭代法的近似結(jié)果與仿真結(jié)果偏差較小，其中系統(tǒng)生產(chǎn)周期的偏差則比產(chǎn)出率的偏差更大。

表1 系統(tǒng)平均產(chǎn)出率結(jié)果對(duì)比

表2 系統(tǒng)平均生產(chǎn)周期結(jié)果對(duì)比

2.3.2 緩沖區(qū)容量對(duì)系統(tǒng)性能的影響

考慮一個(gè)具有16個(gè)工作站的作業(yè)車間，未考慮重入加工與返修、報(bào)廢時(shí)的系統(tǒng)模型，如圖6所示。根據(jù)系統(tǒng)輸入?yún)?shù)值設(shè)計(jì)3組實(shí)驗(yàn)，每組包含12個(gè)算例。限于篇幅，本文只列舉其中一組算例，參數(shù)如下：系統(tǒng)外任務(wù)到達(dá)率為λ1=λ2=λ3= 0.4。工作站加工速率及緩沖區(qū)容量分別為，當(dāng)i=1～9時(shí)，μi=0.8，Ni=4；當(dāng)i=10～15時(shí)μi=1.2，Ni=6；μ16=2.4，N16=10。考慮工作站加工過(guò)程的分布類型分別為二階愛(ài)爾朗分布(SCV=0.5)、負(fù)指數(shù)分布(SCV=1.0)和二階超指數(shù)分布(SCV=1.5)。

在部件測(cè)試階段和最終測(cè)試階段都可能發(fā)生返修或報(bào)廢的情形，發(fā)生概率分別為：α7-7=0.05，α8-8=0.05，α9-9=0.05；α10-1=0.05，α10-2=0.02，α10-4=0.10，α10-5=0.05，α10-0=0.03；α11-2=0.02，α11-3=0.05，α11-5=0.05，α11-6=0.10，α11-0=0.03；α14-14=0.05，α15-15=0.05；α16-12=0.05，α16-13=0.05。由于合流的工作站#10，#11和#16，以及發(fā)生重入加工或返修的工作站負(fù)荷率(工作流強(qiáng)度)較大而成為系統(tǒng)的瓶頸環(huán)節(jié)。為改善系統(tǒng)性能，考慮3組增加系統(tǒng)瓶頸節(jié)點(diǎn)的緩沖區(qū)容量的算例分析系統(tǒng)性能的變化規(guī)律：(a)Ni+1，(b)Ni+2，(c)Ni+3。

計(jì)算結(jié)果如表3所示，其中“Δ/%”為速率迭代法與仿真結(jié)果的相對(duì)偏差百分比。速率迭代法計(jì)算系統(tǒng)產(chǎn)出率和生產(chǎn)周期與仿真結(jié)果對(duì)比的偏差都很小，且具有相似的漸進(jìn)趨勢(shì)[1,9](即隨著緩沖區(qū)容量的增長(zhǎng)，解析結(jié)果和仿真解法均具有相同的變化趨勢(shì))，如圖7所示。由圖7可以看出，系統(tǒng)平均產(chǎn)出率和生產(chǎn)周期均隨著緩沖區(qū)容量的增加而增長(zhǎng)，但是生產(chǎn)周期的變化幅度要比產(chǎn)出率大得多。在緩沖區(qū)容量為無(wú)限大時(shí)，節(jié)點(diǎn)之間的耦合作用很小，因此，緩沖區(qū)容量的增加有利于降低耦合作用的影響。同時(shí)，節(jié)點(diǎn)的阻塞概率也會(huì)降低，因此可以提高系統(tǒng)產(chǎn)出率。但是，增加緩沖區(qū)容量的同時(shí)，也會(huì)在生產(chǎn)過(guò)程中增加在制品的數(shù)量，工件在系統(tǒng)中的排隊(duì)等待時(shí)間變長(zhǎng)，最終加長(zhǎng)了系統(tǒng)生產(chǎn)周期。由此可以看出，若要權(quán)衡系統(tǒng)產(chǎn)出率和生產(chǎn)周期的變化而改善系統(tǒng)性能，需要合理地優(yōu)化配置系統(tǒng)的緩沖區(qū)容量。

表3 算例結(jié)果對(duì)比

3 緩沖區(qū)容量配置優(yōu)化方法

3.1 求解算法

BAP模型中，由于系統(tǒng)性能指標(biāo)(平均產(chǎn)出率和生產(chǎn)周期)是關(guān)于決策變量(緩沖區(qū)容量大小)的非封閉函數(shù)，本文采用Polyblock算法[29]，并嵌入速率迭代法進(jìn)行求解，具體步驟如下：

步驟1初始化。

步驟2區(qū)域分割。

步驟3枚舉搜索。

3.2 優(yōu)化案例

以某企業(yè)生產(chǎn)車間為例，針對(duì)包含工作站數(shù)量為m={2,3,…,8}的作業(yè)車間，分別考慮3種生產(chǎn)情形：

(1)產(chǎn)線平衡的情形 系統(tǒng)外工件輸入到工作站#1的平均到達(dá)速率為每小時(shí)1個(gè)工件(即λ1=1)，每個(gè)工作站的平均加工速率為每小時(shí)1.4個(gè)工件(即μi=1.4,?i)；考慮產(chǎn)線“對(duì)稱或中心對(duì)稱”的重入加工情況，即任意工作站i,?i>(m/2)到工作站j=(m+1-i)的路徑概率為αij=5%。

(2)產(chǎn)線平衡且具有較高重入率的情形 工作站重入率為αij=10%,?i。

(3)產(chǎn)線非平衡的情形 工作站加工速率為μi∈{1.4,1.5},?i。

如表4和表5所示為緩沖區(qū)容量配置問(wèn)題的求解結(jié)果，對(duì)于具有不同數(shù)量工作站的系統(tǒng)，由速率迭代法計(jì)算的系統(tǒng)產(chǎn)出率和生產(chǎn)周期的近似度都非常高。在其他參數(shù)不變的情況下，隨著系統(tǒng)規(guī)模的擴(kuò)大，最優(yōu)化的緩沖區(qū)容量也隨之增加。對(duì)于平衡系統(tǒng)，在系統(tǒng)重入率較低時(shí)，整體的緩沖區(qū)容量分布大致呈“平緩下降的階梯型”，除了m=5和m=8的系統(tǒng)為先增長(zhǎng)后下降的分布趨勢(shì)。并且，合并重入工件流的工作站(即對(duì)稱產(chǎn)線上游工作站)所配置的緩沖區(qū)容量之和不小于分解重入工件流的工作站(即對(duì)稱產(chǎn)線的下游工作站)；而對(duì)于具有較高重入率的算例結(jié)果則相反。對(duì)于非平衡系統(tǒng)，由算例結(jié)果可以看出本文所提出的方法也能有效求解非平衡系統(tǒng)的緩沖區(qū)優(yōu)化配置問(wèn)題。

因此，本文所提出的優(yōu)化算法可以用于求解制造系統(tǒng)的資源配置優(yōu)化問(wèn)題，在滿足車間產(chǎn)能和訂單交貨期的條件下，優(yōu)化緩沖區(qū)容量配置，降低投資成本。

表4 平衡系統(tǒng)的緩沖區(qū)優(yōu)化配置

續(xù)表1

表5 非平衡系統(tǒng)的緩沖區(qū)優(yōu)化配置

4 結(jié)束語(yǔ)

針對(duì)定制型制造企業(yè)，考慮可重入作業(yè)的生產(chǎn)車間，建立包含前饋式結(jié)構(gòu)和反饋結(jié)構(gòu)的任意拓?fù)浣Y(jié)構(gòu)、工作站輸入/輸出過(guò)程服從一般分布的GI/G/1/K排隊(duì)網(wǎng)模型，提出一種兩層嵌套迭代的速率迭代法，近似求解系統(tǒng)性能指標(biāo)值。將反饋過(guò)程分解為一個(gè)分流過(guò)程和一個(gè)合流過(guò)程的組合，通過(guò)擬合節(jié)點(diǎn)輸入/輸出過(guò)程分布的速率和平方變異系數(shù)對(duì)排隊(duì)網(wǎng)絡(luò)進(jìn)行分析，推導(dǎo)出非線性方程組迭代求解系統(tǒng)性能指標(biāo)值。算例實(shí)驗(yàn)表明，將節(jié)點(diǎn)的輸入過(guò)程假設(shè)為負(fù)指數(shù)分布會(huì)導(dǎo)致非常大的偏差，而本文所提出的近似求解方法計(jì)算系統(tǒng)性能指標(biāo)值均具有較好的近似度。最后，針對(duì)緩沖區(qū)容量配置優(yōu)化問(wèn)題，建立隨機(jī)非線性整數(shù)規(guī)劃模型，提出嵌入速率迭代法的Polyblock算法，并通過(guò)優(yōu)化案例求解制造系統(tǒng)緩沖區(qū)容量的配置方案。

本文考慮的系統(tǒng)模型為單類產(chǎn)品的工件加工過(guò)程，實(shí)際上對(duì)于定制生產(chǎn)系統(tǒng)往往具有多品種小批量的生產(chǎn)特點(diǎn)，今后將針對(duì)具有不同工藝路徑的多類產(chǎn)品工件的系統(tǒng)資源配置問(wèn)題進(jìn)行研究。