(57)【特許請求の範囲】
【請求項１】
物品を搬送するための搬送路を構成する複数の搬送区間と、前記物品が前記搬送路で投入される投入位置と、前記搬送区間ごとに前記物品を搬送するのに必要な負荷を含む搬送負荷と、前記物品に対する複数の工程を処理する複数の工程処理装置の前記搬送路の配置位置と、を含むレイアウトデータと、前記物品に対する前記工程を処理する順序を含む処理工程データと、前記工程と処理可能な前記工程処理装置との対応情報を含む装置データと、前記投入位置の投入量を含む生産量データとに基づいて、ｎ番目の工程を処理する各工程処理装置とｎ＋１番目の工程を処理する工程処理装置間の単位時間あたりの搬送量を変数とする線形計画問題を作成し、ｎ＝０の投入位置の工程からｎ＝｜Ｎ｜の払出位置の工程までのｎについて前記線形計画問題を順に解くソルバー機能を有する作成部と、
前記線形計画問題の解に含まれる全工程の前記工程処理装置間の単位時間あたりの前記搬送量を用いて前記搬送区間ごとの単位時間あたりの搬送量を算出する算出部と、を備えるシミュレーション装置。
【請求項２】
前記レイアウトデータに基づいて、前記投入位置と前記搬送路の分岐位置と前記工程処理装置の位置を頂点とし、前記搬送路の搬送方向を有向辺の方向とし、前記有向辺の重みを前記頂点間の搬送負荷とするレイアウトグラフを作成するレイアウトグラフ作成部を備える請求項１に記載のシミュレーション装置。
【請求項３】
前記レイアウトデータと、前記処理工程データと、前記装置データと、前記生産量データを記憶する記憶部を備える請求項１または２に記載のシミュレーション装置。
【請求項４】
前記レイアウトグラフと、前記処理工程データと、前記装置データとに基づいて、ｎ番目の工程を処理する各工程処理装置からｎ＋１番目の工程を処理する前記工程処理装置間の搬送路を前記物品が通過する経路を示す搬送経路を決定する搬送経路計算部を備え、
前記作成部が、前記搬送経路計算部が決定する前記搬送経路を利用して線形計画問題を作成する請求項２に記載のシミュレーション装置。
【請求項５】
前記記憶部が、前記工程処理装置の配置位置に代わり、前記工程処理装置とその台数を定めた装置区画の位置を記憶する請求項３に記載のシミュレーション装置。
【請求項６】
前記工程処理装置が処理可能な物品数をユーザが指定する、ユーザ指定データを前記記憶部内に含み、
前記作成部が、前記ユーザ指定データに基づいて線形計画問題を作成する請求項３に記載のシミュレーション装置。
【請求項７】
特定の工程処理装置間の単位時間あたりの搬送量をユーザが指定する、ユーザ指定データを前記記憶部内に含み、
前記作成部が、前記ユーザ指定データに基づいて線形計画問題を作成する請求項３に記載のシミュレーション装置。
【請求項８】
前記搬送経路計算部が、各工程処理装置間の前記搬送経路を最小とする請求項４に記載のシミュレーション装置。
【請求項９】
前記搬送経路をユーザが指定する、ユーザ指定データを記憶する記憶部を備え、
前記作成部が、前記ユーザ指定データに基づいて線形計画問題を作成する請求項４に記載のシミュレーション装置。
【請求項１０】
前記作成部が、前記工程を処理できる各工程処理装置への物品の投入量を均等とした線形計画問題を作成する請求項１乃至９のいずれか１項に記載のシミュレーション装置。
【請求項１１】
前記装置データとして、前記工程処理装置が前記物品を処理するのに要する時間を含み、前記作成部が前記工程を処理する各工程処理装置の稼働時間を平準化するように線形計画問題を作成する請求項１乃至１０のいずれか１項に記載のシミュレーション装置。
【請求項１２】
前記線形計画問題の解が、前記工程処理装置ごとの全工程での物品の処理量を含み、前記算出部が、前記処理量を前記工程処理装置ごとに算出する請求項１乃至１１のいずれか１項に記載のシミュレーション装置。
【請求項１３】
工程を処理する各工程処理装置間の単位時間当たりの物品の搬送量を変数とする線形計画問題を作成し、前記線形計画問題を解くソルバー機能を有する作成部と、前記線形計画問題の解に基づいて搬送区間ごとの単位時間あたりの前記物品の搬送量を算出する算出部と、を備えるシミュレーション装置におけるシミュレーション方法であって、
前記作成部において前記物品を搬送するための搬送路を構成する複数の前記搬送区間と、前記物品が前記搬送路で投入される投入位置と、前記搬送区間ごとに前記物品を搬送するのに必要な負荷を含む搬送負荷と、前記物品に対する複数の工程を処理する複数の工程処理装置の前記搬送路の配置位置と、を含むレイアウトデータと、前記物品に対する前記工程を処理する順序を含む処理工程データと、前記工程と処理可能な前記工程処理装置との対応情報を含む装置データと、前記投入位置の投入量を含む生産量データとに基づいて、ｎ番目の工程を処理する各工程処理装置とｎ＋１番目の工程を処理する工程処理装置間の単位時間あたりの搬送量を変数とする前記線形計画問題を作成し、
ｎ＝０の投入位置の工程からｎ＝｜Ｎ｜の払出位置の工程までのｎについて前記線形計画問題を順に解き、
前記算出部において前記線形計画問題の解に含まれる全工程の前記工程処理装置間の単位時間あたりの前記搬送量を用いて前記搬送区間ごとの単位時間あたりの搬送量を算出するシミュレーション方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、異なる工程処理装置間で物品を搬送する搬送路の利用状況（混雑状況）をシミュレートするシミュレーション装置及び方法に関する。
【背景技術】
【０００２】
半導体工場においては、物品は品種ごとに複数の決まった処理工程を経て完成品となる。工程を処理する複数の工程処理装置は、搬送路で結ばれており、物品は搬送路を利用し次の工程処理装置へ移動する。効率的な製造のためには、工程処理装置や搬送路の効率的なレイアウト設計が必要であり、設計段階からあらかじめ搬送路の利用状況を可視化できるシミュレータが利用される。このようなシミュレータの利用により、複雑な製造工程でも効率良い製造装置や搬送路の配置が可能となり、タクトタイムや製造コストを低減することができる。
【０００３】
現在、一般的に用いられているシミュレータは、時系列に沿って物品がどの処理工程を行っているのかあるいは搬送路上のどこにあるのかなどの動きを模擬するようにシミュレーションしていくものである。この様な時系列に沿って行うシミュレーションでは、半導体工場の様に大規模、複雑な製造工程の場合、シミュレーション時間が膨大にかかり、製造装置や搬送路の効率的なレイアウト設計を検討する際の負担となっている。
【０００４】
大規模なシミュレーションモデルや多大なシミュレーション時間を要することなく最終状態までシミュレーションできるシミュレータの構築が必要となっている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−３１０４６７号公報
【特許文献２】特開２００８−９３７５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明が解決しようとしている課題は、時系列に沿って物品の動きを模擬することはせず、定常状態（最終状態）における搬送路の利用状況（混雑状況）を直接計算することで短時間でのシミュレーションを可能にすることである。
【課題を解決するための手段】
【０００７】
実施形態のシミュレーション装置は、物品を搬送するための搬送路を構成する複数の搬送区間と、前記物品が前記搬送路で投入される投入位置と、前記搬送区間ごとに前記物品を搬送するのに必要な負荷を含む搬送負荷と、前記物品に対する複数の工程を処理する複数の工程処理装置の前記搬送路の配置位置と、を含むレイアウトデータと、前記物品に対する前記工程を処理する順序を含む処理工程データと、前記工程と処理可能な前記工程処理装置との対応情報を含む装置データと、前記投入位置の投入量を含む生産量データとに基づいて、ｎ番目の工程を処理する各工程処理装置とｎ＋１番目の工程を処理する工程処理装置間の単位時間あたりの搬送量を変数とする線形計画問題を作成し、ｎ＝０の投入位置の工程からｎ＝｜Ｎ｜の払出位置の工程までのｎについて線形計画問題を順に解くソルバー機能を有する作成部と、前記線形計画問題の解に含まれる全工程の前記工程処理装置間の単位時間あたりの前記搬送量を用いて搬送区間ごとの単位時間あたりの搬送量を算出する算出部と、を備える。
【図面の簡単な説明】
【０００８】
【図１】第１の実施形態のブロック図。
【図２】第１の実施形態のフローチャート。
【図３】レイアウトデータと生産量データの例。
【図４】処理工程データの例。
【図５】装置データの例。
【図６】線形計画問題の作成例。
【図７】算出部の結果（レイアウトデータに流量表示）。
【図８】第２の実施形態のブロック図。
【図９】第２の実施形態のフローチャート。
【図１０】レイアウトグラフ。
【図１１】算出部の結果（レイアウトグラフに流量表示）。
【図１２】第３の実施形態のブロック図。
【図１３】第３の実施形態のフローチャート。
【図１４】搬送経路計算部の結果例（搬送負荷最小の結果）。
【図１５】第４の実施形態のブロック図。
【発明を実施するための形態】
【０００９】
以下、図面を参照して実施形態に係るシミュレーション装置を説明する。
【００１０】
（第１の実施形態）
図１は、第１の実施形態に係るシミュレーション装置を示すブロック図である。図２がそのフローチャートである。
【００１１】
第１の実施形態のシミュレーション装置は、シミュレーションに用いる各種パラメータ（レイアウトデータ２１、生産量データ２２、処理工程データ２３、装置データ２４）を収集するための入力部１０と、入力部１０から得たパラメータを記憶する記憶部２０と、パラメータに基づいて単位時間あたりの搬送量を線形計画法に基づいてシミュレーションするとともに、シミュレーションして得られた単位時間あたりの搬送量を加算して、定常状態における搬送路の混雑状況を求める演算部３０と、定常状態における搬送路の混雑状況を出力するための出力部５０を備える。
【００１２】
入力部１０には、演算部内で演算を実行するために必要なパラメータが入力される。
【００１３】
後述するように、半導体工場の場合には、物品を搬送する搬送路と、搬送路から物品を受け取って所定の処理工程を実行し、処理工程の実行後は搬送路に当該搬送品を返却する複数の工程処理装置が分散配置されている。レイアウトデータ２１はこのようなレイアウト情報を含んでいる。生産量データ２２は搬送路に投入される単位時間あたりの物品の量を示している。処理工程データ２３は、物品（品種ごと）に適用される処理工程の順序を示している。装置データ２４は、分散配置される工程処理装置ごとにそれぞれがどんな工程を処理可能であるかを示している。ここでいう物品とは、半製品や製造品または完成品等を含む。
【００１４】
入力手段としては、コンピュータを用いて直接入力しても良いし、上記のパラメータデータが入ったＵＳＢメモリ等により入力しても良い。
【００１５】
記憶部２０には、入力部１０で入力されたパラメータを記憶するもので、ハードディスク等の記憶媒体が考えられる（Ｓ２０１）。実施形態のシミュレーション装置では、レイアウトデータ２１として、物品を搬送するための搬送路を構成する複数の搬送区間（搬送路の分岐点間）と、前記物品が前記搬送路で投入される投入位置と、前記搬送区間ごとに前記物品を搬送するのに必要な負荷を含む搬送負荷（搬送方向、距離、物品を搬送するのに要する搬送時間、物品を搬送するのに必要なエネルギー等の少なくともいずれか１つを含む）と、前記物品に対する複数の工程を処理する複数の工程処理装置の前記搬送路の配置位置と、を含んでいる。記憶部２０には、その他にも、ユーザが指定した様々なデータを入力し記憶できる。
【００１６】
図３は、レイアウトデータ２１に生産量データ２２を重ねて図示した例である。レイアウトデータ２１には、搬送路と工程処理装置の配置などが示されている。図中の矢印は、搬送路とその搬送方向であり、Ａ〜Ｃの符号は工程処理装置の種類とその位置を示している。搬送路上の括弧付き数字は、搬送区間の搬送負荷を示している。例えば、図３の投入位置から初めの分岐点までの搬送区間の搬送負荷は６で表されている。この値が大きい程、搬送区間の搬送負荷が大きいことを示している。
【００１７】
生産量データ２２は、搬送路上の物品の投入位置と投入位置における物品の単位時間あたりの投入量及び払出位置として示される。図３では、投入位置と払出位置はそれぞれ１つしか存在しないが、これらは、複数あっても良い。
【００１８】
図４は、処理工程データ２３の例である。品種Ｘについての投入から払出までの各工程の順序を表している。品種とは、製品の種類を表し、品種は複数あっても良いし、品種毎に工程順が異なっても良い。どの品種についてシミュレーションを行うかは、選択することができる（Ｓ２０２）。
【００１９】
図５は、装置データ２４の例である。例えば、工程処理装置Ａは工程Ｐ１、Ｐ２を処理でき、工程処理装置Ｂは工程Ｑを処理できる等の情報である。
【００２０】
演算部３０は、記憶部２０内のデータに基づいて線形計画問題を作成し、それを解くことにより搬送路の混雑状況をシミュレートする。演算部３０は、工程処理装置間の搬送流量にかかる線形計画問題を作成するとともに、作成された線形計画問題をソルバー４０を用いて解くための作成部３１と、ソルバーで解かれた搬送流量を搬送区間ごとに加算する算出部３２とを含む。
【００２１】
線形計画問題とは、与えられた線形（１次式）な等式および不等式制約のもとで, 線形目的関数を最大化あるいは最小化する問題である。線形計画問題は、構造が単純であり、大規模でも高速に解けるという特徴があり、非常に実用的で強力な数理モデルである。
【００２２】
作成部３１は、処理工程データ２３に含まれる工程列の工程間ごとに処理を行う。作成部３１の機能を説明するため、定数と変数を定義する。
【００２３】
ｎ番目の工程を処理できる工程処理装置をＮ１〜Ｎ|Ｎ|（|Ｎ|台存在すると仮定）とし、ｎ＋１番目の工程を処理できる工程処理装置をＭ１〜Ｍ|Ｍ|（|Ｍ|台存在すると仮定）とする。工程処理装置Ｎ１〜Ｎ|Ｎ|が処理する物品数をそれぞれＴ１〜Ｔ|Ｎ|（定数）とする。また、工程処理装置Ｍ１〜Ｍ|Ｍ|が処理する物品数を格納する変数をｕ１〜ｕ|Ｍ|とする。Ｔ１〜Ｔ|Ｎ|が定数であるのに対し、ｕ１〜ｕ|Ｍ|は変数である。
【００２４】
作成部３１の作成する線形計画問題は、ｎ番目の工程を処理する物品数（Ｔ１〜Ｔ|Ｎ|）を利用し、ｎ＋１番目の工程を処理する物品数を求める問題となり、ｎ＝０の工程を処理する装置の処理数は投入量に対応するため漸化式を解くように次々に各工程・各装置の処理する物品量が求められる。
【００２５】
Ｗ［ｎ］［ｍ］を工程処理装置Ｎｎから工程処理装置Ｍｍへの工程処理装置間の搬送経路の搬送負荷とする。搬送経路は、複数の搬送区間を含むものであり第１の実施形態での工程処理装置間の搬送経路は、あらかじめユーザにより与えられているか、最短経路として入力され、定数として与えられる。
【００２６】
ｒ［ｎ］［ｍ］は、工程処理装置ＮｎからＭｍへの物品の工程処理装置間の搬送流量を格納する変数である。工程処理装置間の搬送流量とは、単位時間あたりの搬送量であり、流量が大きい程、その箇所が混雑していることを示す。
【００２７】
作成部３１の作成する線形計画問題は、変数をｕ１〜ｕ|Ｍ|と変数ｒ［ｎ］［ｍ］の値を求める問題となる。図６が、線形計画問題の作成例である。工程処理装置Ｎ１から出ていく物品数がＴ１であり、この物品数が、任意に工程処理装置Ｍ１〜Ｍ|Ｍ|に振り分けられる。他の工程処理装置Ｎ２〜Ｎ|Ｎ|から出ていくＴ２〜Ｔ|Ｎ|についても同様に任意の工程処理装置Ｍ１〜Ｍ|Ｍ|に振り分けられる。
【００２８】
線形計画問題における必須の制約式は、流量保存のため、工程処理装置Ｎｎから出ていく流量と工程処理装置Ｎｎが処理する流量とが一致することを表す式（１）、
【数１】
0006605951.tif 000002
と、工程処理装置Ｍｍの処理する物品量は工程処理装置Ｍｍへ入ってくる流量と一致することを表す式（２）、
【数２】
0006605951.tif 000003
の２式である。
【００２９】
そして、目的関数は搬送負荷最小化を表す式（３）である。目的関数はシミュレーションしたい内容によって適宜変更してもよい。例えば、搬送負荷を最大にしたシミュレーションをする場合はｍｉｎ．を ｍａｘ．にする（Ｓ２０３）。
【数３】
0006605951.tif 000004
【００３０】
このように作成した線形計画問題の計算手段として、線形計画問題を解くためのソルバーを用いて解かせると、式（３）中の変数ｕ１〜ｕ|Ｍ|と変数ｒ［ｎ］［ｍ］の値が求まる（Ｓ２０４）。
【００３１】
ソルバーとは、計算を実行するソフトウェアのことを言い、汎用の線形計画問題のソルバーとしてＧｕｒｏｂｉ、ＣＰＬＥＸ等がある。線形計画問題ソルバー４０は、演算部内に含めても良いし、ソルバーを含んだ外部装置を用いて線形計画問題を計算させた後、その解を演算部３０に戻しても良い。
【００３２】
算出部３２は作成部３１の作成した変数ｒ［ｎ］［ｍ］の値（線形計画問題ソルバーが求めた解）を受け取る。変数ｒ［ｎ］［ｍ］の値は工程ｎの工程処理装置Ｎｎから工程ｎ＋１の工程処理装置Ｍｍへの単位時間あたりの搬送量であり、工程処理装置間の搬送経路の搬送負荷は、あらかじめユーザにより与えられており既知であるため、レイアウトデータにおけるどの搬送区間にｒ［ｎ］［ｍ］の値に対応する流量が発生するかが分かる。
【００３３】
算出部３２は全ての変数ｒ［ｎ］［ｍ］の値を搬送区間ごとに加算していく（Ｓ２０５）。任意の工程間に関して、変数ｒ［ｎ］［ｍ］の値の搬送区間ごとの加算が終了した時点で結果を出力する（Ｓ２０６）。
【００３４】
また算出部３２は、作成部３１の作成した変数ｕ１〜ｕ|Ｍ|の値（線形計画問題ソルバー４０が求めた解）を受取る。変数ｕ１〜ｕ|Ｍ|の値は装置Ｍ１〜Ｍ|Ｍ|の処理量である。任意の工程間に関して、変数ｕ１〜ｕ|Ｍ|の値を工程処理装置ごとに加算すると最終的に各装置が処理する物品量も計算出来る。
【００３５】
演算部３０の計算は、記憶部２０に記憶されたデータに基づき、主にコンピュータのＣＰＵ（中央演算処理装置）などで計算される。
【００３６】
出力部５０は、モニタ等を用いて搬送路の混雑状況のシミュレーション結果を表示する。具体的には、算出部３２が求めた搬送区間ごとの搬送流量の結果が表示される。
【００３７】
例えば、図７は、図３のレイアウトデータ２１上に算出部３２で求めた搬送流量を表示したものである。これが、工程処理装置間の搬送経路の搬送負荷を最小として計算した場合の最終的なシミュレーション結果である。搬送路の分岐点間である搬送区間毎の搬送流量がレイアウトデータ２１上に表示される。
【００３８】
上述したように搬送流量は、単位時間あたりの物品の搬送量を示しており、図７の例の場合、搬送路の中で、工程処理装置Ａの箇所が流量９であり混雑していることになる。
【００３９】
以上のように、第１の実施形態によれば、定常状態における工程間の搬送区間ごとの単位時間あたりの搬送量を高速に計算できる線形計画問題を作成し、搬送区間の定常状態での利用状況を高速に計算できるようになる。
【００４０】
（第２の実施形態）
図８は、第２の実施形態を示すブロック図である。図９がそのフローチャートである。
【００４１】
本実施形態の実施手順として、記憶部内のレイアウトデータ２１に基づいて、演算部３０内のレイアウトグラフ作成部３３でレイアウトグラフを作成する手順がある。それ以外の実施手順については、第１の実施形態と変わらないため、新しく増えたレイアウトグラフ作成部３３について説明する。
【００４２】
レイアウトグラフとは、図３のレイアウトデータにおける、投入位置、搬送路の分岐位置、及び工程処理装置位置を頂点とし、搬送方向を有向辺の方向とし、辺の重みを搬送負荷とする重み付有向グラフである。
【００４３】
レイアウトグラフは、記憶部２０内のレイアウトデータ２１と生産量データ２２を用いて演算部３０のレイアウトグラフ作成部３３で作成する（Ｓ９０１）。
【００４４】
図１０がレイアウトグラフの例である。分岐点に番号を付して、各工程処理装置位置に頂点を作成し、同一工程処理装置間でも名称を変更している。図３のレイアウトデータ２１の工程処理装置ＡをＡ１〜Ａ４としている。工程処理装置間の数字は、隣接する工程処理装置間を物品が移動するのに必要とされる搬送負荷を示している。基本的には、搬送区間の搬送負荷を搬送区間に存在する工程処理装置で均等割りした値としている。図１０の場合、頂点５と２の間の搬送区間の搬送負荷はそれぞれ５であり、頂点５と２の間にはそれぞれ４台の工程処理装置が存在するので、隣接する工程処理装置間の搬送負荷はそれぞれ１となる。レイアウトデータ２１では、搬送区間毎に搬送負荷を示しているが、レイアウトグラフでは、隣接する頂点毎に搬送負荷を示している。
【００４５】
隣接する工程処理装置間ごとの搬送負荷が決まっている場合は、ユーザがそれぞれ決定しても良い。これにより、搬送区間に複数の工程処理装置がある場合でも、より細かい搬送負荷が解る。
【００４６】
図１０の例では、払出位置に対しても頂点を作成しているが、払出位置を特別に扱わず、処理工程データにおいて、最後の工程を払出位置とするような工程列と考えても良い。
【００４７】
また、搬送路の分岐点である頂点２、５間、及び頂点３、４間を等搬送負荷となるように配置しているが、１つの搬送区間内の複数の工程処理装置を１つの頂点に代表させても良い。同一の装置を一纏めにした装置区画を考える場合は、複数の工程処理装置を１つの頂点に代表させても良い。
【００４８】
このようなレイアウトグラフを作成することで、ダイクストラ法等のアルゴリズムを用いることにより容易に最短経路を算出できる。ダイクストラ法とは、最短経路を効率的に解くグラフ理論に基づき、スタートからゴールまでの最短距離と経路を求めることができるアルゴリズムである。第一の実施形態の工程処理装置間の搬送経路の搬送負荷は、あらかじめユーザに与えられたものを用いているが、上記アルゴリズムとレイアウトグラフを用いることにより工程処理装置間の最短経路を与えることもできる。
【００４９】
また、図１１の例のように、算出部３２での結果をレイアウトグラフに出力して表示することもできる。演算部で計算するためのレイアウト情報として、レイアウトデータ２１に代わり、レイアウトグラフで与えても良い。
【００５０】
以上のように、第２の実施形態によれば、レイアウトグラフを作成することにより、
レイアウトデータ２１を必要最低限必要な情報に変換し、作成部３１の問題作成を容易にできる。
【００５１】
（第３の実施形態）
図１２は、第３の実施形態を示すブロック図である。図１３がそのフローチャートである。
【００５２】
本実施形態の実施手順として、演算部３０内の搬送経路計算部３４で、工程処理装置間の物品の搬送経路を計算する手順がある。それ以外の実施手順については、他の実施形態と変わらないため、新たに追加された搬送経路計算部３４について説明する。
【００５３】
搬送経路とは、複数の搬送区間を含み物品が搬送路を通過する経路のことをいう。ここでは、搬送経路と記載しているが搬送負荷と同一の意味として解釈される。
【００５４】
搬送経路計算部３４は、装置データおよびレイアウトグラフに基づいてｎ番目の工程を処理する各工程処理装置からｎ＋１番目の工程を処理する任意の工程処理装置について搬送経路を決定する。ここでは、ｎ＝０の工程を処理する工程処理装置を投入位置と考え、ｎ＝|Ｎ|＋１の工程を処理する工程処理装置を払出位置と考える（工程数を|Ｎ|とした）。
【００５５】
例えば、ｎ＝０の工程処理装置は、図１０のレイアウトグラフにおける頂点０、ｎ＝１の工程処理装置は、レイアウトグラフにおける頂点Ａ１〜Ａ４の４点であるので、搬送経路計算部３４の結果としては、図１４における最初の４行が得られる（搬送経路が最小となる経路を探索した場合）。同様にｎ＝１の工程を処理する各工程処理装置（Ａ１〜Ａ４）とｎ＝２の工程を処理する任意の工程処理装置（Ｂ１〜Ｂ４）間についても搬送経路を計算する（Ｓ１３０１）。
【００５６】
搬送経路計算部３４の結果からは、物品の移動が発生し得る全工程処理装置間について、搬送経路が分かる。
【００５７】
搬送経路計算部３４の計算する経路は、工程処理装置間での搬送経路が最小となる経路、いわゆる最短経路とするが、ユーザが指定する経路が存在するならばその経路を結果として返しても良い。
【００５８】
線形計画問題の目的関数として用いられる工程処理装置間の搬送経路の搬送負荷であるＷ［ｎ］［ｍ］は、搬送経路計算部３４の結果から定数として与えられる。
【００５９】
以上のように、第３の実施形態によれば、工程処理装置間の搬送経路（例えば、最短経路）を自動決定することを可能にし、さらに、入力情報として工程処理装置間の搬送経路を与えることを不必要にすることで、搬送経路の決まっていない装置レイアウト設計時等の際も利用できるようになる。
【００６０】
（第４の実施形態）
図１５は、第４の実施形態を示すブロック図である。本実施形態の実施手順として、記憶部２０に記憶されたユーザ指定データ２５を用いて、作成部３１で作成された線形計画問題に制約式を与える手順がある。それ以外の実施手順については、他の実施形態と変わらないため、新たに追加されたユーザ指定データに基づいて線形計画問題に制約式を与える手順について説明する。
【００６１】
ユーザ指定データ２５とは、線形計画問題を解く際に課す制約式のことを指し、ある工程処理装置が処理できる物品数や、ある工程処理装置が物品を処理する時間や工程処理装置Ａから工程処理装置Ｂへの単位時間あたりの搬送量等の条件が含まれる。
【００６２】
上述したように線形計画問題の目的式は、式（３）で表される。
【数４】
0006605951.tif 000005
【００６３】
そして、式（３）の線形計画問題を計算する際の制約式としては、以下が考えられる。
【００６４】
例えば、ｎ＋１番目の工程を処理する工程処理装置に同量の物品数を処理させたい場合は、制約式として、式（４）を追加する。
【数５】
0006605951.tif 000006
【００６５】
また、工程処理装置Ｍｍが物品を処理するのに要する時間Ｓｍが与えられていて、工程処理装置の可動時間を平準化したい場合には、制約式として、式（５）を追加する。
【数６】
0006605951.tif 000007
【００６６】
また、工程処理装置Ｍｍの物品を処理する量をユーザ指定の値Ｘｍとさせたい場合には、制約式として、式（６）を追加する。
【数７】
0006605951.tif 000008
【００６７】
Ｘｍ以下とさせたい場合には、式（７）を追加する。
【数８】
0006605951.tif 000009
【００６８】
Ｘｍ以上とさせたい場合には、式（８）を追加する。
【数９】
0006605951.tif 000010
【００６９】
工程処理装置Ｎｎから工程処理装置Ｍｍへの単位時間あたりの搬送量をユーザ指定の値Ｚｍとさせたい場合には、制約式として、式（９）を追加する。
【数１０】
0006605951.tif 000011
【００７０】
Ｚｍ以下とさせたい場合には、式（１０）を追加する。
【数１１】
0006605951.tif 000012
【００７１】
Ｚｍ以上とさせたい場合には、式（１１）を追加する。
【数１２】
0006605951.tif 000013
を追加する。
【００７２】
このように作成した線形計画問題をソルバーによって解かせることにより、変数をｕ１〜ｕ|Ｍ|と変数ｒ［ｎ］［ｍ］の値が求まる。
【００７３】
以上のように、第４の実施形態によれば、ユーザ指定データ２５を用いることにより、全ての工程処理装置について各工程を処理する物品量を均等に割り振ると仮定した場合の、搬送区間の利用状況（混雑状況）や、全ての工程処理装置について各工程の物品処理時間を均等にすると仮定した場合の、搬送区間の利用状況（混雑状況）や、各工程・各装置について処理する物品量を指定した条件でシミュレーションすることができる。
【００７４】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７５】
１０：入力部
２０：記憶部
２１：レイアウトデータ
２２：生産量データ
２３：処理工程データ
２４：装置データ
２５：ユーザ指定データ
３０：演算部
３１：作成部
３２：算出部
３３：レイアウトグラフ作成部
３４：搬送経路計算部
４０：線形計画問題ソルバー
５０：出力部
【図１】
0006605951.tif 000014
【図２】
0006605951.tif 000015
【図３】
0006605951.tif 000016
【図４】
0006605951.tif 000017
【図５】
0006605951.tif 000018
【図６】
0006605951.tif 000019
【図７】
0006605951.tif 000020
【図８】
0006605951.tif 000021
【図９】
0006605951.tif 000022
【図１０】
0006605951.tif 000023
【図１１】
0006605951.tif 000024
【図１２】
0006605951.tif 000025
【図１３】
0006605951.tif 000026
【図１４】
0006605951.tif 000027
【図１５】
0006605951.tif 000028