シフトスケジューリング問題における量子アニーリングマシンの初期評価

• Item type: Symposium(1)
• 公開日: 2021-11-25
• タイトル: シフトスケジューリング問題における量子アニーリングマシンの初期評価
• タイトル / 言語: en
• タイトル: Initial Evaluation of a Quantum Annealing Machine for the Shift Scheduling Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: スケジューリング
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 慶應義塾大学政策メディア研究科
• 著者所属: 株式会社KDDI総合研究所／慶應義塾大学政策メディア研究科
• 著者所属: 慶應義塾大学環境情報学部
• 著者所属(英): en
• 著者所属(英): Keio University
• 著者所属(英): en
• 著者所属(英): KDDI Research, Inc. / Keio University
• 著者所属(英): en
• 著者所属(英): Keio University
• 著者名: 浜田, 捺希; 斎藤, 和広; 川島, 英之
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: シフトスケジューリング問題はコールセンターのアルバイトなどのシフトの組み合わせ最適化問題である．この問題はナーススケジューリング問題などの必要な人員数が定められ，複数の制約の元で人員を割り当てなければならないスケジューリングを行う現実問題に応用することが可能な問題である．この問題は考慮する人数や期間が増えるほど組合せ数が膨大となり，厳密解を求めることが困難となる．量子アニーリングは量子コンピュータの一種として，このような組み合わせ最適化問題を現実時間で解くことが期待されている．本論文では目的関数や制約式を量子アニーリングに適用できるQUBO(Quadratic Unconstrained Binary Optimization)で定式化し，D-wave社の量子アニーリングマシンを用いてシフトスケジューリングにおける量子アニーリング適用の効果を評価た．更に，量子アニーリングシミュレータであるOpenJijと既存手法として制約充足問題のソルバーであるThe Z3 theorem proverと比較し，量子アニーリングマシンの有効性を検証した．
• 書誌情報: コンピュータシステム・シンポジウム論文集; 巻 2021, p. 11-18, 発行日 2021-11-25
• 出版者 / 言語: ja
• 出版者: 情報処理学会