基因演算法應用於大學排課最佳化系統建置之研究

Genetic Algorithm on the optimization framework of Timetabling problem for University

張士宇(Shr -Yu Jang)

指導教授 ： 宋裕祺

國立臺北科技大學/工程學院/土木與防災研究所/碩士(2009年)

摘要

摘要
論文名稱：基因演算法應用於大學排課最佳化系統建置之研究 頁數：100
校所別：國立台北科技大學土木與防災研究所
畢業時間：九十七學年度第二學期 學位：碩士
研究生：張士宇 指導教授：宋裕祺
關鍵詞：基因演算法、排課問題
大專院校之排課一直都是教務行政人員各學期感到頭痛的問題。此問題受資
源分配限制，亦屬於NP-Complete 之問題，主要有課程、教師、教室、班級等資
源上的限制。使用傳統方法由行政人員來排課，不僅耗時耗力且不盡能滿足每位
老師的需求，常常需要透過與老師的溝通與協調來達成。
本文利用基因演算法求解排課問題，將教師課表設為染色體基因以儘量滿足
教師需求及教室分配之問題，使單一課程可在不同教室上課，增加排課較多之選
擇性。本系統利用C#撰寫程式語言，並結合資料庫之應用，方便使用者修改以及
維護資料。最後以筆者就讀之學校排課為例，結果證明本系統在多重資源限制下
可得到出令人滿意之結果。

關鍵字

基因演算法 ； 排課問題

並列摘要

ABSTRACT
Title：Genetic Algorithm on the optimization framework of Pages：100
Timetabling problem for University
School：National Taipei University of Technology
Time：July, 2009 Degree：Master
Researcher：Shr Yu, Jang Advisor：Yu-Chi, Sung
Keywords：Genetic Algorithms、School Timetabling
Course scheduling is a complicated problem for University which makes
administrative personnel feels puzzled in every term. This problem is limited by
resource allocation, also belonging to the NP-Complete problem, there are such
restrictions on resources as course, teacher, classroom, class, etc.Using administrative
personnel to solve course scheduling problem in traditional method does not only waste
time but also consume strength and can not satisfy all the teacher’s requires entirely, and
need to coordination with the teachers.
The thesis solves timetabling problem with Genetic Algorithm method, and set
teacher's school timetable as the chromosome gene to satisfy the teacher’s requirement
and arrange classroom assigning problem, making the single course have a class in
different classrooms to increase the option of course scheduling. This work constructs
with C# and combines the database, it helps the users revise and maintain the data
conveniently.

並列關鍵字

Genetic Algorithms ； School Timetabling

參考文獻

[2] B. Edmund, E. David, and W. Rupert, "A Genetic Algorithm for University Timetabling", Department of Computer Science, University of Nottingham, 1994.

[3] D. E. Goldberg, Genetic Algorithms in Search, Optimisation and Machine Learning, Addison-Wesley, Reading, 1989.

[4] D. C. Wood, "A Technique for Colouring a Graph Application to Large Scale Timetabling Problem", The Computer Journal, vol. 12, 1969, pp. 317-319.

[5] E. H. Loo, T. N. Goh, and H. L. Ong, "A Heuristic Approach to Scheduling University Timetables", Compute. Education, vol. 10, no. 3, 1986, pp. 388-397.

[6] Horacio Martinez-Alfaro and Gerardo Flores-Teran, "Solving the Classroom Assignment Problem With Simulated Annealing", Center for Artificial Intelligence, ITESM, IEEE 1998.