啟發式算法在電梯生產計劃領域的應用

孫加洲 周炳海

(同濟大學 機械與能源工程學院 上海201804)

回顧過去一個世紀，隨著國內國際市場競爭的日益激烈，市場對制造企業的生產計劃與控制提出了新的挑戰，因此，繼傳統MRP之后，最優化技術、約束理論以及高級計劃與排程，日益成為了生產計劃領域研究的熱點問題，而最近提出的“智能制造”和“中國制造2025”等理念，更是對企業的科學化、智能化管理提出了更高的要求。

傳統的MRP系統在實際應用過程中逐漸暴露出以下弱點：（1）MRP計劃方式中對于DS設定的是固定提前量；（2）MRP計劃一般是建立在工作能力無限的基礎上；（3）由于MRP不具有動態擇優邏輯，當有多個排程方案時，需要人工去判斷和比較；（4）由于人工介入的內容較多，MRP計劃編制耗時較長，當計劃變更時，更是相當困難。

為了解決上述問題，引入了高級計劃與排產技術，高級計劃與排產是“Advanced Planning and Scheduling”的中文翻譯，簡稱APS，該技術是數學算法、計算機技術與IE管理思想三者的結晶，它對于解決部門內部、不同部門之間甚至是企業之間的全局優化，提供了一套系統的方法論。

全局優化的過程中會建立合適的數學模型，采取基于直觀經驗構造的智能化算法，明確限制條件，通過復雜的運算得出一系列可行解或最優解。通過引入APS排程，企業可以識別制造瓶頸，精確排產天數，減少在制品和庫存，快速同步計劃，并最終實現企業資源的最優化調度。

1 問題說明與目標提出

伴隨著中國城鎮化進程的推進，住宅建筑、商業建筑以及基礎設施的投入均處于較高水平，電梯行業也迎來了黃金時期，目前我國電梯年產量和保有量都居世界第一位，電梯產品的市場前景良好。

為響應市場對電梯安全性，外觀裝潢，運行穩定性等方面的訴求，企業采用了訂貨工程型的生產方式（Engineer to Order, ETO），從接受客戶訂單后開始著手設計與制造，在滿足客戶的同時，也帶來了其他負面影響。

一方面，由于機種、速度、載重及提升高度等選配指標的多樣化，導致同一功能的各種部件生產時間差異很大，而工作中心的可供工時幾乎恒定，必然造成產能供需不均衡。

另一方面，電梯需要現場安裝的產品特點決定了電梯部件一般是以多組木箱的形式交付客戶，為了降低倉儲成本，減少工段在制品，各木箱內的部件需要集中產出并及時裝箱。

在傳統的MRP計劃模式下，只能考慮預先設置的靜態單一的限制條件，常用的限制條件有：一條工藝線路所涉及的多個工作中心之中的瓶頸工作中心負荷、內作部品所在箱子的箱內同期性、特殊規格排產連續性、重要客戶的提前交貨期限、未進行備庫的外協部品最短交貨期等。

一般以其中一種限制條件完成排產后，通過得出的排產結果，反向驗證其余限制條件是否被滿足。如果滿足則計劃可行，如果不滿足，則需要調整計劃。除了運算過程復雜、調整費時費力之外，這樣的計劃方式存在以下幾點主要矛盾：（1）如果根據各工作中心的生產能力獨立安排產能，會造成裝箱成套率低，工段在制品大量堆積，進而造成每日成套臺數和裝箱負荷波動很大。（2）如果根據裝箱情況進行排產，滿足了箱內同期性，則各工作中心的負荷波動會增加，工段時忙時閑，情況嚴重時工段無法完成生產任務。（3）如果選定一個工作中心作為主流，其余工作中心參照其進行排產，雖然是一個介于兩者之間的方案，但是評定以哪個工作中心為標準，這個工作本身就比較困難。

基于上述分析不難發現，傳統MRP計劃模式已無法解決企業面臨的問題，為了從公司整體角度做好資源合理分配，平衡生產負荷，減少在制品，在保持各品目原有生產方式不變的前提下，通過引入APS對原有排程邏輯進行優化，最終給出一個可以兼顧每日產能波動性和裝箱同期性的生產組織方案。

2 解決思路與步驟

2.1 APS概念與參數

1） 計劃負荷波動

計劃負荷是工段生產任務與生產能力關系的體現，等于每日計劃時間與增值作業時間（在崗時間*綜合率）的比值，其值越小，說明計劃的可執行度越高，平準性越好；

2） 箱內同期性

反映一個箱內所有部件完工日期的差異天數。其數值越小，反映需要裝入同一個箱子的部件越集中產出，中間在制品越少；

3） 訂單離散性

反映一個訂單的電梯部件排產在同一天的情況；

4)WC(Work Center)

工作中心縮寫，指的是直接改變物料形態或性質的生產作業單元，以WCk表示第k個工作中心；

5)WCk的利用率

ηk=WCk上的已排工時/WCk的可供工時；

6)WCk欠排利用率密度

ηk欠=（WCk上的可供工時×排產系數-WCk上的已排工時）/（WCk的可供工時×排產系數×剩余可排臺數）；

7)WCk累計欠排利用率密度

ηk欠=（WCk上的可供工時×排產系數-WCk上的累計已排工時）/（WCk的可供工時×排產系數×剩余可排臺數）；

8)排產系數

計劃排產時每天可用系數，完整一天的系數為1.0，假設前旬最后一天已排產當日產能的30%，則后旬第一天的排產系數為0.7；

9)WCk可供工時

WCk可供工時=WCk的可供人數×出勤時間×綜合能率；

10)WCk可用可供工時：

WCk可用可供工時=WCk的可供人數×出勤時間×綜合能率×排產系數；

11)TS折合比

TS折合比=該工事番號在WCk上的TS/本旬所有工事番號在WCk上的平均TS；

2.2 總體思路

對于一次排程，先計算瓶頸工作中心負荷和設定最大利用率，確定本次投產的訂單所需的生產天數，然后讀取之前排產的情況，將兩者結合后，動態排入一個本次投產中最合適的訂單，并刷新負荷，接下來循環執行排入訂單與刷新負荷的操作，直到所有訂單都被賦予了日期。

2.3 具體步驟

(1)找出投產對象中涉及所有工作中心中，最大與最小單天累積的欠排利用率密度之差最大的工作中心，設為WCk；

(2)從各天中找出工作中心欠排利用率密度最高的一天，設為Day i；

(3)找出對WCk的TS 折合比最大的工事番號，設為Type j；若投產的工事番號對該工作中心TS折合比相同，則找出對其他工作中心TS折合比最大的規格；

(4)將該Type j工事番號排入Day i；

(5)更新本次投產所有工作中心的累計欠排定利用率密度；

(6)重復步驟(1)至(5)，直到所有工事番號都被賦予了排產日期。

3 案例分析

3.1 適用對象

K01箱、K02箱、K03箱、K04箱。

3.2 對象特點分析

(1)K01箱、K02箱、K03箱、K04箱相關部件及其涉及工作中心狀況如表1、表2所示。

表1 K01箱情況介紹

表2 K02、K03、K04箱情況介紹

3.3 模型建立

(1)手配方式為整體外協的部件（灰色底色部分），由對應的外協廠結合各自公司產能等實際情況予以考慮；

(2)手配方式為匯總的部件，由制造科室指定專人進行統一作業，通過產能規劃予以考慮；

(3)手配方式為內做的部件， K01箱、K02箱、K03箱、K04箱涉及工作中心品目較多，將各品目工作中心分為兩類：共線與非共線工作中心。由于后者影響的范圍較小，在排產順序上，先排定非共線工作中心，再排定共線工作中心；

由于大型層門門機數量較少，雖然涉及多道工序，但一定不會成為本次K01排產瓶頸工作中心，在后續排產標準層門門機時，通過裝配負荷予以考慮；由于轎門門機對激光機負荷影響有限，一定不會成為本次K01排產瓶頸工作中心，故在后續排產盤式袖壁操作面板時，通過臨時外協調整予以考慮；由于轎門門機對特種折彎機，鉚接工作中心影響有限，一定不會成為本次8#排產瓶頸工作中心，也同樣在標準層門門機排產時予以考慮；

因此可以將原先復雜的排產模型簡化，如表3所示。（其中共線工作中心后面用-G表示，非共線工作中心后面用-FG表示）

表3 排產因素簡化表

(4)基于以上客觀條件，制定排產邏輯如圖1所示。

圖1 排產邏輯流程圖

(5)理論排產效果如圖2所示。

圖2 排產預期效果圖

3.4 詳細算法

1）工作中心TS收集

將本次展開BM數據，通過TS和計劃模塊進行匹配，匯總成以工事番號為單位的各工作中心TS，完成排產基礎數據的準備工作；

2）旬分析

通過多能工調配，加班率設定，平衡各個工作中心工作天數與標準工作天數之間差異，滿足既定的交貨期，通過旬分析中與標準天數的差異及其累計差異，判斷計劃范圍是否符合公司進行狀況，并確定多能工調整，加班，調休等措施；

3)排產天數確定

非共線WC天數=各自WC排產天數

共線WC排產天數=MAX（各共線WC天數）

4)分類集合

以工事番號+品目+TS為單位，按照30min為標準將總TS分類集合，集合后名稱以品目+該集合最小TS命名，這樣便于提升啟發式排產的效率；

5)啟發式排產

TS折合比計算：

TS折合比=該工番在WCk上的TS/本旬所有工番在WCk上的平均TS

其中，平均TS=∑本旬所有工番在該WCK上的TS/工番數量；

各WC天與天之間利用率差值GAP的計算：

WCk的GAP=MAX(各天ηk)-MIN(各天ηk)；

排產系數即可排天數，由于非共線WC和共線WC的排產天數不同，故排產系數分開設置；

DS設定，指一批物料經過一道加工工序所需要的時間；

非共線WC排產

每個工作中心的利用率=已排工時/（可供工時×排產系數）

排產步驟（終止條件，當有一個WC負荷超過110%時，則終止該天的排產）

當本旬和上旬有交叉時，交叉處的可供工時全部按照上旬的可供工時計算；

修正由于上旬和本旬可供工時差異造成的天數差異：

如果交叉天數大于1天，則分別對每天進行計算，將合計影響天數計入本旬；

設首日系數為a，修正前天數為t，修正后天數為T，前旬可供工時Ga，本旬可供工時Gb，本旬需求TS為Y，則有以下等式；

將式（1）式（2），兩式聯立，有Gb×a+（t-a）×Gb=Ga×a+（T-a）×Gb

得到修正前后天數之間的關系：

整理成文字性描述為：

修正后的WCk排產天數=本旬WCk排產天數+（1-上旬WCk可供工時/本旬WCk的可供工時）×本旬數首日排產系數；

確定每日排產系數，分成三部分，分別是首日，中間天數和最后一天

首日排產系數=1-上旬末日的排產系數；

中間天數一般為1，如果當中有某幾天排產過，參考首日系數的計算及修正方式；

最后一天系數=總排產天數-本旬已確定排產系數之和；

判斷各非共線WC的GAP，找出GAP最大的一個WC（如果GAP相同，則選擇限速器裝配WC）；

選擇該WC在TS折合比計算表格中最大的一個類別，在排產表格中找到該WC利用率最小的一天，把該規格中一個的該WC的生產日期標記為該天；

工番選擇時，優先選擇和當天已排工番相同圖號、參數的工番；

根據DS Master，推出各相關WC的生產日期，DS Master如表4所示；

DS（單位為天）樣例如下：通過以下DS直接推出工藝線路中各WC的生產日期，如表4所示。

表4 DS推算設定表

刷新排產表格（全表格刷新），如此重復，直到排產表格中各規格全部排完；

修正排產系數不是1的該天的利用率顯示，也就是下次排產的首日系數a；

顯示利用率=計算出利用率×本旬排產系數。

6）共線WC排產

排產步驟（終止條件，當有一個WC負荷超過110%時，則終止該天的排產。）

當本旬和上旬有交叉時，交叉處的可供工時全部按照上旬的可供工時計算；

修正由于上旬和本旬瓶頸WC可供工時差異造成的天數差異；

修正后的瓶頸WC天數=本旬瓶頸WC排產天數+（1-上旬瓶頸WC可供工時/本旬瓶頸WC的可供工時）×本旬首日排產系數，如果交叉天數大于1天，則分別對每天進行計算，將合計影響天數計入本旬；（推導過程與非共線一致，不再推導）；

計算共線WC的瓶頸WC排產天數：

先計算共線WCk的初始需求天數設為T'k，由于初始非共線WC的排產天數與共線WC的排產天數存在差異，當非共線WC排入后，共線WC的天數相應發生變化；

設變化后的排產天數為Tk，則Tk=Tk’-∑非共線WCk利用率；

瓶頸WC的天數=MAX（Tk）

確定每日排產系數，系數的分類和確定方法與非共線一致；

判斷各共線WC的GAP，找出GAP最大的一個工作中心（如果GAP相同，則選擇機械剪板WC）；

選擇該WC在TS折合比計算表格中最大的一個類別，在排產表格中找到該WC利用率最小的一天，把該規格中一個工番的該WC的生產日期設定為該天，工番選擇時，優先選擇和當天已排工番相同圖號、參數的工番；

根據DS Master，推出各相關WC的生產日期，樣例參考非共線；

DS有無判斷條件，該WC有TS則有，否則則無；

如果TS為0，有可能是內外內的工藝線路，需要進行DS推算。

刷新排產表格（全表格刷新），如此重復，直到排產表格中各規格全部排完；

修正排產系數不是1的該天的利用率顯示，修正方式同非共線。

由于限速器、安全鉗裝配、導靴裝配有同期性要求，故在進行啟發式排產的時候進行捆綁處理。

整體外協品目排產：由于整體外協品目與內做品目有同期性要求，故采取將整體外協跟隨內做品目的排產方法。

小日程的輸出順序：以日期為第一優先級，圖號和參數為第二第三優先級，這樣利于工段集中生產。

表5 排產結果對比表

圖3 箱內同期性對比折線圖

4 效果評價與對比

對當年12月份的訂單按照兩種方式進行了模擬排產，并將結果按照箱內同期性、訂單離散性、計劃負荷波動性以及排程時間，分別進行了對比，數據如下：

首先，不難看出，通過引入APS排程，箱內同期性從原來的平均0.92天下降為平均0.11天，約每天減少生產現場40箱左右的裝箱區域在制品堆積，極大地緩解了該區域的裝箱成套性；

并且，對參與模擬的100個工事番號制成如圖3所示折線圖，橫軸代表工事番號的序號，縱軸代表箱內同期性的天數，可以明顯看出箱內同期性從原先的高位大幅度震動，轉變為低位的小幅度震動，由此得出，在箱內同期性上，APS排程相比MRP排程有了極大的改善，排產結果對比如表5所示。

其次，對改善前后的計劃負荷的波動性制成如圖4所示統計圖，計劃波動從原來的峰谷波動12%，下降到峰谷波動4.6%，總共下降了7.4個百分點，極大地提升了生產的穩定性和可操作性。

圖4 排產負荷峰谷統計圖

最后，排產時間方面，從原來的純手動排產120分鐘，下降到人工調整排產基礎數據20分鐘，系統運算4分鐘，總共24分鐘，排產用時縮短了五分之四，極大提升了排產效率。

綜上所述，APS排程相比于原來的手動排程，在訂單離散性上有一定改善，而在工作中心負荷波動性箱內同期性，計劃排程時間，這三項指標上有十分明顯的改善。

5 結語

本文展示的方法既滿足了多品種部件的同期性要求，又兼顧每日產出臺數及其工作中心負荷，在生產計劃領域具有一定的普遍適用性。

但是，階段性成功的背后也客觀地看到：

(1)由于多能工調配邏輯難以構建等問題，導致存在瓶頸工序的共線多工序部件，在瓶頸工序負荷排滿后，其余工序負荷還有空余；

(2)沒有考慮短交貨項目插單對標準工期的排產項目影響。

今后會帶著這些問題對現有排程邏輯做進一步的優化，完善APS排產的邏輯，提升企業的生產管理科學性。