以限制規劃模式求解校內運動表－以中原大學系際盃壘球賽為例

Constraint Programming Approach to the Intramural Sport-Scheduling Problem: Case Study of the CYCU Softball League

蔡宗憲(Chung-Hsieh Tsai) ； 李士賢(Shuh-Hsien Lee)

《先進工程學刊》 7卷2期 (2012/04) Pp. 81-85

https://doi.org/10.29948/JAE.201204.0004

摘要

本文以校系際盃壘球賽為例，建構限制規劃模式（ConstraintProgramming，CP）求解滿足場地與時間限制條件的賽程表。目標是18支參賽隊伍在11週153場比賽期間3個場地出賽的次數相同，且各隊出賽時間、隔場限制相等，達到機會均等的公平原則。特別是引進三連戰制度，使賽程延誤的可能性大為降低。研究以虛擬球隊的方式進行求解，顯示限制規劃模式確能有效率的解決運動排程問題。

關鍵字

運動排程 ； 限制滿足問題 ； 限制規劃

並列摘要

The purpose of this paper is to create a schedule for the intramural softball league that satisfies venues availability and various timing restrictions. To this end, a constraint programming approach is employed as the methodology to solve the problem. The proposed schedule is reasonably fair to each team in result of 153 games among 18 teams are assigned at 3 venues on specific time evenly spaced and the games are, with the constraint, separated into one game after the next one throughout the 11-week season as well. Furthermore, by introducing a 3 consecutive games model, the possibility in delay to the games is significantly reduced. Results imply that after several virtual teams are added to the scheduling process to meet all the requirements, the constraint programming approach achieves feasible solution efficiently for the sports scheduling problem.

並列關鍵字

sports scheduling ； constraint satisfaction problem ； constraint programming