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