大學自動排課算法設計與實現

電子通信論文編號:TX042        論文字數:17736,頁數:37

目    錄
1 緒論   1
1.1 課題背景及其目的   1
1.2 國內外研究狀況   2
1.3 課題研究方法   3
1.4 論文構成及研究內容   3
2 排課模型的建立與分析   5
2.1 教務流程簡介   5
2.2 課表的制定原則   6
2.3 排課系統的基本需求分析  8
2.4 排課問題模型  9
2.4.1 符號約定  9
2.4.2 建立組合優化模型   10
2.4.2.1約束條件定義  10
2.4.2.2 目標函數定義   11
2.4.2.3 模型描述   11
3 禁忌搜索算法理論研究   12
3.1 禁忌搜索簡介  12
3.2 禁忌搜索原理  12
3.3 禁忌搜索示例  12
3.4禁忌搜索算法流程  14
4 基于禁忌搜索的排課問題求解   16
4.1 算法總體思想   16
4.2 符號定義   16
4.2.1 基本信息定義   16
4.2.2 基本函數定義  17
4.2.3 組合信息定義  17
4.3 基于網絡流的預處理算法   17
4.4 基于禁忌搜索的時間分配算法  20
4.4.1定義域   20
4.4.2目標函數   20
4.4.3禁忌搜索的主要參數描述  21
4.4.4 禁忌搜索算法步驟  22
4.5 后續操作   24
4.6 算法運行實例分析   24
4.6.1 輸入數據   24
4.6.2 預處理步驟分析   25
4.6.3 禁忌搜索過程分析   26
4.6.4 輸出周課表   27
5 結論   29
5.1 對本文工作的總結   29
5.2 對進一步研究的展望   30
致謝   32
參考資料   33

摘要

    排課問題是涉及班級、教師、教室等因素的決策優化問題，也是組合規劃中的典型問題。在自動排課系統中，處理排課問題所用的算法處于核心地位，由于排課問題本身的復雜性，尋找這樣一個有效算法還是有相當的難度。本文課題來源于自動排課問題的求解算法研究。
    本文借鑒以往的成功經驗并結合本學校的實際情況，提出了一種基于禁忌搜索算法的排課問題解決方案。首先，使用網絡最大流算法預處理，把授課任務分成若干組，同組的任務可以同時進行而不發生沖突，而且保證教室需求量不大于供應量。然后，使用禁忌搜索尋求任務組與時間的最優組合方式。最后，給任務分配教室輸出課表。本文先給出了算法的總體框架，然后對如何建立網絡流模型以及禁忌搜索的各個要素進行了詳細的說明，最后使用真實數據進行了仿真測試。
    這種方案結合了經典的網絡流算法與禁忌搜索算法，使兩種算法優勢互補，帶來了較好的處理問題能力。經實際數據的仿真驗證，該算法具有一定可行性和適用性。

關鍵詞：排課問題，組合優化，網絡流，禁忌搜索

Abstract
  Course-timetabling problem, an optimization decision-making problem involving factors such as classes, teachers and classrooms etc, is a typical problem of combinatorial planning. In an automated-course-timetabling system, the algorithm of course timetabling enjoys the core status, but it is rather difficult for us to find an effective processing algorithm due to the complexity of the course-timetabling problem itself. The subject studied in this paper originates from the research on the algorithm of automatic course-timetabling problem.
  This paper introduced a method to solve the course-timetabling problem based on taboo search. First, uses the network max-flow algorithm in preprocessing to divide the teaching tasks into several groups, in which the tasks can be carried on simultaneously without collisions and the number of the required classrooms not lager than the number of the supplied ones. Second, seeks a best combination between task groups and time slots using taboo search. Last, assigns a classroom to every teaching task and outputs the course timetable.This paper proposes an outline of the algorithm at first. Then, a detailed explanation is given on how to establish the network-flow model as well as how to use the essential factors in taboo search. Finally, uses the real data to carry out the simulation test.
  The implementation of the plan, which unifies the classical network flows algorithm and the modern heuristic taboo search algorithm, causes the superiorities of two algorithms supplementing each other, and improves the ability of processing problems. After confirmed through the real data simulation, the algorithm which this paper proposed is of certain feasibility and the serviceability.
Keywords: Course-Timetabling Problem,Combinatorial Optimization
Network Flow,Taboo Search