擠壓插入式算法在排課系統中的應用研究

閆英琪，景 麗，劉淑紅

（蘭州城市學院，甘肅 蘭州 730000）

擠壓插入式算法在排課系統中的應用研究

閆英琪，景 麗，劉淑紅

（蘭州城市學院，甘肅 蘭州 730000）

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

擠壓插入式算法；排課系統；中小學

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

21世紀是信息化的計算機文化時代。計算機不僅是一種信息處理工具，而且能改變人類生存方式。那么利用計算機能否為學校排課呢？在肯定計算機能夠迅速且準確排課的條件下，項目組成員決定針對項目學校開發一個簡單易行的排課系統。

1 系統概述

依據Windows操作系統環境，用Visual Basic 6.0軟件開發工具制作排課系統[1，2]。以項目學校的課程安排為依據，按照課程要求進行排課。排課后，輸出的課表如有不合理的地方，可以直接對其進行調整。

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

2 擠壓插入式算法設計

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

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

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

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

3 遇到的問題及解決方案

3.1 課程不能全部排完

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

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

3.2 課表空洞

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

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

3.3 排出的課不合理

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

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

在課表上進行微調有2種情況：將2門課程進行調換和將一門課程調換到課表上沒有排課的地方。

（1）2門課程之間的調換，流程見圖3。

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

這樣既能將所有課程排入課表，又能在課表上直接進行微調，達到了完全實用的目的。

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

[2]江高舉.VB6.0開發人員指南[M].北京：清華大學出版社，1997.

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

G43

B

1671-1246（2011）05-0043-02

甘肅省教育科學“十一五”規劃課題“甘肅省中小學教師信息技術能力培訓內容及體系建構研究”（GSBG[2009]GXG067）之系列研究成果