【經(jīng)典文章】智能工廠,不能不知道的調(diào)度算法
發(fā)布時間:2020-10-22發(fā)布人:admin
一、排產(chǎn)調(diào)度問題的提出
敏捷制造作為21世紀(jì)企業(yè)的先進制造模式,綜合了精益JIT、并行工程等多種先進制造模式的哲理,其目的是要以最低成本制造出顧客滿意的產(chǎn)品,即是完全面向顧客的。
在這種模式下,如何進行組織管理,包括如何組織動態(tài)聯(lián)盟、如何重構(gòu)車間和單元、如何安排生產(chǎn)計劃、如何進行排產(chǎn)調(diào)度都是我們面臨的問題。其中車間作業(yè)排產(chǎn)調(diào)度與控制技術(shù)是實現(xiàn)生產(chǎn)高效率、高柔性和高可靠性的關(guān)鍵,有效實用的排產(chǎn)調(diào)度方法和優(yōu)化技術(shù)的研究與應(yīng)用已成為智能制造技術(shù)實踐的基礎(chǔ)。
排產(chǎn)調(diào)度問題主要集中在車間的計劃與排產(chǎn)調(diào)度方面,是針對一項可分解的工作(如產(chǎn)品制造),探討在在盡可能滿足約束條件(如交貨期、工藝路線、資源情況)的前提下,通過下達(dá)生產(chǎn)指令,安排其組成部分(操作)使用哪些資源、其加工時間及加工的先后順序,以獲得產(chǎn)品制造時間或成本的最優(yōu)化。在理論研究中,生產(chǎn)排產(chǎn)調(diào)度問題常被稱為排序問題或資源分配問題。
二、排產(chǎn)調(diào)度問題的分類
生產(chǎn)排產(chǎn)調(diào)度系統(tǒng)的分類方法很多,主要有以下幾種:
(1)?根據(jù)加工系統(tǒng)的復(fù)雜度,可分為單機、多臺并行機、Flow Shop(流水線加工)和 Job Shop(任務(wù)型加工)。
單機排產(chǎn)調(diào)度問題是所有的操作任務(wù)都在單臺機器上完成,為此存在任務(wù)的優(yōu)化排隊問題,多臺并行機的排產(chǎn)調(diào)度問題更復(fù)雜,因而優(yōu)化問題更突出。
Flow Shop型問題假設(shè)所有作業(yè)都在同樣的設(shè)備上加工,并有一致的加工操作和加工順序。Job Shop是最一般的排產(chǎn)調(diào)度類型、并不限制作業(yè)的操作的加工設(shè)備,并允許一個作業(yè)加工具有不同的加工路徑。
(2)?根據(jù)性能指標(biāo),分為基于排產(chǎn)調(diào)度成本和排產(chǎn)調(diào)度性能的指標(biāo)兩大類。
(3)?根據(jù)生產(chǎn)環(huán)境的特點,可將排產(chǎn)調(diào)度問題分為確定性排產(chǎn)調(diào)度和隨機性排產(chǎn)調(diào)度問題。
(4)?根據(jù)作業(yè)的加工特點,可將排產(chǎn)調(diào)度問題分為靜態(tài)排產(chǎn)調(diào)度和動態(tài)排產(chǎn)調(diào)度。
靜態(tài)排產(chǎn)調(diào)度是指所有待安排加工的工作均處于待加工狀態(tài),因而進行—次排產(chǎn)調(diào)度后、各作業(yè)的加工被確定、在以后的加工過程中就不再改變;動態(tài)排產(chǎn)調(diào)度是指作業(yè)依次進入待加工狀態(tài)、各種作業(yè)不斷進入系統(tǒng)接受加工、同時完成加工的作業(yè)又不斷離開,還要考慮作業(yè)環(huán)境中不斷出現(xiàn)的動態(tài)擾動、如作業(yè)的加工超時、設(shè)備的損壞等。因此動態(tài)排產(chǎn)調(diào)度要根據(jù)系統(tǒng)中作業(yè)、設(shè)備等的狀況,不斷地進行排產(chǎn)調(diào)度。實際排產(chǎn)調(diào)度的類型往往是Job Shop型且是動態(tài)的。
三、生產(chǎn)排產(chǎn)調(diào)度的環(huán)境特征
一般的排產(chǎn)調(diào)度問題都是對于具體生產(chǎn)環(huán)境中復(fù)雜的、動態(tài)的、多目標(biāo)的排產(chǎn)調(diào)度問題的一種抽象和簡化,因而,一個排產(chǎn)調(diào)度算法可以通過其如何表述這些復(fù)雜性來進行分類。
由于實際生產(chǎn)環(huán)境是千差萬別的,那末,一個排產(chǎn)調(diào)度算法就應(yīng)該根據(jù)其是否能適合對應(yīng)的生產(chǎn)環(huán)境的重要特征來進行評估。為了幫助區(qū)別不同的生產(chǎn)排產(chǎn)調(diào)度策略,給出了典型生產(chǎn)排產(chǎn)調(diào)度環(huán)境的五個特征,這將有助于我們了解各種不同的排產(chǎn)調(diào)度算法的應(yīng)用環(huán)境。
1、?邊界條件:
生產(chǎn)排產(chǎn)調(diào)度常常是一個重排產(chǎn)調(diào)度問題,即修改已有的生產(chǎn)排產(chǎn)調(diào)度去適應(yīng)新的作業(yè)。為提供重排產(chǎn)調(diào)度,排產(chǎn)調(diào)度算法應(yīng)能處理生產(chǎn)系統(tǒng)中有關(guān)的初始狀態(tài)。類似的生產(chǎn)排產(chǎn)調(diào)度通常是在一個有限的時間區(qū)域里進行的,系統(tǒng)的最優(yōu)解(或次優(yōu)解)亦是在限定的邊界范圍內(nèi)來獲取。
2、?分批大小和調(diào)整成本:
為有效地解決實際生產(chǎn)中的排產(chǎn)調(diào)度問題,往往將任務(wù)分成多批進行,并考慮改變已有排產(chǎn)調(diào)度結(jié)果所付出的代價(調(diào)整成本)。
3、?加工路徑:
在實際生產(chǎn)中,作業(yè)的加工路徑可能需要動態(tài)改變,工藝順序可能是半有序的(Semi order)。
4、?隨機事件和擾動:
出現(xiàn)關(guān)鍵作業(yè)、設(shè)備損壞、加工操作失敗、原料短缺、加工時間、到達(dá)時間、交貨期的改變等。
5、?性能指標(biāo)和多目標(biāo):
追求不同的性能指標(biāo)往往會得到不同的優(yōu)化解,同時,系統(tǒng)目標(biāo)也以多目標(biāo)為主。
四、排產(chǎn)調(diào)度問題的特點
實際的排產(chǎn)調(diào)度問題有以下特點:
(1)?復(fù)雜性
由于裝卸作業(yè)、裝卸設(shè)備、庫場、搬運系統(tǒng)之間相互影響、相互作用、每個作業(yè)又要考慮它的到達(dá)時間、裝卸時間、準(zhǔn)備時間、操作順序、交貨期等,因而相當(dāng)復(fù)雜。
由于排產(chǎn)調(diào)度問題是在等式或不等式約束下求性能指標(biāo)的優(yōu)化,在計算量上往往是NP(多項式復(fù)雜性)完全問題,即隨著問題規(guī)模的增大,對于求解最優(yōu)化的計算量呈指數(shù)增長,使得一些常規(guī)的最優(yōu)化方法往往無能為力。
(2)?動態(tài)隨機性
在實際的生產(chǎn)排產(chǎn)調(diào)度系統(tǒng)中存在很多隨機的和不確定的因素,比如作業(yè)到達(dá)時間的不確定性、作業(yè)的加工時間也有一定的隨機性,而且生產(chǎn)系統(tǒng)中常出現(xiàn)一些實發(fā)偶然事件,如設(shè)備的損壞、修復(fù)、作業(yè)交貨期的改變等。
(3)?多目標(biāo)。
實際的計劃排產(chǎn)調(diào)度往往是多目標(biāo)的,并且這些目標(biāo)間可能發(fā)生沖突。排產(chǎn)調(diào)度目標(biāo)分為基于排產(chǎn)調(diào)度成本和排產(chǎn)調(diào)度性能的指標(biāo)兩大類。
也有排產(chǎn)調(diào)度目標(biāo)分三類:基于作業(yè)交貨期的目標(biāo)、基于作業(yè)完成時間的目標(biāo)、基于生產(chǎn)成本的目標(biāo)。這種多目標(biāo)性導(dǎo)致排產(chǎn)調(diào)度的復(fù)雜性和計算量急劇增加。
五、排產(chǎn)調(diào)度問題的研究方法
—般的排產(chǎn)調(diào)度問題都是對于具體生產(chǎn)環(huán)境中復(fù)雜的、動態(tài)的、多目標(biāo)的排產(chǎn)調(diào)度問題的一種抽象和簡化,因而一個排產(chǎn)調(diào)度算法可以通過其如何表述這些復(fù)雜性進行分類。由于實際中生產(chǎn)環(huán)境是千差萬別的,那么一個排產(chǎn)調(diào)度算法就應(yīng)該根據(jù)其是否能適合對應(yīng)的生產(chǎn)環(huán)境的重要特征進行評估。
在對排產(chǎn)調(diào)度問題進行研究的方法上,最初是集中在整數(shù)規(guī)劃、仿真和簡單的規(guī)則上,這些方法不是排產(chǎn)調(diào)度結(jié)果不理想就是難以解決復(fù)雜的問題。隨著各種新的相關(guān)學(xué)科與優(yōu)化技術(shù)的建立與發(fā)展,在排產(chǎn)調(diào)度領(lǐng)域也出現(xiàn)了許多新的優(yōu)化方法,比如神經(jīng)網(wǎng)絡(luò)、模擬退火法、遺傳算法、禁忌搜索法等,使得排產(chǎn)調(diào)度問題的研究方法向多元化方向發(fā)展。下面我們分別對這些方法進行總結(jié):
(1)?運籌學(xué)方法
運籌學(xué)方法是將生產(chǎn)排產(chǎn)調(diào)度問題簡化為數(shù)學(xué)規(guī)劃模型,采用基于枚舉思想的分枝定界法或動態(tài)規(guī)劃算法進行解決排產(chǎn)調(diào)度最優(yōu)化或近優(yōu)化問題,屬于精確方法。不同的分枝定界法,其不同點主要在于分析規(guī)則、定界機制和上界的產(chǎn)生這三方面存在差異。這類方法雖然從理論上能求得最優(yōu)解,但由于其計算復(fù)雜性的原因、因而不能獲得真正的實用。
對于復(fù)雜的問題,這種純數(shù)學(xué)方法有模型抽取困難、運算量大、算法難以實現(xiàn)的弱點,對于生產(chǎn)環(huán)境中的動態(tài)排產(chǎn)調(diào)度實現(xiàn)復(fù)雜,解決不了動態(tài)及快速響應(yīng)市場的問題。
(2)?基于規(guī)則的方法
對生產(chǎn)加工任務(wù)進行排產(chǎn)調(diào)度的最傳統(tǒng)的方法是使用排產(chǎn)調(diào)度規(guī)則(Dispatching Rules),已經(jīng)有許多排產(chǎn)調(diào)度規(guī)則被應(yīng)用,因其排產(chǎn)調(diào)度規(guī)則簡單、易于實現(xiàn)、計算復(fù)雜度低等原因,能夠用于動態(tài)實時排產(chǎn)調(diào)度系統(tǒng)中,許多年來一直受到廣泛研究,并不斷涌現(xiàn)出新的排產(chǎn)調(diào)度規(guī)則。如較優(yōu)的單元零件加工排產(chǎn)調(diào)度算法,在減少等待時間、提高生產(chǎn)率等諸多約束條件下達(dá)到了一種較為科學(xué)有效的排產(chǎn)調(diào)度效果。
規(guī)則按形式分為了三類:簡單規(guī)則、復(fù)合規(guī)則、啟發(fā)式規(guī)則;隨著計算機運算速度的飛速提高,人們希望尋找新的近似排產(chǎn)調(diào)度方法,它以合理的額外計算時間為代價,換得比單純啟發(fā)式規(guī)則所得到的排產(chǎn)調(diào)度更好的排產(chǎn)調(diào)度。在這方面比較有代表性的有移動瓶頸方法(Bottle Neck Procedure),用來解決以最小化 Make Span(制造時間)為目標(biāo)的 Job Shop排產(chǎn)調(diào)度問題,它通過不斷地對移動的瓶頸設(shè)備進行單機排產(chǎn)調(diào)度,來獲取更好的次優(yōu)解。
總的說來,啟發(fā)式規(guī)則直觀、簡單、易于實現(xiàn)。但是近研究表明并不存在一個全局最優(yōu)的排產(chǎn)調(diào)度規(guī)則,它們的有效性依賴于對特殊性能需求的標(biāo)準(zhǔn)及生產(chǎn)條件。
它是局部優(yōu)化方法,難以得到全局優(yōu)化結(jié)果,并且不能對得到的結(jié)果進行次優(yōu)性的定量評估。顧客需求的個性化及要求企業(yè)響應(yīng)市場的敏捷性,往往在生產(chǎn)加工過程中加入了更多的不確定性及復(fù)雜性約束,尋找排產(chǎn)調(diào)度最優(yōu)算法本身是一個NP完全問題,這些使得基于規(guī)則的排產(chǎn)調(diào)度思想已不能適合敏捷化制造的要求。
(3)系統(tǒng)仿真的方法
仿真方法是不單純追求系統(tǒng)的數(shù)學(xué)模型,側(cè)重對系統(tǒng)中運行的邏輯關(guān)系的描述,能夠?qū)ιa(chǎn)排產(chǎn)調(diào)度方案進行比較評價,分析系統(tǒng)的動態(tài)性能,并選擇系統(tǒng)的動態(tài)結(jié)構(gòu)參數(shù)。由于制造系統(tǒng)的復(fù)雜性,很難用一個精確的解析模型來進行描述和分析。而通過運行仿真模型來收集數(shù)據(jù),則能對實際系統(tǒng)進行性能、狀態(tài)等方面的分析,從而,能對系統(tǒng)采用合適的控制排產(chǎn)調(diào)度方法。
仿真方法最早被用來作為測試排產(chǎn)調(diào)度啟發(fā)式規(guī)則及分派規(guī)則的工具。后來,人們發(fā)現(xiàn),通過將簡單的優(yōu)先權(quán)規(guī)則進行組合,或用一個簡單的優(yōu)先權(quán)規(guī)則將一些啟發(fā)式規(guī)則進行組合,這樣的排產(chǎn)調(diào)度優(yōu)于單獨的優(yōu)先權(quán)規(guī)則。
于是,仿真方法逐漸發(fā)展為一種人機交互的柔性仿真工具,并用來進行車間排產(chǎn)調(diào)度。這樣,就能通過仿真而動態(tài)地展現(xiàn)Job Shop車間的狀態(tài),分析在不同的排產(chǎn)調(diào)度方法下的系統(tǒng)性能,并運用知識和經(jīng)驗去選擇合適的排產(chǎn)調(diào)度方法(規(guī)則),從而改善排產(chǎn)調(diào)度性能。
基于純仿真法雖然可以包含解析模型無法描述的因素,并且可以提供給使用者一個排產(chǎn)調(diào)度性能測試的機會,但其不可避免地存在以下問題:
-鑒于其實驗性,因此,很難對生產(chǎn)排產(chǎn)調(diào)度的理論作出貢獻(xiàn)。
-應(yīng)用仿真進行生產(chǎn)排產(chǎn)調(diào)度的成本很高,不僅在于產(chǎn)生排產(chǎn)調(diào)度的計算時間上,而且在于設(shè)計、建立、運行仿真模型上的高成本。
-仿真的準(zhǔn)確性受編程人員的判斷和技巧的限制,甚至很高精度的仿真模型也無法保證通過實驗總能找到最優(yōu)或次優(yōu)的排產(chǎn)調(diào)度。
(4)?基于 DEDS的解析模型方法
由于制造系統(tǒng)是一類典型的離散事件系統(tǒng),因此,可以用研究離散事件系統(tǒng)的解析模型和方法去探討車間排產(chǎn)調(diào)度問題,諸如排隊論、極大/極小代數(shù)模型、Petri網(wǎng)等。
排產(chǎn)調(diào)度中的排隊論方法是一種隨機優(yōu)化方法,它將每個設(shè)備看成一個服務(wù)臺,將每個作業(yè)作為一個客戶。作業(yè)的各種復(fù)雜的可變特性及復(fù)雜的路徑,可通過將其加工時間及到達(dá)時間假設(shè)為一個隨機分布來進行描述。
總的說來,排隊網(wǎng)絡(luò)模型由于從隨機統(tǒng)計的角度來描述制造系統(tǒng),難以表述系統(tǒng)中存在的某些特性(如有限的緩存空間等),同時,產(chǎn)生的輸出是基于系統(tǒng)穩(wěn)態(tài)操作的平均量,因此,很難得到比較具體的細(xì)節(jié)。
Petri網(wǎng)作為一種圖形建模工具可以形象地表示和分析FMS中加工過程的并發(fā)和分布特征以及多項作業(yè)共享資源時的沖突現(xiàn)象,具有很強的建模能力,對于描述系統(tǒng)的不確定性和隨機性也具有一定的優(yōu)越性。在制造自動化領(lǐng)域,利用 Petri網(wǎng)及其擴展形式的模型進行死鎖分析、排產(chǎn)調(diào)度決策和性能評價等。
目前,Petri網(wǎng)模型用于排產(chǎn)調(diào)度還存在以下的問題:
-節(jié)點語義的單義性,使得所攜帶的系統(tǒng)信息量不夠豐富。
-重用性差。Petri網(wǎng)多是基于制造中作業(yè)的加工流程建模,當(dāng)作業(yè)需求或工藝稍有變動時,必須修改模型結(jié)構(gòu),這難于適應(yīng)制造中存在的不確定因素。
-不能對高級的排產(chǎn)調(diào)度規(guī)則加以建模,通常只能用禁止弧機制體現(xiàn)一些低級控制。
(5)基于排序的方法
該方法是先有可行性加工順序,然后才確定每個操作的開工時間,并對這個順序進行優(yōu)化,它雖然屬于近似算法,但有可能達(dá)到最優(yōu)的排產(chǎn)調(diào)度方案。它主要包括鄰近搜索法,它在生產(chǎn)排產(chǎn)調(diào)度領(lǐng)域得到了相當(dāng)廣泛的應(yīng)用,在探索解空間時,僅對選定的成本函數(shù)值的變化做出響應(yīng),因而通用性強。
這類方法包括局部探索(Local Search)、模擬退火法(Simulated Annealing)、列表尋優(yōu)法(Table Search),遺傳算法(Genetic Algorithms)。鄰近搜索雖然可能得到最優(yōu)的排產(chǎn)調(diào)度方案,但也存在各自的不足, 很多采取混合算法來彌補單一方法的不足。
-啟發(fā)式圖搜索法
對于表述為整數(shù)規(guī)劃的排產(chǎn)調(diào)度問題,最初采用分枝定界法來解決,而后其他的啟發(fā)式圖搜索法也被應(yīng)用于解決排產(chǎn)調(diào)度問題。
將排產(chǎn)調(diào)度排序問題用一個圖來表示,首先構(gòu)造一個可行解,采用基于隱枚舉的搜索方法不斷提高解的次優(yōu)性;采用束搜索法(beam search)來識別瓶頸機器,進行排產(chǎn)調(diào)度;為了解決搜索空間太大的問題,通過對分枝定界法和約束搜索法進行系統(tǒng)的分析,提出了一種過濾束搜索法(filter beam search),用來解決單臺機器提前/延期問題和加權(quán)延期的 Flow Shop問題;對于圖搜索算法,如何提高搜索效率并減少內(nèi)存使用以解決規(guī)模較大的問題,還需要進一步探索。
-模擬退火法
模擬退火算法(SA)將組合優(yōu)化問題與統(tǒng)計力學(xué)中的熱平衡問題類比,另辟了求解組合優(yōu)化問題的新途徑。它通過模擬退火過程,可找到全局(或近似)最優(yōu)解。其基本思想為:把每種組合狀態(tài) Si看成某一物質(zhì)系統(tǒng)的微觀狀態(tài),而將其對應(yīng)的目標(biāo)函數(shù)C(Si)看成該物質(zhì)系統(tǒng)在狀態(tài)Si下的內(nèi)能;用控制參數(shù)T類比溫度,讓T從一個足夠高的值慢慢下降,對每個T,用 Metropolis抽樣法在計算機上模擬該體系在此T下的熱平衡態(tài),即如果 C(s’),對當(dāng)前狀態(tài)Si作隨機擾動以產(chǎn)生一個新狀態(tài)s’。
模擬退火法的幾個重要部分為:生成函數(shù)(generation)、容忍函數(shù)(acceptance function)、 Markov鏈長、降溫過程和結(jié)束準(zhǔn)則。模擬退火法的改進算法有加溫退火法、有記憶的模擬退火法等。
為Flow Shop問題求解構(gòu)造了一類模擬退火法,并通過六種不同的隨機抽樣方式分析了算法漸近收斂于全局最優(yōu)解,分別解決了具有最小Make Span指標(biāo)且具有無限中間存儲(UIS)、有限中間存儲(FIS)和無中間存儲(NIS)的 Flow Shop排序問題;
一種改進的模擬退火法,用來解決具有最小 Make span指標(biāo)的 Flow Shop排序問題,并與禁忌搜索法等進行了比較;另外,模擬退火法也可與其他方法相結(jié)合進行求解,如先用貪心法(greedy法)搜索,將得到的作業(yè)序列作為初始解,再用模擬退火法求解單機排產(chǎn)調(diào)度問題,其結(jié)果表明這種方法比單純用模擬退火法和貪心法要好;將模擬退火法與啟發(fā)式算法相結(jié)合的方法,求解具有交貨期約束的Job Shop排產(chǎn)調(diào)度問題。
由于模擬退火法能以一定的概率接受差的能量值,因而有可能跳出局部極小,但它的收斂速度較慢,很難用于實時動態(tài)排產(chǎn)調(diào)度環(huán)境。
-禁忌搜索法
對于復(fù)雜的組合優(yōu)化問題,禁忌搜索也是一種通過領(lǐng)域搜索以獲取最優(yōu)解的方法。禁忌搜索是一種迭代方法,它開始于一個初始可行解S,然后移動到領(lǐng)域N(S)中最好的解s’,即s’,對于目標(biāo)函數(shù)F(S)在領(lǐng)域 N(S)中是最優(yōu)的。然后,從新的開始點重復(fù)此法。
為了避免死循環(huán),禁忌搜索把最近進行的T個移動(T可固定也可變化)放在一個稱作 tabu list的表中(也稱短期記憶),在目前的迭代中這些移動是被禁止的,在一定數(shù)目的迭代之后它們又被釋放出來。這樣的tabu list是一個循環(huán)表,它被循環(huán)地修改,其長度T稱作Tabu size。最后,還須定義一個停止準(zhǔn)則來終止整個算法。由于tabu list的限制,使其在搜索中有可能跳出局部極小。針對求解交貨期下帶有等待時間懲罰的提前/拖期單機排產(chǎn)調(diào)度問題。
-神經(jīng)網(wǎng)絡(luò)優(yōu)化
Hopfield神經(jīng)網(wǎng)絡(luò)模型的提出為求解各種有約束優(yōu)化問題開辟了一條新途徑,它的主要思路是:通過一個Lyaplmov能量函數(shù)構(gòu)造網(wǎng)絡(luò)的極值,當(dāng)網(wǎng)絡(luò)迭代收斂時,能量函數(shù)達(dá)到極小,使與能量函數(shù)對應(yīng)的目標(biāo)函數(shù)得到優(yōu)化。
隨機 Hopfield網(wǎng)絡(luò)來解決 Job Shop排產(chǎn)調(diào)度問題的方法;改進的Hopfield網(wǎng)絡(luò)的整數(shù)線性規(guī)劃神經(jīng)網(wǎng)絡(luò)方法來解決 Job Shop排產(chǎn)調(diào)度問題。
-遺傳算法
美國Michigan大學(xué)的J.H.Holland于本世紀(jì)末提出了一種新的并行優(yōu)化搜索方法:遺傳算法(Genetic Algorithm),它是一種基于進化論優(yōu)勝劣汰、自然選擇、適者生存和物種遺傳思想的隨機優(yōu)化搜索算法,通過群體的進化來進行全局性優(yōu)化搜索。
它以其很強的并行性和很高的計算效率正日益受到人們的關(guān)注。它對組合優(yōu)化問題求解的主要過程是:給定一組初始解作為一個群體,通過選擇、交換和變異等遺傳操作符來搜索問題的最優(yōu)解。
基于遺傳算法的啟發(fā)式方法,用于解決以最小化Make span為指標(biāo)的flow shop排產(chǎn)調(diào)度問題;可以將遺傳算法與圖搜索法相結(jié)合,利用遺傳算法進行知識的推理、啟發(fā),再用過濾束搜索法(filter beam search)進行優(yōu)化搜索,以得到高質(zhì)量的制造靜態(tài)排產(chǎn)調(diào)度。
總的來說,遺傳算法的最大優(yōu)點是通過群體間的相互作用,保持已經(jīng)搜索到的信息,這是基于單次搜索過程的優(yōu)化方法所無法比擬的。但是,遺傳算法也存在著計算速度較慢的問題。
(6)人工智能的排產(chǎn)調(diào)度方法
近年來受實際需要的推動,基于知識的智能排產(chǎn)調(diào)度系統(tǒng)和方法的研究取得了很大的進展。人工智能在上個世紀(jì)60年代就將計劃問題作為其應(yīng)用領(lǐng)域之一,但直到上個世紀(jì)80年代,開展基于約束傳播的ISIS(Intelligent Scheduling and Information System)的研究為標(biāo)志,人工智能才真正開始應(yīng)用于排產(chǎn)調(diào)度問題。
基于知識的排產(chǎn)調(diào)度方法是用專家系統(tǒng)自動產(chǎn)生排產(chǎn)調(diào)度或輔助人去排產(chǎn)調(diào)度。它是將傳統(tǒng)的排產(chǎn)調(diào)度方法與基于知識的排產(chǎn)調(diào)度評價相結(jié)合的方法。
在支持某些活動發(fā)生的資源條件具備時(稱為決策點),根據(jù)系統(tǒng)當(dāng)時所處的屬性狀態(tài),決定采取何種規(guī)則(策略),確定或選擇活動發(fā)生的順序和時間,即狀態(tài)指導(dǎo)的智能排產(chǎn)調(diào)度方法。
總的來說,主要包括智能排產(chǎn)調(diào)度專家系統(tǒng)、基于智能搜索的方法及基于多代理技術(shù)(Multi-Agent System 簡稱MAS)的合作求解的方法等。其中,智能排產(chǎn)調(diào)度專家系統(tǒng)是人工智能應(yīng)用的體現(xiàn),由于專家系統(tǒng)中知識獲取和推理速度這兩個瓶頸,使得神經(jīng)網(wǎng)絡(luò)逐漸被采用,但還存在訓(xùn)練速度慢、探索能力弱等缺點。
基于多代理技術(shù)的合作求解方法是較新的智能排產(chǎn)調(diào)度方法,它提供了一種動態(tài)靈活、快速響應(yīng)市場的生產(chǎn)排產(chǎn)調(diào)度機制,它以分布式人工智能(Distributed Artificial Intelligence簡稱DAI)中的多代理機制作為新的生產(chǎn)組織與運行模式,通過代理(Agent)之間的合作以及MAS系統(tǒng)協(xié)調(diào)來完成生產(chǎn)任務(wù)的排產(chǎn)調(diào)度,并達(dá)到預(yù)先規(guī)定的生產(chǎn)目標(biāo)及生產(chǎn)狀態(tài)。在這種研究方法中,在Agent內(nèi)部也可采用基于規(guī)則及智能推理相結(jié)合的混合方法,來構(gòu)造基于MAS的生產(chǎn)排產(chǎn)調(diào)度系統(tǒng)。
六、排產(chǎn)調(diào)度方法存在的問題
排產(chǎn)調(diào)度領(lǐng)域中的大部分問題都具有NP問題,雖然對它的研究已有幾十年的歷史,但至今尚未形成一套系統(tǒng)的方法和理論,理論研究與實際應(yīng)用之間還存在著很大差距。尤其隨著JIT(Just-In-Time)思想的廣泛采用,E/T(Earliness/Tardiness)排產(chǎn)調(diào)度問題,即使得工件盡量按交貨期完成,變得越來越突出。
實際應(yīng)用中的排產(chǎn)調(diào)度方法能夠響應(yīng)系統(tǒng)的動態(tài)變化,但不能保證得到好的排產(chǎn)調(diào)度:一些理論上的最優(yōu)化方法能提供最優(yōu)排產(chǎn)調(diào)度,但由于其計算的復(fù)雜性,并且忽略了很多實際因素,離實際運用還有較大距離。基于最優(yōu)化的方法,諸如動態(tài)規(guī)劃算法與分枝定界算法等等,由于其大多數(shù)是建立在對可能排產(chǎn)調(diào)度的部分枚舉上,因此只能解決小規(guī)模的排產(chǎn)調(diào)度問題,距離實用還有較大距離。
由于大多排產(chǎn)調(diào)度問題屬于一類NP困難組合問題,因此尋找具有多項式復(fù)雜性的最優(yōu)算法幾乎是不可能的。但因其解的最優(yōu)性、至今仍激發(fā)著學(xué)者們進行不斷的探索。
各種近似啟發(fā)式方法、諸如基于規(guī)則的算法等,由于能在合理的時間內(nèi)產(chǎn)生比較滿意的排產(chǎn)調(diào)度,因此廣泛應(yīng)用于實際排產(chǎn)調(diào)度中,但其往往對所得的排產(chǎn)調(diào)度解的次優(yōu)性不能進行評估。
在這方面有必要探索更好的近似最優(yōu)排產(chǎn)調(diào)度算法,可以考慮增加合理的計算時間代價,提高解的次優(yōu)性。各種基于統(tǒng)計優(yōu)化的方法、諸如模擬退火法、遺傳算法等,提供了一種解決排產(chǎn)調(diào)度優(yōu)化問題的新途徑,但同別的優(yōu)化算法類似,其也存在著一定程度的校舉、一般來說收斂到最優(yōu)解很慢,并且對于判斷解的最優(yōu)性也很困難。
在實際車間排產(chǎn)調(diào)度中,計劃與車間排產(chǎn)調(diào)度往往是分層進行的,但這可能造成計劃在實際排產(chǎn)調(diào)度中的不可行問題,如何將計劃與排產(chǎn)調(diào)度結(jié)合考慮,以求總體的優(yōu)化也是需要進一步研究的。另外,還有很多有待進一步研究的問題,比如實際車間排產(chǎn)調(diào)度的多目標(biāo)性等。排產(chǎn)調(diào)度理論、方法與應(yīng)用的研究是一項非常艱巨的工作,目前人們還在進行各種各樣的探索性研究工作。
由于排產(chǎn)調(diào)度問題的復(fù)雜性,實際生產(chǎn)排產(chǎn)調(diào)度的目標(biāo)應(yīng)定為尋找一個好的、可行的的解決方案而常常不是最優(yōu)的方案。盡管有大量的解決排產(chǎn)調(diào)度的方案,但是只有少數(shù)的方法應(yīng)用于實際。其中,基于智能的排產(chǎn)調(diào)度方法應(yīng)用人類專家的經(jīng)驗及特殊領(lǐng)域的知識,在解決排產(chǎn)調(diào)度問題上已經(jīng)做出了很多成績。
關(guān)鍵技術(shù)
尋找車間排產(chǎn)調(diào)度的最優(yōu)解從理論上將是NP-完全問題,沒有一個確定的算法來解決這個問題。許多約束條件,使得實際的排產(chǎn)調(diào)度問題變得非常困難,比如:設(shè)備的可選性、制造環(huán)境的動態(tài)與不確定性、約束條件的矛盾(最小加工時間與最大設(shè)備利用率)等等,實際上,生產(chǎn)排產(chǎn)調(diào)度問題大部分是集中于簡化問題,然后尋找最優(yōu)解或次優(yōu)解。研究與開發(fā)排產(chǎn)調(diào)度系統(tǒng)面臨的關(guān)鍵問題主要有:
-信息表達(dá):
包括排產(chǎn)調(diào)度任務(wù)及特殊信息(工作能力、可選生產(chǎn)計劃等)的描述。
-交互性設(shè)計:
交互性不單指人機界面的問題,它應(yīng)支持人對排產(chǎn)調(diào)度過程的直接參與,因為純粹的自動化排產(chǎn)調(diào)度是不現(xiàn)實的,它忽略了具有最終決策職責(zé)的排產(chǎn)調(diào)度行家的重要作用。
-多種排產(chǎn)調(diào)度方法的結(jié)合
與已有信息環(huán)境的集成:現(xiàn)有企業(yè)都已具有了自己的信息技術(shù)基礎(chǔ)結(jié)構(gòu),排產(chǎn)調(diào)度系統(tǒng)應(yīng)能與現(xiàn)有環(huán)境進行通訊與信息交換,并作為信息系統(tǒng)的一部分,因此應(yīng)提供與標(biāo)準(zhǔn)系統(tǒng)(如數(shù)據(jù)庫、網(wǎng)絡(luò)等)的通用接口。
相關(guān)技術(shù)
從系統(tǒng)分析方法學(xué)角度而言,解決車間作業(yè)優(yōu)化排產(chǎn)調(diào)度與控制主要涉及:
-運籌學(xué):
復(fù)雜系統(tǒng)分析、各種數(shù)學(xué)模型的分析與建立。
-人工智能理論:
神經(jīng)網(wǎng)絡(luò)的方法、基于智能搜索的方法、基于多代理技術(shù)的合作求解的方法。用于實時控制的動態(tài)排產(chǎn)調(diào)度及建模方法。
從信息技術(shù)角度而言,車間作業(yè)排產(chǎn)調(diào)度與控制技術(shù)是計算機應(yīng)用領(lǐng)域面臨的一個非常重要的難題,主要涉及的關(guān)鍵技術(shù)有:
-計算機網(wǎng)絡(luò)與通信技術(shù)
-數(shù)據(jù)庫技術(shù)
-系統(tǒng)建模與仿真技術(shù)
-人機接口
-虛擬現(xiàn)實技術(shù)
【主要優(yōu)化排產(chǎn)調(diào)度網(wǎng)址】
Production Scheduling Models
http://www.informs.org/Conf/SD97/TALKS/MD23.html
A Direct Hot Charge Steel Production Scheduling System
http://www.informs.org/Conf/NO95/TALKS/SD3.3.html
Partners in Excellence: Production Scheduling and Releases
http://www.uta.com/do/pie/sec131.htm
Article - Production Scheduling Routing and Bill of Materials
http://www.cybor.co.nz/news/prosch.html
Article - Capacity Planning and Real Time Production Scheduling
http://www.cybor.co.nz/news/capplan.html
finishing.com Software, Education, & Training Directory
http://www.finishing.com/Directory/software.html
Production & Scheduling
http://www.informs.org/Conf/Dallas97/TALKS/TD09.html
Master Production Scheduling
http://www.ems.com/education/seminars/pln_seminars/pln_mps.htm
Master Production Scheduling:
http://www.ie.eng.ua.edu/current ... ie464-9/tsld002.htm
Sci.Op-Research (1995) by author
http://mat.gsiaNaNu.edu/GROUP95C/author.html
Sci.Op-Research (1995) by date
http://mat.gsiaNaNu.edu/GROUP95C/date.html
Maestro: Production Scheduling [JJT Inc.]
http://www.compassionatefriends.org/scheduling.html
Production Scheduling & Shop Floor Control
http://www.monitorsoftware.com/product.htm
Master Production Scheduling:
http://www.ie.eng.ua.edu/current ... /ie464-9/sld002.htm
Sci.Op-Research (1995) by thread
http://mat.gsiaNaNu.edu/GROUP95C/index.html
MPS-Master Production Scheduling Module - Integrated Manufacturing Solutions
http://www.magimfg.com/Master_Production_Scheduler.htm
Tempo Adds Value to Factory Production Scheduling
http://www.sm.com/sched/tempo/default.htm
Production Scheduling [3,p191]
http://www-mec.eng.monash.edu.au ... _control/sld014.htm
Production Scheduling [3,p191]
http://www-mec.eng.monash.edu.au ... control/tsld014.htm
Production Scheduling Workstation
http://www.objectapps.com/Produc ... lingWorkstation.htm
Production Scheduling in the Supply Chain Environments
http://www.informs.org/Conf/Montreal98/TALKS/TE10.html
CIM Assignment Production scheduling
http://http2.brunel.ac.uk:8080/~ ... ments/schedule.html
Production Scheduling & Capacity Reservation Systems
http://www.informs.org/Conf/SD97/TALKS/MD09.html
Production & Scheduling II
http://www.informs.org/Conf/Montreal98/TALKS/WC08.html
Production Scheduling Problems at Bethlehem Steel Corporation
http://www.informs.org/Conf/WA96/TALKS/ME18.3.html
Production Scheduling I
http://www.informs.org/Conf/SD97/TALKS/SA10.html
Production Scheduling & Due Date Management
http://www.informs.org/Conf/SD97/TALKS/MC23.html
中國很多企業(yè)處于亞健康狀態(tài),其特征是“三高”即高交期、高庫存、高成本。精益生產(chǎn)、MES、APS、供應(yīng)鏈優(yōu)化是消除企業(yè)三高的良方,建立高效的計劃執(zhí)行架構(gòu)體系,實現(xiàn)卓越制造。
? ? ? ? ? ? ? ? ? ? ? 摘自---蔡穎 高效計劃與智能排程研究會---------------