動(dòng)態(tài)不確定環(huán)境下生產(chǎn)調(diào)度算法研究.pdf

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

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

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

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

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

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

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