基于改進差分算法解決流水車間問題

李超，張曉霞

（遼寧科技大學計算機與軟件工程學院，鞍山114051）

1 課題研究的背景和意義

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

2 研究現狀

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

它的描述為：n個產品{j1,j2,…,jn}，在m臺機器{1,2,3,…,m}上加工，每一個產品的完成都需要執行每道程序，即一個產品需要流經m個機器，而且，每個產品又不能同時需要一個機器，并且一臺機器不能同時生產兩個或多個產品，否則會出現程序執行錯誤，并且各個產品在不同機器上的所需時間都不同，其目的是獲得最優的調度方案，滿足對問題的多重面考慮。

3 差分算法的基本原理

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

它是由父代產生子代，二者中較好的作為新的父代進入下一代執行之后的循環迭代。而又不同于傳統的EA，DE首先執行變異，然后任意抽取三個，運用數學中向量的加減得到新的變異個體，按照流程順序將變異個體與目標個體交叉得到對應的子代個體，并將它與目標個體進行適應值比較，優勝劣汰，直到算法的結果結束[4]。

4 差分算法的進化流程

差分算法的概述如下：

（1）設定差分算法控制參數，順應函數采用實數編碼。

（2）隨機產生初始種群。

（3）預估（2），通過實驗得到它們的適應度值。

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

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

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

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

（7）進化代數k=k+1，轉步驟（4）[3]。

5 蟻群算法的進化流程

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

圖1 蟻群算法流程圖

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

設有5個工價、4臺機器的生產車間調度，每個工件需要的時間如下：

j i：是第i個工件j：是第j道工序

通過設置NP=20，來研究實驗結果，運用圖1，得到4-3-1-2-5的解，需要72分鐘。通過數據的分析，差分算法的迭代規律如圖2，蟻群算法的迭代規律如圖3。

圖2 差分算法的迭代值

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

圖3 蟻群算法的迭代值

把數據代入蟻群算法，得到4-2-5-1-3的解，需要93分鐘，比差分算法的運算結果長，差分算法與之對比，因其算法的優質解得概率達到80%以上，所以差分算法比蟻群算法更符合車間。

表1 兩種算法結果對比

從兩次實驗結果中分析可以得出：

（1）差分算法比蟻群算法的運行結果要好，運行速度要快，結果更清晰明白，所以差分算法在優化類問題中具有典型的優勢的。

（2）差分算法的能力要強于蟻群算法，主要是因為它的最優解具有普遍性，會根據情況做出改變，但是蟻群算法相對而言就相對絕對了，不具有普遍性。

（3）通過實驗結果表明，提出的差分算法相對于蟻群算法在解決流水車間問題時，求解質量非常有效。所以在流水車間問題上，改進的差分算法更有優勢。

7 結語

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

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

（2）好的算法需要有好的平臺載體去呈現它，為了使人們更容易操縱它，需要將成熟的算法結合軟件應用到實際生產問題，才是最終想達到的目的。

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