馮夢華,謝 勇 FENG Meng-hua, XIE Yong
(華中科技大學(xué) 系統(tǒng)工程研究所,湖北 武漢430074)
(Institute of Systems Engineering, Huazhong University of Science & Technology, Wuhan 430074, China)
生產(chǎn)計(jì)劃與調(diào)度問題是制造企業(yè)最基礎(chǔ)也最核心的問題,是在滿足某些約束條件(如有限生產(chǎn)能力及資源、任務(wù)釋放時(shí)間和截止期等) 下對任務(wù)進(jìn)行合理排序,并安排各個(gè)任務(wù)開工時(shí)間,最終實(shí)現(xiàn)企業(yè)一個(gè)或多個(gè)目標(biāo)的最優(yōu)化。實(shí)際中對調(diào)度的評價(jià)大致可歸為三類:最大能力指標(biāo)、成本指標(biāo)、客戶滿意度指標(biāo)[1],其中最大能力指標(biāo)大多應(yīng)用在需求固定或需求無上限的情況下,傳統(tǒng)生產(chǎn)調(diào)度應(yīng)用較多,但實(shí)際卻是提前完成生產(chǎn)的成品需入成品倉庫需要支付一筆不小的倉儲費(fèi)用,延期生產(chǎn)產(chǎn)品則會有損企業(yè)聲譽(yù),同時(shí)企業(yè)還需支付違約金,因此實(shí)際中更多的綜合考慮庫存成本以及延期懲罰費(fèi)用。
考慮庫存成本、延期懲罰生產(chǎn)調(diào)度問題的核心是準(zhǔn)時(shí)化生產(chǎn)。專家學(xué)者對其進(jìn)行大量研究:Held[2]和Bagchi U[3]研究了單機(jī)環(huán)境下的提前、拖期調(diào)度問題;Prabuddha De[4]探討了單機(jī)調(diào)度完成時(shí)間偏差最小化問題,調(diào)度中考慮了不同任務(wù)的加權(quán)系數(shù)情況;Coleman[5]針對考慮任務(wù)準(zhǔn)備時(shí)間與加工順序相關(guān)這一實(shí)際情況研究單機(jī)調(diào)度問題;Fry and Armstrong[6],Garey and Tarjan[7]和Yano and Kim[8]研究了給定排序下的開工時(shí)間優(yōu)化問題,但對懲罰權(quán)重有一定的限制;Cheng T C E[9]討論了互不相關(guān)的任務(wù)在多機(jī)的并行調(diào)度問題,闡述流程時(shí)間加成本最小、提前拖期懲罰費(fèi)用最小兩個(gè)問題。
多機(jī)并行調(diào)度問題雖得到一定研究,但調(diào)度的任務(wù)間大多是無關(guān)的,然實(shí)際中會由于生產(chǎn)容量限制需要將訂單拆分為加工任務(wù),這些任務(wù)間實(shí)際上存在一定關(guān)系的,這對調(diào)度有一定的影響。本文以某酒企業(yè)生產(chǎn)為研究背景,研究已知交貨期的訂單在生產(chǎn)容量限制分割為子訂單后的多機(jī)并行調(diào)度問題,盡量實(shí)現(xiàn)各訂單的準(zhǔn)時(shí)化生產(chǎn)。
本文研究的酒生產(chǎn)調(diào)度是在一般車間調(diào)度問題上簡化的,不考慮具體的工藝路線,整套的工藝路線在一臺機(jī)器上即可生產(chǎn)完;其中加入了生產(chǎn)中容量限制這一約束,在可能情況下都以最大容量組織生產(chǎn),最后不夠最大容量的人任為一批組織生產(chǎn),這就要求先要對生產(chǎn)訂單進(jìn)行分割,在此基礎(chǔ)上進(jìn)行調(diào)度。本文的計(jì)劃排程描述如下:實(shí)現(xiàn)i個(gè)訂單在m臺機(jī)器上并行調(diào)度,其中涉及訂單拆分情況。排產(chǎn)調(diào)度要做的是:(1) 根據(jù)產(chǎn)品的最大生產(chǎn)容量將i個(gè)訂單分割為各子訂單即要排產(chǎn)的任務(wù)。(2) 把各子訂單安排到m臺機(jī)器上生產(chǎn)并確定產(chǎn)線上子訂單的生產(chǎn)順序和生產(chǎn)時(shí)間;調(diào)度的目標(biāo)是使得所有訂單能夠在交貨
期附近結(jié)束生產(chǎn),使得批生產(chǎn)、庫存成本、延期懲罰費(fèi)用最小。生產(chǎn)計(jì)劃流程圖如圖1 所示:
對多產(chǎn)品批處理的多機(jī)并行調(diào)度問題作如下假設(shè):
(1) 每個(gè)訂單只包含一種產(chǎn)品,并指定交貨期、生產(chǎn)數(shù)量;
(2) 每種產(chǎn)品可以在多臺機(jī)器上生產(chǎn);
(3) 生產(chǎn)中不允許出現(xiàn)中斷;
(4) 每一次生產(chǎn)都以最大容量生產(chǎn),不夠最大容量仍組織一次生產(chǎn);
(5) 產(chǎn)品在機(jī)器上的批處理時(shí)間依產(chǎn)品種類不同;
(6) 產(chǎn)品之間的轉(zhuǎn)換時(shí)間依產(chǎn)品種類不同,不同產(chǎn)線上相同轉(zhuǎn)換順序的轉(zhuǎn)換時(shí)間相同。
該模型中使用的符號索引、決策變量及參數(shù)如表1 所示:
表1 變量參數(shù)定義
問題的數(shù)學(xué)模型為:
式(1) 是計(jì)劃排產(chǎn)的目標(biāo),表達(dá)式中依次為批生產(chǎn)費(fèi)用、延期懲罰費(fèi)用、生產(chǎn)庫存懲罰,其中庫存費(fèi)用與單位庫存成本及庫存時(shí)間成正比,而延期費(fèi)用與訂單的生產(chǎn)數(shù)量成正比。表達(dá)式中的完成時(shí)間Cik與決策變量關(guān)系為式(2)表示分割后的每個(gè)子訂單智能安排在一條產(chǎn)線上約束;式(3) 表示任務(wù)間加工順序約束,前驅(qū)任務(wù)完工后才能開始后繼任務(wù);式(4) 表示訂單的分割子訂單的開始時(shí)間與完成時(shí)間之間的約束關(guān)系。
本文調(diào)度借鑒一般調(diào)度問題的解決工具遺傳算法,利用遺傳算法能同時(shí)使用多個(gè)搜索點(diǎn),有能力在各種調(diào)度方案之間進(jìn)行選擇交叉和變異等運(yùn)算,可以跳出局部最優(yōu)的陷阱,使解集性能不斷得到優(yōu)化。但本文求解過程不似一般調(diào)度問題,存在區(qū)別為:調(diào)度任務(wù)間不是相互獨(dú)立的。一般調(diào)度問題中各任務(wù)間相互獨(dú)立,在使用遺傳算法確定其生產(chǎn)順序后,采用線性規(guī)劃方法即可求解;但本文中調(diào)度任務(wù)間并不完全獨(dú)立,存在多個(gè)任務(wù)來自同一訂單情況,而目標(biāo)函數(shù)中庫存、延期懲罰分別與任務(wù)以及訂單相關(guān),兩者之間有關(guān)聯(lián),采用線性規(guī)劃問題不能得以解決,故在采用遺傳算法優(yōu)化任務(wù)的排序順序后嵌套遺傳算法確定優(yōu)化排產(chǎn)順序下的各任務(wù)開始生產(chǎn)時(shí)間使得生產(chǎn)、庫存、延期懲罰費(fèi)用最小。其算法流程如圖2 所示。
(1) 個(gè)體編碼
外層遺傳算法求解任務(wù)的機(jī)臺號及其順序,采用向量組的編碼方法,任務(wù)k在產(chǎn)線m上加工,則位基因表示為個(gè)體基因則為其中第一行為隨機(jī)排列的任務(wù),第二行為任務(wù)的產(chǎn)線編號,任務(wù)間的加工順序則遵循在基因第一行中的排列順序。
內(nèi)層遺傳算法求解各任務(wù)開始加工時(shí)間,采用一般向量編碼方法,任務(wù)單k開始加工的時(shí)間Sk,則個(gè)體基因?yàn)?/p>
(2) 適應(yīng)度函數(shù)的選取
(3) 選 擇
兩層遺傳算法均選取最優(yōu)保存策略為選擇機(jī)制,保證適應(yīng)性好的個(gè)體保留到下一代中。
(4) 交 叉
外層遺傳算法中向量組基因若采用傳統(tǒng)的交叉方法,可能會產(chǎn)生任務(wù)加工產(chǎn)線不滿足約束條件的不合法個(gè)體,基于此外層采用EOX 交叉法:在交叉操作的兩父代個(gè)體(A、B) 中選擇父代個(gè)體(A),隨機(jī)取其中的一段基因串(S),將B中的第一行元素與S的第一行元素進(jìn)行比較,如果存在相同的則從B中刪除掉對應(yīng)元素的基因,將S插入到B中被刪除掉的基因第一行元素中與S中第一行第一個(gè)元素相同的地方,形成新的個(gè)體。依上述交叉過程反過來即可產(chǎn)生另一新個(gè)體。
內(nèi)層遺傳算法中的位基因涉及浮點(diǎn)數(shù),采用中間交叉即子個(gè)體i=父個(gè)體Ai+F× (父個(gè)體Bi-父個(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ì)算其開始加工時(shí)間范圍,在此范圍內(nèi)對開始加工時(shí)間變異。
(6) 終止條件
設(shè)定循環(huán)最大次數(shù)。
上述數(shù)學(xué)模型中目標(biāo)函數(shù)考慮了庫存、拖期懲罰以及生產(chǎn)啟動三種費(fèi)用,將該模型與目標(biāo)中只考慮其中一項(xiàng)比較,研究不同費(fèi)用目標(biāo)對調(diào)度結(jié)果以及各項(xiàng)性能指標(biāo)改變,本文主要考慮目標(biāo)中只有拖期懲罰費(fèi)用。為了方便,簡記兩種模型目標(biāo)為:考慮三種費(fèi)用記為費(fèi)用和模型,只考慮拖期懲罰記為拖期模型。
采用Balakrishnan N[10]中參數(shù)設(shè)置規(guī)則設(shè)置實(shí)驗(yàn)數(shù)據(jù):生產(chǎn)啟動費(fèi)用滿足U[0,5 0 ];產(chǎn)品間的轉(zhuǎn)換時(shí)間滿足U[25,75 ];產(chǎn)品生產(chǎn)批量及批處理時(shí)間均滿足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ù)設(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)
通過表4、表5 的數(shù)據(jù)對比可知,相同懲罰系數(shù)下拖期模型的延遲訂單數(shù)小于費(fèi)用和模型,訂單最大完成時(shí)間、最大拖期時(shí)間均小但是最大在庫時(shí)間大,因?yàn)橥掀谀P椭豢紤]拖期費(fèi)用要求訂單盡量不延期,任務(wù)調(diào)度時(shí)任務(wù)間的時(shí)間間隙會減小,相應(yīng)訂單延遲數(shù)、最大完成時(shí)間、最大拖期時(shí)間均小,但會形成大量成品的在庫積壓,犧牲在制品庫存積壓縮減訂單延期;且隨著懲罰系數(shù)增大,延遲訂單數(shù)、最大完成時(shí)間、最大拖期時(shí)間減小、最大庫存時(shí)間增大,因?yàn)殡S著懲罰系數(shù)增大,懲罰費(fèi)用在總費(fèi)用中占的比例逐漸增大,這要求排產(chǎn)時(shí)訂單不延期,任務(wù)間的時(shí)隙會漸漸變小直至為0,成品的在庫時(shí)間也會增大。特別說明,表3 中延遲訂單數(shù)并沒有明顯變化因?yàn)橛唵瘟縉=6 情況下各訂單間截止日期比較相近,在最小化拖期懲罰下排產(chǎn)會造成較多的訂單延遲且變化不大;表4 中延遲訂單數(shù)變化比較明顯因?yàn)橛唵蜰=9 情況下訂單間截止期有比較大的差距,隨著懲罰系數(shù)增大,提前生產(chǎn)的訂單數(shù)量會增大延遲的訂單數(shù)就會逐漸減少。
不同訂單量,不同拖期懲罰系數(shù)下各費(fèi)用如圖3、圖4 所示。
由圖3、圖4 可知,不同懲罰系數(shù)下,拖期模型的拖期懲罰費(fèi)用小于費(fèi)用和模型,但是庫存費(fèi)用、總費(fèi)用均大,因?yàn)橥掀谀P椭豢紤]拖期費(fèi)用要求訂單盡量不延期但是允許提前生產(chǎn)存在,對比下會造成更多的庫存費(fèi)用,拖期模型是通過增大庫存費(fèi)用來減少懲罰費(fèi)用,又由于懲罰費(fèi)用小時(shí)庫存費(fèi)用在總費(fèi)用占有較大比例會造成最終總費(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è)提供良好的選擇。
針對多產(chǎn)品生產(chǎn)調(diào)度問題,結(jié)合準(zhǔn)時(shí)化生產(chǎn)理念,提出了一種混合整數(shù)數(shù)學(xué)模型,模型中考慮批量生產(chǎn)約束、生產(chǎn)啟動時(shí)間以及多機(jī)并行等實(shí)際問題。比較不同拖期懲罰系數(shù)及不同目標(biāo)下的各項(xiàng)性能指標(biāo)。通過實(shí)驗(yàn)對比數(shù)據(jù),考慮提前/拖期懲罰費(fèi)用、生產(chǎn)啟動費(fèi)用之和優(yōu)于只考慮拖期懲罰,從利潤角度出發(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.