杜 貞，葉春明，凌遠(yuǎn)雄

DU Zhen,YE Chunming,LING Yuanxiong

上海理工大學(xué) 管理學(xué)院，上海200093

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

1 引言

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

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

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

本文結(jié)合生產(chǎn)實(shí)際情況，將學(xué)習(xí)效應(yīng)模型加入到PFSP 中，建立基于學(xué)習(xí)效應(yīng)的PFSP 模型，應(yīng)用螢火蟲算法進(jìn)行模型的求解，并將不同學(xué)習(xí)率下對(duì)應(yīng)的結(jié)果進(jìn)行對(duì)比，找出差距，為制造企業(yè)提供理論依據(jù)。

2 數(shù)學(xué)模型的構(gòu)建

2.1 學(xué)習(xí)效應(yīng)模型

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

2.2 基于學(xué)習(xí)效應(yīng)的PFSP 模型

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

目標(biāo)函數(shù)：

3 螢火蟲算法

3.1 算法原理

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

3.2 數(shù)學(xué)描述

對(duì)螢火蟲算法的優(yōu)化機(jī)理從數(shù)學(xué)角度有以下定義[8，13]：

定義1螢火蟲亮度的計(jì)算公式為：

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

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

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

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

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

3.3 算法設(shè)計(jì)

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

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

3.4 算法流程

步驟1進(jìn)行基本參數(shù)初始化設(shè)置，依次設(shè)置螢火蟲數(shù)目k、最大吸引度β0、光強(qiáng)吸收強(qiáng)度γ、步長因子α的取值，算法最大迭代次數(shù)maxGen，以及獨(dú)立運(yùn)行次數(shù)。

步驟2初始化螢火蟲位置，計(jì)算每只螢火蟲對(duì)應(yīng)的目標(biāo)函數(shù)值，并將其作為螢火蟲各自的最大熒光亮度。

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

步驟4對(duì)更新后的螢火蟲位置進(jìn)行交叉和變異操作，并重新計(jì)算螢火蟲的相對(duì)亮度，更新最優(yōu)解。

步驟5當(dāng)達(dá)到最大搜索次數(shù)時(shí)轉(zhuǎn)步驟6，否則，將搜索次數(shù)增加1，轉(zhuǎn)步驟3 進(jìn)行下一輪搜索。

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

算法流程圖如圖1 所示。

圖1 螢火蟲算法流程圖

4 仿真測試

本文選取Car 類基準(zhǔn)測試問題[14]來驗(yàn)證螢火蟲算法的有效性，并對(duì)建立的含學(xué)習(xí)效應(yīng)的PFSP 模型進(jìn)行測試求解。

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

4.1 對(duì)不含學(xué)習(xí)效應(yīng)的PFSP 問題進(jìn)行測試

應(yīng)用螢火蟲算法對(duì)測試問題進(jìn)行仿真測試，并與粒子群算法（PSO）和遺傳算法（GA）的測試結(jié)果進(jìn)行對(duì)比。其中粒子群算法的粒子數(shù)為40，學(xué)習(xí)因子C1=C2=1.5，采用Wstart=0.9、Wend=0.4 的線性遞減慣性權(quán)重，最大迭代次數(shù)也為300，獨(dú)立運(yùn)行20 次。遺傳算法結(jié)果取自文獻(xiàn)[15]。結(jié)果如表1 所示。

表1 car類問題優(yōu)化結(jié)果

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

根據(jù)學(xué)習(xí)因子的計(jì)算公式a=lgl/lg 2 可知，不含有學(xué)習(xí)效應(yīng)的PFSP問題既是學(xué)習(xí)率為100%的PFSP問題。

4.2 對(duì)含有學(xué)習(xí)效應(yīng)的PFSP 問題進(jìn)行求解

行業(yè)不同，流水車間存在的學(xué)習(xí)率也不同，因此對(duì)學(xué)習(xí)效應(yīng)在PFSP問題中的應(yīng)用要考慮不同的學(xué)習(xí)率。當(dāng)學(xué)習(xí)率l分別是90%、80%、70%、60%、50%時(shí)學(xué)習(xí)效應(yīng)因子a分別是-0.152、-0.322、-0.515、-0.737、-1。在獨(dú)立運(yùn)行螢火蟲算法20 次后得到的優(yōu)化結(jié)果如表2 所示。

表2 含學(xué)習(xí)效應(yīng)的Car類問題優(yōu)化結(jié)果

圖2 優(yōu)化結(jié)果的線性擬合情況

4.3 結(jié)果分析

（1）擬合分析

對(duì)Car 類問題在不同學(xué)習(xí)率下的優(yōu)化結(jié)果進(jìn)行線性擬合（圖2），從圖2 中可以看出，隨著學(xué)習(xí)率的降低，各測試問題目標(biāo)函數(shù)值的減小趨勢均十分明顯。因此在PFSP 問題中加入學(xué)習(xí)效應(yīng)后，工件的最小化最大完工時(shí)間縮短，并隨著學(xué)習(xí)效果的增強(qiáng)，最小化最大完工時(shí)間呈明顯的減小趨勢。

（2）敏感性分析

敏感性分析是一種定量描述模型輸入變量對(duì)輸出變量的重要性程度的方法。敏感度系數(shù)是敏感性分析的評(píng)價(jià)指標(biāo)，它是目標(biāo)值變化的百分率與敏感因素變化的百分率之比，計(jì)算公式為：

式中，SAF為評(píng)價(jià)指標(biāo)A對(duì)于不確定因素F的敏感度系數(shù)；ΔF/F為不確定因素F 的變化率；ΔA/A為不確定因素F發(fā)生ΔF變化時(shí)，評(píng)價(jià)指標(biāo)A的相對(duì)變化率。SAF＞0 表示評(píng)價(jià)指標(biāo)與不確定因素同方向變化；SAF＜0表示評(píng)價(jià)指標(biāo)與不確定因素反方向變化。|SAF|越大表明評(píng)價(jià)指標(biāo)A對(duì)于不確定性因素F越敏感；反之則不敏感[16]。

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

綜上可知，學(xué)習(xí)效應(yīng)對(duì)PFSP的目標(biāo)函數(shù)值有很大影響，企業(yè)在實(shí)際生產(chǎn)中考慮學(xué)習(xí)效應(yīng)的存在是十分必要的。

表3 學(xué)習(xí)率敏感度系數(shù)表

5 結(jié)束語

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

[1] 劉延風(fēng)，劉三陽.基于混合電磁算法求解置換流水車間調(diào)度問題[J].系統(tǒng)仿真學(xué)報(bào)，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ìn)的粒子群算法求解置換流水車間調(diào)度問題[J].計(jì)算機(jī)應(yīng)用，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] 劉長平，葉春明.置換流水車間調(diào)度問題的螢火蟲算法求解[J].工業(yè)工程與管理，2012，17（3）：56-59.

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

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

[9] 孫林輝，王丹，王吉波.具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水作業(yè)問題[J].系統(tǒng)管理學(xué)報(bào)，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] 張新功.具有學(xué)習(xí)效應(yīng)的重新排序問題[J].重慶師范大學(xué)學(xué)報(bào)，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] 劉長平，葉春明.一種新穎的仿生群智能優(yōu)化算法：螢火蟲算法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（9）：3295-3297.

[14] 王凌.智能優(yōu)化算法及其應(yīng)用研究[M].北京：清華大學(xué)出版社，2001：195-196.

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

[16] 成其謙.投資項(xiàng)目評(píng)價(jià)[M].北京：中國人民大學(xué)出版社，2010：120-126.