遺傳算法求解一類帶工藝約束的并行機調度問題.pdf

1、作業(yè)車間調度問題（JSSP）是一類典型的生產調度問題，具有很強的工程背景，許多實際工程問題均可與之相轉化。近年來，隨著先進制造技術的發(fā)展，車間調度問題的含義有所拓展，增加了隨機性、動態(tài)性、不確定性、約束性、多目標等，與實際生產更為接近。JSSP屬于NP完全類，因此開發(fā)求解JSSP的有效算法一直是調度和優(yōu)化領域的重要課題。并行機調度(ParallelMachineScheduling,PMS)是現(xiàn)實生活中廠礦企業(yè)經常面臨的一類問題，一個作

2、業(yè)分成幾道工序來完成。它允許工序由一個機床集合中的任意一臺加工，調度的目的是將工序分配給各機床，并對各機床上的工序進行排序以使完成所有工序的時間最小化。遺傳算法是基于“優(yōu)勝劣汰、適者生存”的一種高度并行、隨機和自適應優(yōu)化算法。它將問題的求解表示成染色體的適者生存過程，通過染色體群的一代代不斷進化，包括復制、交叉和變異等操作,最終收斂到“最適應環(huán)境”的個體，從而求得問題的最優(yōu)解或滿意解。GA原理和操作簡單，通用性強，不受限制性條件的約束，

3、且具有隱含并行性和全局解空間搜索能力，在機器學習、模式識別、控制工程、VLSI設計等領域,尤其是在生產調度領域得到廣泛的應用。如何利用GA高效求解JSP,一直被認為是一個具有挑戰(zhàn)意義的難題并成為研究的熱點。本文主要針對一個具體的生產調度實例，采用自己的編碼形式來求解；從結果來看，此方法簡單易行，收斂快，適用范圍廣，是完全可行的一種求解方法。遺傳算法已經成功應用于組合優(yōu)化問題，如TSP，于是很多研究人員想到用遺傳算法這種搜尋技術來解決調度

4、問題。并行機調度工序時，允許工序由一個機床集合中的任意一臺加工（機床集合一般由工藝約束決定），而這更符合生產實際情況。并行機調度比一般調度問題復雜，因為前者不僅要決定怎樣把各工序分配到機器上，還要實時確定每臺機器的工序操作次序。本文的目的就是試圖用遺傳算法來解決一類帶工藝約束的并行機調度問題?，F(xiàn)代生產系統(tǒng)運行管理的核心是生產計劃與調度理論和技術，由于工業(yè)生產系統(tǒng)運行管理復雜的特點，故其生產計劃調度與控制十分重要。它對降低生產成本、縮短制

5、造周期、提高生產效益均具有重要的意義。生產調度問題是一個資源分配問題，只不過這里的資源是設備而已。一個調度是按先后順序條件將所有任務安排到設備上的一種方案，通常約束的數(shù)目很大，使得生產調度問題成為一個非常難解的NP完全問題。隨著問題規(guī)模的擴大，生產調度算法的復雜性呈指數(shù)增長，目前一般都選用啟發(fā)式調度規(guī)則進行生產實時調度。由于調度規(guī)則是基于經驗，故沒有普遍適用的規(guī)則存在，某一規(guī)則只能運用于一定的場合，應用調度規(guī)則求得的解也只是問題的近似解