高中教師排班對於教育機構的運作效率、教學品質和教師滿意度具有重要影響。本研究提出了一種基於蟻群優化演算法（Ant Colony System, ACS）的解決方案，針對高中教師排班這一複雜的組合優化問題進行建模與求解。教師排班問題涉及多種硬限制和軟限制，包括教師授課時數分配、科目連續性、時段偏好等多重因素，為學校行政人員帶來巨大挑戰。我們設計了一個包含多層級費洛蒙矩陣的ACS模型，專門適應高中教師排班的特殊需求。該模型包括班級選擇、教師分配等決策層級，並針對問題特性對費洛蒙結構和啟發式信息進行了設計。我們採用創新的節點表示策略，將教師與班級、科目的分配轉化為節點選擇問題，使演算法能更有效地探索解空間。實驗結果表明，相較於傳統隨機排程方法，本研究的ACS演算法能生成更優質的教師排班方案。透過分析關鍵參數對搜索過程的影響，發現適當參數調整能在解的品質和演算法效率間取得平衡，同時滿足各項限制條件。本研究不僅證實ACS 在教師排班問題的應用價值，也為參數調整策略提供實證參考，研究成果可應用於高中排班系統及其他類似組合優化問題。

High school teacher scheduling plays a crucial role in institutional operations, teaching quality, and teacher satisfaction. This study proposes a solution based on Ant Colony System (ACS) to model and solve the complex combinatorial optimization problem of high school teacher scheduling. The scheduling problem involves multiple hard and soft constraints, including teaching hour allocation, subject continuity, and time slot preferences, which presents significant challenges for school administrators. We designed an ACS model incorporating multi-level pheromone matrices specifically adapted to the unique requirements of high school teacher scheduling. The model encompasses decision levels such as class selection and teacher assignment, with customized pheromone structures and heuristic information. We employed an innovative node representation strategy, transforming teacher-class-subject assignments into node selection problems, enabling the algorithm to explore the solution space more effectively. Experimental results demonstrate that our proposed ACS algorithm generates higher-quality teacher schedules compared to traditional random scheduling methods. Through analyzing the impact of key parameters on the search process, we found that appropriate parameter adjustments can achieve a balance between solution quality and algorithm efficiency while satisfying various constraints. This study not only confirms the applicability of ACS to teacher scheduling problems but also provides empirical references for parameter tuning strategies. The research outcomes can be applied to high school scheduling systems and other similar combinatorial optimization problems.

[1] D. Abramson. Constructing school timetables using simulated annealing: Sequential and parallel algorithms. Management Science, 37(1):98-113, 1991. doi: 10.1287/mnsc.37.1.98.
[2] Gangaram Anandalingam and Terry L Friesz. Hierarchical optimization: An introduction. Annals of Operations Research, 34(1):1-11, 1992.
[3] Hadrien Cambazard, Emmanuel Hebrard, Barry O’Sullivan, and Alexandre Papadopoulos. Local search and constraint programming for the post enrolment based course timetabling problem. Annals of Operations Research, 194(1):111-135, 2012. doi: 10.1007/s10479-010-0737-7.
[4] Stephen Casey and Jonathan Thompson. Grasping the examination scheduling problem. In E. Burke and P. De Causmaecker, editors, Practice and Theory of Automated Timetabling IV, volume 2740 of Lecture Notes in Computer Science, pages 232-244, Berlin, Heidelberg, 2003. PATAT 2002, Springer. doi: 10.1007/978-3-540-45157-0_15.
[5] Chun-Te Chen and Matthew M. Lin. Ant colony system for effective doctor rostering. Journal of Decision Making and Healthcare, 1(2):57-68, 2024. doi: 10.69829/jdmh-024-0102-ta01.
[6] Feng-Yi Chen. Optimization of high school course scheduling. Master’s thesis, National Cheng Kung University, Tainan, Taiwan, 7 2024. In Chinese with English abstract.
[7] Tim B. Cooper and Jeffrey H. Kingston. The complexity of timetable construction problems. In Practice and Theory of Automated Timetabling, pages 283-295. Basser Department of Computer Science, The University of Sydney, Springer Berlin Heidelberg, 1996.
[8] Marco Dorigo and Luca Maria Gambardella. A study of some properties of ant-q. In H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature– PPSN IV, Lecture Notes in Computer Science, pages 656-665, Berlin, 1996. Springer-Verlag. doi: 10.1007/3-540-61723-X_1029. TR/IRIDIA/1996-4, Université Libre de Bruxelles, Belgium.
[9] Marco Dorigo and Luca Maria Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53-66, April 1997. doi: 10.1109/4235.585892. Senior Member, IEEE, and Member, IEEE.
[10] Luca Maria Gambardella and Marco Dorigo. Solving symmetric and asymmetric tsps by ant colonies. In Proceedings of IEEE International Conference on Evolutionary Computation (ICEC’96), pages 622-627, Nagoya, Japan, 1996. IEEE. doi: 10.1109/ICEC.1996.542672.
[11] Luca Maria Gambardella, Éric D Taillard, and Marco Dorigo. Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society, 50(2):167-176, 1999. doi: 10.1057/palgrave.jors.2600676.
[12] Margarida Moz and Margarida Vaz Pato. A genetic algorithm approach to a nurse rerostering problem. Computers & Operations Research, 34(3):667-691, 2007. doi: 10.1016/j.cor.2005.03.019.
[13] Ahmed Oughalime, Wan Rosmanira Ismail, and Liong Choong Yeun. A tabu search approach to the nurse scheduling problem. In 2008 IEEE International Conference on Industrial Engineering and Engineering Management, pages 978-983. IEEE, 2008. doi: 10.1109/IEEM.2008.4738030.
[14] Nelishia Pillay. An overview of school timetabling research. Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, pages 321-335, 2014.
[15] Javier Puente, Alberto Gómez, Isabel Fernández, and Paolo Priore. Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms. Computers & Industrial Engineering, 56(4):1232-1242, 2009. doi: 10.1016/j.cie.2008.07.016.
[16] Andrea Schaerf. A survey of automated timetabling. Artificial Intelligence Review, 13(2):87-127, 1999.
[17] Rafał Skinderowicz. Improving ant colony optimization efficiency for solving large tsp instances. Applied Soft Computing, 2022. doi: 10.1016/j.asoc.2022.108653. Accepted Manuscript.
[18] Krzysztof Socha, Joshua Knowles, and Michael Sampels. A MAX-MIN ant system for the university course timetabling problem. In International Workshop on Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 1-13. Springer, 2002.