大專院校自動化排課系統最佳化之研究

Optimal design of university course scheduling system

黃允成；陳奕安

排課排程 ； 偏好 ； 整數規劃法 ； Courses scheduling ； preference ； Integer programming model

資訊與管理科學

10卷1期（2017 / 07 / 30）

3 - 19

繁體中文

排課問題為一特殊之排程問題，亦為一最佳化求解問題。目前許多學校仍以人工方式進行排課，既耗時又費力。透過文獻整理，可了解各種不同排課方式，並對排課問題進行深入探討。本研究係將人工排課邏輯、教師偏好、各項資源限制及多種人性化因素等，轉換成電腦化自動排課系統，透過整數規劃法建立完整之排課模型，再運用數學規劃軟體進行排課系統模型設計。本研究同時考量教師授課時段偏好、各項資源限制(包含空間、班級、教師、課程連堂與否、重修方便性、教師居住地遠近、課程進度一致性等)及公平性，運用多種軟體，進行電腦化自動排課系統之開發與設計，並經實際案例分析，驗證本研究所開發之排課系統，遠比人工排課方式更具完整性、公平性與效率性，深具實務應用價值。

Courses scheduling is a special scheduling, and it’s also an optimization problem. Many schools and universities still to do the courses scheduling by hand. The handmade courses schedulingis inefficiency and time-consuming. Based on handmade course scheduling logic and considering the teacher’s preference and varioushumanity factors, we build up anInteger programming model and then design a computerized course scheduling system to find out an optimal course scheduling timetable. In this system, we considered variousresources' constraints (including spaces, classes, teachers, course arrangement, course retake, living locations of teachers，progress of the same course in different classes, and so on), teachers' preferences and fairness. Furthermore, we transferred the binary solution into a user-friendly timetable, automatically. In this study, we solving the course scheduling problemwithmultiple software packages to create three-type courses timetables. Through by real case testing, the proposed system is more efficiency and fairness than handmade ones.

1. Abdelhalim, EA,El Khayat, GA(2017).A Utilization-based Genetic Algorithm for Solving the University Timetabling Problem (UGA).Alexandria Engineering Journal,55(2),1395-1409.
2. Abdelhalim, EA,ElKhayat, GA(2017).An information visibility-based university timetabling for efficient use of learning spaces (IVUT).Egyptian Informatics Journal,17(3),315-325.
3. Alvarez-Valdes, R,Crespo, E,Tamarit, JM(2002).Design and implementation of a course scheduling system using Tabu Search.European Journal of Operational Research,137(3),512-523.
4. Burke, E,Jackson, K,Kinston, JH,Weare, R(1998).Automated university timetabling:The state of the art.The Computer Journal,40(9),565-571.
5. Dorneles, AP,Olinto, CB,Buriol, LS(2017).A column generation approach to high school timetabling modeled as a multicommodity flow problem.European Journal of Operational Research,256(3),685-695.
6. MirHassani, SA(2006).A computational approach to enhancing course timetabling with integer programming.Applied Mathematics and Computation,175(1),814-822.
7. Mooney, EL,Rardin, RL,Parmenter, WJ(1996).Large-Scale classroom scheduling.IIE Transactions,28(5),369-378.
8. Shiau, DF.(2011).A hybrid particle swarm optimization for auniversity course schedulingproblem with flexible preferences.Expert Systems withApplications,38(1),235-248.
9. Skoullis, VI,Tassopoulos, IX,Beligiannis, GN.(2017).Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm.Applied Soft Computing,52,277-289.
10. Tassopoulos, IX,Beligiannis, GN(2012).Solving effectively the school timetabling problem using particle swarm optimization.Expert Systems with Applications,39(5),6029-6040.