應用強化學習算法求解置換流水車間調度問題①

張東陽,葉春明

(上海理工大學 管理學院,上海 200093)

1 引言

排序問題是生產系統和服務系統中的一類典型問題,它作為傳統問題和熱點問題,至今一直有眾多學者研究.根據工件的不同加工特點,排序問題可分為流水作業排序(flow-shop scheduling)、自由作業排序(openshop scheduling)和異序作業排序(job-shop scheduling)[1],其中Flow-shop排序又可分為同順序和任意序兩大類,同順序Flow-shop排序問題又稱置換流水車間調度問題(Permutation Flow Shop Problem,PFSP).相關理論證明,3臺機器以上的PFSP即為NP難題[2],至今還未發現具有多項式時間的優化算法.

目前,解決這類問題有效方法主要包括：精確算法,啟發式算法,智能優化算法.如枚舉法、分支定界法等精確算法只對小規模問題的求解有著很好的效果.如Gupta法、RA法和NEH法等啟發式算法可以求解快速構造問題的解,但是解的質量較差[3].近年來,遺傳算法[4]、人工神經網絡[5]、蟻群算法[6]、粒子群算法[7],煙花算法[8]、進化算法[9]等智能優化算法因能在合理的時間內獲得較優解,受到了眾多學者的廣泛研究,并已經成為解決該類問題的重要方法.

近年來,隨著技術的進步,機器學習領域里一個古老又嶄新的理論——強化學習[10,11],又得到了科研人員的廣泛重視.但目前強化學習主要應用在游戲比賽、控制系統和機器人等領域[12-14],應用在生產調度中的并不多.Wang等學者將Q-學習算法應用到單機作業排序問題上,發現智能體經過學習能夠從給定的規則中選出較好的規則,證明了將強化學習應用到生產調度的可能性和有效性[15,16].Zhang等學者利用多智能協作機制解決了非置換流水車間調度問題[17],國內的潘燕春等學者將Q-學習算法與遺傳算法有機的結合起來,在作業車間調度取得較好的效果[18,19].王超等學者提出了改進的Q-學習算法運用于動態車間調度,構建了一系列符合強化學習標準的規則[20].可以看到,過往的文獻里面強化學習應用在調度上大部分是多智能體協作,或者與其它算法結合去解決調度問題.因此,本文用單智能體的強化學習來解決置換流水車間調度問題,合理的將狀態定義為作業序列,將動作定義為機器前可選加工的工件,來適應強化學習方法.智能體通過與環境不斷交互,學習一個動作值函數,該函數給出智能體在每個狀態下執行不同動作帶來的獎賞,伴隨函數值更新,進而影響到行為選擇策略,從而找到最小化最大完工時的狀態序列.最后用該算法對OR-Library提供Flow-shop國際標準算例進行仿真實驗分析,最終的實驗結果驗證了算法的有效性.

2 置換流水車間調度問題描述

置換流水車間調度可以描述為[21,22]：n個工件要在m個機器上加工,每個工件的加工順序相同,每一臺機器加工的工件的順序也相同,各工件在各機器上的加工時間已知,要求找到一個加工方案使得調度的目標最優.本文選取最小化最大加工時間為目標的調度問題.對該問題常作出以下假設：

1)一個工件在同一時刻只能在一臺機器上工；

2)一臺機器在同一時刻智能加工一個工件；

3)工件一旦在機器上加工就不能停止；

4)每臺機器上的工件加工順序相同.

問題的數學描述如下,假設各工件按機器1到m的順序加工,令 π ={π1,π2,···,πn}為所有工件的一個排序.pij為工件i在機器上j的加工時間,不考慮所有工件準備時間,C(πi,j)為工件 πi在機器j上加工完成時間.

其中,式(1)中的i=2,···,n；j=2,···,n,式(2)為最大完工時間.

3 強化學習理論

強化學習是人工智能領域中機器學習的關鍵技術,不同于監督學習和無監督學習,主要特點在于與環境交互,具有很強的自適應能力,具有實時學習的能力.強化學習的目標是在與環境的試探性交互中學習行為策略,來獲取最大的長期獎賞[23].圖1描述了強化學習的過程,強化學習最主要的是兩個主體,分別為智能體和智能體所處的環境,環境意味著多樣的復雜狀態,所有的狀態可以看成一個集合S.當智能體接受到t時刻的狀態st(st∈S)以及從上一個狀態st-1轉變成st所得到的瞬時獎勵rt,智能體從可選的行為集合A中選取一個動作at來執行,這樣環境狀態就轉移為st+1,同時智能體接受來自于環境狀態改變瞬時獎勵rt+1和t+ 1時刻的狀態st+1,根據從中學習到的經驗,來決策t+ 1時刻的動作at+1.按此循環,智能通過不斷與環境交互,根據學習到的策略,不斷嘗試并調整自身的行為,來獲取最大的長期獎賞.

圖1 強化學習模型

強化學習的算法可以分為2類,一類是基于模型已知的動態規劃法,一類是基于模型未知的算法如蒙特卡洛算法、Q-Learning算法、TD算法等.本文采用的Q-Learning算法來解決問題.算法的核心是一個簡單的值迭代更新,每個狀態動作對都有一個Q值關聯,當智能體處在t時刻的狀態st選擇操作at時,該狀態動作對的Q值將根據選擇該操作時收到的獎勵和后續狀態的最佳Q值進行更新.狀態操作對的更新規則如下：

式(3)中,表示學習率,學習率越大,表明立即獎賞和未來獎賞對當前的影響較大,智能體越能看到未來的結果,但收斂速度會比較慢,表示折扣因子,代表決策者對得到的獎賞的偏好,折扣因子越大,智能體越有遠見,即考慮當前的選擇對未來的結果造成的影響.已經證明,在馬爾科夫決策過程中,在某些限制條件下,QL能夠收斂到最優值[24].QL算法更新過程如算法1所示.

算法1.QL算法初始化Q值for each episode：初始化狀態s for each episode step：在t時刻下狀態 的所有可能行為中選取一個行為images/BZ_201_511_1487_536_1512.png images/BZ_201_1002_1487_1027_1512.png執行動作,得到下一狀態images/BZ_201_660_1531_710_1565.png和獎賞值更新Q值：[()]images/BZ_201_418_1540_443_1565.png images/BZ_201_843_1540_864_1565.pngimages/BZ_201_366_1649_1108_1699.pngimages/BZ_201_285_1720_385_1745.pngend for end for

算法中的智能體有2種不同動作選擇策略：探索和利用,而 ε-貪心行動值法是智能體選擇動作的常用的策略,以較大概率(1 -ε)選擇完全貪婪行動,以較小概率(貪婪率)ε隨機選擇行動[10].ε越小越重于利用,即利用現有的學習成果來選取行動,ε越大越重于探索,即隨機選取行動.

4 Q-Learning在PFSP上的應用

利用強化學習解決PFSP問題,最重要是如何將問題映射到強化學習模型中,并利用相關算法來得到優化的策略結果.本文構建了環境中的狀態集,動作和反饋函數,并采用QL算法來進行優化.

定義1.狀態集.將n×m的PFSP問題中m個機器中的第一個機器當作智能體,將第一臺機器前的未加工的工件作為環(境狀)態.根據文獻[25],智能體的狀態可以設定為Si=Ari,每個智能體(i)都有|Si|=2n(n表示工件數)狀態.在我們的案例中只有一個智能體,因此,所有狀態的集合為 |S|=2n,表示為S={s1,s2,···,sn2}.

定義2.動作集.將智能體前可以選擇加工的工件作為可選的動作.因此,在我們的案例中可選擇的動作集為A={a1,a2,···,an}.

定義3.反饋函數.我們選取最小化最大完工時間作為獎勵信號,最小化最大完工時間越小,獎勵值越大,意味著選取的動作也好,函數表示如下：

根據上述的定義,將PFSP問題映射到QL算法中,具體描述如算法2所示.

算法2.QL解決PFSP問題算法初始化：Q(s,a)={}Best={}for each episode step：初始化狀態s={}while not finished(所有工件)：初始化所有動作值根據狀態s利用貪心行動值法來選擇動作執行動作,得到下一個狀態st+1和獎賞值r(1/makespan)更新Q(s,a)[()]images/BZ_201_1439_1684_2180_1734.pngimages/BZ_201_1365_1755_1457_1780.pngimages/BZ_201_1357_1909_1457_1934.pngend while if makespan(s)< makespan(Best)：end for

5 實驗結果分析

為驗證QL算法解決置換流水車間問題的性能,選擇OR-Library中Carl類例題,21個Reeves例題來進行測試,將實驗結果與一些算法進行比較.算法程序用Python3.0編寫,運行環境為Windows 7 64位系統,處理器為2.60 GHz,4 GB內存.經過初步實驗,分析了不同學習參數對學習的影響,最后確定了相關參數,迭代次數為5000,學習率為0.1,折扣因子為0.8,貪婪率為0.2.以相對誤差率RE=(C-C*)/C*×100%,平均誤差率ARE=(Ca-C*)/C*×100%和最優誤差率BRE=(Cbest-C*)/C*×100%為比較標準,每個例題運行20次.其中C為算法運行的結果,C*為算列的最優值.Ca,Cbest分別為所求解的平均值和最優值.

選擇Car類例題與文獻[25]提到的螢火蟲算法(FA)、粒子群算法(PSO)、啟發式算法NEH來進行比較.從表1和圖2中我們可以看出,QL算法在Car類算例中基本能找到最優值,與PSO,FA等智能算法尋優效果上相差不大,而啟發式算法NEH求解算例最優的效果一般,只適用于對精度要求不高的場合.在算例的平均誤差上,QL算法求解質量優于PSO算法,和FA算法不相上下,展現了QL算法的良好穩定性.說明QL算法對置換流水車間調度問題有較好的尋優能力.

表1 Car類問題測試結果

圖2 平均值比較

選取算例Car4算例來分析QL算法的收斂能力,從圖3中發現QL算法剛開始下降較快,在中間一段時間內雖然兩次陷入了局部最優值,但最后都成功跳出了局部最優,達到最優值.

圖3 算例Car4最優值下降曲線圖

表2給出了QL算法對Reeves例題(Rec37、Rec39、Rec41 3個算例的值不是最優值,而是最優上界).測試結果,并與PSO[25],GA[26]等知名算法比較,QL算法的平均最優值最小,表明整體上QL算法的尋優能力比GA和PSO算法都好.

表2 Reeves例題BRE測試結果

6 結束語

面對日益增長的大規模調度問題,開發新型算法越來越重要.本文提出了基于QL算法解決置換流水車間調度問題的算法,通過對Car算例和Reeves算例等基準問題進行測試并與已有的算法進行比較,評價了該算法的有效性.結果表明,該方法是解決置換流水車間調度問題的一種有效的方法.