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

1、隨著工業(yè)化的快速發(fā)展，制造業(yè)的生產線變得越來越復雜，對于能及時處理訂單的能力也要求越來越高。怎樣設計一個好的調度方案成為了制造業(yè)成功的關鍵的因素之一。
　　車間調度是一個經典的調度問題，始于上個世紀50年代。在車間調度問題中，當一個或多個活動的開始時間發(fā)生了改變，可能會產生活動操作時間上的沖突，則系統需要一個高效率的方法來調整調度方案。因為多代理方法可以快速得到一個可行解，所以本論文選擇多代理方法進行研究。多代理方法是指系統包含了

2、一系列不同的代理，這些代理相互獨立，并且每一個代理都有獨自解決問題的能力和不同的方法。代理之間通過信息的更新及傳達，進行合作和交互從而解決問題，當每一個代理上的個體不存在違反約束的情況，則得出最終結果。正是由于每個代理具有非常強的問題解決能力，所以多代理方法可以快速得到一個可行解。
　　而根據調度理論上的研究，因為瓶頸機器對系統而言，有最緊的約束，所以瓶頸機器很大程度上決定了整個系統的性能。為了使多代理方法得到更好的解，本文在多代

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

4、可能性。根據大量的能引起死鎖產生的實驗數據，總結出三種死鎖和每種死鎖產生的原因。為了使這三種死鎖得以解決，在原算法的基礎上，本文提出了兩種方法：預防死鎖和發(fā)現并解決死鎖，并且努力減少因解決死鎖所而帶來對系統性能的影響。
　　本文提出的方案可以在較短時間內得到不錯的調度方案，同時也解決了自身算法的缺陷-死鎖。實驗結果表明改進的算法成功地解決了較小規(guī)模問題中存在的死鎖，對于較大問題，因為機器的分配方案非常多，所以不能一一測試，但在幾百