JPH10293784A

JPH10293784A - スケジューリング方法及び装置

Info

Publication number: JPH10293784A
Application number: JP10132497A
Authority: JP
Inventors: Tatsuhiro Sato; 達広佐藤; Toshihiro Eguchi; 俊宏江口; Tomohiro Murata; 智洋村田
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1997-04-18
Filing date: 1997-04-18
Publication date: 1998-11-04

Abstract

(57)【要約】【課題】計画条件・計画目標の変化に対して柔軟な解作
成をする生産・交通スケジューリングシステムを提供す
ることである。【解決手段】ステップ０１０３において、操作手順に関
する制約０１０２を生成し、操作の資源割当の組合せを
確率的に調整するステップ０１０６と、操作の必要資源
の時間的競合を解消してスケジュールの解候補を作成す
るステップ０１０７と、作成された解候補を評価して評
価値を算出するステップ０１０８と、算出された評価値
を上記の資源割当の確率的調整ステップ０１０６にフィ
ードバックするステップ０１０９を繰り返してスケジュ
ールの最適解探索処理を行うステップ０１０５でスケジ
ュールを表す解０１１３を作成し、解の表示とオペレー
タによる編集ステップ０１１４で解の表示と出力とデー
タ修正と解探索の再実行の指示をおこなう。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、生産、交通分野に
おけるスケジューリング業務を計算機で支援する方法及
び装置に関するものであり、具体的には計算機を利用し
た計画の立案方法、立案結果の表示方法、立案結果の修
正方法、立案結果の検証方法に関する。

【０００２】

【従来の技術】確率的探索技法を用いたスケジューリン
グ方法に関しては、（１）「ジョブショップスケジュー
リング問題解決方式」（特開平５−２２５２０３）に記
載されているとおり、あらかじめ使用資源が与えられた
いくつかの作業を含む複数の作業が与えられた場合に、
同じ資源を共有する作業間の実行順序を決定することを
スケジューリングと捉え、その解探索を遺伝的アルゴリ
ズム（ＧＡ）により実現する手法が知られている。

【０００３】また、交通分野における車両入換計画作成
方法に関しては、（２）「入換トータルシステム」（安
斎他：鉄道と電気技術，Ｖol．６，Ｎo．２，１９９
５）に記載されているとおり、車両入換計画作成のノウ
ハウを抽出したものをＡＩのルールとして取り込み計画
作成に反映させる手法が知られている。

【０００４】

【発明が解決しようとする課題】上記従来例（１）にお
いては、使用資源の時間的競合を解消して作業に実行順
序をつけることをスケジューリングと捉えＧＡにより解
探索を行なうが、作業の使用資源の割当は計画作成者が
手作業により与える必要がある。さらに、作成した解を
評価した結果、それが計画作成者の意図を十分に反映し
た解ではない、もしくは実行可能な順序をつけることが
不可能である場合には、その内容に応じて資源割当の組
合せを変更することが必要となることがあるが、上記従
来例においては、解の評価の度合を資源の割当に反映さ
せることができないという問題点があった。また、上記
従来例（１）においては、作業を実行するために必要と
される補助的な処理はスケジューリング対象ではないた
め、作成されたスケジュールが作業の実行順序について
は正しくても補助的処理の実行可能性が保証されていな
いために、実際には実行不可能であるという問題点もあ
った。

【０００５】上記従来例（２）においては、特定の鉄道
車両基地における車両入換計画を、車両基地に固有の計
画条件や計画目標を組み込んだ探索論理により作成をお
こうなうため、それらが変化した場合に実行可能解の探
索が困難になる、他の車両基地の車両入換計画作成に適
用することができない、というスケジューリングシステ
ムの保守・開発上の点で問題点があった。

【０００６】本発明の目的は、作業と作業の実行に必要
な補助的な処理を操作として同一視し、生産・交通スケ
ジューリング問題を、仕事の完了に必要な操作の手順と
各操作の使用資源と各操作の処理時刻（実行順序）を決
定することであると捉え、確率的探索技法の中で操作に
資源割当を生成・調整する手法と操作の使用資源の時間
的競合を解消する手法を融合することにより、計画条件
・計画目標の変化に対して柔軟な解作成をおこなう生産
・交通スケジューリングシステムを提供することにあ
る。

【０００７】

【課題を解決するための手段】上記目的は、入力された
仕事データから操作手順に関する制約を生成するステッ
プにおいて、操作種類を示す節点を連結する有向ネット
ワーク構造を持つ操作手順に関する制約を生成し、操作
の資源割当の組合せを確率的に調整するステップにおい
て、操作手順に関する制約の各節点の資源の割当状況を
全ての仕事について示す染色体を解探索パラメータに設
定された個数だけ生成・調整し、操作の必要資源の時間
的競合を解消してスケジュールの解候補を作成するステ
ップにおいて、操作手順に関する制約と染色体から初期
解を作成し、初期解の中の使用資源を競合する操作のど
ちらか一方を、作業操作間に設定された作業に関する制
約を充足させつつ時間後方にずらすことにより競合を解
消して解候補を作成し、得られたスケジュールの解候補
を評価して評価値を算出するステップにおいて、所定の
制約条件から作成された解評価項目の充足の程度に応じ
て解候補の各々の評価値を算出し、評価値を上記の資源
割当の確率的調整ステップにフィードバックするステッ
プにおいて、解候補を作成する際に使用した染色体デー
タに算出した評価値を与え、スケジュール候補の最適解
探索処理を（１）資源割当の組合せを確率的に調整する
ステップ、（２）操作の必要資源の時間的競合を解消し
てスケジュールの解候補を作成するステップ、（３）解
候補を評価して評価値を算出するステップ、（４）評価
値を資源割当の確率的調整ステップにフィードバックす
るステップ、を繰り返すことによりおこない、最適化の
結果得られたスケジュールの解を表示してオペレータが
操作するステップにおいて、仕事データ、資源に関する
制約、解探索パラメータ、作業の順序に関する制約、解
評価項目を修正し、解探索の再実行を指示することで達
成される。

【０００８】

【発明の実施の形態】以下、本発明に係るスケジューリ
ング方法及び装置の一実施例として、鉄道車両基地にお
ける車両入換計画作成システムについて説明する。

【０００９】本実施例は、鉄道車両基地における車両運
用計画業務を支援するシステムであり、車両基地に入区
する全ての車両（以下編成と呼ぶ）があらかじめ定めら
れた出区時刻までの間に所定の清掃・点検・修理等の作
業が受けられるように、車両基地内での編成の転線スケ
ジュールを作成するものである。

【００１０】図１は本発明の基本構成を示す図である。
実施例の詳細な説明をはじめる前に、図１を用いて本発
明の概要を説明する。

【００１１】本発明により実現されるスケジューリング
方法・装置は、仕事のスケジュールを作成するために利
用される。ここで仕事とは、ある目的を達成するための
一連の作業のまとまりのことであり、仕事の開始時刻と
終了時刻はあらかじめ決められているものとする。仕事
の目的は本発明の実施例が対象とする具体的なスケジュ
ーリング問題により様々に異なる。生産工場における製
品の加工スケジュール作成問題を例にとると、原料を決
められた加工工程により処理して特定の製品を作ること
が一個の仕事にあたる。また、この場合には仕事の開始
時刻は原料の投入可能時刻、終了時刻は製品の納期、作
業は加工工程における各工程にそれぞれ該当する。仕事
データ０１０１は、複数の仕事に関するそれぞれの開始
時刻、終了時刻、必要とする作業に関する情報を少なく
とも含んでいる。本発明により実現されるスケジューリ
ング方法・装置はこの仕事データを処理し、複数の計画
条件やユーザ要求を高いレベルで満足する各仕事の実行
可能な「操作系列（シーケンス）」を作成する。操作と
は、スケジューリング対象においてそれ以上分割するこ
とのないなんらかの処理のことである。仕事における作
業も操作の一種である。また、作業をおこなうために必
要な補助的な処理も操作に該当する。上記の生産工場に
おける製品の加工スケジュール作成問題に関しては、各
工程間で加工途中の半製品を受け渡す処理、半製品を次
の工程の開始時刻まで貯蔵する処理、工程開始のための
段取り処理等がこれにあたる。操作は、少なくとも実行
の開始時刻、終了時刻、使用資源の３点を定義すること
により具体化される。使用資源は、原料、加工や搬送の
ための機械、機械を動かす人間、貯蔵スペースや搬送経
路等、操作を実行するために必要とされる物質的・人的
・空間的な対象であり、各操作種類ごとの利用可能な資
源の情報は資源に関する制約０１０２の中で定義され
る。また、例えばある工程間の半製品の搬送経路が、前
工程と後工程で使用される機械の物理的配置によって制
約を受けることがあるように、実行可能なスケジュール
を生成するために資源間の関係を利用することが必要と
なる場合がある。このような資源間の関係情報も資源に
関する制約に含まれる。

【００１２】仕事の操作系列は、ある仕事を完了するた
めに必要な操作の一連の流れであり、この流れに沿って
操作を順番に実行することにより仕事を支障なく完了す
ることが可能となる。以降では、仕事のスケジュール、
もしくはスケジューリング問題の解と記述した場合、そ
れらは仕事の操作系列を意味するものとする。

【００１３】本発明により実現されるスケジューリング
方法・装置は、仕事データを入力として受取った後に、
ステップ０１０３において操作手順に関する制約０１０
４を生成する。操作手順に関する制約とは、与えられた
仕事を完了するために必要な操作の種類と、それら複数
の操作同士のつながりを規定する情報である。補助的な
処理を一切考慮する必要のない単純なスケジューリング
問題の場合、操作手順に関する制約は、図２（ａ）に示
すように仕事に含まれる作業の種類を実行順に並べた単
純なリストになる。しかしながら、作業間の補助的な処
理は各仕事ごとに厳密に定義される作業とは異なり、例
えば工程間の半製品の受け渡しの経路や方法が異なって
いても完成する製品は同じであるように、同じ結果をも
たらす処理が複数存在し、それらの選択に自由度がある
ことが多い。そのため、操作手順に関する制約は一般的
には図２（ｂ）に示すように操作種類を節点とする複雑
な有向ネットワークとなる。

【００１４】この有向ネットワーク上で全ての作業節点
を実行順にたどって一本のパスを得て、そのパスの各節
点を時間的制約に違反しないように操作として具体化し
たものが仕事の一スケジュールである。図３にスケジュ
ールの視覚的表現であるガントチャートの一例を示す。
ガントチャートの縦軸と横軸はそれぞれスケジューリン
グ環境における資源と時間帯である。横棒０３０１をは
じめとする表の中の太い棒が一個の操作であり、棒の縦
の位置が操作の使用資源を、横の位置と棒の長さが実行
時間帯をそれぞれ表している。

【００１５】スケジューリング対象の仕事が一つの場合
は、このようにして得られる全てのスケジュールが実行
可能解となる。しかしながら、資源を共有し、時間的に
重なりがある複数の仕事が与えられた場合は、個々の仕
事のスケジュールを独立に作成しても操作間で使用資源
の時間的競合が発生し、実行可能解を得ることは困難で
ある。資源競合のない実行可能解を作成するためには、
操作手順の選択と操作の具体化（資源と時刻の割当）を
相互に関連させつつ適切に行うことが必要である。本発
明においては図１ステップ０１０５の解探索処理でそれ
を実現する。

【００１６】本ステップは４個の内部ステップのループ
結合を基本構成とする。資源割当の確率的調整ステップ
（０１０６）は、操作種類の有向ネットワークの各節点
に資源を割当てたデータを入力として受取り、遺伝的ア
ルゴリズム（ＧＡ）に代表される組合せ問題の確率的探
索手法を用いてその割当資源の組合せをより望ましいも
のへと変化させる。この際に解探索パラメータ０１１０
を確率的探索の制御データとして使用する。資源競合の
解消ステップ（０１０７）は、操作手順の選択と操作の
具体化をおこない解候補を作成する。操作の使用資源は
前記ステップにおいて調整されたものを用いる。作成の
初期段階で各仕事のスケジュールを独立に作成し、発生
した資源競合を操作手順と操作の時間割当の変更により
解消する。異なる仕事の特定の作業間に実行順序が定義
されている場合には、その情報を作業の順序に関する制
約０１１１として取り込み、資源競合解消ルールとして
利用する。解候補の評価ステップ（０１０８）は、競合
解消ステップで得られた解候補に対し、解評価項目０１
１２に含まれる計画条件とユーザ要求の充足度とを判定
して充足度に応じた評価値を与える。この評価値は評価
値のフィードバックステップ（０１０９）により上記資
源割当の確率的調整ステップへ送られ、資源割当の最適
化に利用される。上記４ステップのループ処理を繰り返
すことにより、割当資源の組合せが徐々に最適化され、
最終的に質の高い実行可能解を生成することができる。
解探索ステップは、このループ処理を解探索パラメータ
に含まれる規定ループ回数だけ繰り返した後に、最終的
に得られた解候補を解０１１３として出力する。

【００１７】ステップ０１１４では解を表示装置０１１
６に表示し、入力装置０１１５からオペレータによる操
作を受け付ける。オペレータは、仕事データ、資源に関
する制約、解探索パラメータ、作業の順序に関する制
約、解評価項目を表示装置に出力させてそれらを編集
し、編集されたデータを用いて解探索処理を再び指示す
ることができる。オペレータによって承認を受けた解
は、正式な計画として登録され、実務フォーマットに変
換された上でプリンタ０１１７から出力される。

【００１８】本実施例は、図１に示される全てのデータ
と処理と装置を車両入換計画作成用に具体化することで
実現される。以降では、その詳細を図１との対応を明ら
かにしながら順次説明する。

【００１９】まず本実施例の計画対象である、車両基地
における車両入換計画の概要を図４、図５、図６を用い
て説明する。

【００２０】図４は、仮想的な鉄道車両基地における車
両入換計画を示す帳票の一部である。帳票の各行が車両
基地内での編成の一回の転線を表している。ここで転線
とは、車両基地内の番線から別の番線への移動のことで
ある。例えば符号０４０１の転線は、編成０２を番線０
７から番線０５へ９時３０分から移動することを表す。
さらに「内容」と「作業詳細」から、この転線は番線０
５で作業「清掃１」を受けるためのものであることが読
みとれる。各転線は開始時刻の順番に並んでおり、この
順番を遵守して転線をおこなうことにより、基地内に入
区する全ての編成が、予定された清掃・点検・修理等の
作業が受けられる番線へ次々に移動し、移動中や在線中
に互いに衝突することなしに出区予定時刻に車両基地を
出ていくことが可能となる。

【００２１】図５は、当該車両基地のレイアウト図であ
る。７本の番線と入出区線を１本持っている。番線０１
は２つの区に分割されており、それぞれの区に異なる編
成が在線できる。２区への出入りは１区に編成が在線し
ていない場合に限られるという特別な制約があるが、そ
れを除くと区は通常の番線と同じものとみなせるため、
以降の記述では特に断らない限り区を番線として扱うも
のとする。編成は番線及び入出区線の間につなげられた
転線ルートを通って他の番線もしくは車両基地の外部と
の間を行き来することができる。図４に示す車両基地
は、説明を分かり易くするために１本の転線ルートで全
ての番線と車両基地の外部を行き来できる単純な構造に
なっているが、特定の番線間のみを移動できる転線ルー
トが複数ある構造の場合にも本実施例は対応している。
また入出区線が複数本ある場合も同様である。図４の車
両基地も含めて、一般に車両基地内の番線は用途別に３
種類に分類できる。（１）作業番線：清掃・点検・修理
等の作業が可能な専用設備を持つ番線（２）留置番線：
作業番線の空きや出区を待つ間在線する番線（３）引上
番線：番線間を移動するために一時的に在線する番線作
業番線は、清掃可能番線、点検可能番線といったよう
に、可能な作業種類によってさらに細かく分類される。
同一設備で異なる作業が可能な場合もあるので、各作業
の可能番線は重複していることがある。留置番線は特別
の設備が不要なために、基地内のほとんどの番線がこれ
に該当する。作業番線の一部を留置番線として併用する
車両基地も存在し、その場合には作業番線の集合と留置
番線の集合には重なりがある。図４の車両基地を例にと
ると、引上線は番線０６と番線０７の２本である。レイ
アウトからわかるとおり、他の番線が番線０６と番線０
７以外の別の番線に向かう場合には、必ず一度番線０６
か番線０７に「引き上げ」てから目的番線に移動しなけ
ればならない。すなわち、入出区を除けば、転線は発番
線か着番線のいずれか一方が必ず引上線になる。よっ
て、引上線はその使用頻度が高いために留置等の他の目
的で使用されることはほとんどなく、在線時間も極めて
短い。

【００２２】図６は、図４の車両入換計画表をダイヤ形
式に変換した車両入換ダイヤの一部である。横軸は一日
の時間帯、縦軸は車両基地内の番線である。水平線０６
０１をはじめとする水平線が各番線における在線を、斜
線０６０２をはじめとする水平線同士を結ぶ斜線が番線
間の移動をそれぞれ表している。ある特定の編成が入区
から出区までの間に車両基地内を動き回る様子は、該当
編成の入出区から始まり入出区で終わる斜線と水平線か
らなる１本のすじをたどっていくことで容易にわかる。
また、車両入換ダイヤは、移動時と在線時の衝突がそれ
ぞれ斜線と水平線の時間的重なりとして視覚的に表現さ
れるため、それらの検出も容易である。

【００２３】以上をまとめると、車両入換計画作成問題
は、ある特定のレイアウトを持つ車両基地に入区する全
ての編成の出区迄の移動・在線の系列を、様々な制約条
件を考慮しながら作成することであるといえる。考慮す
べき制約条件は、必須制約と目標制約の２種類に分類で
きる。必須制約は、全ての実行可能な車両入換計画が必
ず満たさなければならない制約条件であり、（１）各編
成の出区時刻を守る（２）在線時の番線の競合、移動時
の転線ルートの競合がない（３）予定された作業が実行
可能な番線に規定時間以上在線し、なおかつ在線順序が
作業順序と等しいの３点が挙げられる。目標制約は必須
制約よりも弱い制約条件であり、これを充足しなくても
必須制約さえ充足していれば車両入換計画の実行可能性
が損なわれることはない。目標制約は車両入換計画の品
質に関わる制約条件と見なすことができ、目標制約の充
足度が高い車両入換計画であればあるほど高品質である
と言える。また目標制約はその種類が多く、システム開
発時にはその全てを十分に把握できない場合がある。さ
らに車両基地レイアウトや基地内の諸設備といった車両
基地特性の変化によっても目標制約は動的に変化する。
そこで、ここではある程度普遍的であると考えられる目
標制約のみを挙げる。

【００２４】１．転線回数が少ない２．各編成の余裕度が大きい３．作業順序を守る全ての編制の総転線回数が少ないということは、車両入
換を一個の作業としてトータルに捉えた場合のコストが
それだけ少ないということを意味する。余裕度とは、編
成が予定された作業を全て終了してから出区するまでの
空き時間のことである。余裕度が大きければ、列車ダイ
ヤの乱れ等のために出区予定時刻が早まった場合の対応
も容易であり、また空き時間を利用してさらに他の作業
を受けることも可能となるなど、スケジューリング環境
の動的変化に対して頑健な計画となる。（３）の作業順
序は、ここでは各編成に予定された複数の作業の実施順
序のことではなく、異なる編成の作業間に設定された実
施順序のことで、例えば、「清掃１は編成１０、編成０
３、編成０８の順序で実施する」といったものである。

【００２５】目標制約としては以上の他に、「各編成の
余裕度のばらつきが少ない」、「作業者の番線間の移動
距離が少ない」、「番線使用に偏りがない」、「番線使
用の優先順位を守る」といったものが考えられる。

【００２６】本発明の適用により、上記の車両入換計画
作成問題を解く計画作成システムを実現できる。以降で
は、図１における各データとステップの実現の詳細につ
いて順次説明する。

【００２７】まず図０１０１の仕事データについて述べ
る。車両入換計画作成問題における１個の仕事は、１編
成の入区から出区までに実施すべき予定された作業のま
とまりのことである。図７に仕事データの具体例を示
す。この例においては、仕事データは複数の仕事から構
成されており、その中の仕事０１は編成番号が０３、入
区時刻が９時３６分、出区時刻が１１時０３分、その間
に３個の作業が予定されており、各作業の所要時間もあ
らかじめ与えられる。この仕事データを入力としてステ
ップ０１０３で操作手順に関する制約を生成する。本実
施例における操作は下記の種類のいずれかに分類され
る。

【００２８】（１）作業操作（２）留置操作（３）
引上操作（４）移動操作作業操作は、各編成に予定された作業が実施可能な番線
での所要時間以上の在線を意味する。作業はさらに清掃
・点検・修理といったようにさらに細かく分けられ、そ
のそれぞれに応じて作業操作も分類される。また作業操
作が使用する資源は各作業が可能な番線である。留置操
作は、作業番線の空きを待つ間の番線での在線を意味す
る。留置操作が使用する資源は、留置番線として設定さ
れた番線のいずれかとなる。引上操作は引上線として設
定された番線における所用時間以上の在線を意味する。
移動操作は、文字どおり番線間もしくは番線と入出区線
を介した車両基地の外部との間の移動を意味し、その使
用資源は車両基地内の転線ルートである。作業操作が仕
事の完了に必須な操作であり、それ以外の操作（２）
（３）（４）が作業の実施のための補助的な処理に対応
する。図８に本実施例で使用する操作のデータ構造を示
す。各操作データには操作番号がつけられ、仕事番号、
操作種類、開始時刻、終了時刻、処理時間、使用資源の
６項目の情報を含む。操作種類が作業の場合、操作種類
には仕事の作業番号が入る。作業種類の詳細情報を知る
ためには、仕事番号が示す仕事を前記仕事データから取
り出し、その作業内容の項目を作業番号でアクセスす
る。以降の記述では、入区操作、出区操作という用語が
でてくる場合があるが、これらは入区時と出区時の移動
操作を意味するものであり、特に断らない限り通常の移
動操作として扱う。

【００２９】上記操作を具体化して適切な順序で並べた
ものが、仕事（編成の入区から出区までに予定された作
業のまとまり）のスケジュールを表す操作シーケンスで
ある。本実施例の操作シーケンスのデータ構造を図９に
示す。各操作シーケンスには他と区別するための相異な
るシーケンス番号が付けられる。操作シーケンスの主内
容は、符号０９０１の操作データへの参照リストであ
る。この他に付加的な情報として、スケジューリング対
象の仕事の仕事番号、操作リストの操作数、該操作シー
ケンスの余裕度が含まれる。

【００３０】図７の仕事データを入力として図１ステッ
プ０１０３において操作手順に関する制約を生成する。
車両入換計画作成問題における操作手順に関する制約の
例として、作業が一つの仕事の場合を図１０（ａ）に示
す。この操作種類の有向ネットワーク上で、入区節点か
ら出区節点までの作業節点を含む任意の一本のパスが実
行可能な操作手順を表す。この例で最も簡単な操作手順
は、入区、作業、出区の３節点のみからなるパスであ
る。この操作手順に対して、入区と作業、作業と出区の
間に留置のための在線操作系列を挿入するに従ってより
複雑な操作手順が得られる。出区時刻を守ることを考慮
しなければ、挿入できる留置のための在線操作系列の数
に制限はなく、その場合には可能な操作手順の数は無数
に存在する。しかしながら、車両入換業務においては業
務効率・負担の観点から転線回数はできるだけ少ない方
が望ましく、また実際に作業の前後で留置を高々一回お
こなうだけで転線ルート・番線の競合を回避できる場合
がほとんどであるため、本実施例においては、図１０
（ｂ）のように有限のネットワーク構造を操作手順に関
する制約とする。このネットワークを用いると、最も簡
単な操作手順は先に述べた入区節点、作業節点、出区節
点の３節点のみからなるパスであり、最も複雑な操作手
順は作業の前後で留置線への在線を一度づつおこなう操
作系列を含むパスである。以降の記述では前者を操作手
順の最良パターン、後者を操作手順の最悪パターンと呼
ぶことにする。図から明らかに類推できるように、全て
の操作手順は最良パターンを部分ネットワークとして含
み、最悪パターンに部分ネットワークとして含まれる性
質を持つ。これは即ち最良パターンと最悪パターンから
全ての操作手順を構成することが可能であることを意味
する。そこで、本実施例で用いる操作手順に関する制約
のデータ構造は図１１に示すものとした。各データに
は、他と区別するための相異なる番号がつけられ、付加
的な情報として対象の仕事の仕事番号を含む。主内容
は、符号１１０１の最悪パターンのリストと符号１１０
２の最良パターンのリストであり、各リストには操作種
類を表すデータが格納される。また、双方のパターンに
共通する作業節点の位置を記憶しておくために、それら
の対を同一資源操作対として格納する。以降の記述で
は、このデータ構造のデータを操作シーケンステンプレ
ート、または単にテンプレートと呼ぶことにする。

【００３１】本実施例において、図１ステップ０１０３
の操作手順における制約の生成に対応する処理は、操作
シーケンステンプレートの生成処理である。図１２のフ
ローチャートを参照しながらこの処理の説明を行う。ま
ずステップ１２０１においてテンプレート数ｍの初期化
をおこなう。ステップ１２０２で終了判定をおこない、
テンプレート数ｍが仕事データの仕事数を超えた場合に
は処理を終了する。ステップ１２０３では、最悪パター
ン上の位置ｗ、最良パターン上の位置ｂ、共通資源を持
つ操作対（作業節点）の数ｓを初期化する。ステップ１
２０４では、テンプレートの仕事番号に仕事ｍの番号を
設定する。ステップ１２０５では最悪パターンと最良パ
ターンの先頭位置に操作種類「入区」を設定する。ステ
ップ１２０６では作業数カウンタｎを初期化する。ステ
ップ１２０７ではループ処理の終了判定をおこない、作
業数カウンタｎが仕事ｍの作業数を超えた場合にはルー
プ処理を終了し、ステップ１２１４でテンプレート数ｍ
の値を１増やしてステップ１２０２の処理の終了判定へ
戻る。ループ処理を続行する場合には、ステップ１２０
８へ進み、最悪パターンに対して位置ｗを増やしながら
操作種類「留置」、「移動」、「引上」、「移動」を順
次設定する。これらは留置番線への在線のための一連の
操作系列を表す。次にステップ１２０９において最悪、
最良の両パターンに対して、位置ｗ、ｂをそれぞれ増や
しながら操作種類「仕事ｍの作業番号ｎの作業」、「移
動」、「引上」を順次設定する。そしてステップ１２１
０で、直前のステップにおいて作業を設定した位置の対
を同一資源操作対として登録してｓを１増やす。以上が
１回のループにおける処理であり、その後ステップ１２
１１で作業数カウンタｎを１増やしてステップ１２０７
のループ処理の終了判定へ戻る。ループ処理を抜けた後
は、ステップ１２１２へ進む。このステップでは、最悪
パターンに対して位置ｗを増やしながら操作種類「留
置」、「出区」を設定する。次にステップ１２１３にお
いて、最良パターンに対して位置ｂを２減らして操作種
類「出区」を設定する。この処理の終了で１個のテンプ
レートが完成する。その後はテンプレート数ｍを１増や
して終了判定ステップ１２０２へ進む。以上の処理によ
り、仕事データ中の各仕事に対応する操作シーケンステ
ンプレートが生成される。

【００３２】操作シーケンステンプレートは、図１ステ
ップ０１０５の解探索処理の主入力データとなる。本ス
テップの説明に入る前に、図１符号０１０２の資源に関
する制約と図１符号０１１０の解探索パラメータの本実
施例における実現の詳細を説明する。まず資源に関する
制約について説明する。車両入換計画作成問題において
操作が使用する資源は、車両基地内の番線及び転線ルー
トのいずれかである。各資源がどの種類の操作で使用可
能であるかという情報は、資源属性テーブルとして定義
される。そのデータ構造を図１３に示す。テーブルの各
行が操作種類ごとの使用可能な資源のリストを表してい
る。各資源は複数の用途で使うことができるため、同じ
資源が別の行に重複して格納される場合がある。ただ
し、引上操作と移動操作の資源は他の用途には使われる
ことはないものとする。車両基地のレイアウトによって
は、特定の番線間の移動に用いる転線経路が制限される
場合があるため、実行可能なスケジュールの生成にはこ
の番線・転線経路の接続情報を利用する必要がある。そ
こで資源に関する制約として資源属性テーブルに加え
て、資源間の関係を定義する接続判定テーブルを採用す
る。そのデータ構造を図１４に示す。テーブルの縦軸は
車両基地内の転線経路で横軸が同じく番線である。テー
ブルの各項目は縦の位置の転線経路と横の位置の番線が
接続されている、すなわち該番線が該転線経路を通って
移動可能であるかどうかを表す値が格納される。値ＴＲ
ＵＥは接続可能を、値ＦＡＬＳＥは接続不可能をそれぞ
れ表す。

【００３３】次に解探索パラメータについて説明する。
本実施例においては、解探索処理の基本アーキテクチャ
として確率的探索手法の一つである遺伝的アルゴリズム
（ＧＡ）を利用する。ＧＡは組合せ問題の解候補を生物
個体に見立て、各個体の形質を決める染色体情報に対し
て個体集団の世代交代サイクルの中で遺伝子オペレーシ
ョンを施すことにより、質の高い個体集団を探索する。
この探索を制御するために解探索パラメータが用いられ
る。本実施例における解探索パラメータを図１５に示
す。採用したパラメータは「実行世代数」、「個体集団
のサイズ」、遺伝子オペレーションの際の「自然淘汰
率」、「突然変異率」、そして解探索の再実行時に用い
られる「延長世代数」とした。これらはどれもＧＡの適
用に際して一般的に用いられるものである。

【００３４】図１ステップ０１０５の解探索処理の説明
をおこなう。前述したように、解探索処理の基本アーキ
テクチャにはＧＡを採用した。ＧＡは組合せ問題に対す
る解探索手法の枠組の総称であり、それぞれの詳細な仕
様があらかじめ与えられているわけではない。ＧＡの適
用にあたっては、構成部分を対象問題に対して適切に実
現する必要がある。以下その実現の詳細を図１６のフロ
ーチャートを参照しながら順次説明するとともに、図１
の解探索処理の内部ステップである「資源割当の確率的
調整」、「資源競合の解消」、「解候補の評価」、「評
価値のフィードバック」の各ステップと構成部分との対
応関係を示す。まずステップ１６０１において、図１７
に示す資源割当テーブルの初期化をおこなう。資源割当
テーブルとは、スケジューリング対象の全ての操作シー
ケンステンプレートの最悪パターン及び最良パターンの
各要素に資源を割り当てたデータのことである。資源割
当テーブルの生成は、操作手順に関する制約を表す有向
ネットワークの各節点に資源を割り当てる処理に対応す
る。解探索処理は本ステップにおいて、この資源割当テ
ーブルを解探索パラメータの集団個体数と等しい数だけ
初期化する。その後の処理においてこの資源割当テーブ
ルはＧＡの染色体とみなされ、ＧＡの枠組みの中でその
内容が確率的に調整される。次にステップ１６０２では
世代数カウンタｍを初期化する。ステップ１６０３では
処理の終了判定をおこない、世代数カウンタｍが解探索
パラメータで設定された実行世代数を超えた場合には処
理を終了する。ステップ１６０４では染色体（資源割当
テーブル）の内容を確率的に調整する。本ステップが図
１ステップ０１０６の資源割当の確率的調整処理に対応
する。本ステップは内部ステップとしてＧＡの一般的な
遺伝子オペレーションである、自然淘汰（１６０５）、
交叉（１６０６）、突然変異（１６０７）の３個の処理
を含む。これらの処理はＧＡの定義の中に具体的な手法
が示されているわけではなく、ＧＡの適用対象や染色体
の構造ごとに個別に実現する必要がある。その実現内容
については解探索処理を一通り説明した後で詳細に述べ
る。次にステップ１６０８において染色体ポインタｎを
初期化する。ステップ１６０９ではループ処理の終了判
定をおこない、染色体ポインタｎが解探索パラメータで
設定した集団個体数を超えた場合にはループ処理を終了
し、ステップ１６１０で世代数カウンタｍを１増やして
ステップ１６０３の処理の終了判定へ戻る。ループ処理
を続行する場合にはステップ１６１１へ進み、ｎ個目の
染色体を入力データとして解、すなわち仕事の操作シー
ケンスを生成する。本ステップが操作手順の選択と具体
化をおこなう図１ステップ０１０７の資源競合の解消処
理に対応する。次にステップ１６１２において生成した
解に対する計画条件とユーザ要求の充足度を評価する。
本ステップが図１ステップ０１０８の解候補の評価ステ
ップに対応する。その後は前記評価ステップで各解に与
えられた評価値をステップ１６１３において染色体にフ
ィードバックする。ここまでが１回のループ処理であ
り、これで１個の解候補が生成される。ステップ１６１
４では染色体ポインタｎの値を１増やしてステップ１６
０９のループ処理の終了判定に戻る。

【００３５】以下では、解探索処理の構成ステップであ
る、資源割当テーブル（染色体）の初期化ステップ、染
色体の確率的調整ステップ、解（操作シーケンス）の生
成ステップ、解の評価ステップの実現の詳細を順次説明
していく。

【００３６】図１８のフローチャートを参照しながら資
源割当テーブル（染色体）の初期化処理を説明する。ま
ずステップ１８０１において個体番号ｍを初期化する。
ステップ１８０２では処理の終了判定をおこない、個体
番号ｍが解探索パラメータにおいて設定された集団個体
数を超えた場合には処理を終了する。処理が終了しない
場合には、ステップ１８０３に進みテンプレート番号ｎ
を初期化する。ステップ１８０４ではループ処理の終了
判定をおこない、テンプレート番号ｎがテンプレート数
を超えた場合にはステップ１８０５で個体番号ｍを１増
やして処理の終了判定ステップ１８０２へ戻る。ループ
処理が終了しない場合はステップ１８０５へ進み、テン
プレートｎの最悪パターンに資源を割り当てる。この処
理の詳細を図１９のフローチャートを参照しながら説明
する。

【００３７】まずステップ１９０１においてテンプレー
ト上の位置ｍを初期化する。ステップ１９０２では処理
の終了判定をおこない、テンプレート上の位置が最悪パ
ターンの操作数を超えた場合には処理を終了する。処理
を終了しない場合にはステップ１９０３に進み、操作種
類変数ｋに最悪パターンの位置ｍの値を設定する。ステ
ップ１９０４ではｍがパターンの先頭かどうかを判定
し、ｍが先頭の場合にはステップ１９０５へ進み、資源
属性テーブルを参照しながら操作種類ｋの資源をランダ
ムに選択して位置ｍに設定する。ｍが先頭でない場合に
は資源属性テーブルと接続判定テーブルの双方を参照し
ながら、操作種類がｋでなおかつ位置ｍ−１の資源と接
続可能な資源をランダムに選択して位置ｍに設定する。
ステップ１９０７ではｍを１増やして処理の終了判定ス
テップ１９０２へ戻る。

【００３８】図１８に戻り資源割当テーブルの初期化処
理の説明を続ける。ステップ１８０５の次はステップ１
８０６においてテンプレートｎの最良パターンに資源を
割り当てる。本ステップは処理対象が最悪パターンから
最良パターンに代わっただけで処理内容はステップ１８
０５と全く同じである。ステップ１８０５とステップ１
８０６により最悪・最良両パターンに対して資源が割り
当てられるが、このままでは同一の作業節点に対して両
パターンに異なる資源が割り当てられる可能性がある。
そこでステップ１８０７において最悪パターンと最良パ
ターンの同一の作業節点が格納される位置の資源を同じ
ものにする。ここまでが１回のループ処理であり、これ
でテンプレート１個に対する資源割り当てが完了する。
ステップ１８０８ではテンプレート番号ｎの値を１増や
してステップ１８０４のループ処理の終了判定へ戻る。

【００３９】次に図１６ステップ１６０４の染色体の確
率的調整処理について説明する。本処理は３個の内部ス
テップからなる。まず第１番目のステップ１６０５では
ＧＡの遺伝子オペレーションのひとつである染色体の自
然淘汰処理をおこなう。図１６ステップ１６１３の評価
値のフィードバックにより染色体に与えられた評価値を
用いて、評価値の低いものから順に解探索パラメータで
設定された自然淘汰率に応じた個数の染色体を削除す
る。探索の初期世代では染色体に評価値が与えられてい
ないため、この場合は特別に全ての染色体が同一の評価
値を持つものとして処理をおこなう。以下の交叉処理、
突然変異処理においても初期世代ではこれと同じ処理を
おこなうものとする。

【００４０】次のステップ１６０５の交叉処理では、自
然淘汰処理によって減少した染色体数の分だけ新たな染
色体を生成して補充する。新たな染色体の生成は、染色
体集合から任意に２個の染色体を選択し、両者の要素
（これを遺伝子と呼ぶ）を合成することで実現する。染
色体が資源割当テーブルの場合にはその要素は資源であ
り、これが遺伝子にあたる。以降の記述では、生成元の
染色体を親染色体、新たに生成される染色体を子染色体
と呼ぶことにする。

【００４１】任意に選択した親染色体Ａと親染色体Ｂか
ら子染色体Ｃを生成する処理について、図２０のフロー
チャートを参照しながら説明をおこなう。まずステップ
２００１においてテンプレート番号ｍを初期化する。ス
テップ２００２では処理の終了判定をおこない、テンプ
レート番号ｍがテンプレート数を超えた場合には処理を
終了する。処理を終了しない場合にはステップ２００３
に進み、親染色体Ａと親染色体Ｂから子染色体のテンプ
レートｍの最悪パターンを生成する。本ステップの詳細
を図２１のフローチャートを用いて詳細に説明する。

【００４２】まずステップ２１０１において最悪パター
ン上の位置ｍを初期化する。ステップ２１０２では終了
判定をおこない、位置ｍが最悪パターンの長さを超えた
場合には処理を終了する。処理を終了しない場合には、
ステップ２１０３に進み資源変数ａ及びｂに、親Ａと親
Ｂの最悪パターン上の位置ｍの値をそれぞれ格納する。
ステップ２１０４ではｍがパターンの先頭かどうかを判
定し、先頭であればステップ２１０５において確率Ｐｃ
でａまたはｂを子染色体の最悪パターン上の位置ｍに設
定する。ここで確率Ｐｃは、より評価値の高い親の遺伝
子を子染色体が継承する可能性がその優秀さの程度を反
映するように動的に決定される値である。親染色体Ａが
優秀である場合の確率Ｐｃの算出式を以下に示す。Ｐｃ
＝（親染色体Ａの評価値）／（（親染色体Ａの評価値）
＋（親染色体Ｂの評価値））ステップ２１０５の終了後
はステップ２１０６へ進み位置ｍの値を１増やしてステ
ップ２１０２の処理の終了判定へ戻る。位置ｍが先頭で
はない場合はステップ２１場合はステップ２１０９へ進み確率Ｐｃでａまたはｂを
子染色体の最悪パターンの位置ｍに設定する。ステップ
２１０９の終了後はステップ２１０６へ進み位置体の最悪パターンの位置ｍに設定する。ステップ２１１
１の終了後はステップ２１０６へ進み位置ｍの値を１増
やしてステップ２１０２の処理の終了判定へ戻る。ステ
ップ２１１０の判定処理が偽の場合はステップ２１１２
で再び接続判定をへ進みａを子染色体の最悪パターンの位置ｍに設定す
る。ステップ２１１３の終了後はステップ２１０６へ進
み位置ｍの値を１増やしてステップ２１０２の処理の終
了判定へ戻る。どちらも接続可能では無い場合にはステ
ップ２１１４へ進み確率Ｐcでａまたはｂを子染色体の
最悪パターンの位置ｍに設定する。ステップ２１１４の
終了後はステップ２１０６へ進み位置ｍの値を１増やし
てステップ２１０２の処理の終了判定へ戻る。

【００４３】図２０に戻り子染色体の生成処理について
の説明を続ける。ステップ２００３の終了後は、ステッ
プ２００４で親染色体Ａと親染色体Ｂから子染色体のテ
ンプレートｍの最良パターンを生成する。本ステップは
処理対象が最悪パターンから最良パターンに代わっただ
けで処理内容はステップ２００３と全く同じである。ス
テップ２００３とステップ２００４により子染色体のテ
ンプレートｍの最悪・最良両パターンが生成されるが、
このままでは同一の作業節点に対して両パターンに異な
る資源が割り当てられる可能性がある。そこでステップ
２００５において最悪パターンと最良パターンの同一の
作業節点が格納される位置の資源を同じものにする。ス
テップ２００６ではテンプレート番号ｍの値を１増やし
て処理の終了判定ステップ２００２に戻る。

【００４４】図１６に戻り、ステップ１６０７の突然変
異処理について説明する。突然変異は染色体の遺伝子コ
ードをランダムに変化する処理であり、これにより解探
索が局所解に陥ることを防ぐ。この際、全くランダムに
遺伝子を変化させると実行可能解が得られなくなる可能
性が非常に高くなる。そこでこれを防ぐために、資源に
関する制約である資源割当テーブルと接続判定テーブル
を参照しながら適切な資源（遺伝子）を選択する必要が
ある。本ステップの詳細を図２２のフローチャートを参
照しながら説明する。

【００４５】まずステップ２２０１においてテンプレー
ト番号ｍを初期化する。ステップ２２０２では処理の終
了判定をおこない、テンプレート番号ｍがテンプレート
数を超えた場合には処理を終了する。処理を終了しない
場合にはステップ２２０３に進み、テンプレートｍの最
悪パターンに突然変異を施す。本ステップの詳細を図２
３のフローチャートを用いて詳細に説明する。

【００４６】まずステップ２３０１において最悪パター
ン上の位置ｎを初期化する。ステップ２３０２では処理
の終了判定をおこない、位置ｎが最悪パターンの長さを
超えた場合には処理を終了する。処理を終了しない場合
にはステップ２３０３に進み、整数変数ｖに１から１０
００までの値をランダムに格納する。ステップ２３０４
ではｖと解探索パラメータで設定された突然変異率との
大小比較を行う。ｖが突然変異率より大きい場合はステ
ップ２３０５で位置ｎの値を１増やして処理の終了判定
２３０１へ戻る。ｖが突然変異率より小さい場合はステ
ップ２３０６へ進み、操作種類変数ｋにテンプレートｍ
の最悪パターンの位置ｎの値を設定する。ステップ２３
０７では位置ｎがパターンの先頭であるかを判定する。
位置ｎが先頭でない場合はステップ２３０８に進み、資
源属性テーブルと接続判定テーブルの双方を参照しなが
ら、操作種類がｋでなおかつ位置ｎ−１の資源と接続可
能な資源をランダムに選択して位置ｎに設定する。位置
ｎが先頭の場合はステップ２３０９へ進み、資源属性テ
ーブルを参照しながら操作種類ｋの資源をランダムに選
択して位置ｎに設定する。ステップ２３０８とステップ
２３０９の終了後は、どちらもステップ２３０５で位置
ｎの値を１増やして処理の終了判定ステップ２３０５へ
戻る。

【００４７】図２２に戻り突然変異処理の説明を続け
る。ステップ２２０３の終了後はステップ２２０４に進
み、テンプレートｍの最良パターンに対して突然変異を
施す。本ステップは、処理対象が最悪パターンから最良
パターンに代わっただけで処理内容はステップ２２０３
と全く同じである。ステップ２２０３とステップ２２０
４により染色体のテンプレートｍの最悪・最良両パター
ンに突然変異が施されるが、このままでは同一の作業節
点に対して両パターンに異なる資源が割り当てられる可
能性がある。そこでステップ２２０５において最悪パタ
ーンと最良パターンの同一の作業節点が格納される位置
の資源を同じものにする。ステップ２２０６ではテンプ
レート番号ｍの値を１増やして処理の終了判定ステップ
２２０２に戻る。

【００４８】以上で図１６の解探索処理における染色体
の確率的調整ステップ１６０４の説明を終える。次に解
（操作シーケンス）の生成ステップ１６１１について説
明する。

【００４９】まず本ステップの処理の基本的な考え方を
以下に示す。

【００５０】１．余裕度をなるべく大きくとりながら各
仕事の操作シーケンスを独立に初期化する。

【００５１】２．初期解に資源競合もしくは作業操作間
の順序制約違反を起こす操作対が存在する場合は、（ａ）操作の時間割当の変更（操作のシフト）（ｂ）操作手順の変更の２つの処理を適切におこなうことにより解消を図る。
ただし留置操作は資源競合解消の対象からはずす。

【００５２】３．資源を競合する操作対からシフト操作
を選択（操作の順序付け）する際には、（ａ）作業操作間の順序制約違反が新たに発生しない（ｂ）各操作シーケンスの余裕度が均等になるの２点を考慮しながらおこなう。すなわち上記（ａ）
（ｂ）を資源競合解消ルールとして用いる。

【００５３】４．（１）〜（３）によっても解消できな
い資源競合と作業間の順序制約違反が残った場合には、
その後の実行世代で、図１６の染色体の確率的調整ステ
ップ１６０４により解消可能な資源割当の組合せが生成
されることを期待して解消をあきらめる。

【００５４】留置操作に関する資源競合が存在する場合
も、上記と同様の考え方から本ステップでは何の処理も
おこなわない。

【００５５】次に図２４のフローチャートを参照しなが
ら本ステップの詳細を説明する。このフローチャートを
利用して全体の処理の流れを一通り説明した後に、さら
に詳しい解説が必要と思われる構成ステップについて説
明をおこなう。

【００５６】まずステップ２４０１において全ての仕事
の操作シーケンスを独立に初期化する。ステップ２４０
２では初期解に対して順序制約違反の解消をおこなう。
ステップ２４０３において全ての操作シーケンスの操作
からガントチャートを構成する。図２５に本実施例で使
用するガントチャートのデータ構造を示す。基本要素は
操作データへの参照であり、それらが使用資源ごとにリ
ストを構成する。各リストは操作の開始時刻の順番で常
に整列されている。図２４に戻って説明を続ける。ステ
ップ２４０４では、ガントチャートを利用して資源競合
操作対の集合を作成する。ステップ２４０５では、各操
作シーケンスの余裕度を計算し、余裕度が負数、すなわ
ち出区時刻をオーバーする編成が一つでも存在する場合
にはフラグＯutＯverに符号ＴＲＵＥを、そうではない
場合には符号ＦＡＬＳＥを設定する。ステップ２４０６
では処理の終了判定をおこない、資源競合の数と作業順
序違反の数が共に０であるか、またはフラグＯutＯver
がＴＲＵＥである場合には処理を終了する。処理を終了
しない場合にはステップ２４０７に進み、シフト開始時
刻が最も早い資源競合操作対と同じく順序制約違反操作
対の間でシフト開始時刻を比較する。資源競合操作対の
シフト開始時刻が早い場合にはステップ２４０８でその
資源競合を解消する。順序制約違反操作対のシフト開始
時刻が早い場合にはステップ２４０９でその順序制約違
反を解消する。上記両ステップのどちらかを終了した後
は、ステップ２４１０に進み操作変数ｐにシフトした操
作を格納する。ステップ２４１１において操作シーケン
スの中でｐの前方に発生した資源競合を解消する。次に
ステップ２４０４の資源競合操作対集合の生成処理を再
び行う。ステップ２４１２では順序制約式の充足度を判
定し、ステップ２４０５へ戻る。

【００５７】以上が解（操作シーケンス）の生成処理の
概要である。次に、詳しい解説が必要と思われる構成ス
テップの詳細を順次説明する。なお以降の説明で使用す
るフローチャートの中で、データの内部要素を参照する
場合には参照記号「．」を用いる場合がある。例えば、
「テンプレートｍ．最良パターン」と記述した場合は、
テンプレートｍの最良パターンを指す。

【００５８】まず図２４ステップ２４０１の操作シーケ
ンス初期化処理を説明する。資源競合や作業順序制約の
違反の発生を考慮せずに各操作シーケンスを独立に作成
する場合、最も余裕度が大きい操作手順は、最も操作数
が少ない最良パターンであることは自明である。そこで
本ステップでは、操作シーケンステンプレートの最良パ
ターンの各操作を具体化して初期解を生成する。本ステ
ップの処理の詳細を図２６のフローチャートを参照しな
がら説明する。

【００５９】ステップ２６０１においてテンプレート番
号ｍを初期化する。ステップ２６０２では処理の終了判
定をおこない、テンプレート番号ｍがテンプレート数を
超えた場合には処理を終了する。処理を終了しない場合
にはステップ２６０３へ進み、仕事番号ｗにテンプレー
トｍの仕事番号を格納する。ステップ２６０４では操作
番号ｎを初期化する。ステップ２６０５では操作番号ｎ
を用いてループ処理の終了判定をおこなう。操作番号ｎ
がテンプレートｍの最良パターンの要素数を超えた場合
には、テンプレートｍに対する操作シーケンスの生成が
完了したのでループ処理を終了する。その後はまずステ
ップ２６１５で、操作シーケンスの最後の操作の終了時
刻が仕事ｗの終了時刻と等しくなるように操作の割当時
間を調整する。具体的には、操作シーケンスの最後の作
業操作の処理時間を適切な長さまで延ばすことで実現す
る。次にステップ２６１６で操作シーケンスの余裕度を
計算する。そしてステップ２６０６でテンプレート番号
ｍの値を１増やしてステップ２６０２の処理の終了判定
に戻る。ループ処理を続ける場合にはステップ２６０７
へ進み、操作種類変数ｋにテンプレートｍの最良パター
ンにおける位置ｎの値を、資源変数ｖに資源割当テーブ
ルのテンプレートｍの最良パターンにおける位置ｎの値
をそれぞれ格納する。ステップ２６０８では新しい操作
データを生成（操作変数ｏpに格納）し、それを操作シ
ーケンスｍの第ｎ番目に設定する。ステップ２６０９で
はｏpの仕事番号にｗを、操作種類にｋを、使用資源に
ｖをそれぞれ設定する。ステップ２６１０ではｏpの処
理時間を設定する。操作種類が作業の場合には、仕事デ
ータの作業内容を参照して所要時間を取得し、その値を
処理時間に設定する。それ以外の操作の場合は、あらか
じめ決められた所要時間（例：番線０１から番線０７へ
の移動は５分）を処理時間に設定する。ステップ２６１
１では操作種類ｋが入区であるかどうか判定し、入区の
場合はステップ２６１２で操作ｏpの開始時刻に仕事ｗ
の開始時刻を設定する。入区ではない場合はステップ２
６１３でｏpの開始時刻に操作シーケンスの一つ前の操
作の終了時刻を設定する。一般的な仕事のスケジューリ
ング問題においては、同一操作シーケンス中の隣合う操
作は時間的重なりがなければ開始時刻と終了時刻の関係
に制約がないことが多い。しかしながら、車両入換計画
作成問題においては各操作の処理が連続していなければ
得られた解は実行可能ではないため、このような問題固
有の時刻割当処理が必要となる。以降で説明する操作の
シフト処理においてもこの操作の連続性に関する制約を
遵守する必要があるため、シフト処理を施した場合にシ
フトした操作の後ろに位置する操作のみならず前に存在
する操作も処理時間帯が変化する。それに付随して資源
競合や順序制約違反が新たに発生する可能性があるた
め、車両入換計画作成問題においては一般的な仕事のス
ケジューリング問題よりも実行可能な操作シーケンスの
生成処理が複雑なものとなる。

【００６０】図２６の説明を続ける。ステップ２６１２
またはステップ２６１３のいずれかを終了した後に、ス
テップ２６１４で操作ｏｐの終了時刻を設定する。ここ
までが一回のループ処理であり、ステップ２６１７で操
作番号ｎの値を１増やしてループ処理の終了判定ステッ
プ２６０５へ戻る。

【００６１】図２４ステップ２４０２の順序制約式違反
解消処理について説明する。順序制約式とは、２つの作
業操作の開始時刻と終了時刻、もしくは定数からなる不
等式・等式のことである。作業操作Ａと作業操作Ｂを用
いて構成される順序制約式の全てを以下に示す。

【００６２】１．Ａ．開始時刻＊Ｂ．開始時刻２．Ａ．終了時刻＊Ｂ．開始時刻３．Ａ．開始時刻＊Ｂ．終了時刻４．Ａ．終了時刻＊Ｂ．終了時刻５．Ａ．開始時刻＃定数６．Ａ．終了時刻＃定数７．Ｂ．開始時刻＃定数８．Ｂ．終了時刻＃定数符号＊は演算子＜＞ ≦ ≧ ＝のいずれかを表
し、符号＃は演算子＞ ≧ ＝のいずれかを表す。ス
テップ２４０２では、設定された順序制約式に違反する
操作対を発見し、操作のシフトにより違反の解消を行
う。図２７に本実施例で使用する順序制約式のデータ構
造を示す。このデータ構造は、使用する演算子、左辺の
操作、右辺の操作（もしくは定数）に関する情報と制御
用データへの参照からなる。制御用データは順序制約違
反の解消時に用いる情報であり、該順序制約式が違反状
態にあるかどうかを示す違反フラグ、該順序制約式が有
効であるかどうかを示す有効フラグ、左辺と右辺の操作
データへの参照、違反解消時にシフトする操作、シフト
の開始時刻、シフトの幅、シフトの種類からなる。

【００６３】シフトの種類については図２８を用いて詳
しく説明する。まずシフト種類Ｔypelは、シフトする操
作の開始時刻が順序制約式に含まれている場合である。
例として順序制約式「作業操作Ａの開始時刻＜作
業操作Ｂの開始時刻」を用いる。この順序制約式に違反
した状況では、シフト対象となるのは作業操作Ｂであ
り、シフト幅ｗは「Ｂの開始時刻 − Ａの開始時刻」
により計算される。シフトの方法は図のように作業操作
Ｂの全体をｗ以上後ろへずらす。これにより順序制約式
の違反が充足される。

【００６４】次にシフト種類Ｔype２は、シフトする操
作の終了時刻が順序制約式に含まれている場合である。
例として順序制約式「作業操作Ａの開始時刻＜作業
操作Ｂの終了時刻」を用いる。この順序制約式に違反し
た状況では、シフト対象となるのは作業操作Ｂである。
Ｔype１と同様に作業操作Ｂの全体を後ろへずらすこと
により順序制約違反を解消できるが、その代わりにＢの
終了時刻の延長によっても同じく順序制約違反を解消で
きる。なおかつこの場合には、操作の連続性を保つため
に操作シーケンスのＢの前方にある操作に対して割当時
間を変化させる必要がない。そこでこの場合には、「Ｂ
の終了時刻 − Ａの開始時刻」で計算される幅ｗだけ
作業操作Ｂの終了時刻を延長することにより順序制約の
違反を解消する。

【００６５】全ての順序制約式は、式の要素の値を演算
子に従って比較することにより違反、無違反の判定が可
能である。また順序制約式が違反状態の場合には、違反
操作対に対するシフト対象操作、シフト幅、シフト開始
時刻、シフト種類を複雑な処理をせずに一意に決定する
ことができる。

【００６６】図２９のフローチャートを参照しながら順
序制約式違反解消処理について説明する。まずステップ
２９０１において、有効フラグがＴＲＵＥである順序制
約式に対してその充足度を判定する。違反状態の順序制
約式に対しては、違反操作対に対するシフト対象操作、
シフト幅、シフト開始時刻、シフト種類を決定してそれ
らの値を制御データの各項目に設定する。ステップ２９
０２では処理の終了判定をおこない、違反状態の順序制
約式の数が０の場合には処理を終了する。処理を終了し
ない場合にはステップ２４０９に進み、シフト開始時刻
が最も早い順序制約式の違反を解消する。その後は再び
ステップ２９０１の順序制約式の充足度判定へ戻る。シ
フト開始時刻が最も早い順序制約違反を順次解消してい
くことにより、最終的に順序制約違反のない操作シーケ
ンス集合を生成することができる。

【００６７】図３０のフローチャートを用いて最も早い
順序制約違反の解消処理を詳細に説明する。まずステッ
プ３００１において制御データ変数ｄatに違反を解消す
る順序制約式の制御データを格納する。ステップ３００
２では、操作変数ｏpに制御データｄatのシフト対象操
作を、整数変数ｗidthに制御データｄatのシフト幅をそ
れぞれ格納する。ステップ３００３ではシフト種類の判
定を行う。制御データｄatのシフト種類がｔypelの場合
には、ステップ３００４においてシフト操作ｏp、シフ
ト幅ｗidthで操作のシフトと空き時間帯の調整をおこな
い処理を終了すこない処理を終了する。上記の処理により、図２８で説
明した２つのシフト種類のそれぞれに対応した違反解消
処理を実行する。ステップ２９０４の操作のシフトと空
き時間帯の調整処理の詳細を、図３１のフローチャート
を参照しながら説明する。

【００６８】ここではシフト操作をｏp、シフト幅をｗi
dthとする。まずステップ３１０１において操作ｏpをシ
ーケンス中で幅ｗidthだけシフトする。この処理の概要
を図３２を用いて説明する。操作３２０１をシフト対象
の操作とすると、まずこの操作から操作シーケンスを前
にたどって、直前に作業か留置操作がある操作まで戻
る。図３２では操作３２０２がそれに該当する。次に操
作３２０２以降の部分シーケンスを幅ｗidthだけ後ろへ
ずらす。すなわち、部分シーケンスに含まれる全ての操
作の開始時刻と終了時刻に値ｗidthを加える。操作を前
にたどる処理は、移動操作と引上操作処理時間を一定に
保つために必要とされる。この処理をおこなわないと、
シフト操作後の空き時間帯の調整処理で両者の処理時間
が延長される場合がある。

【００６９】上記の処理により出区時刻が予定時刻を超
過する。そこで出区操作が予定時刻に間に合うように、
できるだけ出区直前の作業操作か留置操作の処理時間を
短縮する。短縮の限度は、作業操作の場合は作業の所要
時間、留置操作の場合は留置番線の在線最小時間であ
る。限度を超えても予定時刻をオーバーする場合にはそ
こで短縮処理を打ち切る。

【００７０】以上が操作のシフト処理の概要である。こ
の処理により、後ろにずれた部分シーケンスの先頭操作
とその直前の操作の間に空き時間が生じる。実行可能な
車両入換計画を生成するためには操作の連続性に関する
制約を遵守する必要があるため、この空き時間をなんら
かの方法で埋める処理が必要となる。その方法として以
下の２つが考えられる。（１）直前の操作の終了時刻を
延長する。図３２の場合は操作３２０４の終了時刻を延
長して直後の操作の開始時刻と等しくする。（２）留置
番線への転線操作系列を挿入する。ただし、作業の合間
の留置番線への在線は高々１回であるとの制限があるた
め、既に留置番線への転線操作系列が挿入されている場
合にはこの手法は使えない。

【００７１】（１）に関してはその処理内容は自明であ
る。（２）の留置番線への転線操作系列の挿入処理につ
いては、その概要を図３３を用いて説明する。まず空き
時間帯の前後の作業操作の間にある移動操作と引上操作
（図３３では部分操作系列３３０１）を全て削除する。
次に該操作シーケンスの雛型となった操作シーケンステ
ンプレートと資源割当テーブルから最悪パターンを取り
出す。それぞれの最悪パターンから空き時間帯に対応す
る部分パターンを取り出す。この部分パターンが留置番
線への在線操作系列となっている。図３３では部分パタ
ーン３３０２と部分パターン３３０３がそれに該当す
る。これらの部分パターンから部分操作シーケンスを具
体化して空き時間帯に挿入する。

【００７２】留置番線への転線操作系列の挿入処理は、
仕事の操作手順の変更処理とみなすことができる。以降
で詳しく説明するが、この処理を適切におこなうことに
より順序制約違反と資源競合の新たな発生を防止するこ
とが可能となる。

【００７３】空き時間帯の調整に手法（１）を適用した
場合には、操作手順か変化することがないため余分な転
線の発生を極力抑えることが可能である。しかしなが
ら、これにより処理時間が延長された作業操作または留
置操作が資源競合を起こす可能性が高い。さらに、作業
操作については順序制約違反の発生の可能性もある。こ
れに対して手法（２）を適用した場合は、転線回数が増
えるデメリットがあるが、直前の操作の割当時間は変化
しないためそれに対する資源競合や順序制約違反が新た
に発生することはない。また以降で詳しく述べるが、本
実施例における資源競合の解消ステップは留置操作を解
消の対象としないため、留置番線への転線操作系列を挿
入しても新たに資源競合を起こす可能性がある操作は、
挿入された移動操作と引上操作だけである。これらの操
作は処理時間が一定でなおかつ非常に短いため、競合が
発生する頻度は作業操作や留置操作の終了時刻を延長し
た場合と比べると極めて少ない。空き時間帯の２つの手
法の使い分けは、図３１に戻り操作のシフトと空き時間
帯の調整処理を説明する中で明らかにする。

【００７４】ステップ３１０１を終了した後はステップ
３１０２へ進み、空き時間帯の調整処理（１）をおこな
う。次にステップ３１０３でシフトした操作ｏpの種類
判定をおこない、ｏpが作業操作ではない場合には処理
を終了する。これはすなわち、移動操作や引上操作がシ
フト対象の場合には直前に留置番線への転線操作系列を
挿入することはないということを意味する。ｏpが作業
操作の場合にはステップ３１０５においてｏpの直前に
資源競合（留置操作を除く）もしくは順序制約違反が新
たに発生したかどうか判定する。発生していなければ処
理を終了する。発生している場合はステップ３１０６で
延長した処理時間を元に戻し、ステップ３１０７で空き
時間帯の調整処理（２）をおこない処理を終了する。

【００７５】図２４に戻り解（操作シーケンス）の生成
処理における主要な構成ステップの説明を続ける。次は
ステップ２４０４の資源競合操作対集合の生成処理につ
いて説明する。まず本実施例で用いる資源競合操作対の
データ構造を図３４に示す。

【００７６】各資源競合操作対は他と区別するための相
異なる操作対番号が与えられる。データの内容は、操作
対を構成する２個の操作データへの参照、競合解消時に
シフト処理によりつけられる操作間の順序、シフト開始
時刻、シフト幅からなる。操作間順序が１→２の場合
は、競合解消時に操作２を後ろへシフトすることを意味
し、逆に操作間順序が２→１の場合は操作１を後ろへシ
フトすることを意味する。シフト開始時刻とシフト幅
は、操作間に付けられる順序に従って決定される。

【００７７】次に図３５のフローチャートを参照しなが
ら資源競合操作対集合の生成処理の詳細を説明する。ス
テップ３５０１で資源変数ｍを初期化する。ステップ３
５０２は処理の終了判定をおこない、資源変数ｍが資源
総数を超えた場合には処理を終了する。処理を終了しな
い場合にはステップ３５０３に進み、ガントチャートを
利用して資源ｍを使用する全ての操作対を取り出し部分
処理３５０４を施す。この処理の詳細は、まずステップ
３５０５において操作対のそれぞれの操作の種類を判定
する。どちらかの操作の種類が留置の場合には部分処理
を終了する。どちらの種類も留置ではない場合はステッ
プ３５０６へ進み、操作対を構成する操作ｏｐ１と操作
ｏｐ２が時間的重なりがあるかどうかを判定する。時間
的重なりがなければ部分処理を終了する。時間的重なり
がある場合には、ステップ３５０７において操作対（ｏ
ｐ１，ｏｐ２）から資源競合操作対集合を作成する。そ
の後ステップ３５０８で資源競合操作対を集合に加えて
部分処理を終了する。全ての操作対に対して部分処理３
５０４を施した後は、ステップ３５０９で資源変数の値
を１増やして終了判定ステップ３５０２へ戻る。ステッ
プ３５０７の資源競合操作対集合の作成処理について詳
細に説明する。資源競合は、操作対のどちらの操作に対
しても適切な幅だけ後ろへシフトすることにより解消可
能である。したがって、操作対に２通りの順序のどちら
をつけることも可能であるが、本実施例では以下に示す
基本方針のもとで操作対に順序を付ける。（１）新たな
順序制約違反が発生しない操作を付ける。（２）どちら
の順序でも順序制約違反が発生しなければ、シフト処理
を施した場合に前方に留置番線への転線操作系列を挿入
しなくても済む（すなわち既に挿入済みであるか、直前
の操作の終了時刻を延長しても資源競合と順序制約違反
がおこらない）方の操作をシフトする順序をつける。
（３）どちらの順序でも順序制約違反が発生する場合は
余裕度の大きい操作をシフトする順序をつける。この場
合はどちらの順序のもとでシフト処理を施しても明らか
に順序制約違反が発生する。（４）どちらの順序でも留
置番線への転線操作系列を挿入しなくても済む、または
どちらの順序でも留置番線への転線操作系列の挿入が必
要となる場合は、余裕度の大きい操作をシフトする順序
をつける。この基本的方針のもとで競合操作対に順序づ
けをおこなって資源競合を解消すれば、各操作シーケン
スの余裕度が均等でなおかつ順序制約を極力充足する実
行可能解の生成を期待できる。

【００７８】基本方針を具体化した処理の詳細を、図３
６のフローチャートを参照しながら説明する。まずステ
ップ３６０１において資源競合操作対変数ｐairに新し
い資源競合操作対を生成して格納する。ステップ３６０
２では生成対象の操作対（ｏp１，ｏp２）に対して、ｏ
p１をシフトした場合とｏp２をシフトした場合のシフト
幅をそれぞれ算出する。ステップ３６０３ではｏp１か
ｏp２のどちらかが入区または出区操作かどうかの判定
をおこなう。どちらかが入区または出区操作の場合はス
テップ３６０４へ進み入区または出区操作ではない方の
操作をシフトする順序をｐair．順序に設定する。その
後はｐairに他の値を適切に設定して処理を終了する。
どちらも入区または出区操作ではない場合は、ステップ
３６０５でｏp１とｏp２が共に作業操作であるかどうか
の判定をおこなう。少なくともどちらかが作業操作では
ない場合は、ステップ３６１０に進む。共に作業操作の
場合はステップ３６０６に進み、ｏp１とｏp２のどちら
もシフトすることによりｏp１とｏp２の間の順序制約違
反を新たに生じるかどうか判定する。どちらも新たに発
生しなければステップ３６１０へ進む。どちらか少なく
とも一方が新たに順序制約式違反を発生する場合にはス
テップ３６０７でどちらをシフトしてもｏp１とｏp２の
間に順序制約式違反を生じるかどうか判定する。どちら
も生じる場合はステップ３６０８で余裕度が大きい操作
をシフトする順序をｐair．順序に設定する。どちらか
片方のみが順序制約違反を生じる場合はステップ３６０
９へ進み、順序制約違反を生じないシフトをおこなう順
序をｐair．順序に設定する。ステップ３６０８または
ステップ３６０９の終了後は、共にｐairに他の値を適
切に設定して処理を終了する。ステップ３６１０では、
ｏp１とｏp２のどちらかだけが、シフト後に直前の作業
または留置操作の処理時間をシフト幅だけ延長すると資
源競合か順序制約違反を新たに生じるかどうか判定す
る。これが真の場合はステップ３６１１で競合と違反が
生じないシフトをおこなう順序をｐair．順序に設定す
る。偽の場合は余裕度が大きい操作をシフトする順序を
ｐair．順序に設定する。ステップ３６１１またはステ
ップ３６１２の終了後は、共にｐairに他の値を適切に
設定して処理を終了する。

【００７９】図２４に戻り解（操作シーケンス）の生成
処理における主要な構成ステップの説明を続ける。ステ
ップ２４０８の最も早い資源競合の解消処理について、
図３７のフローチャートを参照しながら説明する。

【００８０】まずステップ３７０１において資源競合操
作対変数ｐairにシフト開始時刻が最も早い資源競合操
作対を格納する。次にステップ３７０２で操作変数ｏp
にシフト対象操作を、操作変数ｋeepに固定する操作
を、整数変数ｗidthにシフト幅をそれぞれｐairから取
り出して格納する。ステップ３７０３ではｋeepが操作
シーケンスの中の最後の作業操作であり、なおかつその
後ろに留置番線への転線操作系列が挿入されていないか
どうかを判定する。これが真の場合はｋeepは出区前の
待機を兼ねた作業操作であるため、処理時間を大幅に短
縮することが可能である。よってステップ３７０４でｋ
eepの処理時間を最大限縮め、ステップ３７０５でｋeep
の後ろに留置番線への転線操作系列を挿入して処理を終
了する。挿入の方法は図３１ステップ３１０７と同様で
ある。判定が偽の場合は図３０の順序制約違反の解消処
理で説明したステップ３００４の操作のシフトと空き時
間帯の調整処理を、シフト操作ｏp、シフト幅ｗidthと
して実行して処理を終了する。図２４に戻り解（操作
シーケンス）の生成処理における主要な構成ステップの
説明を続ける。ステップ２４０９の最も早い順序制約式
の違反解消処理については図２９の順序制約式違反解消
処理の説明で述べた。ステップ２４１１のシフト操作の
前方に生じた資源競合の解消処理について図３８のフロ
ーチャートを参照しながら説明する。

【００８１】まずステップ３８０１において、シフトし
た操作ｐの前方にある全ての操作に関する資源競合操作
対の集合を生成する。本ステップの詳細を図３９のフロ
ーチャートを参照しながら説明する。

【００８２】まずステップ３９０１において、操作変数
ｔmpにｐを含む操作シーケンスの先頭操作を格納する。
次にステップ３９０２では処理の終了判定をおこない、
ｔmpとｐが同一操作の場合は処理を終了する。処理を終
了しない場合にはステップ３９０３に進みｔmpの種類が
留置であるかどうか判定する。ｔmpの種類が留置の場合
にはステップ３９０９でｔmpに操作シーケンス中のｔmp
の次の操作を格納し、ステップ３９０２の終了判定処理
に戻る。ｔmpの種類が留置ではない場合にはステップ３
９０４に進み、ガントチャートを利用してｔmpと同じ資
源を使用する全ての操作に対して部分処理３９０５を施
す。部分処理はまずステップ３９０６でｔmpと該操作の
間に時間的重なりがあるかどうかを判定する。時間的重
なりがない場合は部分処理を終了する。時間的重なりが
ある場合はステップ３９０７でｔmpをシフトする順序で
資源競合操作対集合を生成する。ステップ３９０８にお
いて資源競合操作対を集合に加えて部分処理を終了す
る。部分処理を終了した後は、ステップ３９０９でｔmp
に操作シーケンス中のｔmpの次の操作を格納し、ステッ
プ３９０２の終了判定処理に戻る。

【００８３】図３８に戻ってシフトした操作の前方に生
じた資源競合の解消処理の説明を続ける。ステップ３８
０１を終了した後にステップ３８０２に進み、処理の終
了判定をおこなう。資源競合操作対集合の数が０の場合
は処理を終了する。集合の数が０でない場合にはステッ
プ２４０９の最も早い資源競合の解消処理をおこなう。
その後はステップ３８０１へ戻る。以上で図１６の解探
索処理における解（操作シーケンス）の生成処理の詳細
説明を終える。次に解探索処理における解の評価ステッ
プについて説明する。本ステップでは、生成した解があ
らかじめ設定した解の評価項目をどの程度充足している
かをチェックして、項目の違反件数と違反内容に応じた
ペナルティから減点法で評価値を与える。本実施例で用
いる解評価項目の例を図４０に示す。この解評価項目に
対する項目の削除・追加や、違反時のペナルティの調整
は容易にできる。図４１のフローチャートを参照しなが
ら解の評価処理の詳細を説明する。

【００８４】まずステップ４１０１において項目番号ｍ
を初期化する。ステップ４１０２では処理の終了判定を
おこない、項目番号ｍが解の評価項目数を超えた場合に
は処理を終了する。処理を終了しない場合にはステップ
４１０３に進み、得点ｐに規定の最高得点を格納する。
ステップ４１０４では評価項目ｍに対する解の充足度を
判定し、項目に違反した件数を記憶しておく。ステップ
４１０５において得点ｐから式、「違反件数×評価項目
ｍのペナルティ」により算出した得点を引く。ステップ
４１０６で項目番号ｍの値を１増やして終了判定ステッ
プ４１０２へ戻る。

【００８５】以上で図１６の解探索処理の詳細説明を終
える。本発明の基本構成（図１）に示されるデータと処
理と装置の本実施例における具体化についての説明を続
ける。図１の解０１１３は、図１６のフローチャートに
基づいて説明した解探索処理で得られる全ての仕事（編
成）に対する操作シーケンスである。そのデータ構造は
図９で示した。

【００８６】本実施例では、図１ステップ０１１４にお
ける解の表示とオペレータの操作処理において、解を表
示装置０１１６に表示し、入力装置０１１５からオペレ
ータによる操作を受け付ける。オペレータは、図７の仕
事データ、図１３の資源属性テーブル、図１４の接続判
定テーブル、図１５の解探索パラメータ、図２７の順序
制約式、図４０の解評価項目を表示装置に出力させてそ
れらを編集し、編集されたデータを用いて図１６の解探
索処理の実行を再び指示することができる。オペレータ
によって承認を受けた解は、正式な車両入換計画として
登録され、実務フォーマットに変換された上でプリンタ
０１１７から出力される。

【００８７】

【発明の効果】【図面の簡単な説明】

【図１】本発明の基本構成である。

【図２】操作手順に関する制約の説明図である。

【図３】ガントチャートの例である。

【図４】車両入換計画表の例である。

【図５】車両基地レイアウトの例である。

【図６】車両入換ダイヤの例である。

【図７】本実施例における仕事データのデータ構造であ
る。

【図８】本実施例における操作データのデータ構造であ
る。

【図９】本実施例における操作シーケンスのデータ構造
である。

【図１０】本実施例における操作手順に関する制約の説
明図である。

【図１１】操作シーケンステンプレートのデータ構造で
ある。

【図１２】操作シーケンステンプレート生成処理フロー
である。

【図１３】資源属性テーブルのデータ構造である。

【図１４】接続判定テーブルのデータ構造である。

【図１５】本実施例における解探索パラメータの説明図
である。

【図１６】本実施例における解探索処理フローである。

【図１７】資源割当テーブルのデータ構造である。

【図１８】資源割当テーブルの初期化処理フローであ
る。

【図１９】操作シーケンステンプレートの最悪パターン
に資源を割り当てる処理のフローである。

【図２０】子染色体の生成処理フローである。

【図２１】親染色体から子染色体の操作シーケンステン
プレートの最悪経路を生成する処理のフローである。

【図２２】突然変異処理フローである。

【図２３】操作シーケンステンプレートの最悪経路に対
する突然変異処理フローである。

【図２４】操作シーケンスの生成処理フローである。

【図２５】本実施例におけるガントチャートのデータ構
造である。

【図２６】操作シーケンスの初期化処理フローである。

【図２７】本実施例における順序制約式のデータ構造で
ある。

【図２８】順序制約違反操作対の説明図である。

【図２９】順序制約違反の解消処理フローである。

【図３０】最も早い順序制約違反の解消処理フローであ
る。

【図３１】操作のシフトと空き時間帯の調整処理であ
る。

【図３２】操作のシフト処理の説明図である。

【図３３】留置番線への転線操作系列の挿入処理の説明
図である。

【図３４】資源競合操作対のデータ構造である。

【図３５】資源競合操作対集合生成処理フローである。

【図３６】資源競合操作対生成処理フローである。

【図３７】最も早い資源競合の解消処理フローである。

【図３８】ある操作の前方に生じた資源競合の解消処理
フローである。

【図３９】ある操作の前方の全ての処理に関する資源競
合操作対の生成処理フローである。

【図４０】本実施例における解評価項目の説明図であ
る。

【図４１】解の評価処理フローである。

【符号の説明】

０１０１…仕事データ、０１０２…資源に関する制約、
０１０３…操作手順に関する制約の生成、０１０４…操
作手順に関する制約、０１０５…解探索処理、０１０６
…資源割当の確率的調整、０１０７…資源競合の解消、
０１０８…解候補の評価、０１０９…評価値の
フィードバック、０１１１…作業の順序に関する制約、
０１１２…解評価項目、０１１３…解、０１１４…解の
表示とオペレータの操作、０１１５…入力装置、０１１
６…表示装置、０１１７…プリンタ。

Claims

【特許請求の範囲】

【請求項１】操作集合Ｏは、必須操作集合Ｗと補助操作
集合ＶからＯ≡Ｗ∪Ｖと構成される順序関係≦を持つ半
順序集合で、要素ｏｐは資源集合Ｒの要素である資源ｒ
と時刻集合Ｔの要素である開始時刻ｓtと時刻集合Ｔの
要素である終了時刻ｆtを属性として持ち、仕事Ｊi（ｉ
＝１，２，・・・）は、Ｊi⊂Ｗである全順序部分集合
で、全ての要素の属性が未割当で、Ｊ₁∩Ｊ₂∩・・・＝
φであり、仕事ＪiのスケジュールＳiは、Ｊi⊂Ｓi⊂Ｏ
である全順序部分集合で、全ての要素の属性が割当済み
で、Ｓ₁∩Ｓ₂∩・・・＝φであり、与えられた全ての仕
事のスケジュールＳall≡Ｓ₁∪Ｓ₂∪・・・を作成する
情報処理装置を利用するスケジューリング方法であっ
て、（１）入力された仕事データから、各仕事が使用可能な
操作と操作間の順序を示す操作手順に関する制約を、操
作を節点とする有向ネットワークとして生成するステッ
プと、（２）操作の資源割当の組合せを確率的に調整す
るステップと、（３）操作の必要資源の時間的競合を解
消して全ての仕事のスケジュールの解候補を作成するス
テップと、（４）ステップ（３）の実行により得られた
解候補を評価して評価値を算出するステップと、（５）
ステップ（４）の実行により得られた評価値を上記の資
源割当の確率的調整ステップにフィードバックするステ
ップと、（６）解候補の最適解探索処理を上記のステッ
プ（２）〜（５）をを繰り返すことにより行なうステッ
プと、（７）最適化の結果得られた全ての仕事のスケジ
ュールを表す解を表示してオペレータが編集するステッ
プとを有することを特徴とするスケジューリング方法。
【請求項２】請求項１において、ステップ（２）は、前
記操作手順に関する制約の各節点の資源の割当状況を全
ての仕事について示す染色体を、資源の属性と資源間の
関係を示す資源に関する制約を充足させつつ解探索パラ
メータに設定された個数作成することを特徴とする請求
項１項記載のスケジューリング方法。
【請求項３】請求項１において、ステップ（２）は、染
色体に与えられた評価値に基づいて、染色体に少なくと
も自然淘汰処理、交叉処理、突然変異処理を含む遺伝的
操作を施して、操作手順に関する制約の各節点の資源の
割当状況が異なる新たな染色体データを作成することを
特徴とする請求項１項記載のスケジューリング方法。
【請求項４】請求項３において、前記交叉処理は、ラン
ダムに選択された２個の染色体の同一節点の資源の割当
状況からどちらか一方を選択して新しい染色体の同一節
点に設定することを特徴とする請求項１項記載のスケジ
ューリング方法。
【請求項５】請求項４において、ランダムに選択された
２個の染色体の同一節点の資源の割当状況からどちらか
一方を選択する際には、資源に関する制約を充足する資
源の割当状況を選択し、どちらも資源に関する制約を充
足する場合には、評価値の高い染色体データの資源の割
当状況を継承する可能性が、その評価値の相対的な高さ
の程度を反映するように動的に決定された確率に従って
選択をおこなうことを特徴とする請求項１項記載のスケ
ジューリング方法。
【請求項６】請求項３において、前記突然変異処理は、
染色体の一部の節点の資源の割当状況を、資源に関する
制約に違反しない限りにおいて確率的に変更することを
特徴とする請求項１項記載のスケジューリング方法。
【請求項７】請求項１において、ステップ（３）は、
（ａ）各仕事に対して操作手順と、各操作の使用資源
と、各操作の処理時間を示す操作シーケンスを作成し、
全ての操作シーケンスについて作業の順序に関する制約
の充足処理を施して各仕事のスケジュールとする各仕事
のスケジュールの初期化サブステップと、（ｂ）（ａ）
の実行により得られた全ての仕事のスケジュールの解候
補から、使用資源の時間的競合を起こす操作対を選択し
て資源競合を解消するサブステップを有することを特徴
とする請求項１項記載のスケジューリング方法。
【請求項８】請求項７において、サブステップ（ａ）
は、各仕事の操作手順を操作手順に関する制約から選択
し、各操作の使用資源を染色体から得た資源の割当状況
に基づき割り当てることを特徴とする請求項１項記載の
スケジューリング方法。
【請求項９】請求項７において、サブステップ（ａ）
は、作業操作の開始時刻と作業操作の終了時刻と定数か
らなる不等式または等式である順序制約式を作業の順序
に関する制約として、順序制約式に含まれるいずれかの
操作の開始時刻と終了時刻を時間後方へずらすことによ
り作業の順序に関する制約を充足することを特徴とする
請求項１項記載のスケジューリング方法。
【請求項１０】請求項７において、サブステップ（ｂ）
は、使用資源の時間的競合を起こす操作対に対して２つ
の操作の一方を選択して、選択した操作の開始時刻と終
了時刻を時間後方へずらす処理により使用資源の時間的
競合を解消することを特徴とする請求項１項記載のスケ
ジューリング方法。
【請求項１１】請求項１０において、開始時刻と終了時
刻を時間後方へずらされた操作と、該操作の時間前方に
存在する同一の仕事のスケジュールに含まれる操作との
間に生じた空き時間を、（１）操作の終了時刻の延長、
（２）操作手順の部分変更、のいずれかにより調整する
ことを特徴とする請求項１項記載のスケジューリング方
法。
【請求項１２】請求項１０において、２つの操作の一方
を選択する場合には、開始時刻と終了時刻を時間後方へ
ずらすことにより新たな順序制約式違反を生じない操作
を選択することを特徴とする請求項１項記載のスケジュ
ーリング方法。
【請求項１３】請求項１において、ステップ（４）は、
所定の制約条件から作成された解評価項目の充足の程度
に応じて解候補の各々の評価値を算出することを特徴と
する請求項１項記載のスケジューリング方法。
【請求項１４】請求項１において、ステップ（５）は、
前記ステップ（４）で算出した評価値を、解候補を作成
する際に使用した染色体に与えることを特徴とする請求
項１項記載のスケジューリング方法。
【請求項１５】請求項１において、ステップ（５）は、
オペレータが入力装置を用いて、仕事データ、資源に関
する制約、解探索パラメータ、作業の順序に関する制
約、解評価項目を修正し、解探索の再実行を指示するこ
とを特徴とする請求項１項記載のスケジューリング方
法。
【請求項１６】操作集合Ｏは、必須操作集合Ｗと補助操
作集合ＶからＯ≡Ｗ∪Ｖと構成される順序関係≦を持つ
半順序集合で、要素ｏpは資源集合Ｒの要素である資源
ｒと時刻集合Ｔの要素である開始時刻ｓtと時刻集合Ｔ
の要素である終了時刻ｆtを属性として持ち、仕事Ｊi
（ｉ＝１，２，・・・）は、Ｊi⊂Ｗである全順序部分
集合で、全ての要素の属性が未割当で、Ｊ₁∩Ｊ₂∩・・
・＝φであり、仕事ＪiのスケジュールＳiは、Ｊi⊂Ｓi
⊂Ｏである全順序部分集合で、全ての要素の属性が割当
済みで、Ｓ₁∩Ｓ₂∩・・・＝φであり、与えられた全て
の仕事のスケジュールＳall≡Ｓ₁∪Ｓ₂∪・・・を作成
する情報処理装置を利用するスケジューリング装置であ
って、（１）入力された仕事データから、各仕事が使用可能な
操作と操作間の順序を示す操作手順に関する制約を、操
作を節点とする有向ネットワークとして生成する手段
と、（２）操作の資源割当の組合せを確率的に調整する
手段と、（３）操作の必要資源の時間的競合を解消して
全ての仕事のスケジュールの解候補を作成する手段と、
（４）手段（３）の実行により得られた解候補を評価し
て評価値を算出する手段と、（５）手段（４）の実行に
より得られた評価値を上記の資源割当の確率的調整手段
にフィードバックする手段と、（６）解候補の最適解探
索処理を上記の手段（２）〜（５）をを繰り返すことに
より行なう手段と、（７）最適化の結果得られた全ての
仕事のスケジュールを表す解を表示してオペレータが編
集する手段とを有することを特徴とするスケジューリン
グ装置。