多目標(biāo)柔性Ｊｏｂ Ｓｈｏｐ調(diào)度問題的技術(shù)現(xiàn)狀和發(fā)展趨勢

摘 要：首先概述了多目標(biāo)柔性Job Shop調(diào)度問題的基本概念，包括問題定義、常用假設(shè)條件、性能指標(biāo)和問題的分類，討論了其復(fù)雜性；其次，分別從建模、優(yōu)化方法和原型系統(tǒng)研究方面綜述了其發(fā)展過程和研究現(xiàn)狀，對(duì)一類更加通用的多目標(biāo)柔性Job Shop問題進(jìn)行了簡單的文獻(xiàn)綜述；最后指出了現(xiàn)有研究存在的問題與不足，并對(duì)未來的發(fā)展趨勢進(jìn)行了探討。

關(guān)鍵詞： 多目標(biāo)； 柔性工作車間調(diào)度； 建模； 優(yōu)化方法； 原型系統(tǒng)

中圖分類號(hào)：TP273.5 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)03－0001－05

自從1954年Johnson對(duì)兩臺(tái)機(jī)床的Flow Shop型調(diào)度問題進(jìn)行研究后，學(xué)術(shù)界和實(shí)務(wù)界對(duì)生產(chǎn)調(diào)度問題展開了廣泛的探討，并取得了豐碩的成果。但是這些調(diào)度理論對(duì)現(xiàn)實(shí)情況設(shè)定了很多假設(shè)，很難用于生產(chǎn)實(shí)踐中[1]。因此，探討更少假設(shè)、能真正體現(xiàn)實(shí)際生產(chǎn)的調(diào)度理論和方法具有非常重要的現(xiàn)實(shí)意義。

柔性Job Shop調(diào)度問題[2]（Flexible Job Shop Scheduling Problem， FJSP）就是在這種形勢下產(chǎn)生的。它是對(duì)經(jīng)典Job Shop問題的擴(kuò)展，不但繼承了Job Shop問題的所有特征，而且增加了新的求解難度：允許某道工序在多臺(tái)機(jī)器上加工，一臺(tái)機(jī)器可以加工多種類型的工序。調(diào)度的首要工作是將工序分配到機(jī)器上，即機(jī)器分配問題；其次才是真正的調(diào)度問題。多目標(biāo)下的FJSP擴(kuò)大了最優(yōu)調(diào)度的搜索空間，而且需要滿足更多約束條件，導(dǎo)致問題更加復(fù)雜。這類調(diào)度問題的復(fù)雜性、約束多樣性、動(dòng)態(tài)性決定了對(duì)該問題的研究能夠反映實(shí)際生產(chǎn)過程，具有一定的實(shí)際意義[3]。本文綜述了多目標(biāo)FJSP的一系列研究成果。

1 多目標(biāo)FJSP

（1）調(diào)度問題描述。

多目標(biāo)FJSP是經(jīng)典Job Shop調(diào)度的擴(kuò)展，可在經(jīng)典Job Shop的基礎(chǔ)上定義：

在M個(gè)機(jī)器上加工N個(gè)工件，每個(gè)工件J_j由n_j個(gè)工序組成，n_j個(gè)工序之間有工藝的先后約束，工件的每道工序可由M臺(tái)機(jī)器中的多臺(tái)機(jī)器加工。M_ij表示第j個(gè)工件的第i道工序可用機(jī)器集合M_ij{1，2，…，M}；O_ijk表示第j個(gè)工件的第i道工序可用機(jī)器k；p_ijk表示第j個(gè)工件的第i道工序在第k個(gè)機(jī)器上加工需要的時(shí)間，即1≤j≤N，1≤i≤n_j，1≤k≤M。調(diào)度的任務(wù)是在M臺(tái)機(jī)器上安排N個(gè)工件的加工任務(wù)，同時(shí)最優(yōu)化一系列給定的性能指標(biāo)，并滿足一些約束條件。

（2）常用假設(shè)。

為了簡化問題，經(jīng)常作出以下假設(shè)：

①所有機(jī)器在t=0時(shí)刻都可用。

②所有工件在t=0時(shí)刻都可被加工。

③所有工件的工藝計(jì)劃是固定不變的，即工序的先后順序不能違背。

④工序在可供選擇的機(jī)器上的加工時(shí)間已確定。

⑤每個(gè)工件在固定時(shí)刻只能在一臺(tái)機(jī)器上加工。

⑥加工是非搶占式的，即給定時(shí)刻機(jī)器k只能加工一個(gè)工件，只有該工件的此工序加工完畢后才能加工別的工件，即工件的加工不允許中斷。

（3）常用性能指標(biāo)。

多目標(biāo)的FJSP研究文獻(xiàn)中，常用的調(diào)度指標(biāo)如下：

①M(fèi)akespan是調(diào)度的最小生產(chǎn)周期，即所有工件的最大完成時(shí)間的最小值。這個(gè)指標(biāo)用得最多，可參見文獻(xiàn)[4~8]等。

②流經(jīng)時(shí)間是指工件最后一道工序完成時(shí)間與開始釋放時(shí)間之間的差值，可分為工件的流經(jīng)時(shí)間、整個(gè)調(diào)度任務(wù)的最大流經(jīng)時(shí)間、平均流經(jīng)時(shí)間和加權(quán)流經(jīng)時(shí)間等。這類指標(biāo)也比較常用，可參見文獻(xiàn)[4，9]等。

③提前時(shí)間/延遲時(shí)間是指工件的完成時(shí)間與交貨期時(shí)間的差值。差值為正時(shí)是延遲時(shí)間；差值為負(fù)時(shí)是提前時(shí)間。在JIT制企業(yè)中，這兩個(gè)指標(biāo)是最重要的。其變化形式有最大提前時(shí)間/最大延遲時(shí)間、平均提前時(shí)間/平均延遲時(shí)間，可參見文獻(xiàn)[8，10～14]等。

④機(jī)器總負(fù)荷/瓶頸機(jī)器的最大負(fù)荷。機(jī)器總負(fù)荷是指一個(gè)調(diào)度方案產(chǎn)生的所有機(jī)器負(fù)荷的總和；瓶頸機(jī)器的最大負(fù)荷是指負(fù)荷最大的機(jī)器的負(fù)荷值。在帶有機(jī)器柔性的FJSP中，這兩個(gè)指標(biāo)最常見，因?yàn)樗鼈儗?duì)于合理分配資源和提高生產(chǎn)效率有著重要的意義，可參見文獻(xiàn)[7，15]等。

⑤成品存儲(chǔ)成本是指工件提前完成又不能提前交貨時(shí)，制造商需要一定的費(fèi)用保管成品，可參見文獻(xiàn)[17]等。

⑥拖工懲罰成本是指工件晚于交貨期完成時(shí)，制造商需要提供給客戶額外的罰金和與拖期時(shí)間相關(guān)的罰金，可參見文獻(xiàn)[17]等。

（4）問題分類。

由FJSP的描述可以看出，該類問題可分為兩類[18]：

①完全FJSP，對(duì)于O_ij，M_ij=M，表示第j個(gè)工件的第i道工序可以在所有機(jī)器上加工；

②部分FJSP，對(duì)于O_ij，M_ijM，表示第j個(gè)工件的第i道工序只能在M個(gè)機(jī)器中的部分機(jī)器上加工，即至少有一臺(tái)機(jī)器不能加工i工序。

（5）復(fù)雜性分析。

如前所述，F(xiàn)JSP包含兩個(gè)子問題，即機(jī)器分配問題和工序調(diào)度問題。相對(duì)經(jīng)典Job Shop問題，求解難度增加；當(dāng)FJSP具有幾個(gè)目標(biāo)函數(shù)時(shí)，求解難度進(jìn)一步增加。因?yàn)樵诙嗄繕?biāo)優(yōu)化中，最優(yōu)的定義已發(fā)生變化，真正試圖找到的是一種妥協(xié)（即有效解），而不是簡單的一個(gè)全局最優(yōu)解。一個(gè)有效解（Pareto最優(yōu)解）是指不可能在不損壞其他目標(biāo)性能的前提下提高任何一個(gè)目標(biāo)的性能[19]。對(duì)于多目標(biāo)互相沖突的優(yōu)化問題，最優(yōu)解不止一個(gè)。帶有兩個(gè)或單個(gè)目標(biāo)的問題可以從指標(biāo)圖的含義中清楚地表明選擇，但在高維問題中，顯示結(jié)果成為超平面，進(jìn)行選擇就非常復(fù)雜了，復(fù)雜程度隨著目標(biāo)數(shù)量的增加而大致呈指數(shù)上升趨勢，計(jì)算費(fèi)用也隨著目標(biāo)數(shù)量的增加而顯著上升。唐國春[20]已經(jīng)證明，如果問題1‖γ1是NPhard的，那么多目標(biāo)調(diào)度問題1‖(γ1，γ2）和線性權(quán)函數(shù)的多目標(biāo)調(diào)度問題1‖αγ1+βγ2也是NPhard的。Janson[9]證明了對(duì)于單目標(biāo)的FJSP存在近似的多項(xiàng)式求解方法，用m1m|chain，op≤u|Cmax表示FJSP，已經(jīng)證明212|chain，n=3|Cmax， 312|chain，n=2|Cmax， 212|chain，op≤2|Cmax等問題是NPhard。姜思杰[21]用分步法求解單目標(biāo)的FJSP的兩個(gè)子問題，并討論了問題的復(fù)雜性，得出的結(jié)論是問題的復(fù)雜度不僅與ｍ2ｎ、ｍｎ和ｍ有關(guān)，還與總操作數(shù)有關(guān)。專門針對(duì)多目標(biāo)FJSP的復(fù)雜性分析尚未見諸文獻(xiàn)。

2 發(fā)展過程與研究現(xiàn)狀

2.1 發(fā)展歷史

首先研究FJSP的是Bruker和Schlie[2]，他們開發(fā)出了一個(gè)多項(xiàng)式方法求解兩個(gè)工件的FJSP；當(dāng)時(shí)他們假設(shè)能加工同一個(gè)工序的機(jī)器的加工時(shí)間是相同的。在此以后，學(xué)者們逐漸展開了對(duì)FJSP的研究。文獻(xiàn)中也有將FJSP稱為帶有機(jī)器柔性的JSP[22]或者具有柔性加工路徑的JSP[23]。

2.2 建模方法研究現(xiàn)狀

2.2.1 數(shù)學(xué)模型

一些學(xué)者從整數(shù)規(guī)劃的角度建立了多目標(biāo)FJSP的數(shù)學(xué)模型。龐哈利[24]從集成化的角度研究了柔性Job Shop計(jì)劃和調(diào)度問題，建立了兩層混合整數(shù)規(guī)劃模型，并用遺傳算法求解最佳加工路徑，用啟發(fā)式規(guī)則求解調(diào)度問題。

2.2.2 析取圖模型

JSSP的析取圖模型G=(N，A，E)由Balas[25]提出，N包含代表所有工序的節(jié)點(diǎn)；A包含連接同一工件的鄰接工序的邊；E包含連接同一機(jī)器上加工工序的非連接邊，非連接邊可以有兩個(gè)可能的方向。調(diào)度過程將固定所有非連接邊的方向，以確定同一機(jī)器上工序的順序，并采用帶有優(yōu)先箭頭的連接邊取代非連接邊。DauzèrePérès[22]用非連接圖建模了調(diào)度問題，并建立了鄰域結(jié)構(gòu)，進(jìn)而采用基于鄰域結(jié)構(gòu)的禁忌搜索進(jìn)行求解。

2.3 優(yōu)化方法研究現(xiàn)狀

2.3.1 數(shù)學(xué)規(guī)劃方法

數(shù)學(xué)規(guī)劃將生產(chǎn)調(diào)度問題簡化為數(shù)學(xué)規(guī)劃模型，采用整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃以及決策分析等方法來解決調(diào)度最優(yōu)化或近似優(yōu)化問題，也稱為優(yōu)化調(diào)度方法。該方法一般能產(chǎn)生一個(gè)精確最優(yōu)解。Hoitomt[11]利用拉氏松弛法求解并行機(jī)調(diào)度問題，目標(biāo)是加權(quán)延遲。Torabi等人[26]建模了FJSP的批量調(diào)度模型，這是一個(gè)混合01規(guī)劃模型，并用枚舉的方法進(jìn)行求解。Angel等人[5]研究了用拉氏松弛法近似求解單機(jī)環(huán)境下雙目標(biāo)FJSP；這種方法對(duì)于小規(guī)模問題尚可求解，一旦問題規(guī)模增加則很難求解，即使能求解也需要花費(fèi)大量的計(jì)算時(shí)間。

2.3.2 啟發(fā)式方法

由復(fù)雜性分析可知，三個(gè)以上工件的FJSP就變成NP hard了。為了能在相對(duì)短的時(shí)間內(nèi)獲得近似最優(yōu)解，所以很自然地想到用啟發(fā)式算法求解。

（1）分派規(guī)則法。

采用該方法求解多目標(biāo)FJSP的研究較少，主要有：Ho和Tay[27]利用組合分派規(guī)則解決FJSP，詳細(xì)地設(shè)計(jì)了算法，并驗(yàn)證了算法的性能；AlvarezValdes等人[28] 提出了一個(gè)啟發(fā)式規(guī)則，建模玻璃生產(chǎn)企業(yè)的生產(chǎn)調(diào)度為FJSP；Dimitr等人[17]從成本的角度優(yōu)化調(diào)度，僅僅考慮了延遲成本和存儲(chǔ)成本，對(duì)生產(chǎn)成本沒有考慮，提出了一個(gè)啟發(fā)式規(guī)則，采用中心極限定理解決了調(diào)度中的競爭問題。

（2）人工智能法。

人工智能是指模擬人類智能活動(dòng)進(jìn)行優(yōu)化的方法，目前僅見到神經(jīng)網(wǎng)絡(luò)求解FJSP的少量研究。潘全科[16]采用了小腦模型對(duì)多目標(biāo)調(diào)度系統(tǒng)進(jìn)行了研究。通過小腦模型神經(jīng)網(wǎng)絡(luò)對(duì)已有的多目標(biāo)綜合評(píng)價(jià)調(diào)度案例的學(xué)習(xí)，替代評(píng)價(jià)群體進(jìn)行評(píng)價(jià)，進(jìn)而可以減少評(píng)價(jià)的工作量，更能較好地利用和積累專家的經(jīng)驗(yàn)，使評(píng)價(jià)過程具有自學(xué)習(xí)能力。

（3）鄰域搜索法。該

搜索法包括遺傳算法、禁忌搜索、模擬退火、貪婪算法等。按照求解多目標(biāo)FJSP時(shí)的步驟可以將求解方法分為兩類：

①分步法，它是將FJSP中的機(jī)器分配問題和工序調(diào)度問題分別求解，這類方法用得比較多。

Brandimarte[29]是第一個(gè)采用分步法求解多目標(biāo)FJSP的，他首先用現(xiàn)存的分派規(guī)則求解路線選擇問題，然后利用禁忌搜索求解調(diào)度問題。Cintia Rigao[12]也采用禁忌搜索分步求解FJSP，其優(yōu)化目標(biāo)是延遲目標(biāo)和設(shè)備總負(fù)荷。Kacem等人[18，30]用GA解決FJSP，并且采用兩個(gè)方法分別解決機(jī)器分配問題和工序調(diào)度問題：①局部搜索法，建立理想的資源分配模式；②分配模型控制的遺傳算法，用它求解單目標(biāo)和多目標(biāo)的FJSP。多目標(biāo)問題[7]是Makespan、總負(fù)荷和最大負(fù)荷均最小化的FJSP，求解出的是一個(gè)Pareto解集。他們還提出用模糊集概念[31]處理目標(biāo)的不可公度性，根據(jù)Pareto解的多樣性，Kacem[32]提出最壞邊界分析來估算調(diào)度方案的性能。Zribi等人[33]采用的分階段的方法也是分步法，分別建立了數(shù)學(xué)模型：首先采用定位法和禁忌搜索確定最佳分配方案；再采用GA求解工序調(diào)度問題。Tamaki等人[34]利用混合整型規(guī)劃建模FJSP，問題特征包括機(jī)器的安裝準(zhǔn)備/卸工件時(shí)間，并采用遺傳算法進(jìn)行了優(yōu)化。Cochran等人[35]提出兩階段多目標(biāo)求解方法：第一階段按照加權(quán)合并的思想將多目標(biāo)轉(zhuǎn)換為單目標(biāo)，運(yùn)行到一定時(shí)間切換到第二階段；第二階段采用多種群思想，按照目標(biāo)的個(gè)數(shù)將種群劃分為N＋1個(gè)子種群分別進(jìn)化，每一代保留各自的最優(yōu)解直接遺傳到下一代，直到停止標(biāo)準(zhǔn)滿足。這其實(shí)是多種群GA的變形。Mesghouni等人[36]研究了遺傳算法求解多目標(biāo)FJSP。Zhang[37]針對(duì)標(biāo)準(zhǔn)遺傳算法求解FJSP的低效率問題，提出了一種多階段的GA算法，并用來優(yōu)化Makespan、最大負(fù)荷和平均負(fù)荷三個(gè)指標(biāo)；結(jié)果表明在這三個(gè)指標(biāo)的優(yōu)化性能上，提出的方法比啟發(fā)式規(guī)則、標(biāo)準(zhǔn)GA和Kacem、Hammadi等人的方法都要優(yōu)越。

在遺傳算法的設(shè)計(jì)上一些學(xué)者提出了新的見解。Ho和Tay等人[27]認(rèn)為求解FJSP的GA染色體需要特殊設(shè)計(jì)，并給出兩個(gè)標(biāo)準(zhǔn)評(píng)估染色體性能：計(jì)算的時(shí)間和空間復(fù)雜性；保持解的可行性需要，提出了一種解決機(jī)器可以反復(fù)使用的FJSP的有效方法。余琦瑋[38]基于遺傳算法的柔性作業(yè)車間調(diào)度優(yōu)化，針對(duì)模型的特殊性提出了染色體兩層編碼結(jié)構(gòu)，將AOV、AOE網(wǎng)絡(luò)圖分別應(yīng)用到解碼和適應(yīng)度函數(shù)的計(jì)算中。楊曉梅[3]也類似地設(shè)計(jì)了兩層染色體，交叉變異操作分別在各層染色體內(nèi)進(jìn)行。盧冰原等人[39，40]對(duì)模糊環(huán)境下的FJSP進(jìn)行了研究，模糊加工時(shí)間用三角模糊數(shù)表示，優(yōu)化目標(biāo)是Makespan，采用遺傳算法進(jìn)行求解；實(shí)行雙染色體機(jī)制，一個(gè)染色體表示工序的機(jī)器分配，另外一個(gè)染色體表示機(jī)器上的工序加工順序。類似地，陳皓等人[41]用遺傳算法求解柔性作業(yè)車間調(diào)度問題，他設(shè)計(jì)的基因編碼主串表示調(diào)度路徑，副串表示調(diào)度次序。在主串中引入交叉算子，主/副串以不同概率發(fā)生變異算子，并隨機(jī)交換其中兩位。Chen[42]用遺傳算法求解FJSP，并用圖論模擬染色體，染色體同樣分為兩部分。趙巍等人[43]通過輪換的方法提出了一種改進(jìn)算法，將加工任務(wù)分配到不同的并行機(jī)器上去執(zhí)行，有利于機(jī)器的負(fù)載平衡。潘全科等人[44]結(jié)合實(shí)際生產(chǎn)過程，考慮到工件的加工受到機(jī)床、工人和機(jī)器人等資源的制約，并且可以有多種可行的工藝路線。

夏蔚軍等人[15，45]研究了基于微粒群優(yōu)化和模擬退火集成的方法解決多目標(biāo)FJSP。多目標(biāo)的處理方法是采用加權(quán)和的方法將多目標(biāo)問題轉(zhuǎn)換為單目標(biāo)問題。求解思路是分別求兩個(gè)子問題，即微粒群優(yōu)化求解機(jī)器分配問題和模擬退火求解排序問題。

②集成法，它是同時(shí)解決FSJP的兩個(gè)子問題。

孫志峻等人[23]用遺傳算法研究了具有柔性加工路徑的作業(yè)車間的智能優(yōu)化調(diào)度問題，提出一種將遺傳算法和分派規(guī)則相結(jié)合的調(diào)度算法，將加工計(jì)劃與生產(chǎn)調(diào)度同時(shí)考慮，避免了加工計(jì)劃和生產(chǎn)調(diào)度相脫節(jié)的弊端；他們[46]還針對(duì)FJSP的批量加工問題進(jìn)行了探討。趙偉等人[47]研究了Job Shop類型柔性制造系統(tǒng)的調(diào)度問題，其中每個(gè)工件都有多個(gè)可替代的工藝計(jì)劃，并且每個(gè)操作均可在多個(gè)機(jī)器上選擇加工，建立了多目標(biāo)混合整數(shù)規(guī)劃模型，利用遺傳算法進(jìn)行求解。

DauzèrePérès等人[48]定義了鄰域結(jié)構(gòu)方法，不區(qū)分分配問題和調(diào)度問題，并且基于該鄰域結(jié)構(gòu)提出了禁忌搜索過程求解FJSP。Baykasoglu[49]是第一個(gè)采用語法的方法建模FJSP的人，他用資源元來定義機(jī)器能力，優(yōu)化的目標(biāo)是單目標(biāo)；考慮到定義資源元的難度和多目標(biāo)優(yōu)化的需求，還提出了基于語法的多目標(biāo)FJSP的調(diào)度模型[50]，并詳細(xì)討論了模型的求解方法，采用多目標(biāo)禁忌搜索方法。

Mati等人[51]提出了用貪婪式啟發(fā)式規(guī)則同時(shí)解決FJSP的分配和工序調(diào)度兩個(gè)子問題。

利用蟻群算法求解FJSP的研究以Vincent T’kindt等人[52，53]為主，他們提出一種交互式求解雙目標(biāo)調(diào)度問題的方法：由優(yōu)化方法求出一組Pareto解，然后決策者根據(jù)自己的偏好信息選擇出最滿意的Pareto解。關(guān)于此方面的所有優(yōu)秀研究成果可參見文獻(xiàn)[54]。

Loukil等人[55]利用模擬退火求解多目標(biāo)生產(chǎn)調(diào)度問題。Maqrini等人[56]提出了化工行業(yè)的FJSP的描述，并用模擬退火算法求解。

2.4 調(diào)度原型系統(tǒng)研究現(xiàn)狀

對(duì)調(diào)度原型系統(tǒng)的研究較少，文獻(xiàn)中僅見到Khoo[57]的研究，他提出了一個(gè)原型系統(tǒng)——擴(kuò)展遺傳算法的制造系統(tǒng)多目標(biāo)調(diào)度器。原型系統(tǒng)總體框架的輸入是數(shù)據(jù)庫文件，輸出是一個(gè)可行的近似或最優(yōu)調(diào)度方案，中央處理部分為一個(gè)調(diào)度工具箱。工具箱集成了各種類型的調(diào)度問題，如Job Shop、Flow Shop和制造單元等，但是沒有考慮FJSP。

2.5 面向工件的多目標(biāo)FJSP研究現(xiàn)狀

上述討論的多目標(biāo)FJSP中，均默認(rèn)了各個(gè)工件的性能指標(biāo)集是相同的，稱做I類多目標(biāo)FJSP。但是實(shí)際情況中，因?yàn)楝F(xiàn)代企業(yè)的生產(chǎn)能力大大提高，車間調(diào)度員一次需要安排并投產(chǎn)一大批各種類型的訂單，常常會(huì)碰到工件性能指標(biāo)集不同的情況，此時(shí)必須兼顧各個(gè)工件本身的性能指標(biāo)要求。該類問題稱為面向工件的多目標(biāo)FJSP調(diào)度問題或II類多目標(biāo)FJSP，定義如下：

在M個(gè)機(jī)器上加工N個(gè)工件，每個(gè)工件J_j由n_j個(gè)工序組成，n_j個(gè)工序之間有工藝的先后約束，工件的每道工序可由M臺(tái)機(jī)器中的多臺(tái)機(jī)器加工。用M_ij表示第j個(gè)工件的第i道工序可用機(jī)器集合M_ij{1，2，…，M}；O_ijk表示第j個(gè)工件的第i道工序可用機(jī)器k；p_ijk表示第j個(gè)工件的第i道工序在第k個(gè)機(jī)器上加工需要的時(shí)間，即1≤j≤N，1≤i≤nj，1≤k≤M。每個(gè)工件J_j的性能指標(biāo)集為A_j，如果對(duì)任意的1≤i≤N，1≤j≤N，都有A_i＝A_j時(shí)，所有工件的性能指標(biāo)集相同，則該問題轉(zhuǎn)換為通常的多目標(biāo)FJSP。可見本文討論的問題是更加通用意義上的多目標(biāo)FJSP，常說的多目標(biāo)調(diào)度問題只是其中的一個(gè)子集。調(diào)度的任務(wù)是在M臺(tái)機(jī)器上安排N個(gè)工件的加工任務(wù)，同時(shí)最優(yōu)化各個(gè)工件預(yù)定的性能指標(biāo)集，并滿足一些必要的約束條件。由定義可以看出，II類問題比I類問題更加接近實(shí)際，進(jìn)一步縮小了理論與實(shí)踐之間的“代溝”。

遺憾的是這方面的研究非常少，主要是日本大阪大學(xué)的學(xué)者M(jìn)urata教授[58～60]所做的一系列工作。他的核心思想是將該類確定的FJSP轉(zhuǎn)換為模糊交貨期調(diào)度問題；他還進(jìn)一步提出了不同工件重要性的影響[61]，進(jìn)而提出基于規(guī)則的權(quán)重定義方法，得出的結(jié)論是遺傳算法比模擬退火算法更能有效地求解該類多目標(biāo)調(diào)度問題，研究著重在多工件單目標(biāo)情況上。Li[62]發(fā)展了Murata的理論，他研究了FJSP領(lǐng)域的多工件多目標(biāo)的情況，建模了這類多目標(biāo)模糊FJSP，采用滿意度作為多個(gè)目標(biāo)的折中，進(jìn)而作為優(yōu)化目標(biāo)。

3 存在的問題與不足

（1）調(diào)度的優(yōu)化準(zhǔn)則中，基于性能的指標(biāo)研究較多，基于代價(jià)指標(biāo)的研究很少，少量文獻(xiàn)僅涉及到懲罰成本與成品存儲(chǔ)成本問題，很少提及到生產(chǎn)成本和在制品存儲(chǔ)成本的問題。然而這類指標(biāo)對(duì)企業(yè)的管理決策又是至關(guān)重要的。

（2）FJSP模型的研究很少，文獻(xiàn)中僅見到數(shù)學(xué)規(guī)劃模型和基于語法的模型。關(guān)于多目標(biāo)FJSP框架性的研究幾乎沒有。

（3）對(duì)于多目標(biāo)優(yōu)化方法的理論分析沒有系統(tǒng)研究，如何保證優(yōu)化方法的收斂性和Pareto解的多樣性是多目標(biāo)優(yōu)化方法亟待解決的問題。

（4）柔性作業(yè)車間多目標(biāo)調(diào)度問題的討論僅僅局限在所有工件的目標(biāo)均相同情況下的多目標(biāo)調(diào)度問題中，關(guān)于各種工件目標(biāo)不同的多目標(biāo)調(diào)度問題的研究很不成熟，而進(jìn)一步考慮在工件生產(chǎn)批量也不等的情況下的研究更是無人提及。

（5）動(dòng)態(tài)調(diào)度問題雖然研究得很多，但都是僅限于單一目標(biāo)的優(yōu)化，優(yōu)化目標(biāo)隨時(shí)間而變的動(dòng)態(tài)多目標(biāo)調(diào)度問題的研究尚未見到。

（6）多目標(biāo)FJSP原型系統(tǒng)的研究太少，有很多問題值得進(jìn)一步探討，而且與企業(yè)其他控制系統(tǒng)和信息系統(tǒng)存在“信息鴻溝”。

4 發(fā)展趨勢

相對(duì)經(jīng)典Job Shop的豐富研究，F(xiàn)JSP的研究還處于初級(jí)階段，多目標(biāo)下的FJSP研究更是如此，有許多值得探索的地方。

（1）建立包括生產(chǎn)成本在內(nèi)的多目標(biāo)FJSP模型，充分考慮企業(yè)對(duì)成本的關(guān)注，使得調(diào)度模型更好地反映現(xiàn)實(shí)情況。指標(biāo)體系應(yīng)包括基于性能和基于代價(jià)的兩類指標(biāo)。

（2）經(jīng)典Job Shop的研究已經(jīng)取得了豐富的成果，將這些優(yōu)秀的理論成果應(yīng)用到FJSP是一個(gè)重要的發(fā)展方向。尤其是研究數(shù)學(xué)邏輯嚴(yán)密的模型表示方法、規(guī)范和描述生產(chǎn)調(diào)度框架是當(dāng)務(wù)之急。

（3）工件目標(biāo)差異的多目標(biāo)FJSP也是一個(gè)重要內(nèi)容。

（4）多目標(biāo)問題的一個(gè)最大問題是針對(duì)同一個(gè)問題，采用不同方法得到的解往往不同[63]。如何評(píng)價(jià)衡量得到的解的質(zhì)量是一個(gè)迫在眉睫的研究方向。

（5）過去的研究大多數(shù)是基于禁忌搜索和遺傳算法的。探求其他智能方法如神經(jīng)網(wǎng)絡(luò)方法、Agent技術(shù)等，求解多目標(biāo)FJSP是一個(gè)重要的研究方向。多種方法的混合使用能大大避免單純使用一種方法的不足與缺陷，是一個(gè)值得關(guān)注的方向。盡管文獻(xiàn)中采用GA的方法占多數(shù)，但是截至目前為止，采用GA求解高維、多約束、多目標(biāo)的優(yōu)化問題仍是一個(gè)沒有較好解決的問題，其進(jìn)展必將推動(dòng)GA在許多工程領(lǐng)域的應(yīng)用。

（6）開發(fā)實(shí)用的多目標(biāo)FJSP原型系統(tǒng)，尤其是探討ERP環(huán)境下生產(chǎn)調(diào)度系統(tǒng)與企業(yè)其他信息系統(tǒng)之間的信息交流問題，從而真正實(shí)現(xiàn)將調(diào)度理論應(yīng)用到生產(chǎn)實(shí)踐中。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。