應用螢火蟲算法求解基于學習效應的PFSP 問題

杜 貞，葉春明，凌遠雄

DU Zhen,YE Chunming,LING Yuanxiong

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

Department of Management,University of Shanghai for Science and Technology,Shanghai 200093,China

1 引言

置換流水車間調度問題（Permutation Flow-shop Scheduling Problem，PFSP）是實際生產車間中一類重要的流水車間調度問題，尤其適用于單件大批量生產背景的制造型企業。該問題可以被描述為：n個工件在m臺不同的機器上加工，每個工件有m道不同的工序，每道工序要在不同的機器上加工完成；n個工件通過m臺機器的順序相同，它們在每臺機器上的加工順序也相同；每臺機器每次只能加工一個工件，每個工件每次只能由一臺機器加工；已知每個工件在每臺機器上的加工時間；求解的目標是確定最優加工順序，使得按照該順序加工工件時總完工時間最小。

對PFSP 的求解方法，可以分為三種類型：精確方法、啟發式算法以及智能優化算法。研究表明，精確算法只適用于小規模問題的求解，啟發式算法求解質量較差[1]，而當m>2 時，PFSP 問題已是NP 難題[2]，因此隨著問題規模的增加，調度問題的解空間容量巨大，其求解過程更加復雜。由于精確方法和啟發式算法的局限性，目前對該問題的求解方法趨向于使用更高效的智能優化算法，包括遺傳算法、禁忌搜索算法、模擬退火法、蟻群優化算法以及粒子群算法等[3]。本文采用的螢火蟲算法[4-5]是一種比較新穎的算法，在生產調度方面的研究剛剛起步，但也取得了一些成果：文獻[6-8]分別應用該算法求解PFSP 和Job-shop 調度問題，通過對PFSP 中的典型Car 類測試問題和Job-shop 調度問題的FT、LA 兩類測試問題進行仿真測試，并將結果與粒子群等算法的結果進行對比，驗證了算法的可行性和有效性。

在經典的排序理論中，工件的加工時間都沒有考慮與工件的加工位置的關系。然而，在一些實際排序問題中，由于工人或機器在長時間加工相同或類似的工件時，加工效率可能會逐漸提高，從而使后加工的工件的加工時間變小，這種現象被稱為具有學習效應[9]。學習效應在生產中的影響最早是由Wright[10]提出的，之后國內外很多學者對其進行了研究，研究發現絕大多數行業存在學習效應，且由于環境、工藝、工序、生產設備等因素的差異，不同的行業學習率有所不同。相關學者對將學習效應應用到工件排序問題中進行了研究，其中孫林輝等[9]對工件具有學習效應的2 臺機器流水作業排序問題進行了研究，給出了問題的數學規劃模型，同時對大規模問題給出3 個啟發式算法并驗證了這3 個算法解決所研究問題具有有效性；張新功[11]對具有學習效應的最小化總完工時間的重新排序問題進行了研究，對于最大序列錯位、總序列錯位和最大時間錯位下的最小化總完工時間問題給出了多項式時間算法，對于總時間錯位下的最小化總完工時間問題提出了動態規劃算法，并證明這個算法是擬多項式時間的。

本文結合生產實際情況，將學習效應模型加入到PFSP 中，建立基于學習效應的PFSP 模型，應用螢火蟲算法進行模型的求解，并將不同學習率下對應的結果進行對比，找出差距，為制造企業提供理論依據。

2 數學模型的構建

2.1 學習效應模型

本文采用Biskup[12]提出的一種與工件的加工位置有關的學習效應模型：Pjr=Pj·ra，j，r=1,2,…,n，其中，a≤0 是學習效應因子，a=lgl/lg 2，l為學習率；Pj和Pjr分別為工件的基本加工時間和實際加工時間；r為工件的加工位置。

2.2 基于學習效應的PFSP 模型

假設有n個工件在m臺機器上加工；工件的待加工序列為π(r1，r2，…，rn)，其中ri表示排序中第i個位置上待加工工件對應的工件編號；編號為ri的工件在機器j上的正常加工時間為P(ri，j)(i=1，2，…，n；j=1，2，…，m)，若每個機器有相同的學習率，則其實際加工時間為P(ri，j)·ia，其中a為學習效應因子；C(ri，j)是編號為ri的工件在機器j上的完工時間；目標函數是最小化最大完工時間（Makespan）。則基于學習效應的置換流水車間調度問題的模型為：

目標函數：

3 螢火蟲算法

3.1 算法原理

自然界的螢火蟲具有發光的特性。它們在晚上群聚時，通過散發熒光素來實現求偶、照明、警戒等信息交流活動。螢火蟲算法就是模擬螢火蟲的這一特性產生的。在螢火蟲算法中，每只螢火蟲被看做解空間的一個解，螢火蟲種群作為初始解隨機分布在目標函數的定義空間內。通過該算法中包含的亮度這一要素，將螢火蟲在解空間中的位置與目標函數值對應起來：螢火蟲越亮表示它所在的位置越好，即它所對應的目標函數值越優，從而能夠吸引亮度低的螢火蟲向自己所在的方向移動。螢火蟲算法的另一要素——吸引度，與螢火蟲自身的亮度成正比關系，亮度越大，吸引度越高，它決定螢火蟲移動的距離。算法的優化過程為：亮度高的螢火蟲吸引亮度低的螢火蟲朝自己方向移動，螢火蟲的亮度和吸引度就會不斷變化，螢火蟲的位置也相應地不斷得到更新，最終使大部分螢火蟲聚集在位置較優處，從而實現目標優化[8，13]。

3.2 數學描述

對螢火蟲算法的優化機理從數學角度有以下定義[8，13]：

定義1螢火蟲亮度的計算公式為：

其中I0為最大熒光亮度，即亮度較大的螢火蟲j自身發出的亮度，與目標函數值呈正比；γ為光強吸收系數，由于距離的增加和傳播媒介的吸收，熒光亮度會逐漸減弱，這里設置光強吸收系數來體現此特性，可以設為常數；rij表示螢火蟲i與j之間的空間距離。

定義2螢火蟲吸引度的計算公式為：

其中β0為最大吸引度，即亮度較大的螢火蟲j所在位置的吸引度；γ、rij意義同上。

定義3螢火蟲i被螢火蟲j吸引向其所在方向移動的位置更新公式為：

其中，χi、χj分別為螢火蟲i和j所處的空間位置；α為步長因子，在[0，1]范圍內取值；rand為隨機因子，在[0，1]上服從均勻分布。式中α·(rand－1/2)的作用是對螢火蟲進行隨機擾動，避免過早陷入局部最優。

3.3 算法設計

在搜索空間中，螢火蟲的位置用n維向量χi=(xi，1，xi，2，…，xi，n)表示，n個分量均由隨機方式產生。針對PFSP 問題，采用基于ROV 規則的隨機鍵編碼方式，既螢火蟲位置向量的每一個分量代表一個工件，對向量中的分量進行升序排序，通過對每個分量的位置與下標進行映射將螢火蟲的位置向量和機器上各工件的加工序列π(r1，r2，…，rn)聯系起來。

在螢火蟲位置更新過程中，考慮外界因素的影響，螢火蟲的位置向量會發生一定的交叉和變異。為了增加算法的搜索精度，在算法設計過程中增加交叉和變異操作。

3.4 算法流程

步驟1進行基本參數初始化設置，依次設置螢火蟲數目k、最大吸引度β0、光強吸收強度γ、步長因子α的取值，算法最大迭代次數maxGen，以及獨立運行次數。

步驟2初始化螢火蟲位置，計算每只螢火蟲對應的目標函數值，并將其作為螢火蟲各自的最大熒光亮度。

步驟3根據式（6）和式（7）分別計算螢火蟲的亮度和吸引度，由熒光亮度決定螢火蟲的移動方向，并更新螢火蟲位置。

步驟4對更新后的螢火蟲位置進行交叉和變異操作，并重新計算螢火蟲的相對亮度，更新最優解。

步驟5當達到最大搜索次數時轉步驟6，否則，將搜索次數增加1，轉步驟3 進行下一輪搜索。

步驟6輸出全局最優解，并將每次迭代后的最優解繪制成圖。

算法流程圖如圖1 所示。

圖1 螢火蟲算法流程圖

4 仿真測試

本文選取Car 類基準測試問題[14]來驗證螢火蟲算法的有效性，并對建立的含學習效應的PFSP 模型進行測試求解。

算法在處理器主頻2.10 GHz，物理內存2 GB，Windows 7操作系統的PC機下進行，應用MATLAB R2012a編譯軟件編碼。算法參數設置為：螢火蟲數目k=40，最大吸引度β0=1，光強吸收強度γ=1，步長因子α=0.3，最大迭代次數maxGen=300，算法獨立運行20 次。

4.1 對不含學習效應的PFSP 問題進行測試

應用螢火蟲算法對測試問題進行仿真測試，并與粒子群算法（PSO）和遺傳算法（GA）的測試結果進行對比。其中粒子群算法的粒子數為40，學習因子C1=C2=1.5，采用Wstart=0.9、Wend=0.4 的線性遞減慣性權重，最大迭代次數也為300，獨立運行20 次。遺傳算法結果取自文獻[15]。結果如表1 所示。

表1 car類問題優化結果

表1中，C*是理論最優解，SR表示尋優成功率，BRE表示最優相對誤差，ARE表示平均相對誤差。其中，BRE=(min(Cmax)-C*)/C*×100%,ARE=(avg(Cmax)-C*)/C*×100%。從測試數據可以看出，螢火蟲算法不論在尋優成功率還是在相對誤差方面性能都明顯優于粒子群算法和遺傳算法，驗證了螢火蟲算法求解PFSP問題的可行性和有效性。

根據學習因子的計算公式a=lgl/lg 2 可知，不含有學習效應的PFSP問題既是學習率為100%的PFSP問題。

4.2 對含有學習效應的PFSP 問題進行求解

行業不同，流水車間存在的學習率也不同，因此對學習效應在PFSP問題中的應用要考慮不同的學習率。當學習率l分別是90%、80%、70%、60%、50%時學習效應因子a分別是-0.152、-0.322、-0.515、-0.737、-1。在獨立運行螢火蟲算法20 次后得到的優化結果如表2 所示。

表2 含學習效應的Car類問題優化結果

圖2 優化結果的線性擬合情況

4.3 結果分析

（1）擬合分析

對Car 類問題在不同學習率下的優化結果進行線性擬合（圖2），從圖2 中可以看出，隨著學習率的降低，各測試問題目標函數值的減小趨勢均十分明顯。因此在PFSP 問題中加入學習效應后，工件的最小化最大完工時間縮短，并隨著學習效果的增強，最小化最大完工時間呈明顯的減小趨勢。

（2）敏感性分析

敏感性分析是一種定量描述模型輸入變量對輸出變量的重要性程度的方法。敏感度系數是敏感性分析的評價指標，它是目標值變化的百分率與敏感因素變化的百分率之比，計算公式為：

式中，SAF為評價指標A對于不確定因素F的敏感度系數；ΔF/F為不確定因素F 的變化率；ΔA/A為不確定因素F發生ΔF變化時，評價指標A的相對變化率。SAF＞0 表示評價指標與不確定因素同方向變化；SAF＜0表示評價指標與不確定因素反方向變化。|SAF|越大表明評價指標A對于不確定性因素F越敏感；反之則不敏感[16]。

本文采用敏感性分析來定量地研究學習效應對目標函數值的影響程度。根據公式（9）計算學習率的敏感度系數，匯總于表3 中。由表3 可以看出，除了在敏感因素變化率為-50% 時，Car7 對應的敏感度系數0.94 小于1 外，其余所有Car 問題在不同學習率下的敏感性系數均大于1，其中部分敏感度系數大于2，這說明：學習率與目標函數值同方向變化，學習率越低，學習效果越明顯；學習率每變化1%，目標函數值將變化1%以上，從而得出結論——學習率屬較敏感的因素。

綜上可知，學習效應對PFSP的目標函數值有很大影響，企業在實際生產中考慮學習效應的存在是十分必要的。

表3 學習率敏感度系數表

5 結束語

本文通過測試和分析，在驗證了螢火蟲算法求解PFSP 問題具有可行性和有效性的基礎上，得出結論：學習率是影響工件加工完成時間的一個較敏感因素；由于學習效應的存在，批量生產的工件的最小化最大完工時間會比理論值小，且學習效果越好，實際值與理論值差距越明顯。因此企業在安排生產計劃時考慮學習效應這一影響總完工時間的因素，可以使預測的結果更接近實際情況，制定出更加合理準確的生產計劃，從而促進生產力的提升。本文只針對學習效應在PFSP 中的應用問題進行了研究，鑒于生產調度的多樣性，基于學習效應的生產調度問題還有待作進一步研究。

[1] 劉延風，劉三陽.基于混合電磁算法求解置換流水車間調度問題[J].系統仿真學報，2012，24（3）：603-607.

[2] Garey M R，Johnson D S，Sethi R.The complexity of flow-shop and job-shop scheduling[J].Mathematics of Operations Research，1976，1（2）：117-129.

[3] 張其亮，陳永生，韓斌.改進的粒子群算法求解置換流水車間調度問題[J].計算機應用，2012，32（4）：1022-1024.

[4] Yang X S.Nature-inspired metaheuristic algothms[M].UK，Beckington：Luniver Press，2008：83-96.

[5] Yang X S.Firefly algorithms for multimodal optimization[J].Lecture Notes in Computer Sciences，2009，5792：169-178.

[6] 劉長平，葉春明.置換流水車間調度問題的螢火蟲算法求解[J].工業工程與管理，2012，17（3）：56-59.

[7] 楊嬌，葉春明.應用新型螢火蟲算法求解Job-shop 調度問題[J/OL].計算機工程與應用，http：//www.cnki.net/kcms/detail/11.2127.TP.20120907.1626.017.html.

[8] 周季華，葉春明.應用螢火蟲算法求解置換流水線問題[J].計算機應用研究，2013，30（1）：152-154.

[9] 孫林輝，王丹，王吉波.具有學習效應的總完工時間流水作業問題[J].系統管理學報，2011，20（1）：114-118.

[10] Wright T P.Factors affecting the cost of airplanes[J].Journal of Aeronautical Sciences，1936（3）：122-128.

[11] 張新功.具有學習效應的重新排序問題[J].重慶師范大學學報，2012，29（1）：1-6.

[12] Biskup D.Single-machine scheduling with learning considerations[J].European Journal of Operational Research，1999，115（1）：173-178.

[13] 劉長平，葉春明.一種新穎的仿生群智能優化算法：螢火蟲算法[J].計算機應用研究，2011，28（9）：3295-3297.

[14] 王凌.智能優化算法及其應用研究[M].北京：清華大學出版社，2001：195-196.

[15] 王凌.車間調度及其遺傳算法[M].北京：清華大學出版社，2003：118-121.

[16] 成其謙.投資項目評價[M].北京：中國人民大學出版社，2010：120-126.