多產(chǎn)品批處理的多機(jī)并行調(diào)度問(wèn)題研究

馮夢(mèng)華，謝 勇 FENG Meng-hua, XIE Yong

（華中科技大學(xué) 系統(tǒng)工程研究所，湖北 武漢430074）

(Institute of Systems Engineering, Huazhong University of Science & Technology, Wuhan 430074, China)

0 引 言

生產(chǎn)計(jì)劃與調(diào)度問(wèn)題是制造企業(yè)最基礎(chǔ)也最核心的問(wèn)題，是在滿足某些約束條件（如有限生產(chǎn)能力及資源、任務(wù)釋放時(shí)間和截止期等） 下對(duì)任務(wù)進(jìn)行合理排序，并安排各個(gè)任務(wù)開(kāi)工時(shí)間，最終實(shí)現(xiàn)企業(yè)一個(gè)或多個(gè)目標(biāo)的最優(yōu)化。實(shí)際中對(duì)調(diào)度的評(píng)價(jià)大致可歸為三類(lèi)：最大能力指標(biāo)、成本指標(biāo)、客戶滿意度指標(biāo)[1]，其中最大能力指標(biāo)大多應(yīng)用在需求固定或需求無(wú)上限的情況下，傳統(tǒng)生產(chǎn)調(diào)度應(yīng)用較多，但實(shí)際卻是提前完成生產(chǎn)的成品需入成品倉(cāng)庫(kù)需要支付一筆不小的倉(cāng)儲(chǔ)費(fèi)用，延期生產(chǎn)產(chǎn)品則會(huì)有損企業(yè)聲譽(yù)，同時(shí)企業(yè)還需支付違約金，因此實(shí)際中更多的綜合考慮庫(kù)存成本以及延期懲罰費(fèi)用。

考慮庫(kù)存成本、延期懲罰生產(chǎn)調(diào)度問(wèn)題的核心是準(zhǔn)時(shí)化生產(chǎn)。專(zhuān)家學(xué)者對(duì)其進(jìn)行大量研究：Held[2]和Bagchi U[3]研究了單機(jī)環(huán)境下的提前、拖期調(diào)度問(wèn)題；Prabuddha De[4]探討了單機(jī)調(diào)度完成時(shí)間偏差最小化問(wèn)題，調(diào)度中考慮了不同任務(wù)的加權(quán)系數(shù)情況；Coleman[5]針對(duì)考慮任務(wù)準(zhǔn)備時(shí)間與加工順序相關(guān)這一實(shí)際情況研究單機(jī)調(diào)度問(wèn)題；Fry and Armstrong[6]，Garey and Tarjan[7]和Yano and Kim[8]研究了給定排序下的開(kāi)工時(shí)間優(yōu)化問(wèn)題，但對(duì)懲罰權(quán)重有一定的限制；Cheng T C E[9]討論了互不相關(guān)的任務(wù)在多機(jī)的并行調(diào)度問(wèn)題，闡述流程時(shí)間加成本最小、提前拖期懲罰費(fèi)用最小兩個(gè)問(wèn)題。

多機(jī)并行調(diào)度問(wèn)題雖得到一定研究，但調(diào)度的任務(wù)間大多是無(wú)關(guān)的，然實(shí)際中會(huì)由于生產(chǎn)容量限制需要將訂單拆分為加工任務(wù)，這些任務(wù)間實(shí)際上存在一定關(guān)系的，這對(duì)調(diào)度有一定的影響。本文以某酒企業(yè)生產(chǎn)為研究背景，研究已知交貨期的訂單在生產(chǎn)容量限制分割為子訂單后的多機(jī)并行調(diào)度問(wèn)題，盡量實(shí)現(xiàn)各訂單的準(zhǔn)時(shí)化生產(chǎn)。

1 問(wèn)題描述

本文研究的酒生產(chǎn)調(diào)度是在一般車(chē)間調(diào)度問(wèn)題上簡(jiǎn)化的，不考慮具體的工藝路線，整套的工藝路線在一臺(tái)機(jī)器上即可生產(chǎn)完；其中加入了生產(chǎn)中容量限制這一約束，在可能情況下都以最大容量組織生產(chǎn)，最后不夠最大容量的人任為一批組織生產(chǎn)，這就要求先要對(duì)生產(chǎn)訂單進(jìn)行分割，在此基礎(chǔ)上進(jìn)行調(diào)度。本文的計(jì)劃排程描述如下：實(shí)現(xiàn)i個(gè)訂單在m臺(tái)機(jī)器上并行調(diào)度，其中涉及訂單拆分情況。排產(chǎn)調(diào)度要做的是：（1） 根據(jù)產(chǎn)品的最大生產(chǎn)容量將i個(gè)訂單分割為各子訂單即要排產(chǎn)的任務(wù)。（2） 把各子訂單安排到m臺(tái)機(jī)器上生產(chǎn)并確定產(chǎn)線上子訂單的生產(chǎn)順序和生產(chǎn)時(shí)間；調(diào)度的目標(biāo)是使得所有訂單能夠在交貨

期附近結(jié)束生產(chǎn)，使得批生產(chǎn)、庫(kù)存成本、延期懲罰費(fèi)用最小。生產(chǎn)計(jì)劃流程圖如圖1 所示：

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

對(duì)多產(chǎn)品批處理的多機(jī)并行調(diào)度問(wèn)題作如下假設(shè)：

（1） 每個(gè)訂單只包含一種產(chǎn)品，并指定交貨期、生產(chǎn)數(shù)量；

（2） 每種產(chǎn)品可以在多臺(tái)機(jī)器上生產(chǎn)；

（3） 生產(chǎn)中不允許出現(xiàn)中斷；

（4） 每一次生產(chǎn)都以最大容量生產(chǎn)，不夠最大容量仍組織一次生產(chǎn)；

（5） 產(chǎn)品在機(jī)器上的批處理時(shí)間依產(chǎn)品種類(lèi)不同；

（6） 產(chǎn)品之間的轉(zhuǎn)換時(shí)間依產(chǎn)品種類(lèi)不同，不同產(chǎn)線上相同轉(zhuǎn)換順序的轉(zhuǎn)換時(shí)間相同。

該模型中使用的符號(hào)索引、決策變量及參數(shù)如表1 所示：

表1 變量參數(shù)定義

問(wèn)題的數(shù)學(xué)模型為：

式（1） 是計(jì)劃排產(chǎn)的目標(biāo)，表達(dá)式中依次為批生產(chǎn)費(fèi)用、延期懲罰費(fèi)用、生產(chǎn)庫(kù)存懲罰，其中庫(kù)存費(fèi)用與單位庫(kù)存成本及庫(kù)存時(shí)間成正比，而延期費(fèi)用與訂單的生產(chǎn)數(shù)量成正比。表達(dá)式中的完成時(shí)間Cik與決策變量關(guān)系為式（2）表示分割后的每個(gè)子訂單智能安排在一條產(chǎn)線上約束；式（3） 表示任務(wù)間加工順序約束，前驅(qū)任務(wù)完工后才能開(kāi)始后繼任務(wù)；式（4） 表示訂單的分割子訂單的開(kāi)始時(shí)間與完成時(shí)間之間的約束關(guān)系。

3 遺傳算法優(yōu)化求解

本文調(diào)度借鑒一般調(diào)度問(wèn)題的解決工具遺傳算法，利用遺傳算法能同時(shí)使用多個(gè)搜索點(diǎn)，有能力在各種調(diào)度方案之間進(jìn)行選擇交叉和變異等運(yùn)算，可以跳出局部最優(yōu)的陷阱，使解集性能不斷得到優(yōu)化。但本文求解過(guò)程不似一般調(diào)度問(wèn)題，存在區(qū)別為：調(diào)度任務(wù)間不是相互獨(dú)立的。一般調(diào)度問(wèn)題中各任務(wù)間相互獨(dú)立，在使用遺傳算法確定其生產(chǎn)順序后，采用線性規(guī)劃方法即可求解；但本文中調(diào)度任務(wù)間并不完全獨(dú)立，存在多個(gè)任務(wù)來(lái)自同一訂單情況，而目標(biāo)函數(shù)中庫(kù)存、延期懲罰分別與任務(wù)以及訂單相關(guān)，兩者之間有關(guān)聯(lián)，采用線性規(guī)劃問(wèn)題不能得以解決，故在采用遺傳算法優(yōu)化任務(wù)的排序順序后嵌套遺傳算法確定優(yōu)化排產(chǎn)順序下的各任務(wù)開(kāi)始生產(chǎn)時(shí)間使得生產(chǎn)、庫(kù)存、延期懲罰費(fèi)用最小。其算法流程如圖2 所示。

（1） 個(gè)體編碼

外層遺傳算法求解任務(wù)的機(jī)臺(tái)號(hào)及其順序，采用向量組的編碼方法，任務(wù)k在產(chǎn)線m上加工，則位基因表示為個(gè)體基因則為其中第一行為隨機(jī)排列的任務(wù)，第二行為任務(wù)的產(chǎn)線編號(hào)，任務(wù)間的加工順序則遵循在基因第一行中的排列順序。

內(nèi)層遺傳算法求解各任務(wù)開(kāi)始加工時(shí)間，采用一般向量編碼方法，任務(wù)單k開(kāi)始加工的時(shí)間Sk，則個(gè)體基因?yàn)?/p>

（2） 適應(yīng)度函數(shù)的選取

（3） 選 擇

兩層遺傳算法均選取最優(yōu)保存策略為選擇機(jī)制，保證適應(yīng)性好的個(gè)體保留到下一代中。

（4） 交 叉

外層遺傳算法中向量組基因若采用傳統(tǒng)的交叉方法，可能會(huì)產(chǎn)生任務(wù)加工產(chǎn)線不滿足約束條件的不合法個(gè)體，基于此外層采用EOX 交叉法：在交叉操作的兩父代個(gè)體（A、B） 中選擇父代個(gè)體（A），隨機(jī)取其中的一段基因串（S），將B中的第一行元素與S的第一行元素進(jìn)行比較，如果存在相同的則從B中刪除掉對(duì)應(yīng)元素的基因，將S插入到B中被刪除掉的基因第一行元素中與S中第一行第一個(gè)元素相同的地方，形成新的個(gè)體。依上述交叉過(guò)程反過(guò)來(lái)即可產(chǎn)生另一新個(gè)體。

內(nèi)層遺傳算法中的位基因涉及浮點(diǎn)數(shù)，采用中間交叉即子個(gè)體i=父?jìng)€(gè)體Ai+F× （父?jìng)€(gè)體Bi-父?jìng)€(gè)體Ai），直至交叉產(chǎn)生滿足時(shí)間約束關(guān)系的個(gè)體。

（5） 變 異

外層算法中的個(gè)體基因包含任務(wù)加工產(chǎn)線及其順序，變異時(shí)要考慮任務(wù)加工產(chǎn)線以及任務(wù)加工順序變異，采用單點(diǎn)變異（改變?nèi)蝿?wù)的加工產(chǎn)線） 及交換變異（改變?nèi)蝿?wù)的加工順序） 相結(jié)合的方法保證變異的多樣性。

內(nèi)層算法中根據(jù)任務(wù)的加工順序計(jì)算其開(kāi)始加工時(shí)間范圍，在此范圍內(nèi)對(duì)開(kāi)始加工時(shí)間變異。

（6） 終止條件

設(shè)定循環(huán)最大次數(shù)。

4 實(shí)驗(yàn)結(jié)果分析比較

上述數(shù)學(xué)模型中目標(biāo)函數(shù)考慮了庫(kù)存、拖期懲罰以及生產(chǎn)啟動(dòng)三種費(fèi)用，將該模型與目標(biāo)中只考慮其中一項(xiàng)比較，研究不同費(fèi)用目標(biāo)對(duì)調(diào)度結(jié)果以及各項(xiàng)性能指標(biāo)改變，本文主要考慮目標(biāo)中只有拖期懲罰費(fèi)用。為了方便，簡(jiǎn)記兩種模型目標(biāo)為：考慮三種費(fèi)用記為費(fèi)用和模型，只考慮拖期懲罰記為拖期模型。

采用Balakrishnan N[10]中參數(shù)設(shè)置規(guī)則設(shè)置實(shí)驗(yàn)數(shù)據(jù)：生產(chǎn)啟動(dòng)費(fèi)用滿足U[0,5 0 ]；產(chǎn)品間的轉(zhuǎn)換時(shí)間滿足U[25,75 ]；產(chǎn)品生產(chǎn)批量及批處理時(shí)間均滿足N（100,100）；產(chǎn)品的庫(kù)存成本及拖期懲罰滿足U[0,4]、U[0,6]；訂單中產(chǎn)品生產(chǎn)數(shù)量滿足U[0,N]，其中N=批次容量*產(chǎn)線數(shù)；訂單截止期則滿足U[1.2*processtime,3*processtime]，其中processtime是產(chǎn)品的批處理時(shí)間。

參數(shù)設(shè)置完后，比較不同模型中三種費(fèi)用及各項(xiàng)性能指標(biāo)，然后改變拖期懲罰系數(shù)進(jìn)行相同實(shí)驗(yàn)。不同模型的三種費(fèi)用結(jié)果如表2、表3 所示：

表2 拖期模型的各項(xiàng)費(fèi)用數(shù)據(jù)

表3 費(fèi)用和模型的各項(xiàng)費(fèi)用數(shù)據(jù)

不同模型的各項(xiàng)性能指標(biāo)結(jié)果如表4、表5 所示。

表4 拖期模型的各項(xiàng)性能指標(biāo)

表5 費(fèi)用和模型的各項(xiàng)性能指標(biāo)

通過(guò)表4、表5 的數(shù)據(jù)對(duì)比可知，相同懲罰系數(shù)下拖期模型的延遲訂單數(shù)小于費(fèi)用和模型，訂單最大完成時(shí)間、最大拖期時(shí)間均小但是最大在庫(kù)時(shí)間大，因?yàn)橥掀谀Ｐ椭豢紤]拖期費(fèi)用要求訂單盡量不延期，任務(wù)調(diào)度時(shí)任務(wù)間的時(shí)間間隙會(huì)減小，相應(yīng)訂單延遲數(shù)、最大完成時(shí)間、最大拖期時(shí)間均小，但會(huì)形成大量成品的在庫(kù)積壓，犧牲在制品庫(kù)存積壓縮減訂單延期；且隨著懲罰系數(shù)增大，延遲訂單數(shù)、最大完成時(shí)間、最大拖期時(shí)間減小、最大庫(kù)存時(shí)間增大，因?yàn)殡S著懲罰系數(shù)增大，懲罰費(fèi)用在總費(fèi)用中占的比例逐漸增大，這要求排產(chǎn)時(shí)訂單不延期，任務(wù)間的時(shí)隙會(huì)漸漸變小直至為0，成品的在庫(kù)時(shí)間也會(huì)增大。特別說(shuō)明，表3 中延遲訂單數(shù)并沒(méi)有明顯變化因?yàn)橛唵瘟縉=6 情況下各訂單間截止日期比較相近，在最小化拖期懲罰下排產(chǎn)會(huì)造成較多的訂單延遲且變化不大；表4 中延遲訂單數(shù)變化比較明顯因?yàn)橛唵蜰=9 情況下訂單間截止期有比較大的差距，隨著懲罰系數(shù)增大，提前生產(chǎn)的訂單數(shù)量會(huì)增大延遲的訂單數(shù)就會(huì)逐漸減少。

不同訂單量，不同拖期懲罰系數(shù)下各費(fèi)用如圖3、圖4 所示。

由圖3、圖4 可知，不同懲罰系數(shù)下，拖期模型的拖期懲罰費(fèi)用小于費(fèi)用和模型，但是庫(kù)存費(fèi)用、總費(fèi)用均大，因?yàn)橥掀谀Ｐ椭豢紤]拖期費(fèi)用要求訂單盡量不延期但是允許提前生產(chǎn)存在，對(duì)比下會(huì)造成更多的庫(kù)存費(fèi)用，拖期模型是通過(guò)增大庫(kù)存費(fèi)用來(lái)減少懲罰費(fèi)用，又由于懲罰費(fèi)用小時(shí)庫(kù)存費(fèi)用在總費(fèi)用占有較大比例會(huì)造成最終總費(fèi)用增大；且隨著懲罰系數(shù)的增大，不同目標(biāo)下費(fèi)用之間的差距減小，因?yàn)殡S著懲罰系數(shù)的增大，懲罰費(fèi)用在總費(fèi)用中占的比例逐漸增大。相比只考慮拖期費(fèi)用，準(zhǔn)時(shí)化生產(chǎn)的費(fèi)用和模型為企業(yè)提供良好的選擇。

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

針對(duì)多產(chǎn)品生產(chǎn)調(diào)度問(wèn)題，結(jié)合準(zhǔn)時(shí)化生產(chǎn)理念，提出了一種混合整數(shù)數(shù)學(xué)模型，模型中考慮批量生產(chǎn)約束、生產(chǎn)啟動(dòng)時(shí)間以及多機(jī)并行等實(shí)際問(wèn)題。比較不同拖期懲罰系數(shù)及不同目標(biāo)下的各項(xiàng)性能指標(biāo)。通過(guò)實(shí)驗(yàn)對(duì)比數(shù)據(jù)，考慮提前/拖期懲罰費(fèi)用、生產(chǎn)啟動(dòng)費(fèi)用之和優(yōu)于只考慮拖期懲罰，從利潤(rùn)角度出發(fā)為企業(yè)提供一個(gè)良好的解決方案，且為不同指標(biāo)需求提供選擇。進(jìn)一步的研究可考慮結(jié)合啟發(fā)式規(guī)則排產(chǎn)縮短計(jì)算時(shí)間。

[1] 宋毅. 基于遺傳算法的生產(chǎn)調(diào)度方法及其軟件實(shí)現(xiàn)[D]. 杭州：浙江工業(yè)大學(xué)（碩士學(xué)位論文），2003.

[2] Held M, Karp R M. A dynamic programming approach to sequencing problems[J]. Journal of the Society for Industrial &Applied Mathematics, 1962,10(1):196-210.

[3] Bagchi U, Sullivan R S, Chang Y L. Minimizing mean squared deviation of completion times about a common due date[J].Management Science, 1987,33(7):894-906.

[4] De P, Ghosh J B, Wells C E. Scheduling to minimize weighted earliness and tardiness about a common due-date[J]. Computers & operations research, 1991,18(5):465-475.

[5] COLEMAN B. TECHNICAL NOTE: A SIMPLE MODEL FOR OPTIMIZING THE SINGLE MACHINE EARLY/TARDY PROBLEM WITH SEQUENCE-DEPENDENT SETUPS[J]. Production and Operations Management, 1992,1(2):225-228.

[6] Fry T D, Armstrong R D, Blackstone J H. Minimizing weighted absolute deviation in single machine scheduling[J]. IIE transactions, 1987,19(4):445-450.

[7] Garey M R, Tarjan R E, Wilfong G T. One-processor scheduling with symmetric earliness and tardiness penalties[J]. Mathematics of Operations Research, 1988,13(2):330-348.

[8] Yano C A, Kim Y D. Algorithms for a class of single-machine weighted tardiness and earliness problems[J]. European Journal of Operational Research, 1991,52(2):167-178.

[9] Cheng T C E, Chen Z L. Parallel-machine scheduling problems with earliness and tardiness penalties[J]. Journal of the Operational Research Society, 1994(5):685-695.

[10] Balakrishnan N, Kanet J J, Sridharan V. Early/tardy scheduling with sequence dependent setups on uniform parallel machines[J]. Computers and Operations Research, 1999,26(2):127-141.