【文章內(nèi)容簡介】 ，進入的界 面也 排課算法 目前常用算法 目前，解決排課問題常用的方法有：著色算法 [11]，通過研究時間資源庫的形成策略，分析基于時間資源的排課算法 [12]?；诜謱臃种?、貪心算法的排課系統(tǒng)的設(shè)計與實現(xiàn) [13]，基于圖論方法的自動優(yōu)化排課模型研究 [14]，基于資源受限的非線性約束多目標排課模型及算法 [15]，整數(shù)規(guī)劃解決排課問題 [16]，基于遺傳禁忌算智能排課系統(tǒng)的設(shè)計與實現(xiàn) 10 法結(jié)合解決排課問題 [17]等。這些方法雖然提高了搜索效率，但由于高校普遍存在課程量大，教室、教師資源緊張，排課約束條件多且條件經(jīng)常變化等問題，排課算法的應(yīng) 用仍然受到很大限制 [19]。 排課問題描述 排課問題的約束條件 排課即要滿足一定的硬約束條件來協(xié)調(diào)處理教師、教室、學生、時間之間的多維沖突，同時還要盡可能滿足一些軟約束條件，從而使排出的課表 更 加合理， 滿足人性化需求。硬約束條件要求系統(tǒng)必須滿足的條件，而軟約束條件是在滿足硬約束條件以后要考慮的約束條件，軟約束條件不要求系統(tǒng)必須滿足，但滿足這些條件能得到較優(yōu)解。常用的硬約束條件有： (1) 所 有的課程都必須被安排； (2) 除合班課外，同一時間，一個教室只能被一個班級占用； (3) 除選修課外，同一時間，一個班級只能安排一門課程； (4) 同一時間，一個教師只能在一個教室上課； (5) 同一個教師所上的不同課程不能發(fā)生在同一時間； (6) 兩門課程不能在同一個時間安排在同一個教室； (7) 教室的類型必須與課程要求一致； (8) 教室的最大容納人數(shù)必須大于等于在該教室上課的學生人數(shù)等； (9) 不同課程時間段不同，如體育課只能在白天且不安排在第一節(jié)，選修課不能安排在早上等。 常用的軟約束條件有： (1) 同一門課程的上課時間盡量間隔均勻。例如某課程周學時為 4 學時，以 2 學時為一 個教學單位，需安排兩次。兩次的安排時間盡量間隔一天或者一天以上； (2) 每個學生的課程均勻的分布在工作日中； (3) 學生的上課時間要盡量選擇在較好的上課時間段； (4) 對班級、 教室、教師的單雙周上課時間點盡量匹配，以節(jié)約教學資源； 智能排課系統(tǒng)的設(shè)計與實現(xiàn) 11 排課問題的數(shù)學表示 如果用 C 表示課程、 S 表示班級、 N 表示時間、 R 表示教室， T 表示教師， 排課問題的目標就是找出滿足約束條件的 (C， S， N， R， T)組合。并且，這五種元素之間存在一定的對應(yīng)關(guān)系： ① C 與 S 之間的對應(yīng)關(guān)系，即每個班級有其特定要上的課程 ； ② C 與 T 之間的對應(yīng)關(guān)系，即每門課程有一定的任課教師； ③ (N， R)與 (S， C， T)之間的對應(yīng)關(guān)系，即每個教室在某一時間段只能有一個班級上一門課程。排課問題的實質(zhì)就是對于給定的一組 (S， C， T)要分配其一個滿足上課條件的時空片 (N， R)。即找到 (N， R)與 (S， C， T)之間的一一對應(yīng)關(guān)系。 排課問題的優(yōu)先級問題 排課中有很多等待分配時空片的 (S， C， T)，如何安排它們的分配次序，不僅關(guān)系到算法的性能、安排的合理性，更關(guān)系到最終能否求出可行解。因此，分配次序的好壞也是每個算法中要仔細處理的問題 。在本文的算法中，是對每一組 (S， C， T)設(shè)定優(yōu)先級，然后按照優(yōu)先級的高低次序分配時空片。設(shè)定 (S， C， T) 優(yōu)先級要考慮的因素有： ① (S， C， T)中課程 C 的類別，對于不同類別的課程，給它們設(shè)定相應(yīng)的優(yōu)先值，本算法中針對課程類別的優(yōu)先級設(shè)定如下：專業(yè)基礎(chǔ)課、公共基礎(chǔ)課、專業(yè)限選課 、 專業(yè)選修課 、公選課 優(yōu)先級別依次降低， 其中專業(yè)基礎(chǔ)課級別最高，公選 課級別最低； ② (S， C， T)中課程 C 在一周內(nèi)要上的次數(shù)。即一門課程 周學時越多， 優(yōu)先級越高； ③ (S， C， T)中班級 S 所需要上的課程總數(shù)的大小。即學生每周要上的 課 程總數(shù)越多， 優(yōu)先級越高； ④ (S， C， T)中學生 S 中的人 數(shù)的大小。 最后根據(jù)各個因素的重要性不同，給每個因素設(shè)置一定的權(quán)重系數(shù) p[0]、p[1]、 p[2]、 p[3]，最后求四種因素的帶權(quán)累加和 ， 即得到一個 (S， C， T)的優(yōu)先級， 每次按照 (S， C， T)的優(yōu)先級的降序次序來分配時空片。 智能排課系統(tǒng)的設(shè)計與實現(xiàn) 12 算法思想 該算法在選擇每一組教學任務(wù) (S， C， T)時是按貪心策略來選擇， 即按 (S， C， T)優(yōu)先級的降序次序選擇優(yōu)先級最高的教學任務(wù)。 接下來在進行時空片分配過程 中采用分治的策略，在分配過程中分為三個層次： 1）即先分配要上課的星期數(shù)（星期數(shù)是指星期一到星期五的任意一天）， 2）再分配其該天的上課時間段（在本文中某天的上課時間段分為 5 個時間段，上午 2 節(jié)為第 1 個時間段， 上午 4 節(jié)為第 2 個時間段，下午 2 節(jié)為第3 個時間段，下午 4 節(jié)為第 4 個時間段，晚上 2 節(jié)或者 3 節(jié)為第 5個時間段）， 3）最后分配上課的教室。同時在每一階段的分配過程中，都要對資源總數(shù)和使用狀況作統(tǒng)計和記錄，從而防止不計后果的資源濫用。算法主要步驟如下： Step1：初始化。 ：初始化，將所有教室按類型劃分， 并在每一類型中按教室容量統(tǒng)計可用教室資源的數(shù)目。例如，可將教室劃分為：普通教室、多媒體教室、語音室、物理實驗室、機房等。 然后按教室可容納人數(shù)分為 060 人、 60120 人、 120140人這 4 個不同等級。然后統(tǒng)計記錄每一類型不同容量范圍的可用教室資源數(shù)目。 ：預排序，將待排的所有課程先按周學時降序排列，然后再將待排的所有課程先按所需教室類型升序排列，再按所需教室容量降序分配，即先為上課人數(shù)多的課程分配教室，防止較小的班級占用大教室，最后再將所有需要使用同一類型和容量教室的課程按優(yōu)先級降 序排序。 Step2：分配上課的星期數(shù)。按照排序后的次序，再參照剩余的可用資源記錄來分配每組 (S， C， T)在一周內(nèi)要上課的星期數(shù)。同時參考總課表，使得班級和教師的上課時間在一周內(nèi)盡可能均勻分布。 Step3:分配某天內(nèi)上課的時間段。 對每種類型和大小的教室資源按其在一周內(nèi)的某一天的 5 個時段的分配情況作統(tǒng)計。 在分配時間段的時候， 從第一個時段到第 5 個時段依次查看是否還有剩余資源，若有，則為其分配相應(yīng)的是時間段，否則看能否將某個已被占用的時間段調(diào)整后再為其分配。分配的過程中要 參照總課表，防止時間沖突。 智能排課系統(tǒng)的設(shè)計與實現(xiàn) 13 若有不能分配的， 查找與其相關(guān)的已經(jīng)分配了時間段的課程，并看看能否重新為它分配時間段，從而將原來的時間段讓給不能成功找到時間段的那個課程使用。 Step4:分配上課的教室：根據(jù)每一課程要求的上課時間和教室類型及大小為其分配教室。對于每個已經(jīng)分配了星期數(shù)和時間段的課程，一般來說，都是找得到可用教室的，因為在前兩個分配階段中，是嚴格按照資源剩余狀況來進行分配的。同時在分配上課所用的教室時，也考慮到單雙周情況，以便充分利用教室資源。 算法分析 基于分治貪 心相結(jié)合的排課算法主要分為 3 個階段：即分配上課星期數(shù)、分 配上課時間段、分配上課的教室。這里對算法的時間復雜度進行分析。 第一階段：分配上課星期數(shù)，為每一門課程分配上課星期數(shù)的運算次數(shù)主要與課程數(shù)目有關(guān)； 第二階段：分配上課的時段，為一次課分配上課時段所進行判斷的次數(shù)最壞 為 5 次，分配上課時段的運算次數(shù)主要和每周上的總課程次數(shù)有關(guān)。 第三階段： 根據(jù)上課星期數(shù)和上課時段分配教室 ； 因此該算法主要和問題的規(guī)模有關(guān)， 即與要排課的課目數(shù)、課程的 周 學時數(shù)及教室數(shù)目有關(guān)。和基于貪心策略 、 基于隨機分配時間片的排課 算法進行比較，該算法的運行時間介于二者之間，效率略低于基于貪心策略的排課算法， 比基于隨機分配時間片的排課算法效率要高。但該算法在成功排課的數(shù)量上，性能比基于貪心策略的算法會略好。 因為分治與貪心相結(jié)合的算法中是當有滿足條件的資源時，便一定會為其分配。而貪心策略中，可能雖然存在可用資源時仍會遺漏可行解。 智能排課系統(tǒng)的設(shè)計與實現(xiàn) 14 5 數(shù)據(jù)庫設(shè)計 系統(tǒng)數(shù)據(jù)表 根據(jù)系統(tǒng)需求分析 ，以及考慮到數(shù)據(jù)表之間的關(guān)聯(lián)性 ， 系統(tǒng) 需要建立 7 個表，2 個視圖， 其用途說明如下表 所示。 表 51 系統(tǒng) 數(shù)據(jù)表 數(shù)據(jù)表 名稱 數(shù)據(jù)表描述 Class 保存 班級基本信息 Hb 保存組成各合班的班級號 Teacher 記錄教師信息 Classroom 記錄教室信息 Course 保存課程信息 Lesson_plans 保存教學計劃 R_L 存儲總課表 表 52 系統(tǒng)視圖 數(shù)據(jù)表 名稱 數(shù)據(jù)表描述 Lp_view 保存需要排課的信息，利于排課 RL_view 保存教室安排信息，利于查詢班級時間及教室時間 UML 建模圖 下圖主要是對應(yīng)實體關(guān)系圖，經(jīng)過分析了各實體及其屬性，用 Microsoft Office Visio 2021 畫出下圖。 智能排課系統(tǒng)的設(shè)計與實現(xiàn) 15 教 師P K 教 師 i d 教 師 姓 名 職 稱 年 齡 已 上 過 課 程 所 屬 部 門教 室P K 教 室 I D 容 量 類 別班 級P K 班 級 I D 專 業(yè) 年 級 人 數(shù)課 程P K 課 程 I D 課 程 名課 程 計 劃P K 課 程 計 劃 i d 課 程 i d 班 級 i d 教 師 i d 周 節(jié) 次 總 課 時 課 程 性 質(zhì) 課 程 計 劃 列 1 排 課 權(quán) 重R _ TP K k c _ i d 星 期 節(jié) 次 教 室 i d 是 否 可 用 課 程 計 劃 i d 單 雙 周合 班P K 合 班 號P K 分 班 號圖 51 UML 建模圖 數(shù)據(jù)字典 下列表 到 表 給出 7 個數(shù)據(jù)表： 班級信息 表、 合班 表、 教室信息 表、教師信息 表、 課程信息 表、 教學計劃 表、 總課 表的具體描述，包括數(shù)據(jù)描述、數(shù)據(jù)名稱、數(shù)據(jù)類型等。 表 53 Course班級信息 表 字段名稱 說明 數(shù)據(jù)類型 長度 主 /外鍵 約束 備注 Class_id 班級編 號 Char 10 主鍵 Class_name 班級 名 Char 20 非空 智能排課系統(tǒng)的設(shè)計與實現(xiàn) 16 Department 專業(yè) Char 20 grade 年級 Char 10 number 人數(shù) Int 非空 Hb 是否合班 int 非空 默認 0（否） 表 54 hb合班表 字段名稱 說明 數(shù)據(jù)類型 長度 主 /外鍵 約束 備注 Hb_id 合班號 Char 10 主鍵 Class_id 小班號 Char 10 外鍵 非空 表 55 classroom教室信息 表 字段名稱 說明 數(shù)據(jù)類型 長度 主 /外鍵 約束 備注 Cr_id 教室 編號 Char 10 主鍵 Capacity 教室容量 Int Category 教室類別 Char 10 非空 表 56 Teacher教師信息表 字段名稱 說明 數(shù)據(jù)類型 長度 主 /外鍵 約束 備注 T_id 教師 編號 Char 10 主鍵 T_name 教室姓名 Char 10 非空 profession 職稱 Char 10 age 年齡 Int Department 所屬學院 Char 10 表 57 Course課程信息表 字段名稱 說明 數(shù)據(jù)類型 長度 主 /外鍵 約束 備注 C_id 課程 號 Char 10 主鍵 C_name 課程 名 Char 20 非空 智能排課系統(tǒng)的設(shè)計與實現(xiàn) 17 表 58 lesson_plans教學計劃表 字段名稱 說明 數(shù)據(jù)類型 長度 主 /外鍵 約束 備注 Lesson_id 課程計劃號 Char 10 主鍵 C_id 課程號 Char 10 外鍵 非空 參照 course 表中的 c_id Class_id 班級號 Char 10 外鍵 非空 參照 class 表中 class_id T_id 教師編號 Char 10 外鍵 非空 參照 Teacher 表中 t_id C_nature 課程性質(zhì) Char 10 W_jieci 周節(jié)次 Int 非空 Z_jieci 總節(jié)次 Int Paike 是否排課 Int 默認為 0（未排課） Category 教室性質(zhì) Char 10 Qz 權(quán)重 Int 自動計算 表 59 R_L總課表 字段名稱 說明 數(shù)據(jù)類型 長度 主 / 外鍵 約束 備注 Kc_id 排課標