混流企業(yè)中基于瓶頸的啟發(fā)式算法的應(yīng)用

陳駐民，羊 英

(1.東華大學(xué)管理學(xué)院上海 200051;2.上海第二工業(yè)大學(xué)實驗實訓(xùn)中心，上海 201209)

筆者研究的是非相關(guān)平行機(jī)臺的混流生產(chǎn)中帶有瓶頸的作業(yè)排序問題，非相關(guān)平行機(jī)臺的混流生產(chǎn)在現(xiàn)實的生產(chǎn)系統(tǒng)中十分普遍，該現(xiàn)象的產(chǎn)生可能是由于為了擴(kuò)大生產(chǎn)能力而在某些階段增加了平行機(jī)臺，或者由于在某些階段存在新、舊機(jī)器的協(xié)同工作而存在非相關(guān)平行機(jī)臺。存在瓶頸現(xiàn)象的混流生產(chǎn)在實際的生產(chǎn)系統(tǒng)也經(jīng)常出現(xiàn)［1-7］，例如化工、紡織、食品和造紙等企業(yè)，這些企業(yè)在生產(chǎn)過程中常出現(xiàn)相似產(chǎn)品在非相關(guān)平行機(jī)上的作業(yè)排序問題，同時這些生產(chǎn)系統(tǒng)也通常會存在生產(chǎn)瓶頸。瓶頸的管理在生產(chǎn)排序中是一個非常重要的管理任務(wù)，對于帶有瓶頸的生產(chǎn)線的排序通常分以下3個步驟來完成［8-9］:①瓶頸的識別;②瓶頸階段的排序;③非瓶頸階段的排序。筆者對研究的混流生產(chǎn)問題作如下假設(shè):存在n個工件需要通過J個生產(chǎn)階段的流水生產(chǎn)線，同時每個階段均有一個或多個平行機(jī)臺。

近年來很多研究者開始研究混流生產(chǎn)問題，但是大多數(shù)研究者研究的是多階段的混流生產(chǎn)中存在相同平行機(jī)臺的排序問題［10］，研究者通常采用模擬退火算法、遺傳算法等搜索方法完成該問題的生產(chǎn)排序，但是搜索的效率存在很大的問題，同時對于研究的問題也有很多限制，而對于混流生產(chǎn)中非相關(guān)平行機(jī)臺的問題很少有人去解決。筆者以紡織企業(yè)為例，提出了一個基于瓶頸的啟發(fā)式算法在非相關(guān)平行機(jī)臺生產(chǎn)排序中的應(yīng)用，該算法的目的是為了最小化上述問題的完工時間，同時該算法的效率及適用場合優(yōu)于智能搜索算法，可較好地解決混流生產(chǎn)中帶瓶頸的生產(chǎn)排序問題。

1 混流生產(chǎn)中基于瓶頸的啟發(fā)式算法

1.1 符號的定義

所提出的基于瓶頸的啟發(fā)式算法用于解決非相關(guān)平行機(jī)臺的混流生產(chǎn)作業(yè)排序，由于假設(shè)每個階段都存在非相關(guān)平行機(jī)臺，因此在每一個階段中都使用以下3種機(jī)器選取規(guī)則:①在可用的機(jī)器中選取最早空閑的機(jī)器;②當(dāng)工件分配到可用機(jī)器的時候，選取可以最早完工的機(jī)器;③當(dāng)工件分配到該階段所有機(jī)器時(可用或不可用)，選取可以最早完工的機(jī)器。

為了描述該方法，對如下的符號進(jìn)行了定義:

i為工件編號，i=1，2，3，…，n;j為階段編號，j=1，2，3，…，J;b 為瓶頸階段編號，b∈［1，2，3，…，J］;s為在階段 j機(jī)器的編號，s=1，2，3，…，mj;mj為階段j中非相關(guān)平行機(jī)臺的數(shù)目為工件i在j階段的平均處理時間;Pibs為在瓶頸階段b工件i在機(jī)器s上的處理時間;Rj為階段j的工作負(fù)荷;CiJ為工件i在最后階段J的完成時間;為工件i在瓶頸階段b之前的總的處理時間;為工件i在瓶頸階段b之后的總的處理時間。

1.2 問題描述

筆者對需要解決的問題作如下的假設(shè):包含J個階段，其中又包含一個瓶頸階段b，在階段j有mj個非相關(guān)平行機(jī)臺，非相關(guān)平行機(jī)臺mj的數(shù)量可能不同;有n個工件需要被處理，每個工件執(zhí)行相同的加工路徑;所有的工件在0時刻都是可用的;每個工件在每個階段每臺機(jī)器上的處理時間都是預(yù)先知道的，一臺機(jī)器在一個時刻只能處理一個工件，在兩個階段之間有無限緩沖期，這里不考慮停機(jī)或裝設(shè)成本;工作的負(fù)荷作為瓶頸的指示器，階段j的工作負(fù)荷通過計算該階段所有操作的處理時間總和除以機(jī)器的數(shù)量得到，用公式，擁有最大Rj值的階段被定義為瓶頸階段。

1.3 算法描述

GAREY等人證明了具有3臺機(jī)器的最小化完工時間流程排序問題是一個NP困難問題，HOOGEVEEN等人證明了具有兩階段的最小化完工時間的問題是NP困難問題，因此，筆者提出的問題一定也是NP困難問題。

筆者基于瓶頸的啟發(fā)式算法主要思想是瓶頸階段的計劃可能會影響非瓶頸階段的計劃，該啟發(fā)式算法包含3步:①確認(rèn)瓶頸階段;②采用基于瓶頸的方法產(chǎn)生最初的排序次序;③在最初的排序基礎(chǔ)上采用基于瓶頸的插入方法產(chǎn)生最后的排序。

算法中的最初計劃的排序方法如下:

(1)把集合A置為空集。

(2)把系統(tǒng)分為瓶頸前系統(tǒng)，瓶頸系統(tǒng)以及瓶頸后系統(tǒng)，計算瓶頸前系統(tǒng)和瓶頸后系統(tǒng)的時間和時間。

(6)在集合A中獲得最初的工件序列。

(7)停止程序。

算法中在最初排序的基礎(chǔ)上采用基于瓶頸的插入方法產(chǎn)生最終的排序方法如下:

(1)選擇最初序列中的第一個工件，讓它成為當(dāng)前序列。

(2)在最初序列中選擇下一個工件，把它插入到當(dāng)前序列的前、后位置和每兩個連續(xù)工件的中間位置。

(3)計算在第(2)步中產(chǎn)生的部分序列的完工時間，然后在瓶頸階段調(diào)整工件的進(jìn)入序列，同時在第一階段也要同時調(diào)整其序列。

(4)選擇最小的完工時間的部分序列，讓該部分序列成為當(dāng)前序列。

(5)當(dāng)目前部分計劃包含所有工件時，停止程序，否則轉(zhuǎn)到第(2)步。

2 實例驗證

筆者以某紡織企業(yè)為例，表1中給出了原棉在經(jīng)過染色、紡紗和織布3個階段的處理時間。

表1 原棉的單位處理時間

利用基于瓶頸的啟發(fā)式算法進(jìn)行計算。

(1)計算表1中每個階段的工作負(fù)荷，它們是 R1=52.55，R2=120.00，R3=66.25，經(jīng)過計算確定階段2是其瓶頸。

(2)采用基于瓶頸的方法產(chǎn)生最初的排序次序。最后產(chǎn)生的最初最優(yōu)序列為1-3-2。

(3)在最初的排序基礎(chǔ)上采用基于瓶頸的插入方法產(chǎn)生最后的排序。

計算部分序列3-1的完工時間，如表2所示，其完工時間的值為170。

表2 序列3-1的完工時間值

計算部分序列1-3的完工時間，如表3所示，其完工時間的值為200。

表3 序列1-3的完工時間值

確定其最優(yōu)部分排列為3-1。

計算部分序列2-3-1的完工時間，如表4所示，其完工時間的值為235。

表4 序列2-3-1的完工時間值

計算部分序列3-2-1的完工時間，如表5所示，其完工時間的值為250。

表5 序列3-2-1的完工時間值

計算部分序列3-1-2的完工時間，如表6所示，其完工時間的值為220。

表6 序列3-1-2的完工時間值

最后得到最優(yōu)序列為3-1-2。表2～表6中的4個字段的含義分別為:第1個字段為原棉編號，第2個字段為工序編號，第3個字段為原棉加工開始時間，第4個字段為原棉加工結(jié)束時間。

3 結(jié)論

筆者以紡織企業(yè)為例采用基于瓶頸的啟發(fā)式算法較好地解決了基于瓶頸的非相關(guān)平行機(jī)臺的混合流程型企業(yè)的排序問題，同時該方法也可以較好地推廣到基于瓶頸的工件生產(chǎn)排序問題中。關(guān)于非相關(guān)平行機(jī)臺的排序問題研究目前還鮮見報道，對于該問題的研究基本局限于采用模擬退火算法、遺傳算法等搜索算法，而搜索算法的效率問題卻成為了實際應(yīng)用的瓶頸。筆者提出的算法能大大提高排序效率，測試采用C++編制的程序，在6.88 s內(nèi)可以解決100個工件的排序問題，該算法有較好的應(yīng)用前景。

［1］WITTROCK R J.An adaptable scheduling algorithm for flexible flow lines［J］.Operations Research，1988(36):445-453.

［2］GUINET A G P，SOLOMON M.Scheduling hybrid flow shops to minimize maximum tardiness or maximum completion time［J］.International Journal of Production Research，1996(34):1643-1654.

［3］LEON V J，RAMAMOORTHY B.An adaptable problem space-based search method for flexible flow line scheduling［J］.IIE Transactions，1997(29):115 –125.

［4］AGNETIS A，PACIFICI A，ROSSI F，et al.Scheduling of flexible flow shop in an automobile assembly plant［J］.European Journal of Operational Research，1997，97(2):348-362.

［5］JIN Z H，OHNO K，ITO T，et al.Scheduling hybrid flow shops in printed circuit board assembly lines［J］.Production and Operations Management，2002(12):216-230.

［6］SAWIK T.An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers［J］.Mathematical and Computer Modeling，2002(36):461-471.

［7］ALISANTOSO D，KHOO L P，JIANG P Y.An immune algorithm approach to the scheduling of a flexible PCB flow shop［J］.International Journal of Advanced Manufacturing Technology，2003(22):819-827.

［8］ADLER L，F(xiàn)RAIMAN N，KOBACKER E，et al.BPSS:a scheduling support system for the packaging industry［J］.Operations Research，1993(41):641 –648.

［9］PATERNINA-ARBOLEDA C D，MONTOYA-TORRES J R，ACERO-DOMINGUEZ M J，et al.Scheduling jobs on a k-stage flexible flow-shop［J］.Annals of Operations Research，2008(164):29-40.

［10］LINN R，ZHANG W.Hybrid flow shop scheduling:a survey［J］.Computer and Industrial Engineering，1999(37):57-61.