汪和平 齊欣然 陳夢凱

(1.安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院, 安徽 馬鞍山 243002; 2.重慶大學(xué) 管理科學(xué)與房地產(chǎn)學(xué)院, 重慶 400044)

0 引言

裝配式建筑因其綠色節(jié)能、資源節(jié)約、高效低耗、施工方便等顯著優(yōu)勢成為國內(nèi)外建筑行業(yè)發(fā)展的主流[1]。近幾年來,國務(wù)院和住建部陸續(xù)出臺了《國務(wù)院辦公廳關(guān)于促進(jìn)建筑業(yè)持續(xù)健康發(fā)展的意見》[2]《“十三五”裝配式建筑行動方案》[3]等相關(guān)文件,明確全國裝配式建筑比例新目標(biāo),全面推進(jìn)裝配式建筑發(fā)展。2020年新型冠狀肺炎疫情爆發(fā)之際,病患人數(shù)激增,醫(yī)療床位緊缺,火神山醫(yī)院采用了行業(yè)最前沿的裝配式建筑技術(shù)在短短十日完成了它的規(guī)劃、建造與交付,最大限度地采用了拼裝式工業(yè)化成品創(chuàng)造了中國建筑新速度。裝配式建筑無疑成為我國建筑產(chǎn)業(yè)轉(zhuǎn)型升級的新路徑。

當(dāng)前,我國的裝配式建筑處于初步階段,建筑成本高,發(fā)展速度較慢,仍存在資源配置不合理、構(gòu)件生產(chǎn)順序混亂、各環(huán)節(jié)協(xié)調(diào)配合不完善等問題[4]。而裝配式建筑構(gòu)件的生產(chǎn)是整個建筑過程中的關(guān)鍵環(huán)節(jié),對項(xiàng)目能否按時按質(zhì)完成起決定性作用。裝配式建筑預(yù)制構(gòu)件生產(chǎn)調(diào)度問題也成為學(xué)界關(guān)注的重點(diǎn)話題。

早期研究主要以單條車間流水線生產(chǎn)模式為主,圍繞生產(chǎn)時長、生產(chǎn)成本進(jìn)行建模優(yōu)化。國外學(xué)者Benjaora和Dawood[5-7]最先對預(yù)制構(gòu)件的生產(chǎn)做出相應(yīng)的研究,建立了構(gòu)件生產(chǎn)總時長及交貨差時模型。之后相關(guān)學(xué)者根據(jù)生產(chǎn)實(shí)際情況發(fā)現(xiàn)構(gòu)件進(jìn)入流水線時帶有優(yōu)先級的生產(chǎn)排序會對生產(chǎn)時間產(chǎn)生影響,因而在原有模型的基礎(chǔ)上又增加了生產(chǎn)優(yōu)先級的優(yōu)化思路。Chan和Hu[8]為控制交付時間設(shè)置了不同構(gòu)件進(jìn)入單條流水線的優(yōu)先級,制定了帶有適度加班時間的流水車間排序模型。隨著研究的深入,生產(chǎn)過程中生產(chǎn)區(qū)域限制及受限資源的利用率等不同因素開始受到研究者的重視。Ko等[9]在Chan等的研究基礎(chǔ)上考慮到構(gòu)件的尺寸大小不同于其他產(chǎn)品,在各工作站等待生產(chǎn)區(qū)域的占地面積較大,因而建立了緩沖區(qū)容量受限的多目標(biāo)預(yù)制生產(chǎn)調(diào)度模型(MOPPSM)。Khalili等[10]通過研究發(fā)現(xiàn)生產(chǎn)過程中對模具的制造、使用、更換及轉(zhuǎn)換成本進(jìn)行控制也能有效提高模具利用率,建立了模具分配集成問題的混合整數(shù)線性規(guī)劃(MILP)模型。Wang等[11]則從全局出發(fā),將生產(chǎn)、儲存和運(yùn)輸三個階段從供應(yīng)鏈的視角對傳統(tǒng)的生產(chǎn)調(diào)度模型進(jìn)行了改進(jìn)。

隨著近些年經(jīng)濟(jì)的發(fā)展,傳統(tǒng)單一流水線的生產(chǎn)能力已不能滿足生產(chǎn)需求,學(xué)者們開始對多流水線車間生產(chǎn)模式進(jìn)行研究。Yang等[12]將車間生產(chǎn)過程劃分為支模、鋼筋及預(yù)埋件安置、澆筑、養(yǎng)護(hù)、拆模五道工序,根據(jù)多流水車間中模具資源的共享情況,設(shè)置了構(gòu)件進(jìn)入不同生產(chǎn)線的調(diào)度方案,綜合考慮生產(chǎn)過程中時間、成本、順次生產(chǎn)的構(gòu)件變化等多方面優(yōu)化目標(biāo)建立了多流水線生產(chǎn)作業(yè)計劃模型(MPFSM)。蒙秋男[13]為解決產(chǎn)品生產(chǎn)節(jié)拍不同影響生產(chǎn)連續(xù)性的問題,在保證混流產(chǎn)品在無等待的生產(chǎn)條件下,在多條流水線中對總裝分裝任務(wù)排序進(jìn)行優(yōu)化。Xu等[14]研究了構(gòu)件在多流水線生產(chǎn)過程中每個步驟所分配到的時間與預(yù)計生產(chǎn)時間的差值,將實(shí)際與預(yù)計的差值調(diào)整到最小以此來避免物料的重調(diào)度。Wang等[15]在多條流水線共同生產(chǎn)的前提下對預(yù)制構(gòu)件的生產(chǎn)進(jìn)行重調(diào)度,對生產(chǎn)過程中的動態(tài)需求變化做出響應(yīng)。

在多目標(biāo)流水線優(yōu)化模型求解方面,相關(guān)學(xué)者采用了不同的進(jìn)化算法進(jìn)行求解。早前主要以遺傳算法為主,Benjaora、Dawood[5-7]

及Zhai[16]等幾位學(xué)者最先通過仿真得出遺傳算法(GA)更能有效的減少作業(yè)時間、提高生產(chǎn)效率、滿足生產(chǎn)交付計劃。之后開始有學(xué)者研究改進(jìn)算法或混合算法對多目標(biāo)流水生產(chǎn)的優(yōu)化求解。Albehadili等[17]混合了隨機(jī)化偏向策略的迭代貪婪算法(BRIG)求解車間出現(xiàn)新訂單干擾或機(jī)械損壞等干擾問題的多目標(biāo)生產(chǎn)模型。黎陽等[18]對模擬退火算法的初始退火溫度進(jìn)行改進(jìn),提高了大規(guī)模流水置換車間生產(chǎn)的求解質(zhì)量。軒華[19]提出一種融合變鄰域搜索過程和改進(jìn)遺傳流程的混合優(yōu)化算法對多階段的惡化柔性流水車間調(diào)度進(jìn)行了優(yōu)化。姚遠(yuǎn)遠(yuǎn)等[20]設(shè)計了一種改進(jìn)多目標(biāo)灰狼優(yōu)化算法(IMOGWO)求解混合流水車間調(diào)度問題。Tang[21]提出了一種基于改進(jìn)粒子群算法的車間調(diào)度算法來搜索動態(tài)柔性車間調(diào)度問題中的帕累托最優(yōu)解,并通過數(shù)值檢驗(yàn)驗(yàn)證了改進(jìn)粒子群算法的性能和效率。

隨著多目標(biāo)優(yōu)化調(diào)度考慮因素的增多,傳統(tǒng)的進(jìn)化算法的求解能力在三個及以上多目標(biāo)優(yōu)化問題上逐漸降低,學(xué)者們開始研究更換適合高維多目標(biāo)的求解方法。Long[22]提出了一種基于非支配排序遺傳算法-II(NSGA-II)的混合多目標(biāo)進(jìn)化算法,能夠有效求解帶有釋放時間的多目標(biāo)調(diào)度模型。李林林[23]基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)提出了一種改進(jìn)的分解多目標(biāo)進(jìn)化算法(MOEA/D-GL),基于分組和統(tǒng)計學(xué)習(xí)機(jī)制對外部存檔進(jìn)行改進(jìn),并利用距離的替換策略更新了種群,提高了種群的多樣性。馮超[24]將近鄰傳播算法引入到強(qiáng)度帕累托進(jìn)化算法(SPEA-Ⅱ)中,通過對算法的多樣性保持策略進(jìn)行改進(jìn),提高了算法Pareto前端分布的均勻性與收斂效果。Bhesdadiya[25]使用第三代非支配排序遺傳算法(NSGA-Ⅲ)求解多目標(biāo)組合經(jīng)濟(jì)排放調(diào)度問題,同時考慮功率平衡、傳輸損耗、排放價值和燃料成本等優(yōu)化目標(biāo),與其他優(yōu)化算法進(jìn)行對比實(shí)驗(yàn),驗(yàn)證了NSGA-Ⅲ在高維優(yōu)化問題上的有效性。

雖然現(xiàn)有文獻(xiàn)針對裝配式預(yù)制構(gòu)件的生產(chǎn)調(diào)度和模型優(yōu)化進(jìn)行了大量研究,但仍存在以下不足。首先,在預(yù)制構(gòu)件生產(chǎn)模式的選擇方面,現(xiàn)有研究多以模式單一的單流水作業(yè)為對象,對構(gòu)件在車間混合生產(chǎn)的情況研究不足。其次,從目標(biāo)優(yōu)化的確定方面,現(xiàn)有研究主要圍繞交付期和生產(chǎn)成本,對空閑等待、生產(chǎn)總時長、庫存成本、生產(chǎn)能耗等方面缺少綜合分析。第三,在對構(gòu)件生產(chǎn)模型優(yōu)化求解方面,現(xiàn)有的研究以傳統(tǒng)進(jìn)化算法為主,這類算法在對高維多目標(biāo)問題進(jìn)行優(yōu)化時難以獲得質(zhì)量較高的解,且求解質(zhì)量對初始種群的依賴較大。

基于此,本文在現(xiàn)有研究理論和方法的基礎(chǔ)上,構(gòu)建了多流水線構(gòu)件混合生產(chǎn)的調(diào)度模型,綜合考慮車間調(diào)度的模具資源配置、構(gòu)件生產(chǎn)順序、構(gòu)件在流水線的變化程度、生產(chǎn)成本、生產(chǎn)工期和生產(chǎn)能耗等多維度的目標(biāo)優(yōu)化,并基于改進(jìn)種群初始化的NSGA-Ⅲ算法對模型進(jìn)行求解,以避免傳統(tǒng)進(jìn)化算法在目標(biāo)大于3個的高維問題優(yōu)化上能力不足的缺陷。

1 裝配式建筑構(gòu)件生產(chǎn)工藝概述

裝配式建筑預(yù)制構(gòu)件生產(chǎn)種類繁多,不同的項(xiàng)目甚至是同項(xiàng)目中不同構(gòu)件的尺寸、所需數(shù)量、使用材料等都不同,需要根據(jù)訂單需求制定生產(chǎn)計劃,實(shí)現(xiàn)準(zhǔn)時化生產(chǎn),盡可能減少提前生產(chǎn)導(dǎo)致的庫存成本或延期交貨需賠付的成本。預(yù)制構(gòu)件生產(chǎn)是裝配式建筑的核心階段,工程質(zhì)量很大程度取決于產(chǎn)出構(gòu)件的質(zhì)量?，F(xiàn)階段我國裝配式建筑預(yù)制構(gòu)件的生產(chǎn)根據(jù)不同的生產(chǎn)工藝主要可分為固定模臺生產(chǎn)和流水線生產(chǎn)兩種。對比發(fā)現(xiàn),流水車間生產(chǎn)勞動力投入少、生產(chǎn)成本低、可操作性強(qiáng)、能耗損失小,通常被作為預(yù)制車間的主要生產(chǎn)模式。下面則主要針對流水車間構(gòu)件的生產(chǎn)工藝進(jìn)行介紹。

裝配式建筑預(yù)制構(gòu)件的生產(chǎn)流程主要包括生產(chǎn)前準(zhǔn)備階段、生產(chǎn)階段及儲運(yùn)階段三個階段[26]。第一階段是在生產(chǎn)線外對生產(chǎn)前的物料進(jìn)行準(zhǔn)備及檢驗(yàn)、完成鋼筋加工、模臺模具的準(zhǔn)備等;第二階段在第一階段準(zhǔn)備完全的前提下,在流水車間生產(chǎn)線上完成構(gòu)件的生產(chǎn),主要步驟包括模具模臺的清理組裝、吊放鋼筋籠、預(yù)埋件埋設(shè)、混凝土澆筑及振搗、預(yù)養(yǎng)護(hù)及養(yǎng)護(hù)、構(gòu)件脫模及放置、成品檢驗(yàn)及修補(bǔ)等過程。第三階段是將構(gòu)件編號再運(yùn)輸至儲藏地或施工現(xiàn)場。其基本生產(chǎn)工藝流程如圖1所示。

圖1 裝配式建筑構(gòu)件生產(chǎn)基本工藝流程圖Figure 1Basic production process of prefabricated building components

2 預(yù)制構(gòu)件流水車間生產(chǎn)調(diào)度模型

2.1 問題描述

流水式預(yù)制構(gòu)件車間生產(chǎn)流程大致可分為組模(M1)、鋼筋籠及預(yù)埋件放置(M2)、混凝土澆筑(M3)、養(yǎng)護(hù)(M4)、脫模(M5)和清理修補(bǔ)(M6)六道工序,每一道工序設(shè)一個工作站對其進(jìn)行作業(yè)。各類預(yù)制構(gòu)件在上述六道工作站按相同的程序進(jìn)行生產(chǎn),但是不同構(gòu)件在不同工序上的處理時間不同,構(gòu)件根據(jù)排序依次進(jìn)入流水生產(chǎn)線,最終完成生產(chǎn)。其中M1、M2、M5、M6如果在一個工作日內(nèi)沒有完成,可延續(xù)到下一個工作日繼續(xù)作業(yè),M3、M4屬于不可間斷作業(yè),澆筑完成后應(yīng)立即進(jìn)行養(yǎng)護(hù)步驟。澆筑(M3)工序如果在工作時間內(nèi)不能完成,則可考慮通過一定程度的加班來完成該道工序。而養(yǎng)護(hù)過程(M4)不需要人工的參與,可在非工作時間在養(yǎng)護(hù)窯進(jìn)行養(yǎng)護(hù),并且可同時養(yǎng)護(hù)多個構(gòu)件。為了直觀展現(xiàn)六道工序處理的時間進(jìn)度,對各生產(chǎn)工序的完成時間進(jìn)度進(jìn)行描述,假設(shè)某構(gòu)件j經(jīng)過各生產(chǎn)工作站k的完成時間C(j,k)以及經(jīng)過該道工序的生產(chǎn)時間P(j,k)可用下圖2表示。

圖2 各生產(chǎn)工序的完成時間進(jìn)度圖示Figure 2The completion time schedule of each production process

由于車間生產(chǎn)過程步驟較多,工藝流程較為復(fù)雜,因而當(dāng)生產(chǎn)企業(yè)接受多個構(gòu)件需求訂單需同時進(jìn)行生產(chǎn)并準(zhǔn)時完成交付時,會因調(diào)度不當(dāng)存在一些問題,如構(gòu)件進(jìn)入生產(chǎn)線順序混亂,車間共享資源配置不合理、構(gòu)件頻繁更換模板等會造成構(gòu)件在各個環(huán)節(jié)等待時間較長、機(jī)器空載能耗浪費(fèi)等,進(jìn)而影響到交付進(jìn)度,對生產(chǎn)企業(yè)造成一定的損失。因而對預(yù)制構(gòu)件流水車間生產(chǎn)過程進(jìn)行優(yōu)化時,需綜合考慮下列幾個方面:

(1)構(gòu)件等待總時間最短

構(gòu)件經(jīng)過一條流水線上的六道工序依次完成生產(chǎn),但由于每道工序一次只能處理一個構(gòu)件(養(yǎng)護(hù)步驟受養(yǎng)護(hù)窯容量限制除外),若構(gòu)件在某個工作站準(zhǔn)備進(jìn)行處理時,前方有構(gòu)件尚未處理完畢,需等待前方構(gòu)件處理完畢才能進(jìn)行。養(yǎng)護(hù)過程需等待養(yǎng)護(hù)窯存在剩余容量才可進(jìn)入養(yǎng)護(hù)。若構(gòu)件生產(chǎn)調(diào)度安排不合理,會造成生產(chǎn)過程中構(gòu)件空閑等待生產(chǎn)的時間較長,帶來資源浪費(fèi),因而需要盡量減少構(gòu)件的空閑等待時間。

(2)準(zhǔn)時生產(chǎn)

構(gòu)件生產(chǎn)企業(yè)要按照訂單中約定的交貨期進(jìn)行準(zhǔn)時交貨,若生產(chǎn)時間把控不當(dāng)提前將構(gòu)件生產(chǎn)完畢,需在工廠內(nèi)存放直至交貨,從而增大生產(chǎn)企業(yè)的庫存成本;反之若超出交貨期還未進(jìn)行交付,需付一定的違約金。因而構(gòu)件的準(zhǔn)時化生產(chǎn)有利于降低企業(yè)成本。

(3)生產(chǎn)時長最短

生產(chǎn)企業(yè)會存在同時為多個訂單生產(chǎn)預(yù)制構(gòu)件的情況,甚至可能面臨緊急生產(chǎn)任務(wù)。因而在生產(chǎn)時長最小的要求下最大限度的發(fā)揮車間的生產(chǎn)能力,完成快速生產(chǎn)、及時交付的生產(chǎn)任務(wù),有利于減少勞動力、設(shè)備等的浪費(fèi),提升客戶滿意度。

(4)減少構(gòu)件型號變化次數(shù)

不同型號構(gòu)件由于所使用的模具等生產(chǎn)工具不同,若對構(gòu)件生產(chǎn)順序調(diào)配不合理,構(gòu)件型號在同一條流水線上則會頻繁發(fā)生變換,進(jìn)而使得同一型號的構(gòu)件所對應(yīng)的生產(chǎn)工具或設(shè)備等需不斷調(diào)整。這樣不僅增加了工人操作時間,更是降低了生產(chǎn)效率,也為生產(chǎn)車間現(xiàn)場管理加大了難度。因而需要保持各流水線上依次生產(chǎn)的構(gòu)件型號盡量穩(wěn)定不變。

(5)控制生產(chǎn)能耗

生產(chǎn)線上構(gòu)件經(jīng)過每一道工作站時,有其對應(yīng)的機(jī)器對構(gòu)件進(jìn)行處理。生產(chǎn)過程中首先用模臺清理機(jī)對模臺進(jìn)行清理,再用脫模劑噴涂機(jī)向模臺表面均勻噴上脫模劑,并經(jīng)過數(shù)控劃線機(jī)在模臺上全自動劃線。模臺模具等準(zhǔn)備完畢后,將混凝土拌合物運(yùn)送至混凝土布料機(jī)內(nèi),并向模具內(nèi)澆筑混凝土并經(jīng)過振搗機(jī)將混凝土壓實(shí),再使用趕平機(jī)進(jìn)行趕平。澆筑步驟完成后隨即送往預(yù)養(yǎng)護(hù)窯蒸發(fā)構(gòu)件水分,進(jìn)行前期加熱養(yǎng)護(hù)。預(yù)養(yǎng)護(hù)結(jié)束后使用拉毛裝置增大表面摩擦,再用抹光機(jī)對內(nèi)外墻板表面進(jìn)行抹光,送入立體養(yǎng)護(hù)窯完成養(yǎng)護(hù)步驟,加速混凝土硬化至一定的強(qiáng)度,最后使用碼垛車出庫,并用側(cè)力脫膜機(jī)對構(gòu)件進(jìn)行翻轉(zhuǎn)脫模后,使用噴繪儀噴繪產(chǎn)品詳細(xì)參數(shù),最終吊運(yùn)至堆放場地。生產(chǎn)車間為了迎合低碳、綠色的生產(chǎn)趨勢,需盡可能在生產(chǎn)時減少機(jī)器能耗的浪費(fèi)。

2.2 模型的構(gòu)建

假設(shè)某流水作業(yè)車間有n條流水線(N=1,2,…,n)參與生產(chǎn),分別在六道工作站生產(chǎn)m個預(yù)制構(gòu)件(M=1,2,…,m),每條流水線共有T臺機(jī)器(T=1,2,…,t)在生產(chǎn)中用來加工構(gòu)件。現(xiàn)假設(shè)第i條流水線上需生產(chǎn)mi個預(yù)制構(gòu)件,對預(yù)制構(gòu)件生產(chǎn)順序進(jìn)行排序,第j個(j=1,2,…,u)進(jìn)入第i條流水線的構(gòu)件序號為Ni,j,依次進(jìn)入負(fù)責(zé)第k(k≤6)道工序的工作站Mi,k。

第i條流水線上排序?yàn)閖的預(yù)制構(gòu)件進(jìn)入第k道工序的開始時間、生產(chǎn)時間、結(jié)束時間分別表示為S(Ni,j,Mi,k)、Pi,j,k、C(Ni,j,Mi,k)。預(yù)制構(gòu)件的交貨日期為Di,j,假設(shè)延期完工的賠率為δi,j,提前完工導(dǎo)致的庫存費(fèi)率為γi,j。

目標(biāo)函數(shù):

(1)預(yù)制構(gòu)件在生產(chǎn)過程中等待總時間最短:

(2)預(yù)制構(gòu)件未準(zhǔn)時生產(chǎn)造成的損失最少:

(3)預(yù)制構(gòu)件生產(chǎn)總時長最短:

(4)預(yù)制構(gòu)件在流水線上類型變化程度最小:

其中,ETf和EQf分別表示預(yù)制構(gòu)件種類和變化次數(shù)的一致性,數(shù)值越小,表示構(gòu)件變化程度越小,有利于提高生產(chǎn)率。Ti,f和Qi,f分別表示第i條生產(chǎn)線上的預(yù)制構(gòu)件種類數(shù)和變化次數(shù)。式(5)表示預(yù)制構(gòu)件的一致性可以通過求解單流水線一致性幾何均值得出。

(5)生產(chǎn)過程中機(jī)器的能源消耗最小:

式(6)表示生產(chǎn)過程中機(jī)器的總能源消耗主要包括機(jī)器加工時產(chǎn)生的能量以及機(jī)器空載時產(chǎn)生的能量。其中EZ表示機(jī)器加工時的總能耗,EQ則表示空載時的總能耗。表示第i條流水線上排序?yàn)閖的構(gòu)件在機(jī)器r上的加工時間;Pr表示機(jī)器r的運(yùn)行功率,PDr表示機(jī)器r的空轉(zhuǎn)功率。

約束條件:

式(9)分別表示工序和工作站之間的緊前緊后約束;式(10)表示工序3和工序4加工過程不可間斷;式(11)表示相關(guān)取值范圍;式(12)表示澆筑工序約束,式(13)表示養(yǎng)護(hù)工序約束;式(14)表示其他工序約束。

其中:

式中D表示工作的天數(shù),為正常工作時間;HN為非正常工作時間;HA為允許加班時間(HA＜HN)。

在實(shí)際生產(chǎn)過程中,預(yù)制構(gòu)件的生產(chǎn)都需要借助模具才能完成。由于同類型模具數(shù)量有限,且模具為所有流水線的共享資源,因而引入生產(chǎn)優(yōu)先級的概念。生產(chǎn)優(yōu)先級高的構(gòu)件優(yōu)先生產(chǎn)并優(yōu)先占用共享資源,模具按照構(gòu)件的優(yōu)先級進(jìn)行分配,構(gòu)件養(yǎng)護(hù)則需等待養(yǎng)護(hù)室存在空閑容量才可進(jìn)入。

式(15)則表示模具等待的約束,即第i條流水線上排序?yàn)閖的構(gòu)件ω使用α型模具應(yīng)等待有同等類型模具釋放之后再開始。其中l(wèi)表示ω在全部構(gòu)件中的生產(chǎn)排序,lα表示ω在所有使用α型模具構(gòu)件中的生產(chǎn)排序,α型模具的數(shù)量為Xα,g(α,l,lα,Xα)表示第lα-Xα到第lα-1個α型模具釋放的時間集合。

養(yǎng)護(hù)工序需要在前面構(gòu)件養(yǎng)護(hù)完成后才可繼續(xù),式(16)則表示養(yǎng)護(hù)窯容量限制約束,即第i條流水線上排序?yàn)閖的構(gòu)件養(yǎng)護(hù)的開始需等待前序生產(chǎn)中有構(gòu)件結(jié)束才可進(jìn)行。其中β表示養(yǎng)護(hù)室容量約束,h(j,β)表示第j-β到第j-1個構(gòu)件養(yǎng)護(hù)結(jié)束的時間集合。

3 基于第三代非支配排序遺傳算法求解構(gòu)件生產(chǎn)調(diào)度問題

3.1 NSGA-Ⅲ算法概述

一直以來,多目標(biāo)進(jìn)化算法(EMOA)在解決兩目標(biāo)和三目標(biāo)優(yōu)化問題時,均可以在這類問題上找到收斂性、分布性良好的解集。但是在大多數(shù)現(xiàn)實(shí)問題中,經(jīng)常同時存在四個甚至更多優(yōu)化目標(biāo)。因此處理高維多目標(biāo)的優(yōu)化已經(jīng)成為現(xiàn)今多目標(biāo)進(jìn)化算法的重要研究方向[27]。而基于參考點(diǎn)選擇的NSGA-Ⅲ算法能夠很好的解決在高維多目標(biāo)優(yōu)化時遇到的問題,通過對NSGA-Ⅲ算法的中的擁擠度選擇算子進(jìn)行替換,在生成均勻參考點(diǎn)之后,基于參考點(diǎn)使用最小生境選擇機(jī)制在快速非支配排序后選擇優(yōu)良個體,能夠有效保證算法的多樣性和收斂性[28]。

3.2 NSGA-Ⅲ算法步驟

NSGA-Ⅲ的算法步驟與NSGA-II的框架大致相同,都是通過快速非支配排序?qū)⒎N群個體進(jìn)行分層,分別進(jìn)入不同的非支配層級。不同點(diǎn)在于NSGA-II的是用擁擠度和擁擠度比較算子來進(jìn)行選擇,而NSGA-III是利用良好分布的參考點(diǎn)來保持種群的多樣性。NSGA-Ⅲ的一般步驟如下:

(1)第一步 初始化

初始化均勻參考點(diǎn)Zs,同時隨機(jī)產(chǎn)生規(guī)模為N的初始種群Pt,初始種群Pt通過選擇、交叉、變異生成種群Qt。并將種群Pt和Qt合并,產(chǎn)生規(guī)模為2N的新種群Rt。

(2)第二步 快速非支配排序

對種群Rt使用基于帕累托理論的快速非支配方法進(jìn)行排序,以此類推構(gòu)造出包含不同等級的非支配解集F={F1,

F2,…,Fn}。

(3)第三步 選擇個體

從非支配解集F中第一層F1開始,初始化St=?,令St=St∪F1,如果此時St依舊小于N,則繼續(xù)添加非支配集中的下一層F2,直到執(zhí)行St=St∪Fl后存在,此時對Fl層使用基于均勻參考點(diǎn)的小生境選擇方法進(jìn)行選擇,直到

(4)第四步 目標(biāo)函數(shù)標(biāo)準(zhǔn)化

計算MX個目標(biāo)函數(shù)中每一個目標(biāo)維度i上的最小值,即第i個目標(biāo)上對應(yīng)的最小數(shù)值為Zi,數(shù)值構(gòu)成當(dāng)前種群的理想點(diǎn)集合,再根據(jù)標(biāo)準(zhǔn)化公式將理想點(diǎn)變?yōu)樵c(diǎn)。標(biāo)準(zhǔn)化公式如公式(19)所示。

找出式(20)中數(shù)值最小的個體在不同維度上的極值點(diǎn),使用極值點(diǎn)可以確定一個超平面,再根據(jù)超平面與各個坐標(biāo)軸的交點(diǎn)所對應(yīng)的函數(shù)值算出對應(yīng)坐標(biāo)軸上的截距,截距即為極值點(diǎn)在對應(yīng)坐標(biāo)軸上的坐標(biāo)值ai,最后進(jìn)行標(biāo)準(zhǔn)化操作,如公式(21)所示。

(5)第五步 關(guān)聯(lián)操作

在對空間內(nèi)的每個目標(biāo)進(jìn)行自適應(yīng)歸一化操作后,將種群St中每一個個體與參考點(diǎn)進(jìn)行關(guān)聯(lián)。將參考點(diǎn)與原點(diǎn)相連來定義與超平面上每個參考點(diǎn)相對應(yīng)的參考線。然后從每個參考線計算到種群中每一個個體的距離。在歸一化的目標(biāo)空間中最接近個體的參考點(diǎn)被視為與該個體相關(guān)聯(lián)。

(6)第六步 參考點(diǎn)選擇機(jī)制篩選子代與去除參考點(diǎn)

將參考點(diǎn)集合中每一個參考點(diǎn)j定義一個小生境數(shù)ρj,種群St中與參考點(diǎn)關(guān)聯(lián)的個體數(shù)量記錄為小生境數(shù)ρj的值,之后將具有最小生成鏡數(shù)的參考點(diǎn)選出記錄為,計算當(dāng)前種群中與參考點(diǎn)k的關(guān)聯(lián)個體數(shù)I。

判斷I的值,如果等于0則重新選擇當(dāng)前種群中其他小生境數(shù)最小的點(diǎn)作為,如果I不等于0,判斷ρ等于0時選擇與參考點(diǎn)關(guān)聯(lián)個體中與參考線距離最小的個體加入下一代種群Pt+1,否則就隨機(jī)選取一個個體加入到下一代種群Pt+1,重復(fù)以上操作直到滿足種群規(guī)模N為止。

3.3 編碼設(shè)計

遺傳算法的編碼是整個算法執(zhí)行的基礎(chǔ)。本實(shí)驗(yàn)的優(yōu)化變量是裝配式預(yù)制構(gòu)件生產(chǎn)優(yōu)先級l及負(fù)責(zé)對其加工的流水線編號i,因此本實(shí)驗(yàn)采用了雙染色體編碼策略,2條染色體分別針對構(gòu)件和流水線進(jìn)行編碼,用于確定一個生產(chǎn)任務(wù)中構(gòu)件的生產(chǎn)順序和流水線分配。構(gòu)件生產(chǎn)優(yōu)先級染色體通過一個1×m的矩陣構(gòu)建,矩陣中每一位的數(shù)字al代表對應(yīng)編號的預(yù)制構(gòu)件,每一位的列號l代表預(yù)制構(gòu)件的生產(chǎn)優(yōu)先級。其中a∈[1,2,…,m],m為本次生產(chǎn)任務(wù)的預(yù)制構(gòu)件的數(shù)量。流水線分配染色體同樣通過一個1×m的矩陣構(gòu)建,矩陣中每一位的數(shù)字bl代表負(fù)責(zé)生產(chǎn)構(gòu)件al的流水線編號。其中b∈[1,2,…,n],n代表工廠中負(fù)責(zé)加工預(yù)制構(gòu)件的流水線數(shù)量。

3.4 初始解的生成

種群初始化影響著整個遺傳算法的性能。遺傳算法的初始種群一般是隨機(jī)生成的,為了提高初始解的質(zhì)量,此處對初始種群進(jìn)行了改進(jìn)。初始化種群后,將生產(chǎn)過程中等待總時間的倒數(shù)作為適應(yīng)度對初始種群進(jìn)行評價,依據(jù)設(shè)置的修復(fù)規(guī)模λ,挑選適應(yīng)度最低的λ個體對解進(jìn)行檢查及修正。修正流程如下:

(1)假設(shè)待生產(chǎn)構(gòu)件中使用α類模具的構(gòu)件數(shù)量為ε1,用于生產(chǎn)該類型構(gòu)件的模具數(shù)量為ε2,則可通過模具數(shù)量與待生產(chǎn)構(gòu)件數(shù)的差值判斷是否可能因?yàn)槟＞卟蛔阍斐傻却?即εt=ε1-ε2,如果滿足εt＞0則將模具類型代碼加入矩陣o。并將矩陣o中元素依據(jù)εt的值降序排列。

(2)依據(jù)矩陣o中的元素,依次比對當(dāng)前生產(chǎn)優(yōu)先級矩陣J1中對應(yīng)的構(gòu)件類型,并且按照構(gòu)件類型將前ε2個構(gòu)件編號順序加入矩陣J2中,之后的εt個構(gòu)件加入矩陣J3中,對應(yīng)的構(gòu)件編號加入J2或J3后同時從J1刪除。之后將矩陣J2、J3與J1合并產(chǎn)生新的生產(chǎn)優(yōu)先級矩陣(如圖3所示),從而完成對生產(chǎn)序列的修正。

圖3 優(yōu)先級矩陣的生成Figure 3Generation of priority matrix

(3)對比調(diào)整后的解與初始解的適應(yīng)度,若調(diào)整后的解優(yōu)于初始解則替換,否則仍保留初始解。循環(huán)操作直至將所有選中的劣解都得到替換,可提高初始解的質(zhì)量,加快收斂速度。

此外,對決定流水線分配的染色體采取負(fù)載均衡的措施,一方面優(yōu)先將構(gòu)件分配進(jìn)入累計加工時間最短的流水線,另一方面盡可能地優(yōu)先使構(gòu)件被分配進(jìn)入已有相同構(gòu)件類型的流水線中。

3.5 遺傳操作

(1)交叉

構(gòu)件優(yōu)先級染色體進(jìn)行交叉操作,其過程是選擇一對染色體作為父代,隨機(jī)生成它的起止點(diǎn),并使2條父代染色體使用相同的起止點(diǎn),之后將父代中兩條染色體起止點(diǎn)內(nèi)的基因進(jìn)行交換,如圖4所示。由于本實(shí)驗(yàn)采用的排列編碼要求染色體內(nèi)的每一位不能出現(xiàn)重復(fù),因此交換后需要根據(jù)交換的兩組基因建立映射關(guān)系,如圖5所示。映射關(guān)系表明,交叉后的子代染色體中存在2個基因4,2個基因8。根據(jù)映射關(guān)系將染色體中重復(fù)的基因進(jìn)行轉(zhuǎn)換,直到染色體內(nèi)沒有重復(fù)的基因?yàn)橹?。這樣所有的沖突基因都會被修正,保證了子代染色體基因無沖突。

圖4 交叉算子Figure 4Crossover operato

圖5 映射關(guān)系Figure 5Mapping relationships

(2)變異

首先以設(shè)定好的變異概率判斷種群中的所有個體是否發(fā)生變異。其次判斷構(gòu)件生產(chǎn)優(yōu)先級的染色體。由于構(gòu)件編碼不可重復(fù),本文采取互換法進(jìn)行處理,即隨機(jī)選擇2個位點(diǎn),將基因進(jìn)行互換。最后,對于決定流水線分配的染色體,對隨機(jī)指定某一位或某幾位基因座上的值進(jìn)行變異運(yùn)算。

4 案例分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文以安徽省某裝配式建筑生產(chǎn)企業(yè)預(yù)制構(gòu)件生產(chǎn)車間的調(diào)研數(shù)據(jù)為例進(jìn)行實(shí)證分析。表1記錄了隨機(jī)選取的十個構(gòu)件關(guān)于構(gòu)件類型、模具尺寸類型及其數(shù)量、各道工序所需時間、交付時間和懲罰系數(shù)等相關(guān)數(shù)據(jù)。

表1 生產(chǎn)調(diào)度模型相關(guān)數(shù)據(jù)Table 1Relevant data of production scheduling model

其中每個工作日的正常工作時間(HW)和非正常工作時間(HN)根據(jù)生產(chǎn)情況分別設(shè)置為8小時和16個小時,允許加班時長不得超過4個小時。養(yǎng)護(hù)室養(yǎng)護(hù)預(yù)制構(gòu)件的容量為4件。構(gòu)件在生產(chǎn)過程中在每一個機(jī)器上的生產(chǎn)時間及其所用機(jī)器的功率如表2所示。

表2 構(gòu)件在各個機(jī)器上的生產(chǎn)時間及機(jī)器功率Table 2Production time and machine power of components on each machine

4.2 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證NSGA-Ⅲ算法的有效性,本文同時選取了SPEA2[29]、NSGA-Ⅱ、NSGA-Ⅲ三種算法,對構(gòu)件生產(chǎn)多目標(biāo)模型進(jìn)行優(yōu)化并對實(shí)證結(jié)果進(jìn)行比較。其中NSGA-Ⅱ、NSGA-Ⅲ算法分別使用二項(xiàng)式分布交叉算子和高斯變異算子,SPEA2使用二項(xiàng)式分布交叉算子。

本實(shí)驗(yàn)中三種算法參數(shù)如表3所示,實(shí)驗(yàn)時迭代次數(shù)分別為50、100和200次。使用Python3.7.4進(jìn)行編程,運(yùn)行程

表3 不同算法的參數(shù)設(shè)置Table 3Parameter settings of different algorithms

序的計算機(jī)CPU型號為Intel Xeon E3-1231 v3,主頻3.4GHz,內(nèi)存16G?；谏鲜鰯?shù)據(jù)對SPEA2、NSGA-Ⅱ、NSGA-Ⅲ三種算法進(jìn)行程序編寫,隨機(jī)生成不同流水線數(shù)量、不同構(gòu)件數(shù)量及不同模具數(shù)量的3個案例,分別得到三種算法的調(diào)度方案,表中2?10?(3?2?3)表示案例規(guī)模為2條流水線上生產(chǎn)10個構(gòu)件,ABC三種模具數(shù)分別為3個、2個、3個。

本實(shí)驗(yàn)生成流水線、構(gòu)件數(shù)、ABC三種模具數(shù)量為2?10(3?2?3)、迭代次數(shù)200代的規(guī)模下使用NSGA-Ⅲ算法的構(gòu)件生產(chǎn)甘特圖(見圖6所示),相應(yīng)的目標(biāo)函數(shù)值為f(x1)=302.10 h,f(x2)=642.6 ￥,f(x3)=78.5 h,f(x4)=6,f(x5)=10286.06 kw·h。并且給出NSGA-Ⅲ算法3個目標(biāo)維度的Pareto前沿,如圖7所示,形成的帕累托曲面較為明顯(由于目標(biāo)函數(shù)數(shù)量較多,Pareto解集構(gòu)成超曲面,難以直觀的表示出來,因此選取三個目標(biāo)函數(shù)構(gòu)成三維Pareto前沿表示[30])。

圖6 NSGA-Ⅲ最優(yōu)調(diào)度甘特圖Figure 6NSGA-Ⅲ optimal scheduling Gantt chart

圖7 三個維度下不同目標(biāo)函數(shù)的Pareto前沿Figure 7Pareto frontier with different objective functions in three dimensions

4.3 算法結(jié)果對比

為了直觀的表示不同算法對模型優(yōu)化后結(jié)果的分布情況和優(yōu)化的有效性,圖8用箱線圖描述了三種算法不同目標(biāo)函數(shù)的優(yōu)化結(jié)果?？梢钥闯?NSGA-Ⅲ算法的優(yōu)化結(jié)果在5個目標(biāo)函數(shù)上聚集區(qū)間均為最大,在生產(chǎn)總時長、未準(zhǔn)時生產(chǎn)造成的損失、變化程度和能源消耗這幾個目標(biāo)函數(shù)上,最小值均低于其他對比算法的優(yōu)化結(jié)果。分析結(jié)果說明三種算法的解有顯著差異,NSGA-Ⅲ算法的求解質(zhì)量較好,獲得的解集分布更加均勻、廣泛,能為決策者提供更為全面、合理的待選方案。

圖8 不同目標(biāo)函數(shù)的優(yōu)化結(jié)果Figure 8Optimization results of different objective functions

實(shí)驗(yàn)將三種算法在2?10?(3?2?3)、3?20?(6?4?6)、4?30?(13?6?9)三種不同案例規(guī)模以及不同迭代次數(shù)下的運(yùn)行時間、反映解集收斂性的分布性評價指標(biāo)(Spacing,SP)[31]以及評價解集分布性的超體積指標(biāo)(HV,Hypervolume)[32]進(jìn)行對比以體現(xiàn)三種不同算法對案例求解時的差異。為避免算法單次運(yùn)行結(jié)果的隨機(jī)不確定性,實(shí)驗(yàn)中將三個算法在不同迭代次數(shù)的情況下獨(dú)立運(yùn)行20次,求取指標(biāo)的平均值,表4記錄了三種算法的運(yùn)行時間對比,表5和表6分別表示算法得到的Pareto解集分布性評價指標(biāo)和超體積指標(biāo)的對比情況。

從表4的相關(guān)數(shù)據(jù)可以得出,NSGA-Ⅲ算法在不同案例規(guī)模和迭代次數(shù)情況下,運(yùn)行時間均比NSGA-Ⅱ和SPEA2短,算法最小運(yùn)行時間為1.702秒,最大運(yùn)行時間16.468秒,遠(yuǎn)小于其他對比算法的1.857秒和19.557秒,差距超過10%。一般來說預(yù)制構(gòu)件生產(chǎn)廠從接受訂單到安排生產(chǎn)之間有較長的時間間隔,故NSGA-Ⅲ算法在對生成方案優(yōu)化時足以滿足實(shí)際情況下工廠對程序運(yùn)算時間的要求。表5中NSGA-Ⅲ的分布性評價指標(biāo)SP相較于對比算法有較強(qiáng)的優(yōu)勢,表明NSGA-Ⅲ在所得Pareto解集能更好的分布于解空間,解集的分布性更好。在收斂性方面根據(jù)超體積指標(biāo)HV進(jìn)行對比,HV值越大代表算法收斂性和多樣性越好,從表6可看出,NSGA-Ⅲ的HV基本高于NSGA-Ⅱ和SPEA2,表明NSGA-Ⅲ得到的Pareto解集可以較好的收斂到理想的Pareto前沿,并且具有更好的解集多樣性。

表4 算法運(yùn)行時間對比Table 4Comparison of algorithm running time

表5 分布性評價指標(biāo)SP對比Table 5Comparison of distribution evaluation index SP

表6 超體積指標(biāo)HV對比Table 6Comparison of supervolume index HV

5 結(jié)論

本文對裝配式建筑預(yù)制構(gòu)件的生產(chǎn)過程進(jìn)行了深入的分析,通過調(diào)研發(fā)現(xiàn)實(shí)際生產(chǎn)過程需綜合考慮多方面的因素來提高生產(chǎn)企業(yè)的效益,因而本文針對構(gòu)件流水車間生產(chǎn)流程的優(yōu)化問題做出以下研究:

(1)本文設(shè)置了多條流水線的車間生產(chǎn)模式,讓不同類型的構(gòu)件通過合理調(diào)度安排進(jìn)入指定的生產(chǎn)線并按照一定的排序進(jìn)行混合生產(chǎn),在模具共享資源數(shù)量約束和養(yǎng)護(hù)窯容量約束的前提下,建立了考慮構(gòu)件等待總時間、生產(chǎn)總時長、提前或滯后交貨成本、構(gòu)件型號變換程度及車間機(jī)器能耗的多目標(biāo)模型。

(2)在求解構(gòu)建的高維多目標(biāo)生產(chǎn)調(diào)度模型時,采用了優(yōu)化初始種群的NSGA-Ⅲ算法對其進(jìn)行求解。通過對比發(fā)現(xiàn)NSGA-Ⅲ在求解高維多目標(biāo)優(yōu)化問題上的算法性能優(yōu)于NSGA-Ⅲ和SPEA2兩種算法,驗(yàn)證了該算法可以求解出較優(yōu)的調(diào)度方案。

(3)本文以安徽省某裝配式建筑生產(chǎn)企業(yè)預(yù)制構(gòu)件生產(chǎn)車間的調(diào)研數(shù)據(jù)為例進(jìn)行實(shí)證分析,對不同流水線數(shù)量、不同構(gòu)件數(shù)量及不同模具數(shù)量的多個案例進(jìn)行測試,實(shí)驗(yàn)表明本文構(gòu)建模型的有效性,以及采用的NSGA-Ⅲ算法能較為穩(wěn)定的在不同案例中有效減少實(shí)際生產(chǎn)過程中的空閑等待時間,縮短工期,減少不同類型構(gòu)件的頻繁變換、降低成本和機(jī)器能耗。

因而,本文提出的高維多目標(biāo)生產(chǎn)調(diào)度模型以及優(yōu)化算法對預(yù)制構(gòu)件生產(chǎn)企業(yè)的生產(chǎn)實(shí)踐起一定的指導(dǎo)性意義。第一,生產(chǎn)企業(yè)可通過高維多目標(biāo)模型中的生產(chǎn)調(diào)度計劃合理安排共享資源、優(yōu)化排產(chǎn)順序,提高生產(chǎn)效率,降低生產(chǎn)成本。第二,生產(chǎn)企業(yè)可對生產(chǎn)進(jìn)度進(jìn)行控制,實(shí)現(xiàn)生產(chǎn)全過程的生產(chǎn)進(jìn)度監(jiān)控,保證生產(chǎn)廠能完成構(gòu)件的準(zhǔn)時交付。第三,生產(chǎn)企業(yè)可通過合理調(diào)度,根據(jù)不同的生產(chǎn)需求量對車間的生產(chǎn)能耗進(jìn)行動態(tài)控制,進(jìn)一步降低能耗成本,迎合綠色生產(chǎn)的發(fā)展趨勢。