排課問題是一個在多重限制下的最佳化問題，其限制包含班級數、教師人數、課程安排等，由學校行政人員根據給予的限制條件，去安排課表。在本篇研究中，基於教師授課鐘點數、班級的課程安排、各個科目的應上課節數與各班的授課教師 安排等限制條件，建構出對應的限制式，目標是盡可能安排各科領域時間以及最 佳化教師授課天數等，最後透過線性規劃來尋找目標函數的最佳解。本研究採用 Python 及 MATLAB 撰寫其求解的演算法架構，模擬一所完整包含三個年級，30個班、81位教師，約8萬個變數、11萬條不等式以及1千條等式的二元變數問題，並 成功求得此問題的課表。

The course scheduling problem is an optimization problem with multiple constraints, including the number of classes, teachers, and course arrangements. School administrative staff arrange the schedule based on the given constraints. In this study, general constraints such as the teaching hours for teachers, course arrangements for each class, the required number of lessons for each subject, and the assignment of teachers to each class are modeled into corresponding constraint equations. Then, the objective functions are constructed to address scenarios commonly encountered in high school scheduling, such as optimizing collaborative lesson planning times and the number of teaching days for teachers. Finally, linear programming is used to find the optimal scheduling solution. This study uses Python and MATLAB to develop the algorithmic framework for solving the problem, simulating a high school scheduling scenario involving three grades, 30 classes, 81 teachers, approximately 80,000 variables, 110,000 inequalities, and 1,000 equalities' binary variable problem, successfully obtaining a solution to this scheduling problem.

[1] Mei Ching Chen, San Nah Sze, Say Leng Goh, Nasser R. Sabar, and Graham Kendall. A survey of university course timetabling problem: Perspectives, trends and opportunities. IEEE Access, 9:106515–106529, 2021.
[2] A.S. Asratian and D. de Werra. A generalized class–teacher model for some timetabling problems. European Journal of Operational Research, 143(3):531–542, 2002.
[3] Janice K. Winch and Jack Yurkiewicz. Case article—class scheduling with linear programming. INFORMS Transactions on Education, 15(1):143–147, 2014.
[4] John J. Dinkel, John Mote, and M. A. Venkataramanan. Or practice—an efficient decision support system for academic course scheduling. Operations Research, 37(6):853–864, 1989.
[5] Hamed Babaei, Jaber Karimpour, and Amin Hadidi. A survey of approaches for university course timetabling problem. Computers Industrial Engineering, 86:43–59, 2015. Applications of Computational Intelligence and Fuzzy Logic to Manufacturing and Service Systems.
[6] 王富民. 基因演算法於排課問題上之研究. Master’s thesis, 國立臺灣師範大學資訊教育研究所, 2001.
[7] N G A P H Saptarini, I W Suasnawa, and P I Ciptayani. Senior high school course scheduling using genetic algorithm. Journal of Physics: Conference Series, 953(1):012067, jan 2018.
[8] R Ansari and N Saubari. Application of genetic algorithm concept on course scheduling. IOP Conference Series: Materials Science and Engineering, 821(1):012043, apr 2020.
[9] Yen-Zen Wang. Using genetic algorithm methods to solve course scheduling problems. Expert Systems with Applications, 25(1):39–50, 2003.
[10] Melanie Mitchell. An Introduction to Genetic Algorithms. The MIT Press, 02 1996.
[11] 蔡鎬匡. 將柏拉圖最佳化應用於高中排課系統. Master’s thesis, 國立中正大學資訊工程所, 2009.
[12] E. Aycan and T. Ayav. Solving the course scheduling problem using simulated annealing. In 2009 IEEE International Advance Computing Conference, pages 462–466, 2009.
[13] Ramon Alvarez-Valdes, Enric Crespo, and Jose M Tamarit. Design and implementation of a course scheduling system using tabu search. European Journal of Operational Research, 137(3):512–523, 2002.
[14] Daniel Costa. A tabu search algorithm for computing an operational timetable. European Journal of Operational Research, 76(1):98–110, 1994.
[15] George B. Dantzig. Linear programming. Operations Research, 50(1):42–47, 2002.
[16] H. P. Williams. Model building in mathematical programming / H. Paul Williams. Wiley, Chichester ;, 4th ed. edition, 1999.
[17] Jiří Matoušek and Bernd. Gärtner. Understanding and using linear programming / Jiří Matoušek, Bernd Gärtner. Universitext. Springer, Berlin, 2007.
[18] Michael C. Ferris, Olvi L. Mangasarian, and Stephen J. Wright. Linear programming with MATLAB / Michael C. Ferris, Olvi L. Mangasarian, Stephen J. Wright. MPS-SIAM series on optimization. Society for Industrial and Applied Mathematics, Philadelphia, 2007.
[19] Mark M. Meerschaert. Chapter 3 - computational methods for optimization. In Mark M. Meerschaert, editor, Mathematical Modeling (Fourth Edition), pages 57– 112. Academic Press, Boston, fourth edition edition, 2013.
[20] Christodoulos A. Floudas and Xiaoxia Lin. Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research, 139:131–162, 2005.
[21] Laurence A. Wolsey. Integer programming / Laurence A. Wolsey. Wiley- Interscience series in discrete mathematics and optimization. Wiley, New York, 1998.