基于自然啟發(fā)式算法的作業(yè)車間調(diào)度問題理論與應(yīng)用研究.pdf

1、調(diào)度是影響制造業(yè)生產(chǎn)效率的關(guān)鍵因素。采用合理的調(diào)度可以縮短工期、減少庫存、按時交貨和提高信譽。隨著全球市場競爭的加劇、客戶需求的多樣化和個性化，制造系統(tǒng)的調(diào)度問題日益受到廣泛的重視。
　　 生產(chǎn)調(diào)度問題種類繁多，方法多樣，其中單件車間調(diào)度(Job-Shop SchedulingProblem)是最基本、最著名的機器調(diào)度問題，同時也是最困難的NP-hard組合優(yōu)化問題之一。人們?yōu)榻鉀Q這一難題已經(jīng)付出幾十年的努力，但至今最先進(jìn)的算法

2、仍很難得到規(guī)模較小問題的最優(yōu)解。近十幾年來，通過模擬自然界中生物、物理過程和人類行為過程而發(fā)展的元啟發(fā)式算法，如遺傳算法、禁忌搜索、模擬退火、粒子群優(yōu)化算法、蟻群優(yōu)化算法等，為解決調(diào)度問題提供了新的思路和手段，引起了國內(nèi)外學(xué)者廣泛的興趣。遺傳算法和局部搜索算法是目前主要應(yīng)用于調(diào)度的元啟發(fā)式算法。遺傳算法所具有的只根據(jù)個體的適應(yīng)度值進(jìn)行搜索、較少需要問題相關(guān)具體領(lǐng)域知識的特點使遺傳算法在生產(chǎn)調(diào)度等問題中得到非常廣泛的應(yīng)用。本文改進(jìn)傳統(tǒng)的遺

3、傳算法，提出以下三點來解決Job-Shop 問題：一是提出一種全主動調(diào)度類型，進(jìn)一步縮小搜索的解空間；
　　 二是提出了一種基于工序編碼的交叉算子POX (Precedence Operation Crossover)，使子代能更好地繼承父代的優(yōu)良特征；三是為克服傳統(tǒng)遺傳算法存在的早熟收斂問題，設(shè)計了一種改進(jìn)子代產(chǎn)生模式的遺傳算法。用基準(zhǔn)實例測試改進(jìn)的遺傳算法，試驗結(jié)果顯示該算法能比其他遺傳算法更有效地解決調(diào)度問題。接著本文研究

4、了局部搜索算法，特別是禁忌搜索算法，在Job-Shop 調(diào)度問題中的運用。禁忌搜索算法的優(yōu)化效率依賴于問題模型，鄰域結(jié)構(gòu)和移動評價策略是影響算法搜索效率和解質(zhì)量的關(guān)鍵因素。本文提出一種新的高效鄰域結(jié)構(gòu)，結(jié)合適當(dāng)?shù)囊苿釉u價策略和禁忌搜索參數(shù)，設(shè)計了一種動態(tài)強化的禁忌算法。使用該算法對大量的基準(zhǔn)實例進(jìn)行測試，試驗結(jié)果顯示對于矩形基準(zhǔn)實例，該算法在質(zhì)量和效率上可以超越目前其他算法。
　　 最近的許多研究顯示單一算法較難解決復(fù)雜的調(diào)度問

5、題，混合優(yōu)化算法能提供更強大的搜索能力。然而，到目前為止混合算法仍是一種藝術(shù)。調(diào)度問題的解空間結(jié)構(gòu)屬于非常復(fù)雜的“大山谷”(Big Valley)拓?fù)浣Y(jié)構(gòu)，為了更好地探索調(diào)度問題復(fù)雜的空間結(jié)構(gòu)、彌補單一算法的不足，本文提出應(yīng)用自然規(guī)律來混合算法，將不同算法進(jìn)行有機和諧地結(jié)合，設(shè)計了兩種混合優(yōu)化算法，使算法更深刻地反映問題的本質(zhì)。應(yīng)用提出的混合優(yōu)化算法求解著名Job-Shop 調(diào)度基準(zhǔn)問題，取得了迄今為止最好的結(jié)果，達(dá)到了國際水平的前沿。

6、在ABZ、YN、SWV、TA和DMU基準(zhǔn)問題的106個未解決實例中，改進(jìn)了84個實例的當(dāng)前最好解，有3個實例證明達(dá)到最優(yōu)解。對于最著名的TA基準(zhǔn)實例，發(fā)布的最好解已被作為最新結(jié)果在國外專業(yè)網(wǎng)站上公布。通過與已正式發(fā)表最好的算法進(jìn)行比較可看出，對于極困難的Job-Shop 調(diào)度問題，混合優(yōu)化算法在解的質(zhì)量方面超過目前最先進(jìn)的算法。
　　 在實際生產(chǎn)環(huán)境中，調(diào)度問題具有多目標(biāo)性、多資源性、動態(tài)性和隨機性等特點。
　　 基于研

7、究傳統(tǒng)Job-Shop 調(diào)度問題的成功經(jīng)驗，本文對實際生產(chǎn)中廣泛存在的調(diào)度問題進(jìn)行了深入研究，在性能指標(biāo)方面，研究了總拖期時間最小、提前/拖期懲罰代價最小等性能指標(biāo)；在生產(chǎn)模式方面，研究了柔性作業(yè)車間調(diào)度問題(Flexible Job-ShopScheduling Problem)、動態(tài)調(diào)度(Dynamic Scheduling)，并設(shè)計了相應(yīng)的優(yōu)化算法，如針對柔性作業(yè)車間調(diào)度問題的特點，提出了一種雙層子代產(chǎn)生模式的改進(jìn)遺傳算法；將靜態(tài)

8、調(diào)度問題的成功經(jīng)驗擴展到動態(tài)調(diào)度問題，提出了一種基于改進(jìn)遺傳算法的滾動調(diào)度策略?；谶@些研究成果開發(fā)出動態(tài)調(diào)度原型系統(tǒng)，使理論研究能應(yīng)用于企業(yè)創(chuàng)造價值。
　　 作業(yè)車間調(diào)度是車間制造執(zhí)行系統(tǒng)(MES)的核心功能之一，合理、有效的作業(yè)調(diào)度是MES在離散制造業(yè)成功應(yīng)用的關(guān)鍵。在研究車間作業(yè)調(diào)度問題理論和應(yīng)用的基礎(chǔ)上，本文對單件小批量生產(chǎn)方式的車間作業(yè)計劃與調(diào)度方面的實現(xiàn)方法進(jìn)行了深入的研究，結(jié)合協(xié)作企業(yè)的應(yīng)用背景，開發(fā)出敏捷化車間制