基于一種新編碼的作業(yè)車間調度.pdf

1、作業(yè)車間調度問題（Job Shop Scheduling Problem，簡稱JSSP）是一個非常復雜的NP—難組合優(yōu)化問題，它在工程應用中有著十分重要的意義。早期學者對作業(yè)車間調度問題的研究主要集中在數學方法上。隨著計算機運算速度的迅速增長和對調度有效性要求的顯著增加，越來越強調在消耗某些額外計算費用的基礎上獲得更好的調度方案，于是，各種啟發(fā)式方法在作業(yè)車間調度問題中的應用應運而生。 本文在研究現(xiàn)有的JSSP求解方法和相關基本

2、理論的基礎上，對目前JSSP的編碼方式（特別是基于操作的編碼方式）進行了深入的分析，提出了一種新的JSSP編碼方式——調度編碼。該編碼直接表示為調度矩陣和調度中各操作的完成時間矩陣的形式，不需要解碼過程，從而避免了編碼空間與調度空間多對一的映射問題。 人工免疫系統(tǒng)是近年來計算智能的研究熱點。本文對免疫克隆選擇算法進行了深入的研究，并結合新的編碼方式，提出了一種基于調度編碼的免疫記憶克隆選擇作業(yè)車間調度算法。 該算法根據新

3、的編碼方式和JSSP解分布較廣的特點，構造了抗體群和抗體死亡單元。抗體群根據抗體親和力的大小被分為記憶單元和一般抗體單元。記憶單元保存抗體群中親和力較高的抗體。 算法通過對記憶單元和一般抗體單元中的每個抗體執(zhí)行免疫克隆操作，使抗體群不斷進化。 在算法的每一次迭代以后，對記憶單元和一般抗體單元中的抗體進行交互。對一般抗體單元中某些不能變好的抗體執(zhí)行死亡操作，并用新產生的抗體替代?？贵w死亡單元是一個規(guī)模固定的，比抗體群規(guī)模小