一種面向教學(xué)的排課沖突檢測算法

朱維軍，王迤冉

(1.鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001; 2.周口師范學(xué)院 計(jì)算機(jī)與科學(xué)技術(shù)學(xué)院，河南 周口 466001)

?

一種面向教學(xué)的排課沖突檢測算法

朱維軍1，王迤冉2

(1.鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001; 2.周口師范學(xué)院 計(jì)算機(jī)與科學(xué)技術(shù)學(xué)院，河南 周口 466001)

摘要：排課算法可在大規(guī)?？臻g上對(duì)排課元素實(shí)施自動(dòng)編排.然而，目前未見報(bào)道有關(guān)針對(duì)已排好的課表實(shí)施正確性檢測的通用全自動(dòng)方法.為此，給出課表所需滿足約束條件的形式化描述；在此基礎(chǔ)上，分別給出3個(gè)子算法以檢測3種約束條件；順序調(diào)用這些子算法，即可得到一種面向教學(xué)實(shí)踐的排課沖突檢測算法.檢測實(shí)驗(yàn)證實(shí)了新方法的有效性.

關(guān)鍵詞：排課系統(tǒng)；算法；沖突檢測；課程表

0引言

利用計(jì)算機(jī)進(jìn)行自動(dòng)排課可以大幅提高排課效率，并增強(qiáng)課表的合理性.排課算法為排課系統(tǒng)提供核心引擎，因而對(duì)算法的研究是提升排課效率及確保正確性的關(guān)鍵.目前為止已發(fā)展成熟并被廣泛使用的排課算法有：遺傳算法[1]、貪心算法[2-3]、回溯算法[4]等.這些算法各有其優(yōu)勢與不足，基于這些算法的系統(tǒng)也在實(shí)際的高校排課中發(fā)揮了重要作用.

然而，所謂通用的高校排課系統(tǒng)并不能滿足不同教學(xué)單位的個(gè)性化需求，因此，用戶單位的二次開發(fā)在所難免.不幸的是，二次開發(fā)后的系統(tǒng)并不能自動(dòng)確保課表的正確性，也就是說，課表需要滿足的硬約束條件不再必然被滿足.如果此問題不能被有效解決，在實(shí)踐中甚至有可能發(fā)生大面積教學(xué)事故.為此，用戶單位需要一套與排課系統(tǒng)無關(guān)的獨(dú)立檢測系統(tǒng)，來檢測課表中是否存在沖突.

一系列工作針對(duì)此問題開展研究.文獻(xiàn)[5]指出了上述問題的具體幾個(gè)方面，然而，未給出檢測算法.文獻(xiàn)[6]給出了帶有沖突檢測的排課系統(tǒng)，其沖突檢測算法只針對(duì)軟約束條件，并不對(duì)課表是否滿足硬約束條件進(jìn)行檢測.文獻(xiàn)[7]使用占位數(shù)組設(shè)計(jì)排課算法，沖突檢測為設(shè)計(jì)課表提供依據(jù)，卻并沒有針對(duì)通用排課算法給出通用的沖突檢測方法.文獻(xiàn)[8]給出了對(duì)課表進(jìn)行沖突檢測的算法，這個(gè)算法發(fā)揮功能與排課算法無關(guān)，然而，卻是在一定的限制下，在通用環(huán)境下算法并不可用.

為此，本文提出一種沖突檢測算法，可以對(duì)任何排課算法排出的課表進(jìn)行沖突檢測.

1課表必須滿足的硬條件及其形式化描述

1.1自然語言描述[8]

一份正確有效的課表，必須避免排課元素的沖突，其中，排課元素包括：時(shí)間、教室、教師、班級(jí)、課程.課表必須同時(shí)滿足如下3個(gè)硬條件：

(1)教室不沖突：同一時(shí)間，不能在同一教室安排兩門不同課程；

(2)教師不沖突：同一時(shí)間，不能讓同一教師為兩個(gè)不同班級(jí)上課；

(3)班級(jí)不沖突：同一時(shí)間，不能為同一班級(jí)安排兩門不同課程.

1.2形式語言描述

定義1課表是一個(gè)5維向量A(T,R,P,C,L)，其中，t∈T是離散時(shí)間片，r∈R是教室，p∈P是教師，c∈C是班級(jí)，l∈L是課程，如果在時(shí)間片t，教師p在教室r給班級(jí)c上課程l，則A(t,r,p,c,l)=1，否則A(t,r,p,c,l)=0.

定義2“教室不沖突”條件可被定義為

?t?r?p1?c1?l1?p2?c2?l2(((A(t,r,p1,c1,l1)=1)∧(A(t,r,p2,c2,l2)=1))→(l1=l2)).

定義3“教師不沖突”條件可被定義為

?t?p?r1?c1?l1?r2?c2?l2(((A(t,r1,p,c1,l1)=1)∧(A(t,r2,p,c2,l2)=1))→(c1=c2)).

定義4“班級(jí)不沖突”條件可被定義為

?t?c?p1?r1?l1?p2?r2?l2(((A(t,r1,p1,c,l1)=1)∧(A(t,r2,p2,c,l2)=1))→(l1=l2)).

2沖突檢測算法

有了第1節(jié)給出的形式化描述，即可給出對(duì)3個(gè)條件的檢測方法，分別如2.1節(jié)、2.2節(jié)、2.3節(jié)所示.依次調(diào)用這些方法，即可得到課表沖突檢測算法，如2.4節(jié)所示.

2.1教室沖突檢測子算法

Procedure ROOM

Input: 排好的課表即5維向量A(T,R,P,C,L)

Output: 有關(guān)是否存在教室沖突的檢測結(jié)果

Begin

{ifA(t,r,p,c,l)=1, thenco(l):=true}

}

}

if ?i?j(i≠j)∧co(i)∧co(j),then//若被安排兩門課

{return((t,r,i,j)&“教室有沖突”);flag:=1} //報(bào)告沖突位置

}

}

End

2.2教師沖突檢測子算法

Procedure PROFESSOR

Input: 排好的課表即5維向量A(T,R,P,C,L)

Output: 有關(guān)是否存在教師沖突的檢測結(jié)果

Begin

{ifA(t,r,p,c,l)=1, thenco(c):=true}

}

}

if ?i?j(i≠j)∧co(i)∧co(j), then//若被安排兩班級(jí)

{return ((t,p,i,j)&“教師有沖突”);flag:=1} //報(bào)告沖突位置

}

}

End

2.3班級(jí)沖突檢測子算法

Procedure CLASS

Input: 排好的課表即5維向量A(T,R,P,C,L)

Output: 有關(guān)是否存在班級(jí)沖突的檢測結(jié)果

Begin

{ifA(t,r,p,c,l)=1, thenco(l):=true}

}

}

if ?i?j(i≠j)∧co(i)∧co(j),then//若被安排兩門課

{return((t,c,i,j)&”班級(jí)有沖突”);flag:=1}//報(bào)告沖突位置

}

}

End

2.4沖突檢測算法

Procedure DETECTION

Input: 排好的課表即5維向量A(T,R,P,C,L)

Output: 有關(guān)課表是否存在沖突的檢測結(jié)果

Begin

flag:=0;//當(dāng)存在沖突時(shí)，flag被置為1

ROOM;

PROFESSOR;

CLASS;

ifflag=0 then return (“課表無沖突”), else return(“課表有沖突”)

End

3算法復(fù)雜度分析

4結(jié)論

本文的主要成果是算法DETECTION，它是一種可以全自動(dòng)地檢測給定的課表是否滿足教室無沖突、教師無沖突、班級(jí)無沖突等約束條件的通用方法.筆者使用來自多家教學(xué)單位提供的模擬課表共計(jì)50份作為樣本，一部分課表由人工編排，另一部分由半人工編排，其余的則分別由多種算法全自動(dòng)編排，不同的課表及采用的排課方法符合不同教學(xué)單位的不同個(gè)性化需求.針對(duì)這些樣本，實(shí)施了一系列實(shí)驗(yàn)性檢測.新算法在兩小時(shí)內(nèi)發(fā)現(xiàn)了8處編排沖突；作為對(duì)照，5名實(shí)驗(yàn)人員用了一周時(shí)間僅僅發(fā)現(xiàn)了2處沖突.結(jié)果表明，新算法可高效地發(fā)現(xiàn)各類課表中的沖突現(xiàn)象.

參考文獻(xiàn)

[1]許秀林，胡克瑾.基于約束滿足和遺傳算法的排課算法[J].計(jì)算機(jī)工程，2010，36(14)：281-284.

[2]王偉，余利華.基于貪心法和禁忌搜索的實(shí)用高校排課系統(tǒng)[J].計(jì)算機(jī)應(yīng)用，2007，27(11)：2 873-2 876.

[3]梁立，陳玉華，徐敏.基于貪心法的排課算法[J].云南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，25(3)：9-12.

[4]吳志斌，陳淑珍.回溯算法與計(jì)算機(jī)智能排課[J].計(jì)算機(jī)工程，1999，25(3)：79-80.

[5]黃玉波.高校排課流程及沖突檢測分析[J].軟件導(dǎo)刊，2010，9(2)：16-17.

[6]高武奇，康鳳舉，鐘聯(lián)炯.基于沖突檢測算法的二級(jí)排課系統(tǒng)[J].西安工業(yè)大學(xué)學(xué)報(bào)，2008，28(5)：506-510.

[7]張海濤，李俊杰，嚴(yán)偉榆，等.基于學(xué)分制的排課沖突檢測優(yōu)化算法研究[J].電子設(shè)計(jì)工程，2013，21(15)：8-10.

[8]肖剛.排課沖突檢測的設(shè)計(jì)及實(shí)現(xiàn)[J].軟件導(dǎo)刊，2011，10(5)：5-7.

An Instruction-oriented Algorithm for Detecting

Collisions in Class Schedule

ZHU Wei-jun1， WANG Yi-ran2

(1.SchoolofInformationEngineering,ZhengzhouUniversity,Zhengzhou450001,China;

2.SchoolofComputerScienceandTechnology,ZhoukouNormalUniversity,Zhoukou460001,China)

Abstract:The existing course arrangement algorithms can deal with time, rooms, teachers, classes and courses in large scale. Up to now, no method is given to check whether a class schedule is effective automatically, or not. To address this problem, we formulize the constraint conditions. On the basis of it, three sub-algorithms are formulated to check these conditions. By calling the sub-algorithms one by one, we obtain an algorithm for detecting collisions in a class schedule. The experimental results demonstrate the new method is effective.

Key words:course arrangement systems; algorithm; collision detection; class schedule

中圖分類號(hào)：TP311.1；G473.4

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1007-0834(2015)02-0030-04

doi：10.3969/j.issn.1007-0834.2015.02.008

作者簡介：朱維軍(1976—)，男，河南鄭州人，鄭州大學(xué)信息工程學(xué)院副教授，博士、博士后，主要研究方向：教育技術(shù)、信息安全.

基金項(xiàng)目：河南省高等學(xué)校青年骨干教師資助計(jì)劃項(xiàng)目(2014GGJS-001)

收稿日期：2015-02-28