(57)【要約】【課題】既に処理した工程の結果を、その後に処理する工程の結果に基づいて修正する処理に要する時間を最小化するように、工程の処理順序を決定する。【解決手段】工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置と、第１の工程より後に処理し得る第２の工程の何れについても、第１の工程をその第２の工程より先に処理した方がその第２の工程より後に処理するよりも修正処理の所要時間が短いという条件が満たされるか否かを、記憶装置から読み出した各期待値に基づき判断する第１判断部と、条件が満たされる場合に、第１の工程を各々の第２の工程より先に処理すると決定する第１決定部と、第１決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定するスケジュール部とを備えるシステムを提供する。【選択図】図６
2008299531.tif 000002
【特許請求の範囲】
【請求項１】
複数の工程の処理順序を決定するシステムであって、
工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置と、
第１の工程より後に処理し得る第２の工程の何れについても、第１の工程をその第２の工程より先に処理した方がその第２の工程より後に処理するよりも修正処理の所要時間が短いという、第１条件が満たされるか否かを、前記記憶装置から読み出した各期待値に基づき判断する第１判断部と、
第１条件が満たされる場合に、第１の工程をそれぞれの第２の工程より先に処理すると決定する第１決定部と、
前記第１決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を出力するスケジュール部と
を備えるシステム。
【請求項２】
前記複数の工程は、ある製品を設計するために予め定められたものであり、
それぞれの工程は、その製品の一部分の設計を決定し、または、その製品の生産工程の一部分の設計を決定するものであり、
前記記憶装置は、工程の組ごとに、一方の工程より後の他方の工程を処理した場合にその一方の工程において決定した設計を他方の工程において決定した設計と整合させるために生じる設計変更の所要時間の期待値を記憶している
請求項１に記載のシステム。
【請求項３】
前記第１判断部は、さらに、第１の工程より先に処理し得る第２の工程の何れについても、第１の工程をその第２の工程より後に処理した方がその第２の工程より先に処理するよりも修正処理の所要時間が短いという、第２条件が満たされるか否かを判断し、
前記第１決定部は、第２条件が満たされる場合に、第１の工程をそれぞれの第２の工程より後に処理すると決定する
請求項２に記載のシステム。
【請求項４】
前記第１判断部は、他の工程との間の処理順序が未決定の各工程を順次第１の工程とし、その第１の工程が前記第１条件および前記第２条件の何れかを満たすか判断する処理を、前記第１条件および前記第２条件の何れかを満たす第１の工程がなくなるまで繰り返し
前記第１決定部は、前記第１判断部により前記第１条件および前記第２条件のいずれかが満たされると判断されるたびに、第１の工程およびそれぞれの第２の工程の間の処理順序を決定する
請求項３に記載のシステム。
【請求項５】
第１の工程より後であって第２の工程より先に処理し得る工程、または、第２の工程より後であって第１の工程より先に処理し得る工程の集合Ｃについて、この集合Ｃの何れの部分集合についても、第１の工程、当該部分集合内の各工程、および、第２の工程をこの順に処理した方が、第２の工程、当該部分集合内の各工程、および、当該第１の工程をこの順に処理するよりも、設計変更の所要時間を短縮できるという、第３条件が満たされるかを、前記記憶装置から読み出した各期待値に基づいて判断する第２判断部と、
第３条件が満たされる場合に、第１の工程を第２の工程より先に処理すると決定する第２決定部と
を更に備え、
前記スケジュール部は、前記第１および第２決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定する
請求項３に記載のシステム。
【請求項６】
前記記憶装置は、さらに、ある工程を他の工程よりも先に処理しなければならないことを示す順序制約を記憶しており、
前記第１判断部は、前記記憶装置から読み出した順序制約に基づき、その順序制約および既に決定した処理順序に従う範囲内で、第１の工程より先または後に処理し得る第２の工程を検索し、第１条件または第２条件を満たすか否かを判断し、
前記第２判断部は、前記記憶装置から読み出した順序制約に基づき、その順序制約および既に決定した処理順序に従う範囲内で、第１の工程より後であって第２の工程より先に処理し得る工程、または、第２の工程より後であって第１の工程より先に処理し得る工程の集合を検索し、第３条件を満たすか判断する
請求項５に記載のシステム。
【請求項７】
前記第２判断部は、それぞれの工程の組を順次第１の工程および第２の工程とし、その第１の工程および第２の工程の組が第３条件を満たすか判断する処理を、第３条件を満たす第１の工程および第２の工程の組がなくなるまで繰り返し、
前記第２決定部は、前記第２判断部により前記第３条件が満たされると判断されるたびに、第１の工程および第２の工程の間の処理順序を決定する
請求項５に記載のシステム。
【請求項８】
前記第１判断部は、前記第２決定部により処理順序が決定された後に、さらに、他の工程との間で処理順序が未決定の各工程を順次第１の工程とし、その第１の工程が前記第１条件および前記第２条件の何れかを満たすか判断する処理を、前記第１条件および前記第２条件の何れかを満たす第１の工程がなくなるまで繰り返し、
前記第２判断部は、前記第１決定部により処理順序が決定された後に、さらに、相互の処理順序が未決定の工程の各組を順次第１の工程および第２の工程とし、その第１の工程および第２の工程の組が第３条件を満たすか判断する処理を、第３条件を満たす第１の工程および第２の工程の組がなくなるまで繰り返し、
前記スケジュール部は、前記第１判断部および前記第２判断部により繰り返された判断に基づき前記第１決定部および前記第２決定部により処理順序が決定されたことに応じて、決定されたその処理順序に従う範囲内で、他の工程の処理順序を決定する
請求項７に記載のシステム。
【請求項９】
前記第２判断部は、
第２の工程を第１の工程より先に処理する場合と比較して、第１の工程を第２の工程より先に処理することで短縮できる設計変更の所要時間の期待値を算出し、
前記集合Ｃに含まれる工程のうち、第１の工程より後かつ第２の工程より先に処理する場合と比較して第２の工程より後かつ第１の工程より先に処理することにより、設計変更の所要時間の期待値を増加させる各々の工程について、その期待値の増分を算出し、
前記の短縮できる所要時間の期待値が前記の期待値の増分の合計以上であることを条件に、第３条件を満たすと判断する
請求項５に記載のシステム。
【請求項１０】
前記第１決定部および前記第２決定部の少なくとも何れかによって第１の工程および第２の工程の間の処理順序が新たに決定されたことに応じ、第１の工程より先に処理することが既に決定されている第３の工程を、第２の工程より先に処理すると決定し、第２の工程より後に処理することが既に決定されている第４の工程を、第１の工程より後に処理すると決定する第３決定部を更に備える、請求項５に記載のシステム。
【請求項１１】
前記記憶装置は、さらに、第１の工程を第２の工程よりも先に処理しなければならないことを示す順序制約を複数記憶しており、
前記第３決定部は、ある順序制約に規定された前記第１の工程より先に処理することが他の順序制約により規定されている第３の工程を、当該順序制約に規定された前記第２の工程より先に処理すると決定し、当該第２の工程より後に処理することが他の順序制約により規定されている第４の工程を、当該第１の工程より後に処理すると決定する、請求項１０に記載のシステム。
【請求項１２】
前記スケジュール部は、
前記第１決定部および前記第２決定部によっては処理順序が決定しなかった工程の集合である未決定集合に含まれる各工程について、その工程を未決定集合の中で最初に処理すると仮定した場合におけるその未決定集合の中における各工程の処理順序を、前記第１決定部および前記第２決定部により決定し、
決定した各処理順序のうち、設計変更による所要時間の期待値が最も小さい処理順序を選択して出力する
請求項５に記載のシステム。
【請求項１３】
前記複数の工程は、自動車を設計するために予め定められたものであり、
それぞれの工程は、その自動車の部品の形状および材料の少なくとも一部を決定し、または、その自動車の生産工程の少なくとも一部を決定するものであり、
前記記憶装置は、工程の組ごとに、一方の工程より後の他方の工程を処理した場合にその一方の工程において決定した設計を他方の工程において決定した設計と整合させるために生じる設計変更の所要時間の期待値を記憶しており、
前記スケジュール部は、前記第１決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を自動車の設計順序として出力する
請求項２に記載のシステム。
【請求項１４】
工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために修正処理が生じる確率の入力、および、その一方の工程の結果をその他方の工程の結果に整合させるための処理時間の入力を受け付け、工程の組ごとに受け付けた確率および所要時間の積を算出し、処理時間の期待値として前記記憶装置に格納する、入力部を更に備える請求項２に記載のシステム。
【請求項１５】
複数の工程の処理順序を決定するシステムであって、
工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置と、
第１の工程より先に処理し得る第２の工程の何れについても、第１の工程をその第２の工程より後に処理した方がその第２の工程より先に処理するよりも修正処理の所要時間の期待値が短縮できるという、第２条件を満たすか否かを、前記記憶装置から読み出した各期待値に基づき判断する第１判断部と、
第２条件を満たす場合に、第１の工程をそれぞれの第２の工程より後に処理すると決定する第１決定部と、
前記第１決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を出力するスケジュール部と
を備えるシステム。
【請求項１６】
複数の工程の処理順序を決定するシステムであって、
工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置と、
第１の工程より後であって第２の工程より先に処理し得る工程、または、第２の工程より後であって第１の工程より先に処理し得る工程の集合Ｃについて、集合Ｃの何れの部分集合についても、第１の工程、当該部分集合内の各工程、および、第２の工程をこの順に処理した方が、第２の工程、当該部分集合内の各工程、および、当該第１の工程をこの順に処理するよりも、設計変更の所要時間の期待値を短縮できるという、第３条件を満たすかを、前記記憶装置から読み出した各期待値に基づいて判断する第２判断部と、
第３条件を満たす場合に、第１の工程を第２の工程より先に処理すると決定する第２決定部と
前記第２決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を出力するスケジュール部と
を備えるシステム。
【請求項１７】
複数の工程の処理順序を決定するシステムとしてコンピュータを機能させるプログラムであって、
工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置を有するコンピュータを、
第１の工程より後に処理し得る第２の工程の何れについても、第１の工程をその第２の工程より先に処理した方がその第２の工程より後に処理するよりも修正処理の所要時間が短いという、第１条件が満たされるか否かを、前記記憶装置から読み出した各期待値に基づき判断する第１判断部と、
第１条件が満たされる場合に、第１の工程をそれぞれの第２の工程より先に処理すると決定する第１決定部と、
前記第１決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を出力するスケジュール部と
して機能させるプログラム。
【請求項１８】
複数の工程の処理順序を決定するシステムとして、コンピュータを機能させるプログラムであって、
工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置を有するコンピュータを、
第１の工程より後であって第２の工程より先に処理し得る工程、または、第２の工程より後であって第１の工程より先に処理し得る工程の集合Ｃについて、集合Ｃの何れの部分集合についても、第１の工程、当該部分集合内の各工程、および、第２の工程をこの順に処理した方が、第２の工程、当該部分集合内の各工程、および、当該第１の工程をこの順に処理するよりも、設計変更の所要時間の期待値を短縮できるという、第３条件を満たすかを、前記記憶装置から読み出した各期待値に基づいて判断する第２判断部と、
第３条件を満たす場合に、第１の工程を第２の工程より先に処理すると決定する第２決定部と
前記第２決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を出力するスケジュール部と
して機能させるプログラム。
【請求項１９】
複数の工程の処理順序をコンピュータにより決定する方法であって、
前記コンピュータは、工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置を有し、
第１の工程より後に処理し得る第２の工程の何れについても、第１の工程をその第２の工程より先に処理した方がその第２の工程より後に処理するよりも修正処理の所要時間が短いという、第１条件が満たされるか否かを、前記記憶装置から読み出した各期待値に基づき判断するステップと、
第１条件が満たされる場合に、第１の工程をそれぞれの第２の工程より先に処理すると決定するステップと、
このステップにより決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を出力するステップと
を備える方法。
【請求項２０】
複数の工程の処理順序をコンピュータにより決定する方法であって、
前記コンピュータは、工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置を有し、
第１の工程より後であって第２の工程より先に処理し得る工程、または、第２の工程より後であって第１の工程より先に処理し得る工程の集合Ｃについて、集合Ｃの何れの部分集合についても、第１の工程、当該部分集合内の各工程、および、第２の工程をこの順に処理した方が、第２の工程、当該部分集合内の各工程、および、当該第１の工程をこの順に処理するよりも、設計変更の所要時間の期待値を短縮できるという、第３条件を満たすかを、前記記憶装置から読み出した各期待値に基づいて判断するステップと、
第３条件を満たす場合に、第１の工程を第２の工程より先に処理すると決定するステップと、
このステップにより決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を出力するステップと
を備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、工程の処理順序を決定する技術に関する。特に、本発明は、工程の処理順序によっては、先に処理した工程の結果を後に修正し得る場合において、工程の処理順序を適切に決定する技術に関する。
【背景技術】
【０００２】
自動車などの製品の設計工程においては完成までの期間の短縮が費用および利益の観点から重要である。そこでエンジニアの作業時間を短縮するために、最適な設計を自動的に生成したり、決定すべきパラメータの最適値を自動的に決定する技術が提案されている（特許文献１−４を参照。）。例えば、特許文献１は、設計の中で決定すべきパラメータ値を自動的に最適に決定するための技術を開示している。特許文献２は壁パネルの最適な配置設計を求める技術を開示している。特許文献３および４は回路の設計において、回路のパラメータを最適化するための技術を開示している。
【０００３】
【特許文献１】特開２００４−０３０６６１号公報
【特許文献２】特開２０００−２３５５９１号公報
【特許文献３】特開平５−１７４０９２号公報
【特許文献４】特開２０００−２９９１９号公報
【非特許文献１】T. R. Browning, "Applying the Design Structure Matrix to System Decomposition and Integration Problems: A Review and New Directions," IEEE Transactions on Engineering Management, 48(3): 292-306, 2001. http://www.iese.uiuc.edu/pdlab/GE498AY/4DSMs.pdf
【非特許文献２】R. P. Smith and S. D. Eppinger, "A predictive model of sequential iteration in engineering design," Management Science, 43(8): 1104-1120, 1997. http://web.mit.edu/eppinger/www/pdf/Smith_MS_Aug1997.pdf
【非特許文献３】J. L. Rogers, "Integrating a genetic algorithm into a knowledge-based system for ordering complex design processes," NASA, Hampton, VA, TM-110 247, 1996. http://citeseer.ist.psu.edu/cache/papers/cs/3461/ftp:zSzzSztechreports.larc.nasa.govzSzpubzSztechreportszSzlarczSz96zSzNASA-96-tm110247.pdf/rogers96integrating.pdf
【非特許文献４】Steven D. Eppinger, "Model-Based Approaches to Managing Concurrent Engineering," Journal of Engineering Design, vol. 2, no. 4, pp. 283-290, 1991.  http://web.mit.edu/eppinger/www/pdf/Eppinger_JED_1991.pdf
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、自動車やその部品の設計は非常に複雑であり、コンピュータを用いてそれらを自動化する技術は提案されていない。さらに、自動車などの大規模な製品の設計は膨大な数の工程を要し、また、それぞれの工程は相互に依存することもあるので、どの工程から順に開始するかを決定することさえも非常に困難である。たとえば、ある２つの工程が相互に依存する場合には、そのどちらの工程を先に処理しても、既に処理した工程の結果を、その後に処理した工程の結果と整合するように修正しなければならない場合がある。この修正の処理に要する時間は工程の処理順序によって異なる。したがって、工程の処理順序を適切に決定しなければ、修正の処理に要する時間の合計が膨大となって設計全体の効率を低下させてしまうおそれがある。
【０００５】
参考技術として、作業手順を適切に決定するための技術（非特許文献１−４を参照。）を挙げる。これらの技術を、自動車の設計工程に応用できるとも考えられる。しかしながら、非特許文献１の技術を自動車に応用した場合、工程の数が多すぎて現実的な時間で順序決定のための計算が完了しない。また、非特許文献２−３の技術は、最適な順序を近似的に算出するものであるため、決定した処理順序に改善の余地がある場合がある。
そこで本発明は、上記の課題を解決することのできるシステム、方法およびプログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明の第１の形態においては、複数の工程の処理順序を決定するシステムであって、工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために生じる修正処理の所要時間の期待値を記憶している記憶装置と、第１の工程より後に処理し得る第２の工程の何れについても、第１の工程をその第２の工程より先に処理した方がその第２の工程より後に処理するよりも修正処理の所要時間が短いという、第１条件が満たされるか否かを、前記記憶装置から読み出した各期待値に基づき判断する第１判断部と、第１条件が満たされる場合に、第１の工程をそれぞれの第２の工程より先に処理すると決定する第１決定部と、前記第１決定部により決定された処理順序に従う範囲内で、他の工程の処理順序を決定して、決定した処理順序を出力するスケジュール部とを備えるシステムを提供する。また、当該システムとしてコンピュータを機能させるプログラム、および、当該システムにより工程の処理順序を決定する方法を提供する。
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明を実施するための最良の形態】
【０００７】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【０００８】
図１は、本実施の形態に係る決定システム１０の全体構成を示す。決定システム１０は、入力部１００と、記憶装置１１０と、本体部１２０とを備える。入力部１００は、確率データ２０、処理時間データ３０および順序制約データ４０の入力を受け付ける。確率データ２０は、工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるために修正処理が生じる確率を示す。処理時間データ３０は、工程の組ごとに、一方の工程より後に他方の工程を処理した場合にその一方の工程の結果をその他方の工程の結果に整合させるための処理時間を示す。順序制約データ４０は、ある第１の工程を他の第２の工程よりも先に処理しなければならない制約を複数含んでいる。
【０００９】
入力部１００は、工程の組ごとに、入力を受け付けた確率および処理時間の積を算出し、修正処理の所要時間の期待値を表す期待値データ５０を生成して、記憶装置１１０に格納する。また、入力部１００は、入力を受け付けた順序制約データ４０を記憶装置１１０に格納する。本体部１２０は、これらのデータに基づいて、全ての工程を設計に矛盾が無いように完了させることを前提に、修正処理の所要時間の期待値を最小化できるような、工程の最適な処理順序を決定して出力する。
【００１０】
図２ａは、本実施の形態に係る確率データ２０のデータ構造の第１例を示す。自動車などの製品を設計する場合において、各工程はその製品の一部分の要素の設計を決定するために予め定められている。ここで、製品の一部分の要素とは、その製品の部分または部品のことをいう。例えば、図２ａに示す４つの工程は、それぞれ、自動車の部分または部品である、「ドアオープニングライン」、「Ａピラー板厚」、「Ａピラー基本断面」および「フロントガラスモール」の設計を決定する工程である。ある部分または部品の設計を決定する、とは、その部分または部品の形状および材料の少なくとも１つを決定することをいう。より具体的には、部品の設計の決定には、部品の形状を決定するためにその長さ、幅、厚みまたは角度などの数値を決定することが含まれる。これに加えて、各工程は、その製品の生産工程の一部分の設計を決定するために予め定められたものであってもよい。例えば、各工程は、金属板を金型でプレス加工する生産工程において、使用する金型の形状および金型の数の少なくとも一方を決定するものであってもよい。
【００１１】
図２ａに示す確率データ２０によると、Ａピラー基本断面の設計を決定する工程の後に、Ａピラー板厚の設計を決定する工程を処理した場合において、先に処理したＡピラー基本断面の設計に戻ってその内容を修正しなければならない確率は８０％である。他の工程の組についての数値の意味は同様であり、例えばＡピラー板厚を先に、フロントガラスモールをその後に決定した場合において、その決定と先に決定したＡピラー板厚の設計との間に矛盾が生じたために修正しなければならない確率は５０％である。空欄は修正処理が発生しないこと、即ち確率が０％であることを示す。
図２ａは、製品の設計を決定するために必要な数多くの工程の一部を抽出して例示的に説明するものである。この例示を拡張・一般化して、２６の工程について修正処理の発生確率を図式化したものを図２ｂに示す。
【００１２】
図２ｂは、本実施の形態に係る確率データ２０のデータ構造の第２例を示す。この第２例では、各工程の識別子をアルファベット一文字で表している。実際には各工程には、製品またはその生産工程のどの部分の設計を決定するか、あるいは、どのような数値を決定するか、という、具体的な設計の内容が予め対応して定められている。また、先に処理する工程の識別子を行方向に、後に処理する工程の識別子を列方向に配列して示し、各工程の組に対応する数値は修正処理の発生確率を示す。一例として、工程ｃを先に、工程ａをその後（工程ｃの次とは限らない）に処理した場合において、工程ｃの結果を修正する処理が発生する確率は２０％である。
【００１３】
以上のように図２ａ−ｂとして示した確率の数値は、製品を設計するエンジニアによって決定されて入力されてもよいし、過去に類似の製品を設計した場合の作業日誌に基づいて算出されて入力されてもよい。以降、工程ａより後に工程ｂを処理した場合にその工程ａの結果を工程ｂの結果に整合させるために修正処理が生じる確率を、関数ｐを用いて、ｐ［ｂ］［ａ］と表す。
【００１４】
図３ａは、本実施の形態に係る処理時間データ３０のデータ構造の第１例を示す。図３ａは、図２ａに示す４つの工程、即ち、「ドアオープニングライン」、「Ａピラー板厚」、「Ａピラー基本断面」および「フロントガラスモール」の設計を決定する工程に対応している。そして、処理時間データ３０は、これらの工程のうち任意の２つの工程の組のそれぞれについて、一方の工程より後に他方の工程を処理した場合にその一方の工程において決定した設計をその他方の工程において決定した設計と整合させるために生じる設計変更の、平均の処理時間を示している。
【００１５】
具体的には、Ａピラー基本断面の設計を決定する工程の後に、Ａピラー板厚の設計を決定する工程を処理した場合において、先に設計したＡピラー基本断面を修正するために要する処理時間の平均は４時間である。他の工程の組についても数値の意味は同様であり、例えばＡピラー板厚を先に、フロントガラスモールをその後に決定した場合において、先に決定したＡピラー板厚の設計を修正するために要する処理時間の平均は８時間である。
図３ａは、製品の設計を決定するために必要な数多くの工程の一部を抽出して例示的に説明するものである。この例示を拡張・一般化して、２６の工程について修正の処理時間を図式化したものを図３ｂに示す。
【００１６】
図３ｂは、本実施の形態に係る処理時間データ３０のデータ構造の第２例を示す。この第２例は、図２ｂに示す確率データ２０に対応しており、各工程の識別子をアルファベット一文字で表している。実際には各工程には、製品またはその生産工程のどの部分の設計を決定するか、あるいは、どのような数値を決定するか、という、具体的な設計の内容が予め対応して定められている。また、先に処理する工程の識別子を行方向に、後に処理する工程の識別子を列方向に配列して示し、各工程の組に対応する数値は修正の処理時間の平均を示す。一例として、工程ｃを先に、工程ａをその後に処理した場合において、工程ｃの結果を修正する処理時間の平均は８時間である。
【００１７】
以上のように図３ａ−ｂとして示した修正の処理時間の数値は、製品を設計するエンジニアによって決定されて入力されてもよいし、過去に類似の製品を設計した場合の作業日誌に基づいて算出されて入力されてもよい。以降、工程ａより後に工程ｂを処理した場合にその工程ａの結果を工程ｂの結果に整合させるために必要な修正の処理時間を、関数ｗを用いて、ｗ［ｂ］［ａ］と表す。
【００１８】
図４は、本実施の形態に係る順序制約データ４０のデータ構造の一例を示す。特定の工程の組については、一方の工程を必ず先に処理しなければ、他方の工程を全く処理できない場合がある。入力部１００は、このような特定の組とその処理の順序とを示す情報として順序制約データ４０の入力を受け付ける。図４に示す順序制約データ４０の例では、各工程の識別子をアルファベット一文字で表している。実際には各工程には、製品またはその生産工程のどの部分の設計を決定するか、などの具体的な設計の内容が予め対応して定められている。また、先に処理する工程の識別子を列方向に、後に処理する工程の識別子を行方向に配列して示す。
【００１９】
ある工程ａを先に、工程ｂをその後に処理しなければならない順序制約をｃｏｎｓｔｒａｉｎｔ（ａ，ｂ）＝１およびｃｏｎｓｔｒａｉｎｔ（ｂ，ａ）＝−１と表す。即ち、数値１は、ある工程の順列についてその順に処理しなければならない順序制約があることを示し、数値−１は、その逆順に処理しなければならない順序制約があることを示す。図４は、このような関数ｃｏｎｓｔｒａｉｎｔの数値を、任意の２つの工程の順列について表したものである。一例として、工程ｉは工程ｊよりも先に処理しなければならないことを表している。
【００２０】
他の例として、入力部１００は、順序制約データ４０の入力を受け付けなくてもよい。この場合には、入力部１００は、順序制約を修正処理の発生確率および修正時間に反映させた確率データ２０および処理時間データ３０の入力を受け付ける。例えば、この確率データ２０は、その順序制約に反する順序で工程を処理した場合の修正処理の発生確率として、例えば１００％などの極めて高い数値を含む。同様に、処理時間データ３０は、その順序制約に反する順序で工程を処理した場合の修正処理の時間として、例えば全工程の組合せの中で最大の修正時間と同一の修正時間などの、極めて大きい数値を含む。このように、順序制約データ４０の入力は必須ではなく、順序制約データ４０を用いずとも順序制約を実質的に反映して処理順序を決定することもできる。
【００２１】
入力部１００は、以上のように確率データ２０、処理時間データ３０、および、必要に応じてさらに順序制約データ４０の入力を受け付けると、続いて確率データ２０および処理時間データ３０に基づいて期待値データ５０を生成して、記憶装置１１０に格納する。この結果として記憶装置１１０が記憶する期待値データ５０の一例を図５に示す。
図５は、本実施の形態に係る期待値データ５０のデータ構造の一例を示す。入力部１００が算出する修正処理の所要時間の期待値は、工程の組ごとに入力を受け付けた確率および処理時間の積である。図５は、この所要時間の積を示す数値を示している。また、先に処理する工程の識別子を行方向に、後に処理する工程の識別子を列方向に配列した表形式によって表している。一例として、工程ｃを先に、工程ａをその後に処理した場合における所要時間の期待値は１．６時間である。以降、工程ａより後に工程ｂを処理した場合にその工程ａの結果を工程ｂの結果に整合させるための修正処理の所要時間の期待値を、関数ｔを用いて、ｔ［ｂ］［ａ］と表す。ｔ［ｂ］［ａ］＝ｐ［ｂ］［ａ］×ｗ［ｂ］［ａ］である。
【００２２】
図６は、本実施の形態に係る本体部１２０の機能構成を示す。本体部１２０は、第１判断部６００と、第１決定部６１０と、第３決定部６２０と、第２判断部６３０と、第２決定部６４０と、スケジュール部６５０とを有する。これらの各部は、後述のＣＰＵ１０００が、コンピュータにインストールされたプログラムを実行することによって実現される。第１判断部６００は、他の何れかの工程との間で処理順序が未決定の工程を順次選択する。選択した工程を第１の工程と呼ぶ。そして、第１判断部６００は、選択したその第１の工程が予め定められた第１条件および第２条件の何れかを満たすかを判断する。
【００２３】
第１条件は、その第１の工程より後に処理し得る第２の工程の何れについても、その第１の工程をその第２の工程より先に処理した方がその第２の工程より後に処理するよりも修正処理の所要時間が「短くなる」という条件である。この「短くなる」という条件は、「長くならない」という条件であってもよい。即ち、何れの第２の工程についても、第１の工程をその先に処理した方が所要時間が短いか等しい場合に、第１条件が満たされると判断してもよい。このように等しい場合も条件成立とすることで、第１条件が満たされ易くなるので、工程の最適順序を探索する空間を一層狭めることができる。
【００２４】
また、第２条件は、その第１の工程より先に処理し得る第２の工程の何れについても、第１の工程をその第２の工程より後に処理した方がその第２の工程より先に処理するよりも修正処理の所要時間が「短くなる」という条件である。この「短くなる」という条件は、「長くならない」という条件であってもよい。即ち、何れの第２の工程についても、第１の工程をその後に処理した方が所要時間が短いか等しい場合に、第２条件が満たされると判断してもよい。このように等しい場合も条件成立とすることで、第２条件が満たされ易くなるので、工程の最適順序を探索する空間を一層狭めることができる。これらの第１および第２条件の判断は、記憶装置１１０から読み出した、工程の組の各々についての所要時間の期待値に基づいて行われる。
【００２５】
そして、第１決定部６１０は、第１条件が満たされると判断されるたびに、第１の工程をそれぞれの第２の工程より先に処理すると決定する。また、第１決定部６１０は、第２条件が満たされると判断されるたびに、第１の工程をそれぞれの第２の工程より後に処理すると決定する。決定された順序は、記憶装置１１０に格納される。ある工程ａの次に工程ｂを処理すると決定してそれを記憶装置１１０に格納することを、以降の説明ではｄｏＢｅｆｏｒｅ［ａ］［ｂ］＝１、および、ｄｏＢｅｆｏｒｅ［ｂ］［ａ］＝−１という式で表す。なお、ｄｏＢｅｆｏｒｅは、第１引数の工程の後に第２引数の工程を処理する場合に１を、その逆の順に処理する場合に−１を、順序が未決定の場合に０を返す関数である。
【００２６】
第１判断部６００は、第１条件および第２条件についてのこれらの判断を、第１決定部６１０または後述の第２決定部６４０等によって次々に順序が決定された結果第１条件および第２条件の何れかを満たす第１の工程がなくなるまで繰り返す。
【００２７】
第３決定部６２０は、第１決定部６１０および後述の第２決定部６４０の少なくとも何れかによって新たに順序が決定されたことに応じ、その決定された順序に基づき推移法則を適用して新たに順序を決定する。具体的には、第１の工程および第２の工程をこの順に処理すると決定された場合において、第３決定部６２０は、第１の工程より先に処理することが既に決定されている第３の工程を、第２の工程より先に処理すると決定する。また、第３決定部６２０は、第２の工程より後に処理することが既に決定されている第４の工程を、第１の工程より後に処理すると決定する。
【００２８】
第２判断部６３０は、相互の処理順序が未決定の工程の各組を順次選択する。選択した工程の組を第１の工程および第２の工程と呼ぶ。そして、第２判断部６３０は、第１の工程より後であって第２の工程より先に処理し得る工程の集合Ｃを求める。集合Ｃは、既に第１決定部６１０または第２決定部６４０により決定され、記憶装置１１０に格納された処理順序（即ちｄｏＢｅｆｏｒｅの値）、および、順序制約データ４０に基づいて求められる。そして、第２判断部６３０は、集合Ｃの何れの部分集合についても、第１の工程、当該部分集合内の各工程、および、第２の工程をこの順に処理した方が、第２の工程、当該部分集合内の各工程、および、第１の工程をこの順に処理するよりも、設計変更の所要時間を「短縮できる」という、第３条件が満たされるかを判断する。この判断は、記憶装置１１０から読み出した所要時間についての各期待値に基づいて行われる。なお、この「短縮できる」という条件は、「増加させない」という条件であってもよい。即ち、第１の工程、部分集合内の各工程、および、第２の工程をこの順に処理した方が、第２の工程、部分集合内の各工程、および、第１の工程をこの順に処理するよりも、設計変更の所要時間を短縮できるか、あるいは、変化しない場合に、第３条件が満たされると判断してもよい。このように等しい場合も条件成立とすることで、第３条件が満たされ易くなるので、工程の最適順序を探索する空間を一層狭めることができる。
【００２９】
第２決定部６４０は、この第３条件が満たされると判断されるたびに、第１の工程を第２の工程より先に処理すると決定する。第２判断部６３０は、以上の第３条件についての判断を、第３条件を満たす第１の工程および第２の工程の組がなくなるまで繰り返す。
以上、第１−第３の何れの条件も満たされなくなった時点において決定済の処理順序は、記憶装置１１０から読み出され、第２判断部６３０からスケジュール部６５０に対し出力される。この処理順序を示すデータを部分順序データ１５０とする。
【００３０】
次に、スケジュール部６５０は、順序制約データ４０に規定された順序制約、ならびに、第１決定部６１０、第２決定部６４０および第３決定部６２０により決定された処理順序に従う範囲内で、順序未決定の工程の集合である未決定集合内の工程の処理順序を決定して、決定した処理順序を出力する。処理順序の決定は、例えば、全数探索、動的計画法または局所探索法によるものであってよい。全数探索は、例えば、未決定集合内の工程の組合せの中で決定可能な全ての順序について、その順序を決定したと仮定した場合の修正処理の所要時間の合計を求め、その合計を最小とする順序を決定順序とすることをいう。このような全数探索などの方法は、工程の数が多いと現実的な時間で完了しないか、あるいは、完了するとしても十分に効率的な解が得られない場合がある。ただし、第１決定部６１０および第２決定部６４０により未決定の工程数を十分に減少して探索空間を狭めることができるので、現実的な時間で完了させることができる。
【００３１】
他の方法として、スケジュール部６５０は、以下の方法によって未決定部分の順序を決定してもよい。スケジュール部６５０は、まず、未決定集合を示す未決定データ１７０を決定システム１０から読み出す。そして、スケジュール部６５０は、未決定集合に含まれる各工程について、その工程を未決定集合の中で最初に処理すると仮定した場合におけるその未決定集合の中における各工程の処理順序を、第１決定部６１０および第２決定部６４０を再帰的に利用することにより決定する。これは、例えば、未決定集合中の工程の処理順序を決定する問題を部分問題とし、その部分問題を示す部分問題データ１７５を記憶装置１１０に格納したうえで、第１判断部６００に処理開始を指示することによって実現される。
【００３２】
未決定集合は第１決定部６１０および第２決定部６４０によっては順序が決定されなかった工程の集合であるから、未決定集合の中でどの工程を最初に処理すると最適であるかは、第１決定部６１０および第２決定部６４０により決定不能である。しかしながら、未決定集合の中で最初に処理するべき工程を仮定してしまえば、その残りの工程の処理順序を第１決定部６１０および第２決定部６４０により決定できる場合がある。スケジュール部６５０は、このようにして複数の工程の各々を最初に処理すると仮定した場合における最適な処理順序の各々を求める。そして、スケジュール部６５０は、求めた処理順序のうち最も修正処理の所要時間が短い処理順序を選択して、処理順序データ１６０に含めて出力する。
【００３３】
以下、図７から図１９を参照して、順序決定の各処理について更に詳しく説明する。
図７は、本実施の形態に係る決定システム１０の処理段階の概要を示すフローチャートである。入力部１００は、確率データ２０、処理時間データ３０および順序制約データ４０の入力を受け付ける（Ｓ７００）。製品の設計に必要な工程がまだ入力されていない場合には、入力部１００は、これらの入力も更に受け付ける。入力部１００は、確率データ２０および処理時間データ３０に基づいて期待値データ５０を算出して、順序制約データ４０と共に記憶装置１１０に格納する。これに加えて、入力部１００は、決定済みの処理順序を記憶するための領域を記憶装置１１０内に確保してもよい。
【００３４】
そして、順序制約データ４０を入力した場合には、入力部１００は、以下のＳ７０２およびＳ７０４の処理を行う。まず、入力部１００は、順序制約データ４０に規定された順序制約を、決定済みの処理順序を記憶するためのその領域に複写して、決定済みの処理順序とする（Ｓ７０２）。このようにすれば、以降の処理において順序制約を特に別途に考慮しなくてよい。そして、入力部１００は、それぞれの順序制約について第３決定部による処理をさせる（Ｓ７０４）。具体的には、入力部１００は、各順序制約について、その順序制約において先に処理することが規定されている第１の工程を第１引数とし、その順序制約において後に処理することが規定されている第２の工程を第２引数として、第３決定部６２０に処理をさせる。これにより、第３決定部６２０は、その第１の工程より先に処理することが他の順序制約により規定されている第３の工程を、その第２の工程より先に処理すると決定し、その第２の工程より後に処理することが他の順序制約により規定されている第４の工程をその該第１の工程より後に処理すると決定する。この結果、以降に順次決定する順序と順序制約とが矛盾することを防止できる。
【００３５】
次に、第１判断部６００は、第１条件および第２条件のいずれかを満たす工程の検出を試みる（Ｓ７０５）。検出されたことを条件に（Ｓ７１０：ＹＥＳ）、第１決定部６１０は、第１の工程およびそれぞれの第２の工程の間の処理順序を決定する（Ｓ７２０）。その後に決定システム１０はＳ７０５に処理を戻して、他の工程が第１条件および第２条件のいずれかを満たすか更に判断する。一方、第１条件または第２条件を満たす工程が検出されないことを条件に（Ｓ７１０：ＮＯ）、第２判断部６３０は、第３条件を満たす工程の検出を試みる（Ｓ７３０）。検出されたことを条件に（Ｓ７４０：ＹＥＳ）、第２決定部６４０は、第１の工程および第２の工程の間の処理順序を決定する（Ｓ７５０）。
【００３６】
その後に決定システム１０は、Ｓ７０５に処理を戻す。この結果、第１判断部６００は、第２決定部６４０により処理順序が決定された後に、その決定によって新たに第１または第２条件が満たされるようになったか否かをさらに判断する。一方、第３条件を満たす工程が検出されない場合には（Ｓ７４０：ＮＯ）、この場合には第１条件または第２条件を満たす工程も検出できないので、スケジュール部６５が、別の方法によって、順序未決定の他の工程についての処理順序を決定する（Ｓ７６０）。
【００３７】
図８は、Ｓ７０５における処理の詳細を示すフローチャートである。まず、第１判断部６００は、製品の設計に必要な全ての工程の集合をＣとする（Ｓ８００）。次に、第１判断部６００は、集合Ｃが空集合か否かを判断する（Ｓ８１０）。空集合であれば（Ｓ８１０：ＹＥＳ）、第１判断部６００は、第１条件および第２条件のいずれかを満たす工程が検出されないと判断する（Ｓ８６０）。一方、空集合でなければ（Ｓ８１０：ＮＯ）、第１判断部６００は、集合Ｃから工程を１つ取得する。工程を取得する、とは、集合Ｃから工程を選択したうえで、選択したその工程を集合Ｃから取り除くことをいう。このような集合の操作は、集合に含まれる各工程の識別子をＲＡＭ１０２０などのメモリに記憶したうえで、そのＲＡＭ１０２０に読出しや書込みのアクセスをすることによって実現される。このような集合操作やこれに類する操作の実現方法は、当業者にとって自明なものであるから以降その詳細な説明を省略する。
【００３８】
Ｓ８２０において取得した工程を工程ａとする。工程ａは本発明に係る第１の工程の候補となる工程である。続いて、第１判断部６００は、この工程ａが第１条件および第２条件のいずれかを満たすか判断する（Ｓ８３０）。何れも満たさないことを条件に（Ｓ８４０：ＮＯ）、第１判断部６００は、Ｓ８１０に処理を戻し、第１条件および第２条件のいずれかを満たすか順次判断する処理を、第１条件および第２条件のいずれかを満たす第１の工程がなくなるまで繰り返す。一方、第１条件および第２条件のいずれかが満たされることを条件に（Ｓ８４０：ＹＥＳ）、第１判断部６００は、第１条件および第２条件のいずれかを満たす工程が検出されたと判断し、第１条件を満たす場合には数値１を、第２条件を満たす場合には数値−１をそれぞれ第１決定部６１０に対し出力する（Ｓ８５０）。
【００３９】
図９ａは、Ｓ８３０における処理の詳細を示すフローチャートである。第１判断部６００は、第１の工程の候補として選択した工程ａとの間で処理順序が未決定の他の工程ｃがあるか否かを判断する（Ｓ９００）。この判断は、数式を用いて、「ａ≠ｃかつｄｏＢｅｆｏｒｅ［ａ］［ｃ］＝０を満たすｃが存在するか？」と表される。実現方法の１つとして、第１判断部６００は、記憶装置１１０に記憶された決定済みの順序にアクセスして、工程ａが何れかの工程との間で順序が未決定かどうかを判断すればよい。そのような工程ｃがなければ（Ｓ９００：ＮＯ）、第１判断部６００は、工程ａが第１条件および第２条件の何れも満たさないと判断する（Ｓ９９０）。
【００４０】
そのような工程ｃがあれば（Ｓ９００：ＹＥＳ）、第１判断部６００は、工程ａより先に処理し得る工程の集合をＣとする（Ｓ９１０）。工程ａより先に処理し得る工程の集合とは、順序制約データ４０により規定される順序制約、ならびに、第１決定部６１０、第３決定部６２０および第２決定部６４０の何れかによって既に決定された処理順序に従っても、工程ａより先に処理する可能性のある工程の集合のことをいう。この集合Ｃは、数式を用いて、ｃ≠ａかつｄｏＢｅｆｏｒｅ［ｃ］［ａ］≠１を満たすｃの集合として表される。
【００４１】
次に、第１判断部６００は、工程Ｃが空集合か否かを判断する（Ｓ９２０）。Ｃが空集合であれば（Ｓ９２０：ＹＥＳ）、第１判断部６００は、工程ａが第１条件を満たすと判断し、数値１を出力する（Ｓ９２５）。Ｃが空集合でなければ（Ｓ９２０：ＮＯ）、第１判断部６００は、集合Ｃから工程を１つ取得して、工程ｃとする（Ｓ９３０）。この工程ｃは、工程ａより後に処理し得る工程、即ち第２の工程の一例である。次に、第１判断部６００は、工程ａをその工程ｃより先に処理した方がその工程ｃより後に処理するよりも修正時間の所要時間が長くないかどうかを判断する（Ｓ９４０）。この判断は、数式を用いて、「ｔ［ａ］［ｃ］＜ｔ［ｃ］［ａ］が成立するか？」と表される。
【００４２】
所要時間が長くなければ（Ｓ９４０：ＮＯ）、第１判断部６００はＳ９００に処理を戻して集合Ｃ内の他の工程についても所要時間の条件が満たされるかどうかを判断する。所要時間が長ければ（Ｓ９４０：ＹＥＳ）、第１判断部６００は、工程ａは第１条件を満たさないと判断して、続いて第２条件の充足性を判断するために、工程ａより後に処理し得る工程の集合をＣとする（Ｓ９５０）。工程ａより後に処理し得る工程も、工程ａより先に処理し得る工程の判断と同様に、順序制約データ４０に規定された順序制約および既に決定された処理順序に従っても工程ａより後に処理する可能性があるかどうかによって判断される。
【００４３】
次に、第１判断部６００は、集合Ｃが空集合か否かを判断する（Ｓ９６０）。集合Ｃが空集合であれば（Ｓ９６０：ＹＥＳ）、第１判断部６００は、工程ａが第２条件を満たすと判断し、数値−１を出力する（Ｓ９６５）。一方、集合Ｃが空集合でなければ（Ｓ９６０：ＮＯ）、第１判断部６００は、集合Ｃから工程を１つ取得して、工程ｃとする（Ｓ９７０）。そして次に、第１判断部６００は、工程ａをその工程ｃより後に処理した方がその工程ｃより先に処理するよりも修正時間の所要時間が長いかどうかを判断する（Ｓ９８０）。この判断は、数式を用いて、「ｔ［ａ］［ｃ］＞ｔ［ｃ］［ａ］が存在するか？」と表される。
【００４４】
所要時間が長ければ（Ｓ９８０：ＹＥＳ）、第１判断部６００は、第１および第２条件の何れも満たさないと判断する（Ｓ９９０）。所要時間が長くなければ（Ｓ９８０：ＮＯ）、第１判断部６００は、Ｓ９６０に処理を戻して、集合Ｃ内の他の工程についても所要時間の条件が満たされるかどうかを判断する。
以上の処理により、第１判断部６００は、ある工程ａが第１条件および第２条件のいずれかを満たすか否か、および、満たすとすればどちらを満たすかを判断することができる。
【００４５】
図９ｂは、第１条件を満たすかどうかの判断を示す概念図である。図９ｂでは、各工程を模式的にノードとして表し、既に決定した処理順序又は順序制約を２重線の矢印のエッジで表す。また、順序は未決定だがこの順に処理するとこの逆順に処理するよりも修正時間の期待値を短縮できる関係を単線の矢印のエッジで表す。また、特に規定の無い場合は、図上方に記載の工程から図下方に記載の工程の順に処理すると、その逆に処理するよりも、修正処理の所要時間の期待値を短縮できることを表している。また、説明の簡略のため、エッジにより結ばれていない工程の組については、その処理順序をここでは考慮しない。
【００４６】
ノードａ１は、ノードｂよりも後、かつ、ノードｆよりも先に処理されることが既に決定されている。そして、ノードａ１とノードａ２との間では処理順序が決定されてないが、ノードａ１をノードａ２よりも先に処理した方が修正処理の期待値を短縮できる。このような場合は、ノードａ１について第１条件が満たされる。ノードａ１より先に処理することが決定済みのノードｂを除外して考えれば、全てのノード（即ちこの例ではノードｆおよびノードａ２）よりも先に処理した方が修正処理の期待値を短縮できるからである。
【００４７】
他方、ノードａ２は、ノードｃより後、かつ、ノードｅより先に処理されることが既に決定されている。そして、ノードａ２は、ノードｄとの間では処理順序が決定されてないが、ノードａ２をノードｄよりも先に処理した方が修正処理の期待値を短縮できる。しかしながら、ノードａ２を、順序未決定のノードａ１より先に処理しても処理時間の期待値が短縮されない。したがって、ノードａ２は第１条件を満たさない。ただし、ノードａ１をノードａ２よりも先に処理することを決定した後には、ノードａ２より後に処理し得るノードはノードｄおよびノードｅのみとなるので、ノードａ２は第１条件を満たす。
【００４８】
このように、第１判断部６００は、工程ａ１および工程ａ２の処理順序をこの順に決定する。工程の数が多い実際の課題では、第１判断部６００は、先に処理すべき工程から順に順次各工程の処理順序を決定してゆく。また、第２条件についてもこの例と同様である。即ち、第１判断部６００は、第２条件の判断を通じて、後に処理すべき工程から順に順次各工程の処理順序を決定してゆく。
【００４９】
図１０は、Ｓ７２０における処理の詳細を示すフローチャートである。第１条件または第２条件を満たす工程が検出された場合において、まず、第１決定部６１０は、条件を満たす工程ａとの間で処理順序が未決定の工程の集合をＢとする（Ｓ１０００）。第１決定部６１０は、集合Ｂが空集合か否かを判断する（Ｓ１０１０）。空集合であれば（Ｓ１０１０：ＹＥＳ）、第１決定部６１０は、第１条件または第２条件成立による順序の決定を終了する。Ｂが空集合でなければ（Ｓ１０１０：ＮＯ）、第１決定部６１０は、Ｂから工程を１つ取得して、工程ｂとする（Ｓ１０２０）。
【００５０】
次に、第１決定部６１０は、工程ａが第１条件を満たす場合には工程ａを工程ｂの先に処理すると決定する（Ｓ１０３０）。工程ａが第２条件を満たす場合には、第１決定部６１０は、工程ａを工程ｂの後に処理すると決定する。これらの決定の処理は、まとめて、ｄｏＢｅｆｏｒｅ［ａ］［ｂ］＝（戻り値）およびｄｏＢｅｆｏｒｅ［ｂ］［ａ］＝−（戻り値）と表される。（戻り値）は、第１判断部６００が出力する値を表す。「戻り値」の名称は、第１判断部６００をプログラム言語の仕様のうえでの関数として実現する場合に、第１判断部６００の出力はこの関数の戻り値として表されることに由来する。
【００５１】
次に、第１決定部６１０は、戻り値が数値１か数値−１かを判断する（Ｓ１０４０）。数値１の場合（Ｓ１０４０：１）、第１決定部６１０は、工程ａおよび工程ｂをこの順に配列した順列を引数として、第３決定部６２０に順序決定の処理をさせる（Ｓ１０５０）。この引数という用語も、戻り値と同様に、第３決定部６２０をプログラム言語の仕様の上での関数として実現する場合に、その関数に与える入力パラメータは関数の引数として表されることに由来する。一方、戻り値が数値−１の場合に（Ｓ１０４０：−１）、第１決定部６１０は、工程ｂおよび工程ａをこの順に配列した順列を引数として、第３決定部６２０に順序決定の処理をさせる（Ｓ１０６０）。
【００５２】
図１１ａは、Ｓ７３０における処理の詳細を示すフローチャートである。第２判断部６３０は、まず、相互の処理順序が未決定の工程の各順列の集合をＤとする（Ｓ１１００）。そして、第２判断部６３０は、集合Ｄが空集合かどうかを判断する（Ｓ１１１０）。空集合であれば（Ｓ１１１０：ＹＥＳ）、第２判断部６３０は、第３条件を満たす工程の組が検出されないと判断して（Ｓ１１２０）、処理を終了する。一方、Ｄが空集合でなければ（Ｓ１１１０：ＮＯ）、第２判断部６３０は、Ｄから工程の組を取得して、工程ａおよび工程ｂとする（Ｓ１１３０）。工程ａは本発明の第１の工程であり、工程ｂは本発明の第２の工程である。
【００５３】
次に、第２判断部６３０は、工程ａおよび工程ｂの組が第３条件を満たすか判断する（Ｓ１１４０）。第３条件とは、工程ａより後であって工程ｂより先に処理し得る工程、または、工程ｂより後であって工程ａより先に処理し得る工程の集合Ｃについて、この集合Ｃの何れの部分集合についても、工程ａ、当該部分集合内の各工程、および、工程ｂをこの順に処理した方が、工程ｂ、当該部分集合内の各工程、および、工程ａをこの順に処理するよりも、設計変更の所要時間の期待値を増加させないという条件である。この第３条件が満たされない場合には（Ｓ１１５０：ＮＯ）、第２判断部６３０は、Ｓ１１１０に処理を戻して、第３条件を満たす第１の工程および第２の工程の組がなくなるまで順次判断する処理を繰り返す。第３条件が満たされる場合には（Ｓ１１５０：ＹＥＳ）、第２判断部６３０は、第３条件を満たす工程が検出されたと判断して（Ｓ１１６０）、処理を終了する。
【００５４】
図１１ｂは、第３条件を満たすかどうかの判断を示す概念図である。工程ａより後であって工程ｂより先に処理し得る工程、または、工程ｂより後であって工程ａより先に処理し得る工程の集合Ｃには、いま、工程ｃ１、工程ｃ２、および工程ｃ３が含まれるものとする。すると、工程ａの後かつ工程ｂの先、または、工程ｂの後かつ工程ａの先に処理され得る工程の集合は、集合Ｃの全ての部分集合、即ち、空集合φ、｛ｃ１｝、｛ｃ２｝、｛ｃ３｝、｛ｃ１，ｃ２｝、｛ｃ１，ｃ３｝、｛ｃ２，ｃ３｝、および、｛ｃ１，ｃ２，ｃ３｝の何れかとなる。
【００５５】
この例について第３条件の充足性を判断するアイデアについて説明する。まず、工程ａを工程ｂより先に処理するか後に処理するかの判断は、工程ａおよび工程ｂの関係に基づき発生する修正処理のみならず、その間に処理し得る集合Ｃの部分集合に属する工程と工程ａ、ｂとの間の関係に基づく修正処理に基づき行わなければならない。工程ａおよび工程ｂの関係に基づくと、工程ａを工程ｂより後に処理するよりも、工程ａを工程ｂより先に処理した方が修正処理の所要時間を短縮できるかどうかが判断の基準となる。短縮できることを、数式では、ｔ［ｂ］［ａ］＜ｔ［ａ］［ｂ］と表し、短縮できる時間を、ｔ［ａ］［ｂ］−ｔ［ｂ］［ａ］と表すことができる。
【００５６】
そして、集合Ｃに含まれる各工程ｃについて、工程ａ、ｃ、ｂをこの順に処理することで、工程ｂ、ｃ、ａをこの順に処理する場合と比較して増加する修正処理の所要時間を求めたうえで、どの工程ｃを選んで集合Ｃの部分集合としても、この増加する時間の合計が、上記の短縮できる時間以下となるかどうかを判断すればよい。例えば工程ｃ１について、工程ａ、ｃ１、ｂをこの順に処理することで増加する所要時間の期待値は、数式を用いて、ｔ［ｃ１］［ａ］＋ｔ［ｂ］［ｃ１］−ｔ［ｃ１］［ｂ］−ｔ［ａ］［ｃ１］と表すことができる。この計算を、集合Ｃに含まれる各工程について行ったうえで、集合Ｃに含まれる各部分集合についてそれに含まれる各工程についての計算結果を合計すれば、各部分集合について増加する時間の合計を求めることができる。
【００５７】
このようにして短縮される時間と増加する時間の合計とを、全部分集合について比較すれば、工程ａをｂより先に処理するべきかどうかが判断できる。しかしながら、集合Ｃの部分集合の数が多い場合には、上記のアイデアをそのままコンピュータの上で実現したのでは計算に時間がかかりすぎる場合がある。以下、図１２ａを参照して、大部分の部分集合についての判断を省略しつつも、第３条件の判断を適切かつ効率的に実現する方法について説明する。
【００５８】
図１２ａは、Ｓ１１４０における処理の詳細を示すフローチャートである。まず、第２判断部６３０は、工程ｂを工程ａより先に処理する場合と比較して、工程ａを工程ｂより先に処理することで短縮できる設計変更の所要時間の期待値を算出する（Ｓ１２００）。この算出は、数式を用いて、ｄｉｆｆ＝ｔ［ｂ］［ａ］−ｔ［ａ］［ｂ］として表される。算出される数値が負の数の場合にはその絶対値で表される時間を短縮できることを示し、数値が正の数の場合にはその絶対値で表される時間が増加してしまうことを示す。
【００５９】
次に、第２判断部６３０は、工程ａ、ｂ以外の全工程の集合をＣとする（Ｓ１２１０）。そして、第２判断部６３０は、集合Ｃから工程を１つ取得して工程ｃとする（Ｓ１２２０）。次に、第２判断部６３０は、工程ｃを工程ａおよびｂの何れよりも後に処理することが決定済みか、または、工程ｃを工程ａおよびｂの何れよりも先に処理することが決定済みかを判断する（Ｓ１２３０）。このように決定済みの場合には、工程ｃを工程ａおよびｂの一方よりも後、かつ他方よりも先に処理することはできない。したがって、決定済みの場合には（Ｓ１２３０：ＹＥＳ）、第２判断部６３０は、Ｓ１２５０に処理を移して次の工程について判断する。
【００６０】
一方、このように決定済みでは無い場合には（Ｓ１２３０：ＮＯ）、第２判断部６３０は、工程ｃを、工程ａより後かつ工程ｂより先に処理する場合と比較して工程ｂより後かつ工程ａより先に処理することにより、設計変更の所要時間の期待値を増加させる場合についてのみ、その増分を算出して、Ｓ１２００にて算出した短縮される時間から減じる（Ｓ１２４０）。この増分は、数式を用いて、ｔ［ｃ］［ａ］＋ｔ［ｂ］［ｃ］−ｔ［ｃ］［ｂ］−ｔ［ａ］［ｃ］と表される。また、短縮される所要時間の期待値からこの増分を減じる処理は、数式を用いて、ｄｉｆｆ＝ｄｉｆｆ＋ｍａｘ（０，ｔ［ｃ］［ａ］＋ｔ［ｂ］［ｃ］−ｔ［ｃ］［ｂ］−ｔ［ａ］［ｃ］）と表される。
【００６１】
この結果、工程ａを工程ｂより先に処理しても修正処理の所要時間の期待値が増加するようになった場合には（Ｓ１２５０：ＹＥＳ）、第２判断部６３０は、第３条件を満たす工程の組が検出されないと判断し（Ｓ１２６０）、処理を終了する。この判断は、数式を用いて、「ｄｉｆｆ＞０が成立するか？」と表される。一方、工程ａを工程ｂより先に処理することで所要時間の期待値が増加しない場合には（Ｓ１２５０：ＮＯ）、第２判断部６３０は、続いて集合Ｃが空集合かどうかを判断する（Ｓ１２７０）。空集合でなければ（Ｓ１２７０：ＮＯ）、第２判断部６３０は、Ｓ１２２０に処理を戻して、集合Ｃに含まれる他の工程についての判断に処理を移す。一方、空集合であれば（Ｓ１２７０：ＹＥＳ）、第２判断部６３０は、第３条件を満たす工程の組が検出されたと判断する（Ｓ１２８０）。
【００６２】
以上、図１２ａを参照して説明したように、第２判断部６３０は、工程ａより後かつ工程ｂより先に処理する場合と比較して工程ｂより後かつ工程ａより先に処理することにより、設計変更の所要時間の期待値を増加させる各々の工程について、その期待値の増分を算出することができる。そして、第２判断部６３０は、工程ａを工程ｂより先に処理することで短縮できる設計変更の所要時間の期待値が、上記の期待値の増分の合計以上であることを条件に、第３条件を満たすと判断する。このようにすることで、集合Ｃの全ての部分集合を判断の対象とせずに、工程ａの後かつ工程ｂの先に処理することで修正処理の所要時間を最も長くする部分集合についてのみ判断の対象として、所要時間の判断に要する処理時間を節約することができる。
【００６３】
図１２ｂは、第３条件の充足を効率的に判断するための工夫を示す概念図である。工程ａより後かつ工程ｂより先に処理することで、その逆順に処理するよりも、修正処理の所要時間の期待値を増加させてしまう工程を、工程ｃ１および工程ｃ３とする。この場合、上記図１２ａのＳ１２４０において、これらの工程ｃ１および工程ｃ３を工程ａより後かつ工程ｂより先に処理することによって増加させる期待値のみを、変数ｄｉｆｆの値に加える。そして、工程ａより後かつ工程ｂより先に処理することで所要時間を短縮できる工程ｃ２については、その短縮できる時間を変数ｄｉｆｆの値に反映させない。
【００６４】
これは即ち、第２判断部６３０が、工程ａより後かつ工程ｂより先に処理することで修正処理を最も長くしてしまう部分集合である｛ｃ１，ｃ３｝についてのみを判断の対象としていることに他ならない。このように、本来は８つの部分集合を判断の対象としなければならないところを、１つの部分集合のみを判断の対象とすることで、判断に要する時間を短縮することができる。これは、集合Ｃのサイズが大きい場合には一層顕著になる。
【００６５】
図１３は、Ｓ７５０における処理の詳細を示すフローチャートである。工程ａおよび工程ｂの組が第３条件を満たす場合に、第２決定部６４０は、工程ａを工程ｂより先に処理すると決定する（Ｓ１３００）。この決定は、数式を用いて、ｄｏＢｅｆｏｒｅ［ａ］［ｂ］＝１およびｄｏＢｅｆｏｒｅ［ｂ］［ａ］＝−１と表される。そして、工程ａを第１引数とし、工程ｂを第２引数として、第３決定部６２０を実現するための関数を呼び出し、第３決定部６２０により処理をさせる（Ｓ１３１０）。
【００６６】
図１４は、Ｓ７０４、Ｓ１０５０、Ｓ１０６０およびＳ１２１０として共通して機能する処理の詳細を示すフローチャートを示す。第３決定部６２０は、まず、第１引数である工程ａおよび第２引数である工程ｂ以外の全工程の集合をＣとする（Ｓ１４００）。そして、第３決定部６２０は、集合Ｃから工程を１つ選択して、工程ｃとする（Ｓ１４１０）。この工程ｃは、本発明に係る第３の工程または第４の工程の候補となる工程である。そして、第３決定部６２０は、工程ｃおよび工程ａの間で処理順序が決定しておらず、かつ、工程ｃを工程ｂより後に処理することが既に決定されているかを判断する（Ｓ１４２０）。
【００６７】
そのような場合には（Ｓ１４２０：ＹＥＳ）、第３決定部６２０は、工程ｃを工程ａより後に処理すると決定する（Ｓ１４３０）。これにより、工程ａ、ｂの処理順序、および、既に決定されていた他の処理順序に推移法則を適用して、工程ａ、ｃの処理順序を定めることができる。そして、第３決定部６２０は、工程ａおよび工程ｃの順列を新たに引数として、本図の処理を再帰的に適用する（Ｓ１４４０）。
【００６８】
次に、第３決定部６２０は、工程ｃおよび工程ａの間で処理順序が決定しておらず、かつ、工程ｃを工程ａより先に処理することが既に決定されているかを判断する（Ｓ１４５０）。そのような場合には（Ｓ１４５０：ＹＥＳ）、第３決定部６２０は、工程ｃを工程ｂの先に処理すると決定する（Ｓ１４６０）。そして、第３決定部６２０は、工程ｃおよび工程ｂの順列を新たに引数として、本図の処理を再帰的に適用する（Ｓ１４７０）。
【００６９】
続いて、第３決定部６２０は、Ｓ１４１０において選択した工程ｃを集合Ｃから取得したうえで（Ｓ１４８０）、集合Ｃが空集合かどうかを判断する（Ｓ１４９０）。Ｃが空集合であれば（Ｓ１４９０：ＹＥＳ）、第３決定部６２０は、本図の処理を終了する。Ｃが空集合でなければ（Ｓ１４９０：ＮＯ）、第３決定部６２０は、Ｓ１４１０に処理を戻して集合Ｃに含まれる他の工程についての判断を行う。
【００７０】
このように、第１決定部６１０および第２決定部６４０、ならびに、第３決定部６２０自体によって新たに処理順序が１つ決定されるたびに、第３決定部６２０は、その処理順序および既に決定された他の処理順序に推移法則を適用して新たな処理順序を決定することができる。これにより、ある工程の組についてその処理順序を推移的に決定できるにもかかわらず未決定としてその後の処理を行うことを防止し、処理順序の循環などの矛盾の発生を防止できる。
【００７１】
以上、図７から図１４を参照して工程の処理順序を決定する処理の流れを説明したが、図中で用いられる集合Ｃ、工程ａ、ｂ、ｃなどのシンボルは、それが定義された処理ステップを含む図中でのみ有効であり、引数や戻り値などの明示がある場合を除き、他の図で定義された同一のシンボルとは無関係である。即ちこれらは、これらの処理をプログラム言語を用いて実装した場合の局所変数・プライベート変数としての役割を果たす。一方で、ｄｏＢｅｆｏｒｅやｔなどの、記憶装置１１０に記憶されるものとして予め定義したデータは、複数の図の処理に渡って普遍的に存在するものである。即ちこれらは、これらの処理をプログラム言語を用いて実装した場合の大域変数・公開変数としての役割を果たす。
【００７２】
図１５ａは、本実施の形態に係る決定システム１０により生成された部分順序データ１５０の一例を示す。図１５ｂは、部分順序データ１５０において工程の配列順序をその処理順序に並べ替えて示す。ここで部分順序データ１５０として示す数値は、上述の説明で用いた関数ｄｏＢｅｆｏｒｅの値である。ｄｏＢｅｆｏｒｅの第１引数に相当する工程の識別子を列方向に、ｄｏＢｅｆｏｒｅの第２引数に相当する工程の識別子を行方向に、それぞれ配列している。例えば、ｄｏＢｅｆｏｒｅ［ｂ］［ｄ］は、ｂ行ｄ列の要素、即ち数値１である。これは、工程ｂを工程ｄよりも先に処理すると決定されたことを示す。
【００７３】
部分順序データ１５０を参照すると、工程ｂを最初に処理して、その次に、ｄ、ａ、ｃ、ｉ、ｊ、ｋ、ｍ、ｎ、ｑ、ｒ、ｗ、ｌ、ｙをこの順に処理することが決定されている。また、工程ｈ、ｇをこの順に最後に処理することが決定されている。また、工程ｙの後であって工程ｈより先に、工程ｅ、ｆ、ｓ、ｔ、ｕ、ｖ、ｏ、ｘ、ｐ、ｚを処理することは決定されているが、これらの工程の間の処理順序は部分的にしか決定されていない。これらの集合を、第１決定部６１０、第３決定部６２０および第２決定部６４０によっては処理順序が決定しなかった、未決定集合と呼ぶ。続いて、スケジュール部６５０は、この未決定集合の中における工程の処理順序を、他の方法によって決定する。この結果として決定された処理順序が処理順序データ１６０である。
【００７４】
図１６は、本実施の形態に係る決定システム１０により生成された処理順序データ１６０の一例を示す。図は、各工程の配列順序を決定された処理順序と同じになるように並べ替えたうえで、修正処理に要する所要時間の期待値を示している。対角線の左下に示す数値が、各工程の組ごとに発生する修正処理の所要時間の期待値である。例えば工程ｉ、ｊをこの順に処理した場合において、発生する修正処理の所要時間の期待値は８時間である。スケジュール部６５０は、処理順序データ１６０として示すこの表形式のデータを、画面に表示してもよい。これにより、画面を参照したエンジニアは、自動車等の製品を設計するための最適な順序を把握して、設計作業の効率化に役立てることができる。さらに、スケジュール部６５０は、修正処理の所要時間の期待値の合計を、対角線の左下に示す数値を合計することによって算出し、この表形式のデータと共に表示してよい。この例の場合は、合計時間である１１４時間が表示される。
【００７５】
以上、図１から図１６を参照して説明した決定システム１０によれば、予め定められた工程の集合のうちの多くの部分について、その最適な処理順序を、第１決定部６１０および第２決定部６４０等による極めて迅速な処理によって決定することができる。これにより、探索空間を狭めて最適順序を探し出し易くすることができる。例えば、残りの工程については、全数探索などの従来手法によっても現実的な時間で最適な処理順序を決定でき、あるいは、人手による試行錯誤によっても適切な処理順序を決定することができる。
【００７６】
続いて、図１７−２０を参照して、スケジュール部６５０が未決定集合の中の工程の処理順序までをも、更に効率的に決定する処理について説明をすすめる。
図１７は、本実施の形態に係るスケジュール部６５０が読み出す未決定データ１７０の一例を示す。スケジュール部６５０は、まず、未決定データ１７０として例示するように、部分順序データ１５０のうち未決定集合内の工程に対応する部分を選択して記憶装置１１０から読出し、また、期待値データ５０のうち未決定集合内の工程に対応する部分を選択して記憶装置１１０から読み出す。未決定データ１７０を参照すると、工程ｓ、ｔ、ｕ、ｖをこの順に処理することは決定済みであるが、これらの工程を未決定集合の中で最初に処理するのか、最後に処理するのか、あるいは、これらの工程の間に他の工程を処理するのかは決定されていない。また、工程ｏより工程ｐを後に処理することは決定済みであるが、これらの工程を未決定集合の中で何番目に処理するのかは決定されていない。
【００７７】
スケジュール部６５０は、この未決定データ１７０に基づいて、第１決定部６１０および第２決定部６４０を再帰的に利用しながら、未決定集合中の工程の処理順序を決定してゆく。
図１８は、本実施の形態に係るスケジュール部６５０の処理の概要を示す。スケジュール部６５０は、未決定集合｛ｅｆｓｔｕｖｏｘｐｚ｝に含まれる各工程について、その工程を未決定集合の中で最初に処理すると仮定し、その各仮定における未決定集合内の最適な処理順序を決定する。即ち例えば、まず、工程ｅを最初に処理すると仮定して、その残りの工程の最適な処理順序を決定する。次に、工程ｆを最初に処理すると仮定して、その残りの工程の最適な処理順序を決定する。但し、未決定データ１７０に従うと工程ｔ、ｕ、ｖ、ｐは最初に処理しないことが決定済みなので、これらの工程を最初に処理するという仮定は行わない。
【００７８】
続いて、各仮定における最適な処理順序を決定する手法について説明する。スケジュール部６５０は、未決定データ１７０にある仮定を加えた場合における未決定集合中の処理順序を生成して、部分問題データ１７５とする。その一例を図１９に示す。
図１９は、本実施の形態に係るスケジュール部６５０が出力する部分問題データ１７５の一例を示す。工程ｅを最初に処理すると決定した結果、工程ｅは未決定集合中の他の何れの工程よりも先に処理されることが決定される。即ちｄｏＢｅｆｏｒｅ［ｅ］［ｆ］やｄｏＢｅｆｏｒｅ［ｅ］［ｓ］などは全て１になる。スケジュール部６５０は、このような部分問題データ１７５を生成して記憶装置１１０に格納する。そして、スケジュール部６５０は、順序制約データ４０に代えて部分問題データ１７５を参照させるように設定したうえで、第１判断部６００、第１決定部６１０、第３決定部６２０、第２判断部６３０および第２決定部６４０に図１から図１６を参照して説明した処理と同様の処理を再帰的に行わせる。この結果、それぞれの仮定に対応して最適な処理順序が決定され得る。スケジュール部６５０は、このようにして決定された最適な処理順序のそれぞれについて、修正処理の所要時間の期待値を算出する。そして、スケジュール部６５０は、算出した期待値が最も短い処理順序を選択して出力する。
【００７９】
以上、図１７−図１９を参照して説明したように、スケジュール部６５０は、新たな仮定を加えて一部の処理順序を決定することで、未決定集合内の工程の処理順序までをも第１判断部６００、第１決定部６１０、第３決定部６２０、第２判断部６３０および第２決定部６４０により決定させることができる。これにより、一部の工程のみならず全てについて、極めて効率的に最適な処理順序を決定することができる。
【００８０】
図２０は、本実施の形態に係る決定システム１０として機能するコンピュータのハードウェア構成の一例を示す。コンピュータは、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、及びグラフィックコントローラ１０７５を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＲＯＭ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００８１】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＲＯＭ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００８２】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、コンピュータが使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０又はハードディスクドライブ１０４０に提供する。
【００８３】
また、入出力コントローラ１０８４には、ＲＯＭ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＲＯＭ１０１０は、コンピュータの起動時にＣＰＵ１０００が実行するブートプログラムや、コンピュータのハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、入出力チップ１０７０を介してＲＡＭ１０２０またはハードディスクドライブ１０４０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００８４】
コンピュータに提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ１０７０及び/又は入出力コントローラ１０８４を介して、記録媒体から読み出されコンピュータにインストールされて実行される。プログラムがコンピュータ等に働きかけて行わせる動作は、図１から図１９において説明した決定システム１０における動作と同一であるから、説明を省略する。
【００８５】
以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータに提供してもよい。
【００８６】
以上、図１から図２０を参照して説明したように、本実施の形態に係る決定システム１０によれば、内容が高度なため依存関係が複雑な複数の工程の処理順序を、その所要時間を最小化するように決定することができる。この決定には、工程の数（即ち設計のために決定しなければならない要素の数）に応じて指数関数的に計算時間が増加する全数探索などの手法と比較して、極めて高速に完了する。したがって、自動車設計などの実際の製品設計に適用することで、その開発期間を短縮し、または、余剰期間を追加機能の開発や品質向上に充当することができる。
【００８７】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることのできることが当業者にとって明らかである。例えば、第１−第３条件の判断順序は上記の例に限定されるものではなく、各条件の判断を繰り返し行うものであれば、他の順序であってよい。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００８８】
【図１】図１は、本実施の形態に係る決定システム１０の全体構成を示す。
【図２ａ】図２ａは、本実施の形態に係る確率データ２０のデータ構造の第１例を示す。
【図２ｂ】図２ｂは、本実施の形態に係る確率データ２０のデータ構造の第２例を示す。
【図３ａ】図３ａは、本実施の形態に係る処理時間データ３０のデータ構造の第１例を示す。
【図３ｂ】図３ｂは、本実施の形態に係る処理時間データ３０のデータ構造の第２例を示す。
【図４】図４は、本実施の形態に係る順序制約データ４０のデータ構造の一例を示す。
【図５】図５は、本実施の形態に係る期待値データ５０のデータ構造の一例を示す。
【図６】図６は、本実施の形態に係る本体部１２０の機能構成を示す。
【図７】図７は、本実施の形態に係る決定システム１０の処理段階の概要を示すフローチャートである。
【図８】図８は、Ｓ７０５における処理の詳細を示すフローチャートである。
【図９ａ】図９ａは、Ｓ８３０における処理の詳細を示すフローチャートである。
【図９ｂ】図９ｂは、第１条件を満たすかどうかの判断を示す概念図である。
【図１０】図１０は、Ｓ７２０における処理の詳細を示すフローチャートである。
【図１１ａ】図１１ａは、Ｓ７３０における処理の詳細を示すフローチャートである。
【図１１ｂ】図１１ｂは、第３条件を満たすかどうかの判断を示す概念図である。
【図１２ａ】図１２ａは、Ｓ１１４０における処理の詳細を示すフローチャートである。
【図１２ｂ】図１２ｂは、第３条件の充足を効率的に判断するための工夫を示す概念図である。
【図１３】図１３は、Ｓ７５０における処理の詳細を示すフローチャートである。
【図１４】図１４は、Ｓ７０４、Ｓ１０５０、Ｓ１０６０およびＳ１２１０として共通して機能する処理の詳細を示すフローチャートを示す。
【図１５ａ】図１５ａは、本実施の形態に係る決定システム１０により生成された部分順序データ１５０の一例を示す。
【図１５ｂ】図１５ｂは、部分順序データ１５０において工程の配列順序をその処理順序に並べ替えて示す。
【図１６】図１６は、本実施の形態に係る決定システム１０により生成された処理順序データ１６０の一例を示す。
【図１７】図１７は、本実施の形態に係るスケジュール部６５０が読み出す未決定データ１７０の一例を示す。
【図１８】図１８は、本実施の形態に係るスケジュール部６５０の処理の概要を示す。
【図１９】図１９は、本実施の形態に係るスケジュール部６５０が出力する部分問題データ１７５の一例を示す。
【図２０】図２０は、本実施の形態に係る決定システム１０として機能するコンピュータのハードウェア構成の一例を示す。
【符号の説明】
【００８９】
１０  決定システム
２０  確率データ
３０  処理時間データ
４０  順序制約データ
５０  期待値データ
１００  入力部
１１０  記憶装置
１２０  本体部
１５０  部分順序データ
１６０  処理順序データ
１７０  未決定データ
１７５  部分問題データ
６００  第１判断部
６１０  第１決定部
６２０  第３決定部
６３０  第２判断部
６４０  第２決定部
６５０  スケジュール部
【図１】
2008299531.tif 000003
【図２ａ】
2008299531.tif 000004
【図２ｂ】
2008299531.tif 000005
【図３ａ】
2008299531.tif 000006
【図３ｂ】
2008299531.tif 000007
【図４】
2008299531.tif 000008
【図５】
2008299531.tif 000009
【図６】
2008299531.tif 000010
【図７】
2008299531.tif 000011
【図８】
2008299531.tif 000012
【図９ａ】
2008299531.tif 000013
【図９ｂ】
2008299531.tif 000014
【図１０】
2008299531.tif 000015
【図１１ａ】
2008299531.tif 000016
【図１１ｂ】
2008299531.tif 000017
【図１２ａ】
2008299531.tif 000018
【図１２ｂ】
2008299531.tif 000019
【図１３】
2008299531.tif 000020
【図１４】
2008299531.tif 000021
【図１５ａ】
2008299531.tif 000022
【図１５ｂ】
2008299531.tif 000023
【図１６】
2008299531.tif 000024
【図１７】
2008299531.tif 000025
【図１８】
2008299531.tif 000026
【図１９】
2008299531.tif 000027
【図２０】
2008299531.tif 000028