論文：　平成22年度修士論文
題目：　デッドロック回避方策を用いたAGVのタスク割当てと経路計画の同時最適化
著者：　田中　友貴

本研究では，動的搬送環境下でのAGVのタスク割当てと経路計画について，新たなタスクが与えられた時点を初期条件とした搬送システムモデルをペトリネットによって表現し，その最適発火系列問題を繰り返し解くことにより，タスク割当てと経路計画を同時に最適化する方法を提案する．最適発火系列問題の解法として，大規模問題に対して有効なペトリネットの分解と調整による最適化法を採用する．静的問題を表現するペトリネットは，タスク割当てに関するサブネットとAGVの経路計画に関するサブネットにそれぞれ分解される．サブネットから構成された部分問題は，ダイクストラ法を用いて求解される．また，ペトリネットの分解と調整による最適化法に対し，デッドロック回避方策を用いた実行可能化アルゴリズムを導入することで，導出された発火列の実行可能性を保証する．数値実験において，提案法と最近傍法によるタスク割当てを用いた手法を比較し，タスク割当てと経路計画を同時に最適化することの有効性を静的問題，および動的問題に対して検証する．

論文：　平成22年度修士論文
題目：　列生成法による鉄道乗務員スケジューリング問題の解法
著者：　室井　裕喜

鉄道乗務員スケジューリング問題とは，列車を計画通りに運行できるよう，乗務員を割当てる問題である．鉄道乗務員スケジューリング問題の有効な解法 の一つとして列生成法による解法が提案されている．この解法は精度の良い下界値を求めることができるが，収束に時間を要するという欠点を持っている．そこで，本研究では鉄道乗務員スケジューリング問題に対し双対不等式を提案し，列生成法による解法に適用する．列車の運行計画より生成した双対不等式を用 いて双対空間を切除することにより，列生成法の収束性改善を目指す．さらに，本研究では効率の良い実行可能化法を検討し，列生成法の計算時間短縮を目指 す．鉄道乗務員スケジューリング問題は主にヨーロッパにおいて研究が盛んであり，実用化も進んでいる．しかし，本問題は国・地域・鉄道事業者ごとに目的・ 制約条件が異なり，海外において実用段階にある先行研究では日本で見られる制約が考慮されていない．そこで，本研究では日本で見られる制約を考慮した鉄道 乗務員スケジューリング問題に対し，列生成法による解法の適用をおこなう．乗務員の上限制約・一連続乗務時間上限制約・食事休憩制約などを考慮し，列生成 子問題の解法・実行可能解の作成方法に対する改善を提案する．また，数値実験によりその効果を検証する．

論文：　平成22年度修士論文
題目：　時間オートマトンによるスケジューリング問題の分解可能性に関する考察
著者：　若竹　雅人

ある与えられた問題に対して，個々の要素のモデル化を時間オートマトンで行い，それらの個々のモデルのパラレルコンポジションを構成することにより，システム全体のモデルを容易に得ることが可能である．しかしながら，システムを構成する要素の数が増大化，システムが大規模化すると状態空間爆発の問題が生じる．本研究では，状態空間爆発の問題を避けるために時間オートマトンの分解と調整によるスケジューリング問題の解法を提案する．提案法は，得られた解を調整することにより，全体の実行可能解を得る手法である．スケジューリング問題の全体実行可能なモデルに対し分解条件を定義し，分解条件を満たすような複数の分解例を示す．示した複数の分解法をフローショップスケジューリング問題に適用することにより，提案法の有効性を検証する．

論文：　平成21年度修士論文
題目：　ラグランジュ緩和を用いたペトリネットの分解と調整によるスケジューリング手法察
著者：　島谷　謙一

生産システムなどの様々な分野において, 離散事象システムを表現するためのモデルとしてペトリネットは幅広く用いられている. ペトリネットを用いることでシステムは表現され, 最適化問題は, 与えられた目標マーキングに到達するトランジションの発火系列のうち, 目的関数を最小化するものを決定する問題として定式化される. しかし, システムの規模が大きくなるにつれてペトリネットの構造が複雑化するため, 全体の厳密解を得ることは困難となる. このような問題を解決するため, ペトリネットを複数のサブネットに分解し, サブネットごとに部分解を求める手法が提案されている. 本研究では, ラグランジュ緩和を用いて制約条件を緩和し, サブネットごとに部分問題を定式化し, 部分問題の解の導出と調整を繰り返す分散型スケジューリング手法を提案する. 提案手法について自律無人搬送車(AGV)経路計画問題やフローショップ・スケジューリング問題において, 数値実験による従来手法との結果の比較を行い, 提案手法の有効性を検証する. また, 提案手法のハイブリッドペトリネットへの応用も行う. ハイブリッドペトリネットは, ペトリネットに連続の要素をもたせた拡張モデルである. 離散値と連続値が混在するシステムに対して, 数値実験により提案手法の応用を行う.

論文：　平成21年度修士論文
題目：　カット生成を用いたラグランジュ緩和によるフローショップ問題の解法
著者：　平中　雄一郎

スケジューリング問題には，ハイブリットフローショップスケジューリング問題，処理順序依存の段取り時間を考慮したフローショップスケジューリング問題がある．これらの問題は現実のスケジューリング問題の多くが帰着されるNP困難な問題であり，実用的な計算時間で精度の良い近似解を導出すること，およびその解の評価を行うことが求められている．そこで，本研究では，ハイブリットフローショップスケジューリング問題，処理順序依存の段取りを考慮したフローショップスケジューリング問題それぞれに対して，カット生成を用いたラグランジュ緩和による解法を提案する．提案法は，スケジューリング問題を実用的な時間内で解き，下界値の導出による解の最適性評価が可能なラグランジュ緩和法と呼ばれる手法を基本とする．これは，問題を緩和し，容易に解くことが可能な部分問題に分解して，動的計画法で効率よく解く手法である．本研究では，このラグランジュ緩和法を，対象とする問題に適用する方法を示す．さらに，緩和問題にカットと呼ばれる妥当制約を追加して得られる下界値を改善する手法についても提案する．また，実用的な計算時間で問題を解くことができるように，計算量の削減方法も提案する．最後に，数値実験によって，提案手法とその他手法との比較，様々な問題に対する適用などを行い，提案手法の有効性を示す．

論文：　平成21年度修士論文
題目：　数量割引を考慮した不確定需要下におけるサプライチェーン計画問題の解法法
著者：　山崎　修平

本論文では，数量割引を考慮したサプライチェーン計画問題の解法を提案する．対象とする問題はZhang and Ma(2008)によって提案されたモデルであり，数量割引を考慮した取引契約の下でのサプライヤ選択と，不確定需要下において生産量や在庫量を同時に決定する単一期間のサプライチェーン計画問題である．サプライチェーン計画問題において数量割引を考慮する場合，サプライヤと生産者間の取引価格は生産量に依存して変化するため，問題は非線形混合整数計画問題として定式化される．この問題に対して，Duran and Grossmann(1986)によって提案された外部近似法とヒューリスティックスを組み合わせた解法のアルゴリズムを提案する．提案手法では，離散変数を固定した条件下での主問題を解くことによって得られる上界値と, 連続変数を固定した条件下で逐次線形化することによって得られる下界値との差を小さくすることによって, 解の最適性を保証しながら解の探索を行う．提案手法の有効性を検証するため，Zhang and Ma(2008)によって与えられた3つの例題に対して，提案手法と, 分枝限定法と非線形計画法を組み合わせた従来法との性能比較を行った．数値実験の結果，上界値算出にSQP法を採用した提案手法によって小規模問題では最適解が得られること，および大規模問題に対しては，上界値算出にヒューリスティックを採用した方法が有効であることを確認した．

論文：　平成21年度修士論文
題目：　ペトリネットの分解による最適発火系列問題の解法と状態数に関する考察
著者：　吉江　瞬

ペトリネットを用いた従来のスケジューリング手法では, 極めて簡単な構造を持つペトリネットですら状態数が膨大になり, 全ての状態を探索して最適なスケジュールを決定することは困難である. このような状態空間爆発を回避する有効な方法として, ペトリネットの分解による最適発火系列問題(OTFS) の解法が提案されている. 従来の分解法のアルゴリズムにおいては, OTFSを表現するペトリネットを複数のサブネットに分解する際のサブネットの選択方法には複数の候補が存在する. 本研究では, サブネットによって生成される可到達状態木と可到達状態グラフについて, 生成される状態数が時間ステップに関して多項式オーダーとなるようなサブクラスを定義する. そして, これら