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

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

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

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