求解柔性工件調度問題的啟發式算法

秦儉 茹海鵬

摘要：柔性工件調度問題（FJSP）是一個強NP難問題，盡管對于一個小規模問題，也很難在多項式時間內最優求解。本文針對目標函數為最小化總完工時間的FJSP提出一種有效的啟發式算法。該啟發式算法易于實現，并能快速獲得高質量的解。為驗證該啟發式算法的有效性，從文獻中找出10組基準問題進行測試，并將求解結果與問題下界進行比較，結果表明本文設計的啟發式算法能夠在極短時間內獲得相對誤差較低的解。

關鍵詞：柔性；工件調度；啟發式

調度問題一般是指在一個給定的時間展望期內，將有限的資源分配給不同的任務，以使得某一目標達到最優。調度問題廣泛存在于制造行業當中，對提高制造行業的生產效率等具有重要的作用。其中工件調度問題是實際生產中最為常見的一類調度問題。而在現代制造環境中，每臺機器的加工類型趨于柔性化，即一臺機器可以進行多種類型的操作，進而提出了柔性工件調度問題（FJSP），該問題在理論上和實踐上都具有更加重要的意義。

1 FJSP問題描述

FJSP問題是指將個工件分配給m臺機器進行加工，其中每個工件需依次經過步操作，而每一步操作都可以在某一可選機器集合中選擇一臺進行，每臺機器可進行多種類型的操作。需要為每一步操作選擇一臺機器進行加工，同時還需決定在該臺機器上開始加工的時間。顯然，相較于經典的工件調度問題，FJSP還需為每步操作選定一臺機器，這就使得FJSP更加復雜，該問題已經被證明是強NP難問題。[1]本文將針對目標為最小化總完工時間的FJSP設計一種有效的啟發式算法，可以在極短時間內獲得高質量的解。

2 設計啟發式算法求解FJSP問題

構造的啟發式如下：將工件和機器分別按照的降序和的升序排列，為操作選擇機器的總體思路為，首先依次調度所有工件的第一步操作，再調度所有工件的第二步操作，以此類推，直至所有工件的所有操作均調度完成，此時即可得到一份完整的工件調度結果。具體來說，針對操作，對每臺機器，分別計算評價函數

分別為上述四項標準的權重，即表示各自的重要程度。

令，即針對操作，找到最小評價函數值所對應的機器，則將操作安排在機器上加工，同時該機器的最大完工時間變為，繼續根據上述評價函數調度下一操作，直至所有工件的操作j均調度完成。此時開始對所有工件的操作j+1按照同樣的辦法分配機器，直至所有工件都分配完畢，則可獲得一份完整的工件調度。

3 數據測試

為了測試算法的有效性，本文從Brandimarte[2]中選取了5組經常被其它文獻引用的基準問題（benchmark problem）進行測試。本文在求解時間、最大完工時間以及與下界的相對誤差等方面，對本文所提的啟發式算法及文獻[3]中的算法進行了比較，比較結果如下表所示。該實驗結果表明：

4 結論

本文通過構造啟發式算法求解柔性工件調度（FJSP）問題。針對一組基準問題，可獲得高質量的解。結果表明，針對40個和50個工件的問題，獲得最優解的比例分別可以達到100%以及80%，對于100個工件的問題，相對誤差率也僅有0.99%。這說明該算法對于大規模的SMTWT問題也可以獲得質量較高的解。

參考文獻：

[1]Garey MR，Johnson DS，Sethi R.The complexity of flow shop and jobshop scheduling[J].Mathematics of Operations Research，1976，1（2）：117129.

[2]Brandimarte P.Routing and scheduling in a flexible job shop by tabu search[J].Annals of Operations Research，1993，41（1）：157183.

[3]Li JQ.A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem[J].International Journal of Advanced Manufacturing Technology，2010，52（58）：683697.

作者簡介：秦儉（1981），女，漢族，遼寧沈陽人，碩士，講師，研究方向：應用數學；茹海鵬（1983），男，漢族，遼寧葫蘆島人，本科，工程師，研究方向：壓縮機。