蟻群聚類算法在差異工件批調度問題的應用研究.pdf

1、目前，全球的經(jīng)濟快速發(fā)展，各企業(yè)間的競爭日趨激烈，怎樣合理地利用有限資源以提高生產效率，盡量減少生產消耗成為社會廣泛關注的焦點。而合理的調度可以優(yōu)化企業(yè)資源，均衡各部門的配置，最終實現(xiàn)資源利用的最大化。所以，調度問題的研究得到了大家普遍的關注。目前，調度問題在生產調配、物流運輸和計算機人工智能等方面存在十分廣泛的運用。
　　差異工件批調度的問題是在經(jīng)典批調度問題上的深化，每個工件的加工時間和尺寸各不相同，相同批次的工件尺寸和不能超

2、過機器的容量。這種問題實際上比具有相同尺寸工件的批調度更復雜，然而由于它更貼近日常的生產現(xiàn)狀，因此對該類型問題的探索有著顯著的經(jīng)濟回報和社會效應。
　　本文是對于工件數(shù)為m和機器容量為B的單機批處理問題進行研究。每個工件Ji(i=1，2，...，m)的加工時間為pi，尺寸為si，每個工件的加工時間和尺寸都不一樣。每次機器將部分工件作為一批同時進行加工，且這批工件的尺寸和不超過機器的容量。假如一個批準備加工，在該批加工結束之前，不可

3、以被暫停也不可以再增加新的工件，批的加工時間和批中工件的最大加工時間相等，在同一個批的工件有同樣的完工時間。本文的問題目標是極小化最大完工時間。
　　本文首先從調度基本知識開始，介紹了調度問題的概念和參數(shù)表示等內容。然后對經(jīng)典調度進行描述，再過渡到對批調度的陳述，并對兩者的區(qū)別進行了闡述，最后介紹了差異工件批調度的問題。
　　其次，本文描述了求解批調度問題的幾種重要算法:數(shù)學規(guī)劃法(Mathematical Programm

4、ing)、啟發(fā)式算法(Heuristic Algorithm)、遺傳算法(Genetic Algorithm)、模擬退火算法(Simulated Annealing)和粒子群算法(ParticleSwarm Optimization)等，并且對不同算法的原理進行了詳細介紹，同時給出算法求解問題的一般過程。
　　接著，文章介紹了蟻群算法(Ant Colony Optimization)及其基礎知識，包括工作原理、基本模型、參數(shù)設置、

5、性能目標和評價方式等內容。之后，對聚類分析(Cluster analysis)的知識進行了介紹，包括聚類分析的概念、分析方法和衡量標準等內容。
　　隨后，本文探討了蟻群聚類算法求解差異工件單機系統(tǒng)批調度問題的算法。為了解決蟻群算法因為盲目搜索而導致耗時較長的不足，引入聚類算法構建優(yōu)化的目標候選列表來彌補這個缺陷，具體來說是以工件的加工時間和尺寸來定義工件之間的相異度，將加工時間和尺寸接近的工件分在同一批。之后再運用蟻群搜索的特性來