整數規劃應用於大學排課作業 —以中原大學工業與系統工程系為例

Integer Programming for University Class Scheduling-Department of Industrial and Systems Engineering at CYCU as an Example

李昕融(Hsin-Jung Li)

指導教授 ： 蘇玲慧

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2011年)

https://doi.org/10.6840/cycu201100911

摘要

大學排課作業是每學期的例行性業務，是件相當耗費時間之作業，為一種複雜的排程問題，亦為NP-Complete的問題。
本研究利用整數規劃模式，以中原大學工業與系統工程學系為例，求解排課問題，目的是將課程排入時段，在滿足各種條件限制條件之下，使各課程盡量皆可排入理想授課時段。本模式條件限制有分為硬性限制(hard constraints)和軟性限制(soft constraints)，硬性限制為不可違背之條件，軟性限制為盡量達成之條件。最後配合ILOG OPL求解軟體，在有效時間內完成排課，且證明所排出之課表皆符合系上規定。

關鍵字

整數規劃 ； 排程問題

並列摘要

University schedule arrangement for each semester is a routine operation. It is a quite time-consuming operation and also a very complex scheduling problem called a NP-complete (Non-deterministic Polynomial Time) problem.
In this study, we developed an integer programming model, and used Department of Industrial and Systems Engineering, Chung Yuan Christian University, as an example. The purpose is to arrange all the courses to time. Our objective is to maximize the quantity of courses that could arrange the teachers’ preference time, and satisfy every restricted condition. In this model, there are two types of constraints: hard constraint and soft constraint. The hard constraints must be satisfied without any violations, and the soft constrains are satisfied as far as possible. Finally, we solved the model by software ILOG OPL in feasible time. The effective time to complete the course arrangement and the discharge of the curriculum are in compliance with department regulations.

並列關鍵字

Scheduling problem ； Integer programming

參考文獻

Billionnet, A. (1999) ” Integer programming to schedule a hierarchical workforce with variable demands” European Journal of Operational Research, Vol. 114, pp. 105-114.

Bard, J. F., Binici, C., deSilva, A. H. (2003) ” Staff scheduling at the United States Postal Service” Computers & Operations Research 30, pp. 745-771.

Daskalaki, S., Birbas, T., Housos, E. (2004) ” An integer programming formulation for a case study” European Journal of Operational Research, Vol. 153, pp. 117-135.

Donald, L. D., Masood, A., B., Hollingsworth, J. (1998) ”A multi-objective course scheduling model: combining faculty preferences for courses and times.”Computers, Vol. 25. No. 4. pp. 303-316.

Dimopoulou, M., Miliotis, P (2001) ” Implementation of a university course and examination timetabling.” European Journal of Operational Research, Vol. 130, pp. 202-213.