基于TOPSIS算法優(yōu)化高校實(shí)驗(yàn)排課系統(tǒng)研究與實(shí)現(xiàn)

謝旭 李艷玲 吳仁壽

摘 要：目前各高校、普通高校等教育機(jī)構(gòu)在教學(xué)排課上普遍采用回溯算法、貪心算法以及遺產(chǎn)算法等進(jìn)行課程編排，這種編排方式在編排數(shù)量大，約束復(fù)雜的情況下是無法得到人性化的排課效果，比如：學(xué)生上課在時(shí)間上過于擁擠，上課地點(diǎn)空間跨度太大，以上算法在計(jì)算機(jī)上執(zhí)行來完成排課工作還是會(huì)存在各種各樣的缺陷。目前所存在的排課算法研究也是相當(dāng)多的，但是在實(shí)際執(zhí)行結(jié)果上并不能完全適應(yīng)學(xué)生以及教師便捷地授課和上課的實(shí)際的需求。因而本文在已有研究基礎(chǔ)上提出基于TOPSIS算法來優(yōu)化高校實(shí)驗(yàn)排課設(shè)計(jì)以解決在課程安排緊湊，實(shí)驗(yàn)課室有限情況下的排課困難的問題。

關(guān)鍵詞：課程編排 TOPSIS算法 排課系統(tǒng)

中圖分類號：TP311.5 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2018）04（a）-0006-04

Abstract：At present colleges and universities， such as regular institutions of higher education institutions of backtracking algorithm is widely used in teaching process， a greedy algorithm and inheritance algorithm and so on carries on the curriculum arrangement， the layout in the choreography is big enough， constraint complex situations cannot be arranging the effect of human nature， such as students to class on time is too crowded， venue space span is too large， the above algorithm to perform on the computer to complete the course arrangement will exist all kinds of defects.At present， there are quite a lot of research on scheduling algorithms， but the actual implementation results cannot fully adapt to the students and the practical needs of teachers' convenient teaching and teaching.Therefore， based on the existing research， this paper proposes a TOPSIS algorithm to optimize the design of experimental courses in colleges and universities in order to solve the problem of difficulty in arranging courses under the tight schedule and limited experimental classrooms.

Key Words：Curriculum arrangement； TOPSIS algorithm； Course arranging sustem

排課一直是高校或者普通高中學(xué)校教學(xué)管理中一項(xiàng)重要且復(fù)雜的工作，特別是當(dāng)授課所需的設(shè)備設(shè)施稀缺或者教師課程安排緊湊時(shí)，都會(huì)造成學(xué)生、教師之間時(shí)間沖突以及課程錯(cuò)亂的矛盾。所以，編排科學(xué)并且可行性高的教學(xué)課表是教學(xué)開展的核心所在。編排課程表實(shí)質(zhì)上是在教學(xué)計(jì)劃己經(jīng)被制定好的基礎(chǔ)上，按照也理學(xué)和教育學(xué)原理，由教務(wù)科根據(jù)不同的約束條件以表格的形式合理、有效地安排教學(xué)計(jì)劃的過程[1]。在實(shí)際排課應(yīng)用中，由于個(gè)人時(shí)間安排、不同上課班級之間課程編排、實(shí)驗(yàn)教學(xué)設(shè)施資源有限等因素，排課算法在實(shí)際應(yīng)用中兼容性和通適性較差，無法保證所編排的課程都適應(yīng)所有人。因此，在算法設(shè)計(jì)方面，我們也力求約束條件之間能滿足大范圍學(xué)生的需求特點(diǎn)，優(yōu)化課程編排，以優(yōu)化在授課資源稀缺下，學(xué)校排課困難的問題。

1 目前國內(nèi)所存在的排課算法現(xiàn)狀

排課問題從數(shù)學(xué)上講，是一個(gè)在時(shí)間、教師、學(xué)生和教室四維空間，以培養(yǎng)方案和各種特殊要求為約束條件的組合規(guī)劃問題，其實(shí)質(zhì)就間，以培養(yǎng)方案和各種特殊要求為約束條件的組合規(guī)劃問題，其實(shí)質(zhì)就是解決各因素之間的沖突[2]。因此在設(shè)計(jì)與投入使用方面都有一定研究限制和難度，就研究范圍而已，目前國內(nèi)存在著多種多樣的排課算法，在實(shí)際應(yīng)用方面也算法的時(shí)間效率和耗費(fèi)的資源也不盡相同，常見使用的算法有遺傳算法、貪心算法、動(dòng)態(tài)規(guī)劃和回溯算法等。

例如：貪婪算法，貪婪算法的設(shè)計(jì)思想是分階段工作，在每一個(gè)階段選擇局部最優(yōu)，而不考慮將來后果。對最終的解不追求最優(yōu)解，能夠得到某種意義下的近似解的分級處理方法。貪婪算法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪算法常以當(dāng)前情況為基礎(chǔ)做最優(yōu)選擇，而不考慮各種可能的整體情況[3]。

又如回溯算法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法，它在包含問題所有解的一顆狀態(tài)空間樹上，按優(yōu)先條件向前搜索，以達(dá)到目標(biāo)。算法搜索至狀態(tài)空間樹上的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。若肯定不包含，則跳過對以該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。這種走不通就退回的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)點(diǎn)稱之為回溯點(diǎn)。回溯算法在用來求解問題的所有解時(shí)，要回溯到根且要搜索過根結(jié)點(diǎn)的所有子樹才可以結(jié)束，而在用來求解問題的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束[4]。

在實(shí)際應(yīng)用中，貪婪算法在求解排課問題上會(huì)出現(xiàn)同一班級上課時(shí)間集中或者太過于分散或者相連的不用科目上課的教師距離太過于遠(yuǎn)。這和他排序的算法有關(guān)，由于算法在排序時(shí)選擇的是局部最優(yōu)，也就意味著在不用約束條件中不能綜合考慮不同情況下的班級排課和上課時(shí)間之間相互協(xié)調(diào)。采用回溯算法，通過搜索節(jié)點(diǎn)的方式來確定排課的時(shí)間地點(diǎn)，相比貪婪算法，回溯算法在排課過程更為細(xì)膩，在排課質(zhì)量上，有更高的契合度和滿意度，使用情況良好。

就目前實(shí)驗(yàn)所使用的算法使用情況來看，排課算法之間優(yōu)劣都有差異，在研究了幾個(gè)常用算法的基礎(chǔ)上，提出使用TOPSIS算法來進(jìn)行排課設(shè)計(jì)，已解決對于任意一個(gè)班級排課難，排課不科學(xué)的問題，已提高排課的效率。

2 支持方便實(shí)用的互動(dòng)式實(shí)用式的系統(tǒng)設(shè)計(jì)

針對目前國內(nèi)主流的教學(xué)排課系統(tǒng)的兼容性和實(shí)用性入手，本系統(tǒng)以建議安裝的桌面應(yīng)用程序入手，方便教師與學(xué)生的使用。旨在打造一個(gè)易于使用的靈活性教學(xué)排課平臺，并且便捷的將排課結(jié)果導(dǎo)出供學(xué)生使用。

2.1 系統(tǒng)功能框圖

按照本系統(tǒng)的實(shí)際需求分析，以軟件工程理論為基礎(chǔ)和指導(dǎo)思想，初步確定本系統(tǒng)地功能結(jié)構(gòu)，如圖1所示。

2.1.1 初始設(shè)置

（1）歷史排課信息管理功能：對以前排課信息包含教師信息、教室信息以及班級信息進(jìn)行管理，為今后排課提供相關(guān)決策信息。

（2）清除系統(tǒng)數(shù)據(jù)功能：給重新編排的初值清零，避免系統(tǒng)混亂。

（3）設(shè)置系統(tǒng)值功能：為各使用單位提供便利。例如：設(shè)置學(xué)校名稱、學(xué)院名稱。

（4）排課初值設(shè)置功能：此功能與教學(xué)機(jī)制密切相關(guān)，用戶根據(jù)實(shí)際情況設(shè)置學(xué)期的教學(xué)周數(shù)以及每周的上課天數(shù)、每天開設(shè)的節(jié)次數(shù)等。

2.1.2 基本信息管理

基于本系統(tǒng)兼容性方面的考慮，諸如教師基本信息、教室基本信息、班級基本信息以及課程信息等可以借助人事管理系統(tǒng)、學(xué)籍管理系統(tǒng)直接導(dǎo)入，同時(shí)，導(dǎo)入的基本信息可去除冗余，并增加新的可用字段，并且各部分信息管理具有輸入、查詢、瀏覽、修改、刪除及打印各式報(bào)表的功能。

教學(xué)計(jì)劃管理是整個(gè)排課系統(tǒng)的根基，教學(xué)計(jì)劃管理規(guī)范可以說是整個(gè)排課工作進(jìn)行的先決條件，因?yàn)榻虒W(xué)計(jì)劃和專業(yè)緊密聯(lián)系，教學(xué)計(jì)劃的完備與否直接影響著專業(yè)開課計(jì)劃，所以它同樣具有輸入、查詢、瀏覽、修改、刪除及打印報(bào)表的功能。最后，還有教學(xué)日歷管理，它主要是準(zhǔn)確提供每個(gè)教學(xué)周所對應(yīng)的教學(xué)時(shí)間。

2.1.3 排課管理

理論課程的預(yù)安排是正式排課之前必須經(jīng)過的步驟，它目的是為了檢測教學(xué)任務(wù)是否安排合理、教學(xué)資源是否夠用、約束條件是否能夠滿足。

（1）遵循資源規(guī)劃實(shí)踐類教學(xué)環(huán)節(jié)進(jìn)程。

（2）理論教學(xué)任務(wù)根據(jù)進(jìn)程是否一致、人數(shù)多少、特殊要求來確定教室類型，并分教室類型統(tǒng)計(jì)教學(xué)總量，從而判斷教室是否滿足需求。

（3）滿足條件則提示預(yù)安排成功。

（4）若小教室不夠使用可安排大教室或合班，若大教室不夠則需要拆班。

（5）若特殊需求不能滿足則需要增添設(shè)備，經(jīng)調(diào)整繼續(xù)執(zhí)行直到滿足。

教學(xué)任務(wù)的管理就是指已經(jīng)編排好的教師的實(shí)際班級開課計(jì)劃，根據(jù)課程特點(diǎn)以及教師實(shí)際要求對教學(xué)任務(wù)表增加或刪除約束條件并添加輸入、查詢、瀏覽、修改、刪除及打印報(bào)表的功能。

自動(dòng)周次規(guī)劃管理就是指自動(dòng)排課之前對教師、教室以及班級所做的一種周次時(shí)間規(guī)劃，并為其提供可以安排理論教學(xué)的周數(shù)；然后，規(guī)劃出課程的周學(xué)時(shí)數(shù)。本系統(tǒng)中為教師、教室以及班級分別建立了一個(gè)規(guī)劃表專門用于對排課周次的控制，將不能用于理論課編排的時(shí)間全部鎖定。

最后，自動(dòng)排課管理按照完全整理好的排課數(shù)據(jù)用確定好的算法完成自動(dòng)編排。手工排課管理主要是增加本系統(tǒng)的靈活性，針對某些約束條件特殊或臨時(shí)調(diào)課的情況利用手工排課來解決沖突問題，達(dá)到成功排課的目的。

2.1.4 課表管理

教師任務(wù)書、教室課表、班級課表以及時(shí)間課表管理均能提供多樣化打印。

課表查詢功能可以隨時(shí)提供教師、教室、班級以及時(shí)間來查詢課表，同時(shí)，還可以進(jìn)行組合查詢?yōu)檎{(diào)課提供準(zhǔn)確可靠的信息。

2.1.5 工作量管理

此功能主要是加強(qiáng)學(xué)校對于教師工作量的管理，規(guī)范工作量計(jì)算辦法，其中計(jì)算機(jī)公式是計(jì)算工作量的政策依據(jù)，不同學(xué)校標(biāo)準(zhǔn)并不一致，而且計(jì)算辦法也在不斷更新，為了保證系統(tǒng)具有一定的通用性，計(jì)算公式的管理可以對計(jì)算公式進(jìn)行隨時(shí)調(diào)整以適應(yīng)不同需要。

2.1.6 系統(tǒng)設(shè)置

為了增強(qiáng)系統(tǒng)可靠性和安全性，專門在系統(tǒng)設(shè)置中添加數(shù)據(jù)備份和數(shù)據(jù)恢復(fù)功能，便于今后對數(shù)據(jù)更新和維護(hù)，其中用戶管理是對用戶名、密碼、權(quán)限的修改的設(shè)置；代碼維護(hù)是指完成對系統(tǒng)中所用到的所有代碼更新和維護(hù)。

2.2 TOPSIS排課算法設(shè)計(jì)

TOPSIS法是C.L.Hwang和K.Yoon于1981年首次提出，TOPSIS法根據(jù)有限個(gè)評價(jià)對象與理想化目標(biāo)的接近程度進(jìn)行排序的方法，是在現(xiàn)有的對象中進(jìn)行相對優(yōu)劣的評價(jià)。TOPSIS法是多目標(biāo)決策中常用方法之一，通過監(jiān)測評價(jià)對象中最優(yōu)解與最劣解的距離來進(jìn)行排序，當(dāng)評價(jià)對象最靠近最優(yōu)秀解的同時(shí)又遠(yuǎn)離最劣解，則是最理想的決策，反之，則為不理想決策。即在課程編排過程，通過計(jì)算不同等待排課班級在所指定時(shí)間段內(nèi)，選中具體班級使用實(shí)驗(yàn)可使整個(gè)排課過程在排課方案中最接近最優(yōu)解的同時(shí)又遠(yuǎn)離最劣解。

2.3 TOPSIS算法原理簡述

首先對n個(gè)評價(jià)單元選擇p個(gè)評價(jià)指標(biāo)進(jìn)行綜合評價(jià) （如果p個(gè)指標(biāo)中有逆向指標(biāo)或適度指標(biāo)，則將其正向化），原始數(shù)據(jù)矩陣如下：

依照相對貼近度的大小對目標(biāo)進(jìn)行排序，形成決策依據(jù)。

在同一時(shí)間段，對有上課的教室所能上課的班級進(jìn)行排課的選擇，就轉(zhuǎn)變?yōu)橛?jì)算需要上課班級選擇所需要課室的屬性值，并進(jìn)行決策排序。

相比論文在上文所提到的各類算法在使用過程的排課過程中的基本原理，使用TOPSIS算法進(jìn)行排課在排課過程能夠有效地減少類似其他排課算法容易出現(xiàn)的課程擁擠、幾何空間跨度大、課室分配不合理等現(xiàn)象。通過正理想值與負(fù)理想值所計(jì)算出來的最優(yōu)解與最劣解來衡量對比排課過程所出現(xiàn)的可能性選擇，并且選擇最有的可能性排課。這樣的排課算法，顯然有一下幾個(gè)優(yōu)點(diǎn)。

（1）保證學(xué)生所有課程在上課期間分布均勻。

（2）保證學(xué)生在同一上課時(shí)間段所經(jīng)過的空間距離不會(huì)太遠(yuǎn)。

（3）保證教師在授課和教室之間的時(shí)間安排分布均勻.

（4）保證學(xué)校所有的教學(xué)資源充分地利用。

在計(jì)算機(jī)編程方面，將復(fù)雜的編排情況轉(zhuǎn)化為可計(jì)算的矩陣以及可量化的指標(biāo)來時(shí)間結(jié)果的輸出，實(shí)現(xiàn)科學(xué)的編程過程，使整個(gè)系統(tǒng)在開發(fā)過程更加快捷，且算法實(shí)現(xiàn)難度適中，便于實(shí)現(xiàn)。

2.4 系統(tǒng)的架構(gòu)與部署

在算法設(shè)計(jì)以及為了更加便于實(shí)現(xiàn)以投入使用，在系統(tǒng)設(shè)計(jì)上，采用C/S結(jié)構(gòu)，通過服務(wù)器端的管理控制以及數(shù)據(jù)保存，服務(wù)器端以一個(gè)軟件包的形式簡易安裝我Windows平臺上，方便教師在教學(xué)管理和課程安排，并且極大的節(jié)省了排課時(shí)間。

系統(tǒng)采用Visual Studio 2015作為開發(fā)工具，采用SqlServer 2008數(shù)據(jù)庫來存儲(chǔ)數(shù)據(jù)，使系統(tǒng)在Windows上更加兼容。并且，系統(tǒng)開發(fā)也采用三層架構(gòu)來進(jìn)行開發(fā)，分清界面層（User Interface layer）、業(yè)務(wù)邏輯層（Business Logic Layer）、數(shù)據(jù)訪問層（Data access layer），使系統(tǒng)結(jié)構(gòu)更加的明確，可以降低層與層之間的依賴，并且在后期維護(hù)的時(shí)候，極大地降低了維護(hù)成本和維護(hù)時(shí)間[5]。

在安裝部署上，將數(shù)據(jù)與編排任務(wù)合理分配到Client端和Server端，降低了系統(tǒng)的通訊開銷，在使用本排課系統(tǒng)時(shí)需要安裝客戶端才可進(jìn)行管理操作。客戶端和服務(wù)器端的程序不同，用戶的程序主要在客戶端，服務(wù)器端主要提供數(shù)據(jù)管理、數(shù)據(jù)共享、數(shù)據(jù)及系統(tǒng)維護(hù)和并發(fā)控制等，客戶端程序主要完成用戶的具體的業(yè)務(wù)。當(dāng)教師需要進(jìn)行排課時(shí)，只需要在Windows平臺安裝軟件安裝包，即可使用并且再次使用不用重復(fù)安裝。

2.5 TOPSIS算法在排課上的實(shí)現(xiàn)

開發(fā)后的系統(tǒng)可以在導(dǎo)入班級信息后選擇班級所需要進(jìn)行的實(shí)驗(yàn)，并且實(shí)現(xiàn)可選課程來進(jìn)行排課，結(jié)果顯示如圖3所示。

不僅學(xué)生所需進(jìn)行的實(shí)驗(yàn)可選，上課時(shí)間也可以進(jìn)行選擇，確保教師在教學(xué)安排上更具靈活性，并且加此約束進(jìn)行排課。

在本系統(tǒng)中，排課的最終結(jié)果將以excel表格形式導(dǎo)出，方便師生在教學(xué)過程使用。

3 結(jié)語

高校排課一直是作為實(shí)用型研究項(xiàng)目的研究對象，其算法在設(shè)計(jì)上也有較高的復(fù)雜性和時(shí)間復(fù)雜度，因而在實(shí)際應(yīng)用中也會(huì)存在各種特殊情況與不合理的編排，通過對比多種排課算法設(shè)計(jì)在設(shè)計(jì)與實(shí)際執(zhí)行的情況，本論文提出利用TOPSIS算法來優(yōu)化高校實(shí)驗(yàn)課程的編排，盡最大的努力來使排課更加人性化與具有更高的現(xiàn)實(shí)可執(zhí)行性。

參考文獻(xiàn)

[1] 李雙成.中職學(xué)校排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].華南理工大學(xué)，2014

[2] 楊緒華.佳木斯大學(xué)排課系統(tǒng)的分析與設(shè)計(jì)[D].北京郵電大學(xué)，2016

[3] 高明芳，趙敏.高校自動(dòng)排課系統(tǒng)排課算法的研究與設(shè)計(jì)[J].電腦知識與技術(shù)，2010，6（29）：8229-8230，8233.

[4] 張華.智能排課算法的研究及實(shí)現(xiàn)[D].山東大學(xué)，2010.

[5] 孟亞輝.基于校園網(wǎng)的多協(xié)議節(jié)約資源型離線下載系統(tǒng)設(shè)計(jì)[J].廣東石油化工學(xué)院學(xué)報(bào)，2016（4）：32-36.