JPH09297791A - マンマシン協調型スケジューリング方法 - Google Patents

Abstract

(57)【要約】 【課題】 縦方向にジョブ番号、横方向に複数の日付を
とるマトリクスの各メッシュについて制約条件の下にリ
ソースを割り当てるスケジューリング方法において、既
に作成された解候補をオペレータ介入によって改善す
る。 【解決手段】 デコード部１０３１は、マトリクスの各
メッシュに対応して制約条件を緩和するか否かを示す０
／１コードを格納するコード群１０１１と制約条件１０
２１とを参照して各メッシュにリソースを割り当てて解
候補１０３２を作成し、編集／表示部１０５１がこの解
候補を表示する。解候補の一部を凍結するオペレータの
要求に応じて凍結対象のメッシュと凍結確率を凍結条件
１０２２に格納する。デコード部１０３１は、凍結条件
１０２２を参照して凍結要求メッシュについては設定さ
れた確率で既存の解候補の対応するメッシュの割当リソ
ースを保存し、新しい解候補を作成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、電子計算機を利用
するスケジューリングシステムに係わり、特に並列に実
行される複数のジョブに対してリソースを割り当てると
ともにオペレータの介入によって解の一部を人間が制御
するマンマシン協調型のスケジューリング方法に関する
ものである。

【０００２】

【従来の技術】交通分野における車両の運用計画作成で
は、人工知能（ＡＩ）の技法を応用したシステムが実用
化されている。例えば「高橋、他：車両基地におけるコ
ンピュータ利用，ｐｐ４７−５０，三菱電機技法ｖｏ
ｌ．６１，Ｎｏ．２，１９８７」は、パソコンを利用し
て車両運用管理支援システムを構築している。このシス
テムでは、専門家の知識を利用して全列車の走行キロ数
が均一となるように数日先の運用を考慮して計画を作成
している。また「車両運用計画エキスパートシステム，
ｐｐ２２４，東芝レビューｖｏｌ．４９，Ｎｏ．３，１
９９３」は、車両運用計画の作成だけでなく、留置計画
の自動作成ならびに故障時等に代替可能な車両を自動検
索する機能をサポートしている。

【０００３】

【発明が解決しようとする課題】従来のスケジューリン
グシステムは、解の探索論理にあらかじめ問題固有の探
索知識を組み込んだアプローチが主流であったが、これ
らは計画条件が変化すると実行可能解の探索が困難にな
るなど、保守・拡張性の点で問題があった。

【０００４】またスケジューリングシステムが提案する
解候補に制約違反が残った場合に、制約違反を解消する
のが容易でないという問題があった。

【０００５】本発明の目的は、オペレータがシステムと
協調しながら解の探索を進めることによって上記問題を
解決することにある。

【０００６】

【課題を解決するための手段】本発明は、複数のジョブ
に対して機材や人員等のリソースを割り当てるスケジュ
ーリング方法において、縦軸方向に各ジョブの識別子、
横軸方向に複数の時間帯をとる２次元マトリクスの各メ
ッシュについて制約条件に従ってリソースを割り当てる
ものとし、このマトリクスの各メッシュに対応して制約
条件を緩和するか否かを示す０／１コードを設定し、制
約条件の強さとこの０／１コードとから定まる規則を適
用して各メッシュにリソースを割り当てて解候補を作成
し、解候補が制約条件を充足し評価項目を満足する程度
に応じて評価値を付与し、評価値の高い解候補に対応す
る０／１コードのマトリクスを保存するとともに新たな
０／１コードをもつマトリクスを生成しながら上記ステ
ップを繰り返して複数の解候補を作成するスケジューリ
ング方法を前提とする。

【０００７】本発明は、このようにして作成された解候
補の中からオペレータが選択したターゲット解候補の一
部である複数のメッシュから成る領域について割り当て
るリソースを確率的に凍結するときの凍結確率を設定
し、凍結確率が設定されたメッシュについては設定され
た確率でターゲット解候補の対応するメッシュの割当リ
ソースを保存し、この確率を外れるメッシュか又は凍結
確率が設定されていないメッシュについては制約条件の
強さと該０／１コードとから定まる規則を適用して各メ
ッシュにリソースを割り当てて新しい解候補を作成する
スケジューリング方法を特徴とする。

【０００８】なお割り当てるリソースを確率的に凍結す
るときの凍結確率を設定する代わりに、連続する複数の
時間帯に亘って特定メッシュの間に同一リソースを割り
当てるところのリソースの接続状態を凍結するときの凍
結確率を設定してもよい。

【０００９】

【発明の実施の形態】以下、本発明の一実施形態として
列車ダイヤに対する車両の運用計画の作成問題を例にと
って図面を用いて説明する。

【００１０】鉄道の車両は、定期的に検査を受けること
が法律により義務付けられている。検査には車両を一旦
分解して再度組立てる長期検査や、チェック項目を検査
器で自動検査する短期検査など様々なレベルの検査が存
在する。また検査を受ける頻度も車両の種別毎に異な
り、ある鉄道路線においては動力車は１〜２年に１回の
ペースで長期検査を受け、２〜３ヵ月に１回のペースで
短期検査を受けることが義務づけられている。なお全て
の車両について検査計画があらかじめ作成されている。

【００１１】一般的には列車の運行ダイヤに割り当てら
れる車両は毎日変更される。例えばある路線における車
両の運用形態は、運用１に割り当てられた車両が翌日は
運用２、翌々日は運用３といったようにローテーション
するように配慮されている。車両の運用計画作成問題
は、年間の検査計画と列車ダイヤを制約条件として、１
ヵ月分の運用番号（ジョブ）に車両（リソース）を割り
当てる組み合わせ問題である。

【００１２】図１は、本実施形態の計画立案処理を行う
システムの構成図である。解探索エンジン１０１０は、
コード群１０１１とコード操作部１０１２から構成され
る。コード群１０１１は、縦軸方向にジョブ、横軸方向
に日付が配置される２次元マトリクスの集合であり、各
マトリクスの各メッシュには０か１かのコードが割り当
てられる。入力データ１０２０は、制約条件１０２１、
凍結条件１０２２及び最適化目標１０２３から構成さ
れ、記憶装置上に設定されるデータである。制約条件１
０２１はジョブにリソースを割り当てるときの制約条件
を規定するものであり、接続制約と割当制約から成る。
凍結条件１０２２は、オペレータからの要求に従って２
次元マトリクスの各メッシュについて接続条件又は割当
条件を凍結する条件を設定するものである。制約解消部
１０３０は、デコード部１０３１と解候補１０３２から
構成される。デコード部１０３１は、ジョブ×日付が配
列されるマトリクスの各メッシュにリソースを割り当て
る処理部であり、制約条件１０２１に規定される制約条
件の強さとコード群１０１１上の０／１コードとによっ
て制御されるルールを選択して実行することによってリ
ソースの割り当てを行い、その結果を解候補１０３２に
出力する。またデコード部１０３１は、凍結条件１０２
２に従って凍結条件が設定されたメッシュについてター
ゲット解候補のリソース割当を確率的に凍結する。ここ
でターゲット解候補は、複数の解候補１０３２のうちの
１つであり、あらかじめオペレータによって選択された
作成済の解候補である。最適化目標１０２３は、いくつ
かの評価項目ごとにその評価指標を求める関数と評価項
目の重みを設定するものである。多目的評価部１０４０
は、評価部１０４１と評価データ１０４２から構成され
る。評価部１０４１は、解候補１０３２上の処理結果に
ついて制約条件１０２１と最適化目標１０２３とを参照
して評価を行い、その結果として各解候補に評価値を付
与して評価データ１０４２に出力する処理部である。コ
ード操作部１０１２は、評価データ１０４２及びコード
群１０１１を入力して、評価値の低い解候補に適用した
コード群をコード群１０１１から抹消したり、複数のコ
ード群を合成して新しいコード群を生成するなどの操作
を行い、新しいコード群をコード群１０１１に格納する
処理部である。本実施形態のシステムは、コード操作部
１０１２の処理、デコード部１０３１の処理及び評価部
１０４１の処理を１サイクルの処理とし、このサイクル
を何回か繰り返すことによって計画の最適化を行う。マ
ンマシン部１０５０は、編集／表示部１０５１及びディ
スプレイ１０５２から構成される。編集／表示部１０５
１は、解候補１０３２を入力して、得られた解候補をグ
ラフや表によってディスプレイ１０５２に表示したり、
オペレータが制約条件１０２１、凍結条件１０２２及び
最適化目標１０２３上のデータをインタラクティブに作
成したり変更するよう支援する処理部である。

【００１３】図２は、コード群１０１１のデータ形式を
示す図である。コード群１０１１はｍ個のマトリクスか
ら成り、各マトリクスのＡ，Ｂ，・・・，Ｅは運用番
号、１，２，・・・，ｎは日付である。各メッシュには
０か１がランダムにあるいはコード操作によって生成さ
れ、割り当てられる。マトリクスは制約条件を制御する
テーブルであり、１は制約緩和、０は制約充足を意味す
る。

【００１４】図３は、本実施形態のシステムの処理の流
れの概略を示すフローチャートである。編集／表示部１
０５１は、オペレータからの入力データに従って制約条
件１０２１及び最適化目標１０２３を設定する（ステッ
プ２０１０）。次にコード操作部１０１２は、コード群
１０１１の初期化を行う（ステップ２０２０）。初期状
態では、コード操作部１０１２はランダムに異なる０／
１パターンをもつマトリクスをｍ個作成する。次にデコ
ード部１０３１は、制約条件１０２１とコード群１０１
１に従って運用マトリクスの各メッシュにリソースを割
り付け（ステップ２０３０）、得られたマトリクスを解
候補１０３２に格納する（ステップ２０４０）。次に評
価部１０４１は、制約条件１０２１及び最適化目標１０
２３を参照して登録された解候補１０３２の評価を行い
（ステップ２０５０）その結果を評価データ１０４２に
格納する。次に探索終了条件を満足するかどうかを判定
する（ステップ２０６０）。探索終了条件とは、所定値
以上の評価値を得た解候補が出現した場合や探索サイク
ルが所定回数に達した場合などである。探索終了条件を
満足せず処理を続行するとき（ステップ２０６０続
行）、コード操作部１０１２は評価データ１０４２を参
照して評価値の高い解候補１０３２に対応するコード群
１０１１中のマトリクスを優先的に保存し、評価値の低
いマトリクスを確率的に抹消したり新しいコード群のマ
トリクスを生成するなどのコード操作を行って（ステッ
プ２０７０）、ステップ２０３０に戻る。一方探索終了
条件を満足し処理を終了するとき（ステップ２０６０終
了）、編集／表示部１０５１は評価データ１０４２を参
照して解候補１０３２の中で最も評価値の高い解候補を
ディスプレイ１０５２に表示する（ステップ２０８
０）。また編集／表示部１０５１は、オペレータの要求
によって解候補１０３２中の解候補とその評価値をディ
スプレイ１０５２に表示する。オペレータは表示された
解候補を参照して評価値の低い解候補を解候補１０３２
から削除したり、制約条件１０２１や最適化目標１０２
３を変更したり、凍結条件１０２２を設定することがで
きる。凍結条件１０２２を設定するときには、オペレー
タは解候補１０３２のうちの１つをターゲット解候補と
して指定する。このようにしてオペレータが処理の続行
を指示したとき（ステップ２０９０続行）、ステップ２
０１０に戻って上記処理を繰り返す。凍結条件１０２２
が設定されたとき、デコード部１０３１は凍結条件１０
２２に従って凍結条件が設定されたメッシュについてタ
ーゲット解候補のリソース割当を確率的に凍結する。オ
ペレータが表示された解候補を承認したとき（ステップ
２０９０承認）、編集／表示部１０５１はこの解候補を
正式な解として登録したり、図示しないプリンタ上に印
刷して（ステップ２１００）、計画立案処理を終了す
る。

【００１５】図４は、デコード部１０３１の処理の流れ
を示すフローチャートである。デコード部１０３１は、
コード操作部１０１２が生成するコード群１０１１のマ
トリクスに対応して複数の運用マトリクスを作成するも
のとし、処理中のマトリクスを指すポインタを初期化し
（ステップ４０１０）、処理中のマトリクスについて日
付ポインタを初期化する（ステップ４０２０）。次に現
在の日付についてリソース割当の対象とするメッシュを
選択し（ステップ４０３０）、選択したメッシュにリソ
ースを割り当てる（ステップ４０４０）。現在の日付に
ついて未割当メッシュが存在する場合（ステップ４０５
０有）には、ステップ４０３０に戻って上記処理を繰り
返す。未割当メッシュが存在しない場合（ステップ４０
５０無）には、日付ポインタを更新する（ステップ４０
６０）。日付ポインタが上限を越えていないとき続行と
し（ステップ４０７０続行）、ステップ４０３０に戻っ
て上記処理を繰り返す。日付ポインタが上限を越えてい
るとき、当該マトリクスについての処理を終了とし（ス
テップ４０７０終了）、処理中のマトリクスを指すポイ
ンタを更新する（ステップ４０８０）。マトリクスポイ
ンタが所定値を越えていなければ続行とし（ステップ４
０９０続行）、ステップ４０２０に戻って次のマトリク
スについて上記処理を繰り返す。マトリクスポインタが
所定値を越えているとき（ステップ４０９０終了）、デ
コード部１０３１の処理を終了する。

【００１６】制約条件１０２１は、運用計画の種々の制
約を登録するテーブルであり、接続制約を規定するテー
ブルと割当制約を規定するテーブルから構成される。図
５は、接続制約を規定するテーブルの例を示す図であ
る。縦軸Ａ〜Ｅは運用番号を表し、横軸１〜ｎは日付を
表す。接続制約は運用番号×日付で指定される特定メッ
シュの間の同一リソースの割り当てを規定する制約であ
る。各メッシュには複数の接続制約を登録することが可
能であり、図５の例では、メッシュ８０１０について登
録された接続制約の内容８０２０は、 （１）当メッシュには、前日に運行Ａに割り当てた同じ
リソースを割り当てなければならない（必須かつ肯
定）。 （２）当メッシュには、前日に運行Ｂに割り当てた同じ
リソースを割り当ててはならない（必須かつ否定）。 （３）当メッシュには、前日に運行Ｃに割り当てた同じ
リソースを割り当てたい（目標かつ肯定）。 （４）当メッシュには、前日に運行Ｄに割り当てた同じ
リソースを割り当てたくない（目標かつ否定）。を意味
する。

【００１７】図６は、割当制約を規定するテーブルの例
を示す図である。接続制約と同じ様に縦軸Ａ〜Ｅは運用
番号を表し、横軸１〜ｎは日付を表す。割当制約は、運
用番号×日付で指定される特定のメッシュへの特定のリ
ソースの割り当てを規定する制約である。各メッシュに
は、複数の割当制約を登録可能であり、図６の例では、
メッシュ９０１０に登録された割当制約の内容９０３０
は、 （１）当メッシュには、リソースＲ１を割り当てなけれ
ばならない。 （２）当メッシュには、リソースＲ２を割り当ててはな
らない。 （３）当メッシュには、リソースＲ３を割り当てたい。 （４）当メッシュには、リソースＲ４を割り当てたくな
い。 を意味し、同様にメッシュ９０２０に登録された割当制
約の内容９０４０は、 （１）当メッシュには、客車に属するリソースを割り当
ててはならない。 （２）当メッシュには、動力車に属するリソースを割り
当てたい。 を意味する。このようにリソースの識別子を直接指定し
たり、リソースの属性を用いて特定の属性に含まれる複
数のリソースを一括して指定する。

【００１８】凍結条件１０２２は、ターゲット解候補の
一部を確率的に凍結するためのテーブルであり、接続凍
結テーブルと割当凍結テーブルから構成される。図７
（ａ）は、接続凍結テーブルの例を示す図である。接続
凍結テーブルは、解をマトリクスの各メッシュに配置さ
れたリソースとし、同一リソースを接続したときの同一
リソース間の接続の状態を確率的に凍結するためのテー
ブルである。図７（ａ）の例ではＢ−２のメッシュとＣ
−２のメッシュについて同一リソースの接続状態を凍結
する。例えばＣ−２のメッシュには凍結強度６０１０と
して０．９５の凍結確率を与える。凍結確率は０〜１の
数字で表現される。凍結確率０は凍結しないことに等し
い。図７（ｂ）は、ディスプレイ１０５２に表示される
車両運用グラフであり、同一車両を直線で接続して示し
たグラフである。オペレータがいくつかの車両を含む矩
形領域を指示すると、その領域に含まれる車両の接続状
態が凍結される。凍結確率は入力データとして与えられ
る。図７（ｂ）の例では、図７（ａ）の例に対応して結
果としてＢ−２のメッシュとＣ−２のメッシュについて
接続状態が凍結される。なお各メッシュでなく矩形領域
全体に対して凍結確率を付与してもよい。

【００１９】図８は、割当凍結テーブルの例を示す図で
ある。割当凍結テーブルは、各メッシュについてリソー
スの割当状態を確率的に凍結するためのテーブルであ
る。図８（ａ）の例では網目表示したメッシュについて
割当状態を凍結する。例えばＣ−２のメッシュには凍結
強度７０１０として１．０の凍結確率を与える。図８
（ｂ）は、ディスプレイ１０５２に表示される車両運用
グラフである。オペレータがいくつかの車両を含む矩形
領域を指示すると、その領域に含まれる車両の割当状態
が凍結される。凍結確率は入力データとして与えられ
る。図８（ｂ）の例では、図８（ａ）の例に対応して網
目表示した車両の割当状態が凍結される。なお各メッシ
ュでなく矩形領域全体に対して凍結確率を付与してもよ
い。

【００２０】図９は、ステップ４０３０のリソース割当
の対象とするメッシュを選択する処理を展開して示すフ
ローチャートである。デコード部１０３１は、凍結条件
１０２２を参照して現在のマトリクス及び現在の日付に
ついて未割当メッシュであってかつ凍結要求をしている
メッシュがあるかどうか判定する（ステップ５０１
０）。未割当かつ凍結要求メッシュがある場合（ステッ
プ５０１０あり）には、未割当メッシュの中で登録され
ている凍結強度が最も大きいメッシュを１つ選択する
（ステップ５０２０）。すなわち接続凍結テーブルと割
当凍結テーブルの両方について凍結強度が最大のメッシ
ュを選択するとともにいずれのテーブルを適用するか凍
結モードを決定する。未割当かつ凍結要求メッシュが見
当らない場合（ステップ５０１０なし）には、制約条件
１０２１を参照して未割当メッシュの中で制約強度が最
も大きいメッシュを１つ選択する（ステップ５０３
０）。制約強度の大きさの順は、制約条件が（１）必須
かつ肯定、（２）必須かつ否定、（３）目標かつ肯定、
（４）目標かつ否定、（５）制約なしの順である。

【００２１】図１０は、デコードルール１２０１０と、
このルールから起動される制約充足デコード手続き１２
０２０及び制約緩和デコード手続き１２０３０の事例を
示す図である。デコードルール１２０１０、制約充足デ
コード手続き１２０２０及び制約緩和デコード手続き１
２０３０は、図示しない記憶装置上に格納される。デコ
ードルール１２０１０は、制約強度と０／１コードとに
対応していずれかのルールを選択する規則を規定する。
制約充足デコード手続き１２０２０は、制約条件を充足
するような手続きを記述する。制約緩和デコード手続き
１２０３０は、制約条件を緩和するような手続きを記述
する。

【００２２】図１１は、ターゲット解候補の事例を示す
図である。解候補は運用番号×日付が配列されるマトリ
クスの各メッシュにリソースとしての車両を割り当てた
運用マトリクスである。解候補は常に複数個存在し、そ
のうちターゲットポインタ１１０１０で指示された解候
補がターゲット解候補である。オペレータは、ターゲッ
トポインタ１１０１０を指定することにより、複数の解
候補の中から１つのターゲット解候補を選択し、ディス
プレイ１０５２に表示されたターゲット解候補について
凍結要求をすることができる。

【００２３】図１２は、ステップ４０４０の割当リソー
スを選択する処理を展開して示すフローチャートであ
る。デコード部１０３１は、選択したメッシュが凍結要
求メッシュか否かを判定する（ステップ１００１０）。
凍結要求メッシュでなければ（ステップ１００１０Ｎ
Ｏ）、当該メッシュについて対応する制約強度とコード
群１０１１の０／１コードを取得し（ステップ１００８
０）、デコードルール１２０１０、制約充足デコード手
続き１２０２０及び制約緩和デコード手続き１２０３０
を参照し、デコードルールを実行してリソースの割当を
行う（ステップ１００９０）。凍結要求メッシュであれ
ば（ステップ１００１０ＹＥＳ）、ステップ５０２０で
決定した凍結強度Ｘを取得し（ステップ１００１５）、
０〜１の範囲の乱数を発生させる（ステップ１００２
０）。次に乱数Ｒと凍結強度Ｘとを比較し（ステップ１
００３０）、Ｒ≧Ｘであれば（ステップ１００３０
≧）、ステップ１００８０及び１００９０を実行する。
Ｒ＜Ｘであれば（ステップ１００３０＜）、凍結モード
が割当凍結の場合（ステップ１００４０割当）には、タ
ーゲット解候補の対応するメッシュを参照し（ステップ
１００５０）、その割当リソースを当該メッシュにコピ
ーすることによってリソース割当を行う（ステップ１０
０７０）。凍結モードが接続凍結の場合（ステップ１０
０４０接続）には、ターゲット解候補の対応するメッシ
ュに割り当てられているリソースと前日の同一リソース
を割り当てている運用番号を参照し（ステップ１００６
０）、同じ接続関係を保存するように現在作成中の解候
補の前日の同一運用番号の割当リソースを当該メッシュ
にコピーすることによってリソース割当を行う（ステッ
プ１００７０）。

【００２４】図１３は、最適化目標１０２３の例を示す
図である。最適化目標１０２３は、各評価項目について
評価を実行する関数の名称及び評価の結果として得られ
た評価指標に対する重みを設定する。

【００２５】図１４は、評価部１０４１の処理の流れを
示すフローチャートである。評価部１０４１は、現在評
価中の解候補を指すマトリクスポインタを初期化し（ス
テップ１３０１０）、評価値の基準値を初期化する（ス
テップ１３０２０）。例えば評価結果の最高得点を１０
００点満点とすれば、初期値として１０００を設定す
る。次にペナルティを初期化する（ステップ１３０３
０）。ペナルティは違反点数であるので、初期値として
０を設定する。次にマトリクスポインタによって指定さ
れる解候補１０３２を読み込んで（ステップ１３０４
０）、制約条件１０２１を参照して制約違反のチェック
を行う（ステップ１３０５０）。その結果として違反点
数が算出される。違反点数は必須制約違反を大きくし、
目標制約違反を小さくする。次に解候補が全体としてど
の程度最適化目標を充足しているかをチェックする（ス
テップ１３０６０）。評価部１０４１は最適化目標１０
２３を参照して各評価項目ごとに評価関数を実行する。
評価関数は解候補を入力データとし、評価指標をペナル
ティとして出力する。各評価項目の評価指標に重みを掛
けてすべての評価項目について累計した結果が最適化目
標についてのペナルティである。次に評価の基準値から
制約違反のペナルティと最適化目標のペナルティとを減
算して評価値を得る（ステップ１３０７０）。次に得ら
れた評価値を解候補の識別子と対応させて評価データ１
０４２に書き込む（ステップ１３０８０）。次にマトリ
クスポインタを更新する（ステップ１３０９０）。マト
リクスポインタが所定値を越えていなければ続行とし
（ステップ１３１００続行）、ステップ１３０２０に戻
って次の解候補について上記処理を繰り返す。マトリク
スポインタが所定値を越えているとき（ステップ１３１
００終了）、評価部１０４１の処理を終了する。

【００２６】図１５は、ステップ１３０５０の制約チェ
ックの処理を展開して示すフローチャートである。まず
評価部１０４１は、日付ポインタを初期化する（ステッ
プ１４０１０）。次に制約条件１０２１の接続制約を参
照して該当日付の接続制約の制約違反チェックを行い
（ステップ１４０２０）、制約違反が存在する場合（ス
テップ１４０３０有り）にはペナルティとして違反点数
を加算する（ステップ１４０４０）。また制約違反をし
た解候補１０３２上のマトリクスのメッシュに必須制約
違反か目標制約違反かを区別するマークを記憶する。次
に制約条件１０２１の割当制約を参照して該当日付の割
当制約の制約違反チェックを行い（ステップ１４０５
０）、制約違反が存在する場合（ステップ１４０６０有
り）には、ペナルティとして違反点数を加算する（ステ
ップ１４０７０）。また制約違反をした解候補１０３２
上のマトリクスのメッシュに必須制約違反か目標制約違
反かを区別するマークを記憶する。次に日付ポインタを
更新する（ステップ１４０８０）。日付が上限値を越え
ていなければ処理続行とし（ステップ１４０９０続
行）、ステップ１４０２０に戻って上記処理を繰り返
す。日付が上限値を越えたとき、制約チェック処理を終
了する（ステップ１４０９０終了）。

【００２７】コード操作部１０１２は、評価データ１０
４２を参照し、解候補１０３２に対応する評価値の高い
コード群１０１１中のマトリクスを優先的に保存し、評
価値の低いマトリクスはマトリクスの確率的な抹消（自
然淘汰）、２つのマトリクスの合成による新しいコード
群の生成（交叉）、０／１コードパタンの確率的な反転
（突然変異）を行って、新たな０／１コードの組み合わ
せをもつマトリクスを生成する。自然淘汰は常にｍ個の
マトリクスを保存するように、保存されているマトリク
ス及び追加されたマトリクスのうちから評価値の低いマ
トリクスを抹消することである。交叉は２つの親となる
マトリクスの同一メッシュにある０／１コードを合成規
則に基づいて合成し、合成されたコードを子の同一メッ
シュに設定する方法である。一例として合成する２つの
親の同一メッシュのコードが同一ならば子の同一メッシ
ュのコードも同じものを継承させ、親のコードが異なる
場合には確率Ｐに応じて子のコードを決定する。ここで
確率Ｐは、子のコードの非０要素比率が評価値の高い親
の非０要素比率と同一になるように動的に定められる。
一般に遺伝的アルゴリズムにおける突然変異オペレーシ
ョンの目的は解探索が局所解に陥るのを防ぐことであ
る。突然変異オペレーションは、ある突然変異率Ｐによ
り０／１コードを反転させる処理である。

【００２８】マンマシン部１０５０の編集／表示部１０
５１は、解候補１０３２及び評価データ１０４２を入力
して得られた解候補をグラフや表によつて表示する。ま
た編集／表示部１０５１は、制約条件１０２１、凍結条
件１０２２及び最適化目標１０２３の内容の変更を支援
する。

【００２９】凍結条件１０２２を設定するときには、編
集／表示部１０５１は解候補１０３２内の解候補をディ
スプレイ１０５２上に表示する。オペレータがターゲッ
ト解候補を選択したとき、編集／表示部１０５１は選択
された解候補を指すようにターゲットポインタ１１０１
０を設定する。次にオペレータが接続凍結と割当凍結の
いずれかを指示し、マウスのような入力装置を介して図
７（ｂ）及び図８（ｂ）に示すようにいくつかの車両を
含む矩形領域を指示すると、編集／表示部１０５１は凍
結強度を入力する必要のあるメッシュを決定する。接続
凍結の場合には、編集／表示部１０５１は指定された矩
形領域の２番目の日付にポインタを設定する。当該日付
の中で同一リソースがこの矩形領域の範囲内の前日の領
域内にあれば接続凍結の対象となるメッシュ、なければ
接続凍結の対象とならないメッシュである。このように
して当該日付の中で凍結強度を入力する必要のあるメッ
シュを選択して強調表示する。当該日付についてメッシ
ュの選択を終了したら矩形領域の３番目の日付にポイン
タを更新して上記の処理を繰り返す。このようにして矩
形領域の最後の日付まで上記処理を繰り返す。凍結強度
を入力するメッシュが決定したら、編集／表示部１０５
１は各メッシュを１つ１つ順に強調表示してオペレータ
に凍結強度の入力を促す。編集／表示部１０５１が凍結
強度の選択枝をいくつか列挙するメニューを表示し、前
のメッシュについて選択された選択枝をそのまま入力
し、選択枝を変更するときのみ改めて選択し直すように
すると操作性が良い。割当凍結の場合には、指定された
矩形領域内でリソースが割り当てられているすべてのメ
ッシュが割当凍結の対象となるメッシュであり、凍結強
度を入力する必要がある。このようにして凍結の対象と
するメッシュと凍結強度が決まったとき、編集／表示部
１０５１は接続凍結テーブル又は割当凍結テーブルを作
成して凍結条件１０２２として登録する。

【００３０】図１６（ａ）は、解候補１０３２を表で示
す車両運用表である。Ｒ０１，Ｒ０２・・・は車両の識
別子である。図１１（ｂ）は車両運用グラフであり、同
一車両を直線で接続して示したグラフである。

【００３１】図１７は、車両運用グラフであるが、制約
違反したリソースの割り付けを強調表示している。黒丸
は必須制約違反、斜線を引いた丸は目標制約違反をした
リソース割り付けを示す。グラフの縦軸方向の項目は運
用番号である。

【００３２】図１８は、車両運用表であるが、縦軸方向
に車両の識別子をとり、横軸方向に日付をとり、各メッ
シュに運用番号を表示するものである。この表において
も必須制約違反及び目標制約違反したリソース割り付け
を表示色によって強調表示することができる。

【００３３】図１９は、各評価項目の評価指標の充足度
を正規化して示すレーダチャートである。Ａ，Ｂ，Ｃ，
Ｄは評価項目である。オペレータは、このレーダチャー
トのＡ，Ｂ，Ｃ，Ｄいずれかの値を変更することによっ
て各評価指標の重みを変更することが可能である。

【００３４】上記実施形態では、オペレータが割当凍結
を設定するとき、図８（ｂ）に示すように縦軸方向に運
用番号をとり、横軸方向に日付をとった車両運用表に基
づいて設定した。しかし図１８に示すように縦軸方向に
車両の識別子をとり、横軸方向に日付をとった車両運用
表について矩形領域を指定して割当凍結することも可能
である。編集／表示部１０５１は、割当凍結されたメッ
シュについてその車両の識別子と運用番号との対応を保
存するように前者の車両運用表の形式に変換した割当凍
結テーブルを作成して凍結条件１０２２に登録する。ま
たオペレータの指示があれば、編集／表示部１０５１は
前者の形式の車両運用表を後者の形式の車両運用表に変
換してディスプレイ１０５２に表示する。また後者の形
式の車両運用表を前者の形式の車両運用表に変換してデ
ィスプレイ１０５２に表示する。

【００３５】上記実施形態によれば、得られた解候補に
必須の制約違反がある場合に車両運用表上で制約違反の
ない領域を凍結できるので、解の探索空間が広くならな
いように制限することができる。このときこの領域を確
率的に凍結するために探索空間が極端に制限されること
を防止し、制約違反を解消するような解を探る余地を残
すものである。従って制約違反のない領域を例えば凍結
強度１．０で凍結して制約違反が解消しない場合に、オ
ペレータは凍結強度を下げることによって探索空間をあ
る程度制限しつつ制約違反が解消する道を探ることがで
きる。そして割当凍結よりも接続凍結の方が探索空間に
対する制限が緩いことが理解される。

【００３６】以上の実施形態は、車両運用計画を例にと
って説明したが、本発明は各ジョブが並列に実行できる
ような条件付リソース割当てアプリケーションであれば
他のアプリケーションにも適用される。ここでリソース
とは、機材、人員等である。一般に２次元マトリクスの
縦軸方向に各ジョブの識別子、横軸方向に複数の時間帯
（時間、日、週、月など）がとられる。

【００３７】

【発明の効果】本発明によれば、ターゲット解候補の一
部を確率的に凍結できるので、解を求めるための探索空
間をある程度制限しながら解候補に残存する制約違反を
解消することができ、マンマシン協調によるスケジュー
リングの効果を発揮することができる。

【図面の簡単な説明】

【図１】実施形態の計画立案処理を行うシステムの構成
図である。

【図２】実施形態のコード群１０１１のデータ形式を示
す図である。

【図３】実施形態の全体の処理の流れを示すフローチャ
ートである。

【図４】実施形態のデコード部１０３１の処理の流れを
示すフローチャートである。

【図５】接続制約を規定するテーブルの例を示す図であ
る。

【図６】割当制約を規定するテーブルの例を示す図であ
る。

【図７】接続凍結テーブルの例と領域の指示方法の例を
示す図である。

【図８】割当凍結テーブルの例と領域の指示方法の例を
示す図である。

【図９】実施形態のステップ４０４０の処理の詳細を示
すフローチャートである。

【図１０】デコードルールとそれを適用する手続きの例
を示す図である。

【図１１】ターゲット解候補の事例を示す図である。

【図１２】ステップ４０４０の処理の詳細を示すフロー
チャートである。

【図１３】実施形態の最適化目標１０２３のデータ形式
を示す図である。

【図１４】実施形態の評価部１０４１の処理の流れを示
すフローチャートである。

【図１５】実施形態のステップ１３０５０の制約チェッ
ク処理の詳細を示すフローチャートである。

【図１６】実施形態の車両運用表及び車両運用グラフを
示す図である。

【図１７】実施形態の制約違反を強調表示する車両運用
グラフを示す図である。

【図１８】実施形態の他の車両運用表を示す図である。

【図１９】実施形態の各評価項目の評価指標の充足度を
示すレーダチャートである。

【符号の説明】

１０２１・・・制約条件、１０２２・・・凍結条件、１
０３１・・・デコード部、１０３２・・・解候補、１０
５１・・・編集／表示部

Claims (6)

【特許請求の範囲】
1. 【請求項１】複数のジョブに対して機材や人員等のリソ
   ースを割り当てるスケジューリング方法において、縦軸
   方向に各ジョブの識別子、横軸方向に複数の時間帯をと
   る２次元マトリクスの各メッシュについて制約条件に従
   ってリソースを割り当てるものとし、 該制約条件を記憶装置上に設定するステップと、 オペレータの要求に応じて、過去に得られた解候補（タ
   ーゲット解候補）の一部である複数のメッシュから成る
   領域について割り当てるリソースを確率的に凍結すると
   きの凍結確率を記憶装置上に設定するステップと、 該マトリクスの各メッシュに対応して制約条件を緩和す
   るか否かを示す０／１コードを記憶装置上に設定するス
   テップと、 該凍結確率が設定されたメッシュについては設定された
   確率で該ターゲット解候補の対応するメッシュの割当リ
   ソースを保存し、該確率を外れるメッシュか又は該凍結
   確率が設定されていないメッシュについては制約条件の
   強さと該０／１コードとから定まる規則を適用して各メ
   ッシュにリソースを割り当てて新しい解候補を作成する
   ステップと、 該解候補が制約条件を充足し、評価項目を満足する程度
   に応じて評価値を付与するステップとを有することを特
   徴とするマンマシン協調型スケジューリング方法。
2. 【請求項２】割り当てるリソースを確率的に凍結すると
   きの凍結確率を設定する代わりに、連続する複数の時間
   帯に亘って特定メッシュの間に同一リソースを割り当て
   るところのリソースの接続状態を凍結するときの凍結確
   率を設定することを特徴とする請求項１記載のマンマシ
   ン協調型スケジューリング方法。
3. 【請求項３】該ターゲット解候補のマトリクスを表示装
   置上に表示し、オペレータが該ターゲット解候補上で複
   数のメッシュを含む矩形領域と凍結確率を指定する要求
   に応答して該矩形領域に含まれるメッシュと該凍結確率
   を凍結テーブルとして保存することを特徴とする請求項
   １記載のマンマシン協調型スケジューリング方法。
4. 【請求項４】縦軸方向に各ジョブの識別子、横軸方向に
   複数の時間帯をとる第１の形式のターゲット解候補を縦
   軸方向に各リソースの識別子、横軸方向に複数の時間帯
   をとる第２の形式のターゲット解候補に変換して表示装
   置上に表示し、オペレータが指定した複数のメッシュを
   含む矩形領域についてジョブ×時間帯とリソースとの対
   応を保存して第１の形式の凍結テーブルに変換して保存
   することを特徴とする請求項３記載のマンマシン協調型
   スケジューリング方法。
5. 【請求項５】該ターゲット解候補のマトリクスを表示装
   置上に表示し、オペレータが該ターゲット解候補上で複
   数のメッシュを含む矩形領域と凍結確率を指定する要求
   に応答して該矩形領域に含まれるメッシュについて該リ
   ソースの接続状態をチェックして凍結の対象となるメッ
   シュを決定し、凍結対象となるメッシュと凍結確率を凍
   結テーブルとして保存することを特徴とする請求項２記
   載のマンマシン協調型スケジューリング方法。
6. 【請求項６】該スケジューリングは、車両の運用計画で
   あり、該ジョブの識別子は運用番号であり、該リソース
   は車両であることを特徴とする請求項１又は２記載のマ
   ンマシン協調型スケジューリング方法。