非相關平行機臺的間斷批量和計劃排序研究

陳駐民， 羊 英

（1.東華大學 管理學院，上海 200051；2.上海第二工業大學，上海 201209）

0 引言

混合流程生產的概念產生于70年代[1]，是指包含若干個生產階段或工作中心，每個生產階段或工作中心都有平行機器[2]。某些生產階段可能只由一個設備，但是至少有一個生產階段必須有多個設備。每個產品必須在每個生產階段的至少一臺機器上進行加工處理。本文研究的是混合流程型企業的間斷批量和計劃的定制問題。該問題是一個同時考慮批量和計劃問題，對于該問題的研究引起了很多研究者的關注[3～7]。文獻[8]解決的問題是相同平行機的批量和計劃問題，考慮的是固定的裝設成本，而且沒有延期的發生，文獻[9]提出了解決單個機器及相同平行機的方法。本文采用文獻[8]提到的方法解決間斷批量和計劃排序，本文以紡織企業為例，考慮的是非相同平行機的問題，很好地解決了與紡織企業具有相似特征的相似產品在非相關平行機上的混合流程型企業的間斷批量和計劃排序問題。

1 算法描述

本文的啟發式算法涉及如下幾個概念：空閑區—指在未分配生產任務的加工機器上連續的空閑天數，完成生產訂單 I，需要產品j1的數量為nj1個單位，需要的加工工具為s1，最后的完成日期為DDI，算法中假定完成該訂單需要6個空閑天數，如圖1所示。在空閑區的描述中規定j*是不同于j1的產品，s*是不同于S1的機器。同時有以下幾個表達方式需要說明：

圖1 空閑區類型

1）(j1,0) 被加工的產品為j1，直到訂單的截止日期有若干可用的空閑天數。

2）(s1,0) 產品j*的生產需要利用工具s1，同時直到訂單的截止日期有一系列可用的空閑天數。

3）(j1,0,j*) 或 (s1,0,s*) 空閑區開始處安排生產j1或j*,需要相應的工具s1或s*，結束的時候一定是生產不同的產品j*，使用不同的工具s*。

4）(j*,0,j1)或(s*,0,s1) 空閑區開始處安排生產j*,需要相應的工具s*，結束的時候一定是生產不同的產品j1，使用不同的工具s1。另外，空閑區是不固定的，或者在開始，或者在結束，對于不同的產品也可以使用同樣的工具。

該算法有以下三個步驟：1）選擇生產訂單，2）選擇一個空閑區域用于指派產品訂單，3）把一個產品訂單分配到空閑區域。具體算法如下。在批量和計劃制定開始之前，先把生產訂單進行排序，產生生產訂單列表。該列表可以細分成不同的子列表，相同的訂單截止日期可以組成一個子列表。

1.1 選擇一個生產順序

產品的生產順序是由給定的生產列表制定的，生產列表的順序是由不同的優先規則制定的，可以采用如下幾種優先規則：

1）處理生產訂單的機器數量

該規則是通過增加可以用來進行生產的機器數量來安排生產訂單。這樣可以避免一些小訂單（只需要幾臺機器）不會總排斥在計劃外。

2）生產訂單的規模

采用這個規則，可以降序安排訂單大小。采用此規則，可以使總的生產規模最大化。另一方面，該規則的一個最大的缺點是把小的訂單總是排斥在計劃之外。

3）參考以前計劃中的優先級

采用該規則，從上個月制定的計劃中檢查最后幾臺機器的排序情況，選擇同樣類型的訂單最先排序，采用該方法可能會得到最小的換設頻率。

4）由用戶定義優先級

用戶可以根據他想要的順序定義訂單的優先級。

1.2 給選定的空閑區分配訂單

選定的生產訂單分配到空閑區域，采用的是后溯或前溯計劃的方法。先介紹幾個符號定義：

1）DDI：產品I的訂單截止日期；

2）Nj1,I：生產訂單I的產品j1的計劃生產數量；

3）u：空閑區的長度，例如：連續空閑的天數；

4）h: 空閑區的第一天；

5）pj1,m：產品j1在選中的空閑區機器m上的生產率；

6）ls1：機器工具的使用壽命，用百分數來表示；

7）wsi,j1,m：在機器m 上生產產品1天的其工具的損耗，用百分數來表示。具體方法如下：前溯計劃：

1）分配產品j1到空閑區的第一天；

2）空閑區天數=空閑區天數-1；

3）訂單上的數量= 訂單上的數量-產品j1在機器m上的生產率；

4）工具的使用壽命=工具的使用壽命-在機器m上生產產品j1一天的損耗；

5）如果u=0 或nj1=0 或ls1=0 結束程序否則轉到step2；

后溯計劃：

1）分配產品j1給后一個空閑區的第一天（h+u-1）；

2）空閑區天數=空閑區天數-1；

3）訂單上的數量= 訂單上的數量-產品j1在機器m上的生產率；

4）工具的使用壽命=工具的使用壽命-工具在機器m上生產產品j1一天的損耗；

5）如果u=0 或nj1=0 或ls1=0 結束程序否則轉到2）。

1.3 為生產訂單的分配選定一個空閑區域

在選擇了生產訂單算法，并且把生產訂單分配給一個機器以后，采用以下的算法進行：

假設當前正在加工的產品為產品D和產品B，正在使用的工具是S1。

1）如果存在[j1,0]或[j1,0,j*]或[j*,0,j1]空閑區，則轉到2），否則如果存在[s1,0]或[s1,0,s*]或[s*,0,s1]則轉到3），否則選擇有最大空閑天數的空閑區u，然后采用后溯計劃方法；

2）如果存在[j1,0]或[j1,0,j*]，則采用前溯計劃方法，否則如果存在[j*,0,j1]，則采用后溯計劃方法；

3） 讀取正在使用工具s1加工的產品D和產品B；

4）讀取可用的空閑區[s1,0]；[s1,0,s*]；[s*,0,s1])；

5）讀取將要被插入空閑區的產品型號d或b；

6） 如果(D;[s1,0]或[s1,0,s*];d)或（B；[s1,0]或 [s1,0,s*];d）或(B;[s1,0]或[s1,0,s*];b) 則采用前溯計劃方法，否則如果（D;[s*,0,s1];d）或（D;[s*,0,s1];b）或(B;[s*,0,s1]);b) 則采用后溯計劃方法，否則選取有最大空閑天數的空閑區后采用后溯計劃方法。

該算法盡力尋找現在正在被機器所加工的相同產品訂單，如果訂單中不存在和正在處理的產品相同的訂單則去找尋使用相同工具的的訂單，如果上述兩種情況都沒發現，則采用后溯計劃方法尋找更大的空閑區間。

2 算法示例

考慮如下的例子，要在4臺機器上安排8個訂單，訂單的排序及其訂單內容如表1所示。生產過程中要考慮如下假設：

1）機器換設的原因是生產的產品使用的工具發生改變，或者工具的自然磨損。

2）工具的磨損為每天10%

3）生產線的生產能力為每天10個單位

4）訂單的排序可以采用多種方式安排其優先級

表1 排序后訂單

開始時，即上一個計劃的最后一天，機器1加工的產品是產品a，所用的工具是X，剩余80%的耐耗時間，機器2 加工的產品是產品c，工具是Y，剩余30% 的耐耗時間，機器3加工的產品是產品f,所用的工具是Z，剩余70%的耐耗時間，機器4加工的產品是產品g，所用的工具是X，剩余50%的耐耗時間。采用本文的算法，可得到如下的結果，如圖2 所示：

圖2 采用啟發式算法的結果

圖2中給出的排序訂單8中的產品g有10個單位的生產任務由于超過了其生產能力而未被安排。

本文以某紡織企業為例，表2給出了實際生產系統中某月的訂單情況。

表2 某月定單情況

表3 實際系統與采用啟發式算法的比較

從表3中可以看出，采用該啟發式算法可以使換設次數和拖期率都能得到明顯改善。

3 結論

本文給出了一個求解混合流程企業中非相關平行機的間斷批量和計劃排序的啟發式算法，該算法的目的是最小化換設頻率，其間考慮生產能力，工具的自然損耗，訂單的優先級排序以及訂單的最后截止日期等限制，采用此方法能夠較方便地同時解決生產中批量的規劃和生產排序問題。

[1] T.S.Arthanary,K.G.Ramaswamy,An extension of two machine sequencing problems[J].Operations Research8(1971)10–22.

[2] S.E.Elmaghraby, R.E.Karnoub, Production control inflexible flowshops:anexamplefromtextile manufacturing[C].OR ReportNo.305ORand IE Department,NorthCarolina State University,USA,1995.

[3] Salomon,M.,Kroon,L.G.,Kuik,R.,&VanWassenhove,L.N.(1991).Some extensions of the discrete lotsizing and scheduling problem[J].Management Science,37,801–812.

[4] Drexl, A.,& Kimms,A.(1997).Lot sizing andscheduling—Survey and extensions[J].European Journal of Operational Research,99,221-235.

[5] Fleischmann,B.(1990).The discrete lot-sizing and problem[J].European Journal of Operational Research,44,337-348.

[6] Staggemeier,A.T.,Clark,A.R.(2001).A survey of lot and scheduling models[C].Proceedings of the 23rd Annual Symposium of the BrazilianOperational Research Society(SOBRAPO),Brazil (938–947).

[7] Kuik,R.,Salomon, M.,&VanWassenhove,L.N.(1994).Batching decisions: Structure andmodels[J].European Journal of Operational Research,75,243-263.

[8] Pattloch,M.,Schmidt,G.,&Kovalyov,M.Y.(2001).algorithms for lot size scheduling with application in the tobacco industry[J].Computers and Industrial Engineering,39,235-253.

[9] Blazewicz,J.,Ecker,K.,Pesch,E.,Schmidt,G.,Weglarz,J.(1996).Scheduling computers and manufacturing processes[C].Berlin:Springer.