文献

J-GLOBAL ID：201802268929658950   整理番号：18A0331715

高等学校時間割作成のための探索MaxSATベース大規模近傍【Powered by NICT】

MaxSAT-based large neighborhood search for high school timetabling

著者 (2件)： Demirovic Emir (Vienna University of Technology, Institute of Information Systems, Databases and Artificial Intelligence Group, Favoritenstrasse 9/184-2, 1040 Vienna, Austria) ,  Musliu Nysret (Vienna University of Technology, Institute of Information Systems, Databases and Artificial Intelligence Group, Favoritenstrasse 9/184-2, 1040 Vienna, Austria)
資料名： Computers & Operations Research  (Computers & Operations Research)
巻： 78  ページ： 172-180  発行年： 2017年 
JST資料番号： H0216B  ISSN： 0305-0548  CODEN： CMORAP  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 高等学校時間割作成(HSTT)は良く知られた,広い拡散問題である。問題は種々の制約に関して配位資源(例えば教師,室),時間,とイベント(例えば講義)から構成されている。残念なことに,HSTTは解決困難であり,HSTTの簡単な変異体に対する実現可能解は,NP完全であることが証明されている。局所探索を結合した新規maxSATベース大規模近傍探索とHSTTのための新しいアルゴリズムを提案した。局所探索アルゴリズムは,初期溶液を駆動する局所最適に使用され,maxSATに基づく,より強力な大規模近傍探索(LNS)法を用いて解をさらに改善した。第三回国際タイムテーブリング競技会2011とXHSTT2014ベンチマークアーカイブから採取した場合に関する実験結果を用いて提案アプローチの有効性を証明した。した39例中27例をモデル化することができた。XHSTTの現在使用されているmaxSAT定式化は一般的で資源割り当てを支持しないので,残りの12例はモデル化しなかった。モデル化できる場合について,他のXHSTT最先端解法と比較した場合,このアルゴリズムは良好な性能を示し,いくつかの例のための新しい最も良く知られた上限を計算した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： モデリング ,  アルゴリズム ,  定式化 ,  *近傍探索法 ,  資源割付
準シソーラス用語： 最先端 ,  競技 ,  講義 ,  *近傍 ,  *時間割 , 【Automatic Indexing@JST】

著者キーワード (4件)： Max ,  SATHigh学校の時間割作成 ,  大規模近傍探索 ,  局所探索

分類 (1件)： 工程管理  (KB03030P)

タイトルに関連する用語 (5件)： 学校 ,  時間割 ,  探索 ,  大規模 ,  近傍