基于MOEA-D的多目標(biāo)考試時間表調(diào)度算法研究.pdf

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

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

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