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

謝旭 李艷玲 吳仁壽

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

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

中圖分類號：TP311.5 文獻標識碼：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

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

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

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

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

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

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

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

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

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

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

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

2.1.1 初始設(shè)置

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

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

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

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

2.1.2 基本信息管理

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

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

2.1.3 排課管理

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

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

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

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

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

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

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

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

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

2.1.4 課表管理

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

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

2.1.5 工作量管理

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

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

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

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

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

2.3 TOPSIS算法原理簡述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

參考文獻

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

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

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

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

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