每學期初學校排課人員必須進行排課作業，一直以來都是排課人員所面臨的難題，目的是為了排出一個合理且高品質的課表，但往往耗費心力也無法有效地排出讓學生和教師皆滿意的課表。學校排課問題(School Timetabling Problem; STP)屬於時間表問題(Timetabling Problem; TTP)的一種，此問題主要將班級、教師、教室、課程等資源相互組合並指派於合適的時間段，同時需滿足相關的限制條件，而如何在有限的資源下排出可行又令人滿意的課表是具有一定的難度和複雜度，因此，排課問題常被視為NP-Complete或NP-hard問題。
本研究以臺灣一所國民中學進行中學排課問題(High School Timetabling Problem; HSTP)中之國民中學排課問題(Junior High School Timetabling Problem)研究與實際應用，建構以老師角度為考量目標的數學模型，並運用此國民中學之實際資料為題庫，提出基因演算法(Genetic Algorithm; GA)進行測試與求解此問題，在符合所有硬性限制下最小化所有軟性限制之值，以找出可行且有品質的排課表。最後將實驗結果與Gurobi進行比較，結果顯示本研究所提出的GA演算法求解能力與效率皆優於Gurobi。

The course timetabling is an important yet difficult decision which needs to be carefully planned by every school. However, it is difficult to generate course timetables that satisfy all the teachers and students. Thus, this research focuses on the School Timetabling Problem (STP) which aims to allocate a set of courses and a set of teachers to a set of classes over available time slots with an objective of minimizing teachers’ workload. This problem is regarded as an NP-hard problem and therefore, there is no polynomial algorithm that can be used to solve the problem.
This research focuses on the High school Timetabling Problem (HSTP) of a Taiwan’s junior high school. A mathematical model and a genetic algorithm (GA) are proposed for the problem. The mathematical model is solved by a branch-and-bound algorithm provided by Gurobi solver while the GA is implemented in C++ language. Experimental results show that the proposed GA outperforms Gurobi in terms of both solution quality and computational time. In addition, sensitivity analyses are conducted to analyze the impact of changing GA parameters on the objective value.

Ahmed, L. N., Özcan, E., & Kheiri, A. (2015). Solving high school timetabling problems worldwide using selection hyper-heuristics. Expert Systems with Applications, 42(13), 5463-5471.
Akkan, C., Gülcü, A. J. C., & Research, O. (2018). A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem. Computers & Operations Research, 90, 22-32.
Al-Yakoob, S. M., & Sherali, H. D. (2015). Mathematical models and algorithms for a high school timetabling problem. Computers & Operations Research, 61, 56-68.
Babaei, H., Karimpour, J., Hadidi, A. J. C., & Engineering, I. (2015). A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 86, 43-59.
Broder, S. (1964). Final examination scheduling. Communications of the ACM, 7(8), 494-498.
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.
Demirović, E., & Musliu, N. (2017). MaxSAT-based large neighborhood search for high school timetabling. Computers & Operations Research, 78, 172-180.
Deris, S., Omatu, S., & Ohta, H. (2000). Timetable planning using the constraint-based reasoning. Computers & Operations Research, 27(9), 819-840.
Di Gaspero, L., McCollum, B., & Schaerf, A. (2007). The second international timetabling competition (ITC-2007): Curriculum-based course timetabling (track 3). Technical Report QUB/IEEE/Tech/ITC2007/CurriculumCTT/v1. 0, Queen’s University, Belfast, United Kingdom.
Dorneles, Á. P., de Araújo, O. C., & Buriol, L. S. (2017). A column generation approach to high school timetabling modeled as a multicommodity flow problem. European Journal of Operational Research, 256(3), 685-695.
Drexl, A., & Salewski, F. (1997). Distribution requirements and compactness constraints in school timetabling. European Journal of Operational Research, 102(1), 193-214.
Even, S., Itai, A., & Shamir, A. (1975). On the complexity of time table and multi-commodity flow problems. Paper presented at the 16th Annual Symposium on Foundations of Computer Science.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning: Addison-Wesley Longman Publishing Co., Inc.
Gotlieb, C. C. (1963). The construction of class-teacher timetables. In IFIP congress, 62, 73-77.
Gunawan, A., Ng, K. M., & Poh, K. L. (2007). An improvement heuristic for the timetabling problem. International Journal Computational Science, 1(2), 162.
Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence.
Kheiri, A., Özcan, E., & Parkes, A. J. (2016). A stochastic local search algorithm with adaptive acceptance for high-school timetabling. Annals of Operations Research, 239(1), 135-151.
Kristiansen, S., Sørensen, M., & Stidsen, T. R. (2015). Integer programming for the generalized high school timetabling problem. Journal of Scheduling, 18(4), 377-392.
Leite, N., Melício, F., & Rosa, A. C. (2019). A fast simulated annealing algorithm for the examination timetabling problem. Expert Systems with Applications, 122, 137-151.
Lewis, R. (2008). A survey of metaheuristic-based techniques for university timetabling problems. OR spectrum, 30(1), 167-190.
Minh, K. N. T. T., Thanh, N. D. T., Trang, K. T., & Hue, N. T. T. (2010). Using tabu search for solving a high school timetabling problem. In Advances in Intelligent Information and Database Systems (pp. 305-313): Springer.
Odeniyi, O., Omidiora, E., Olabiyisi, S., & Oyeleye, C. J. A. J. o. R. i. C. S. (2020). A mathematical programming model and enhanced simulated annealing algorithm for the school timetabling problem. Asian Journal of Research in Computer Science, 21-38.
Pillay, N. (2014). A survey of school timetabling research. Annals of Operations Research, 218(1), 261-293.
Post, G., Ahmadi, S., Daskalaki, S., Kingston, J. H., Kyngas, J., Nurmi, C., & Ranson, D. (2012). An XML format for benchmarks in high school timetabling. Annals of Operations Research, 194(1), 385-397.
Qu, R., Burke, E., McCollum, B., Merlot, L. T., & Lee, S. Y. (2006). A survey of search methodologies and automated approaches for examination timetabling. Computer Science Technical Report No. NOTTCS-TR-2006-4, UK.
Saptarini, N., Suasnawa, I., & Ciptayani, P. (2018). Senior high school course scheduling using genetic algorithm. Paper presented at the Journal of Physics: Conference Series.
Saviniec, L., & Constantino, A. A. (2017). Effective local search algorithms for high school timetabling problems. Applied Soft Computing, 60, 363-373.
Saviniec, L., Santos, M. O., & Costa, A. M. (2018). Parallel local search algorithms for high school timetabling problems. European Journal of Operational Research, 265(1), 81-98.
Saviniec, L., Santos, M. O., Costa, A. M., & dos Santos, L. M. J. E. J. o. O. R. (2020). Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems. European Journal of Operational Research, 280(3), 1064-1081.
Schaerf, A. (1999). A survey of automated timetabling. Artificial intelligence review, 13(2), 87-127.
Skoullis, V. I., Tassopoulos, I. X., & Beligiannis, G. N. (2017). Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm. Applied Soft Computing, 52, 277-289.
Tassopoulos, I. X., & Beligiannis, G. N. (2012). Solving effectively the school timetabling problem using particle swarm optimization. Expert Systems with Applications, 39(5), 6029-6040.
Tassopoulos, I. X., Iliopoulou, C. A., & Beligiannis, G. N. (2019). Solving the Greek school timetabling problem by a mixed integer programming model. Journal of the Operational Research Society, 71(1), 117-132.
ten Eikelder, H. M., & Willemen, R. (2000). Some complexity aspects of secondary school timetabling problems. Paper presented at the International Conference on the Practice and Theory of Automated Timetabling.
Woumans, G., De Boeck, L., Beliën, J., & Creemers, S. J. E. J. o. O. R. (2016). A column generation approach for solving the examination-timetabling problem. European Journal of Operational Research, 253(1), 178-194.
Zhang, D., Liu, Y., M’Hallah, R., & Leung, S. C. (2010). A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. European Journal of Operational Research, 203(3), 550-558.
Zheng, S., Wang, L., Liu, Y., Zhang, R. J. I. J. o. C. S., & Mathematics. (2015). A simulated annealing algorithm for university course timetabling considering travelling distances. International Journal of Computing Science and Mathematics, 6(2), 139-151.
王江山，「以多標規劃求解大學教師排課最佳化之研究」，國立成功大學工業與資訊管理學系碩士在職專班碩士論文，民國93年
李昆穎，「演化式策略在國民中學排課問題之最佳化研究」，中華大學資訊工程學系碩士在職專班碩士論文，民國102年。
林俐儀，「設計啟發式演化式策略最佳化國民中學排課問題」，中華大學資訊工程學系碩士論文，民國104年。
邱元泰，「遺傳演算法在排課問題之應用」，國立中正大學數學研究所碩士論文，民國91年。
邱炤幃，「基因演算法在國小排課問題之應用」，屏東科技大學資訊管理系所
碩士論文，民國100年。
侯兆昇，「運用基因演算法解決高等職業學校排課問題」，義守大學資訊工程學系碩士論文，民國107年。
唐學明，「軍事學校電腦排課問題之探討」，復興崗學報(59)，129-155，民國85年。
康家豪，「國小自動排課系統之研究─粒子群最佳化演算法的應用」，臺北市立大學數學資訊教育學系數學資訊教育教學碩士學位班碩士論文，民國103年。
陳仲星，「國民中學排課問題最佳化研究─使用基因演算法」，樹德科技大學資訊管理系碩士論文，民國106年。
陳奕憲，「基因演算法在國民中學排課問題之最佳化研究」，南華大學資訊管理學系碩士班碩士論文，民國100年。
陳熠，「以C語言撰寫排課系統-以逢甲應數系為例」，逢甲大學應用數學學系碩士論文，民國104年。
彭美玉，「演化式策略於國民小學排課問題之最佳化研究」，中華大學資訊工程學系碩士論文，民國104年。
彭振為, 陳國祥, 范瑞芳, & 陳耀宗，「以基因演算法為基礎之排課系統」，國立澎湖科技大學資訊工程學系，第七屆離島資訊技術與應用研討會摘要論6文集，民國97年。
賀羲之，「基於人工智慧之排課系統」，國立臺北教育大學資訊科學系碩士論文，民國105年。
楊漢文，「以成本導向為基礎之排課系統」，國立東華大學資訊工程學系碩士論文，民國103年。
廖聖揚，「應用限制規劃方法求解軍事院校排課問題」，國立高雄第一科技大學資訊管理所碩士論文，民國94年。