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

鄭加石+廉政

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

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

DOIDOI：10.11907/rjdk.171696

中圖分類號：TP319

文獻標識碼：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世紀70年代，排課問題就被證明是NP完全問題[1]。排課問題的復雜度隨問題規模的增大而劇烈增加。目前，對于NP完全問題求解主要是通過尋找一些降低計算復雜度的近似算法，沒有通用算法，因而諸如動態規劃[2]、遺傳算法[3]、模擬退火算法[4]等用于近似求解NP完全問題的算法都可以用于解決排課問題。這類算法的共同特征是集中式處理，如果已排好的課表出現了某些變動而需要重排，則算法對這種動態變化響應并不及時。針對上述問題，建立排課問題的圖論模型，提出使用多代理系統的分布式博弈算法[5]對課表進行編排。使用多代理系統的分布式博弈學習算法對課表進行編排的優點是：對于已經編排好的課表，如果某一部分課表發生變動，只需進行局部調整便可生成新的課表，效率得到極大提高。

1 問題描述

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

1.1 基本約束條件

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

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

1.2 擴展約束條件

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

2 模型設計

2.1 基本假設

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

2.3 排課模型完善

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

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

4 實驗數據及結果分析

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

5 結語

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

參考文獻：

[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] 程學先，祝蘇薇.一種基于動態規劃的課程調度算法的研究與實現[J].武漢理工大學學報：交通科學與工程版，2006，30（3）：485-488.

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

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

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

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

（責任編輯：孫 娟）endprint