ニューラルネットワークによる複数機械の協調タスクを含んだ並列機械スケジューリング

概要

論文の詳細を見る
本稿では並列機械スケジューリング問題の一種として,特に複数のマシンが同期・協調的に処理する「協調タスク」を含み,さらに目的関数として「滞留時間和」「納期ずれ時間和」の双方を扱う問題に言及し,これを解決する手法としてリカレント型ニューラルネットワークの組合せ最適化を応用した新たなモデルを提案した.提案モデルは「タスク」「マシン」および「処理時刻」を符号化した3次元構造のスケジュール層と,問題に内在する制約や目的関数を符号化した制約層から構成される構造とした.特に処理時刻を直接符号化したことで,協調タスクにともなうマシンの同期が容易になった.また,周囲に配置された複数の制約層が中央のスケジュール層を制御する構造により,複数の制約や目的関数の同時並行的な処理が可能となった.評価実験ではタスク数とマシン数の増加に対する提案モデルの効率性を調査したほか,協調タスクを含まない場合と含む場合の双方のスケジューリングについて,既存手法との比較を行った.その結果,特に納期ずれ時間和に関して従来手法より優れた結果が得られ,モデルの有効性が示された.
2006-10-15