遺傳算法求解一類(lèi)帶工藝約束的并行機(jī)調(diào)度問(wèn)題.pdf

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

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

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

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

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