于 淼,趙 潔,焦紅超
(沈陽建筑大學(xué)管理學(xué)院,遼寧 沈陽 110168)
裝配式建筑在我國發(fā)展還不夠成熟,預(yù)制構(gòu)件生產(chǎn)管理專業(yè)化程度低,生產(chǎn)過程中出現(xiàn)了調(diào)度混亂、生產(chǎn)效率低下、成本高等問題[1],一定程度上阻礙了建筑工業(yè)化進程。因此,對預(yù)制構(gòu)件進行科學(xué)排產(chǎn)極其重要。目前,眾多學(xué)者對預(yù)制構(gòu)件生產(chǎn)車間展開了研究,有學(xué)者針對生產(chǎn)工序?qū)δP瓦M行了改造。Li等[2]從供應(yīng)鏈角度考慮預(yù)制構(gòu)件生產(chǎn)過程的勞動力、庫存資源約束,構(gòu)建了以生產(chǎn)成本最小化為目標(biāo)的生產(chǎn)調(diào)度模型。Wang等[3]通過構(gòu)建全供應(yīng)鏈生產(chǎn)調(diào)度模型,分析了新增工序?qū)ν旯r間的影響規(guī)律。Kong等[4]在原有生產(chǎn)調(diào)度模型中增加裝配環(huán)節(jié),指出裝配式建筑包含生產(chǎn)—運輸—裝配3個部分,建立了以最大生產(chǎn)效率為目標(biāo)的裝配式建筑全過程的資源調(diào)度模型。
為貼合現(xiàn)實生產(chǎn)條件,一些學(xué)者把資源約束引入生產(chǎn)調(diào)度模型,Chan等[5]在約束條件中加入養(yǎng)護室處理能力約束。Ko等[6]在Chan等[5]的基礎(chǔ)上增加了相鄰兩個工位之間的緩沖區(qū)容量約束,提高了模型實用性。在算法求解方面,遺傳算法應(yīng)用較多。謝思聰?shù)萚7]運用遺傳算法,解決了招投標(biāo)和生產(chǎn)兩個階段的預(yù)制構(gòu)件優(yōu)化問題。程月明等[8]運用非支配排序遺傳算法求解了考慮養(yǎng)護窯數(shù)量的混凝土預(yù)制構(gòu)件優(yōu)化模型。Ma等[9]采用非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithms,NSGA)對多條生產(chǎn)線優(yōu)化模型進行了求解,完成了多條生產(chǎn)線優(yōu)化。
上述研究都是針對考慮資源約束的裝配式建筑預(yù)制構(gòu)件的靜態(tài)生產(chǎn)調(diào)度的,忽略了預(yù)制構(gòu)件加工環(huán)境的動態(tài)性和不確定性。此外,在預(yù)制構(gòu)件生產(chǎn)調(diào)度效果評價上,對完工時間和懲罰成本這兩個相互沖突的目標(biāo)的處理上存在欠缺。針對以上研究存在的不足,筆者在綜合考慮模板約束和緩沖區(qū)約束的條件下對緊急插單情況下裝配式建筑預(yù)制構(gòu)件多目標(biāo)生產(chǎn)調(diào)度問題進行研究,運用多目標(biāo)差分進化算法,優(yōu)化預(yù)制構(gòu)件生產(chǎn)調(diào)度方案,通過合理安排構(gòu)件生產(chǎn)順序,保證構(gòu)件在滿足完工時間最短和懲罰成本最少的雙目標(biāo)下順利交貨。
混凝土預(yù)制構(gòu)件生產(chǎn)車間與制造業(yè)的生產(chǎn)車間類似,都是經(jīng)過各種生產(chǎn)環(huán)節(jié),生產(chǎn)出所需要的產(chǎn)品[10]。預(yù)制構(gòu)件的生產(chǎn)過程如圖1(a)所示。根據(jù)生產(chǎn)的工藝特征將其分為并行工序和串行工序,其中,混凝土養(yǎng)護為并行工序,可同時處理多個工件,其余則為串行工序。在預(yù)制生產(chǎn)環(huán)境中,該條流水線由Nk道工序組成,待生產(chǎn)j個預(yù)制構(gòu)件,每個預(yù)制構(gòu)件均包含Nk道工序,且這j個預(yù)制構(gòu)件必須在所有工序上以相同的順序進行加工。Sj,Nk為對預(yù)制構(gòu)件(j,Nk)開始進行加工的時間;Pj,Nk為對預(yù)制構(gòu)件(j,Nk)進行處理所需的時間;E(j,Nk)為預(yù)制構(gòu)件加工結(jié)束的時間;dj為不施工方向預(yù)制構(gòu)件生產(chǎn)方提出的交貨日期。該批預(yù)制構(gòu)件的調(diào)度結(jié)束后,有一批數(shù)量為n*的緊急插單任務(wù)出現(xiàn)(見圖1(b)),需要立即進行排程,將這批預(yù)制構(gòu)件記為j*={n+1,n+2,,n+n*}。插單對生產(chǎn)計劃造成擾動,原先的調(diào)度計劃失效,需要進行重新調(diào)度。
圖1 預(yù)制構(gòu)件生產(chǎn)工序與問題描述
預(yù)制構(gòu)件生產(chǎn)應(yīng)當(dāng)滿足以下要求:①每個工件必須按1,2,,m順序在所有機器上進行工序處理;②除混凝土澆筑、養(yǎng)護外,其余工序均為搶占式工序;③預(yù)制構(gòu)件的加工時間包括其準(zhǔn)備時間,已知且不會發(fā)生變化;④除混凝土養(yǎng)護外,工序允許等待。
預(yù)制構(gòu)件生產(chǎn)調(diào)度模型參數(shù)如表1所示。
表1 預(yù)制構(gòu)件生產(chǎn)調(diào)度模型參數(shù)定義及說明
對預(yù)制構(gòu)件調(diào)度結(jié)果進行評價時,需要同時兼顧多個目標(biāo),確保調(diào)度結(jié)果符合預(yù)制構(gòu)件生產(chǎn)優(yōu)化的要求。因此,本研究選用完工時間和懲罰成本作為評價指標(biāo),對調(diào)度結(jié)果進行評價。完工時間為
f1=E(n,Nm)
(1)
懲罰成本通過完工時間大于交貨期產(chǎn)生的延遲成本和小于交貨期產(chǎn)生的庫存成本兩部分的和來計算
(2)
式中:Ej為預(yù)制構(gòu)件j的完工時間。
目標(biāo)函數(shù)為
F=min(f1,f2)
(3)
(1)可中斷工序
模具組裝、預(yù)埋件放置、拆模、構(gòu)件修補均屬于可中斷工序,即在8 h內(nèi)該工序沒有完成,可延后到第二天完成??芍袛喙ば虻耐旯r間為
1,2,5,6
(4)
預(yù)制構(gòu)件生產(chǎn)工序累計完成時間為
T=max[E(j-1,Nk),E(j,Nk-1)]+Pj,Nk
(5)
(2)不可中斷工序
①混凝土澆筑。混凝土澆筑過程中涉及水泥的使用,屬于不可中斷工序,如果在加班時間內(nèi)可以完成,則選擇加班完成,反之,混凝土澆筑工序應(yīng)推遲到第二天進行。預(yù)制構(gòu)件混凝土澆筑工序完工時間為
E(j,Nk)=
(6)
式中:HA為加班時間(HW>HA)。
②混凝土養(yǎng)護。混凝土養(yǎng)護屬于非搶占式工序,不同類型的預(yù)制構(gòu)件可以在同一時間進行養(yǎng)護,因此,混凝土養(yǎng)護開始時間在澆筑工序之后,其完成時間為
T*=E(j,N3)+Pj,Nk
(7)
E(j,Nk)=
(8)
③模板約束。預(yù)制構(gòu)件生產(chǎn)效率受模具數(shù)量的影響,因模板數(shù)量有限,會出現(xiàn)預(yù)制構(gòu)件模板等待時間。當(dāng)模具均被占用,只有等先進行拆模工序的預(yù)制構(gòu)件釋放模板后,下一個預(yù)制構(gòu)件才能開始模具安裝。第j個預(yù)制構(gòu)件使用β模具的開始時間為
S(j,β,N1)≥minXβ{?y{E(y,β,N5)}}
(9)
式中:β為模具類型;Xβ為模具β的數(shù)量。
④緩沖區(qū)約束。緩沖區(qū)約束指相鄰工序之間的空間容量要大于預(yù)制構(gòu)件半成品的需要[11]。若工序Nk與工序Nk+1之間的存儲容量為BNk,那么構(gòu)件j從Nk離開的時間必須晚于構(gòu)件j-BNk進入Nk+1的時間,此舉可保證各工序之間不發(fā)生阻塞現(xiàn)象。緩沖區(qū)約束表達式為
E(j,Nk)≥S(j-BNK,Nk+1)
(10)
多目標(biāo)差分進化算法是一種主要針對多個目標(biāo)進行優(yōu)化的算法。利用父代個體向量間差分的原理進行種群個體的迭代更新,得到所求問題的最優(yōu)解。算法包括交叉、變異和選擇3個核心操作,符合進化算法的一般流程[12]。
采用整數(shù)序列編碼方式,先將工件連續(xù)編號,再將工件編號的排列組合作為一個完整的編碼序列。例如:工件總數(shù)為10,隨機編碼序列A=[4,6,5,3,8,2,1,9,7,10],說明每道工序加工的工件順序為4,6,,10。
適應(yīng)度函數(shù)用z1、z2表示,計算式為
z1=f1;z2=f2
(11)
設(shè)置種群規(guī)模、最大迭代次數(shù)、交叉概率。隨機生成1個初始種群p,對初始種群p的適應(yīng)度函數(shù)值進行計算。
對初始種群p進行交叉變異,產(chǎn)生第二代種群q,計算第二代種群q的適應(yīng)度值。
對p、q進行比較,如果p支配q,挑選p作為新一代種群,如果p與q沒有支配關(guān)系,則全部作為新一代種群。
對步驟(5)產(chǎn)生的新種群按照式(12)進行擁擠距離計算,然后根據(jù)計算結(jié)果挑選擁擠距離大的個體產(chǎn)生新的種群。
(12)
若滿足G≥100,則輸出Pareto最優(yōu)解集;反之,令迭代次數(shù)G=G+1,直到達到最大迭代次數(shù),終止循環(huán)。
完整的MODE算法流程如圖2所示。
圖2 MODE算法流程
筆者以某企業(yè)的預(yù)制外墻板生產(chǎn)線為例進行分析,其預(yù)制構(gòu)件生產(chǎn)信息如表2所示,其中,N1為模具組裝;N2為預(yù)埋件放置;N3為混凝土澆筑;N4為混凝土養(yǎng)護;N5為拆模;N6為構(gòu)件修補。預(yù)制構(gòu)件各工序加工時間與交付時間、違約費與庫存費均通過實地調(diào)研和與部分負責(zé)人訪談得到(見表2)。在這一批次的8個預(yù)制構(gòu)件生產(chǎn)過程中,使用了A、B、C 3種模具。每天的常規(guī)工作時間(HW)為8 h。根據(jù)企業(yè)要求,加班時長(HA)不能超過4 h,相鄰工位緩沖區(qū)空間設(shè)置為1,即相鄰工位能同時容納1個預(yù)制構(gòu)件。預(yù)制構(gòu)件生產(chǎn)準(zhǔn)備工作已經(jīng)做好,收到一個緊急訂單,該訂單包含2個預(yù)制構(gòu)件H,其生產(chǎn)信息如表3所示。
數(shù)值計算過程中,初始種群規(guī)模NP=100,交叉概率CR=0.9,最大迭代次數(shù)G=100,采用MATLAB R2018b 軟件編程,利用多目標(biāo)差分進化算法實現(xiàn)多目標(biāo)調(diào)度優(yōu)化。根據(jù)算法所設(shè)置的數(shù)值精度,對模型進行求解,求得Pareto最優(yōu)解集(見圖3)。該初始調(diào)度產(chǎn)生3個調(diào)度方案(見表4)。
表2 預(yù)制構(gòu)件生產(chǎn)信息
表3 緊急插入訂單信息
緊急訂單出現(xiàn)后,需要對初始預(yù)制構(gòu)件和緊急訂單中的構(gòu)件進行重新決策,首先選擇初始調(diào)度中設(shè)備閑置時間最大的方案,對該方案中預(yù)制構(gòu)件和緊急訂單中包含的構(gòu)件進行重調(diào)度。新增2個預(yù)制構(gòu)件H各工序占用各工序的處理時間如表5所示。
圖3 MODE算法優(yōu)化得到的Pareto最優(yōu)解
表4 預(yù)制構(gòu)件生產(chǎn)初始調(diào)度計劃
表5 新增預(yù)制構(gòu)件生產(chǎn)占用各工序時間 h
(1)重調(diào)度生產(chǎn)方案選擇
初始調(diào)度方案中,各工序空閑時間為從該工序生產(chǎn)的持續(xù)時間中抽去所有加工工件在機器上加工處理的時間,則各方案的各工序閑置時間如表6所示。方案1的機器閑置時間為173.4 h,閑置時間最長且大于表5中新增構(gòu)件H所需的生產(chǎn)時間,因此,選擇方案1進行生產(chǎn)重調(diào)度。
表6 預(yù)制構(gòu)件生產(chǎn)初始調(diào)度各方案閑置時間 h
(2)重調(diào)度求解
根據(jù)方案1,由于緊急訂單到達時,4號預(yù)制構(gòu)件的第一道工序已經(jīng)完成,進行重調(diào)度時其第一道工序加工時間為0,則方案1預(yù)制構(gòu)件生產(chǎn)重調(diào)度模型輸入信息如表7所示。
表7 預(yù)制構(gòu)件生產(chǎn)重調(diào)度模型輸入信息
筆者運用多目標(biāo)差分進化算法對預(yù)制構(gòu)件重調(diào)度模型進行求解,得到4個新的調(diào)度方案(見圖4)。為突出該算法的求解效果,將多目標(biāo)差分進化算法與啟發(fā)式算法NEH(Nawaz、Enscore、Ham)進行比較,NEH算法的核心思想是根據(jù)工件的加工時間把工件按照從大到小的順序進行排列。選取序列中最靠前的兩個工件進行組合,找到最小的工件排序,重復(fù)以上操作,直到全部工件被組合完畢[13]。啟發(fā)式算法NEH的參數(shù)設(shè)置參考多目標(biāo)差分進化算法(MODE)、初始種群迭代次數(shù)、交叉概率,優(yōu)化后得到2個新的調(diào)度方案(見圖5)。
圖4 MODE算法優(yōu)化得到的重調(diào)度Pareto最優(yōu)解
圖5 NEH算法優(yōu)化得到的重調(diào)度Pareto最優(yōu)解
筆者引入距離和CPU運行時間兩個指標(biāo)對兩種算法得到的帕累托最優(yōu)解的質(zhì)量進行評價。
①距離指標(biāo)(GD)是檢驗算法求得的所有非支配解之間的遠近程度的數(shù)值[14]。計算式為
(13)
式中:C為非支配解集合中的解的數(shù)量;dp為所有非支配解中任一向量距離與其他向量之間的最小歐式距離。GD越小,則非支配解距離非支配解集合越近,算法性能越好[14]。
②CPU運行時間是主要用于檢測算法運行效率的指標(biāo)。運行效率隨著運行時間的縮短而提高。
根據(jù)兩種算法的優(yōu)化結(jié)果計算上述兩項指標(biāo),評價結(jié)果如表8所示。比較運行時間可知,MODE算法比NEH算法時間短,其運行效率優(yōu)于NEH算法;比較距離可知,MODE算法比NEH算法更接近最優(yōu)解,其收斂性更好。
表8 多目標(biāo)優(yōu)化實驗結(jié)果對比
MODE算法優(yōu)化得到4個調(diào)度方案(見表9),完工時間隨著懲罰成本的增加而減少。因此,當(dāng)企業(yè)接到緊急訂單時,可以選取完工時間最小的方案進行生產(chǎn)。
表9 MODE算法優(yōu)化得到的預(yù)制構(gòu)件生產(chǎn)重調(diào)度計劃
筆者通過對插單擾動下裝配式建筑預(yù)制構(gòu)件生產(chǎn)重調(diào)度問題進行研究,優(yōu)化了預(yù)制構(gòu)件生產(chǎn)順序,達到了降低預(yù)制構(gòu)件生產(chǎn)成本的目的。通過構(gòu)建多目標(biāo)的預(yù)制構(gòu)件生產(chǎn)調(diào)度模型,選取多目標(biāo)差分進化算法進行算法設(shè)計,求得最優(yōu)預(yù)制構(gòu)件排產(chǎn)計劃,并通過案例分析證明了所構(gòu)建的求解預(yù)制構(gòu)件生產(chǎn)優(yōu)化模型操作簡單,運用的多目標(biāo)差分進化算法在獲得Pareto最優(yōu)解上優(yōu)于啟發(fā)式算法,進一步豐富了預(yù)制構(gòu)件生產(chǎn)求解思路,可為裝配式建筑預(yù)制構(gòu)件生產(chǎn)方提供參考,有利于預(yù)制構(gòu)件生產(chǎn)方針對緊急插單問題,安排合理的排產(chǎn)計劃。