[發明專利]排課方法及系統

有效

• 申請號: 201810796422.2
• 申請日: 2018-07-19
• 公開（公告）號: CN109242137B
• 公開（公告）日: 2020-11-27
• 發明（設計）人: 魏勇
• 申請（專利權）人: 深圳信息職業技術學院
• 主分類號: G06F17/10
• 分類號: G06F17/10
• 代理公司: 深圳中一專利商標事務所 44237
• 代理人: 官建紅

本發明適用于教學管理技術領域，提供了一種排課方法及系統，包括：獲取課程數、課程對象數和周課表對象集，根據所述課程數和所述課程對象數對所述周課表對象集進行分組，建立分組組合幾何模型，根據蟻群算法在所述分組組合幾何模型中建立多條路徑，所述路徑攜帶信息素，根據所述信息素，選擇多條路徑中的一條作為排課結果。本發明基于分組組合幾何模型，通過反復模擬蟻群路線，根據蟻群釋放的信息素得到排課課表，解決了現有的排課方法時間復雜度高的排課問題，避免了采用遺傳算法時因“基因突變”導致排課表不收斂的問題。

技術領域

本發明屬于教學管理技術領域，尤其涉及一種排課方法及系統。

背景技術

排課表又稱為時間表問題TTP(Time Table Problem)，解決TTP問題的一種方法是遺傳算法GA(Genetic Algorithm)。GA是一種抽象于生物進化過程的、基于自然選擇和生物遺傳機制的優化技術，按照“優勝劣汰，適者生存”的原則，通過快速隨機搜索力求找到最優解或滿意解。但GA容易產生早熟收斂的問題，導致得到的解為局部最優解而非全局最優解，存在因“基因突變”導致排課表不收斂的問題，同時GA算法實現復雜，當數據量大時，時間復雜度高。

利用分組組合生成算法進行全枚舉是解決TTP問題的另一種方法。由理論可知，分組組合可以生成TTP問題的所有解，但當數據量較大時，枚舉所有解往往因計算量巨大而很難在實踐中得到應用。例如將各有6節、6節、8節、6節和4節的5門課，排到一張5×6的課表中，利用分組組合生成算法，共有734,396,875,494,282,000種課表，通過全枚舉得到所有的課表，再找到一個適合的課表顯然難以實現。

現有的排課方法在數據量較大時耗時大大增加，難以在實踐中得到應用，亟需一種時間復雜度低、可快速得到全局最優解的排課方法。

發明內容

有鑒于此，本發明實施例提供了一種排課方法及系統，以解決現有的排課方法時間復雜度高，難以快速得到全局最優解的排課問題，避免采用遺傳算法時因“基因突變”導致排課表不收斂的問題。

本發明實施例的第一方面提供了一種排課方法，包括：

獲取課程數、課程對象數和周課表對象集；

根據所述課程數和所述課程對象數對所述周課表對象集進行分組，建立分組組合幾何模型；

根據蟻群算法在所述分組組合幾何模型中建立多條路徑，所述路徑攜帶信息素；

根據所述信息素，選擇多條路徑中的一條作為排課結果。

在一種可能的實現方式中，所述根據所述課程數和所述課程對象數對所述周課表對象集進行分組，包括：

根據課程數k和課程對象數n_i，將周課表對象集n分為k組，其中，所述課程對象數n_i表示第i個課程的數量，i、k和n均為正整數。

在一種可能的實現方式中，所述建立分組組合幾何模型，包括：

在平面直角坐標系中建立分組組合的起點和終點，確定由所述分組組合的起點沿坐標軸正方向前進到所述分組組合的終點的路徑為所述分組組合幾何模型。

在一種可能的實現方式中，所述在平面直角坐標系中建立分組組合的起點和終點，包括：

在平面直角坐標系中建立第1個分組的起點為(0，0)，第1個分組的終點為(n₁，n-n₁)；