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

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

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