基于智能排產的生產設備核算方法研究

張 波

（中國航空規劃設計研究總院有限公司，北京 100120）

1 背景

生產設備數量核算是生產線工藝設計的重點之一。傳統的基于設備年時基數和可用系數的估算方法雖然實施簡便，但是未能充分考慮實際生產過程中約束條件（例如：原材料、設備、刀具、夾具的可用性）和各種意外情況（例如：設備故障、緊急插單、季節波動等）。智能排產利用計算機技術，在企業的生產資源限制下，以某種最優化方式（例如：交付周期最短、設備負載最均衡、生產成本最低等）來分配這些資源，滿足產品的生產需要。因此，在生產線設計過程中，引入智能排產技術有利于更加細致地考慮各種生產資源約束和隨機情況，借助計算機模擬仿真實現對復雜情況的精確分析，從而更加科學地核算設備數量是否滿足生產實際需求。

智能排產是一個學術界和工業界都很關注問題，甚至許多MES軟件都內嵌了相應的模塊。然而，由于生產實際要求和約束條件千差萬別，很多“通用型”的智能排產軟件都不能很好地滿足用戶個性化的需求。在很多情況下，依然需要根據用戶特定的需要和實際情況實行深度的定制開發。對于生產線設計單位而言，面對千變萬化的設計任務，有必要積極開展相關研究，培養相關能力，力求做到“隨機應變”。

2 基于智能排產的生產設備核算方法研究思路

生產實際要求和約束條件的千變萬化導致智能排產問題具有很強的多變性，然而從其組合優化的本質屬性來看，其求解的方法卻是相對有限并存在通用性的。掌握這些通用的算法可以為解決各類智能排產問題提供必要和高效的思路和方法。為此，可以從組合優化的經典原型問題出發，探求常見經典算法的思想精髓、適用范圍、求解速度和解的質量，然后結合企業典型生產場景提出相應的排產算法，并通過實際工程應用加以驗證和應用，對實際的設備數量進行校核。

其中原型問題選取著名的旅行推銷商（TSP）問題，即旅行推銷商要不重復地遍歷給定的一組城市并返回到出發點，在已知兩兩城市之間的距離的情況下，如何安排路徑使得總路徑最短。作為組合優化算法研究中的經典題目，TSP問題受到了廣泛的關注，眾多學者提出了多種求解方法，其中包括：暴力搜索、動態規劃、分支界定、線性規劃、排斥鏈、禁忌搜索、模擬退火、遺傳算法、……等。TSP問題為展現這些算法的思想精髓提供了一個統一的平臺，并為算法效能的橫向比較提供了統一的標尺。因此，利用TSP問題來學習上述各種優化算法，有望收到事半功倍的效果。

不同的組合優化算法在適用范圍、求解速度和解的質量等方面必然存在著差異，對于企業不同的應用場景需要選擇、組合、創造新的智能排產算法，實現從一般到特殊的轉變。在此，需要廣泛、深入地了解企業的生產資源現狀、生產組織方式和現實的生產需求和困難，并將它們轉化為用數學語言描述的約束條件和優化目標。例如，最大可用設備數量（生產資源現狀）、批量生產或單件流（生產組織方式）、設備故障率（生產困難）、生產周期最短（優化目標）等。對于初步開展此類工作的生產線設計單位而言，可以先從2～3種典型的應用場景入手，積累經驗。未來更多的應用需求通常可以通過對典型應用場景的簡單修改或擴充來加以滿足。

對于生產設備數量核算而言，關注的不是如何對一兩個具體的生產任務包進行智能排產，而要從統計學的角度來構建“典型任務包”。通過對典型任務包中各種任務情況的智能排產結果進行統計分析，然后根據指定的滿足概率確定最低的設備數量要求。例如，對于瓶頸生產資源的基于智能排產的生產設備核算，需要考慮并發生產需求的時間分布概率，在此基礎之上確定在特定的生產周期（比如一年）內如果以95%的概率完成生產任務，各種生產設備分別需要多少臺套。通用的算法框架如圖1所示。

圖1 基于優化排產的設備數量核算通用算法框架

3 關鍵技術難點及解決方案

開展基于智能排產的生產設備核算研究可能遇到以下技術難點：

（1）高效智能排產算法的構建。高效智能排產算法的構建是此項工作的核心內容，其難度主要在于組合優化問題自身由于組合情況增加而可能帶來的巨大運算量，這可能導致計算機存儲空間不足，或者計算時間超出實際應用所能忍耐的最大限度。

存儲需求方面：如果在TSP問題中簡單地探求50個城市的排列順序，需要考察的情況為49!/2=3.04x1062種[1]，假設存儲一種排列需要50個字節（順序排列），那么總的存儲需求為1.52x1064字節！據稱人類自文明誕生到2003年以來產生的信息大概也只有5EB（5x1018字節）[2]。顯然，這樣的存儲需求已經遠遠超出了目前人類所有IT設備的存儲能力的總和。

計算時間方面：以TSP問題為例，盡管該問題已經提出了幾十年，當城市節點的數量較多時，求解的時間依然是一個天文數字。Cook等人在2005年、2006年的研究表明[3]，如果采用十分先進的Concorde TSP Solver來求解33810個城市節點的TSP問題，需要15.7個CPU·年；如果求解85 900個城市節點的TSP問題，需要136個CPU·年。即便采取多CPU并行處理技術，10 000個CPU同時處理也分別需要13.75和119小時！對于任何一家企業而言，這樣的計算時間根本是無法想象的。

（2）典型任務包的構建。典型任務包的構建是實現此項研究目標的必要手段，其難度主要在于如何根據大量離散的數據構建合理的、具有典型代表性的樣本，以盡可能小的樣本容量最大限度地真實反映生產線實際運行狀態，以減少模擬仿真的運行次數，從而提高整體速度和實用性。

企業在生產過程中隨時面臨著各種各樣的隨機突發情況，其中包括但不限于：關鍵設備故障、操作工人請假、停電/停水、緊急插單、原材料供應不及時、配套廠家拖期、……。此外，國內的許多企業還常常受到批次和年度生產計劃的影響，全年生產不均衡，呈現出一定的“季節性波動”。各種突發事件的概率分布是不同的，而季節性波動又給多種隨機性中引入了趨勢性。

常用的蒙特卡洛隨機試驗方法可以較好地模擬多變量多參數的隨機過程，但是這種方法過度依賴隨機產生的大樣本（通常數以萬計），對于本身求解時間較長的排產算法而言，無疑是雪上加霜！

針對上述技術難點，可以采取以下措施加以解決。

（1）探求高效率的近似解法以降低對存儲空間的需求，盡可能縮短求解時間。面對無比龐大的組合數，必須摒棄通過遍歷所有組合情況來尋找最優解的常規思路。為此，必須放棄對精確解的苛求，現實地尋找近似解。實際上，對于絕大多數組合優化問題而言，雖然最優解（即精確解）只有一個或為數不多的幾個，其近最優解（即近似解）通常會有很多，而后者往往較容易獲得，并且與最優解的差距并不明顯。對于工程實際應用而言，在絕大多數的情況下，這種差距的意義更是微不足道。

面對龐大的組合情況，近似算法摒棄了逐個搜索最優解的努力，轉而采取“撒大網，順藤摸瓜”的策略。具體地說，此類算法通常先在解空間中隨機地產生一些可行解，然后再從這些可行解中篩選出比較優良的解，通過對可行解試探性地修改并進行多次反復地迭代，來逐步逼近最優解。目前學術界已經開發出了許多種近似解法，其中包括但不限于[1-5]：模擬退火（Simulated Annealing）、禁忌搜索（Tabu Search）、排斥鏈（Ejection Chains）、遺傳算法（Genetic Algorithm）、神經網絡（Neural Network）、混合蛙跳算法（Shuffled Frog Leaping）、群體智能算法（Swarm Intelligence）等。上述算法已經被成功地應用于許多實際問題，取得了良好的效果。需要在深入了解它們思想精髓的基礎之上，結合實際工程需要，靈活地加以運用，開發出適用的具體算法。

（2）通過概率分解的方法構建小樣本的典型任務包。除了盡可能提高排產算法的運行效率，提高設備核算速度的重要途徑就是盡可能減少需要檢驗的典型任務包的樣本容量。在合理、清晰地定義“生產任務完成概率”的概念的基礎之上，分別確定任務完成的標準并對各種可能發生的情況進行基于概率的合理組合，有望大大減少典型任務包的樣本容量。例如，對于特定設備組合下的任務按時完成概率考察時，可以嘗試進行如下定義：

任務按時完成概率=∑(任務完成情況得分x各種對應情況發生的概率)，其中：

任務完成情況得分=1（按時完成）或0（未能按時完成）。

需要考慮的各種情況包括：生產周期占比（任務包周期/1年）、故障組合（各設備都不發生故障、只有1臺設備發生故障、只有2臺設備發生故障、……）、插單情況（插單任務包出現的概率）。

在考慮各種情況發生的概率時，可以只考慮那些相對而言出現概率較高情況。例如，假設只有5臺設備，每臺設備在任務包周期內的發生故障的概率都只有1%（“0”代表無故障發生，“1”代表有故障發生），那么對于以95%任務按時完成概率為目標的核算而言，通常只需要考慮出現概率較大的前6種情況即可（即各設備都不發生故障，以及分別只有1臺設備發生故障）。它們覆蓋了99.90%的故障發生情況。有關典型任務包的設計，可以借鑒統計學中的實驗設計技術，Antony等人的研究[5]為大幅度減少測試樣本數量提供了有益的參考。

（3）通過遞進篩選的方式減少模擬仿真的次數。即分步考慮計劃任務、緊急插單和設備故障等多種情況，及時排除不需要考慮的設備組合情況。具體而言，就是沿著“計劃任務→計劃任務+緊急插單→計劃任務+緊急插單+設備故障→……”排產難度依次加大的順序來分步地考察現有的設備組合是否滿足要求。如果發現當前的設備組合情況已經不能滿足指定的生產任務完成概率（比如95%），就不再進一步考察后續的情況，而是立刻根據需要增加需要的設備，達到指定的生產任務完成概率后再進一步考慮更加困難和復雜的情況。

4 總結與展望

智能化制造對生產線設計企業提出了更高的技術要求，傳統的估算方法已經不能很好地滿足設計需求。基于智能排產的生產線設備核算方法將各種生產資源約束和隨機情況納入考慮，為提高生產線設計水平和質量提供了新的思路和手段。由于種種原因，相關方法研究在國內尚未充分展開。隨著智能制造思想和理念在國內的推廣，該項研究有望得到廣泛的重視。其研究成果不僅可以提高生產線設計的水平，還將推動企業運營管理水平的進一步提高。

［1］ William J.Cook.In Pursuit of the Traveling Salesman：Mathematics at the Limits of Computation ［M］.Prince?ton University Press，2012.

［2］Frank J.Ohlhorst.Big Data Analytics［M］.John Wiley&Sons，Ltd，2012.

［3］ David L.Applegate，Rober E.Bixby，Vasek Chvatal，et al.The Traveling Salesman Problem： A Computation?al Stduy［M］.Princeton University Press，2006.

［4］ Jacek Blazewicz， Klaus H.Ecker， et al.Scheduling Computer and Manufacturing Processes ［M］.Spring?er-Verlag Berlin Heidelberg GmbH，2001.

［5］ Jiju Antony.Design of Experiments for Engineers and Sci?entists［M］.Elsevier，2014.