一、排產(chǎn)調(diào)度問題的提出

敏捷制造作為21世紀(jì)企業(yè)的先進(jìn)制造模式，綜合了精益JIT、并行工程等多種先進(jìn)制造模式的哲理，其目的是要以最低成本制造出顧客滿意的產(chǎn)品，即是完全面向顧客的。

在這種模式下，如何進(jìn)行組織管理，包括如何組織動態(tài)聯(lián)盟、如何重構(gòu)車間和單元、如何安排生產(chǎn)計(jì)劃、如何進(jìn)行排產(chǎn)調(diào)度都是我們面臨的問題。其中車間作業(yè)排產(chǎn)調(diào)度與控制技術(shù)是實(shí)現(xiàn)生產(chǎn)高效率、高柔性和高可靠性的關(guān)鍵，有效實(shí)用的排產(chǎn)調(diào)度方法和優(yōu)化技術(shù)的研究與應(yīng)用已成為智能制造技術(shù)實(shí)踐的基礎(chǔ)。

排產(chǎn)調(diào)度問題主要集中在車間的計(jì)劃與排產(chǎn)調(diào)度方面，是針對一項(xiàng)可分解的工作（如產(chǎn)品制造），探討在在盡可能滿足約束條件（如交貨期、工藝路線、資源情況）的前提下，通過下達(dá)生產(chǎn)指令，安排其組成部分（操作）使用哪些資源、其加工時(shí)間及加工的先后順序，以獲得產(chǎn)品制造時(shí)間或成本的最優(yōu)化。在理論研究中，生產(chǎn)排產(chǎn)調(diào)度問題常被稱為排序問題或資源分配問題。

二、排產(chǎn)調(diào)度問題的分類

生產(chǎn)排產(chǎn)調(diào)度系統(tǒng)的分類方法很多，主要有以下幾種：

(1)?根據(jù)加工系統(tǒng)的復(fù)雜度，可分為單機(jī)、多臺并行機(jī)、Flow Shop(流水線加工)和 Job Shop（任務(wù)型加工）。

單機(jī)排產(chǎn)調(diào)度問題是所有的操作任務(wù)都在單臺機(jī)器上完成，為此存在任務(wù)的優(yōu)化排隊(duì)問題，多臺并行機(jī)的排產(chǎn)調(diào)度問題更復(fù)雜，因而優(yōu)化問題更突出。

Flow Shop型問題假設(shè)所有作業(yè)都在同樣的設(shè)備上加工，并有一致的加工操作和加工順序。Job Shop是最一般的排產(chǎn)調(diào)度類型、并不限制作業(yè)的操作的加工設(shè)備，并允許一個(gè)作業(yè)加工具有不同的加工路徑。

(2)?根據(jù)性能指標(biāo)，分為基于排產(chǎn)調(diào)度成本和排產(chǎn)調(diào)度性能的指標(biāo)兩大類。

(3)?根據(jù)生產(chǎn)環(huán)境的特點(diǎn)，可將排產(chǎn)調(diào)度問題分為確定性排產(chǎn)調(diào)度和隨機(jī)性排產(chǎn)調(diào)度問題。

(4)?根據(jù)作業(yè)的加工特點(diǎn)，可將排產(chǎn)調(diào)度問題分為靜態(tài)排產(chǎn)調(diào)度和動態(tài)排產(chǎn)調(diào)度。

靜態(tài)排產(chǎn)調(diào)度是指所有待安排加工的工作均處于待加工狀態(tài)，因而進(jìn)行—次排產(chǎn)調(diào)度后、各作業(yè)的加工被確定、在以后的加工過程中就不再改變；動態(tài)排產(chǎn)調(diào)度是指作業(yè)依次進(jìn)入待加工狀態(tài)、各種作業(yè)不斷進(jìn)入系統(tǒng)接受加工、同時(shí)完成加工的作業(yè)又不斷離開，還要考慮作業(yè)環(huán)境中不斷出現(xiàn)的動態(tài)擾動、如作業(yè)的加工超時(shí)、設(shè)備的損壞等。因此動態(tài)排產(chǎn)調(diào)度要根據(jù)系統(tǒng)中作業(yè)、設(shè)備等的狀況，不斷地進(jìn)行排產(chǎn)調(diào)度。實(shí)際排產(chǎn)調(diào)度的類型往往是Job Shop型且是動態(tài)的。

三、生產(chǎn)排產(chǎn)調(diào)度的環(huán)境特征

一般的排產(chǎn)調(diào)度問題都是對于具體生產(chǎn)環(huán)境中復(fù)雜的、動態(tài)的、多目標(biāo)的排產(chǎn)調(diào)度問題的一種抽象和簡化，因而，一個(gè)排產(chǎn)調(diào)度算法可以通過其如何表述這些復(fù)雜性來進(jìn)行分類。

由于實(shí)際生產(chǎn)環(huán)境是千差萬別的，那末，一個(gè)排產(chǎn)調(diào)度算法就應(yīng)該根據(jù)其是否能適合對應(yīng)的生產(chǎn)環(huán)境的重要特征來進(jìn)行評估。為了幫助區(qū)別不同的生產(chǎn)排產(chǎn)調(diào)度策略，給出了典型生產(chǎn)排產(chǎn)調(diào)度環(huán)境的五個(gè)特征，這將有助于我們了解各種不同的排產(chǎn)調(diào)度算法的應(yīng)用環(huán)境。

1、?邊界條件：

生產(chǎn)排產(chǎn)調(diào)度常常是一個(gè)重排產(chǎn)調(diào)度問題，即修改已有的生產(chǎn)排產(chǎn)調(diào)度去適應(yīng)新的作業(yè)。為提供重排產(chǎn)調(diào)度，排產(chǎn)調(diào)度算法應(yīng)能處理生產(chǎn)系統(tǒng)中有關(guān)的初始狀態(tài)。類似的生產(chǎn)排產(chǎn)調(diào)度通常是在一個(gè)有限的時(shí)間區(qū)域里進(jìn)行的，系統(tǒng)的最優(yōu)解（或次優(yōu)解）亦是在限定的邊界范圍內(nèi)來獲取。

2、?分批大小和調(diào)整成本：

為有效地解決實(shí)際生產(chǎn)中的排產(chǎn)調(diào)度問題，往往將任務(wù)分成多批進(jìn)行，并考慮改變已有排產(chǎn)調(diào)度結(jié)果所付出的代價(jià)（調(diào)整成本）。

3、?加工路徑：

在實(shí)際生產(chǎn)中，作業(yè)的加工路徑可能需要動態(tài)改變，工藝順序可能是半有序的(Semi order)。

4、?隨機(jī)事件和擾動：

出現(xiàn)關(guān)鍵作業(yè)、設(shè)備損壞、加工操作失敗、原料短缺、加工時(shí)間、到達(dá)時(shí)間、交貨期的改變等。

5、?性能指標(biāo)和多目標(biāo)：

追求不同的性能指標(biāo)往往會得到不同的優(yōu)化解，同時(shí)，系統(tǒng)目標(biāo)也以多目標(biāo)為主。

四、排產(chǎn)調(diào)度問題的特點(diǎn)

實(shí)際的排產(chǎn)調(diào)度問題有以下特點(diǎn)：

(1)?復(fù)雜性

由于裝卸作業(yè)、裝卸設(shè)備、庫場、搬運(yùn)系統(tǒng)之間相互影響、相互作用、每個(gè)作業(yè)又要考慮它的到達(dá)時(shí)間、裝卸時(shí)間、準(zhǔn)備時(shí)間、操作順序、交貨期等，因而相當(dāng)復(fù)雜。

由于排產(chǎn)調(diào)度問題是在等式或不等式約束下求性能指標(biāo)的優(yōu)化，在計(jì)算量上往往是NP(多項(xiàng)式復(fù)雜性)完全問題，即隨著問題規(guī)模的增大，對于求解最優(yōu)化的計(jì)算量呈指數(shù)增長，使得一些常規(guī)的最優(yōu)化方法往往無能為力。

(2)?動態(tài)隨機(jī)性

在實(shí)際的生產(chǎn)排產(chǎn)調(diào)度系統(tǒng)中存在很多隨機(jī)的和不確定的因素，比如作業(yè)到達(dá)時(shí)間的不確定性、作業(yè)的加工時(shí)間也有一定的隨機(jī)性，而且生產(chǎn)系統(tǒng)中常出現(xiàn)一些實(shí)發(fā)偶然事件，如設(shè)備的損壞、修復(fù)、作業(yè)交貨期的改變等。

(3)?多目標(biāo)。

實(shí)際的計(jì)劃排產(chǎn)調(diào)度往往是多目標(biāo)的，并且這些目標(biāo)間可能發(fā)生沖突。排產(chǎn)調(diào)度目標(biāo)分為基于排產(chǎn)調(diào)度成本和排產(chǎn)調(diào)度性能的指標(biāo)兩大類。

也有排產(chǎn)調(diào)度目標(biāo)分三類：基于作業(yè)交貨期的目標(biāo)、基于作業(yè)完成時(shí)間的目標(biāo)、基于生產(chǎn)成本的目標(biāo)。這種多目標(biāo)性導(dǎo)致排產(chǎn)調(diào)度的復(fù)雜性和計(jì)算量急劇增加。

五、排產(chǎn)調(diào)度問題的研究方法

—般的排產(chǎn)調(diào)度問題都是對于具體生產(chǎn)環(huán)境中復(fù)雜的、動態(tài)的、多目標(biāo)的排產(chǎn)調(diào)度問題的一種抽象和簡化，因而一個(gè)排產(chǎn)調(diào)度算法可以通過其如何表述這些復(fù)雜性進(jìn)行分類。由于實(shí)際中生產(chǎn)環(huán)境是千差萬別的，那么一個(gè)排產(chǎn)調(diào)度算法就應(yīng)該根據(jù)其是否能適合對應(yīng)的生產(chǎn)環(huán)境的重要特征進(jìn)行評估。

在對排產(chǎn)調(diào)度問題進(jìn)行研究的方法上，最初是集中在整數(shù)規(guī)劃、仿真和簡單的規(guī)則上，這些方法不是排產(chǎn)調(diào)度結(jié)果不理想就是難以解決復(fù)雜的問題。隨著各種新的相關(guān)學(xué)科與優(yōu)化技術(shù)的建立與發(fā)展，在排產(chǎn)調(diào)度領(lǐng)域也出現(xiàn)了許多新的優(yōu)化方法，比如神經(jīng)網(wǎng)絡(luò)、模擬退火法、遺傳算法、禁忌搜索法等，使得排產(chǎn)調(diào)度問題的研究方法向多元化方向發(fā)展。下面我們分別對這些方法進(jìn)行總結(jié)：

(1)?運(yùn)籌學(xué)方法

運(yùn)籌學(xué)方法是將生產(chǎn)排產(chǎn)調(diào)度問題簡化為數(shù)學(xué)規(guī)劃模型，采用基于枚舉思想的分枝定界法或動態(tài)規(guī)劃算法進(jìn)行解決排產(chǎn)調(diào)度最優(yōu)化或近優(yōu)化問題，屬于精確方法。不同的分枝定界法，其不同點(diǎn)主要在于分析規(guī)則、定界機(jī)制和上界的產(chǎn)生這三方面存在差異。這類方法雖然從理論上能求得最優(yōu)解，但由于其計(jì)算復(fù)雜性的原因、因而不能獲得真正的實(shí)用。

對于復(fù)雜的問題，這種純數(shù)學(xué)方法有模型抽取困難、運(yùn)算量大、算法難以實(shí)現(xiàn)的弱點(diǎn)，對于生產(chǎn)環(huán)境中的動態(tài)排產(chǎn)調(diào)度實(shí)現(xiàn)復(fù)雜，解決不了動態(tài)及快速響應(yīng)市場的問題。

(2)?基于規(guī)則的方法

對生產(chǎn)加工任務(wù)進(jìn)行排產(chǎn)調(diào)度的最傳統(tǒng)的方法是使用排產(chǎn)調(diào)度規(guī)則（Dispatching Rules），已經(jīng)有許多排產(chǎn)調(diào)度規(guī)則被應(yīng)用，因其排產(chǎn)調(diào)度規(guī)則簡單、易于實(shí)現(xiàn)、計(jì)算復(fù)雜度低等原因，能夠用于動態(tài)實(shí)時(shí)排產(chǎn)調(diào)度系統(tǒng)中，許多年來一直受到廣泛研究，并不斷涌現(xiàn)出新的排產(chǎn)調(diào)度規(guī)則。如較優(yōu)的單元零件加工排產(chǎn)調(diào)度算法，在減少等待時(shí)間、提高生產(chǎn)率等諸多約束條件下達(dá)到了一種較為科學(xué)有效的排產(chǎn)調(diào)度效果。

規(guī)則按形式分為了三類：簡單規(guī)則、復(fù)合規(guī)則、啟發(fā)式規(guī)則；隨著計(jì)算機(jī)運(yùn)算速度的飛速提高，人們希望尋找新的近似排產(chǎn)調(diào)度方法，它以合理的額外計(jì)算時(shí)間為代價(jià)，換得比單純啟發(fā)式規(guī)則所得到的排產(chǎn)調(diào)度更好的排產(chǎn)調(diào)度。在這方面比較有代表性的有移動瓶頸方法（Bottle Neck Procedure)，用來解決以最小化 Make Span(制造時(shí)間)為目標(biāo)的 Job Shop排產(chǎn)調(diào)度問題，它通過不斷地對移動的瓶頸設(shè)備進(jìn)行單機(jī)排產(chǎn)調(diào)度，來獲取更好的次優(yōu)解。

總的說來，啟發(fā)式規(guī)則直觀、簡單、易于實(shí)現(xiàn)。但是近研究表明并不存在一個(gè)全局最優(yōu)的排產(chǎn)調(diào)度規(guī)則，它們的有效性依賴于對特殊性能需求的標(biāo)準(zhǔn)及生產(chǎn)條件。

它是局部優(yōu)化方法，難以得到全局優(yōu)化結(jié)果，并且不能對得到的結(jié)果進(jìn)行次優(yōu)性的定量評估。顧客需求的個(gè)性化及要求企業(yè)響應(yīng)市場的敏捷性，往往在生產(chǎn)加工過程中加入了更多的不確定性及復(fù)雜性約束，尋找排產(chǎn)調(diào)度最優(yōu)算法本身是一個(gè)NP完全問題，這些使得基于規(guī)則的排產(chǎn)調(diào)度思想已不能適合敏捷化制造的要求。

(3)系統(tǒng)仿真的方法

仿真方法是不單純追求系統(tǒng)的數(shù)學(xué)模型，側(cè)重對系統(tǒng)中運(yùn)行的邏輯關(guān)系的描述，能夠?qū)ιa(chǎn)排產(chǎn)調(diào)度方案進(jìn)行比較評價(jià)，分析系統(tǒng)的動態(tài)性能，并選擇系統(tǒng)的動態(tài)結(jié)構(gòu)參數(shù)。由于制造系統(tǒng)的復(fù)雜性，很難用一個(gè)精確的解析模型來進(jìn)行描述和分析。而通過運(yùn)行仿真模型來收集數(shù)據(jù)，則能對實(shí)際系統(tǒng)進(jìn)行性能、狀態(tài)等方面的分析，從而，能對系統(tǒng)采用合適的控制排產(chǎn)調(diào)度方法。

仿真方法最早被用來作為測試排產(chǎn)調(diào)度啟發(fā)式規(guī)則及分派規(guī)則的工具。后來，人們發(fā)現(xiàn)，通過將簡單的優(yōu)先權(quán)規(guī)則進(jìn)行組合，或用一個(gè)簡單的優(yōu)先權(quán)規(guī)則將一些啟發(fā)式規(guī)則進(jìn)行組合，這樣的排產(chǎn)調(diào)度優(yōu)于單獨(dú)的優(yōu)先權(quán)規(guī)則。

于是，仿真方法逐漸發(fā)展為一種人機(jī)交互的柔性仿真工具，并用來進(jìn)行車間排產(chǎn)調(diào)度。這樣，就能通過仿真而動態(tài)地展現(xiàn)Job Shop車間的狀態(tài)，分析在不同的排產(chǎn)調(diào)度方法下的系統(tǒng)性能，并運(yùn)用知識和經(jīng)驗(yàn)去選擇合適的排產(chǎn)調(diào)度方法(規(guī)則)，從而改善排產(chǎn)調(diào)度性能。

基于純仿真法雖然可以包含解析模型無法描述的因素，并且可以提供給使用者一個(gè)排產(chǎn)調(diào)度性能測試的機(jī)會，但其不可避免地存在以下問題：

-鑒于其實(shí)驗(yàn)性，因此，很難對生產(chǎn)排產(chǎn)調(diào)度的理論作出貢獻(xiàn)。

-應(yīng)用仿真進(jìn)行生產(chǎn)排產(chǎn)調(diào)度的成本很高，不僅在于產(chǎn)生排產(chǎn)調(diào)度的計(jì)算時(shí)間上，而且在于設(shè)計(jì)、建立、運(yùn)行仿真模型上的高成本。

-仿真的準(zhǔn)確性受編程人員的判斷和技巧的限制，甚至很高精度的仿真模型也無法保證通過實(shí)驗(yàn)總能找到最優(yōu)或次優(yōu)的排產(chǎn)調(diào)度。

(4)?基于 DEDS的解析模型方法

由于制造系統(tǒng)是一類典型的離散事件系統(tǒng)，因此，可以用研究離散事件系統(tǒng)的解析模型和方法去探討車間排產(chǎn)調(diào)度問題，諸如排隊(duì)論、極大/極小代數(shù)模型、Petri網(wǎng)等。

排產(chǎn)調(diào)度中的排隊(duì)論方法是一種隨機(jī)優(yōu)化方法，它將每個(gè)設(shè)備看成一個(gè)服務(wù)臺，將每個(gè)作業(yè)作為一個(gè)客戶。作業(yè)的各種復(fù)雜的可變特性及復(fù)雜的路徑，可通過將其加工時(shí)間及到達(dá)時(shí)間假設(shè)為一個(gè)隨機(jī)分布來進(jìn)行描述。

總的說來，排隊(duì)網(wǎng)絡(luò)模型由于從隨機(jī)統(tǒng)計(jì)的角度來描述制造系統(tǒng)，難以表述系統(tǒng)中存在的某些特性（如有限的緩存空間等），同時(shí)，產(chǎn)生的輸出是基于系統(tǒng)穩(wěn)態(tài)操作的平均量，因此，很難得到比較具體的細(xì)節(jié)。

Petri網(wǎng)作為一種圖形建模工具可以形象地表示和分析FMS中加工過程的并發(fā)和分布特征以及多項(xiàng)作業(yè)共享資源時(shí)的沖突現(xiàn)象，具有很強(qiáng)的建模能力，對于描述系統(tǒng)的不確定性和隨機(jī)性也具有一定的優(yōu)越性。在制造自動化領(lǐng)域，利用 Petri網(wǎng)及其擴(kuò)展形式的模型進(jìn)行死鎖分析、排產(chǎn)調(diào)度決策和性能評價(jià)等。

目前，Petri網(wǎng)模型用于排產(chǎn)調(diào)度還存在以下的問題：

-節(jié)點(diǎn)語義的單義性，使得所攜帶的系統(tǒng)信息量不夠豐富。

-重用性差。Petri網(wǎng)多是基于制造中作業(yè)的加工流程建模，當(dāng)作業(yè)需求或工藝稍有變動時(shí)，必須修改模型結(jié)構(gòu)，這難于適應(yīng)制造中存在的不確定因素。

-不能對高級的排產(chǎn)調(diào)度規(guī)則加以建模，通常只能用禁止弧機(jī)制體現(xiàn)一些低級控制。

(5)基于排序的方法

該方法是先有可行性加工順序，然后才確定每個(gè)操作的開工時(shí)間，并對這個(gè)順序進(jìn)行優(yōu)化，它雖然屬于近似算法，但有可能達(dá)到最優(yōu)的排產(chǎn)調(diào)度方案。它主要包括鄰近搜索法，它在生產(chǎn)排產(chǎn)調(diào)度領(lǐng)域得到了相當(dāng)廣泛的應(yīng)用，在探索解空間時(shí)，僅對選定的成本函數(shù)值的變化做出響應(yīng)，因而通用性強(qiáng)。

這類方法包括局部探索（Local Search）、模擬退火法（Simulated Annealing）、列表尋優(yōu)法（Table Search），遺傳算法（Genetic Algorithms）。鄰近搜索雖然可能得到最優(yōu)的排產(chǎn)調(diào)度方案，但也存在各自的不足, 很多采取混合算法來彌補(bǔ)單一方法的不足。

-啟發(fā)式圖搜索法

對于表述為整數(shù)規(guī)劃的排產(chǎn)調(diào)度問題，最初采用分枝定界法來解決，而后其他的啟發(fā)式圖搜索法也被應(yīng)用于解決排產(chǎn)調(diào)度問題。

將排產(chǎn)調(diào)度排序問題用一個(gè)圖來表示，首先構(gòu)造一個(gè)可行解，采用基于隱枚舉的搜索方法不斷提高解的次優(yōu)性；采用束搜索法(beam search)來識別瓶頸機(jī)器，進(jìn)行排產(chǎn)調(diào)度；為了解決搜索空間太大的問題，通過對分枝定界法和約束搜索法進(jìn)行系統(tǒng)的分析，提出了一種過濾束搜索法(filter beam search)，用來解決單臺機(jī)器提前／延期問題和加權(quán)延期的 Flow Shop問題；對于圖搜索算法，如何提高搜索效率并減少內(nèi)存使用以解決規(guī)模較大的問題，還需要進(jìn)一步探索。

-模擬退火法

模擬退火算法(SA)將組合優(yōu)化問題與統(tǒng)計(jì)力學(xué)中的熱平衡問題類比，另辟了求解組合優(yōu)化問題的新途徑。它通過模擬退火過程，可找到全局(或近似)最優(yōu)解。其基本思想為：把每種組合狀態(tài) Si看成某一物質(zhì)系統(tǒng)的微觀狀態(tài)，而將其對應(yīng)的目標(biāo)函數(shù)C(Si)看成該物質(zhì)系統(tǒng)在狀態(tài)Si下的內(nèi)能；用控制參數(shù)T類比溫度，讓T從一個(gè)足夠高的值慢慢下降，對每個(gè)T，用 Metropolis抽樣法在計(jì)算機(jī)上模擬該體系在此T下的熱平衡態(tài)，即如果 C(s’)，對當(dāng)前狀態(tài)Si作隨機(jī)擾動以產(chǎn)生一個(gè)新狀態(tài)s’。

模擬退火法的幾個(gè)重要部分為：生成函數(shù)(generation)、容忍函數(shù)(acceptance function)、 Markov鏈長、降溫過程和結(jié)束準(zhǔn)則。模擬退火法的改進(jìn)算法有加溫退火法、有記憶的模擬退火法等。

為Flow Shop問題求解構(gòu)造了一類模擬退火法，并通過六種不同的隨機(jī)抽樣方式分析了算法漸近收斂于全局最優(yōu)解，分別解決了具有最小Make Span指標(biāo)且具有無限中間存儲(UIS)、有限中間存儲(FIS)和無中間存儲(NIS)的 Flow Shop排序問題；

一種改進(jìn)的模擬退火法，用來解決具有最小 Make span指標(biāo)的 Flow Shop排序問題，并與禁忌搜索法等進(jìn)行了比較；另外，模擬退火法也可與其他方法相結(jié)合進(jìn)行求解，如先用貪心法(greedy法)搜索，將得到的作業(yè)序列作為初始解，再用模擬退火法求解單機(jī)排產(chǎn)調(diào)度問題，其結(jié)果表明這種方法比單純用模擬退火法和貪心法要好；將模擬退火法與啟發(fā)式算法相結(jié)合的方法，求解具有交貨期約束的Job Shop排產(chǎn)調(diào)度問題。

由于模擬退火法能以一定的概率接受差的能量值，因而有可能跳出局部極小，但它的收斂速度較慢，很難用于實(shí)時(shí)動態(tài)排產(chǎn)調(diào)度環(huán)境。

-禁忌搜索法

對于復(fù)雜的組合優(yōu)化問題，禁忌搜索也是一種通過領(lǐng)域搜索以獲取最優(yōu)解的方法。禁忌搜索是一種迭代方法，它開始于一個(gè)初始可行解S，然后移動到領(lǐng)域N(S)中最好的解s’，即s’，對于目標(biāo)函數(shù)F(S)在領(lǐng)域 N(S)中是最優(yōu)的。然后，從新的開始點(diǎn)重復(fù)此法。

為了避免死循環(huán)，禁忌搜索把最近進(jìn)行的T個(gè)移動（T可固定也可變化）放在一個(gè)稱作 tabu list的表中(也稱短期記憶)，在目前的迭代中這些移動是被禁止的，在一定數(shù)目的迭代之后它們又被釋放出來。這樣的tabu list是一個(gè)循環(huán)表，它被循環(huán)地修改，其長度T稱作Tabu size。最后，還須定義一個(gè)停止準(zhǔn)則來終止整個(gè)算法。由于tabu list的限制，使其在搜索中有可能跳出局部極小。針對求解交貨期下帶有等待時(shí)間懲罰的提前／拖期單機(jī)排產(chǎn)調(diào)度問題。

-神經(jīng)網(wǎng)絡(luò)優(yōu)化

Hopfield神經(jīng)網(wǎng)絡(luò)模型的提出為求解各種有約束優(yōu)化問題開辟了一條新途徑，它的主要思路是：通過一個(gè)Lyaplmov能量函數(shù)構(gòu)造網(wǎng)絡(luò)的極值，當(dāng)網(wǎng)絡(luò)迭代收斂時(shí)，能量函數(shù)達(dá)到極小，使與能量函數(shù)對應(yīng)的目標(biāo)函數(shù)得到優(yōu)化。

隨機(jī) Hopfield網(wǎng)絡(luò)來解決 Job Shop排產(chǎn)調(diào)度問題的方法；改進(jìn)的Hopfield網(wǎng)絡(luò)的整數(shù)線性規(guī)劃神經(jīng)網(wǎng)絡(luò)方法來解決 Job Shop排產(chǎn)調(diào)度問題。

-遺傳算法

美國Michigan大學(xué)的J.H.Holland于本世紀(jì)末提出了一種新的并行優(yōu)化搜索方法：遺傳算法(Genetic Algorithm)，它是一種基于進(jìn)化論優(yōu)勝劣汰、自然選擇、適者生存和物種遺傳思想的隨機(jī)優(yōu)化搜索算法，通過群體的進(jìn)化來進(jìn)行全局性優(yōu)化搜索。

它以其很強(qiáng)的并行性和很高的計(jì)算效率正日益受到人們的關(guān)注。它對組合優(yōu)化問題求解的主要過程是：給定一組初始解作為一個(gè)群體，通過選擇、交換和變異等遺傳操作符來搜索問題的最優(yōu)解。

基于遺傳算法的啟發(fā)式方法，用于解決以最小化Make span為指標(biāo)的flow shop排產(chǎn)調(diào)度問題；可以將遺傳算法與圖搜索法相結(jié)合，利用遺傳算法進(jìn)行知識的推理、啟發(fā)，再用過濾束搜索法(filter beam search)進(jìn)行優(yōu)化搜索，以得到高質(zhì)量的制造靜態(tài)排產(chǎn)調(diào)度。

總的來說，遺傳算法的最大優(yōu)點(diǎn)是通過群體間的相互作用，保持已經(jīng)搜索到的信息，這是基于單次搜索過程的優(yōu)化方法所無法比擬的。但是，遺傳算法也存在著計(jì)算速度較慢的問題。

(6)人工智能的排產(chǎn)調(diào)度方法

近年來受實(shí)際需要的推動，基于知識的智能排產(chǎn)調(diào)度系統(tǒng)和方法的研究取得了很大的進(jìn)展。人工智能在上個(gè)世紀(jì)60年代就將計(jì)劃問題作為其應(yīng)用領(lǐng)域之一，但直到上個(gè)世紀(jì)80年代，開展基于約束傳播的ISIS(Intelligent Scheduling and Information System)的研究為標(biāo)志，人工智能才真正開始應(yīng)用于排產(chǎn)調(diào)度問題。

基于知識的排產(chǎn)調(diào)度方法是用專家系統(tǒng)自動產(chǎn)生排產(chǎn)調(diào)度或輔助人去排產(chǎn)調(diào)度。它是將傳統(tǒng)的排產(chǎn)調(diào)度方法與基于知識的排產(chǎn)調(diào)度評價(jià)相結(jié)合的方法。

在支持某些活動發(fā)生的資源條件具備時(shí)(稱為決策點(diǎn))，根據(jù)系統(tǒng)當(dāng)時(shí)所處的屬性狀態(tài)，決定采取何種規(guī)則(策略)，確定或選擇活動發(fā)生的順序和時(shí)間，即狀態(tài)指導(dǎo)的智能排產(chǎn)調(diào)度方法。

總的來說，主要包括智能排產(chǎn)調(diào)度專家系統(tǒng)、基于智能搜索的方法及基于多代理技術(shù)（Multi-Agent System 簡稱MAS）的合作求解的方法等。其中，智能排產(chǎn)調(diào)度專家系統(tǒng)是人工智能應(yīng)用的體現(xiàn)，由于專家系統(tǒng)中知識獲取和推理速度這兩個(gè)瓶頸，使得神經(jīng)網(wǎng)絡(luò)逐漸被采用，但還存在訓(xùn)練速度慢、探索能力弱等缺點(diǎn)。

基于多代理技術(shù)的合作求解方法是較新的智能排產(chǎn)調(diào)度方法，它提供了一種動態(tài)靈活、快速響應(yīng)市場的生產(chǎn)排產(chǎn)調(diào)度機(jī)制，它以分布式人工智能（Distributed Artificial Intelligence簡稱DAI）中的多代理機(jī)制作為新的生產(chǎn)組織與運(yùn)行模式，通過代理（Agent）之間的合作以及MAS系統(tǒng)協(xié)調(diào)來完成生產(chǎn)任務(wù)的排產(chǎn)調(diào)度，并達(dá)到預(yù)先規(guī)定的生產(chǎn)目標(biāo)及生產(chǎn)狀態(tài)。在這種研究方法中，在Agent內(nèi)部也可采用基于規(guī)則及智能推理相結(jié)合的混合方法，來構(gòu)造基于MAS的生產(chǎn)排產(chǎn)調(diào)度系統(tǒng)。

六、排產(chǎn)調(diào)度方法存在的問題

排產(chǎn)調(diào)度領(lǐng)域中的大部分問題都具有NP問題，雖然對它的研究已有幾十年的歷史，但至今尚未形成一套系統(tǒng)的方法和理論，理論研究與實(shí)際應(yīng)用之間還存在著很大差距。尤其隨著JIT（Just-In-Time）思想的廣泛采用，E/T（Earliness/Tardiness）排產(chǎn)調(diào)度問題，即使得工件盡量按交貨期完成，變得越來越突出。

實(shí)際應(yīng)用中的排產(chǎn)調(diào)度方法能夠響應(yīng)系統(tǒng)的動態(tài)變化，但不能保證得到好的排產(chǎn)調(diào)度：一些理論上的最優(yōu)化方法能提供最優(yōu)排產(chǎn)調(diào)度，但由于其計(jì)算的復(fù)雜性，并且忽略了很多實(shí)際因素，離實(shí)際運(yùn)用還有較大距離?；谧顑?yōu)化的方法，諸如動態(tài)規(guī)劃算法與分枝定界算法等等，由于其大多數(shù)是建立在對可能排產(chǎn)調(diào)度的部分枚舉上，因此只能解決小規(guī)模的排產(chǎn)調(diào)度問題，距離實(shí)用還有較大距離。

由于大多排產(chǎn)調(diào)度問題屬于一類NP困難組合問題，因此尋找具有多項(xiàng)式復(fù)雜性的最優(yōu)算法幾乎是不可能的。但因其解的最優(yōu)性、至今仍激發(fā)著學(xué)者們進(jìn)行不斷的探索。

各種近似啟發(fā)式方法、諸如基于規(guī)則的算法等，由于能在合理的時(shí)間內(nèi)產(chǎn)生比較滿意的排產(chǎn)調(diào)度，因此廣泛應(yīng)用于實(shí)際排產(chǎn)調(diào)度中，但其往往對所得的排產(chǎn)調(diào)度解的次優(yōu)性不能進(jìn)行評估。

在這方面有必要探索更好的近似最優(yōu)排產(chǎn)調(diào)度算法，可以考慮增加合理的計(jì)算時(shí)間代價(jià)，提高解的次優(yōu)性。各種基于統(tǒng)計(jì)優(yōu)化的方法、諸如模擬退火法、遺傳算法等，提供了一種解決排產(chǎn)調(diào)度優(yōu)化問題的新途徑，但同別的優(yōu)化算法類似，其也存在著一定程度的校舉、一般來說收斂到最優(yōu)解很慢，并且對于判斷解的最優(yōu)性也很困難。

在實(shí)際車間排產(chǎn)調(diào)度中，計(jì)劃與車間排產(chǎn)調(diào)度往往是分層進(jìn)行的，但這可能造成計(jì)劃在實(shí)際排產(chǎn)調(diào)度中的不可行問題，如何將計(jì)劃與排產(chǎn)調(diào)度結(jié)合考慮，以求總體的優(yōu)化也是需要進(jìn)一步研究的。另外，還有很多有待進(jìn)一步研究的問題，比如實(shí)際車間排產(chǎn)調(diào)度的多目標(biāo)性等。排產(chǎn)調(diào)度理論、方法與應(yīng)用的研究是一項(xiàng)非常艱巨的工作，目前人們還在進(jìn)行各種各樣的探索性研究工作。

由于排產(chǎn)調(diào)度問題的復(fù)雜性，實(shí)際生產(chǎn)排產(chǎn)調(diào)度的目標(biāo)應(yīng)定為尋找一個(gè)好的、可行的的解決方案而常常不是最優(yōu)的方案。盡管有大量的解決排產(chǎn)調(diào)度的方案，但是只有少數(shù)的方法應(yīng)用于實(shí)際。其中，基于智能的排產(chǎn)調(diào)度方法應(yīng)用人類專家的經(jīng)驗(yàn)及特殊領(lǐng)域的知識，在解決排產(chǎn)調(diào)度問題上已經(jīng)做出了很多成績。

關(guān)鍵技術(shù)

尋找車間排產(chǎn)調(diào)度的最優(yōu)解從理論上將是NP-完全問題，沒有一個(gè)確定的算法來解決這個(gè)問題。許多約束條件，使得實(shí)際的排產(chǎn)調(diào)度問題變得非常困難，比如：設(shè)備的可選性、制造環(huán)境的動態(tài)與不確定性、約束條件的矛盾（最小加工時(shí)間與最大設(shè)備利用率）等等，實(shí)際上，生產(chǎn)排產(chǎn)調(diào)度問題大部分是集中于簡化問題，然后尋找最優(yōu)解或次優(yōu)解。研究與開發(fā)排產(chǎn)調(diào)度系統(tǒng)面臨的關(guān)鍵問題主要有：

-信息表達(dá)：

包括排產(chǎn)調(diào)度任務(wù)及特殊信息（工作能力、可選生產(chǎn)計(jì)劃等）的描述。

-交互性設(shè)計(jì)：

交互性不單指人機(jī)界面的問題，它應(yīng)支持人對排產(chǎn)調(diào)度過程的直接參與，因?yàn)榧兇獾淖詣踊女a(chǎn)調(diào)度是不現(xiàn)實(shí)的，它忽略了具有最終決策職責(zé)的排產(chǎn)調(diào)度行家的重要作用。

-多種排產(chǎn)調(diào)度方法的結(jié)合

與已有信息環(huán)境的集成：現(xiàn)有企業(yè)都已具有了自己的信息技術(shù)基礎(chǔ)結(jié)構(gòu)，排產(chǎn)調(diào)度系統(tǒng)應(yīng)能與現(xiàn)有環(huán)境進(jìn)行通訊與信息交換，并作為信息系統(tǒng)的一部分，因此應(yīng)提供與標(biāo)準(zhǔn)系統(tǒng)（如數(shù)據(jù)庫、網(wǎng)絡(luò)等）的通用接口。

相關(guān)技術(shù)

從系統(tǒng)分析方法學(xué)角度而言，解決車間作業(yè)優(yōu)化排產(chǎn)調(diào)度與控制主要涉及：

-運(yùn)籌學(xué)：

復(fù)雜系統(tǒng)分析、各種數(shù)學(xué)模型的分析與建立。

-人工智能理論：

神經(jīng)網(wǎng)絡(luò)的方法、基于智能搜索的方法、基于多代理技術(shù)的合作求解的方法。用于實(shí)時(shí)控制的動態(tài)排產(chǎn)調(diào)度及建模方法。

從信息技術(shù)角度而言，車間作業(yè)排產(chǎn)調(diào)度與控制技術(shù)是計(jì)算機(jī)應(yīng)用領(lǐng)域面臨的一個(gè)非常重要的難題，主要涉及的關(guān)鍵技術(shù)有：

-計(jì)算機(jī)網(wǎng)絡(luò)與通信技術(shù)

-數(shù)據(jù)庫技術(shù)

-系統(tǒng)建模與仿真技術(shù)

-人機(jī)接口

-虛擬現(xiàn)實(shí)技術(shù)

【主要優(yōu)化排產(chǎn)調(diào)度網(wǎng)址】

Production Scheduling Models

http://www.informs.org/Conf/SD97/TALKS/MD23.html

A Direct Hot Charge Steel Production Scheduling System

http://www.informs.org/Conf/NO95/TALKS/SD3.3.html

Partners in Excellence: Production Scheduling and Releases

http://www.uta.com/do/pie/sec131.htm

Article - Production Scheduling Routing and Bill of Materials

http://www.cybor.co.nz/news/prosch.html

Article - Capacity Planning and Real Time Production Scheduling

http://www.cybor.co.nz/news/capplan.html

finishing.com Software, Education, & Training Directory

http://www.finishing.com/Directory/software.html

Production & Scheduling

http://www.informs.org/Conf/Dallas97/TALKS/TD09.html

Master Production Scheduling

http://www.ems.com/education/seminars/pln_seminars/pln_mps.htm

Master Production Scheduling:

http://www.ie.eng.ua.edu/current ... ie464-9/tsld002.htm

Sci.Op-Research (1995) by author

http://mat.gsiaNaNu.edu/GROUP95C/author.html

Sci.Op-Research (1995) by date

http://mat.gsiaNaNu.edu/GROUP95C/date.html

Maestro: Production Scheduling [JJT Inc.]

http://www.compassionatefriends.org/scheduling.html

Production Scheduling & Shop Floor Control

http://www.monitorsoftware.com/product.htm

Master Production Scheduling:

http://www.ie.eng.ua.edu/current ... /ie464-9/sld002.htm

Sci.Op-Research (1995) by thread

http://mat.gsiaNaNu.edu/GROUP95C/index.html

MPS-Master Production Scheduling Module - Integrated Manufacturing Solutions

http://www.magimfg.com/Master_Production_Scheduler.htm

Tempo Adds Value to Factory Production Scheduling

http://www.sm.com/sched/tempo/default.htm

Production Scheduling [3,p191]

http://www-mec.eng.monash.edu.au ... _control/sld014.htm

Production Scheduling [3,p191]

http://www-mec.eng.monash.edu.au ... control/tsld014.htm

Production Scheduling Workstation

http://www.objectapps.com/Produc ... lingWorkstation.htm

Production Scheduling in the Supply Chain Environments

http://www.informs.org/Conf/Montreal98/TALKS/TE10.html

CIM Assignment Production scheduling

http://http2.brunel.ac.uk:8080/~ ... ments/schedule.html

Production Scheduling & Capacity Reservation Systems

http://www.informs.org/Conf/SD97/TALKS/MD09.html

Production & Scheduling II

http://www.informs.org/Conf/Montreal98/TALKS/WC08.html

Production Scheduling Problems at Bethlehem Steel Corporation

http://www.informs.org/Conf/WA96/TALKS/ME18.3.html

Production Scheduling I

http://www.informs.org/Conf/SD97/TALKS/SA10.html

Production Scheduling & Due Date Management

http://www.informs.org/Conf/SD97/TALKS/MC23.html

中國很多企業(yè)處于亞健康狀態(tài)，其特征是“三高”即高交期、高庫存、高成本。精益生產(chǎn)、MES、APS、供應(yīng)鏈優(yōu)化是消除企業(yè)三高的良方，建立高效的計(jì)劃執(zhí)行架構(gòu)體系，實(shí)現(xiàn)卓越制造。

? ? ? ? ? ? ? ? ? ? ? 摘自---蔡穎 高效計(jì)劃與智能排程研究會---------------