　多目的スケジューリング問題において　　

シナリオを想定した選好解集合の生成法に関する研究

＜研究の目的＞　

　本研究はいくつかのシナリオを想定し、多目的の計画モデルにおいて、シナリオ変化に伴う解の非劣性と選好最適性の評価が問題について、いくつかの方法を提案して選好解集合を生成します。

＜多目的計画モデル＞　

実行可能解の集合Xと次元の評価基準ベクトルで与えられたときの多目的計画モデルは次のように定式化される。　　　　　　　　　　

そのおよびが確定的であり、これらを規定するパラメータの値が計画期間中に変わらなければ通常の多目的計画モデルとなる、しかし、スケジューリングなどでは作業時間や納期が急に変わる場合があり、上式のモデルでは不十分である。そこで、将来起こりうる状況をいくつかのシナリオにまとめ、「シナリオを想定した多目的計画モデル」と考えます。　　　　　　　，

ただし、はi番目のシナリオ、Iはシナリオインデックスの集合。

＜提案法＞候補解を順序を付けて、敏感性と最悪ケースなどで選好解集合を求めます。

① point ranking

② set ranking

③ preference ranking

そこで、候補解の順序付けた後、どのようにnの確率を使って選好解集合を表現するのは今後の課題となります。

＜n/1/( )　スケジューリング問題への適用＞

　シナリオを想定した多目的計画モデルの例として、平均滞留時間および最大納期遅れ時間の最小化問題する2目的単一機械スケジューリング問題を取り上げ、加工時間や納期が当初の計画から変わるというシナリオを想定します。　

モデルの前提条件：１、時刻ｔ＝０で着手可能なｎ個のジョブ，，　が一つずつ単一機械で加工され２、段取り時間はジョブの加工順序に依存せず加工時間に含まれ３、ジョブの加工中は他のジャブの割り込みを許さない、４、加工時間と納期は計画後に変わる可能性があり、それをシナリオ、で表します。シナリオにおけるジョブの加工時間を、納期をとする、任意のスケジューリングｓでi番目に加工されるジョブをとすれば、その加工完了時刻は　となり、平均滞留時間と最大納期遅れ時間はそれぞれおよびとなります。これで、シナリオを想定したとの2目的最小化スケジューリング問題は　と定式化される。ただし、である。　シナリオにおける非劣スケジュール集合は＜w－G修正アルゴリズム＞で容易でもとめられます。手順１シナリオ下でSPTおよびEDDでスケジュールを求め、（SPT, ）, （SPT, ）,および（EDD, ）, （EDD, ）を求める手順２　T= （SPT, ）とする。手順３とし、未スケジュールジョブ集合をU＝｛J1，J2，，，，Jn｝とする。手順4　となるジョブをスケジュールのk番目に置く、このようなジョブが複数個存在する場合にはそれらのすべてのケースを例挙する。手順５　U=U/｛｝、　、ｋ＝ｋ－１手順6　ｋ＝１なら、残った未スケジュールジョブをスケジュールの1番目におき、手順4へ戻る。手順７　与えられたスケジュールを非劣スケジュール集合に加える、得られたスケジュールのが（EDD, ）に等しければ終了、それ以外は、T=T－とし、手順3へ戻る、ただし、は十分小さな正数とする。

＜今後で課題＞　　

提案法を使って、数値実験より提案法の有効性を検討していきたい。