閆英琪，景 麗，劉淑紅

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

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

閆英琪，景 麗，劉淑紅

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

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

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

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

21世紀(jì)是信息化的計算機文化時代。計算機不僅是一種信息處理工具，而且能改變?nèi)祟惿娣绞健Ｄ敲蠢糜嬎銠C能否為學(xué)校排課呢？在肯定計算機能夠迅速且準(zhǔn)確排課的條件下，項目組成員決定針對項目學(xué)校開發(fā)一個簡單易行的排課系統(tǒng)。

1 系統(tǒng)概述

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

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

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

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

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

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

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

3 遇到的問題及解決方案

3.1 課程不能全部排完

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

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

3.2 課表空洞

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

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

3.3 排出的課不合理

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

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

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

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

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

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

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

[2]江高舉.VB6.0開發(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）之系列研究成果