請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/80400完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | Chun-Chung Wang | en |
| dc.contributor.author | 王俊中 | zh_TW |
| dc.date.accessioned | 2022-11-24T03:05:50Z | - |
| dc.date.available | 2021-08-10 | |
| dc.date.available | 2022-11-24T03:05:50Z | - |
| dc.date.copyright | 2021-08-10 | |
| dc.date.issued | 2021 | |
| dc.date.submitted | 2021-08-03 | |
| dc.identifier.citation | [1] Jeff Zillgitt. NBA schedule more player friendly with fewer back-to-back games. USA TODAY Sports, Aug 2015. URL https://www.usatoday.com/story/sports/2015/08/12/nba-schedule-more-player-friendly-fewer-back-back-games/31564149/. [2] George L Nemhauser and Michael A Trick. Scheduling a major college basketball conference. Operations Research, 46(1):1–8, 1998. [3] Rasmus V Rasmussen and Michael A Trick. Round robin scheduling–a survey. European Journal of Operational Research, 188(3):617–636, 2008. [4] Kelly King Easton. Using integer programming and constraint programming to solve sports scheduling problems. PhD thesis, Georgia Institute of Technology, 2002. [5] Filipe Brandão and João Pedro Pedroso. A complete search method for the relaxed traveling tournament problem. EURO Journal on Computational Optimization, 2(1):77–86, 2014. [6] Andrew Lim, Brian Rodrigues, and Xingwen Zhang. Scheduling sports competitions at multiple venues—revisited. European Journal of Operational Research, 175(1):171–186, 2006. [7] Graham Kendall, Sigrid Knust, Celso C Ribeiro, and Sebastián Urrutia. Scheduling in sports: An annotated bibliography. Computers Operations Research, 37(1):1–19, 2010. [8] Kelly Easton, George Nemhauser, and Michael Trick. The traveling tournament problem description and benchmarks. In International Conference on Principles and Practice of Constraint Programming, pages 580–584. Springer, 2001. [9] Clemens Thielen and Stephan Westphal. Complexity of the traveling tournament problem. Theoretical Computer Science, 412(4-5):345–351, 2011. [10] Rishiraj Bhattacharyya. Complexity of the unconstrained traveling tournament problem. Operations Research Letters, 44(5):649–654, 2016. [11] Sam Craig, Lyndon While, and Luigi Barone. Scheduling for the National Hockey League using a multi-objective evolutionary algorithm. In Australasian Joint Conference on Artificial Intelligence, pages 381–390. Springer, 2009. [12] Daniel Costa. An evolutionary tabu search algorithm and the NHL scheduling problem. INFOR: Information Systems and Operational Research, 33(3):161–178, 1995. [13] Mike B Wright. Scheduling fixtures for basketball New Zealand. Computers Operations Research, 33(7):1875–1893, 2006. [14] Kent J Kostuk and Keith A Willoughby. A decision support system for scheduling the Canadian Football League. Interfaces, 42(3):286–295, 2012. [15] Diego Recalde, Ramiro Torres, and Polo Vaca. Scheduling the professional Ecuadorian football league by integer programming. Computers Operations Research, 40(10):2478–2484, 2013. [16] Guillermo Durán, Santiago Durán, Javier Marenco, Federico Mascialino, and Pablo A Rey. Scheduling Argentina’s professional basketball leagues: A variation on the travelling tournament problem. European Journal of Operational Research, 275(3):1126–1138, 2019. [17] David Van Bulck and Dries Goossens. Handling fairness issues in time-relaxed tournaments with availability constraints. Computers Operations Research, 115: 104856, 2020. [18] James C Bean and John R Birge. Reducing travelling costs and player fatigue in the National Basketball Association. Interfaces, 10(3):98–102, 1980. [19] Renjun Bao. Time relaxed round robin tournament and the NBA scheduling problem. PhD thesis, Cleveland State University, 2009. [20] Feng-Cheng Yang. NBA sports game scheduling problem and GA-based solver. In 2017 International Conference on Industrial Engineering, Management Science and Application (ICIMSA), pages 1–5, 2017. [21] Hua-An Lu and Wei-Cheng Chen. A tournament scheduling model for National Basketball Association (NBA) regular season games. Journal of Advanced Research in Social Sciences and Humanities, 2(1):17–26, 2017. [22] Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983. [23] Gurobi Optimization. LLC. Gurobi optimizer reference manual, 2021. URL www.gurobi.com. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/80400 | - |
| dc.description.abstract | 運動賽事之排程對於任何一個運動賽事聯盟來說都是一個十分複雜且重要的問題，排程的品質直接影響了運動員的表現以及比賽的可看性。不必要的旅行距離以及過多的連續出賽次數不僅僅增加了運動員的疲勞也增加了整體聯盟的移動成本。 美國職業籃球聯盟(NBA) 是全世界知名的職業籃球聯盟，許多人更視其為籃球的最高殿堂，而其複雜的賽事規則以及眾多的隊伍數量使得在安排賽程上顯得十分困難。本論文提出了一個結合整數規劃及模擬退火演算法的兩階段式演算法去安排NBA 例行賽事，並且在符合賽事規則的情況下最小化球隊總旅行公里數以及所有球隊連續兩天出戰之次數。 我們利用 2018-19 NBA 例行賽的規則進行實驗並與 2018-19 NBA官方賽程進行比較。實驗結果顯示我們提出的演算法所規劃的賽程在兩個目標函數的表現上能同時進步12 %. | zh_TW |
| dc.description.provenance | Made available in DSpace on 2022-11-24T03:05:50Z (GMT). No. of bitstreams: 1 U0001-1211202013262400.pdf: 312542 bytes, checksum: b80e11d553129e7c7171c53e470d7484 (MD5) Previous issue date: 2021 | en |
| dc.description.tableofcontents | 誌謝ii 摘要iii Abstract iv 1 Introduction 1 2 Literature Review 3 2.1 Sports scheduling 3 2.1.1 Schedule types 3 2.1.2 Tournament structure 4 2.1.3 Common optimization objectives 4 2.1.4 Proposed methods 4 2.2 Travelling tournament problem 4 2.3 Time-relaxed sports scheduling 5 2.4 NBA scheduling problem 6 3 Problem Description 7 3.1 Structure and constraints 7 3.1.1 Basic structure 7 3.1.2 Special games 8 3.1.3 Constraints 8 3.2 Problem definition 9 3.3 Computational complexity 10 3.4 Objective functions 11 4 A Two-Phase Algorithm 14 4.1 Phase 1: Integer programming 14 4.1.1 Mathematical formula 15 4.2 Phase 2: Simulated annealing 16 4.2.1 Simulated annealing algorithm configurations 17 4.2.2 Generating neighbouring solutions 18 5 Computational Results 20 5.1 Simulated annealing parameters 20 5.2 Experiments in NBA 21 6 Conclusions and Future Work 26 Bibliography 28 | |
| dc.language.iso | en | |
| dc.subject | 組合最佳化 | zh_TW |
| dc.subject | 運動排程 | zh_TW |
| dc.subject | 整數規劃 | zh_TW |
| dc.subject | 模擬退火演算法 | zh_TW |
| dc.subject | integer programming | en |
| dc.subject | combinatorial optimization | en |
| dc.subject | sport scheduling | en |
| dc.subject | simulated annealing | en |
| dc.title | 結合整數規劃以及模擬退火演算法求解美國職業籃球例行賽事排程問題 | zh_TW |
| dc.title | Scheduling NBA Regular Season Games with Integer Programming and Simulated Annealing Algorithm | en |
| dc.date.schoolyear | 109-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 吳彥緯(Hsin-Tsai Liu),王弘倫(Chih-Yang Tseng) | |
| dc.subject.keyword | 運動排程,整數規劃,模擬退火演算法,組合最佳化, | zh_TW |
| dc.subject.keyword | sport scheduling,integer programming,simulated annealing,,combinatorial optimization, | en |
| dc.relation.page | 30 | |
| dc.identifier.doi | 10.6342/NTU202004332 | |
| dc.rights.note | 同意授權(限校園內公開) | |
| dc.date.accepted | 2021-08-05 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-1211202013262400.pdf 授權僅限NTU校內IP使用（校園外請利用VPN校外連線服務） | 305.22 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。