運動競賽模型之建構與分析 -以中原大學系壘聯賽為例

Construction and analysis of sport scheduling -Chung Yuan Christian University Softball League as as Example

黃信瑋(Hsin-Wei Huang)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu201100778

摘要

本研究針對中原大學系隊壘球的賽程進行探討，分析在隊伍數為何的情況下該於幾週內可排完賽程且滿足硬性限制與軟性限制，了解整個賽事的架構後再利用限制滿足規劃(Constraint Satisfaction programming)的方式由程式排出完整的賽程。
本研究後續又對單次循環賽中隊伍間的影響(Carryover effect)進行研究，由對稱矩陣法(diagonal symmetric matrix)產生多組循環賽，再利用禁忌搜尋法(Tabu search)搜尋每組循環賽的最佳解，再由多組的最佳解中找尋本部分的目標值。

關鍵字

限制滿足規劃 ； 禁忌搜尋法 ； 影響值 ； 循環賽

並列摘要

In this paper,we consider a sport league scheduling problem which occurs in the Department Chung Yuan Christian University softball leagues. The problem receives the number of teams and decide the number of weeks of the scheduling where different hard and soft constraints have to be taken into account.We understand the structure of the softball league and use Constraint Satisfaction programming to generate Schedule.
The second part of this paper,we consider the carry-over effects value of a round robin tournament schedule .We use the diagonal symmetric matrix to generate many round robin tournaments schedule and using “Tabu search” to search for each local optimal solution. Final,the purpose of this paper is to find the optimal solution from each local optimal solution.

並列關鍵字

round robin tournament schedule ； Tabu search ； Carryover effect ； Constraint Satisfaction programming

參考文獻

Miyashiro, R., & Matsui, T. (2006). Minimizing the Carry-Over Effects Value in a Round-Robin Tournament. TATAT, 460-463.

Bartsch, T., Drexl, A., & Kroger, S. (2006). Scheduling the professional soccer leagues of Austria and Germany. Computers & Operations Research, 33(7), 1907-1937.

Brailsford, S. C., Potts, C. N., & Smith, B. M. (1999). Constraint satisfaction problems:Algorithms and applications. European Journal of Operational Research, 119, 557-581.

Briskorn, D., & Drexl, A. (2009). A branching scheme for finding cost-minimal round robin tournaments. European Journal of Operational Research, 197(1), 68-76.

Briskorn, D., & Knust, S. (2010). Constructing fair sports league schedules with regard to strength groups. Discrete Applied Mathematics, 158(2), 123-135.