高校排課問題的研究

彭志勇+楊鴻章

摘要：本文對排課問題進行了詳細的描述，并對所提出的問題進行了分析，探討了排課問題的約束條件，最后求解出排課問題的數學模型。

關鍵詞：排課問題；約束關系；數學模型

一、 排課問題的概述

新的教育體制對課表的編排在隨著現代教學的改革以及各項教育工程的實施開始有了較大的變化，編排課表在學校的教務管理工作中，是一件非常復雜而且棘手的工作。首先，根據各因素間約束關系的不同，將多重約束條件分為硬約束和軟約束，從而可以得出各因素之間的有效的矩陣。除此之外，在每一個時間上都相應的安排課程，再以0～1規劃方法分別將教師、教室分配到課表上的不同時間段上。通過0～1規劃的方法進行改進并優化，將多重約束條件加入其中，將偏好系數應用當中，建立排課模型，按照題目所給出的數據，使用計算機編程，并進行模型驗證，求出所需要的課程表，最后給出教師、教室的配置建議。

從數學角度上講，主要建立一個排課模型，并建立一個關于課程類別、教室編號的C～R關系表，然后建立目標函數，也就是對模型進行優化。最后，按照各種因素對排課模型的優先度進行計算，從而能夠得出排課模型的最優解。

初始化排課問題，課程類別、教室編號、教師上課時間這三個方面存在一定的關系，它們分別是1對1的對應關系，1對n的對應關系和n對n的對應關系。

因此，我們再對它們之間的屬性進行分析，根據它們之間的相互關聯可以得出相對合理的排課方案，最后來分析方案的合理性。

二、 排課問題要素的分析

為了保證學校日常工作以及教學任務的順利完成，而又能很好的在排課過程中避免各因素間的沖突，我們對以下幾個重要因素進行了詳細的分析。

（一） 課程

課程編排的時候安排時間的一個重要對象就是課程，課程的性質通常體現在以下幾個方面，每門課程的性質的值都會影響課程安排的最終結果。

課時數，在每一周的教學計劃當中教務人員必須對每門課程預先設定課時數，每周必須要安排一定的課時數，必須要有足夠的時間段安排給那些課程。

課程具有可拆的性質，通常情況下，每次上課的節數為2節，當有些課程每周的課時大于2節課的時候，那么就要將課程分成兩次或者多次來進行。

課程的類別，大學的課程主要分為公共課和專業課，其中公共課主要包括英語、數學等基礎課程。

（二） 教師

在教學環節中，其中最重要的資源之一就是教師，在教務人員排課的過程中，都是一個教師兼任幾門課程，這也就是所謂的一對多的關系。教師相應的屬性主要有教師編號，所能勝任的課程類別、上課時間要求等。

（三） 教室

每門課程要安排一個合理的教室來用，在安排教室的過程中也要考慮到很多因素，教室的主要屬性有教室編號、最大座位數、教室類別等，我們對教室屬性的描述主要包括以下幾點：

教室類別

教室的類別主要有多媒體教室、普通教室、計算機機房等。針對于不同的課程，我們應該給這些課程安排一個合理的教室。

教室的使用情況

教室在同一段時間只能讓一門課程來使用，我們應該對教室的資源進行充分的利用。

最大座位數

為了保證課程安排的合理性，上課的人數不能超過教室的最大座位數。在上公共課的時候，幾個班級合在一起上，必須安排在大教室上課，而小班教學的課程，則可以安排在較小的教室，這樣就可以對資源進行充分的利用。

三、 排課問題數學模型的建立

通過對排課問題進行分析，課程必須得全部安排在一個星期之內這樣才合理。我們把一個星期分成五天，分別用1、2、3、4、5這五個數字來進行表示，把每一天按四個部分來劃分，分別用a、b、c、d這四個字母來進行表示，這樣，我們便得出了一個5×4的矩陣。其中，星期一、星期二、星期三、星期四、星期五可以用j=1、2、3、4、5來進行表示；而i=a、b、c、d代表1、2節課，3、4節課，5、6節課和7、8節課。

（一） 約束條件

當約束條件不一樣時，可以排列組合時間和空間，從而來開展正常的教學工作，對于一張課表而言，它至少需要具備以下幾個硬約束條件：

a. 任課教師之間不能夠產生沖突；

b. 上課的教室不能產生沖突；

c. 專業之間不能夠相互沖突。

（二） 建立一般模型

參考文獻：

[1] 樊星.利用遺傳算法求解大學課表問題[J].科學技術與工程，2007，（09）：87-89.

[2] 陳誼，楊怡，張國龍，王尚忠.基于優先級自動排課算法PCSA的設計與實現方案[J].北京工商大學學報（自然科學版），2002，（02）：96-98.

[3] 熊余賢.排課算法對比研究及一些新思路[J].大視野，2008，（07）：65-66.

[4] 李琳，李秀娟，周德祥.計算機排課系統的設計與實現[J].鄭州工業高等專科學校學報，2004，（02）：81-83.

[5] 龔莎.基于回溯法的自動排課算法[J].硅谷，2010，（15）：78-80.

[6] 張穎，劉艷秋.軟計算方法[M].北京：科學出版社，2004：57-80.endprint