大規(guī)模復(fù)雜生產(chǎn)調(diào)度問題瓶頸分解方法研究.pdf

1、生產(chǎn)調(diào)度問題是在時(shí)間上優(yōu)化分配機(jī)器資源給相互競爭的工件，由于其強(qiáng)大的工程應(yīng)用背景和優(yōu)化求解的難處理性(NP-hard)，長期受到制造領(lǐng)域和學(xué)術(shù)界的高度重視。隨著制造規(guī)模和復(fù)雜程度的不斷提高，大規(guī)模復(fù)雜生產(chǎn)調(diào)度問題已成為當(dāng)前制造業(yè)面臨的難題，存在建模和優(yōu)化求解的困難。分解方法是處理大規(guī)模復(fù)雜生產(chǎn)調(diào)度問題的一種常用方法，但傳統(tǒng)的分解方法收斂速度慢，容易陷入局部最優(yōu)。目前已有一些瓶頸調(diào)度方法試圖從全局優(yōu)化的角度處理大規(guī)模問題，但非常有限，在算

2、法設(shè)計(jì)、理論分析和應(yīng)用方面都存在很大的研究空間。本文利用瓶頸思想，結(jié)合分解方法，提出了一種瓶頸分解方法，并對(duì)大規(guī)模復(fù)雜生產(chǎn)調(diào)度問題進(jìn)行了深入的研究。主要工作包括以下幾個(gè)方面： ⑴在大系統(tǒng)分解思想的指導(dǎo)下，給出了車間調(diào)度問題機(jī)器層分解方法的一般描述，并指出傳統(tǒng)分解方法在求解大規(guī)模調(diào)度問題時(shí)可能存在的不足。利用能力不均衡生產(chǎn)線存在瓶頸的特性，剖析瓶頸思想的內(nèi)在機(jī)理，結(jié)合大系統(tǒng)分解思想提出了瓶頸分解方法的一般框架，并指出該方法的關(guān)鍵技

3、術(shù)。 ⑵在分析單瓶頸Flowshop生產(chǎn)線特點(diǎn)的基礎(chǔ)上，提出了一種單瓶頸分解算法。該方法將Flowshop上的機(jī)器分為瓶頸機(jī)、上游非瓶頸機(jī)和下游非瓶頸機(jī)。松弛非瓶頸機(jī)加工能力約束，原Flowshop問題簡化為一個(gè)單機(jī)調(diào)度問題。瓶頸機(jī)的調(diào)度可以通過優(yōu)化求解該簡化問題獲得。根據(jù)瓶頸機(jī)的調(diào)度結(jié)果，上游非瓶頸機(jī)采用有效的分派規(guī)則從后往前依次調(diào)度，而下游非瓶頸機(jī)則采用規(guī)則從前往后依次調(diào)度。隨后我們給出了非瓶頸機(jī)冗余能力的條件，證明滿足此條

4、件下的Flowshop問題的最優(yōu)調(diào)度為排列調(diào)度，即非瓶頸機(jī)上工件的加工安排與瓶頸機(jī)的調(diào)度安排一致。大量的仿真結(jié)果顯示單瓶頸分解算法可以在較快的時(shí)間內(nèi)獲得較好的解。 ⑶針對(duì)單瓶頸Jobshop調(diào)度問題，提出了一種單瓶頸分解算法。該方法利用生產(chǎn)線主導(dǎo)瓶頸的特點(diǎn)將Jobshop中的機(jī)器分為瓶頸機(jī)和非瓶頸機(jī)。假設(shè)非瓶頸機(jī)加工能力無限大，將非瓶頸機(jī)上的工序集結(jié)成一個(gè)時(shí)間遲延環(huán)節(jié)，原問題則簡化為一個(gè)帶到達(dá)時(shí)間和傳遞時(shí)間約束的單機(jī)調(diào)度問題。瓶

5、頸機(jī)上工件的加工安排可以通過優(yōu)化求解此單機(jī)問題獲得，而非瓶頸機(jī)則采用有效的啟發(fā)式算法調(diào)度。通過調(diào)整瓶頸機(jī)上工序的到達(dá)時(shí)間和傳遞時(shí)間協(xié)調(diào)瓶頸機(jī)與非瓶頸機(jī)之間的關(guān)聯(lián)。仿真結(jié)果顯示該算法求解瓶頸程度較高的Jobshop問題非常有效。 ⑷針對(duì)能力較不均衡的Jobshop生產(chǎn)線，提出了一種約束調(diào)度算法。該算法給出了一種迭代辨識(shí)約束機(jī)(包括長期瓶頸和暫時(shí)瓶頸)的方法。每次迭代，采用有效的規(guī)則調(diào)度非約束機(jī)，并根據(jù)調(diào)度結(jié)果從中辨識(shí)約束機(jī)，該過程

6、迭代進(jìn)行直至不存在新的約束機(jī)。約束機(jī)模型可描述為一個(gè)帶時(shí)間遲延的多機(jī)調(diào)度問題，該問題的最優(yōu)解是原問題最優(yōu)解的一個(gè)下界。隨著約束機(jī)不斷辨識(shí)，相應(yīng)的約束機(jī)模型也迭代更新，我們證明約束機(jī)子問題的最優(yōu)解在迭代過程中不斷提高，朝著原問題最優(yōu)解的方向逐步逼近。與傳統(tǒng)的移動(dòng)瓶頸方法相比，約束調(diào)度算法在提高計(jì)算效率的同時(shí)保證了調(diào)度的優(yōu)化性能。大量的仿真比較研究顯示，該算法可以在調(diào)度質(zhì)量和計(jì)算時(shí)間之間獲得一個(gè)好的均衡。 ⑸針對(duì)約束調(diào)度算法無法求解

7、的更大規(guī)模Jobshop調(diào)度問題，提出了一種滾動(dòng)瓶頸分解策略。該方法在瓶頸分解方法的基礎(chǔ)上，結(jié)合滾動(dòng)時(shí)域分解的思想，將整個(gè)調(diào)度時(shí)域分解為若干決策子窗口，每個(gè)時(shí)間窗口對(duì)應(yīng)的子問題采用瓶頸分解方法求解。該方法從空間層和時(shí)間層對(duì)大規(guī)模問題進(jìn)行分解，它為求解超大規(guī)模Jobshop調(diào)度問題提供了一種新的解決思路。仿真結(jié)果驗(yàn)證了滾動(dòng)瓶頸分解方法的有效性。 ⑹將滾動(dòng)瓶頸分解方法應(yīng)用至一個(gè)更復(fù)雜的Jobshop調(diào)度問題，即半導(dǎo)體生產(chǎn)線，針對(duì)半導(dǎo)