基于MOEA-D的多目標考試時間表調度算法研究.pdf

1、調度問題自上世紀中后期便引起了大量學者的廣泛關注,其中,時間表調度作為一類特殊的資源調度問題,廣泛應用在學校課程和考試的時間安排、航班時刻表的制定、體育比賽等活動中,與人們的日常生活息息相關。本文以大學考試時間表問題作為研究對象進行了研究。
　　大學考試時間表問題作為一個NP完全問題,因其會隨著問題規(guī)模的擴大,求解難度也會隨著增大。近年來,用進化算法解決這類問題已經成為一個研究熱點,得到了廣泛的研究。對于大學考試時間表的研究目前主

2、要還是集中在單目標方面,即在固定時間段的前提下,將一系列考試無沖突的安排到這些固定的時間段內。但是在實際的應用中,學校每學期的考試時間長度安排是不一樣的,這也就導致決策者需要更多不同時間段的考試時間表來進行決策。同時,也有學者提出,如果時間段長度可以設定的很大,那很有可能會使沖突數變?yōu)榱?。從上可以得?無論是實際需要還是理論研究,對多目標考試時間表的研究都是必須的。
　　在本文中,第一次使用基于分解的多目標進化算法(MOEA/D)

3、解決多目標考試時間表問題,同時優(yōu)化時間表的時間段長度和人均沖突數。首先針對多目標考試時間表問題的特殊性,本文設計了兩種混合初始化方式、交叉和變異算子以及針對MOEA/D算法的鄰域選擇算子。通過在11個數據集上的對比實驗,驗證了本文提出的算法的有效性,能夠解決多目標考試時間表這一問題。然后為了提高算法的收斂性以及 Pareto前沿面的均勻分布,本人提出了改進的 MOEA/D算法,即結合 Memetic算法,來解決多目標考試時間表問題。用兩