應用新型螢火蟲算法求解Job-shop調度問題

上海理工大學 管理學院，上海 200093

上海理工大學 管理學院，上海 200093

1 引言

生產調度問題是在一定的時間內，進行可用共享資源的分配和生產任務的排序，以滿足某些指定的性能指標[1]，簡單地說，生產調度問題就是按時間分配資源來完成任務的問題。問題的求解目標就是找到一個將一組資源安排到設備上去，以最優某項加工性能指標的方案[2]。車間作業調度問題（Job-shop Scheduling Problem，JSP）是最著名的調度問題之一，已被證明是一個組合優化問題及典型的NP-hard難題[3]，對于此類問題的優化調度研究具很高的理論和實際工程應用價值，同時長時間來也一直是學術界和工程界的研究熱點。

目前，已有各種優化算法廣泛應用于處理JSP調度問題，主要分為精確算法和近似算法兩大類[4]：精確方法主要有分支定界法、數學規劃法、拉格朗日松弛法等，該類算法可求得問題的精確解，但計算量大、耗時長，只適合求解一些小規模調度問題，由于實際調度問題的復雜性，此類算法難以得到真正應用。近似算法是當前車間作業調度中應用最為廣泛的方法，主要有遺傳算法、模擬退火算法、禁忌搜索法等。通常在這些算法的搜索過程中采用隨機步長，對處理大規模的調度問題有很好的效果，但并不能保證得到最優解。螢火蟲算法（Firefly algorithm）是劍橋學者Yang[5]于2005年受自然界中螢火蟲的發光行為啟發而提出來的一種仿生智能群算法，目前，FA算法已應用于處理函數優化問題[6-9]及組合優化問題[10]，但在處理生產調度中的JSP問題國內還沒有相關文獻，本文將該算法應用于求解Job-shop調度問題，并通過實驗仿真對其可行性進行驗證，結果表明該方法的可行性和有效性。……