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

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

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

0 引 言

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1） 個體編碼

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

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

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

（3） 選 擇

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

（4） 交 叉

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

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

（5） 變 異

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

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

（6） 終止條件

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

4 實驗結(jié)果分析比較

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

采用Balakrishnan N[10]中參數(shù)設(shè)置規(guī)則設(shè)置實驗數(shù)據(jù)：生產(chǎn)啟動費用滿足U[0,5 0 ]；產(chǎn)品間的轉(zhuǎn)換時間滿足U[25,75 ]；產(chǎn)品生產(chǎn)批量及批處理時間均滿足N（100,100）；產(chǎn)品的庫存成本及拖期懲罰滿足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è)置完后，比較不同模型中三種費用及各項性能指標(biāo)，然后改變拖期懲罰系數(shù)進行相同實驗。不同模型的三種費用結(jié)果如表2、表3 所示：

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

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

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

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

表5 費用和模型的各項性能指標(biāo)

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

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

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

5 結(jié)束語

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

[1] 宋毅. 基于遺傳算法的生產(chǎn)調(diào)度方法及其軟件實現(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.