Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lên lịch tổ chức giải quần vợt theo thể thức round robin dưới những hạn chế về thời gian sân và cầu thủ
Tóm tắt
Một vấn đề thực tiễn mà ban quản lý của một câu lạc bộ quần vợt gặp phải là tổ chức một giải quần vợt cho các thành viên trong câu lạc bộ. Các tham gia giải đấu sẽ được chia thành các loạt khác nhau: trong mỗi loạt, mỗi cầu thủ sẽ thi đấu một lần mỗi tuần với một đối thủ khác trong thể thức thi đấu vòng tròn. Tất cả các trận đấu đều có một giới hạn thời gian là một giờ. Tất cả các loạt sẽ sử dụng chung một nhóm sân, với tính khả dụng hàng tuần đã được xác định trước. Hơn nữa, các cầu thủ cũng có những hạn chế về thời gian khả dụng của họ. Với sự khả dụng của các sân và cầu thủ, mục tiêu là lập lịch cho giải đấu mà không vi phạm các hạn chế, hoặc thực tế hơn, nhằm tối đa hóa số lượng trận đấu khả thi. Vấn đề này có thể được định hình như một bài toán ghép nối tối đa, với ràng buộc bổ sung rằng mỗi cầu thủ chỉ được thi đấu một lần mỗi tuần. Nó cũng có thể được mô hình hóa như một bài toán đỉnh tối đa. Một quy trình khai thác hai bước được đề xuất để giải quyết vấn đề: đầu tiên, các giải thi đấu vòng tròn cho mỗi loạt được tạo ra, sau đó, các trận đấu của mỗi giải đấu được phân bổ cho các sân khả dụng cho mỗi tuần bằng cách sử dụng quy trình tìm kiếm cục bộ. Quy trình này đã được triển khai thành công và hiện đang được câu lạc bộ quần vợt sử dụng.
Từ khóa
#giải quần vợt #lập lịch thi đấu #thể thức round robin #tối đa hóa trận đấu #hạn chế khả dụngTài liệu tham khảo
D.C. Blest and D.G. Fitzgerald, Scheduling sports competitions with a given distribution of times, Discrete Applied Mathematics 22(1988/89)9-19.
F. Della Croce, Generalized Pairwise Interchanges and machine scheduling, European Journal of Operational Research 73(1995)310-319.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
F. Glover, Tabu search, Part I, ORSA Journal on Computing 1(1989)190-206.
F. Glover, Tabu search, Part II, ORSA Journal on Computing 2(1990)4-32.
J. Haselgrove and J. Leech, A tournament design problem, American Mathematics Monthly 84(1977)198-201.
E. Mendelsohn and A. Rosa, One-factorizations of the complete graph — a survey, Journal of Graph Theory 9(1985)43-65.
C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, 1982.
J.A.M. Schreuder, Combinatorial aspects of construction of competition of Dutch Professional Football Leagues, Discrete Applied Mathematics 35(1992)301-312.
J.A.M. Schreuder, Construction of fixture lists for Professional Football Leagues, Internal Report, Ph.D., Department of Management Science, University of Strathclyde, Glasgow, UK, 1993.
W.D. Wallis, A tournament problem, Journal of the Australian Mathematical Society (B) 24(1983)289-291.
D. de Werra, Scheduling in sports, in: Studies on Graphs and Discrete Programming, ed. P. Hansen, North-Holland, Amsterdam, 1981, pp. 381-395.
D. de Werra, L. Jacot-Descombes and P. Masson, A constrained sports scheduling problem, Discrete Applied Mathematics 26(1990)41-49.