自動化制造單元調(diào)度算法綜述

摘 要:作為未來先進制造系統(tǒng)的重要發(fā)展方向，自動化制造單元(robotic cells)在半導體和印刷電路板制造、化學電鍍、鋼鐵冶煉和機械制造等行業(yè)獲得了日趨廣泛的應用。為全面總結(jié)自動化制造單元調(diào)度算法的研究現(xiàn)狀，對自動化制造單元進行分類，在此基礎上綜述了國內(nèi)外自動化制造單元調(diào)度方法取得的進展及存在的問題，并指明了其進一步的研究方向。

關(guān)鍵詞:自動化制造單元; 調(diào)度; 物料運送機器人; 算法

中圖分類號:O211.1;TP278文獻標志碼:A

文章編號:1001-3695(2010)06-2001-05

doi:10.3969/j.issn.1001-3695.2010.06.001

Survey on scheduling algorithms for robotic cells

ZHOU Zhen， CHE A-da

(School of Management， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:As a significant development direction for future advanced manufacturing systems， robotic cells have more and more broad applications in the areas of printed circuit boards manufacturing， chemical electroplating， steel smelting， mechanical manufacture， and so on. For a detailed survey on robotic cells scheduling algorithms， this paper firstly classified robotic cells. Based on the classification， presented an overview of recent developments in scheduling algorithms for robotic cells at abroad and home and their disadvantages. Finally， gave the possible directions for future research.

Key words:robotic cells; scheduling; material handling robot; algorithms

0 引言

現(xiàn)代化的先進制造系統(tǒng)往往應用計算機控制的物料運送機器人來執(zhí)行制造系統(tǒng)中工作站之間的工件運送作業(yè)，如集束型半導體制造系統(tǒng)(cluster tool)[1，2]、印刷電路板自動化電鍍生產(chǎn)線[3，4]、鋼鐵冶煉生產(chǎn)線[5，6]、柔性制造單元[7，8]等。具有物料運送機器人的自動化制造系統(tǒng)通常被通稱為自動化制造單元(robotic cells)。自動化制造單元的調(diào)度比經(jīng)典的流水車間(flow-shop)和單件車間(job-shop)調(diào)度問題要復雜得多，因為此類系統(tǒng)的調(diào)度不僅要合理安排工件的加工作業(yè)，而且更要有效地規(guī)劃機器人的物料運送作業(yè)。隨著制造業(yè)競爭的日益加劇，作為先進制造中生產(chǎn)組織與過程優(yōu)化的一個重要方面，生產(chǎn)調(diào)度問題受到日益廣泛的重視，調(diào)度決策水平已經(jīng)成為現(xiàn)代制造企業(yè)經(jīng)營過程能否穩(wěn)定、高效運轉(zhuǎn)的決定性因素之一。

先進制造模式在制造系統(tǒng)中的不斷應用迫切需要人們不斷完善現(xiàn)代生產(chǎn)調(diào)度理論與方法，以不斷適應制造系統(tǒng)運作模式的更新。國內(nèi)外研究者對經(jīng)典的生產(chǎn)調(diào)度問題(如flow-shop和job-shop調(diào)度問題)進行了廣泛和深入的研究[9，10]。但是，對作為未來制造系統(tǒng)主要發(fā)展方向的自動化制造單元的調(diào)度研究還沒有引起足夠的重視。在半導體和印刷電路板等相關(guān)產(chǎn)業(yè)廣闊應用前景的推動下，自動化制造單元的優(yōu)化和調(diào)度開始成為近年來國際自動化和管理科學領(lǐng)域的研究熱點。

1 自動化制造單元調(diào)度問題描述和分類

1.1 問題描述

自動化制造單元通常由一系列完成特定加工工序的工作站和用于自動化物料運送的機器人組成，如圖1所示。所有工件在加工開始前都已經(jīng)到達裝載站，并且等待機器人將其搬入制造單元進行加工。工件在工作站上完成一個工序的加工后，由計算機控制的機器人卸載并搬運至下一個工序所對應的工作站上進行加工。一個工件不能同時在兩臺或多臺工作站上加工，一臺工作站也不能同時加工兩個或多個工件。當所有加工工序完成后，工件從卸載站離開系統(tǒng)。系統(tǒng)中存在一個或多個機器人用于執(zhí)行搬運作業(yè)。對于自動化制造單元而言，機器人物料運送作業(yè)的執(zhí)行順序直接影響著系統(tǒng)生產(chǎn)效率的高低。

自動化制造單元的調(diào)度問題可歸結(jié)為:并行優(yōu)化和調(diào)度制造單元中工作站和物料運送機器人，即優(yōu)化工件加工順序和機器人的運送作業(yè)，以在保證產(chǎn)品質(zhì)量的前提下使系統(tǒng)生產(chǎn)率最大。

1.2 自動化制造單元分類

目前國內(nèi)外對自動化制造單元調(diào)度的研究分布于不同的應用領(lǐng)域中，在經(jīng)典的英文文獻中也就有不同的叫法，如集束型半導體制造系統(tǒng)調(diào)度在英文中被稱做cluster tool scheduling[1，2]、印刷電路板自動化電鍍生產(chǎn)線調(diào)度被稱做hoist scheduling[3，4]、制造單元調(diào)度被稱做robotic cells scheduling[7，8]等。本文從工件在工作站上的等待時間、制造單元物理結(jié)構(gòu)和加工工件類型三個角度，對自動化制造單元進行分類歸納。

1.2.1 無限等待、有限等待與無等待自動化制造單元

無限等待、有限等待和無等待這三類制造單元的不同之處在于工件在工作站上完成加工后能否繼續(xù)在工作站上等待，直到物料運送機器人空閑時來搬運。在無限等待自動化制造單元中，如機械制造系統(tǒng)，工件在某個工作站上的等待時間為無限長，即工件在該工作站上完成加工后必要時可以一直停留在工作站上，直到機器人空閑時來搬運;在有限等待自動化制造單元中，如集束型半導體制造系統(tǒng)，工件(如晶圓[11])在工作站(處理腔體，chamber)上完成如化學氣相沉積(chemical vapor deposition，CVD)、物理氣相沉積(phisical vapor deposition，PVD)、平坦化、光阻曝光處理等[1，2]化學物理處理后必須在給定的時間內(nèi)被機器人搬走，以防止廢品產(chǎn)生;在無等待自動化制造單元中，如高精度印刷電路板電鍍生產(chǎn)線和鋼鐵冶煉生產(chǎn)線，對工件的加工時間有著精確的要求，工件在工作站(化學處理槽或冶煉爐)上完成處理后必須立刻被機器人從工作站上搬走，否則有可能會產(chǎn)生廢品。

1.2.2 簡單與復雜自動化制造單元

在傳統(tǒng)的自動化制造單元中，各處理工序和處理工作站之間存在著一對一的關(guān)系(即每一個處理工序?qū)┮灰粋€工作站，反之亦然)，工件按工藝路線中確定的順序串行地訪問各工序?qū)墓ぷ髡竞箅x開制造單元。在半導體和印刷電路板制造等相關(guān)行業(yè)的迅猛發(fā)展下，自動化制造單元日益向復雜化發(fā)展，主要體現(xiàn)在制造單元物理結(jié)構(gòu)的復雜化，即自動化制造單元中可重入工作站和并行工作站的出現(xiàn)。

a)可重入(re-entrant)工作站。被工件重復訪問的工作站，也即被多個處理工序共享的工作站。

b)并行(parallel)工作站。在加工時間特別長的瓶頸處理工序上所設置的多個同時加工工件的工作站，以有效平衡各工序之間的載荷。

由于可重入工作站和并行工作站的出現(xiàn)，自動化制造單元中工件的流動方向呈現(xiàn)多重入和串并行的特點。本文從制造單元物理結(jié)構(gòu)的角度，將具有可重入工作站和并行工作站的自動化制造單元稱為復雜自動化制造單元;將傳統(tǒng)的自動化制造單元稱為簡單自動化制造單元。由于需要有效地協(xié)調(diào)可重入工作站和并行工作站上的工件加工作業(yè)以避免工作站上工件加工沖突，復雜自動化制造單元的調(diào)度比簡單制造單元調(diào)度要復雜得多。

1.2.3 單流與混流自動化制造單元

自動化制造單元日益向復雜化發(fā)展的另一個主要體現(xiàn)是加工產(chǎn)品種類的多樣化。隨著用戶對產(chǎn)品的個性化要求越來越高，多品種小批量生產(chǎn)成為企業(yè)的主要制造模式。混流生產(chǎn)是近幾十年來為了適應多品種生產(chǎn)的需要而發(fā)展起來的一種新的生產(chǎn)組織方式。所謂混流自動化制造單元是指在一定時間內(nèi)，在同一生產(chǎn)系統(tǒng)中混合連續(xù)地生產(chǎn)多種類型產(chǎn)品的自動化制造單元。相應地，只生產(chǎn)一種類型產(chǎn)品的制造單元被稱為單流自動化制造單元。混流自動化制造單元的調(diào)度比單流制造單元調(diào)度要復雜得多，因為它的調(diào)度不僅要合理規(guī)劃各種不同類型工件的加工順序，更要有效地規(guī)劃機器人的物料運送作業(yè)。

2 自動化制造單元調(diào)度算法研究進展

絕大多數(shù)自動化制造單元調(diào)度問題為NP難題(NP-hard)，如Lei等人[12]證明了即使只有一個機器人的有限等待簡單自動化制造單元調(diào)度問題為強NP難題，也就是說問題解的個數(shù)隨問題規(guī)模呈指數(shù)增長;Brauner等人[13]則證明了具有任意工作站布置的無限等待簡單自動化制造單元調(diào)度問題為強NP難題。

大量文獻分析表明，自動化制造單元調(diào)度問題的研究方法可分為兩大類，即精確算法和啟發(fā)式近優(yōu)方法。自動化制造單元調(diào)度問題的研究最初主要集中在精確算法上(如分支定界法、動態(tài)規(guī)劃、混合整數(shù)規(guī)劃等數(shù)學規(guī)劃方法)，解決了一系列有代表意義的調(diào)度問題，但精確算法難以解決大規(guī)模的復雜調(diào)度問題。隨著相關(guān)學科與優(yōu)化技術(shù)的發(fā)展，自動化制造單元調(diào)度領(lǐng)域涌現(xiàn)了許多新的啟發(fā)式優(yōu)化方法，如基于人工智能和計算智能的調(diào)度方法。以下對自動化制造單元的各類研究方法進行系統(tǒng)綜述。

2.1 多項式算法

多項式算法(polynomial algorithm)主要應用于無等待以及具有特殊工作站布置的某些無限等待自動化制造單元調(diào)度問題上。

由于無等待制造單元中工件在工作站上完成加工后必須立刻由物料運送機器人搬運到下一個工作站，其調(diào)度問題在無限等待、有限等待和無等待這三類制造單元調(diào)度問題中具有最嚴格的約束，這類問題常常存在多項式快速算法。文獻中多項式算法求解無等待自動化制造單元調(diào)度問題往往先應用禁止區(qū)間法(prohibited intervals)建立問題的數(shù)學模型，通過數(shù)學分析區(qū)間分析相結(jié)合的方法分析該模型，在此基礎上證明問題的最優(yōu)解必定在有限個特殊點上，從而將高維問題縮減為低維問題，再設計一個特定的可行解檢查算法來判斷每個特殊點(即縮減的低維問題)的可行性，最后對整個算法的調(diào)度復雜性作出分析。遵循以上解決思路和研究方法，研究者們在多項式算法上取得了以下成果。

在簡單制造單元調(diào)度研究上，Levner等人[14]在理論上證明了單機器人無等待制造單元調(diào)度問題不是NP難題，為多項式可解;Karzanov等人[15]研究了多機器人無等待制造單元調(diào)度問題。上述兩項研究都是假設系統(tǒng)中每個機器人在各自獨立的并行軌道上運行的，沒有考慮單一軌道上多機器人運行時可能存在的碰撞問題。Kats等人[16]提出的用于解決多機器人調(diào)度問題的多項式算法，能在給定的周期調(diào)度下最小化機器人數(shù)，而Leung等人[17]在此基礎上提出的多項式算法不僅能最小化任意周期時間長的機器人數(shù)，而且還能在給定的機器人數(shù)下優(yōu)化生產(chǎn)系統(tǒng)。Liu等人[18]、Che等人[19]則分別為單一軌道上單向運行的雙機器人、多機器人調(diào)度問題提出了相應的有效的多項式算法，車阿大等人[20]進一步擴展了文獻[19]，解決了單一軌道上雙向運行的多機器人調(diào)度問題。

在復雜制造單元調(diào)度研究上，Kats等人[21]為只存在可重入工作站的調(diào)度問題提出了多項式算法，該算法不適用于有并行工作站存在的調(diào)度問題，Che等人[22]證明了同時存在并行工作站和可重入工作站的調(diào)度問題為多項式可解，同時他們在文獻[23]中最終提出了解決復雜制造單元調(diào)度問題的多項式算法。

將多項式算法用于混流自動化制造單元調(diào)度問題的研究略少于前兩者，主要有:Che等人[24]首次證明2度無等待制造單元調(diào)度問題為多項式可解，并指出該多項式算法可擴展至解決2度無等待混流制造單元調(diào)度問題。Agnetis[5]為分別加工多個相同工件或不同工件的具有兩個或三個工作站的混流制造單元開發(fā)了多項式調(diào)度算法，但當加工多個相同工件時，由于該調(diào)度初始工件的特性不同于穩(wěn)態(tài)時的情況，這種算法在一個單位周期內(nèi)對四個及四個以上工作站的情況不適用。Agnetis等人[25]研究了只有三個工作站的混流制造單元調(diào)度問題，應用了一種多項式算法解決了多種不同類型工件調(diào)度問題，但該算法不能解決任意工作站個數(shù)的調(diào)度問題。

另一方面，任意工作站間距離為常量的無限等待制造單元通常也是多項式可解，即可根據(jù)這類調(diào)度問題的特性導出最優(yōu)解的下界(lower bound)。在一般性的假設前提下，可證明出調(diào)度問題的某個特殊可行解的最優(yōu)值等于所導出的最優(yōu)解的下界。主要工作包括:Dawande等人[26]用多項式算法解決此類簡單制造單元生產(chǎn)率最大化問題;Geismar等人[27]則為存在并行工作站的單機器人調(diào)度問題提出了一種多項式算法;進一步地，Geismar等人[28]又將該算法擴展至多機器人調(diào)度問題，并以三個機器人的制造單元為例，通過仿真模擬驗證了該算法優(yōu)于當時FSI International Inc所使用的一種基于啟發(fā)式近優(yōu)算法的調(diào)度方案。

2.2 混合整數(shù)規(guī)劃方法

混合整數(shù)規(guī)劃方法(mixed integer programming)主要應用于為NP難題的有限等待簡單自動化制造單元調(diào)度問題上。應用混合整數(shù)規(guī)劃方法研究自動化制造單元調(diào)度問題的基本思路是首先分析所要研究的調(diào)度問題特征，在此基礎上建立問題的混合整數(shù)規(guī)劃模型，再應用商品化優(yōu)化軟件來求解。Phillips等人[29]最早為有限等待制造單元調(diào)度問題提出了第一個混合整數(shù)規(guī)劃模型，并提供了迄今為止這一研究領(lǐng)域最為權(quán)威的基準研究案例。針對他們所提出的混合整數(shù)規(guī)劃模型不能求解有可重入工作站的制造單元調(diào)度問題的缺陷和不足，周支立等人[30]加人適當?shù)乃沙谧兞考捌浼s束方程，提出了一種改進的混合整數(shù)規(guī)劃模型，但是他們的模型均沒有考慮同時存在并行工作站和可重入工作站的復雜情況。而Liu等人[31]則為存在并行工作站和可重入工作站的復雜制造單元調(diào)度問題提出了綜合的混合整數(shù)規(guī)劃方法。另外，Leung等人[3，32]分別對多機器人無等待、有限等待制造單元調(diào)度問題提出了混合整數(shù)規(guī)劃模型。

2.3 分支定界算法

分支定界算法(branch-and-bound algorithm)大多用于有限等待自動化制造單元調(diào)度問題上。在有限等待自動化制造單元中，工件在工作站上完成加工后，必須在預先給定的時間內(nèi)從工作站上搬走。因此從數(shù)學模型的角度看，這類調(diào)度問題具有緊約束，通常能夠建立起能充分表示其變量之間的內(nèi)在關(guān)系以及調(diào)度問題機理的分析性數(shù)學模型，適合應用分支定界算法。文獻中應用分支定界算法解決自動化制造單元調(diào)度問題的基本思路是:首先建立所研究問題的數(shù)學模型，然后在對建立的模型進行有效分析的基礎上，研究和開發(fā)最優(yōu)解的一些解析性質(zhì)，再根據(jù)這些解析性質(zhì)和問題的具體結(jié)構(gòu)設計有效的分支定界算法來求解問題。

Shapiro等人[33]首次把基于枚舉的算法用于有限等待簡單制造單元調(diào)度問題的研究上;之后，在同一問題研究上，Lei等人[34]用一組簡單代數(shù)不等式求出問題的可行解，再用一種基于分支定界的枚舉算法從中找出最優(yōu)解。Chen等人[35]提出一種明確的分支定界算法，用基于圖論的方法求解模型中線性規(guī)劃問題，大大減低了計算機CPU對該問題的處理時間。Che等人[36，37]進一步擴展了文獻[35]的研究成果，解決了多機器人和復雜制造單元調(diào)度問題。Lei等人[38]用一種分支定界算法搜尋到加工兩種類型工件的有限等待混流制造單元調(diào)度問題的最優(yōu)解，并證明了該混流制造單元比單流制造單元應具有更高的生產(chǎn)效率。此外，有關(guān)混流制造單元調(diào)度問題的研究還可見Mateo等人[39]在加泰羅尼亞科技大學(Universitat Politècnica de Catalunya)的一份科技報告上。最近，Che等人[40]用分支定界算法解決了無等待混流制造單元調(diào)度問題。特別值得注意的是，上述分支定界算法均通過各種不同的方式直接或間接枚舉機器人搬運作業(yè)順序以及工件投放順序。

2.4 啟發(fā)式算法

基于數(shù)學規(guī)劃的精確算法盡管能保證獲得最優(yōu)解，但其計算時間隨問題規(guī)模的增加以指數(shù)速度增加，一般只能解決較小規(guī)模的自動化制造單元調(diào)度問題。對大規(guī)模調(diào)度問題而言，啟發(fā)式算法(heuristic algorithms)是一個很好的解決方法。Lei等人[41]、周支立等人[42~44]分別為各種類型的有限等待制造單元調(diào)度問題提出了特定的啟發(fā)式算法。Gultekin等人[45]為無限等待簡單制造單元調(diào)度問題提出了一種實用的啟發(fā)式算法。 Sriskandarajah等人[46]則研究了無限等待混流制造單元調(diào)度問題，提出了解決兩個工作站調(diào)度問題的啟發(fā)式算法，并將其擴展至m個工作站的情況。Henrik等人[47]提出了一種啟發(fā)式算法解決了有限等待混流制造單元調(diào)度問題。

調(diào)度規(guī)則作為一種最常見的啟發(fā)式方法，由于簡單、易于實現(xiàn)和計算復雜度低，常被用于自動化制造單元動態(tài)調(diào)度問題中。自動化制造單元的調(diào)度規(guī)則包括工件調(diào)度規(guī)則和機器人調(diào)度規(guī)則兩類。工件調(diào)度規(guī)則主要是決定工件的投放時間(即工件進入制造單元開始加工時間)，而機器人調(diào)度規(guī)則主要是有效地分配工件搬運作業(yè)以及確定其執(zhí)行順序。

研究者們根據(jù)自動化制造單元具體的特點，開發(fā)了各種工件調(diào)度規(guī)則。Song等人[48]開發(fā)了一種稱為最早進入時間(earliest start time，EST)的工件調(diào)度規(guī)則，其基本思想是按照先到先服務的原則來盡可能早地將工件投放到制造單元中。Chauvet等人[49]改進了該規(guī)則，提出了正反向最早進入時間算法(forward-backward earliest start time，F(xiàn)BEST)。Yih等人[50]則提出了一種結(jié)合最早進入時間和工件加工時間窗口的工件調(diào)度啟發(fā)式規(guī)則。Thesen等人[51]提出的工件調(diào)度啟發(fā)式規(guī)則要求新工件的進入不會破壞所有工件在制造單元中各個工作站上的加工時間窗口。Sun等人[52]進一步簡化了該規(guī)則，他們的算法要求新工件的進入不會破壞工件在制造單元中第一個工作站上的加工時間窗口。Mak等人[53]則進一步擴展了上述研究，開發(fā)了一種新的工件調(diào)度啟發(fā)式規(guī)則，該規(guī)則保證新工件的進入不會破壞前一個工件在各個工作站上的加工時間窗口。

在機器人調(diào)度規(guī)則上，Thesen等人[51]提出了四種機器人動態(tài)調(diào)度規(guī)則，分別為nearest robot first(NRF)、average tank assignment(ATA)、average robot assignment(ARA)和boundary shift by job location(BSJL)。這四種規(guī)則除NRF外，其余三種規(guī)則均限制機器人只能在其固定的活動范圍內(nèi)執(zhí)行搬運作業(yè)。Sun等人[52]則開發(fā)了一個仿真平臺，對NRF、ARA、BSJL三種規(guī)則的性能進行了仿真。Mak等人[53]為了進一步提高機器人的使用效率，對ATA、ARA和BSJL三種調(diào)度規(guī)則進行了改進，增設了相鄰機器人的重疊合作區(qū)域(overlapping zone)，提出了modified ATA(MATA)、modified ARA(MARA)和modified BSJL(MBSJL)三種機器人調(diào)度規(guī)則。

2.5 元啟發(fā)式算法

元啟發(fā)式算法(meta-heuristic algorithms)包括遺傳算法(genetic algorithm)、模擬退火算法(simulation annealing algorithm)、禁忌搜索算法(tabu search algorithm)、粒子群算法(particle swarm optimization)、蟻群算法(ant colony algorithm)等。近十年來，這些方法被逐漸引入到自動化制造單元調(diào)度問題研究中，并取得了一定的研究進展。

2.5.1 遺傳算法

遺傳算法的設計包括染色體編碼、適應值函數(shù)計算、初始種群的生成、遺傳算子的設計等，其中編碼方法是遺傳算法設計的關(guān)鍵。從已有文獻看出，將遺傳算法應用于自動化制造單元調(diào)度問題中主要有兩種編碼方法，即基于工件加工時間的編碼方法和基于機器人搬運順序的編碼方法。例如，Lim[54]、Soukhal等人[55]分別采用基于機器人搬運順序編碼方法的遺傳算法來求解有限等待、無等待制造單元調(diào)度問題;李鵬等人[56]則采用基于工件加工時間編碼方法的遺傳算法來求解有限等待制造單元調(diào)度問題，并利用混沌初始化技術(shù)來生成高效的初始種群，提高了遺傳算法的收斂速度和優(yōu)化質(zhì)量，但對于大規(guī)模調(diào)度問題，可能會出現(xiàn)解搜索時間較長的情況。

2.5.2 模擬退火算法

楊廣文等人[57]提出了一種求解多機器人制造單元調(diào)度問題的模擬退火算法。他們用大量隨機模擬的算例驗證了該算法的有效性，并指出該算法在理論上能得到最優(yōu)解。但在實際中，由于有限計算量條件下最優(yōu)解的獲得和收斂速度對收斂條件和退火時間有很強的依賴性，若要得到大規(guī)模的多機器人調(diào)度問題的最優(yōu)解或滿意解，如何控制退火過程至關(guān)重要。

2.5.3 禁忌搜索算法

趙振宏等人[58]為無限等待混流制造單元調(diào)度問題提出了一種基于極大代數(shù)的建模方法，開發(fā)了基于禁忌搜索的啟發(fā)式調(diào)度算法。該算法可以同時對工件的加工順序和機器人物料輸送順序進行優(yōu)化，能夠解決較大規(guī)模的調(diào)度問題，適用于更為復雜的制造單元系統(tǒng)，但通過禁忌搜索過程所得的解是近優(yōu)解，與最優(yōu)解尚有一定的偏差。周支立等人[59]則為雙機器人有限等待制造單元調(diào)度問題提出了一種基于線性規(guī)劃模型和禁忌表的搜索算法。該算法的核心是用線性規(guī)劃模型來求給定機器人分配和運送順序下的最優(yōu)解，應用禁忌表來避免相同線性規(guī)劃問題的求解，量化示例表明了該算法的高效性。

2.5.4 粒子群算法

粒子群算法已被廣泛應用于非線性連續(xù)優(yōu)化、組合優(yōu)化問題的求解中，但將粒子群算法應用于自動化制造單元調(diào)度問題的文獻較少。Kamalabadi等人[60]為有三個工作站的混流制造單元調(diào)度問題建立了S6策略假設下基于Petri網(wǎng)的數(shù)學模型，并提出了一種粒子群算法解決了該問題。但是該算法假設了連續(xù)兩個工作站之間搬運時間和工件裝卸載時間均為一個時間單位，并且只適用于有三個工作站的制造單元調(diào)度問題。

3 結(jié)束語

雖然自動化制造單元調(diào)度問題的研究已取得了一定的研究成果，但由于在這一領(lǐng)域的大部分問題都具有NP難特性，至今尚未有非常高效的解決方法和理論。通過對自動化制造單元調(diào)度方法的綜述，可以總結(jié)出自動化制造單元調(diào)度理論和方法的幾個未來研究方向:

a)文獻中研究的大部分自動化制造單元調(diào)度問題都是對于實際生產(chǎn)環(huán)境中復雜的、動態(tài)隨機的調(diào)度問題的一種抽象和簡化，因此大多數(shù)文獻研究的都是較簡單的調(diào)度問題，對于更符合實際應用的自動化制造單元調(diào)度問題的研究尚未見報道，如復雜混流制造單元的調(diào)度問題。毫無疑問，這些方面的研究將成為未來方向之一。

b)與精確算法相比，元啟發(fā)式算法盡管相對簡單、靈活，計算效率高，但不一定能保證所得解的可行性和全局最優(yōu)性，甚至在多數(shù)情況下，無法分析所得解同最優(yōu)解的近似程度。因此為了克服各種元啟發(fā)式算法的缺點和發(fā)揮其各自的優(yōu)勢，將兩種或兩種以上啟發(fā)式算法結(jié)合起來形成更加高效的混合智能啟發(fā)算法，將是自動化制造單元調(diào)度算法研究的重要方向之一。

c)目前大多數(shù)文獻研究的都是靜態(tài)調(diào)度問題。由于靜態(tài)調(diào)度無法隨著制造環(huán)境的變化動態(tài)地對調(diào)度方案進行調(diào)度，大部分有關(guān)靜態(tài)調(diào)度問題的研究成果很難應用于動態(tài)環(huán)境下的自動化制造單元調(diào)度中。相對于靜態(tài)調(diào)度而言，動態(tài)調(diào)度更加符合自動化制造單元的實際生產(chǎn)環(huán)境。尋找有效的動態(tài)調(diào)度算法以解決自動化制造單元動態(tài)調(diào)度的不確定性、動態(tài)性、復雜性難題是今后的研究方向。

參考文獻:

[1]KIM J H， LEE T E. Schedulability analysis of time-constrained cluster tools with bounded time variation by an extended Petri net [J]. IEEE Trans on Automation Science and Engineering，2008，5(3):490-503.

[2]WU Nai-qi， CHU Cheng-bin， CHU Feng， et al. A Petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints [J]. IEEE Trans on Semiconductor Manufacturing，2008，21(2):224-237.

[3]LEUNG J，ZHANG Guo-qing. Optimal cyclic scheduling for printed-circuit-board production lines with multiple hoists and general proces-sing sequences [J]. IEEE Trans on Robotics and Automation，2003，19(3):480-484.

[4]CHE A-da， CHU Cheng-bin， CHU Feng. Multicyclic hoist scheduling with constant processing times [J]. IEEE Trans on Robotics and Automation，2002，18(1):69-80.

[5]AGNETIS A. Scheduling no-wait robotic cells with two and three machines [J]. European Journal of Operational Research，2000，123(2):303-314.

[6]TANG Li-xin， XIE Xie， LIU Ji-yin. Scheduling of a single crane in batch annealing process [J]. Computers Operations Research，2009，36(10):2853-2865.

[7]DAWANDE M， GEISMARH N， SETHI S， et al. Sequencing and scheduling in robotic cells: recent developments [J]. Journal of Scheduling，2005，8(5):387-426.

[8]CHE A-da，CHU Cheng-bin.Multi-degree cyclic scheduling of two robots in a no-wait flowshop [J]. IEEE Trans on Automation Science and Engineering，2005，2(2):173-183.

[9]王書鋒， 鄒益仁. 車間作業(yè)調(diào)度(JSSP)技術(shù)問題簡明綜述[J]. 系統(tǒng)工程理論與實踐，2003，23(1): 49-55.

[10]徐俊剛， 戴國忠， 王宏安. 生產(chǎn)調(diào)度理論和方法研究綜述[J]. 計算機研究與發(fā)展， 2004，41(2):257-267.

[11]潘春榮， 伍乃騏. 晶圓制造自動化組合設備的調(diào)度問題研究[J]. 計算機集成制造系統(tǒng)，2009，15(3):522-528.

[12]LEI L， WANG T. A proof: the cyclic hoist scheduling problem is NP-hard [R]. New Jersey: Rutgers University，1989.

[13]BRAUNER N， FINKE G， KUBIAK W. Complexity of one-cycle robotic flow shops [J]. Journal of Scheduling，2003，6(4):355-371.

[14]LEVNER E， KATS V， LEVIT V E. An improved algorithm for cyclic scheduling in a robotic cell [J]. European Journal of Operational Research，1997，97(3):500-508.

[15]KARZANOV A V， LIVSHITS E M. Minimal quantity of operators for serving a homogeneous linear technological process [J]. Automation and Remote Control，1978，39(3):162-169.

[16]KATS V， LEVNER E. Minimizing the number of robots to meet a given cyclic schedule [J]. Annals of Operations Research，1997，69(1):209-226.

[17]LEUNG J， LEVNER E. An efficient algorithm for multi-hoist cyclic scheduling with fixed processing times [J]. Operations Research Letters，2006，34(4):465-472.

[18]LIU Ji-yin， JIANG Yun. An efficient optimal solution to the two-hoist no-wait cyclic scheduling problem [J]. Operations Research，2005，53(2): 313-327.

[19]CHE A-da， CHU Cheng-bin. Optimal scheduling of material handling devices in a PCB production line: problem formulation and a polynomial algorithm [J]. Mathematical Problems in Engineering，2008，2008:1-21.

[20]車阿大， 王遠. 無等待多機器人制造單元調(diào)度模型和算法研究[J]. 計算機集成制造系統(tǒng)，2008，14(3): 525-534.

[21]KATS V， LEVNER E. A strongly polynomial algorithm for no-wait cyclic robotic flowshop scheduling [J]. Operations Research Letters，1997，21(4):171-179.

[22]CHE A-da， CHU Cheng-bin. A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line [J]. Operations Research Letters，2005，33(3):274-284.

[23]車阿大， 晏鵬宇， 楊乃定. 復雜無等待自動化制造系統(tǒng)的調(diào)度算法研究[J]. 計算機集成制造系統(tǒng)，2007，13(8):1616-1623.

[24]CHE A-da， CHU Cheng-bin， LEVNER E.A polynomial algorithm for 2-degree cyclic robot scheduling[J]. European Journal of Operational Research，2003，145(1):31-44.

[25]AGNETIS A， PACCIARELLI D. Part sequencing in three-machine no-wait robotic cells [J]. Operations Research Letters，2000，27(4):185-192.

[26]DAWANDE M， SRISKANDARAJAH C， SETHI S. On throughput maximization in constant travel-time robotic cells [J]. Manufactu-ring and Service Operations Management， 2002，4(4):296-312.

[27]GEISMAR N， DAWANDE M， SRISKANDARAJAH C. Robotic cells with parallel machines: throughput maximization in constant travel-time cells [J]. Journal of Scheduling， 2004，7(5):375-395.

[28]GEISMAR N， SRISKANDARAJAH C， RAMANAN N.Increasing throughput for robotic cells with parallel machines and multiple robots [J]. IEEE Trans on Automation Science and Engineering，2004，1(1):84-89.

[29]PHILLIPS L W， UNGER P S. Mathematical programming solution of a hoist scheduling program [J]. AIIE Transactions，1976，8(2):219-225.

[30]周支立，李懷祖. 一個改進的單抓鉤周期性排序模型及其在自動化學處理線中的應用[J]. 高技術(shù)通訊，2003，13(9):59-62.

[31]LIU Ji-yin， JIANG Yun， ZHOU Zhi-li. Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution [J]. IIE Transactions， 2002，34(10):905-914.

[32]LEUNG J， ZHANG Guo-qing， YANG Xiao-guang， et al. Optimal cyclic multi-hoist scheduling: a mixed integer programming approach [J]. Operations Research，2004，52(6):965-976.

[33]SHAPIRO G W， NUTTLE H W. Hoist scheduling for a PCB electroplating facility [J]. IIE Transactions，1988，20(2):157-167.

[34]LEI L， WANG T J. Determining optimal cyclic hoist schedules in a single-hoist electroplating line [J]. IIE Transactions，1994，26(2):25-33.

[35]CHEN Hao-xun， CHU Cheng-bin， PROTH J M. Cyclic scheduling of a hoist with time window constraints [J]. IEEE Trans on Robotics and Automation，1998，14(1):144-152.

[36]CHE A-da， CHU Cheng-bin. Single-track multi-hoist scheduling problem: a collision-free resolution based on a branch and bound approach [J]. International Journal of Production Research，2004，42(12):2435-2456.

[37]CHE A-da， CHU Cheng-bin. Cyclic hoist scheduling in large real-life electroplating lines [J]. OR Spectrum，2007，29(3):445-470.

[38]LEI Lei， LIU Qing. Optimal cyclic scheduling of a robotic processing line with two-product and time-window constraints [J]. INFOR，2001，39(2):185-199.

[39]MATEO D， MANUEL， COMPANGYS P， et al. New computational experiences on the hoist scheduling problem for cyclic manufacturing of different products [R].Barcelona:Universitat Politècnica de Cata-lunya， 2007.

[40]CHE A-da， YAN Peng-yu， YANG Nai-ding， et al. Optimal cyclic scheduling of a hoist and multi-type parts with fixed processing times [J]. International Journal of Production Research，2010，48(5):1225-1243.

[41]LEI Lei， ARMSTRONG R， GU Shan-hong. Minimizing the fleet size with dependent time window and single-track constraints [J]. Operation Research Letters，1993，14(2):91-98.

[42]周支立，李懷祖.單抓鉤動態(tài)排序的啟發(fā)式算法[J]. 系統(tǒng)工程理論方法應用，2002，11(2):136-140.

[43]ZHOU Zhi-li， LIU Ji-yin. A heuristic algorithm for the two-hoist cyclic sche-duling problem with overlapping hoist coverage ranges [J]. IIE Transactions，2008，40(8):782-794.

[44]ZHOU Zhi-li， LI Ling. A solution for cyclic scheduling of multi-hoists without overlapping [J]. Annals of Operations Research，2009，168(1):5-21.

[45]GULTEKIN H， AKTURK M S， KARASAN O E. Scheduling in robotic cells: process flexibility and cell layout [J]. International Journal of Production Research，2008，46(8):2105-2121.

[46]SRISKANDARAJAH C， DROBOUCHEVITCH I， SETHI S， et al. Scheduling multiple parts in a robotic cell served by a dual-gripper robot [J]. Operations Research，2004，52(1):65-82.

[47]HENRIK J， BIERWIRTH C， KOPFER H. A heuristic scheduling procedure for multi-item hoist production lines [J]. International Journal of Production Economics，2007，105(1):54-69.

[48]SONG Wen-wei， ZABINSKY Z B， STORCH R L. An algorithm for scheduling a chemical processing tank line [J]. Production Planning Control，1993，4(4):323-332.

[49]CHAUVET F， LEVNER E， MEYZIN L K， et al. On-line scheduling in a surface treatment system [J]. European Journal of Operatio-nal Research，2000，120(2):382-392.

[50]YIH Y. An algorithm for hoist scheduling problems [J]. International Journal of Production Research，1994，32(3):501-516.

[51]THESEN A， LEI Lei. An expert scheduling system for material handling hoists [J]. Journal of Manufacturing Systems，1990，9(3):247-252.

[52]SUN T C， LAI K K， LAM K， et al. A study of heuristics for bidirectional multi-hoist production scheduling systems [J]. International Journal of Production Economics，1994，33(1-3):207-214.

[53]MAK R T， GUPTA S M， LAM K. Modeling of material handling hoist operations in a PCB manufacturing facility [J]. Journal of Electronics Manufacturing，2002，11(1):33-50.

[54]LIM J M. A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line [J]. Computer and Industrial Engineering，1997，33(3-4):789-792.

[55]SOUKHAL A， MARTINEAU P. Resolution of a scheduling problem in a flowshop robotic cell [J]. European Journal of Operational Research，2005，161(1):62-76.

[56]李鵬，車阿大. 基于混沌遺傳算法的自動化生產(chǎn)單元調(diào)度算法研究[J]. 系統(tǒng)工程，2008，26(11):75-80.

[57]楊廣文，鞠大鵬，鄭緯民，等. 利用模擬退火技術(shù)求解多Hoist調(diào)度問題[J].軟件學報，2001，12(1):11-17.

[58]趙振宏，肖田元. 機器人制造單元的建模與任務調(diào)度策略[J]. 計算機集成制造系統(tǒng)，2001，7(4):7-11.

[59]周支立，汪應洛.無重疊區(qū)的兩抓鉤周期性排序問題的一個搜索求解法[J].系統(tǒng)工程，2007，25(4):104-109.

[60]KAMALABADI I N， GHOLAMI S， MIRZAEI A H.Considering a cyclic multiple-part type three-machine robotic cell problem[C]//Proc of IEEE International Conference on Industrial Engineering and Engineering Management.2007:704-708.