大學(xué)課程表問(wèn)題中的算法研究與應(yīng)用.pdf

1、課程表問(wèn)題(UTP)是一個(gè)應(yīng)用廣泛的、典型的組合優(yōu)化和不確定性調(diào)度問(wèn)題，并且已經(jīng)被證明是NP完全問(wèn)題。隨著高校規(guī)模的不斷擴(kuò)大，和教學(xué)管理信息化的不斷深入，傳統(tǒng)的手工排課和計(jì)算機(jī)輔助排課已經(jīng)越來(lái)越難以適應(yīng)現(xiàn)實(shí)的需求，而自動(dòng)化排課系統(tǒng)，因其固有的高難度和復(fù)雜性，它的研究與實(shí)現(xiàn)成為完善中南大學(xué)網(wǎng)絡(luò)教學(xué)管理系統(tǒng)十分重要的一環(huán)。本文從實(shí)際應(yīng)用出發(fā)，基于動(dòng)態(tài)規(guī)劃的思想，提出了一種解決大學(xué)課程表問(wèn)題的混合算法，并基于此算法設(shè)計(jì)并實(shí)現(xiàn)了自動(dòng)化排課系統(tǒng)。

2、 本文首先介紹了UTP問(wèn)題的研究現(xiàn)狀、涉及的因素、各種約束條件，及其數(shù)學(xué)模型，然后詳細(xì)闡述了將課程表問(wèn)題劃分為時(shí)間片安排和場(chǎng)地安排兩個(gè)階段，分別采用智能算法和最佳適應(yīng)算法逐段求解，并最終求得全局較優(yōu)解的混合算法。然后，對(duì)混合算法與經(jīng)典遺傳算法進(jìn)行了對(duì)比實(shí)驗(yàn)分析，結(jié)果表明這種分階段決策的算法在保證課表質(zhì)量的同時(shí)，能夠有效的減小遺傳算法在求解UTP問(wèn)題中的復(fù)雜度，提高程序的運(yùn)行速度，也有利于工程應(yīng)用中對(duì)多目標(biāo)優(yōu)化的進(jìn)一步擴(kuò)展。