混合流水車間調度問題的IPSO算法

李　解　任魏翔　秦永彬

(貴州大學計算機科學與技術學院　貴陽　550025)

混合流水車間調度問題的IPSO算法

李解任魏翔秦永彬

(貴州大學計算機科學與技術學院貴陽550025)

摘要混合流水車間調度問題又稱柔性流水車間調度問題,廣泛存在于現代工業之中。它是對傳統流水車間的擴展。其中,每道工序可能有多臺機器負責處理。針對混合流水車間調度問題,論文以最小化最大完成時間為目標建立整數規劃模型,將經典粒子群優化算法進行改進,并同教與學算法(Teaching-Learning Based Optimation,TLBO)相結合,提出了一種用于解決該問題的改進的粒子群算法(Improved Particle Swam Optical Algorithm,IPSO)。算法在產生初始種群的過程中,首先將原問題轉化為一系列置換流水車間調度問題,并求得其解。之后,將得到的解作為初始種群的一部分。由于現有的粒子群算法具有易收斂于局部最優解的缺點。因此為防止算法收斂于局部最優解,引入變異操作。此外,在粒子群優化算法的基礎上引入適用于求解混合流水車間的TLBO算法的老師階段和學生階段。設計正交試驗對算法參數設置進行分析,并確定了較優的參數組合。通過基于算例的仿真實驗,并與現有的解決混合流水車間調度問題的算法進行比較,驗證所提出IPSO算法是有效的。

關鍵詞流水車間調度; 粒子群算法; TLBO; IPSO; 最大完成時間

Class NumberTP312

1引言

混合流水車間調度問題是置換流水車間調度問題的擴展。混合流水車間由一系列生產階段組成。其中,至少一個階段包括多臺并行機器。每個待處理任務包含相同的工序,并且每個任務工序順序相同。任務的每道工序只由相應生產階段中的一臺機器處理。混合流水車間調度問題作為置換流水車間調度問題的擴展,其研究成果不僅應用于電子[1]、汽車[2]等制造行業,而且在實時圖像分析技術[3]等計算機領域的前沿發揮了重要作用。由于具有兩個生產階段,第一個生產階段機器數為1,第二個生產階段機器數為2的混合流水車間調度問題已是強NP-hard[4]。因此,在問題規模增加的情況下,合理的時間內已無法精確求得條件更為復雜的混合流水車間調度問題的最優解。Wittrock[5]首次提出以最小化最大完成時間為目標且生產階段數大于3的混合流水車間調度問題,并為該問題提出了一種分支定界算法。為更加有效地得到該類問題的近似解,并且使其更接近于最優解蟻群算法[6]、模擬退火算法[7]、禁忌搜索[8]等智能優化算法及其混合算法[9～10]被用于混合流水車間調度問題。其中,蟻群算法通過模擬蟻群搜索食物求解調度問題。該算法的并行性高且不易收斂于局部最優解。但是由于蟻群算法相對復雜。因此,該算法的收斂速度慢。模擬退火算法來源于固體有高溫降溫至常溫過程中分子由無序狀態到基態的物理原理。該算法能夠搜索到較接近于最優解的近似解,并且易于實現。但是模擬退火算法對參數的選擇較敏感,且對問題的解搜索速度慢。禁忌搜索算法是一種模擬人類思考過程中的記憶功能避免對問題的一些解的迂回搜索的算法。該算法的運行結果對初始解具有較強的依賴性。與以上智能優化算法不同的是,粒子群算法具有簡潔性、易實現以及快速收斂性等優點。但是該算法在已陷入局部最優,并且其理論基礎不完善。因此,該算法仍存在大量的研究空間。

粒子群優化(Particle Swarm Optimization,PSO)算法最早是為解決連續非線性函數而提出的一種智能優化算法[11]。該算法通過模擬鳥群等動物群體的遷移活動來解決各種優化問題。現階段對PSO算法的改進主要集中在與其他算法相結合、改進編碼方式,利用其他算法的解作為初始種群的一部分等方面。

教與學優化算法(Teaching and Learning Based Optimation,TLBO)來源于學校教學過程中老師對學生的教與學過程以及學生之間的相互學習過程。在教學過程中,老師通過教學提升學生的知識水平。同時,學生之間能夠通過相互學習來提高自身的知識水平。教與學算法首先在文獻[12]中被提出,并且成功地應用于求解優化問題。教與學算法被提出以來已經成功地運用于各種優化問題之中。

本文針對混合流水車間調度問題,提出一種新的初始種群產生方法,并引入變異操作,并引入教與學優化算法中適用于求解混合流水車間調度問題的老師階段和學生階段,從而提出一種改進的粒子群優化算法(Improved Particle Swam Optimization Algorithm,IPSO)。通過仿真實驗驗證所提出算法能夠在合理的時間內得到混合流水車間調度問題較優的近似解。

2問題描述

具有m(m≥2)階段混合流水車間調度問題描述如下:生產系統所包括生產階段數為m(m≥2),各生產階段由多臺具有相同加工功能且性能不一定相同的并行機器組成。n個待加工工件在生產系統中按照相同的工序順序進行加工,并且不同工件在相同機器上的處理時間相互獨立。工件的第r(r=1,2,…,m)道工序只能由第r個生產階段的并行機器中的一臺機器處理。問題的優化目標:對待處理工件排序并為各工件分配機器,使得生產系統處理完成所有工件的最大完成時間最小。該調度問題以文獻[13]所提出的三元組α|β|γ方式可以表示為F(k1,k2,…,km)‖Cmax。其中,第一部分F(k1,k2,…,km)表明該問題的機器環境是具有r個階段,每個階段具有ki(i=1,2,…,m)臺并行機器的混合流水車間;第二部分描述與任務相關的特征和約束,此處為空表示沒有相應的約束限制;第三部分Cmax描述問題的優化目標為最小化最大完成時間。

基于以上描述,問題目標為:確定負責處理所有待處理任務的各道工序的機器以及各臺機器處理任務的順序,即調度S,使得最大完成時間Cmax最小。由于每個工件工序順序相同,并且同一生產階段上的機器性能不一定相同。所以,Cmax為調度S中所有任務在第m個階段的完成時間的最大值,即maxCjm(j=1,2,…,n)。

3數學模型

假設生產系統需要處理n個工件,各工件的處理包括順序相同的m道工序。生產系統中第r個生產階段負責處理工件的第r道工序,并且該生產階段上機器數為kr。工件的每道工序由相應生產階段上的一臺機器進行處理。

基于以上假設、問題描述以及相關符號說明,可以將F(k1,k2,…,km)‖Cmax混合流水車間調度問題轉換為如下整數規劃問題:

min max{Cjm}

(1)

(2)

(3)

(4)

(5)

xijhr,xi0hr,x0jhr,xjhr∈{0,1}

(6)

其中,i=1,2,…,n;j=1,2,…,n;h=1,…,kr;r=1,2,…,m。

整數規劃問題的目標為min max{Cjm},即最小化最大完成時間。

約束(1)確保每個任務的每道工序只能由一臺機器進行處理,約束(2)確保每臺機器同一時刻只能處理一個工件,約束(3)確保任何一臺機器上處理的每一個任務最多只能有一個前趨任務、約束(4)用于計算任務的完成時間、約束(5)確保每個工件的工序順序相同;約束(6)為4個指示變量,每個變量取值涵義如下:

4IPSO算法

粒子群優化算法模擬捕食行為的一種進化算法。其在執行過程中保存了若干個可行解,每個可行解稱為一個粒子,若干個粒子構成一個種群。算法在執行的過程中,各粒子通過不斷調整各自的速度和位置信息向問題的最優解移動。為防止粒子群算法在執行過程中陷入局部最優解,本文在標準粒子群算法的基礎上引入變異操作。

4.1粒子的編碼

4.2種群初始化

在算法的第一次迭代之前,產生初始種群。本文所設計算法的初始種群由三部分組成。假設算種群規模為popsize。初始種群的第一部分為原問題轉化而成的Fm|(perm)|Cmax調度問題的解。第二部分為將原問題轉換為m-1個F2|(perm)|Cmax問題的解。第三部分的初始解以均勻分布隨機生成popsize-m個解。

初始種群的剩余部分以均勻分布隨機生成。

4.3粒子速度和位置的更新

粒子群算法在執行過程中,各個粒子通過各自的局部最優解以及全局最優解更新自身的速度和位置信息,向問題的最優解的位置靠近。傳統的粒子群算法中粒子的位置和速度更新公式如下

v(t+1)=ω×v(t)+c1×r1×(p(t)-x(t))

+c2×r2×(g(t)-x(t))x(t+1)

=x(t)+v(t+1)

其中,ω為慣性因子;v(t+1)為該粒子在算法的第t+1次迭代的速度;x(t+1)為粒子在算法的第t+1次的位置;c1為局部最優解對速度更新影響的權重;c2為全局最優解對速度更新影響的權重;r1、r2為0～1之間的隨機數;p(t)為粒子在算法的第t次迭代的局部最優解;g(t)為算法第t次迭代的全局最優解。

但是由于F(k1,k2,k3,…,km)‖Cmax問題解的采用矩陣方式進行編碼,所以以上粒子速度和位置的更新方法已不適用。基于以上原因,本文采用另一種方式對粒子速度和位置進行更新。對粒子的速度隨機地進行交換方式或者插入方式的更新。將各粒子與全局最優解或者局部最優解進行交叉操作來更新粒子的位置信息。

粒子以交換方式或者插入方式進行速度更新的具體過程如圖1、圖2所示:在當前解的矩陣中隨機選取兩行。粒子若以交換方式進行速度更新,則將隨機選取的兩行的內容進行交換。粒子若以插入方式進行更新,則將其中一行插入到另外一行之前。

圖1　交換方式更新速度

圖2　插入方式更新速度

粒子以交叉操作進行位置更新的具體過程為:在當前解中隨機選取兩個交叉點i,j(1≤i

4.4變異

為防種群中粒子的多樣性降低,從而造成算法的早熟收斂,對進入局部最優的粒子進行變異操作。本文算法首先判斷在最近的若干次迭代中各個粒子的局部最優解是否發生變化。若存在局部最優解沒有變化的粒子,則認為算法陷入局部最優解并對該粒子進行變異操作。

執行變異操作的粒子隨機選擇某一工件,并以均勻概率分布將負責處理該工件各道工序的機器改為生產系統中相應生產階段的其他機器。

4.5老師階段

教與學算法的老師階段中,老師通過教授學生知識來提高學生的知識水平或者成績,使學生的知識水平或成績接近于老師的知識水平或成績。算法在老師階段的執行過程中如下:

1) 在粒子群中選擇若干適應值最高的粒子作為老師,其他的粒子作為老師。

2) 被選為老師之外的每個粒子,隨機選擇一個老師,與其進行交叉操作。采用交換方式進行交叉操作。

3) 若交叉結果對應的適應值優于交叉之前的適應值,那么更新當前粒子為交叉所得的結果。

4.6學生階段

該階段的執行過程中,每個學生通過同學之間的相互學習來提高自身的知識水平或者成績。算法在學生階段的執行過程:每個學生選擇高于其適應值的學生進行交叉操作,并更新當前學生粒子為交叉結果。

4.7終止條件

當算法迭代次數達到指定值后,算法停止運算,并輸出結果。

4.8IPSO算法的具體步驟

IPSO算法:

Input:P,PT//PT為各個生產階段包含的機器的數量

Output:S,Cmax

Begin:

Step1初始化算法最大迭代次數eranum、慣性系數InertiaCoef、學習系數LearnCoef、種群規模popsize,目標值未改變的次數unchangedTimes等參數。

Step2產生粒子數量為popsize的初始種群。在3維矩陣Schedule中記錄初始種群中每個粒子的編碼矩陣。在矩陣ValForGB中記錄種群的全局最優值,并用矩陣GB記錄全局最優值對應的矩陣編碼。在矩陣ValForPB中記錄各粒子的局部最優值,并在矩陣PB中記錄局部最優值對應的矩陣編碼。

Step3如果算法迭代次數小于最大遺傳代數eranum,則轉Step4,否則,轉Step7

Step4種群Schedule中每個粒子以概率InertiaCoef更新速度,以概率LearnCoef更新根據局部最優值ValForPB更新位置,或者根據全局最優值ValForGB更新位置信息。計算更新后各個粒子對應的目標函數值,并將計算結果存入矩陣ValForSchedule中。

Step5如果ValForSchedule中最小值小于ValForGB中的值,則更新ValForGB為ValForSchedule中的最小值,同時更新GB為ValForSchedule中的最小值對應的編碼矩陣;否則,不更新GB和ValForGB。如果粒子更新后對應的目標函數值小于其局部最優值,則更新該粒子局部最優值ValForPB為當前粒子對應的目標函數值,同時更新PB為當前粒子對應的編碼矩陣。

Step6在Schedule中選擇對應ValForSchedule值最小的若干個粒子作為老師teacherSchedule。

Step7對于每個粒子,在teacherSchedule中隨機選擇一個粒子作為老師,并與其進行交叉操作。若交叉結果的適應值優于當前粒子的適應值,則更新當前粒子為交叉結果。

Step8對于每個粒子,隨機選擇種群中的另外一個適應值更高的粒子,并與其進行交叉操作。更新當前粒子為交叉操作所得的結果。

Step9計算各個粒子對應目標函數值連續未改變的算法迭代次數。若未改變的算法迭代次數超過unchangedTimes的值,則對該粒子進行變異操作;否則,不進行變異。轉Step3。

Step10輸出GB和ValForGB,算法結束運行。

End

5實驗設計與結果

5.1實驗設計

本文提出的算法在Matlab 2014環境下實現,并運行于在CPU為Inter Core 3.20GHz的計算機。為確定算法中種群規模、學習因子、慣性因子等參數的取值,利用文獻[14]中實例的數據設計因子數為3,因子取值水平數為4,參數組合數為16,即規模為L16(43)的正交試驗。正交試驗中各個任務的加工時間如表1所示。其中每個參數取值即正交試驗的因子取值包括三個水平,如表2所示。每種參數組合各進行30次試驗,并計算目標函數的平均值。算法最大迭代次數為1000次。正交試驗的結果如表3所示。

表1　正交試驗中各個任務的加工時間

表2　算法參數取值水平

表3　正交試驗具體結果

表4　各參數取值水平的影響

由正交試驗的具體結果可得出種群規模、學習因子、慣性因子這三個參數的不同取值水平對算法的影響,如表4所示。通過觀察各參數不同取值水平對目標值的影響,發現當種群規模、學習因子、慣性因子取值水平分別為150、0.2、0.5時,所對應的目標函數值最小。因此,設定算法的種群規模為150,學習因子為0.2,慣性因子為0.5。

本文選取文獻[15]和文獻[16]的不同規模的測試數據驗證本文提出算法的有效性。第1組實驗數據包括12個任務,4個生產階段。其中,每個生產階段分別包括3臺、3臺、2臺、2臺并行機器。各個任務在每道工序中的每臺機器上的加工時間如表5所示。第2組實驗數據的任務數為12,生產階段數為3,機器數為8,。其中第1個生產階段包括3臺機器,第2個生產階段的包括3臺機器,第三個生產階段包括2臺機器。各個任務在每臺機器上處理所需時間如表6所示。

表5　第1組實驗任務處理時間數據

表6　第2組實驗任務處理時間數據

5.2實驗結果與分析

利用所提出算法求解分別第1組實驗實例和第2組實驗實例各10次,實驗結果如表7和表8所示。

表7　第1組實驗結果

表8　第2組實驗結果比較

本文提出算法10次運算第1組實驗實例的最優解為302,最差解為320。而文獻[15]所提出方法所得最優結果為347。基于以上分析,本文提出算法優于文獻[15]提出的方法。

通過對表8中數據的分析可得,文獻[16]的算法最優解為14,本文提出算法的最優解為12。并且本文所提算法每次運算結果均優于文獻[16]中算法的結果。因此,所提出IPSO算法優于文獻[16]所提出的方法。

6結語

本文在研究混合流水車間調度問題的基礎上,將粒子群優化算法和教育學優化算法相結合,提出了用于求解該類問題的IPSO算法。初始解產生過程中,將原問題轉換為Fm|(perm)|Cmax以及多個F2|(perm)|Cmax流水車間調度問題,并將所轉換問題的解作為初始解的一部分。通過正交試驗設置合適的算法參數。設計仿真實驗并與已有的文獻中計算結果進行比較。仿真實驗的結果表明,本文所提出的IPSO算法能求得混合流水車間相對較優的近似解。

下一步的研究方向:改進所提出的算法或提出更為高效的算法用于求解具有隨機故障的混合流水車間調度問題。

參 考 文 獻

[1] Kurz M E, Askin R G. Scheduling flexible flow lines with sequence-dependent setup times[J]. European Journal of Operational Research,2004,159(1):66-82.

[2] Wilson J M. Henry Ford vs. assembly line balancing[J]. International Journal of Production Research,2014,52(3):757-765.

[3] Ercan M F, Fung Y F. Real-time image interpretation on a multi-layer architecture[C]//TENCON 99. Proceedings of the IEEE Region 10 Conference. IEEE,1999,2:1303-1306.

[4] Hoogeveen J A, Lenstra J K, Veltman B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard[J]. European Journal of Operational Research,1996,89(1):172-175.

[5] Wittrock R J. Scheduling algorithms for flexible flow lines[J]. IBM Journal of Research and Development,1985,29(4):401-412.

[6] Sioud A, Gagné C, Gravel M. An ant colony optimization for solving a hybrid flexible flowshop[C]//Proceedings of the 2014 conference companion on Genetic and evolutionary computation companion. ACM,2014:17-18.

[7] Mirsanei H S, Zandieh M, Moayed M J, et al. A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times[J]. Journal of Intelligent Manufacturing,2011,22(6):965-978.

[8] Shahvari O, Salmasi N, Logendran R, et al. An efficient tabu search algorithm for flexible flow shop sequence-dependent group scheduling problems[J]. International Journal of Production Research,2012,50(15):4237-4254.

[9] Niu Q, Zhou T, Ma S. A Quantum-Inspired Immune Algorithm for Hybrid Flow Shop with Makespan Criterion[J]. J. UCS,2009,15(4):765-785.

[10] Janiak A, Kozan E, Lichtenstein M, et al. Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion[J]. International Journal of Production Economics,2007,105(2):407-424.

[11] Eberhart R C, Kennedy J. A new optimizer using particle swarm theory[C]//Proceedings of the sixth international symposium on micro machine and human science,1995,1:39-43.

[12] Rao R V, Savsani V J, Vakharia D P. Teaching-learning-based optimization: a novel method for constrained mechanical design optimization problems[J]. Computer-Aided Design,2011,43(3):303-315.

[13] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics,1979,5:287-326.

[14] 周輝仁,唐萬生,魏穎輝.柔性Flow Shop調度的遺傳算法優化[J].計算機工程與應用,2009,45(30):224-226.

ZHOU Renhui, TANG Wansheng, WEI Yinghui. Genetic algorithm optimization of flexible Flow Shop scheduling[J]. Computer Engineering and Applications,2009,45(30):224-226.

[15] 崔建雙,李鐵克,張文新.混合流水車間調度模型及其遺傳算法[J].北京科技大學學報,2005,27(5):623-626.

CUI Jianshuang, LI Tieke, ZHANG Wenxin. Hybrid flow shop scheduling model and genetic algorithm[J]. Journal of University of Science and Technology Beijing,2005,27(5):623-626.

[16] 董婷婷.基于遺傳算法的混合流水車間調度問題研究[D].阜新:遼寧工程技術大學,2008.DONG Tingting. The Study Based on the Genetic Algorithm of Hybrid Flow Shop Scheduling Problem[D]. Fuxin: Liaoning Technical University,2008.

Improved Particle Swam Optimization Algorithm for Hybrid Flow Shop Scheduling

LI JieREN WeixiangQIN Yongbin

(College of Computer Science and Technology, Guizhou University, Guiyang550025)

AbstractFor the hybrid flow shop scheduling problem which aims to minimize makespan, an integer program model is established. The improved particle swarm optimization algorithm with a new method of generating initial population, which is based on the study of classic particle swarm optimization algorithm, is presented. The new method transforms the hybrid flow shop scheduling problem into m-machine permutation flow shop scheduling problem. Parts of initial solutions consist of the transformed scheduling problem solution. The teacher phase and student phase of TLBO for solving hybrid flow shop scheduling problem is introduced into the proposed algorithm. The phenomenon that the particle converging on local optimum is avoided by mutation operation. Suitable parameters are suggested by perpendicular experiments on influence of parameter setting. Simulation experiments and comparisons with existing algorithms show the presented algorithm is effective.

Key Wordsflow shop, particle swarm optimization, teaching-learning based optimization, improved particle swarm optical algorithm, makespan

收稿日期:2015年12月4日,修回日期:2016年1月19日

基金項目:國家自然科學基金(編號:61262006,61540050);貴州省重大應用基礎研究項目(編號:黔科合JZ字[2014]2001);貴州省科技廳聯合基金(編號:黔科合LH字[2014]7636號);貴州大學研究生創新基金(編號:研理工2015012)資助。

作者簡介:李解,女,碩士,研究方向:算法設計與分析。任魏翔,男,碩士,研究方向:算法設計與分析。秦永彬,男,副教授,碩士生導師,研究方向:智慧計算與智能計算、大數據管理與應用等。

中圖分類號TP312

DOI:10.3969/j.issn.1672-9722.2016.06.001