基于差分進(jìn)化算法的FMS中機(jī)器與AGV同時調(diào)度方法

伍 樂，宋豫川，呂向飛，雷 琦

(重慶大學(xué) 機(jī)械傳動國家重點(diǎn)實(shí)驗室，重慶 400044)

在現(xiàn)代制造業(yè)生產(chǎn)中，多品種小批量、多樣化個性化定制的生產(chǎn)模式已成為發(fā)展趨勢，這必將會對柔性制造系統(tǒng)(flexible manufacturing system, FMS)提出更高的要求。生產(chǎn)調(diào)度是柔性制造系統(tǒng)的基礎(chǔ)，制定科學(xué)合理的調(diào)度方案，對柔性制造系統(tǒng)的性能具有重要影響。其中，柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem，F(xiàn)JSP)是非常復(fù)雜的NP難題。在以往的FJSP研究中，為了簡化數(shù)學(xué)模型解決問題，大多忽略了工件在不同機(jī)器之間的運(yùn)輸時間，或?qū)⑵浒诠ぜ庸r間內(nèi)，這都是不合理的，特別是當(dāng)工件的移動完全依賴于自動導(dǎo)引小車(automated guided vehicle，AGV)并且運(yùn)輸時間與加工時間相當(dāng)時[1]。因此，有必要對FMS中的機(jī)器與AGV同時調(diào)度問題進(jìn)行研究。

針對機(jī)器與AGV同時調(diào)度問題，國內(nèi)外學(xué)者進(jìn)行了很多研究。早期，Bilge等[2]將問題表述為一個非線性混合整數(shù)規(guī)劃模型，采用帶滑動時間窗的迭代啟發(fā)式方法進(jìn)行求解。這種精確求解算法能夠在簡單小規(guī)模問題上取得全局最優(yōu)解，但隨著問題復(fù)雜度的增加，無法在合理時間內(nèi)搜索到滿意解。近年來，智能優(yōu)化算法如遺傳算法[3-8]、差分進(jìn)化算法[9]、粒子群算法[10-11]、蟻群算法[12]、花授粉算法[13]等，在求解具有復(fù)雜約束的同時調(diào)度問題上，取得了較好的進(jìn)步。Abdelmaguid等[3]提出一種新的啟發(fā)式編碼方案，采用混合遺傳算法同時調(diào)度機(jī)器與AGV。Kumar等[9]提出機(jī)器選擇和車輛分配兩種啟發(fā)式算法，并與差分進(jìn)化算法相結(jié)合，為工件分配合適的機(jī)器與AGV，但沒有對算法進(jìn)行改進(jìn)，僅對工序操作進(jìn)行了基本差分變換。……