表題番号：1997A-135 日付：2002/02/25
研究課題制約の厳しいスケジューリング問題へのＯＲアプローチ
研究者所属（当時） 資格 氏名
（代表者） 理工学部 教授 森戸　晋
研究成果概要
　従来扱われてきた比較的制約の緩いスケジューリング問題に対して、実際のスケジューリング問題は、対象のいかんを問わず、多くの複雑な制約条件を満たさなければいけないという場合が多い。このような制約の厳しいスケジューリング問題に対する体系的方法論が確立しているとは言い難い。本研究では、生産スケジューリングと看護婦シフトスケジューリングを取り上げ、数理計画法に基づく最適化やメタヒューリスティックス解法を用いた解法を用いたスケジュール生成の可能性と有効性を明らかにした。
　生産スケジューリングに関しては、他品種少量あるいは変種変量生産を支えるフレキシブル生産システム（ＦＭＳ）と、装置産業系のスケジューリングを取り上げ、シミュレーション／最適化、ならびに、混合整数計画法を用いた、実際的なスケジュール最適化方法を提案し、コンピュータを用いた数値実験によってその有効性と実用性を立証した。ＦＭＳに関しては、同種ジョブが繰り返し流れるＦＭＳ環境において、作業時間が短いジョブを優先する優先規則の納期性能が優れていることに着目し、これをもとに、優先規則の納期性能のをシミュレーションで評価しながら最適な優先順位を探索する方法を構築し、実験によってその性能を評価した。提案した方法は、シミュレーションによって特定のオーダー（＝同種ジョブの集まり）の納期余裕があると判断された場合に、当該ジョブの作業時間を長めに「見積もる」ことによって、オーダーの優先順位を落とすという操作に基づく局所探索であり、わずかのシミュレーション回数で、従来の作業時間に基づく優先規則より１割以上納期性能を改善可能である。
　一方、看護婦のシフトスケジューリングに関しては、複数の病院での聞き取り調査に基づき問題の特性を明らかにした上で、数理計画による定式化を試み、商用パッケージを用いた解法の性能を評価した。その結果、大規模な数理計画問題を単純に解こうとするとうまく解けない場合も、問題を複数の部分問題に「分割」して逐一的に解くことによって実用的な計算時間の範囲内で解が導出できることを明らかにした。
研究成果の発表
Susumu Morito and Keun Hyung Lee,“Efficient Simulation/Optimization of Dispatching Priority with‘Fake’Processing Time”, Proceedings of the 1997 Winter Simulation Conference, pp.872-789, 1997年12月。
村上元一、今泉淳、森戸晋、「ジョブの分岐のある２段階複数機械フローショップにおける納期遅れ最小化スケジューリング―ラグランジュ緩和に基づくヒューリスティックアプローチ」、生産スケジューリング・シンポジウム'97講演論文集、pp.85-90, 1997年10月。
Susumu Morito and Keun Hyung Lee,“Data Perturbation in Simulation-Based Dispatching with Application to FMS”, Proceedings of the World Congress on Systems Simulation, pp.168-174, 1997年9月。