一種邏輯決策的排課算法

屈正庚

（商洛學(xué)院 計算機科學(xué)系，陜西 商洛 726000）

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

1 解決排課問題的思路

1.1 基本思想

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

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

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

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

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

1.2 解決問題的流程

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

圖1 排課流程Fig.1 Scheduling process

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

2 邏輯決策的排課算法

2.1 算法的思想

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

2.2 算法的關(guān)鍵技術(shù)

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

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

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

表2 教師課表Tab.2 Teachers curriculum

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

如果教師與時間和教室按位進(jìn)行邏輯或運算，結(jié)果為“1”表示有沖突發(fā)生，則進(jìn)一步對教師與時間和教室按位進(jìn)行邏輯與運算，結(jié)果為“0”表示沖突可以解決，根據(jù)課程加權(quán)值進(jìn)行排序，采用協(xié)商技術(shù)。結(jié)果為“1”表示最嚴(yán)重，就要轉(zhuǎn)變決策，這時要回到初始狀態(tài)，重新分配資源。

3 邏輯決策的算法實驗結(jié)果

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

假設(shè)現(xiàn)在只有2個教室供班級上課，一周上課時間5天，每天安排4大節(jié)課程，對班級的一周課程進(jìn)行安排。教學(xué)安進(jìn)度表如表3所示。

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

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

表4 班級課表Tab.4 Class curriculum

地理 1班：周一（1-2）上文學(xué)欣賞，周二（1-2）上基礎(chǔ)數(shù)學(xué)，周三（1-2）上哲學(xué)，（3-4）上文學(xué)欣賞，周四（1-2）上公共體育，（3-4）上基礎(chǔ)數(shù)學(xué)，周五（3-4）上經(jīng)濟學(xué)。

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

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

4 結(jié)束語

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

[1]楊東風(fēng).自愿選課算法分析與優(yōu)化研究[J].電子設(shè)計工程，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]祝勇仁，曹煥亞.應(yīng)用遺傳算法求解排課問題[J].計算機應(yīng)

用與軟件，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]李紅嬋，戶剛，朱顥東.基于群體優(yōu)勢遺傳算法的高校排課問題研究[J].計算機工程與應(yīng)用，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].計算機工程與應(yīng)用，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ìn)粒子群算法排課問題研究[J].河北科技大學(xué)學(xué)報，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]高武奇，康鳳舉，鐘聯(lián)炯.基于沖突檢測算法的二級排課系統(tǒng)[J].西安工業(yè)大學(xué)學(xué)報，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]徐成剛，易軍凱，肖洋.基于約束邏輯程序設(shè)計的排課算法研究[J].計算機工程與應(yīng)用，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].計算機工程與應(yīng)用，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#舟運用遺傳算法的排課系統(tǒng)[J].電子設(shè)計工程，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]滕姿，鄧輝文，楊久俊.基于遺傳算法的排課系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機應(yīng)用，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]韋玉，馮速.免疫遺傳算法在排課問題中的應(yīng)用[J].北京師范大學(xué)學(xué)報，2008，44（2）:168-172.

WEI Yu，F(xiàn)ENG 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.