改進果蠅算法求解零空閑流水車間調度問題*

尹瑞雪，馮旭青，吳 拓，李付春，王 澤

(貴州大學機械工程學院，貴陽 550025)

0 引言

零空閑流水車間調度問題(NIFS)具有很強的工業背景，廣泛見于集成電路、紡織、玻璃和陶器等產品的生產制造過程中。基于成本及加工工藝要求的考慮，要求每臺機器一旦開始加工某個工件，則需要不間斷的把所有工作都加工完成，不允許機器操作之間有空閑時間，即機器不能空轉。

實現零空閑車間調度將有效節約機床閑置能耗，是實現機加工行業節能減排的有效途徑之一。因此，針對該問題，國內外學者展開了一系列研究。BAPTISTE等[1]證明了F/no-idle/Cmax是一個NP難問題。武磊等[2]求解以總流經時間和最大完工時間為目標的零空閑流水線調度問題，改進了和聲搜索算法的求解模型。王亞敏等[3]以E/T指標最優為優化測度，提出了一種蛙跳求解算法。潘全科等[4]基于PSO算法，提出了離散粒子群算法求解NIFS問題。李麗娟等[5]則改進了標準覓食算法，引入交叉優化算子、混合復制策略及自適應遷徙概率求解問題。研究表明，采用更有效更穩定的優化算法是獲得最優解的重要前提。

針對該優化問題，本文擬采用果蠅優化算法(fruit fly optimization algorithm，FOA)[6]，該算法是一種新的基于果蠅覓食行為尋找全局最優解的新方法。該算法操作簡單，易于實現，具有較好的局部搜索能力[7]。已有的研究中，僅有少數學者采用該算法解決此類優化問題。杜利珍等[8]針對不相關并行機混合流水車間調度問題，利用權重系數來提高算法的隨機搜索能力。……