(57)【要約】【課題】生産計画に適用できるスケジューリング問題処理方法に関し、実際的な処理時間で効率的に最短時間の仕事順序を取得できる処理方法を提供する。【解決手段】データ受付手段１１は仕事とそのコスト含むデータを受け付け、マスタマトリクス作成手段１２は全仕事数を行数および列数としコストをセル値とするマスタマトリクスＭ０を作成し、ワークマトリクス作成手段１３はマスタマトリクスＭ０と同一のワークマトリクスＭ１、Ｍ２を作成する。条件チェック手段１４は、マスタマトリクスＭ０から所定のセル値を抽出・複写したワークマトリクスＭ１が、巡回路成立の第１条件を満たせば、ワークマトリクスＭ１のセル値から当該仕事に後続および前置する仕事を設定したワークマトリクスＭ２が巡回路成立の第２条件を満たすか否かを判定し、第２条件を満たすワークマトリクスＭ２の前置および後続の仕事のセル位置をもとに仕事順序を決定する。【選択図】　　　　　図８
2004086648.tif 000002
【特許請求の範囲】
【請求項１】
複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理方法において、
仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付ける処理ステップと、
全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成する処理ステップと、
前記マスタマトリクスを記憶する処理ステップと、
前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成する処理ステップと、
前記第１ワークマトリクスを記憶する処理ステップと、
前記第２ワークマトリクスを記憶する処理ステップと、
前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写する処理ステップと、
セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでない場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定する処理ステップと、
前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含する場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定する処理ステップとを備える
ことを特徴とするスケジューリング問題処理方法。
【請求項２】
請求項１に記載のスケジューリング問題処理方法において、
前記データを受け付ける処理ステップは、さらに、前記移行コストに関するコスト制約を受け付け、
前記マスタマトリクスを作成する処理ステップは、前記コスト制約を参照して、前記マスタマトリクスの該当するセル値を増加させる
ことを特徴とするスケジューリング問題処理方法。
【請求項３】
請求項１に記載のスケジューリング問題処理方法において、
前記データを受け付ける処理ステップは、さらに、前記仕事と前記仕事の後続仕事との経路確定を受け付け、
前記マスタマトリクスを作成する処理ステップは、前記経路確定を参照して、前記マスタマトリクスの該当するセル値を減少させる
ことを特徴とするスケジューリング問題処理方法。
【請求項４】
複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理を実現する処理ステップをコンピュータに実行させるための処理プログラムであって、
仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付ける処理ステップと、
全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成する処理ステップと、
前記マスタマトリクスを記憶する処理ステップと、
前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成する処理ステップと、
前記第１ワークマトリクスを記憶する処理ステップと、
前記第２ワークマトリクスを記憶する処理ステップと、
前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写する処理ステップと、
セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでない場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定する処理ステップと、
前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含する場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定する処理ステップとを、
コンピュータに実行させる
ことを特徴とするスケジューリング問題処理プログラム。
【請求項５】
複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理装置において、
仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付けるデータ受付手段と、
全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成するマスタマトリクス作成手段と、
前記マスタマトリクスを記憶するマスタマトリクス記憶手段と、
前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成するワークマトリクス作成手段と、
前記第１ワークマトリクスを記憶する第１ワークマトリクス記憶手段と、
前記第２ワークマトリクスを記憶する第２ワークマトリクス記憶手段と、
前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写するセル値設定処理手段と、
セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでないという第１条件を満たすか否かを判定する第１条件チェック手段と、
前記第１条件を満たす場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定し、前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含するという第２条件を満たすか否かを判定する第２条件チェック手段と、
前記第２条件を満たす場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定するスケジュール決定手段とを備える
ことを特徴とするスケジューリング問題処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、生産計画、配送計画などに適用できるスケジューリング問題をコンピュータを用いて効率的に処理するためのスケジューリング問題処理方法、スケジューリング問題処理プログラム、およびスケジューリング問題処理装置に関する。
【０００２】
【従来の技術】
スケジューリング問題とは、例えば生産計画において、複数の仕事が与えられていて、それぞれ次の仕事にとりかかるまでの準備時間（段取り替え時間）が必要だとする場合に、全ての仕事についての作業時間の総和が最小に近くなるように仕事の順序を求める問題である。
【０００３】
生産計画や配送計画に適用されるスケジューリング問題は、仕事や品目を巡回すべき拠点および各仕事間の準備時間を拠点間の移動時間と想定することができ、平面に散在する拠点を一巡する経路のなかで最短経路を探索する巡回セールスマン問題と本質的に同等である。
【０００４】
【発明が解決しようとする課題】
巡回セールスマン問題での一巡する経路の数は、Ｎ個の拠点に対して（Ｎ−１）！だけ存在するため、すべての可能性を検討しようとすると仕事数の増加に伴い仕事の組み合わせの計算量が爆発的に増加するため、コンピュータを利用しても実用的な時間では処理できず最適解を得ることは困難である。
【０００５】
したがって、スケジューリング問題においても、例えば生産計画に適用する場合には、「重要な顧客の注文を優先して立案する」などの経験則を用いて組み合わせを制限して処理時間が実用的な時間となるように対処して解を求めていたが、かかる処理で得られる解は必ずしも最適解ではないこともあった。
【０００６】
本発明の目的は、実用的な処理時間で最適解を求めることが可能なスケジューリング問題処理方法を提供することである。
【０００７】
また、本発明の目的は、上記スケジューリング問題処理方法をコンピュータに実行させるためのプログラムを提供することである。
【０００８】
また、本発明の目的は、上記スケジューリング問題処理方法を実現する処理装置を提供することである。
【０００９】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理方法であって、仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付ける処理ステップと、全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成する処理ステップと、前記マスタマトリクスを記憶する処理ステップと、前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成する処理ステップと、前記第１ワークマトリクスを記憶する処理ステップと、前記第２ワークマトリクスを記憶する処理ステップと、前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写する処理ステップと、セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでない場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定する処理ステップと、前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含する場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定する処理ステップとを備える。
【００１０】
また、本発明は、複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理装置であって、仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付けるデータ受付手段と、全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成するマスタマトリクス作成手段と、前記マスタマトリクスを記憶するマスタマトリクス記憶手段と、前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成するワークマトリクス作成手段と、前記第１ワークマトリクスを記憶する第１ワークマトリクス記憶手段と、前記第２ワークマトリクスを記憶する第２ワークマトリクス記憶手段と、前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写するセル値設定処理手段と、セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでないという第１条件を満たすか否かを判定する第１条件チェック手段と、前記第１条件を満たす場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定し、前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含するという第２条件を満たすか否かを判定する第２条件チェック手段と、前記第２条件を満たす場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定するスケジュール決定手段とを備える。
【００１１】
まず、本発明の原理を説明する。なお、スケジューリング問題における工程群および各工程間の段取り替え時間は、巡回セールスマン問題における拠点群および各拠点間の移動時間（移動コスト）に相当するので、以下では、工程を拠点と、段取り替え時間を移動コストとし、スケジューリング問題を巡回セールスマン問題に置き換えて説明する。
【００１２】
本発明は、処理対象となる拠点および各拠点間の移動コストをマトリクス形式で格納しておく。そして、マトリクス内で移動コストの値が小さいセルに着目し、所定の基準値より小さい値を持つセルで再構成したマトリクスを解析して巡回路が成立する条件を満たすか否かを判定し、巡回路成立の条件を満たす場合に当該マトリクスが示す順序に従って拠点を抽出して巡回路を決定していくものである。
【００１３】
図１に、本発明で用いる拠点および拠点間の移動コストを表したマトリクスの例を示す。図１のマトリクスｍ１は、Ａ、Ｂ、Ｃ、Ｄ、Ｅの５つの拠点を巡回する問題を示し、各セルの値は拠点間の移動時間（移動コスト）を示す。
【００１４】
マトリクスｍ１において、縦の列（Ｆｒｏｍ列）は、自拠点から他拠点へ行くことを意味し、各セル値は、当該列に対応する拠点から各行に対応する他拠点への移動コストを示す。また、横の行（Ｔｏ行）は、他拠点から当該行に対応する拠点へ来ることを意味する。例えば、Ｆｒｏｍ列の拠点Ａ（最左列）に着目すると、拠点Ａから拠点Ｃへの移動（Ａ→Ｃ）にかかる移動コストは３であり、拠点Ａから拠点Ｄへ（Ａ→Ｄ）の移動コストは１であり、拠点Ａから拠点Ｅへ（Ａ→Ｅ）の移動コストは３であることを示す。また、拠点Ａから拠点Ｂへ（Ａ→Ｂ）の移動コスト＝０とは、Ａ→Ｂの移動コストは無視できることを意味する。
【００１５】
また、マトリクスｍ１では、Ａ→Ｅの移動とＥ→Ａの移動の場合のように、移動方向によって移動コストが異なる状態を設定することも可能である。さらに、Ｆｒｏｍ列の拠点Ｅ（最右列）で、拠点Ｅから拠点Ａへ（Ｅ→Ａ）の移動コストを示すセル値が「×」であるとは、Ｅ→Ａの移動は不可能であることを表している。
【００１６】
図２〜図７を用いて、巡回路が成立する場合のマトリクスのマッピング位置のパターンについて説明する。
【００１７】
図２に、Ａ→Ｂ→Ｃ→Ｄ→Ｅという巡回路のみの移動コストを表すマトリクスの例を示す。図２のマトリクスｍ２では、Ａ→Ｂの移動コスト＝０、Ｂ→Ｃの移動コスト＝５、Ｃ→Ｄの移動コスト＝１、Ｄ→Ｅの移動コスト＝１であることを表している。Ｎｒは、Ｆｒｏｍ列の各拠点のセル値を持つセル（行）の数を示し、Ｎｃは、Ｔｏ行の各拠点のセル値を持つセル（列）の数を示す。
【００１８】
マトリクスｍ２では、Ｆｒｏｍ列の拠点ＥのＮｒが０であり、拠点Ｅがどの拠点へも行くことができない拠点すなわち出発拠点になりえない拠点であることがわかる。また、Ｔｏ行の拠点ＡのＮｃが０であり、拠点Ａがどの拠点からも到着できない拠点すなわち到着拠点になりえない拠点であることがわかる。
【００１９】
そして、マトリクスｍ２のＦｒｏｍ列に着目すると、ある拠点について値を持つセルが少なくとも１つあれば（Ｎｒが０でなければ）、その拠点は他の拠点への出発拠点となりえることがわかる。また、Ｔｏ行に着目すると、ある拠点について値を持つセルが少なくとも１つあれば（Ｎｃが０でなければ）、その拠点は他の拠点からの到着拠点となりえることがわかる。
【００２０】
このように、Ａ→Ｂ→Ｃ→Ｄ→Ｅという巡回路のみが存在するマトリクスｍ２のＦｒｏｍ列（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）のＮｒの配列は、「１、１、１、１、０」となり、Ｔｏ行（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）のＮｃの配列は、「０、１、１、１、１」となる。
【００２１】
したがって、ｎ拠点を巡回するための巡回路が成立するためには、以下の条件を満たす必要があることになる。
１）出発拠点がｎ−１以上必要であり、
２）到着拠点もｎ−１以上必要であり、
３）出発拠点でも到着拠点でもない拠点が存在してはならない。
【００２２】
上記１）〜３）を換言すると、「値のない列が２列以上なくかつ値のない行が２行以上ないこと、および、値のない行が１であってかつ値のない列が１である場合に、その行および列が同じ拠点でないこと」という条件になる。この条件を第１条件とする。
【００２３】
さらに、マトリクスが前記第１条件を満たす場合に常に巡回路が成立するか否かを検証する。図３（Ａ）に別のマトリクスの例を示し、図３（Ｂ）に、当該マトリクスが表す経路を示す。
【００２４】
図３（Ａ）のマトリクスｍ３は、出発拠点および到着拠点となる拠点がｎ−１あり、出発拠点または到着拠点のいずれにもなりえない拠点は存在しないので、前記第１条件を満たすものである。
【００２５】
ここで、マトリクスｍ３のＦｒｏｍ列の拠点ＣとＴｏ行の拠点Ｄとのセルに着目すると、Ｃ→Ｄへの移動コストであるセル値は１であり、Ｃ→Ｄの経路は存在する。しかし、Ｆｒｏｍ列の拠点ＤとＴｏ行の拠点Ｃとのセルには値が存在していない。これにより、経路Ｃ→Ｄはあるが、拠点Ｄがどの出発拠点にもならずかつ拠点Ｃがどの拠点からも到着拠点にならない場合には、図３（Ｂ）に示すように、経路Ａ→Ｂ→Ｅと経路Ｃ→Ｄとが分離して巡回路が成立しないことを意味する。
【００２６】
そこで、マトリクスが巡回路成立を表現するためにさらに必要な条件を検討する。図４に、巡回路Ａ→Ｂ→Ｃ→Ｄ→Ｅを示す。巡回路の５拠点のうち、出発拠点かつ到着拠点である拠点は、拠点Ｂ、ＣおよびＤの３拠点である。一方、図３（Ｂ）の経路では、出発拠点かつ到着拠点である拠点は、同様に、拠点Ａ、ＢおよびＥの３拠点であるが、経路がＥ→Ａ→Ｂ、Ａ→Ｂ→Ｅ、またはＢ→Ｅ→Ａとなっており、同じ条件では３拠点（Ａ、ＢおよびＥ）しか経由しておらず、全ての拠点を経由していない。
【００２７】
よって、巡回路が成立するためには以下の第２条件をも満たす必要がある。
４）出発拠点かつ到着拠点でもある拠点で、それらの拠点の出発元となる拠点または到着先となる拠点の集合がすべての拠点を包含している。
【００２８】
さらに、第１条件および第２条件を満たす経路を表すマトリクス上の表現について検討する。
【００２９】
図５（Ａ）に別のマトリクスの例を示す。図５（Ａ）のマトリクスｍ４では、出発拠点かつ到着拠点でもある拠点は、拠点Ｂ、ＣおよびＤの３拠点である。また、拠点Ｂの出発元が拠点Ａであり到着先が拠点Ｅであり、拠点Ｃの出発元が拠点Ｂで到着先が拠点Ｄであり、拠点Ｄの出発元が拠点Ａであり到着先が拠点Ｃである。よって、マトリクスｍ４は、前記第２条件を満たしていることになる。
【００３０】
しかし、実際には、マトリクスｍ４が表す経路は、図５（Ｂ）に示すように、順回路にならない。これは、マトリクスｍ４は、経路Ｃ→Ｄおよびその逆経路Ｄ→Ｃの２経路が存在することを表しているが、この２経路が１つの巡回路として両立しないために、マトリクスｍ４が実質的には前記第２条件を満たしていないことになるからである。したがって、実質的に第２条件を満たしていないにもかかわらずマトリクス上で第２条件を満たすことになるような表現を排除する必要がある。
【００３１】
本発明では、双方向の経路がマトリクス上での線対称上の位置で表現することができることから、マトリクス上で逆経路を持つ経路が現れるように出発元および到着先を区別して表すことができるマトリクスを採用する。すなわち、マトリクス上である拠点に着目した場合に、当該着目拠点のＦｒｏｍ列で、着目拠点への出発元となる他の拠点に対応するＴｏ行と交わるセルに「出発元」を設定し、着目拠点から到着先となる他の拠点に対応するＴｏ行と交わるセルに「到着先」を設定する。
【００３２】
図６に、出発元および到着先を表すマトリクスの例を示す。図６のマトリクスｍ５は、前記の図３（Ｂ）に示す経路の出発元および到着先を表したマトリクスである。図３（Ｂ）の拠点Ａ、ＢおよびＥからなる経路において、拠点Ａからみると、拠点Ｂはその到着先であり、拠点Ｅはその出発元である。
【００３３】
図３（Ａ）に示すマトリクスｍ３と同じ大きさの２次元配列であるマトリクスｍ５を用意し、Ｆｒｏｍ列の拠点Ａの列において、Ｔｏ行の拠点Ｂの行と交わるセルに「到着先（値＝０）」を設定し、Ｔｏ行の拠点Ｅの行と交わるセルに「出発元（値＝１）」を設定する。なお、図の中で、「到着先（値＝０）」は、白丸（○）で示し、「出発元（値＝１）」は、黒丸（●）で示す。
【００３４】
そして、マトリクスｍ５の到着先および出発元の表現から、以下について確認することができる。
ａ）マトリクスｍ５の斜線を軸として到着先（白丸）と出発元（黒丸）とは対称位置となる、
ｂ）１の列または行に到着先（白丸）および出発元（黒丸）の両方が存在する場合に、その拠点は出発拠点かつ到着拠点である。マトリクスｍ５では、拠点Ａ、ＢおよびＥの列がこれに該当する、
ｃ）Ｆｒｏｍ列の拠点Ａ、Ｂ、Ｅにおいて、到着先（白丸）および出発元（黒丸）になっている他の拠点は、拠点Ａ、ＢおよびＥのみであり全拠点を包含していない。
【００３５】
また、経路とその逆経路とを重複して持ち、拠点同士が相互に到着先もしくは出発元となる関係であるような経路（以下、逆経路とする）について説明する。逆経路は、マトリクス上では、図７（Ａ）に示すようなマトリクスとして表現される。図７（Ａ）に示すマトリクスｍ６において、図７（Ｂ）のような逆経路Ｃ←→Ｄは、斜線を軸とした対称位置のセルそれぞれに到着先（白丸）が設定されて表現されることになる。
【００３６】
そして、マトリクス上で拠点同士の到着先（または出発元）が相互に対称位置にある場合には、それらの拠点が逆経路の関係であるため、拠点包含チェックができないことがわかる。そこで、巡回路成立の条件をチェックの際には、マトリクス上でかかる逆経路を示す位置関係を調整する必要があることがわかる。
【００３７】
以上説明したように、巡回セールスマン問題を処理する際には、マトリクスで表現した問題に対して第１条件および第２条件による判定処理と逆経路の調整処理とを行う必要がある。
【００３８】
そこで、本発明は、以下のように作用する。
【００３９】
本発明は、仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付け、全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成して記憶しておく。また、前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成して記憶しておく。
【００４０】
そして、前記マスタマトリクスから所定の基準値（初期値は最小値）以下のセル値を抽出して前記第１ワークマトリクスに複写し、セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでないという第１条件を満たすかどうか判定し、前記第１条件を満たす場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定する。さらに、前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含するという第２条件を満たすかどうかを判定し、前記第２条件を満たす場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定する。
【００４１】
すなわち、本発明では、処理するスケジューリング問題を表すマスタマトリクス（図１参照）から所定の基準値（コスト基準値）より小さい移動コスト値のみをコピーして作成した第１ワークマトリクスをもとに第１条件を参照して判定する。さらに第１条件を満たす第１ワークマトリクスを解析して作成した各拠点の到着先（白丸）および出発元（黒丸）を示す第２ワークマトリクス（図６参照）をもとに第２条件を参照して判定し、巡回路が成立するこれらの条件を満たす第２ワークマトリクスのみを利用して、第２ワークマトリクスに現れた到着先および出発元のパターンに従って各拠点を抽出し巡回路を決定する。
【００４２】
また、巡回路が成立しない場合には、最小値から所定分だけ加算したコスト基準値をもとに、マスタマトリクスから次に大きな値のセル値を第１ワークマトリクスに追加コピーする。そして、セル値を追加コピーした第１ワークマトリクスをもとに作成した第２ワークマトリクスで巡回路が成立するまで処理を繰り返していく。
【００４３】
このように、本発明は、拠点および移動コストをマトリクス形式で管理し、問題を表すマトリクス上で移動コストが小さい経路だけに着目することにより、巡回路数を制限し、最適解を取得するまでの処理時間を短縮化することを可能とする。
【００４４】
また、本発明は、作成する巡経路を限定し、マトリクス上に表現されたパターンそのものにもとづいて巡回路成立可否の判断を行うことにより、実用的な処理時間で最適解を求めることを可能とする。
【００４５】
なお、特開平５−０４６５９１「客の動線解析方法」のように、巡回セールスマン問題を解く際に、各地点間の移動時間をマトリクスで表現し行列を作成する手法が知られている。しかし、この方法では、巡回セールスマン問題を解く際に参照する値を内部的にマトリクス状にまとめているにすぎず、本発明のように、マトリクスそのものを用いて処理時間を軽減するものではない。
【００４６】
【発明の実施の形態】
図８に、本発明の実施の形態におけるシステム構成例を示す。本発明にかかるスケジューリング問題処理装置１は、データ受付手段１１、マスタマトリクス作成手段１２、ワークマトリクス作成手段１３、条件チェック手段１４、およびスケジュール決定手段１５からなる。
【００４７】
データ受付手段１１は、入力手段２を通じて、スケジューリング問題の工程（拠点）と、その工程から次の工程を開始するまでに必要な段取り替え時間（移動コスト）を含むデータを受け付ける手段である。
【００４８】
また、データ受付手段１１は、問題に対する時間制約などの条件がある場合には、それらの条件を受け付ける。時間制約は、処理対象のスケジュールがある条件で実施などされる場合に移動コストに加算もしくは減算される時間をいう。
【００４９】
マスタマトリクス作成手段１２は、データ受付手段１１が受け付けた拠点および移動コストのデータをもとに、全拠点数の行数および列数からなる２次元配列を作成し、各拠点間の移動コストをセル値とするマスタマトリクスＭ０を作成する手段である。マスタマトリクスＭ０は、前記図１に示すマトリクスと同様である。マスタマトリクスＭ０の各セルには各拠点間の移動コストが設定される。
【００５０】
また、マスタマトリクス作成手段１２は、データ受付手段１１が受け付けた時間制約などの条件を参照してマスタマトリクスＭ０のセル値を変更する。
【００５１】
ワークマトリクス作成手段１３は、マスタマトリクスＭ０と同一の列および行からなり、セル値が設定されていないワークマトリクスＭ１ならびにワークマトリクスＭ２を作成する手段である。
【００５２】
条件チェック手段１４は、所定のコスト基準値にしたがってマスタマトリクスＭ０のセル値（移動コスト）のうち所定値以下のセル値を選択し、ワークマトリクスＭ１にコピーし、ワークマトリクスＭ１を解析して第１条件を満たすか否かをチェックし、さらに、第１条件を満たすワークマトリクスＭ１をもとに各拠点の到着先および出発元をワークマトリクスＭ２に設定し、ワークマトリクスＭ２を解析して第２条件を満たすか否かをチェックする手段である。
【００５３】
条件チェック手段１４は、セル値設定部１４１、第１条件チェック部１４２、および第２条件チェック部１４３を備える。
【００５４】
セル値設定部１４１は、マスタマトリクスＭ０のセル値のうち、所定のコスト基準値以下のセル値をワークマトリクスＭ１にコピーする手段である。図９に、前記図１に示すマトリクスｍ１をマスタマトリクスＭ０とする場合に、コスト基準値＝０のときに、セル値をコピーしたワークマトリクスＭ１の例を示す。マスタマトリクスＭ０の３箇所のセル値（＝０）は、ワークマトリクスＭ１の同じ位置のセルへコピーされる。
【００５５】
また、セル値設定部１４１は、コスト基準値の初期値を移動コストの最小値とし、第１条件チェック部１４２または第２条件チェック部１４３から条件チェックＮＧが通知されると、コスト基準値を所定の値ずつ増加させて、マスタマトリクスＭ０のセル値のうち、該当するセル値をワークマトリクスＭ１にコピーする。
【００５６】
第１条件チェック部１４２は、所定のコスト基準値以下のセル値がコピーされたワークマトリクスＭ１が、所定の第１条件を満たすか否かをチェックする手段である。第１条件は、巡回路が成立するための前提条件であって、「全拠点数がｎである場合に、出発拠点、到着拠点がｎ−１であり、出発も到着もしない拠点が０であること」を内容とする。第１条件チェック部１４２は、ワークマトリクスＭ１が第１条件を満たす場合にはチェックＯＫを送出し、満たさない場合にはチェックＮＧを送出する。
【００５７】
第２条件チェック部１４３は、第１条件を満たすワークマトリクスＭ１を参照して、各拠点の到着先（値＝０）および出発元（値＝１）をワークマトリクスＭ２に設定し、ワークマトリクスＭ２上に設定された到着先および出発元からなるパターンが第２条件を満たすか否かをチェックする手段である。第２条件とは、巡回路が成立するための条件であって、「全拠点数がｎである場合に、出発拠点でもあり到着拠点でもある拠点がｎ−２あり、かつ、そのｎ−２の拠点の出発元となる拠点および到着先となる拠点の集合が全拠点を包含すること」を内容とする。
【００５８】
図１０に、図９に示すワークマトリクスＭ１の到着先を設定したワークマトリクスＭ２の例を示す。第２条件チェック部１４３は、ワークマトリクスＭ１のセル値に対応するワークマトリクスＭ２のセルに到着先を示す値＝０（白丸）を設定する。
【００５９】
さらに、ワークマトリクスＭ２の到着先を設定したセルと斜線を軸として線対称に位置するセルに出発元を示す値＝１（黒丸）を設定し、到着先と出発元との設定が重複する場合には到着先または出発元を調整して、調整後のワークマトリクスＭ２を用いて第２条件をチェックする。
【００６０】
スケジュール決定手段１５は、第２条件を満たすワークマトリクスＭ２上で設定された到着先および出発元を参照し、順に拠点を抽出して巡回路を決定する手段である。なお、決定した巡回路は、問題の解として出力手段３へ出力される。
【００６１】
以下、スケジューリング問題処理装置１の処理を具体的に説明する。
【００６２】
データ受付手段１１は、入力手段２から処理対象の問題の拠点および次の拠点への移動コスト、時間制約などのデータを受け付ける。そして、マスタマトリクス作成手段１２は、データ受付手段１１が受け付けたデータをもとに、全拠点を行および列とする２次元配列であって、移動コストをセル値とするマスタマトリクスＭ０を作成する。さらに、ワークマトリクス作成手段１３は、マスタマトリクスＭ０と同じ大きさのワークマトリクスＭ１およびワークマトリクスＭ２を作成する。
【００６３】
条件チェック手段１４のセル値設定部１４１は、セル値の最少値をコスト基準値とし、このコスト基準値をもとに該当するセル値（移動コスト）を抽出しワークマトリクスＭ１へコピーする。例えば、図１に示すマスタマトリクスＭ０において、コスト基準値が０（セル値の最小値）であれば、セル値設定部１４１は、値＝０のセル値を抽出してワークマトリクスＭ１にコピーする。図９に示すようなワークマトリクスＭ１が作成される。
【００６４】
次に、第１条件チェック部１４２は、図９に示すワークマトリクスＭ１が第１条件を満たすか否かをチェックする。ここで、図９に示すワークマトリクスＭ１は第１条件「値のない行が２行以上なく、かつ、値のない列が２列以上ないこと、および値のない行が１行ありかつ値のない列が１列ある場合に、その行および列が同じ拠点でないこと」を満たさないので、第１条件チェック部１４２は、チェックＮＧを送出する。
【００６５】
チェックＮＧを受けて、セル値設定部１４１は、コスト基準値を所定分だけ加算して、コスト基準値（＝１とする）をもとに、最少値の次に小さい値のセル値を抽出し、ワークマトリクスＭ１へ追加してコピーする。図１１に、セル値＝０、１がマッピングされたワークマトリクスＭ１を示す。ここで、第１条件チェック部１４２は、図１１に示すワークマトリクスＭ１が第１条件を満たすのでチェックＯＫを送出する。
【００６６】
チェックＯＫを受けて、第２条件チェック部１４３は、ワークマトリクスＭ１上でセル値を持つセル位置に対応するワークマトリクスＭ２のセルに、到着先である値＝０（白丸）を設定する。ここで、ワークマトリクスＭ２の列または行のいずれかに着目して、各拠点に値＝０（白丸）が設定されたセルが複数となる場合には、ワークマトリクスＭ１に設定されたセル値のうち、最小のセル値に対応するセルだけに値＝０を設定し、それ以外のセル値＝０（白丸）を削除する。
【００６７】
図１２に、図１１のワークマトリクスＭ１から作成したワークマトリクスＭ２であって、セル値＝０、１にもとづいて設定された到着先（白丸）および、セル値が最小でなく削除対象となる到着先（白丸に二重消し線で示す）を表したワークマトリクスＭ２を示す。
【００６８】
ここで、例えばＦｒｏｍ列の拠点Ａに着目すると、拠点Ｂの行および拠点Ｄの行との交点のセルにそれぞれ到着先（白丸）が設定されているが、拠点Ｂのセル値＝０、拠点Ｄのセル値＝１であるので（図１１参照）、拠点Ｄの到着先が削除の対象となる。また、Ｆｒｏｍ列の拠点Ｄに着目すると、拠点Ａの行および拠点Ｅの行の交点のセルに到着先（白丸）が設定されているが、いずれもセル値＝１であるので、両セルの到着先は削除の対象としない。
【００６９】
さらに、第２条件チェック部１４３は、到着先を設定したセルに着目（着目セル）し、その着目セルと斜線を軸として対称位置にあるセル（対称セル）に到着先が設定されていなければ、その対称セルに出発元である値＝１（黒丸）を設定する。一方、対称セルに到着先（白丸）が既に設定されていれば、対称セルに調整候補（値＝−１）を設定する。図１３に、到着先、出発元、および調整候補が設定されたワークマトリクスＭ２の例を示す。図１３では、到着先を白丸、出発元を黒丸、調整候補をハッチング白丸で示す。
【００７０】
第２条件チェック部１４３は、図１３に示すワークマトリクスＭ２を用いて、以下のような到着先および出発元の調整処理を行う。
【００７１】
まず、ワークマトリクスＭ２で、Ｆｒｏｍ列またはＴｏ行のいずれかに着目する。例えばＦｒｏｍ列に着目し、最初の拠点に対応する列について、その列で到着先が設定されたセルを着目セルとして、着目セルの対称位置にある対称セルに調整候補が設定されていれば、着目した列において既に到着先／出発元が確定したセルがあるかどうかを調べる。すでに確定したセルがある場合には、着目セルに既設定ではない値（到着先／出発元）を設定し、その対称セルに着目セルの設定ではない値を設定する。さらに、次の拠点に対応する列に着目して、同様の処理を行い、ワークマトリクスＭ２のすべての調整候補について調整を行う。
【００７２】
例えば、図１３のワークマトリクスＭ２のＦｒｏｍ列の拠点Ｂの列で、拠点Ｅの行との交点のセルを着目セルとする。拠点Ｂの列の拠点Ａの行との交点セルは出発元（黒丸）が既に確定しているので、着目セルには到着先（白丸）を設定し、その対称セル（拠点Ｅの列と拠点Ｂの行との交点セル）には、出発元（黒丸）が設定される。
【００７３】
同様に、拠点Ｄの列の拠点Ｅの行との交点セルを着目セルとすると、拠点Ｄの列と拠点Ａの行との交点セルは到着先（白丸）が確定しているので、着目セルには出発元（黒丸）が設定され、その対称セル（拠点Ｅの列と拠点Ｄの行との交点セル）には、到着先（白丸）が設定される。図１４に、セルの設定を調整した後のワークマトリクスＭ２を示す。
【００７４】
セル設定の調整後、第２条件チェック部１４３は、調整済みのワークマトリクスＭ２が第２条件「出発拠点でもあり到着拠点でもある拠点がｎ−２以上あり、それらの拠点の出発元の拠点または到着先の拠点の集合が全拠点を包含する」を満たすかどうかをチェックする。ここで、図１４のワークマトリクスＭ２は、第２条件を満たすのでチェックＯＫの通知を送出する。
【００７５】
スケジュール決定手段１５は、第２条件のチェックＯＫの通知を受け、ワークマトリクスＭ２のＦｒｏｍ列に着目して、到着先となる拠点しか存在しない列、すなわち出発元（黒丸）が設定されていない列を抽出し、その列に対応する拠点を出発拠点とする。そして、出発拠点とした拠点の列で、到着先（白丸）が設定されたセルが交わる行に対応する拠点を次の巡回拠点とする。さらに、その拠点に対応する列へ移動して、同様に到着先（白丸）が設定されたセルで交わる行に対応する拠点を次の巡回拠点とする。このようにしてすべての列について処理が終了した時点で、出発拠点から順に抽出した巡回拠点を並べて巡回路とする。
【００７６】
例えば、図１４のワークマトリクスＭ２では、出発元（黒丸）が設定されていない拠点Ｃの列をみて、拠点Ｃを出発拠点とする。次に、拠点Ｃの列で到着先（白丸）が拠点Ｅの行との交点セルに設定されているので、拠点Ｅを次の巡回拠点とする。さらに、拠点Ｅの列をみて、到着先（白丸）が設定された拠点Ｄとの交点セルから拠点Ｄを次の巡回拠点とする。続いて、拠点Ｄの列で到着先（白丸）が設定された拠点Ａとの交点セルから拠点Ａを次の巡回拠点とし、拠点Ａの列で到着先（白丸）が設定された拠点Ｂとの交点セルから拠点Ｂを次の巡回拠点とする。ここで、すべての列について処理が終了したので、抽出した巡回拠点の順にＣ→Ｅ→Ｄ→Ａ→Ｂが巡回路となる。この巡回路は、表現したスケジュールを問題の最適解として出力手段３へ出力される。
【００７７】
図１５に、本発明の処理フローを示す。
【００７８】
スケジューリング問題処理装置１は、データ受付手段１１により、入力手段２から処理対象の問題についての拠点およびその移動コスト、時間制約などのデータを受け付ける（ステップＳ１）。そして、マスタマトリクス作成手段１２により、マスタマトリクスＭ０の作成を行う（ステップＳ２）。
【００７９】
図１６に、ステップＳ２のマスタマトリクス作成の処理フローを示す。マスタマトリクス作成手段１２は、データ受付手段１１が受け付けたデータの拠点数を入力し（ステップＳ２０）、拠点数を列数および行数とする２次元配列を作成して（ステップＳ２１）、拠点ごとの移動コストをセル値として設定する（ステップＳ２２）。さらに、データ受付手段１１が時間制約を受け付けたときは、時間制約をセル値に反映する（ステップＳ２３）。
【００８０】
次に、ワークマトリクス作成手段１３により、ワークマトリクスＭ１を作成し（ステップＳ３）、ワークマトリクスＭ２を作成する（ステップＳ４）。
【００８１】
図１７に、ステップＳ３およびステップＳ４のワークマトリクス作成の処理フローを示す。ワークマトリクス作成手段１３は、データ受付手段１１が受け付けたデータの拠点数を入力し（ステップＳ３０）、拠点数を列数および行数とする２次元配列を作成する（ステップＳ３１）。
【００８２】
次に、条件チェック手段１４のセル値設定部１４１により、コスト基準値を０（最小値）にし（ステップＳ５）、マスタマトリクスＭ０からコスト基準値に該当するセル値をワークマトリクスＭ１にコピーする（ステップＳ６）。
【００８３】
次に、第１条件チェック部１４２により、セル値がコピーされたワークマトリクスＭ１が第１条件を満たすか否かをチェックする（ステップＳ７）。そして、チェックがＯＫであれば（ステップＳ８）、チェックＯＫを送出する。また、チェックがＮＧであれば（ステップＳ８）、チェックＮＧを送出する。
【００８４】
チェックＮＧが送出された場合には、第１条件チェック部１４２により、コスト基準値の値を１つ加算して（ステップＳ９）、再度マスタマトリクスＭ０からコスト基準値に該当するセル値をワークマトリクスＭ１に追加してコピーする（ステップＳ６）。
【００８５】
チェックＯＫが送出された場合には、第２条件チェック部１４３により、ワークマトリクスＭ１から作成したワークマトリクスＭ２を用いて第２条件をチェックする（ステップＳ１０）。
【００８６】
図１８に、第２条件チェックの処理フローを示す。第２条件チェック部１４３は、ワークマトリクスＭ１のすべての列（行）について、以下のステップＳ４１およびステップＳ４２の処理が行われたかどうかをチェックする（ステップＳ４０）。
【００８７】
ステップＳ４０の処理でチェックしていない列（行）があれば、次の列（行）に着目して（ステップＳ４１）、着目した列（行）において最小のセル値のみをワークマトリクスＭ２へ記録する（ステップＳ４２）。
【００８８】
すべての列（行）についてステップＳ４１およびステップＳ４２の処理を行っていれば（ステップＳ４０）、さらに、ワークマトリクスＭ２のすべての列（行）について、以下のステップＳ４４以降の処理を行ったかどうかをチェックする（ステップＳ４３）。
【００８９】
ステップＳ４３の処理でチェックしていない列（行）があれば、次の到着先（値＝０）が設定されたセルにのみ着目して（ステップＳ４４）、着目セルの線対称の位置にある対称セルに到着先（値＝０）があるかどうかを調べる（ステップＳ４５）。そして、対称セルに到着先（値＝０）があれば、対称セルに調整候補（値＝−１）を記録する（ステップＳ４６）。一方、対称セルに到着先（値＝０）がなければ、対称セルに出発元（値＝１）を記録する（ステップＳ４７）。
【００９０】
すべての列（行に）ついてステップＳ４４ないしステップＳ４７の処理を行っていれば（ステップＳ４３）、調整処理を行う（ステップＳ４８）。
【００９１】
図１９に、ステップＳ４８の調整処理の処理フローを示す。第２条件チェック部１４３は、カウンタを０（ゼロ）にして初期化し（ステップＳ５０）、すべての列（行）についてステップＳ５２以降の処理を行ったかどうかをチェックする（ステップＳ５１）。
【００９２】
ステップＳ５１の処理で、すべての列（行）についてステップＳ５２以降の処理を行っていなければ、次の列（行）に着目し（ステップＳ５２）、着目した列（行）に到着先（値＝０）を持つセルおよび出発元（値＝１）を持つセルの両方があるかどうかを調べる（ステップＳ５３）。着目した列（行）に、到着先（値＝０）を持つセルおよび出発元（値＝１）を持つセルの両方があれば、カウンタに１を加算して（ステップＳ５４）、ステップＳ５１の処理へ戻る。
【００９３】
一方、着目した列（行）に、到着先（値＝０）を持つセルおよび出発元（値＝１）を持つセルの両方がなければ、さらに調整候補（値＝−１）があるかどうかを調べる（ステップＳ５５）。
【００９４】
そして、調整候補（値＝−１）があれば、調整候補（値＝−１）を出発元（値＝１）か到着先（値＝０）のうちでその列（行）のセルには存在しないほうの値に変更し（ステップＳ５６）、着目した調整候補のセルの対称セルの値をステップＳ５６で変更した値とは逆の値に設定する（ステップＳ５７）。また、調整候補（値＝−１）がなければ、ステップＳ５１の処理へ戻る。
【００９５】
その後、カウンタに１を加算して（ステップＳ５４）、ステップＳ５１の処理へ戻り、すべての列（行）について、ステップＳ５２ないしステップＳ５７の処理を行っていたら、カウンタ値が拠点数−２以上であるかどうか調べる（ステップＳ５８）。
【００９６】
カウンタ値が拠点数−２以上であれば、さらにカウントした列（行）が全拠点を包含しているかどうかを調べ（ステップＳ５９）、カウントした行が全拠点を包含していれば、第２条件のチェックＯＫを送出する（ステップＳ５１０）。
【００９７】
一方、カウンタ値が拠点数−２以上でない場合（ステップＳ５８）、または、カウントした列（行）が全拠点を包含していない場合（ステップＳ５９）のいずれかであるときは、第２条件のチェックＮＧを送出する（ステップＳ５１１）。
【００９８】
そして、ステップＳ１０の処理で、チェックＯＫが送出された場合には（ステップＳ１１）、スケジュール決定手段１５により、巡回路の探索を行う（ステップＳ１２）。
【００９９】
図２０に、巡回路探索の処理フローを示す。スケジュール決定手段１５は、すべての列（行）についてステップＳ６１以降の処理を行ったかどうかをチェックする（ステップＳ６０）。ステップＳ６０の処理で、すべての列（行）についてステップＳ６１およびステップＳ６２の処理を行うまで、次の列（行）に着目して（ステップＳ６１）、着目した列（行）に出発元（値＝１）を持つセルがひとつもないかどうかをチェックする（ステップＳ６２）。
【０１００】
着目した列（行）に出発元（値＝１）を持つセルがひとつもなければ、その列の拠点を出発拠点とする（ステップＳ６３）。そして、着目した列で到着先（値＝０）を持つセルで交わる行（列）と同じ拠点の列（行）に着目し（ステップＳ６４）、未だ全拠点を巡回していなければ（ステップＳ６５）、ステップＳ６３で着目した列で到着先（値＝０）を持つセルで交わる行（列）に対応する拠点を経由点に登録し（ステップＳ６６）、経由点に登録した拠点に対応する列に着目して（ステップＳ６７）、ステップＳ６５の処理へ戻る。ステップＳ６５の処理で、すでに全拠点を巡回していれば処理を終了する。
【０１０１】
なお、ステップＳ１１の処理で、第２条件のチェックＮＧが送出されている場合には、セル値設定部１４１により、コスト基準値に１を加算して（ステップＳ１３）、ワークマトリクスＭ０を参照して、加算したコスト基準値に該当するセル値をワークマトリクスＭ１にコピーして（ステップＳ１４）、コピーしたワークマトリクスＭ１を第２条件チェック部１４３に渡し、第２条件チェック部１４３により、第２条件のチェックを行う。（ステップＳ１０）。
【０１０２】
以下に、スケジューリング問題処理装置１のデータ受付手段１１が時間制約を受け付けた場合の処理を説明する。
【０１０３】
図２１（Ａ）に、ある生産計画での工程（拠点）Ａ、Ｂ、Ｃ、Ｄ、Ｅについて、各拠点ごとに利用可能な時間帯が制限される状況を示す。工程（拠点）Ａから工程（拠点）Ｂへの段取り替え（移動）に待ち時間＝４が必要である。ここで、図２１（Ａ）の各拠点の段取り替え時間（移動コスト）が、前記図１に示すマスタマトリクスＭ０のように設定されているとすると、Ａ→Ｂへの移動コストは０であって、移動コストは無視できることになる。
【０１０４】
しかし、実際には、図２１（Ａ）に示すように待ち時間＝４があるため、工程（拠点）Ａを最も遅く開始（出発）した場合でも工程（拠点）Ｂへの移動コストは実質的に４となる。
【０１０５】
そこで、スケジューリング問題処理装置１は、データ受付手段１１により待ち時間などの時間制約のデータを受け付けると、マスタマトリクス作成手段１２により、前記図１に示すマスタマトリクスＭ０を作成した後、待ち時間などの時間制約をもとに該当するセルのコスト値を変更する。例えば、マスタマトリクスＭ０の拠点Ａから拠点Ｂへの移動コストが０である場合に、Ａ→Ｂの移動に対する待ち時間＝４を参照して、図２１（Ｂ）に示すように、マスタマトリクスＭ０のＦｒｏｍ列の拠点ＡとＴｏ行の拠点Ｂとのセル値＝０に「＋４」加算して再設定する。
【０１０６】
かかる変更により、Ａ→Ｂの経路のコスト値が他の拠点間のコスト値に比べて大きくなるために、Ａ→Ｂの経路が採用されにくくなり、待ち時間などの時間制約を反映した巡回路が選択されることになる。
【０１０７】
また、すでに作成した流れが良い工程、すなわち良い巡回路をマトリクスに反映させたい場合がある。図２２（Ａ）に示すガントチャートで表されたペンキ製造工程の各ジョブの流れすなわち拠点の順回路が良いために、このガントチャートをマトリクスに反映させたいとする。
【０１０８】
スケジューリング問題処理装置１は、データ受付手段１１により、ペンキ製造工程の巡回路に該当する各ジョブ（拠点）と次のジョブへの段取り替え時間（移動コスト）と、順序を確定したいジョブ間の経路確定のデータを受け付ける。そして、マスタマトリクス作成手段１２により、図２２（Ｂ）に示す処理フローのようにして、マスタマトリクスＭ０に良い巡回路を規定する条件を反映させる。
【０１０９】
マスタマトリクス作成手段１２では、次のジョブ（最初は先頭拠点）に着目し（ステップＳ７０）、経路確定にかかる後続のジョブがあるかどうかを調べ（ステップＳ７１）、後続のジョブがあれば、マスタマトリクスＭ０のＦｒｏｍの列で着目する拠点とＴｏ行の後続する拠点と交わるセルの値（移動コスト）を例えば１減算して（ステップＳ７２）、次の拠点に着目する（ステップＳ７０）。そして、経路確定にかかる後続のジョブがなくなるまで処理を繰り返す。
【０１１０】
なお、複数の工程の場合には、工程数だけ図２２（Ｂ）の処理を繰り返す。その場合には、ある工程の巡回路を決定すると、上工程と下工程との関係から他の工程には時間制約が生じるため、生じた時間制約についてもマスタマトリクスＭ０に反映させる処理を行う。
【０１１１】
以上、本発明をその実施の態様により説明したが、本発明はその主旨の範囲において種々の変形が可能である。
【０１１２】
例えば、本発明の実施の形態では、スケジューリング問題処理装置１は、マスタマトリクスおよびワークマトリクスの処理に関し、列に着目して処理するものとして説明したが、行に着目して処理することも当然に可能である。
【０１１３】
また、スケジュール決定手段１５は、巡回路の探索の処理において、出発拠点を求めてから巡回拠点を探索する処理を行うものとして説明したが、到着先が設定されていない拠点の列を求めてから巡回拠点を逆の方向で探索する処理を行うようにしてもよい。また、着目した列または行に到着先もしくは出発元が複数ある場合には、すべての到着先／出発元について巡回路探索の処理を行うようにして、スケジュール決定手段１５により、総コストが最小の巡回路を最適解とするようにしてもよい。
【０１１４】
また、本発明の各手段または機能または要素は、コンピュータにより読み取られ実行される処理プログラムとして実現することができる。また、本発明を実現する処理プログラムは、コンピュータが読み取り可能な、可搬媒体メモリ、半導体メモリ、ハードディスクなどの適当な記録媒体に格納することができ、これらの記録媒体に記録して提供され、または、通信インタフェースを介して種々の通信網を利用した送受信により提供されるものである。
【０１１５】
本発明の形態および実施例の特徴を列記すると以下のとおりである。
【０１１６】
（付記１）　複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理方法において、
仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付ける処理ステップと、
全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成する処理ステップと、
前記マスタマトリクスを記憶する処理ステップと、
前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成する処理ステップと、
前記第１ワークマトリクスを記憶する処理ステップと、
前記第２ワークマトリクスを記憶する処理ステップと、
前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写する処理ステップと、
セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでない場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定する処理ステップと、
前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含する場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定する処理ステップとを備える
ことを特徴とするスケジューリング問題処理方法。
【０１１７】
（付記２）　前記付記１に記載のスケジューリング問題処理方法において、
前記データを受け付ける処理ステップは、さらに、前記移行コストに関するコスト制約を受け付け、
前記マスタマトリクスを作成する処理ステップは、前記コスト制約を参照して、前記マスタマトリクスの該当するセル値を増加させる
ことを特徴とするスケジューリング問題処理方法。
【０１１８】
（付記３）　前記付記１に記載のスケジューリング問題処理方法において、
前記データを受け付ける処理ステップは、さらに、前記仕事と前記仕事の後続仕事との経路確定を受け付け、
前記マスタマトリクスを作成する処理ステップは、前記経路確定を参照して、前記マスタマトリクスの該当するセル値を減少させる
ことを特徴とするスケジューリング問題処理方法。
【０１１９】
（付記４）　複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理を実現する処理ステップをコンピュータに実行させるための処理プログラムであって、
仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付ける処理ステップと、
全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成する処理ステップと、
前記マスタマトリクスを記憶する処理ステップと、
前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成する処理ステップと、
前記第１ワークマトリクスを記憶する処理ステップと、
前記第２ワークマトリクスを記憶する処理ステップと、
前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写する処理ステップと、
セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでない場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定する処理ステップと、
前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含する場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定する処理ステップとを、
コンピュータに実行させる
ことを特徴とするスケジューリング問題処理プログラム。
【０１２０】
（付記５）　複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理を実現する処理ステップをコンピュータに実行させるための処理プログラムを記録した記録媒体であって、
仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付ける処理ステップと、
全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成する処理ステップと、
前記マスタマトリクスを記憶する処理ステップと、
前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成する処理ステップと、
前記第１ワークマトリクスを記憶する処理ステップと、
前記第２ワークマトリクスを記憶する処理ステップと、
前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写する処理ステップと、
セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでない場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定する処理ステップと、
前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含する場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定する処理ステップとを、
コンピュータに実行させるための処理プログラムを記録した
ことを特徴とするスケジューリング問題処理プログラム記録媒体。
【０１２１】
（付記６）　複数の仕事が与えられているときに、全仕事の作業時間の総和が最小に近くなるように仕事順序を求めるスケジューリング問題処理装置において、
仕事と当該仕事から後続仕事への移行コストとを含むデータを受け付けるデータ受付手段と、
全仕事数を行数および列数とし、前記仕事の移行コストをセル値とするマスタマトリクスを作成するマスタマトリクス作成手段と、
前記マスタマトリクスを記憶するマスタマトリクス記憶手段と、
前記マスタマトリクスと同一の行および列からなる第１ワークマトリクスおよび第２ワークマトリクスを作成するワークマトリクス作成手段と、
前記第１ワークマトリクスを記憶する第１ワークマトリクス記憶手段と、
前記第２ワークマトリクスを記憶する第２ワークマトリクス記憶手段と、
前記マスタマトリクスから所定の基準値以下のセル値を抽出して前記第１ワークマトリクスに複写するセル値設定処理手段と、
セル値が複写された前記第１ワークマトリクスが、前記セル値のない列または行がそれぞれ２以上なく、かつ、前記セル値のない列または行が１である場合に当該行および列が同一の仕事に対応するものでないという第１条件を満たすか否かを判定する第１条件チェック手段と、
前記第１条件を満たす場合に、前記第１ワークマトリクスのセル値の位置から当該仕事の後続仕事および当該仕事に先立つ前置仕事をそれぞれ解析して前記第２ワークマトリクスの該当するセルに設定し、前記後続仕事および前記前置仕事が設定された第２ワークマトリクスが、全仕事数をｎとする場合に、他の仕事に対して前置仕事かつ後続仕事となる仕事の数がｎ−２以上であり、かつ、当該仕事の前記前置仕事および前記後続仕事の集合が全仕事を包含するという第２条件を満たすか否かを判定する第２条件チェック手段と、
前記第２条件を満たす場合に、前記第２ワークマトリクスの前置仕事および後続仕事のパターンにもとづいて前記仕事順序を決定するスケジュール決定手段とを備える
ことを特徴とするスケジューリング問題処理装置。
【０１２２】
【発明の効果】
以上説明したように、本発明によれば、スケジューリング問題における工程（拠点）および次の工程への段取り替え時間（移動コスト）をマトリクス形式で管理し、一定値を超える移動コストを無視したときに出現するマトリクス上のパターンに着目し、そのパターンが巡回路が成立するための条件を満たすかどうかを判定し、巡回路が成立すると判定したマトリクスに現れた巡回パターンに従って各拠点を抽出し巡回路である工程スケジュールを決定する。
【０１２３】
よって、一定値を超える移動コストを無視してコストが小さい経路だけに着目することにより、巡回路数を制限し、最適解を取得するまでの処理時間を短縮化できるという効果を奏する。
【０１２４】
さらに、作成する巡経路を限定し、マトリクス上に表現されたパターンそのものにもとづいて巡回路成立可否の判断を行うことにより、実用的な処理時間で最適解を求めることができるという効果を奏する。
【０１２５】
また、本発明では、拠点によって巡回可能な時間が制約されている場合に、移動コストに待ち時間などの時間制約を加算しまたは減算して加味する。これにより、待ち時間が発生するような経路を回避してより最適な巡回路である工程スケジュールを決定することができるという効果を奏する。
【０１２６】
また、人が良いスケジュールであるとして確認したスケジュールをスケジューリング問題として受け付け、このスケジュールの経路を一種の制約条件としてとらえてマトリクス上のセル値（移動コスト）に反映させる。これにより、良いスケジュールをマトリクスとして管理して移動コストの見直しが可能となり、一種の学習機能を実現することができるという効果を奏する。
【図面の簡単な説明】
【図１】スケジューリング問題における拠点間の移動コストを表したマトリクスの例を示す図である。
【図２】巡回路Ａ→Ｂ→Ｃ→Ｄ→Ｅのみの移動コストを表したマトリクスの例を示す図である。
【図３】別のマトリクスの例および当該マトリクスが表す巡回路を示す図である。
【図４】巡回路Ａ→Ｂ→Ｃ→Ｄ→Ｅを示す図である。
【図５】別のマトリクスの例および当該マトリクスが表す経路を示す図である。
【図６】出発元および到着先を表すマトリクスの例を示す図である。
【図７】逆経路を示すマトリクスの例を示す図である。
【図８】本発明の実施の形態におけるシステム構成例を示す図である。
【図９】セル値＝０をコピーしたワークマトリクスＭ１の例を示す図である。
【図１０】到着先を設定したワークマトリクスＭ２の例を示す図である。
【図１１】セル値＝０、１がコピーされたワークマトリクスＭ１を示す図である。
【図１２】値＝０が設定されたセルおよび削除対象となる値＝０を表したワークマトリクスＭ２を示す図である。
【図１３】到着先、出発元、および調整候補が設定されたワークマトリクスＭ２を示す図である。
【図１４】セルの設定を調整した後のワークマトリクスＭ２を示す図である。
【図１５】本発明の処理フローを示す図である。
【図１６】ステップＳ２のマスタマトリクス作成の処理フローを示す図である。
【図１７】ステップＳ３およびステップＳ４のワークマトリクス作成の処理フローを示す図である。
【図１８】ステップＳ１０の第２条件チェックの処理フローを示す図である。
【図１９】ステップＳ４８の調整処理の処理フローを示す図である。
【図２０】ステップＳ１２の巡回路探索の処理フローを示す図である。
【図２１】時間制約の取り扱いを説明するための図である。
【図２２】良い工程をマトリクスに反映させる処理を説明するための図である。
【符号の説明】
１　スケジューリング問題処理装置
１１　データ受付手段
１２　マスタマトリクス作成手段
１３　ワークマトリクス作成手段
１４　条件チェック手段
１４１　セル値設定部
１４２　第１条件チェック部
１４３　第２条件チェック部
１５　スケジュール決定手段
２　入力手段
３　出力手段
【図１】
2004086648.tif 000003
【図２】
2004086648.tif 000004
【図３】
2004086648.tif 000005
【図４】
2004086648.tif 000006
【図５】
2004086648.tif 000007
【図６】
2004086648.tif 000008
【図７】
2004086648.tif 000009
【図８】
2004086648.tif 000010
【図９】
2004086648.tif 000011
【図１０】
2004086648.tif 000012
【図１１】
2004086648.tif 000013
【図１２】
2004086648.tif 000014
【図１３】
2004086648.tif 000015
【図１４】
2004086648.tif 000016
【図１５】
2004086648.tif 000017
【図１６】
2004086648.tif 000018
【図１７】
2004086648.tif 000019
【図１８】
2004086648.tif 000020
【図１９】
2004086648.tif 000021
【図２０】
2004086648.tif 000022
【図２１】
2004086648.tif 000023
【図２２】
2004086648.tif 000024