非相關(guān)平行機(jī)臺(tái)的間斷批量和計(jì)劃排序研究

陳駐民， 羊 英

（1.東華大學(xué) 管理學(xué)院，上海 200051；2.上海第二工業(yè)大學(xué)，上海 201209）

0 引言

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

1 算法描述

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

圖1 空閑區(qū)類型

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

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

3）(j1,0,j*) 或 (s1,0,s*) 空閑區(qū)開(kāi)始處安排生產(chǎn)j1或j*,需要相應(yīng)的工具s1或s*，結(jié)束的時(shí)候一定是生產(chǎn)不同的產(chǎn)品j*，使用不同的工具s*。

4）(j*,0,j1)或(s*,0,s1) 空閑區(qū)開(kāi)始處安排生產(chǎn)j*,需要相應(yīng)的工具s*，結(jié)束的時(shí)候一定是生產(chǎn)不同的產(chǎn)品j1，使用不同的工具s1。另外，空閑區(qū)是不固定的，或者在開(kāi)始，或者在結(jié)束，對(duì)于不同的產(chǎn)品也可以使用同樣的工具。

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

1.1 選擇一個(gè)生產(chǎn)順序

產(chǎn)品的生產(chǎn)順序是由給定的生產(chǎn)列表制定的，生產(chǎn)列表的順序是由不同的優(yōu)先規(guī)則制定的，可以采用如下幾種優(yōu)先規(guī)則：

1）處理生產(chǎn)訂單的機(jī)器數(shù)量

該規(guī)則是通過(guò)增加可以用來(lái)進(jìn)行生產(chǎn)的機(jī)器數(shù)量來(lái)安排生產(chǎn)訂單。這樣可以避免一些小訂單（只需要幾臺(tái)機(jī)器）不會(huì)總排斥在計(jì)劃外。

2）生產(chǎn)訂單的規(guī)模

采用這個(gè)規(guī)則，可以降序安排訂單大小。采用此規(guī)則，可以使總的生產(chǎn)規(guī)模最大化。另一方面，該規(guī)則的一個(gè)最大的缺點(diǎn)是把小的訂單總是排斥在計(jì)劃之外。

3）參考以前計(jì)劃中的優(yōu)先級(jí)

采用該規(guī)則，從上個(gè)月制定的計(jì)劃中檢查最后幾臺(tái)機(jī)器的排序情況，選擇同樣類型的訂單最先排序，采用該方法可能會(huì)得到最小的換設(shè)頻率。

4）由用戶定義優(yōu)先級(jí)

用戶可以根據(jù)他想要的順序定義訂單的優(yōu)先級(jí)。

1.2 給選定的空閑區(qū)分配訂單

選定的生產(chǎn)訂單分配到空閑區(qū)域，采用的是后溯或前溯計(jì)劃的方法。先介紹幾個(gè)符號(hào)定義：

1）DDI：產(chǎn)品I的訂單截止日期；

2）Nj1,I：生產(chǎn)訂單I的產(chǎn)品j1的計(jì)劃生產(chǎn)數(shù)量；

3）u：空閑區(qū)的長(zhǎng)度，例如：連續(xù)空閑的天數(shù)；

4）h: 空閑區(qū)的第一天；

5）pj1,m：產(chǎn)品j1在選中的空閑區(qū)機(jī)器m上的生產(chǎn)率；

6）ls1：機(jī)器工具的使用壽命，用百分?jǐn)?shù)來(lái)表示；

7）wsi,j1,m：在機(jī)器m 上生產(chǎn)產(chǎn)品1天的其工具的損耗，用百分?jǐn)?shù)來(lái)表示。具體方法如下：前溯計(jì)劃：

1）分配產(chǎn)品j1到空閑區(qū)的第一天；

2）空閑區(qū)天數(shù)=空閑區(qū)天數(shù)-1；

3）訂單上的數(shù)量= 訂單上的數(shù)量-產(chǎn)品j1在機(jī)器m上的生產(chǎn)率；

4）工具的使用壽命=工具的使用壽命-在機(jī)器m上生產(chǎn)產(chǎn)品j1一天的損耗；

5）如果u=0 或nj1=0 或ls1=0 結(jié)束程序否則轉(zhuǎn)到step2；

后溯計(jì)劃：

1）分配產(chǎn)品j1給后一個(gè)空閑區(qū)的第一天（h+u-1）；

2）空閑區(qū)天數(shù)=空閑區(qū)天數(shù)-1；

3）訂單上的數(shù)量= 訂單上的數(shù)量-產(chǎn)品j1在機(jī)器m上的生產(chǎn)率；

4）工具的使用壽命=工具的使用壽命-工具在機(jī)器m上生產(chǎn)產(chǎn)品j1一天的損耗；

5）如果u=0 或nj1=0 或ls1=0 結(jié)束程序否則轉(zhuǎn)到2）。

1.3 為生產(chǎn)訂單的分配選定一個(gè)空閑區(qū)域

在選擇了生產(chǎn)訂單算法，并且把生產(chǎn)訂單分配給一個(gè)機(jī)器以后，采用以下的算法進(jìn)行：

假設(shè)當(dāng)前正在加工的產(chǎn)品為產(chǎn)品D和產(chǎn)品B，正在使用的工具是S1。

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

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

3） 讀取正在使用工具s1加工的產(chǎn)品D和產(chǎn)品B；

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

5）讀取將要被插入空閑區(qū)的產(chǎn)品型號(hào)d或b；

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

該算法盡力尋找現(xiàn)在正在被機(jī)器所加工的相同產(chǎn)品訂單，如果訂單中不存在和正在處理的產(chǎn)品相同的訂單則去找尋使用相同工具的的訂單，如果上述兩種情況都沒(méi)發(fā)現(xiàn)，則采用后溯計(jì)劃方法尋找更大的空閑區(qū)間。

2 算法示例

考慮如下的例子，要在4臺(tái)機(jī)器上安排8個(gè)訂單，訂單的排序及其訂單內(nèi)容如表1所示。生產(chǎn)過(guò)程中要考慮如下假設(shè)：

1）機(jī)器換設(shè)的原因是生產(chǎn)的產(chǎn)品使用的工具發(fā)生改變，或者工具的自然磨損。

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

3）生產(chǎn)線的生產(chǎn)能力為每天10個(gè)單位

4）訂單的排序可以采用多種方式安排其優(yōu)先級(jí)

表1 排序后訂單

開(kāi)始時(shí)，即上一個(gè)計(jì)劃的最后一天，機(jī)器1加工的產(chǎn)品是產(chǎn)品a，所用的工具是X，剩余80%的耐耗時(shí)間，機(jī)器2 加工的產(chǎn)品是產(chǎn)品c，工具是Y，剩余30% 的耐耗時(shí)間，機(jī)器3加工的產(chǎn)品是產(chǎn)品f,所用的工具是Z，剩余70%的耐耗時(shí)間，機(jī)器4加工的產(chǎn)品是產(chǎn)品g，所用的工具是X，剩余50%的耐耗時(shí)間。采用本文的算法，可得到如下的結(jié)果，如圖2 所示：

圖2 采用啟發(fā)式算法的結(jié)果

圖2中給出的排序訂單8中的產(chǎn)品g有10個(gè)單位的生產(chǎn)任務(wù)由于超過(guò)了其生產(chǎn)能力而未被安排。

本文以某紡織企業(yè)為例，表2給出了實(shí)際生產(chǎn)系統(tǒng)中某月的訂單情況。

表2 某月定單情況

表3 實(shí)際系統(tǒng)與采用啟發(fā)式算法的比較

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

3 結(jié)論

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

[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.