一類流水型知識(shí)化制造單元調(diào)度的自進(jìn)化算法

李文超 嚴(yán)洪森

1．東南大學(xué)復(fù)雜工程系統(tǒng)測(cè)量與控制教育部重點(diǎn)實(shí)驗(yàn)室，南京，210096 2．江蘇大學(xué)，鎮(zhèn)江，212013

0 引言

知識(shí)化制造系統(tǒng)（knowledgeable manufacturing system，KMS）是于2001年出現(xiàn)的關(guān)于制造系統(tǒng)的一個(gè)新概念［1］，它以時(shí)間、質(zhì)量、成本、服務(wù)和環(huán)境為主要目標(biāo)，具備自適應(yīng)、自學(xué)習(xí)、自進(jìn)化、自重構(gòu)等特征，是一種高智能制造系統(tǒng)。近年來隨著對(duì)KMS研究的逐步深入，不斷有新的成果推出。如文獻(xiàn)［2－4］提出將先進(jìn)制造模式用知識(shí)網(wǎng)表示，運(yùn)用知識(shí)網(wǎng)多重集的運(yùn)算，實(shí)現(xiàn)先進(jìn)制造模式的自重構(gòu)；文獻(xiàn)［5］利用B－Q學(xué)習(xí)算法，構(gòu)建了一種適用于KMS中動(dòng)態(tài)調(diào)度問題的自適應(yīng)調(diào)度控制策略；文獻(xiàn)［6］通過構(gòu)建一種分布式自動(dòng)機(jī)死鎖監(jiān)控器來解決知識(shí)化制造單元死鎖問題；文獻(xiàn)［7］提出了一種運(yùn)用自學(xué)習(xí)方法確定不同模型的組合權(quán)重對(duì)產(chǎn)品市場(chǎng)擴(kuò)散進(jìn)行預(yù)測(cè)的方法；文獻(xiàn)［8］對(duì)知識(shí)網(wǎng)多重集表達(dá)式進(jìn)行優(yōu)化，給出了基于用戶功能需求的知識(shí)網(wǎng)自動(dòng)生成方法。

上述文獻(xiàn)多偏重于對(duì)KMS的整體性能進(jìn)行研究（如對(duì)系統(tǒng)自重構(gòu)、自適應(yīng)等特征進(jìn)行研究），而對(duì)于組成KMS的基本單元KMC的個(gè)體性能（如自進(jìn)化）的研究則較少涉及。KMS作為復(fù)雜大系統(tǒng)，其基本元素KMC間差別很大，可分為加工Agent、物料運(yùn)輸設(shè)備、工業(yè)現(xiàn)場(chǎng)總線、產(chǎn)品市場(chǎng)預(yù)測(cè)、調(diào)度決策等類型模塊。不同類別KMC間存在本質(zhì)差別，對(duì)其個(gè)體性能的研究應(yīng)針對(duì)具體問題進(jìn)行具體分析。通過對(duì)流水型知識(shí)化制造單元（FSKMC）的分析，我們提出一種有別于常規(guī)，以尋優(yōu)為目的，具備學(xué)習(xí)能力的自進(jìn)化算法。該算法能夠通過離線學(xué)習(xí)，通過從環(huán)境中獲取相應(yīng)知識(shí)來不斷提高其搜索能力。

流水型知識(shí)化制造單元是以Flow－shop問題為對(duì)象的一類調(diào)度決策型制造單元。與傳統(tǒng)Flow－shop問題研究所不同的是，該單元雖然以獲取最優(yōu)調(diào)度策略作為其目標(biāo)，但更注重于在運(yùn)行過程中通過對(duì)已往調(diào)度數(shù)據(jù)的分析學(xué)習(xí)獲得相關(guān)知識(shí)的能力，使其調(diào)度水平能夠不斷提升，即具備自進(jìn)化能力。機(jī)器數(shù)大于2的Flow－shop調(diào)度（簡(jiǎn)稱Flow－shop）問題自1976年被證明為NP完全問題后［9］，對(duì)于該問題的研究大多集中于以尋找較優(yōu)解為目標(biāo)的近似算法，如文獻(xiàn)［10］所提的禁忌搜索算法、文獻(xiàn)［11－12］的遺傳算法，以及文獻(xiàn)［13］的模擬退火算法等。這些啟發(fā)式近似算法對(duì)于規(guī)模較大問題能夠在規(guī)定時(shí)間內(nèi)找到較滿意近優(yōu)解，但這類方法由于引入隨機(jī)性，也存在一些缺點(diǎn)，如對(duì)問題參數(shù)敏感、依賴初始解等不穩(wěn)定特征，并且由于其結(jié)構(gòu)是一固定程式，算法性能得不到改善。

Flow－shop屬于NP完全問題，至今仍未有獲取其最優(yōu)解的有效算法。近來不斷有學(xué)者提出一些具備學(xué)習(xí)能力的算法，這類算法的特點(diǎn)是在運(yùn)行時(shí)通過對(duì)已往數(shù)據(jù)進(jìn)行分析能夠獲取問題特征及規(guī)律，使算法的求解性能得以提升，如文獻(xiàn)［14－16］提出的算法均能夠在一定程度上通過學(xué)習(xí)提高算法搜索能力。基于迭代的強(qiáng)化學(xué)習(xí)（reinforcement learning）對(duì)于調(diào)度類問題展現(xiàn)了較好的學(xué)習(xí)能力，目前已被應(yīng)用于調(diào)度問題研究［17－19］。由于Flow－shop的解空間隨著問題規(guī)模變大急劇增加，使強(qiáng)化學(xué)習(xí)所面臨的狀態(tài)空間迅速變大，導(dǎo)致值函數(shù)收斂速度變慢。針對(duì)該問題，本文提取問題典型參數(shù)來表征系統(tǒng)狀態(tài)特征，有效降低了狀態(tài)空間的復(fù)雜性。同時(shí)采用一種混合核支持向量機(jī)（SVM）對(duì)值函數(shù)進(jìn)行逼近，使所學(xué)知識(shí)具備較強(qiáng)泛化能力，具備良好自進(jìn)化能力。

1 問題描述

流水型知識(shí)化制造單元含有m個(gè)處理Agent，有n項(xiàng)任務(wù)（task）待處理。需要對(duì)n項(xiàng)任務(wù)進(jìn)行調(diào)度，即確定各項(xiàng)任務(wù)在各Agent上的處理順序，使得某些性能指標(biāo)達(dá)到最優(yōu)，通常以任務(wù)最大完工周期（makespan）作為指標(biāo)。各項(xiàng)任務(wù)在各Agent上處理時(shí)，需滿足如下要求：①每項(xiàng)任務(wù)按相同次序通過m個(gè)Agent；②每個(gè)Agent上各項(xiàng)任務(wù)通過次序相同；③每項(xiàng)任務(wù)在每個(gè)Agent上的處理時(shí)間是確定的；④每個(gè)Agent在同一時(shí)間只能完成一項(xiàng)任務(wù)；⑤每項(xiàng)任務(wù)在同一時(shí)間只能在一個(gè)Agent上完成。

該單元每個(gè)可行調(diào)度方案可用排列：ω＝（ω（1），ω（2），…，ω（i），…，ω（n））表 示，ω（i）（i ＝1，2，…，n）為排在第i個(gè)位置上的待處理任務(wù)。記Cmax（ω）為序列ω的最大完工周期，Π為該單元所有可行調(diào)度方案的集合，則最優(yōu)調(diào)度方案為

記piω（j）為序列ω 中第j 項(xiàng)任務(wù)ω（j）在第i個(gè)Agent上的處理時(shí)間，則n項(xiàng)任務(wù)在m個(gè)Agent上的處理時(shí)間可用一m×n矩陣P（ω）表示，即

式中，piω（j）為P（ω）的第i行第j列的元素。

2 算法相關(guān)理論基礎(chǔ)

本文所提自進(jìn)化算法以強(qiáng)化學(xué)習(xí)中值迭代思想為基礎(chǔ)，以q因子表示值函數(shù)，通過一種混合核支持向量機(jī)實(shí)現(xiàn)對(duì)q因子的學(xué)習(xí)。

2.1 強(qiáng)化學(xué)習(xí)

作為機(jī)器學(xué)習(xí)和智能控制方面的一種重要技術(shù)方法，強(qiáng)化學(xué)習(xí)已被廣泛應(yīng)用于控制系統(tǒng)、機(jī)器人、庫存控制、調(diào)度管理等諸多領(lǐng)域。其主要思想在于智能系統(tǒng)通過觀察環(huán)境對(duì)自身行為的反饋信號(hào)，獲取知識(shí)，改進(jìn)行動(dòng)策略，達(dá)到預(yù)定目的。

系統(tǒng)在狀態(tài)s采取策略π時(shí)，期望回報(bào)可用值函數(shù)vπ（s）表示如下［20］：

系統(tǒng)在狀態(tài)s采取的最優(yōu)策略π＊（s）可由對(duì)應(yīng)最優(yōu)值函數(shù)v＊（s）確定。理論上可求解式（5）獲得v＊（s）值。對(duì)于流水型知識(shí)化制造單元，由于每個(gè)問題狀態(tài)空間隨問題規(guī)模急劇增加，該方法不可行。我們采取值迭代方法求取v＊（s）。記狀態(tài)—?jiǎng)幼鲗?duì)（si，a）的q因子為

則式（5）可寫為

在一定簡(jiǎn)化條件下，式（8）所得＾q（si，a）可完全收斂于q（si，a）［21］。即便如此，對(duì)于流水型知識(shí)化制造單元，由于前述原因，該方法依然不現(xiàn)實(shí)。為此，我們用支持向量機(jī)通過離線學(xué)習(xí)方式，實(shí)現(xiàn)對(duì)q（si，a）的逼近。

2.2 支持向量機(jī)

基于VC維理論由結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則導(dǎo)出的支持向量機(jī)已被廣泛應(yīng)用于許多模式識(shí)別、非線性函數(shù)回歸問題［21］，其基本思想是：將輸入向量映射到一個(gè)高維線性特征空間，利用定義在特征空間的懲罰超平面作為決策面，使模型的復(fù)雜性問題在高維空間得以解決，結(jié)果具備很好的泛化性能。

對(duì)于樣本集X ＝ ｛（xi，di）｜i＝1，2，…，n｝，d與x存在函數(shù)依賴關(guān)系。d的估計(jì)y可通過將x映射到高維線性空間實(shí)現(xiàn)，即

引入非負(fù)松弛變量ξi、ξ′i，上述函數(shù)回歸問題可轉(zhuǎn)化為模式分類問題，相應(yīng)地，在高維空間分類超平面約束優(yōu)化問題可描述為［21］

式中，C、ε為給定常數(shù)。上述約束優(yōu)化問題可通過引入Lagrange函數(shù)并構(gòu)造其對(duì)偶問題進(jìn)行求解，可得到d的逼近函數(shù)為

式中，αi、α′i為L(zhǎng)agrange乘子，可由式（10）的Lagrange函數(shù)對(duì)偶問題求得；k（x，xi）為由Mercer定理定義的內(nèi)積核函數(shù)［21］。

內(nèi)積核函數(shù)的具體形式在很大程度上決定著SVM的性能。目前常用核函數(shù)形式主要有多項(xiàng)式核函數(shù)、Gauss核函數(shù)、Sigmoid核函數(shù)等。多項(xiàng)式核函數(shù)有良好全局性能，具備較強(qiáng)外推能力；Gauss核函數(shù)局部性能較好；Sigmoid核函數(shù)不穩(wěn)定，若選擇參數(shù)不當(dāng)則不能滿足核函數(shù)要求。為充分發(fā)揮SVM的性能，本文提出一種混合核函數(shù)，并證明其滿足核函數(shù)條件。所給核函數(shù)形式為

式中，λ為最優(yōu)混合系數(shù)，λ∈ （0，1）。

為簡(jiǎn)化式（12）的證明過程，先引入一核函數(shù)判定定理，具體如下：

引理1［22］X 為一給定有限輸入空間，k（x，z）（x，z∈X）為定義在該空間上的一對(duì)稱函數(shù)，則k（x，z）為核函數(shù)的充分必要條件是矩陣K為半正定陣，即

定理1 式（12）所給函數(shù)kmix（x，z）是定義在Rd空間上的核函數(shù)。

證明 函數(shù)k1（x，z）＝ （xTz＋1）2是定義在Rd空間上的一多項(xiàng)式核函數(shù)，則矩陣K（1）為

對(duì) ?x?Rd，有

有

即矩陣K為半正定陣。另外，由式（12）可知：kmix（x，z）＝kmix（z，x），即kmix（x，z）是對(duì)稱函數(shù)，故它是定義在Rd空間上一核函數(shù)，證畢。

3 FSKMC調(diào)度自進(jìn)化算法

基于強(qiáng)化學(xué)習(xí)的FSKMC調(diào)度自進(jìn)化算法能夠通過離線仿真學(xué)習(xí)，所學(xué)知識(shí)隱含在SVM的回歸函數(shù)中，如遇到類似問題，調(diào)度單元調(diào)用所獲知識(shí)能夠迅速給出問題決策方案。在算法具體實(shí)施中存在一些技術(shù)性問題，如系統(tǒng)狀態(tài)識(shí)別、動(dòng)作表示等，這些問題的處理直接影響著算法性能。

3.1 FSKMC狀態(tài)特征識(shí)別

對(duì)于一具體FSKMC問題，其可行調(diào)度方案ω和處理時(shí)間矩陣P（ω）能準(zhǔn)確表示其狀態(tài)。這種表示難以被學(xué)習(xí)系統(tǒng)識(shí)別，需要抽取系統(tǒng)的主要特征，并做必要簡(jiǎn)化，使同規(guī)模FSKMC問題有相同表示形式。具體實(shí)施方法如下：

（1）處理時(shí)間矩陣P（ω）歸一化。對(duì)具體問題的P（ω）進(jìn)行歸一化處理，消除其數(shù)值上的差別。歸一化后的矩陣記為P（ω）＝ （piω（j））m×n，可表示為

（2）狀態(tài)特征抽取。各種狀態(tài)特征參數(shù)定義如下：

縱向指標(biāo)t

橫向指標(biāo)a

記ac，i為第i個(gè)Agent完工時(shí)間，有

由上述特征參數(shù)，對(duì)于規(guī)模為m×n的FSKMC，其狀態(tài)特征（支持向量機(jī)的輸入量）可表示為

3.2 動(dòng)作表示

通過SVM對(duì)q因子進(jìn)行函數(shù)逼近，狀態(tài)和動(dòng)作都需要有明確的表示方法。在此給出FSKMC在學(xué)習(xí)過程中的具體動(dòng)作定義，并給出其量化表示方法。

定義1 FSKMC處于狀態(tài)ω時(shí)，將ω中處于第f個(gè)位置上的任務(wù)ω（f）和處于第g個(gè)位置上的任務(wù)ω（g），相互交換位置的操作稱為對(duì)狀態(tài)ω的一個(gè)動(dòng)作，記為sw（f，g）（f，g ∈ （1，2，…，n），f≠g），其值為

式（30）是對(duì)狀態(tài)ω采取動(dòng)作sw（f，g）的一個(gè)數(shù)值化表示，因?yàn)樵搫?dòng)作作為支持向量機(jī)的一個(gè)輸入變量，需要數(shù)值化。

對(duì)狀態(tài)ω采取動(dòng)作sw（f，g），系統(tǒng)轉(zhuǎn)換到另外一個(gè)狀態(tài)ω＇，可表示如下：

3.3 自進(jìn)化算法實(shí)現(xiàn)

算法核心主要通過對(duì)式（8）不斷迭代更新，調(diào)整SVM逼近函數(shù)參數(shù)，使其能夠更加接近q因子真實(shí)值。其中＾qt（si，a）由式（11）逼近函數(shù)獲得，其逼近誤差為

在FSKMC中，狀態(tài)si、sj由其對(duì)應(yīng)序列解ωi、ωj的處理時(shí)間矩陣表示，即si＝P（ωi），sj＝P（ωj）。

記每次迭代狀態(tài)－動(dòng)作對(duì)目標(biāo)值為

在每步迭代中，適當(dāng)改變逼近函數(shù)參數(shù)，以縮短誤差。

算法實(shí)現(xiàn)步驟如下：

（1）初始化。對(duì)SVM的權(quán)值w賦初始權(quán)值w0。從Π中隨機(jī)選擇序列ω0為FSKMC的初始狀態(tài)s0，即s0＝P（ω0）；對(duì)st賦值，即st＝s0，ω ＝ω0。給出計(jì)算循環(huán)次數(shù)上下界N1、N2和常數(shù)C、ε、Δ。

（2）對(duì)狀態(tài)st所在序列ω提取狀態(tài)特征，即求sc（ω）。選取使?fàn)顟B(tài)－動(dòng)作對(duì)的立即回報(bào)值r（st，a）最大的動(dòng)作為當(dāng)前動(dòng)作，計(jì)算動(dòng)作值sw（f，g）。

（3）由式（11）計(jì)算＾qt（st，a），由式（32）、式（33）分 別 計(jì) 算 Δqt（st，a）、qtart（st，a）， 并 判 斷｜Δqt（st，a）｜＜Δ是否成立。若成立，轉(zhuǎn)步驟（6）；否則轉(zhuǎn)步驟（4）。

（4）判斷計(jì)算循環(huán)次數(shù)是否超過上界N1，若是，則轉(zhuǎn)步驟（7）；否則，將 點(diǎn) （sc（ω），sw（p，q），qtar（st，a））加入SVM的樣本點(diǎn)集X。對(duì)SVM重新進(jìn)行學(xué)習(xí)。

（5）更新狀態(tài)。將狀態(tài)－動(dòng)作對(duì)（st，a）的后繼狀態(tài)s′t、ω＇分別賦予st、ω，轉(zhuǎn)步驟（2）。

（6）判斷計(jì)算循環(huán)次數(shù)是否低于下界N2。若是，則轉(zhuǎn)步驟（5）；否則，轉(zhuǎn)步驟（7）。

（7）終止程序。

4 數(shù)值仿真實(shí)驗(yàn)

我們從兩個(gè)方面設(shè)計(jì)了數(shù)值仿真實(shí)驗(yàn)：一方面從考察算法對(duì)問題求解整體效果角度進(jìn)行仿真實(shí)驗(yàn)；另一方面從考察算法離線學(xué)習(xí)規(guī)模變化對(duì)算法性能影響進(jìn)行仿真實(shí)驗(yàn)。前者主要針對(duì)一些典型算例，比較分析所提算法與傳統(tǒng)算法間的差別；后者主要通過改變算法離線學(xué)習(xí)時(shí)間（迭代次數(shù)）以及訓(xùn)練算例規(guī)模，分析比較算法性能變化規(guī)律。算法用MATLAB7．0編寫程序?qū)崿F(xiàn)，仿真實(shí)驗(yàn)在 CPU 為 Celeron M（1．6GHz），內(nèi)存為504M的PC上進(jìn)行。

針對(duì)文獻(xiàn)［10］中的五類規(guī)模（分別為20×20、50×20、100×20、200×20、500×20）算例，分別從求解精度和效率兩個(gè)方面對(duì)文獻(xiàn)［10－11］所提算法（分別記為TSGW和RY）和我們所提算法（記為SEFSMC）進(jìn)行比較。算法SEFSMC在求解問題前進(jìn)行了有限度離線學(xué)習(xí)，學(xué)習(xí)過程各參數(shù)設(shè)定如表1所示。

表1 學(xué)習(xí)過程主要參數(shù)

圖1所示為三種算法求解精度比較（橫坐標(biāo)Ti表示不同規(guī)模算例，順序同前；縱坐標(biāo)為各類算例最大完工周期Cmax）。圖中顯示出算法SEFSMC的精度低于算法TSGW和RY的精度，在問題規(guī)模較小時(shí)差別較顯著，但隨著問題規(guī)模增加，算法SEFSMC和算法TSGW、RY的精度間差距逐步減小。

圖1 三種算法求解精度比較

圖2 所示為三種算法求解效率比較。算法SEFSMC求解所花時(shí)間遠(yuǎn)低于算法TSGW和RY的求解時(shí)間，且隨著問題規(guī)模增加，算法TSGW和RY花費(fèi)時(shí)間急劇增加，而SEFSMC所花費(fèi)時(shí)間上升幅度緩慢。

不像傳統(tǒng)算法，其求解性能保持固定不變，算法SEFSMC的性能是隨著迭代次數(shù)和訓(xùn)練算例增加而不斷提升的。圖3所示為算法SEFSMC對(duì)規(guī)模為100×20算例學(xué)習(xí)時(shí)，求解精度與迭代次數(shù)、訓(xùn)練算例數(shù)目之間的變化趨勢(shì)。由圖3可知，算法求解精度隨學(xué)習(xí)過程中迭代次數(shù)的增加

圖2 三種算法求解效率比較

圖3 求解精度與迭代次數(shù)、訓(xùn)練算例之間的趨勢(shì)

而不斷提高，學(xué)習(xí)樣本（即算例）增加使得學(xué)習(xí)更充分，從而使算法求解精度得到提高。算例按文獻(xiàn)［23］方法隨機(jī)產(chǎn)生，圖中縱坐標(biāo)為各算例最大完工周期的均值，橫坐標(biāo)為學(xué)習(xí)過程迭代次數(shù)。

圖4所示為算法SEFSMC對(duì)規(guī)模為200×20算例學(xué)習(xí)時(shí)，求解時(shí)間與迭代次數(shù)、訓(xùn)練算例數(shù)目之間的變化趨勢(shì)。由圖4可知，當(dāng)學(xué)習(xí)樣本較少時(shí)因?qū)W習(xí)不太充分，算法求解時(shí)間雖然隨迭代次數(shù)增加而總體下降，但不很穩(wěn)定。當(dāng)學(xué)習(xí)樣本增多（10個(gè)算例以上），學(xué)習(xí)過程充分時(shí)，求解時(shí)間就會(huì)隨著迭代次數(shù)的增加而不斷降低。算例產(chǎn)生方式同圖3，圖中縱坐標(biāo)為求解時(shí)間均值，橫坐標(biāo)為學(xué)習(xí)過程迭代次數(shù)。

圖4 求解時(shí)間與迭代次數(shù)、訓(xùn)練算例之間的趨勢(shì)

圖3 、圖4仿真說明，算法SEFSMC在充分學(xué)習(xí)的情況下，其自身求解精度和求解效率能不斷得到提高，這些學(xué)習(xí)過程均可在離線情況下通過仿真完成。

5 結(jié)語

本文針對(duì)流水型知識(shí)化制造單元（FSKMC），提出一種具備學(xué)習(xí)能力的調(diào)度自進(jìn)化算法。通過離線學(xué)習(xí)算法能夠從環(huán)境中獲取相應(yīng)知識(shí)，不斷提高其搜索能力。提出一種混合核支持向量機(jī)能夠?qū)χ岛瘮?shù)進(jìn)行有效逼近，避免學(xué)習(xí)過程中狀態(tài)過多問題。數(shù)值仿真實(shí)驗(yàn)表明，算法雖然在求解精度方面存在不足，但在求解效率方面有明顯優(yōu)勢(shì)，且求解精度的不足可通過不斷進(jìn)行離線學(xué)習(xí)加以提升，因此比較適合工程應(yīng)用。

［1］ 嚴(yán)洪森，劉飛．知識(shí)化制造系統(tǒng)－新一代先進(jìn)制造系統(tǒng)［J］．計(jì)算機(jī)集成制造系統(tǒng)，2001，7（8）：7－11．

［2］ Yan Hongsen．A New Complicated Knowledge Representation Approach Based on Knowledge Meshes［J］．IEEE Transactions on Knowledge and Data Engineering，2006，18（1）：47－62．

［3］ 嚴(yán)洪森．新的先進(jìn)制造模式知識(shí)表示方法［J］．機(jī)械工程學(xué)報(bào)，2006，42（10）：80－90．

［4］ 薛朝改，嚴(yán)洪森．基于Agent網(wǎng)的知識(shí)網(wǎng)的自重構(gòu)研究［J］．計(jì)算機(jī)集成制造系統(tǒng)，2003，9（11）：995－1000．

［5］ 楊宏兵，嚴(yán)洪森．知識(shí)化制造系統(tǒng)中動(dòng)態(tài)調(diào)度的自適應(yīng)策略研究［J］．控制與決策，2007，22（12）：1335－1340．

［6］ 楊宏兵，嚴(yán)洪森．基于自動(dòng)機(jī)的知識(shí)化制造單元死鎖控制策略研究［J］．中國機(jī)械工程，2009，20（5）：546－552．

［7］ 馬開平，嚴(yán)洪森．產(chǎn)品市場(chǎng)擴(kuò)散行為預(yù)測(cè)的自學(xué)習(xí)方法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2008，14（12）：2484－2491．

［8］ 薛朝改，嚴(yán)洪森．．基于用戶功能需求的知識(shí)網(wǎng)的自動(dòng)生成研究［J］．控制與決策，2005，20（9）：996－1001．

［9］ Garey M R，Johnson D S，Sethi R．The Complexity of Flow－shop and Job－shop Scheduling［J］．Mathematics of Operations Research，1976，1（2）：117－129．

［10］ Grabowski J，Wodecki M．A Very Fast Tabu Search Algorithm for the Permutation Flow－shop Problem with Makespan Criterion［J］．Computers and Operations Research，2004，31（11）：1891－1909．

［11］ Reeves C R，Yamada T．Genetic Algorithms，Path Relinking，and the Flowshop Sequencing Problem［J］．Evolutionary Computation，1998，6（1）：45－60．

［12］ Wang L，Zheng D Z．An Effective Hybrid Heuristic for Flow Shop Scheduling［J］．The International Journal of Advanced Manufacturing Technology，2003，21（1）：38－44．

［13］ Ogbu F，Smith D．Simulated Annealing for Permutation Flowshop Problem［J］．Omega，1990，19（1）：64－67．

［14］ Anurag A，Selcuk C，Enes E．Improvement Heuristic for the Flow－shop Scheduling Problem：an Adaptive－learning Approach［J］．European of Operational Research，2006，169（2）：801－815．

［15］ Lee I，Michael J S．A Neural－net Approach to Real Time Flow－shop Sequencing［J］．Computers＆Industrial Engineering，2000，38（1）：125－147．

［16］ Solimanpur M，Vrat P，Shankar R．A Neural－tabu Search Heuristic for Flow－shop Scheduling Problem［J］．Computers ＆ Operations Research，2004，31（11）：2151－2164．

［17］ Aydin M E，O¨ztemel E．Dynamic Job－shop Scheduling Using Reinforcement Learning Agents［J］．Robotics and Autonomous Systems，2000，33（2）：169－178．

［18］ Stefan P．Flow－shop Scheduling Based on Reinforcement Learning Algorithm［J］．Production Systems and Information Engineering，2003，1（1）：83－90．

［19］ Wang Y C，Usher J M．Application of Reinforcement Learning for Agent－based Production Scheduling［J］．Engineering Applications of Artificial Intelligence，2005，18（1）：73－82．

［20］ Mitchell T M．Machine Learning［M］．Beijing：China Machine Press，2003．

［21］ Haykin S．Neural Networks：a Comprehensive Foundation［M］．2nd．Beijing：China Machine Press，2004．

［22］ Cristianini N，Shawe T J．An Introduction to Support Vector Machines and other Kernel－based Learning Methods［M］．Beijing：China Machine Press，2005．

［23］ Taillard E．Benchmarks for Basic Scheduling Problems［J］．European Journal of Operational Research，1993，64（2）：278－285．