含有運(yùn)輸小車的柔性作業(yè)車間調(diào)度研究

周鑫

摘? 要：在實(shí)際的柔性作業(yè)車間調(diào)度中，不但工件需要加工時(shí)間，而且工件在各個(gè)機(jī)器之間利用AGV（自動(dòng)導(dǎo)引小車）轉(zhuǎn)移也需要占用一定的時(shí)間，因此對(duì)柔性作業(yè)車間調(diào)度中考慮AGV運(yùn)輸時(shí)間的研究更具有實(shí)際意義。針對(duì)此問題，本文建立含有AGV的柔性作業(yè)車間調(diào)度的數(shù)學(xué)模型，針對(duì)問題自身特點(diǎn)對(duì)遺傳算法進(jìn)行改進(jìn)，引入局部搜索策略加強(qiáng)局部尋優(yōu)能力，將模擬退火算法作為局部搜索策略加入全局搜索中，增強(qiáng)了算法的收斂性能。通過在仿真實(shí)驗(yàn)平臺(tái)上的實(shí)驗(yàn)數(shù)據(jù)結(jié)果可以看出，本算法有比較好的效果。

關(guān)鍵詞：遺傳算法;柔性作業(yè)車間調(diào)度;模擬退火;自動(dòng)引導(dǎo)小車

中圖分類號(hào)：TP301? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： In the actual flexible job-shop scheduling， it is more of practical significance to consider transportation time of Automatic Guided Vehicle （AGV） in flexible job-shop scheduling Research， because workpieces not only require processing time， but also take a certain amount of time to be transferred between machines using AGV. Aiming at this problem， this paper proposes to establish a mathematical model of flexible job-shop scheduling with AGV and improve genetic algorithm according to characteristics of the problem. Local search strategy is introduced to strengthen the local optimization ability， and simulated annealing algorithm is added as a local search strategy to global search in order to enhance algorithm convergence performance. Experimental data from simulation experiment platform show that this algorithm is comparatively effective.

Keywords： genetic algorithm; flexible job-shop scheduling; simulated annealing; automatic guided vehicle

1? ?引言（Introduction）

FJSP是公認(rèn)的NP難問題，所以FJSP一直是國內(nèi)外學(xué)者研究的熱點(diǎn)[1]。這個(gè)問題從20世紀(jì)90年代Bruker等人提出后，國內(nèi)外的專家學(xué)者進(jìn)行了深入廣泛的研究。FJSP是JSP的擴(kuò)展，JSP工件的工序所在的加工機(jī)器是固定的，F(xiàn)JSP更加符合實(shí)際車間中的生產(chǎn)環(huán)境。目前求解FJSP的主要智能算法有遺傳算法[2]、免疫算法[3]、粒子群算法[4]、蟻群算法[5]等。張國輝等[6]使用隨機(jī)初始化種群優(yōu)化方法。趙詩奎[7]等基于設(shè)備均衡的策略并運(yùn)用均勻設(shè)計(jì)的思想優(yōu)化了種群的初始化方法。張立果[8]等針對(duì)多目標(biāo)的柔性作業(yè)車間調(diào)度問題提出新的交叉策略來進(jìn)行求解。在實(shí)際的生產(chǎn)環(huán)境中，工件在不同的加工機(jī)器之間通過AGV小車進(jìn)行搬運(yùn)。

對(duì)于AGV參與集成車間調(diào)度問題的研究也得到一些學(xué)者的廣泛研究，付建林等[9]對(duì)AGV和車間調(diào)度之間的融合調(diào)度方法——AGV調(diào)度優(yōu)化問題做了一個(gè)分類，為研究AGV融合車間調(diào)度的學(xué)者提供了學(xué)習(xí)的建議。戴敏等[10]針對(duì)加工機(jī)器和AGV的集成調(diào)度提出了改進(jìn)的分布估計(jì)算法進(jìn)行優(yōu)化研究。劉二輝等[11]通過改進(jìn)花授粉算法對(duì)AGV和機(jī)器的集成調(diào)度進(jìn)行了研究。徐云琴等[12]研究了AGV在柔性作業(yè)車間調(diào)度中的數(shù)量變化對(duì)加工時(shí)間的影響。賀長征等[13]對(duì)AGV在柔性作業(yè)車間中的路徑進(jìn)行了優(yōu)化。

通過閱讀以上文獻(xiàn)發(fā)現(xiàn)，目前AGV在柔性作業(yè)車間調(diào)度中的集成調(diào)度相關(guān)研究較少，大部分的文獻(xiàn)都沒有研究車間調(diào)度和AGV相融合的問題。針對(duì)此問題，本文將考慮AGV在實(shí)際生產(chǎn)環(huán)境中發(fā)揮調(diào)度作用這一因素，研究柔性作業(yè)車間AGV的融合問題，讓本文的研究更加符合實(shí)際的生產(chǎn)環(huán)境。本文內(nèi)容和以上文獻(xiàn)的主要區(qū)別為：本文在遺傳算法中加入局部搜索增強(qiáng)局部尋優(yōu)能力，并研究了有AGV情況下的車間調(diào)度問題。

2? 含有AGV的柔性作業(yè)車間調(diào)度模型（Flexible job-shop scheduling model with AGV）

2.1? ?問題描述

含有AGV的柔性車間調(diào)度問題可以描述為：n個(gè)工件由多臺(tái)AGV運(yùn)送到多臺(tái)不同的機(jī)器上加工，工件的不同工序在不同的機(jī)器上進(jìn)行加工的加工時(shí)間不同，每臺(tái)加工機(jī)器之間的距離也不相同。每個(gè)工件有ni道不同的工序、r個(gè)AGV，且

r

未加工的工件和已加工的工件分別放置在未加工的區(qū)域P1和已加工的區(qū)域P2。

（1）AGV的搬運(yùn)速度是不變的，搬運(yùn)時(shí)間和機(jī)器之間的距離有關(guān)，設(shè)相鄰的機(jī)器之間距離相等。

（2）一臺(tái)機(jī)器一次處理一個(gè)零件。

（3）不計(jì)算工件在設(shè)備緩沖區(qū)中的時(shí)間。

（4）在最初的時(shí)刻，所有的機(jī)器和工件都可以使用。

（5）AGV的運(yùn)輸路線是固定的，AGV的運(yùn)輸沒有延遲，并且不同AGV的運(yùn)輸不會(huì)相互干擾。

2.2? ?模型建立

根據(jù)以上描述的資源約束條件建立模型，在車間調(diào)度中有多目標(biāo)優(yōu)化和單目標(biāo)優(yōu)化，本文采用比較常見的單目標(biāo)優(yōu)化方案，以所有工件加工完成的最小時(shí)間為目標(biāo)。

式中，i為工件（i=1，2，…，h），h為工件數(shù);j為工序（j=1，2，…，k），k為工序數(shù);m為機(jī)器（m=1，2，…，M），M為機(jī)器的數(shù)量;Tms和Tme表示加工開始和結(jié)束的時(shí)間;Tagvs和Tagve為小車運(yùn)輸工件的過程所消耗的時(shí)間;Tmn表示工件從機(jī)器m到機(jī)器n之間所花費(fèi)的時(shí)間;Tijs和Tije是第i個(gè)工件的第j道工序的加工開始和結(jié)束時(shí)間;是第i個(gè)工件的第j道工序的加工時(shí)間;和分別表示工序Oij是否在機(jī)器上加工，0表示不加工，1表示加工。

公式（1）為最小完工時(shí)間;公式（2）表示AGV的運(yùn)輸時(shí)間由兩臺(tái)設(shè)備之間的距離決定;公式（3）表示AGV運(yùn)輸工件是獨(dú)立運(yùn)行的;公式（4）表示小車能使工件的每一道工序完成后瞬間被小車運(yùn)往下一個(gè)機(jī)器;公式（5）表示一道工序開始后不能停止;公式（6）和公式（7）表示一個(gè)工件的一道工序在某一時(shí)刻只能被一臺(tái)加工機(jī)器加工;公式（8）表示相同工件的工序是有順序進(jìn)行加工的;公式（9）表示將工序累加。

3? 改進(jìn)遺傳算法設(shè)計(jì)（Improved genetic algorithm design）

3.1? ?基本原理

本文算法的基本原理是在原有GA的基礎(chǔ)上加以改進(jìn)，延用GA的基本框架，并用模擬退火作為局部搜索讓算法的收斂性能更好，并且在每次全局搜索過程中的交叉變異之后都要進(jìn)行局部搜索，從而能夠達(dá)到獲得較好質(zhì)量的最優(yōu)解的目的。改進(jìn)GA的程序結(jié)構(gòu)流程圖，如圖1所示。

3.2? ?全局搜索方法

本文研究的算法是基于傳統(tǒng)的遺傳算法的基本原理，并結(jié)合車間調(diào)度的實(shí)際生產(chǎn)環(huán)境加以改進(jìn)。在實(shí)際的車間調(diào)度中要考慮工件在不同機(jī)器之間的運(yùn)輸過程等因素，因此本文在結(jié)合GA的基礎(chǔ)上將AGV和機(jī)器進(jìn)行融合調(diào)度研究。在全局搜索方法中加入局部搜索，延用GA的基本框架，并用模擬退火作為局部搜索讓算法的收斂性能更好。GA的基本框架原理是由隨機(jī)產(chǎn)生初始解，經(jīng)過評(píng)估、選擇、交叉、變異等操作最終獲得最優(yōu)解的過程。

3.3? ?編碼與解碼

傳統(tǒng)的遺傳算法中，一旦種群規(guī)模太大，無法有效淘汰無用的個(gè)體，容易出現(xiàn)局部最優(yōu)的情況，既影響了種群的進(jìn)化速度，又影響了計(jì)算結(jié)果的準(zhǔn)確性，因此根據(jù)第2節(jié)含有AGV的柔性車間調(diào)度數(shù)學(xué)模型，本文有兩種編碼方式：一種編碼方式是對(duì)機(jī)器進(jìn)行編碼，另一種編碼方式是對(duì)工序進(jìn)行編碼。

為了展示本文算法所提出的編碼，用三臺(tái)加工機(jī)器和三個(gè)加工工件為實(shí)驗(yàn)例子模擬實(shí)際加工環(huán)境。表1和表2表示三臺(tái)加工機(jī)器上三個(gè)工件的不同工藝的加工條件，不同加工機(jī)器之間工件的運(yùn)輸時(shí)間不同，以及不同加工機(jī)器之間的距離不同。其中，Oij表示工件i的第j道工序。

假設(shè)工序Oij在機(jī)器Mi上加工，各工件的加工順序是按照同一個(gè)工件有先后順序的約束，以選取322321321為機(jī)器的編碼、112233123為工序的編碼為例，其對(duì)應(yīng)的解碼過程如圖2（a）和圖2（b）所示。

3.4? ?選擇操作

選擇操作是算法流程中關(guān)鍵的一步，通過選擇操作這一步驟獲得質(zhì)量較高的解，選擇的過程中確定選擇的策略和選擇優(yōu)質(zhì)解的比例至關(guān)重要。選擇的目標(biāo)性過強(qiáng)可能會(huì)導(dǎo)致進(jìn)入早熟的狀態(tài)，導(dǎo)致結(jié)果局部最優(yōu)的情況;選擇優(yōu)秀質(zhì)量解的比例太小會(huì)導(dǎo)致淘汰的速度變慢，增加算法的運(yùn)行時(shí)長，降低算法的性能。

選擇策略是新種群的4/5用輪盤賭選擇，選擇的概率符合大自然的規(guī)律隨機(jī)產(chǎn)生。每次選擇大于隨機(jī)概率的個(gè)體到新種群。新種群剩下的1/5的組成部分通過選擇策略找到當(dāng)前解中最優(yōu)個(gè)體，然后復(fù)制該個(gè)體，復(fù)制數(shù)量是新種群的1/5。

3.5? ?交叉操作

交叉操作在遺傳算法中是必不可少的，是模擬生物進(jìn)化過程中兩條染色體之間互相交叉重組新的染色體的過程。根據(jù)所采用的編碼的特點(diǎn)，采用IPOX[14]交叉操作，基于工序編碼。

IPOX操作是在POX操作基礎(chǔ)上經(jīng)改進(jìn)而形成的。IPOX的具體操作如圖3所示。P1、P2和C1、C2表示一對(duì)染色體經(jīng)過交叉后又重新組合成的一對(duì)新的染色體。IPOX交叉操作過程為：

（1）將全部工件分為B1和B2兩個(gè)集合。

（2）將P1染色體中有B1集合中的工件序列加入C1，P2染色體中有B2集合中的工件序列加入C2。

（3）將P2染色體中有B2集合中的工件序列加入C1，P1染色體中有B1集合中的工件序列加入C2。

3.6? ?變異操作

變異操作是模擬生物的基因突變過程，可以防止進(jìn)入結(jié)果過早收斂，在一定程度上增加了種群的多樣性，增加了跳出局部極小的可能性。本文采用兩種變異的操作方式：第一種在染色體的n個(gè)基因中，隨機(jī)產(chǎn)生位置i和j（i

3.7? ?局部搜索策略

局部搜索是為了解決非常復(fù)雜的問題而出現(xiàn)的一種解決最優(yōu)問題的算法，最優(yōu)解的時(shí)間有可能是很長的，局部搜索策略為了防止整個(gè)算法的尋優(yōu)時(shí)間過長，通過局部搜索尋找近似最優(yōu)解。局部搜索算法是從爬山法改進(jìn)而來的，其過程和原理同貪心搜索算法類似，總是從當(dāng)前解的領(lǐng)域解空間中選擇一個(gè)最好質(zhì)量解作為下次迭代過程中的當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解（Local Optimal Solution）。局部搜索算法的基本過程可以描述為：選取一個(gè)初始的解，然后通過某種領(lǐng)域動(dòng)作產(chǎn)生初始解的鄰居解，再選擇更優(yōu)的鄰居解。一直重復(fù)以上過程，直到達(dá)到終止條件。

以下是模擬退火算法的基本原理解釋，T為溫度，降溫過程具體的表示為：

公式（10）中k是一個(gè)自然常數(shù)，并且dE<0，表示溫度退火的過程。從該公式中可以得出：

exp（dE/kT）取值是（0，1），dE代表下降的溫度，那么P（dE）的函數(shù)取值范圍是（0，1）。隨著溫度T的降低，P（dE）會(huì)逐漸降低。我們認(rèn)為向更差解的轉(zhuǎn)變是溫度躍遷過程，我們以概率P（dE）接受它，當(dāng)算法結(jié)束時(shí)所得到的解即為所得到的最佳結(jié)果。

4? 實(shí)驗(yàn)結(jié)果與分析（Experimental results and analysis）

本文實(shí)驗(yàn)的環(huán)境為Windows 10系統(tǒng)，在VS開發(fā)環(huán)境下求得程序的最優(yōu)解，并將最后結(jié)果與文獻(xiàn)中的算法結(jié)果相比較。在仿真實(shí)驗(yàn)中，設(shè)置種群的數(shù)目為5，初始交叉概率為0.4，種群的大小為1，000，初始突變概率是0.05，分段函數(shù)中的片段數(shù)為n/5。

表3表示五個(gè)工件在五臺(tái)機(jī)器上的加工工藝，每個(gè)工件有三道不同的工序，用Oij表示，機(jī)器用M表示。小車的運(yùn)輸時(shí)間表如表4所示，機(jī)器之間的距離不同，導(dǎo)致不同機(jī)器之間的運(yùn)輸時(shí)間不同。

本文測(cè)試了實(shí)驗(yàn)數(shù)據(jù)，設(shè)置機(jī)器的數(shù)量為10。從表5的實(shí)驗(yàn)結(jié)果中的數(shù)據(jù)可以看出，本文改進(jìn)的算法性能有一定的提升。圖4為改進(jìn)遺傳算法和平均值的對(duì)比結(jié)果。圖5是本次實(shí)例中的調(diào)度的甘特圖。綜合圖表的數(shù)據(jù)可以得出本文的算法比平均值的進(jìn)化速度更快。

5? ?結(jié)論（Conclusion）

本文考慮AGV的運(yùn)輸時(shí)長這一實(shí)際生產(chǎn)環(huán)境中的因素，讓本文的研究更加符合實(shí)際生產(chǎn)環(huán)境。建立了含有AGV的柔性作業(yè)車間調(diào)度的數(shù)學(xué)模型，針對(duì)問題自身特點(diǎn)對(duì)遺傳算法進(jìn)行改進(jìn)，引入局部搜索策略加強(qiáng)局部尋優(yōu)能力，將模擬退火算法作為局部搜索策略加入全局搜索中，增強(qiáng)了算法的收斂性能。遺傳算法是進(jìn)行全局范圍的搜索求解，加入局部搜索是為了更快地找到最優(yōu)近似解或者次優(yōu)解的個(gè)體。本文中的實(shí)驗(yàn)測(cè)試數(shù)據(jù)充分體現(xiàn)了本文算法的有效性和可行性。

參考文獻(xiàn)（References）

[1] S. Karthikeyan， P. Asokan， S. Nickolas， et al. A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems[J]. Int. J. of Bio-Inspired Computation， 2015， 7（6）：386-401.

[2] ZHANG G H， GAO L， SHI Y. An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications， 2011， 38（4）：3563-3573.

[3] SHAO X Y， LIU W Q， LIU Q， et al. Hybrid discrete particle

swarm optimization for multi-objective flexible job-shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology， 2013， 67（9）：2885-2091.

[4] 余建軍，孫樹棟，郝京輝.免疫算法求解多目標(biāo)柔性作業(yè)車間調(diào)度研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2006，12（10）：1643-1650.

[5] YAO B Z， YANG C Y， HU J J， et al. An improved ant colony optimization for flexible job shop scheduling problems[J]. Advanced Science Letters， 2011， 4（6）：2127-2131.

[6] 張國輝，高亮，李培根，等.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機(jī)械工程學(xué)報(bào)，2009，45（7）：145-151.

[7] 趙詩奎，方水良，顧新建.柔性車間調(diào)度的新型初始機(jī)制遺傳算法[J].浙江大學(xué)學(xué)報(bào)（工學(xué)版），2013，47（6）：1022-1030.

[8] 張立果，黎向鋒，左敦穩(wěn)，等.求解多目標(biāo)柔性作業(yè)車間調(diào)度問題的兩層遺傳算法[J].計(jì)算機(jī)應(yīng)用，2020，40（S1）：14-22.

[9] 付建林，張恒志，張劍，等.自動(dòng)導(dǎo)引車調(diào)度優(yōu)化研究綜述[J].系統(tǒng)仿真學(xué)報(bào)，2020，32（09）：1664-1675.

[10] 戴敏，張玉偉，曾勵(lì).綠色作業(yè)車間機(jī)器與AGV的集成調(diào)度研究[J].南京航空航天大學(xué)學(xué)報(bào)，2020，52（03）：468-477.

[11] 劉二輝，姚錫凡，陶韜，等.基于改進(jìn)花授粉算法的共融AGV作業(yè)車間調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng)，2019，25（09）：2219-2236.

[12] 徐云琴，葉春明，曹磊.含有AGV的柔性車間調(diào)度優(yōu)化研究[J].計(jì)算機(jī)應(yīng)用研究，2018，35（11）：3271-3275.

[13] 賀長征，宋豫川，雷琦，等.柔性作業(yè)車間多自動(dòng)導(dǎo)引小車和機(jī)器的集成調(diào)度[J].中國機(jī)械工程，2019，30（04）：438-447.

[14] 張超勇，董星，王曉娟，等.基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度[J].機(jī)械工程學(xué)報(bào)，2010，46（11）：156-164.

作者簡介：

周? ?鑫（1991-），男，碩士生.研究領(lǐng)域：智能調(diào)度算法，決策分析.