基于分類優(yōu)化和優(yōu)先級(jí)算法的自動(dòng)排課探討

摘要：為解決目前高校自動(dòng)排課系統(tǒng)設(shè)計(jì)復(fù)雜、排課效率低的問(wèn)題，提出了一種基于分類優(yōu)化、優(yōu)先級(jí)算法以及矩陣匹配運(yùn)算的自動(dòng)排課算法。該算法首先對(duì)課程進(jìn)行分類優(yōu)化，然后按優(yōu)先級(jí)進(jìn)行計(jì)算，其次引入矩陣的迭加匹配運(yùn)算，將整個(gè)問(wèn)題分層分類處理， 從而使大問(wèn)題分散在各個(gè)子問(wèn)題當(dāng)中，并通過(guò)逐層處理達(dá)到了降低算法復(fù)雜性、減少死鎖的目的， 最終實(shí)現(xiàn)自動(dòng)排課。

關(guān)鍵詞：自動(dòng)排課；分類；優(yōu)先級(jí)

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)34-1645-02

The Discuss on Automatic Course Arrangement Based on Classification Optimization and Priority Algorithm

GOU Zheng-wei， LI Chuan-dong

(College of Computer Science， Chongqing University， Chongqing 400044， China)

Abstract: To solve the problems of the complexity and low effectiveness of course schedule in automatic course arrangement system in universities， a new algorithm for automatic course arrangement is proposed based on the theory of classification optimization， priority algorithm and matrix computation. The main ideas of the proposed method are as follows. The courses to be scheduled are firstly optimally classified and then leveled and sorted based on the priority and matching matrices. Thus， a large problem is shifted into some small problems that can be solved easily. Thus， automatic course arrangement is implemented with lower complexity and reduced deadlock.

Key words: automatic course arrangement; classification priority; matrix match

1 前言

目前，關(guān)于高校排課算法的研究一直是一個(gè)熱點(diǎn)問(wèn)題，早在20世紀(jì)70年代就有人提出自動(dòng)排課這一問(wèn)題，直到現(xiàn)在，研究自動(dòng)排課系統(tǒng)的步伐一直就未停止過(guò)。就目前而言，已經(jīng)有部分高校和公司成功開(kāi)發(fā)出了學(xué)校自動(dòng)排課軟件并投入使用。其采用的算法大多集中在目前比較流行的基于圖論的算法、利用人工智能的遺傳算法、蟻群算法等。但由于這些算法均存在著思路復(fù)雜、開(kāi)發(fā)難度大、優(yōu)化不確切等問(wèn)題；因而，軟件除具有各自的一些優(yōu)點(diǎn)外，還不同程度地存在一些問(wèn)題，例如，排課效率低、排出的課程不夠合理、與人工排課相差很遠(yuǎn)、且受多種條件的限制等。

針對(duì)上述存在的問(wèn)題，本文提出了一種基于分類優(yōu)化和優(yōu)先級(jí)的算法，該算法先對(duì)課時(shí)段、課程和教室進(jìn)行分類優(yōu)化，然后運(yùn)用優(yōu)先級(jí)算法結(jié)合矩陣的迭加匹配運(yùn)算實(shí)現(xiàn)自動(dòng)排課，從而解決了排課中關(guān)系多、因素多、約束條件多等問(wèn)題。

2 排課問(wèn)題的描述

排課是將教師、學(xué)生和相應(yīng)的課程在時(shí)間和空間上根據(jù)不同的約束條件進(jìn)行合理的安排，避免沖突，以使教學(xué)工作順利進(jìn)行。對(duì)教師、班級(jí)、課程、時(shí)間、教室五部分資源進(jìn)行最優(yōu)化配置，符合教學(xué)規(guī)律，才能保證充分發(fā)揮各個(gè)資源的優(yōu)勢(shì)，提高教學(xué)質(zhì)量。隨著高校教學(xué)規(guī)模的擴(kuò)大，人數(shù)增加，校區(qū)增加，教師增加，排課涉及的因素越來(lái)越多，問(wèn)題越來(lái)越復(fù)雜，使得手工操作逐漸無(wú)法勝任排課工作。為了提高教務(wù)管理工作效率，改善教學(xué)管理質(zhì)量，合理高效地利用有限資源，使課表編排更合理、科學(xué)、快速，自動(dòng)排課系統(tǒng)的設(shè)計(jì)被人們所廣泛關(guān)注。

為了編排出令各方面都滿意的課程表，在課程編排過(guò)程中應(yīng)遵循一定的規(guī)則，盡量滿足各種約束條件。下面列出了部分排課問(wèn)題所涉及的約束條件（1-3為硬約束，其它為軟約束）：

1) 一個(gè)班級(jí)在同一時(shí)間只能安排一門課；

2) 一個(gè)老師在同一時(shí)間只能安排一門課；

3) 一個(gè)教室在同一時(shí)間只能安排一門課；

4) 教室容量必須滿足上課學(xué)生人數(shù)；

5) 課程要安排在它所需要類型的教室中如多媒體教室、機(jī)房、物理實(shí)驗(yàn)室等；

6) 同一個(gè)班級(jí)上的同一門課程在一周之內(nèi)應(yīng)間隔排列；

7) 繁難課程應(yīng)盡量排在精力充沛的上午授課；

8) 體育課應(yīng)該排在下午或者上午三四節(jié)，體育課后面避免安排講授課；

9) 實(shí)驗(yàn)、操作課應(yīng)排在下午或晚上；

10) 教師半天的活動(dòng)盡量安排在一個(gè)校區(qū)；

11) 一個(gè)班級(jí)同一課程在一天內(nèi)上課不能超過(guò)3學(xué)時(shí)。

要對(duì)課表在多資源上實(shí)現(xiàn)絕對(duì)最優(yōu)的配置實(shí)際上是不可能的，因此，考慮在無(wú)任何硬性沖突的基礎(chǔ)上，能夠滿足盡量多的軟性沖突，我們就認(rèn)為這個(gè)課表是可行并且較優(yōu)的。

3 排課問(wèn)題的定義

在設(shè)計(jì)算法時(shí)，為了降低課程調(diào)度的算法復(fù)雜性，主要采用了分類、優(yōu)先級(jí)以及矩陣迭加匹配的算法思想。首先對(duì)排課數(shù)據(jù)和時(shí)間單元進(jìn)行預(yù)處理，主要的預(yù)處理過(guò)程有：

3.1 課程預(yù)處理

各院系根據(jù)各年級(jí)開(kāi)課情況，制訂相應(yīng)的教學(xué)計(jì)劃。即本院系教師所授課程以及所授的班級(jí)上報(bào)教務(wù)部門，教務(wù)部門依據(jù)該課程所需課時(shí)以及課程的類型、重要程度等確定該課程的優(yōu)先級(jí)，以此確定自動(dòng)排課的排課號(hào)，為按優(yōu)先級(jí)排課打下基礎(chǔ)。同時(shí)，我們把課程按每天上課的時(shí)段分為五種類型，需第一二節(jié)上的為一型，三四節(jié)上的為二型，下午五六節(jié)上的為三型，七八節(jié)上的為四型，晚上九十節(jié)上的為五型。

3.2 教室預(yù)處理

教室根據(jù)實(shí)際情況按校區(qū)可分為普通1型(XX人以內(nèi))，普通2型(XX至XX人)、普通3型(XX人以上)、多媒體1型、多媒體2型、多媒體3型、網(wǎng)絡(luò)1型、網(wǎng)絡(luò)2型、網(wǎng)絡(luò)3型、室外等等類型。這樣，我們就避免了教室資源的浪費(fèi)，把最接近的人數(shù)安排在相應(yīng)的教室中，也就是說(shuō)我們把問(wèn)題進(jìn)行分類，化整為零，然后分門別類進(jìn)行排課處理，這樣做就可以大大降低算法的復(fù)雜性，從而提高排課處理的速度。

3.3 時(shí)間預(yù)處理

設(shè)置每?jī)尚r(shí)為一課程單元計(jì)算，j表示一周的課程單元數(shù)，i表示一學(xué)期的周數(shù)。定義三張時(shí)間矩陣表，一張是教師的矩陣表，表示為Tn[i，j]，一張是學(xué)生班級(jí)的矩陣表，表示為Cn[i，j]，一張是教室的矩陣表，表示為Rn[i，j]。我們排課的最終目的就是要把所有的課程都安排在這三個(gè)矩陣內(nèi)，且使這三張矩陣表迭加匹配成功，并盡量遵循人工排課的規(guī)律。設(shè)一天5個(gè)單元課時(shí)，一周5天計(jì)算，就是25課時(shí)，那么j的最大值就為25，即定義可用時(shí)間代碼 j=1…25，其中 j=1…5 分別表示周一的排課情況，j=6…10 分別表示周二的排課情況，以些類推。

矩陣的值為正整數(shù)，我們定義當(dāng)Tn[i，j]、Cn[i，j]、Rn[i，j]>0時(shí)分別表示第i周第j時(shí)間單元教師、班級(jí)和教室不可用; Tn[i，j]、Cn[i，j]、Rn[i，j]=0 分別表示第i周第j時(shí)間單元教師、班級(jí)和教室可用。當(dāng)且僅當(dāng)Tn[i，j]Cn[i，j]Rn[i，j]=0時(shí)方可排課，同時(shí)將Tn[i，j]、Cn[i，j]、Rn[i，j]分別變?yōu)橄鄳?yīng)的排課號(hào)。本規(guī)則就滿足了約束條件1、2、3。

為滿足約束條件7、8、9，我們?cè)O(shè)置當(dāng)且僅當(dāng)j%5的值與課程的類型匹配方可排課。為滿足約束條件4、5，當(dāng)選擇教室時(shí)，先按學(xué)生人數(shù)選擇相應(yīng)類型的教室，如找不到匹配的教室，則在相應(yīng)的校區(qū)內(nèi)選擇與之類型一樣但可容納人數(shù)較多的教室，這樣盡量避免了教室資源的浪費(fèi)。

4 排課的設(shè)計(jì)與實(shí)現(xiàn)

4.1 設(shè)定課程編排的優(yōu)先級(jí)

把課程信息表按周學(xué)時(shí)和課程類型降序排列，讓周學(xué)時(shí)多以及需要在上午排課的課程優(yōu)先排課，然后逐步降低優(yōu)先級(jí)，按優(yōu)先級(jí)進(jìn)行排課。

4.2 設(shè)定時(shí)間的控制條件

周學(xué)時(shí)為 2、4、6 的課程排第一次課時(shí)不需什么條件，當(dāng)排第二或三次課時(shí)，設(shè)前一次排此課程的時(shí)間為 PP，本次為 I，則控制|PP- I|/5>0，這樣可以保證同一班級(jí)同一課程在一天內(nèi)上課不超過(guò) 3 學(xué)時(shí); 控制|PP-I|/5>1并且PP! =0，這樣可以保證同一班級(jí)同一課程的兩次課盡量不排在相鄰的兩天。

4.3 按優(yōu)先級(jí)進(jìn)行排課

首先取課時(shí)數(shù)多的課程進(jìn)行預(yù)排課，分別按每周需要上的課時(shí)數(shù)及上課時(shí)間根據(jù)4.2設(shè)置的控制條件進(jìn)行預(yù)排課，修改Cn[i，j]矩陣值，然后與Tn[i，j]矩陣值進(jìn)行對(duì)比，如果Tn[i，j]均滿足條件，再在對(duì)應(yīng)校區(qū)相應(yīng)類型的教室集合中選取教室，與Rn[i，j]值進(jìn)行對(duì)比，三張表均滿足，則把修改的矩陣值保存，如果不滿足，則繼續(xù)搜尋教室，直至找到為止。如果Tn[i，j]不滿足條件，則修改Cn[i，j]的值，繼續(xù)以上操作。如果有合班情況，則增加一個(gè)Cn[i，j]，四個(gè)表進(jìn)行比較，四個(gè)均滿足，則表示此課程可以排課，把相應(yīng)的排課號(hào)分別寫(xiě)入相應(yīng)的矩陣表內(nèi)，繼續(xù)排下一課程，直至排課完畢。詳細(xì)流程詳見(jiàn)圖1。

4.4 排課后處理

為一門課程安排了一次課之后，必須將課程的相關(guān)信息寫(xiě)入排課結(jié)果表中，修改三個(gè)矩陣表的值為相應(yīng)課程的排課號(hào)。由于班級(jí)、教師和教室的可用時(shí)間單元是安排課程的依據(jù)，所以在安排了一次課程之后一定要把已排的時(shí)間單元設(shè)置相應(yīng)的排課號(hào)保存至各矩陣中，以確保下一次排課的順利進(jìn)行。用排課號(hào)表示該時(shí)間單元已經(jīng)安排相應(yīng)的課程，用“0”表示該時(shí)間單元可以繼續(xù)安排課程。（下轉(zhuǎn)第1669頁(yè)）

（上接第1646頁(yè)）

5 結(jié)論

本文對(duì)自動(dòng)排課算法進(jìn)行了較細(xì)致的研究，提出了一種基于分類優(yōu)化和優(yōu)先級(jí)的自動(dòng)排課算法。該算法通過(guò)劃分類型、計(jì)算優(yōu)先級(jí)以及利用矩陣匹配等方法將整個(gè)問(wèn)題分類分層處理，從而使矛盾分散在各個(gè)子問(wèn)題當(dāng)中，并通過(guò)逐層處理達(dá)到了降低算法復(fù)雜性、減少死鎖的目的，基本實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)排課功能。

該算法具有如下特點(diǎn)：首先，排課時(shí)設(shè)置了排課優(yōu)先級(jí)，周學(xué)時(shí)多的課程優(yōu)先排課，大大減少了產(chǎn)生沖突的機(jī)率。其次，時(shí)間是在教師、教室和班級(jí)共同的空閑時(shí)間集合中產(chǎn)生，并且可以防止一周幾次課集中于某一段時(shí)間，一學(xué)期中集中于某幾周。再次，課表還可以實(shí)現(xiàn)單雙周排課，解決高校排課不靈活的問(wèn)題。由于課表問(wèn)題規(guī)模大、約束復(fù)雜以及問(wèn)題不斷變化等特點(diǎn)，以及個(gè)人水平有限，系統(tǒng)還有很多性能需要優(yōu)化，還存在很多尚待解決的問(wèn)題，主要有：在設(shè)計(jì)中考慮影響排課順序的因素時(shí)總有些顧此失彼，需要有更好的模型支持；歷史上比較優(yōu)化的排課結(jié)果如何在排課中運(yùn)用？等等。這些都有待于在今后不斷改進(jìn)和完善。

參考文獻(xiàn)：

[1] lai L F，Hsueh N L.An Artificial Intelligence Approach to Course Timetabling[C].IEEE，2006.

[2] 陶華亭，張?zhí)腋?基于圖論方法的自動(dòng)優(yōu)化排課模型研究[J].微計(jì)算機(jī)信息，2005(17).

[3] 趙惠怡.基于蟻群算法的排課問(wèn)題的研究[D].大連：大連海事大學(xué)，2007.

[4] 湛德照.高校自動(dòng)排課系統(tǒng)的算法研究與實(shí)現(xiàn)[D].重慶：重慶大學(xué)，2006.

[5] 王曙霞，涂俊英.基于優(yōu)先級(jí)的自動(dòng)排課模塊的設(shè)計(jì)與實(shí)現(xiàn)[J].電腦與電信，2006(10).

[6] 雷濤，王靜，徐巖.基于分組優(yōu)化和矩陣運(yùn)算的自動(dòng)排課算法[J].蘭州交通大學(xué)學(xué)報(bào)，2007(6).

[7] 陳誼，楊怡.基于優(yōu)先級(jí)自動(dòng)排課算法PCSA的設(shè)計(jì)與實(shí)現(xiàn)方案[J].北京工商大學(xué)學(xué)報(bào)，2002(6).