「 1. 調度的概念 」

調度問題的基本描述是“如何把有限的資源在合理的時間內分配給若干個任務，以滿足或優化一個或多個目標”。調度不只是排序，還需要根據得到的排序確定各個任務的開始時間和結束時間。調度問題廣泛存在于各種領域，如企業管理、生產管理、交通運輸、航空航天、醫療衛生和網絡通訊等，幾乎存在于工程科學的所有分支領域內。它也是智能制造領域的關鍵核心問題之一，因此，調度問題的研究十分重要。

「 2. 智能調度的特點 」

生產調度的對象與目標決定了這一問題具有復雜特性，其突出表現為調度目標的多樣性、調度環境的不確定性和問題求解過程的復雜性。具體表現如下：

（1）多目標性。生產調度的總體目標一般是由一系列的調度計劃約束條件和評價指標所構成，在不同類型的生產企業和不同的制造環境下，往往種類繁多、形式多樣，這在很大程度上決定了調度目標的多樣性。對于調度計劃評價指標，通常考慮最多的是生產周期最短，其他還包括交貨期、設備利用率最高、成本最低、最短的延遲、最小提前或者拖期懲罰、在制品庫存量最少等。在實際生產中有時不只是單純考慮某一項要求，由于各項要求可能彼此沖突，因而在調度計劃制定過程中必須綜合權衡考慮。

（2）不確定性。在實際的生產調度系統中存在種種隨機的和不確定的因素，如加工時間波動、機床設備故障、原材料緊缺、緊急訂單插入等各種意外因素。調度計劃執行期間所面臨的制造環境很少與計劃制定過程中所考慮的完全一致，其結果即使不會導致既定計劃完全作廢，也常常需要對其進行不同程度的修改，以便充分適應現場狀況的變化，這就使得更為復雜的動態調度成為必要。

（3）復雜性。多目標性和不確定性均在調度問題求解過程的復雜性中得以集中體現，并使這一工作變得更為艱巨。眾所周知，經典調度問題本身已經是一類極其復雜的組合優化問題，大規模生產過程中工件加工的調度總數簡直就是天文數字。如果再加入其他評價指標，并考慮環境隨機因素，問題的復雜程度可想而知。

調度問題的復雜特性，制約著相關技術的應用與發展，使得該領域內尋求有效方法的眾多努力長期以來難以完全滿足實際應用的需要；而智能調度技術的出現，為解決調度問題提供了新的方法；同時，也正是因為存在如此巨大的挑戰，多年來，對于這一問題的研究吸引了來自不同領域的大量研究應用人員，提出了若干現行的方法和技術，在不同程度上對實際問題的解決做出了各自的貢獻。

「 3. 智能調度的關鍵技術 」

1）數學規劃方法與求解器

數學規劃方法是較早地用于求解車間調度的方法。20世紀60年代，這個時期研究人員傾向于設計具有多項式時間復雜度的確定性方法，以期求出車間調度問題的最優解。混合整數規劃方法（mixed integer programming）是常用求解調度問題的數學方法，該方法限制部分決策變量必須是整數，但是在運算中整數變量的數量會隨問題規模呈指數規模增長。所以，有研究人員認為使用整數規劃方法求解調度問題在計算上是不可行的。用于求解調度問題比較成功的數學方法包括：拉格朗日松弛法（lagrangian relaxation）和分解方法（decomposition methods）。拉格朗日松弛法用非負拉格朗日乘子將工藝約束和資源約束進行松弛，最后將懲罰函數加入目標函數中，在可行的時間里能對復雜的規劃問題提供較好的解，該方法已經用于解決作業車間調度問題。分解方法將原問題分解為多個小的易于求解的子問題，將子問題求出最優，該方法也已用于求解調度問題。

分枝定界法（bound & branch，B&B）是主要的枚舉策略之一。它用動態結構分枝來描述所有的可行解空間，這些分枝隱含有要被搜索的可行解。這個方法可以用數學式和規則來描述，在對最優解搜索過程中，它允許把大部分的分枝從搜索過程中去掉。這種方法從它誕生之日起，就十分流行。它適合求解總工序數N<250的調度問題，對于求解大規模問題，由于它需要巨大的計算時間，因此限制了它的使用。該方法也被大量地用于求解車間調度問題。Carlier在1989年提出的分枝定界法第一次證明了著名的作業車間調度基準實例FT10問題的最優解是930。

目前，建立的數學規劃模型可以通過求解器來求解。求解器是一類封裝好的優化算法程序包，研究人員可以使用求解器來優化調度等復雜問題，而不需要自己編寫算法代碼。常用的求解器包括Cplex、Gurobi、MOSEK等。通常不同的求解器具有其獨立的數學語言，用以編寫建立好的數學模型。針對不同屬性的模型需要調用不同的優化算法，而對同一數學模型則需要使用不同的建模語言多次編寫，這無疑增大了問題的求解工作量。

2）啟發式方法

20世紀70年代，研究人員對調度問題的計算復雜性進行了深入的研究，證明絕大多數的調度問題是NP-Complete問題。他們不再追求用精確算法來求出該問題的最優解，而是通過近似算法在可以接受的時間內尋求該問題的滿意解，因此提出用啟發式方法來求解該問題。Panwalkar總結和歸納了113種調度規則，并將它們分為了三類：簡單規則、復合規則和啟發式規則。

（1）優先分配規則（priority dispatch rules，PDR）

這種方法是分配一個優先權給所有待加工的工序，然后選擇優先權最高的加工工序先加工，接下來按優先權次序依次進行排序。該方法具有容易實現和較小時間復雜性的特點，是在實際應用中解決調度問題的常用方法。常用的規則包括：SOT(shortest operation time))、LOT(longest operation time)、LRPT (longest remaining processing time)、SRPT (shortest remaining processing time)、LORPT (longest operation remaining processing time)、Random、FCFS (first come first served)、SPT (shortest processing time)、LPT (longest processing time)、LOS (longest operation successor)、SNRO (smallest number of remaining operations)、LNRO(largest number of remaining operations)。

優先分配規則雖然速度非常快，但是具有短視的天性，如它只考慮機器的當前狀態和解的質量等級等問題，而不能全面的考慮問題。

（2）基于瓶頸的啟發式方法（bottleneck based heuristics）

一般包括瓶頸移動方法（shifting bottleneck procedure，SBP）和Beam搜索。Admas在1988年提出的SBP方法是第一個解決FT10標準問題的啟發式方法。這個構造算法能取得好的結果的主要原因之一是因為它是徹底解決了單一機器排序問題的算法。SBP方法是按照解的大小順序對所有機器進行排序，有著最大下界的機器被確定為瓶頸機器。SBP對瓶頸機器排序，留下被忽視的未被排序的機器，固定已排序的機器。當每次瓶頸機器排序后，每個先前被排定的有接受改進能力的機器，通過解決單一機器問題的方法，再次被局部重新最優化，而單一機器問題的排序是用Carlier提出的方法迭代解決。SBP方法雖然能比PDR方法提供質量更好的解，但是計算時間長，算法實施比較復雜。

3）智能優化方法

智能優化方法是一類受生物智能或物理現象所啟發的隨機搜索算法，目前在理論上還遠不如傳統優化算法完善，往往也不能確保解的最優性。但從實際應用上看，這類算法一般不要求目標函數和約束的連續性與凸性，甚至有時都不需要解析表達式，對計算中數據的不確定性也有很強的適應能力。由于這些獨特的優點和機制，智能優化方法引起了眾多國內外學者的重視，且在諸多領域中得到了廣泛應用，展示出強勁的發展勢頭。調度領域的智能優化方法主要包括進化算法、群智能優化算法、局部搜索算法等。

（1）進化算法

進化算法是一類模擬生物進化過程的智能優化方法，主要包括遺傳算法（genetic algorithm, GA）、遺傳規劃（genetic programming, GP）、進化策略（evolution strategies, ES）和進化規劃（evolution programming, EP），廣泛應用于規劃與調度等組合優化問題。其中，遺傳算法是在調度領域中應用最廣泛的進化算法。

（2）群智能優化算法

群智能優化算法主要是通過模擬昆蟲、鳥群和魚群等群體行為所構造的一類智能優化方法。這些群體按照一種合作的方式尋找食物或躲避追捕，群體中的每個成員通過學習它自身的經驗和其他成員的經驗來不斷地改變搜索的方向。任何一種受動物的社會行為機制而啟發設計出的算法均屬于群智能優化算法。在調度領域中，常見的群智能優化算法有粒子群算法（particle swarm optimization，PSO）、蟻群算法（ant colony optimization，ACO）等。

（3）局部搜索算法

局部搜索（local search, LS）算法是運用人工智能、物理學等領域的某些思想，對基本局部搜索算法進行推廣或擴展，目的是為克服基本局部搜索算法極易陷入局部最優的缺點，并形成了以禁忌搜索算法、模擬退火算法等為代表的算法，是求解調度問題的常用方法。

（4）人工智能算法

人工智能是是一門多領域交叉學科，涉及概率論、統計學、逼近論、凸分析、算法復雜度理論等多門學科。專門研究計算機怎樣模擬或實現人類的學習行為，以獲取新的知識或技能，重新組織已有的知識結構使之不斷改善自身的性能。經典的人工智能算法包括決策樹（decision trees）、樸素貝葉斯分類（naive bayesian classification）、支持向量機（support vector machine，SVM）、主成分分析（principal component analysis，PCA）等。

目前，人工智能相關算法的核心功能主要是用于分類和預測兩個方面。而調度問題的本質是優化過程，可行解的數量眾多，難以直接采用人工智能對其求解。因此，必須在調度問題中，找到分類或預測的步驟，并將其替換為人工智能算法進行輔助求解。華中科技大學的黎陽、高亮、李新宇等提出了一種基于殘差神經網絡的置換流水車間調度方法。

圖為置換流水車間調度的甘特圖，當需要交換工件8和5進行鄰域搜索的時候，如果采用計算makespan的方式來判斷交換后結果的好壞，則會占用大量的計算時間。因此將該過程替換為殘差神經網絡的分類過程。將計算時間移到調度準備階段，完全不占用寶貴的求解時間。針對于特定的車間，利用歷史數據提前對神經網絡進行訓練并保存好訓練之后的網絡參數。在需要調用的時候，只需要一次矩陣運算即可，計算時間消耗近乎于0，能大大提高算法的優化效率。

 

置換流水車間調度甘特圖

「 4. 智能調度的未來發展趨勢 」

1）當前面臨的問題

盡管車間調度研究已經成為熱點研究領域，許多學者也在這一領域產出許多成果，但車間調度問題的研究仍然面臨著許多問題。為了提高求解結果和方法的通用性，通常會使用數學模型對問題進行求解，但數學模型的求解效率低，且只能對小規模問題進行求解；為了提高問題的求解效率和對大規模問題進行求解，學者們提出用智能優化算法對問題進行求解，但智能算法的求解結果具有一定的不穩定性，同時智能優化算法的通用性較低，需要針對特定的問題設計特定的優化過程。現在又有學者提出將數學模型與智能算法相結合的求解思路，但兩者之間如何結合，結合之后怎樣求解仍然需要研究和探索。

2）未來發展趨勢

車間調度優化是提高企業生產效率的關鍵，因此對車間調度問題的研究必然越來越受到重視，其主要的發展趨勢有以下幾點：

（1）伴隨著生產工藝的復雜化、生產任務的大批量化、生產場景的多樣化等趨勢，對調度問題的研究必將朝著更加貼近生產實際問題的方向發展，例如問題中包含實際生產約束、串\并行的多車間協同調度、動態調度等。

（2）伴隨著上下游企業之間的聯盟、面向用戶的生產模式的發展等，分布式生產調度的研究必然會成為一個重要研究方向。

（3）隨著智能車間的發展，車間調度問題與其他生產問題的聯系正在逐步加強，這必然會形成一個更加復雜的耦合問題，如車間調度問題與工藝規劃問題的結合、車間調度問題與物流運輸問題的結合等，這些問題的研究對提高企業生產效益具有重要意義。

來源于：來源：改編自：《智能制造概論》   

作者：李培根 高亮