人性化高校排課算法的設(shè)計(jì)與實(shí)現(xiàn)

林嵐嵐

(廣東水利電力職業(yè)技術(shù)學(xué)院，廣東廣州510635)

1.引言

本人在2004年開(kāi)發(fā)了滿足本校排課需求的排課系統(tǒng)，近兩年學(xué)校將教學(xué)中心轉(zhuǎn)移到新校區(qū)，舊的排課規(guī)則已經(jīng)不能滿足新的需求，故在原有系統(tǒng)的基礎(chǔ)上根據(jù)新的排課規(guī)則設(shè)計(jì)了新的排課算法，使新的排課算法能滿足新的排課需求。

本論文主要介紹了新的排課規(guī)則，以及滿足新排課規(guī)則的排課算法的設(shè)計(jì)與實(shí)現(xiàn)。

2.人性化的排課規(guī)則

由于本校新舊校區(qū)距離比較遠(yuǎn)，往返新舊校區(qū)需要花費(fèi)比較長(zhǎng)的時(shí)間，為了體現(xiàn)“以人為本”的排課理念，在新校區(qū)上課的教師盡可能采用集中排課的方式，即一天安排四節(jié)或六節(jié)課，并且盡可能晚上不安排課程。

為了提高教學(xué)資源的利用率，對(duì)同專業(yè)的兩個(gè)班級(jí)的相同課程，通常采用理論課合班實(shí)踐課分班的原則。在教學(xué)資源充足的情況下，對(duì)同一個(gè)班同一門(mén)純理論課或純實(shí)踐課一天最多安排兩節(jié)、理論實(shí)踐相結(jié)合的課程最多安排四節(jié)，這里的理論實(shí)踐課是指理論課和實(shí)踐課的課時(shí)比為1：1的課程。

為了提高學(xué)生對(duì)知識(shí)的吸收率，對(duì)同一個(gè)班通常不會(huì)連續(xù)兩天安排相同的理論課。對(duì)理論實(shí)踐相結(jié)合的課程通常是先安排理論課再安排實(shí)踐課，實(shí)踐課緊跟在理論課后面。

為了滿足前后課銜接和充分利用教學(xué)資源的需要，對(duì)同一排課對(duì)象在一周的同一時(shí)間可根據(jù)周數(shù)的不同安排不同的課程，這里的排課對(duì)象指教師、教室和班級(jí)。

3.數(shù)據(jù)庫(kù)的設(shè)計(jì)

排課系統(tǒng)中包含7個(gè)數(shù)據(jù)表：教師基本信息表、班級(jí)基本信息表、教室基本信息表、課程安排表、教師課表、班級(jí)課表和教室課表。教師基本信息表、班級(jí)基本信息表和教室基本信息表中都有一個(gè)名為“排課情況”的字段，用來(lái)表示當(dāng)前的排課情況。

課程安排表中包含了課程名稱、上課班級(jí)代碼、授課教師編號(hào)、起止周、周學(xué)時(shí)、合班否、課程類型、排課否和備注等字段。“上課班級(jí)代碼”字段用來(lái)存放單班或合班上課的班級(jí)代碼，“課程類型”字段用來(lái)存放“純理論”、“純實(shí)踐”、“理論實(shí)踐課”等上課類型，“排課否”字段在排課后通過(guò)賦予字段值“是”或“否”來(lái)表示該課程能否排課，“備注”字段用來(lái)存放排課信息，排課過(guò)程中將每次排課的時(shí)間地點(diǎn)都存放在該字段中，當(dāng)排課失敗時(shí)可根據(jù)該字段的信息對(duì)當(dāng)前課程進(jìn)行手動(dòng)排課。

4.排課算法的設(shè)計(jì)

排課算法的設(shè)計(jì)思路如下所述：

首先對(duì)與排課相關(guān)的表進(jìn)行初始化操作。把教師基本信息表、班級(jí)基本信息表和教室基本信息表中的“排課情況”字段的字段值設(shè)置為400個(gè)＊號(hào)，同時(shí)把課程安排表中的“排課否”的字段值設(shè)置為“否”，并清除“備注”字段的值。

然后根據(jù)課程安排表進(jìn)行排課。先對(duì)排課要求比較高的合班理論分班實(shí)踐課進(jìn)行排課，然后對(duì)單班理論實(shí)踐課進(jìn)行排課，再對(duì)合班純理論課進(jìn)行排課，最后對(duì)單班純理論或純實(shí)踐課進(jìn)行排課。

下面以合班理論分班實(shí)踐課的排課為例，說(shuō)明算法的設(shè)計(jì)。

合班理論分班實(shí)踐課排課算法()

5.人性化排課規(guī)則的實(shí)現(xiàn)

(1)對(duì)相同的排課對(duì)象按周數(shù)的不同安排不同的課程

為了實(shí)現(xiàn)對(duì)相同的排課對(duì)象按周數(shù)的不同安排不同的課程，在教師基本信息表、班級(jí)基本信息表和教室基本信息表中定義了"排課情況"字段用來(lái)表示各排課對(duì)象的排課情況，該字段用400個(gè)字符表示20個(gè)教學(xué)周中每一周20次課（一次課相當(dāng)兩節(jié)課）的排課情況，該字段的第一個(gè)字符表示第一周星期一1、2節(jié)的排課情況，第二個(gè)字符表示第一周星期一3、4節(jié)的排課情況，依次類推。如果某一字符為＊號(hào)則表示該時(shí)間點(diǎn)未排課，如果為#號(hào)則表示已排課。如果要獲取第week周星期i第j次課的上課情況，可通過(guò)判斷該字段的第(week-1)＊20+(i-1)＊4+j個(gè)字符是否為＊號(hào)來(lái)得知該時(shí)間點(diǎn)是否未排課。

(2)合班理論分班實(shí)踐課程及相同課程的理論課不連續(xù)兩天安排的人性化排課

合班理論分班實(shí)踐課程的最佳排課規(guī)則是1、2節(jié)合班上理論課，3、4節(jié)一個(gè)單班上實(shí)踐課，5、6節(jié)另一個(gè)單班上實(shí)踐課；其次是5、6節(jié)合班上理論課，第二天的1、2節(jié)一個(gè)單班上實(shí)踐課，第二天的3、4節(jié)另一個(gè)單班上實(shí)踐課。

為了滿足上述規(guī)則和相同課程的理論課不連續(xù)兩天安排的原則，在設(shè)計(jì)算法時(shí)用i%5+1表示星期幾，用j%3+1表示第幾次課，用WeekStart表示課程的開(kāi)始周，用WeekEnd表示課程的結(jié)束周，為理論課查找排課時(shí)間點(diǎn)的算法如下：

上述算法用表示第幾節(jié)的循環(huán)變量作為外循環(huán)、用表示星期幾的循環(huán)變量作為內(nèi)循環(huán)，并且循環(huán)變量的更改采用加2而不是加1，從而使排課時(shí)間點(diǎn)從每一天的1、2節(jié)開(kāi)始查找，當(dāng)所有的1、2節(jié)都不滿足要求時(shí)才查找每一天的5、6節(jié)，最后查找3、4節(jié)，在選擇星期幾上課時(shí)，是按照星期一、星期三、星期五、星期二、星期四的順序查找，從而實(shí)現(xiàn)相同課程的理論課不連續(xù)兩天安排的原則。

特別注意的是為了滿足廣大教師晚上不愿上課的需求，在自動(dòng)排課算法中不考慮對(duì)7、8節(jié)進(jìn)行排課，故上述算法的外循環(huán)用for(j=0；j＜6；j=j+2)而不是for(j=0；j＜8；j=j+2)。

為了實(shí)現(xiàn)實(shí)踐課緊跟在理論課后面安排的原則，在選擇實(shí)踐課上課時(shí)間點(diǎn)時(shí)，應(yīng)從當(dāng)前理論課的時(shí)間點(diǎn)后面開(kāi)始查找，這時(shí)只需用一重循環(huán)來(lái)遍歷一周的所有上課時(shí)間點(diǎn)。實(shí)踐課的排課算法如下：

6.小結(jié)

為了測(cè)試本排課系統(tǒng)的性能，本人以上學(xué)期計(jì)算機(jī)系的實(shí)際排課數(shù)據(jù)作為測(cè)試數(shù)據(jù)，其中多媒體教室12個(gè)，實(shí)訓(xùn)場(chǎng)8個(gè)，班級(jí)26個(gè)，教師34人，班平均周課時(shí)20節(jié)，采用本排課系統(tǒng)進(jìn)行排課后，除了兩個(gè)周學(xué)時(shí)為28節(jié)課的班級(jí)不能完成自動(dòng)排課外，其它都能安排到上課時(shí)間，并且大部分排課時(shí)間滿足我校的排課規(guī)則。實(shí)驗(yàn)結(jié)果表明該排課算法的設(shè)計(jì)比較合理，能滿足實(shí)際排課需求。