車間作業(yè)調(diào)度jobshopscheduling講解(編輯修改稿)
2025-06-17 13:26 本頁面
【文章內(nèi)容簡介】 ：領(lǐng)域結(jié)構(gòu)的構(gòu)造。在 Jobshop中，對所有機器上的每個工件都考慮其領(lǐng)域結(jié)構(gòu)，效率是非常低下的 ,也可能導(dǎo)致不可行解的產(chǎn)生。通常是考慮基于關(guān)鍵路勁的領(lǐng)域結(jié)構(gòu)構(gòu)造方法。 ?關(guān)鍵路徑：調(diào)度序列中的最長路徑，它制約著整個調(diào)度的完工時間。 局部搜索算法 關(guān)鍵塊 ? 關(guān)鍵塊：連續(xù)的一組關(guān)鍵工序，因而，可能存在多個關(guān)鍵塊。 ? 目前的領(lǐng)域結(jié)構(gòu)都是基于關(guān)鍵塊的，有多種領(lǐng)域操作，但都是基于移動關(guān)鍵塊兩端的工序。不產(chǎn)生不可行解，效率高。 局部搜索算法的不足 ?當遇到局部極值的時候， Local search 的算法將遇到瓶頸，從而需要更多的策略或更好的算法跳出local optima。 跳坑策略以及 ILS ?跳坑策略：對當前解進行大的改動（擾動）。 ?迭代局部搜索算法：結(jié)合跳坑策略形成的算法。 禁忌搜索 (Tabu Search) ?提出 : 由美國工程院院士，馮若依曼理論獎獲得者Fred Glover 最先在 1986年提出 Tabu Search算法。 ? Tabu Search : 將之前搜索過的解 禁忌，每次只選擇沒被禁忌的解或滿足解禁策略的解。因而，它可以接受比自身差的解，從而跳出局部極值點，去搜索新的解空間。 ?解禁策略：遇到一個雖被禁忌，但卻比歷史最優(yōu)解還要好的解時，解禁，選擇此解。 ?禁忌長度 : 每個解 被禁忌的時間長度。 ?禁忌對象：可以禁忌 完整的解，也可以禁忌 部分解 或是 領(lǐng)域動作。 禁忌搜索 (Tabu Search) ?禁忌對象的選擇一般與相應(yīng)的領(lǐng)域結(jié)構(gòu)對應(yīng)起來，效果會比較好。 ? Jobshop中常用的禁忌對象：若 JA 插入 JB之后，則將 JA和 JB之間的所有工序的排列和在機器上的位置禁忌住，標記在禁忌列表 (Tabu_List)里。 遺傳算法概述 ?遺傳算法（ Geic Algorithms ,GA）研究的歷史比較短， 20世紀 60年代末期到 70年代初期，主要由美國 Michigan大學(xué)的 John Holland與其同事、學(xué)生們研究形成了一個較完整的理論和方法，從試圖解釋自然系統(tǒng)中生物的復(fù)雜適應(yīng)過程入手，模擬生物進化的機制來構(gòu)造人工系統(tǒng)的模型。隨后經(jīng)過 20余年的發(fā)展，取得了豐
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1