蟻群聚類算法在差異工件批調(diào)度問(wèn)題的應(yīng)用研究.pdf

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

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

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

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

5、性能目標(biāo)和評(píng)價(jià)方式等內(nèi)容。之后，對(duì)聚類分析(Cluster analysis)的知識(shí)進(jìn)行了介紹，包括聚類分析的概念、分析方法和衡量標(biāo)準(zhǔn)等內(nèi)容。
　　隨后，本文探討了蟻群聚類算法求解差異工件單機(jī)系統(tǒng)批調(diào)度問(wèn)題的算法。為了解決蟻群算法因?yàn)槊つ克阉鞫鴮?dǎo)致耗時(shí)較長(zhǎng)的不足，引入聚類算法構(gòu)建優(yōu)化的目標(biāo)候選列表來(lái)彌補(bǔ)這個(gè)缺陷，具體來(lái)說(shuō)是以工件的加工時(shí)間和尺寸來(lái)定義工件之間的相異度，將加工時(shí)間和尺寸接近的工件分在同一批。之后再運(yùn)用蟻群搜索的特性來(lái)