(57)【要約】【課題】より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に対してクリティカルチェーン法を適用可能とし、処理時間の不確定性が高い場合にも納期遅れを出さず、かつ納期短縮を図り得るスケジュール作成方法、スケジュール作成装置及びコンピュータプログラムを提供する。【解決手段】例えばシステムの稼動中にクリティカルチェーン法を適用して計画期間の短縮を図る場合でも、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を利用して、当該クリティカルチェーン法を適用した際に用いるＰＢ及びＦＢの位置及び値を簡単に取得することができる。従って、より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に対してクリティカルチェーン法を適用可能とし、処理時間の不確定性が高い場合にも納期遅れを出さず、かつ納期短縮を図り得る。【選択図】図２
2010198339.tif 000002
【特許請求の範囲】
【請求項１】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数１４１〜数１４４で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である。ｋはｋ番目の前記処理対象の工程処理であることを表す。）と、
【数１４１】
2010198339.tif 000147
【数１４２】
2010198339.tif 000148
【数１４３】
2010198339.tif 000149
【数１４４】
2010198339.tif 000150
前記行列Ｆを基に前記max-plus代数の定理を利用した次の数１４５から算出された行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【数１４５】
2010198339.tif 000151
を用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記各工程の実行時間を短縮したことによる遅れを防止するための猶予時間であるプロジェクトバッファの設置位置を決定すると共に、前記プロジェクトバッファの値を算出するプロジェクトバッファ算出ステップと、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数１４６でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）を算出し、該行列υ，ｗ´と前記行列Ｆｋとを用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記非クリティカルパス上の工程による遅れを防止するための猶予時間であるフィーデングバッファの設置位置を決定すると共に、前記フィーデングバッファの値を算出するフィーデングバッファ算出ステップと、
【数１４６】
2010198339.tif 000152
を実行することを特徴とするスケジュール作成方法。
【請求項２】
前記プロジェクトバッファ算出ステップは、
行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥ（ｋ）を、前記演算部が取得し、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数１４７に基づき前記プロジェクトバッファの値を前記演算部で算出する
【数１４７】
2010198339.tif 000153
（ＰＢは前記プロジェクトバッファを表し、ｑは任意の数字。丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
ことを特徴とする請求項１記載のスケジュール作成方法。
【請求項３】
前記最早終了時刻ｙＥ（ｋ）は、前記行列Ｃ０ｋと最早開始時刻ｘＥ（ｋ）とを用いて、前記演算部によって次の数１４８により算出され、
【数１４８】
2010198339.tif 000154
前記最早開始時刻ｘＥ（ｋ）は、ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び前記入力時刻ｕ（ｋ）とを利用し、前記演算部によって次の数１４９に基づき算出される
【数１４９】
2010198339.tif 000155
ことを特徴とする請求項２記載のスケジュール作成方法。
【請求項４】
前記プロジェクトバッファ算出ステップは、
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した前記工程ｊを決定し、該工程ｊの次工程が前記プロジェクトバッファの設置位置であると、前記演算部によって決定する
ことを特徴とする請求項１〜３うちいずれか１項記載のスケジュール作成方法。
【請求項５】
前記フィーデングバッファ算出ステップは、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数１５０に基づき行列Ｆβαを前記演算部で算出する第１のステップと、
【数１５０】
2010198339.tif 000156
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数１５１により行列υ´を前記演算部で算出する第２のステップと
【数１５１】
2010198339.tif 000157
を実行することを特徴とする請求項１〜４のうちいずれか１項記載のスケジュール作成方法。
【請求項６】
前記第２のステップの後に、
前記行列υと前記行列Ｆｋとを用い前記max-plus代数の定理を利用した次の数１５２により行列Ｆββを算出し、前記行列υ´と前記行列Ｆββとを用い前記max-plus代数の定理を利用した次の数１５３に基づいて行列ｐを前記演算部で算出する第３のステップと、
【数１５２】
2010198339.tif 000158
【数１５３】
2010198339.tif 000159
前記行列ｐの要素を次の数１５４の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数１５５を基に行列Ｆ〜ββを算出し、前記行列Ｆ〜ββを基に前記max-plus代数の定理を利用した次の数１５６から行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を前記演算部で算出する第４のステップと、
【数１５４】
2010198339.tif 000160
【数１５５】
2010198339.tif 000161
【数１５６】
2010198339.tif 000162
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用した次の数１５７により前記フィーデングバッファの値を抽出した行列ＦＢを、前記演算部で算出する第５のステップと
【数１５７】
2010198339.tif 000163
（ｑは任意の数字）
を実行することを特徴とする請求項５記載のスケジュール作成方法。
【請求項７】
前記各工程の実行時間を１／ｑに短縮した短縮実行時間を前記演算部で算出する実行時間短縮ステップを備え、
前記入力パラメータに前記プロジェクトバッファの値と前記フィーデングバッファの値とを追加し、かつ前記短縮実行時間を用いて、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋの各要素をそれぞれ前記演算部で決定し、該行列Ｆｋを用いて前記行列Ｆ＊を前記演算部で算出することを特徴とする請求項６記載のスケジュール作成方法。
【請求項８】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数１５８〜数１６１で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【数１５８】
2010198339.tif 000164
【数１５９】
2010198339.tif 000165
【数１６０】
2010198339.tif 000166
【数１６１】
2010198339.tif 000167
前記max-plus代数の定理を利用して前記行列Ｆを基に算出された次の数１６２の行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【数１６２】
2010198339.tif 000168
を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥ（ｋ）を、前記演算部が取得する第１のステップと、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数１６３に基づきプロジェクトバッファの値を前記演算部で算出する第２のステップと、
【数１６３】
2010198339.tif 000169
（ＰＢはプロジェクトバッファを表し、ｑは任意の数字。丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
を実行することを特徴とするスケジュール作成方法。
【請求項９】
前記最早終了時刻ｙＥ（ｋ）は、前記行列Ｃ０ｋと最早開始時刻ｘＥ（ｋ）とを用いて、前記演算部によって次の数１６４により算出され、
【数１６４】
2010198339.tif 000170
前記最早開始時刻ｘＥ（ｋ）は、ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び入力時刻ｕ（ｋ）とを利用し、前記演算部によって次の数１６５に基づき算出される
【数１６５】
2010198339.tif 000171
ことを特徴とする請求項８記載のスケジュール作成方法。
【請求項１０】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｊにおける実行時間をｄｊ（ｋ）としたときに、前記入力パラメータに基づいて次の数１６６で定義されたシステム構造を表現する行列Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素を前記演算部で決定する第１のステップと、
【数１６６】
2010198339.tif 000172
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した工程ｊを決定し、前記工程ｊの次工程がプロジェクトバッファの設置位置であると、前記演算部によって決定する第２のステップとを実行することを特徴とするスケジュール作成方法。
【請求項１１】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数１６７でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）と、
【数１６７】
2010198339.tif 000173
前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数１６８で定義されたシステム構造を表現する行列Ｆｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【数１６８】
2010198339.tif 000174
を前記演算部が取得する第１のステップと、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数１６９に基づき行列Ｆβαを、前記演算部で算出する第２のステップと、
【数１６９】
2010198339.tif 000175
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数１７０により行列υ´を前記演算部で算出する第３のステップと
【数１７０】
2010198339.tif 000176
を実行することを特徴とするスケジュール作成方法。
【請求項１２】
前記第３のステップの後に、
前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した次の数１７１により行列Ｆββを算出し、前記行列υ´と該行列Ｆββとから前記max-plus代数の定理を利用した次の数１７２に基づいて行列ｐを、前記演算部で算出する第４のステップと、
【数１７１】
2010198339.tif 000177
【数１７２】
2010198339.tif 000178
前記行列ｐの要素を次の数１７３の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数１７４を基に行列Ｆ〜ββを算出し、前記max-plus代数の定理を利用して前記行列Ｆ〜ββを基に次の数１７５の行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を前記演算部で算出する第５のステップと、
【数１７３】
2010198339.tif 000179
【数１７４】
2010198339.tif 000180
【数１７５】
2010198339.tif 000181
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用して次の数１７６によりフィーデングバッファの値を抽出した行列ＦＢを、前記演算部で算出する第６のステップと
【数１７６】
2010198339.tif 000182
（ｑは任意の数字）
を実行することを特徴とする請求項１１記載のスケジュール作成方法。
【請求項１３】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数１７７〜数１８０で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である。ｋはｋ番目の前記処理対象の工程処理であることを表す。）と、
【数１７７】
2010198339.tif 000183
【数１７８】
2010198339.tif 000184
【数１７９】
2010198339.tif 000185
【数１８０】
2010198339.tif 000186
前記max-plus代数の定理を利用して前記行列Ｆを基に算出された次の数１８１の行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【数１８１】
2010198339.tif 000187
を用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記各工程の実行時間を短縮したことによる遅れを防止するための猶予時間であるプロジェクトバッファの設置位置を決定すると共に、前記プロジェクトバッファの値を算出し、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数１８２でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）を算出し、該行列υ，ｗ´と前記行列Ｆｋとを用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記非クリティカルパス上の工程による遅れを防止するための猶予時間であるフィーデングバッファの設置位置を決定すると共に、前記フィーデングバッファの値を算出するように、前記演算部を構成した
【数１８２】
2010198339.tif 000188
ことを特徴とするスケジュール作成装置。
【請求項１４】
前記演算部は、
行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥ（ｋ）を取得し、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数１８３に基づきプロジェクトバッファの値を算出する
【数１８３】
2010198339.tif 000189
（ＰＢはプロジェクトバッファを表し、ｑは任意の数字。丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
ことを特徴とする請求項１３記載のスケジュール作成装置。
【請求項１５】
前記演算部は、
ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び前記入力時刻ｕ（ｋ）とを利用し、次の数１８４に基づき最早開始時刻ｘＥ（ｋ）を算出し、
【数１８４】
2010198339.tif 000190
前記行列Ｃ０ｋと前記最早開始時刻ｘＥ（ｋ）とを用いて次の数１８５により前記最早終了時刻ｙＥ（ｋ）を算出する
【数１８５】
2010198339.tif 000191
ことを特徴とする請求項１４記載のスケジュール作成装置。
【請求項１６】
前記演算部は、
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した前記工程ｊを決定し、該工程ｊの次工程が前記プロジェクトバッファの設置位置であると決定する
ことを特徴とする請求項１３〜１５うちいずれか１項記載のスケジュール作成装置。
【請求項１７】
前記演算部は、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数１８６に基づき行列Ｆβαを算出し、
【数１８６】
2010198339.tif 000192
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数１８７により行列υ´を算出する
【数１８７】
2010198339.tif 000193
ことを特徴とする請求項１３〜１６のうちいずれか１項記載のスケジュール作成装置。
【請求項１８】
前記演算部は、
前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した次の数１８８により行列Ｆββを算出し、前記行列υ´と前記行列Ｆββとから前記max-plus代数の定理を利用した次の数１８９に基づいて行列ｐを算出し、
【数１８８】
2010198339.tif 000194
【数１８９】
2010198339.tif 000195
前記行列ｐの要素を次の数１９０の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数１９１を基に行列Ｆ〜ββを算出し、前記行列Ｆ〜ββを基に前記max-plus代数の定理を利用した次の数１９２から行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を算出し、
【数１９０】
2010198339.tif 000196
【数１９１】
2010198339.tif 000197
【数１９２】
2010198339.tif 000198
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用した次の数１９３により前記フィーデングバッファの値を抽出した行列ＦＢを算出する
【数１９３】
2010198339.tif 000199
（ｑは任意の数字）
ことを特徴とする請求項１７記載のスケジュール作成装置。
【請求項１９】
前記演算部は、
前記各工程の実行時間を１／ｑに短縮した短縮実行時間を算出し、
前記入力パラメータに前記プロジェクトバッファの値と前記フィーデングバッファの値とを追加し、かつ前記短縮実行時間を用いて、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋの各要素をそれぞれ決定し、該行列Ｆｋを用いて前記行列Ｆ＊を算出する
ことを特徴とする請求項１８記載のスケジュール作成装置。
【請求項２０】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数１９４〜数１９７で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【数１９４】
2010198339.tif 000200
【数１９５】
2010198339.tif 000201
【数１９６】
2010198339.tif 000202
【数１９７】
2010198339.tif 000203
前記max-plus代数の定理を利用して前記行列Ｆを基に算出された次の数１９８の行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【数１９８】
2010198339.tif 000204
を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥを、前記演算部が取得し、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数１９９に基づきプロジェクトバッファの値を算出するように、前記演算部を構成した
【数１９９】
2010198339.tif 000205
（ＰＢはプロジェクトバッファを表し、ｑは任意の数字。丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
ことを特徴とするスケジュール作成装置。
【請求項２１】
前記演算部は、
ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び入力時刻ｕ（ｋ）とを利用し、次の数２００に基づき最早開始時刻ｘＥ（ｋ）を算出し、
【数２００】
2010198339.tif 000206
前記行列Ｃ０ｋと前記最早開始時刻ｘＥ（ｋ）とを用いて次の数２０１により前記最早終了時刻ｙＥ（ｋ）を算出する
【数２０１】
2010198339.tif 000207
ことを特徴とする請求項２０記載のスケジュール作成装置。
【請求項２２】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｊにおける実行時間をｄｊ（ｋ）としたときに、前記入力パラメータに基づいて次の数２０２で定義されたシステム構造を表現する行列Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素を前記演算部で決定し、
【数２０２】
2010198339.tif 000208
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した工程ｊの次工程が、プロジェクトバッファの設置位置であると決定するように、前記演算部を構成したことを特徴とするスケジュール作成装置。
【請求項２３】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数２０３でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）と、
【数２０３】
2010198339.tif 000209
前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数２０４で定義されたシステム構造を表現する行列Ｆｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【数２０４】
2010198339.tif 000210
を前記演算部が取得し、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数２０５に基づき行列Ｆβαを算出し、
【数２０５】
2010198339.tif 000211
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数２０６により行列υ´を算出するように、前記演算部を構成した
【数２０６】
2010198339.tif 000212
ことを特徴とするスケジュール作成装置。
【請求項２４】
前記演算部は、
前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した次の数２０７により行列Ｆββを算出して、前記行列υ´と該行列Ｆββとから前記max-plus代数の定理を利用した次の数２０８に基づいて行列ｐを算出し、
【数２０７】
2010198339.tif 000213
【数２０８】
2010198339.tif 000214
前記行列ｐの要素を次の数２０９の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数２１０を基に行列Ｆ〜ββを算出して、前記max-plus代数の定理を利用して前記行列Ｆ〜ββを基に次の数２１１の行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を算出し、
【数２０９】
2010198339.tif 000215
【数２１０】
2010198339.tif 000216
【数２１１】
2010198339.tif 000217
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用して次の数２１２によりフィーデングバッファの値を抽出した行列ＦＢを算出する
【数２１２】
2010198339.tif 000218
（ｑは任意の数字）
ことを特徴とする請求項２３記載のスケジュール作成装置。
【請求項２５】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるようにコンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数２１３〜数２１６で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である。ｋはｋ番目の前記処理対象の工程処理であることを表す。）と、
【数２１３】
2010198339.tif 000219
【数２１４】
2010198339.tif 000220
【数２１５】
2010198339.tif 000221
【数２１６】
2010198339.tif 000222
前記max-plus代数の定理を利用して前記行列Ｆを基に算出された次の数２１７の行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【数２１７】
2010198339.tif 000223
を用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記各工程の実行時間を短縮したことによる遅れを防止するための猶予時間であるプロジェクトバッファの設置位置を決定すると共に、前記プロジェクトバッファの値を算出するプロジェクトバッファ算出ステップと、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数２１８でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）を算出し、該行列υ，ｗ´と前記行列Ｆｋとを用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記非クリティカルパス上の工程による遅れを防止するための猶予時間であるフィーデングバッファの設置位置を決定すると共に、前記フィーデングバッファの値を算出するフィーデングバッファ算出ステップと、
【数２１８】
2010198339.tif 000224
を前記コンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項２６】
前記プロジェクトバッファ算出ステップは、前記コンピュータに、
行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥ（ｋ）を取得させ、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数２１９に基づきプロジェクトバッファの値を算出させる
【数２１９】
2010198339.tif 000225
（ＰＢは前記プロジェクトバッファを表し、ｑは任意の数字。丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
ことを特徴とする請求項２５記載のコンピュータプログラム。
【請求項２７】
前記コンピュータに、
ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び前記入力時刻ｕ（ｋ）とを利用し、次の数２２０に基づき最早開始時刻ｘＥ（ｋ）を算出させ、
【数２２０】
2010198339.tif 000226
前記行列Ｃ０ｋと前記最早開始時刻ｘＥ（ｋ）とを用いて次の数２２１により前記最早終了時刻ｙＥ（ｋ）を算出させる
【数２２１】
2010198339.tif 000227
ことを特徴とする請求項２６記載のコンピュータプログラム。
【請求項２８】
前記プロジェクトバッファ算出ステップでは、
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した前記工程ｊを決定し、該工程ｊの次工程が前記プロジェクトバッファの設置位置であると、前記コンピュータに決定させる
ことを特徴とする請求項２５〜２７うちいずれか１項記載のコンピュータプログラム。
【請求項２９】
前記フィーデングバッファ算出ステップでは、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数２２２に基づき行列Ｆβαを算出する第１のステップと、
【数２２２】
2010198339.tif 000228
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数２２３により行列υ´を算出する第２のステップと、
【数２２３】
2010198339.tif 000229
を前記コンピュータに実行させることを特徴とする請求項２５〜２８のうちいずれか１項記載のコンピュータプログラム。
【請求項３０】
前記第２のステップの後に、
前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した次の数２２４により行列Ｆββを算出し、前記行列υ´と前記行列Ｆββとから前記max-plus代数の定理を利用した次の数２２５に基づいて行列ｐを算出する第３のステップと、
【数２２４】
2010198339.tif 000230
【数２２５】
2010198339.tif 000231
前記行列ｐの要素を次の数２２６の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数２２７を基に行列Ｆ〜ββを算出し、前記行列Ｆ〜ββを基に前記max-plus代数の定理を利用した次の数２２８から行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を算出する第４のステップと、
【数２２６】
2010198339.tif 000232
【数２２７】
2010198339.tif 000233
【数２２８】
2010198339.tif 000234
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用した次の数２２９により前記フィーデングバッファの値を抽出した行列ＦＢを算出する第５のステップと
【数２２９】
2010198339.tif 000235
（ｑは任意の数字）
を前記コンピュータに実行させることを特徴とする請求項２９記載のコンピュータプログラム。
【請求項３１】
前記コンピュータに、
前記各工程の実行時間を１／ｑに短縮した短縮実行時間を算出させ、
前記プロジェクトバッファ及び前記フィーデングバッファを追加し、かつ前記短縮実行時間を用いて、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋの各要素をそれぞれ決定させ、該行列Ｆｋを用いて前記行列Ｆ＊を算出させることを特徴とする請求項３０記載のコンピュータプログラム。
【請求項３２】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるようにコンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数２３０〜数２３３で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【数２３０】
2010198339.tif 000236
【数２３１】
2010198339.tif 000237
【数２３２】
2010198339.tif 000238
【数２３３】
2010198339.tif 000239
前記max-plus代数の定理を利用して前記行列Ｆを基に算出された次の数２３４の行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【数２３４】
2010198339.tif 000240
を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥを、前記コンピュータに取得させ、
前記最早終了時刻ｙＥを用い、前記max-plus代数の定理を利用した次の数２３５に基づきプロジェクトバッファの値を前記コンピュータに算出させる
【数２３５】
2010198339.tif 000241
（ＰＢはプロジェクトバッファを表し、ｑは任意の数字。丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
ことを特徴とするコンピュータプログラム。
【請求項３３】
前記コンピュータに、
ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び入力時刻ｕ（ｋ）とを利用して次の数２３６に基づき最早開始時刻ｘＥ（ｋ）を算出させ、
【数２３６】
2010198339.tif 000242
前記行列Ｃ０ｋと前記最早開始時刻ｘＥ（ｋ）とを用いて次の数２３７により前記最早終了時刻ｙＥ（ｋ）を算出させる
【数２３７】
2010198339.tif 000243
ことを特徴とする請求項３２記載のコンピュータプログラム。
【請求項３４】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるようにコンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｊにおける実行時間をｄｊ（ｋ）としたときに、前記入力パラメータに基づいて次の数２３８で定義されたシステム構造を表現する行列Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素を決定する第１のステップと、
【数２３８】
2010198339.tif 000244
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した工程ｊの次工程が、プロジェクトバッファの設置位置であると決定する第２のステップとを前記コンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項３５】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるようにコンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数２３９でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）と、
【数２３９】
2010198339.tif 000245
前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数２４０で定義されたシステム構造を表現する行列Ｆｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【数２４０】
2010198339.tif 000246
を取得する第１のステップと、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数２４１に基づき行列Ｆβαを算出する第２のステップと、
【数２４１】
2010198339.tif 000247
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記第１のステップで取得した前記行列ｗ´と、前記第２のステップで取得した前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数２４２により行列υ´を算出する第３のステップと
【数２４２】
2010198339.tif 000248
をコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項３６】
前記第３のステップの後に、
前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した次の数２４３により行列Ｆββを算出し、前記第３のステップで算出した行列υ´と、該行列Ｆββとから前記max-plus代数の定理を利用した次の数２４４に基づいて行列ｐを算出する第４のステップと、
【数２４３】
2010198339.tif 000249
【数２４４】
2010198339.tif 000250
前記第４のステップで算出した前記行列ｐの要素を次の数２４５の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数２４６を基に行列Ｆ〜ββを算出し、前記max-plus代数の定理を利用して前記行列Ｆ〜ββを基に次の数２４７の行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を算出する第５のステップと、
【数２４５】
2010198339.tif 000251
【数２４６】
2010198339.tif 000252
【数２４７】
2010198339.tif 000253
前記行列υ´と前記行列Ｆ〜＊ββと行列υとを基に前記max-plus代数の定理を利用して次の数２４８によりフィーデングバッファの値を抽出した行列ＦＢを算出する第６のステップと
【数２４８】
2010198339.tif 000254
（ｑは任意の数字）
をコンピュータに実行させることを特徴とする請求項３５記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の工程を経て作業を行なう作業プロセスのスケジュール作成方法、スケジュール作成装置及びコンピュータプログラムに関する。
【背景技術】
【０００２】
生産システムの工程管理や、プロジェクトの進捗管理など、複数の工程が存在する作業プロセスに対して管理を行なう場合、例えば、ある工程が終了しないと次の工程に移れない、又は複数の工程で同時並行して作業が可能であるなど、様々な制約条件が課されている。そのため、こうしたシステムやプロジェクトの管理（マネジメント）には、納期遅れを出さす、かつできるだけ低コストで実行することが求められる。また、複数存在する工程の中で、どこが作業効率の最も悪い工程箇所であるボトルネックであるのかを常に把握し、納期遅れが生じないように、これらの工程の進捗状況には、常に注意を払うことが必要である。
【０００３】
従来、この種のシステムやプロジェクトのスケジュール管理としては、ガントチャートがしばしば用いられ、また重要な経路の把握には、アローダイアグラムを用いて解析することが多い。前者のガントチャートによる方法は、各工程がいつ実行されるのかが明確に記述されるため、人員や設備の計画やタスクの進捗状況把握に適している。しかし、工程の実行順序に関する制約関係は明示されないため、一つの工程の遅れが後続の工程や終了時刻にどのような影響を与えるのかを把握するのが難しいという欠点がある。
【０００４】
他方、アローダイアグラムによる方法は、タスクの実行順序を明確に記述するため、ボトルネック工程を把握することが容易にできる利点がある。その反面、どの資源をいつ使うのかの把握が難しく、資源割当や進捗管理といった用途には向いていない。また、同一資源を共有しながら複数のプロジェクトを同時並行で実施したり、同一の製品を繰り返し生産したりするような場合の解析には向いていない。
【０００５】
同一資源を繰り返し用いるようなシステムの記述と解析方法の一つに、時間付きペトリネット（ＴＰＮ）を用いる方法も提案されている。この方法では、トランジションの発火時刻を、工程の開始時刻や終了時刻とすると共に、プレース内でのトークンの保有時間を工程の実行時間とし、制御プレースによって資源の非競合（no-concurrency）を表現している。全てのプレースの上流と下流にトランジションが一つずつあるようなペトリネットのサブクラスは、ＴＥＧ（Timed Event Graph）と呼ばれており、ＴＥＧの振る舞いは、後述するmax-plus代数を用いて表現できることが知られている。
【０００６】
max-plus代数は、別名（max，＋）代数とも呼ばれており、離散事象システムのモデリング，解析，制御のための代表的なアプローチとして研究が進められている。離散事象システムの典型的な事象生起条件は、（１）複数の離散現象の同期（synchronization）。すなわち、全て生起することが別な離散現象の生起条件となる。（２）事象生起後、一定時間が経過した後に別の事象が生起する。以上の２つの条件が挙げられるが、max-plus代数では、（１）の条件を事象生起時刻のmax演算で記述し、（２）の条件を事象生起時刻と経過時間の＋演算で記述することができる。
【０００７】
max-plus代数の一番大きな特徴は、前記max演算を加算，＋演算を乗算と定義することで、本来は非線形演算となるmax演算に、ある種の線形特性を持たせることができる点にある。そのため、通常の（＋，×）代数系で成立する交換則や分配則が、スカラーや行列の演算において成立するなど、興味深い性質を持つ。また、前記ＴＥＧの挙動は、ＭＰＬ（max-plus線形）形式と呼ばれるmax-plus代数系での線形方程式を用いて表現できることが知られており、これは現代制御理論におけるシステムの状態空間表現に類似した形式となっている。このため、内部モデル制御やモデル予測制御など、現代制御理論における研究成果を応用する試みも行われている。
【０００８】
そこで、この種のスケジュール作成方法やスケジュール作成装置に用いられるmax-plus代数について、より具体的に説明する。max-plus代数とは、或るクラスの離散事象システムの記述に適した代数系であり、ここでは実数体をＲと表し、Ｄ＝Ｒ∪｛±∞｝において、加算及び乗算の二つの演算式を次のように定義する。
【０００９】
【数１】
2010198339.tif 000003
【００１０】
なお、上記加算や乗算の演算子は、通常の代数系での演算子と区別するために、「＋」や「×」のシンボルを丸印で囲んで表現するが、乗算については混乱のない限り演算子の表記を省略する（すなわち後者の式をｘｙと表記する）。これらの演算子の間には、通常の代数系と同様に、交換法則，結合法則，分配法則が成り立ち、式の変形など通常の代数系と同様の計算を行なうことができる。また、演算の優先順位は、加算よりも乗算が高いとする。加算及び乗算の単位元を、それぞれε（＝−∞）及びｅ（＝０）と定義すると、任意のｘ∈Ｄに対して、次の式が成り立つ。
【００１１】
【数２】
2010198339.tif 000004
【００１２】
さらに、上記数１や数２の式以外に、次の２つの演算子（∧，＼）も次のように定義する。
【００１３】
【数３】
2010198339.tif 000005
【００１４】
ここで、上記max関数は、括弧内で最大の値を算出することを意味し、min関数は、括弧内で最小の値を算出することを意味する。また、べき乗演算子は、次のように記述される。
【００１５】
【数４】
2010198339.tif 000006
【００１６】
複数の数に対する演算子は、ｍ≦ｎのときに、次のように記述される。
【００１７】
【数５】
2010198339.tif 000007
【００１８】
【数６】
2010198339.tif 000008
【００１９】
【数７】
2010198339.tif 000009
【００２０】
なお、ｍ＞ｎの場合は、何も演算を行なわず、前後の演算に対する単位元に成るものとする。
【００２１】
max-plus代数では、Ｄの元を要素に持つ行列に対しても、同様の演算子を用いて定義することができる。ここでは、ｍ行ｎ列の行列Ｘ（Ｘ∈Ｄｍ×ｎ）に対し、ＸＴは行列Ｘの転置行列を表し、［Ｘ］ijはｉ行ｊ列の要素を表わすものとする。また、ｍ行ｎ列の行列Ｘ，Ｙ（Ｘ，Ｙ∈Ｄｍ×ｎ）において、全てのｉ及びｊに対して（但し、１≦ｉ≦ｍ，１≦ｊ≦ｎ）、［Ｘ］ij≦［Ｙ］ijが成立するときに、Ｘ≦Ｙと表す。このとき、Ｘ，Ｙ∈Ｄｍ×ｎに対して、次の式に示す演算式を定義する。
【００２２】
【数８】
2010198339.tif 000010
【００２３】
【数９】
2010198339.tif 000011
【００２４】
また、ｍ行ｌ列の行列Ｘと、ｌ行ｐ列の行列Ｙ（Ｘ∈Ｄｍ×ｌ，Ｙ∈Ｄｌ×ｐ）に対して、次の式に示す演算式を定義する。
【００２５】
【数１０】
2010198339.tif 000012
【００２６】
【数１１】
2010198339.tif 000013
【００２７】
さらに、加算の単位元はεｍｎと表記し、これはεｍｎ∈Ｄｍ×ｎにおいて、全ての要素がεであることを意味する。また乗算の単位元はｅｍと表記し、これはｅｍ∈Ｄｍ×ｍにおいて、対角要素のみｅで、それ以外の非対称要素は全てεであることを意味する。以上の定義により、max-plus代数において、線形性を有する行列演算が可能となる。そして、こうしたmax-plus代数を用いることで、作業プロセス内で順に行われる作業の順番（以下、イベントカウンタと言う）を独立変数とし、作業プロセス内で作業が行われる時刻をイベントカウンタの関数として記述することで、工程管理や進捗管理におけるスケジュールを作成することができる。
【００２８】
次に、上記max-plus代数を用いたＭＰＬシステムについて説明する。ＭＰＬシステムとは、そのシステムの振る舞いがmax-plus代数上で線形な形式で表現することができるシステムのことで、次の式に示すような現代制御理論の状態空間表現に類似した形式で表される。
【００２９】
【数１２】
2010198339.tif 000014
【００３０】
【数１３】
2010198339.tif 000015
【００３１】
上式におけるイベントカウンタｋは、初期状態からの事象の発生回数を表す。また、ｘ（ｋ）∈Ｄｎ，ｕ（ｋ）∈Ｄｐ，ｙ（ｋ）∈Ｄｑはそれぞれ、状態変数，制御入力，制御出力であり、ｋ回目の事象が起こる時刻を表す。なお、ｎ，ｐ，ｑはそれぞれの変数の持つ次元である。さらに、Ａ∈Ｄｎ×ｎ，Ｂ∈Ｄｎ×ｐ，Ｃ∈Ｄｑ×ｎはそれぞれ、システム行列，入力行列，出力行列である。
【００３２】
ここで、図６に示すような作業プロセスとしての生産プロセスが、ＭＰＬシステムによりどのようにしてモデリングされるのかを具体的に説明する。図６は、複数の工程からなる生産システムにおける加工順序の一例を示した模式図であって、ここでは入力から工程（１）に材料（部品）を投入して加工し、その加工が終了した後に、工程（２）と工程（３）で同時並行的に材料の加工を行なう。続く工程（４）では、工程（２）と工程（３）の両方から加工済部品を受け取って加工を行ない、この工程（４）の加工が完了すると、製品として完成し出力される。
【００３３】
この生産システムに対して、工程（１）〜（４）の各加工時間を、それぞれｄ１，ｄ２，ｄ３，ｄ４とする。また、ｋ番目のバッチ加工に関して、工程（１）に投入される材料の投入時刻をｕ（ｋ）とし、工程（１）〜（４）におけるそれぞれの加工開始時刻を、ｘ１（ｋ），ｘ２（ｋ），ｘ３（ｋ），ｘ４（ｋ）とし、全ての加工が終了した製品の完成時刻をｙ（ｋ）として定義する。つまり、ｕ（ｋ）及びｙ（ｋ）は、各々システムに対する制御入力と制御出力に相当し、ｘ１（ｋ）〜ｘ４（ｋ）は、システム内部の状態変数に相当する。
【００３４】
さらに、図中に示した生産システムの各工程（１）〜（４）には、次のような制約条件が課せられているものとする。
・１つの材料は、全ての工程（１）〜（４）を１回だけ通過する。
・各工程（１）〜（４）の設備が稼動中のときには、その加工が終了するまで、次の加工を開始できない。
・先行工程を有する工程（２）〜（４）は、それらの先行工程の加工が終了しないと、加工を開始できない。
・入力のある工程（１）は、当該番号の材料を受け取らないと加工を開始できない。
・各工程（１）〜（４）の設備が空、即ち稼動していない状態で、先行工程や入力から材料を受け取ると、直ちに加工を開始する。
【００３５】
以上の制約条件より、工程（１）が（ｋ）番目の材料の加工を開始する時刻ｘ１（ｋ）は、ｋ番目の材料が投入された時刻ｕ（ｋ）と、工程（１）でｋ−１番目の材料の加工が終了した時刻ｘ１（ｋ−１）＋ｄ１の遅い方に定められる。工程（２）が（ｋ）番目の材料の加工を開始する時刻ｘ２（ｋ）は、工程（２）でｋ−１番目の材料の加工が終了した時刻ｘ２（ｋ−１）＋ｄ２と、工程（１）からｋ番目の加工済材料を受け取った時刻ｘ１（ｋ）＋ｄ１の遅い方に定められ、同様に、工程（３）がｋ番目の材料の加工を開始する時刻ｘ３（ｋ）は、工程（３）でｋ−１番目の材料の加工が終了した時刻ｘ３（ｋ−１）＋ｄ３と、工程（１）からｋ番目の加工済材料を受け取った時刻ｘ１（ｋ）＋ｄ１の遅い方に定められる。また、工程（４）がｋ番目の材料の加工を開始する時刻ｘ４（ｋ）は、工程（２）からｋ番目の加工済材料を受け取った時刻ｘ２（ｋ）＋ｄ２と、工程（３）からｋ番目の加工済材料を受け取った時刻ｘ３（ｋ）＋ｄ３と、工程（４）でｋ−１番目の材料の加工が終了した時刻ｘ４（ｋ−１）＋ｄ４の遅い方に定められる。さらに、ｋ番目の加工済材料が製品として完了する時刻ｙ（ｋ）は、工程（４）でｋ番目の材料の加工が終了した時刻ｘ４（ｋ）＋ｄ４に一致する。これらをmax-plus代数により表現すると、前述した遅い方の時刻の算出はmax演算子で記述することができるので、以下に示す各数式のようになる。
【００３６】
【数１４】
2010198339.tif 000016
【００３７】
【数１５】
2010198339.tif 000017
【００３８】
【数１６】
2010198339.tif 000018
【００３９】
【数１７】
2010198339.tif 000019
【００４０】
【数１８】
2010198339.tif 000020
【００４１】
上記数１４を数１５及び数１６に代入し、これらを数１７に代入すると、数１４〜数１８は前記数１２や数１３で表され、ＭＰＬシステムの形式で記述することができる。但し、ここでの数１２や数１３におけるシステム行列Ａや、入力行列Ｂ、出力行列Ｃは、次の式のようになる。
【００４２】
【数１９】
2010198339.tif 000021
【００４３】
数１２や数１３の式は、作業プロセスでの作業開始時刻及び終了時刻に関する一般的な表現となっており、これらの数式をさらに変形すると、未来の製品完了時刻ｙ（ｋ＋１）を、現在の内部状態ｘ（ｋ）と、未来の材料の投入時刻ｕ（ｋ＋１）とにより計算することが可能になる。従って、生産システムの内部状態ｘ（ｋ）が定まっており、未来の製品完了時刻ｙ（ｋ＋１）として、生産システムにおける納期である望ましい出力Ｒ（ｋ＋１）を定めたとき、納期遅れを出すことがない適切な入力ｕ（ｋ＋１）を求めることができる。また、イベントカウンタがｋ＋２以降の場合は、イベントカウンタを一つずつ増やして再計算することにより、生産システムに適切な投入時刻を求めることが可能となり、最終的に作業プロセスのスケジュールを作成することができる。
【００４４】
こうしたＭＰＬシステムを利用した生産システムのモデリングは、例えば特許文献１や特許文献２などにも開示され、作業プロセスのスケジュールを作成する方法として広く採用されているが、例えば先行制約を有するプロジェクトのスケジューリング問題にも同様に適用することができ、その場合の各工程はタスクに相当する。但し、本発明では、こうしたタスクを含めたものを工程として定義する。
【先行技術文献】
【特許文献】
【００４５】
【特許文献１】特開２００４−２４０８５３号公報
【特許文献２】特開２００５−３３９１７８号公報
【発明の概要】
【発明が解決しようとする課題】
【００４６】
上述したような作業プロセスのスケジュールを作成するためには、作業プロセスをモデル化して、上記数１５〜数１７にあるような右辺にｘｉ（ｋ）を含む式から、数１２のような右辺にｘ（ｋ）が現れない形式に変形を行って、ＭＰＬシステムに適合する作業プロセスの状態を表現した式に作成変換し、線形計画法などを用いた数値計算を行なう必要がある。しかし、従来のこうした方法では、作業プロセスの状態を表現する数１２や数１３の式を手作業で作成していたため、複雑な作業プロセスに対して適用することが困難であるという問題があった。また、こうした点を考慮して、特許文献１では、作業プロセスのスケジュールを作成する一連の手順をコンピュータで処理する手法を提案しているが、メモリ消費が大きく処理システムが膨大なものとなり、計算が非効率で改善が求められていた。
【００４７】
また、従来の工程管理では、個々の工程が計画通り確実に終了することを前提にしているため、作業計画に遅れが生じないように各工程において予め余裕（安全時間）を持たせた加工時間が設定されている。そして、こうした余裕ある加工時間が設定されている場合には、作業着手を先延ばしする誘引にもなり、また所定の工程において早期に作業が完了しても、スケジュール上の終了日まで次工程に引き渡さない虞もあり、結局はスケジュール全体に遅れが生じる虞があるという問題があった。
【００４８】
本発明は上記の問題点に鑑みなされたもので、より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に対してクリティカルチェーン法を適用可能とし、処理時間の不確定性が高い場合にも納期遅れを出さず、かつ納期短縮を図り得るスケジュール作成方法、スケジュール作成装置及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００４９】
本発明は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数２０〜数２３で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である。ｋはｋ番目の前記処理対象の工程処理であることを表す。）と、
【００５０】
【数２０】
2010198339.tif 000022
【００５１】
【数２１】
2010198339.tif 000023
【００５２】
【数２２】
2010198339.tif 000024
【００５３】
【数２３】
2010198339.tif 000025
【００５４】
前記行列Ｆを基に前記max-plus代数の定理を利用した次の数２４から算出された行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【００５５】
【数２４】
2010198339.tif 000026
【００５６】
を用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記各工程の実行時間を短縮したことによる遅れを防止するための猶予時間であるプロジェクトバッファの設置位置を決定すると共に、前記プロジェクトバッファの値を算出するプロジェクトバッファ算出ステップと、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数２５でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）を算出し、該行列υ，ｗ´と前記行列Ｆｋとを用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記非クリティカルパス上の工程による遅れを防止するための猶予時間であるフィーデングバッファの設置位置を決定すると共に、前記フィーデングバッファの値を算出するフィーデングバッファ算出ステップと、
【００５７】
【数２５】
2010198339.tif 000027
【００５８】
を実行するスケジュール作成方法である。
【００５９】
この場合、前記プロジェクトバッファ算出ステップは、
行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥ（ｋ）を、前記演算部が取得し、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数２６に基づき前記プロジェクトバッファの値を前記演算部で算出する
【００６０】
【数２６】
2010198339.tif 000028
【００６１】
（ＰＢは前記プロジェクトバッファを表し、ｑは任意の数字。丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）ことが好ましい。
【００６２】
また、前記最早終了時刻ｙＥ（ｋ）は、前記行列Ｃ０ｋと最早開始時刻ｘＥ（ｋ）とを用いて、前記演算部によって次の数２７により算出され、
【００６３】
【数２７】
2010198339.tif 000029
【００６４】
前記最早開始時刻ｘＥ（ｋ）は、ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び前記入力時刻ｕ（ｋ）とを利用し、前記演算部によって次の数２８に基づき算出される。
【００６５】
【数２８】
2010198339.tif 000030
【００６６】
また、前記プロジェクトバッファ算出ステップは、前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した前記工程ｊを決定し、該工程ｊの次工程が前記プロジェクトバッファの設置位置であると、前記演算部によって決定する。
【００６７】
また、前記フィーデングバッファ算出ステップは、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数２９に基づき行列Ｆβαを前記演算部で算出する第１のステップと、
【００６８】
【数２９】
2010198339.tif 000031
【００６９】
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数３０により行列υ´を前記演算部で算出する第２のステップと、
【００７０】
【数３０】
2010198339.tif 000032
【００７１】
を実行することが好ましい。
【００７２】
また、前記第２のステップの後に、前記行列υと前記行列Ｆｋとを用い前記max-plus代数の定理を利用した次の数３１により行列Ｆββを算出し、前記行列υ´と前記行列Ｆββとを用い前記max-plus代数の定理を利用した次の数３２に基づいて行列ｐを前記演算部で算出する第３のステップと、
【００７３】
【数３１】
2010198339.tif 000033
【００７４】
【数３２】
2010198339.tif 000034
【００７５】
前記行列ｐの要素を次の数３３の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数３４を基に行列Ｆ〜ββを算出し、前記行列Ｆ〜ββを基に前記max-plus代数の定理を利用した次の数３５から行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を前記演算部で算出する第４のステップと、
【００７６】
【数３３】
2010198339.tif 000035
【００７７】
【数３４】
2010198339.tif 000036
【００７８】
【数３５】
2010198339.tif 000037
【００７９】
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用した次の数３６により前記フィーデングバッファの値を抽出した行列ＦＢを、前記演算部で算出する第５のステップと
【００８０】
【数３６】
2010198339.tif 000038
【００８１】
を実行することが好ましい。
【００８２】
また、前記各工程の実行時間を１／ｑに短縮した短縮実行時間を前記演算部で算出する実行時間短縮ステップを備え、前記入力パラメータに前記プロジェクトバッファの値と前記フィーデングバッファの値とを追加し、かつ前記短縮実行時間を用いて、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋの各要素をそれぞれ前記演算部で決定し、該行列Ｆｋを用いて前記行列Ｆ＊を前記演算部で算出することが好ましい。
【００８３】
また、本発明は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数３７〜数４０で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【００８４】
【数３７】
2010198339.tif 000039
【００８５】
【数３８】
2010198339.tif 000040
【００８６】
【数３９】
2010198339.tif 000041
【００８７】
【数４０】
2010198339.tif 000042
【００８８】
前記max-plus代数の定理を利用して前記行列Ｆを基に算出された次の数４１の行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【００８９】
【数４１】
2010198339.tif 000043
【００９０】
を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥ（ｋ）を、前記演算部が取得する第１のステップと、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数４２に基づきプロジェクトバッファの値を前記演算部で算出する第２のステップと、
【００９１】
【数４２】
2010198339.tif 000044
【００９２】
（ＰＢはプロジェクトバッファを表し、ｑは任意の数字。丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
を実行するスケジュール作成方法である。
【００９３】
また、前記最早終了時刻ｙＥ（ｋ）は、前記行列Ｃ０ｋと最早開始時刻ｘＥ（ｋ）とを用いて、前記演算部によって次の数４３により算出され、
【００９４】
【数４３】
2010198339.tif 000045
【００９５】
前記最早開始時刻ｘＥ（ｋ）は、ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び入力時刻ｕ（ｋ）とを利用し、前記演算部によって次の数４４に基づき算出される。
【００９６】
【数４４】
2010198339.tif 000046
【００９７】
また、本発明は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｊにおける実行時間をｄｊ（ｋ）としたときに、前記入力パラメータに基づいて次の数４５で定義されたシステム構造を表現する行列Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素を前記演算部で決定する第１のステップと、
【００９８】
【数４５】
2010198339.tif 000047
【００９９】
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した工程ｊを決定し、前記工程ｊの次工程がプロジェクトバッファの設置位置であると、前記演算部によって決定する第２のステップとを実行するスケジュール作成方法である。
【０１００】
また、本発明は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数４６でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）と、
【０１０１】
【数４６】
2010198339.tif 000048
【０１０２】
前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数４７で定義されたシステム構造を表現する行列Ｆｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【０１０３】
【数４７】
2010198339.tif 000049
【０１０４】
を前記演算部が取得する第１のステップと、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数４８に基づき行列Ｆβαを前記演算部で算出する第２のステップと、
【０１０５】
【数４８】
2010198339.tif 000050
【０１０６】
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数４９により行列υ´を前記演算部で算出する第３のステップと
【０１０７】
【数４９】
2010198339.tif 000051
【０１０８】
を実行するスケジュール作成方法である。
【０１０９】
また、前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した次の数５０により行列Ｆββを算出し、前記行列υ´と該行列Ｆββとから前記max-plus代数の定理を利用した次の数５１に基づいて行列ｐを前記演算部で算出する第４のステップと、
【０１１０】
【数５０】
2010198339.tif 000052
【０１１１】
【数５１】
2010198339.tif 000053
【０１１２】
前記行列ｐの要素を次の数５２の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数５３を基に行列Ｆ〜ββを算出し、前記max-plus代数の定理を利用して前記行列Ｆ〜ββを基に次の数５４の行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を前記演算部で算出する第５のステップと、
【０１１３】
【数５２】
2010198339.tif 000054
【０１１４】
【数５３】
2010198339.tif 000055
【０１１５】
【数５４】
2010198339.tif 000056
【０１１６】
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用して次の数５５によりフィーデングバッファの値を抽出した行列ＦＢを、前記演算部で算出する第６のステップと
【０１１７】
【数５５】
2010198339.tif 000057
【０１１８】
を実行するスケジュール作成方法である。
【０１１９】
そして、本発明によるこれらスケジュール作成方法については、これらスケジュール作成方法をコンピュータに実行させるためのコンピュータプログラムを当該コンピュータに対して読み込ませることにより、当該コンピュータとコンピュータプログラムとの協働した演算処理を実行させることで、スケジュール作成装置を構築させることができる。
【０１２０】
すなわち、本発明によるスケジュール作成装置は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数５６〜数５９で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である。ｋはｋ番目の前記処理対象の工程処理であることを表す。）と、
【０１２１】
【数５６】
2010198339.tif 000058
【０１２２】
【数５７】
2010198339.tif 000059
【０１２３】
【数５８】
2010198339.tif 000060
【０１２４】
【数５９】
2010198339.tif 000061
【０１２５】
前記max-plus代数の定理を利用して前記行列Ｆを基に算出された次の数６０の行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【０１２６】
【数６０】
2010198339.tif 000062
【０１２７】
を用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記各工程の実行時間を短縮したことによる遅れを防止するための猶予時間であるプロジェクトバッファの設置位置を決定すると共に、前記プロジェクトバッファの値を算出し、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数６１でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）を算出し、該行列υ，ｗ´と前記行列Ｆｋとを用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記非クリティカルパス上の工程による遅れを防止するための猶予時間であるフィーデングバッファの設置位置を決定すると共に、前記フィーデングバッファの値を算出するように、前記演算部を構成した
【０１２８】
【数６１】
2010198339.tif 000063
【０１２９】
ことを特徴とするスケジュール作成装置である。
【０１３０】
また、前記演算部は、
行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥ（ｋ）を取得し、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数６２に基づきプロジェクトバッファの値を算出する。
【０１３１】
【数６２】
2010198339.tif 000064
【０１３２】
また、前記演算部は、
ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び前記入力時刻ｕ（ｋ）とを利用し、次の数６３に基づき最早開始時刻ｘＥ（ｋ）を算出し、
【０１３３】
【数６３】
2010198339.tif 000065
【０１３４】
前記行列Ｃ０ｋと前記最早開始時刻ｘＥ（ｋ）とを用いて次の数６４により前記最早終了時刻ｙＥ（ｋ）を算出する。
【０１３５】
【数６４】
2010198339.tif 000066
【０１３６】
また、前記演算部は、
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した前記工程ｊを決定し、該工程ｊの次工程が前記プロジェクトバッファの設置位置であると決定することが好ましい。
【０１３７】
また、前記演算部は、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数６５に基づき行列Ｆβαを算出し、
【０１３８】
【数６５】
2010198339.tif 000067
【０１３９】
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数６６により行列υ´を算出する
【０１４０】
【数６６】
2010198339.tif 000068
【０１４１】
ような構成としている。
【０１４２】
また、前記演算部は、
前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した次の数６７により行列Ｆββを算出し、前記行列υ´と前記行列Ｆββとから前記max-plus代数の定理を利用した次の数６８に基づいて行列ｐを算出し、
【０１４３】
【数６７】
2010198339.tif 000069
【０１４４】
【数６８】
2010198339.tif 000070
【０１４５】
前記行列ｐの要素を次の数６９の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数７０を基に行列Ｆ〜ββを算出し、前記行列Ｆ〜ββを基に前記max-plus代数の定理を利用した次の数７１から行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を算出し、
【０１４６】
【数６９】
2010198339.tif 000071
【０１４７】
【数７０】
2010198339.tif 000072
【０１４８】
【数７１】
2010198339.tif 000073
【０１４９】
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用した次の数７２により前記フィーデングバッファの値を抽出した行列ＦＢを算出する
【０１５０】
【数７２】
2010198339.tif 000074
【０１５１】
ことを特徴とする。
【０１５２】
また、前記演算部は、
前記各工程の実行時間を１／ｑに短縮した短縮実行時間を算出し、前記入力パラメータに前記プロジェクトバッファの値と前記フィーデングバッファの値とを追加し、かつ前記短縮実行時間を用いて、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋの各要素をそれぞれ決定し、該行列Ｆｋを用いて前記行列Ｆ＊を算出することが好ましい。
【０１５３】
また、本発明のスケジュール作成装置は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数７３〜数７６で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【０１５４】
【数７３】
2010198339.tif 000075
【０１５５】
【数７４】
2010198339.tif 000076
【０１５６】
【数７５】
2010198339.tif 000077
【０１５７】
【数７６】
2010198339.tif 000078
【０１５８】
前記max-plus代数の定理を利用して前記行列Ｆを基に算出された次の数７７の行列Ｆ＊（但し、Ｆｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算であることを表す）と、
【０１５９】
【数７７】
2010198339.tif 000079
【０１６０】
を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥを、前記演算部が取得し、
前記最早終了時刻ｙＥ（ｋ）を用い、前記max-plus代数の定理を利用した次の数７８に基づきプロジェクトバッファの値を算出するように、前記演算部を構成した
【０１６１】
【数７８】
2010198339.tif 000080
【０１６２】
（ＰＢはプロジェクトバッファを表し、ｑは任意の数字であり、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）スケジュール作成装置である。
【０１６３】
また、前記演算部は、
ｋ番目の前記処理対象の工程処理に関して、各工程での処理開始時刻をｘ（ｋ−１）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び入力時刻ｕ（ｋ）とを利用し、次の数７９に基づき最早開始時刻ｘＥ（ｋ）を算出し、
【０１６４】
【数７９】
2010198339.tif 000081
【０１６５】
前記行列Ｃ０ｋと前記最早開始時刻ｘＥ（ｋ）とを用いて次の数８０により前記最早終了時刻ｙＥ（ｋ）を算出する
【０１６６】
【数８０】
2010198339.tif 000082
【０１６７】
ことが好ましい。
【０１６８】
また、本発明スケジュール作成装置は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｊにおける実行時間をｄｊ（ｋ）としたときに、前記入力パラメータに基づいて次の数８１で定義されたシステム構造を表現する行列Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素を前記演算部で決定し、
【０１６９】
【数８１】
2010198339.tif 000083
【０１７０】
前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した工程ｊの次工程が、プロジェクトバッファの設置位置であると決定するように、前記演算部を構成したスケジュール作成装置である。
【０１７１】
また、本発明のスケジュール作成装置は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を表現するために、前記処理対象を受け渡す前記各工程の実行順序を表した先行制約関係情報と、前記各工程における実行時間とからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして次の数８２でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）と、
【０１７２】
【数８２】
2010198339.tif 000084
【０１７３】
前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、次の数８３で定義されたシステム構造を表現する行列Ｆｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）と、
【０１７４】
【数８３】
2010198339.tif 000085
【０１７５】
を前記演算部が取得し、
前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した次の数８４に基づき行列Ｆβαを算出し、
【０１７６】
【数８４】
2010198339.tif 000086
【０１７７】
（diagは対角行列を表し、Ｔは転置行列を表し、丸で囲んだ×は前記max-plus代数で定理される乗算であることを表す）
前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した次の数８５により行列υ´を算出し、
【０１７８】
【数８５】
2010198339.tif 000087
【０１７９】
ことを特徴とするスケジュール作成装置である。
【０１８０】
また、このスケジュール作成装置は、前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した次の数８６により行列Ｆββを算出して、前記行列υ´と該行列Ｆββとから前記max-plus代数の定理を利用した次の数８７に基づいて行列ｐを算出し、
【０１８１】
【数８６】
2010198339.tif 000088
【０１８２】
【数８７】
2010198339.tif 000089
【０１８３】
前記行列ｐの要素を次の数８８の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した次の数８９を基に行列Ｆ〜ββを算出して、前記max-plus代数の定理を利用して前記行列Ｆ〜ββを基に次の数９０の行列Ｆ〜＊ββ（但し、Ｆ〜ββｌにおいて全ての要素がεになり、またｎは工程数である。ｅｎは対角要素のみｅで、それ以外の非対角要素が全てεであるｎ行ｎ列の行列である。丸で囲んだ＋は前記max-plus代数で定理される加算を表す）を算出し、
【０１８４】
【数８８】
2010198339.tif 000090
【０１８５】
【数８９】
2010198339.tif 000091
【０１８６】
【数９０】
2010198339.tif 000092
【０１８７】
前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用して次の数９１によりフィーデングバッファの値を抽出した行列ＦＢを算出するように、前記演算部を構成した。
【０１８８】
【数９１】
2010198339.tif 000093
【発明の効果】
【０１８９】
請求項１の方法，請求項１３の装置，及び請求項２５のコンピュータプログラムによれば、例えばシステムにクリティカルチェーン法を適用して計画期間の短縮を図る場合でも、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を利用して、当該クリティカルチェーン法を適用した際に用いるプロジェクトバッファ及びフィーデングバッファのそれぞれの位置及び値を簡単に取得することができる。従って、より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に対してクリティカルチェーン法を適用可能とし、処理時間の不確定性が高い場合にも納期遅れを出さず、かつ納期短縮を図り得る。
【０１９０】
請求項２，８の方法，請求項１４，２０の装置，及び請求項２６，３２のコンピュータプログラムによれば、先に算出した行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を利用して、プロジェクトバッファの値を簡単に算出することができる。
【０１９１】
請求項３，９の方法，請求項１５，２１の装置，及び請求項２７，３３のコンピュータプログラムによれば、プロジェクトバッファの値を算出する際に用いられる前記最早開始時刻ｘＥ（ｋ）と前記最早終了時刻ｙＥ（ｋ）とを、先に算出した行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を利用して簡単に算出することができる。
【０１９２】
請求項４，１０の方法，請求項１６，２２の装置，及び請求項２８，３４のコンピュータプログラムによれば、先に算出した行列Ｃ０ｋを利用して、プロジェクトバッファの位置を簡単に決定することができる。
【０１９３】
請求項５，１１の方法，請求項１７，２３の装置，及び請求項２９，３５のコンピュータプログラムによれば、先に算出した前記行列υ，ｗ´，Ｆｋを利用して、フィーデングバッファの位置を簡単に決定することができる。
【０１９４】
請求項６，１２の方法，請求項１８，２４の装置，及び請求項３０，３６のコンピュータプログラムによれば、先に算出した前記行列υ，υ´，Ｆｋを利用して、フィーデングバッファの値を簡単に決定することができる。
【０１９５】
請求項７の方法，請求項１９の装置，及び請求項３１のコンピュータプログラムによれば、プロジェクトバッファとフィーデングバッファとを追加した状態で、行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，の各要素を決定し、さらにここで決定した行列Ｆから行列Ｆ＊を算出して、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋを簡単に取得することができる。
【図面の簡単な説明】
【０１９６】
【図１】生産システムにおける加工順序の一例を示した模式図である。
【図２】生産システムに対してクリティカルチェーン法を適用してＰＢ及びＦＢを追加したときの加工順序の一例を示した模式図である。
【図３】本発明におけるスケジュール作成装置の内部構成を示すブロック図である。
【図４】同上、スケジュール作成装置による処理手順を示すフローチャートである。
【図５】同上、スケジュール作成装置による再スケジュール作成処理手順を示すフローチャートである。
【図６】従来における生産システムにおける加工順序の説明に供する模式図である。
【発明を実施するための形態】
【０１９７】
以下、添付図面に基づいて、本発明における好適な実施例を詳細に説明する。
【０１９８】
（１）本発明の概要
本発明は、本願発明者による先願（特開２００７−３３４８５５号公報）において既に提案されているmax-plus代数を用いたＭＰＬシステムに、クリティカルチェーン法を適用可能とした点に特徴を有する。クリティカルチェーン法とは、制約理論の下、各工程における加工時間の遅延を予め念頭においた上で、プロジェクト所要時間を短縮し、かつ納期遅れを減らすためのスケジューリング方法である。ここで、制約理論とは、ボトルネックが生産性を決定する工程とみなし、他の工程とバランスを図りながらボトルネックを改善し、全体の生産性を向上させる理論である。このような制約理論の下では、個々の工程の最適化を目指すのではなく、クリティカルパス（後述する）などを制約条件にして、計画全体としての最適化を目指す。
【０１９９】
ここで、クリティカルパスとは、生産システムにおいて入力から出力に向けて工程を結んだ複数の経路のうち、入力から出力までに要する時間が最長で、かつ遅れが許されない経路をいう。図１は、複数の工程からなる生産システムにおける加工順序の一例を示した模式図であり、この生産システムＳＴ１を一例として、クリティカルパスについて以下説明する。先ず始めにこの生産システムＳＴ１について説明すると、当該生産システムＳＴ１は、例えば入力から出力までの間に複数の工程（１）〜（７）が設けられており、入力から工程（１）に材料（部品又はジョブともいう）を投入して加工し、その加工が終了した後に、工程（２）と工程（３）で同時並行的に材料の加工を行なう。工程（２）は、工程（１）から受け取った加工済みの材料にさらに加工を行い、これを工程（４）及び工程（５）にそれぞれ投入する。また、このとき工程（３）は、工程（１）から受け取った加工済みの材料にさらに加工を行い、これを工程（４）、工程（５）及び工程（６）にそれぞれ投入する。
【０２００】
工程（４）は、工程（２）及び工程（３）の両方からそれぞれ加工済の材料を受け取ると、これら加工済の材料をさらに加工して工程（７）に投入する。工程（５）は、工程（２）及び工程（３）の両方からそれぞれ加工済の材料を受け取ると、これら加工済の材料をさらに加工して工程（７）に投入する。工程（６）は、工程（３）から加工済の材料を受け取ると、この加工済の材料をさらに加工して工程（７）に投入する。工程（７）は、工程（４）、工程（５）及び工程（６）全てから加工済の材料を受け取ると、これらを加工して、製品として完成させて出力する。
【０２０１】
そして、この生産システムＳＴ１においては、例えば工程（１）の加工時間ｄ１が３、工程（２）の加工時間ｄ２が６、工程（３）の加工時間ｄ３が３、工程（４）の加工時間ｄ４が１２、工程（５）の加工時間ｄ５が３、工程（６）の加工時間ｄ６が３、及び工程（７）の加工時間ｄ７が６にそれぞれ設定されている。因みに、本発明による生産システムＳＴ１における各工程（１）〜（７）には、次のような制約条件が課せられているものとする。
・１つの材料は、全ての工程（１）〜（７）を１回だけ通過する。
・各工程（１）〜（７）の設備が稼動中のときには、その加工が終了するまで、次の加工を開始できない。
・先行工程を有する工程（２）〜（７）は、それらの先行工程の加工が終了しないと、加工を開始できない。
・入力のある工程（１）は、入力があるまで（材料を受け取るまで)加工を開始できない。
・各工程（１）〜（７）の設備が空、即ち稼動していない状態で、先行工程や入力から材料を受け取ると、直ちに加工を開始する。
【０２０２】
このような生産システムＳＴ１では、入力から出力までの間において、工程（１），（２），（４）及び（７）を経由する経路の全加工時間が２７となり、例えば工程（１），（２），（５）及び（７）を経由する経路や、工程（１），（３），（５）及び（７）を経由する経路など他の経路において要する全加工時間に比べて最長となることから、工程（１），（２），（４）及び（７）を経由する経路がクリティカルパスとなる。
【０２０３】
ここで、このような生産システムＳＴ１においては、各工程（１）〜（７）の加工時間ｄ１〜ｄ７を見積る際に、不確実性を考慮して、一般的に、約９０％以上の確率で工程作業を確実に完了できると推測される加工時間（ＨＰ：Highly Possible）を見積り、このように余裕時間を含ませたＨＰを各工程（１）〜（７）の加工時間ｄ１〜ｄ７とすることで、入力から出力までの作業計画全体が遅れないように図られている。
【０２０４】
これに対してクリティカルチェーン法では、各工程（１）〜（７）において見積られる加工時間ｄ１〜ｄ７として、約５０％程度の確率で工程作業を完了できると推測される加工時間（ＡＢＰ：Aggressive But Possible）を用いる。ＡＢＰは、経験的にＨＰの１／３まで短縮可能であるとされており、次の数９２のように表されることが多く、この場合、ＨＰに含まれる余裕時間は次の数９３で表すことができる。
【０２０５】
【数９２】
2010198339.tif 000094
【０２０６】
【数９３】
2010198339.tif 000095
【０２０７】
クリティカルチェーン法では、このように各工程（１）〜（７）の加工時間ｄ１〜ｄ７をＡＢＰに基づいて見積り、各工程（１）〜（７）における加工時間ｄ１〜ｄ７を短縮させる。そして、このクリティカルチェーン法では、入力から出力までの経路の所定位置に、猶予時間としてプロジェクトバッファ（以下、これを単にＰＢと呼ぶ）とフィーデングバッファ（以下、これを単にＦＢと呼ぶ）とを設けることで、各工程（１）〜（７）の不確実性によって、仮に所定の工程にて加工時間が長くなっても、計画全体の遅延を防止し得るようになされている。
【０２０８】
図２においてＳＴ２は、図１の生産システムＳＴ１に対してクリティカルチェーン法を適用し、生産システムＳＴ１を新たに構築し直した生産システムを示すものである。ここで、ＰＢとは、生産システムＳＴ２上の各工程（１）〜（７）で遅延が生じることで、計画全体に遅延が生じることを防止するための猶予時間であり、クリティカルパス上の最終工程（７）と出力との間に設置される。また、ＦＢ３，ＦＢ５，ＦＢ６（以下、これらをまとめて単にＦＢとする）は、クリティカルパスに合流するクリティカルパス以外の経路（以下、これを非クリティカルパスと呼ぶ）上の各工程（３），（５），（６）で遅延が生じることで、計画全体に遅延が生じることを防止するための猶予時間であり、非クリティカルパスとクリティカルパスとの合流点に設置される。
【０２０９】
本発明では、後述するスケジュール作成装置によって、工程間の制約条件や加工時間をmax-plus代数を用いたＭＰＬシステムで表現し、各工程の最早開始時刻や最遅開始時刻（後述する）、クリティカルパスとなる経路などを求め、当該ＭＰＬシステムを利用してクリティカルチェーン法で用いるＰＢの位置及び値と、ＦＢの位置及び値とを決定することができる（後述する）。
【０２１０】
そして、本発明では、各工程の加工時間をＡＢＰに短縮し、かつＰＢ、ＦＢを追加した生産システムＳＴ２について、再び工程間の制約条件や加工時間をmax-plus代数を用いたＭＰＬシステムで表現し、計画全体として短縮化を図った各工程の最早開始時刻や最遅開始時刻などを算出することが可能になる。
【０２１１】
（２）本発明によるスケジュール作成装置の構成
図３は、本発明におけるスケジュール作成装置１の内部構成を示すブロック図である。スケジュール作成装置１は、パーソナルコンピュータ又はサーバ装置などの汎用コンピュータを用いて構成されている。スケジュール作成装置１は、演算を行なうＣＰＵ（演算部）１１と、演算に伴って発生する一時的な情報などを記憶するＲＡＭ（記憶部）１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備えている。スケジュール作成装置１全体を統括的に制御するＣＰＵ１１は、ＣＤ−ＲＯＭ等の記録媒体２から本発明のコンピュータプログラム２０を外部記憶装置１３にて読み取り、読み取ったコンピュータプログラム２０を内部記憶装置１４に記憶させる。コンピュータプログラム２０は必要に応じて内部記憶装置１４からＲＡＭ１２へロードされ、ロードされたコンピュータプログラム２０に基づいてＣＰＵ１１はスケジュール作成装置１に必要な処理を実行する。
【０２１２】
スケジュール作成装置１は、キーボード等のオペレータの操作により情報が入力される装置，又は図示しない外部の装置からスケジュール作成のために必要な情報が入力される装置からなる入力装置１５を備えている。また、スケジュール装置１は、ＣＲＴディスプレイ等の表示装置，プリンタ装置，又は作成したスケジュールを図示しない外部の装置へ出力する装置からなる出力装置１６を備えている。
【０２１３】
なお、本発明のコンピュータプログラム２０は、スケジュール作成装置１に接続された図示しない外部のサーバ装置からスケジュール作成装置１へロードされて内部記憶装置１４に記憶される形態であってもよい。
【０２１４】
本発明のスケジュール作成装置１が行なう処理の目的は、作業プロセスの最適なスケジュールを作成することであり、より具体的には、オペレータが入力装置１５から入力した各種入力パラメータに基づいて、前述したＭＰＬシステムに適合する作業プロセスの状態を表現した式（数１２及び数１３）を、スケジュール作成装置１に作成させるＭＰＬ形式作成手順をコンピュータプログラムに含んでいる。
【０２１５】
また、このコンピュータプログラム２０には、前記ＭＰＬ形式作成手順の途中で導入された行列を利用して、システムの全工程における最早開始時刻及び最早終了時刻と、最遅開始時刻及び最遅入力時刻と、ＰＢの位置及び値と、ＦＢの位置及び値とをスケジュール作成装置１に決定させるスケジュール作成手順を含んでいる。さらに、このコンピュータプログラム２０には、クリティカルチェーン法を適用することで、前記スケジュール作成手順で決定した最早開始時刻及び最早終了時刻と、最遅開始時刻及び最遅入力時刻とが、どのように変化するのかをスケジュール作成装置１に決定させる再スケジュール作成手順を含んでいる。
【０２１６】
そして、このようなコンピュータプログラム２０を記憶した記憶媒体２を外部記憶手段１３に装着すると、スケジュール作成装置１のＣＰＵ１１は当該コンピュータプログラム２０をＲＡＭ１２に自動的にロードし、内蔵する上記各手順を処理実行する。つまりスケジュール作成装置１のＣＰＵ１１は、ソフトウェア上の機能として、オペレータが入力装置１５から入力した各種パラメータに基づいて、ＭＰＬシステムに適合する作業プロセスの状態を表現した式（数１２及び数１３）を作成するＭＰＬ形式作成手段３１と、前記ＭＰＬ形式作成手順の途中で導入された行列を利用して、システムの全工程における最早開始時刻及び最早終了時刻と、最遅開始時刻及び最遅入力時刻と、ＰＢ及びＦＢとを決定するスケジュール作成手段３２と、クリティカルチェーン法を適用することで、前記スケジュール作成手順で決定した最早開始時刻及び最早終了時刻と、最遅開始時刻及び最遅入力時刻とが、どのように変化するのかを決定する再スケジュール作成手段３３と、を備えている。
【０２１７】
（２−１）max-plus代数を用いたＭＰＬシステムについて
先ず始めに、スケジュール作成装置１は、スケジュールを作成しようとする作業プロセスについて、システム構造を表現するために、工程間の先行順序を表した先行制約関係情報と各工程の実行時間とからなる入力パラメータをオペレータにより入力装置１５を介して入力させる。具体的には、生産システムを構成する工程に対して、各工程の工程名と、各工程の加工時間（実行時間）となるＨＰ値と、先行制約関係情報とがパラメータとして入力装置１５を介して入力される。また、スケジュール作成装置１には、先行制約関係情報として、先行工程となる工程の番号と、入力を持つ工程の入力時間と、出力の有無を示す出力工程とが、オペレータによって入力装置１５を介して入力される
ＭＰＬ形式作成手段３１は、スケジュールを作成しようとする作業プロセスにおいて、ｋ番目の材料（ジョブ）について、各工程ｉ（但し、ｉは１以上の自然数で、１≦ｉ≦ｎ、ｎはシステムの全工程数を表す）の加工時間をｄｉ（ｋ）（≧０）とし、初期状態ｘ（０）＝εn1としたときに、システム構造を表現するために、入力された前記入力パラメータから、次の行列Ａ０ｋ，Ｆｋ，Ｂ０，及びＣ０ｋの各要素を算出し決定する（但し、例えば［Ａ０ｋ］ijは行列Ａ０ｋにおけるｉ行ｊ列での要素を表し、１≦[ｉ，ｊ]≦ｎ）。因みに、これら行列Ａ０ｋ，Ｆｋ，Ｂ０，及びＣ０ｋや、これらを利用した後述する最早開始時刻、最遅開始時刻などに関しては、本願発明者による先願（特開２００７−３３４８５５号公報）において既に提案されていることから、ここでは各行列や式の証明などについては詳しくは説明せず、その概略についてのみ説明する。
【０２１８】
【数９４】
2010198339.tif 000096
【０２１９】
【数９５】
2010198339.tif 000097
【０２２０】
【数９６】
2010198339.tif 000098
【０２２１】
【数９７】
2010198339.tif 000099
【０２２２】
行列Ａ０ｋは、工程数をｎとしたときに、ｎ次の正方行列で表され、その対角要素が各工程ｉの加工時間ｄｉ（ｋ）となり、それ以外の要素がεとなる。行列Ｆｋもｎ次の正方行列で表され、工程ｉが先行工程ｊを有するｉ行ｊ列の要素が、先行工程ｊの加工時間ｄｊ（ｋ）となり、それ以外の要素がεとなる。行列Ｂ０は、工程数に等しい行と、入力数に等しい列で表わされ、工程ｉが入力ｊを有する場合は、ｉ行ｊ列の要素がｅとなり、それ以外の要素はεとなる。さらに行列Ｃ０ｋは、出力数に等しい行と、工程数に等しい列で表わされ、工程ｊが入力ｉを有する場合は、ｉ行ｊ列の要素が工程ｊの加工時間ｄｊ（ｋ）となり、それ以外の要素はεとなる。
【０２２３】
スケジュール作成手段３２は、このように表現された行列Ａ０ｋ，Ｆｋ，Ｂ０，及びＣ０ｋを利用して、全ての工程について最早開始時刻及び最遅開始時刻を算出すると共に、この算出した最遅開始時刻から最早開始時刻を減算することで、全ての工程におけるトータルフロートの算出とクリティカルパスの抽出を行なうものである。なお、これ以降の説明では、全工程の最早開始時刻をｘＥとし、全工程の最遅開始時刻をｘＬとして表記すると共に、簡略化のために、必要に応じてイベントカウンタ（ｋ），ｋの記述（ｋ番目の材料（ジョブ）に対する加工を行っていることを示す記述）を省略する。
【０２２４】
ここでスケジュール作成手段３２が算出する最早開始時刻ｘＥは、その工程が最も早く加工を開始できる時刻として定義される。工程ｉ（１≦ｉ≦ｎ）の最早開始時刻ｘＥ（ｋ）は、次の式のように表わせる。
【０２２５】
【数９８】
2010198339.tif 000100
【０２２６】
ここで、生産システムの初期状態として、加工開始時刻をｘ（ｋ）とし、外部から入力される投入時刻をｕ（ｋ）とする。但し、この数９８における行列Ｆ＊ｋは、次の式に従って、ＭＰＬ形式作成手段３１により算出される。ＭＰＬ形式作成手段３１は、全ての要素がεになるまで、行列Ｆｋの累乗（Ｆ２ｋ，Ｆ３ｋ…）を逐次的に計算する。すなわち、次の式中にあるｌ（１＜ｌ＜ｎ）は、システムの先行制約条件に依存するものであり、全ての要素がεになるまで、行列Ｆｋの累乗が逐次的に計算される。なお、ｅｎはｎ行ｎ列のｅの対角行列を示す。また、ここでＦ２ｋ等の計算については、一般的な行列の乗算の定義には従わずに、上述した数１の定義に従って算出されるものである。
【０２２７】
【数９９】
2010198339.tif 000101
【０２２８】
また、このときの加工終了時刻、すなわち最早終了時刻は、次の式で与えられる。
【０２２９】
【数１００】
2010198339.tif 000102
【０２３０】
つまり、スケジュール作成手段３２は、前記ＭＰＬ形式作成手段３１で算出されてＲＡＭ１２に記憶された行列Ａ０ｋ，Ｂ０，Ｆ＊ｋを用いることで、数９８により全ての工程ｉにおける最早開始時刻ｘＥ（ｋ）を簡単に算出でき、またこの最早開始時刻ｘＥ（ｋ）と、ＭＰＬ形式作成手段３１で算出されてＲＡＭ１２に記憶された行列Ｃ０ｋとを用いることで、数１００によりシステムの最早終了時刻ｙＥ（ｋ）を簡単に算出できる。
【０２３１】
次に、スケジュール作成手段３２が算出する最遅開始時刻ｘＬについて説明すると、当該最遅開始時刻ｘＬ（ｋ）とは、ある工程において、最早開始時刻ｘＥ（ｋ）で加工を行なった場合と同一の出力時刻を実現することが可能な、最も遅い加工開始時刻として定義される。工程ｉ（１≦ｉ≦ｎ）の最遅開始時刻ｘＬ（ｋ）は、次の式のように表わせる。なお、ｙ（ｋ）は出力時刻（作業終了時刻）を示す。
【０２３２】
【数１０１】
2010198339.tif 000103
【０２３３】
つまり、スケジュール作成手段３２は、前記ＭＰＬ形式作成手段３１で算出されてＲＡＭ１２に記憶された行列Ａ０ｋ，Ｃ０ｋ，Ｆ＊ｋと、先にスケジュール作成手段３２により算出されてＲＡＭ１２に記憶された最早開始時刻ｘＥ（ｋ）及び出力時刻ｙ（ｋ）とを用いることで、数１０１により全ての工程ｉにおける最遅開始時刻ｘＬ（ｋ）を簡単に算出できる。
【０２３４】
さらに、最遅開始時刻ｘＬ（ｋ）に対応する最も遅い入力時刻である最遅入力時刻ｕＬ（ｋ）は、次の式のように計算できる。
【０２３５】
【数１０２】
2010198339.tif 000104
【０２３６】
スケジュール作成手段３２は、前記数９８や数１０１に基づいて算出してＲＡＭ１２に記憶された最早開始時刻ｘＥ（ｋ）と最遅開始時刻ｘＬ（ｋ）とを用いて、トータルフロートがゼロとなる経路を抽出することができる。トータルフロートとは、当該工程が持つ余裕時間の総合計で定義され、後続工程が出力時刻に影響を及ぼさない範囲で最も遅く加工を開始する場合の最遅開始時刻ｘＬ（ｋ）と、当該工程が最も早く加工を開始した場合の最早開始時刻ｘＥ（ｋ）との差で表わすことができる。従って、工程ｉ（１≦ｉ≦ｎ）のトータルフロートｗ（ｋ）は、最遅開始時刻ｘＬ（ｋ）から最早開始時刻ｘＥ（ｋ）を減算した次の式のように表わせる。
【０２３７】
【数１０３】
2010198339.tif 000105
【０２３８】
ここでクリティカルパスは、トータルフロートｗ（ｋ）が０になる工程の集合として与えられ、この条件を満たす工程の集合αについて数式で表わすと次のようになる。
【０２３９】
【数１０４】
2010198339.tif 000106
【０２４０】
つまり、スケジュール作成手段３２は、先に算出した最早開始時刻ｘＥ（ｋ）と最遅開始時刻ｘＬ（ｋ）とを用いて、数１０３や数１０４により全ての工程ｉにおけるトータルフロートｗ（ｋ）を簡単に抽出できると共に、入力から出力までの全工程のうち、どの工程がクリティカルパスとなっているのかを簡単に抽出できる。
【０２４１】
（２−２）ＰＢの位置及び値について
かかる構成に加えてスケジュール作成手段３２は、生産システムにおけるＰＢの位置を決定し得ると共に、ＰＢの値を算出し得るようになされている。ここでＰＢは、生産システムの各工程で遅延が生じることで、最終的に計画全体が遅延することを防止するための猶予時間であることから、クリティカルパス上の最終工程と出力との間に設置される。従って、ＰＢの位置は、最終工程を特定できる数９７に示す行列Ｃ０ｋから決定することができる。行列[Ｃ０ｋ]ｉｊの第（ｉ，ｎ）要素が有限値を持つ場合には、クリティカルパス上の工程は外部出力を持つ工程ｎの後方にＰＢを設置する。つまり、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で算出されてＲＡＭ１２に記憶された行列Ｃ０ｋを用いることで、ＰＢの位置を簡単に特定できる。
【０２４２】
また、ＰＢの値は、最早終了時刻ｙＥ（ｋ）の１／３の時間と定義され、次の式により算出することができる。これはＡＢＰが上述の数９２に示したように、統計的にＨＰの１／３まで短縮可能であるとされていることによる。
【０２４３】
【数１０５】
2010198339.tif 000107
【０２４４】
つまり、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で算出されてＲＡＭ１２に記憶された最早終了時刻ｙＥ（ｋ）を用いることで、ＰＢの値を簡単に算出できる。
【０２４５】
（２−３）ＦＢの位置及び値について
かかる構成に加えてスケジュール作成手段３２は、生産システムにおいてＦＢの位置を決定し、各ＦＢの位置における値を算出し得るようになされている。ここでＦＢは、非クリティカルパスからクリティカルパスへ合流する工程の集合による遅延によって、計画全体が遅延することを防止するための猶予時間であることから、非クリティカルパスからクリティカルパスに合流する合流点に設置される。このＦＢの位置は以下のようにして決定される。
【０２４６】
（２−３−１）ＦＢの位置
先ず始めに、スケジュール作成手段３２は、次の式に示すように、クリティカルパス上にある工程ｉの要素をｅとして表し、非クリティカルパス上にある工程ｉの要素をεと表した行列[ｗ´]ｉを求める。また、スケジュール作成手段３２は、行列[ｗ´]ｉとは逆に非クリティカルパス上にある工程ｉの要素をｅと表し、クリティカルパス上にある工程ｉの要素をεと表した行列[υ]ｉを求める。なお、以下、クリティカルパス上にある工程ｉの集合をαとし、非クリティカルパス上にある工程ｉの集合をβとして表す。
【０２４７】
【数１０６】
2010198339.tif 000108
【０２４８】
ここで行列[ｗ´]ｉは、上述したトータルフロートｗ（ｋ）が０になる要素をｅと表し、０でない他の要素をεと表すことにより求められる。また、行列[υ]ｉは、前記行列[ｗ]ｉにおいて決定されたｅ及びεの各要素を、逆のε及びｅの要素に変換することにより求められる。
【０２４９】
ところで行列Ｆｋについては、次の式に示すように、クリティカルパス上の工程間での遷移を表す行列Ｆααと、クリティカルパス上の工程から非クリティカルパス上の工程への遷移を表す行列Ｆαβと、非クリティカルパス上の工程からクリティカルパス上の工程への遷移を表す行列Ｆβαと、非クリティカルパス上の工程間での遷移を表す行列Ｆββとに分解することができる。
【０２５０】
【数１０７】
2010198339.tif 000109
【０２５１】
ここで行列Ｆαα，Ｆαβ，Ｆβα，Ｆββは、それぞれ次の式により算出することができる。なお、次の式中におけるdiagとは対角行列を意味する。
【０２５２】
【数１０８】
2010198339.tif 000110
【０２５３】
【数１０９】
2010198339.tif 000111
【０２５４】
【数１１０】
2010198339.tif 000112
【０２５５】
【数１１１】
2010198339.tif 000113
【０２５６】
ここで、非クリティカルパス上の工程の集合βのうち、次の工程がクリティカルパス上の工程となる工程については、上述した数１１０により算出した行列Ｆβαと、上述した数１０６により算出した行列ｗ´とに基づいて、次の式に示す行列υ´によって表すことができる。なお、この式におけるｋ´は１≦ｋ´≦ｎであり、ｌは１≦ｌ≦ｎである。
【０２５７】
【数１１２】
2010198339.tif 000114
【０２５８】
ここで上述した数１１２における行列ＦＴβαは、次の式のような性質を満たす（Ｔは転置行列を示す）。
【０２５９】
【数１１３】
2010198339.tif 000115
【０２６０】
そして、上述した数１１２は、ｌ∈αと、ｋ´∈αの条件を満たすとき、次の数１１４のように表すことができ、またｌ∈αと、ｋ´∈βの条件を満たすとき、次の数１１５のように表すことができ、さらにｌ∈βの条件を満たすとき、同じく次の数１１４のように表すことができる。なお、ここでｄｋ´は、非クリティカルパス上の工程の集合βのうち、次の工程がクリティカルパス上の工程となる工程ｋ´の加工時間を示すものである。
【０２６１】
【数１１４】
2010198339.tif 000116
【０２６２】
【数１１５】
2010198339.tif 000117
【０２６３】
そして、これら数１１２〜数１１５を要約すると、行列υ´は次の式のように表すことができる。なお、次の式では、非クリティカルパス上の工程の集合βのうち、次の工程がクリティカルパス上の工程となる工程ｋ´の集合をγとして表している（すなわちγ⊆β）。
【０２６４】
【数１１６】
2010198339.tif 000118
【０２６５】
つまり、スケジュール作成手段３２は、前記数１１０に基づいて算出した行列Ｆβαと、前記数１０６に基づいて算出した行列ｗ´とを用いて、前記数１１６から行列υ´を算出することにより、非クリティカルパス上の工程のうち、次の工程がクリティカルパス上の工程となる工程ｋ´を特定し得るようになされている。また、スケジュール作成手段３２は、非クリティカルパス上の工程の集合βのうち、次の工程がクリティカルパス上の工程となる工程ｋ´の加工時間ｄｋ´のみを抽出し得るようになされている。
【０２６６】
（２−３−２）ＦＢの値
次に、スケジュール作成手段３２は、各ＦＢの値を算出し得るようになされている。ここでＦＢの値は、クリティカルパスと非クリティカルパスとの分岐点から、当該非クリティカルパスとクリティカルパスとの合流点までにある非クリティカルパス上における全工程の加工時間の合計となり、次の式により算出することができる。
【０２６７】
【数１１７】
2010198339.tif 000119
【０２６８】
ここで、行列υは前記数１０６により算出したものであり、diag（υ´）の行列υ´は前記数１１６により算出したものである。また数１１７のうち行列Ｆ〜＊ββは次の式のように表せる。
【０２６９】
【数１１８】
2010198339.tif 000120
【０２７０】
上の式中にある行列Ｆ〜ββは次の式のように表せる。この行列Ｆ〜ββは、数１１１において、非クリティカルパス上の工程からＦＢを介在して非クリティカルパス上の工程へと遷移する経路において、ＦＢ前までの経路を削除したときの非クリティカルパス上の工程間の遷移を表す行列である（例えば図２において工程（３），（５）の経路にうち、クリティカルパスへ遷移する工程（３）を削除した工程（５）を示す）。
【０２７１】
【数１１９】
2010198339.tif 000121
【０２７２】
但し、ここでのｐは、数１１１の行列Ｆββと、数１１６の行列υ´とを用いて次のように表される。なお、このｐは、前の工程にＦＢを持つ非クリティカルパス上の工程の集合を表している。
【０２７３】
【数１２０】
2010198339.tif 000122
【０２７４】
ここで上述した数１１９における演算子♯は数１２１のように定義される。従って、行列ｐ♯は、各工程の実際の加工時間を含んだ行列ｐの要素を単にεとｅとにより表すものである。
【０２７５】
【数１２１】
2010198339.tif 000123
【０２７６】
つまり、スケジュール作成手段３２は、ＲＡＭ１２に記憶された数１１１で表される行列Ｆββと、数１１６で表される行列υ´とを用いて数１２０及び数１２１に基づきdiag（ｐ♯）を算出した後、数１１９及び数１１８を基に行列Ｆ〜＊ββを算出する。これによりスケジュール作成手段３２は、算出したdiag（υ´）と行列Ｆ〜＊ββと行列υとに基づいて数１１７により行列ＦＢを算出することができる。この行列ＦＢは、ε以外の有限値の要素が各ＦＢの位置での値となる。
【０２７７】
（３）生産システムにおけるＰＢ及びＦＢの具体的な一例
次に、上述したＰＢ及びＦＢの位置を決定し、ＰＢ及びＦＢの値を算出するまでの一連の処理について、図１に示すような生産システムＳＴ１と、図４に示すフローチャートとを用いて具体的に説明する。実際上、スケジュール作成装置１のＣＰＵ１１は、ルーチンＲＴ１の開始ステップから入ってステップＳＰ１に移る。ステップＳＰ１においてＣＰＵ１１は、生産システムＳＴ１の構造を表現するための入力パラメータを、入力装置１５を介して取得し、次のステップＳＰ２及びステップＳＰ７に移る。
【０２７８】
この実施の形態の場合では、生産システムＳＴ１の構造を表現するために、下記の表１に示すような入力リストに沿って入力パラメータが入力され、内部記憶装置１４に記憶させる。例えば、入力リストには、生産システムＳＴ１を構成する各工程（１）〜（７）を識別するための工程名が入力される工程名欄と、各工程（１）〜（７）毎に設定された作業時間ｄ１〜ｄ７が入力されるＨＰ値欄と、先行の工程（２）〜（６）の有無が工程番号により入力される先行工程欄と、入力のある工程（１）の材料受け取り時間が入力される入力時間欄と、最終の工程（７）から材料が出力されることを示す出力工程欄とが設けられている。また、入力リストでは、入力から出力に向けて順番に各工程に工程番号が付されており、工程名欄、ＨＰ値欄、先行工程欄、入力時間欄及び出力工程欄が、工程番号毎に対応付けられている。スケジュール作成装置１は、入力リストの各欄にこれらパラメータが入力されることにより、図１に示すような生産システムＳＴ１の構造が表現されるようになされている。
【０２７９】
【表１】
2010198339.tif 000124
【０２８０】
ステップＳＰ２においてＭＰＬ形式作成手段３１は、入力された入力パラメータに基づいて各工程（１）〜（７）の加工時間ｄ１〜ｄ７を示す行列Ａ０ｋ−１と、先行工程の有無を示す行列Ｆと、入力を持つ工程（１）を示す行列Ｂ０と、出力を持つ工程（７）を示す行列Ｃ０とを決定し、次のステップＳＰ３へ移る。ここで、具体的に行列Ａ０ｋ−１は、生産システムＳＴ１が工程（１）〜（７）によって構成されていることから、工程番号１〜７の順に７行７列（１≦ｉ≦７、１≦ｊ≦７）の正方行列で表される対角行列(diagonal matrix)となり、その対角要素に各工程（１）〜（７）の加工時間ｄ１〜ｄ７が割り当てられ、それ以外の要素にεが割り当てられる。なお、次式の行列Ａ０ｋ−１については、ｋ−１番目の材料に関して着目して作成されていることを示す添え字ｋ−１が表記されているが、図４や他の行列Ｆ，Ｂ０，Ｃ０などについてｋは省略する。
【０２８１】
【数１２２】
2010198339.tif 000125
【０２８２】
また、ＭＰＬ形式作成手段３１は、入力リストの先行工程欄及びＨＰ値欄と、前記数９５とに基づいて先行工程の有無を示す行列Ｆを次の式のように決定する。すなわち、行列Ｆは、生産システムＳＴ１が工程（１）〜（７）によって構成されていることから、工程番号１〜７の順に７行７列で表され、工程数に対応した行が設けられ、列に各工程（１）〜（７）の先行工程の加工時間ｄ１〜ｄ６が表される。例えば、行列Ｆの２行目は、工程番号２である工程（２）の先行工程の情報が示されており、先行工程である工程（１）の加工時間３が２行１列に示され、それ以外の要素にεが示される。
【０２８３】
【数１２３】
2010198339.tif 000126
【０２８４】
また、ＭＰＬ形式作成手段３１は、入力リストの入力時間欄と前記数９６とに基づいて行列Ｂ０を次の式のように決定する。行列Ｂ０は、工程数に等しい行と、入力数に等しい列で表わされる。従って、図１に示す生産システムＳＴ１では、工程番号１の工程（１）のみが入力を持つことから、工程番号１に対応する１行目が、入力を有することを示すｅとなり、それ以外がεとなる。
【０２８５】
【数１２４】
2010198339.tif 000127
【０２８６】
さらに、ＭＰＬ形式作成手段３１は、入力リストの出力工程欄等と前記数９７とに基づいて行列Ｃ０を次の式のように決定する。行列Ｃ０は、出力数に等しい行と、工程数に等しい列で表わされる。従って、図１に示す生産システムＳＴ１では、工程番号７の工程（７）のみが出力を持つことから、工程番号７に対応する７行目のみが当該工程番号７の加工時間６となり、それ以外がεとなる。
【０２８７】
【数１２５】
2010198339.tif 000128
【０２８８】
続いてＭＰＬ形式作成手段３１は、全ての要素がεになるまで、前記行列Ｆの累乗（Ｆ２，Ｆ３…）を逐次的に計算する。この生産システムＳＴ１の例では、結局、行列Ｆ＊は次の式のように計算される。
【０２８９】
【数１２６】
2010198339.tif 000129
【０２９０】
ステップＳＰ３においてスケジュール作成手段３２は、ステップＳＰ２において決定した行列Ａ０ｋ−１，Ｆ，Ｂ０，Ｃ０，Ｆ＊を用いて、前記数９８及び数１００に基づき全工程（１）〜（７）の最早開始時刻ｘＥ（ｋ）と最早終了時刻ｙＥ（ｋ）とを算出し、次のステップＳＰ４に移る。ここで、この実施の形態の場合、スケジュール作成手段３２は、生産システムＳＴ１の初期状態として、加工開始時間をｘ（ｋ）＝ε７１とし、外部入力の時刻をｕ（ｋ）＝０とすると、最早開始時刻ｘＥと最早終了時刻ｙＥとを次の式から算出することができる。
【０２９１】
【数１２７】
2010198339.tif 000130
【０２９２】
スケジュール作成手段３２は、これら算出した最早開始時刻ｘＥと、最早終了時刻ｙＥと、入力リストのＨＰ値とを基に次の表２のような出力リストを作成し得るようになされている。スケジュール作成手段３２は、各工程（１）〜（７）毎に付した工程番号１〜７に対して最早開始時刻ｘＥと最早終了時刻ｙＥとを対応付けた出力リストを、出力装置１６に出力させることが可能である。
【０２９３】
【表２】
2010198339.tif 000131
【０２９４】
ステップＳＰ４においてスケジュール作成手段３２は、前述の数１０１及び数１０２をそれぞれ用いて、全工程（１）〜（７）の最遅開始時刻ｘＬ及び最遅入力時刻ｕＬをそれぞれ次の式のように算出し、次のステップＳＰ５に移る。
【０２９５】
【数１２８】
2010198339.tif 000132
【０２９６】
この場合、工程（１）〜（７）の最遅開始時刻ｘＬは、それぞれ０，３，６，９，１８，１８，２１であり、入力の最遅入力時刻ｕＬは０である。
【０２９７】
ステップＳＰ５においてスケジュール作成手段は、数１０３を用いて、全工程（１）〜（７）のトータルフロートｗを次の式のように算出して、当該トータルフロートｗに基づいてクリティカルパスを特定し、次のステップＳＰ６に移る。なお、ここではイベントカウンタ（ｋ）については省略している。
【０２９８】
【数１２９】
2010198339.tif 000133
【０２９９】
この場合、工程（１）〜（７）のトータルフロートｗは、それぞれ０，０，３，０，９，１２，０であり、このことから工程（３），（５），（６）は、それぞれ余裕時間があることが分かる。スケジュール生成手段３２は、前記数１２９で得た結果から、トータルフロートｗが０である工程、即ち遅れ時間が許されない工程（１），（２），（４），（７）を、クリティカルパス上の工程の集合{１，２，４，７}として抽出することができる。
【０３００】
ステップＳＰ６においてスケジュール作成手段３２は、ＰＢ及びＦＢの位置を決定すると共に、ＰＢ及びＦＢの値を算出し、次のステップＳＰ７に移る。実際上、スケジュール作成手段３２は、前記数１２５の行列Ｃ０によって工程（７）が最終工程であると判別し、図２に示すように、当該工程（７）の後ろがＰＢを設置する位置であると決定する。また、スケジュール作成手段３２は、前記数１０５を基にＰＢの値ｄＰＢ（図２）として「９」を算出する。さらに、スケジュール作成手段３２は、前記数１０６に基づいて次の式のように行列υ及び行列ｗ´を決定する。
【０３０１】
【数１３０】
2010198339.tif 000134
【０３０２】
次いで、スケジュール作成手段３２は、前記数１１０及び数１１３に基づいて行列ＦＴβαを算出して、これら行列ｗ´，ＦＴβαを用いて前記数１１６から行列υ´を次の式のように算出する。
【０３０３】
【数１３１】
2010198339.tif 000135
【０３０４】
この行列υ´は、有限値となった要素に対応した工程（３），（５），（６）が、非クリティカルパス上にあり、かつ次の工程がクリティカルパス上の工程となる集合γであることを意味している。よって、スケジュール作成手段３２は、行列υ´の有限値となった要素に基づいて、図２に示すように、工程（３），（５），（６）の後がＦＢ３，ＦＢ５，ＦＢ６の設置位置であると決定する。
【０３０５】
次いで、スケジュール作成手段３２は、ＦＢ３，ＦＢ５，ＦＢ６の値を算出するために、前記数１１１を基に行列Ｆββを算出した後、この行列Ｆββと前記数１３１の行列υ´とを用いて、前記数１２０から行列ｐを算出する。次いでスケジュール作成手段３２は、前記数１２１の定義に従って行列ｐをdiag（ｐ♯）に変換し、diag（ｐ♯）と、前記行列Ｆββとを用いて前記数１１９及び数１１８から行列Ｆ〜＊ββを算出して、前記数１１７に基づいて次の式のような行列ＦＢを算出する。
【０３０６】
【数１３２】
2010198339.tif 000136
【０３０７】
かくして、スケジュール作成手段３２は、前記数１３２で得た結果から、行列ＦＢの有限値に基づいてＦＢ３，ＦＢ５，ＦＢ６の値ｄＦＢ３，ｄＦＢ５，ｄＦＢ６（図２）として「１」を抽出することができる。このようにしてスケジュール作成手段３２は、ＰＢの位置及び値ｄＰＢと、ＦＢの位置及び値ｄＦＢ３，ｄＦＢ５，ｄＦＢ６とをそれぞれ算出すると、次のサブルーチンＳＲＴ２へ移る。
【０３０８】
このとき、ステップＳＰ２〜ステップＳＰ６と並行して実行されるステップＳＰ７において、再スケジュール作成手段３３は、各工程の加工時間が１／３まで短縮可能であるとのクリティカルチェーン法の理論に基づいて、各工程（１）〜（７）の加工時間ｄ１〜ｄ７をそれぞれ１／３としたＡＢＰを前記数９２に基づいて算出し、次のサブルーチンＳＲＴ２に移る。
【０３０９】
サブルーチンＳＲＴ２において、再スケジュール作成手段３３は、後述する再スケジュール作成処理を実行することにより、表１の入力リストと表２の出力リストとを更新し、ＡＢＰや、ＰＢ、ＦＢに基づいて計画全体を短縮化させた新たなスケジュールを作成し、次のステップＳＰ８に移り、上述した処理を終了する。
【０３１０】
（４）再スケジュール作成処理
次に、再スケジュール作成処理について、図２における生産システムＳＴ２を一例とし、図５に示すフローチャートを用いて以下説明する。再スケジュール作成手段３３は、ルーチンＲＴ２の開始ステップから入ってステップＳＰ１１に移る。ステップＳＰ１１において再スケジュール作成手段３３は、次の表３に示すように、表１に示した入力リストのうち各工程（１）〜（７）のＨＰ値をＡＢＰの値に更新して、次のステップＳＰ１２に移る。
【０３１１】
【表３】
2010198339.tif 000137
【０３１２】
ステップＳＰ１２において再スケジュール作成手段３３は、ＰＢの追加のために新たに工程番号８の欄を入力リストに追加すると共に、当該工程番号８の欄における工程名欄、ＨＰ値欄、先行工程欄、入力時間欄及び出力工程欄にそれぞれＰＢに関する各種情報を追加して当該入力リストを更新し、次のステップＳＰ１３に移る。すなわち、再スケジュール作成手段３３は、表３に示すように、工程番号８の欄に対して、工程名欄を「ＰＢ」とし、ＰＢの値ｄＰＢである「９」をＨＰ値欄に追加し、ＰＢの先行工程となる工程（７）を示す工程番号７を先行工程欄に追加する。また、再スケジュール作成手段３３は、ＰＢを追加する前に最終工程であった工程（７）の出力工程欄を、最終工程でないことを示す「Ｎ」に変更すると共に、ＰＢの工程番号８の欄における出力工程欄に「Ｙ」を表記し、ＰＢが最終工程であることを表す。なお、このＰＢは、入力を持たないため、入力時間欄に入力を持たないことを示す「−」が付される。
【０３１３】
ステップＳＰ１３において再スケジュール作成手段３３は、ＦＢ３，ＦＢ５，ＦＢ６の追加のために新たに工程番号９、１０及び１１の欄を入力リストに追加すると共に、当該工程番号９、１０及び１１の各欄において工程名欄、ＨＰ値欄、先行工程欄、入力時間欄及び出力工程欄にそれぞれＦＢ３，ＦＢ５，ＦＢ６に関する各種情報を追加する等して当該入力リストを更新し、次のステップＳＰ１４に移る。
【０３１４】
すなわち、再スケジュール作成手段３３は、工程番号９の欄に対して、工程名欄を「ＦＢ３」とし、ＦＢ３の値ｄＦＢ３である「１」をＨＰ値欄に追加し、ＦＢ３の先行工程となる工程（３）を示す工程番号３を先行工程欄に追加する。また、再スケジュール作成手段３３は、工程番号１０の欄に対して、工程名欄を「ＦＢ５」とし、ＦＢ５の値ｄＦＢ５である「１」をＨＰ値欄に追加し、ＦＢ５の先行工程となる工程（５）を示す工程番号５を先行工程欄に追加する。さらに、再スケジュール作成手段３３は、工程番号１１の欄に対して、工程名欄を「ＦＢ６」とし、ＦＢ６の値ｄＦＢ６である「１」をＨＰ値欄に追加し、ＦＢ６の先行工程となる工程（６）を示す工程番号６を先行工程欄に追加する。なお、ＦＢ３，ＦＢ５，ＦＢ６については、入力を持たないため、入力時間欄に「−」が付され、また最終工程でないため、出力工程欄に最終工程でないことを示す「Ｎ」が付される。
【０３１５】
また、再スケジュール作成手段３３は、ＦＢ３，ＦＢ５，ＦＢ６を追加したことにより、工程（４）〜（７）の先行工程が変更することから、ＰＢ，ＦＢ３，ＦＢ５，ＦＢ６の先行工程欄の情報に基づき、工程（４）〜（７）の先行工程欄を修正する。例えば工程（４）では、更新前において先行工程欄に工程（２），（３）の工程番号２，３が表記されているが、ＦＢ３が追加されることにより、先行工程が工程（２），ＦＢ３となり、当該工程（２），ＦＢ３を示す工程番号２，９に先行工程欄を変更する。
【０３１６】
このようにして再スケジュール作成手段３３は、表３に示すように、工程（１）〜（７）の各先行工程欄について、ＰＢ，ＦＢ３，ＦＢ５，ＦＢ６の先行工程欄に表記された工程番号７，３，５，６を先行工程としている工程（４）〜（７）の各先行工程欄を、先行工程となるＰＢ，ＦＢ３、ＦＢ５又はＦＢ６の工程番号８，９，１０，１１に変更する。
【０３１７】
これに加えて再スケジュール作成手段３３は、ＰＢ，ＦＢ３，ＦＢ５，ＦＢ６を追加した全工程に対して、先行工程欄を基に入力から出力までの経路に沿って改めて工程番号を順番に付してゆき、工程番号を更新する。この実施の形態の場合、工程番号１，２，３については、先行工程が変更されないことから、更新後においても工程番号１´，２´，３´となる。なお、更新後の新たな工程番号については「´」を付して表す。工程番号４〜７は、先行工程が変更されることから、新たな工程番号が付される。このうち工程番号４〜６では、先行工程欄に追加されたＦＢ３の工程番号９を優先し、当該工程番号９に対して工程番号４´が新たに付される。これにより工程（４），（５），（６）は工程番号が５´，６´，７´となる。
【０３１８】
また、工程（７）の先行工程欄には、工程番号１０，１１が表記されていることから、当該工程番号１０，１１のＦＢ５，ＦＢ６が工程（７）よりも優先されて工程番号が付される。ここでＦＢ５は、先行工程欄が工程番号５であることから、ＦＢ６における先行工程欄の工程番号６よりも先であることから、ＦＢ５を優先して新たに工程番号８´を付し、次いでＦＢ６に工程番号９´を付す。最後に、ＰＢの先行工程である工程（７）に対して工程番号１０´を付すと共に、ＰＢに対して工程番号１１´を付す。
【０３１９】
このようにして再スケジュール作成手段３３は、表３に示すように、工程（１）〜（７）、ＰＢ、ＦＢ３、ＦＢ５及びＦＢ６に対して入力から出力に沿った順番で工程番号１´〜１１´を新たに付し直すようになされている。なお、各先行工程欄についても新たな工程番号１´〜１１´に変更され得る。
【０３２０】
ステップＳＰ１４において再スケジュール作成手段３３は、表３に示す更新された入力リストにおける新たに付された工程番号１´〜１１´を基に、ステップＳＰ２と同様にして行列Ａｃｋ−１０，Ｆｃ，Ｂｃ０，Ｃｃ０を決定すると共に、行列Ｆｃ＊を算出し、次のステップＳＰ１５に移る。なお、行列Ａｃｋ−１０，Ｆｃ，Ｂｃ０，Ｃｃ０，Ｆｃ＊において付されている添え字ｃは、ＰＢ，ＦＢ３，ＦＢ５，ＦＢ６を新たに追加したことにより更新された入力リスト（表３）を用いて、行列Ａｋ−１０，Ｆ，Ｂ０，Ｃ０，Ｆ＊の各要素が決定されたことを示すものである。
【０３２１】
この実施の形態の場合、行列Ａｃｋ−１０，Ｆｃ，Ｂｃ０，Ｃｃ０，Ｆｃ＊は、新たに付された工程番号１´〜１１´の順番に要素が決定されることにより次の式のようになる。
【０３２２】
【数１３３】
2010198339.tif 000138
【０３２３】
【数１３４】
2010198339.tif 000139
【０３２４】
【数１３５】
2010198339.tif 000140
【０３２５】
【数１３６】
2010198339.tif 000141
【０３２６】
例えば、行列Ａｃｋ−１０では、新たに付された工程番号１´〜１１´を基に、工程（１）〜（３）、ＦＢ３、工程（４）〜（６）、ＦＢ５、ＦＢ６、工程（７）及びＰＢの順に各加工時間の配列が決定される。また行列Ｆｃは、新たに付された工程番号１´〜１１´を基に、工程（１）〜（３）、ＦＢ３、工程（４）〜（６）、ＦＢ５、ＦＢ６、工程（７）及びＰＢの順に先行工程の有無を示す１１行１１列の行列となる。例えば、行列Ｆｃの１１行目には、工程番号１１´であるＰＢの先行工程の情報が示され、先行工程となる工程番号１０´（工程（７））のＡＢＰの加工時間２が１１行１０列の要素となり、それ以外の要素がεとなる。また、行列Ｂｃ０，Ｃｃ０についても、新たに付された工程番号１´〜１１´を基に、工程（１）〜（３）、ＦＢ３、工程（４）〜（６）、ＦＢ５、ＦＢ６、工程（７）及びＰＢの順番に決定される。行列Ｆｃ＊は、行列Ｆｃを利用して前記数９９から算出される。
【０３２７】
ステップＳＰ１５において再スケジュール作成手段３３は、ステップＳＰ１４において決定した行列Ａｃｋ−１０，Ｆｃ，Ｂｃ０，Ｃｃ０，Ｆｃ＊を用いて、前記数９８及び数１００に基づき全工程の最早開始時刻ｘｃＥと最早終了時刻ｙｃＥとをそれぞれ次の式のように算出し、次のステップＳＰ１６に移る。
【０３２８】
【数１３７】
2010198339.tif 000142
【０３２９】
そして、再スケジュール作成手段３３は、これら最早開始時刻ｘｃＥと、最早終了時刻ｙｃＥと、更新した入力リスト（表３）のＨＰ値（ＡＢＰ）とを基に次の表４のような出力リストを新たに作成し得るようになされている。これにより再スケジュール作成手段３３は、工程番号１´〜１１´に対し最早開始時刻ｘｃＥと最早終了時刻ｙｃＥとを対応付けた出力リストを、出力装置１６に出力させることが可能となる。
【０３３０】
【表４】
2010198339.tif 000143
【０３３１】
かくして最早開始時刻ｘｃＥは、従来のスケジューリング法における最早開始時刻ｘＥの１／３の時間に短縮させることができると共に、最早終了時刻ｙｃＥは、従来のスケジューリング法における最早終了時刻ｙＥの２／３の時間に短縮できる。つまり、このスケジュール作成装置１では、数９４〜数９７及び数９９で定義された行列Ａ０，Ｆ，Ｂ０，Ｃ，Ｆ＊の各要素を、ＡＢＰやＰＢ、ＦＢを用いて再び決定し、その結果得られた行列Ａｃ０，Ｆｃ，Ｂｃ０，Ｃｃ０，Ｆｃ＊からＭＰＬシステムの形式に基づく数１２の行列Ａ，Ｂを算出できるように、前記ＭＰＬ形式作成手段３１を構成すれば、数１２及び数１３にて記述されるＭＰＬ形式での状態空間表現を取得することができる。そして、この数１２及び数１３を利用して、生産システムの各工程の加工時間を短縮させつつ、計画全体としての遅れを防止したスケジュール作成を行なうことが可能になる。
【０３３２】
次に、ステップＳＰ１６において再スケジュール作成手段３３は、前述数１０１及び数１０２を用いて、全工程ｉの最遅開始時刻ｘｃＬ及び最遅入力時刻ｕｃＬをそれぞれ次の式のように算出し、次のステップＳＰ１６に移り、上述した処理を終了する。
【０３３３】
【数１３８】
2010198339.tif 000144
【０３３４】
この場合、工程番号１´〜１１´の工程（１）〜（３）、ＦＢ３、工程（４）〜（６）、ＦＢ５、ＦＢ６、工程（７）及びＰＢの各最遅開始時刻ｘｃＬは、それぞれ０，１，１，２，３，５，５，６，６，７，９であり、入力の最遅入力時刻ｕｃＬは０である。これにより再スケジュール作成手段３３は、数１０３を用いて、新たに全工程のトータルフロートｗｃを次の式のように算出して、当該トータルフロートｗｃに基づいてボトルネック工程やクリティカルパスの抽出を行うことができる。
【０３３５】
【数１３９】
2010198339.tif 000145
【０３３６】
この場合、工程（１）〜（３）、ＦＢ３、工程（４）〜（６）、ＦＢ５、ＦＢ６、工程（７）及びＰＢのトータルフロートｗｃは、それぞれ０，０，０，０，０，２，２，２，２，０，０であり、工程（１）〜（３），ＦＢ３，工程（４），工程（７），ＰＢは、それぞれ余裕時間があることが分かる。再スケジュール生成手段３３は、数１３９で得た結果から、トータルフロートｗｃが０である工程、即ち遅れ時間が許されない工程（１），（２），（４），（７），ＰＢと、工程（１），（３），ＦＢ３，（４），（７），ＰＢを、クリティカルパス上の工程の集合{１，２，４，７，ＰＢ}及び{１，３，ＦＢ３，４，７，ＰＢ}として、またボトルネック工程として抽出することができる。
【０３３７】
このように、本実施例における再スケジュール作成手段３３は、各工程の加工時間が１／３に短縮され、新たにＰＢ、ＦＢを追加されたのを受けて、数１３７に基づいて、更新後の最早開始時刻ｘｃＥを算出する。そして、数１３７及び数１３８に基づいて、更新後の最早終了時刻ｙｃＥ及び最遅開始時刻ｘｃＬを各々算出し、さらに数１３９に基づいて、ボトルネック工程やクリティカルパスの抽出を行なうようにしている。これによって、例えばシステムの稼動中にクリティカルチェーン法を適用して計画期間の短縮を図る場合でも、システムの各工程ｉ毎に最早開始時刻ｘｃＥや最早終了時刻ｙｃＥ、最遅開始時刻ｘｃＬの算出と、それにより得られる更新後のボトルネック工程やクリティカルパスを適確に抽出することができる。
【０３３８】
（５）動作及び効果
以上のように本実施例では、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理してゆき、その処理結果を出力に送り出す離散事象システムの状態を数１２及び数１３の式で表現するために、前記処理対象（材料、部品、ジョブ）を受け渡す前記各工程ｉの実行順序を表した先行制約関係情報と、前記各工程ｉにおける実行時間ｄｉとからなる入力パラメータを、max-plus代数上で線形なＭＰＬ形式に演算部（ＣＰＵ１１）が変換するスケジュール作成装置１において、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄｉ（ｋ）としたときに、前記入力パラメータに基づいて各要素をそれぞれ決定した、前記数９４〜数９７で定義されたシステム構造を表現する行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である。ｋはｋ番目の前記処理対象の工程処理であることを表す。）と、前記数９９の行列Ｆ＊とを用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記各工程の実行時間を短縮したことによる遅れを防止するための猶予時間であるＰＢの位置を決定すると共に、前記ＰＢの値を算出する。
【０３３９】
また、スケジュール作成装置１では、前記離散事象システムにおける前記入力から前記出力までの複数の経路のうち、前記入力から前記出力までに要する時間が最長となる経路をクリティカルパスとし、それ以外の経路を非クリティカルパスとして前記数１０６でシステム構造を表現する行列υ，ｗ´（但し、［Ｘ］iは行列Ｘにおけるｉ行の要素である）を算出し、該行列υ，ｗ´と前記行列Ｆｋとを用い、前記max-plus代数の定理を利用した所定の演算処理を実行することで、前記非クリティカルパス上の工程による遅れを防止するための猶予時間であるＦＢの位置を決定すると共に、前記ＦＢの値を算出するように、スケジュール作成手段３２を構成した。
【０３４０】
このようなスケジュール作成装置１，スケジュール作成方法，及びコンピュータプログラム２０では、例えばシステムの稼動中にクリティカルチェーン法を適用して計画期間の短縮を図る場合でも、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を利用して、当該クリティカルチェーン法を適用した際に用いるＰＢ及びＦＢの位置及び値を簡単に取得することができる。従って、与えられたシステムをＭＰＬシステムとして、より少ないメモリ消費で表現できる形式に対してクリティカルチェーン法を適用可能とし、処理時間の不確定性が高い場合にも納期遅れを出さず、かつ納期短縮を図り得るスケジュール作成方法、スケジュール作成装置１及びコンピュータプログラムを提供することが可能となる。
【０３４１】
また、スケジュール作成装置１では、前記行列Ａ０ｋ，Ｂ０，及びＦ＊ｋと、前記処理開始時刻ｘ（ｋ−１）及び前記入力時刻ｕ（ｋ）とを利用し、前記数９８に基づき最早開始時刻ｘＥ（ｋ）を算出し、前記行列Ｃ０ｋと前記最早開始時刻ｘＥ（ｋ）とを用いて次の数１００により前記最早終了時刻ｙＥ（ｋ）を算出する演算部としてのスケジュール作成手段３２を備えている。
【０３４２】
こうすれば、スケジュール作成装置１では、行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を用いて算出された、前記各工程で前記処理対処の処理を最も早く終了させたときの出力での最早終了時刻ｙＥ（ｋ）を利用して、前記max-plus代数の定理を利用した前記数１０５に基づきＰＢの値を、演算部としてのスケジュール作成手段３２により簡単に取得することができる。
【０３４３】
また、スケジュール作成装置１では、前記行列Ｃ０の各要素のうち、前記実行時間ｄｉ（ｋ）となった要素に対応した前記工程ｊを基に、該工程ｊの次工程がＰＢの設置位置であると容易に決定することができる。
【０３４４】
また、スケジュール作成装置１では、前記行列υ，ｗ´，Ｆｋを用い、前記max-plus代数の定理を利用した前記数１１０に基づき行列Ｆβαを算出し、前記行列ｗ´と前記行列Ｆβαとに基づいて、前記max-plus代数の定理を利用した前記数１１２により行列υ´を算出し、前記行列υと前記行列Ｆｋとを基に前記max-plus代数の定理を利用した前記数１１１と前記数１２０に基づいて行列ｐを算出する演算部としてのスケジュール作成手段３２を備えている。
【０３４５】
このスケジュール作成手段３２は、続いて、前記行列ｐの要素を前記数１２１の定義に従ってεとｅとに置き換えた行列ｐ♯と、前記行列Ｆββとから前記max-plus代数の定理を利用した前記数１１９を基に行列Ｆ〜ββを算出し、前記行列Ｆ〜ββを基に前記max-plus代数の定理を利用した前記数１１８から行列Ｆ〜＊ββを算出し、前記行列υ´と前記行列Ｆ〜＊ββと前記行列υとを基に前記max-plus代数の定理を利用した次の数１１７によりＦＢの値を抽出した行列ＦＢを算出する。
【０３４６】
こうすればスケジュール作成装置１では、例えばシステムの稼動中にクリティカルチェーン法を適用して計画期間の短縮を図る場合でも、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，Ｆ＊を利用して、当該クリティカルチェーン法を適用する際に用いるＦＢの値を簡単に取得することができる。
【０３４７】
また、スケジュール作成装置１では、各工程の実行時間を１／３に短縮した短縮実行時間を算出し、入力パラメータにＰＢの値とＦＢの値とを追加し、かつ各工程の短縮実行時間を用いて、行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋ，の各要素を決定し、さらにここで決定した行列Ｆから行列Ｆ＊を算出することにで、クリティカルチェーン法を適用しつつ、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ０ｋ，Ｆｋ，Ｂ０，Ｃ０ｋを簡単に取得することができる。
【０３４８】
なお、本発明は上記実施例に限定されるものではなく、本発明の要旨の範囲において種々の変形実施が可能である。例えば、実施例中では、複数の工程からなる生産システムを例として採用したが、タスクに順序制約を有するプロジェクト管理などを含むあらゆるシステムや、プロジェクトスケジューリング問題や、物流システムの配送計画問題などにも、そのまま適用が可能である。また、入力や出力が複数箇所存在するような、いわゆるＭＩＭＯ（Multiple Input Multiple Output）型構造を有するシステムへの適用も可能であり、従来知られているＰＥＲＴ（Program Evaluation and Review Technique）による方法よりも、適用範囲が広いことを意味する。
【０３４９】
また、上述した実施の形態においては、クリティカルチェーン法におけるＡＢＰは統計的にＨＰの１／３まで短縮可能であることから、各工程の実行時間を１／３に短縮した短縮実行時間を適用し、かつ前記数１０５と前記数１１７の式中においても、それぞれ１／３の数字を用いるようにした場合について述べたが、本発明はこれに限らず、この他種々の数字を適用してもよい。この場合、前記各工程の実行時間を１／ｑ（ｑは任意の数字）に短縮した短縮実行時間を適用した場合には、前記数１０５と前記数１１７はそれぞれ次の数１４０のように表すことができる。
【０３５０】
【数１４０】
2010198339.tif 000146
【符号の説明】
【０３５１】
１  スケジュール作成装置（コンピュータ）
１１  ＣＰＵ（演算部）
１２  ＲＡＭ（記憶部）
１６  入力装置（取込部）
２０  コンピュータプログラム
【図１】
2010198339.tif 000255
【図２】
2010198339.tif 000256
【図３】
2010198339.tif 000257
【図４】
2010198339.tif 000258
【図５】
2010198339.tif 000259
【図６】
2010198339.tif 000260