基于繼承的高校排課策略研究

常可沛，李琴，李臣學(xué)

摘要：以上海理工大學(xué)本科生排課為例，經(jīng)統(tǒng)計(jì)分析，排課過程中產(chǎn)生了大量的冗余工作量。分析影響排課的各項(xiàng)因素，對排課差異性影響較大的專業(yè)培養(yǎng)計(jì)劃變動進(jìn)行了著重分析研究，并提出針對培養(yǎng)計(jì)劃變動的排課策略，通過試驗(yàn)，將此策略應(yīng)用于實(shí)際的專業(yè)課程表編排中，可以有效提高排課效率，降低沖突率，極大地優(yōu)化了排課過程。

關(guān)鍵詞：排課;差異性;繼承

中圖分類號：G642.0 ? ? 文獻(xiàn)標(biāo)志碼：A ? ? 文章編號：1674-9324（2020）01-0075-02

一、引言

教學(xué)任務(wù)安排是高校教務(wù)管理日常工作中最重要、最基本的環(huán)節(jié)，對后續(xù)教學(xué)活動的順利開展進(jìn)行起著關(guān)鍵的作用，是穩(wěn)定教學(xué)秩序的主要因素。為不同專業(yè)制定出科學(xué)高效的課程表，一方面能夠優(yōu)化教師授課安排、教學(xué)效果以及學(xué)生的學(xué)習(xí)效果，另一方面可以充分利用學(xué)校的各種資源，避免因分配不均衡而導(dǎo)致的資源緊張或資源浪費(fèi)。

一直以來，大多數(shù)的高校排課算法研究是將課程安排作為一個(gè)運(yùn)籌學(xué)時(shí)間表問題進(jìn)行處理，目前已有眾多算法研究應(yīng)用于課程表編排，如遺傳算法[1，2]、蟻群算法、模擬退火算法等，并在此基礎(chǔ)上有所改進(jìn)，以適應(yīng)不同的課程表編排需求[3]。不過，以上算法都是對課程進(jìn)行一次重新地安排。本文則以上海理工大學(xué)本科生排課為例，考慮到課程表重新編排產(chǎn)生的冗余工作量，通過學(xué)年之間課程表差異性的原因分析，研究出一種針對差異的排課策略。以專業(yè)的實(shí)際情況試驗(yàn)，并通過沖突檢測檢驗(yàn)此排課策略的效果。

二、排課問題分析和描述

上海理工大學(xué)本科生教學(xué)實(shí)行完全學(xué)分制，學(xué)生按照培養(yǎng)計(jì)劃并結(jié)合自己的專業(yè)要求及興趣進(jìn)行選課，最終修讀完成后達(dá)到畢業(yè)條件。畢業(yè)條件為學(xué)生培養(yǎng)計(jì)劃中各個(gè)課程組學(xué)分均達(dá)到要求。按照專業(yè)具體修讀計(jì)劃，部分課程組中可修讀學(xué)分?jǐn)?shù)與要求學(xué)分?jǐn)?shù)一致，此類課程組中所有課程為必修課程;而另一部分課程組中可修讀學(xué)分?jǐn)?shù)大于要求學(xué)分?jǐn)?shù)，這類課程組中學(xué)生有一定的選擇空間，可以在所列課程中根據(jù)自己專業(yè)需求和興趣所在進(jìn)行選擇性修讀。每個(gè)學(xué)期課程的開設(shè)及安排，最終的原始需求都是源于專業(yè)的培養(yǎng)計(jì)劃，培養(yǎng)計(jì)劃中所要求的課程即為當(dāng)學(xué)期應(yīng)開設(shè)的課程，因此專業(yè)培養(yǎng)計(jì)劃的變動直接影響到當(dāng)前學(xué)期的開課安排。

目前上海理工大學(xué)課程安排都是以手工安排的方式進(jìn)行，存在如下現(xiàn)狀：每個(gè)學(xué)期每門課程均為手工排課，每學(xué)期需要排課數(shù)量超過3000個(gè)教學(xué)班，效率低下，并且其中很多為重復(fù)工作量。根據(jù)2016—2017學(xué)年和2017—2018學(xué)年和兩個(gè)學(xué)年四個(gè)學(xué)期的學(xué)科基礎(chǔ)和專業(yè)課程對比統(tǒng)計(jì)，課程重復(fù)率平均約為84%，可以看出在完全手工排課的過程中，大量的工作量都是重復(fù)的。

本科生課程表編排涉及多方面的因素，主要包括：所開課程、上課時(shí)間、上課地點(diǎn)、任課教師、任務(wù)人數(shù)、專業(yè)計(jì)劃等。以上海理工大學(xué)的實(shí)際情況來看，學(xué)科基礎(chǔ)和專業(yè)課開設(shè)的任課教師、任務(wù)人數(shù)沒有太大的變化，具有較高的重復(fù)性。

三、基于繼承的課程安排策略研究

專業(yè)培養(yǎng)計(jì)劃變更包含以下幾種情況：減少課程;增加課程;課程建議修讀學(xué)期變更（此類變更等同于在某個(gè)年級專業(yè)中減少課程并且在另一個(gè)年級專業(yè)中增加課程）;課程歸屬課程組變更（此類變更等同于某個(gè)課程組減少課程，某個(gè)課程組增加課程）。因此，針對計(jì)劃變更，課程安排均可以減少或增加課程這兩種操作實(shí)現(xiàn)。

以前一學(xué)年的課程為基礎(chǔ)，進(jìn)行下一學(xué)年學(xué)期的差異性課程編排，首先要對原始課程表進(jìn)行數(shù)據(jù)化。每一門課的排課信息可描述為一個(gè)集合：{課程（C），學(xué)分?jǐn)?shù)（c），任課教師（T），上課時(shí)間（t），年級專業(yè)（S），課程組（R）}。因原始數(shù)據(jù)的上課地點(diǎn)已經(jīng)進(jìn)行了安排，不存在資源不夠使用的情況，因此教室資源不列在課程信息中，但在后面新增課程的安排時(shí)，需要考慮避開教室使用率較高的時(shí)間段，這個(gè)將在后文中描述。按照學(xué)科基礎(chǔ)和專業(yè)課的時(shí)間約束，將課程時(shí)間C列為一個(gè)矩陣，i=a、b、c、d，代表每天的12節(jié)、34/345節(jié)、67節(jié)、89節(jié)，j=1、2、3、4、5，代表周一、周二、周三、周四、周五，上課時(shí)間t=ij。

在以上課程模型的基礎(chǔ)上，進(jìn)行新學(xué)年學(xué)期的課程編排，以某年級某專業(yè)的一張課程表為編排的基本對象，將需要編排課程表的學(xué)期課程羅列出來，并對比兩個(gè)學(xué)年學(xué)期的專業(yè)培養(yǎng)計(jì)劃：（1）將沒有進(jìn)行過計(jì)劃變更的課程，直接繼承前一年的編排信息。（2）對于減少課程的任務(wù)變更，在新學(xué)年學(xué)期的課程表中直接將此門課程的信息去掉。（3）對于增加課程的任務(wù)變更，按照如下邏輯進(jìn)行對新增課程Ci安排時(shí)間。搜尋本年級專業(yè)課程表S=Si中不沖突的時(shí)間Sit≠Siti，并且整張課程表中任課教師不沖突的時(shí)間Tit≠Titi，同時(shí)考慮到教室資源使用率較高的情況，避開資源緊張的時(shí)間段，按照以下時(shí)間搜索策略：①如果課程學(xué)分?jǐn)?shù)Ci={1，2，4，6}（目前排課最大學(xué)分?jǐn)?shù)為6），在本年級專業(yè)課程表S=Si的課程中搜尋t={iaj1，idj1，iaj2，idj2，

iaj3，idj3，iaj4，idj4，iaj5，idj5，icj1，icj2，icj3，icj4，icj5，ibj1，ibj2，ibj3，ibj4，ibj5}中Tit≠Titi的1段/2段/3段空余時(shí)間，并寫入Ci的課程信息。②如果課程學(xué)分?jǐn)?shù)Ci=3，則在本年級專業(yè)課程表S=Si的課程中搜尋t={ibj1，ibj2，ibj3，ibj4，ibj5}中的空余時(shí)間，并在整張課程表中對比是否有Tit相同的課程存在，如Tit≠Titi，則為可用時(shí)間段，即可安排并寫入課程編排信息，如果存在Tit=Titi，則此集合中時(shí)間段均不可用，則在t={iaj1，idj1，iaj2，idj2，iaj3，idj3，iaj4，idj4，iaj5，idj5}中按照同樣的約束條件搜尋兩段空余時(shí)間并寫入Ci的課程信息。③如果課程學(xué)分?jǐn)?shù)Ci=5，則首先在本年級專業(yè)課程表S=Si的課程中搜尋t={ibj1，ibj2，ibj3，ibj4，ibj5}中的空余時(shí)間，并在整張課程表中對比是否有Tit相同的課程存在，如Tit≠Titi，則為可用時(shí)間段，將其寫入課程編排信息并繼續(xù)在t={iaj1，idj1，iaj2，idj2，iaj3，idj3，iaj4，idj4，iaj5，idj5，icj1，icj2，icj3，icj4，icj5}中按照同樣的約束條件搜尋第二個(gè)時(shí)間段并寫入課程信息;如果存在Tit=Titi，則此集合中時(shí)間段均不可用，則在t={iaj1，idj1，iaj2，idj2，iaj3，idj3，iaj4，idj4，iaj5，idj5，icj1，icj2，icj3，icj4，icj5}中按照同樣的約束條件搜尋三段空余時(shí)間并寫入Ci的課程信息。④如果經(jīng)過搜尋沒有合適的時(shí)間可以安排，則在課程組Ri中，尋找可沖突安排的課程時(shí)間，將兩門課重疊安排，可沖突安排的課程組一定是包含的學(xué)分?jǐn)?shù)大于課程組要求的學(xué)分?jǐn)?shù)，搜索R=Ri且S=Si，將課程時(shí)間t寫入Ci的課程信息。⑤如果以上策略均無法搜索到合適的課程時(shí)間，則需要考慮專業(yè)培養(yǎng)計(jì)劃的變更是否合理，是否超出了此年級專業(yè)的最大課程數(shù)量，可將此結(jié)果反饋給相關(guān)專業(yè)負(fù)責(zé)人作為參考進(jìn)行重新衡量。

以上策略按照課程的學(xué)分?jǐn)?shù)不同，選取了不同的課程時(shí)間搜索范圍，并且在搜索的時(shí)間范圍內(nèi)，按照上課資源緊張程度排列，資源緊張的時(shí)間段排在后面，優(yōu)先搜索資源較為充足的時(shí)間段，保證了資源的平均分配。

為了驗(yàn)證此排課策略，特選取上海理工大學(xué)2017—2018學(xué)年和2018—2019學(xué)年培養(yǎng)計(jì)劃中的八個(gè)專業(yè)課程變更情況進(jìn)行例證，這幾個(gè)專業(yè)的專業(yè)計(jì)劃變更涵蓋了以上專業(yè)計(jì)劃變更的四種情況分析。在Excel環(huán)境下將此策略轉(zhuǎn)換成函數(shù)代碼進(jìn)行驗(yàn)證。經(jīng)試驗(yàn)，新編排出的課程表符合新的專業(yè)培養(yǎng)計(jì)劃要求，并且可以完全通過沖突檢測。

四、小結(jié)

專業(yè)培養(yǎng)計(jì)劃是教學(xué)任務(wù)安排的依據(jù)，本文根據(jù)上海理工大學(xué)的實(shí)際情況進(jìn)行分析，提取專業(yè)培養(yǎng)計(jì)劃的變動并針對改動點(diǎn)進(jìn)行課程編排，以繼承的方式完成了新一學(xué)期的課程編排的策略研究，極大地提高了排課的工作效率;另一方面，專業(yè)培養(yǎng)計(jì)劃是教學(xué)任務(wù)安排的前期工作，將課程編排工作提前至專業(yè)計(jì)劃環(huán)節(jié)，可以較早發(fā)現(xiàn)任務(wù)中的問題，從而避免在之后的排課選課過程中因發(fā)現(xiàn)問題較晚而產(chǎn)生被動的情況。

參考文獻(xiàn)：

[1]王衛(wèi)紅，李文瓊.基于改進(jìn)遺傳算法的高中走班制排課算法[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2016，44（6）：601-607.

[2]韋玉，馮速.免疫遺傳算法在排課問題中的應(yīng)用[J].北京師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，44（2）：168-173.

[3]宗薇.高校智能排課系統(tǒng)算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)仿真，2011，28（12）：389-392.

Study on University Courses Arrangement Based on Inheritance

—A case study of undergraduate course arrangement in University of Shanghai for Science and Technology

CHANG Ke-pei，LI Qin，LI Chen-xue

（Office of Educational Administration，University of Shanghai for Science and Technology，

Shanghai 200093，China）

Abstract：Taking the undergraduate courses scheduling of USST as an example，a large amount of redundant workload has been generated in the courses scheduling through statistical analysis.This paper analyses the factors influencing the courses arrangement，emphatically analyses the changes of the professional training plan which have great influence on the difference of the courses arrangement，and puts forward the strategy of the courses arrangement which according to the change of the training plan.Through the experiment，applying this strategy to the actual courses arrangement can effectively improve the efficiency of the courses arrangement，reduce the conflict rate and greatly optimize the courses arrangement process.

Key words：courses arrangement;difference;inheritance