張 波

（中國航空規(guī)劃設(shè)計研究總院有限公司，北京 100120）

1 背景

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

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

2 基于智能排產(chǎn)的生產(chǎn)設(shè)備核算方法研究思路

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

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

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

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

圖1 基于優(yōu)化排產(chǎn)的設(shè)備數(shù)量核算通用算法框架

3 關(guān)鍵技術(shù)難點及解決方案

開展基于智能排產(chǎn)的生產(chǎn)設(shè)備核算研究可能遇到以下技術(shù)難點：

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

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

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

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

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

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

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

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

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

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

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

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

需要考慮的各種情況包括：生產(chǎn)周期占比（任務(wù)包周期/1年）、故障組合（各設(shè)備都不發(fā)生故障、只有1臺設(shè)備發(fā)生故障、只有2臺設(shè)備發(fā)生故障、……）、插單情況（插單任務(wù)包出現(xiàn)的概率）。

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

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

4 總結(jié)與展望

智能化制造對生產(chǎn)線設(shè)計企業(yè)提出了更高的技術(shù)要求，傳統(tǒng)的估算方法已經(jīng)不能很好地滿足設(shè)計需求?；谥悄芘女a(chǎn)的生產(chǎn)線設(shè)備核算方法將各種生產(chǎn)資源約束和隨機情況納入考慮，為提高生產(chǎn)線設(shè)計水平和質(zhì)量提供了新的思路和手段。由于種種原因，相關(guān)方法研究在國內(nèi)尚未充分展開。隨著智能制造思想和理念在國內(nèi)的推廣，該項研究有望得到廣泛的重視。其研究成果不僅可以提高生產(chǎn)線設(shè)計的水平，還將推動企業(yè)運營管理水平的進一步提高。

［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.