制造業的車間調度問題優化算法比較研究

摘要：目前，制造業的競爭日益激烈，在企業的日常運作過程中，會經常遇到各種各樣的復雜的調度問題，車間生產調度問題解決的好壞直接影響著企業的運作效率和最終的客戶滿意程度，最終影響著企業對市場的反應能力和競爭力。因此，調度問題已經成為運營管理領域的一大研究熱點。大量的學者研究生產調度優化問題，采用了各種優化方法。文章綜述了車間生產調度問題的各種優化方法，對其發展歷程、優缺點、適用性等都作了詳細的說明，并對它們作以比較分析，從而找到最適合現實狀況的優化方法。

關鍵詞：調度問題；最優化算法；啟發式算法

中圖分類號：F273文獻標識碼：A

文章編號：1002-3100(2008)06-0117-03

Abstract: At present， competition in manufacturing is growing tougher and tougher. There are all kinds of complicated scheduling problem in operations of manufacturing companies. How to solve the scheduling problem will affect the efficiency and the customer's satisfaction， and the power and response ability of the company. So scheduling problem becomes a very popular problem in OM. Lots of scholars adopts various methods to solve actual problem. This paper sums up all kinds of methods of scheduling problem and particularly explain merit and disadvantages， evolution course and applicability， which compare and analyze them each other in order to discover best of realistic status's optimum methods.

Key words: scheduling problem; optimized algorithm; heuristic algorithm

0引言

制造業是我國國民經濟的支柱產業，是直接創造社會財富的基礎。隨著人們生活水平的日益提高、科技創新速度的加快和市場的國際化，制造業市場環境發生了巨大變化，需求日益個性化、多樣化和快速變化。這使得倡導標準化和批量化的大批量制造模式陷入了前所未有的困境。按顧客訂單生產的多品種、小批量，以及大規模定制的生產模式逐漸成為制造行業的主流。這種情況下，生產線同時加工的產品種類增加，給生產作業計劃調度增加了難度，同時也使優化生產作業計劃提高生產效率成為制造業管理技術革新的重要內容。

目前，制造業產品競爭的焦點在于產品質優價廉、準時交貨、多品種小批量，而生產車間作業的調度是制造企業運營管理所面臨的基本問題，在企業的日常運作過程中，會經常遇到各種各樣的調度問題，調度問題解決的好壞直接影響著企業的運作效率和最終的客戶滿意程度，最終影響著企業對市場的反應能力和競爭力。

1問題描述

車間調度問題一般可以描述為：n個工件在m臺機器上加工，一個工件分為k道工序，每道工序可以在若干臺機器上加工。每一臺機器在每個時刻只能加工某個工件的某道工序，只能在上道工序加工完成后才能開始下一道工序的加工，前者稱為占用約束，后者稱為順序約束。車間調度問題的決策內容包括分配決策（工件的加工順序）、時間決策（工件各工序的加工時間）和路徑決策（工件工序的加工設備的分配）。所以車間調度的實質是屬于NP-Hard（Nondeterministic polynomial-Hard， 非確定性多項式難問題）組合問題。隨著問題規模的擴大，組合優化問題的搜索空間急劇擴大，有時在目前的計算機上用枚舉法很難或者甚至不可能得到其精確最優解。對于這類復雜問題，人們已意識到應把精力放在尋求其滿意解上。

2車間調度問題的優化方法

自從上世紀50年代以來，調度問題在學術界得到了廣泛的研究。五十多年來，出現了大量的理論研究。這些研究基本上都致力于尋找各種各樣調度問題的多項式算法。但是，很多的調度問題是不存在多項式算法的，在此過程研究中，導致了計算復雜性概念的誕生。此后，調度問題的理論研究變為或者尋找到問題的多項式算法或者證明該問題不存在多項式算法。

在對經典的調度問題取得大量的理論成果之后，90年代開始，理論研究的重心轉移到將這些經典的算法更多的與實際的調度問題結合上，學術界轉向了對復雜調度問題的啟發式算法和搜索技術的研究。這些近似算法能夠在一個相對合理的時間內找到一個滿意的調度方案。

下面，簡單介紹在制造業應用的車間調度優化算法。這些方法可分為最優化算法和啟發式算法兩類。

2.1最優化算法

優化算法又分為有效最優化方法和精確最優化方法。有效最優化方法是指在多項式時間內求得最優化調度的一類方法。但是，由于多數調度問題的NP-Hard特性，這類有效最優化算法是不存在的。精確最優化算法是一類具有一般性的組合最優化方法，主要包括線性規劃LP、非線性規劃NLP、動態規劃DP、拉格朗日乘子法和分枝定界等。LP 作為一種精確的運籌學方法，是較成熟的方法之一，但實際中很多問題不能以簡單的線性關系精確表達，且涉及的變量多為整數，因此限制了LP的使用。分枝定界的使用效率與定界的方法及搜索空間的結構密切相關，僅適用于中小規模的問題，在解決受多重復雜條件約束和含有不確定因素的排序問題時結果不理想。

2.2啟發式算法

調度算法的研究經歷了從有效最優化算法、精確求解算法到計算復雜性的研究、啟發式算法及其有效性的研究歷程。進入80年代，隨著技術和管理對更高層次的要求，過多的假設和對制造過程的簡化在很大程度上制約著調度理論的研究和實際應用的范圍，于是開展了對更復雜、更接近于實際的調度目標函數、制造環境及工藝約束條件的問題的研究。由此產生的啟發式算法有：

2.2.1優先分派規則。一個調度規則可以由多個優先級規則和（或）啟發式規則組成。優先級規則（Priority Rule）按某種方法給每個待排序的工作指定一個數值，并優先安排具有最小值的工作。常用的規則有最早交貨期（Earliest due-date，EDD）、最短加工時間（Shortest processing time，SPT）、最長加工時間（Largest processing time，LPT）、先入先出（First in first out，FIFO）等，實際使用時可以將若干個優先級規則加權組合，形成組合的優先級規則。啟發式規則指經驗法則，是比優先級規則更深一層的一些規則，其優點是可以縮短尋優過程。

2.2.2基于知識的方法。基于知識的調度優化方法利用專家系統自動產生調度或輔助人去調度，它將傳統的調度方法與基于知識的評價相結合，對設計適用于生產實際的高效益、高柔性的系統具有啟發意義。在應用中，專家系統中知識的獲取和推理速度是兩個瓶頸，專家系統有研制花費昂貴、知識的難于獲取和表達的缺點，將人工智能方法能與其他方法結合會得到更有效的調度方案。

Farhoodi在1990年提出了一個針對動態的車間調度問題的基于知識的優化方法，是基于知識的方法在調度問題中的很好的應用[1]。

2.2.3神經網絡方法。神經網絡已被成功地應用于解決組合優化問題，用神經網絡的方法建立生產調度的模型關鍵在于分別用不同類型的單元網絡表示不同類型的約束條件，然后通過適當連接這些單元神經網絡，得到資源約束和排序約束的網絡表示，進一步實現生產調度的建模。在大規模、復雜調度問題中，存在計算速度慢與結構參數難于確定的缺點，易陷入局部最小和全局搜索能力弱。王萬良在2002年提出了基于神經網絡的作業車間生產調度的新方法，給出了作業車間生產調度問題（JSP）的約束條件及其換位矩陣表示，提出了新的包括所有約束條件的計算能量函數表達式，得到相應的作業車間調度問題的Hopfield神經網絡結構與權值解析表達式，并提出相應的Hopfield神經網絡作業車間調度方法[2]。

2.2.4模擬退火算法。模擬退火算法由Metropolis等人提出，利用受控隨機概率接受劣解，避免陷入局部最優，是一種串行全局優化算法，在運籌學的各個領域有大量的研究。其收斂性要求初溫應足夠高，使解空間各狀態能以幾乎相同的概率出現，模擬退火的弱點是搜索空間過于龐大和下降溫度難于掌握。趙良輝2006年結合車間調度問題的特點闡述了模擬退火算法在解決車間調度問題上的應用，提出了基于模擬退火算法的車間調度問題模型，并以Matlab為工具進行了仿真實驗[3]。

2.2.5遺傳算法。遺傳算法是Holland基于自然遺傳進化的絕對模型提出的并行搜索機制，算法簡單，魯棒性強，非常適合解決調度問題。對生產調度問題，基因的選取一般為排序決策變量，通常采取二進制的編碼方式，同時交叉算子和編碼表示對算法的收斂性會產生影響。應用中，為解決收斂速度慢的缺點，許多學者嘗試采取遺傳算法和其他算法相結合的方式。此外，遺傳算法對初始種群很敏感，有采取其他啟發式（如優先排序規則）產生初始種群的改進方法，近年來，對基于遺傳算法的混合優化策略方面的研究出現了一些成果。

Crauwels(1996)研究了一個單機器的批處理生產調度問題，通過數值仿真計算，比較了模擬退火、禁忌搜索、遺傳算法和一種啟發式算法，結果表明在該環境下遺傳算法效果最好[4]。

2.2.6禁忌搜索算法。禁忌搜索是Glove提出的模擬智能過程的一種具有記憶功能的全局逐步優化算法，對變動的排序在其可行解的所有空間中進行搜尋。通過設置禁忌表記憶近期搜索路徑，避免陷入局部最優或重復過去的搜索，并由此控制進一步的搜索方向，同時利用中、長期的存儲機制進行強化和多樣化搜索。黃志在2006年描述了一種解決作業車間調度最短完工時間問題的有效的啟發式算法，該算法基于禁忌搜索技術。為了得到更好的結果，還將倒轉技術引入到算法中。從對一組問題基準實例的實驗計算結果看，該算法在合理的計算時間內對多個實例得到比2004年提出的ISSB算法更好的結果[5]。

2.2.7拍賣算法。拍賣算法（bidding algorithm）是研究調度問題的一種新思路，也稱為基于市場的（market based）排序或基于代理的（agent-based）排序。該方法需要設立工件代理（job agent）和機器代理（machine agent），并建立一套市場拍賣機制，通過市場招投標的方式，確定工件的加工順序。工件代理的目標是在預算約束條件下，使工件被按時完成；機器代理的目標是利益最大化。應用該方法調度的研究內容包括拍賣機制的建立、定價的規則、預算約束的建立、兩類代理的最優決策法則等。

Ouelhadj（2004）研究了鋼鐵生產中的連鑄和熱軋的生產過程，分析了一種基于代理的調度機制，設計了基于合同網絡協議的兩層投標機制，并將禁忌搜索算法包含在調度機制中，最后通過算例分析了該方法的效果[6]。

2.3各種算法的比較分析

最優化算法的優點在于求解精確，目標直指最優解，在面對簡單問題的時候，可以找到適合問題的最優解。但是，當問題的規模增大時，算法的計算時間隨之呈指數增加，會發生“組合爆炸”，給求解計算帶來困難。另外，使用最優化算法時，通常要加上一些脫離實際情況的假設，在一定程度上也導致了理論研究與實際應用的脫節。

與精確最優化算法相比，啟發式算法的明顯優勢在于：啟發式算法相對比較簡單，計算效率高，能顯著地節省計算開支；而且啟發式算法靈活多變，在考慮多種方案和不能用定量表示約束集合時，常能把它作為制定計劃的工具。但是，啟發式算法有明顯不足之處，即有可能出現所產生的解比全局最優解差很多的情況，而且差的程度總是不夠明確。因此，合理的計算時間和所求出的解的最優性就成為衡量啟發式算法性能的標準。

那么對于啟發式算法中的各種算法來說，在一定時期、一定情況下都有各自的優點，都有解決某一類問題的優越性，但隨著發展的需要，對優化方法要求也越來越高，下面對各種方法進行比較分析，通過表格的形式來展現各自的特點。

縱上所述，車間作業調度問題中的各種算法各有利弊，在不同情況下可以有針對性的選擇。

3結論

本文是針對制造業實際應用當中的車間調度問題而言的，對不同條件下的調度問題應該有針對性的選擇不同的方法。將各種優化方法都詳細地作了介紹，給出其優缺點及適用性，讓讀者清晰明了，可以根據各自所需進行合理的選擇。

另外從目前的研究情況來看，針對實際生產中的復雜問題，越來越多的跡象表明在同一個問題中使用兩個或多個算法結合的方法更容易得到更好的結果，所以混合算法的使用是將來的一個發展趨勢。

參考文獻：

[1]Farhoodi F A. Knowledge-based approach to dynamic job-shop scheduling[J]. International Journal of Computer Integrated Manufacturing， 1990，3(2):84-95.

[2] 王萬良，吳啟迪，徐新黎. 基于Hopfield神經網絡的作業車間生產調度方法[J]. 自動化學報，2002，28(5):838-844.

[3] 趙良輝，鄧飛其. 用于作業車間調度的模擬退火算法[J]. 制造業自動化，2006，28(3):10-23.

[4]H.A.J. Crauwels， C.N. Potts， L.N. Van Wassenhove. Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs[J]. European Journal of Operational Research， 1996(90):200-213.

[5] 黃志，黃文奇. 一種基于禁忌搜索的作業車間調度算法[J]. 計算機工程與應用，2006(3):12-14.

[6]D. Ouelhadj， S. Petrovic， P.I. Cowling and A. Meisels. Inter-agent cooperation and communication for agent-based robust dynamic scheduling in steel production[J]. Advanced Engineering Informatics， 2004(18):161-172.