車(chē)間作業(yè)調(diào)度jobshopscheduling講解.ppt

車(chē)間調(diào)度算法(job shop scheduling),彭博 2012-11-21,主要內(nèi)容,Jobshop 調(diào)度問(wèn)題 遺傳算法理論 遺傳算法在車(chē)間調(diào)度算法中的求解過(guò)程,問(wèn)題提出,車(chē)間作業(yè)調(diào)度(Job-Shop Scheduling),簡(jiǎn)稱(chēng)JSS,是一個(gè)典型的NP難問(wèn)題，是Operation Research領(lǐng)域中研究的重要課題。它的研究不僅具有重大的現(xiàn)實(shí)意義，而且具有深遠(yuǎn)的理論意義。長(zhǎng)期以來(lái)，JSS研究的方法始終以啟發(fā)式算法為主導(dǎo)，絕大部分的JSS研究工作也都圍繞著啟發(fā)式算法進(jìn)行，如基于啟發(fā)式算法的JSS仿真系統(tǒng)，基于啟發(fā)式算法的并行JSS系統(tǒng)，基于啟發(fā)式算法的JSS專(zhuān)家系統(tǒng)，等等，盡管這些研究取得了一定的應(yīng)用效果，但是卻存在著難以克服的弱點(diǎn)，如計(jì)算規(guī)模不可能較大，尋優(yōu)結(jié)果不具備全局特性等等。近年來(lái)，又有學(xué)者提出了基于神經(jīng)網(wǎng)絡(luò)的車(chē)間作業(yè)調(diào)度系統(tǒng)，但此種方法在JSS規(guī)模較大時(shí)，卻存在著計(jì)算速度慢與結(jié)構(gòu)參數(shù)難以確定的弱點(diǎn)。由此可見(jiàn)，要想進(jìn)一步研究JSS,選擇一種有效的方法極為必要。,問(wèn)題描述：,假設(shè)有 n個(gè)工件J1,J2,Jn 要在m臺(tái)機(jī)器M1,M2,Mm上進(jìn)行加工。每個(gè)工件以一定的次序在所有的機(jī)器上輪流加工。每個(gè)工件分成m個(gè)工序，而每個(gè)工序?qū)?yīng)了相應(yīng)的加工機(jī)器。其中，工序的加工時(shí)間給定。,J1: M1 M2 M3 J2: M3 M1 M2 J3: M2 M3 M1,工序1 工序2 工序3,約束,工件上約束：每個(gè)工件上的工序只能在上一個(gè)工序執(zhí)行結(jié)束以后，才能開(kāi)始執(zhí)行下一個(gè)工序。 機(jī)器上約束：每臺(tái)機(jī)器每一個(gè)時(shí)刻最多只能執(zhí)行一個(gè)工件，且該工序的執(zhí)行時(shí)間是非搶占的。 最大完工時(shí)間(Makespan)：完成所有工序所需要的總時(shí)間。,J1: M1 M2 M3 J2: M3 M1 M2 J3: M2 M3 M1,工序1 工序2 工序3,目標(biāo),有M臺(tái)機(jī)器及N個(gè)工件，由于工件的加工工藝的要求，每個(gè)工件使用M臺(tái)機(jī)器的次序以及每道工序所花費(fèi)的時(shí)間已經(jīng)給定。如何安排在每臺(tái)機(jī)器上工件的加工順序，使得總的完工時(shí)間(Makespan)最小。,Jobshop 調(diào)度問(wèn)題的實(shí)際應(yīng)用,在解決實(shí)際問(wèn)題的時(shí)候，“工件”和“機(jī)器”可以拓展成相應(yīng)的問(wèn)題描述。譬如：在生產(chǎn)車(chē)間當(dāng)中，把一個(gè)零件或是一組零件看是需要加工的“工件”，而把加工用的車(chē)床看成是“機(jī)器”；在飛機(jī)調(diào)度問(wèn)題中，可以將若干個(gè)不同的飛機(jī)看成“工件”，而將飛機(jī)需要進(jìn)行的操作，看成是需要操作的“機(jī)器”。 因而，job shop scheduling問(wèn)題的實(shí)際應(yīng)用是非常廣泛的。,遺傳算法在解Job-shop調(diào)度問(wèn)題方面的研究現(xiàn)狀,由于Job-Shop調(diào)度問(wèn)題是一個(gè)NP難題，而遺傳算法為求NP難度問(wèn)題的近似解提供了一種有效手段，所以現(xiàn)在許多人都致力于用遺傳算法解決Job-shop問(wèn)題，各有特點(diǎn)。但就目前來(lái)看： (1)由于Job-Shop調(diào)度問(wèn)題的特殊性，編碼機(jī)制顯得尤為重要，因?yàn)榫幋a機(jī)制選擇不當(dāng)，遺傳算法的雜交、變異算子很容易破壞原加工順序。 (2)死鎖問(wèn)題也是一個(gè)重要問(wèn)題，如果處理不當(dāng)，死鎖的出現(xiàn)是無(wú)法預(yù)料的。 (3)收斂性及收斂速度問(wèn)題，應(yīng)用GA解Job-Shop調(diào)度問(wèn)題時(shí)很少有人考慮這兩個(gè)問(wèn)題，所以得到的結(jié)果與最佳值的接近程度無(wú)理論保證。,Job-shop的求解方法,局部搜索（Local Search） 禁忌搜索（Tabu Search） 遺傳算法（Genetic Algorithm） 混合進(jìn)化算法(Memetic Algorithm),局部搜索算法,領(lǐng)域結(jié)構(gòu)（Neighborhood）:將一個(gè)初始解進(jìn)行微小變動(dòng)以后，產(chǎn)生的解的集合。,Neighborhood,局部搜索算法,從一個(gè)初始解開(kāi)始，每次從領(lǐng)域結(jié)構(gòu)中選擇一個(gè)最好的鄰居解作為下一個(gè)初始解，迭代搜索解空間的過(guò)程。,局部搜索算法,核心：領(lǐng)域結(jié)構(gòu)的構(gòu)造。在Job-shop中，對(duì)所有機(jī)器上的每個(gè)工件都考慮其領(lǐng)域結(jié)構(gòu)，效率是非常低下的,也可能導(dǎo)致不可行解的產(chǎn)生。通常是考慮基于關(guān)鍵路勁的領(lǐng)域結(jié)構(gòu)構(gòu)造方法。 關(guān)鍵路徑：調(diào)度序列中的最長(zhǎng)路徑，它制約著整個(gè)調(diào)度的完工時(shí)間。,局部搜索算法,關(guān)鍵塊,關(guān)鍵塊：連續(xù)的一組關(guān)鍵工序，因而，可能存在多個(gè)關(guān)鍵塊。 目前的領(lǐng)域結(jié)構(gòu)都是基于關(guān)鍵塊的，有多種領(lǐng)域操作，但都是基于移動(dòng)關(guān)鍵塊兩端的工序。不產(chǎn)生不可行解，效率高。,局部搜索算法的不足,當(dāng)遇到局部極值的時(shí)候，Local search 的算法將遇到瓶頸，從而需要更多的策略或更好的算法跳出local optima。,跳坑策略以及ILS,跳坑策略：對(duì)當(dāng)前解進(jìn)行大的改動(dòng)（擾動(dòng)）。 迭代局部搜索算法：結(jié)合跳坑策略形成的算法。,禁忌搜索(Tabu Search),提出 : 由美國(guó)工程院院士，馮若依曼理論獎(jiǎng)獲得者Fred Glover 最先在1986年提出Tabu Search算法。 Tabu Search : 將之前搜索過(guò)的解 禁忌，每次只選擇沒(méi)被禁忌的解或滿足解禁策略的解。因而，它可以接受比自身差的解，從而跳出局部極值點(diǎn)，去搜索新的解空間。 解禁策略：遇到一個(gè)雖被禁忌，但卻比歷史最優(yōu)解還要好的解時(shí)，解禁，選擇此解。 禁忌長(zhǎng)度: 每個(gè)解 被禁忌的時(shí)間長(zhǎng)度。 禁忌對(duì)象：可以禁忌 完整的解，也可以禁忌 部分解 或是 領(lǐng)域動(dòng)作。,禁忌搜索(Tabu Search),禁忌對(duì)象的選擇一般與相應(yīng)的領(lǐng)域結(jié)構(gòu)對(duì)應(yīng)起來(lái)，效果會(huì)比較好。 Job-shop中常用的禁忌對(duì)象：若JA 插入JB之后，則將JA和JB之間的所有工序的排列和在機(jī)器上的位置禁忌住，標(biāo)記在禁忌列表(Tabu_List)里。,遺傳算法概述,遺傳算法（Genetic Algorithms ,GA）研究的歷史比較短，20世紀(jì)60年代末期到70年代初期，主要由美國(guó)Michigan大學(xué)的John Holland與其同事、學(xué)生們研究形成了一個(gè)較完整的理論和方法，從試圖解釋自然系統(tǒng)中生物的復(fù)雜適應(yīng)過(guò)程入手，模擬生物進(jìn)化的機(jī)制來(lái)構(gòu)造人工系統(tǒng)的模型。隨后經(jīng)過(guò)20余年的發(fā)展，取得了豐碩的應(yīng)用成果和理論研究的進(jìn)展，特別是近年來(lái)世界范圍形成的進(jìn)化計(jì)算熱潮，計(jì)算智能已作為人工智能研究的一個(gè)重要方向，以及后來(lái)的人工生命研究興起，使遺傳算法受到廣泛的關(guān)注。,遺傳算法概述,從1985年在美國(guó)卡耐基梅隆大學(xué)召開(kāi)的第一屆國(guó)際遺傳算法會(huì)議(International Conference on Genetic Algorithms:ICGA85),到1997年5月IEEE Transactions on Evolutionary Computation創(chuàng)刊,遺傳算法作為具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計(jì)算和建模方法的研究漸趨成熟。,遺傳算法基本概念和術(shù)語(yǔ),遺傳算法是模擬前述生物進(jìn)化過(guò)程的計(jì)算模型。下面先給出幾個(gè)生物學(xué)的基本概念與術(shù)語(yǔ)，這對(duì)于理解遺傳算法是非常重要的。 染色體(chromosome)：具有遺傳性質(zhì)基因序列。 種群（population） 染色體帶有特征的個(gè)體的集合稱(chēng)為種群。該集合內(nèi)個(gè)體數(shù)稱(chēng)為群體的大小。,遺傳算法基本概念和術(shù)語(yǔ),適應(yīng)度（fitness） 在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕。 選擇（selection） 指決定以一定的概率從種群中選擇若干個(gè)體的操作。一般而言，選擇的過(guò)程是一種基于適應(yīng)度的優(yōu)勝劣汰的過(guò)程。,遺傳算法基本概念和術(shù)語(yǔ),交叉（crossover） 有性生殖生物在繁殖下一代時(shí)，兩個(gè)同源染色體通過(guò)交叉而重組，亦即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。這個(gè)過(guò)程又稱(chēng)基因重組（recombination），俗稱(chēng)“雜交”。 變異（mutation） 在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀。,基本遺傳算法的實(shí)現(xiàn)方法,各種不同的遺傳算法都有相同的的特點(diǎn)，即通過(guò)對(duì)生物遺傳和進(jìn)化過(guò)程中選擇、交叉、變異機(jī)理的模仿，來(lái)完成對(duì)問(wèn)題最優(yōu)解的自適應(yīng)搜索過(guò)程?；谶@個(gè)共同特點(diǎn)，Goldberg總結(jié)出了一種統(tǒng)一的最基本的遺傳算法基本遺傳算法（Simple Genetic Algorithm,簡(jiǎn)稱(chēng)SGA）。SGA只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。因此為方便起見(jiàn)，本文在以后的應(yīng)用中用此方法。,遺傳算法解決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)?？梢愿郊由蟼€(gè)體之間的距離，保持交叉的兩個(gè)個(gè)體的分散性，避免近親的后果。特例：兩個(gè)解相同個(gè)體的后代和父代的解也相同。,遺傳算法流程,Step1. 初始化種群（采用隨機(jī)策略） Step2. 隨機(jī)選擇兩個(gè)個(gè)體交叉，產(chǎn)生新個(gè)體加 入到種群。 Step3. 根據(jù)適應(yīng)度函數(shù)，對(duì)種群進(jìn)行維護(hù)，淘汰掉適應(yīng)度低的個(gè)體。 Step4. 沒(méi)有到達(dá)終止條件，就Goto Step 2.,Hybrid Evolution Algorithm-Memetic,Memetic Algorithm:將Local Sea