預制構件流水車間訂單接受與調度的集成優化

熊福力, 儲夢伶

(西安建筑科技大學 信息與控制工程學院,陜西 西安 710055)

0 引言

裝配式建筑在城市可持續發展方面具有非常明顯的優勢，預制構件生產是裝配式建筑行業發展的關鍵，對于提高裝配式建筑生產效率和降低能耗，具有重要的現實意義。但預制構件的生產處理過程相比于傳統流水車間調度問題更加復雜。迄今為止，預制構件生產調度方面已有較多研究[1～3]，但均是假定訂單固定的情況下對工件生產做出調度決策，而未考慮預制構件生產能力限制和客戶交貨期要求。在日益激烈的預制構件生產競爭環境下，為避免過高的懲罰費用并追求利潤最大化，預制構件制造商通常在計劃周期前并不盲目接受所有訂單，而是需要根據預制構件企業實際生產能力和訂單交貨期等實際情況，對訂單做出選擇，選擇那些可以獲得更多利潤的訂單，進而安排訂單生產調度。因此該問題比傳統預制生產調度問題更為復雜，需要對訂單選擇和生產調度做出綜合決策，從而增加預制構件制造企業總利潤和客戶滿意度，我們將此問題稱為預制構件訂單接受與調度問題(Order acceptance and scheduling under precast production environments, OAS_PPE)。

對于訂單接受與調度問題，Rom和Slotnick[4]研究了單機環境下帶拖期懲罰的訂單接受與調度問題。Chen，Lu和Yang[5]提出混合進化算法下生產調度的并行優化，其目標函數是最小化順序相關的過渡成本和非執行處罰。Nobibon和Leus[6]求解了單機環境下訂單接受與調度問題的精確算法。王柏琳等[7]研究了置換流水車間對工件拒絕和工件調度的聯合決策。以上研究均是基于單機調度或者傳統置換流水車間調度環境。雖然訂單接受與調度問題在實際預制構件生產管理過程中時有發生，但這方面的相關研究尚未見報導。

本文針對OAS_PPE問題，以凈利潤最大化為目標，根據預制構件企業實際生產能力和客戶交貨期要求，同時對訂單選擇和生產調度進行決策。與已有的OAS研究不同的是[8～11]，預制構件生產過程由于存在可中斷和不可中斷，串行和并行工序并存等復雜工況特點，使得OAS_PPE問題是比傳統流水車間調度問題更為復雜的多決策離散集成優化問題，同時由于工藝約束中帶有高度非線性，因此難以利用傳統的流水車間調度模型及方法進行有效求解。

近年來，遺傳算法(Genetic algorithm, GA)、禁忌搜索(Tabu search, TS)、混合遺傳-禁忌搜索(Hybrid GA and TS，GA_TS) 和迭代貪婪(Iterated greedy algorithms, IG)等智能優化算法在求解流水車間調度問題上取得了很多成功應用[12～14]。其中IG算法占有較為明顯的優勢[13,14]。Ruzi等[13]設計了分布式置換流水車間調度問題的迭代貪婪方法。Ribas等[14]針對有阻塞流水車間調度問題提出了一種迭代貪婪算法，在計算時間和求解質量上取得了較好的效果。鑒于此，本文將通過深入挖掘特定問題性質，集成構造啟發式、鄰域搜索結構以及破壞-構造機制，提出有效的混合迭代貪婪搜索框架，克服整數變量、多決策屬性和大量非線性復雜約束帶來的求解困難，有效提升求解質量和搜索效率，并有望顯著改善預制構件制造企業的凈利潤。

1 OAS_PPE問題描述與模型建立

1.1 問題描述

預制構件生產流程要依次經過模具組裝、預埋件安裝、澆筑、養護、拆模以及精加工六道工序，具有流水生產特點，但與傳統流水線不同的是，預制構件生產流水線具有串并行混合生產的特點，在蒸汽養護階段，多個蒸汽養護室可以同時對多個工件進行并行處理，而其他五個生產階段則屬于串行生產階段，同一時刻只能處理一個訂單任務。同時從預制構件生產實際出發，考慮了每天12個小時的非工作時間，這個時間段內需要工人參與的生產過程將無法進行，而傳統的流水生產過程通常假設一天24小時均可以利用；預制構件各個生產過程具有可中斷和不可中斷混合生產的特點，在澆筑階段，一旦開工，則不允許中斷；在模具組裝、預埋件安裝、拆模以及精加工等生產階段，如果在加班之后還無法完成，則允許中斷，未完成的工作將推遲到下一個工作日完成，而傳統的流水生產過程則假設各個階段的生產過程是不可間斷的。

基于以上預制構件生產背景，本文所研究的OAS_PPE問題可描述如下：預制構件制造企業共收到J個訂單，記為J= {1,2,…,J}。在該計劃周期結束前不插入其他生產計劃。通常由于交貨期要求和生產能力限制，為減少由于訂單拖期導致的高額懲罰費用，預制構件制造商必須選擇性接受訂單以獲取更多利潤。其中Tj:max{0,Cj,6-d}表示訂單j的拖期時間。如果接受訂單j，則訂單j的凈利潤為Qj-wjTj。企業需要同時確定接受的訂單集合與生產排序，從而最大化總凈利潤。

1.2 數學模型

1.2.1 參數及變量說明

(1)模型標引及參數

(2)決策變量

yj為二進制變量，如果訂單j被接受，yj為1，否則為0；xj,[k]為二進制變量，如果訂單j被接受并分配至調度序列的第k個位置，xj,[k]為1，否則為0；Cj,s為訂單j第s道工序的完工時間；C[k],s為訂單序列第k個位置訂單第s道工序的完工時間；Tj為訂單j的拖期時間，Tj:=max{0,Cj,6-d}；A[k],s為訂單調度序列第k個位置第s道工序的累計完工時間；D[k],s為訂單調度序列第k個位置第s道工序的累計工作天數。

1.2.2 混合整數非線性規劃模型

以最大化凈利潤為目標，可建立OAS_PPE優化模型如下:

優化目標:

(13)

其中，式(1)表示模型的目標為最大化總凈利潤；式(2)定義訂單的拖期時間，其中M為非常大的正常數；式(3)約束每個被接受的訂單都分配至工件序列中的一個位置；式(4)限制每個調度序列位置最多被分配一個訂單；式(5)計算累計工作天數；式(6)計算第k個位置訂單在第s個階段的累計完成時間，即串行情況下第k個位置訂單在第s道工序的的最早完成時間；式(7)計算訂單在調度序列第k個位置的訂單第1，2，5，6道工序的完工時間，這四道工序均為可間斷工序，若不能在規定的工作時間內完成，可將未完成的部分移至下一個階段完成；式(8)計算調度序列第k個位置的訂單在澆筑工序(第3道工序)的完工時間，由于澆筑工序的不可間斷性，因此該工序若不能在包含加班的時間段內完成，則需推遲到下一個工作日進行；式(9)計算調度序列第k個位置的訂單在養護工序(第4道工序)的累計完成時間。式(10)為養護工序，其具有不可中斷性和并行性，并且不需人工看護，因此該工序完工時間計算有以下兩種情況：若養護工序可在包含加班的時間內完成, 則完工時間即為該工序開工時間加處理時間。若養護工序在夜間完成，其完工時間視為下一個工作日的開始時間。式(11)～(13)定義了各決策變量的取值范圍。需要指出的是，該模型中既包括連續變量又包括離散變量，需要對訂單選擇和訂單調度進行集成決策。從目標函數角度看，含有變量乘積的形式；從約束角度看，該模型中既包括線性約束，也包括復雜的非線性約束，如式(5)～(8)。加之OAS_PPE問題本身固有的NP-難性，因此該模型難以利用現有優化軟件進行直接求解。

2 算法

由于傳統的預制構件生產調度或者流水車間調度方面的研究一般僅限于對機器上工件排序進行單一決策研究[13,14]，因此其相關調度算法很難直接應用到OAS_PPE問題上，在這種情況下需要根據問題特點設計特定算法。本節通過集成特定問題知識、構造啟發式、局部搜索和破壞-構造機制，提出了一種有效的混合加速迭代貪婪搜索框架。基于該框架，結合后插入操作和前后混合式插入操作，提出了兩種混合加速迭代貪婪搜索算法。

2.1 混合加速迭代貪婪搜索

本文所提出的混合加速迭代貪婪框架如算法1所示。其基本步驟如下：(1)通過構造啟發式NEH算法[15]產生一個完整的訂單調度序列作為初始解；(2)通過兩階段局部搜索方法改進初始解；(3)通過破壞和加速構造對當前解進行攝動；(4)對得到的新解再次利用兩階段局部搜索方法進行搜索得到新解。對步驟(3)和(4)交替運行直到滿足終止條件。

算法1(混合加速迭代貪婪搜索)輸入:實例數據和算法參數輸出:構造性序列π?和最優目標函數值TNR(π?)1π0←初始解2π?←TLS(π0)%利用算法33對π?執行破壞策略,即從π?中隨機選擇d個訂單組成πd;πR則為除去d個訂單后剩余的訂單組成的調度序列4πR←利用加速構造策略在πR的最佳位置插入πdi使目標值TNR最大5π2←TLS(πR)%利用算法36如果TNR(π?)

下面針對構造啟發式、兩階段局部搜索以及破壞和構造機制等關鍵部件進行介紹。

(1)構造啟發式產生初始解

通過構造啟發式NEH算法(算法2)產生一個較好的完整的訂單調度序列作為初始解。

算法2(初始解的產生)輸入:實例數據和算法參數輸出:構造性序列π0和其所對應目標值TNR(π0)1pj=∑s∈kpj,s2設置π1←Ф,π2←Ф,πa←Ф,πb←Ф,πc←Ф,πd←Ф3π1←(πp1,…,πpj,…,πpJ),一批訂單按Pj非遞增排序π2←(πQ1,…,πQj,…,πQJ),一批訂單按Qj非遞減排序4πa←(πp1,πp2),πb←π1πaπc←(πQ1,πQ2),πd←π2πc5πa←在πa的最佳位置插入πbj使得TNR值最大πc←在πc的最佳位置插入πdj使得TNR值最大6如果TNR(πa)>TNR(πc),則π0←πa否則π0←πc7返回π0,TNR(π0)

(2)兩階段局部搜索

為提高個體局部搜索能力，設計了基于交換操作的兩階段局部搜索方法(算法3)，包括訂單交換階段和訂單回插階段。在訂單交換階段，調度序列中隨機選擇兩個訂單進行交換操作，通過判斷交換后的序列中每個訂單完成時間是否超過截止日期，確定接受集與拒絕集。與傳統局部搜索不同的是，本文局部搜索基于OAS問題特點，在執行交換操作之后，并不直接進行目標函數評估，而是進一步將拒絕集的訂單逐步插入到使TNR最大位置的接受集中，并與初始序列目標值比較，我們將該階段簡稱為回插階段。以上過程重復進行，直至局部搜索達最大迭代次數。

算法3兩階段局部搜索輸入:實例數據,算法參數,一組訂單序列π=(π1,π2,…,πj,…,πJ),最大迭代次數Iter輸出:最優解π?和最優目標函數值TNR(π?)1π?←初始解2在調度序列π?隨機選擇兩個位置的訂單進行交換生成一個新的序列π1=(π1′,π2′,…,πk′,…,πJ′)3設置πa←Ф和πr←Ф4計算π1中πk′的完工時間C[k]5如果C[k]TNR(π?),則π?←πa8返回π?,TNR(π?)

(2)破壞和加速構造機制

在迭代貪婪算法中，從序列π*中隨機抽取d個訂單組成訂單抽取序列πd。抽取訂單后剩余的訂單序列為πR。在傳統IG算法[13,14]的構造階段，需將破壞訂單集合πd中的訂單依次插入剩余訂單集合πR的所有位置并計算目標值以便找出最佳插入位置，由于此過程需遍歷πR的所有位置，因此該操作是導致IG算法運行效率降低的主要原因之一。為克服該困難，首先給出如下性質：

性質1在一個訂單序列π=(π1,π2,…,πk,…,πJ)中，如果在第[k]個位置的訂單完工時間超過其截止日期，則該訂單插入到當前位置之后的所有位置均會超過截止日期，因此被拒絕。

利用該性質可得加速構造策略1如下：

基于性質1和2可得加速構造策略2如下：

加速構造策略2(Speedup Strategy 2, SS2)：在HIG算法重構造階段，將某個訂單j插到剩余訂單集合的最后一個位置[k]構成新的調度序列。若滿足≥C[k],6,則停止將此訂單插入到這組訂單排列順序的其它位置。若不滿足，則執行加速構造策略1。

基于迭代貪婪搜索框架，分別結合SS1和SS2提出了兩種迭代加速貪婪搜索算法，在這里命名為HIG_SS1和HIG_SS2。采用傳統構造方法的混合迭代貪婪搜索算法命名為HIG。在下一節中，我們將驗證它們的有效性。

3 實驗仿真與結果分析

3.1 算例生成與算法參數設置

訂單數目J從集合{20, 30, 50, 70}中選取。為保證訂單的多樣性和差異性，針對不同規模訂單，不同種類預制構件各隨機生成10個不同組合的算例。各個生產階段的處理時間及拖期懲罰采用文獻[1]中的測試數據。本文算法基于Matlab 2016a在處理器Intel(R) Core (TM) i7-8550U CPU @1.80 GHZ 199GHZ內存為8GB的個人計算機上實現。為便于比較算法，我們還分別設計了適用于OAS_PPE問題的GA、TS和HGA_TS。其中HGA_TS算法是將遺傳算法搜索到的相對較好解作為禁忌算法的初始解進行尋優，通過兩種算法的交替迭代進行解的更新。通過田口方法調節算法參數，優化后的各算法參數如表1所示。其中d為破壞階段抽取工件個數；TL為禁忌表長度；α為HGA_TS中GA與TS運行時間占比；SN為鄰域長度；PS為種群規模；pc與pm分別為交叉率與變異率。

表1 算法參數設置

3.2 算法對比分析

本文中，不同規模的訂單各取十組算例，每組算例運行20次。對于同一規模算例，為公平比較，所有算法均采用相同的運行時間。由于傳統預制構件生產調度問題多以GA作為求解方法，因此本文以GA為基準算法，定義相對GA改進率如下：

運用上式，可以針對某一算例l計算各算法相對于GA的改進率。

表2給出了不同訂單規模情況下不同算法相對于GA的平均改進率,即對某一規模的10個算例的改進率取平均值。由表2和圖1可以看出，與GA,TS和HGA_TS相比，HIG_SS1，HIG_SS2以及HIG具有較為明顯的改進，尤其是HIG_SS2,在訂單數為20，30和50時，平均改進率最大，而HIG_SS1則在訂單數為70時，平均改進率最大。相對于GA,HIG_SS1的綜合改進率達到了6.77%(見表2最后一行)。換句話說，如果用遺傳算法優化可以得到10萬元的總凈利潤，利用HIG_SS1可以額外平均增加6770元的利潤。從表2和圖1還可以看出，帶有加速構造策略的兩種算法(HIG_SS1和HIG_SS2)明顯優于不帶加速構造策略的算法HIG，說明加速構造策略在相同運行時間情況下可以有效改善混合迭代貪婪算法求解質量。

表2 各算法相對于GA的平均改進率(%)

3.3 加速構造搜索策略有效性驗證

為驗證兩種加速構造策略的有效性，對于同一規模算例，所有算法均在相同迭代次數下對運算時間進行對比。使用運行時間改進率(IR，Improved Ratio)來評估算法性能。具體如下：

IR=(RHTGi-RTHIG_SSi)×100/RTHIGi

其中,RTHIGi表示HIG算法在各規模實例上的平均運行時間，RTHIG_SSi表示具有加速構造策略i的算法在各規模實例上的平均運行時間。

表3給出了相同迭代次數下HIG、HIG_SS1和HIG_SS2三種算法的計算結果。從表3可以看出，與無加速構造策略的算法HIG相比，HIG_SS1和HIG_SS2兩種算法在20個不同的算例中均有17個算例獲得了運行效率的改進, 占比90%。如圖2所示，對于不同規模的訂單數，HIG_SS1的運行時間相較于HIG的運行時間改進率分別為2.09%、5.83%、4.29%和4.96%。而HIG_SS2相較于HIG的運行時間改進率分別為5.65%、7.88%、5.41%和5.97%。由此可見，加速構造策略1和2均具有良好的加速性能。同時，由表3和圖2可知，在最大值，平均值，標準差基本相同情況下，對于所有訂單規模，HIG_SS2的整體加速效果均優于HIG_SS1。

表3 相同迭代次數下HIG,HIG_SS1和HIG_SS2計算結果

3.4 加速構造策略收斂性驗證分析

圖3為不同規模問題情況下HIG、HIG_SS1和HIG_SS2三種算法的收斂曲線，其中橫軸表示迭代次數，縱軸表示迭代次數對應的最大凈利潤TNR。如圖3所示，三種算法在不同規模下均迅速收斂。隨著迭代次數的增加，HIG_SS2在20、50和70規模訂單的算例時收斂速度最快，且解的質量最好，50規模時其收斂曲線在20代后均趨于平穩。而HIG_SS1在30規模訂單的算例時收斂速度較快，且解的質量最好。

4 結語

本文研究了公共交貨期情形下預制構件生產環境中的訂單接受與調度集成問題，建立了非線性混合整數數學規劃模型。鑒于該問題復雜性，通過集成特定問題性質、構造啟發式以及鄰域搜索方法和破壞-構造機制，提出了一種基于加速構造策略的混合迭代貪婪搜索框架。基于兩種調度序列插入操作性質，進而提出了兩種混合加速迭代貪婪搜索算法(HIG_SS1和HIG_SS2)以提升算法運行效率，計算結果顯示，與GA，TS和HGA_TS相比，HIG_SS1和HIG_SS2具有更好的求解質量和魯棒性。同時驗證了兩種加速構造策略均能提升算法運行效率。與HIG相比，HIG_SS1和HIG_SS2算法收斂均較快，而且在相同的運行時間內，它們具有更好的平均求解質量。未來研究可以考慮將具有加速構造策略的混合迭代貪婪算法擴展至更為復雜的預制構件生產調度環境，比如分布式預制構件生產調度系統，不確定條件下的預制生產調度系統等。