基于克隆原理的排課算法研究

王蓮娟　李星華

摘? 要：高校排課問題是數學和計算機領域的一個經典問題，如何將教室、教師、課程、班級、時間段等要素進行合理的安排，是排課算法需要重點研究和解決的問題。文章對排課問題的功能需求分析、數據庫設計、算法設計等幾個部分進行了闡述，提出了基于克隆原理的排課算法，通過時間單元對象的引入與時間段的合理劃分并與其他對象進行綁定實現對其他對象的克隆，可以把四維空間的問題進行轉化，從而簡化問題的復雜度，使復雜的排課問題得到解決。

關鍵詞：克隆原理;排課;時間單元

中圖分類號：TP301.6? ? ? 文獻標識碼：A 文章編號：2096-4706（2020）02-0018-03

Abstract：Course scheduling is a classic problem in the field of mathematics and computer science. The major issue that the course scheduling algorithm studies and aims to solve are how to arrange reasonably and scientifically the many factors including classrooms，teachers，courses，classes and time frame，etc. Through the elaboration of the functional needs analysis of course scheduling issues，design of database and algorithm，the author manages to propose the course scheduling algorithm based on clone principles. Through importing the object of time unit and dividing time frame reasonably and binding with other objects，the clone of these objects can be turned into reality，so that the problems in four-dimensional space can be converted and the complexity of the problems can be simplified，by which the complicated problem of course scheduling will be solved.

Keywords：clone theory;course scheduling;time unit

0? 引? 言

排課工作一直是各個學校教務處在教學管理中的重要工作之一，隨著招生規模的持續擴大，廣大高職院校的專業體系也變得越來越豐富和完善，這就為排課工作帶來了巨大的壓力。[1]在計算機技術出現之前，統籌安排各班級上課的時間需要人工來完成，在編排過程中花費大量的時間和精力，然而結果并不能令人滿意，經常會出現教師上課沖突的情況。隨著計算機技術的不斷發展，開發一個智能排課系統，讓計算機來代替人工排課成為可能。

智能排課系統開發主要包括服務器的建立和網頁的開發兩個方面。該系統能夠實現上課時間的安排、教室的安排，課程的安排、教師授課的安排，以及它們之間的不沖突和資源的高效利用等功能;切合學院教學需要，降低了排課管理工作的工作量，提高了工作效率，同時課程安排完成后，可迅速生成課表情況信息，為教學工作提供更多的方便。排課系統中最核心的技術就是排課算法，科學的排課算法能更好地利用各種資源，使課程安排更為合理，提高工作效率。

1? 功能需求分析

我院現有在校生3893人，教學班127個，多媒體教室133間，所有教室均安裝有多媒體教學設備，如高性能計算機、高清投影設備、無線麥克風、公放設備等，可以滿足所有班級日常教學的需求。按照目前的教學資源配置情況，每個班級可以固定一間教室授課，也可以采用流動教室形式授課。

排課問題主要綜合考慮的要素有教室、課程、教師、班級和時間段，將五個要素進行合理的組合，使資源配置最優化，得到最優的排課方案。排課算法重點要解決各種要素之間的沖突問題：同一時間段一個班級只能選擇一門課程;同一時刻同一個教室只能上一門課程;同一時刻一個教師只能上一門課程;給班級安排的教室必須可以容納所有上該課程的學生;必須要有特定的教室提供給特定課程使用;盡可能滿足大多數人相鄰兩節課上課地點近;體育課后盡量不要安排課程;[2]所有課程以2課時為一個單元進行編排;周三下午和周五下午不排課;所有課程從第一周上到最后一周。

正式排課之前需要設置開課計劃，主要任務是設置班級、課程、教師的對應關系，為排課做好前期的準備工作。

2? 數據庫設計

2.1? E-R模型

本排課算法中主要涉及的實體對象有學生、教師、教室、班級、課程、時間單元等。學生實體模型如圖1所示，教師實體模型如圖2所示，班級實體模型如圖3所示，課程實體模型如圖4所示，教室實體模型如圖5所示，時間單元實體模型如圖6所示，各實體聯系如圖7所示。

2.2? 數據表設計

根據E-R模型進行數據庫設計，需要在數據庫中構建如下數據表：

學生表（學號，姓名，性別，身份證號，系，專業，班級……）

教師表（工號，姓名，性別，身份證號，部門，職稱……）

班級表（代碼，名稱，所在系，專業，人數，輔導員，教室）

課程表（代碼，名稱，開設系，課時，學分，性質）

時間單元表（代碼，時間段）

排課表（班級代碼，課程代碼，教師工號，上課時間單元，課程學時標識）

3? 算法設計

3.1? 基于克隆原理的排課算法規則

（1）教師和學生都不能發生課時沖突，即沒有教師要同時給兩個（或兩個以上的）班上課，也沒有一個班要同時上兩門（或兩門以上）不同的課程;（2）所有課程以2課時為一個單元進行編排;（3）時間單元共分成20個，每周一至周五每天4個單元，每個單元包含2個課時，對20個單元依次編號，1-20號;（4）周三和周五下午不排課，即11-12、19-20時間單元不排課;（5）每天的課程盡可能安排在前3個單元，即1-3、5-7、9-10、13-15、17-18時間單元優先排課;（6）所有課程從第一周上到最后一周;（7）所有教室均為統一規格的多媒體教室。

3.2? 設置開課計劃

設置開課計劃的主要任務是設置班級、課程、教師的對應關系，存入排課表中。每2個課時為一個單元進行編排，如果一個教師給一個班級上的是4個課時的課程，則在排課表中出現2條記錄，通過增加一個課程學時標識字段來區分（1表示這門課的1-2課時，2表示這門課的3-4課時，依此類推）。

3.3? 基于克隆原理的排課算法設計

長期以來，人們在研究該如何排課這個問題時，選擇使用過許多不同的算法，如遺傳算法、模擬退火算法、回溯搜索算法、圖論算法等。[3]通過對現有排課算法的研究和學習，為了簡化算法，本算法在研究過程中按照班級固定教室的規則進行排課，可將教室作為班級的屬性。排課過程中先統一進行編排，對于個別課程有特殊要求的進行人工微調。

排課過程中以班級對象為基礎，遍歷所有的班級對象，對每個班級的所有課程進行編排，在編排每一門課程時需要判斷是否可以正常編排到對應的時間單元上（主要判斷所排時間單元對應的教師是否可以正常排課——每個教師分配到不同的時間單元，就相當于變成了多個教師克隆，當一個教師對應的時間單元已經被安排，則相當于這個教師克隆被占用，則后面再給這個教師排課時就不能再使用這個教師克隆。這里可以稱為克隆原理，同樣適用于教室和時間單元相結合，一個教室分配到不同的時間單元，就相當于多個教室克隆）。如果前面一個單元不能正常安排該門課程，則將該門課程往后面一個單元進行編排，直至把當前課程安排到一個時間單元上為止。安排完一門課程之后進行下一門課程的編排，直至所有課程編排結束為止。

這里的克隆原理又可以理解為時間轉實體原理，即將包含有時間的四維空間問題中的時間維度進行轉化，把時間維度分解成若干個時間單元和教師、教室對象進行綁定，相當于克隆出來多個教師和教室對象，從而簡化問題復雜度，達到實現排課算法的可行性的目的。

4? 結? 論

本文所闡述的基于克隆原理的排課算法是針對班級固定教室進行的研究，可以完成基本的排課功能，由于我院教學資源充足，按照固定教室的形式設置算法，可以滿足我院日常排課的要求。但在實際排課過程中，很多學校的教學資源有限，采取固定教室的形式排課，無法滿足日常教學的需求。為了算法能夠得到進一步推廣，更好地利用現有的教學資源，需要把所有教室輪換起來，每個班級都沒有固定教室，下一步將會針對這個問題對算法進一步優化，使排課算法更科學合理。

參考文獻：

[1] 梁利亭.遺傳算法在高職院校排課問題中的研究與應用 [J].湖北開放職業學院學報，2019，32（1）：76-78.

[2] 邵舒佳，趙盈，杜戰其.基于遺傳算法的高校排課分析 [J].科技創新與生產力，2015（11）：42-43+46.

[3] 李昕怡，蘇振華.基于邊著色理論的排課問題的應用 [J].懷化學院學報，2018，37（5）：33-36.

作者簡介：王蓮娟（1987.11-），女，漢族，北京人，教務學籍管理科副科長，本科，研究方向：算法、計算機應用;李星華（1979.08-），男，蒙古族，遼寧朝陽人，學生科科長，副研究員，研究生，研究方向：算法、數據庫、教育管理。