基于改進(jìn)差分算法解決流水車間問題

李超，張曉霞

（遼寧科技大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，鞍山114051）

1 課題研究的背景和意義

隨著時(shí)代的進(jìn)步，科技的創(chuàng)新，行業(yè)間不斷的競(jìng)爭(zhēng)，要想在市場(chǎng)上占得先機(jī)，就必須提高競(jìng)爭(zhēng)力，那么就需要從源頭出發(fā)，所以他們將注意力放到生產(chǎn)上的調(diào)度問題，以至于算法不停優(yōu)化，效率不斷的提高，逐漸趨近于理想水平。本文的主要研討的內(nèi)容是流水車間問題。最早是Miller、Maxwell和Eonway等人進(jìn)行實(shí)際研究，他們的研究也為后來的發(fā)展打好根基。隨著時(shí)間的迭代，直到約瑟夫哈林頓提出計(jì)算機(jī)集成概念CIMS，它是逐步分解的生產(chǎn)過程合并在一起，進(jìn)行總體的優(yōu)化運(yùn)算，進(jìn)而使生產(chǎn)效率提高，所以企業(yè)的有用功增大，無用功逐漸減少。也正因?yàn)槿绱?，流水車間調(diào)度被許多生產(chǎn)行業(yè)所關(guān)注，所以現(xiàn)在大多數(shù)車間都在不同程度地應(yīng)用這門技術(shù)。而本文以時(shí)代為背景，順應(yīng)時(shí)代的要求，通過研究改進(jìn)的差分算法來解決流水車間問題[1]。

2 研究現(xiàn)狀

流水車間調(diào)度是車間調(diào)度中的基本問題。在企業(yè)的生產(chǎn)流程上，每一個(gè)小小的產(chǎn)品都必經(jīng)過所有步驟才能成功。對(duì)于車間產(chǎn)品的每一步都需要仔細(xì)設(shè)計(jì)，不容一點(diǎn)誤差，尤其是這些制件需要在流水線上遵循相同的加工路線，也就是說按次序加工，不能有一點(diǎn)顛倒，否則就會(huì)生產(chǎn)失敗，所以對(duì)于每個(gè)產(chǎn)品的加工順序的選擇就顯得尤為重要。而每個(gè)產(chǎn)品的加工順序就構(gòu)成流水車間，他們之間的調(diào)度就是流水車間調(diào)度[2]。

它的描述為：n個(gè)產(chǎn)品{j1,j2,…,jn}，在m臺(tái)機(jī)器{1,2,3,…,m}上加工，每一個(gè)產(chǎn)品的完成都需要執(zhí)行每道程序，即一個(gè)產(chǎn)品需要流經(jīng)m個(gè)機(jī)器，而且，每個(gè)產(chǎn)品又不能同時(shí)需要一個(gè)機(jī)器，并且一臺(tái)機(jī)器不能同時(shí)生產(chǎn)兩個(gè)或多個(gè)產(chǎn)品，否則會(huì)出現(xiàn)程序執(zhí)行錯(cuò)誤，并且各個(gè)產(chǎn)品在不同機(jī)器上的所需時(shí)間都不同，其目的是獲得最優(yōu)的調(diào)度方案，滿足對(duì)問題的多重面考慮。

3 差分算法的基本原理

由StomnR和PriceK在1995年推出一種隨機(jī)并行搜索的差分算法，它具有優(yōu)化不連續(xù)函數(shù)的能力。1996年差分進(jìn)化算法在速度位于季軍，卻廣泛被應(yīng)用。差分算法是基于群體智能理論的算法，具有全局搜索策略，通過實(shí)數(shù)編碼、變異操作和競(jìng)爭(zhēng)生存策略，來降低了操作的復(fù)雜性[3]。

它是由父代產(chǎn)生子代，二者中較好的作為新的父代進(jìn)入下一代執(zhí)行之后的循環(huán)迭代。而又不同于傳統(tǒng)的EA，DE首先執(zhí)行變異，然后任意抽取三個(gè)，運(yùn)用數(shù)學(xué)中向量的加減得到新的變異個(gè)體，按照流程順序?qū)⒆儺悅€(gè)體與目標(biāo)個(gè)體交叉得到對(duì)應(yīng)的子代個(gè)體，并將它與目標(biāo)個(gè)體進(jìn)行適應(yīng)值比較，優(yōu)勝劣汰，直到算法的結(jié)果結(jié)束[4]。

4 差分算法的進(jìn)化流程

差分算法的概述如下：

（1）設(shè)定差分算法控制參數(shù)，順應(yīng)函數(shù)采用實(shí)數(shù)編碼。

（2）隨機(jī)產(chǎn)生初始種群。

（3）預(yù)估（2），通過實(shí)驗(yàn)得到它們的適應(yīng)度值。

（4）判斷是不是到達(dá)迭代數(shù)的峰值。如果是，則直接輸出它的排列順序；如果不是，繼續(xù)執(zhí)行操作。

（5）實(shí)行變異和交叉操作，將變異向量V i,G與父向量X i,G雜交，通過二項(xiàng)式雜交算子得到第j維個(gè)體，公式為：

CR是交叉概率因子，jrand是維數(shù)[1 ,D]之間的均勻分布，進(jìn)而得到中間種群

（6）在（2）和（5）中進(jìn)行選擇，得到新種群，利用一對(duì)一貪婪選擇，父子代的個(gè)體向量比較，優(yōu)良個(gè)體遺傳給下一代，計(jì)算公式表示為：

（7）進(jìn)化代數(shù)k=k+1，轉(zhuǎn)步驟（4）[3]。

5 蟻群算法的進(jìn)化流程

蟻群算法顧名思義是基于螞蟻研究出來的，它與螞蟻的生理功能相類似，在尋食的途徑中，需要通過生理反應(yīng)留下的信息素來選擇那條道路，研究總結(jié)螞蟻尋路的規(guī)律來建立算法模型，并通過不時(shí)更新信息素濃度來更新算法的循環(huán)操作，最終使求得的最符合理想結(jié)果，所以這個(gè)過程被稱為蟻群算法[5]。概述如圖1。

圖1 蟻群算法流程圖

6 差分算法與蟻群算法的比較

設(shè)有5個(gè)工價(jià)、4臺(tái)機(jī)器的生產(chǎn)車間調(diào)度，每個(gè)工件需要的時(shí)間如下：

j i：是第i個(gè)工件j：是第j道工序

通過設(shè)置NP=20，來研究實(shí)驗(yàn)結(jié)果，運(yùn)用圖1，得到4-3-1-2-5的解，需要72分鐘。通過數(shù)據(jù)的分析，差分算法的迭代規(guī)律如圖2，蟻群算法的迭代規(guī)律如圖3。

圖2 差分算法的迭代值

通過圖2數(shù)據(jù)可得，水平坐標(biāo)表示的迭代次數(shù)在70就趨近于水平，圖3數(shù)據(jù)可得，蟻群算法的迭代次數(shù)在80~90之間，處于波動(dòng)狀態(tài)，所以，差分算法更適合解決流水車間問題，需要迭代超過70次，或者更多次才合適。而數(shù)據(jù)得出的結(jié)果就更是驗(yàn)證了這一結(jié)論。

圖3 蟻群算法的迭代值

把數(shù)據(jù)代入蟻群算法，得到4-2-5-1-3的解，需要93分鐘，比差分算法的運(yùn)算結(jié)果長(zhǎng)，差分算法與之對(duì)比，因其算法的優(yōu)質(zhì)解得概率達(dá)到80%以上，所以差分算法比蟻群算法更符合車間。

表1 兩種算法結(jié)果對(duì)比

從兩次實(shí)驗(yàn)結(jié)果中分析可以得出：

（1）差分算法比蟻群算法的運(yùn)行結(jié)果要好，運(yùn)行速度要快，結(jié)果更清晰明白，所以差分算法在優(yōu)化類問題中具有典型的優(yōu)勢(shì)的。

（2）差分算法的能力要強(qiáng)于蟻群算法，主要是因?yàn)樗淖顑?yōu)解具有普遍性，會(huì)根據(jù)情況做出改變，但是蟻群算法相對(duì)而言就相對(duì)絕對(duì)了，不具有普遍性。

（3）通過實(shí)驗(yàn)結(jié)果表明，提出的差分算法相對(duì)于蟻群算法在解決流水車間問題時(shí)，求解質(zhì)量非常有效。所以在流水車間問題上，改進(jìn)的差分算法更有優(yōu)勢(shì)。

7 結(jié)語(yǔ)

從現(xiàn)有的研討結(jié)果以及本文的計(jì)算過程可以清楚地知道，流水車間問題的算法研究與實(shí)際運(yùn)用相互磨合，具有一定的成果，但是如果使流水車間問題的研討能夠更廣泛地被企業(yè)應(yīng)用，依然存在待改良的方面，主要有一下幾點(diǎn)：

（1）目前研討的流水車間問題主要應(yīng)用在小規(guī)模的企業(yè)，如何使它更適應(yīng)大規(guī)模的范圍，還需要考慮的問題很多，而對(duì)應(yīng)的難度會(huì)成倍增加，所以這將是日后研究的重點(diǎn)[6]。

（2）好的算法需要有好的平臺(tái)載體去呈現(xiàn)它，為了使人們更容易操縱它，需要將成熟的算法結(jié)合軟件應(yīng)用到實(shí)際生產(chǎn)問題，才是最終想達(dá)到的目的。

（3）對(duì)于流水車間調(diào)度問題本身的研究方法，本文只是研究一點(diǎn)，還需要進(jìn)行創(chuàng)新思考，研究出更高效的算法步驟，為我們所用。現(xiàn)如今隨著智能優(yōu)化算法的進(jìn)步，不斷棄其糟粕，用之精華，不斷吸收優(yōu)秀的科學(xué)理論，與現(xiàn)代工業(yè)相結(jié)合，將會(huì)促進(jìn)社會(huì)的進(jìn)步。