用于作業(yè)調(diào)度的基于瓶頸的多代理方法研究.pdf

1、隨著工業(yè)化的快速發(fā)展，制造業(yè)的生產(chǎn)線變得越來(lái)越復(fù)雜，對(duì)于能及時(shí)處理訂單的能力也要求越來(lái)越高。怎樣設(shè)計(jì)一個(gè)好的調(diào)度方案成為了制造業(yè)成功的關(guān)鍵的因素之一。
　　車(chē)間調(diào)度是一個(gè)經(jīng)典的調(diào)度問(wèn)題，始于上個(gè)世紀(jì)50年代。在車(chē)間調(diào)度問(wèn)題中，當(dāng)一個(gè)或多個(gè)活動(dòng)的開(kāi)始時(shí)間發(fā)生了改變，可能會(huì)產(chǎn)生活動(dòng)操作時(shí)間上的沖突，則系統(tǒng)需要一個(gè)高效率的方法來(lái)調(diào)整調(diào)度方案。因?yàn)槎啻矸椒梢钥焖俚玫揭粋€(gè)可行解，所以本論文選擇多代理方法進(jìn)行研究。多代理方法是指系統(tǒng)包含了

2、一系列不同的代理，這些代理相互獨(dú)立，并且每一個(gè)代理都有獨(dú)自解決問(wèn)題的能力和不同的方法。代理之間通過(guò)信息的更新及傳達(dá)，進(jìn)行合作和交互從而解決問(wèn)題，當(dāng)每一個(gè)代理上的個(gè)體不存在違反約束的情況，則得出最終結(jié)果。正是由于每個(gè)代理具有非常強(qiáng)的問(wèn)題解決能力，所以多代理方法可以快速得到一個(gè)可行解。
　　而根據(jù)調(diào)度理論上的研究，因?yàn)槠款i機(jī)器對(duì)系統(tǒng)而言，有最緊的約束，所以瓶頸機(jī)器很大程度上決定了整個(gè)系統(tǒng)的性能。為了使多代理方法得到更好的解，本文在多代

3、理方法的基礎(chǔ)上運(yùn)用了瓶頸策略，即選擇出系統(tǒng)的瓶頸機(jī)器并對(duì)瓶頸機(jī)器上活動(dòng)的處理加以優(yōu)化?；谄款i策略的多代理算法將系統(tǒng)分為了三個(gè)代理：生產(chǎn)作業(yè)代理，機(jī)器代理和瓶頸機(jī)器代理。瓶頸機(jī)器的優(yōu)化包含兩部分，一是指對(duì)瓶頸機(jī)器的初始化進(jìn)行優(yōu)化，二是指對(duì)解決沖突時(shí)的做法進(jìn)行了優(yōu)化，使優(yōu)化的算法比原先算法有更進(jìn)一步的提高。然而根據(jù)基于瓶頸策略的多代理系統(tǒng)解決問(wèn)題的算法框架，雖然這個(gè)方法顯示了良好的性能，但由于解決過(guò)程是一個(gè)循環(huán)的迭代，所以算法有陷入死鎖的

4、可能性。根據(jù)大量的能引起死鎖產(chǎn)生的實(shí)驗(yàn)數(shù)據(jù)，總結(jié)出三種死鎖和每種死鎖產(chǎn)生的原因。為了使這三種死鎖得以解決，在原算法的基礎(chǔ)上，本文提出了兩種方法：預(yù)防死鎖和發(fā)現(xiàn)并解決死鎖，并且努力減少因解決死鎖所而帶來(lái)對(duì)系統(tǒng)性能的影響。
　　本文提出的方案可以在較短時(shí)間內(nèi)得到不錯(cuò)的調(diào)度方案，同時(shí)也解決了自身算法的缺陷-死鎖。實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法成功地解決了較小規(guī)模問(wèn)題中存在的死鎖，對(duì)于較大問(wèn)題，因?yàn)闄C(jī)器的分配方案非常多，所以不能一一測(cè)試，但在幾百