王蓮娟　李星華

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

關(guān)鍵詞：克隆原理;排課;時間單元

中圖分類號：TP301.6? ? ? 文獻標(biāo)識碼：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? 引? 言

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

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

1? 功能需求分析

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

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

正式排課之前需要設(shè)置開課計劃，主要任務(wù)是設(shè)置班級、課程、教師的對應(yīng)關(guān)系，為排課做好前期的準(zhǔn)備工作。

2? 數(shù)據(jù)庫設(shè)計

2.1? E-R模型

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

2.2? 數(shù)據(jù)表設(shè)計

根據(jù)E-R模型進行數(shù)據(jù)庫設(shè)計，需要在數(shù)據(jù)庫中構(gòu)建如下數(shù)據(jù)表：

學(xué)生表（學(xué)號，姓名，性別，身份證號，系，專業(yè)，班級……）

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

班級表（代碼，名稱，所在系，專業(yè)，人數(shù)，輔導(dǎo)員，教室）

課程表（代碼，名稱，開設(shè)系，課時，學(xué)分，性質(zhì)）

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

排課表（班級代碼，課程代碼，教師工號，上課時間單元，課程學(xué)時標(biāo)識）

3? 算法設(shè)計

3.1? 基于克隆原理的排課算法規(guī)則

（1）教師和學(xué)生都不能發(fā)生課時沖突，即沒有教師要同時給兩個（或兩個以上的）班上課，也沒有一個班要同時上兩門（或兩門以上）不同的課程;（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時間單元優(yōu)先排課;（6）所有課程從第一周上到最后一周;（7）所有教室均為統(tǒng)一規(guī)格的多媒體教室。

3.2? 設(shè)置開課計劃

設(shè)置開課計劃的主要任務(wù)是設(shè)置班級、課程、教師的對應(yīng)關(guān)系，存入排課表中。每2個課時為一個單元進行編排，如果一個教師給一個班級上的是4個課時的課程，則在排課表中出現(xiàn)2條記錄，通過增加一個課程學(xué)時標(biāo)識字段來區(qū)分（1表示這門課的1-2課時，2表示這門課的3-4課時，依此類推）。

3.3? 基于克隆原理的排課算法設(shè)計

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

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

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

4? 結(jié)? 論

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

參考文獻：

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

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

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

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