蛙跳算法與批量無等待流水線調度問題的優化

摘要：針對以makespan為指標的批量無等待流水線調度問題，提出了一種有效的離散蛙跳算法。首先采用基于工序的編碼方式使蛙跳算法直接應用于調度問題；其次采用基于NEH與改進NEH和隨機產生相結合的初始化方法，保證了初始解的高質量和分布性；再次采用交叉或變異方法產生新解，保持了種群的優越性和多樣性；最后對全局最優解執行快速局部搜索，有效地降低了算法的時間復雜度，平衡算法的全局和局部開發能力。對隨機生成不同規模的實例進行廣泛的實驗，通過仿真實驗結果的比較，表明所得蛙跳算法的有效性和高效性。

關鍵詞：批量無等待流水線調度；蛙跳算法；快速局部搜索

中圖分類號：TP18 文獻標志碼：A 文章編號：1001－3695(2010)08－2909－04