(57)【要約】【課題】本発明は、より最適な工程フローの設計解を短時間で設計することができる工程設計支援装置を提供することを目的とする。【解決手段】本発明に係る工程設計支援装置は、工程グルーピング部１０４、工程グループフロー生成部１０５、および工程フロー生成部１０６を備えている。工程グルーピング部１０４は、工程ｓ１０間の関連性の高さを示す関連度４０に基づいて、関連性の高い工程ｓ１０を所定のグループに属させるグルーピング処理を、複数の工程ｓ１０に対して実施する。工程グループフロー生成部１０５は、設計情報に基づいて、グルーピング処理の結果生成されたグループの各々を並べた、工程グループフローを生成する。工程フロー生成部１０６は、設計情報に基づいて、グループに属する各工程ｓ１０を並べる。【選択図】図１０
2009184028.tif 000002
【特許請求の範囲】
【請求項１】
複数の工程ブロックを並べることにより得られる、処理工程の実行順序を示す工程フローを、決定する工程設計支援装置において、
前記工程ブロック間の関連性の高さを示す関連度に基づいて、前記工程ブロックを所定のグループに属させるグルーピング処理を、前記複数の工程ブロックに対して実施する工程グルーピング部と、
各前記工程ブロック毎に規定される設計条件である設計情報に基づいて、前記グルーピング処理の結果生成された前記グループの各々を直列的若しくは並列的に並べた、工程グループフローを生成する工程グループフロー生成部と、
前記設計情報に基づいて、前記グループに属する各前記工程ブロックを直列的若しくは並列的に並べる工程フロー生成部とを、備えている、
ことを特徴とする工程設計支援装置。
【請求項２】
前記工程ブロックの順序制約を表す工程先行制約グラフにおいて、前記設計情報に基づいて、前記関連度を自動的に定義する工程関連度定義部を、さらに備えている、
ことを特徴とする請求項１に記載の工程設計支援装置。
【請求項３】
前記工程設計支援装置における、工程設計処理を実行する時間を計測する処理時間計測部と、
前記処理時間計測部による計測時間が、予め設定されている閾時間を超えたときに、前記グルーピング処理の条件を変更するグルーピング条件調整部とを、さらに備えている、
ことを特徴とする請求項１に記載の工程設計支援装置。
【請求項４】
前記関連度に基づいて、前記工程先行制約グラフを分割する工程先行制約グラフ分割部を、さらに備えており、
前記グルーピング部は、
前記工程先行制約グラフ分割部により分割された当該分割後の工程先行制約グラフに対して、前記グルーピング処理を実施する、
ことを特徴とする請求項２に記載の工程設計支援装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、所定の処理の工程順序を設計することができる工程設計支援装置に係る発明である。
【背景技術】
【０００２】
従来の工程設計支援装置では、知識ベースを備えている。そして、作業、作業優先順位、各作業のタクトタイム、制約条件及び工具交換等に要する付加時間等の属性データが当該装置に入力される。これにより、工程設計支援装置は、入力された属性データ及び知識ベースの情報に基づいて優先順位を設定し、その優先順位に基づいて工程の実行順序を決定する（例えば特許文献１）。
【０００３】
当該特許文献１に係る工程設計支援装置にあっては、与えられた複数の工程を一列に並べたときに最適となるような工程フローの解を生成する場合に、前工程から後工程へ順に工程の候補を決定していく。その際、工程の候補として先行制約を満たすものが複数存在する場合には、知識ベースで与えられている条件や各工程に定義された重みの値に基づいて候補を１つのみに絞り込む。
【０００４】
【特許文献１】特開平５−１８１８７３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に係る工程設計支援装置では、工程を１つずつ前工程から後工程へと順に決定していくため、初期段階から設計解の候補を削除することになる。したがって、最終的な全体の設計解として最適なものが生成されるとは限らない。例えば、最初の工程としてはあまりよい設計解ではなくても、その工程を最初の工程としたとする。このことで、後の工程を並列化してタクトタイムを縮めることができ、全体的にもよい設計解となる場合もある。
【０００６】
また、特許文献１に係る工程設計支援装置では、各工程で使用するリソース（ロボット、加工機、その他の専用機等の設備やハンドやドリル等の工具や冶具や作業台等）は１つのみであり、複数のリソースを定義することができない。また、全体として使用可能なリソースの数についても管理していないため、一列にシーケンシャルに並んだ工程しか生成できない。したがって、当該工程設計支援装置では、工程に複数設備による協調動作を含んだ場合や複数工程が並行して実行される場合は、工程フローが決定できない。
【０００７】
そこで、本発明は、より最適な工程フローの設計解を短時間で設計することができる工程設計支援装置を提供することを目的とする。さらには、工程に複数設備による協調動作を含んだ場合、あるいは、複数工程が並行して実行される場合でも、自動的によい設計解を設計できる工程設計支援装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の目的を達成するために、本発明に係る請求項１に記載の工程設計支援装置は、複数の工程ブロックを並べることにより得られる、処理工程の実行順序を示す工程フローを、決定する工程設計支援装置において、前記工程ブロック間の関連性の高さを示す関連度に基づいて、前記工程ブロックを所定のグループに属させるグルーピング処理を、前記複数の工程ブロックに対して実施する工程グルーピング部と、各前記工程ブロック毎に規定される設計条件である設計情報に基づいて、前記グルーピング処理の結果生成された前記グループの各々を直列的若しくは並列的に並べた、工程グループフローを生成する工程グループフロー生成部と、前記設計情報に基づいて、前記グループに属する各前記工程ブロックを直列的若しくは並列的に並べる工程フロー生成部とを、備えている。
【発明の効果】
【０００９】
本発明の請求項１に記載の工程設計支援装置は、工程ブロック間の関連性の高さを示す関連度に基づいて、工程ブロックを所定のグループに属させるグルーピング処理を、複数の工程ブロックに対して実施する工程グルーピング部と、各工程ブロック毎に規定される設計条件である設計情報に基づいて、グルーピング処理の結果生成されたグループの各々を直列的若しくは並列的に並べた、工程グループフローを生成する工程グループフロー生成部と、設計情報に基づいて、グループに属する各工程ブロックを直列的若しくは並列的に並べる工程フロー生成部とを、備えている。
【００１０】
したがって、より最適な工程フローの設計解を、より短時間で設計することができる。また、関連性のある工程ブロックが連続しやすいように、解（工程フロー）を生成することができる。また、工程設計処理の時間を大幅に短縮し、よい工程設計解を効率的（より短時間に）に生成することができる。また、工程に複数設備による協調動作を含んだ場合、あるいは、複数工程が並行して実行される場合でも、よい設計解を設計できる。
【発明を実施するための最良の形態】
【００１１】
以下、この発明をその実施の形態を示す図面に基づいて具体的に説明する。
【００１２】
＜実施の形態１＞
＜部品−工程関係情報＞
図１は、本発明の実施の形態１による工程設計支援装置において扱う、工程ｓ１０と部品ｐ１１の関係を表す情報を示した図である。なお、本発明において、工程ｓ１０は、工程フローを構成する、工程ブロックであると把握できる。
【００１３】
工程ｓ１０から矢印によって部品ｐ１１へ接続することにより、その工程とその工程で扱う部品との関係を表す情報を構成する。この情報により、ある工程で扱う部品を特定することができる。ある工程がある部品と別の部品とを組み合わせる工程であった場合、例えば図１に示すように、工程１、部品ａおよび部品ｂの関係のように表すことができる。
【００１４】
＜工程情報＞
図２は、工程ｓ１０の詳細を表す工程情報２０の内容を示した図である。
【００１５】
工程ｓ１０には、工程名の他に、作業タイプ、部品構成、工程標準時間、作業精度、作業方向、リソース要求仕様を定義することができる。
【００１６】
作業タイプとは、工程ｓ１０での作業の種類である。例えば、組み立て用の工程の場合、搬送、組み付け、嵌め込み、ネジ締め、把持、ハンド交換等の作業タイプがあり、加工用の工程の場合、切削、面削り、穴あけ、荒加工、面取り、ネジ立て、仕上げ削り等の作業タイプがある。
【００１７】
部品構成とは、工程ｓ１０で扱う部品の構成である。例えば、Ｍ２ネジをカバーにネジ締めする工程ｓ１０の場合、ネジ締めという工程ｓ１０は、Ｍ２ネジという部品とカバーという部品から構成されることになる。また、カバーに穴あけを行う工程ｓ１０の場合、穴あけという工程ｓ１０は、カバーという部品から構成されることになる。
【００１８】
工程標準時間とは、工程ｓ１０での作業を実行するのに要すると見積もられた時間である。時間の単位は、例えば秒であってもよいし、時間の単位であれば、その他の単位であってもよい。
【００１９】
作業精度とは、工程ｓ１０での作業に必要とされる精度である。例えば、ロボットによって部品を把持する工程ｓ１０の場合の位置精度（５ｍｍ以内等）や、穴あけ加工を行う工程ｓ１０の場合の公差（２ｍｍ以内等）のことである。作業精度は、位置精度や公差等の精度の種類と共に、５ｍｍ以内や２ｍｍ以内等のような表現で表される。また、精度の種類が不要な場合は、省略してもよい。
【００２０】
作業方向とは、工程ｓ１０で作業を行う場合の作業の方向である。例えば、ロボットによって部品を組み付ける工程ｓ１０の場合の組み付け方向のことである。作業方向は、例えば、直交座標系におけるベクトルの方向で表したものでもよいし、その他でも方向を表す情報であればよい。
【００２１】
リソース要求仕様とは、その工程ｓ１０での作業に必要とされるリソース（ロボット、加工機、その他の専用機等の設備やハンドやドリル等の工具や冶具や作業台等）の種類および数等のことであり、作業に必要となるリソースを特定するのに使用しうる各種情報のことである。例えば、複数のロボットを使用して部品を支えながら嵌め込む工程ｓ１０の場合、支え用ロボットが１台と嵌め込み用ロボットが１台必要というリソース要求仕様になる。
【００２２】
図２の例では、上記で説明した情報を工程情報２０として定義しているが、それ以外にも、工程ｓ１０で作業を行うのに費やしてよい時間の最大値（作業時間要求仕様）や、工程ｓ１０で組み立てや加工を行う部品を扱うリソース（設備）の詳細な要求仕様（可搬サイズ、可搬重量、把持力、搬送速度、ネジ径、ネジ長、締め付けトルク、圧入力等）やその他の工程設計に有用な情報を定義し、工程設計処理に使用してもよい。
【００２３】
上記で説明した工程情報２０を参照することにより、その工程を実現するために必要な条件を認識することができる。
【００２４】
＜工程先行制約グラフ＞
図３は、工程ｓ１０の順序制約を表す工程先行制約グラフを示した図である。
【００２５】
それぞれの工程ｓ１０を工程先行制約関係３０で結ぶことにより、工程ｓ１０間の順序制約を表す。工程先行制約関係３０の矢印の元の工程ｓ１０から矢印の先の工程ｓ１０への順序で工程を実行する必要があることを表している。例えば、図３の場合、工程２、工程３および工程４は、工程１の後で実行する必要がある。工程７および工程９は、工程２、工程３および工程６の後で実行する必要がある。
【００２６】
また、工程先行制約関係３０には、当該工程先行制約関係３０によってつながる工程ｓ１０間の関連度４０を定義することができる。
【００２７】
＜関連度付き工程先行制約グラフ＞
図４は、工程先行制約グラフの工程先行制約関係３０に関連度４０を付与した関連度付き工程先行制約グラフを示した図である。
【００２８】
関連度４０は、工程先行制約関係３０で結ばれた工程ｓ１０間の関連性の高さを表す数値であり、例えば大きい値ほど関連性が高いことを表す。工程先行制約関係３０の関連度４０を参照することにより、工程先行制約関係３０で結ばれた工程ｓ１０間の関連性の高さを認識することができる。
【００２９】
＜工程グループ先行制約（工程のグルーピング）＞
図５は、工程グループ５０の順序制約を表す工程グループ先行制約グラフを示した図である。
【００３０】
工程グループ５０は、工程ｓ１０間の関連度４０に基づいて、関連性の高い工程ｓ１０を１つのグループとしてまとめて扱う単位である。図５に示すように、工程グループ５０の中には単一あるいは複数の工程ｓ１０を含み、１つのグループとして扱う。それぞれの工程グループ５０を工程グループ先行制約関係５１で結ぶことにより、工程グループ５０間の順序制約を表す。工程グループ先行制約関係５１の矢印の元の工程グループから矢印の先の工程グループへの順序で、工程グループ５０を実行する必要があることを表している。
【００３１】
例えば、図５の場合、工程グループ２、工程グループ３および工程グループ４は、工程グループ１の後で実行する必要がある。工程グループ５は、工程グループ２、工程グループ３および工程グループ４の後で実行する必要がある。また、工程グループ先行制約関係５１には、当該工程グループ先行制約関係５１によってつながる工程グループ５０間のグループ関連度５２を、工程ｓ１０間の関連度４０と同様に定義することができる。
【００３２】
＜工程グループ情報＞
図６は、工程グループ５０の詳細を表す工程グループ情報６０の内容を示した図である。
【００３３】
工程グループ情報６０には、工程グループ名の他に、工程グループ内工程情報、工程グループ標準時間、工程グループリソース要求仕様を定義することができる。
【００３４】
工程グループ内工程情報は、工程グループ５０に含まれる工程ｓ１０の情報である。工程グループ５０に含まれるすべての工程情報２０を定義することができる。また、工程グループ内工程情報には、その工程グループ５０に含まれる工程ｓ１０間の工程先行制約関係３０の情報も含まれる。
【００３５】
工程グループ標準時間は、工程グループ５０での作業（単一あるいは複数の工程ｓ１０）を実行するのに要すると見積もられた時間である。
【００３６】
工程グループリソース要求仕様は、工程グループ５０での作業（単一あるいは複数の工程ｓ１０）に必要とされるリソースの仕様である。必要とされるリソースの種類と必要となる数の最大値を定義する。
【００３７】
図６の例では、上記で説明した情報を工程グループ情報６０として定義しているが、それ以外にも、工程設計に有用な情報があればそれを定義し、工程設計処理に使用してもよい。
【００３８】
上記で説明した工程グループ情報６０を参照することにより、その工程グループ５０を実現するために必要な条件を認識することができる。
【００３９】
＜工程グループフロー（工程グループの並べ替え）＞
図７は、工程グループ５０のフロー（工程グループフロー）を示した図である。
【００４０】
与えられた順序の制約や使用可能なリソース数等の設計条件（設計情報により規定される条件）を満たすように（設計情報に基づいて）、工程グループ５０を並べ替えて工程グループフローを生成する。ここで、設計情報とは、各工程ブロック毎に規定される、当該工程ブロックで要する設計条件である。それぞれの工程グループ５０を工程グループ実行順序関係７０で結ぶことにより、工程グループ５０間の実行順序を表す。工程グループ実行順序関係７０の矢印の元の工程グループ５０から矢印の先の工程グループ５０への順序で、工程グループ５０を実行することを表している。
【００４１】
例えば、図７の場合、工程グループ１の後で、工程グループ２および工程グループ４を実行する。工程グループ２の後で、工程グループ３を実行する。また、工程グループ３および工程グループ４の後で、工程グループ５を実行することを表している。
【００４２】
＜工程フローの例１（工程グループの展開）＞
図８は、工程ｓ１０のフロー（工程フロー）の一例を示した図である。
【００４３】
与えられた順序の制約や使用可能なリソース数等の設計条件を満たすように（設計情報に基づいて）、工程ｓ１０を並べ替えて工程フローを生成する。それぞれの工程ｓ１０を工程実行順序関係８０で結ぶことにより、工程ｓ１０間の実行順序を表す。工程実行順序関係８０の矢印の元の工程ｓ１０から矢印の先の工程ｓ１０への順序で工程を実行することを表している。
【００４４】
例えば、図８の場合、工程１の後で、工程２および工程４を実行する。工程２の後で、工程３を実行する。工程４の後で、工程５を実行する。工程５の後で、工程６を実行する。また、工程３および工程６の後で、工程７および工程９を実行する。工程７の後で、工程８を実行する。工程９の後で、工程１０を実行する。さらに、工程８および工程１０の後で工程１１を実行することを表している。
【００４５】
＜工程フローの例２（工程グループの展開）＞
図９は、図８で示した工程フローを生成するときに工程先行制約グラフが入力され、使用可能なリソース数等として異なる条件が入力された場合に、生成される工程フローの例を示した図である。
【００４６】
使用可能なリソース数等の設計条件が異なる場合には、このように図８に示した工程フローとは異なる工程フローを生成する可能性がある。例えば、工程３および工程６以降の作業で必要となるリソースが並列に作業できるのに十分な数だけないような場合、このような工程フローになる可能性がある。換言すれば、使用可能なリソース数の範囲内において、工程ｓ１０を並列化させて並べることができる。なお、使用可能なリソース数等の条件以外でも、工程ｓ１０の順序の制約が異なるような場合には、生成される工程フローが異なる可能性がある。
【００４７】
＜工程設計支援装置の構成＞
図１０は、本発明の実施の形態１による工程設計支援装置の構成の一例を示した図である。
【００４８】
工程設計支援装置は、工程設計支援装置で扱うデータを処理して最終的な出力である工程フローを生成する工程設計処理部１００と、工程設計支援装置で扱うデータの入出力を行うデータ入出力部１０２とから構成される。
【００４９】
データ入出力部１０２は、工程設計に必要となる設計情報１０１の各種データの入力および出力を行う。
【００５０】
また、工程設計処理部１００は、設計情報記憶部１０１、工程関連定義部１０３、工程グルーピング部１０４、工程グループフロー生成部１０５、および工程フロー生成部１０６から構成されている。
【００５１】
設計情報記憶部１０１には、工程設計支援装置で扱う工程情報２０および制約情報等のデータである設計情報が格納される。ここで、設計情報には、例えば、工程情報２０、工程先行制約グラフ、使用可能なリソース数、タクトタイム等の制約情報が含まれる。
【００５２】
工程関連定義部１０３では、工程ｓ１０間を結んだ工程先行制約関係３０に、関連度４０を定義する。
【００５３】
工程グルーピング部１０４は、設計情報記憶部１０１に格納されている設計情報に基づいて、工程先行制約グラフ中の工程ｓ１０を工程グループ５０へグルーピングし、工程グループ先行制約グラフを生成する。
【００５４】
工程グループフロー生成部１０５は、工程グループ先行制約グラフと使用可能なリソース等の設計条件から、実行可能な工程グループフローを生成する。つまり、工程グループフロー生成部１０５は、設計情報記憶部１０１に格納されている設計情報に基づいて、各工程グループ５０を並べる。
【００５５】
工程フロー生成部１０６は、工程グループフローと使用可能なリソース等の設計条件から、実行可能な工程フローを生成する。つまり、工程フロー生成部１０６は、各工程グループ５０ごとに、設計情報記憶部１０１に格納されている設計情報に基づいて、各工程ｓ１０を並べる。
【００５６】
図１０に示した構成からなる工程設計支援装置によって、工程設計を行う処理フローを以下で図１２を用いて説明する。
【００５７】
＜ハードウェア構成＞
図１１は、本実施の形態１による工程設計支援装置のハードウェアの構成図である。
【００５８】
当該ハードウェアは、パソコンなどの計算機、携帯端末などの電子機器である。図１１に示すように、ハードウェアは、入力部２２０、記憶部２２１、処理部２２２、および表示部２２３により構成されている。
【００５９】
入力部２２０は、キーボード、テンキー、カーソルキー、マウス、ジョイスティック等であり、当該入力部を外部から操作することにより設定情報等の情報が入力される。記憶部２２１は、前記情報を記憶する。処理部２２２は、記憶部２２１に記憶されている情報に基づき、演算処理を行う。なお、処理部２２２は、伝送線、ネットワーク、無線通信により外部と通信を行う通信部を用いて外部と情報をやり取りするように構成してもよい。表示部２２３は、処理部２２２における演算処理結果を文字、画像などの表示情報として液晶ディスプレイ、ＣＲＴに表示する。
【００６０】
図１０と図１１との対比において、データ入出力部１０２のデータを入力する部分は、入力部２２０において実現される。また、データ入出力部１０２のデータを出力する部分は、表示部２２３において実現される。また、設計情報記憶部１０１は、記憶部２２１において実現される。なお、記憶部２２１には、電子機器を設計情報の記憶手段として実行させるためのプログラムが記憶され、その記憶手段はこのプログラムを読み出し、当該手段を実行する。残りの各処理部である工程関連定義部１０３と、工程具ルーピング部１０４と、工程グループフロー生成部１０５と、工程フロー生成部１０６とは、処理部２２２において実現される。
【００６１】
＜フローチャート（工程設計）＞
図１２は、図１０、１１に示した構成からなる工程設計支援装置によって、工程設計を行う処理フローの概略を示したフローチャートである。本工程設計支援装置における工程設計処理では、ステップＳ１からステップＳ４が実行される。
【００６２】
ステップＳ１では、工程先行制約グラフにおける工程ｓ１０間の工程先行制約関係３０に関連度４０を定義する。ステップＳ１の処理は、工程関連定義部１０３で実行される。工程先行制約関係３０への関連度４０の定義は、工程設計支援装置のユーザが手動で定義してもよいし、工程設計支援装置が自動的に定義してもよい。工程設計支援装置が自動的に定義する場合は、設計情報記憶部１０１の設計情報を参照し、その情報に基づいて工程ｓ１０間の関連度４０を算出し、当該算出された関連度４０を工程先行制約関係３０において定義する。
【００６３】
ステップＳ２では、設計情報および工程先行制約グラフの工程先行制約関係３０に定義された関連度４０に基づいて、工程先行制約グラフ中の工程ｓ１０を工程グループ５０へグルーピングし、工程グループ先行制約グラフを生成する。ステップＳ２の処理は、工程グルーピング部１０４で実行される。
【００６４】
ステップＳ３では、設計情報を参照し、当該設計情報に基づいて、工程グループ先行制約グラフ中の工程グループ５０を並べ替えて、工程グループフローを生成する。ステップＳ３の処理は、工程グループフロー生成部１０５で実行される。
【００６５】
ステップＳ４では、設計情報１０１を参照し、当該設計情報に基づいて、工程グループフローから工程フローを生成する。ステップＳ４の処理は、工程フロー生成部１０６で実行される。
【００６６】
以上のステップＳ１からステップＳ４までの処理を実行することにより、入力された工程先行制約グラフを含む設計情報に基づいて、リソースやタクトタイム等の条件を満たす工程フローを生成することができる。なお、設計情報の一部として、リソースやタクトタイム等の条件は、あらかじめ与えられているものとする。
【００６７】
＜フローチャート（関連度の定義）＞
図１３は、工程設計支援装置における工程設計で、関連度４０の定義を行う処理フローを示したフローチャートである。本工程設計支援装置における関連度定義処理では、ステップＳ１１からステップＳ１５が実行される。
【００６８】
ステップＳ１１では、工程先行制約グラフから未処理の工程先行制約関係３０を１つ抽出する。
【００６９】
ステップＳ１２では、抽出した工程先行制約関係３０の前後につながる工程１０を取得する。
【００７０】
ステップＳ１３では、抽出した工程先行制約関係３０に対する関連度４０を算出する。ここで、当該関連度４０の算出は、工程設計支援装置が外部から入力されるユーザからの何らかの条件に基づいて行ってもよい。また、当該関連度４０の算出は、取得した工程１０のつながり方や工程情報２０の内容等の設計情報に基づいて自動的に行ってもよい。自動的に算出する場合は、例えば、下記の「関連度算出の条件」で示すような各条件で関連度４０を算出することができる。
【００７１】
ステップＳ１４では、ステップＳ１３で算出した関連度４０を、当該関連度４０の算出対象である工程先行制約関係３０に設定する。
【００７２】
ステップＳ１５では、すべての工程先行制約関係３０に対して関連度４０の定義（設定）が完了したかどうかを判定する。ステップＳ１５において、関連度４０の定義が完了していればリターンし、完了していなければステップＳ１１へ戻る。
【００７３】
以上の処理を実行することにより、入力された工程先行制約グラフのすべての工程先行制約関係３０に対して、関連度４０を定義することができる。
【００７４】
＜関連度算出の条件＞
条件（１）：抽出した工程先行制約関係３０の前後につながる工程ｓ１０が、１：１で直列につながるだけで、他の工程ｓ１０とつながることがない場合、高い関連度４０を与える（他の工程ｓ１０への先行制約関係３０がなく、連続して作業しやすい）。
【００７５】
条件（２）：抽出した工程先行制約関係３０の前後につながる工程ｓ１０が、同じあるいは類似する作業タイプである場合、高い関連度４０を与える。例えば、作業タイプが同じ場合は最も高い関連度４０を与え、類似する場合は同じ場合よりも低い関連度４０を与える。類似の判定については、例えば、作業タイプをあらかじめカテゴリに分類しておき、同じカテゴリに属する作業タイプは類似すると判定すればよい。
【００７６】
条件（３）：抽出した工程先行制約関係３０の前後につながる工程ｓ１０の部品構成が、同じあるいは類似している場合、高い関連度４０を与える。例えば、部品構成が同じ場合は最も高い関連度４０を与え、類似する場合は同じ場合よりも低い関連度４０を与える。類似の判定については、例えば、構成する部品に同じ部品が部分的に含まれる場合は類似すると判定すればよい。また、同じ部品が含まれる割合に応じて与える関連度４０を変えてもよい。
【００７７】
条件（４）：抽出した工程先行制約関係３０の前後につながる工程ｓ１０の精度が、同じあるいは類似している場合、高い関連度４０を与える。例えば、作業精度が同じ場合は最も高い関連度４０を与え、類似する場合は同じ場合よりも低い関連度４０を与える。類似の判定については、例えば、作業精度の差の閾値（５ｍｍ等）をあらかじめ規定しておき、作業精度の差が閾値を超過しない場合は類似すると判定すればよい。また、作業精度の差の量に応じて与える関連度４０を変えてもよい（差がない場合は高い値、２ｍｍ未満の場合は中位の値、２ｍｍ以上で５ｍｍ未満の場合は低い値等）。
【００７８】
条件（５）：抽出した工程先行制約関係３０の前後につながる工程ｓ１０の作業方向が、同じあるいは類似している場合、高い関連度４０を与える。例えば、作業方向が同じ場合は最も高い関連度４０を与え、類似する場合は同じ場合よりも低い関連度４０を与える。類似の判定については、例えば、作業方向を直交座標系におけるベクトルの方向で表す場合、あらかじめ作業方向の角度の差の閾値を規定しておき、作業方向の角度の差が閾値を超過しない場合は類似すると判定すればよい。また、作業方向の角度の差の大きさに応じて与える関連度４０を変えてもよい（差がない場合は高い値、２０度未満の場合は中位の値、２０度以上で４５度未満の場合は低い値等）。
【００７９】
条件（６）：抽出した工程先行制約関係３０の前後につながる工程ｓ１０のリソース要求仕様が、同じあるいは類似している場合、高い関連度４０を与える。例えば、リソース要求仕様に同じリソースが部分的に含まれる場合は類似すると判定すればよい。また、同じリソースが含まれる割合に応じて与える関連度４０を変えてもよい。
【００８０】
上記の関連度算出の条件（１）〜（６）に基づいて関連度４０を与える際は、加算方式で与えてもよいし、条件に応じて絶対的な数値で与えてもよい。また、上記に挙げた例以外にも、工程ｓ１０間の関連性に影響する情報に基づいた条件があれば、その条件に従って関連度４０を算出してもよい。
【００８１】
＜フローチャート（工程のグルーピング）＞
図１４は、工程設計支援装置における工程設計で、工程ｓ１０のグルーピングを行う処理フローを示したフローチャートである。本工程設計支援装置における工程グルーピング処理では、ステップＳ２１からステップＳ２６を実行する。
【００８２】
ステップＳ２１では、工程先行制約グラフのすべての工程ｓ１０をそれぞれ１つの工程グループ５０として工程グループ先行制約グラフを作成する。つまり、まず、１工程＝１工程グループとしておき、後の処理でそれらの工程グループ５０を集約していく。工程ｓ１０間の工程先行制約関係３０に対応するように、工程グループ５０間を工程グループ先行制約関係５１でつなげて工程グループ先行制約グラフを作成する。また、工程先行制約関係３０の関連度４０と同じ値を、対応する工程グループ先行制約関係５１のグループ関連度５２として設定する。
【００８３】
ステップＳ２２では、工程グループ先行制約グラフから未処理の工程グループ先行制約関係５１を１つ抽出する。
【００８４】
ステップＳ２３では、抽出した工程グループ先行制約関係５１の前後につながる工程グループ５０を取得する。
【００８５】
ステップＳ２４では、抽出した工程グループ先行制約関係５１に定義されたグループ関連度５２に基づいて、前後につながる工程グループ５０のグルーピングの可否を判定する。例えば、グループ関連度５２がある規定された値よりも大きい場合、工程グループ５０間の関連性が高いと判断してグルーピング可と判定する。他方、グループ関連度５２がある規定された値以下である場合、工程グループ５０間の関連性は低いと判断してグルーピング否と判定する。さらに、グルーピング可能な最大数（グルーピング可能最大数）も規定しておく。そして、現在のグルーピングした回数がグルーピング可能最大数以内であれば、グルーピング可とする。他方、現在のグルーピングした回数がグルーピング可能最大数を超えるならば、グルーピング否と判定してもよい。また、工程ｓ１０をグルーピング処理するための条件であれば、その他の条件で判定してもよい。
【００８６】
ステップＳ２５では、ステップＳ２４でグルーピング可と判定された工程グループ先行制約関係５１に対して、その工程グループ先行制約関係５１でつながる前後の工程グループ５０を１つの工程グループ５０として結合する。１つの工程グループ５０から、結合する前後の工程グループ５０へそれぞれつながる工程グループ先行制約関係５１が複数ある場合を想定する。具体的に、例えば、図５の工程グループ５へつながる工程２からは、２本の工程グループ先行制約関係５１があり、工程３や工程６からも２本の工程グループ先行制約関係５１がある場合を想定する。この場合には、例えば、それらの工程グループ先行制約関係５１のグループ関連度５２の平均値を取り、その平均値をグループ関連度５２とする１つの工程グループ先行制約関係５１を、結合してできる１つの工程グループ５０へつなげるようにする。前記例では、新たに付けるグループ関連度５２の値は平均値にしているが、平均値以外にも最小値や最大値にしてもよい。
【００８７】
１つの工程グループ５０から、結合する前後の工程グループ５０へそれぞれつながる工程グループ先行制約関係５１が単一である場合を想定する。具体的に、例えば、図５の工程グループ４へつながる工程グループ先行制約関係５１の場合を想定する。この場合には、結合する前後の工程グループ５０へつながる工程グループ先行制約関係５１を、結合してできる１つの工程グループ５０へそのままつなげるようにする。
【００８８】
また、結合してできる工程グループ５０のすべての作業を実行するのに要する時間の見積もりを工程グループ標準時間として算出する。更に、結合してできる工程グループ５０のすべての作業を実行するのに必要となるリソースを工程グループリソース要求仕様として設定する。工程グループ標準時間は、工程グループ５０の先頭の工程ｓ１０から順に末尾の工程ｓ１０まで辿り、それらの工程ｓ１０の工程標準時間を積算して算出する。
【００８９】
図５の工程グループ５のように並列に並ぶ工程ｓ１０が含まれる場合は、使用可能なリソース数の範囲内で並列化する。そして、並列化した部分については、それらの部分の工程ｓ１０の工程標準時間を積算した後、それらを比較して大きい方を並列化した部分に要する時間として積算する。並列化の仕方が複数ある場合は、それらに対してそれぞれ工程グループ標準時間を算出し、最も大きい値（最悪値）を工程グループ標準時間とする。
【００９０】
工程グループリソース要求仕様についても、まず、工程グループ標準時間と同様に工程グループ５０の先頭の工程ｓ１０から順に末尾の工程ｓ１０まで辿る。そして、それらの工程ｓ１０のリソース要求仕様に基づいて各リソースに対して必要となる数の最大値（最悪値）を、工程グループリソース要求仕様として設定する。
【００９１】
なお、前記の例では、その工程グループ内で工程ｓ１０が並列化できるような場合でもグルーピング処理するようにしている。しかし、並列化できるような場合は、グルーピング処理せずに、直列に並んだ工程ｓ１０の場合のみグルーピングするようにしてもよい。このような場合には、上記のような使用可能なリソース数を考慮した並列化の可能性の判定や、並列化を考慮した工程グループ標準時間の算出等の複雑な処理を省略することできる。
【００９２】
結合してできる工程グループ５０の工程グループ情報６０（図６）の工程情報として、結合する前後の工程グループ５０に含まれる工程ｓ１０の情報を合わせたものを定義する。また、工程グループ標準時間として、上記で算出したものを定義する。更に、工程グループリソース要求仕様として、上記で求めたものを定義する。結合してできる工程グループ５０の工程グループ情報６０には、その工程グループ５０に含まれる工程ｓ１０に関わる工程先行制約関係３０も併せて保持する。
【００９３】
ステップＳ２６では、すべての工程グループ先行制約関係５１に対して、工程グルーピング処理を実施したか否かを判定する。すべての工程グループ先行制約関係５１に対して工程グルーピング処理が完了していれば、リターンする。他方、すべての工程グループ先行制約関係５１に対して工程グルーピング処理が完了していなければ、ステップＳ２２へ戻る。
【００９４】
以上の処理を実行することにより、入力された工程先行制約グラフの中の関連度４０の高い工程ｓ１０をグルーピングされる。そして、当該グルーピング処理により、工程グループ先行制約グラフを生成することができる。
【００９５】
＜フローチャート（工程グループフローの生成）＞
図１５は、工程設計支援装置における工程設計で、工程グループフローの生成を行う処理フローを示したフローチャートである。本工程設計支援装置における工程グループフロー生成処理では、ステップＳ３１からステップＳ３９を実行する。
【００９６】
ステップＳ３１では、工程グルーピング処理で生成した工程グループ先行制約グラフの先頭の工程グループ５０を選択する。そして、次に処理を行う候補となる工程グループ５０を、保持する次候補リストへ追加する。追加する先頭の工程グループ５０は、単一でも複数でもよい。
【００９７】
ステップＳ３２では、次候補リストにある工程グループ５０の中で、次に実行可能な工程グループ５０のセット（組合せ）をすべて抽出する。実行可能な工程グループ５０とは、現在使用可能なリソースの条件（種類、数等）やタクトタイムの条件（規定時間内）等の設計情報の条件を満たす工程グループ５０である。リソースの条件は、工程グループ情報６０の工程グループリソース要求仕様を参照することで判定できる。タクトタイムは、工程グループ情報６０の工程グループ標準時間を参照することで判定できる。本実施例では、リソースの条件やタクトタイムの条件によって、実行可能性を判定している。しかし、その他の条件で判定したい場合には、その判定に必要となる情報を設計情報として、工程情報２０や工程グループ情報６０に追加すればよい。
【００９８】
ステップＳ３３では、ステップＳ３２で抽出した実行可能な工程グループ５０のセットの中から、１つのセットを抽出する。また、抽出した実行可能な工程グループ５０のセットを実行するのに必要となるリソースの情報（工程グループリソース要求仕様）を参照する。そして、現在使用可能なリソースの条件を更新する（実行するのに必要なリソース分だけ現在使用可能なリソースから減らす等）。
【００９９】
ステップＳ３４では、ステップＳ３３で抽出した１つの実行可能な工程グループ５０のセットを、作成中の工程グループフローの中で最後に完了済みにした工程グループ５０の後に工程グループ実行順序関係７０を付けてつなぐ。抽出した工程グループ５０が先頭の工程グループ５０であり、作成中の工程グループフローの中で最後に完了済みにした工程グループ５０が存在しない場合を想定する。この場合には、抽出した工程グループ５０のみからなる工程グループフローとする。
【０１００】
ステップＳ３５では、作成中の工程グループフローの未完了の工程グループ５０の中から、次に実行を完了する工程グループ５０を特定する。次に実行を完了する工程グループ５０は、未完了の工程グループ５０の中で最も工程グループ標準時間が小さいものである。また、工程グループ５０が完了することで解放されるリソースの情報（工程グループリソース要求仕様）を参照し、現在使用可能なリソースの条件を更新する（完了して空くリソース分だけ現在使用可能なリソースを増やす等）。更に、現在の工程グループフローの実行完了時間に、完了する工程グループ５０の工程グループ標準時間を加算して更新する。ただし、完了する工程グループ５０が他の工程グループ５０と並列に並んでいる場合は、それを考慮して加算する。完了する工程グループ５０の前につながる工程グループ５０の完了時間に、完了する工程グループ５０の工程グループ標準時間を加算し、完了する工程グループ５０までの工程グループ標準時間とする。
【０１０１】
ステップＳ３６では、工程グループ先行制約グラフのすべての工程グループ５０に対する上記処理が完了しているかどうかを判定する。そして、すべての工程グループ５０に対する上記処理が完了していればステップＳ３８へ進み、完了していなければステップＳ３７へ進む。
【０１０２】
ステップＳ３７では、ステップＳ３５で特定した工程グループ５０が完了した後、実行可能となる工程グループ５０を、次候補リストに追加する。その後、再帰的にステップＳ３２以降の処理を再度実行する。実行可能な工程グループ５０については、Ｓ３２で記載したとおりである。
【０１０３】
ステップＳ３８では、すべての工程グループ５０に対して処理が完了しているので、作成した工程グループフローを１つの解として生成（出力）する。
【０１０４】
ステップＳ３９では、ステップＳ３２で抽出したすべての実行可能な工程グループ５０のセットに対して処理が完了したかどうかを判定する。そして、すべての実行可能な工程グループ５０のセットに対して処理が完了していれば、リターンする。他方、すべての実行可能な工程グループ５０のセットに対して処理が完了していなければ、ステップＳ３３へ戻る。
【０１０５】
以上の処理を実行することにより、入力された工程グループ先行制約グラフの各工程グループ５０をリソースの条件やタクトタイムの条件（設計情報の条件）を満たすように並べ替え、工程グループフローを生成することができる。
【０１０６】
＜フローチャート（工程フローの生成）＞
図１６は、工程設計支援装置における工程設計で、工程グループフローから工程フローの生成を行う処理フローの概略を示したフローチャートである。本工程設計支援装置における工程フロー生成処理では、ステップＳ４１からステップＳ４４を実行する。
【０１０７】
ステップＳ４１では、入力された工程グループフローの中から、未処理の工程グループ５０を抽出する。
【０１０８】
ステップＳ４２では、抽出した工程グループ５０に対し、その工程グループ５０内での工程フローを生成する。工程フローを生成する際には、リソースやタクトタイム等（設計情報）の条件を満たすように、抽出した工程グループ５０に属する工程ｓ１０を並べ替える。
【０１０９】
ステップＳ４３では、工程グループフローの中のすべての工程グループ５０に対して、処理が完了したかどうかを判定する。もし、すべての工程グループ５０に対して処理が完了していれば、ステップＳ４４へ進む。他方、すべての工程グループ５０に対して処理が完了していなければ、ステップＳ４１へ戻る。
【０１１０】
ステップＳ４４では、すべての工程グループに対して生成した、工程グループ５０内の工程フローを工程実行順序関係８０で互いにつないで工程フローを生成する。具体的には、各工程グループ実行順序関係７０に対して、その前につながる工程グループ５０内のすべての末尾の工程ｓ１０から、その後につながる工程グループ５０内のすべての先頭の工程ｓ１０へ工程実行順序関係８０をつなぐようにして互いの工程フローを接続する。工程フローは、各工程グループ５０内で生成した工程フローの組合せの数だけ生成される。
【０１１１】
以上の処理を、工程グループフロー生成処理で生成したすべての工程グループフローに対して実行することにより、リソースの条件やタクトタイム等（設計情報）の条件を満たすすべての工程フローを生成することができる。
【０１１２】
＜フローチャート（工程グループ内工程フローの生成）＞
図１７は、工程設計支援装置における工程設計で、工程グループ内の工程フローの生成を行う処理フローを示したフローチャートである。本工程設計支援装置における工程グループ内工程フロー生成処理では、ステップＳ５１からステップＳ５９を実行する。
【０１１３】
ステップＳ５１では、工程グループ５０内の先頭の工程ｓ１０を選択し、次に処理を行う候補となる工程ｓ１０を保持する次候補リストへ追加する。追加する先頭の工程ｓ１０は単一でも複数でもよい。
【０１１４】
ステップＳ５２では、次候補リストにある工程ｓ１０の中で、次に実行可能な工程ｓ１０のセット（組合せ）をすべて抽出する。実行可能な工程ｓ１０とは、現在使用可能なリソースの条件（種類、数等）やタクトタイムの条件（規定時間内）等（設計情報に基づいた条件）を満たす工程ｓ１０である。リソースの条件は、工程情報２０のリソース要求仕様を参照することで判定できる。タクトタイムは、工程情報２０の工程標準時間を参照することで判定できる。本実施例ではリソースの条件やタクトタイムの条件によって、実行可能性を判定している。しかし、その他の条件で判定したい場合には、その判定に必要となる設計情報を工程情報２０に追加すればよい。
【０１１５】
ステップＳ５３では、ステップＳ５２で抽出した実行可能な工程ｓ１０のセットの中から、１つのセットを抽出する。また、抽出した実行可能な工程ｓ１０のセットを実行するのに必要となるリソースの情報（リソース要求仕様）を、参照する。そして、現在使用可能なリソースの条件を更新する。たとえば、当該リソース条件の更新は、実行するのに必要なリソース分だけ、現在使用可能なリソースから減らす等することにより、実現される。
【０１１６】
ステップＳ５４では、ステップＳ５３で抽出した１つの実行可能な工程ｓ１０のセットを、作成中のグループ内工程フローの中で最後に完了済みにした工程ｓ１０の後に、工程実行順序関係８０を付けてつなぐ。抽出した実行可能な工程ｓ１０が、工程グループ５０内で先頭の工程ｓ１０である。仮に、作成中の工程フロー５０の中で最後に完了済みにした工程ｓ１０が存在しない場合には、抽出した工程ｓ１０のみからなる工程フローとする。
【０１１７】
ステップＳ５５では、作成中の工程グループ５０内工程フローの未完了の工程ｓ１０の中から、次に実行を完了する工程ｓ１０を特定する。次に実行を完了する工程ｓ１０は、未完了の工程ｓ１０の中で、最も工程標準時間が小さいものである。また、工程ｓ１０が完了することで解放されるリソースの情報（リソース要求仕様）を参照する。そして、現在使用可能なリソースの条件を更新する（完了して空くリソース分だけ現在使用可能なリソースを増やす等）。更に、現在の工程グループ内工程フローの実行完了時間に、完了する工程ｓ１０の工程標準時間を加算して更新する。ただし、完了する工程ｓ１０が他の工程ｓ１０と並列に並んでいる場合は、それを考慮して加算する。たとえば、完了する工程ｓ１０の前につながる工程ｓ１０の完了時間に、完了する工程ｓ１０の工程標準時間を加算し、完了する工程ｓ１０までの工程グループ内工程フローの実行完了時間とする。
【０１１８】
ステップＳ５６では、工程グループ５０内のすべての工程ｓ１０に対して、ステップＳ５５までの処理が完了しているかどうかを判定する。そして、すべての工程ｓ１０に対して完了していれば、ステップＳ５８へ進み、完了していなければ、ステップＳ５７へ進む。
【０１１９】
ステップＳ５７では、ステップＳ５５で特定した工程１０が完了した後、実行可能となる工程ｓ１０を次候補リストに追加する。その後、再帰的にステップＳ５２以下を実行する。実行可能な工程ｓ１０については、ステップＳ５２で記載したとおりである。
【０１２０】
ステップＳ５８では、工程グループ５０内のすべての工程ｓ１０に対してステップＳ５５までの処理が完了しているので、作成した工程グループ内工程フローを１つの解として生成（出力）する。
【０１２１】
ステップＳ５９では、ステップＳ５２で抽出したすべての実行可能な工程ｓ１０のセットに対して、ステップＳ５８までの処理が完了したかどうかを判定し、完了していればリターンし、完了していなければステップＳ５３へ戻る。
【０１２２】
以上の処理を実行することにより、工程グループ５０内の各工程ｓ１０をリソースの条件やタクトタイムの条件を満たすように並べ替える。これにより、工程グループ内工程フローを生成することができる。
【０１２３】
このような構成によれば、工程情報２０にリソース要求仕様等の設計情報を含んでおり、その設計情報を参照して使用可能なリソースの条件を満たすように、工程設計を行うことができる。したがって、複数のリソース（設備）による協調動作を含む場合や複数の工程１０が並行して実行される場合でも、自動的に工程設計を行うことができる。また、自動的に工程情報２０（設計情報）に基づいて、関連度４０を定義している。これにより、設計者が関連度４０を定義する手間なく、よい設計解（工程フロー）をより短時間で生成することができる。
【０１２４】
また、本実施の形態では、単純に前工程ｓ１０から順に工程ｓ１０を１つずつ決定して行くような処理はしていない。本実施の形態では、工程情報２０（設計情報）に基づいて工程ｓ１０間の関連性から関連度４０を算出して定義する。そして、工程ｓ１０間の関連度４０に従って工程ｓ１０をグループとしてまとめて扱ってその並べ替えを行い、工程フロー全体で設計情報に基づく条件を評価しながら工程設計を行っている。
【０１２５】
したがって、前工程だけで判断するとあまりよい設計解ではないが、後工程まで含めて全体的に判断するとよい設計解となる場合についても、それを設計解として生成することができる。つまり、より最適な工程フローの設計解を、より短時間で設計することができる。
【０１２６】
また、本実施の形態では、工程ｓ１０間の関連度４０に基づいて、工程先行制約グラフの工程１０をグルーピングして工程グループ先行制約グラフを生成している。そして、数の多い工程ｓ１０ではなく、数の少ない工程グループ５０を並べ替えた後に、工程グループ５０を工程フローへ展開している。
【０１２７】
したがって、関連性のある工程ｓ１０が連続しやすいように、解（工程フロー）を生成することができる。また、工程設計処理の時間を大幅に短縮し、よい工程設計解を効率的（より短時間に）に生成することができる。
【０１２８】
また、本実施の形態では、工程フロー生成部１０６は、使用可能なリソース数の範囲内において、工程ｓ１０を並列化させて並べることができる。したがって、より効率の良い工程フローを作成することができる。
【０１２９】
＜実施の形態２＞
＜工程設計支援装置の構成（グルーピング可否条件調整あり）＞
図１８は、本発明の実施の形態２による工程設計支援装置の別の構成の一例を示した図である。本実施の形態に係る工程設計支援装置は、実施の形態１に係る工程設計支援装置に加えて、処理時間計測部１７０とグルーピング条件調整部１７１とを備えている。ここで、処理時間計測部１７０は、工程設計処理を実行中にその処理時間を計測することができる。グルーピング条件調整部１７１は、工程ｓ１０を工程グループ５０にグルーピングする条件を調整することができる。
【０１３０】
図１８に示した別の構成からなる工程設計支援装置によって、工程設計を行う処理フローを、下記において図１９を用いて説明する。なお、本工程設計支援装置で工程設計を行う前に、グルーピング条件を調整するかしないかを判定するための処理時間の閾値（許容最大処理時間）をあらかじめ規定しておく。
【０１３１】
＜ハードウェア構成＞
本実施の形態２の処理時間計測部１７０と、グルーピング条件調整部１７１とは、図１１に示した処理部２２２において実現される。また、本実施の形態２の他の部分については、実施の形態１で説明した図１１のものと同様である。
【０１３２】
＜フローチャート（グルーピング条件調整付き工程設計）＞
図１９は、図１８に示した構成からなる工程設計支援装置によって、工程設計（グルーピング条件調整付き工程設計）を行う処理フローを示したフローチャートである。本工程設計支援装置におけるグルーピング条件調整付き工程設計処理では、ステップＳ６１からステップＳ６８を実行する。
【０１３３】
ステップＳ６１では、工程ｓ１０を工程グループ５０にグルーピングする条件を設定する。最初に設定する場合は、規定された条件（初期条件）を設定する。例えば、関連度４０がある規定された値よりも大きい場合、つまり工程グループ５０間の関連性が高いと判断してグルーピング可と判定する場合は、「関連度４０がある規定された値よりも大きい」ということをグルーピングする条件として設定する。別の例としては、単に関連度４０の閾値をグルーピング条件として設定してもよい。ステップＳ６１を実行した後、ステップＳ６２とステップＳ６５を並列に実行する。
【０１３４】
ステップＳ６２では、図１２に示した工程設計処理を実行する。詳細な処理内容については、実施の形態１において既に記載したとおりである。
【０１３５】
ステップＳ６３では、ステップＳ６２の工程設計処理が最後まで完了したかどうかを判定し、最後まで完了していればステップステップＳ６４へ進み、最後まで完了していなければ（中断していれば）ステップＳ６８へ進む。
【０１３６】
あらかじめ規定された許容最大処理時間内で、工程設計処理が完了している。したがって、ステップＳ６４では、ステップＳ６５の処理時間計測処理を中断してグルーピング条件調整付き工程設計処理を終了する。
【０１３７】
ステップＳ６５では、ステップＳ６２で工程設計処理を実行している時間を計測する。時間の計測は、あらかじめ規定された許容最大処理時間に到達するまで継続し、許容最大処理時間に到達すると処理時間計測処理を完了する。ただし、許容最大処理時間内でステップＳ６２の工程設計処理が完了した場合は、ステップＳ６５の処理を中断する。ステップＳ６５の処理は、処理時間計測部１７０で実行する。
【０１３８】
ステップＳ６６では、ステップＳ６２の工程設計処理の実行時間が、あらかじめ規定された許容最大処理時間（閾時間と把握できる）を超過しているかどうかを判定する。もし、実行時間が許容最大処理時間を超過していれば、ステップＳ６７へ進む。他方、実行時間が許容最大処理時間を超過していなければ、グルーピング条件調整付き工程設計処理を終了する。
【０１３９】
ステップＳ６２の工程設計処理に要する時間が、あらかじめ規定された許容最大処理時間を超過している。したがって、ステップＳ６７では、ステップＳ６２の工程設計処理を中断して、ステップＳ６８へ進む。
【０１４０】
ステップＳ６８では、工程ｓ１０のグルーピングを更に行い、工程設計処理に要する時間が短くなるように、グルーピング条件を調整する。例えば、グルーピングする関連度４０の閾値を現在よりも小さくする。その場合、関連度４０の閾値を現在値よりも−１した値にした条件にしてもよいし、関連度４０の閾値を現在値の１／２の値にした条件にしてもよい。その他、現在よりグルーピングしやすくなる条件に調整することで、工程設計処理に要する時間を短くすることができる。ステップＳ６８のグルーピング条件調整処理は、グルーピング条件調整部１７１で実行する。ステップＳ６８でグルーピング条件を調整した後にステップＳ６１へ戻る。そして、新たなグルーピング条件をもちいて、ステップＳ６１以下のグルーピング条件調整付き工程設計処理を繰り返す。
【０１４１】
このような構成によれば、あらかじめ許容最大処理時間（閾時間）を規定しておくことにより、工程ｓ１０のグルーピングが不十分で工程設計処理に要する時間が大きくなる場合にでも、自動的にグルーピング条件を調整できる。よって、より短時間で工程設計処理を完了することができる。
【０１４２】
また、グルーピングをせずに工程設計を行うグルーピング条件から処理をはじめ、工程設計処理に要する時間がかかりすぎる場合には、徐々にグルーピングしやすい条件にして工程設計処理を行うことができる。これにより、最初から工程設計の解候補を大きく絞り込んで無駄な枝刈りをするということをせずに、効率的に工程設計を行うことができる。しかも、関連度４０に関する知識やノウハウがなくても自動的に工程設計を行うことができる。
【０１４３】
工程設計においては、工程ｓ１０の数の増加に伴い、並べ替えの組み合わせの数が増加し、設計解は指数関数的に増加する。逆に、工程ｓ１０をグルーピングすることによって並べ替える対象の数を少し減らせば、グルーピングした後の工程グループ５０を並べ替えて工程設計を行うことができる。よって、並べ替えの組み合わせの数を大幅に削減し、工程設計の処理時間も大幅に削減することができる。
【０１４４】
＜実施の形態３＞
＜工程設計支援装置の構成（工程先行制約グラフの分割）＞
図２０は、本発明の実施の形態３による工程設計支援装置の別の構成の一例を示した図である。本実施の形態に係る工程設計支援装置は、実施の形態１に係る工程設計支援装置に加えて、工程先行制約グラフ分割部１９０を備えている。工程先行制約グラフ分割部１９０は、工程ｓ１０間の関連度４０に基づいて、工程先行制約グラフを分割することができる。
【０１４５】
図２０に示した別の構成からなる工程設計支援装置によって、工程設計を行う処理フローを下記において、図２１，２２を用いて説明する。
【０１４６】
＜ハードウェア構成＞
本実施の形態３の工程先行制約グラフ分割部１９０は、図１１に示した処理部２２２において実現される。また、本実施の形態３の他の部分については、実施の形態１で説明した図１１の構成と同様である。
【０１４７】
＜フローチャート（工程先行制約グラフ分割付き工程設計）＞
図２１は、図２０に示した構成からなる工程設計支援装置によって工程設計（工程先行制約グラフ分割付き工程設計）を行う処理フローを示したフローチャートである。本工程設計支援装置における工程先行制約グラフ分割付き付き工程設計処理では、ステップＳ７１からステップＳ７８を実行する。
【０１４８】
ステップＳ７１では、工程先行制約グラフにおける工程ｓ１０間の工程先行制約関係３０に関連度４０を定義する。処理の詳細についてはステップＳ１の処理と同様であり、実施の形態１で既に記載したとおりである。
【０１４９】
ステップＳ７２では、工程先行制約グラフの工程先行制約関係３０に定義された関連度４０に基づいて、関連性の低い工程ｓ１０間の部分で工程先行制約グラフを切断し、工程先行制約グラフを分割する。ステップＳ７２の処理は、工程先行制約グラフ分割部１９０で実行する。
【０１５０】
ステップＳ７３では、ステップＳ７２で分割された工程先行制約グラフの１つ（部分工程先行制約グラフ）を抽出する。
【０１５１】
ステップＳ７４では、ステップＳ７３で抽出した工程先行制約グラフ（部分工程先行制約グラフ）に対し、当該部分工程先行制約グラフ内での工程グルーピング処理を実行する。これにより、ステップＳ７４では、当該部分工程先行制約グラフに対する工程グループ先行制約グラフを生成する。当該部分工程先行制約グラフ内での工程グルーピング処理の詳細については、図１１におけるステップＳ２の処理と同様であり、実施の形態１において既に記載したとおりである。
【０１５２】
ステップＳ７５では、ステップＳ７４で生成した工程グループ先行制約グラフ（部分）に対し、工程グループフロー生成処理を実行する。これにより、ステップＳ７５では、工程グループ先行制約グラフ（部分）に対する工程グループフローを生成する。工程グループ先行制約グラフ（部分）に対する工程グループフロー生成処理の詳細については、図１２におけるステップＳ３の処理と同様であり、実施の形態１において既に記載したとおりである。
【０１５３】
ステップＳ７６では、ステップＳ７５で生成した工程グループフロー（部分）に対し、工程フロー生成処理を実行する。これにより、ステップＳ７６では、工程グループフロー（部分）に対する工程フローを生成する。工程グループフロー（部分）に対する工程フロー生成処理の詳細については、図１２におけるＳ４の処理と同様であり、実施の形態１において既に記載したとおりである。
【０１５４】
ステップＳ７７では、ステップＳ７２で分割したすべての工程先行制約グラフに対して、ステップＳ７６までの処理が完了したかどうかを判定する。もし、当該処理が完了していれば、ステップＳ７８へ進む。他方、当該処理が完了していなければ、ステップＳ７３へ戻る。
【０１５５】
ステップＳ７８では、ステップＳ７２で分割したすべての工程先行制約グラフに対して生成した工程フローを、工程実行順序関係８０で互いにつないで工程フローを生成する。具体的には、各工程フロー（部分）に対して、分割前に対象の工程フロー内の工程ｓ１０の前に工程先行制約関係３０でつながっていた工程ｓ１０が属する（対象工程フロー以外の）工程フロー（部分）のすべての末尾の工程ｓ１０から、対象の工程フロー（部分）のすべての先頭の工程ｓ１０へ、工程実行順序関係８０をつなぐようにして互いの工程フローを接続する。すべての工程フロー（部分）に対して、上記の接続処理を実行するとすべての工程ｓ１０を含んだ１つの工程フローが作成される。工程フローは、分割した各工程先行制約グラフ内で生成した工程フローの組合せの数だけ生成される。
【０１５６】
以上の処理を実行することにより、入力された工程先行制約グラフを含む図２０の記憶部に格納された設計情報１０１から、工程ｓ１０間の関連度４０を算出する。そして、その関連度４０に基づいて、工程先行制約グラフを分割し、分割した部分的な工程先行制約グラフごとにリソースやタクトタイム等の条件を満たす工程フローを生成し、それらを組み合わせて最終的な工程フローを生成することができる。
【０１５７】
＜フローチャート（工程先行制約グラフの分割）＞
図２２は、工程設計支援装置における工程設計で、工程ｓ１０間の関連度４０に基づいて工程先行制約グラフを分割する処理フローを示したフローチャートである。本工程設計支援装置における工程先行制約グラフ分割処理では、ステップＳ８１からステップＳ８７を実行する。
【０１５８】
ステップＳ８１では、工程先行制約グラフから未処理の工程先行制約関係３０を１つ抽出する。
【０１５９】
ステップＳ８２では、規定された分割条件に従って、抽出した工程先行制約関係３０の部分で工程ｓ１０間を切断するかどうかを判定し、切断する場合はステップＳ８３へ進み、切断しない場合はステップＳ８４へ進む。
【０１６０】
例えば、関連度４０がある規定された値よりも小さければ、工程ｓ１０間の関連性が低いと判断して切断可と判定し、そうでなければ切断否と判定する。ただし、関連度４０がある規定された値よりも小さくても、その部分で切断することにより、分割した複数の工程先行制約グラフが並列に実行可能になる場合には、切断否とする。これは、ステップＳ７８では並列を考慮した部分工程フローの並べ替えを行わず、すべての部分工程フローを直列に並べるだけにするためである。さらに、切断可能な最大数（切断可能最大数）も規定しておき、現在の切断した回数が切断可能最大数以内であれば切断可とし、そうでなければ切断否と判定してもよい。更に工程ｓ１０間を切断するための条件であれば、その他の条件で判定してもよい。
【０１６１】
ステップＳ８３では、抽出した工程先行制約関係３０の部分で、工程先行制約グラフにおける工程ｓ１０間を切断する。
【０１６２】
ステップＳ８４では、すべての工程先行制約関係３０に対して切断可否判定処理が完了したかどうかを判定し、完了していればステップＳ８５へ進み、完了していなければステップＳ８１へ戻る。
【０１６３】
ステップＳ８５では、これまでの処理で工程ｓ１０間が切断された結果、工程先行制約グラフが分割される場合、それらの部分的な工程先行制約グラフを部分工程先行制約グラフ（部分的な工程先行制約グラフ）としてそれぞれ生成する。
【０１６４】
具体的には、例えば、工程先行制約グラフのある工程ｓ１０から工程先行制約関係３０でつながる工程ｓ１０を切断された部分まで辿ることにより、部分的な工程先行制約グラフとして生成することができる。これを工程先行制約グラフ内のすべての工程ｓ１０（特定した部分的な工程先行制約グラフに含まれる工程ｓ１０は除く）に対して実行する。これにより、分割されたすべての部分的な工程先行制約グラフを生成することができる。
【０１６５】
ステップＳ８６では、ステップＳ８５で生成された部分的な工程先行制約グラフから、分割を完了するかを判定し、分割完了する場合はリターンし、分割完了しない場合はステップＳ８７へ進む。
【０１６６】
例えば、分割数（部分的な工程先行制約グラフの数）が規定値よりも大きければ、十分に分割されていると判断して分割完了可と判定し、そうでなければ分割完了否と判定する。また、分割したすべての部分的な工程先行制約グラフの大きさ（工程ｓ１０の数）が既定値よりも小さければ、十分に分割されていると判断して分割完了可と判定し、そうでなければ分割完了否と判定してもよい。さらに、十分に分割されているかどうかを判定できる条件であれば、その他の条件で判定してもよい。
【０１６７】
ステップＳ８７では、工程先行制約グラフの分割処理において、工程ｓ１０間を切断するかどうかを判定するための切断条件を調整する。
【０１６８】
例えば、切断条件として、関連度４０がある規定された値よりも小さければ、工程ｓ１０間の関連性が低いと判断して切断可と判定し、そうでなければ切断否と判定するような場合、関連度４０の閾値を大きくする。その場合、閾値を現在値よりも＋１大きい値にした条件にしてもよいし、閾値を現在値の２倍の値にした条件にしてもよい。また、切断条件として、切断可能な最大数（切断可能最大数）も規定しておき、現在の切断した回数が切断可能最大数以内であれば切断可とし、そうでなければ切断否と判定するような場合を想定する。この場合では、切断可能最大数を＋１大きい値にした条件にしてもよいし、切断可能最大数を現在値の２倍の値にした条件にしてもよい。工程先行制約グラフがより分割しやすい条件であれば、その他の分割条件にしてもよい。
【０１６９】
このような構成によれば、工程ｓ１０間の関連度４０に基づいて、工程先行制約グラフを分割して部分的に工程設計処理を行い、それらの結果を組み合わせて最終的な工程フローを生成することができる。
【０１７０】
したがって、工程ｓ１０に複数のリソース（設備）による協調動作を含む場合や複数の工程ｓ１０が並行して実行される場合のように問題が複雑な場合でも、次の効果を有する。つまり、工程設計として意味のある部分（工程ｓ１０間の関連性が低い箇所）で工程先行制約グラフを分割することができ、工程設計解をより短時間で生成することができる。なお、実施の形態１でも説明したように、設計情報から工程ｓ１０間の関連度４０を自動的に算出して定義し、その関連度４０に基づいて複雑な問題をより解きやすい問題に分割して解くことができる。したがって、最終的な設計解を更に短時間で生成することができる。
【０１７１】
なお、当該実施の形態３に係る機能を有する工程設計支援装置と、実施の形態２に係る機能を有する工程設計支援装置とを組み合わせた、工程設計支援装置を提供することもできる。
【図面の簡単な説明】
【０１７２】
【図１】実施の形態１に係る工程設計支援装置における、部品と工程の関係を表す情報の一例を示す図である。
【図２】実施の形態１に係る工程設計支援装置における、工程の情報を表す図である。
【図３】実施の形態１に係る工程設計支援装置における、工程先行制約グラフの一例を示す図である。
【図４】実施の形態１に係る工程設計支援装置における、関連度付きの工程先行制約グラフの一例を示す図である。
【図５】実施の形態１に係る工程設計支援装置における、工程グループ先行制約グラフの一例を示す図である。
【図６】実施の形態１に係る工程設計支援装置における、工程グループの情報を表す図である。
【図７】実施の形態１に係る工程設計支援装置で生成される、工程グループフローの一例を示す図である。
【図８】実施の形態１に係る工程設計支援装置で生成される、工程フローの一例を示す図である。
【図９】実施の形態１に係る工程設計支援装置で生成される、工程フローの別の例を示す図である。
【図１０】実施の形態１に係る工程設計支援装置の構成を示す図である。
【図１１】工程設計支援装置のハードウェア構成を示す図である。
【図１２】実施の形態１に係る工程設計支援装置の工程設計処理のフローチャートである。
【図１３】実施の形態１に係る工程設計支援装置の関連度定義処理のフローチャートである。
【図１４】実施の形態１に係る工程設計支援装置の工程グルーピング処理のフローチャートである。
【図１５】実施の形態１に係る工程設計支援装置の工程グループフロー生成処理のフローチャートである。
【図１６】実施の形態１に係る工程設計支援装置の工程フロー生成処理のフローチャートである。
【図１７】実施の形態１に係る工程設計支援装置の工程グループ内工程フロー生成処理のフローチャートである。
【図１８】実施の形態２に係る工程設計支援装置の構成を示す図である。
【図１９】実施の形態２に係る工程設計支援装置のグルーピング条件調整付き工程設計処理のフローチャートである。
【図２０】実施の形態３に係る工程設計支援装置の構成を示す図である。
【図２１】実施の形態３に係る工程設計支援装置の工程先行制約グラフ分割付き工程設計処理のフローチャートである。
【図２２】実施の形態３による工程設計支援装置の工程先行制約グラフ分割処理のフローチャートである。
【符号の説明】
【０１７３】
１０ｓ  工程、１１ｐ  部品、２０  工程情報、３０  工程先行制約関係、４０  関連度、５０  工程グループ、５１  工程グループ先行制約関係、５２  グループ関連度、６０  工程グループ情報、７０  工程グループ実行順序関係、８０  工程実行順序関係、１００  工程設計処理部、１０１  設計情報記憶部、１０２  データ入出力部、１０３  工程関連定義部、１０４  工程グルーピング部、１０５  工程グループフロー生成部、１０６  工程フロー生成部、１７０  処理時間計測部、１７１  グルーピング条件調整部、１９０  工程先行制約グラフ分割部、２２０  入力部、２２１  記憶部、２２２  処理部、２２３  表示部。
【図１】
2009184028.tif 000003
【図２】
2009184028.tif 000004
【図３】
2009184028.tif 000005
【図４】
2009184028.tif 000006
【図５】
2009184028.tif 000007
【図６】
2009184028.tif 000008
【図７】
2009184028.tif 000009
【図８】
2009184028.tif 000010
【図９】
2009184028.tif 000011
【図１０】
2009184028.tif 000012
【図１１】
2009184028.tif 000013
【図１２】
2009184028.tif 000014
【図１３】
2009184028.tif 000015
【図１４】
2009184028.tif 000016
【図１５】
2009184028.tif 000017
【図１６】
2009184028.tif 000018
【図１７】
2009184028.tif 000019
【図１８】
2009184028.tif 000020
【図１９】
2009184028.tif 000021
【図２０】
2009184028.tif 000022
【図２１】
2009184028.tif 000023
【図２２】
2009184028.tif 000024