文献

J-GLOBAL ID：202202281424135796   整理番号：22A1074713

Partial Team Swapを適用したときのKirkmanスケジュールの特性について

On properties of Kirkman schedules applied the partial team swap

著者 (1件)： 柏木佑介 (成蹊大)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 121  号： 407(COMP2021 31-39)  ページ： 16-23 (WEB ONLY)  発行年： 2022年02月27日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究では,Partial Team Swapを適用したときのKirkmanスケジュールの特性について示す.Kirkmanスケジュールは,スポーツスケジューリング問題において最も代表的なシングルラウンドスケジュールである.Partial Team Swap(PTS)とPartial Round Swap(PRS)は,スポーツスケジューリングの局所探索において代表的な近傍探索である.nをチーム数,kをn以外のあるチームとし,pを素数とする.また,P_i,j=[n]\{i,j}=∪^X_Q(Q=_i,j)_x=1P^x_i,jとする.ただし,それぞれのP^x_i,jは,Partial Team Swapの動作によって分割される頂点の集合であり,X_i,jは交換点i,jとしたときの分割数を表している.(1)n-1≠p,または(2)n-1=pかつP^x_k,n⊂P_k,nを満たすKirkmanスケジュールが与えられたとき,Partial Team Swapを適用するとKirkmanスケジュールでなくなるという特性を示した.上記の証明は既に[8]で行われているが,(1)の証明と(2)の証明をそれぞれ別の補題を用いてなされていたため,証明の単純化を図り,2つの条件を1つの補題のみを用いて統一的な証明を与えた.補足として,n-1がメルセンヌ素数である⇒P^x_i,j⊂[n]\{i,j}となる命題において,十分条件は満たしているが必要条件は満たしていないことを示した.また,KirkmanスケジュールにPartial Round Swapを適用すると同型でないKirkmanスケジュールを生成できることも示した.(著者抄録)

シソーラス用語： *スポーツ ,  *スケジューリング ,  *近傍探索法 ,  素数 ,  スケジュール
準シソーラス用語： 局所探索 ,  スケジュール作成

分類 (1件)： オペレーションズリサーチ一般  (KA03010Q)

引用文献 (12件)：

• A.Anagnostopoulos, L. Michel, P. Van Hentenryck, Y. Vergados, ′′A simulated annealing approach to the traveling tournament problem,′′ J Sched, vol.9, pp.177-193, 2006
• Fred Glover, ′′Ejection chains, reference structures and alternating path methods for travering salesman problems,′′ Discrete Applied Mathematics, vol.65, pp.223-253, 1996
• Kobayashi M, ′′Perfect one-factorization of the complete graph,′′ Graphs Comb, pp.351-353, 1989
• Marije Renske Siemann, ′′A polyhedral study of the Travelling Tournament Problem,′′ University of Twente, pp.10-11, 2020
• R. Lewis, J.Thompson, ′′On the Application of Graph Colouring Techniques in Round-Robin Sports Scheduling,′′ Operational Research Group, Cardiff School of Mathematics, 2010

タイトルに関連する用語 (1件)： スケジュール