含批量加工設(shè)備的木門流水車間排產(chǎn)方案

裴 植, 杜 蕊, 方 濤, 李英德

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院,浙江 杭州 310023)

1 問題的提出

隨著木制家具市場競爭的日益激烈,大部分實(shí)木復(fù)合門生產(chǎn)企業(yè)逐漸意識到數(shù)字化制造、科學(xué)排產(chǎn)方案的重要性。通過實(shí)施計(jì)算機(jī)集成制造系統(tǒng)與高效排產(chǎn)算法,可顯著降低生產(chǎn)過程浪費(fèi)和訂單交付延遲,最終提升整體制造系統(tǒng)的效能并有效保證準(zhǔn)時化生產(chǎn)(Just in Time, JIT)。高效木制家具生產(chǎn)系統(tǒng)的突出特點(diǎn)是采用拉式生產(chǎn),即生產(chǎn)節(jié)拍根據(jù)市場需求制訂,以后續(xù)工序的加工狀態(tài)拉動前續(xù)工序的生產(chǎn)制造,采用該方式組織生產(chǎn)可有效降低生產(chǎn)系統(tǒng)的在制品庫存,從而降低持有成本。

本文研究對象為某包含批量加工設(shè)備的實(shí)木復(fù)合門流水車間。在木門生產(chǎn)流程中,需要將多道木門放入熱壓機(jī)中進(jìn)行壓縮膠合作業(yè),如圖1a所示;膠合完成后,等待木門冷卻再進(jìn)行精修作業(yè),如圖1b所示。其中熱壓機(jī)成批膠合工序和木門冷卻的需求是延長實(shí)木復(fù)合門生產(chǎn)周期的重要因素。在本文研究的木門生產(chǎn)流水車間內(nèi),熱壓工序與精修工序間通常存在大量在制品庫存,因此第2階段的精修工序?yàn)樯a(chǎn)系統(tǒng)的瓶頸工序,即第2階段加工時所需的在制品總能得到滿足,不存在缺料情況。

受生產(chǎn)設(shè)備的產(chǎn)能數(shù)量的限制,需要對批量生產(chǎn)順序進(jìn)行合理安排的問題被稱為產(chǎn)能受限的批量問題(Capacitated Lot-Sizing Problem,CLSP),這一問題在制造業(yè)等領(lǐng)域一直備受關(guān)注。在準(zhǔn)時化制造中,企業(yè)高度重視安裝準(zhǔn)備時間(setup time)所占用的時間資源,減少安裝準(zhǔn)備時間可以縮短產(chǎn)品的制造周期,降低產(chǎn)品批量可以減少在制品庫存,然而面對更短的制造周期和更小的產(chǎn)品批量,由于單時段內(nèi)的總安裝準(zhǔn)備時間不可壓縮,導(dǎo)致制造系統(tǒng)的性能降低。TRIGEIRO等[1]證明了考慮安裝準(zhǔn)備時間的批量生產(chǎn)問題的復(fù)雜度為NP-complete,提出包含拉格朗日松弛(Lagrange relaxation)和將每時段加工時長平滑(smoothing procedure)的啟發(fā)式算法,通過該算法構(gòu)建可行解,可確保每個時段均不存在加班時間;BELVAUX等[2]介紹了分支切割算法(branch-and-cut)在批量生產(chǎn)問題中的應(yīng)用及其適用的具體問題;GUAN等[3]考慮無容量約束限制的不確定批量生產(chǎn)問題(Lot Sizing, LS),針對多階段隨機(jī)混合整數(shù)規(guī)劃模型,采用分支切割算法將該問題建模為多階段隨機(jī)混合整數(shù)線性規(guī)劃問題規(guī)劃模型,并設(shè)計(jì)了一種分支切割算法進(jìn)行求解;DEGRAEVE等[4]對CLSP采用Dantzig-Wolfe分解,再用分支定價 (branch-and-price) 算法得到原問題的整數(shù)解,并將分支定價算法的求解性能與TTM啟發(fā)式算法進(jìn)行了對比分析;PIMENTEL等[5]對CLSP采用3種不同的Dantzig-Wolfe分解方法,分別為對產(chǎn)品種類分解、對時段分解、結(jié)合產(chǎn)品種類分解與時段分解的方法;趙世雄等[6]考慮CLSP與預(yù)防性維護(hù)的集成優(yōu)化問題,對其非線性混合整數(shù)規(guī)劃模型設(shè)計(jì)了基于循環(huán)迭代的算法;ARAUJO等[7]對CLSP的時段進(jìn)行Dantzig-Wolfe分解,并提出數(shù)學(xué)轉(zhuǎn)換模型和有效不等式,以加快列生成和拉格朗日松弛過程;FRAGKOS等[8]考慮包含安裝準(zhǔn)備時間的CLSP,對其原數(shù)學(xué)模型先根據(jù)時段拆分,再用分支定價算法求解;DUYGU等[9]研究了安裝準(zhǔn)備時和加班時間為隨機(jī)數(shù)時的CLSP,并用兩種啟發(fā)式算法求解該問題;MOHAMMAD[10]考慮存在加班時間與延遲交貨的CLSP,用魯棒優(yōu)化方法處理需求的不確定性;WU等[11]分別考慮多平行機(jī)條件下的CLSP、設(shè)施規(guī)劃問題和最短路徑問題,用分支定價算法對不同問題進(jìn)行算例分析與對比。然而,上述文獻(xiàn)僅考慮了單個加工階段,且其加工工序?yàn)閱渭魉a(chǎn)制造模式,并不適用于成批加工工序。

近年來,出現(xiàn)了一些批量生產(chǎn)與其他領(lǐng)域結(jié)合的研究。COPIL等[12]綜述了批量生產(chǎn)與調(diào)度問題相結(jié)合的文獻(xiàn);MELEGA等[13]綜述了批量生產(chǎn)與下料問題(cutting stock)相結(jié)合的文獻(xiàn)綜述;DUARTE等[14]考慮單個加工工序多臺平行機(jī)的批量生產(chǎn)與調(diào)度相結(jié)合的問題,采用分支定價算法分別對3個不同的0-1決策變量進(jìn)行分支;HU等[15]和景熠等[16]在汽車制造行業(yè)考慮批量生產(chǎn)與調(diào)度相結(jié)合的問題,用情景樹矩量匹配技術(shù)表示需求的不確定性,用多階段隨機(jī)規(guī)劃模型對該問題進(jìn)行求解和數(shù)值算例分析;ARMAS等[17]將批量生產(chǎn)問題與調(diào)度問題結(jié)合,考慮多平行機(jī)環(huán)境下的絕緣導(dǎo)管行業(yè),采用數(shù)學(xué)規(guī)劃模型與后加工排序相結(jié)合的啟發(fā)式算法尋求生產(chǎn)計(jì)劃和加工順序;MELEGA等[18]將批量生產(chǎn)問題、調(diào)度問題和下料問題三者結(jié)合,考慮與排序相關(guān)的安裝準(zhǔn)備時間,用定價分支法(price-and-branch)進(jìn)行求解;陳豪韻[19]考慮產(chǎn)能受限的批量生產(chǎn)與調(diào)度問題,以及加工過程存在跨時段與制造延期的情形,直接用CPLEX求解器進(jìn)行求解。

通過文獻(xiàn)研究發(fā)現(xiàn),有關(guān)批量生產(chǎn)與訂單分批的研究均未涉及實(shí)木復(fù)合門或木制家具相關(guān)的制造行業(yè),其構(gòu)建的數(shù)學(xué)模型并不適用于當(dāng)前的木門家具生產(chǎn)車間。因此,本文著重考慮木門家具流水車間的實(shí)際情況,面向特殊加工階段的批量生產(chǎn)問題,根據(jù)拉式生產(chǎn)方式進(jìn)行訂單排產(chǎn)研究。該木門生產(chǎn)車間的排產(chǎn)規(guī)則為根據(jù)顧客需求訂單順序生產(chǎn),其中存在大量不必要的產(chǎn)品切換安裝準(zhǔn)備時間。當(dāng)車間以降低成品庫存為目標(biāo)時,可能將生產(chǎn)優(yōu)先級放在減少庫存上,而不是確保及時交付客戶訂單這種情況可能導(dǎo)致部分訂單的生產(chǎn)被推遲,從而降低客戶滿意度。面對隨時段波動的持有成本和制造成本,本文提出不應(yīng)只關(guān)注現(xiàn)有庫存量,而應(yīng)以總時段內(nèi)總成本的最小化為目標(biāo),即無需片面追求零成品庫存,在某些制造成本較低的時段,可多加工部分產(chǎn)品以滿足后續(xù)時段顧客的需求并避免延期交貨。本文針對該車間排產(chǎn)模型設(shè)計(jì)了優(yōu)化算法,為其提供了高效可行的排產(chǎn)方案,其中木門流水車間的第1個工序?yàn)闊釅簷C(jī)成批加工階段,第2個工序?yàn)榫迒渭魉鳂I(yè),將顧客訂單交付看作最終生產(chǎn)階段。通過構(gòu)建問題的優(yōu)化模型與精確求解算法,得到木門加工過程的訂單分批排產(chǎn)設(shè)計(jì)方案。

本文構(gòu)建該木門生產(chǎn)構(gòu)成的混合整數(shù)規(guī)劃模型,并給出符合該實(shí)木復(fù)合門生產(chǎn)車間實(shí)際環(huán)境與情況的假設(shè),將原問題拆分為兩階段子問題。算法設(shè)計(jì)根據(jù)拉式生產(chǎn)模式,首先對第2階段的子問題SS2進(jìn)行Dantzig-Wolfe分解,給出其對應(yīng)的定價子問題(Pricing Subproblem, PS);再采用分支定界與列生產(chǎn)相結(jié)合的分支定價算法求解得到SS2的最優(yōu)解;隨后根據(jù)第2階段的在制品數(shù)量求得第1階段的子問題SS1的最優(yōu)解;最后對該木門排產(chǎn)算法進(jìn)行實(shí)例分析和總結(jié)。

2 問題描述

本文考慮某實(shí)木復(fù)合門流水車間中的壓縮膠合與精修兩個加工階段,該車間能生產(chǎn)多種品類的實(shí)木復(fù)合門。根據(jù)拉式生產(chǎn)方式,第2階段的生產(chǎn)根據(jù)顧客需求進(jìn)行,并將在制品需求信息傳遞給第1階段。第1階段根據(jù)第2階段的在制品需求提前進(jìn)行制造,并保證其準(zhǔn)時化。對于木門的生產(chǎn)流程,先在第1階段的熱壓機(jī)成批膠合,完成后搬運(yùn)至第1階段的在制品貨架上暫存,等待冷卻。第2階段的工人接收到拉式生產(chǎn)信息后,前往該在制品暫存貨架將相應(yīng)數(shù)量的在制品木門搬運(yùn)到第2階段,再進(jìn)行逐個精修作業(yè)。假設(shè)該搬運(yùn)時間可以忽略不計(jì),或者直接計(jì)入第2階段的加工時間內(nèi)。木門在第1階段加工后的冷卻需求也正是這兩個階段無法使用傳送帶傳輸制造的重要原因,而且高溫的木門冷卻時間相對較長,不能在同一時段直接進(jìn)入第2階段精修,必須等待后一時段。因此,2.2節(jié)的數(shù)學(xué)模型中,第1階段的求解時段范圍為[0,T-1],第2階段的求解時段范圍為[1,T]。

因?yàn)槟鹃T的尺寸根據(jù)國家標(biāo)準(zhǔn)為統(tǒng)一長度和寬度,所以第1階段的熱壓機(jī)可以同時膠合不同種類的木門。熱壓機(jī)壓縮膠合一次的加工時間固定,與加工木門的數(shù)量和種類無關(guān),而木門的安裝準(zhǔn)備工作則與木門的數(shù)量和種類有關(guān),此處與單件流水加工工序不同。第2階段的精修工序?yàn)槠胀ǖ膯渭魉庸ぷ鳂I(yè),換模準(zhǔn)備工作與木門種類有關(guān),與數(shù)量無關(guān),加工工作與木門數(shù)量有關(guān)。精修完工后的木門存儲在第2階段的成品倉庫貨架上,以滿足不同時段的顧客需求。這兩個階段的生產(chǎn)如圖2所示,其目標(biāo)是得到一種根據(jù)顧客需求的批量生產(chǎn)方案,使制造成本與持有成本的總和最小化,即最終得到每個時段內(nèi),兩個階段需要生產(chǎn)的不同種類木門的數(shù)量。

2.1 符號說明

為了構(gòu)建木門流水車間批量生產(chǎn)問題的混合整數(shù)規(guī)劃問題,給出如表1所示的符號說明。

表1 數(shù)學(xué)符號說明

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

本文考慮的總時段t=0,1,2,…,T中,對第1階段的求解時段范圍為[0,T-1],對第2階段的求解時段范圍為[1,T];兩個加工階段的初始庫存均為0,即下文公式中第1階段的初始庫存S1,j,-1=0,第2階段的初始庫存S2,j,0=0;第1階段在成批加工前,工人將一批次的木門安裝到熱壓機(jī)上,因此安裝準(zhǔn)備成本sc1,j,t與木門數(shù)量有關(guān);第2階段在流水加工前加工不同的木門,機(jī)器需要進(jìn)行換模作業(yè),因此換模成本sc2,j,t與木門數(shù)量無關(guān);第2階段木門也由工人逐個搬運(yùn)到機(jī)器上,這一搬運(yùn)時間/成本可以計(jì)入加工時間vt2,j/加工成本vc2,j,t中。木門流水車間批量生產(chǎn)的混合整數(shù)規(guī)劃模型構(gòu)建如下:

(1)

s.t.

S1,j,t-1+x1,j,t=aj,t+S1,j,t,
?j∈N,t∈[0,T-1];

(2)

aj,t=x2,j,t+1,?j∈N,t∈[0,T-1];

(3)

(4)

(5)

(6)

S2,j,t-1+x2,j,t=dj,t+S2,j,t,

?j∈N,t∈[1,T];

(7)

(8)

x2,j,t≤(capt-st2,j)/vt2,j,

?j∈N,t∈[1,T];

(9)

(10)

Si,j,t,aj,t,xi,j,t,zt∈Z+,

?i∈I,j∈N,t∈[0,T];

(11)

yj,t∈,?j∈N,t∈[1,T]。

(12)

該混合整數(shù)規(guī)劃模型的建立參照了DEGRAEVE等[4]描述的批量生產(chǎn)問題CLSP,并將該CLSP模型延伸到含成批加工機(jī)器的兩階段模型,其中成批加工機(jī)器熱壓機(jī)受容量約束限制。目標(biāo)函數(shù)(1)為最小化兩個階段的持有成本和制造成本的總和。約束(2)～約束(6)限制了第1階段的批量加工。其中約束(2)為庫存、生產(chǎn)輸入和需求輸出的平衡約束,即第1階段在前一個時段末剩余的木門數(shù)量與該時段加工的木門數(shù)量之和,等于該時段剩余的木門數(shù)量與該時段末從第1階段搬運(yùn)到第2階段的木門數(shù)量之和;約束(3)表示第2階段在該時段的批量生產(chǎn)計(jì)劃,需要先在前一時段末將對應(yīng)的木門數(shù)量從第1階段搬運(yùn)到第2階段的操作臺前,再開始第2階段的加工工作,因此第2階段的加工數(shù)量等于搬運(yùn)數(shù)量;約束(4)限制了第1階段的生產(chǎn)量不能超過后續(xù)第2階段的需求數(shù)量;約束(5)中,若第1階段的熱壓機(jī)在該時段的加工次數(shù)為0則無法生產(chǎn),若加工次數(shù)大于0,則熱壓機(jī)每次加工最多能生產(chǎn)數(shù)量為W的木門;約束(6)為該時段內(nèi)第1階段熱壓機(jī)加工不同木門所消耗的總時間不能超過時段的時間限制,熱壓機(jī)的安裝準(zhǔn)備工作與木門的種類和數(shù)量有關(guān),為st1,jx1,j,t,加工膠合一個批次木門的加工時間與木門的種類和數(shù)量無關(guān),為vt1。約束(7)～約束(10)限制了第2階段的批量生產(chǎn)問題。其中約束(7)和約束(2)相似,為成品庫存平衡約束;約束(8)為第2階段的生產(chǎn)數(shù)量限制,生產(chǎn)數(shù)量不能超過后續(xù)階段的需求總和;約束(9)為生產(chǎn)能力限制,若該時段所有時間都用來生產(chǎn)第j種木門,則該木門生產(chǎn)數(shù)量不得超過該時段的時間容量所能生產(chǎn)的木門數(shù)量;約束(10)為時間限制,在該時段內(nèi)生產(chǎn)的所有品類木門的總用時不能超過時段的時間限制。約束(11)和約束(12)限制了該問題決策變量的取值范圍。

在CLSP中,約束(3)為維系SS1和SS2的鏈接約束,則第1階段子問題SS1可以表示為:

s.t.

式(2),式(4)～式(6);

S1,j,t,x1,j,t,zt∈Z+,?j∈N,t∈[0,T-1]。

第2階段子問題SS2可以表示為:

s.t.

式(7)～式(10);

S2,j,t,x2,j,t∈Z+,yj,t∈,?j∈N,t∈[1,T]。

CLSP的求解非常復(fù)雜,由于在資源約束下,需要對不同的木門、不同的時間段、不同的加工階段和不同的數(shù)量4個維度同時進(jìn)行調(diào)整,使整個過程的制造成本與持有成本的總和最小化。求解CLSP的一大難點(diǎn)在于,其可能存在的排產(chǎn)方案的數(shù)量極大。針對這一特性,該研究方向的文獻(xiàn)通常采用列生成算法來解決。為了進(jìn)一步得到整數(shù)解,采用列生成算法與分支定界算法相結(jié)合的分支定價算法。流水車間的批量生產(chǎn)問題已是經(jīng)典的NP-hard問題,本文對其進(jìn)行拓展延伸,同時考慮包括成批加工階段的兩階段加工車間,因此該問題同屬NP-hard問題,而且計(jì)算過程更加復(fù)雜?？紤]到CLSP的難度,本文根據(jù)該實(shí)木復(fù)合門流水車間存在的普遍情況給出以下合理假設(shè),從而簡化原CLSP問題。在該流水車間內(nèi),第2階段的精修作業(yè)為瓶頸工序,第1階段的生產(chǎn)能力過剩,而且因?yàn)閷?shí)木復(fù)合門經(jīng)過熱壓機(jī)膠合壓縮后無法直接進(jìn)入第2個加工階段,導(dǎo)致這兩個階段之間存在大量的在制品庫存,遂提出以下假設(shè),即在特定時間段內(nèi),第2階段加工所需的在制品均可由第1階段的在制品庫存量來滿足,不存在缺貨的情況。

假設(shè)1對?j∈N,t∈[1,T],存在aj,t-1+S1,j,t-1≥x2,j,t。

根據(jù)上述假設(shè),第1階段與第2階段的排程可以互相獨(dú)立,該假設(shè)將原來的兩階段排程問題拆分簡化為單階段子問題。根據(jù)拉式生產(chǎn)方式,前一階段的生產(chǎn)指令由后一階段的生產(chǎn)計(jì)劃確定,因?yàn)橄葘Φ?階段的子問題設(shè)計(jì)算法,再求解第1批量加工階段的子問題。

3 算法設(shè)計(jì)

根據(jù)拉式生產(chǎn)方式與假設(shè)1,本章先對SS2設(shè)計(jì)分支定價算法得到其整數(shù)最優(yōu)解,再根據(jù)第2階段的在制品需求aj,t=x2,j,t+1,t∈[0,T-1]求解第1階段的子問題SS1。求解SS2的難點(diǎn)在于其可能存在的排產(chǎn)方案數(shù)量極大,針對這一特性,文獻(xiàn)中通常采用列生成算法來解決,然而列生成算法得到的解并非整數(shù)解,因此用分支定價算法得到整數(shù)解。求解SS1的難度較低,因?yàn)榈陔A段使用的成批加工機(jī)器可以同時加工多個不同種類木門。為了提高兩階段CLSP求解效率,本文調(diào)用Gurobi求解器求解SS1。

3.1 SS2集合劃分模型

本節(jié)先將SS2問題通過Dantzig-Wolfe分解的方法轉(zhuǎn)換成等價的集合劃分模型。

(13)

(14)

s.t.

(15)

(16)

(17)

3.2 SS2定價子問題

定義集合劃分模型約束的對偶變量分別為αt和ρj。在3.1節(jié)得到限制松弛主問題后,可解得其對偶變量αt和ρj。對于任意j∈N,定價子問題PSj的目標(biāo)函數(shù)為在所有凸組合的極點(diǎn)k∈Kj中尋找使PSj目標(biāo)函數(shù)最小化的極點(diǎn),通過求解定價子問題,可以找到使RLMP目標(biāo)函數(shù)值更優(yōu)的列,則?j∈N,PSj定義如下:

(18)

s.t.

S2,j,t-1+x2,j,t=dj,t+S2,j,t,
?j∈N,t∈[1,T];

(19)

?j∈N,t∈[1,T];

(20)

x2,j,t≤(capt-st2,j)/vt2,j,

?j∈N,t∈[1,T];

(21)

x2,j,t∈Z+,?j∈N,t∈[1,T];

(22)

yj,t∈,?j∈N,t∈[1,T]。

(23)

3.3 SS2分支定價

本節(jié)將整合3.1節(jié)和3.2節(jié)的模型,給出完整的分支定價算法,分支定價算法可以看作為分支定界與列生成方法的結(jié)合。在分支定界樹的每一個節(jié)點(diǎn)上求解,通過求解線性松弛的RLMP得到對偶變量,將對偶變量傳遞到PS的目標(biāo)函數(shù)中,并用動態(tài)規(guī)劃算法求解每一個PSj,?j∈N。若檢驗(yàn)數(shù)(Reduced Cost) =PS=∑j∈NPSj<0,則將PS解得的列加入RMP構(gòu)成一個新的RMP。重復(fù)循環(huán)以上操作,直到檢驗(yàn)數(shù)大于等于0,沒有新的列可以加入RMP,停止列生成,得到當(dāng)前根節(jié)點(diǎn)的松弛下界。

通過列生成求解的RMP并不能保證得到整數(shù)解,其得到的最優(yōu)值為原問題最優(yōu)整數(shù)解目標(biāo)函數(shù)值的下界。通過列生成得到的最優(yōu)值與對原問題線性松弛得到的最優(yōu)值相等或前者更大,因?yàn)檫@兩者的目標(biāo)函數(shù)都不具有整數(shù)性質(zhì)。為了得到SS2的最優(yōu)整數(shù)解,采用分支定價方法,搜索樹的每一個節(jié)點(diǎn)都需要用列生成來求解,并結(jié)合分支規(guī)則和列生成的定價子問題PS。

3.4 求解器求解 SS1

由于SS1為成批加工機(jī)器,可以同時加工多種不同種類的木門,求解難度較低。為了提高兩階段CLSP的求解效率,本文調(diào)用Gurobi求解器求解SS1。

根據(jù)上述分支定價算法,得到SS2的整數(shù)最優(yōu)解后,將其在制品需求代入SS1,用求解器Gurobi求解第1階段子問題SS1。其中,aj,t為由第2階段傳遞的在制品需求量,即aj,t=x2,j,t+1,?j∈N,t∈[0,T-1]。

4 算例分析

該工作車間的生產(chǎn)能力過剩,車間工作根據(jù)需求訂單排產(chǎn),即實(shí)際生產(chǎn)規(guī)則為按需排產(chǎn)。在?t∈T時間段,第2階段產(chǎn)品j的生產(chǎn)數(shù)量為該時段末顧客的需求量;第1階段產(chǎn)品j的生產(chǎn)數(shù)量為后一時段t+1末顧客的需求量。根據(jù)該按需生產(chǎn)規(guī)則得到的總成本用C1表示,具體實(shí)木復(fù)合門工作車間的按需生產(chǎn)規(guī)則如下:

1: 輸入:參數(shù)N,T,sci,j,t,vci,j,t,sti,j,vt1,vt2,j,hci,j,t,capt,dj,t;變量xi,j,t=0, yj,t=0,zt=0,Si,j,t=0;

2:for j=1 to N do

7:for j=1 to N do

12:輸出C1。

本文建立的數(shù)學(xué)優(yōu)化模型綜合考慮最小化持有成本與制造成本的總和,不過度追求零在制品和零成品庫存,而是根據(jù)不同時段成本的不同,在相對低制造成本時期多生產(chǎn)一部分產(chǎn)品并預(yù)留一部分在制品庫存,以降低車間的總成本。

為了體現(xiàn)本文算法在損耗一部分準(zhǔn)確度的情況下,可以高效求解大規(guī)模的兩階段CLSP,快速為車間提供一套有效的排產(chǎn)方案。用Gurobi求解器求解原問題的混合整數(shù)規(guī)劃模型(CLSP),得到算法成本C2,其與按需生產(chǎn)成本C1的差別如圖4中Gap所示。進(jìn)一步,基于模型規(guī)模的變化分析分支定價算法對問題求解的影響,并將算法求解質(zhì)量和效率與Gurobi求解CLSP進(jìn)行比較。分支定價算法采用Python編程語言,在64 GB RAM 3.70 GHz i7 CPU的計(jì)算機(jī)上運(yùn)行。列生成過程不限制運(yùn)行時間,而是以找不到負(fù)檢驗(yàn)數(shù)為停止列生成的條件,即列生成過程總能找到最優(yōu)整數(shù)解。

模型參數(shù)根據(jù)木門工作車間內(nèi)的生產(chǎn)數(shù)據(jù)設(shè)置,該工作車間的生產(chǎn)數(shù)據(jù)在表2所示的區(qū)間內(nèi)波動。本文算例分析中的參數(shù)在區(qū)間[a,b]內(nèi)根據(jù)均勻分布隨機(jī)生成。

表2 模型參數(shù)設(shè)置

算例模型的規(guī)模根據(jù)木門的種類總數(shù)、生產(chǎn)計(jì)劃總時段、顧客需求量分類。該木門車間生產(chǎn)的木門種類根據(jù)當(dāng)前市場流行風(fēng)格和顧客偏好而定,公司整理出木門種類匯總給顧客挑選,因此車間內(nèi)生產(chǎn)的木門種類總數(shù)隨市場需求而變。若一個顧客表示一戶家庭,鑒于現(xiàn)今的住宅多為小區(qū)套房,每個套房一般有1～3個臥室和1～2個衛(wèi)生間,則一個訂單中同一款式的木門為1～5道。如表3所示,本文將木門的種類規(guī)模分為30(S),50(M),70(L) 3類,考慮的總時間段規(guī)模分為30(S),60(M),100(L)。車間的第1階段為熱壓機(jī)成批膠合壓縮工序,該工序?qū)⑼慌味鄠€不同種類的木門安裝在熱壓機(jī)上同時加工,因此第1階段的單次成批加工成本vc1,t影響車間的總成本;第2階段為精修機(jī)單件流水加工工序,換模準(zhǔn)備一次即能生產(chǎn)同種類的多道木門,因此第2階段的換模成本sc2,j,t影響車間的總成本。為了進(jìn)一步研究車間內(nèi)的成本波動對分支定價算法的影響,將vc1,t,sc2,j,t,hci,j,t分為不同規(guī)模。根據(jù)該車間的成本數(shù)據(jù)統(tǒng)計(jì),第2階段的換模成本分布在兩個區(qū)間內(nèi),該成本一般隨操作員的熟練度、習(xí)慣性和是否依照操作標(biāo)準(zhǔn)作業(yè)等而波動,分別為[0.5,1](S)和[3,5](L);第1階段的成批加工成本波動則在很大程度上與工作環(huán)境、操作員的體力與情緒等有關(guān),分別為[40,60](S)和[80,120](L)。單位木門的庫存持有成本分別為[0.8,1.2](S)和[2,3](L),在確定的工廠倉庫面積下,單位持有成本與顧客需求的淡季或旺季相關(guān)。

表3 不同規(guī)模的模型參數(shù)設(shè)置

在計(jì)算機(jī)上對不同規(guī)模的算例進(jìn)行試運(yùn)行,當(dāng)N/T的規(guī)模為50/100時,求解器Gurobi已無法在8 h內(nèi)直接求解兩階段的原問題CLSP,可見原問題的求解難度極大,將原問題CLSP拆分成兩個階段子問題存在必要性。因此,在后續(xù)算例中將求解器的求解時間限定在600 s以內(nèi)。根據(jù)上述參數(shù)設(shè)置,采用第2章節(jié)設(shè)計(jì)的算法分別求解不同規(guī)模算例,再用求解器在限定時間內(nèi)求解相同的算例。列舉14種不同組合規(guī)模的算例,如表4和表5所示。每一種組合分別用算法求解20次,再用求解器求解20次,共有560次算例。先比較小規(guī)模算例,結(jié)果如表4所示,其中第1～3列為對不同算例設(shè)置的參數(shù)規(guī)模;第4～5列為求解器混合整數(shù)規(guī)劃在限定時間內(nèi)獲得的最優(yōu)值和CPU時間,其中600 s為對求解器求解的限制時間;第6～7列為本文算法所得的算法最優(yōu)值和CPU時間;第8列為算法最優(yōu)值與求解器最優(yōu)值之間的差值Gap,Gap=(算法最優(yōu)值-求解器最優(yōu)值)求解器最優(yōu)值×100%。表中第4～8列均為20次實(shí)驗(yàn)的平均值。針對較小規(guī)模算例,求解器可以在限定時間內(nèi)求得最優(yōu)值,算法的最優(yōu)值與求解器最優(yōu)值之間的Gap很小,平均Gap均在2.65%以內(nèi)。但明顯可見,算法所需的CPU時間大幅縮小,求解器所需時間越多,算法求解時間越高效。本文算法在小規(guī)模算例中犧牲少量最優(yōu)值換取更加高效的求解速度,可以快速為車間提供有效的排產(chǎn)方案。

表4 混合整數(shù)規(guī)劃vs算法小規(guī)模算例結(jié)果

對大規(guī)模算例進(jìn)行比較,如表5所示。在中大規(guī)模算例中,求解器在限定的600 s內(nèi)往往無法得到最優(yōu)值。算法最優(yōu)值與求解器限定時間內(nèi)的最優(yōu)值之間的Gap仍在小范圍內(nèi)波動,平均Gap均小于1.802%。對比分析兩種方法所需的CPU時間,面對最大規(guī)模算例,算法求解所需的CPU時間仍然在預(yù)期范圍內(nèi)。本文算法在中大規(guī)模算例中仍然以犧牲少量最優(yōu)值為條件,來換取更加高效的求解速度。

為了更加直觀地展示不同算例之間算法最優(yōu)值與求解器限定時間內(nèi)最優(yōu)值的差距Gap,繪制帶列散點(diǎn)的箱線圖,如圖5所示。根據(jù)木門種類N與時段T的規(guī)模劃分,將表4和表5中的14種參數(shù)組合為7大組,如圖5最上面的灰色橫軸所示。每個大類中有2個小組,根據(jù)換模成本/第1階段加工成本/兩階段持有成本(sc2,j,tc1,thci,j,t)規(guī)模劃分,分別為圖5中的斜線箱體與灰色箱體。在木門種類N與時段T相同的情況下,第2階段換模成本/第1階段加工成本/兩階段持有成本(sc2,j,tc1,thci,j,t)中的任意一項(xiàng)越大,算法與求解器所得最優(yōu)值之間的Gap越大,而且木門種類N與時段T兩個參數(shù)規(guī)模越大,Gap整體越小,求解器在限定時間內(nèi)所得的解越差。然而分支定價算法的Gap均未超過3.17%,且與求解器CPU時間相比,所需的CPU時間大幅縮小,而求解器已無法在限定時間內(nèi)獲得最優(yōu)解。

根據(jù)表4、表5和圖5的信息,控制某些參數(shù)規(guī)模相同,分析其他參數(shù)改變對算法求解結(jié)果的影響。對比組合2與組合4,前者的時段規(guī)模為S,后者的時段規(guī)模為M,兩者Gap的平均值相差無幾,但時段T越大,算例Gap的標(biāo)準(zhǔn)差越小,樣本點(diǎn)排列越緊密;類似的還有組合6與組合8、組合10與組合12。對比組合8與組合12,前者的木門種數(shù)N規(guī)模為M,后者為L,木門種數(shù)規(guī)模越大,Gap整體越小。對比組合3與組合4,sc2,j,t規(guī)模越大,Gap整體越大,類似的有組合13與14。在對比組合3與組合4的基礎(chǔ)上,對比組合5與組合6,因?yàn)闀r段T規(guī)模不會大幅改變算法的Gap,所以推斷持有成本hci,j,t規(guī)模減小,Gap將近一步增大。同樣在對比組合3與組合4的基礎(chǔ)上,對比組合11與組合12,兩者Gap的平均值相差無幾,散點(diǎn)排列近似相同,可以推斷vc1,t越大,Gap整體越大,而且其影響與sc2,j,t規(guī)模改變的影響相當(dāng)。

本文算法將原問題CLSP拆分成兩階段子問題時,犧牲了整體最優(yōu)值,但顯著提高了計(jì)算速率,并在短時間內(nèi)得到的算法最優(yōu)值與求解器在限定時間內(nèi)得到的最優(yōu)值的差距很小,均未超過3.17%。在木門種類N=50的情況下,求解器已無法在限定時間內(nèi)給出最優(yōu)解,可見求解器的求解效率低下,無法及時給出車間所需的生產(chǎn)排程方案,由此說明了本文算法的有效性。

5 結(jié)束語

本文考慮了含成批加工工序的兩階段實(shí)木復(fù)合門流水生產(chǎn)車間的批量生產(chǎn)問題,通過拉式生產(chǎn)保證準(zhǔn)時化制造,目標(biāo)是在滿足不同時段內(nèi)顧客需求的情況下最小化流水車間的總成本(制造成本與庫存持有成本之和)。首先建立該問題的混合整數(shù)規(guī)劃數(shù)學(xué)模型,根據(jù)實(shí)木復(fù)合門流水車間的實(shí)際環(huán)境與條件,給出與實(shí)際生產(chǎn)現(xiàn)狀相符的假設(shè),使兩階段的批量生產(chǎn)子問題互相獨(dú)立。對SS2進(jìn)行Dantzig-Wolfe分解,得到可行域滿足凸組合conv(Kj)的主問題MP,該MP中的約束有指數(shù)級數(shù)量的列,適合采用列生產(chǎn)方法求解。然而,列生成算法只能得到松弛解,為了進(jìn)一步得到SS2的最優(yōu)整數(shù)解,本文采用分支定界與列生成相結(jié)合的分支定價算法。根據(jù)SS2的在制品需求,拉動第1階段批量工序制造,并求解SS1,最終獲得該流水車間兩個階段的批量生產(chǎn)方案。最后,對不同規(guī)模參數(shù)的木門加工生產(chǎn)線進(jìn)行算例分析,結(jié)果顯示該算法可以求解大規(guī)模算例,算法的最優(yōu)值Gap最高不超過3.17%,且所需的CPU時間仍在可接受范圍內(nèi),而求解器已無法在限定時間內(nèi)獲得最優(yōu)解。本算法在犧牲少量最優(yōu)值的情況下大幅提高了計(jì)算速率,且Gap很小。

本文為制定實(shí)木復(fù)合門流水車間生產(chǎn)控制系統(tǒng)的批量生產(chǎn)方案提供了理論依據(jù),為今后改善木制家具生產(chǎn)過程提供了明確的解決方案。未來可進(jìn)一步拓展木門批量流水車間加工模型,在每個加工環(huán)節(jié)考慮更多實(shí)際生產(chǎn)過程中存在的問題,如包含多臺設(shè)備、加工能耗約束、工人加班限制等。