多產品批處理的多機并行調度問題研究

馮夢華，謝 勇 FENG Meng-hua, XIE Yong

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

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

0 引 言

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

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

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

1 問題描述

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

期附近結束生產，使得批生產、庫存成本、延期懲罰費用最小。生產計劃流程圖如圖1 所示：

2 數(shù)學模型

對多產品批處理的多機并行調度問題作如下假設：

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

（2） 每種產品可以在多臺機器上生產；

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

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

（5） 產品在機器上的批處理時間依產品種類不同；

（6） 產品之間的轉換時間依產品種類不同，不同產線上相同轉換順序的轉換時間相同。

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

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

問題的數(shù)學模型為：

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

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

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

（1） 個體編碼

外層遺傳算法求解任務的機臺號及其順序，采用向量組的編碼方法，任務k在產線m上加工，則位基因表示為個體基因則為其中第一行為隨機排列的任務，第二行為任務的產線編號，任務間的加工順序則遵循在基因第一行中的排列順序。

內層遺傳算法求解各任務開始加工時間，采用一般向量編碼方法，任務單k開始加工的時間Sk，則個體基因為

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

（3） 選 擇

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

（4） 交 叉

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

內層遺傳算法中的位基因涉及浮點數(shù)，采用中間交叉即子個體i=父個體Ai+F× （父個體Bi-父個體Ai），直至交叉產生滿足時間約束關系的個體。

（5） 變 異

外層算法中的個體基因包含任務加工產線及其順序，變異時要考慮任務加工產線以及任務加工順序變異，采用單點變異（改變任務的加工產線） 及交換變異（改變任務的加工順序） 相結合的方法保證變異的多樣性。

內層算法中根據(jù)任務的加工順序計算其開始加工時間范圍，在此范圍內對開始加工時間變異。

（6） 終止條件

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

4 實驗結果分析比較

上述數(shù)學模型中目標函數(shù)考慮了庫存、拖期懲罰以及生產啟動三種費用，將該模型與目標中只考慮其中一項比較，研究不同費用目標對調度結果以及各項性能指標改變，本文主要考慮目標中只有拖期懲罰費用。為了方便，簡記兩種模型目標為：考慮三種費用記為費用和模型，只考慮拖期懲罰記為拖期模型。

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

參數(shù)設置完后，比較不同模型中三種費用及各項性能指標，然后改變拖期懲罰系數(shù)進行相同實驗。不同模型的三種費用結果如表2、表3 所示：

表2 拖期模型的各項費用數(shù)據(jù)

表3 費用和模型的各項費用數(shù)據(jù)

不同模型的各項性能指標結果如表4、表5 所示。

表4 拖期模型的各項性能指標

表5 費用和模型的各項性能指標

通過表4、表5 的數(shù)據(jù)對比可知，相同懲罰系數(shù)下拖期模型的延遲訂單數(shù)小于費用和模型，訂單最大完成時間、最大拖期時間均小但是最大在庫時間大，因為拖期模型只考慮拖期費用要求訂單盡量不延期，任務調度時任務間的時間間隙會減小，相應訂單延遲數(shù)、最大完成時間、最大拖期時間均小，但會形成大量成品的在庫積壓，犧牲在制品庫存積壓縮減訂單延期；且隨著懲罰系數(shù)增大，延遲訂單數(shù)、最大完成時間、最大拖期時間減小、最大庫存時間增大，因為隨著懲罰系數(shù)增大，懲罰費用在總費用中占的比例逐漸增大，這要求排產時訂單不延期，任務間的時隙會漸漸變小直至為0，成品的在庫時間也會增大。特別說明，表3 中延遲訂單數(shù)并沒有明顯變化因為訂單量N=6 情況下各訂單間截止日期比較相近，在最小化拖期懲罰下排產會造成較多的訂單延遲且變化不大；表4 中延遲訂單數(shù)變化比較明顯因為訂單N=9 情況下訂單間截止期有比較大的差距，隨著懲罰系數(shù)增大，提前生產的訂單數(shù)量會增大延遲的訂單數(shù)就會逐漸減少。

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

由圖3、圖4 可知，不同懲罰系數(shù)下，拖期模型的拖期懲罰費用小于費用和模型，但是庫存費用、總費用均大，因為拖期模型只考慮拖期費用要求訂單盡量不延期但是允許提前生產存在，對比下會造成更多的庫存費用，拖期模型是通過增大庫存費用來減少懲罰費用，又由于懲罰費用小時庫存費用在總費用占有較大比例會造成最終總費用增大；且隨著懲罰系數(shù)的增大，不同目標下費用之間的差距減小，因為隨著懲罰系數(shù)的增大，懲罰費用在總費用中占的比例逐漸增大。相比只考慮拖期費用，準時化生產的費用和模型為企業(yè)提供良好的選擇。

5 結束語

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

[1] 宋毅. 基于遺傳算法的生產調度方法及其軟件實現(xiàn)[D]. 杭州：浙江工業(yè)大學（碩士學位論文），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.