一種邏輯決策的排課算法

屈正庚

（商洛學院 計算機科學系，陜西 商洛 726000）

排課系統是一個典型的NP問題，是一個有約束的、非線性的、模糊多目標優化的、難解的、時空組合的數學問題[1-2]。怎樣更好地體現學校各部門之間協同工作能力，怎樣讓學校的資源更合理化的使用，怎樣使教師充分利用卻又不疲倦，正是學校的排課系統需要解決的問題，針對這個方面文中提出了一種采用邏輯決策方式去解決實際生活中存在的問題，通過對0和1進行與和或運算，能得到一個合理的課表，也很容易解決排課過程中出現的沖突問題。實踐證明得到了很好的效果。

1 解決排課問題的思路

1.1 基本思想

排課系統主要圍繞學生、教師、教室、時間4個資源展開活動。在設計系統時，根據實際情況逐步細化每個環節、綜合考慮全局利益、重視發揮整體效果、保證系統運行效率[3-5]。所以設計排課系統時力求保證系統的擴充性、靈活性、安全性、易操作性、易維護性等特征。

一般排課過程的基本思想是：

1）根據課程的性質、教師的使用情況、班級開課的多少確定某門課程的時間段。例如英語、專業課安排在早晨，每個班級課程分布均勻，避免在某一些天中沒有上課的情況；

2）先后對班級和教師進行掃描，判斷該時間段是否有空閑，如果有則給相應班級對應的課程確定教室；沒有則重新分配資源；

3）當確定教室以后，檢測對應的時間段是否有空余的教室，如果有則符合條件安排這門課程，否則更換資源信息。

1.2 解決問題的流程

排課問題就是對教師、班級、教室、時間等資源去爭用并訪問的問題，排課算法流程如圖1所示。

圖1 排課流程Fig.1 Scheduling process

基本過程是：1）選擇出該系別里的專業對應的年級和班級。列表出該班級在這一學期開設的課程；2）根據優先級的順序選擇課程，包括該課程總學時、周學時、主講教師等信息。一般情況下先基礎后專業，先大班后小班，先困難后容易；3）列出帶此門課程的教師信息；4）根據班級情況、教師情況、課程的總學時和周學時確定上課時間段。這一步特別關鍵，是否產生沖突就在這個地方體現。在排列課表時要以人為本，系統利用邊排列邊檢測的手段進行工作。同時，排課完成后最繁瑣的工作就是資源檢查和統計、沖突避免和調節；5）根據周學時選出可利用的教室。一門課程周學時多的盡量固定在一個教室里；6）對于周學時和總學時多的課程設置標記。例如對英語、數學等課程一周多次，在安排時至少隔一天，保證上課效果。

2 邏輯決策的排課算法

2.1 算法的思想

根據教學計劃，列出每個班級開設課程的進度，建立一個教學進度數據庫表。如果對于某一門課程需要合班時，也需要加上一條數據信息。對數據庫中班級進度通過一個專用的標志來表示，包括該班級的課程、教師、時間、教室等信息。通過“0，1”字符串來實現排課過程。“0”表示資源未被占用，“1”表示資源已占用[6-7]。

2.2 算法的關鍵技術

假設09級計算機應用專業一班現在開設3門課程：公共英語、合班課馬克思主義哲學、數據結構，對應的周學時分別為4、2、4，對應的教師分別是教師A、教師 B、教師C。按照一周5天上班，每天上課時間段為4大節課。安排課程時一次性連續上2小時。已知3位教師的教學時間和教室使用情況對應的信息字符串如表1所示。

表1 信息字符串Tab.1 Information string

3位教師與時間和教室按位進行邏輯或運算，結果為“0”表示資源不發生沖突，對此班級安排課表如表2所示。

表2 教師課表Tab.2 Teachers curriculum

根據前面介紹的排課規律和基本原則可知，對這3門課程由高到低的方式排序：公共英語＞馬克思主義哲學＞數據結構，英語盡可能在早晨，周學時為4的至少隔1天。經過全面思考與調整，首先教師C的數據結構只能放在周三（5-6）與周五（5-6）恰當，教師A的公共英語放在周一（3-4）與周四（3-4），教師B的馬克思主義哲學放在周三（1-2）。

如果教師與時間和教室按位進行邏輯或運算，結果為“1”表示有沖突發生，則進一步對教師與時間和教室按位進行邏輯與運算，結果為“0”表示沖突可以解決，根據課程加權值進行排序，采用協商技術。結果為“1”表示最嚴重，就要轉變決策，這時要回到初始狀態，重新分配資源。

3 邏輯決策的算法實驗結果

通過上面描述的算法思想和原理，給出了一個仿真系統，利用該系統對排列的課程進行認真分析、仔細的計算，得到了理想的結果，而且算法運行效率高。對發生的沖突解決起來速度快[8-10]。

假設現在只有2個教室供班級上課，一周上課時間5天，每天安排4大節課程，對班級的一周課程進行安排。教學安進度表如表3所示。

表3 班級課程信息表Tab.3 Class course information sheet

從表3中可以看出，3個班級一共開設了6門課程，每個班級一周上12節課程，共有6名教師。對這些數據按照邏輯運算的法則進行安排課表，結果如表4所示。

表4 班級課表Tab.4 Class curriculum

地理 1班：周一（1-2）上文學欣賞，周二（1-2）上基礎數學，周三（1-2）上哲學，（3-4）上文學欣賞，周四（1-2）上公共體育，（3-4）上基礎數學，周五（3-4）上經濟學。

化學 1班：周一（1-2）上公共英語，周二（3-4）上文學欣賞，周三（1-2）上基礎數學，（3-4）上公共英語，周四（1-2）上大學物理，周五（1-2）上基礎等數學。

電子1班：周一（3-4）上經濟學，周二（1-2）上公共英語，（3-4）上大學物理，周三（5-6）上公共體育，周四（3-4）上大學物理，周五（3-4）上公共英語。

4 結束語

從以上數據分析，該算法是符合實際要求的，采用此算法可以排列出可靠、滿意、穩定的班級課表和教師課表，適合在高等學校使用[11-12]。因此，利用此算法提高管理水平，使教務處的工作變得更加科學化和規范化。該算法以人為本，滿足教務處教師、學生及管理人員不同需求，提高資源的利用率，保證課程的教學效果，加強學校的教學質量。

[1]楊東風.自愿選課算法分析與優化研究[J].電子設計工程，2011，19（5）:108-110.

YANG Dong-feng.Volunteers course algorithm analysis and optimization research[J].Electronic Design Engineering，2011，19（5）:108-110.

[2]祝勇仁，曹煥亞.應用遺傳算法求解排課問題[J].計算機應

用與軟件，2007， 24（12）:130-132.

ZHU Yong-ren，CAO Huan-ya.Application of genetic algorithm to timetable problem[J].Computer Applications and Software，2007，24（12）:130-132.

[3]李紅嬋，戶剛，朱顥東.基于群體優勢遺傳算法的高校排課問題研究[J].計算機工程與應用，2011，47（8）:1235-1237.

LI Hong-chan，HU Gang，ZHU Hao-dong.Research of UTP based on population dominant GA[J].Computer Engineering and Applications，2011，47（10）:233-236.

[4]金保華，李紅嬋.采用新型編碼GA的高校排課問題仿真研究[J].計算機工程與應用，2011，47（13）:1066-1069.

JIN Bao-hua，LI Hong-chan.Simulation study of UTP with new code GA[J].Computer Engineering and Applications，2011，47（13）:1066-1069.

[5]張立巖，張世民，秦敏.基于改進粒子群算法排課問題研究[J].河北科技大學學報，2011，32（3）:55-58.

ZHANG Li-yan，ZHANG Shi-min，QIN Min.Research in improved particle swarm optimization for schedule arrangement[J].Journal of Hebei University of Science and Technology，2011，32（3）:265-269

[6]高武奇，康鳳舉，鐘聯炯.基于沖突檢測算法的二級排課系統[J].西安工業大學學報，2008，5（28）:506-509.

GAO Wu-qi，KANG Feng-ju，ZHONG Lian-jiong.Two-level course arrangement system with collision detection algorithm[J].Journal of Xi’an Technological University，2008，5（28）:506-509.

[7]徐成剛，易軍凱，肖洋.基于約束邏輯程序設計的排課算法研究[J].計算機工程與應用，2006，42（31）:197-199.

XU Cheng-gang，YI Jun-kai，XIAO Yang.Constraint logic programming-based course timetabling algorithm[J].Computer Engineering and Applications，2006，42（31）:197-199.

[8]王鳳，林杰.高校排課問題的圖論模型及算法[J].計算機工程與應用，2009，45（27）:240-242.

WANG Feng，LIN Jie.Model of college time-table problem based on graph theory[J].Computer Engineering and Applications，2009，45（27）:240-242.

[9]王軍，陳建云.基于C#舟運用遺傳算法的排課系統[J].電子設計工程，2010，12（18）:85-88.

WANG Jun，CHEN Jian-yun.Apply genetic algorithm to design timetabling system based on C sharp[J].Electronic Design Engineering，2010，12（18）:85-88.

[10]滕姿，鄧輝文，楊久俊.基于遺傳算法的排課系統的設計與實現[J].計算機應用，2007，27（12）:199-201.

TENG Zi，DENG Hui-wen，YANG Jiu-jun.Timetabling system’s design and implementation based on the genetic algorithm[J].Journal of Computer Application，2007，27（12）:199-201.

[11]韋玉，馮速.免疫遺傳算法在排課問題中的應用[J].北京師范大學學報，2008，44（2）:168-172.

WEI Yu，FENG Su.The application of immune genetic algorithm in the problem of timetabling[J].Journal of Beijing Normal University，2008，44（2）:168-172.

[12]GUO Hong-bin，YAN Jing-feng.Research ofuniversity course scheduling system based on evolutionary algorithm[C]//

The 3rd International Conference on Computational Intelligence and Industrial Application （PACIIA2010），2010:238-240.