彭志勇+楊鴻章

摘要：本文對(duì)排課問題進(jìn)行了詳細(xì)的描述，并對(duì)所提出的問題進(jìn)行了分析，探討了排課問題的約束條件，最后求解出排課問題的數(shù)學(xué)模型。

關(guān)鍵詞：排課問題；約束關(guān)系；數(shù)學(xué)模型

一、 排課問題的概述

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

從數(shù)學(xué)角度上講，主要建立一個(gè)排課模型，并建立一個(gè)關(guān)于課程類別、教室編號(hào)的C～R關(guān)系表，然后建立目標(biāo)函數(shù)，也就是對(duì)模型進(jìn)行優(yōu)化。最后，按照各種因素對(duì)排課模型的優(yōu)先度進(jìn)行計(jì)算，從而能夠得出排課模型的最優(yōu)解。

初始化排課問題，課程類別、教室編號(hào)、教師上課時(shí)間這三個(gè)方面存在一定的關(guān)系，它們分別是1對(duì)1的對(duì)應(yīng)關(guān)系，1對(duì)n的對(duì)應(yīng)關(guān)系和n對(duì)n的對(duì)應(yīng)關(guān)系。

因此，我們?cè)賹?duì)它們之間的屬性進(jìn)行分析，根據(jù)它們之間的相互關(guān)聯(lián)可以得出相對(duì)合理的排課方案，最后來分析方案的合理性。

二、 排課問題要素的分析

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

（一） 課程

課程編排的時(shí)候安排時(shí)間的一個(gè)重要對(duì)象就是課程，課程的性質(zhì)通常體現(xiàn)在以下幾個(gè)方面，每門課程的性質(zhì)的值都會(huì)影響課程安排的最終結(jié)果。

課時(shí)數(shù)，在每一周的教學(xué)計(jì)劃當(dāng)中教務(wù)人員必須對(duì)每門課程預(yù)先設(shè)定課時(shí)數(shù)，每周必須要安排一定的課時(shí)數(shù)，必須要有足夠的時(shí)間段安排給那些課程。

課程具有可拆的性質(zhì)，通常情況下，每次上課的節(jié)數(shù)為2節(jié)，當(dāng)有些課程每周的課時(shí)大于2節(jié)課的時(shí)候，那么就要將課程分成兩次或者多次來進(jìn)行。

課程的類別，大學(xué)的課程主要分為公共課和專業(yè)課，其中公共課主要包括英語、數(shù)學(xué)等基礎(chǔ)課程。

（二） 教師

在教學(xué)環(huán)節(jié)中，其中最重要的資源之一就是教師，在教務(wù)人員排課的過程中，都是一個(gè)教師兼任幾門課程，這也就是所謂的一對(duì)多的關(guān)系。教師相應(yīng)的屬性主要有教師編號(hào)，所能勝任的課程類別、上課時(shí)間要求等。

（三） 教室

每門課程要安排一個(gè)合理的教室來用，在安排教室的過程中也要考慮到很多因素，教室的主要屬性有教室編號(hào)、最大座位數(shù)、教室類別等，我們對(duì)教室屬性的描述主要包括以下幾點(diǎn)：

教室類別

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

教室的使用情況

教室在同一段時(shí)間只能讓一門課程來使用，我們應(yīng)該對(duì)教室的資源進(jìn)行充分的利用。

最大座位數(shù)

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

三、 排課問題數(shù)學(xué)模型的建立

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

（一） 約束條件

當(dāng)約束條件不一樣時(shí)，可以排列組合時(shí)間和空間，從而來開展正常的教學(xué)工作，對(duì)于一張課表而言，它至少需要具備以下幾個(gè)硬約束條件：

a. 任課教師之間不能夠產(chǎn)生沖突；

b. 上課的教室不能產(chǎn)生沖突；

c. 專業(yè)之間不能夠相互沖突。

（二） 建立一般模型

參考文獻(xiàn)：

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

[2] 陳誼，楊怡，張國龍，王尚忠.基于優(yōu)先級(jí)自動(dòng)排課算法PCSA的設(shè)計(jì)與實(shí)現(xiàn)方案[J].北京工商大學(xué)學(xué)報(bào)（自然科學(xué)版），2002，（02）：96-98.

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

[4] 李琳，李秀娟，周德祥.計(jì)算機(jī)排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].鄭州工業(yè)高等專科學(xué)校學(xué)報(bào)，2004，（02）：81-83.

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

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