(57)【要約】【課題】複数の作業工程からなる作業プロセスの状態を表現する式を容易に作成する状態表現方法、状態表現装置、再計算の必要をなくしたスケジュール生成方法、スケジュール生成装置、コンピュータプログラム、及び記録媒体を提供する。【解決手段】作業が終了する予定時刻から、作業が開始される時刻を計算して、スケジュールを求めるための計算式は、図に示す第２構造体を記憶することで、パラメータを未知変数にしたままで表現する。計算式は、ｍａｘ−ｐｌｕｓ代数の和算で結ばれた各項について各一の第２構造体で表され、第２構造体は、各項にはｍａｘ−ｐｌｕｓ代数の乗算で結ばれたどのパラメータが存在しているかを示す。パラメータの値が与えられたときに、与えられたパラメータの値を計算式に代入して、作業プロセスのスケジュールを求める。【選択図】        図１４
2004240853.tif 000002
【特許請求の範囲】
【請求項１】
演算部と記憶部と該記憶部へ情報を取り込む取込部とを備えたコンピュータを用いて、複数の作業工程からなる作業プロセスについて、いずれかの作業工程が作業結果を供出すべき予定時刻から、いずれかの作業工程が作業対象の投入を受け付ける投入時刻を求めて、前記作業プロセスの投入時刻のスケジュールを生成する方法において、
前記予定時刻から前記投入時刻を計算するための計算式を、該計算式に含まれる複数のパラメータを未知変数にしたままで演算部にて作成して記憶部に記憶し、
前記予定時刻及び前記パラメータの夫々の値を取込部にて取り込み、
前記予定時刻及び前記パラメータの夫々の値を前記計算式に代入して、前記投入時刻を演算部にて計算する
ことを特徴とするスケジュール生成方法。
【請求項２】
複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を、演算部と記憶部と該記憶部へ情報を取り込む取込部とを備えたコンピュータを用いて表現する方法において、
作業対象を受け渡す各作業工程同士の関係を指定した制約行列、前記作業プロセスの外部から投入される作業対象である一又は複数の外部投入を受け付ける作業工程を指定した投入行列、及び前記作業プロセスの外部へ供出される作業結果である一又は複数の外部供出を供出する作業工程を指定した供出行列を、取込部にて取り込むステップと、
各作業工程の状態を示す複数のパラメータ、及び各外部投入に係るパラメータの夫々の存在数を示すための第１構造体を演算部にて生成するステップと、
前記制約行列及び前記投入行列が示す情報に基づいて、各作業工程の状態を表現する式にどのパラメータが存在しているかを示す第１構造体を、各作業工程に関連づけて記憶部に記憶するステップと、
各作業工程の状態を示す複数のパラメータの夫々の存在数を示すための第２構造体を演算部にて生成するステップと、
前記作業プロセスの状態を示す第１プロセス行列、第２プロセス行列、及び第３プロセス行列を演算部にて生成するステップと、
各作業工程に関連づけて記憶部に記憶してある第１構造体に基づいて、各作業工程同士の関係に関連するパラメータの存在を示す第２構造体を、第１プロセス行列の各要素として記憶部に記憶するステップと、
各作業工程に関連づけて記憶部に記憶してある第１構造体に基づいて、各作業工程と各外部投入との関係に関連するパラメータの存在を示す第２構造体を、第２プロセス行列の各要素として記憶部に記憶するステップと、
前記供出行列が示す情報に基づいて、各作業工程と各外部供出との関係に関連するパラメータの存在を示す第２構造体を、第３プロセス行列の各要素として記憶部に記憶するステップと
を含むことを特徴とする状態表現方法。
【請求項３】
前記作業プロセスについて、各外部供出が供出されるべき予定時刻から、各外部投入を受け付ける投入時刻を求めて、前記作業プロセスの投入時刻のスケジュールを生成する方法において、
請求項２に記載の状態表現方法を用いて作成された、前記第１プロセス行列、前記第２プロセス行列、及び前記第３プロセス行列を記憶部に記憶するステップと、
前記第１プロセス行列、前記第２プロセス行列、及び前記第３プロセス行列の各要素として記憶部に記憶している第２構造体に基づいて、前記予定時刻から各外部投入を受け付ける投入時刻を求めるための計算式を、該計算式に含まれる各項について該項には各作業工程の状態を示す複数のパラメータのうちどのパラメータが存在しているかを示す第２構造体を記憶部に記憶することで、演算部にて作成するステップと、
前記予定時刻及び前記パラメータの夫々の値を取込部にて取り込むステップと、
前記予定時刻及び前記パラメータの夫々の値を前記計算式に代入して、各外部投入を受け付ける投入時刻を演算部にて計算するステップと
を含むことを特徴とするスケジュール生成方法。
【請求項４】
複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を、演算部と記憶部と該記憶部へ情報を取り込む取込部とを備えたコンピュータを用いて表現する方法において、
対応する要素を所定の値にすることで夫々の作業工程へ作業対象を渡す一又は複数の作業工程を指定した制約行列を、取込部にて取り込むステップと、
対応する要素を所定の値にすることで前記作業プロセスの外部から投入される作業対象であるＭ個の外部投入の夫々を受け付ける作業工程を指定した投入行列を、取込部にて取り込むステップと、
対応する要素を所定の値にすることで前記作業プロセスの外部へ供出される作業結果であるＰ個の外部供出の夫々を供出する作業工程を指定した供出行列を、取込部にて取り込むステップと、
ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存在数を示す配列、ｎ個の各作業工程におけるｋ番目及びｋ＋１番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存在数を示す配列、並びにＭ個のｋ＋１番目の外部投入を受け付ける投入時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存在数を示す配列を含む第１構造体を演算部にて生成するステップと、
ｉ個目の作業工程に関連づけて、ｘｉ  （ｋ）及びｄｉ  （ｋ）に対応する成分が存在を示す値になった第１構造体を記憶部に記憶するステップと、
ｉ個目の作業工程に対して作業対象を渡す他の作業工程が前記制約行列に指定されているか否かを演算部にて判定するステップと、
ｉ個目の作業工程に対して作業対象を渡すｊ（ｊ＝１，２，…，ｎ）個目の作業工程が指定されていると判定された場合は、ｉ個目の作業工程に関連づけて、ｘｊ  （ｋ＋１）及びｄｊ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶部に記憶するステップと、
ｉ個目の作業工程が、Ｍ個の外部投入のいずれかを受け付ける作業工程として前記投入行列に指定されているか否かを演算部にて判定するステップと、
ｉ個目の作業工程がｍ個目の外部投入を受け付ける作業工程として指定されていると判定された場合は、ｉ個目の作業工程に関連づけて、ｕｍ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶部に記憶するステップと、
各作業工程に関連づけて記憶している複数の第１構造体のうち、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があるか否かを演算部にて判定する判定ステップと、
ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があると判定された場合は、関連づけられている複数の第１構造体のｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）に対応する成分が存在数０を示す値になっているｉ個目の作業工程、及びｘｉ  （ｋ＋１）に対応する成分が存在数１以上を示す値になっているｊ個目の作業工程を演算部にて選択する選択ステップと、
ｊ個目の作業工程に関連づけられた第１構造体のｘｉ  （ｋ＋１）に対応する成分以外の各成分の値をｉ個目の作業工程に関連づけられている複数の第１構造体の各成分に加えた新たな複数の第１構造体を、ｊ個目の作業工程に関連づけて記憶部に記憶する記憶ステップと、
ｊ個目の作業工程に関連づけられたｘｉ  （ｋ＋１）の存在を示す第１構造体を記憶部から削除する削除ステップと、
ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体がないと演算部にて判定されるまで、前記判定ステップ、前記選択ステップ、前記記憶ステップ、及び前記削除ステップを演算部及び記憶部にて繰り返すステップと、
｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示す配列を含む第２構造体を演算部にて生成するステップと、
前記作業プロセスの状態を示すｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を演算部にて生成するステップと、
ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶部に記憶するステップと、
ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶部に記憶するステップと、
ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶部に記憶するステップと、
ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶部に記憶するステップと、
ｉ個目の作業工程が、Ｐ個の外部供出のいずれかを供出する作業工程として前記供出行列に指定されているか否かを演算部にて判定するステップと、
ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていると判定された場合は、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分が存在を示す値になった第２構造体を記憶部に記憶するステップと、
ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていないと判定された場合は、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、第２構造体の数が０個であることを記憶部に記憶するステップと、
を含むことを特徴とする状態表現方法。
【請求項５】
前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数により、Ｍ個の外部投入の夫々のｋ＋１，…，ｋ＋Ｎ番目を受け付ける投入時刻｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を求めて、前記作業プロセスの投入時刻のスケジュールを生成する方法であって、
請求項４に記載の状態表現方法を用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  を記憶部に記憶するステップと、
前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  、Ｂｋ＋１  及びＣｋ＋１  を演算部にて作成する作成ステップと、
該作成ステップを演算部にて繰り返して、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を演算部にて作成するステップと、
ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）を内部に含む行列
【数１】
2004240853.tif 000038
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、演算部にて作成するステップと、
｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を取込部にて取り込むステップと、
行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、演算部にて要素の値を−∞とするステップと、
行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、演算部にて要素の値とするステップと、
｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を、
【数２】
2004240853.tif 000039
と演算部にて計算するステップと
を含むことを特徴とするスケジュール生成方法。
【請求項６】
前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数により、Ｍ個の外部投入の夫々のｋ＋１番目を受け付ける投入時刻｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を求めて、前記作業プロセスの投入時刻のスケジュールを生成する方法であって、
請求項４に記載の状態表現方法を用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  を記憶部に記憶するステップと、
前記第１プロセス行列Ａｋ  及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  及びＣｋ＋１  を演算部にて作成する作成ステップと、
該作成ステップを演算部にて繰り返して、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を演算部にて作成するステップと、
ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）からなる行列
【数３】
2004240853.tif 000040
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、演算部にて作成するステップと、
｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を取込部にて取り込むステップと、
行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、演算部にて要素の値を−∞とするステップと、
行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、演算部にて要素の値とするステップと、
｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を、
【数４】
2004240853.tif 000041
と演算部にて計算するステップと
を含むことを特徴とするスケジュール生成方法。
【請求項７】
｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の新たな値を取込部にて取り込むステップと、
取り込んだ｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の新たな値を用いて、行列Γｋ  及びΔｋ’の各要素の値を演算部にて求めるステップと、
求めた行列Γｋ  及びΔｋ’を用いて新たな｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を演算部にて計算するステップと
を更に含むことを特徴とする請求項６に記載のスケジュール生成方法。
【請求項８】
複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を表現する状態表現装置において、
対応する要素を所定の値にすることで夫々の作業工程へ作業対象を渡す一又は複数の作業工程を指定した制約行列を受け付ける手段と、
対応する要素を所定の値にすることで前記作業プロセスの外部から投入される作業対象であるＭ個の外部投入の夫々を受け付ける作業工程を指定した投入行列を受け付ける手段と、
対応する要素を所定の値にすることで前記作業プロセスの外部へ供出される作業結果であるＰ個の外部供出の夫々を供出する作業工程を指定した供出行列を受け付ける手段と、
ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存在数を示す配列、ｎ個の各作業工程におけるｋ番目及びｋ＋１番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存在数を示す配列、並びにＭ個のｋ＋１番目の外部投入を受け付ける投入時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存在数を示す配列を含む第１構造体を生成する手段と、
ｉ個目の作業工程に関連づけて、ｘｉ  （ｋ）及びｄｉ  （ｋ）に対応する成分が存在を示す値になった第１構造体を記憶する手段と、
ｉ個目の作業工程に対して作業対象を渡す他の作業工程が前記制約行列に指定されているか否かを判定する手段と、
ｉ個目の作業工程に対して作業対象を渡すｊ（ｊ＝１，２，…，ｎ）個目の作業工程が指定されていると判定された場合は、ｉ個目の作業工程に関連づけて、ｘｊ  （ｋ＋１）及びｄｊ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶する手段と、
ｉ個目の作業工程が、Ｍ個の外部投入のいずれかを受け付ける作業工程として前記投入行列に指定されているか否かを判定する手段と、
ｉ個目の作業工程がｍ個目の外部投入を受け付ける作業工程として指定されていると判定された場合は、ｉ個目の作業工程に関連づけて、ｕｍ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶する手段と、
各作業工程に関連づけて記憶している複数の第１構造体のうち、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があるか否かを判定する判定手段と、
ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があると判定された場合は、関連づけられている複数の第１構造体のｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）に対応する成分が存在数０を示す値になっているｉ個目の作業工程、及びｘｉ  （ｋ＋１）に対応する成分が存在数１以上を示す値になっているｊ個目の作業工程を選択する選択手段と、
ｊ個目の作業工程に関連づけられた第１構造体のｘｉ  （ｋ＋１）に対応する成分以外の各成分の値をｉ個目の作業工程に関連づけられている複数の第１構造体の各成分に加えた新たな複数の第１構造体を、ｊ個目の作業工程に関連づけて記憶する記憶手段と、
ｊ個目の作業工程に関連づけられたｘｉ  （ｋ＋１）の存在を示す第１構造体を削除する削除手段と、
ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体がないと前記判定手段によって判定されるまで、前記判定手段、前記選択手段、前記記憶手段、及び前記削除手段を繰り返し動作させる手段と、
｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示す配列を含む第２構造体を生成する手段と、
前記作業プロセスの状態を示すｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を生成する手段と、
ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶する手段と、
ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶する手段と、
ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶する手段と、
ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶する手段と、ｉ個目の作業工程が、Ｐ個の外部供出のいずれかを供出する作業工程として前記供出行列に指定されているか否かを判定する手段と、
ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていると判定された場合は、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分が存在を示す値になった第２構造体を記憶する手段と、
ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていないと判定された場合は、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、第２構造体の数が０個であることを記憶する手段と
を備えることを特徴とする状態表現装置。
【請求項９】
前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１，…，ｋ＋Ｎ番目を受け付ける投入時刻｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を求めて、前記作業プロセスの投入時刻のスケジュールを生成する装置であって、
請求項８に記載の状態表現装置を用いて作成された、前記第１プロセス行列Ａｋ  、前記の第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  を記憶する手段と、
前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  、Ｂｋ＋１  及びＣｋ＋１  を作成する作成手段と、
該作成手段の動作を繰り返して、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成する手段と、
ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）を内部に含む行列
【数５】
2004240853.tif 000042
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成する手段と、
｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付ける手段と、
行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞とする手段と、
行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とする手段と、
｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を、
【数６】
2004240853.tif 000043
と計算する手段と
を備えることを特徴とするスケジュール生成装置。
【請求項１０】
前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１番目を受け付ける投入時刻｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を求めて、前記作業プロセスの投入時刻のスケジュールを生成する装置であって、
請求項８に記載の状態表現装置を用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  を記憶する手段と、
前記第１プロセス行列Ａｋ  及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  及びＣｋ＋１  を作成する作成手段と、
該作成手段の動作を繰り返して、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成する手段と、
ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）からなる行列
【数７】
2004240853.tif 000044
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成する手段と、
｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付ける手段と、
行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞とする手段と、
行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とする手段と、
｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を、
【数８】
2004240853.tif 000045
と計算する手段と
を備えることを特徴とするスケジュール生成装置。
【請求項１１】
｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の新たな値を受け付ける手段と、
受け付けた｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の新たな値を用いて、行列Γｋ  及びΔｋ’の各要素の値を求める手段と、
求めた行列Γｋ  及びΔｋ’を用いて新たな｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を計算する手段と
を更に備えることを特徴とする請求項１０に記載のスケジュール生成装置。
【請求項１２】
複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を、コンピュータに表現させるコンピュータプログラムにおいて、
コンピュータに、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存在数を示す配列、ｎ個の各作業工程におけるｋ番目及びｋ＋１番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存在数を示す配列、並びにＭ個のｋ＋１番目の外部投入を受け付ける投入時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存在数を示す配列を含む第１構造体を生成させる手順と、
コンピュータに、ｉ個目の作業工程に関連づけて、ｘｉ  （ｋ）及びｄｉ  （ｋ）に対応する成分が存在を示す値になった第１構造体を記憶させる手順と、
コンピュータに、対応する要素を所定の値にすることで夫々の作業工程へ作業対象を渡す一又は複数の作業工程を指定した制約行列に、ｉ個目の作業工程に対して作業対象を渡す他の作業工程が指定されているか否かを判定させる手順と、ｉ個目の作業工程に対して作業対象を渡すｊ（ｊ＝１，２，…，ｎ）個目の作業工程が指定されていると判定された場合は、コンピュータに、ｉ個目の作業工程に関連づけて、ｘｊ  （ｋ＋１）及びｄｊ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶させる手順と、
コンピュータに、対応する要素を所定の値にすることで前記作業プロセスの外部から投入される作業対象であるＭ個の外部投入の夫々を受け付ける作業工程を指定した投入行列に、ｉ個目の作業工程が、Ｍ個の外部投入のいずれかを受け付ける作業工程として指定されているか否かを判定させる手順と、
ｉ個目の作業工程がｍ個目の外部投入を受け付ける作業工程として指定されていると判定された場合は、コンピュータに、ｉ個目の作業工程に関連づけて、ｕｍ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶させる手順と、
コンピュータに、各作業工程に関連づけて記憶している複数の第１構造体のうち、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があるか否かを判定させる判定手順と、
ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があると判定された場合は、コンピュータに、関連づけられている複数の第１構造体のｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）に対応する成分が存在数０を示す値になっているｉ個目の作業工程、及びｘｉ  （ｋ＋１）に対応する成分が存在数１以上を示す値になっているｊ個目の作業工程を選択させる選択手順と、
コンピュータに、ｊ個目の作業工程に関連づけられた第１構造体のｘｉ  （ｋ＋１）に対応する成分以外の各成分の値をｉ個目の作業工程に関連づけられている複数の第１構造体の各成分に加えた新たな複数の第１構造体を、ｊ個目の作業工程に関連づけて記憶させる記憶手順と、
コンピュータに、ｊ個目の作業工程に関連づけられたｘｉ  （ｋ＋１）の存在を示す第１構造体を削除させる削除手順と、
ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体がないと前記判定手順にて判定されるまで、コンピュータに、前記判定手順、前記選択手順、前記記憶手順、及び前記削除手順を繰り返させる手順と、
コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示す配列を含む第２構造体を生成させる手順と、
コンピュータに、前記作業プロセスの状態を示すｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を生成させる手順と、
コンピュータに、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶させる手順と、
コンピュータに、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶させる手順と、
コンピュータに、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶させる手順と、
コンピュータに、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶させる手順と、
コンピュータに、対応する要素を所定の値にすることで前記作業プロセスの外部へ供出される作業結果であるＰ個の外部供出の夫々を供出する作業工程を指定した供出行列に、ｉ個目の作業工程が、Ｐ個の外部供出のいずれかを供出する作業工程として指定されているか否かを判定させる手順と、
ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていると判定された場合は、コンピュータに、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分が存在を示す値になった第２構造体を記憶させる手順と、
ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていないと判定された場合は、コンピュータに、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、第２構造体の数が０個であることを記憶させる手順と
を含むことを特徴とするコンピュータプログラム。
【請求項１３】
コンピュータに、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１，…，ｋ＋Ｎ番目を受け付ける投入時刻｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を求めさせて、前記作業プロセスの投入時刻のスケジュールを生成させるコンピュータプログラムであって、
コンピュータに、請求項１２に記載のコンピュータプログラムを用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  、Ｂｋ＋１  及びＣｋ＋１  を作成させる作成手順と、
コンピュータに、該作成手順を繰り返させて、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成させる手順と、
コンピュータに、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）を内部に含む行列
【数９】
2004240853.tif 000046
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成させる手順と、
コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付けさせる手順と、
コンピュータに、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞にさせる手順と、
コンピュータに、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とさせる手順と、
コンピュータに、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を用いて、｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を、
【数１０】
2004240853.tif 000047
と計算させる手順と
を含むことを特徴とするコンピュータプログラム。
【請求項１４】
コンピュータに、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１番目を受け付ける投入時刻｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を求めて前記作業プロセスのスケジュールを生成させるコンピュータプログラムであって、
コンピュータに、請求項１２に記載のコンピュータプログラムを用いて作成された前記第１プロセス行列Ａｋ  及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  及びＣｋ＋１  を作成させる作成手順と、
コンピュータに、該作成手順を繰り返させて、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成させる手順と、
コンピュータに、行列Ａｋ  ，Ａｋ＋１  ，…，Ａｋ＋Ｎ−１  、行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  、及び請求項１２に記載のコンピュータプログラムを用いて作成された前記第２プロセス行列Ｂｋ  を用いて、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）からなる行列
【数１１】
2004240853.tif 000048
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成させる手順と、
コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付けさせる手順と、
コンピュータに、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞とさせる手順と、
コンピュータに、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とさせる手順と、
コンピュータに、｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を、
【数１２】
2004240853.tif 000049
と計算させる手順と
を含むことを特徴とするコンピュータプログラム。
【請求項１５】
コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の新たな値を受け付けさせる手順と、
コンピュータに、受け付けた｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の新たな値を用いて、行列Γｋ  及びΔｋ’の各要素の値を求めさせる手順と、
コンピュータに、求めた行列Γｋ  及びΔｋ’を用いて新たな｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を計算させる手順と
を更に含むことを特徴とする請求項１４に記載のコンピュータプログラム。
【請求項１６】
複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を、コンピュータに表現させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、
コンピュータに、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存在数を示す配列、ｎ個の各作業工程におけるｋ番目及びｋ＋１番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存在数を示す配列、並びにＭ個のｋ＋１番目の外部投入を受け付ける投入時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存在数を示す配列を含む第１構造体を生成させる手順と、
コンピュータに、ｉ個目の作業工程に関連づけて、ｘｉ  （ｋ）及びｄｉ  （ｋ）に対応する成分が存在を示す値になった第１構造体を記憶させる手順と、
コンピュータに、対応する要素を所定の値にすることで夫々の作業工程へ作業対象を渡す一又は複数の作業工程を指定した制約行列に、ｉ個目の作業工程に対して作業対象を渡す他の作業工程が指定されているか否かを判定させる手順と、ｉ個目の作業工程に対して作業対象を渡すｊ（ｊ＝１，２，…，ｎ）個目の作業工程が指定されていると判定された場合は、コンピュータに、ｉ個目の作業工程に関連づけて、ｘｊ  （ｋ＋１）及びｄｊ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶させる手順と、
コンピュータに、対応する要素を所定の値にすることで前記作業プロセスの外部から投入される作業対象であるＭ個の外部投入の夫々を受け付ける作業工程を指定した投入行列に、ｉ個目の作業工程が、Ｍ個の外部投入のいずれかを受け付ける作業工程として指定されているか否かを判定させる手順と、
ｉ個目の作業工程がｍ個目の外部投入を受け付ける作業工程として指定されていると判定された場合は、コンピュータに、ｉ個目の作業工程に関連づけて、ｕｍ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶させる手順と、
コンピュータに、各作業工程に関連づけて記憶している複数の第１構造体のうち、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があるか否かを判定させる判定手順と、
ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があると判定された場合は、コンピュータに、関連づけられている複数の第１構造体のｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）に対応する成分が存在数０を示す値になっているｉ個目の作業工程、及びｘｉ  （ｋ＋１）に対応する成分が存在数１以上を示す値になっているｊ個目の作業工程を選択させる選択手順と、
コンピュータに、ｊ個目の作業工程に関連づけられた第１構造体のｘｉ  （ｋ＋１）に対応する成分以外の各成分の値をｉ個目の作業工程に関連づけられている複数の第１構造体の各成分に加えた新たな複数の第１構造体を、ｊ個目の作業工程に関連づけて記憶させる記憶手順と、
コンピュータに、ｊ個目の作業工程に関連づけられたｘｉ  （ｋ＋１）の存在を示す第１構造体を削除させる削除手順と、
ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体がないと前記判定手順にて判定されるまで、コンピュータに、前記判定手順、前記選択手順、前記記憶手順、及び前記削除手順を繰り返させる手順と、
コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示す配列を含む第２構造体を生成させる手順と、
コンピュータに、前記作業プロセスの状態を示すｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を生成させる手順と、
コンピュータに、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶させる手順と、
コンピュータに、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶させる手順と、
コンピュータに、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶させる手順と、
コンピュータに、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶させる手順と、
コンピュータに、対応する要素を所定の値にすることで前記作業プロセスの外部へ供出される作業結果であるＰ個の外部供出の夫々を供出する作業工程を指定した供出行列に、ｉ個目の作業工程が、Ｐ個の外部供出のいずれかを供出する作業工程として指定されているか否かを判定させる手順と、
ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていると判定された場合は、コンピュータに、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分が存在を示す値になった第２構造体を記憶させる手順と、
ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていないと判定された場合は、コンピュータに、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、第２構造体の数が０個であることを記憶させる手順と
を含むコンピュータプログラムを記録してあることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【請求項１７】
コンピュータに、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１，…，ｋ＋Ｎ番目を受け付ける投入時刻｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を求めさせて、前記作業プロセスの投入時刻のスケジュールを生成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体であって、
コンピュータに、請求項１２に記載のコンピュータプログラムを用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  、Ｂｋ＋１  及びＣｋ＋１  を作成させる作成手順と、
コンピュータに、該作成手順を繰り返させて、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成させる手順と、
コンピュータに、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）を内部に含む行列
【数１３】
2004240853.tif 000050
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成させる手順と、
コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付けさせる手順と、
コンピュータに、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞にさせる手順と、
コンピュータに、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とさせる手順と、
コンピュータに、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を用いて、｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を、
【数１４】
2004240853.tif 000051
と計算させる手順と
を含むコンピュータプログラムを記録してあることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【請求項１８】
コンピュータに、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１番目を受け付ける投入時刻｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を求めて前記作業プロセスのスケジュールを生成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体であって、
コンピュータに、請求項１２に記載のコンピュータプログラムを用いて作成された前記第１プロセス行列Ａｋ  及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  及びＣｋ＋１  を作成させる作成手順と、
コンピュータに、該作成手順を繰り返させて、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成させる手順と、
コンピュータに、行列Ａｋ  ，Ａｋ＋１  ，…，Ａｋ＋Ｎ−１  、行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  、及び請求項１２に記載のコンピュータプログラムを用いて作成された前記第２プロセス行列Ｂｋ  を用いて、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）からなる行列
【数１５】
2004240853.tif 000052
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成させる手順と、
コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付けさせる手順と、
コンピュータに、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞とさせる手順と、
コンピュータに、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とさせる手順と、
コンピュータに、｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を、
【数１６】
2004240853.tif 000053
と計算させる手順と
を含むコンピュータプログラムを記録してあることを特徴とするコンピュータでの読み取りが可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の作業工程を経て作業を行う作業プロセスの状態を表現する方法、前記作業プロセスのスケジュールを生成する方法、状態表現装置、スケジュール生成装置、コンピュータプログラム、及び記録媒体に関する。
【０００２】
【従来の技術】
製品を生産するための生産システム、又は物流システム等などの作業プロセスでは、複数の作業工程により構成されており、ある作業工程が終了しないと次の作業工程に移れない、又は特定の作業工程で作業時間が多くかかる等の制約が発生する。これらの順序関係を有する複数の作業工程が存在する作業プロセスでのスケジュールは、前記制約に従いながらしかも納期遅れを出さないように計画する必要がある。従来、スケジュールを生成するために、ガントチャートが用いられており、納期により最終の作業工程の終了時間が規定され、納期から逆算して各作業工程の開始時間が決定される。ガントチャートは、手作業による作成、又は組み合わせ最適化を用いた計算方法による作成などの方法で作成され、作成されたガントチャートに従って、作業プロセスが管理される。
【０００３】
作業プロセスのスケジュールを生成するための方法の一つとして、ｍａｘ−ｐｌｕｓ代数を用いた方法がある。ｍａｘ−ｐｌｕｓ代数では、実数体をＲと表し、ＲＥ  ＝Ｒ∪｛−∞｝において、加算（丸に＋）および乗算（丸に×）を、
【０００４】
【数１７】
2004240853.tif 000003
【０００５】
と定義する。ｍａｘ−ｐｌｕｓ代数の加算および乗算の単位元は、（１）式の定義により、夫々−∞および０となり、夫々を、
加算の単位元：−∞＝ε
乗算の単位元：０＝ｅ
と表す。また、（１）式以外に、以下の２つの演算子も定義する。
【０００６】
【数１８】
2004240853.tif 000004
【０００７】
ｍａｘ−ｐｌｕｓ代数の加算および乗算の演算子は、通常の代数と同様に、乗算が加算よりも優先度が高いとする。ｍａｘ−ｐｌｕｓ代数系においても、通常の代数系と同様に分配法則が成り立ち、式の変形など通常の代数系と同様の代数計算を行うことができる。また、行列に対しても同様な演算子を定義する。Ｍ行ｎ列の行列Ａ，Ｂ、及びｎ行ｐ列の行列Ｃに対して、
【０００８】
【数１９】
2004240853.tif 000005
【０００９】
と定義する。なお、（３）式において、［Ｘ］ｉｊは行列Ｘのｉ行ｊ列成分を表している。以上の定義により、ｍａｘ−ｐｌｕｓ代数において、線形性を有する行列演算が可能となる。以上の如きｍａｘ−ｐｌｕｓ代数を用いて、作業プロセスへの材料の投入，製品の完成などの回数（以下、イベントカウンタと言う）を独立変数とし、作業プロセス内で作業が行われる時刻をイベントカウンタの関数として記述し、スケジュールを生成することができる。
【００１０】
次に、ｍａｘ−ｐｌｕｓ代数を用いて作業プロセス内で作業が行われる時刻を記述する方法を説明する。図２０は、作業プロセスとしての生産システムの例を示す模式図である。図中には、機械Ｍ１，機械Ｍ２，機械Ｍ３が生産設備として備えられており、機械Ｍ１，Ｍ２は、夫々に材料となる部品を投入されて該部品を加工し、機械Ｍ３は、機械Ｍ１，Ｍ２の夫々において加工された部品を渡されて、加工済みの部品を更に加工して完成させる例を示している。部品の投入および受け渡しは次々に繰り返され、部品が加工されていく。この生産システムに対して、以下の変数を定義する。
ｘ１（ｋ），ｘ２（ｋ），ｘ３（ｋ）
：機械Ｍ１，Ｍ２，Ｍ３がｋ番目の部品の加工を開始する時刻
ｕ１（ｋ），ｕ２（ｋ）
：機械Ｍ１，Ｍ２にｋ番目の部品が投入される時刻
ｙ（ｋ）：機械Ｍ３において、ｋ番目の部品の加工が終了する時刻
ｄ１（ｋ），ｄ２（ｋ），ｄ３（ｋ）
：機械Ｍ１，Ｍ２，Ｍ３におけるｋ番目の部品の加工時間
ここで、ｋはイベントカウンタであり、この生産システムにおいては部品番号に相当する。また、図中に示した生産システムには、以下の如き制約条件が存在する。
・機械Ｍ１及び機械Ｍ２は、ｋ番目の部品の加工が終了して、しかも（ｋ＋１）番目の部品が投入されるまで、（ｋ＋１）番目の部品の加工を開始することができない。
・機械Ｍ３は、ｋ番目の部品の加工が終了して、しかも機械Ｍ１及び機械Ｍ２から（ｋ＋１）番目の部品を受け付けるまで、（ｋ＋１）番目の部品の加工を開始することができない。
以上の制約条件より、例えば機械Ｍ１が（ｋ＋１）番目の部品の加工を開始する時刻ｘ１  （ｋ＋１）は、ｋ番目の部品の加工を終了した時刻と、（ｋ＋１）番目の部品が投入された時刻との遅い方の時刻に定められることになる。このように、以上の制約条件は、通常の代数式で以下の如く記述することができる。
【００１１】
【数２０】
2004240853.tif 000006
【００１２】
（４）式は、ｍａｘ及び＋で構成されているため、ｍａｘ−ｐｌｕｓ代数の加算および乗算を用いて表すことができる。従って、（４）式は以下の如く表現することができる。
【００１３】
【数２１】
2004240853.tif 000007
【００１４】
（５）式の第３式に、第１式および第２式を代入して整理することで、（５）式は、
【００１５】
【数２２】
2004240853.tif 000008
【００１６】
となる。但し、図２０に示した生産システムの場合、
【００１７】
【数２３】
2004240853.tif 000009
【００１８】
である。（６）式は、作業プロセスでの作業開始時刻および終了時刻に関する一般的な表現となっている。生産システムでの機械の数、即ち作業プロセスでの作業工程の数をｎとすると、Ａｋ  はｎ×ｎの行列、Ｂｋ  はｎ×Ｍの行列、Ｃｋ  はＰ×ｎの行列である。生産システムの場合は、Ｍは外部から投入される部品の数、Ｐは生産システムで加工が完了する部品の数である。（６）式を繰り返し用いて（ｋ＋１）番目以降についての同様の式を計算すると、
【００１９】
【数２４】
2004240853.tif 000010
【００２０】
が得られる。得られた式の両辺に、夫々Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を前から乗ずることにより、以下の式を得ることができる。
【００２１】
【数２５】
2004240853.tif 000011
【００２２】
ここで、εＰＭは、各要素の値がεであるＰ×Ｍの行列である。（７）式は、未来の部品の加工が終了する時刻Ｙ（ｋ＋１）が、現在の内部状態ｘ（ｋ）と未来の部品の投入時刻Ｕ（ｋ＋１）とから計算されることを示している。従って、生産システムの内部状態ｘ（ｋ）が定まっており、Ｙ（ｋ＋１）として、生産システムにおける納期である望ましい出力Ｒ（ｋ＋１）を定めたとき、納期遅れを出すことがない適切な入力Ｕ（ｋ＋１）を求めることができる。適切な入力Ｕ（ｋ＋１）を求めるためには、（７）式のＹ（ｋ＋１）にＲ（ｋ＋１）を代入した以下の式
【００２３】
【数２６】
2004240853.tif 000012
【００２４】
を満たすＵ（ｋ＋１）を求めれば良い。（８）式は、右辺の第１項または第２項のどちらか大きい方が左辺と等しいことを示しており、右辺の第１項が左辺以下である場合は、右辺の第二項が左辺と等しくなるため、（８）式は、
【００２５】
【数２７】
2004240853.tif 000013
【００２６】
となる。また、右辺の第一項が左辺よりも大きい場合は、（８）式を満たすＵ（ｋ＋１）は存在せず、現在の内部状態では納期遅れが避けられない状態である。しかし、可能な限り納期遅れを小さくするためには、右辺の第二項が示す部品の投入時刻を、右辺の第一項が示す現在の時刻に等しくすれば良い。即ち、
【００２７】
【数２８】
2004240853.tif 000014
【００２８】
となる。（９）式および（１０）式をまとめることにより、
【００２９】
【数２９】
2004240853.tif 000015
【００３０】
が得られる。（１１）式は、ｍａｘ−ｐｌｕｓ代数系でのＵ（ｋ＋１）に対する連立一次方程式の形式となっている。この式は、ｍａｘ−ｐｌｕｓ代数における最大部分解の解法を利用することができる。最大部分解とは、
【００３１】
【数３０】
2004240853.tif 000016
【００３２】
で与えられる連立一次方程式において、式を満たす解が求められる場合にはその解を与え、式を満たす解が求められない場合には右辺の値を超えない範囲で最大の左辺の値を与える解である。（１２）式の最大部分解は、
【００３３】
【数３１】
2004240853.tif 000017
【００３４】
で与えられる。従って、（１１）式の最大部分解は、
【００３５】
【数３２】
2004240853.tif 000018
【００３６】
となる。（１３）式は、生産システムにおいて、定められた予定時刻Ｒ（ｋ＋１）に対して、予定時刻丁度に製品を完成させることができる場合は、予定時刻丁度に製品を完成させるような部品の投入時刻Ｕ（ｋ＋１）を求め、予定時刻丁度に製品を完成させることが不可能な場合は、製品の完成が予定時刻に遅れず、しかも最も遅い投入時刻Ｕ（ｋ＋１）を求めていることを示している。（１３）式では、イベントカウンタがｋ＋１，ｋ＋２，…，ｋ＋Ｎである全ての場合について投入時刻を求めているが、投入時刻は、次の式
【００３７】
【数３３】
2004240853.tif 000019
【００３８】
を用いて、イベントカウンタがｋ＋１の場合のみを求める。ｋ＋２以降の場合は、イベントカウンタを一つづつ増やして再計算することにより求める。（１４）式を用いることにより、生産システムに適切な投入時刻を求めることが可能となり、作業プロセスのスケジュールを作成することができる。
【００３９】
【非特許文献１】
シャッター（Ｂ．  Ｄｅ  Ｓｃｈｕｔｔｅｒ），ブーン（Ｔ．  ｖａｎ  ｄｅｎ  Ｂｏｏｍ）「モデル  プレディクティブ  コントロール  フォア  マックス−プラス−リニア  ディスクリート  イベント  システムズ（Ｍｏｄｅｌ  ｐｒｅｄｉｃｔｉｖｅ  ｃｏｎｔｒｏｌ  ｆｏｒ  ｍａｘ−ｐｌｕｓ−ｌｉｎｅａｒ  ｄｉｓｃｒｅｔｅ  ｅｖｅｎｔ  ｓｙｓｔｅｍｓ）」，オートマティカ（Ａｕｔｏｍａｔｉｃａ），２００１年  ３７巻  ７号  ｐ．１０４９−１０５６
【００４０】
【発明が解決しようとする課題】
（１３）式および（１４）式を用いて作業プロセスのスケジュールを作成するためには、従来は、作業プロセスをモデル化して（６）式に対応する作業プロセスの状態を表現した式を作成し、線形計画法などを用いた数値計算を行い、（１３）式および（１４）式を用いてスケジュールを作成していた。従来の数値計算を行う方法では、作業プロセスの状態を表現する式を作成する作業を手作業で行っているため、複雑な作業プロセスに対して適用することが困難であるという問題がある。また、従来の方法では、部品の受け渡しの順序などの作業プロセスの構成が変化しなくても、パラメータの数値を入れ替える都度、数値計算を最初から再計算する必要があり、計算が非効率で時間がかかるという問題がある。
【００４１】
本発明は、斯かる事情に鑑みてなされたものであって、その目的とするところは、機械同士の関係、各機械と外部投入との関係、及び各機械と外部供出との関係を行列で表して、該行列を読み込むことにより、作業プロセスの状態を表現する式を容易に作成する状態表現方法、状態表現装置、コンピュータを該状態表現装置として実現するためのコンピュータプログラム、及び記録媒体を提供することにある。
【００４２】
更に、本発明の他の目的とするところは、計算に必要な数値の値を、未知変数のまま扱ってスケジュールを計算するための式を作成することにより、再計算の必要をなくしたスケジュール生成方法、スケジュール生成装置、コンピュータを該スケジュール生成装置として実現するためのコンピュータプログラム、及び記録媒体を提供することにある。
【００４３】
【課題を解決するための手段】
第１発明に係るスケジュール生成方法は、演算部と記憶部と該記憶部へ情報を取り込む取込部とを備えたコンピュータを用いて、複数の作業工程からなる作業プロセスについて、いずれかの作業工程が作業結果を供出すべき予定時刻から、いずれかの作業工程が作業対象の投入を受け付ける投入時刻を求めて、前記作業プロセスの投入時刻のスケジュールを生成する方法において、前記予定時刻から前記投入時刻を計算するための計算式を、該計算式に含まれる複数のパラメータを未知変数にしたままで演算部にて作成して記憶部に記憶し、前記予定時刻及び前記パラメータの夫々の値を取込部にて取り込み、前記予定時刻及び前記パラメータの夫々の値を前記計算式に代入して、前記投入時刻を演算部にて計算することを特徴とする。
【００４４】
第２発明に係る状態表現方法は、複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を、演算部と記憶部と該記憶部へ情報を取り込む取込部とを備えたコンピュータを用いて表現する方法において、作業対象を受け渡す各作業工程同士の関係を指定した制約行列、前記作業プロセスの外部から投入される作業対象である一又は複数の外部投入を受け付ける作業工程を指定した投入行列、及び前記作業プロセスの外部へ供出される作業結果である一又は複数の外部供出を供出する作業工程を指定した供出行列を、取込部にて取り込むステップと、各作業工程の状態を示す複数のパラメータ、及び各外部投入に係るパラメータの夫々の存在数を示すための第１構造体を演算部にて生成するステップと、前記制約行列及び前記投入行列が示す情報に基づいて、各作業工程の状態を表現する式にどのパラメータが存在しているかを示す第１構造体を、各作業工程に関連づけて記憶部に記憶するステップと、各作業工程の状態を示す複数のパラメータの夫々の存在数を示すための第２構造体を演算部にて生成するステップと、前記作業プロセスの状態を示す第１プロセス行列、第２プロセス行列、及び第３プロセス行列を演算部にて生成するステップと、各作業工程に関連づけて記憶部に記憶してある第１構造体に基づいて、各作業工程同士の関係に関連するパラメータの存在を示す第２構造体を、第１プロセス行列の各要素として記憶部に記憶するステップと、各作業工程に関連づけて記憶部に記憶してある第１構造体に基づいて、各作業工程と各外部投入との関係に関連するパラメータの存在を示す第２構造体を、第２プロセス行列の各要素として記憶部に記憶するステップと、前記供出行列が示す情報に基づいて、各作業工程と各外部供出との関係に関連するパラメータの存在を示す第２構造体を、第３プロセス行列の各要素として記憶部に記憶するステップとを含むことを特徴とする。
【００４５】
第３発明に係るスケジュール生成方法は、前記作業プロセスについて、各外部供出が供出されるべき予定時刻から、各外部投入を受け付ける投入時刻を求めて、前記作業プロセスの投入時刻のスケジュールを生成する方法において、第２発明に係る状態表現方法を用いて作成された、前記第１プロセス行列、前記第２プロセス行列、及び前記第３プロセス行列を記憶部に記憶するステップと、前記第１プロセス行列、前記第２プロセス行列、及び前記第３プロセス行列の各要素として記憶部に記憶している第２構造体に基づいて、前記予定時刻から各外部投入を受け付ける投入時刻を求めるための計算式を、該計算式に含まれる各項について該項には各作業工程の状態を示す複数のパラメータのうちどのパラメータが存在しているかを示す第２構造体を記憶部に記憶することで、演算部にて作成するステップと、前記予定時刻及び前記パラメータの夫々の値を取込部にて取り込むステップと、前記予定時刻及び前記パラメータの夫々の値を前記計算式に代入して、各外部投入を受け付ける投入時刻を演算部にて計算するステップとを含むことを特徴とする。
【００４６】
第４発明に係る状態表現方法は、複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を、演算部と記憶部と該記憶部へ情報を取り込む取込部とを備えたコンピュータを用いて表現する方法において、対応する要素を所定の値にすることで夫々の作業工程へ作業対象を渡す一又は複数の作業工程を指定した制約行列を、取込部にて取り込むステップと、対応する要素を所定の値にすることで前記作業プロセスの外部から投入される作業対象であるＭ個の外部投入の夫々を受け付ける作業工程を指定した投入行列を、取込部にて取り込むステップと、対応する要素を所定の値にすることで前記作業プロセスの外部へ供出される作業結果であるＰ個の外部供出の夫々を供出する作業工程を指定した供出行列を、取込部にて取り込むステップと、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存在数を示す配列、ｎ個の各作業工程におけるｋ番目及びｋ＋１番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存在数を示す配列、並びにＭ個のｋ＋１番目の外部投入を受け付ける投入時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存在数を示す配列を含む第１構造体を演算部にて生成するステップと、ｉ個目の作業工程に関連づけて、ｘｉ  （ｋ）及びｄｉ  （ｋ）に対応する成分が存在を示す値になった第１構造体を記憶部に記憶するステップと、ｉ個目の作業工程に対して作業対象を渡す他の作業工程が前記制約行列に指定されているか否かを演算部にて判定するステップと、ｉ個目の作業工程に対して作業対象を渡すｊ（ｊ＝１，２，…，ｎ）個目の作業工程が指定されていると判定された場合は、ｉ個目の作業工程に関連づけて、ｘｊ  （ｋ＋１）及びｄｊ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶部に記憶するステップと、ｉ個目の作業工程が、Ｍ個の外部投入のいずれかを受け付ける作業工程として前記投入行列に指定されているか否かを演算部にて判定するステップと、ｉ個目の作業工程がｍ個目の外部投入を受け付ける作業工程として指定されていると判定された場合は、ｉ個目の作業工程に関連づけて、ｕｍ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶部に記憶するステップと、各作業工程に関連づけて記憶している複数の第１構造体のうち、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があるか否かを演算部にて判定する判定ステップと、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があると判定された場合は、関連づけられている複数の第１構造体のｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）に対応する成分が存在数０を示す値になっているｉ個目の作業工程、及びｘｉ  （ｋ＋１）に対応する成分が存在数１以上を示す値になっているｊ個目の作業工程を演算部にて選択する選択ステップと、ｊ個目の作業工程に関連づけられた第１構造体のｘｉ  （ｋ＋１）に対応する成分以外の各成分の値をｉ個目の作業工程に関連づけられている複数の第１構造体の各成分に加えた新たな複数の第１構造体を、ｊ個目の作業工程に関連づけて記憶部に記憶する記憶ステップと、ｊ個目の作業工程に関連づけられたｘｉ  （ｋ＋１）の存在を示す第１構造体を記憶部から削除する削除ステップと、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体がないと演算部にて判定されるまで、前記判定ステップ、前記選択ステップ、前記記憶ステップ、及び前記削除ステップを演算部及び記憶部にて繰り返すステップと、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示す配列を含む第２構造体を演算部にて生成するステップと、前記作業プロセスの状態を示すｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を演算部にて生成するステップと、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶部に記憶するステップと、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶部に記憶するステップと、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶部に記憶するステップと、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶部に記憶するステップと、ｉ個目の作業工程が、Ｐ個の外部供出のいずれかを供出する作業工程として前記供出行列に指定されているか否かを演算部にて判定するステップと、ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていると判定された場合は、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分が存在を示す値になった第２構造体を記憶部に記憶するステップと、ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程とし���指定されていないと判定された場合は、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、第２構造体の数が０個であることを記憶部に記憶するステップと、を含むことを特徴とする。
【００４７】
第５発明に係るスケジュール生成方法は、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数により、Ｍ個の外部投入の夫々のｋ＋１，…，ｋ＋Ｎ番目を受け付ける投入時刻｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を求めて、前記作業プロセスの投入時刻のスケジュールを生成する方法であって、第４発明に係る状態表現方法を用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  を記憶部に記憶するステップと、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  、Ｂｋ＋１  及びＣｋ＋１  を演算部にて作成する作成ステップと、該作成ステップを演算部にて繰り返して、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を演算部にて作成するステップと、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）を内部に含む行列
【００４８】
【数３４】
2004240853.tif 000020
【００４９】
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、演算部にて作成するステップと、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を取込部にて取り込むステップと、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、演算部にて要素の値を−∞とするステップと、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、演算部にて要素の値とするステップと、｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を、
【００５０】
【数３５】
2004240853.tif 000021
【００５１】
と演算部にて計算するステップとを含むことを特徴とする。
【００５２】
第６発明に係るスケジュール生成方法は、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数により、Ｍ個の外部投入の夫々のｋ＋１番目を受け付ける投入時刻｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を求めて、前記作業プロセスの投入時刻のスケジュールを生成する方法であって、第４発明に係る状態表現方法を用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  を記憶部に記憶するステップと、前記第１プロセス行列Ａｋ  及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  及びＣｋ＋１  を演算部にて作成する作成ステップと、該作成ステップを演算部にて繰り返して、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を演算部にて作成するステップと、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）からなる行列
【００５３】
【数３６】
2004240853.tif 000022
【００５４】
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、演算部にて作成するステップと、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を取込部にて取り込むステップと、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、演算部にて要素の値を−∞とするステップと、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、演算部にて要素の値とするステップと、｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を、
【００５５】
【数３７】
2004240853.tif 000023
【００５６】
と演算部にて計算するステップとを含むことを特徴とする。
【００５７】
第７発明に係るスケジュール生成方法は、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の新たな値を取込部にて取り込むステップと、取り込んだ｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の新たな値を用いて、行列Γｋ  及びΔｋ’の各要素の値を演算部にて求めるステップと、求めた行列Γｋ  及びΔｋ’を用いて新たな｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を演算部にて計算するステップとを更に含むことを特徴とする。
【００５８】
第８発明に係る状態表現装置は、複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を表現する状態表現装置において、対応する要素を所定の値にすることで夫々の作業工程へ作業対象を渡す一又は複数の作業工程を指定した制約行列を受け付ける手段と、対応する要素を所定の値にすることで前記作業プロセスの外部から投入される作業対象であるＭ個の外部投入の夫々を受け付ける作業工程を指定した投入行列を受け付ける手段と、対応する要素を所定の値にすることで前記作業プロセスの外部へ供出される作業結果であるＰ個の外部供出の夫々を供出する作業工程を指定した供出行列を受け付ける手段と、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存在数を示す配列、ｎ個の各作業工程におけるｋ番目及びｋ＋１番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存在数を示す配列、並びにＭ個のｋ＋１番目の外部投入を受け付ける投入時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存在数を示す配列を含む第１構造体を生成する手段と、ｉ個目の作業工程に関連づけて、ｘｉ  （ｋ）及びｄｉ  （ｋ）に対応する成分が存在を示す値になった第１構造体を記憶する手段と、ｉ個目の作業工程に対して作業対象を渡す他の作業工程が前記制約行列に指定されているか否かを判定する手段と、ｉ個目の作業工程に対して作業対象を渡すｊ（ｊ＝１，２，…，ｎ）個目の作業工程が指定されていると判定された場合は、ｉ個目の作業工程に関連づけて、ｘｊ  （ｋ＋１）及びｄｊ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶する手段と、ｉ個目の作業工程が、Ｍ個の外部投入のいずれかを受け付ける作業工程として前記投入行列に指定されているか否かを判定する手段と、ｉ個目の作業工程がｍ個目の外部投入を受け付ける作業工程として指定されていると判定された場合は、ｉ個目の作業工程に関連づけて、ｕｍ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶する手段と、各作業工程に関連づけて記憶している複数の第１構造体のうち、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があるか否かを判定する判定手段と、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があると判定された場合は、関連づけられている複数の第１構造体のｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）に対応する成分が存在数０を示す値になっているｉ個目の作業工程、及びｘｉ  （ｋ＋１）に対応する成分が存在数１以上を示す値になって���るｊ個目の作業工程を選択する選択手段と、ｊ個目の作業工程に関連づけられた第１構造体のｘｉ  （ｋ＋１）に対応する成分以外の各成分の値をｉ個目の作業工程に関連づけられている複数の第１構造体の各成分に加えた新たな複数の第１構造体を、ｊ個目の作業工程に関連づけて記憶する記憶手段と、ｊ個目の作業工程に関連づけられたｘｉ  （ｋ＋１）の存在を示す第１構造体を削除する削除手段と、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体がないと前記判定手段によって判定されるまで、前記判定手段、前記選択手段、前記記憶手段、及び前記削除手段を繰り返し動作させる手段と、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示す配列を含む第２構造体を生成する手段と、前記作業プロセスの状態を示すｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を生成する手段と、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶する手段と、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶する手段と、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶する手段と、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶する手段と、ｉ個目の作業工程が、Ｐ個の外部供出のいずれかを供出する作業工程として前記供出行列に指定されているか否かを判定する手段と、ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていると判定された場合は、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分が存在を示す値になった第２構造体を記憶する手段と、ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていないと判定された場合は、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、第２構造体の数が０個であることを記憶する手段とを備えることを特徴とする。
【００５９】
第９発明に係るスケジュール生成装置は、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１，…，ｋ＋Ｎ番目を受け付ける投入時刻｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を求めて、前記作業プロセスの投入時刻のスケジュールを生成する装置であって、第８発明に係る状態表現装置を用いて作成された、前記第１プロセス行列Ａｋ  、前記の第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  を記憶する手段と、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  、Ｂｋ＋１  及びＣｋ＋１  を作成する作成手段と、該作成手段の動作を繰り返して、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成する手段と、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）を内部に含む行列
【００６０】
【数３８】
2004240853.tif 000024
【００６１】
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成する手段と、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付ける手段と、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞とする手段と、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とする手段と、｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を、
【００６２】
【数３９】
2004240853.tif 000025
【００６３】
と計算する手段とを備えることを特徴とする。
【００６４】
第１０発明に係るスケジュール生成装置は、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１番目を受け付ける投入時刻｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を求めて、前記作業プロセスの投入時刻のスケジュールを生成する装置であって、第８発明に係る状態表現装置を用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  を記憶する手段と、前記第１プロセス行列Ａｋ  及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  及びＣｋ＋１  を作成する作成手段と、該作成手段の動作を繰り返して、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成する手段と、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）からなる行列
【００６５】
【数４０】
2004240853.tif 000026
【００６６】
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成する手段と、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付ける手段と、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞とする手段と、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とする手段と、｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を、
【００６７】
【数４１】
2004240853.tif 000027
【００６８】
と計算する手段とを備えることを特徴とする。
【００６９】
第１１発明に係るスケジュール生成装置は、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の新たな値を受け付ける手段と、受け付けた｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の新たな値を用いて、行列Γｋ  及びΔｋ’の各要素の値を求める手段と、求めた行列Γｋ  及びΔｋ’を用いて新たな｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を計算する手段とを更に備えることを特徴とする。
【００７０】
第１２発明に係るコンピュータプログラムは、複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を、コンピュータに表現させるコンピュータプログラムにおいて、コンピュータに、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存在数を示す配列、ｎ個の各作業工程におけるｋ番目及びｋ＋１番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存在数を示す配列、並びにＭ個のｋ＋１番目の外部投入を受け付ける投入時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存在数を示す配列を含む第１構造体を生成させる手順と、コンピュータに、ｉ個目の作業工程に関連づけて、ｘｉ  （ｋ）及びｄｉ  （ｋ）に対応する成分が存在を示す値になった第１構造体を記憶させる手順と、コンピュータに、対応する要素を所定の値にすることで夫々の作業工程へ作業対象を渡す一又は複数の作業工程を指定した制約行列に、ｉ個目の作業工程に対して作業対象を渡す他の作業工程が指定されているか否かを判定させる手順と、ｉ個目の作業工程に対して作業対象を渡すｊ（ｊ＝１，２，…，ｎ）個目の作業工程が指定されていると判定された場合は、コンピュータに、ｉ個目の作業工程に関連づけて、ｘｊ  （ｋ＋１）及びｄｊ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶させる手順と、コンピュータに、対応する要素を所定の値にすることで前記作業プロセスの外部から投入される作業対象であるＭ個の外部投入の夫々を受け付ける作業工程を指定した投入行列に、ｉ個目の作業工程が、Ｍ個の外部投入のいずれかを受け付ける作業工程として指定されているか否かを判定させる手順と、ｉ個目の作業工程がｍ個目の外部投入を受け付ける作業工程として指定されていると判定された場合は、コンピュータに、ｉ個目の作業工程に関連づけて、ｕｍ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶させる手順と、コンピュータに、各作業工程に関連づけて記憶している複数の第１構造体のうち、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があるか否かを判定させる判定手順と、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があると判定された場合は、コンピュータに、関連づけられている複数の第１構造体のｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）に対応する成分が存在数０を示す値になっているｉ個目の作業工程、及びｘｉ  （ｋ＋１）に対応する成分が存在数１以上を示す値になっているｊ個目の作業工程を選択させる選択���順と、コンピュータに、ｊ個目の作業工程に関連づけられた第１構造体のｘｉ  （ｋ＋１）に対応する成分以外の各成分の値をｉ個目の作業工程に関連づけられている複数の第１構造体の各成分に加えた新たな複数の第１構造体を、ｊ個目の作業工程に関連づけて記憶させる記憶手順と、コンピュータに、ｊ個目の作業工程に関連づけられたｘｉ  （ｋ＋１）の存在を示す第１構造体を削除させる削除手順と、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体がないと前記判定手順にて判定されるまで、コンピュータに、前記判定手順、前記選択手順、前記記憶手順、及び前記削除手順を繰り返させる手順と、コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示す配列を含む第２構造体を生成させる手順と、コンピュータに、前記作業プロセスの状態を示すｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を生成させる手順と、コンピュータに、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶させる手順と、コンピュータに、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶させる手順と、コンピュータに、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶させる手順と、コンピュータに、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶させる手順と、コンピュータに、対応する要素を所定の値にすることで前記作業プロセスの外部へ供出される作業結果であるＰ個の外部供出の夫々を供出する作業工程を指定した供出行列に、ｉ個目の作業工程が、Ｐ個の外部供出のいずれかを供出する作業工程として指定されているか否かを判定させる手順と、ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていると判定された場合は、コンピュータに、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分が存在を示す値になった第２構造体を記憶させる手順と、ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていないと判定された場合は、コンピュータに、前記第３プロセス行列Ｃｋ  のｐ行��列目の要素として、第２構造体の数が０個であることを記憶させる手順と
を含むことを特徴とする。
【００７１】
第１３発明に係るコンピュータプログラムは、コンピュータに、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１，…，ｋ＋Ｎ番目を受け付ける投入時刻｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を求めさせて、前記作業プロセスの投入時刻のスケジュールを生成させるコンピュータプログラムであって、コンピュータに、第１２発明に係るコンピュータプログラムを用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  、Ｂｋ＋１  及びＣｋ＋１  を作成させる作成手順と、コンピュータに、該作成手順を繰り返させて、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成させる手順と、コンピュータに、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）を内部に含む行列
【００７２】
【数４２】
2004240853.tif 000028
【００７３】
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成させる手順と、コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付けさせる手順と、コンピュータに、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞にさせる手順と、コンピュータに、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とさせる手順と、コンピュータに、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を用いて、｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を、
【００７４】
【数４３】
2004240853.tif 000029
【００７５】
と計算させる手順とを含むことを特徴とする。
【００７６】
第１４発明に係るコンピュータプログラムは、コンピュータに、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１番目を受け付ける投入時刻｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を求めて前記作業プロセスのスケジュールを生成させるコンピュータプログラムであって、コンピュータに、第１２発明に係るコンピュータプログラムを用いて作成された前記第１プロセス行列Ａｋ  及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  及びＣｋ＋１  を作成させる作成手順と、コンピュータに、該作成手順を繰り返させて、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成させる手順と、コンピュータに、行列Ａｋ  ，Ａｋ＋１  ，…，Ａｋ＋Ｎ−１  、行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  、及び第１２発明に係るコンピュータプログラムを用いて作成された前記第２プロセス行列Ｂｋ  を用いて、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）からなる行列
【００７７】
【数４４】
2004240853.tif 000030
【００７８】
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成させる手順と、コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付けさせる手順と、コンピュータに、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞とさせる手順と、コンピュータに、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とさせる手順と、コンピュータに、｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を、
【００７９】
【数４５】
2004240853.tif 000031
【００８０】
と計算させる手順とを含むことを特徴とする。
【００８１】
第１５発明に係るコンピュータプログラムは、コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の新たな値を受け付けさせる手順と、コンピュータに、受け付けた｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の新たな値を用いて、行列Γｋ  及びΔｋ’の各要素の値を求めさせる手順と、コンピュータに、求めた行列Γｋ  及びΔｋ’を用いて新たな｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を計算させる手順とを更に含むことを特徴とする。
【００８２】
第１６発明に係るコンピュータでの読み取りが可能な記録媒体は、複数の作業工程からなる作業プロセスであり、一の作業工程は、該作業プロセスの外部から投入される作業対象、又は一若しくは複数の他の所定の作業工程から渡される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を、該作業プロセスの外部へ供出するか、又は一若しくは複数の更に他の所定の作業工程へ該作業工程の作業対象として渡す作業プロセスの状態を、コンピュータに表現させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存在数を示す配列、ｎ個の各作業工程におけるｋ番目及びｋ＋１番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存在数を示す配列、並びにＭ個のｋ＋１番目の外部投入を受け付ける投入時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存在数を示す配列を含む第１構造体を生成させる手順と、コンピュータに、ｉ個目の作業工程に関連づけて、ｘｉ  （ｋ）及びｄｉ  （ｋ）に対応する成分が存在を示す値になった第１構造体を記憶させる手順と、コンピュータに、対応する要素を所定の値にすることで夫々の作業工程へ作業対象を渡す一又は複数の作業工程を指定した制約行列に、ｉ個目の作業工程に対して作業対象を渡す他の作業工程が指定されているか否かを判定させる手順と、ｉ個目の作業工程に対して作業対象を渡すｊ（ｊ＝１，２，…，ｎ）個目の作業工程が指定されていると判定された場合は、コンピュータに、ｉ個目の作業工程に関連づけて、ｘｊ  （ｋ＋１）及びｄｊ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶させる手順と、コンピュータに、対応する要素を所定の値にすることで前記作業プロセスの外部から投入される作業対象であるＭ個の外部投入の夫々を受け付ける作業工程を指定した投入行列に、ｉ個目の作業工程が、Ｍ個の外部投入のいずれかを受け付ける作業工程として指定されているか否かを判定させる手順と、ｉ個目の作業工程がｍ個目の外部投入を受け付ける作業工程として指定されていると判定された場合は、コンピュータに、ｉ個目の作業工程に関連づけて、ｕｍ  （ｋ＋１）に対応する成分が存在を示す値になった新たな第１構造体を記憶させる手順と、コンピュータに、各作業工程に関連づけて記憶している複数の第１構造体のうち、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があるか否かを判定させる判定手順と、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体があると判定された場合は、コンピュータに、関連づけられている複数の第１構造体のｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）に対応する成分が存在数０を示す値になっているｉ個目の作業工程、及びｘｉ  （ｋ＋１）に対応す���成分が存在数１以上を示す値になっているｊ個目の作業工程を選択させる選択手順と、コンピュータに、ｊ個目の作業工程に関連づけられた第１構造体のｘｉ  （ｋ＋１）に対応する成分以外の各成分の値をｉ個目の作業工程に関連づけられている複数の第１構造体の各成分に加えた新たな複数の第１構造体を、ｊ個目の作業工程に関連づけて記憶させる記憶手順と、コンピュータに、ｊ個目の作業工程に関連づけられたｘｉ  （ｋ＋１）の存在を示す第１構造体を削除させる削除手順と、ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）のいずれかに対応する成分が存在数１以上を示す値である第１構造体がないと前記判定手順にて判定されるまで、コンピュータに、前記判定手順、前記選択手順、前記記憶手順、及び前記削除手順を繰り返させる手順と、コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示す配列を含む第２構造体を生成させる手順と、コンピュータに、前記作業プロセスの状態を示すｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を生成させる手順と、コンピュータに、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶させる手順と、コンピュータに、ｉ個目の作業工程に、ｘｊ  （ｋ）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶させる手順と、コンピュータに、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である一又は複数の第１構造体が関連づけられている場合は、一又は複数の前記第１構造体の｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶させる手順と、コンピュータに、ｉ個目の作業工程に、ｕｍ  （ｋ＋１）に対応する成分が存在数１以上を示す値である第１構造体が関連づけられていない場合は、前記第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶させる手順と、コンピュータに、対応する要素を所定の値にすることで前記作業プロセスの外部へ供出される作業結果であるＰ個の外部供出の夫々を供出する作業工程を指定した供出行列に、ｉ個目の作業工程が、Ｐ個の外部供出のいずれかを供出する作業工程として指定されているか否かを判定させる手順と、ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されていると判定された場合は、コンピュータに、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分が存在を示す値になった第２構造体を記憶させる手順と、ｉ個目の作業工程がｐ個目の外部供出を供出する作業工程として指定されてい���いと判定された場合は、コンピュータに、前記第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、第２構造体の数が０個であることを記憶させる手順とを含むコンピュータプログラムを記録してあることを特徴とする。
【００８３】
第１７発明に係るコンピュータでの読み取りが可能な記録媒体は、コンピュータに、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１，…，ｋ＋Ｎ番目を受け付ける投入時刻｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を求めさせて、前記作業プロセスの投入時刻のスケジュールを生成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体であって、コンピュータに、第１２発明に係るコンピュータプログラムを用いて作成された、前記第１プロセス行列Ａｋ  、前記第２プロセス行列Ｂｋ  、及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  、Ｂｋ＋１  及びＣｋ＋１  を作成させる作成手順と、コンピュータに、該作成手順を繰り返させて、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成させる手順と、コンピュータに、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）を内部に含む行列
【００８４】
【数４６】
2004240853.tif 000032
【００８５】
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成させる手順と、コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付けさせる手順と、コンピュータに、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞にさせる手順と、コンピュータに、行列Γｋ  及びΔｋ  の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とさせる手順と、コンピュータに、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を用いて、｛ｕｍ  （ｋ＋ｈ）：ｍ＝１，２，…，Ｍ；ｈ＝１，２，…，Ｎ｝を、
【００８６】
【数４７】
2004240853.tif 000033
【００８７】
と計算させる手順とを含むコンピュータプログラムを記録してあることを特徴とする。
【００８８】
第１８発明に係るコンピュータでの読み取りが可能な記録媒体は、コンピュータに、前記作業プロセスについて、ｎ個の各作業工程におけるｋ，ｋ＋１，…，ｋ＋Ｎ番目の作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｎ個の各作業工程におけるｋ番目の作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及びＰ個の外部供出の夫々のｋ＋１，…，ｋ＋Ｎ番目が供出されるべき予定時刻｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝とから、ｍａｘ−ｐｌｕｓ代数を用いて、Ｍ個の外部投入の夫々のｋ＋１番目を受け付ける投入時刻｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を求めて前記作業プロセスのスケジュールを生成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体であって、コンピュータに、第１２発明に係るコンピュータプログラムを用いて作成された前記第１プロセス行列Ａｋ  及び前記第３プロセス行列Ｃｋ  の各要素として記憶している一又は複数の第２構造体が含む各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を、ｋに１を加えた各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とした、新たな一又は複数の第２構造体を各要素として記憶した、行列Ａｋ＋１  及びＣｋ＋１  を作成させる作成手順と、コンピュータに、該作成手順を繰り返させて、行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を作成させる手順と、コンピュータに、行列Ａｋ  ，Ａｋ＋１  ，…，Ａｋ＋Ｎ−１  、行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  、及び第１２発明に係るコンピュータプログラムを用いて作成された前記第２プロセス行列Ｂｋ  を用いて、ｍａｘ−ｐｌｕｓ代数の乗算（丸に×）からなる行列
【００８９】
【数４８】
2004240853.tif 000034
【００９０】
を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成させる手順と、コンピュータに、｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付けさせる手順と、コンピュータに、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が０個である要素は、要素の値を−∞とさせる手順と、コンピュータに、行列Γｋ  及びΔｋ’の各要素の中で、要素として記憶している第２構造体の数が一又は複数である要素は、一の第２構造体で存在数を示されている｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝のいずれかの値の夫々に存在数を掛けて足し合わし、足し合わした値を一又は複数の第２構造体の夫々について比較した中で最も大きい値を、要素の値とさせる手順と、コンピュータに、｛ｕｍ  （ｋ＋１）：ｍ＝１，２，…，Ｍ｝を、
【００９１】
【数４９】
2004240853.tif 000035
【００９２】
と計算させる手順とを含むコンピュータプログラムを記録してあることを特徴とする。
【００９３】
第１発明においては、複数の作業工程からなる作業プロセスについてスケジュールを求めるために、作業結果を供出すべき予定時刻から、作業対象を投入する投入時刻を計算する計算式を、該計算式が含む複数のパラメータを未知変数のままで作成し、パラメータの値が得られたときに、計算式にパラメータの値を代入して投入時刻を計算する。
【００９４】
第２、第４、第８、第１２及び第１６発明においては、他の作業工程から作業対象を受け付ける作業工程を指定した制約行列、外部投入を受け付ける作業工程を指定した投入行列、外部供出を供出する作業工程を指定した供出行列を用いて作業プロセスの状態の入力を行い、制約行列および投入行列から情報を抽出して、各作業工程間の関係、各作業工程と各外部投入との関係、及び各作業工程と外部供出との関係を（５）式の例の如く各作業工程について表した式を、該式を構成する各項にどのパラメータが存在しているかを示す第１構造体を各作業工程に関連づけることで表現し、各作業工程に係る第１構造体および供出行列から情報を抽出して、作業プロセスの状態を示す（６）式に現れる第１プロセス行列Ａｋ  、第２プロセス行列Ｂｋ  、及び第３プロセス行列Ｃｋ  を、各プロセス行列の各要素を構成する各項にどのパラメータが存在しているかを示す第２構造体を用いて表現する。
【００９５】
第３、第５、第９、第１３及び第１７発明においては、ｍａｘ−ｐｌｕｓ代数の和算で結ばれた各項を各一の第２構造体で表して、第２構造体は各項にはｍａｘ−ｐｌｕｓ代数の乗算で結ばれたどのパラメータが存在しているかを示すことにより、（１３）式に現れる各行列の各要素を未知変数の組み合わせで表現しておき、パラメータの値が与えられたときに、与えられたパラメータの値を各行列の各要素に代入して、作業プロセスのスケジュールを計算する。
【００９６】
第６、第１０、第１４及び第１８発明においては、（１４）式に現れる各行列の各要素を未知変数の組み合わせで表現しておき、ｋ＋１〜ｋ＋Ｎ番目の作業に係るパラメータの値を（１４）式に代入して、ｋ＋１番目の作業に係るスケジュールを計算する。
【００９７】
第７、第１１及び第１５発明においては、スケジュールを計算した作業に続く次の作業について、該作業を新たなｋ＋１番目の作業としたｋ＋１〜ｋ＋Ｎ番目の作業に係る新たなパラメータを（１４）式に代入して、前記作業に係るスケジュールを計算する。
【００９８】
【発明の実施の形態】
以下本発明をその実施の形態を示す図面に基づき具体的に説明する。
図１は、本発明のスケジュール生成装置の構成を示すブロック図である。スケジュール生成装置１は、本発明の状態表現装置の機能を兼ね備えており、コンピュータを用いて構成され、演算を行うＣＰＵ（演算部）１１と、演算に伴って発生する一時的な情報を記憶するＲＡＭ（記憶部）１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備えており、ＣＤ−ＲＯＭ等の本発明に係る記録媒体２から本発明に係るコンピュータプログラム２０を外部記憶装置１３にて読み取り、読み取ったコンピュータプログラム２０を内部記憶装置１４に記憶し、ＲＡＭ１２にコンピュータプログラム２０をロードし、ＣＰＵ１１は、ロードしたコンピュータプログラム２０に基づいてスケジュール生成装置１に必要な処理を実行する。スケジュール生成装置１は、キーボード又はマウス等の入力装置（取込部）１５と、液晶ディスプレイ又はＣＲＴディスプレイ等の出力装置１６とを備えており、データの入力を初めとするオペレータからの操作を受け付ける構成となっている。
【００９９】
なお、スケジュール生成装置１は、図示しない通信インタフェースを備え、通信インタフェースに接続されている図示しない外部のサーバ装置から本発明に係るコンピュータプログラム２０をダウンロードし、ＣＰＵ１１にて処理を実行する形態であってもよい。
【０１００】
次に、本発明に係るｎ個の作業工程を機械Ｍ１，Ｍ２，Ｍ３とした、図２０に示した生産システム（作業プロセス）を例として、本発明の状態表現方法およびスケジュール生成方法を説明する。図２は、本発明のスケジュール生成装置１が行う処理の手順を示すフローチャートである。スケジュール生成装置１は、まず、入力装置１５にて、夫々の機械（作業工程）に対して部品を供給する（作業対象を渡す）他の機械を指定した制約行列ＤＸ、外部から部品が供給される（外部投入を受け付ける）機械を指定した投入行列ＤＹ、及び部品を完成させる（外部供出を供出する）機械を指定した供出行列ＤＺの、生産システムにおける各機械間の制約条件を示した条件データと、何ステップ先までのイベントカウンタにおける生産システムのパラメータを用いてスケジュールを計算するかを示すステップ数Ｎとを受け付ける（Ｓ１）。ここで、Ｎを大きくとった場合は、より未来の納期まで考慮してスケジュールを計算することになるため、納期遅れがより小さくなるスケジュールを計算できるが、Ｎが大きくなることによって計算量は大きくなるため、適宜の大きさのＮが定められる。
【０１０１】
図３は、制約行列ＤＸ、投入行列ＤＹ、及び供出行列ＤＺの構成を示す概念図である。制約行列ＤＸは、機械の数ｎに応じたｎ行ｎ列の行列であり、夫々の行は、部品を他の機械から供給される夫々の機械に対応し、夫々の列は、部品を他の機械へ供給する夫々の機械に対応している。ｉ個目の機械がｊ個目の機械から部品の供給を受け付ける場合は、制約行列ＤＸのｉ行ｊ列目の要素が１となり、そうでない場合は、０となる。図４は、制約行列ＤＸ、投入行列ＤＹ、及び供出行列ＤＺの例を示す概念図であり、図２０に示した生産システム例に対する制約行列ＤＸ、投入行列ＤＹ、及び供出行列ＤＺを示している。生産システム例では、機械の数が３であるために制約行列ＤＸは３行３列となり、機械Ｍ１及びＭ２は、共に他の機械から部品の供給を受けないので、制約行列ＤＸの１行目および２行目の要素は全て０となる。また、機械Ｍ３は、機械Ｍ１及びＭ２から部品の供給を受けるので、制約行列ＤＸの３行目は、１列目および２列目の要素が１となり、３列目の要素は０となる。投入行列ＤＹは、外部投入の数Ｍに応じたＭ行ｎ列の行列であり、夫々の行は、外部から供給される夫々の部品に対応し、夫々の列は、外部から部品を供給される夫々の機械に対応している。外部投入である外部から供給されるＭ個の部品のうち、ｍ個目の部品がｊ個目の機械へ供給される場合は、投入行列ＤＹのｍ行ｊ列目の要素が１となり、ｊ列目以外のｍ行目の要素は０となる。生産システム例では、外部投入の数すなわち外部から供給される部品の数が２であるために、投入行列ＤＹは２行３列となり、外部からの１個目の部品が機械Ｍ１に供給されるため、投入行列ＤＹの１行１列目の要素が１となり、１行２列目および３列目の要素が０となる。また、外部からの２個目の部品が機械Ｍ２に供給されるため、投入行列ＤＹの２行２列目の要素が１となり、２行１列目および３列目の要素が０となる。供出行列ＤＺは、外部供出の数Ｐに応じたＰ行ｎ列の行列であり、夫々の行は、機械の作業により完成する夫々の部品に対応し、夫々の列は、部品を完成させる夫々の機械に対応している。外部供出であるいずれかの機械で完成されるＰ個の部品のうち、ｐ個目の部品がｊ個目の機械で完成される場合は、供出行列ＤＺのｐ行ｊ列目の要素が１となり、ｊ列目以外のｐ行目の要素は０となる。生産システム例では、外部供出の数すなわち完成される部品の数が１であるために、供出行列ＤＺは１行３列となり、機械Ｍ３にて部品が完成するため、１行３列目の要素が１となり、他の要素は０となる。
【０１０２】
制約行列ＤＸ、投入行列ＤＹ、及び供出行列ＤＺは、オペレータの操作により、エディタ等を用いて記述され、入力装置１５から入力される。スケジュール生成装置１のＣＰＵ１１は、入力装置１５から制約行列ＤＸ、投入行列ＤＹ、及び供出行列ＤＺを受け付けて、ＲＡＭ１２又は内部記憶装置１４に記憶する。
【０１０３】
ＣＰＵ１１は、コンピュータプログラム２０をＲＡＭ１２にロードし、ロードしたコンピュータプログラム２０に従って、次に、生産システムの状態を、各機械におけるイベントカウンタｋ＋１の加工（ｋ＋１番目の作業）を開始する時刻ｘ（ｋ＋１）＝［ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）］Ｔ  についての以下の式
【０１０４】
【数５０】
2004240853.tif 000036
【０１０５】
に対応する形式で表現する第１状態表現処理を行う（Ｓ２）。（１５）式は、生産システムの状態を（６）式で表現する際の整理する前の段階の式である。
【０１０６】
図５及び図６は、ステップＳ２の第１状態表現処理のサブルーチンの手順を示すフローチャートである。ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、制約行列ＤＸの行数から機械の数ｎを決定し、投入行列ＤＹの行数から外部投入の数Ｍを決定し、供出行列ＤＺの行数から、外部供出の数Ｐを決定する（Ｓ２０１）。生産システム例の場合では、ｎ＝３，Ｍ＝２，Ｐ＝１となる。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、Ｎ，ｎ，Ｍを用いて、各機械間の関係を示した（１５）式を表現するために必要な第１構造体を生成する（Ｓ２０２）。
【０１０７】
図７は、第１構造体の構成を示す概念図である。第１構造体は、生産システムの状態を表した（５）式の如き式内にどのパラメータが存在しているかを示すために用いるデータであり、各機械でのイベントカウンタｋ，ｋ＋１，…，ｋ＋Ｎにおける作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示すＮ行ｎ列の２次元配列、各機械でのイベントカウンタｋ及びｋ＋１における作業を開始する時刻ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ），ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），…，ｘｎ  （ｋ＋１）の夫々の存否を示す２行ｎ列の２次元配列、並びにイベントカウンタｋ＋１における外部投入が行われる時刻ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）の夫々の存否を示す配列を含む。これらの配列の各成分の値は、各パラメータの存在数を示す数値が代入されることになっており、成分の値が０であるときは、該成分に対応するパラメータの非存在を示しており、ｍａｘ−ｐｌｕｓ代数におけるε（＝−∞）に対応する。また、いずれかのパラメータが一つ存在していることを示すときには、第１構造体の前記パラメータに対応する成分の値が１となる。更に、第１構造体は、ｍａｘ−ｐｌｕｓ代数におけるｅ（＝０）に対応する成分を含んでおり、該成分の値は、存在を示しているパラメータを含む項の係数を示している。前記成分の値が１である場合は、項の係数が１であることを示している。一つの第１構造体は、ｍａｘ−ｐｌｕｓ代数の乗算で結ばれている一つの項を表現しており、複数の第１構造体は、複数の項がｍａｘ−ｐｌｕｓ代数の和算で結ばれていることを表現している。例えば、ｘ１  （ｋ）とｄ１  （ｋ）とｄ１  （ｋ＋１）とがｍａｘ−ｐｌｕｓ代数の乗算で結ばれている場合は、ｘ１  （ｋ）とｄ１  （ｋ）とｄ１  （ｋ＋１）とに対応する成分が１となって他の成分が０である一の第１構造体で表現され、ｘ１  （ｋ）及びｄ１  （ｋ）がｍａｘ−ｐｌｕｓ代数の乗算で結ばれた項とｄ１  （ｋ＋１）とがｍａｘ−ｐｌｕｓ代数の和算で結ばれている場合は、ｘ１  （ｋ）及びｄ１  （ｋ）に対応する成分が１となって他の成分が０である第１構造体とｄ１  （ｋ＋１）に対応する成分が１となって他の成分が０である第１構造体とで表現される。また、ｅに対応する成分のみが１となって他の成分が０である場合は、第１構造体が表現する項はｅとなる。
【０１０８】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｉ＝１とし（Ｓ２０３）、ｉ個目の機械に関連づけて、即ち、ｘｉ  （ｋ＋１）について、ｘｉ  （ｋ）とｄｉ  （ｋ）とに対応する成分を１とした第１構造体を記憶する（Ｓ２０４）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｊ＝１とし（Ｓ２０５）、制約行列ＤＸのｉ行ｊ列目の要素であるＤＸｉｊの値が１であるか否かを判定し（Ｓ２０６）、ＤＸｉｊの値が１ではなく０である場合は（Ｓ２０６：ＮＯ）、処理をステップＳ２０８へ進め、ＤＸｉｊの値が１である場合は（Ｓ２０６：ＹＥＳ）、ｉ個目の機械に関連づけて、即ち、ｘｉ  （ｋ＋１）について、ｘｊ  （ｋ＋１）とｄｊ  （ｋ＋１）とに対応する成分を１とした第１構造体を記憶する（Ｓ２０７）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｊの値がｎであるか否かを判定し（Ｓ２０８）、ｊの値がｎではなくｎより小さい値である場合は（Ｓ２０８：ＮＯ）、ｊの値に１を加えてｊをインクリメントし（Ｓ２０９）、処理をステップＳ２０６へ戻す。
【０１０９】
ステップＳ２０８にてｊの値がｎであった場合は（Ｓ２０８：ＹＥＳ）、ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｍ＝１とし（Ｓ２１０）、投入行列ＤＹのｍ行ｉ列目の要素であるＤＹｍｉの値が１であるか否かを判定し（Ｓ２１１）、ＤＹｍｉの値が１ではなく０である場合は（Ｓ２１１：ＮＯ）、処理をステップＳ２１３へ進め、ＤＹｍｉの値が１である場合は（Ｓ２１１：ＹＥＳ）、ｉ個目の機械に関連づけて、即ち、ｘｉ  （ｋ＋１）について、ｕｍ  （ｋ＋１）に対応する成分を１とした第１構造体を記憶する（Ｓ２１２）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｍの値がＭであるか否かを判定し（Ｓ２１３）、ｍの値がＭではなくＭより小さい値である場合は（Ｓ２１３：ＮＯ）、ｍの値に１を加えてｍをインクリメントし（Ｓ２１４）、処理をステップＳ２１１へ戻す。ステップＳ２１３にてｍの値がＭであった場合は（Ｓ２１３：ＹＥＳ）、ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｉの値がｎであるか否かを判定し（Ｓ２１５）、ｉの値がｎではなくｎより小さい値である場合は（Ｓ２１５：ＮＯ）、ｉの値に１を加えてｉをインクリメントし（Ｓ２１６）、処理をステップＳ２０４へ戻し、ｉの値がｎであった場合は（Ｓ２１５：ＹＥＳ）、第１状態表現処理のサブルーチンの手順を終了して、処理をメインへ戻す。
【０１１０】
図８は、第１状態表現処理にて記憶される第１構造体の例を示す概念図であり、生産システム例の場合に記憶される第１構造体を示す。ｘ１  （ｋ＋１）については、ステップＳ２０４にてｘ１  （ｋ）とｄ１  （ｋ）とに対応する成分を１とした第１構造体が記憶され、この第１構造体は、（５）式の第１式の右辺第１項に対応する。また、ステップＳ２１０〜Ｓ２１４にてｕ１  （ｋ＋１）に対応する成分を１とした第１構造体が記憶され、この第１構造体は、（５）式の第１式の右辺第２項に対応する。ｘ１  （ｋ＋１）について記憶された２つの第１構造体により、（５）式の第１式が表現できる。ｘ２  （ｋ＋１）についても同様に、（５）式の第２式を表現する二つの第１構造体が記憶される。また、ｘ３  （ｋ＋１）については、ステップＳ２０４にてｘ１  （ｋ）とｄ１  （ｋ）とに対応する成分を１とした第１構造体が記憶され、ステップＳ２０５〜Ｓ２０９にて、ｘ３  （ｋ＋１）とｄ３  （ｋ＋１）とに対応する成分を１とした第１構造体、及びｘ２  （ｋ＋１）とｄ２  （ｋ＋１）とに対応する成分を１とした第１構造体が記憶され、３つの第１構造体により、（５）式の第３式が表現できる。
【０１１１】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、生産システムの状態を、（６）式に対応する形式で表現する第２状態表現処理を行う（Ｓ３）。図９は、ステップＳ３の第２状態表現処理のサブルーチンの手順を示すフローチャートである。ＣＰＵ１１は、ステップＳ２で記憶された複数の第１構造体の中に、ｘ（ｋ＋１）の成分のいずれかに対応する成分が１となった第１構造体があるか否かを判定し（Ｓ３１）、ｘ（ｋ＋１）の成分のいずれかに対応する成分が１となった第１構造体がない場合は（Ｓ３１：ＮＯ）、第２状態表現処理のサブルーチンの手順を終了して、処理をメインへ戻す。ｘ（ｋ＋１）の成分のいずれかに対応する成分が１となった第１構造体がある場合は（Ｓ３１：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｘｊ  （ｋ＋１）について記憶している第１構造体のｘｉ  （ｋ＋１）に対応する成分が１となっている、ｘｊ  （ｋ＋１）を選択し（Ｓ３２）、ｘｉ  （ｋ＋１）について記憶している第１構造体では、ｘ（ｋ＋１）の成分のいずれかに対応する成分が全て０になっているか否かを判定し（Ｓ３３）、全て０になっていない場合は（Ｓ３３：ＮＯ）、処理をステップＳ３２へ戻して更に他のｘｊ  （ｋ＋１）を選択する。ｘｉ  （ｋ＋１）について記憶している第１構造体でｘ（ｋ＋１）の成分のいずれかに対応する成分が全て０になっている場合は（Ｓ３３：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、選択しているｘｉ  （ｋ＋１）について記憶している、ｘｉ  （ｋ＋１）に対応する成分が１となっている第１構造体において、ｘｉ  （ｋ＋１）に対応する成分以外で１となっている成分の値を、ｘｉ  （ｋ＋１）について記憶している複数の第１構造体に写して、新たな複数の第１構造体を生成し、生成した新たな複数の第１構造体をｘｊ  （ｋ＋１）について記憶し（Ｓ３４）、ｘｊ  （ｋ＋１）について記憶してあるｘｉ  （ｋ＋１）に対応する成分が１となっている第１構造体を削除し（Ｓ３５）、処理をステップＳ３１へ戻す。
【０１１２】
図１０は、第２状態表現処理にて記憶される第１構造体の例を示す概念図であり、生産システム例の場合にｘ３  （ｋ＋１）について記憶される第１構造体を示す。ｘ１  （ｋ＋１）とｄ１  （ｋ＋１）とに対応する成分を１とした第１構造体が削除されて、ｘ１  （ｋ＋１）について記憶されているｘ１  （ｋ）とｄ１  （ｋ）とに対応する成分を１とした第１構造体及びｕ１  （ｋ＋１）に対応する成分を１とした第１構造体に、ｄ１  （ｋ＋１）に対応する成分の値１が写された、新たな二つの第１構造体が記憶され、更に、ｘ２  （ｋ＋１）とｄ２  （ｋ＋１）とに対応する成分を１とした第１構造体が削除されて、ｘ２  （ｋ＋１）について記憶されているｘ２  （ｋ）とｄ２  （ｋ）とに対応する成分を１とした第１構造体及びｕ２  （ｋ＋１）に対応する成分を１とした第１構造体に、ｄ２  （ｋ＋１）に対応する成分の値１が写された、新たな二つの第１構造体が記憶される。ｘ１  （ｋ＋１）及びｘ２  （ｋ＋１）について記憶されている夫々の第１構造体は、第２状態表現処理では変更がない。
【０１１３】
以上までの処理で、ｘ（ｋ＋１）についての式で生産システムの状態が表現され、ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、生産システムの状態を表現するプロセス行列を生成する処理を行う（Ｓ４）。図１１、図１２及び図１３は、ステップＳ４のプロセス行列生成処理のサブルーチンの手順を示すフローチャートである。ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｎ，Ｍ，Ｐを用いて、生産システムの状態を表現するｎ×ｎの第１プロセス行列Ａｋ  、ｎ×Ｍの第２プロセス行列Ｂｋ  、及びＰ×ｎの第３プロセス行列Ｃｋ  を生成し（Ｓ４０１）、各プロセス行列を表現するために必要な第２構造体を生成する（Ｓ４０２）。図１４は、第２構造体の構成を示す概念図である。第２構造体は、各プロセス行列の各要素にどのパラメータが存在しているかを示すために用いるデータであり、ｅ（＝０）に対応する成分と、各機械でのイベントカウンタｋ，ｋ＋１，…，ｋ＋Ｎにおける作業に必要な作業時間｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々の存否を示すＮ行ｎ列の２次元配列を含む。
【０１１４】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｉ＝１とし（Ｓ４０３）、ｊ＝１とし（Ｓ４０４）、ｉ個目の機械に関連づけて即ちｘｉ  （ｋ＋１）について記憶している第１構造体の中に、ｘｊ  （ｋ）に対応する成分の値が１以上である一又は複数の第１構造体があるか否かを判定し（Ｓ４０５）、ｘｊ  （ｋ）に対応する成分の値が１以上である一又は複数の第１構造体がある場合は（Ｓ４０５：ＹＥＳ）、一又は複数の前記第１構造体における｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として記憶し（Ｓ４０６）、ｘｊ  （ｋ）に対応する成分の値が１以上である第１構造体がない場合は（Ｓ４０５：ＮＯ）、第１プロセス行列Ａｋ  のｉ行ｊ列目の要素として、第２構造体の数が０個であることを記憶する（Ｓ４０７）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｊの値がｎであるか否かを判定し（Ｓ４０８）、ｊの値がｎではなくｎより小さい値である場合は（Ｓ４０８：ＮＯ）、ｊの値に１を加えてｊをインクリメントし（Ｓ４０９）、処理をステップＳ４０５へ戻す。
【０１１５】
ステップＳ４０８にてｊの値がｎであった場合は（Ｓ４０８：ＹＥＳ）、ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｍ＝１とし（Ｓ４１０）、ｉ個目の機械に関連づけて即ちｘｉ  （ｋ＋１）について記憶している第１構造体の中に、ｕｍ  （ｋ＋１）に対応する成分の値が１以上である一又は複数の第１構造体があるか否かを判定し（Ｓ４１１）、ｕｍ  （ｋ＋１）に対応する成分の値が１以上である一又は複数の第１構造体がある場合は（Ｓ４１１：ＹＥＳ）、一又は複数の前記第１構造体における｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝の夫々に対応する成分の値を写した一又は複数の第２構造体を、第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として記憶し（Ｓ４１２）、ｕｍ  （ｋ＋１）に対応する成分の値が１以上である第１構造体がない場合は（Ｓ４１１：ＮＯ）、第２プロセス行列Ｂｋ  のｉ行ｍ列目の要素として、第２構造体の数が０個であることを記憶する（Ｓ４１３）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｍの値がＭであるか否かを判定し（Ｓ４１４）、ｍの値がＭではなくＭより小さい値である場合は（Ｓ４１４：ＮＯ）、ｍの値に１を加えてｍをインクリメントし（Ｓ４１５）、処理をステップＳ４１１へ戻す。
【０１１６】
ステップＳ４１４にてｍの値がＭであった場合は（Ｓ４１４：ＹＥＳ）、ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｐ＝１とし（Ｓ４１６）、供出行列ＤＺのｐ行ｉ列目の要素であるＤＺｐｉの値が１であるか否かを判定し（Ｓ４１７）、ＤＺｐｉの値が１である場合は（Ｓ４１７：ＹＥＳ）、第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、ｄｉ  （ｋ）に対応する成分を１とした第２構造体を記憶し（Ｓ４１８）、ＤＺｐｉの値が１ではなく０である場合は（Ｓ４１７：ＮＯ）、第３プロセス行列Ｃｋ  のｐ行ｉ列目の要素として、第２構造体の数が０個であることを記憶する（Ｓ４１９）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｐの値がＰであるか否かを判定し（Ｓ４２０）、ｐの値がＰではなくＰより小さい値である場合は（Ｓ４２０：ＮＯ）、ｐの値に１を加えてｐをインクリメントし（Ｓ４２１）、処理をステップＳ４１７へ戻す。ステップＳ４２０にてｐの値がＰであった場合は（Ｓ４２０：ＹＥＳ）、ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｉの値がｎであるか否かを判定し（Ｓ４２２）、ｉの値がｎではなくｎより小さい値である場合は（Ｓ４２２：ＮＯ）、ｉの値に１を加えてｉをインクリメントし（Ｓ４２３）、処理をステップＳ４０４へ戻し、ｉの値がｎであった場合は（Ｓ４２２：ＹＥＳ）、プロセス行列生成処理のサブルーチンの手順を終了して、処理をメインへ戻す。
【０１１７】
図１５は、プロセス行列生成処理にて生成されるプロセス行列の例を示す概念図であり、生産システム例の場合に生成されるプロセス行列を示す。ｘ１  （ｋ＋１），ｘ２  （ｋ＋１），ｘ３  （ｋ＋１）の夫々について記憶されている第１構造体に応じて、各プロセス行列の各要素として夫々０個または１個の第２構造体が記憶される。例えば、第１プロセス行列Ａｋ  の３行１列目の要素として、ｘ３  （ｋ＋１）について記憶されているｘ１  （ｋ）とｄ１  （ｋ）とｄ１  （ｋ＋１）とに対応する成分が１となっている第１構造体に応じて、ｄ１  （ｋ）とｄ１  （ｋ＋１）とに対応する成分が１となった第２構造体が記憶されており、該要素がｄ１  （ｋ）とｄ１  （ｋ＋１）とがｍａｘ−ｐｌｕｓ代数の乗算で結ばれた項であることを表現している。また、第２構造体の数が０個であることが記憶されている要素は、該要素の値がεであることを表現している。また、第２プロセス行列Ｂｋ  の１行１列目および２行２列目の要素は、ｅに対応する成分のみが１となっており、該要素の値がｅであることを表現している。
【０１１８】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、生成した各プロセス行列を用いて、生産システムのスケジュールを生成するために計算すべき（１３）式に対応する計算式が含む行列を生成する計算式行列生成処理を行う（Ｓ５）。ここで、計算すべき計算式は、（１３）式および（１４）式により、ｘ（ｋ）＝［ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）］Ｔ  と、ｕ（ｋ＋１）＝［ｕ１  （ｋ＋１），ｕ２  （ｋ＋１），…，ｕＭ  （ｋ＋１）］Ｔ  と、ｋ＋ｈ番目のステップにおいてＰ個の外部供出の夫々が供出されるべき納期である予定時刻をｒ（ｋ＋ｈ）＝［ｒ１  （ｋ＋ｈ），ｒ２  （ｋ＋ｈ），…，ｒＰ  （ｋ＋ｈ）］としたときの、ｋ＋１〜ｋ＋Ｎ番目のステップにおけるＰ個の外部供出の夫々の納期Ｒ（ｋ＋１）＝［ｒ（ｋ＋１），ｒ（ｋ＋２），…，ｒ（ｋ＋Ｎ）］Ｔ  とを用いた以下の式となる。
【０１１９】
【数５１】
2004240853.tif 000037
【０１２０】
図１６は、ステップＳ５の計算式行列生成処理のサブルーチンの手順を示すフローチャートである。ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、第１プロセス行列Ａｋ  及び第３プロセス行列Ｃｋ  の各要素として記憶している第２構造体の各ｄｇ  （ｋ＋ｈ）に対応する各成分の値を各ｄｇ  （ｋ＋ｈ＋１）に対応する各成分の値とすることにより、各成分の値をずらした第２構造体を行列Ａｋ＋１  及び行列Ｃｋ＋１  の各要素として記憶して、行列Ａｋ＋１  及び行列Ｃｋ＋１  を作成する（Ｓ５１）。このとき記憶される第２構造体のｄ１  （ｋ），ｄ２  （ｋ），…，ｄｎ  （ｋ）に対応する成分の値には、０が代入される。図１７は、作成された行列Ａｋ＋１  及び行列Ｃｋ＋１  の例を示す概念図であり、生産システム例の場合に作成された行列Ａｋ＋１  及び行列Ｃｋ＋１  を示す。行列Ａｋ＋１  では、例えば、第１プロセス行列Ａｋ  の３行１列目の要素として記憶しているｄ１  （ｋ）及びｄ１  （ｋ＋１）に対応する成分が１となった第２構造体に応じて、３行１列目の要素としてｄ１  （ｋ＋１）及びｄ１  （ｋ＋２）に対応する成分が１となった第２構造体を記憶している。
【０１２１】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、同様に各成分の値をずらした第２構造体を各要素として記憶することにより、行列Ａｋ＋２  ，Ａｋ＋３  ，…，Ａｋ＋Ｎ−１  及び行列Ｃｋ＋２  ，Ｃｋ＋３  ，…，Ｃｋ＋Ｎ  を作成し（Ｓ５２）、（１６）式に含まれる行列Γｋ  を、Ｈ行Ｉ列の行列ＬとＩ行Ｊ列の行列Ｏとの乗算によりなる行列Ｑのｈ（ｈ＝１，２，…，Ｈ）行ｊ（ｊ＝１，２，…，Ｊ）列目の要素Ｑｈｊとして、行列Ｌのｈ行ｉ（ｉ＝１，２，…，Ｉ）列目の要素として記憶しているａｈｉ個の第２構造体の夫々の各成分の値を行列Ｏのｉ行ｊ列目の要素として記憶しているｂｉｊ個の第２構造体の夫々の各成分の値に加えたａｈｉ×ｂｉｊ個の第２構造体を全てのｉについて作成した（ａｈ１×ｂ１ｊ＋ａｈ２×ｂ２ｊ＋…＋ａｈＩ×ｂＩｊ）個の第２構造体を記憶することにより、作成する（Ｓ５３）。このとき、行列Ｑのｈ行ｉ列目の要素または行列Ｏのｉ行ｊ列目の要素として記憶している第２構造体の数が０である場合は、作成される第２構造体の数は０個であり、行列Γｋ  のｈ行ｊ列目の要素として作成される第２構造体の数が０個である場合は、行列Γｋ  のｈ行ｊ列目の要素として、第２構造体の数が０個であることを記憶する。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、（１６）に含まれる行列Δｋ’を同様に作成し（Ｓ５４）、計算式行列生成処理のサブルーチンを終了して処理をメインへ戻す。
【０１２２】
図１８は、計算式行列生成処理にて生成される計算式行列の例を示す概念図であり、生産システム例の場合に生成される行列Γｋ  及びΔｋ’を示す。行列Ａｋ  ，Ａｋ＋１  ，…，Ａｋ＋Ｎ−１  、行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  、及び第２プロセス行列Ｂｋ  の各要素として記憶している第２構造体に応じて、Ｎ行３列の行列Γｋ  、及びＮ行２列の行列Δｋ’の各要素として夫々一又は複数の第２構造体が記憶される。
【０１２３】
ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、作業プロセスのスケジュールを計算する計算処理を行う（Ｓ６）。図１９は、ステップＳ６の計算処理のサブルーチンの手順を示すフローチャートである。スケジュール生成装置１は、入力装置１５にて、スケジュールを計算すべき計算ステップ数Ｔを受け付け（Ｓ６１）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、計算ステップｔをｔ＝１とする（Ｓ６２）。ここで、計算ステップ数Ｔは、生産システムへ外部からＭ個の部品が実際に何回供給されるかに対応する。スケジュール生成装置１は、次に、入力装置１５にて、計算に必要なパラメータの値、即ち｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付け（Ｓ６３）、ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、受け付けたパラメータの値を（１６）式に代入する（Ｓ６４）。このとき、行列Γｋ  及びΔｋ’の各要素の中で、第２構造体の数が０個であることを記憶している要素は、該要素の値をεにする。また、行列Γｋ  及びΔｋ’の各要素の中で、一又は複数の第２構造体を記憶している要素は、一の第２構造体に存在数が示されているｄｇ  （ｋ＋ｈ）の値または計数の値を存在数を掛けた後で互いに足し合わし、足し合わした値が複数の第２構造体の中で最も大きい値を、要素の値とする。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、（３）式の如く規定されているｍａｘ−ｐｌｕｓ代数の行列の計算方法に従って、値を代入した（１６）式により、ｋ＋１番目の部品の完成時刻が納期どおりか、又は納期に遅れない範囲で最も遅くなるようなＭ個の部品の投入時刻ｕ（ｋ＋１）を計算する（Ｓ６５）。ＣＰＵ１１は、次に、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、ｔの値がＴであるか否かを判定し（Ｓ６６）、ｔの値がＴでなかった場合は（Ｓ６６：ＮＯ）、ｔの値をインクリメントし（Ｓ６７）、入力装置１５にて、次のステップにおける投入時刻ｕ（ｋ＋１）を計算するために必要な新たなパラメータの値、即ち新たに定められた｛ｄｇ  （ｋ＋ｈ）：ｇ＝１，２，…，ｎ；ｈ＝０，１，…，Ｎ｝、ｘ１  （ｋ），ｘ２  （ｋ），…，ｘｎ  （ｋ）、及び｛ｒｐ  （ｋ＋ｈ）：ｐ＝１，２，…，Ｐ；ｈ＝１，２，…，Ｎ｝の夫々の値を受け付け（Ｓ６８）、処理をステップＳ６４へ戻して、次のステップにおける投入時刻ｕ（ｋ＋１）を計算する。ステップＳ６６にて、ｔの値がＴであった場合は（Ｓ６６：ＹＥＳ）、ＣＰＵ１１は、ＲＡＭ１２にロードしたコンピュータプログラム２０に従って、計算処理のサブルーチンを終了して処理をメインへ戻し、メインの処理を終了する。
【０１２４】
以上の処理によって、本発明のスケジュール生成装置１は、Ｎステップ先までの生産システムの状態と納期とから、部品の適切な投入時刻を求め、生産システムのスケジュールを生成する。以上詳述した如く、本発明においては、夫々の機械について部品を受け取る他の機械を指定した制約行列、外部投入を受け付ける機械を指定した投入行列、外部供出を供出する機械を指定した供出行列を用いて作業プロセスの状態の入力を行い、制約行列、投入行列および供出行列から情報を抽出して、作業プロセスの状態を表現する第１プロセス行列Ａｋ  、第２プロセス行列Ｂｋ  、及び第３プロセス行列Ｃｋ  を作成するため、手作業で作業プロセスを表現する式を作成する必要がなくなり、複雑な作業プロセスについても容易に状態を表現することができる。
【０１２５】
また、本発明においては、スケジュールを計算するための計算式である（１６）式を立式するために、各機械に関して作業プロセスの状態を表現する各式および作業プロセスの状態を表現する各行列の各要素を、ｍａｘ−ｐｌｕｓ代数の和算で結ばれた各項を各一の構造体で表して、構造体は各項にはｍａｘ−ｐｌｕｓ代数の乗算で結ばれたどのパラメータが存在しているかを示すことによって表現することにより、実際のパラメータの値を代入してスケジュールを計算するための（１６）式に含まれる各行列の各要素を未知変数の組み合わせで表現する。実際のパラメータの値を用いた数値計算ではなく、パラメータの値を未知変数のままにしておいて（１６）式を立式するため、パラメータの値が変化した場合でも、変化したパラメータの値を（１６）式に代入することでスケジュールの計算が可能であり、従来の数値計算の場合は必要であった（１６）式の立式の段階からの再計算が不必要となり、計算の効率が向上して計算時間を短縮することができる。
【０１２６】
更に、本発明においては、現在の作業プロセスの内部状態とＮステップ先までの作業プロセスの状態および納期とを示すパラメータから、作業の１ステップにおけるスケジュールを計算することにより、未来のスケジュールを考慮にいれて納期の遅れをより小さくする計算が行われて、適切なスケジュールが計算される。また、次にパラメータを更新し、更新されたパラメータを用いて更に次の１ステップにおけるスケジュールの計算を行うことにより、機械の故障または納期の変更など作業プロセスの状態に変化が発生した場合でも、作業プロセスの状態に応じた適切なスケジュールを計算することができる。
【０１２７】
なお、本実施の形態においては、（１６）式に基づいてスケジュールを計算する方法を示したが、これに限るものではなく、各プロセス行列の各要素として記憶している第２構造体の各成分の値をずらすことにより行列Ａｋ＋１  ，Ａｋ＋２  ，…，Ａｋ＋Ｎ−１  、行列Ｂｋ＋１  ，Ｂｋ＋２  ，…，Ｂｋ＋Ｎ−１  及び行列Ｃｋ＋１  ，Ｃｋ＋２  ，…，Ｃｋ＋Ｎ  を計算し、（１３）式に含まれる各行列を計算して、受け付けたパラメータを（１３）式に代入してイベントカウンタがｋ＋１〜ｋ＋Ｎとなる各ステップのスケジュールをまとめて計算する方法を用いてもよい。また、本実施の形態においては、生産システムの状態の表現とスケジュールの計算とを続けて行う方法を示したが、生産システムの状態が既に表現されている場合には、表現された状態を用いてスケジュールの計算を最初から行う方法を用いてもよい。また、本実施の形態においては、スケジュールの計算を行う計算ステップ数をＴとして有限回で計算を終了する方法を示したが、計算ステップ数を無限回として無限にスケジュールの計算を繰り返す方法を用いてもよい。
【０１２８】
また、本実施の形態においては、本発明に係る取込部としてマウス又はキーボード等の入力装置１５を用いる形態を示したが、これに限るものではなく、本発明に係る取込部として、スケジュール生成装置１の内部に含むデータベース、又は図示しない通信インタフェースを介して接続されたスケジュール生成装置１外部のデータベースから、必要な情報をＲＡＭ１２へ読み込む手段を用いる形態であってもよい。また、本実施の形態においては、本発明のスケジュール生成装置１は、本発明の状態表現装置の機能を兼ね備えている形態を示したが、これに限るものではなく、スケジュール生成装置１及び状態表現装置を夫々別のコンピュータにて構成し、互いにデータを入出力して計算を行う形態としてもよい。
【０１２９】
更に、本実施の形態においては、本発明に係る作業プロセスとして、生産システムを例として説明したが、一の輸送工程を一の作業工程に対応させた物流システム等、他の作業プロセスについても本発明を適用できることは勿論である。
【０１３０】
【発明の効果】
第１、第３、第５、第９、第１３及び第１７発明においては、実際のパラメータの値を用いた数値計算ではなく、スケジュールを計算するための式に含まれる各行列の各要素を未知変数の組み合わせで表現しておき、式に実際のパラメータの値を代入してスケジュールを計算するため、パラメータの値が変化した場合でも、変化したパラメータの値を前記式に代入することでスケジュールの計算が可能であり、従来の数値計算の場合は必要であった最初からの再計算が不必要となり、計算の効率が向上して計算時間を短縮することができる。
【０１３１】
第２、第４、第８、第１２及び第１６発明においては、制約行列、投入行列および供出行列を用いて作業プロセスの状態の入力を行い、各行列から情報を抽出して、作業プロセスの状態を表現するため、手作業で作業プロセスを表現する式を作成する必要がなくなり、複雑な作業プロセスについても容易に状態を表現することができる。
【０１３２】
第６、第１０、第１４及び第１８発明においては、未来の作業のスケジュールに係るパラメータを用いて、作業の１ステップに係るスケジュールを計算するため、未来のスケジュールを考慮にいれて納期の遅れをより小さくする計算が行われて、適切なスケジュールが計算される。
【０１３３】
第７、第１１及び第１５発明においては、スケジュールを計算した作業に続く次の作業の１ステップについて、パラメータを更新し、更新したパラメータを用いてスケジュールを計算し、各作業のステップについてスケジュールの計算を繰り返すことにより、機械の故障または納期の変更など作業プロセスの状態に変化が発生した場合でも、作業プロセスの状態に応じた適切なスケジュールを計算することができる等、本発明は優れた効果を奏する。
【図面の簡単な説明】
【図１】本発明のスケジュール生成装置の構成を示すブロック図である。
【図２】本発明のスケジュール生成装置が行う処理の手順を示すフローチャートである。
【図３】制約行列ＤＸ、投入行列ＤＹ、及び供出行列ＤＺの構成を示す概念図である。
【図４】制約行列ＤＸ、投入行列ＤＹ、及び供出行列ＤＺの例を示す概念図である。
【図５】ステップＳ２の第１状態表現処理のサブルーチンの手順を示すフローチャートである。
【図６】ステップＳ２の第１状態表現処理のサブルーチンの手順を示すフローチャートである。
【図７】第１構造体の構成を示す概念図である。
【図８】第１状態表現処理にて記憶される第１構造体の例を示す概念図である。
【図９】ステップＳ３の第２状態表現処理のサブルーチンの手順を示すフローチャートである。
【図１０】第２状態表現処理にて記憶される第１構造体の例を示す概念図である。
【図１１】ステップＳ４のプロセス行列生成処理のサブルーチンの手順を示すフローチャートである。
【図１２】ステップＳ４のプロセス行列生成処理のサブルーチンの手順を示すフローチャートである。
【図１３】ステップＳ４のプロセス行列生成処理のサブルーチンの手順を示すフローチャートである。
【図１４】第２構造体の構成を示す概念図である。
【図１５】プロセス行列生成処理にて生成されるプロセス行列の例を示す概念図である。
【図１６】ステップＳ５の計算式行列生成処理のサブルーチンの手順を示すフローチャートである。
【図１７】作成された行列Ａｋ＋１  及び行列Ｃｋ＋１  の例を示す概念図である。
【図１８】計算式行列生成処理にて生成される計算式行列の例を示す概念図である。
【図１９】ステップＳ６の計算処理のサブルーチンの手順を示すフローチャートである。
【図２０】作業プロセスとしての生産システムの例を示す模式図である。
【符号の説明】
１  スケジュール生成装置（状態表現装置）
１１  ＣＰＵ（演算部）
１２  ＲＡＭ（記憶部）
１５  入力装置（取込部）
２  記録媒体
２０  コンピュータプログラム
ＤＸ  制約行列
ＤＹ  投入行列
ＤＺ  供出行列
Ａｋ      第１プロセス行列
Ｂｋ      第２プロセス行列
Ｃｋ      第３プロセス行列
【図１】
2004240853.tif 000054
【図２】
2004240853.tif 000055
【図３】
2004240853.tif 000056
【図４】
2004240853.tif 000057
【図５】
2004240853.tif 000058
【図６】
2004240853.tif 000059
【図７】
2004240853.tif 000060
【図８】
2004240853.tif 000061
【図９】
2004240853.tif 000062
【図１０】
2004240853.tif 000063
【図１１】
2004240853.tif 000064
【図１２】
2004240853.tif 000065
【図１３】
2004240853.tif 000066
【図１４】
2004240853.tif 000067
【図１５】
2004240853.tif 000068
【図１６】
2004240853.tif 000069
【図１７】
2004240853.tif 000070
【図１８】
2004240853.tif 000071
【図１９】
2004240853.tif 000072
【図２０】
2004240853.tif 000073