車間作業(yè)調(diào)度jobshopscheduling講解(更新版)
【正文】 op調(diào)度問(wèn)題的特殊性 ， 編碼機(jī)制顯得尤為重要 ，因?yàn)榫幋a機(jī)制選擇不當(dāng) ， 遺傳算法的雜交 、 變異算子很容易破壞原加工順序 。 ?機(jī)器上約束：每臺(tái)機(jī)器每一個(gè)時(shí)刻最多只能執(zhí)行一個(gè)工件，且該工序的執(zhí)行時(shí)間是非搶占的。長(zhǎng)期以來(lái)， JSS研究的方法始終以啟發(fā)式算法為主導(dǎo)，絕大部分的 JSS研究工作也都圍繞著啟發(fā)式算法進(jìn)行，如基于啟發(fā)式算法的 JSS仿真系統(tǒng)，基于啟發(fā)式算法的并行JSS系統(tǒng)，基于啟發(fā)式算法的 JSS專家系統(tǒng)，等等，盡管這些研究取得了一定的應(yīng)用效果，但是卻存在著難以克服的弱點(diǎn)，如計(jì)算規(guī)模不可能較大，尋優(yōu)結(jié)果不具備全局特性等等。 問(wèn)題描述： ?假設(shè)有 n個(gè)工件 {J1,J2,…,Jn} 要在 m臺(tái)機(jī)器{M1,M2,…,Mm} 上進(jìn)行加工。如何安排在每臺(tái)機(jī)器上工件的加工順序，使得總的完工時(shí)間 (Makespan)最小。 Jobshop的求解方法 局部搜索（ Local Search） 禁忌搜索（ Tabu Search） 遺傳算法（ Geic Algorithm） 混合進(jìn)化算法 (Memetic Algorithm) 局部搜索算法 ?領(lǐng)域結(jié)構(gòu)（ Neighborhood） :將一個(gè)初始解進(jìn)行微小變動(dòng)以后，產(chǎn)生的解的集合。不產(chǎn)生不可行解，效率高。 ?禁忌長(zhǎng)度 : 每個(gè)解 被禁忌的時(shí)間長(zhǎng)度。 遺傳算法基本概念和術(shù)語(yǔ) ?遺傳算法是模擬前述生物進(jìn)化過(guò)程的計(jì)算模型。一般而言，選擇的過(guò)程是一種基于適應(yīng)度的優(yōu)勝劣汰的過(guò)程。 遺傳算法解決 Job shop的幾個(gè)重要構(gòu)成要素 （ 1）染色體編碼方法 {1 2 3 ； 3 1 2 ； 2 3 1} 基本遺傳算法的構(gòu)成要素 （ 2）交叉過(guò)程 下面是一種基于最長(zhǎng)公共子序列的交叉算符，對(duì)兩個(gè)父親個(gè)體的每個(gè)機(jī)器都進(jìn)行如下操作，產(chǎn)生兩個(gè)子代個(gè)體： 遺傳算法的幾個(gè)重要構(gòu)成要素 （ 3）適應(yīng)度評(píng)價(jià)函數(shù) 函數(shù)的主要部分是基于最大完工時(shí)間(Makespan)。 Hybrid Evolution AlgorithmMemetic 部分算例的解 : 謝謝大家
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1