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

王蓮娟　李星華

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

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

中圖分類號(hào)：TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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? 引? 言

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

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

1? 功能需求分析

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

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

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

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

2.1? E-R模型

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

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

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

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

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

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

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

時(shí)間單元表（代碼，時(shí)間段）

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

3? 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

4? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

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

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