擠壓插入式算法在排課系統(tǒng)中的應(yīng)用研究

閆英琪，景 麗，劉淑紅

（蘭州城市學(xué)院，甘肅 蘭州 730000）

擠壓插入式算法在排課系統(tǒng)中的應(yīng)用研究

閆英琪，景 麗，劉淑紅

（蘭州城市學(xué)院，甘肅 蘭州 730000）

為解決西部農(nóng)村地區(qū)中小學(xué)排課難問(wèn)題，開(kāi)發(fā)基于擠壓插入式算法的排課系統(tǒng)，并分析排課過(guò)程中遇到的各種問(wèn)題及解決方案。該排課系統(tǒng)有效減輕了人工排課的繁重工作，為中小學(xué)排課人員帶來(lái)了很大方便。

擠壓插入式算法；排課系統(tǒng)；中小學(xué)

筆者在參與“甘肅省網(wǎng)絡(luò)環(huán)境建立城鄉(xiāng)互動(dòng)教師專(zhuān)業(yè)化能力協(xié)同發(fā)展的策略研究”項(xiàng)目以及在“甘肅省中小學(xué)教師信息技術(shù)能力培訓(xùn)內(nèi)容及體系建構(gòu)研究”項(xiàng)目實(shí)施過(guò)程中，曾調(diào)研近百所甘肅農(nóng)村中小學(xué)的教學(xué)環(huán)境、教學(xué)資源及教學(xué)輔助設(shè)備。在調(diào)查教學(xué)環(huán)境時(shí)發(fā)現(xiàn)大多數(shù)中小學(xué)排課都是人工完成的，主要由學(xué)校教務(wù)處工作人員經(jīng)過(guò)長(zhǎng)時(shí)間的分析、統(tǒng)計(jì)，做出表格后通過(guò)電腦錄入，不但工作量大，且非常繁瑣，容易出錯(cuò)。各學(xué)校每學(xué)期通常要花費(fèi)一個(gè)星期甚至更多時(shí)間排課，既浪費(fèi)人力，也浪費(fèi)時(shí)間。那么，有沒(méi)有切實(shí)可行的辦法解決這個(gè)問(wèn)題呢？

21世紀(jì)是信息化的計(jì)算機(jī)文化時(shí)代。計(jì)算機(jī)不僅是一種信息處理工具，而且能改變?nèi)祟?lèi)生存方式。那么利用計(jì)算機(jī)能否為學(xué)校排課呢？在肯定計(jì)算機(jī)能夠迅速且準(zhǔn)確排課的條件下，項(xiàng)目組成員決定針對(duì)項(xiàng)目學(xué)校開(kāi)發(fā)一個(gè)簡(jiǎn)單易行的排課系統(tǒng)。

1 系統(tǒng)概述

依據(jù)Windows操作系統(tǒng)環(huán)境，用Visual Basic 6.0軟件開(kāi)發(fā)工具制作排課系統(tǒng)[1，2]。以項(xiàng)目學(xué)校的課程安排為依據(jù)，按照課程要求進(jìn)行排課。排課后，輸出的課表如有不合理的地方，可以直接對(duì)其進(jìn)行調(diào)整。

系統(tǒng)結(jié)構(gòu)如圖1，系統(tǒng)分為3部分：輸入、排課和課表輸出。其中輸入部分實(shí)現(xiàn)本學(xué)年的課程安排，教師帶課計(jì)劃的輸入，以及對(duì)輸入數(shù)據(jù)合法性進(jìn)行檢查，如班主任的唯一性，每班只有一個(gè)，且必須有一個(gè)班主任；班級(jí)課程的唯一性，每班的每門(mén)課只能由一位教師教授；課時(shí)數(shù)的校驗(yàn)等。系統(tǒng)核心部分排課模塊是基于擠壓插入式算法，其原理是模擬人工排課，綜合教師、班級(jí)與課程3者因素，按照各門(mén)課程的排課要求進(jìn)行排課，之后再進(jìn)行重排處理，如排出的課表不合理可以進(jìn)行微調(diào)。輸出部分分為屏幕輸出及手工調(diào)整和打印形成文檔輸出2部分。系統(tǒng)數(shù)據(jù)流程見(jiàn)圖2[3]。

2 擠壓插入式算法設(shè)計(jì)

擠壓插入式算法的總體思路是，以課程為核心，以班級(jí)為單位掃描3張課表，這3張課表均標(biāo)記為“F”且符合課時(shí)要求。如果各種條件都滿(mǎn)足，教師在這個(gè)時(shí)間點(diǎn)空閑，并要求教室或公用教室必須在這個(gè)課時(shí)點(diǎn)空閑，即不產(chǎn)生沖突，則在3張課表找到的課時(shí)點(diǎn)填上課程安排；如果產(chǎn)生沖突，可以?huà)呙杵渌n時(shí)點(diǎn)，再檢測(cè)沖突情況進(jìn)行排課。如果最終因不能找到合適的課時(shí)點(diǎn)而未能安排本次課程，那么它的課時(shí)計(jì)數(shù)器將大于0，即這門(mén)課程沒(méi)有排完，留到最后重排，重排的算法與第一次排課掃描插入算法相似，只是稍修改了一些地方。

具體來(lái)看，擠壓插入式算法的實(shí)現(xiàn)，可根據(jù)對(duì)課程屬性的分析劃分為六大集合，以及各種課程的排課要求，將課程人為地確定優(yōu)先級(jí)，也就是排課順序。其順序?yàn)椋弘p周課（健康、國(guó)防、體活）、英語(yǔ)、作文、數(shù)學(xué)、語(yǔ)文講讀、公用教室課、特色課，最后為副課。優(yōu)先級(jí)的確定原則：（1）幾個(gè)教師同時(shí)空閑才能安排的課程優(yōu)先級(jí)高，如雙周課；（2）兼課多的教師的課程優(yōu)先級(jí)高；（3）有特殊要求的課程優(yōu)先級(jí)高；（4）外聘教師的課程優(yōu)先級(jí)高；（5）涉及相關(guān)因素多的課程優(yōu)先級(jí)高。

排課順序確定后，可采取2種掃描順序掃描課表課時(shí)點(diǎn)：橫向掃描和縱向掃描。這2種掃描順序可以互補(bǔ)。下面就橫向掃描和縱向掃描作一解釋。橫向掃描，即每個(gè)課時(shí)點(diǎn)，先橫向從星期一到星期五進(jìn)行掃描，待掃完一輪后，再對(duì)下一個(gè)課時(shí)點(diǎn)進(jìn)行橫向掃描?？v向掃描是對(duì)每天的課時(shí)點(diǎn)進(jìn)行縱向掃描，然后每星期隔2天或3天進(jìn)行跳躍式掃描，避免同一課程連續(xù)2天有課。這里又可以分為正掃和逆掃，正掃是從上午第一節(jié)到第三節(jié)進(jìn)行掃描，逆掃是從下午第七節(jié)到上午第四節(jié)進(jìn)行掃描。根據(jù)不同課程的排課要求，我們對(duì)不同課程采取不同的掃描策略。雙周課、體育課、公用教室課采用縱向逆掃，主課采用縱向正掃，活動(dòng)課、副課使用橫向掃描，以彌補(bǔ)縱向掃描造成中間課時(shí)空閑的不足。

最后再將那些初排未安排的課程依次抽出來(lái)，以班為單位進(jìn)行橫向掃描，查找合適的課時(shí)點(diǎn)，進(jìn)行沖突檢測(cè)，重排這些課程。

3 遇到的問(wèn)題及解決方案

3.1 課程不能全部排完

由于課程種類(lèi)繁多，且排課時(shí)間要求不一樣，主次順序也不同。所以先排的課程較容易排完，而后排的課程由于各種條件的限制很難找到適當(dāng)位置，使得課程不能全部排完。

解決這一問(wèn)題的方法是在課程初排后查詢(xún)是否存在沒(méi)有排完的課。如果有則依次掃描課表，少考慮一些沖突，沒(méi)排完的課程由再排模塊重新排。

3.2 課表空洞

所謂課表空洞是指課程排完后，從課表上看有的前一課時(shí)沒(méi)有排課而后一課時(shí)卻排了課，排出來(lái)的課不夠緊湊。出現(xiàn)這一問(wèn)題主要是因?yàn)橛行┱n程限制了排課時(shí)間。例如語(yǔ)文課要排在英語(yǔ)和數(shù)學(xué)之后，而且2節(jié)課不能連上；課時(shí)超過(guò)5時(shí)上午和下午各排一節(jié)課；副課盡量不排在上午1、2節(jié)；公用教室課必須排在統(tǒng)一、指定的課時(shí)等。

解決這一問(wèn)題的方法是采用不同的課表掃描方式進(jìn)行排課。先排的課進(jìn)行縱向掃描，后排的課進(jìn)行橫向掃描。由于排課時(shí)間點(diǎn)的限制和沖突幾率的限制，縱向掃描又分為從上往下掃描和從下往上掃描方式。例如英語(yǔ)、數(shù)學(xué)、語(yǔ)文等主課采用從上往下掃描方式，而體育、音樂(lè)等沖突幾率較高的課程則采用從下往上的掃描方式。后排的課程如副課則采用橫向掃描方式。這樣，對(duì)各種不同要求的課程采用不同課表掃描方式可以有效解決課表空洞問(wèn)題。

3.3 排出的課不合理

電腦排課是人工智能排課過(guò)程的模擬，因此，排出的課不一定符合學(xué)校的具體要求或某位教師的實(shí)際要求，這也是直接影響排課有效性和實(shí)用性最關(guān)鍵的問(wèn)題。

解決這一問(wèn)題的最好方法是在課程排完后按照實(shí)際需求進(jìn)行調(diào)整，就是微調(diào)。本系統(tǒng)的微調(diào)算法是在課表上直觀調(diào)換2門(mén)課程或者將一門(mén)課程調(diào)換到課表上沒(méi)有排課的地方，微調(diào)模塊自動(dòng)檢測(cè)調(diào)課的教師有沒(méi)有帶課時(shí)間沖突，如果是公共教室課則要考慮公共教室使用是否有沖突，只有在沒(méi)有任何沖突的前提下才能進(jìn)行課程調(diào)換。微調(diào)模塊有效解決了排課不合理問(wèn)題，同時(shí)也大大增強(qiáng)了整個(gè)排課系統(tǒng)的實(shí)用性。

在課表上進(jìn)行微調(diào)有2種情況：將2門(mén)課程進(jìn)行調(diào)換和將一門(mén)課程調(diào)換到課表上沒(méi)有排課的地方。

（1）2門(mén)課程之間的調(diào)換，流程見(jiàn)圖3。

（2）將一門(mén)課調(diào)換到課表上沒(méi)有排課的地方。這種調(diào)換比將2門(mén)課程進(jìn)行調(diào)換更簡(jiǎn)單，只需判斷帶課教師有無(wú)帶課時(shí)間沖突即可。

這樣既能將所有課程排入課表，又能在課表上直接進(jìn)行微調(diào)，達(dá)到了完全實(shí)用的目的。

[1]劉甫迎.VB教程[M].北京：電子科技大學(xué)出版社，1998.

[2]江高舉.VB6.0開(kāi)發(fā)人員指南[M].北京：清華大學(xué)出版社，1997.

[3]林立域.Access 97[M].北京：清華大學(xué)出版社，1999.

G43

B

1671-1246（2011）05-0043-02

甘肅省教育科學(xué)“十一五”規(guī)劃課題“甘肅省中小學(xué)教師信息技術(shù)能力培訓(xùn)內(nèi)容及體系建構(gòu)研究”（GSBG[2009]GXG067）之系列研究成果