動態(tài)不確定環(huán)境下生產調度算法研究.pdf

1、生產調度的目的是在有限時域內為生產任務分配有限的車間資源來優(yōu)化一個或者多個性能指標。以往的關于調度的研究主要集中在理想的調度環(huán)境，一般都是以確定性的數(shù)學模型為基礎，與實際的車間調度環(huán)境存在很大差別。在實際的制造車間中，往往存在著很多動態(tài)不確定因素，如加工時間變動、機器故障或者交貨期變更等。如何在生成預調度時考慮到不確定因素的影響，已經成為解決實際問題的關鍵。不確定因素可以分為部分已知和完全未知兩類，對于第一類情況，在建立預調度優(yōu)化模型時

2、，就應考慮這些因素的影響，可以有效提高調度的魯棒性和穩(wěn)定性：而對于第二類情況，采用反應式的重調度是適應環(huán)境變化的最好解決方式。在動態(tài)不確定環(huán)境下的調度問題，其計算復雜度遠遠超過了靜態(tài)調度問題，使得以往的研究方法難以直接應用，對問題的求解提出了更高的要求。本文圍繞著動態(tài)不確定環(huán)境下的調度問題展開研究，主要研究了三種典型的情況：加工時間不確定、機器隨機故障和工件到達時間未知。 本文的主要工作包括如下五個方面： 1.首先研究了

3、加工時間不確定的單機Just-In-time調度問題。因為在加工時間確定時，不存在一個多項式時間算法得到問題的最優(yōu)調度，所以采用了絕對魯棒指標以最小化所有可能加工時間下的最大代價，這是一個minimax優(yōu)化問題。在給定調度順序后，內層max優(yōu)化問題的決策空間是加工時間構成的凸多面體，而優(yōu)化目標是關于加工時間的凸函數(shù)，則可以在凸多面體的頂點取得max問題的極值，因此大大降低了問題的搜索空間。根據(jù)minimax問題特性設計了一種兩層遺傳算法

4、，與以期望時間為基礎的確定性調度算法相比，在多種加工時間情況下設計的算法得到了更加魯棒的調度。 2.將對不確定加工時間情況下的魯棒調度問題的研究從單機擴展到JobShop。相對于單機問題，JobShop中的約束更加復雜，增加了同一工件所有工序的先后順序約束，因此不具有類似于單機內層max問題的特性，其搜索空間為整個加工時間的可行域，大大增加了計算復雜度。相對于解決單機問題的兩層算法，從兼顧算法性能和計算效率的角度出發(fā)，設計了一種

5、雙空間協(xié)同進化遺傳算法，仿真測試表明了算法的有效性。 3.研究了機器隨機故障情況下兼顧穩(wěn)定性的單機魯棒調度問題，該問題是一個雙目標優(yōu)化問題。在調度執(zhí)行之前，無法獲得真實的性能指標，因此采用期望指標。通過將多次故障集結為一次故障，并采用右移重調度處理故障，簡化了對調度的魯棒性和穩(wěn)定性指標的估算。采用權重和方法將雙目標轉化為單目標問題，設計了兩階段多種群遺傳算法有效確定雙目標優(yōu)化問題的Pareto最優(yōu)解。在仿真試驗中，對四種不同方法

6、進行了對比分析，同時比較了隨機權重和固定權重情況下算法的性能，結果表明了隨機權重比固定權重具有更好的搜索能力。 4.將單機的研究成果擴展到機器隨機故障情況下兼顧穩(wěn)定性的JobShop魯棒調度問題。與單機問題求解算法的不同之處在于染色體的編碼方式，不僅包含了表達工序優(yōu)先關系的基因，還包含了計算插入空閑時間大小的基因。由于JobShop自身約束的復雜性，對調度的魯棒性和穩(wěn)定性指標計算更加困難，因此采用了采樣方法進行估算。在仿真試驗中

7、，對未考慮空閑時間影響和考慮空閑時間影響的兩種算法進行了對比分析，結果表明了后者比前者較大程度改善了穩(wěn)定性，對魯棒性的影響程度很小。 5.對工件到達時間未知的動態(tài)JobShop滾動重調度問題進行了深入研究，提出了關鍵工序集的概念。在滾動時域分解方法框架下，以時間窗口作為滾動窗口，設計了基于關鍵工序集的滾動重調度算法。采用混和遺傳算法有效地確定關鍵工序集及其最優(yōu)調度順序，對關鍵工序集之外的工序，采用了分派規(guī)則確定在機器上的加工順序