1.2　制造系統生產調度問題研究現狀

1.2.1　制造系統生產調度問題的復雜性

針對市場需求面向多品種、小批量定制的發展模式，產品的結構表現出更多的BOM、工序種類繁多及其生產加工要求多車間、多機床及多AGV協調生產等特性，合理而有效的調度將是制造系統實現高效生產的關鍵技術之一。調度優化針對若干可以分解的任務，在滿足一定的約束條件下，安排其組成部分所占用的生產資源以確定所有任務的某一項或者某幾項性能指標達到最優。1954年，美國學者Johnson在他發表的文章中首次闡述了流水車間（Flow Shop）調度問題，從此，生產調度問題的研究開始受到運籌學、應用數學和工程技術等領域的專家學者的重視，并且取得了一系列的豐富理論成果。

生產調度問題一般采用α/β/γ三元組的方法對其進行描述，其中，α用于描述機器環境類型，β用于描述約束和限制要求，γ用于描述某一項或者某幾項性能指標最優要求。

生產調度作為制造系統研究對象之一，它是企業生產管理系統的關鍵。一個良好的生產調度方案，能夠在不增加其他成本的基礎上，提升車間的生產效率，提高企業的競爭力。在實際的企業生產中，生產調度問題往往非常復雜，該類問題通常具有如下固有特性。

（1）調度目標的多元化。車間調度問題的研究，大多數是以完工時間最短為調度目標函數。在企業的實際生產調度中，為了均衡客戶需求和自身經濟效益，企業決策者往往不會僅考慮單一的優化目標，最短完工時間、最小拖延時間、成本最低、能耗最低、機器最大負荷、總負荷等都是車間調度的優化目標。在每次實際生產調度中，往往不止考慮一個目標。

（2）調度條件的約束化。車間調度方案的確定，往往需要考慮各種約束條件，包括任務本身的約束條件，如每道加工工序要滿足基準先行、先面后孔、先粗后精等約束要求。另外，車間調度資源的約束、任務對加工機器的約束、AGV的約束，以及其他一些約束都是在建立目標函數時需要考慮的。

（3）調度對象的柔性化。在傳統的車間調度中，每個工件的加工路徑都是唯一的，即每個任務的加工工序固定，并且每道工序加工的機器也是固定的。而在實際的生產中，柔性生產調度往往更切合實際。柔性生產調度包括加工工藝的柔性、加工機器的柔性、加工方法的柔性。其中，加工工藝的柔性是指工件的加工路徑不唯一，每條工藝路線上的工序也不相同；加工機器的柔性是指工件的加工工序可以由不同的機器完成，加工時間和資源消耗也不同；加工方法的柔性是指同一個加工特征可以用不同的加工方法實現。因為柔性生產調度既要對工序順序進行調度，又要為每個工件選擇合適的工藝（或為每道工序選擇適當的加工機器），所以比一般的車間調度更復雜。

（4）調度環境的動態化。多數的生產調度方案都是假定調度環境是靜態的，即從加工開始到加工結束，所有的資源都是固定不變的。而在實際生產中，往往會出現突發情況，比如，機器發生故障，訂單發生變化，有緊急工件插入，等等。這時，原有的調度方案就不再適用，為了保證企業的利益，就需要及時調整調度方案。動態調度能夠根據加工條件的變化適時地調整調度方案，更符合企業的生產實際。動態調度一般是先對調度任務進行靜態調度，然后再根據生產實際中出現的突發情況，對尚未完成的任務進行重調度。

（5）調度計算的復雜化。生產調度問題在大部分文獻中已經被證明是一個NP-Complete問題，該問題的復雜性在于隨著問題規模的增加，可行解的數量快速遞增，計算的強度呈指數級增大。

1.2.2　現代制造系統生產調度面臨的需求

生產調度問題除了1.2.1節所述的一些固有特性，隨著智能制造系統的發展，制造系統的生產組織模式發生了巨大的變化，生產調度問題也面臨著新的挑戰。由于生產車間是制造系統的重要組成部分和基本單元，是實施客戶需求的真實場所，是工廠生產和管理的基本單位，是企業從事生產經營活動的基礎，因此，其優良的調度方法和運作過程直接體現出制造系統的性能。如圖1.2所示，從業務層次來看，生產車間是接納上層物料、信息和狀態反饋的聚集點，是工廠層的組成單元。

在現代工廠車間里有不同柔性和自動化程度的生產設備，如數控（Numerical Control，NC）機床、計算機數控（Computer Numerical Control，CNC）機床和加工中心等，這些加工設備使生產車間成為具有高度柔性的生產系統。然而，可靠性和柔性程度高的生產制造系統不僅依賴于柔性的設備和組件，在組織生產、配置任務和資料的過程中采用良好的生產管理方式和優秀的調度技術也具有非常重要的作用。合適的調度技術和優化方法是制造車間高效運行的保證。因此，研究高可靠性和高柔性的生產調度技術已經成為現代智能制造系統領域的關鍵性問題之一。同時，現代智能制造系統處在一個動態的運行環境中，許多不可預知的動態事件頻繁發生，如緊急訂單、訂單取消、設備故障或工藝路線變化等。為了快速地適應這些動態變化，智能制造系統對調度技術實時性和響應性的需求更加迫切。

分布性、自治性和協商性是現代智能制造系統具有的顯著特點，而這種特性也是調度技術的發展趨勢。調度技術利用分布的智能單元根據其自身知識實現局部優化，然后通過單元間的協商達到全局優化。這種調度技術完全可以適應各種制造系統中隨機出現的動態事件，并滿足多目標的優化（如成本、時間、資源利用率等）。傳統的調度技術一般采用離線的方式進行調度計算，具有離線性的特點；而新的調度技術除了必須具備分布性、自治性和協商性的特點，還必須具備實時性、智能性和事件驅動性的特點。

1.2.3　現代智能制造系統動態調度技術

為了解決制造系統在實際生產過程中存在的不確定性和隨機性問題，研究現代智能制造系統在動態生產環境下的調度技術引起了不少機構、組織和學者的關注。進入20世紀之后，許多先進的調度優化技術不斷被應用到動態生產調度中，其研究成果持續地得到充實和發展，歸納起來可以分為傳統調度方法和非傳統調度方法兩種。傳統調度方法一般是用離線的方式來解決調度問題，包括近似方法和精確方法，其中涉及的一些具體方法如圖1.3所示。

離線的方法可以獲得較好的優化結果，但是其缺陷也非常明顯，即它很難適應實時調度。而非傳統調度方法是相對離線調度方法而言的，它主要關注制造系統在生產調度實時變化條件下的應對機制及決策方案，并強調調度的連續性，因此，它更適應現代智能制造系統發展的需求。從計算形式上，可以將非傳統調度方法分為集中式調度和分布式調度兩類。集中式調度，顧名思義是所有任務通過一個中央調度器完成任務分配，所得到的調度結果往往是全局最優解。然而由于控制結構的限制，集中式調度很難適應動態變化的制造系統環境，在發生擾動時，制造系統的運行經常被中斷，且計算復雜性很難被分解和降低。分布式調度強調自治與協調，它賦予各個智能單元決策能力和計算能力。各個智能單元在解決自身調度問題的前提下，通過智能單元間的協調調節解決更高層次的調度問題，因此，它具有其他方法所不具備的優點。

（1）利用分布式特性將調度問題離散化，簡化調度問題規模。

（2）智能單元具有優化能力和計算能力，可通過并行計算提高系統運算效率。

（3）智能單元的調度算法靈活多變。

（4）智能單元可集成至實體，并連接物理資源實現實時調度。

（5）針對動態事件，調度系統具有適應性、響應性和擾動事件影響局部性等特點。

自治與協調是分布式調度方法的典型特征，其基本思想是把復雜制造系統的生產組織結構劃分成相互獨立的智能單元，將復雜的調度任務分散至各個智能單元上并行完成。與此同時，各個智能單元之間通過相互間協商完成各自的調度行為，從而實現制造系統調度目標的優化。在現代智能制造系統中，具有自治與協調特性的分布式制造系統以多智能體制造系統（MAMS）和Holon制造系統（HMS）最為典型，而且這種基于自治與協調的調度技術隸屬于分布式智能調度算法的范疇，是MAMS和HMS生產計劃領域的研究熱點。

從目前的研究來看，對MAMS和HMS生產調度的研究主要集中在裝配生產線、柔性制造系統（Flexible manufacturing systems，FMS）、Job Shop、物料處理系統等各個方面。比如，有學者提出了一種針對車間動態調度的多Agent構架。各個加工單元Agent動態地選擇最具適應性的調度規則執行局部調度。當監控Agent認為既定的事件出現時，局部Agent根據優化后的閾值重新選擇調度規則，然后Agent之間通過協商機制完成制造系統的動態調度。還有的學者提出了一種基于協商的多Agent調度系統解決動態事件的彈性作業調度問題。Agent之間采用基于信息素的方法進行協商通信，完成任務分配，也可以采用一種多Agent的AGV路徑選擇/調度方法，利用Agent之間的通信協商完成路徑生成、枚舉時間窗、中斷搜索、調整等待時間和決策路徑選擇等，該方法在單/雙向路徑網絡AGV“無沖突”和“最短路徑選擇”中都表現出了很好的效果。還有學者提出了一種針對動態調度的HMS構架，HMS架構由資源Holon、任務Holon、工藝規劃Holon、生產計劃Holon和工藝規劃Holon組成。Holon之間采用合同網協議進行協商通信。在調度過程中，任務Holon和資源Holon之間通過招投標過程進行任務分配，同時，資源Holon受調度Holon和工藝規劃Holon的約束控制。為了解決隨機加工時間的柔性流水車間調度問題，提出了一種HMS方法，采用兩種調度策略進行動態調度。當任務進入流水車間后，機床Holon根據其隨機屬性被聚集為兩個Holon群。具有低隨機性的Holon群采用遺傳算法生成局部解；具有高隨機性的Holon群成員之間利用基于合同網協商機制進行談判獲得可行的局部解。HMS通過兩種算法的結合獲得全局最優解。

1.2.4　現狀總結

盡管制造系統中Agent（Holon）的自治與協商特性在調度中得到了較為廣泛的應用，但是或多或少仍然存在缺陷或不足。與之前分析的MAMS類似，Agent（Holon）以分布式的形式存在，通過Agent（Holon）的自治以及Agent（Holon）之間的協商來完成生產調度。但是由于Agent（Holon）間具有平等地位，只能根據局部信息做出調度決策，使調度結果達不到最優；并且，整個系統沒有一個集中的調度控制器，在調度過程中不可避免地會產生沖突和死鎖。雖然該問題可以通過多次協商解決，但也帶來了系統通信量大的負擔，尤其在解決大型復雜調度問題時，多次協商帶來的問題將會被放大。另外，若缺乏優秀的調節策略和方法，調度的結果不但達不到預期結果，并且還有惡化的可能。因此，對現代智能制造系統調度領域的研究還存在以下一些需改進之處。

（1）構建更合理的智能制造系統體系構架。

（2）尋找一種更好的協商（通信）機制。

（3）探索更合理和更優化的調度策略和優化方法，為智能單元的協商過程服務。