求解作業(yè)車間調(diào)度問題的高效算法研究

前言

　　從有資源分配的時(shí)代開始，人類就開始接觸到調(diào)度問題。從人們?cè)趹?zhàn)爭(zhēng)中對(duì)軍隊(duì)的調(diào)度到從事農(nóng)耕、娛樂、運(yùn)輸、制作中對(duì)人力和物資的分配與調(diào)度，人類很早就感受到了在有限資源條件下完成指定的任務(wù)需要調(diào)度。然而，一個(gè)很有意思的現(xiàn)象是，雖然調(diào)度問題在軍事、生活等方面的活動(dòng)中普遍存在，但是嚴(yán)格地研究這個(gè)問題卻是在數(shù)千年之后。提出調(diào)度問題的數(shù)學(xué)模型的出現(xiàn)是很晚的，1954年，S.M.Johnson提出了求解流水車間兩臺(tái)機(jī)器下調(diào)度問題最優(yōu)解的法則，這是第一個(gè)求解調(diào)度問題的數(shù)學(xué)模型，Ramser于1959年首次提出交通調(diào)度問題。這既不同于歐拉研究哥尼斯堡七橋問題從而導(dǎo)致圖論的創(chuàng)立，又不同于17世紀(jì)人們從研究投骰子賭博現(xiàn)象而提出的概率論。筆者很早就注意到了這一現(xiàn)象，并做了一些調(diào)查研究，但是到目前為止都沒有找到解釋這個(gè)現(xiàn)象的文獻(xiàn)?；谌藗兡壳皩?duì)各種調(diào)度問題的研究成果，筆者猜想人們數(shù)千年以來都是采用增加資源和人為強(qiáng)制介入的辦法（某種強(qiáng)權(quán)干預(yù)資源分配）來解決現(xiàn)實(shí)中的調(diào)度問題，從而誤導(dǎo)人們認(rèn)為“該問題不是數(shù)學(xué)問題”。當(dāng)然，也可能因?yàn)檫@個(gè)問題過于復(fù)雜，不顯得“有趣”?！　?999年起，筆者開始攻讀博士學(xué)位，師從國際知名的NP難問題研究專家黃文奇教授。我因此有機(jī)會(huì)更加深入地了解了調(diào)度問題，并選擇了作業(yè)車間調(diào)度問題作為我博士論文的研究?jī)?nèi)容。眾所周知，NP難問題是理論計(jì)算機(jī)科學(xué)領(lǐng)域的重要研究對(duì)象，作業(yè)車間調(diào)度問題不僅是NP難的，還被認(rèn)為是最難的組合最優(yōu)化問題之一。人們已經(jīng)知道，為解決工業(yè)生產(chǎn)、物流、經(jīng)濟(jì)管理和網(wǎng)絡(luò)通信等諸多方面的問題，可以借助于求解作業(yè)車間調(diào)度問題的結(jié)果。所以，高效、快速地求解作業(yè)車間調(diào)度問題，既有重要的理論意義，又有重大的應(yīng)用價(jià)值?！　∪藗?yōu)榱饲蠼庾鳂I(yè)車間調(diào)度問題提出了許多方法。在黃文奇教授的悉心指導(dǎo)下，我認(rèn)真總結(jié)了前人的研究結(jié)論，提出了一套求解該問題的方法并完成我的博士論文。特別要指出的是，用我的方法找到了一個(gè)大規(guī)模實(shí)例（50個(gè)作業(yè)，20臺(tái)機(jī)器，1000個(gè)工序）到目前為止的最好解。博士畢業(yè)后，我進(jìn)一步鉆研求解這個(gè)問題的高效率算法的設(shè)計(jì)，提出了擬物擬人方法。擬物擬人方法同原有的方法都不同，雖然這方面的研究剛剛起步，但是可以預(yù)見到它有很好的發(fā)展前景，本書將這個(gè)研究的相關(guān)結(jié)果收錄進(jìn)來了。　　……

內(nèi)容概要

　　本書專門討論了作業(yè)車間調(diào)度問題，提出了改進(jìn)的轉(zhuǎn)換瓶頸算法、一個(gè)混合式鄰域搜索算法、擴(kuò)展HLS的算法、基礎(chǔ)的擬物擬人算法、帶禁忌規(guī)則的擬物擬人算法等一系列求解該問題的高效算法?！　”緯m合計(jì)算機(jī)專業(yè)本科高年級(jí)學(xué)生、研究生閱讀，可供計(jì)算性與算法復(fù)雜性的研究人員閱讀。

書籍目錄

前言第1章 緒論　1.1 組合最優(yōu)化問題　1.2 實(shí)際難解性和NP完全問題　1.3 啟發(fā)式方法　　1.3.1 基本策略　　1.3.2 性能評(píng)價(jià)　　1.3.3 算法類型　　1.3.4 擬物擬人算法　1.4 作業(yè)車間調(diào)度問題及其算法概論　1.5 本書研究?jī)?nèi)容及工作安排　1.6 本章 小結(jié)第2章 改進(jìn)的轉(zhuǎn)換瓶頸算法　2.1 問題的描述及其形式化　　2.1.1 問題的描述　　2.1.2 問題的形式化　2.2 轉(zhuǎn)換瓶頸算法　　2.2.1 問題的一種直觀表示和一個(gè)定理　　2.2.2 轉(zhuǎn)換瓶頸算法　2.3 定理2.2的證明　　2.3.1 一個(gè)關(guān)于單機(jī)調(diào)度的引理　　2.3.2 定理2.2的證明　2.4 改進(jìn)的轉(zhuǎn)換瓶頸算法ISB　　2.4.1 帶擾動(dòng)的Schrage算法　　2.4.2 關(guān)于擾動(dòng)系數(shù)　2.5 部分回溯算法　2.6 對(duì)典型實(shí)例的計(jì)算結(jié)果　2.7 本章 小結(jié)第3章 一個(gè)混合式鄰域搜索算法　3.1 Tabu搜索與作業(yè)車間調(diào)度問題　　3.1.1 Tabu搜索　　3.1.2 作業(yè)車間調(diào)度問題中的Tabu搜索　3.2 鄰域搜索算法HLS　　3.2.1 鄰域結(jié)構(gòu)　　3.2.2 初始解和禁忌表　　3.2.3 一個(gè)基于擬人策略的吸引準(zhǔn)則　　3.2.4 集中和分散策略　　3.2.5 新的鄰域搜索算法　3.3 對(duì)實(shí)例的計(jì)算結(jié)果　3.4 本章 小結(jié)第4章 擴(kuò)展HLS的算法　4.1 常用的鄰域結(jié)構(gòu)　4.2 新鄰域結(jié)構(gòu)的基礎(chǔ)　　4.2.1 兩種新的移動(dòng)　　4.2.2 關(guān)于新移動(dòng)的兩個(gè)定理　4.3 新的混合算法TSISB　　4.3.1 新鄰域的定義　　4.3.2 新的禁忌表　4.4 含隨機(jī)策略的鄰域搜索算法SHLS　4.5 對(duì)實(shí)例的計(jì)算結(jié)果　4.6 關(guān)于最長(zhǎng)路徑長(zhǎng)度的計(jì)算　4.7 本章 小結(jié)第5章 各種啟發(fā)式算法的比較　5.1 基于鄰域搜索算法之比較　5.2 與典型啟發(fā)式算法的比較和分析　5.3 本章 小結(jié)第6章 基礎(chǔ)的擬物擬人算法　6.1 作業(yè)車間調(diào)度問題的物理模型　　6.1.1 作業(yè)車間調(diào)度問題的彈性物理模型　　6.1.2 彈性力和位移量　6.2 擬物算法的基礎(chǔ)　6.3 初始算法　6.4 擬物擬人算法　　6.4.1 反向擠壓策略　　6.4.2 分組計(jì)算策略　　6.4.3 隨機(jī)策略　6.5 實(shí)驗(yàn)結(jié)果　6.6 本章 小結(jié)第7章 帶禁忌規(guī)則的擬物擬人算法　7.1 禁忌搜索算法概述　7.2 帶禁忌規(guī)則的擬物擬人算法　　7.2.1 初始解和鄰域結(jié)構(gòu)　　7.2.2 禁忌表　　7.2.3 搜索和跳坑策略　7.3 算法的實(shí)驗(yàn)結(jié)果　7.4 本章 小結(jié)第8章 總結(jié)及展望　8.1 主要工作總結(jié)及創(chuàng)新　8.2 未來的研究方向　8.3 本章 小結(jié)參考文獻(xiàn)

章節(jié)摘錄

　?。?）不能保證算法一定得到最優(yōu)解；　　（2）性能不穩(wěn)定。啟發(fā)式算法對(duì)同一個(gè)問題的不同實(shí)例的計(jì)算會(huì)產(chǎn)生不同的效果。有些實(shí)例所得的解的優(yōu)度很高，而另一些則相反。在工程應(yīng)用中，啟發(fā)式算法的這種不穩(wěn)定性使得計(jì)算結(jié)果不可信；　?。?）啟發(fā)式算法的優(yōu)劣依賴于具體問題以及設(shè)計(jì)者的經(jīng)驗(yàn)、技術(shù)等，這一點(diǎn)很難總結(jié)成規(guī)律，同時(shí)使不同算法之間難于比較?！　‰m說啟發(fā)式方法有諸多優(yōu)點(diǎn)，但是它本身固有的一個(gè)很嚴(yán)重的缺陷--無法保證得到最優(yōu)解，使得對(duì)啟發(fā)式算法的評(píng)價(jià)顯得尤為重要。一個(gè)好的啟發(fā)式算法可以使其解盡可能地接近最優(yōu)解，同時(shí)保持很好的穩(wěn)定性。評(píng)價(jià)啟發(fā)式算法的性能有很多不同的方法，主要是對(duì)算法的復(fù)雜性和它的計(jì)算效能進(jìn)行分析。下面就簡(jiǎn)要地介紹幾種常用的方法?！　?.最壞情形分析　　最壞情形分析考慮計(jì)算復(fù)雜性和所得解的效果兩個(gè)方面。最壞情形計(jì)算復(fù)雜性分析關(guān)注算法基本運(yùn)算總次數(shù)同實(shí)例的計(jì)算機(jī)二進(jìn)制輸入長(zhǎng)度之間的關(guān)系，從最壞實(shí)例--規(guī)模相同基本計(jì)算步數(shù)最多的實(shí)例的角度來研究、分析算法的計(jì)算時(shí)間復(fù)雜性?！　?.概率分析　　由于最壞情形分析是以最壞的實(shí)例來評(píng)價(jià)一個(gè)算法或者它所得到的解，這樣難免因?yàn)橐粋€(gè)實(shí)例導(dǎo)致對(duì)某個(gè)算法或它所求得解的優(yōu)劣的評(píng)價(jià)完全顛倒。人們認(rèn)識(shí)到應(yīng)該從總體上而非極端的實(shí)例上來評(píng)價(jià)算法，概率分析方法正是著眼于此。這個(gè)方法是從理論上考慮的，針對(duì)一個(gè)算法，我們可以從它的計(jì)算時(shí)間復(fù)雜性和計(jì)算所得解的效果兩個(gè)方面進(jìn)行概率分析。無論作哪一個(gè)方面的分析，都假設(shè)實(shí)例的數(shù)據(jù)服從某一種概率分布。在這些數(shù)據(jù)的一個(gè)已知概率分布的假設(shè)條件下，研究算法或其解的某種平均效果?！　「怕史椒ㄔ谠u(píng)價(jià)算法方面的一個(gè)成功、典型的應(yīng)用是對(duì)線性規(guī)劃單純形法的評(píng)價(jià)。概率發(fā)現(xiàn)方法是一種理論分析方法，它需要對(duì)問題本身有很深入的理解，并且掌握概率模型的建立和概率理論?！　∽顗那樾畏治龊透怕史治龇椒ㄓ幸粋€(gè)共同的特點(diǎn)：用理論的方法分析算法所得到的解同最優(yōu)解之間的誤差界，要求分析者具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，而且分析過程很繁復(fù)?！　?.大規(guī)模計(jì)算分析　　前兩種方法都是理論分析方法，要求有多的數(shù)學(xué)工具和繁復(fù)的推演，而且分析過程很復(fù)雜?！　　?/pre>








圖書封面



圖書標(biāo)簽Tags
無




評(píng)論、評(píng)分、閱讀與下載



還沒讀過(70)
勉強(qiáng)可看(508)
一般般(866)
內(nèi)容豐富(3594)
強(qiáng)力推薦(294)


 


    求解作業(yè)車間調(diào)度問題的高效算法研究 PDF格式下載