張 波
(中國航空規(guī)劃設(shè)計研究總院有限公司,北京 100120)
生產(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)變”。
生產(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ù)量核算通用算法框架
開展基于智能排產(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ù)雜的情況。
智能化制造對生產(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.