基于分布式勢博弈算法的排課方法研究

鄭加石+廉政

摘要：排課問題已被證明是NP完全問題，排課問題的難度隨課表規(guī)模的增大而增加。通過對排課問題建立圖形著色模型，采用分布式勢博弈算法求解。分布式勢博弈算法從局部最優(yōu)入手，最終形成全局最優(yōu)，適用于排課問題求解；同時勢博弈算法對排課問題中課表微調(diào)問題的響應(yīng)是高效的。實踐表明，相較于遺傳算法、模擬退火算法，分布式勢博弈算法對解決排課系統(tǒng)問題具有獨特優(yōu)勢。

關(guān)鍵詞：NP完全問題；勢博弈；分布式勢博弈算法；圖形著色

DOIDOI：10.11907/rjdk.171696

中圖分類號：TP319

文獻標(biāo)識碼：A 文章編號：1672-7800（2017）012-0152-03

Abstract：Scheduling Problem has been proved to be an NP-complete problem， the difficulty of scheduling problem increases with increasing size of the curriculum. Through establishing graphics rendering model and applying to scheduling problem， a distributed potential algorithm is introduced. Distributed potential game algorithm starts to solve the problem from local optimum， which eventually forms the global optimum for the Scheduling Problem. At the same time the potential game algorithm is efficient in response to the course arrangement where there is a micro change in timetable. Practice shows that compared to genetic algorithms， simulated annealing algorithm， distributed game algorithm is unique and effective to solve the Scheduling Problem.

Key Words：scheduling problem； distributed； potential game； graphics rendering

0 引言

早在20世紀(jì)70年代，排課問題就被證明是NP完全問題[1]。排課問題的復(fù)雜度隨問題規(guī)模的增大而劇烈增加。目前，對于NP完全問題求解主要是通過尋找一些降低計算復(fù)雜度的近似算法，沒有通用算法，因而諸如動態(tài)規(guī)劃[2]、遺傳算法[3]、模擬退火算法[4]等用于近似求解NP完全問題的算法都可以用于解決排課問題。這類算法的共同特征是集中式處理，如果已排好的課表出現(xiàn)了某些變動而需要重排，則算法對這種動態(tài)變化響應(yīng)并不及時。針對上述問題，建立排課問題的圖論模型，提出使用多代理系統(tǒng)的分布式博弈算法[5]對課表進行編排。使用多代理系統(tǒng)的分布式博弈學(xué)習(xí)算法對課表進行編排的優(yōu)點是：對于已經(jīng)編排好的課表，如果某一部分課表發(fā)生變動，只需進行局部調(diào)整便可生成新的課表，效率得到極大提高。

1 問題描述

影響排課的因素是多方面的，主要是由教師、教室、課程、班級和時間組成的五元組，排課目標(biāo)是實現(xiàn)這5個元素配置的最優(yōu)化，使得教學(xué)資源得到合理分配及利用。這是一個多約束的組合優(yōu)化問題，此類問題一般不存在唯一最優(yōu)解，找到其中一種近似最優(yōu)解即可。排課問題有兩種類型約束。

1.1 基本約束條件

排課的實質(zhì)是資源分配，解決排課問題的基本要求是基礎(chǔ)教學(xué)資源分配在時間、空間上無沖突。將教學(xué)資源的

分配原則稱為約束，對基礎(chǔ)教學(xué)資源分配的原則稱為基礎(chǔ)約束。通常情況下，這些基礎(chǔ)約束條件是固定的。例如：同一時間，同一教師不能講授一門以上的課程；同一時間，同一班級不能開展一門以上的課程；同一時間，同一教室不能開展一門以上的課程等。

1.2 擴展約束條件

排課問題要求基本約束條件必須得到滿足，但并非所有約束條件都需要得到滿足，稱此類約束為擴展約束。擴展約束一般用于保證課程質(zhì)量，使得課程安排合理、科學(xué)。屬于擴展約束的條件如下：某課程一周內(nèi)有幾次課應(yīng)不在一天進行；英語、語文等記憶性課程應(yīng)放在上午；同一教師的同一課程應(yīng)盡量安排在同一地點等。

2 模型設(shè)計

2.1 基本假設(shè)

按照上述步驟，對于一個具有實際意義的真實課表安排問題，可以將課表排布問題轉(zhuǎn)化為圖的頂點著色問題，其中每周擁有的課時總數(shù)P作為顏色數(shù)，要求與同一個邊相鄰的頂點具有不同的顏色，對圖的頂點進行著色，最后必然會得到一個結(jié)果，將不同班級課程按照顏色由小到大的順序進行排序，便可以得到課程的最終排布。

2.3 排課模型完善

上述模型中，有許多實際約束條件沒有考慮。對于一個實際排課問題，并非每一門課程都擁有同樣的地位，某些課程比如英語，根據(jù)遺忘規(guī)律，需要將其放在上午，最理想的情況是放在上午第一節(jié)課，同時如果一門課在一天內(nèi)進行兩次，就可能導(dǎo)致學(xué)生一時接受不了大量知識，使得學(xué)習(xí)效率下降。解決第1個問題的方式是增加課程對偏好時間段的權(quán)重。還是以英語課程為例，這里設(shè)計一個權(quán)值W（W>1），在計算時將偏好時段乘以W，這就無形中增加了選取最適時段的概率。對于第2個問題，同課不適宜放在同一天進行，也同樣可以通過設(shè)計權(quán)值W的方法解決，只不過權(quán)值小于1（w<1），這就減少了該值被選取的概率。endprint

高校課程表編排有別于中學(xué)課表，主要體現(xiàn)在高校教學(xué)活動中，為了節(jié)約資源，往往教室并不固定，同一門課程在一周內(nèi)不同時刻上課，可能不在同一個教室。因此，在課程表安排好以后，還要為課程安排教室。但需要指出的是，在各班級課程表安排好以后，以各班級同一時間段課程為輸入，以該時段可支配教室為輸出，x為同一時段各班級的課程，y為該時段可支配教室，可以構(gòu)成函數(shù)：

4 實驗數(shù)據(jù)及結(jié)果分析

通過如下兩點衡量排課算法優(yōu)劣：①算法收斂速度，即算法能否快速解決課表排布問題。文中算法收斂速度和圖的總沖突數(shù)成正比，沖突數(shù)為0時，算法收斂，算法收斂時間與循環(huán)次數(shù)成正比；②隨著問題規(guī)模的增加，算法性能表現(xiàn)。對于NP完全問題，隨著問題復(fù)雜度的增加，問題求解難度也相應(yīng)增加，巧妙的算法在收斂性上要優(yōu)于收斂性差的算法。測試結(jié)果（見表1）顯示，隨著問題規(guī)模的增加，沖突數(shù)增加，算法運算復(fù)雜度也相應(yīng)提高。

5 結(jié)語

排課問題作為NP完全問題，其問題難度隨課表規(guī)模的增大而提高。分布式勢博弈算法從局部最優(yōu)入手，最終形成全局最優(yōu)，適用于排課問題求解；并且，勢博弈算法對排課問題中課表微調(diào)問題的響應(yīng)是高效的。本文通過對排課問題建立圖形著色模型，采用分布式勢博弈算法進行求解，對解決排課問題優(yōu)勢明顯。

參考文獻：

[1] EVEN S，ITAI A，SHAMIR A.On the complexity of time table andmulti-commodity flow problems[J].SIAM Journal on Computing，1976，5（4）：691-703.

[2] 程學(xué)先，祝蘇薇.一種基于動態(tài)規(guī)劃的課程調(diào)度算法的研究與實現(xiàn)[J].武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，2006，30（3）：485-488.

[3] 車明，秦存秀，劉凱.基于改進回溯算法的計算機排課系統(tǒng)[J].沈陽工業(yè)大學(xué)學(xué)報，2006，28（6）：667-670.

[4] 劉繼清，陳傳波.模擬退火算法在排課中的應(yīng)用[J].武漢船舶技術(shù)學(xué)院學(xué)報，2003（3）：22-24.

[5] 楊光，蔚承建，王開，等.圖形著色問題的分布式勢博弈算法[J].計算機工程，2012（23）：181-184.

[6] 胡順仁，鄧毅，王錚.基于高校排課系統(tǒng)中的圖論問題研究[J].計算機工程與應(yīng)用，2002（4）：221-256.

（責(zé)任編輯：孫 娟）endprint