(57)【要約】【課題】より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に簡単に導出できるようにする。【解決手段】入力パラメータとして、各工程ｉの実行時間ｄiと工程ｉ間の先行制約関係の各情報をスケジュール作成装置１のＲＡＭ１２に記憶する。スケジュール作成装置１は、この入力パラメータに基づき、独自のシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素を決定し、さらにここで決定した行列Ｆから行列Ｆ*を算出して、簡単にmax-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ0，Ｆ*，Ｂ0，Ｃを取得する。【選択図】図１
2007334855.tif 000002
【特許請求の範囲】
【請求項１】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数１〜数４で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ前記演算部で決定する第１のステップと、
【数１】
2007334855.tif 000232
【数２】
2007334855.tif 000233
【数３】
2007334855.tif 000234
【数４】
2007334855.tif 000235
前記行列Ｆを用いて、次の数５の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を前記演算部で算出する第２のステップと、
【数５】
2007334855.tif 000236
を順次実行することを特徴とするスケジュール作成方法。
【請求項２】
ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１及び第２のステップで算出した行列Ａ0，Ｂ0，及びＦ*と、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）及び入力時刻ｕ（ｋ）とを利用して、次の数６に基づき工程の最早開始時刻ｘEを前記演算部で算出する第３のステップをさらに備えたことを特徴とする請求項１記載のスケジュール作成方法。
【数６】
2007334855.tif 000237
【請求項３】
前記第１および第２のステップで算出した行列Ｃ及びＦ*と、前記第３のステップで算出した前記全ての工程の最早開始時刻ｘEとを利用して、次の数７に基づき全ての工程の最遅開始時刻ｘLを前記演算部で算出する第４のステップをさらに備えたことを特徴とする請求項２記載のスケジュール作成方法。
【数７】
2007334855.tif 000238
【請求項４】
前記最遅開始時刻ｘLから最早開始時刻ｘEを減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、これをボトルネック工程として抽出する第５のステップをさらに備えたことを特徴とする請求項３記載のスケジュール作成方法。
【請求項５】
前記演算部が前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を再計算し、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を前記記憶部に記憶させる第６のステップと、
前記演算部が前記離散事象システムにおける入力時刻ｕの変更情報を取得すると、これを変更後の入力時刻ｕ〜として前記記憶部に記憶させる第７のステップと、
前記離散事象システムにおける処理開始時刻ｘの変更情報を取得すると、これを変更後の処理開始時刻ｘ〜(0)として前記記憶部に記憶させる第８のステップと、
前記記憶部から行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出し、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）と前記第１のステップで算出した行列Ｂ0を用いて、次の数８に基づき変更後の最早開始時刻ｘ〜Eを前記演算部で算出する第９のステップと、
【数８】
2007334855.tif 000239
をさらに備えたことを特徴とする請求項２記載のスケジュール作成方法。
【請求項６】
前記第８のステップで前記離散事象システムにおける処理開始時刻ｘの変更情報だけを取得し、且つその変更後の値が元の値よりも大きくなっているときには、前記第９のステップで、次の数９に基づき変更後の最早開始時刻ｘ〜Eを算出することを特徴とする請求項５記載のスケジュール作成方法。
【数９】
2007334855.tif 000240
【請求項７】
前記第１のステップで算出した行列Ｃまたは前記第６のステップで算出した変更後の行列Ｃ〜及び前記第６のステップで算出したＦ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、次の数１０に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出する第１０のステップをさらに備えたことを特徴とする請求項５または６記載のスケジュール作成方法。
【数１０】
2007334855.tif 000241
【請求項８】
前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算することで、全工程の変更後におけるトータルフロートを算出すると共に、この変更後におけるトータルフロートの値が０になる工程を検索し、それを変更後のボトルネック工程として再抽出する第１１のステップをさらに備えたことを特徴とする請求項７記載のスケジュール作成方法。
【請求項９】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数１１〜数１５で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ前記演算部で決定する第１のステップと、
【数１１】
2007334855.tif 000242
【数１２】
2007334855.tif 000243
【数１３】
2007334855.tif 000244
【数１４】
2007334855.tif 000245
【数１５】
2007334855.tif 000246
前記行列Ｆ0を用いて、次の数１６の行列（ＰkＦ0）*（但し、（ＰkＦ0）lにおいて全ての要素がεになり、またｎは工程数である）を前記演算部で算出する第２のステップと、
【数１６】
2007334855.tif 000247
を順次実行することを特徴とするスケジュール作成方法。
【請求項１０】
ｋ番目の工程処理に関して、各工程での処理終了時刻をｘ+（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１及び第２のステップで算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）とを利用して、次の数１７に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を前記演算部で算出する第３のステップをさらに備えたことを特徴とする請求項９記載のスケジュール作成方法。
【数１７】
2007334855.tif 000248
【請求項１１】
ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ-（ｋ）とし、出力時刻をｕ（ｋ）としたときに、前記第１及び第２のステップで算出した行列Ｐk，Ｃ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）とを利用して、次の数１８に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を前記演算部で算出する第４のステップをさらに備えたことを特徴とする請求項１０記載のスケジュール作成方法。
【数１８】
2007334855.tif 000249
【請求項１２】
前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、これをボトルネック工程として抽出する第５のステップをさらに備えたことを特徴とする請求項１１記載のスケジュール作成方法。
【請求項１３】
前記演算部が、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させる第６のステップと、
前記演算部が前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の入力時刻ｕ（ｋ）〜として前記記憶部に記憶させる第７のステップと、
前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させる第８のステップと、
前記記憶部から行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ+（ｋ−１）と前記第１のステップで算出した行列Ｆ0，Ｂ0を用いて、次の数１９に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を前記演算部で算出する第９のステップと、
【数１９】
2007334855.tif 000250
をさらに備えたことを特徴とする請求項１０記載のスケジュール作成方法。
【請求項１４】
前記演算部が、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させる第１０のステップと、
前記記憶部から読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっているときに、次の数２０に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出する第１１のステップと、
をさらに備えたことを特徴とする請求項１０記載のスケジュール作成方法。
【数２０】
2007334855.tif 000251
【請求項１５】
前記演算部が、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させる第１２のステップと、
前記演算部が前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の出力時刻ｕ（ｋ）〜として前記記憶部に記憶させる第１３のステップと、
前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させる第１４のステップと、
前記記憶部から行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ-（ｋ＋１）と前記第１のステップで算出した行列Ｆ0，Ｃ0を用いて、次の数２１に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を前記演算部で算出する第１５のステップと、
【数２１】
2007334855.tif 000252
をさらに備えたことを特徴とする請求項１１記載のスケジュール作成方法。
【請求項１６】
前記演算部が、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させる第１６のステップと、
前記記憶部から読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっているときに、次の数２２に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出する第１７のステップと、
をさらに備えたことを特徴とする請求項１１記載のスケジュール作成方法。
【数２２】
2007334855.tif 000253
【請求項１７】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を入力パラメータとして取り込む取込部と、前記取込部で取り込んだ入力パラメータを記憶する記憶部と、前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換する演算部と、を備えたスケジュール作成装置において、
前記演算部は、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数２３〜数２６で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ決定し、
【数２３】
2007334855.tif 000254
【数２４】
2007334855.tif 000255
【数２５】
2007334855.tif 000256
【数２６】
2007334855.tif 000257
前記行列Ｆを用いて、次の数２７の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を算出するように構成されることを特徴とするスケジュール作成装置。
【数２７】
2007334855.tif 000258
【請求項１８】
ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記演算部で算出した行列Ａ0，Ｂ0，及びＦ*と、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）及び入力時刻をｕ（ｋ）とを利用して、次の数２８に基づき工程の最早開始時刻ｘEを算出するように、前記演算部を構成したことを特徴とする請求項１７記載のスケジュール作成装置。
【数２８】
2007334855.tif 000259
【請求項１９】
前記演算部で算出した行列Ｃ及びＦ*と、前記全ての工程の最早開始時刻ｘEとを利用して、次の数２９に基づき全ての工程の最遅開始時刻ｘLを算出するように、当該演算部を構成したことを特徴とする請求項１８記載のスケジュール作成装置。
【数２９】
2007334855.tif 000260
【請求項２０】
前記最遅開始時刻ｘLから前記最早開始時刻ｘEを減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、それをボトルネック工程として抽出するように、前記演算部を構成したことを特徴とする請求項１９記載のスケジュール作成装置。
【請求項２１】
前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を再計算し、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を前記記憶部に記憶させ、
前記離散事象システムにおける入力時刻ｕの変更情報を取得すると、これを変更後の入力時刻ｕ〜として前記記憶部に記憶させ、
前記離散事象システムにおける処理開始時刻ｘの変更情報を取得すると、これを変更後の処理開始時刻ｘ〜(0)として前記記憶部に記憶させ、
前記記憶部から行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出し、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）と前記演算部で算出した行列Ｂ0を用いて、次の数３０に基づき変更後の最早開始時刻ｘ〜Eを算出するように、前記演算部を構成したことを特徴とする請求項１８記載のスケジュール作成装置。
【数３０】
2007334855.tif 000261
【請求項２２】
前記離散事象システムにおける処理開始時刻ｘの変更情報だけを取得し、且つその変更後の値が元の値よりも大きくなっているときには、次の数３１に基づき変更後の最早開始時刻ｘ〜Eを算出するように、前記演算部を構成したことを特徴とする請求項２１記載のスケジュール作成装置。
【数３１】
2007334855.tif 000262
【請求項２３】
前記演算部で算出した行列Ｃまたは変更後の行列Ｃ〜及び行列Ｆ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、次の数３２に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出するように、前記演算部を構成したことを特徴とする請求項２１または２２記載のスケジュール作成装置。
【数３２】
2007334855.tif 000263
【請求項２４】
前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算することで、全工程の変更後におけるトータルフロートを算出すると共に、この変更後におけるトータルフロートの値が０になる工程を検索し、それを変更後のボトルネック工程として再抽出するように、前記演算部を構成したことを特徴とする請求項２３記載のスケジュール作成装置。
【請求項２５】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を入力パラメータとして取り込む取込部と、前記取込部で取り込んだ入力パラメータを記憶する記憶部と、前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換する演算部と、を備えたスケジュール作成装置において、
前記演算部は、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数３３〜数３７で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ決定し、
【数３３】
2007334855.tif 000264
【数３４】
2007334855.tif 000265
【数３５】
2007334855.tif 000266
【数３６】
2007334855.tif 000267
【数３７】
2007334855.tif 000268
前記行列Ｆ0を用いて、次の数３８の行列（ＰkＦ0）*（但し、（ＰkＦ0）lにおいて全ての要素がεになり、またｎは工程数である）を算出するように構成されることを特徴とするスケジュール作成装置。
【数３８】
2007334855.tif 000269
【請求項２６】
ｋ番目の工程処理に関して、各工程での処理終了時刻をｘ+（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記演算部で算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）とを利用して、次の数３９に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を算出するように、前記演算部を構成したことを特徴とする請求項２５記載のスケジュール作成装置。
【数３９】
2007334855.tif 000270
【請求項２７】
ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ-（ｋ）とし、出力時刻をｕ（ｋ）としたときに、前記演算部で算出した行列Ｐk，Ｃ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）とを利用して、次の数４０に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を算出するように、前記演算部を構成したことを特徴とする請求項２６記載のスケジュール作成装置。
【数４０】
2007334855.tif 000271
【請求項２８】
前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、これをボトルネック工程として抽出するように、前記演算部を構成したことを特徴とする請求項２７記載のスケジュール作成装置。
【請求項２９】
前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させ、
前記演算部が前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の入力時刻ｕ（ｋ）〜として前記記憶部に記憶させ、
前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させ、
前記記憶部から行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ+（ｋ−１）と前記演算部で算出した行列Ｆ0，Ｂ0を用いて、次の数４１に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出するように、前記演算部を構成したことを特徴とする請求項２６記載のスケジュール作成装置。
【数４１】
2007334855.tif 000272
【請求項３０】
前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させ、
前記記憶部から読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっているときに、次の数４２に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出するように、前記演算部を構成したことを特徴とする請求項２６記載のスケジュール作成装置。
【数４２】
2007334855.tif 000273
【請求項３１】
前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させ、
前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の出力時刻ｕ（ｋ）〜として前記記憶部に記憶させ、
前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させ、
前記記憶部から行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ-（ｋ＋１）と前記演算部で算出した行列Ｆ0，Ｃ0を用いて、次の数４３に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出するように、前記演算部を構成したことを特徴とする請求項２７記載のスケジュール作成装置。
【数４３】
2007334855.tif 000274
【請求項３２】
前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させ、
前記記憶部から読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっているときに、次の数４４に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出するように、前記演算部を構成したことを特徴とする請求項２７記載のスケジュール作成装置。
【数４４】
2007334855.tif 000275
【請求項３３】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を、入力パラメータとしてコンピュータであるスケジュール作成装置に取り込ませ、この入力パラメータを前記コンピュータに記憶させ、さらに前記離散事象システムの状態を表現するために、前記入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるように前記コンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記入力パラメータに基づいて、次の数４５〜数４８で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ決定させる第１の手順と、
【数４５】
2007334855.tif 000276
【数４６】
2007334855.tif 000277
【数４７】
2007334855.tif 000278
【数４８】
2007334855.tif 000279
前記行列Ｆを用いて、次の数４９の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を算出させる第２の手順と、
【数４９】
2007334855.tif 000280
を前記コンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項３４】
ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記処理開始時刻ｘ（ｋ）及び入力時刻ｕ（ｋ）を取り込ませ、この処理開始時刻ｘ（ｋ）及び入力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ａ0，Ｂ0，及びＦ*とを利用して、次の数５０に基づき工程の最早開始時刻ｘEを算出させる第３の手順を、前記コンピュータに実行させることを特徴とする請求項３３記載のコンピュータプログラム。
【数５０】
2007334855.tif 000281
【請求項３５】
前記第１および第２の手順で算出させた行列Ｃ及びＦ*と、前記第３の手順で算出させた前記全ての工程の最早開始時刻ｘEとを利用して、次の数５１に基づき全ての工程の最遅開始時刻ｘLを算出させる第４の手順を、前記コンピュータに実行させることを特徴とする請求項３４記載のコンピュータプログラム。
【数５１】
2007334855.tif 000282
【請求項３６】
前記最遅開始時刻ｘLから最早開始時刻ｘEを減算させることで、全工程のトータルフロートを算出させると共に、このトータルフロートの値が０になる工程を検索させ、これをボトルネック工程として抽出させる第５の手順を、前記コンピュータに実行させることを特徴とする請求項３５記載のコンピュータプログラム。
【請求項３７】
前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を再計算させ、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を記憶させる第６の手順と、
前記離散事象システムにおける入力時刻ｕの変更情報を取得させ、これを変更後の入力時刻ｕ〜として記憶させる第７の手順と、
前記離散事象システムにおける処理開始時刻ｘの変更情報を取得させ、これを変更後の処理開始時刻ｘ〜(0)として記憶させる第８の手順と、
前記行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出させ、前記処理開始時刻ｘ（ｋ）と前記行列Ｂ0を用いて、次の数５２に基づき変更後の最早開始時刻ｘ〜Eを算出させる第９の手順と、を前記コンピュータに実行させることを特徴とする請求項３４記載のコンピュータプログラム。
【数５２】
2007334855.tif 000283
【請求項３８】
前記第８の手順で離散事象システムにおける処理開始時刻ｘの変更情報だけを取得し、且つその変更後の値が元の値よりも大きくなっているときには、前記第９の手順で、次の数５３に基づき変更後の最早開始時刻ｘ〜Eを算出させることを特徴とする請求項３７記載のコンピュータプログラム。
【数５３】
2007334855.tif 000284
【請求項３９】
前記第１の手順で算出させた行列Ｃまたは前記第６の手順で算出させた変更後の行列Ｃ〜及び前記第６の手順で算出させたＦ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、次の数５４に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出させる第１０の手順を、前記コンピュータに実行させることを特徴とする請求項３７または３８記載のコンピュータプログラム。
【数５４】
2007334855.tif 000285
【請求項４０】
前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算させることで、全工程の変更後におけるトータルフロートを算出させると共に、この変更後におけるトータルフロートの値が０になる工程を検索させ、それを変更後のボトルネック工程として再抽出させる第１１の手順を、前記コンピュータに実行させることを特徴とする請求項３９記載のコンピュータプログラム。
【請求項４１】
一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を、入力パラメータとしてコンピュータであるスケジュール作成装置に取り込ませ、この入力パラメータを前記コンピュータに記憶させ、さらに前記離散事象システムの状態を表現するために、前記入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるように前記コンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数５５〜数５９で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ決定させる第１の手順と、
【数５５】
2007334855.tif 000286
【数５６】
2007334855.tif 000287
【数５７】
2007334855.tif 000288
【数５８】
2007334855.tif 000289
【数５９】
2007334855.tif 000290
前記行列Ｆ0を用いて、次の数６０の行列（ＰkＦ0）*（但し、（ＰkＦ0）lにおいて全ての要素がεになり、またｎは工程数である）を算出させる第２の手順と、
【数６０】
2007334855.tif 000291
を前記コンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項４２】
ｋ番目の工程処理に関して、各工程での処理終了時刻をｘ+（ｋ）とし、入力時刻をｕ（ｋ）としたときに、ｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）を取り込ませ、この処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ｐk，Ｂ0，及び（ＰkＦ0）*とを利用して、次の数６１に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を算出させる第３の手順を、前記コンピュータに実行させることを特徴とする請求項４１記載のコンピュータプログラム。
【数６１】
2007334855.tif 000292
【請求項４３】
ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ-（ｋ）とし、出力時刻をｕ（ｋ）としたときに、ｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）を取り込ませ、このｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ｐk，Ｃ0，及び（ＰkＦ0）*とを利用して、次の数６２に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を算出させる第４の手順を、前記コンピュータに実行させることを特徴とする請求項４２記載のコンピュータプログラム。
【数６２】
2007334855.tif 000293
【請求項４４】
前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算させることで、全工程のトータルフロートを算出させると共に、このトータルフロートの値が０になる工程を検索させ、これをボトルネック工程として抽出させる第５の手順を、前記コンピュータに実行させることを特徴とする請求項４３記載のコンピュータプログラム。
【請求項４５】
前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算させ、変更後の行列ＰK〜を記憶させる第６の手順と、
前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得させ、これを変更後の入力時刻ｕ（ｋ）〜として記憶させる第７の手順と、
前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得させ、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として記憶させる第８の手順と、
前記行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出させ、前記処理終了時刻ｘ+（ｋ−１）と前記行列Ｆ0，Ｂ0を用いて、次の数６３に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出させる第９の手順と、
を前記コンピュータに実行させることを特徴とする請求項４２記載のコンピュータプログラム。
【数６３】
2007334855.tif 000294
【請求項４６】
前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得させ、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として記憶させる第１０の手順と、
前記読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっているときに、次の数６４に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出させる第１１の手順と、
を前記コンピュータに実行させることを特徴とする請求項４２記載のコンピュータプログラム。
【数６４】
2007334855.tif 000295
【請求項４７】
前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算させ、変更後の行列ＰK〜を記憶させる第１２の手順と、
前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得させ、これを変更後の出力時刻ｕ（ｋ）〜として記憶させる第１３の手順と、
前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得させ、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として記憶させる第１４の手順と、
前記行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出させ、前記処理終了時刻ｘ-（ｋ＋１）と前記行列Ｆ0，Ｃ0とを用いて、次の数６５に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出させる第１５の手順と、
を前記コンピュータに実行させることを特徴とする請求項４３記載のコンピュータプログラム。
【数６５】
2007334855.tif 000296
【請求項４８】
前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得させ、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として記憶させる第１６の手順と、
前記読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっているときに、次の数６６に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出させる第１７の手順と、
を前記コンピュータに実行させることを特徴とする請求項４３記載のコンピュータプログラム。
【数６６】
2007334855.tif 000297
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の工程を経て作業を行なう作業プロセスのスケジュール作成方法，スケジュール作成装置，及びコンピュータプログラムに関する。
【背景技術】
【０００２】
生産システムの工程管理や、プロジェクトの進捗管理など、複数の工程が存在する作業プロセスに対して管理を行なう場合、例えば、ある工程が終了しないと次の工程に移れない、又は複数の工程で同時並行して作業が可能であるなど、様々な制約条件が課されている。そのため、こうしたシステムやプロジェクトの管理（マネジメント）には、納期遅れを出さす、かつできるだけ低コストで実行することが求められる。また、複数存在する工程の中で、どこが作業効率の最も悪い工程箇所であるボトルネックであるのかを常に把握し、納期遅れが生じないように、これらの工程の進捗状況には、常に注意を払うことが必要である。
【０００３】
従来、この種のシステムやプロジェクトのスケジュール管理としては、ガントチャートがしばしば用いられ、またクリティカルパス（重要な経路）の把握には、アローダイアグラムを用いて解析することが多い。前者のガントチャートによる方法は、各工程がいつ実行されるのかが明確に記述されるため、人員や設備の計画やタスクの進捗状況把握に適している。しかし、工程の実行順序に関する制約関係は明示されないため、一つの工程の遅れが後続の工程や終了時刻にどのような影響を与えるのかを把握するのが難しいという欠点がある。
【０００４】
他方、アローダイアグラムによる方法は、タスクの実行順序を明確に記述するため、クリティカルパス即ちボトルネック工程を把握することが容易にできる利点がある。その反面、どの資源をいつ使うのかの把握が難しく、資源割当や進捗管理といった用途には向いていない。また、同一資源を共有しながら複数のプロジェクトを同時並行で実施したり、同一の製品を繰り返し生産したりするような場合の解析には向いていない。
【０００５】
同一資源を繰り返し用いるようなシステムの記述と解析方法の一つに、時間付きペトリネット（ＴＰＮ）を用いる方法も提案されている。この方法では、トランジションの発火時刻を、工程の開始時刻や終了時刻とすると共に、プレース内でのトークンの保有時間を工程の実行時間とし、制御プレースによって資源の非競合（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代数とは、或るクラスの離散事象システムの記述に適した代数系であり、ここでは実数体をＲと表し、Ｄ＝Ｒ∪｛±∞｝において、加算及び乗算の二つの演算式を次のように定義する。
【０００９】
【数６７】
2007334855.tif 000003
【００１０】
なお、上記加算や乗算の演算子は、通常の代数系での演算子と区別するために、「＋」や「×」のシンボルを丸印で囲んで表現するが、乗算については混乱のない限り演算子の表記を省略する。これらの演算子の間には、通常の代数系と同様に、交換法則，結合法則，分配法則が成り立ち、式の変形など通常の代数系と同様の計算を行なうことができる。また、演算の優先順位は、加算よりも乗算が高いとする。加算及び乗算の単位元を、それぞれε（＝−∞）及びｅ（＝０）と定義すると、任意のｘ∈Ｄに対して、次の式が成り立つ。
【００１１】
【数６８】
2007334855.tif 000004
【００１２】
さらに、上記数６７や数６８の式以外に、次の２つの演算子（∧，＼）も次のように定義する。
【００１３】
【数６９】
2007334855.tif 000005
【００１４】
ここで、上記max関数は、括弧内で最大の値を算出することを意味し、min関数は、括弧内で最小の値を算出することを意味する。また、複数の数に対する演算子は、ｍ≦ｎのときに、次のように記述される。
【００１５】
【数７０】
2007334855.tif 000006
【００１６】
【数７１】
2007334855.tif 000007
【００１７】
【数７２】
2007334855.tif 000008
【００１８】
なお、ｍ＞ｎの場合は、何も演算を行なわず、前後の演算に対する単位元に成るものとする。
【００１９】
max-plus代数では、Ｄの元を要素に持つ行列に対しても、同様の演算子を用いて定義することができる。ここでは、ｍ行ｎ列の行列Ｘ（Ｘ∈Ｄm×n）に対し、ＸTは行列Ｘの転置行列を表し、［Ｘ］ijはｉ行ｊ列の成分（要素）を表わすものとする。また、ｍ行ｎ列の行列Ｘ，Ｙ（Ｘ，Ｙ∈Ｄm×n）において、全てのｉ及びｊに対して（但し、１≦ｉ≦ｍ，１≦ｊ≦ｎ）、［Ｘ］ij≦［Ｙ］ijが成立するときに、Ｘ≦Ｙと表す。このとき、Ｘ，Ｙ∈Ｄm×nに対して、次の式に示す演算式を定義する。
【００２０】
【数７３】
2007334855.tif 000009
【００２１】
【数７４】
2007334855.tif 000010
【００２２】
また、ｍ行ｌ列の行列Ｘと、ｌ行ｐ列の行列Ｙ（Ｘ∈Ｄm×l，Ｙ∈Ｄl×p）に対して、次の式に示す演算式を定義する。
【００２３】
【数７５】
2007334855.tif 000011
【００２４】
【数７６】
2007334855.tif 000012
【００２５】
さらに、加算の単位元はεmnと表記し、これはεmn∈Ｄm×nにおいて、全ての成分がεであることを意味する。また乗算の単位元はｅmと表記し、これはｅm∈Ｄm×mにおいて、対角成分のみｅで、それ以外の非対称成分は全てεであることを意味する。以上の定義により、max-plus代数において、線形性を有する行列演算が可能となる。そして、こうしたmax-plus代数を用いることで、作業プロセス内で順に行われる作業の順番（以下、イベントカウンタと言う）を独立変数とし、作業プロセス内で作業が行われる時刻をイベントカウンタの関数として記述することで、工程管理や進捗管理におけるスケジュールを作成することができる。
【００２６】
次に、上記max-plus代数を用いたＭＰＬシステムについて説明する。ＭＰＬシステムとは、そのシステムの振る舞いがmax-plus代数上で線形な形式で表現することができるシステムのことで、次の式に示すような現代制御理論の状態空間表現に類似した形式で表される。
【００２７】
【数７７】
2007334855.tif 000013
【００２８】
【数７８】
2007334855.tif 000014
【００２９】
上式におけるイベントカウンタｋは、初期状態からの事象の発生回数を表す。また、ｘ（ｋ）∈Ｄn，ｕ（ｋ）∈Ｄp，ｙ（ｋ）∈Ｄqはそれぞれ、状態変数，制御入力，制御出力であり、ｋ回目の事象が起こる時刻を表す。なお、ｎ，ｐ，ｑはそれぞれの変数の持つ次元である。さらに、Ａ∈Ｄn×n，Ｂ∈Ｄn×p，Ｃ∈Ｄq×nはそれぞれ、システム行列，入力行列，出力行列である。
【００３０】
ここで、図７に示すような作業プロセスとしての生産プロセスが、ＭＰＬシステムによりどのようにしてモデリングされるのかを具体的に説明する。図７は、複数の工程からなる生産システムにおける加工順序の一例を示した模式図であって、ここでは入力から工程１に材料（部品）を投入して加工し、その加工が終了した後に、工程２と工程３で同時並行的に材料の加工を行なう。続く工程４では、工程２と工程３の両方から加工済部品を受取って加工を行ない、この工程４の加工が完了すると、製品として完成し出力される。
【００３１】
この生産システムに対して、工程１〜４の各加工時間を、それぞれｄ1，ｄ2，ｄ3，ｄ4とする。また、ｋ番目のバッチ加工に関して、工程１に投入される材料の投入時刻をｕ（ｋ）とし、工程１〜４におけるそれぞれの加工開始時刻を、ｘ1（ｋ），ｘ2（ｋ），ｘ3（ｋ），ｘ4（ｋ）とし、全ての加工が終了した製品の完成時刻をｙ（ｋ）として定義する。つまり、ｕ（ｋ）およびｙ（ｋ）は、各々システムに対する制御入力と制御出力に相当し、ｘ1（ｋ）〜ｘ4（ｋ）は、システム内部の状態変数に相当する。
【００３２】
さらに、図中に示した生産システムの各工程１〜４には、次のような制約条件が課せられているものとする。
・各工程１〜４の設備が稼動中のときには、その加工が終了するまで、次の加工を開始できない。
・先行工程を有する工程２〜４は、それらの先行工程の加工が終了しないと、加工を開始できない。
・入力のある工程１は、当該番号の材料を受取らないと加工を開始できない。
・各工程１〜４の設備が空即ち稼動していない状態で、先行工程や入力から材料を受取ると、直ちに加工を開始する。
【００３３】
以上の制約条件より、工程１が（ｋ＋１）番目の材料の加工を開始する時刻ｘ1（ｋ＋１）は、ｋ＋１番目の材料が投入された時刻ｕ（ｋ＋１）と、工程１でｋ番目の材料の加工が終了した時刻ｘ1（ｋ）＋ｄ1の遅い方に定められると共に、工程２が（ｋ＋１）番目の材料の加工を開始する時刻ｘ2（ｋ＋１）は、工程２でｋ番目の材料の加工が終了した時刻ｘ2（ｋ）＋ｄ2と、工程１から（ｋ＋１）番目の加工済材料を受取った時刻ｘ1（ｋ＋１）＋ｄ1の遅い方に定められ、同様に、工程３が（ｋ＋１）番目の材料の加工を開始する時刻ｘ3（ｋ＋１）は、工程３でｋ番目の材料の加工が終了した時刻ｘ3（ｋ）＋ｄ3と、工程１から（ｋ＋１）番目の加工済材料を受取った時刻ｘ1（ｋ＋１）＋ｄ1の遅い方に定められる。また、工程４が（ｋ＋１）番目の材料の加工を開始する時刻ｘ3（ｋ＋１）は、工程２から（ｋ＋１）番目の加工済材料を受取った時刻ｘ2（ｋ＋１）＋ｄ2と、工程３から（ｋ＋１）番目の加工済材料を受取った時刻ｘ3（ｋ＋１）＋ｄ3と、工程４でｋ番目の材料の加工が終了した時刻ｘ4（ｋ）＋ｄ4の遅い方に定められる。さらに、ｋ番目の加工済材料が製品として完了する時刻ｙ（ｋ）は、工程４でｋ番目の材料の加工が終了した時刻ｘ4（ｋ）＋ｄ4に一致する。これらをmax-plus代数により表現すると、前述した遅い方の時刻の算出はmax演算子で記述することができるので、以下に示す各数式のようになる。
【００３４】
【数７９】
2007334855.tif 000015
【００３５】
【数８０】
2007334855.tif 000016
【００３６】
【数８１】
2007334855.tif 000017
【００３７】
【数８２】
2007334855.tif 000018
【００３８】
【数８３】
2007334855.tif 000019
【００３９】
上記数７９を数８０および数８１に代入し、これらを数４６に代入すると、数７９〜数８３は前記数７７や数７８で表され、ＭＰＬシステムの形式で記述することができる。但し、ここでの数７７や数７８におけるシステム行列Ａや、入力行列Ｂや、出力行列Ｃは、次の式のようになる。
【００４０】
【数８４】
2007334855.tif 000020
【００４１】
数７７や数７８の式は、作業プロセスでの作業開始時刻および終了時刻に関する一般的な表現となっており、これらの数式をさらに変形すると、未来の製品完了時刻ｙ（ｋ＋１）を、現在の内部状態ｘ（ｋ）と、未来の材料の投入時刻ｕ（ｋ＋１）とにより計算することが可能になる。従って、生産システムの内部状態ｘ（ｋ）が定まっており、未来の製品完了時刻ｙ（ｋ＋１）として、生産システムにおける納期である望ましい出力Ｒ（ｋ＋１）を定めたとき、納期遅れを出すことがない適切な入力ｕ（ｋ＋１）を求めることができる。また、イベントカウンタがｋ＋２以降の場合は、イベントカウンタを一つずつ増やして再計算することにより、生産システムに適切な投入時刻を求めることが可能となり、最終的に作業プロセスのスケジュールを作成することができる。
【００４２】
こうしたＭＰＬシステムを利用した生産システムのモデリングは、例えば特許文献１や特許文献２などにも開示され、作業プロセスのスケジュールを作成する方法として広く採用されているが、例えば先行制約を有するプロジェクトのスケジューリング問題にも同様に適用することができ、その場合の各工程はタスクに相当する。但し、本発明では、こうしたタスクを含めたものを工程として定義する。
【特許文献１】特開２００４−２４０８５３号公報
【特許文献２】特開２００５−３３９１７８号公報
【発明の開示】
【発明が解決しようとする課題】
【００４３】
上述したような作業プロセスのスケジュールを作成するためには、作業プロセスをモデル化して、上記数８０〜数８２にあるような右辺にｘi（ｋ＋１）を含む式から、数７７のような右辺にｘ（ｋ＋１）が現れない形式に変形を行って、ＭＰＬシステムに適合する作業プロセスの状態を表現した式に作成変換し、線形計画法などを用いた数値計算を行なう必要がある。しかし、従来のこうした方法では、作業プロセスの状態を表現する数７７や数７８の式を手作業で作成していたため、複雑な作業プロセスに対して適用することが困難であるという問題があった。また、こうした点を考慮して、特許文献１では、作業プロセスのスケジュールを作成する一連の手順をコンピュータで処理する手法を提案しているが、メモリ消費が大きく処理システムが膨大なものとなり、計算が非効率で改善が求められていた。
【００４４】
また、特許文献１や特許文献２では、与えられた納期丁度に製品が完成するように、材料の投入時刻ｕ（ｋ＋１）を求め、システムの状態変化に応じてそれらを適切に修正する方法を提案している。しかし、これは本来システムの入力である材料の投入時刻ｕ（ｋ＋１）を決定することに焦点が当てられており、途中工程における稼動状態の把握や、ボトルネック工程の把握については、十分に検討されてはいなかった。
【００４５】
さらに、システムが実際に稼動開始した後で、材料の投入時刻（入力時刻）や加工時間などの関連パラメータが変化した場合に、効率的な再スケジューリングを行なうことが、工程やプロジェクトなどの管理において重要である。この点についても、改善が求められていた。
【００４６】
本発明は上記の問題点に鑑みなされたもので、その第１の目的は、より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に簡単に導出することが可能なスケジュール作成方法，スケジュール作成装置，及びコンピュータプログラムを提供することにある。
【００４７】
また、本発明の第２の目的は、途中工程の稼動状態や、ボトルネック工程を十分に把握することが可能なスケジュール作成方法，スケジュール作成装置，及びコンピュータプログラムを提供することにある。
【００４８】
さらに、本発明の第３の目的は、システムの稼動後に各種パラメータが変化した場合に、適確に且つ効率的に再スケジューリングを実行できるスケジュール作成方法，スケジュール作成装置，及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００４９】
本発明は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数８５〜数８８で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ前記演算部で決定する第１のステップと、
【００５０】
【数８５】
2007334855.tif 000021
【００５１】
【数８６】
2007334855.tif 000022
【００５２】
【数８７】
2007334855.tif 000023
【００５３】
【数８８】
2007334855.tif 000024
【００５４】
前記行列Ｆを用いて、次の数８９の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を前記演算部で算出する第２のステップと、
【００５５】
【数８９】
2007334855.tif 000025
【００５６】
を順次実行するスケジュール作成方法である。
【００５７】
この場合、ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１及び第２のステップで算出した行列Ａ0，Ｂ0，及びＦ*と、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）及び入力時刻ｕ（ｋ）とを利用して、次の数９０に基づき工程の最早開始時刻ｘEを前記演算部で算出する第３のステップをさらに備えている。
【００５８】
【数９０】
2007334855.tif 000026
【００５９】
また、前記第１および第２のステップで算出した行列Ｃ及びＦ*と、前記第３のステップで算出した前記全ての工程の最早開始時刻ｘEとを利用して、次の数９１に基づき全ての工程の最遅開始時刻ｘLを前記演算部で算出する第４のステップをさらに備えている。
【００６０】
【数９１】
2007334855.tif 000027
【００６１】
さらに、前記最遅開始時刻ｘLから最早開始時刻ｘEを減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、これをボトルネック工程として抽出する第５のステップをさらに備えるのが好ましい。
【００６２】
本発明は、上記方法において、前記演算部が前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を再計算し、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を前記記憶部に記憶させる第６のステップと、
前記演算部が前記離散事象システムにおける入力時刻ｕの変更情報を取得すると、これを変更後の入力時刻ｕ〜として前記記憶部に記憶させる第７のステップと、
前記離散事象システムにおける処理開始時刻ｘの変更情報を取得すると、これを変更後の処理開始時刻ｘ〜(0)として前記記憶部に記憶させる第８のステップと、
前記記憶部から行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出し、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）と前記第１のステップで算出した行列Ｂ0を用いて、次の数９２に基づき変更後の最早開始時刻ｘ〜Eを前記演算部で算出する第９のステップと、
【００６３】
【数９２】
2007334855.tif 000028
【００６４】
をさらに備えている。
【００６５】
この場合、前記第８のステップで前記離散事象システムにおける処理開始時刻ｘの変更情報だけを取得し、且つその変更後の値が元の値よりも大きくなっているときには、前記第９のステップで、次の数９３に基づき変更後の最早開始時刻ｘ〜Eを算出してもよい。
【００６６】
【数９３】
2007334855.tif 000029
【００６７】
上記変更後の最早開始時刻ｘ〜Eを算出した後は、前記第１のステップで算出した行列Ｃまたは前記第６のステップで算出した変更後の行列Ｃ〜及び前記第６のステップで算出したＦ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、次の数９４に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出する第１０のステップをさらに備えるのが好ましい。
【００６８】
【数９４】
2007334855.tif 000030
【００６９】
この場合、前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算することで、全工程の変更後におけるトータルフロートを算出すると共に、この変更後におけるトータルフロートの値が０になる工程を検索し、それを変更後のボトルネック工程として再抽出する第１１のステップをさらに備えるのが好ましい。
【００７０】
また、本発明のスケジュール作成方法は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数９５〜数９９で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ前記演算部で決定する第１のステップと、
【００７１】
【数９５】
2007334855.tif 000031
【００７２】
【数９６】
2007334855.tif 000032
【００７３】
【数９７】
2007334855.tif 000033
【００７４】
【数９８】
2007334855.tif 000034
【００７５】
【数９９】
2007334855.tif 000035
【００７６】
前記行列Ｆ0を用いて、次の数１００の行列（ＰkＦ0）*（但し、（ＰkＦ0）lにおいて全ての要素がεになり、またｎは工程数である）を前記演算部で算出する第２のステップと、
【００７７】
【数１００】
2007334855.tif 000036
【００７８】
を順次実行することを特徴とする。
【００７９】
この場合、ｋ番目の工程処理に関して、各工程での処理終了時刻をｘ+（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１及び第２のステップで算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）とを利用して、次の数１０１に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を前記演算部で算出する第３のステップをさらに備えている。
【００８０】
【数１０１】
2007334855.tif 000037
【００８１】
また、ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ-（ｋ）とし、出力時刻をｕ（ｋ）としたときに、前記第１及び第２のステップで算出した行列Ｐk，Ｃ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）とを利用して、次の数１０２に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を前記演算部で算出する第４のステップをさらに備えている。
【００８２】
【数１０２】
2007334855.tif 000038
【００８３】
さらに好ましくは、前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、これをボトルネック工程として抽出する第５のステップをさらに備えている。
【００８４】
こうした方法において、本発明では、前記演算部が、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させる第６のステップと、
前記演算部が前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の入力時刻ｕ（ｋ）〜として前記記憶部に記憶させる第７のステップと、
前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させる第８のステップと、
前記記憶部から行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ+（ｋ−１）と前記第１のステップで算出した行列Ｆ0，Ｂ0を用いて、次の数１０３に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を前記演算部で算出する第９のステップと、
【００８５】
【数１０３】
2007334855.tif 000039
【００８６】
をさらに備えている。
【００８７】
これに代わる簡便な方法として、前記演算部が、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させる第１０のステップと、
前記記憶部から読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっているときに、次の数１０４に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出する第１１のステップと、をさらに備えてもよい。
【００８８】
【数１０４】
2007334855.tif 000040
【００８９】
また、前記演算部が、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させる第１２のステップと、
前記演算部が前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の出力時刻ｕ（ｋ）〜として前記記憶部に記憶させる第１３のステップと、
前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させる第１４のステップと、
前記記憶部から行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ-（ｋ＋１）と前記第１のステップで算出した行列Ｆ0，Ｃ0を用いて、次の数１０５に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を前記演算部で算出する第１５のステップと、
【００９０】
【数１０５】
2007334855.tif 000041
【００９１】
をさらに備えていてもよい。
【００９２】
簡便な方法として、前記演算部が、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させる第１６のステップと、
前記記憶部から読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっているときに、次の数１０６に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出する第１７のステップと、をさらに備えたものが好ましい。
【００９３】
【数１０６】
2007334855.tif 000042
【００９４】
本発明は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を入力パラメータとして取り込む取込部と、前記取込部で取り込んだ入力パラメータを記憶する記憶部と、前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換する演算部と、を備えたスケジュール作成装置において、
前記演算部は、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数１０７〜数１１０で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ決定し、
【００９５】
【数１０７】
2007334855.tif 000043
【００９６】
【数１０８】
2007334855.tif 000044
【００９７】
【数１０９】
2007334855.tif 000045
【００９８】
【数１１０】
2007334855.tif 000046
【００９９】
前記行列Ｆを用いて、次の数１１１の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を算出するように構成される。
【０１００】
【数１１１】
2007334855.tif 000047
【０１０１】
この場合、ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記演算部で算出した行列Ａ0，Ｂ0，及びＦ*と、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）及び入力時刻をｕ（ｋ）とを利用して、次の数１１２に基づき工程の最早開始時刻ｘEを算出するように、前記演算部を構成してもよい。
【０１０２】
【数１１２】
2007334855.tif 000048
【０１０３】
また、前記演算部で算出した行列Ｃ及びＦ*と、前記全ての工程の最早開始時刻ｘEとを利用して、次の数１１３に基づき全ての工程の最遅開始時刻ｘLを算出するように、当該演算部を構成してもよい。
【０１０４】
【数１１３】
2007334855.tif 000049
【０１０５】
そして、前記最遅開始時刻ｘLから前記最早開始時刻ｘEを減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、それをボトルネック工程として抽出するように、前記演算部を構成するのが好ましい。
【０１０６】
本発明のスケジュール作成装置は、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を再計算し、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を前記記憶部に記憶させ、
前記離散事象システムにおける入力時刻ｕの変更情報を取得すると、これを変更後の入力時刻ｕ〜として前記記憶部に記憶させ、
前記離散事象システムにおける処理開始時刻ｘの変更情報を取得すると、これを変更後の処理開始時刻ｘ〜(0)として前記記憶部に記憶させ、
前記記憶部から行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出し、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）と前記演算部で算出した行列Ｂ0を用いて、次の数１１４に基づき変更後の最早開始時刻ｘ〜Eを算出するように、前記演算部を構成している。
【０１０７】
【数１１４】
2007334855.tif 000050
【０１０８】
この場合、前記離散事象システムにおける処理開始時刻ｘの変更情報だけを取得し、且つその変更後の値が元の値よりも大きくなっているときには、次の数１１５に基づき変更後の最早開始時刻ｘ〜Eを算出するように、前記演算部を構成してもよい。
【０１０９】
【数１１５】
2007334855.tif 000051
【０１１０】
そして、前記演算部で算出した行列Ｃまたは変更後の行列Ｃ〜及び行列Ｆ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、次の数１１６に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出するように、前記演算部を構成するのが好ましい。
【０１１１】
【数１１６】
2007334855.tif 000052
【０１１２】
また、前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算することで、全工程の変更後におけるトータルフロートを算出すると共に、この変更後におけるトータルフロートの値が０になる工程を検索し、それを変更後のボトルネック工程として再抽出するように、前記演算部を構成するのが好ましい。
【０１１３】
また本発明のスケジュール作成装置は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を入力パラメータとして取り込む取込部と、前記取込部で取り込んだ入力パラメータを記憶する記憶部と、前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換する演算部と、を備えたスケジュール作成装置において、
前記演算部は、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数１１７〜数１２１で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ決定し、
【０１１４】
【数１１７】
2007334855.tif 000053
【０１１５】
【数１１８】
2007334855.tif 000054
【０１１６】
【数１１９】
2007334855.tif 000055
【０１１７】
【数１２０】
2007334855.tif 000056
【０１１８】
【数１２１】
2007334855.tif 000057
【０１１９】
前記行列Ｆ0を用いて、次の数１２２の行列（ＰkＦ0）*（但し、（ＰkＦ0）lにおいて全ての要素がεになり、またｎは工程数である）を算出するように構成される。
【０１２０】
【数１２２】
2007334855.tif 000058
【０１２１】
この場合、ｋ番目の工程処理に関して、各工程での処理終了時刻をｘ+（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記演算部で算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）とを利用して、次の数１２３に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を算出するように、前記演算部を構成するのが好ましい。
【０１２２】
【数１２３】
2007334855.tif 000059
【０１２３】
さらに、ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ-（ｋ）とし、出力時刻をｕ（ｋ）としたときに、前記演算部で算出した行列Ｐk，Ｃ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）とを利用して、次の数１２４に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を算出するように、前記演算部を構成するのが好ましい。
【０１２４】
【数１２４】
2007334855.tif 000060
【０１２５】
さらに好ましくは、前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、これをボトルネック工程として抽出するように、前記演算部を構成してもよい。
【０１２６】
こうした構成において、本発明では、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させ、
前記演算部が前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の入力時刻ｕ（ｋ）〜として前記記憶部に記憶させ、
前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させ、
前記記憶部から行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ+（ｋ−１）と前記演算部で算出した行列Ｆ0，Ｂ0を用いて、次の数１２５に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出するように、前記演算部を構成するのが好ましい。
【０１２７】
【数１２５】
2007334855.tif 000061
【０１２８】
これに代わる簡便な装置として、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させ、
前記記憶部から読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっているときに、次の数１２６に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出するように、前記演算部を構成してもよい。
【０１２９】
【数１２６】
2007334855.tif 000062
【０１３０】
また、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させ、
前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の出力時刻ｕ（ｋ）〜として前記記憶部に記憶させ、
前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させ、
前記記憶部から行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ-（ｋ＋１）と前記演算部で算出した行列Ｆ0，Ｃ0を用いて、次の数１２７に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出するように、前記演算部を構成してもよい。
【０１３１】
【数１２７】
2007334855.tif 000063
【０１３２】
これに代わる簡便な装置として、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させ、
前記記憶部から読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっているときに、次の数１２８に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出するように、前記演算部を構成してもよい。
【０１３３】
【数１２８】
2007334855.tif 000064
【０１３４】
本発明は、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を、入力パラメータとしてコンピュータであるスケジュール作成装置に取り込ませ、この入力パラメータを前記コンピュータに記憶させ、さらに前記離散事象システムの状態を表現するために、前記入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるように前記コンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記入力パラメータに基づいて、次の数１２９〜数１３２で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ決定させる第１の手順と、
【０１３５】
【数１２９】
2007334855.tif 000065
【０１３６】
【数１３０】
2007334855.tif 000066
【０１３７】
【数１３１】
2007334855.tif 000067
【０１３８】
【数１３２】
2007334855.tif 000068
【０１３９】
前記行列Ｆを用いて、次の数１３３の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を算出させる第２の手順と、
【０１４０】
【数１３３】
2007334855.tif 000069
【０１４１】
を前記コンピュータに実行させることを特徴とする。
【０１４２】
この場合のコンピュータプログラムは、ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記処理開始時刻ｘ（ｋ）及び入力時刻ｕ（ｋ）を取り込ませ、この処理開始時刻ｘ（ｋ）及び入力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ａ0，Ｂ0，及びＦ*とを利用して、次の数１３４に基づき全ての工程の最早開始時刻ｘEを算出させる第３の手順を、前記コンピュータに実行させてもよい。
【０１４３】
【数１３４】
2007334855.tif 000070
【０１４４】
また、前記第１および第２の手順で算出させた行列Ｃ及びＦ*と、前記第３のステップで算出させた前記全ての工程の最早開始時刻ｘEとを利用して、次の数１３５に基づき全ての工程の最遅開始時刻ｘLを算出させる第４の手順を、コンピュータプログラムによって前記コンピュータに実行させてもよい。
【０１４５】
【数１３５】
2007334855.tif 000071
【０１４６】
そして、前記最遅開始時刻ｘLから最早開始時刻ｘEを減算させることで、全工程のトータルフロートを算出させると共に、このトータルフロートの値が０になる工程を検索させ、これをボトルネック工程として抽出させる第５の手順を、前記コンピュータに実行させるコンピュータプログラムを備えることが好ましい。
【０１４７】
本発明のコンピュータプログラムは、前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を再計算させ、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を記憶させる第６の手順と、
前記離散事象システムにおける入力時刻ｕの変更情報を取得させ、これを変更後の入力時刻ｕ〜として前記記憶部に記憶させる第７の手順と、
前記離散事象システムにおける処理開始時刻ｘの変更情報を取得させ、これを変更後の入力時刻ｘ〜(0)として前記記憶部に記憶させる第８の手順と、
前記行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出させ、前記処理開始時刻ｘ（ｋ）と前記行列Ｂ0を用いて、次の数１３６に基づき変更後の最早開始時刻ｘ〜Eを算出させる第９の手順と、を前記コンピュータに実行させることを特徴とする。
【０１４８】
【数１３６】
2007334855.tif 000072
【０１４９】
この場合、前記第８の手順で離散事象システムにおける処理開始時刻ｘの変更情報だけを取得し、且つその変更後の値が元の値よりも大きくなっているときときには、前記第９の手順で、次の数１３７に基づき変更後の最早開始時刻ｘ〜Eを算出させてもよい。
【０１５０】
【数１３７】
2007334855.tif 000073
【０１５１】
また、前記第１の手順で算出させた行列Ｃまたは前記第６の手順で算出させた変更後の行列Ｃ〜及び前記第６の手順で算出させたＦ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、次の数１３８に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出させる第１０の手順を、前記コンピュータに実行させてもよい。
【０１５２】
【数１３８】
2007334855.tif 000074
【０１５３】
そして、前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算させることで、全工程の変更後におけるトータルフロートを算出させると共に、この変更後におけるトータルフロートの値が０になる工程を検索させ、それを変更後のボトルネック工程として再抽出させる第１１の手順を、前記コンピュータに実行させるのが好ましい。
【０１５４】
また、本発明のコンピュータプログラムは、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を、入力パラメータとしてコンピュータであるスケジュール作成装置に取り込ませ、この入力パラメータを前記コンピュータに記憶させ、さらに前記離散事象システムの状態を表現するために、前記入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるように前記コンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数１３９〜数１４３で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ決定させる第１の手順と、
【０１５５】
【数１３９】
2007334855.tif 000075
【０１５６】
【数１４０】
2007334855.tif 000076
【０１５７】
【数１４１】
2007334855.tif 000077
【０１５８】
【数１４２】
2007334855.tif 000078
【０１５９】
【数１４３】
2007334855.tif 000079
【０１６０】
前記行列Ｆ0を用いて、次の数１４４の行列（ＰkＦ0）*（但し、（ＰkＦ0）lにおいて全ての要素がεになり、またｎは工程数である）を算出させる第２の手順と、を前記コンピュータに実行させることを特徴とする。
【０１６１】
【数１４４】
2007334855.tif 000080
【０１６２】
この場合、ｋ番目の工程処理に関して、各工程での処理終了時刻をｘ+（ｋ）とし、入力時刻をｕ（ｋ）としたときに、ｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）を取り込ませ、この処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ｐk，Ｂ0，及び（ＰkＦ0）*とを利用して、次の数１４５に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を算出させる第３の手順を、前記コンピュータにさらに実行させてもよい。
【０１６３】
【数１４５】
2007334855.tif 000081
【０１６４】
また、ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ-（ｋ）とし、出力時刻をｕ（ｋ）としたときに、ｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）を取り込ませ、このｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ｐk，Ｃ0，及び（ＰkＦ0）*とを利用して、次の数１４６に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を算出させる第４の手順を、さらに前記コンピュータに実行させてもよい。
【０１６５】
【数１４６】
2007334855.tif 000082
【０１６６】
さらに好ましくは、前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算させることで、全工程のトータルフロートを算出させると共に、このトータルフロートの値が０になる工程を検索させ、これをボトルネック工程として抽出させる第５の手順を、さらに前記コンピュータに実行させてもよい。
【０１６７】
こうしたコンピュータプログラムにおいて、前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算させ、変更後の行列ＰK〜を記憶させる第６の手順と、
前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得させ、これを変更後の入力時刻ｕ（ｋ）〜として記憶させる第７の手順と、
前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得させ、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として記憶させる第８の手順と、
前記行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出させ、前記処理終了時刻ｘ+（ｋ−１）と前記行列Ｆ0，Ｂ0を用いて、次の数１４７に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出させる第９の手順と、を前記コンピュータに実行させるのが好ましい。
【０１６８】
【数１４７】
2007334855.tif 000083
【０１６９】
これに代わる簡便なコンピュータプログラムとして、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得させ、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として記憶させる第１０の手順と、
前記読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっているときに、次の数１４８に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出させる第１１の手順と、を前記コンピュータに実行させてもよい。
【０１７０】
【数１４８】
2007334855.tif 000084
【０１７１】
また、前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算させ、変更後の行列ＰK〜を記憶させる第１２の手順と、
前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得させ、これを変更後の出力時刻ｕ（ｋ）〜として記憶させる第１３の手順と、
前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得させ、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として記憶させる第１４の手順と、
前記行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出させ、前記処理終了時刻ｘ-（ｋ＋１）と前記行列Ｆ0，Ｃ0とを用いて、次の数１４９に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出させる第１５の手順と、を前記コンピュータに実行させてもよい。
【０１７２】
【数１４９】
2007334855.tif 000085
【０１７３】
これに代わる簡便なコンピュータプログラムとして、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得させ、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として記憶させる第１６の手順と、
前記読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっているときに、次の数１５０に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出させる第１７の手順と、を前記コンピュータに実行させてもよい。
【０１７４】
【数１５０】
2007334855.tif 000086
【発明の効果】
【０１７５】
請求項１の方法，請求項１７の装置，及び請求項３３のコンピュータプログラムによれば、入力パラメータとして、各工程の実行時間と工程間の先行制約関係の各情報が予め記憶されていれば、そこから独自のシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃについて、その各要素を決定し、さらにここで決定した行列Ｆから行列Ｆ*を算出して、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ0，Ｆ*，Ｂ0，Ｃを簡単に取得することができる。したがって、システムのスケジュール作成をコンピュータで実現する上で、より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に簡単に導出することが可能になる。
【０１７６】
請求項２の方法，請求項１８の装置，及び請求項３４のコンピュータプログラムによれば、初期状態の処理開始時刻ｘ（ｋ）と入力時刻ｕ（ｋ）が取り込まれれば、先に算出した行列Ａ0，Ｂ0，及びＦ*を利用して、システムを構成する全ての工程の最早開始時刻ｘEを簡単に算出することができる。
【０１７７】
請求項３の方法，請求項１９の装置，及び請求項３５のコンピュータプログラムによれば、先に算出した行列Ｃ及びＦ*と、全ての工程の最早開始時刻ｘEとを利用して、システムを構成する全ての工程の最遅開始時刻ｘLを簡単に算出することができる。
【０１７８】
請求項４の方法，請求項２０の装置，及び請求項３６のコンピュータプログラムによれば、全ての工程における最早開始時刻ｘEや最遅開始時刻ｘLが算出されていれば、後は簡単な演算処理によって全ての工程の余裕時間と、ボトルネック工程がどこに存在するのかを簡単に算出することができる。したがって、途中工程の稼動状態や、ボトルネック工程を十分に把握することが可能になる。
【０１７９】
請求項５の方法，請求項２１の装置，及び請求項３７のコンピュータプログラムによれば、システムの稼動開始後に何らかの原因で、その入力時刻や加工時間や加工開始時刻が変化した場合でも、全ての工程における変更後の最早開始時刻ｘ〜Eを適確に且つ効率的に把握することができる。
【０１８０】
請求項６の方法，請求項２２の装置，及び請求項３８のコンピュータプログラムによれば、より単純な算術手順で、全ての工程における変更後の最早開始時刻ｘ〜Eを簡単に把握することができる。
【０１８１】
請求項７の方法，請求項２３の装置，及び請求項３９のコンピュータプログラムによれば、先に算出した行列ＣまたはＣ〜及びＦ*と、全ての工程における変更後の最早開始時刻ｘ〜Eとを利用して、システムを構成する全ての工程における変更後の最遅開始時刻ｘ〜Lを簡単に算出することができる。
【０１８２】
請求項８の方法，請求項２４の装置，及び請求項４０のコンピュータプログラムによれば、全ての工程における変更後の最早開始時刻ｘ〜Eや最遅開始時刻ｘ〜Lを算出できるので、後は簡単な演算処理によって全ての工程における変更後の余裕時間と、変更後のボトルネック工程がどこに存在するのかを簡単に算出することができる。したがって、システムの稼動後に各種パラメータが変化した場合であっても、適確に且つ効率的に再スケジューリングを実行することが可能になる。
【０１８３】
請求項９の方法，請求項２５の装置，及び請求項４１のコンピュータプログラムによれば、入力パラメータとして、各工程の実行時間と工程間の先行制約関係の各情報が予め記憶されていれば、そこから独自のシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0について、その各要素を決定し、さらにここで決定した行列Ｐk，Ｆ0から行列（ＰkＦ0）*を算出して、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0，（ＰkＦ0）*を簡単に取得することができる。したがって、システムのスケジュール作成をコンピュータで実現する上で、より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に簡単に導出することが可能になる。
【０１８４】
さらにこの場合は、システムの構造に依存する行列Ｆo，Ｂo，Ｃo，Ｄ0と、加工時間のパラメータに依存する行列ＰKが明確に分離しており、より簡潔で高速な計算を実現できる。しかも、同じシステムを表現する上で、加工時間のパラメータが減少しており、より簡潔な状態空間表現の導出が可能になる。
【０１８５】
請求項１０の方法，請求項２６の装置，及び請求項４２のコンピュータプログラムによれば、初期状態の処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）が取り込まれれば、先に算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*を利用して、システムを構成する全ての工程の最早終了時刻ｘ+E（ｋ）を簡単に算出することができる。
【０１８６】
請求項１１の方法，請求項２７の装置，及び請求項４３のコンピュータプログラムによれば、初期状態の処理終了時刻ｘ+（ｋ＋１）及び入力時刻ｕ（ｋ）が取り込まれれば、先に算出した行列Ｐk，Ｃ0，及び（ＰkＦ0）*を利用して、システムを構成する全ての工程の最遅開始時刻ｘ-L（ｋ）を簡単に算出することができる。
【０１８７】
請求項１２の方法，請求項２８の装置，及び請求項４４のコンピュータプログラムによれば、全ての工程における最早開始時刻ｘE（ｋ）や最遅開始時刻ｘL（ｋ）が算出されていれば、後は簡単な演算処理によって全ての工程の余裕時間と、ボトルネック工程がどこに存在するのかを簡単に算出することができる。したがって、途中工程の稼動状態や、ボトルネック工程を十分に把握することが可能になる。
【０１８８】
請求項１３の方法，請求項２９の装置，及び請求項４５のコンピュータプログラムによれば、システムの稼動開始後に何らかの原因で、その入力時刻や加工時間や加工終了時刻が変化した場合でも、全ての工程における変更後の最早終了時刻ｘ〜+E（ｋ）を適確に且つ効率的に把握することができる。
【０１８９】
請求項１４の方法，請求項３０の装置，及び請求項４６のコンピュータプログラムによれば、より単純な算術手順で、全ての工程における変更後の最早終了時刻ｘ〜+E（ｋ）を簡単に把握することができる。
【０１９０】
請求項１５の方法，請求項３１の装置，及び請求項４７のコンピュータプログラムによれば、システムの稼動開始後に何らかの原因で、その出力時刻や加工時間や加工終了時刻が変化した場合でも、全ての工程における変更後の最遅開始時刻ｘ〜-L（ｋ）を適確に且つ効率的に把握することができる。
【０１９１】
請求項１６の方法，請求項３２の装置，及び請求項４８のコンピュータプログラムによれば、より単純な算術手順で、全ての工程における変更後の最遅開始時刻ｘ〜-L（ｋ）を簡単に把握することができる。
【発明を実施するための最良の形態】
【０１９２】
以下、添付図面に基づいて、本発明における好適な各実施例を詳細に説明する。図１は、本発明の第１実施例におけるスケジュール作成装置１の内部構成を示すブロック図である。スケジュール作成装置１は、パーソナルコンピュータ又はサーバ装置などの汎用コンピュータを用いて構成されている。スケジュール作成装置１は、演算を行なうＣＰＵ（演算部）１１と、演算に伴って発生する一時的な情報などを記憶するＲＡＭ（記憶部）１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備えている。ＣＰＵ１１は、ＣＤ−ＲＯＭ等の記録媒体２から本発明のコンピュータプログラム２０を外部記憶装置１３にて読み取り、読み取ったコンピュータプログラム２０を内部記憶装置１４に記憶させる。コンピュータプログラム２０は必要に応じて内部記憶装置１４からＲＡＭ１２へロードされ、ロードされたコンピュータプログラム２０に基づいてＣＰＵ１１はスケジュール作成装置１に必要な処理を実行する。
【０１９３】
スケジュール作成装置１は、キーボード等のオペレータの操作により情報が入力される装置，又は図示しない外部の装置からスケジュール作成のために必要な情報が入力される装置からなる入力装置１５を備えている。またスケジュール装置１は、ＣＲＴディスプレイ等の表示装置，プリンタ装置，又は作成したスケジュールを図示しない外部の装置へ出力する装置からなる取込部としての出力装置１６を備えている。
【０１９４】
なお、本発明のコンピュータプログラム２０は、スケジュール作成装置１に接続された図示しない外部のサーバ装置からスケジュール作成装置１へロードされて内部記憶装置１４に記憶される形態であってもよい。
【０１９５】
本発明のスケジュール作成装置１が行なう処理の目的は、作業プロセスの最適なスケジュールを作成することであり、より具体的には、オペレータが入力装置１５から入力した各種パラメータと、工程間の先行制約とに基づいて、前述したＭＰＬシステムに適合する作業プロセスの状態を表現した式（数７７及び数７８）を、スケジュール作成装置１に作成させるＭＰＬ形式作成手順と、前記ＭＰＬ形式作成手順の途中で導入された行列を利用して、システムの全工程における最早開始時刻及び最遅開始時刻や、トータルフロート（余裕時間）及びボトルネック工程をスケジュール作成装置１に決定させるスケジュール生成手順と、入力時刻，加工（すなわち処理）時間または加工開始時刻の変動値を入力したときに、前記スケジュール生成手順で決定した最早開始時刻及び最遅開始時刻や、トータルフロート及びボトルネック工程が、どのように変化するのかを、前記ＭＰＬ形式作成手順の途中で導入された接続行列Ｆを利用して、スケジュール作成装置１に決定させる再スケジュール生成手順と、をコンピュータプログラム２０に含んでいる。
【０１９６】
そして、このようなコンピュータプログラム２０を記憶した記憶媒体２を外部記憶手段１３に装着すると、スケジュール作成装置１のＣＰＵ１１は当該コンピュータプログラム２０をＲＡＭ１２に自動的にロードし、内蔵する上記各手順を処理実行する。つまりスケジュール作成装置１のＣＰＵ１１は、ソフトウェア上の機能として、オペレータが入力装置１５から入力した各種パラメータと、工程間の先行制約とに基づいて、ＭＰＬシステムに適合する作業プロセスの状態を表現した式（数７７及び数７８）を作成するＭＰＬ形式作成手段３１と、前記ＭＰＬ形式作成手段３１がＭＰＬシステムに適合する作業プロセスの状態を表現した式を作成する途中で導入した各行列を利用して、システムの全工程における最早開始時刻及び最遅開始時刻や、トータルフロート（余裕時間）及びボトルネック工程を決定するスケジュール生成手段３２と、入力時刻，加工時間または加工開始時刻の変動値を入力したときに、前記スケジュール生成手順で決定した最早開始時刻及び最遅開始時刻や、トータルフロート及びボトルネック工程が、どのように変化するのかを、前記ＭＰＬ形式作成手順の途中で導入された接続行列Ｆを利用して決定する再スケジュール生成手段３３と、を備えている。
【０１９７】
ＭＰＬ形式作成手段３１は、スケジュールを作成しようとする作業プロセスにおいて、各工程ｉ（但し、ｉは１以上の自然数で、１≦ｉ≦ｎである）における加工開始時刻及び加工時間を、それぞれ［ｘ（ｋ）］i及びｄi（≧０）とし、初期状態ｘ（０）＝εn1としたときに、システム構造を表現するために、入力された前記各種パラメータから、次の新たに導入された行列Ａ0，Ｆ，Ｂ0，及びＣの各要素を算出し決定する。
【０１９８】
【数１５１】
2007334855.tif 000087
【０１９９】
【数１５２】
2007334855.tif 000088
【０２００】
【数１５３】
2007334855.tif 000089
【０２０１】
【数１５４】
2007334855.tif 000090
【０２０２】
特に、上記数１５２に示す行列Ｆは本発明独自のもので、これを以後、接続行列として呼ぶこととする。また、工程ｉとその先行工程ｊとの関係を、便宜的にｊ→ｉと表記する。ここでは、スケジュールの作成対象となる先行制約と同期制約を有する離散事象システムについて、当該システムに課せられる条件を、次のように設定している。
・工程数をｎとし、外部からの入力数をｐとし、外部への出力数をｑとする。
・各バッチ共に全ての工程を通過し、かつ各工程での加工回数は１回である。
・各工程の設備が稼動中のときには、次のバッチの加工は開始できない。
・先行工程を有する工程は、それらの先行工程の加工が終了しないと、加工を開始できない。
・外部入力のある工程１は、対応する原材料を受取らないと、その加工を開始できない。
・加工開始のための条件が全て揃うと、直ちに加工を開始する。
【０２０３】
ここで、以下の４つの式について、上記各行列Ａ0，Ｆ，Ｂ0，Ｃと、状態変数ｘ（ｋ）や入力変数ｕ（ｋ）との積が、どのような意味を持つのかを考察する。
【０２０４】
【数１５５】
2007334855.tif 000091
【０２０５】
【数１５６】
2007334855.tif 000092
【０２０６】
【数１５７】
2007334855.tif 000093
【０２０７】
【数１５８】
2007334855.tif 000094
【０２０８】
上記数１５６において、Ｓiは工程ｉの先行工程番号の集合を示し、集合Ｓiが空集合φでなければ、右辺上段の式となり、集合Ｓiが空集合φであれば、右辺下段の式となる。また、数１５７において、Ｐiは工程ｉに接続された外部入力番号の集合であり、集合Ｐiが空集合φでなければ、右辺上段の式となり、集合Ｐiが空集合φであれば、右辺下段の式となる。なお、本発明で扱うシステムでは、次の式の関係が成立するものとし、先行工程が存在しない工程ｉは、外部入力が必ず存在する。
【０２０９】
【数１５９】
2007334855.tif 000095
【０２１０】
但し、先行工程と外部入力の両方を有する工程が存在してもよく、上記数１５９の逆は成立しない。さらに、数１５８において、Ｔiは出力ｉに接続された工程番号の集合であり、集合Ｔiが空集合φでなければ、右辺上段の式となり、集合Ｔiが空集合φであれば、右辺下段の式となる。
【０２１１】
上記数１５５の右辺は、工程ｉにおける加工終了時刻を示しており、Ａ0ｘ（ｋ）は、各工程における加工終了時刻を意味する。また数１５６において、Ｆｘ（ｋ＋１）は、先行工程の加工終了時刻の中で最も遅い時刻を表しており、また数１５７において、Ｂ0ｕ（ｋ＋１）は、外部からの入力で最も遅い入力時刻を表すことが分かる。さらに数１５８において、Ｃｘ（ｋ）は、接続された工程の加工終了時刻の中で最も遅い時刻を表している。これらの性質を用いると、各工程における加工開始時刻ｘ（ｋ＋１）および出力時刻ｙ（ｋ）は、次のように定式化できる。
【０２１２】
【数１６０】
2007334855.tif 000096
【０２１３】
【数１６１】
2007334855.tif 000097
【０２１４】
数１６０は、前記数７７と類似した形式であるが、右辺にもｘ（ｋ＋１）が含まれている点で、好ましいＭＰＬシステムの形式の記述とは異なる。以下、数１６０が数７７の形式に変形可能であることや、システム行列の構造について、新たに導入した接続行列Ｆに関するいくつかの性質を説明する。
【０２１５】
接続行列Ｆに関し、ここで３つの定理を示す。
・定理１：接続行列Ｆに関して、Ｆl（ｌ≧１）の対角成分は全てεである。
・定理２：接続行列Ｆに関して、［Ｆl］ij≠ε（１≦[ｉ，ｊ]≦ｎ，ｌ≧１）ならば、［Ｆl］ji＝εが成立する。
・定理３：Ｆl＝εnnを満たすｌ（１≦ｌ≦ｎ）が存在する。
【０２１６】
定理１の証明：  以下、簡略化のために、［Ｆ］ij＝ｆij，［Ｆl］ij＝ｆlijと表記する。ｌ＝１のとき，接続行列Ｆの定義より、当該工程が先行工程にはなり得ないので、明らかにｆij＝εが成立する。次にｌ≧２の時に、分配法則を用いると、次の式が成立する。
【０２１７】
【数１６２】
2007334855.tif 000098
【０２１８】
ここで、ｆlii≠ε（ｌ≧２）と仮定すると、max-plus代数の加算演算子（丸に＋）の性質から、次の式が成り立つような[ｋ1，ｋ2，…ｋl-1]の組が少なくとも一つ存在する。
【０２１９】
【数１６３】
2007334855.tif 000099
【０２２０】
また、ｌ＝１の時の性質により、次の式が成立する。
【０２２１】
【数１６４】
2007334855.tif 000100
【０２２２】
したがって、[ｉ，ｋ1，ｋ2，…ｋl-1]は全て異なる値でなければならない。また、このとき上記数１６３により、次の数１６５に示すような先行制約関係が存在することになる。
【０２２３】
【数１６５】
2007334855.tif 000101
【０２２４】
スケジュール作成対象のシステムに課される制約として、各工程での加工回数は一回であるので、数１６５は工程ｉで二回の加工を行なうことを意味し、題意に矛盾する。よって、背理法により、ｆlii≠ε（ｌ≧２）が成り立ち、定理１が証明される。
【０２２５】
定理２の証明：  前記数１６２と同様にして分配法則を用いると、行列ｆlijは次の式のように表わせる。
【０２２６】
【数１６６】
2007334855.tif 000102
【０２２７】
ここで、max-plus代数の加算演算子（丸に＋）の性質から、ｆlij≠εのときに、次の式となるような互いに異なる[ｉ，ｊ，ｋ1，ｋ2，…ｋl-1]の組が少なくとも一つ存在する。
【０２２８】
【数１６７】
2007334855.tif 000103
【０２２９】
これは、次の式となるような先行制約関係が存在することを意味する。
【０２３０】
【数１６８】
2007334855.tif 000104
【０２３１】
ここで、ｆlji≠εと仮定すると、同様な議論により、互いに異なる[ｉ，ｊ，ｋ’1，ｋ’2，…ｋ’l-1]の組に対して、次の式となるような先行制約関係が存在する。
【０２３２】
【数１６９】
2007334855.tif 000105
【０２３３】
数１６８では、工程ｉは工程ｊより上流側にあることになり、また数１６９では、工程ｊは工程ｉより上流側にあることになるので、互いに矛盾する。よって、背理法により、ｆlji＝ε（１≦[ｉ，ｊ]≦ｎ，ｌ≧１）が成り立ち、定理２が証明される。
【０２３４】
定理３の証明：  あるｌに対して、Ｆl＝εnnが成立するならば、Ｆl+h＝εnn（ｈ≧０）が成り立つことを利用して、背理法で証明する。命題が成り立たないと仮定し、Ｆn≠εnnを仮定する。このとき、ｆnij≠εを満たすような[ｉ，ｊ]の組が少なくとも一つ存在する。数１６６において、ｌ＝ｎとすると、次の式を満たすような、互いに異なる１≦[ｉ，ｊ，ｋ1，ｋ2，…ｋl-1]≦ｎの組が少なくとも一つ存在しなければならないが、集合の要素数がｎ＋１個であるため、このような組は存在しない。従って、Ｆn＝εnnであることが証明される。
【０２３５】
【数１７０】
2007334855.tif 000106
【０２３６】
以上の定理を通して、接続行列Ｆに関する幾つかの性質が明らかになった。次に、システムの構造をＭＰＬシステムの形式で表現できるようにするために、前記数１６０から数７７への変形を行なう。数１６０の右辺第二項に現れるｘ（ｋ＋１）に対して、数１６０自身を代入すると、次の式が得られる。
【０２３７】
【数１７１】
2007334855.tif 000107
【０２３８】
同様な手順を繰り返すと、次の式が得られる。
【０２３９】
【数１７２】
2007334855.tif 000108
【０２４０】
但し、この数１７２におけるＦ*は、次の式のような意味である。
【０２４１】
【数１７３】
2007334855.tif 000109
【０２４２】
前記定理３の結果に基づき、Ｆl＝εnnであるので、数１７２の右辺第一項が消去され、数７７と同様のＭＰＬシステムの形式が得られる。従って、数１７３と数７７とを比較すると、次の式に示す関係が成り立つ。
【０２４３】
【数１７４】
2007334855.tif 000110
【０２４４】
つまり、数１５１〜数１５４で定義された行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ決定し、その後は数１７４に従って、前記行列Ａ0，Ｆ，Ｂ0からＭＰＬシステムの形式に基づく数７７の行列Ａ，Ｂを算出できるように、前記ＭＰＬ形式作成手段３１を構成すれば、数７７及び数７８にて記述されるＭＰＬ形式での状態空間表現を取得することができ、この数７７及び数７８を利用して、システムにおける種々のスケジュール作成を行なうことが可能になる。
【０２４５】
次に、本発明で提案するＭＰＬ形式作成手段３１の作用について、図２に示すフローチャートを参照しながら説明する。
【０２４６】
同図において、先ずステップＳ１では、オペレータが取込部である入力装置１５を利用して、スケジュールの作成対象となるシステムの諸情報（即ち、各種の入力パラメータ）を入力する。ここでの諸情報とは、具体的には各工程ｉの加工時間ｄiや、入力，出力及び各工程間の接続構造である。これらの諸情報が一旦記憶部であるＲＡＭ１２に記憶された後、ＲＡＭ１２から読み出されてＭＰＬ形式作成手段３１に転送されると、ステップＳ２において、各行列Ａ0，Ｆ，Ｂ0，Ｃの全要素を決定する。なお、入力の手間を極力省くために、こうした諸情報の中で、例えばシステム全体の接続構造のモデルを予め記憶媒体２や内部記憶装置１４に何種類か記憶保持しておき、入力装置１５からの操作により、その中からスケジュールの作成対象となるシステムの接続構造を選択してＲＡＭ１２に一時的に記憶させ、そこからＭＰＬ形式作成手段３１に転送してもよい。
【０２４７】
一つの例として、前記図７に示すようなシステムの諸情報がＭＰＬ形式作成手段３１に転送された場合を考える。この例では、４つの工程１〜４の各加工時間がｄ1，ｄ2，ｄ3，ｄ4であるので、ＭＰＬ形式作成手段３１は前記数１５１に基づき、行列Ａ0の対角成分の各要素がそれぞれｄ1，ｄ2，ｄ3，ｄ4であり、それ以外の各要素が全てεであるとして、４行４列からなる行列Ａ0の全要素を決定する。また、転送されたシステムの接続構造から、工程１が先行工程を持っておらず、工程２及び工程３が先行工程１を持っており、工程４が先行工程２及び先行工程３を持っていることから、ＭＰＬ形式作成手段３１は前記数１５２に基づき、接続行列Ｆについて、２行１列と３行１列の各要素が何れもｄ1であるとし、４行２列の要素がｄ2であるとし、４行３列の要素がｄ3であるとし、それ以外の各要素が全てεであるとして、４行４列からなる接続行列Ｆの全要素を決定する。さらに、転送されたシステムの接続構造から、入力数は１であり、且つ工程１だけが入力１を持つことから、ＭＰＬ形式作成手段３１は前記数１５２に基づき、１行１列の要素がｅであるとし、それ以外の各要素が全てεであるとして、４行１列からなる行列Ｂ0の全要素を決定する。これを式で表現すると、次のようになる。
【０２４８】
【数１７５】
2007334855.tif 000111
【０２４９】
また行列Ｃは、従来から知られている数８４の行列Ｃと同じものであり、転送されたシステムの接続構造から、出力数は１であり、且つ工程４だけが出力１を持つことから、ＭＰＬ形式作成手段３１は前記数１５４に基づき、１行４列の要素がｄ4ｅあるとし、それ以外の各要素が全てεであるとして、１行４列からなる行列Ｃの全要素を決定することができる。
【０２５０】
このように、ＭＰＬ形式作成手段３１はシステムの諸情報が与えられれば、ステップＳ２の手順で簡単に各行列Ａ0，Ｆ，Ｂ0，Ｃの全要素を決定することができる。
【０２５１】
こうして、ＭＰＬ形式作成手段３１は行列Ａ0，Ｆ，Ｂ0，Ｃの全要素を決定すると、次のステップＳ３において、行列Ｆ*の算出を行なう。これは先ず、工程の数ｎ（この例では４）以下の範囲で、全ての要素がεになるまで、前記数１７３を計算し、次に全ての要素がεになる直前の行列が、前記数１７３における行列Ｆl-1であるとして、この数１７３に基づき行列Ｆ*を算出する。次の式は、ＭＰＬ形式作成手段３１で算出した行列Ｆ2，Ｆ3及びＦ*をそれぞれ示している。
【０２５２】
【数１７６】
2007334855.tif 000112
【０２５３】
図７に示す例では、行列Ｆ3を計算すると、全ての要素がεになるので、行列ｅ4（対角成分の要素がｅで、それ以外の全ての要素はε）と、接続行列Ｆと、接続行列Ｆを二乗した行列Ｆ2を加算することで、数１７６に示すように、行列Ｆ*を簡単に算出できる。
【０２５４】
こうして行列Ｆ*を算出すると、ＭＰＬ形式作成手段３１は必要に応じ、ステップＳ４において、ＭＰＬシステムの形式に従う全ての行列Ａ，Ｂ，Ｃを算出する。行列Ａ及び行列Ｂに関しては、前記数１７４を利用して、ステップＳ３で求めた行列Ｆ*と、ステップＳ２で求めた行列Ａ0及び行列Ｂ0とを乗算すれば簡単に算出できる。また行列Ｃは、前記ステップＳ２で求めたものをそのまま適用すればよい。こうして得られた行列Ａ，Ｂ，Ｃは、前記従来例で示した数８４と一致する。つまり、上述した条件を満たすシステムでは、システムの振る舞いをＭＰＬ形式での式（数７７及び数７８）で簡単に記述することができる。このように、本実施例のＭＰＬ形式作成手段３１は、工程の実行順序を規定する先行制約関係と、各工程における実行時間が所与の条件として与えられ、そのときにシステムの構造を表現する行列として、数１５１〜数１５４の各行列を利用することで、ＭＰＬ形式での状態空間表現を簡単に導出することができる、
次に、スケジュール生成手段３２の具体的な構成について説明する。スケジュール生成手段３２は、前記接続行列Ｆを利用して、全ての行程について最早開始時刻及び最遅開始時刻を算出すると共に、この算出した最遅開始時刻から最早開始時刻を減算することで、全ての行程におけるトータルフロートの算出とボトルネック工程の抽出を行なうものである。なお、これ以降の説明では、全工程の最早開始時刻をｘEとし、全工程の最遅開始時刻をｘLとして表記すると共に、簡略化のために、必要に応じてイベントカウンタ（ｋ＋１）の記述を省略する。
【０２５５】
スケジュール生成手段３２が算出する最早開始時刻ｘEは、その工程が最も早く加工を開始できる時刻として定義される。工程ｉ（１≦ｉ≦ｎ）の最早開始時刻ＥＴiは、次の式のように表わせる。
【０２５６】
【数１７７】
2007334855.tif 000113
【０２５７】
ここで集合Ｓiと集合Ｐiは、数１５６及び数１５７で用いたものと同一である。上記数１７７の右辺第一項は、外部入力を有する場合の入力時刻のうち、最大の値を表しており、集合Ｐiが空集合φの場合、即ちＰi＝[φ]の場合はεとする。前記数１５７により、数１７７の右辺第一項に関して次の式が成り立つ。
【０２５８】
【数１７８】
2007334855.tif 000114
【０２５９】
数１７７の右辺第二項は、先行工程における加工終了時刻の中で最大の値を表しており、集合Ｓiが空集合φの場合、即ちＳi＝[φ]の場合はεとする。前記数１５６により、数１７７の右辺第二項に関して次の式が成り立つ。
【０２６０】
【数１７９】
2007334855.tif 000115
【０２６１】
数１７７の右辺第三項は、当該工程の前のバッチにおける加工終了時刻のうち、最大のものを表している。前記数１５５を用いると、数１７７の右辺第二項に関して次の式が成り立つ。
【０２６２】
【数１８０】
2007334855.tif 000116
【０２６３】
従って、工程ｉ（１≦ｉ≦ｎ）の最早開始時刻［ＸE］iは、次のように表わせる。
【０２６４】
【数１８１】
2007334855.tif 000117
【０２６５】
これは、数１６０と同一形式をしており、即ち数７７のｘ（ｋ＋１）をＸEに置き換えたものに等しいことが分かる。そのため、全工程ｉの最早開始時刻ＸEは、次のように表される。
【０２６６】
【数１８２】
2007334855.tif 000118
【０２６７】
また、このときの加工終了時刻は、次の式で与えられる。
【０２６８】
【数１８３】
2007334855.tif 000119
【０２６９】
つまり、スケジュール生成手段３２は、前記ＭＰＬ形式作成手段３１で算出して得られ、ＲＡＭ１２に記憶された行列Ａ0，Ｂ0，及びＦ*を用いることで、数１８２により全ての工程ｉにおける最早開始時刻ＸEを簡単に算出でき、またこの最早開始時刻ＸEと、ＭＰＬ形式作成手段３１で算出して得られ、ＲＡＭ１２に記憶された行列Ｃとを用いることで、数１８３によりシステムの加工終了時刻ｙを簡単に算出できる。
【０２７０】
次に、スケジュール生成手段３２が算出する最遅開始時刻について説明すると、当該最遅開始時刻とは、ある工程において、最早開始時刻で加工を行なった場合と同一の出力時刻を実現することが可能な、最も遅い加工開始時刻として定義される。工程ｉ（１≦ｉ≦ｎ）の最遅開始時刻ＬＴiは、次の式のように表わせる。
【０２７１】
【数１８４】
2007334855.tif 000120
【０２７２】
上記数１８４において、Ｑiは工程ｉに接続された外部出力番号の集合を示し、Ｒiは工程ｉの後続工程番号の集合を示している。なお、本発明で扱うシステムでは、次の式の関係が成立するものとし、後続工程が存在しない工程ｉは、外部出力が必ず存在する。
【０２７３】
【数１８５】
2007334855.tif 000121
【０２７４】
但し、後続工程と外部出力の両方を有する工程が存在してもよく、上記数１８５の逆は成立しない。前記数１８４の右辺第一項は、外部出力を有する場合の出力時刻のうち、最小の値を表しており、集合Ｑiが空集合φの場合、即ちＱi＝[φ]の場合は−εとする。また、数１８４の右辺第二項は、後続行程を有する場合の加工開始時刻のうち、最小の値を表しており、集合Ｒiが空集合φの場合、即ちＲi＝[φ]の場合は−εとする。前記数１８５を用いると、工程ｉの最遅開始時刻［ＸL］iは、全ての工程ｉで有限な値をとることが確かめられる。数１８４は、次の式のように変形できる。
【０２７５】
【数１８６】
2007334855.tif 000122
【０２７６】
上記の式が任意の工程ｉ（１≦ｉ≦ｎ）に対して成立するので、全工程ｉの最遅開始時刻ＸLは、次のように表される。
【０２７７】
【数１８７】
2007334855.tif 000123
【０２７８】
上記数１８７をより簡潔な形式で表現するために、次の三つの定理を導入する。
・定理４：Ａ，Ｂ∈Ｄl×m，ｘ∈Ｄmにおいて、次の式が成立する。
【０２７９】
【数１８８】
2007334855.tif 000124
【０２８０】
・定理５：Ａ∈Ｄl×m，Ｂ∈Ｄn×l，ｘ∈Ｄnにおいて、次の式が成立する。
【０２８１】
【数１８９】
2007334855.tif 000125
【０２８２】
・定理６：Ａ∈Ｄl×m，  ｘ，ｙ∈Ｄnにおいて、次の式が成立する。
【０２８３】
【数１９０】
2007334855.tif 000126
【０２８４】
定理４は既に証明されており、ここでは改めて説明しない。
【０２８５】
定理５の証明：  ｌ＝ｍ＝ｎ＝１，すなわち、Ａ，Ｂ，Ｘが全てスカラーの場合の証明は、既に知られている。数１８９について、その左辺の第ｉ成分は、次の式のように計算できる。
【０２８６】
【数１９１】
2007334855.tif 000127
【０２８７】
一方、数１８９の右辺の第ｉ成分は、次の式のように計算できる。
【０２８８】
【数１９２】
2007334855.tif 000128
【０２８９】
演算子∧の順序は交換可能であるので、全てのｉ（１≦ｉ≦ｎ）において数１９１と数１９２は共に等しく、定理５が証明される。
【０２９０】
定理６の証明：  ｌ＝ｍ＝ｎ＝１，すなわち、Ａ，Ｂ，Ｘが全てスカラーの場合の証明は、既に知られている。数１９０について、その第ｉ成分は、次の式のように計算できる。
【０２９１】
【数１９３】
2007334855.tif 000129
【０２９２】
これが全てのｉ（１≦ｉ≦ｎ）において成立するので、定理６が証明される。
【０２９３】
前記定理５及び定理６を用いて、数１８７の両辺に次の式を施す。
【０２９４】
【数１９４】
2007334855.tif 000130
【０２９５】
すると、数１８７は次の式のように表わせる。
【０２９６】
【数１９５】
2007334855.tif 000131
【０２９７】
以下、同様にして、次の式を導出できる。
【０２９８】
【数１９６】
2007334855.tif 000132
【０２９９】
数１９３，数１９５及び数１９６を用いて逐次的に代入を繰り返し、前記定理４及び定理５を用いると、全工程ｉの最遅開始時刻ＸLは、次のように表される。
【０３００】
【数１９７】
2007334855.tif 000133
【０３０１】
上式のｙについて、前記数１８３の式を代入すると、最終的に求めようとする全工程ｉの最遅開始時刻ＸLは、次のように表される。
【０３０２】
【数１９８】
2007334855.tif 000134
【０３０３】
つまり、スケジュール生成手段３２は、前記ＭＰＬ形式作成手段３１で算出して得られ、ＲＡＭ１２に記憶された行列Ｃ及びＦ*と、先にスケジュール生成手段３２により算出され、ＲＡＭ１２に記憶された最早開始時刻ＸE及び出力時刻ｙとを用いることで、数１９８により全ての工程ｉにおける最遅開始時刻ＸLを簡単に算出できる。
【０３０４】
さらに、同一の出力時刻ｙを実現するための最も遅い入力時刻ｕLは、外部入力を有する工程の最遅開始時刻に等しく、次の式のように計算できる。
【０３０５】
【数１９９】
2007334855.tif 000135
【０３０６】
これが任意の工程ｉ（１≦ｉ≦ｐ）について成立し、前記数１９７と定理５を考慮すれば、最遅入力時刻ｕLは次の式のように表わせる。
【０３０７】
【数２００】
2007334855.tif 000136
【０３０８】
スケジュール生成手段３２は、上記数１８３や数１９８で求め、ＲＡＭ１２に記憶された最早開始時刻ＸEと最遅開始時刻ＸLを利用して、トータルフロートがゼロとなるボトルネック工程の抽出を抽出することができる。トータルフロートとは、当該工程が持つ余裕時間の総合計で定義され、後続工程が出力時刻に影響を及ぼさない範囲で最も遅く加工を開始する場合の時刻と、当該工程が最も早く加工を開始した場合の加工終了時刻との差で表わすことができる。工程ｉ（１≦ｉ≦ｎ）のトータルフロートＴＦiは、次の式のように表わせる。
【０３０９】
【数２０１】
2007334855.tif 000137
【０３１０】
ここで集合Ｑiと集合Ｒiは、数１８４で用いたものと同様に、工程ｉに接続された外部出力番号の集合と、工程ｉの後続工程番号の集合をそれぞれ示している。また、数２０１の右辺第一項は後続工程に関する制約を表わし、右辺第２項は外部出力への出力時刻に関する制約を表わす。なお、集合Ｑiや集合Ｒiが空集合φの場合、即ちＱi＝[φ]やＲi＝[φ]の場合は、該当する演算子∧を−εとする。しかし、前記数１８５の関係を用いると、トータルフロートＴＦiは、全ての工程ｉにおいて有限な値をとることがわかる。
【０３１１】
上記数２０１を簡潔に表現するために、ここでは次の式のような変形を行なう。
【０３１２】
【数２０２】
2007334855.tif 000138
【０３１３】
上の数２０２は任意の工程ｉ（１≦ｉ≦ｎ）に対して成立するので、全工程ｉのトータルフロートをｗとして表わすと、このトータルフロートｗは次の式が成り立つ。
【０３１４】
【数２０３】
2007334855.tif 000139
【０３１５】
上記数１８７及び定理５と定理６を適用すると、上記数２０３の右辺の一部は、次のように変形できる。
【０３１６】
【数２０４】
2007334855.tif 000140
【０３１７】
ただし、途中で表れるＦ+*は、次のような意味を持つ。
【０３１８】
【数２０５】
2007334855.tif 000141
【０３１９】
上記数２０５は、次の式の関係を満足する。
【０３２０】
【数２０６】
2007334855.tif 000142
【０３２１】
数２０３と数２０４によれば、結局、全工程ｉのトータルフロートｗは、次の式のように求められ、最遅開始時刻ＸLから最早開始時刻ＸEを減算した値となる。
【０３２２】
【数２０７】
2007334855.tif 000143
【０３２３】
ボトルネック工程は、トータルフロートｗが０になる工程の集合として与えられ、これを数式で表わすと次のようになる。
【０３２４】
【数２０８】
2007334855.tif 000144
【０３２５】
つまり、スケジュール生成手段３２は、先にスケジュール生成手段３２が算出した最早開始時刻ＸEと最遅開始時刻ＸLを用いることで、数２０７や数２０８により全ての工程ｉにおけるトータルフロートｗと、どの工程がボトルネックとなっているのかを簡単に抽出できる。
【０３２６】
図３は、上記スケジュール生成手段３２の一連の動作をフローチャートで示したものである。同図において、ステップＳ１１では、スケジュール生成手段３２がＭＰＬ形式作成手段３１から行列Ａ0，Ｂ0，及びＦ*の算出結果を受取ると共に、入力装置１５から初期状態として工程の加工開始時刻ｘ（ｋ）と外部入力時刻ｕを受取ると、数１８２に基づき全ての工程ｉにおける最早開始時刻ＸEを算出する。また、このステップＳ１１では、最早開始時刻ＸEとＭＰＬ形式作成手段３１から取得した行列Ｃの算出結果とを用いて、数１８３により加工終了の出力時刻ｙも算出できる。
【０３２７】
こうして、全ての工程ｉにおける最早開始時刻ＸEや出力時刻ｙを算出すると、スケジュール生成手段３２は数１９８に基づき、全ての工程ｉにおける最早開始時刻ＸEを算出する（ステップＳ１２）。この最早開始時刻ＸEの算出に際しては、ＭＰＬ形式作成手段３１で算出して得られた行列Ｃ及びＦ*と、先にスケジュール生成手段３２が算出した最早開始時刻ＸE及び出力時刻ｙを用いる。
【０３２８】
次にスケジュール生成手段３２は、全ての工程ｉにおけるトータルフロートｗを、ステップＳ１１で算出した最早開始時刻ＸEと、ステップＳ１２で算出した最遅開始時刻ＸLから計算する（ステップＳ１３）。このトータルフロートｗは、前記数２０７から簡単に計算できる。最後に、スケジュール生成手段３２は全ての工程ｉのトータルフロートｗを算出すると、ステップＳ１４において、数２０８に基づきどの行程がボトルネックとなっているのかを抽出する。
【０３２９】
次に、再スケジュール生成手段３３の具体的な構成について説明する。前述のスケジュール生成手段３２は、外部からの入力時刻ｕや、各工程ｉの加工時間ｄi等、システムの稼動が全て決められた通りに実行される状況を仮定しているが、実際には、出力時刻ｙに影響を及ぼしうるような変動要因として、次のような変動が、バッチの加工開始後にしばしば発生する。（１）材料到着時刻の変動：外部入力時刻ｕに影響を及ぼす。（２）加工時間の変動：システムパラメータｄひいては各行列Ａ0，Ｃ，Ｆに影響を及ぼす。（３）加工開始時刻の変動：状態変数８４に影響を及ぼす。
【０３３０】
これらの変動よって、当初の計画から、スケジュール生成手段３２で算出した最早開始時刻ＸE，最遅開始時刻ＸL，またはボトルネック工程が変化することもあるため、工程管理やプロジェクトマネジメントにおいては、効率的な再スケジューリングを考えることは重要である。再スケジュール生成手段３３は、入力時刻，加工時間，加工開始時刻などの変更情報を入力として、各工程ｉにおける最早開始時刻ＸEおよび最遅開始時刻ＸLや、ボトルネックとなる工程がどのように変化したのかを再度見直す機能を有している。
【０３３１】
いま、バッチの加工開始後に何らかの原因で、その入力時刻，加工時間，加工開始時刻などが変化したと仮定する。入力時刻と加工開始時刻については、外部入力時刻ｕと該当する工程ｉの加工開始時刻［ｘ(0)］iにそれぞれ影響を及ぼすことから、これらの外部入力時刻ｕや開始時刻［ｘ(0)］iの変化後における状態を、それぞれ記号の上または横にシンボル〜をつけて次の式のように表わす。
【０３３２】
【数２０９】
2007334855.tif 000145
【０３３３】
また、加工時間に関する変動は、前述のようにシステム行列Ａ0，出力行列Ｃ，接続行列Ｆに影響を及ぼすことから、これらの記号の上または横にもシンボル〜をつけて次の式のように表わす。
【０３３４】
【数２１０】
2007334855.tif 000146
【０３３５】
なお定義により、入力行列Ｂ0は変化しない。これらを用いて、変化後の状態変数を再計算する。まず、再計算の対象となる工程ｉについて、次の式を設定する。
【０３３６】
【数２１１】
2007334855.tif 000147
【０３３７】
ここでは、既に加工開始済の工程や、加工開始前であっても、遅延などにより開始時刻が既に決められている工程は、再計算の対象とはしない。前記数１８１と同様の手順により、再計算対象の工程の中で最上流に位置する工程ｉの最早開始時刻[ｘ〜(1)]iは，次のように表せる。
【０３３８】
【数２１２】
2007334855.tif 000148
【０３３９】
ここでの最上流とは、先行工程が全て加工開始済であるような工程のことを意味し、複数存在する場合もある。また、行列Ａ0〜は、前のバッチに関する加工時間を表現した行列であるので、前のバッチの加工時間が変化しない時には、行列Ａ0に置き換えて計算する。以下、数１７１と同様な手順によって、後続工程の最早開始時刻を逐次的に計算する。
【０３４０】
【数２１３】
2007334855.tif 000149
【０３４１】
なお、成分[・]iの表記は省略している。更新後の最早開始時刻ｘ〜Eは、次のとおり求められる。
【０３４２】
【数２１４】
2007334855.tif 000150
【０３４３】
数２１２と数２１３を用いると、上記数２１４は次の式に変形できる。
【０３４４】
【数２１５】
2007334855.tif 000151
【０３４５】
数２１５は、数１８１をバッチの加工開始後にパラメータが変化した場合にも適用できるような一般化した形式となっている。加工開始前であれば、全ての工程ｉ（１≦ｉ≦ｎ）に対して、次の式が成立するので、これは数１８２と同一となる。
【０３４６】
【数２１６】
2007334855.tif 000152
【０３４７】
特別な場合として、ある工程の加工開始時刻が遅延した場合（但し、プロセスの加工時間ｄiは変化しない）を考える。このとき、遅延が判明した工程の成分のみ値を置き換えると、全ての工程ｉ（１≦ｉ≦ｎ）に対して、次の式が成立する。
【０３４８】
【数２１７】
2007334855.tif 000153
【０３４９】
この場合、数２１７に現れる各行列の値は変化しないことから、次の関係が成立する。
【０３５０】
【数２１８】
2007334855.tif 000154
【０３５１】
従ってこの場合は、一般式である数２１５を次の式のように簡潔に表現することができる。
【０３５２】
【数２１９】
2007334855.tif 000155
【０３５３】
この時に対応する出力時刻ｙ〜と、最遅開始時刻ｘL〜と、ボトルネック工程の抽出は、それぞれ前記数１８３，数１９７，数２０８に対応して、次の式のように求められる。
【０３５４】
【数２２０】
2007334855.tif 000156
【０３５５】
【数２２１】
2007334855.tif 000157
【０３５６】
ボトルネック工程は、システム先行制約関係と、加工時間などにより決定されるが、稼動開始後にこれらのパラメータの値が変化すると、それに伴ってボトルネック工程の位置も変化することがある。その例については、後ほど説明する。
【０３５７】
このように、本実施例における再スケジュール生成手段３３は、変動した入力時刻，ある工程における加工時間，またはある工程における加工開始時刻が、変動パラメータとして入力されたのを受けて、数２１５または数２１９に基づいて、更新後の最早開始時刻ｘ〜Eを算出する。そして、数２２０に基づいて、更新後の出力時刻ｙ〜および最遅開始時刻ｘL〜を各々算出し、さらに数２２１に基づいて、ボトルネック工程の抽出を行なうようにしている。これによって、例えばシステムの稼動中に出力時刻ｙに影響を及ぼしうる変動が発生した場合でも、システムの出力時刻ｙ〜のみならず、各工程ｉ毎における最早開始時刻ｘ〜Eや最遅開始時刻ｘL〜の算出と、それにより得られる更新後のボトルネック工程を適確に抽出することができる。
【０３５８】
なお、変動パラメータの入力は、例えばオペレータが入力装置１５を介して入力するのではなく、各工程ｉ毎に製品の移動状況を感知するセンサを備え、このセンサから得られた感知情報と、内蔵する計時手段とにより、人手を介さず自動的に入力できる構成としてもよい。
【０３５９】
図４は、上記スケジュール再生成手段３３の一連の動作をフローチャートで示したものである。同図において、ステップＳ２１では、スケジュール再生成手段３３に変動パラメータが入力されると、その入力した変動パラメータについて、スケジュール再生成手段３３は、ある工程の加工開始時刻だけが変動した場合なのか否かを判断する。そして、もしそうであれば、ステップＳ２２の手順に進み、数２１９に基づいた簡単な算出式によって、更新後の各工程ｉ毎における最早開始時刻ｘ〜Eを算出し、そうでなければ、別なステップＳ２３の手順に進み、数２１５に基づいた一般的な算出式によって、更新後の各工程ｉ毎における最早開始時刻ｘ〜Eを算出する。こうして得られた最早開始時刻ｘ〜Eは、一時的にＲＡＭ１２に記憶される。
【０３６０】
こうして、最早開始時刻ｘ〜Eの算出が終了すると、スケジュール再生成手段３３はステップＳ２４において、数２２０に基づき更新後の出力時刻ｙ〜および最遅開始時刻ｘL〜を各々算出し、一時的にＲＡＭ１２に記憶する。そして最後にスケジュール再生成手段３３は、ステップＳ２５において、ＲＡＭ１２から読み出した最早開始時刻ｘ〜Eおよび最遅開始時刻ｘL〜を利用し、数２２１に基づいて更新後のボトルネック工程の抽出を行なう。
【０３６１】
次に、表１に示すような先行制約を有する簡単な生産システムを例にして、上述したスケジュール作成装置１の作用を説明する。
【０３６２】
【表１】
2007334855.tif 000158
【０３６３】
表１は、スケジュール作成の対象となる生産システムに課せられたパラメータを示している。ここでは、各工程１〜５に対して、その加工時間と、先行工程の番号と、入力番号と、出力番号の各パラメータが示されている。この表１に基づき、当該生産システムの先行制約や、外部への入出力位置の関係を、図５の模式図で示している。
【０３６４】
表１に示すような各工程のパラメータが、スケジュール作成装置１のＭＰＬ形式作成手段３１に取り込まれると、当該ＭＰＬ形式作成手段３１は、数１５１〜数１５４の定義に基づいて、生産システムの構造を表現する行列Ａ0，Ｆ，Ｂ0，及びＣの各要素を算出し決定する。行列Ａ0は、工程数をｎとしたときに、ｎ次の正方行列で表され、その対角成分が各工程ｉの加工時間ｄiとなり、それ以外の成分がεとなる。行列Ｆもｎ次の正方行列で表され、工程ｉが先行工程ｊを有するｉ行ｊ列の成分が、先行工程ｊの加工時間ｄjとなり、それ以外の成分がεとなる。行列Ｂ0は、工程数に等しい行と、入力数に等しい列で表わされ、工程ｉが入力ｊを有する場合は、ｉ行ｊ列の成分がｅとなり、それ以外の成分はεとなる。さらに行列Ｃは、出力数に等しい行と、工程数に等しい列で表わされ、工程ｊが入力ｉを有する場合は、ｉ行ｊ列の成分が工程ｊの加工時間ｄjとなり、それ以外の成分はεとなる。したがって、表１に示す生産システムの例では、各行列Ａ0，Ｆ，Ｂ0，及びＣが次のように表わされる。
【０３６５】
【数２２２】
2007334855.tif 000159
【０３６６】
なお、上の式中でdiagとは、対角行列の各成分を意味する。またＴは転置行列を意味する。ＭＰＬ形式作成手段３１は続いて、全ての要素がεになるまで、前記接続行列Ｆの累乗（Ｆ2，Ｆ3…）を逐次的に計算する。この生産システムの例では、Ｆ4＝ε55となって、行列中の全ての要素がεになるので、結局Ｆ*は次の式のように計算される。
【０３６７】
【数２２３】
2007334855.tif 000160
【０３６８】
ここで、生産システムの初期状態として、加工開始時間をｘ（ｋ）＝ε51とし、外部入力の時刻をｕ＝［０  ０］Ｔとすると、スケジュール生成手段３２は、前記数１８２及び数１８３に基づいて、各工程ｉにおける最早開始時刻ｘEと、システムの加工終了時刻ｙを次の式のようにそれぞれ算出することができる。
【０３６９】
【数２２４】
2007334855.tif 000161
【０３７０】
続いてスケジュール生成手段３２は、前述の数１９８，数２００及び数２０７をそれぞれ用いて、全工程ｉの最遅開始時刻ＸL，最遅入力時刻ｕL及びトータルフロートｗを次の式のように算出する。
【０３７１】
【数２２５】
2007334855.tif 000162
【０３７２】
即ち、工程１〜５の最遅開始時刻ＸLは、それぞれ０，１，２，４，７であり、入力１及び入力２の最遅入力時刻ｕLは、それぞれ０及び２である。さらに、工程１〜５のトータルフロートｗは、それぞれ０，０，１，１，０であり、工程３，４は、１時間単位の余裕があることが分かる。スケジュール生成手段３２は、数２２５で得た結果から、トータルフロートｗが０である工程、即ち遅れ時間が許されない工程１，２，５を、ボトルネック工程の集合[１，２，５]として抽出することができる。スケジュール生成手段３２により判明した各工程の資源使用計画を、ガントチャートで示したのが図６である。この図６に示すガントチャートは、スケジュール作成装置１がソフトウェアの機能として作成し、出力装置１６に出力させることが可能である。
【０３７３】
次に、上記生産システムを例にして、パラメータに変化が生じた場合における、再スケジュール生成手段３３の動作について検討する。いま、時刻ｔ＝４において、工程４の加工開始時刻が、［ｘ〜(0)］4＝５に遅れることが判明したとする。この変動したパラメータの値を再スケジュール生成手段３３が取得すると、再スケジュール生成手段３３は取得した変更後の加工開始時刻が、元の加工開始時刻よりも大きく、遅延していると判断すれば、前記数２１９及び数２２０（但し、この場合は加工開始時刻のみ変更するため、変更後の行列Ｃ〜を算出する必要がなく、数２２０の行列Ｃ〜は行列Ｃとして計算できる。）に基づいて、新たな最早開始時刻と出力時刻を次のように算出する。
【０３７４】
【数２２６】
2007334855.tif 000163
【０３７５】
なお、上式において、下線を引いた成分が、遅延した開始時刻を示している。数２２６の算出結果によれば、更新した工程１〜５の最早開始時刻Ｘ〜Eは、数２２４で算出した当初の０，１，１，３，７から、それぞれ０，１，１，５，８となり、また出力時刻ｙ〜は、数２２４で算出した当初の１１から１２に遅れることが分かる。この場合、工程４の加工開始時刻は、数２２４で算出した最早開始時刻に対し２時間単位の遅延を生じているが、工程４はボトルネック工程ではないため、終了時刻は１単位時間のみ遅延している。さらに、再スケジュール生成手段３３は、パラメータ変化後における最遅開始時刻Ｘ〜Lとトータルフロートｗを、次の式のように算出することができる。
【０３７６】
【数２２７】
2007334855.tif 000164
【０３７７】
従って、工程１〜５のトータルフロートｗは、それぞれ１，１，２，０，０となり、今度は前記数２２１によって、遅れ時間が許されないボトルネック工程の集合が[４，５]に移動する。そのため、それまで１時間単位の余裕のあった工程４は遅れが許されず、逆にそれまでボトルネック工程であった工程２が、１単位時間の余裕を持つことが分かる。
【０３７８】
このように、本実施例で示した手法を用いることで、先行制約を持つ生産システムのスケジューリングや、プロジェクトマネジメントにおいて、工程計画やボトルネック工程の把握を容易に行なうことができ、またシステムの稼動開始後に予期せぬパラメータの変化が生じた場合でも、望ましい再スケジューリングが可能となる。
【０３７９】
以上のように本実施例では、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を入力パラメータとして取り込む取込部（入力装置１５）と、前記取込部で取り込んだ入力パラメータを記憶する記憶部（ＲＡＭ１２）と、前記離散事象システムの状態を数７７や数７８の式で表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換する演算部（ＣＰＵ１１）と、を備えたスケジュール作成装置１において、前記演算部は、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記記憶部から読み出した入力パラメータに基づいて、上記数１５１〜数１５４で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ決定し、前記行列Ｆを用いて、上記数１７３の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を算出するＭＰＬ形式作成手段３１を備えて構成される。
【０３８０】
また本実施例では、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記記憶部から読み出した入力パラメータに基づいて、上記数１５１〜数１５４で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ前記演算部で決定する第１のステップと、前記行列Ｆを用いて、上記数１７３の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を前記演算部で算出する第２のステップと、を順次実行するものである。
【０３８１】
また本実施例では、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を、入力パラメータとしてコンピュータであるスケジュール作成装置１に取り込ませ、この入力パラメータを前記コンピュータに記憶させ、さらに前記離散事象システムの状態を表現するために、前記入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるように前記コンピュータに演算を行なわせるコンピュータプログラム２０において、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおける実行時間をｄiとしたときに、前記入力パラメータに基づいて、上記数１５１〜数１５４で定義されたシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃの各要素をそれぞれ決定させる第１の手順と、前記行列Ｆを用いて、上記数１７３の行列Ｆ*（但し、Ｆlにおいて全ての要素がεになり、またｎは工程数である）を算出させる第２の手順と、を前記コンピュータに実行させている。
【０３８２】
このようなスケジュール作成装置１，スケジュール作成方法，及びコンピュータプログラム２０であれば、従来技術のようにわざわざ複数の数式（数７９〜数８３）を作成し、そこから任意の数式を適宜代入して、複雑な計算手法によりmax-plus代数上で線形なＭＰＬ形式の式（数７７及び数７８）に含まれる行列Ａ，Ｂ，Ｃを算出しなくても、入力パラメータとして、各工程ｉの実行時間ｄiと工程ｉ間の先行制約関係の各情報がスケジュール作成装置１に記憶されていれば、そこからスケジュール作成装置１が独自のシステム構造を表現する行列Ａ0，Ｆ，Ｂ0，Ｃについて、その各要素を決定し、さらにここで決定した行列Ｆから行列Ｆ*を算出して、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ａ0，Ｆ*，Ｂ0，Ｃを簡単に取得することができる。したがって、システムのスケジュール作成をコンピュータで実現する上で、より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に簡単に導出することが可能になる。
【０３８３】
本実施例におけるスケジュール作成装置は、ｋ番目の工程処理に関して、各工程での処理開始時刻をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記ＭＰＬ形式作成手段３１で算出した行列Ａ0，Ｂ0，及びＦ*と、例えば取込部や記憶部から演算部に取り込まれる前記処理開始時刻ｘ（ｋ）及び入力時刻をｕ（ｋ）とを利用して、前記数１８２に基づき全ての工程の最早開始時刻ｘEを算出するスケジュール生成手段３２を前記演算部が備えている。
【０３８４】
また、本実施例におけるスケジュール作成方法は、前記第１及び第２のステップで算出した行列Ａ0，Ｂ0，及びＦ*と、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）及び入力時刻をｕ（ｋ）とを利用して、前記数１８２に基づき全ての工程の最早開始時刻ｘEを前記演算部で算出する第３のステップをさらに備えている。
【０３８５】
また、本実施例におけるコンピュータプログラム２０は、前記処理開始時刻ｘ（ｋ）及び入力時刻ｕ（ｋ）を取り込ませ、この処理開始時刻ｘ（ｋ）及び入力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ａ0，Ｂ0，及びＦ*とを利用して、前記数１８２に基づき全ての工程の最早開始時刻ｘEを算出させる第３の手順を、前記コンピュータにさらに実行させている。
【０３８６】
こうすれば、初期状態の処理開始時刻ｘ（ｋ）と入力時刻ｕ（ｋ）が取り込まれれば、先に算出した行列Ａ0，Ｂ0，及びＦ*を利用して、システムを構成する全ての工程の最早開始時刻ｘEを簡単に算出することができる。
【０３８７】
さらに、本実施例におけるスケジュール作成装置は、前記演算部で算出した行列Ｃ及びＦ*と、前記全ての工程の最早開始時刻ｘEとを利用して、前記数１９８に基づき全ての工程の最遅開始時刻ｘLを算出するように、前記演算部を構成している。
【０３８８】
こうすれば、先に算出した行列Ｃ及びＦ*と、全ての工程の最早開始時刻ｘEとを利用して、システムを構成する全ての工程の最遅開始時刻ｘLを簡単に算出することができる。
【０３８９】
そしてこれは、前記第１および第２のステップで算出した行列Ｃ及びＦ*と、前記第３のステップで算出した前記全ての工程の最早開始時刻ｘEとを利用して、前記数１９８に基づき全ての工程の最遅開始時刻ｘLを前記演算部で算出する第４のステップをさらに備えたスケジュール作成方法や、前記第１および第２の手順で算出させた行列Ｃ及びＦ*と、前記第３のステップで算出させた前記全ての工程の最早開始時刻ｘEとを利用して、前記数１９８に基づき全ての工程の最遅開始時刻ｘLを前記演算部で算出させる第４の手順を、前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０３９０】
本実施例におけるスケジュール作成装置の演算部は、前記最遅開始時刻ｘLから前記最早開始時刻ｘEを減算することで、全工程ｉのトータルフロートｗを算出すると共に、このトータルフロートｗの値が０になる工程を検索し、それをボトルネック工程として抽出する機能を有する。
【０３９１】
つまり、全ての工程における最早開始時刻ｘEや最遅開始時刻ｘLが算出されていれば、後は簡単な演算処理によって全ての工程の余裕時間と、ボトルネック工程がどこに存在するのかを簡単に算出することができる。したがって、途中工程の稼動状態や、ボトルネック工程を十分に把握することが可能になる。
【０３９２】
そしてこれは、前記最遅開始時刻ｘLから最早開始時刻ｘEを減算することで、全工程ｉのトータルフロートｗを算出すると共に、このトータルフロートｗの値が０になる工程を検索し、これをボトルネック工程として抽出する第５のステップをさらに備えたスケジュール作成方法や、前記最遅開始時刻ｘLから最早開始時刻ｘEを減算させることで、全工程ｉのトータルフロートｗを算出させると共に、このトータルフロートｗの値が０になる工程を検索させ、これをボトルネック工程として抽出させる第５の手順を、前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０３９３】
本実施例におけるスケジュール作成装置の演算部は、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を数１５１，数１５２，数１５４及び数１７３により再計算し、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を前記記憶部に記憶させ、前記離散事象システムにおける入力時刻ｕの変更情報を取得すると、これを変更後の入力時刻ｕ〜として前記記憶部に記憶させ、前記離散事象システムにおける処理開始時刻ｘの変更情報を取得すると、これを変更後の入力時刻ｘ〜(0)として前記記憶部に記憶させ、前記記憶部から行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出し、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）と前記演算部で算出した行列Ｂ0を用いて、前記数２１５に基づき変更後の最早開始時刻ｘ〜Eを算出する機能を有する。
【０３９４】
また本実施例のスケジュール作成方法は、前記演算部が前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を数１５１，数１５２，数１５４及び数１７３により再計算し、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を前記記憶部に記憶させる第６のステップと、前記演算部が前記離散事象システムにおける入力時刻ｕの変更情報を取得すると、これを変更後の入力時刻ｕ〜として前記記憶部に記憶させる第７のステップと、前記離散事象システムにおける処理開始時刻ｘの変更情報を取得すると、これを変更後の入力時刻ｘ〜(0)として前記記憶部に記憶させる第８のステップと、前記記憶部から行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出し、前記演算部に取り込まれる前記処理開始時刻ｘ（ｋ）と前記第１のステップで算出した行列Ｂ0を用いて、前記数２１５に基づき変更後の最早開始時刻ｘ〜Eを前記演算部で算出する第９のステップと、をさらに備えている。
【０３９５】
また、本実施例におけるコンピュータプログラム２０は、前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ａ0，Ｆ，Ｃ，Ｆ*の各要素を数１５１，数１５２，数１５４及び数１７３により再計算させ、変更後の行列Ａ0〜，Ｆ〜，Ｃ〜，Ｆ*〜を記憶させる第６の手順と、前記離散事象システムにおける入力時刻ｕの変更情報を取得させ、これを変更後の入力時刻ｕ〜として前記記憶部に記憶させる第７の手順と、前記離散事象システムにおける処理開始時刻ｘの変更情報を取得させ、これを変更後の入力時刻ｘ〜(0)として前記記憶部に記憶させる第８の手順と、前記行列Ａ0〜，Ｆ*〜，ｘ〜(0)，ｕ〜を読み出させ、前記処理開始時刻ｘ（ｋ）と前記行列Ｂ0を用いて、前記数２１５に基づき変更後の最早開始時刻ｘ〜Eを算出させる第９の手順と、を前記コンピュータにさらに実行させている。
【０３９６】
このようにすれば、システムの稼動開始後に何らかの原因で、その入力時刻や加工時間や加工開始時刻が変化した場合でも、全ての工程における変更後の最早開始時刻ｘ〜Eを適確に且つ効率的に把握することができる。
【０３９７】
この場合、前記離散事象システムにおける処理開始時刻ｘの変更情報だけを取得し、且つその変更後の値が元の値よりも大きくなっていると判断したときには、前記演算部や前記第９のステップで、前記数２１９に基づき変更後の最早開始時刻ｘ〜Eを算出し、または前記第９の手順で、前記数２１９に基づき変更後の最早開始時刻ｘ〜Eをスケジュール作成装置１に算出させてもよい。
【０３９８】
こうすれば、前記数２１５よりも単純な式である数２１９に基づき、全ての工程における変更後の最早開始時刻ｘ〜Eを簡単に把握することができる。
【０３９９】
また、本実施例におけるスケジュール作成装置は、前記演算部で算出した行列Ｃまたは変更後の行列Ｃ〜及びＦ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、次の数２２８に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出するように、前記演算部を構成している。
【０４００】
【数２２８】
2007334855.tif 000165
【０４０１】
こうすれば、先に算出した行列ＣまたはＣ〜及びＦ*と、全ての工程における変更後の最早開始時刻ｘ〜Eとを利用して、システムを構成する全ての工程における変更後の最遅開始時刻ｘ〜Lを簡単に算出することができる。
【０４０２】
そしてこれは、前記第１のステップで算出した行列Ｃまたは前記第６のステップで算出した変更後の行列Ｃ〜及び前記第６のステップで算出したＦ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、上記数２２８に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出する第１０のステップをさらに備えたスケジュール作成方法や、前記第１の手順で算出させた行列Ｃまたは前記第６の手順で算出させた変更後の行列Ｃ〜及び前記第６の手順で算出させたＦ*〜と、全ての工程における前記変更後の最早開始時刻ｘ〜Eとを利用して、上記数２２８に基づき全ての工程における変更後の最遅開始時刻ｘ〜Lを算出させる第１０の手順を、前記コンピュータにさらに実行させても実現する。
【０４０３】
さらに、本実施例におけるスケジュール作成装置の演算部は、前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算することで、全工程ｉの変更後におけるトータルフロートｗを算出すると共に、この変更後におけるトータルフロートｗの値が０になる工程を検索し、それを変更後のボトルネック工程として再抽出する機能を有する。
【０４０４】
つまり、全ての工程における変更後の最早開始時刻ｘ〜Eや最遅開始時刻ｘ〜Lを算出できるので、後は簡単な演算処理によって全ての工程における変更後の余裕時間と、変更後のボトルネック工程がどこに存在するのかを簡単に算出することができる。したがって、システムの稼動後に各種パラメータが変化した場合であっても、適確に且つ効率的に再スケジューリングを実行することが可能になる。
【０４０５】
そしてこれは、前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算することで、全工程ｉの変更後におけるトータルフロートｗを算出すると共に、この変更後におけるトータルフロートｗの値が０になる工程を検索し、それを変更後のボトルネック工程として再抽出する第１１のステップをさらに備えたスケジュール作成方法や、前記変更後の最遅開始時刻ｘ〜Lから前記変更後の最早開始時刻ｘ〜Eを減算させることで、全工程ｉの変更後におけるトータルフロートｗを算出させると共に、この変更後におけるトータルフロートｗの値が０になる工程を検索させ、それを変更後のボトルネック工程として再抽出させる第１１の手順を、前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０４０６】
次に、本発明の他の実施例におけるスケジュール作成方法と、それを実現するスケジュール作成装置１について説明する。なお、上記第１実施例と同一部分には同一符号を付し、その共通する箇所の説明は重複を避けるため極力省略する。
【０４０７】
ここで、最初の第２実施例では、前のイベント（バッチ）との非競合を考慮して、当該イベントの内部状態が、前のイベントの内部状態の関数で表現されるフォワード型のＭＰＬ状態空間表現と再スケジューリングについて説明する。また次の第３実施例では、後続イベントとの非競合を考慮して、当該イベントの内部状態が、後続イベントの内部状態の関数で表現されるバックワード型のＭＰＬ状態空間表現と再スケジューリングについて説明する。これらの第２，第３実施例は、何れも第１実施例よりも表現行列に出現するシステムパラメータの数が少なく、簡単な状態空間表現を導出できるという特徴を有する。また、ＭＰＬ形式の状態表現式が、プロセスの実行順序を表す行列と、プロセスの実行時間を指定する行列とに明確に分離して表現されることも特徴である。これにより、スケジュール作成装置１のコンピュータで、第１実施例よりも簡単で且つ高速な計算を実現できる。さらに、フォワード型およびバックワード型の何れも、それらの表現形式が現代制御理論における双対システムに類似していることも注目される。
【０４０８】
スケジュール作成装置１の内部構成は、図１で示したとおり、各実施例共に共通している。但し、コンピュータプログラム２０に含まれるＭＰＬ形式作成手順，スケジュール作成手順，および再スケジュール作成手順と、こうした手順を各々処理実行するＭＰＬ形式作成手段３１，スケジュール作成手段３２，および再スケジュール作成手段３３の機能構成は、各実施例で異なっている。
【０４０９】
第２実施例におけるフォワード型のＭＰＬ表現について説明すると、ここではスケジュール作成装置１に入力する状態変数として、第１実施例のような加工（バッジ）「開始」時刻ではなく、加工「終了」時刻を割り付ける。これにより、表現行列に含まれるシステムパラメータ（加工時間）の数を減少させることができる。以下、状態変数として加工「終了」時刻を割り付けた場合に、どのような表現行列を含むＭＰＬ表現形式となるのかを説明する。
【０４１０】
先ずここでは、生産システムに課せられる制約条件を、以下のように仮定する。
・工程数はｎで、外部からの入力数と出力数を、それぞれｐおよびｑとする。
・各バッチ共に全ての行程を通過し、かつ加工回数は１回である。
・各工程の設備が稼動中のときには、その加工が終了するまで、次の加工を開始できない。
・先行工程を有する工程は、それらの先行工程の加工が終了しないと、加工を開始できない。
・外部入力のある工程は、対応する原材料が入力されるまで、その加工を開始できない。
【０４１１】
以上の制約条件の下で、ｋ番目の部品に関し、工程ｉ（１≦ｉ≦ｎ）における加工終了時刻を状態変数として割り付けた場合を［ｘ+（ｋ）］iとし、加工開始時刻を状態変数として割り付けた場合を［ｘ-（ｋ）］iとする。またここでは、工程ｉにおけるｋ番目の部品の加工時間をｄi（ｋ）として表わすと、次の数式のような関係が成立する。
【０４１２】
【数２２９】
2007334855.tif 000166
【０４１３】
図８は、工程ｉに関する先行工程や外部入力との関係を模式的にあらわしたものであり、ここで使用する以下の記号は、次のような意味を有する。
【０４１４】
【数２３０】
2007334855.tif 000167
【０４１５】
図８に示す入力変数［ｕ（ｋ）］jは、材料の投入時刻に割り付ける。工程ｉは、前の部品の加工が終了し、全ての先行工程から部品の供給を受け、かつ全ての外部入力から材料が投入されると、加工が開始できる状態となる。したがって、工程ｉにおけるｋ番目のバッチの最早開始時刻［ｘ-E（ｋ）］iは、前述のmax-plus代数を用いて次のように表わせる。
【０４１６】
【数２３１】
2007334855.tif 000168
【０４１７】
上記数２３１の右辺は、工程ｉにおける前のバッチの加工終了時刻，先行工程ｊにおける加工終了時刻，外部入力ｊにおける材料の投入時刻をそれぞれ表している。ここで、数２２９を利用して数２３１を変形すると、次の関係の式が得られる。
【０４１８】
【数２３２】
2007334855.tif 000169
【０４１９】
ここで、次の数２３３〜数２３５に示すような性質を満たす行列Ｐk∈Ｄn×n，Ｆ0∈Ｄn×n，Ｂ0∈Ｄn×pを導入する。行列Ｐkは、システムパラメータであるｋ番目の部品の加工時間ｄi（ｋ）にのみ依存し、行列Ｆ0，Ｂ0は、システムの構造（実行順序関係）にのみ依存して、双方を明確に分離している。また、行列Ｆ0，Ｂ0は、εまたはｅの論理変数だけで構成される。
【０４２０】
【数２３３】
2007334855.tif 000170
【０４２１】
【数２３４】
2007334855.tif 000171
【０４２２】
【数２３５】
2007334855.tif 000172
【０４２３】
なお、上記数２３３におけるdiagは、対角行列を意味する。これらの各行列Ｐk，Ｆ0，Ｂ0を用いると、上記数２３２におけるｋ番目のバッチの最早終了時刻［ｘ+E（ｋ）］iは、次のように表わすことができる。
【０４２４】
【数２３６】
2007334855.tif 000173
【０４２５】
これが、任意の工程ｉについて成立することから、数２３６の最後の式は、次のように表わせる。
【０４２６】
【数２３７】
2007334855.tif 000174
【０４２７】
ここで、数２３７を簡略化するために、次の数２３８に示す定理を用いる。
【０４２８】
【数２３８】
2007334855.tif 000175
【０４２９】
数２３７の右辺第１項のｘ+E（ｋ）に、当該数２３７の右辺全体を代入すると、次の式が得られる。
【０４３０】
【数２３９】
2007334855.tif 000176
【０４３１】
同様にして、この数２３９の右辺第１項のｘ+E（ｋ）に、数２３７の右辺全体を代入することを繰り返し、前記数２３８に示す定理を利用すると、ｋ番目のバッチの最早終了時刻ｘ+E（ｋ）は、次のように簡略化して表わすことができる。
【０４３２】
【数２４０】
2007334855.tif 000177
【０４３３】
但し、上記数２４０の（ＰkＦ0）*は、次のように表わせる。ここで、（ＰkＦ0）lにおいて全ての要素がεになり、またｎは工程数である。
【０４３４】
【数２４１】
2007334855.tif 000178
【０４３５】
上記数２４０において、右辺の中にあって、次の数２４２で表わせる式の第一項ｘ+（ｋ−１）は、ｋ−１番目のイベントカウンタに対するバッチの加工終了時刻を表わし、また第二項Ｂ0ｕ（ｋ）は、外部入力を有する工程における材料の投入時刻を表わすことから、数２４２の式は、各工程の設備が準備（ready）状態になる時刻を表わしていると解釈できる。また、行程の加工時間には陽に存在しない。
【０４３６】
【数２４２】
2007334855.tif 000179
【０４３７】
一方、数２４０の右辺の中にある別な項（ＰkＦ0）*Ｐkは、Ｆ0がシステムの先行制約関係を表わし、Ｐkが行程の加工時間を表わすことから、加工済の部品がシステムの下流方向へ流れて行く際の最短移送時間を表わしていると解釈できる。またこの実施例では、ｋ番目のイベントカウンタにおけるバッチの加工時間だけを含み、複数のイベントカウンタ（例えばｋ番目とｋ＋１番目）におけるバッチの加工時間は含まないパラメータによって、ＭＰＬシステムに適合する作業プロセスの状態を表現した式が算出される。
【０４３８】
続いて、最早の完成時刻を出力変数においたときの出力方程式について考える。ここでは、外部入力から外部出力へ加工を行なわずに直接部品を渡すような、入力と出力とを直接接続するシステム（直達）についても考慮できるようにする。図９は、出力ｉに関する先行工程や外部入力との関係を模式的にあらわしたものであり、ここで使用する変数や集合は、次のような意味を有する。
【０４３９】
【数２４３】
2007334855.tif 000180
【０４４０】
このとき、出力ｉにおけるシステムの最早出力時刻［ｙE（ｋ）］iは、次の式のように表わすことができる。
【０４４１】
【数２４４】
2007334855.tif 000181
【０４４２】
ここで、上記数２４４に関し、次の数２４５および数２４６に示すような性質を満たす行列Ｃ0∈Ｄq×n，Ｄ0∈Ｄq×pを導入する。
【０４４３】
【数２４５】
2007334855.tif 000182
【０４４４】
【数２４６】
2007334855.tif 000183
【０４４５】
これらの各行列Ｃ0，Ｄ0を用いると、上記数２４４における出力変数［ｙE（ｋ）］iは、次のように表わすことができる。
【０４４６】
【数２４７】
2007334855.tif 000184
【０４４７】
上記の式は、任意の出力ｉ（１≦ｉ≦ｑ）について成立するので、次のように書き表せる。
【０４４８】
【数２４８】
2007334855.tif 000185
【０４４９】
なお、図１０に示すように、入力と出力が直接接続していないシステムでは、右辺の第二項Ｄ0ｕ（ｋ）を省略することができるので、その場合のＭＰＬ形式作成手段３１が作成するＭＰＬ形式の状態表現式は、次の数２４９および数２５０のようになる。
【０４５０】
【数２４９】
2007334855.tif 000186
【０４５１】
【数２５０】
2007334855.tif 000187
【０４５２】
このように本実施例では、システムのバッジ終了時刻が状態変数として入力するようにＭＰＬ形式作成手段３１を構成すると共に、前記システムの諸情報（各工程ｉのｋ番目のバッチにおける加工時間ｄi（ｋ）や、入力，出力及び各工程間の接続構造）条件を入力として、数２３３〜数２３５で定義された行列Ｐk，Ｆo，Ｂoの各要素と、数２４５および数２４６で定義された行列Ｃo，Ｄoの各要素を決定し、その後は数２４１に従って、前記行列Ｐk，ＦoからＭＰＬシステムの形式に基づく数２４０（または数２４９）の行列（ＰkＦ0）*Ｐkを算出できるように、前記ＭＰＬ形式作成手段３１を構成すれば、数２４０及び数２４８（または数２５０）にて記述されるＭＰＬ形式での状態空間表現を取得することができ、この数２４０及び数２４８を利用して、後段のスケジュール作成手段３２が、システムにおける種々のスケジュール作成（特に、各バッジの最早加工終了時刻ｘ+E（ｋ）や、システムの最早出力時刻ｙE（ｋ））を行うことが可能となる。
【０４５３】
ここで、前述した図１０のシステムを例にして、本実施例特有の効果を具体的に説明する。先ず第１実施例のように、状態変数として加工開始時刻ｘ（ｋ）やｘ（ｋ−１）が入力される場合、ＭＰＬ形式作成手段３１が作成するＭＰＬ形式での状態空間表現は、次のような式になる。
【０４５４】
【数２５１】
2007334855.tif 000188
【０４５５】
【数２５２】
2007334855.tif 000189
【０４５６】
一方、本実施例でＭＰＬ形式作成手段３１が作成するＭＰＬ形式での状態空間表現は、上述した数２４９および数２５０のようになる。ここで、図１０のシステムに基づく接続構造と加工時間を入力として、以下に示す表現行列ＰK，Ｂo，Ｆo，Ｆk，Ｃo，Ｃkの行と列の各要素を決定すると、次のようになる。
【０４５７】
【数２５３】
2007334855.tif 000190
【０４５８】
このように、第１実施例では、ＭＰＬ形式作成手段３１で決定される三つの表現行列ＰK，Ｆk，Ｃkに、それぞれ加工時間ｄのパラメータが含まれているのに対して、第２実施例では、ＭＰＬ形式作成手段３１で決定される一つの表現行列Ｆkにのみ、加工時間ｄのパラメータが含まれている。しかも、第２実施例では、システムの構造に依存する行列Ｆo，Ｂo，Ｃoと、加工時間ｄのパラメータに依存する行列ＰKが、明確に分離しており、第１実施例よりも簡潔で高速な計算が行なえる。因みに、図１０に示すシステムでは、２つの入力ｊに対して出力ｉが何れも出力を持たないため、数２４６における表現行列Ｄ0は、Ｄ0＝［ε  ε］となる。この表現行列Ｄ0も、システムの構造に依存していて、加工時間ｄのパラメータを含まない。
【０４５９】
また、第２実施例の状態空間表現式に含まれる項（ＰkＦ0）*Ｐkと、第１実施例の状態空間表現式に含まれる項Ｆk*Ｐk-1をそれぞれ計算すると、次のようになる。
【０４６０】
【数２５４】
2007334855.tif 000191
【０４６１】
つまり、同じシステムを表現するのに、第１実施例では、ｄ1（ｋ），ｄ2（ｋ），ｄ1（ｋ−１），ｄ2（ｋ−１），ｄ3（ｋ−１）からなる五種類の加工時間のパラメータが出現するのに対し、第２実施例では、ｄ1（ｋ），ｄ2（ｋ），ｄ3（ｋ）の三種類に加工時間のパラメータが減少しており、より簡潔な状態空間表現の導出が可能になっている。以上のような本実施例の特徴から、大規模なシステムの解析を行なう際に、計算の負荷が高くなったり、パラメータの値が一部でも変化すると、全ての表現行列を再計算しなければならないような煩わしさを解消でき、特に加工時間のパラメータが頻繁に変化するようなシステムや、加工時間のパラメータを未知変数として扱う定式化を行なうような場合に、ＭＰＬ形式作成手段３１における計算処理の負担を軽減することが可能になる。
【０４６２】
次に、本発明の第３実施例におけるバックワード型のＭＰＬ表現について説明する。第１実施例のスケジュール作成手段３２は、数２５１で示したように、前のバッチｋ−１の加工開始時刻ｘ（ｋ−１）と、入力時刻ｕ（ｋ）が与えられると、状態変数ｘ（ｋ）の予測値の下限を求めることで、最早加工開始時刻ｘE（ｋ）を得るようにしているが、この実施例におけるスケジュール作成手段３２は、出力時刻ｙ（ｋ）と、次のバッチｋ＋１の加工開始時刻ｘ（ｋ＋１）が与えられると、状態変数ｘ（ｋ）の予測値の上限を求めることで、最遅加工開始時刻ｘL（ｋ）を得るようになっている。以下、このバックワード型のＭＰＬ状態空間表現が、どのような形式で表わせるのかを説明する。
【０４６３】
先ずここでは、生産システムに課せられる制約条件について考える。前記フォワード型のＭＰＬ表現では、前のバッチとの資源非競合を考慮して、制約条件を仮定したが、本実施例では、次のバッチとの資源非競合を考慮して、次のように制約条件を仮定する。
・当該バッチの加工終了時刻は、後続工程の加工開始時刻以前でなければならない。
・後続工程を有する工程は、それらの後続工程の加工開始時刻以前に、加工を終了していなければならない。
・外部入力のある工程は、出力時刻以前に加工を終了していなければならない。
【０４６４】
次に、入力変数［ｕ（ｋ）］j（但し、１≦ｊ≦ｑ）を、ｊ個の外部出力への出力時刻としてスケジュール作成装置１に与えたときの、各工程における最遅加工開始時刻を導出する。図１１は、工程ｉの後続工程や外部出力との関係を示した図であり、ここで使用する記号で、Ｑiは工程ｉに接続された外部出力番号の集合を意味し、Ｓiは後続工程番号の集合を意味する。なお、工程ｉに外部出力が存在しない場合は、Ｑi＝｛φ｝であり、工程ｉに後続工程が存在しない場合は、Ｓi＝｛φ｝である。工程ｉにおける加工終了時刻は、次の部品の加工開始前で、全ての外部出力への出力時刻および後続工程での部品加工開始前でなければならない。従って、工程ｉにおける最遅終了時刻［ｘ+L（ｋ）］iは、次のように表わせる。
【０４６５】
【数２５５】
2007334855.tif 000192
【０４６６】
上記数２５５において、右辺の各項は左から順に、次のバッチｋ＋１の加工開始時刻と、後続工程ｊにおける加工開始時刻と、外部出力ｊに対する製品の提供時刻を表わしている。前記数２２９を数２５５に代入すると、次の式のような関係が成り立つ。
【０４６７】
【数２５６】
2007334855.tif 000193
【０４６８】
この実施例では、第２実施例と同じ表現行列Ｐk，Ｆ0，Ｃ0を用いる。上記数２５６は、次のように変形できる。
【０４６９】
【数２５７】
2007334855.tif 000194
【０４７０】
上記式は、任意の工程ｉ（１≦ｉ≦ｎ）について成立することから、数２５７は、次のように表わせる。
【０４７１】
【数２５８】
2007334855.tif 000195
【０４７２】
数２５８の右辺第１項のｘ-L（ｋ）に、当該数２５８の右辺全体を代入すると、次の式が得られる。
【０４７３】
【数２５９】
2007334855.tif 000196
【０４７４】
同様にして、この数２５９の右辺第１項のｘ-L（ｋ）に、数２５８の右辺全体を代入することを繰り返し、次の数２６０に示す定理を利用すると、ｋ番目のバッチの最遅加工開始時刻ｘ-L（ｋ）は、次の数２６１のように簡略化して表わすことができる。
【０４７５】
【数２６０】
2007334855.tif 000197
【０４７６】
【数２６１】
2007334855.tif 000198
【０４７７】
続いて、最遅の材料投入時刻を出力変数においたときの出力方程式について考える。上述した直達システムを含むものについても考慮すると、図１２は、外部入力ｉにつながる外部出力や後続工程の関係を模式的にあらわしているが、ここで使用する変数や集合は、次のような意味を有する。
【０４７８】
【数２６２】
2007334855.tif 000199
【０４７９】
このときの最遅材料投入時刻［ｙL（ｋ）］iは、次のように表わせる。
【０４８０】
【数２６３】
2007334855.tif 000200
【０４８１】
なお、出力ｉに後続工程が存在しない場合は、数２６２で定義した集合Ｕi＝｛φ｝であり、外部出力が存在しない場合は、Ｗi＝｛φ｝である。数２６３は、前記表現行列Ｂ0，Ｄ0を用いて、次のように表わせる。
【０４８２】
【数２６４】
2007334855.tif 000201
【０４８３】
これが、任意の出力ｉ（１≦ｉ≦ｑ）について成立するので、数２６４は次のように書き表せる。
【０４８４】
【数２６５】
2007334855.tif 000202
【０４８５】
このように本実施例では、システムの製品完成時刻とバッジ加工開始時刻が入力するようにＭＰＬ形式作成手段３１を構成すると共に、前記システムの諸情報（各工程ｉのｋ番目のバッチにおける加工時間ｄi（ｋ）や、入力，出力及び各工程間の接続構造）条件を入力として、数２３３〜数２３５で定義された行列Ｐk，Ｆo，Ｂoの各要素と、数２４５および数２４６で定義された行列Ｃo，Ｄoの各要素を決定し、その後は数２４１に従って、前記行列Ｐk，ＦoからＭＰＬシステムの形式に基づく数２４０（または数２４９）の行列（ＰkＦ0）*Ｐkを算出できるように、前記ＭＰＬ形式作成手段３１を構成すれば、数２６１及び数２６５にて記述されるＭＰＬ形式での状態空間表現を取得することができ、この数２６１及び数２６５を利用して、後段のスケジュール作成手段３２が、システムにおける種々のスケジュール作成（特に、各バッジの最遅加工開始時刻ｘ-L（ｋ）や、システムの最遅投入時刻ｙL（ｋ））を行うことが可能となる。
【０４８６】
またこの場合も、第２実施例と同様に、システムの構造に依存する行列Ｆo，Ｂo，Ｃoと、加工時間ｄのパラメータに依存する行列ＰKが、明確に分離しており、第１実施例よりも簡潔で高速な計算が行なえる。しかも、同じシステムを表現するのに加工時間のパラメータが減少し、より簡潔な状態空間表現の導出が可能になっている。
【０４８７】
次に、上記第２実施例と第３実施例でスケジュール作成手段３２が計算に利用する状態方程式と出力方程式の類似性について考察する。
【０４８８】
前記数２４８におけるシステムの最早出力時刻ｙE（ｋ）は、次のように表わすこともできる。
【０４８９】
【数２６６】
2007334855.tif 000203
【０４９０】
同様に、数２６５におけるシステムの最遅投入時刻ｙl（ｋ）は、次のように表わすこともできる。
【０４９１】
【数２６７】
2007334855.tif 000204
【０４９２】
一方、現代制御理論における状態方程式と出力方程式は、次の式のように与えられる。
【０４９３】
【数２６８】
2007334855.tif 000205
【０４９４】
【数２６９】
2007334855.tif 000206
【０４９５】
このシステムに対して、次のような双対変換を施す。
【０４９６】
【数２７０】
2007334855.tif 000207
【０４９７】
すると、上記数２６８および数２６９から、次のような双対システムが得られる。
【０４９８】
【数２７１】
2007334855.tif 000208
【０４９９】
【数２７２】
2007334855.tif 000209
【０５００】
これと類似の関係が、上記第２実施例と第３実施例で導いた状態方程式と出力方程式にも当てはまる。先ず、前記数２４０や数２６１において、（ＰkＦ0）*Ｐk＝Ａkとおき、さらに、数２６６や数２６７において、（Ｆ0Ｐk）*Ｂ0＝Ｂk，Ｃo（ＰkＦ0）*＝Ｃkとおく。フォワード型の状態空間表現の方程式である数２４０と数２６６において、右辺の状態変数を最早終了時間においたときも成立するので、下記のような関係が成り立つ。
【０５０１】
【数２７３】
2007334855.tif 000210
【０５０２】
【数２７４】
2007334855.tif 000211
【０５０３】
一方、バックワード型の方程式である数２６１や数２６７では、右辺の状態変数を最遅開始時間においたときも成立するので、下記のような関係が成り立つ。
【０５０４】
【数２７５】
2007334855.tif 000212
【０５０５】
【数２７６】
2007334855.tif 000213
【０５０６】
上記数２７０における時間の反転が、数２７３におけるイベントカウンタの反転に対応するものと考え、また演算子∧や、「・」のシンボルを丸印で囲んだ演算子は、バックワード型での加算および乗算に類した性質を有していることから、数２７３と数２７５の関係は、数２６８と数２７１の関係に極めて類似している。また同様に、数２７４と数２７６の関係は、数２６９と数２７２の関係に極めて類似している。
【０５０７】
このように、本実施例で導いた最早時刻や最遅時刻を求める状態方程式と出力方程式は、現代制御理論における双対システムの概念と非常に類似している。なお、実際のＭＰＬ形式作成手段３やスケジュール作成手段３２が行なう計算では、次の各式における状態方程式や出力方程式を用いる方が、高速に演算を行なうことができ好ましい。
【０５０８】
【数２７７】
2007334855.tif 000214
【０５０９】
【数２７８】
2007334855.tif 000215
【０５１０】
【数２７９】
2007334855.tif 000216
【０５１１】
【数２８０】
2007334855.tif 000217
【０５１２】
上記数２７７〜数２８０の各式において、加工時間に関するパラメータは、行列ＡK＝（ＰkＦ0）*Ｐkにのみ含まれており、その他の表現行列Ｂ0，Ｃ0，Ｄ0は、単位元ε，ｅだけで表わせる定数行列である。そのため、加工時間に関するパラメータの値が変化した場合でも、行列ＡK＝だけを再計算すればよく、ＭＰＬ形式作成手段３１やスケジュール作成手段３２が処理する上での取り扱いが容易である。
【０５１３】
次に、第２実施例や第３実施例で説明したスケジュール作成手段３２を利用して、各工程のトータルフロートや、ボトルネック工程の算出を行なう手順を説明する。前記スケジュール作成装置３２は、ｋ−１番目のバッチの加工終了時刻ｘ（ｋ−１）と、ｋ番目のバッチの材料投入時刻ｕ（ｋ）が入力されると、ＭＰＬ形式作成手段３１が作成した上記数２７７による方程式に基づき、最早加工終了時刻ｘ+E（ｋ）を算出し、またｋ番目のバッチの加工終了時刻ｘ（ｋ）と、材料投入時刻ｕ（ｋ）が入力されると、数２７８による方程式に基づき、最早出力時刻ｙE（ｋ）を算出する。さらに、ｋ＋１番目のバッチの加工開始時刻ｘ（ｋ＋１）と、材料投入時刻ｕ（ｋ）が入力されると、数２７９による方程式に基づき、最遅加工開始時刻ｘ-L（ｋ）を算出し、ｋ＋１番目のバッチの加工開始時刻ｘ（ｋ＋１）と、材料投入時刻ｕ（ｋ）が入力されると、最遅投入時刻ｙL（ｋ）を算出する。
【０５１４】
次に、スケジュール作成手段３２は、次の式を用いて各工程のトータルフロートｗを算出する。この式は、前記数２０７にも示されているが、ｋ番目のバッチの最遅開始時刻ｘL（ｋ）から最早開始時刻ｘE（ｋ）を減算することで得られる。なお、ここでいう最遅開始時刻ｘL（ｋ）とは、前記最遅加工開始時刻ｘ-L（ｋ）や最遅投入時刻ｙL（ｋ）のことであり、最早開始時刻ｘE（ｋ）とは、前記数２２９に基づき、最早加工終了時刻ｘ+E（ｋ）から加工時間ｄ（ｋ）を減算したり、最早出力時刻ｙE（ｋ）から得ることができる。
【０５１５】
【数２８１】
2007334855.tif 000218
【０５１６】
またボトルネック工程は、トータルフロートｗが０になる工程の集合として与えられ、これを数式で表わすと次のようになる。この式は、前記数２０８に対応している。
【０５１７】
【数２８２】
2007334855.tif 000219
【０５１８】
つまり、スケジュール生成手段３２は、先に当該スケジュール生成手段３２が数２７７〜数２８０に基づいて算出した最早開始時刻から最早開始時刻ｘE（ｋ）と最遅開始時刻ｘL（ｋ）を用いることで、数２８１や数２８２により全ての工程ｉにおけるトータルフロートｗと、どの工程がボトルネックとなっているのかを簡単に抽出できる。
【０５１９】
次に、第２実施例や第３実施例における再スケジュール生成手段３３の具体的な構成について説明する。これらの実施例における再スケジュール生成手段３３も、入力時刻，加工時間，加工開始時刻，加工終了時刻などの変更情報を入力として、各工程ｉにおける最早加工終了時刻ｘ+E（ｋ）および最遅加工開始時刻ｘ-L（ｋ）や、ボトルネックとなる工程がどのように変化したのかを再度見直す機能を有している。
【０５２０】
いま、バッチの加工開始後に何らかの原因で、その入力時刻，加工時間，加工終了時刻などが変化したと仮定する。入力時刻と加工終了時刻については、外部入力時刻ｕ（ｋ）と、該当する工程ｉの加工終了時刻［ｘ+(0)（ｋ）］iにそれぞれ影響を及ぼすことから、これらの外部入力時刻ｕ（ｋ）や開始時刻［ｘ+(0)（ｋ）］iの変化後における状態を、第１実施例と同様に、それぞれ記号の上または横にシンボル〜をつけて表わす。また、加工時間に関する変動は、前述のように行列Ｐkにのみ影響を及ぼすことから、この記号の上または横にシンボル〜をつけて表わす。すると第２実施例における再スケジュール生成手段３３は、次の式に基づいて更新後の最早加工終了時刻ｘ+E〜（ｋ）を算出する。
【０５２１】
【数２８３】
2007334855.tif 000220
【０５２２】
なお、上記式の右辺第一項は、変化分に伴なう追加項である。また特別な場合として、プロセスの加工時間ｄi（ｋ）は変化せず、ある工程ｉの加工終了時刻ｘ+(0)（ｋ）だけが遅延したとの入力を受けると、再スケジュール生成手段３３は、次の簡便な計算式によって更新後の最早加工終了時刻ｘ+E〜（ｋ）を算出する。
【０５２３】
【数２８４】
2007334855.tif 000221
【０５２４】
これを第１実施例の場合と比較すると、第１実施例では上記数２８３と数２８４に対応して、次の各式で更新後の最早加工開始時刻ｘE（ｋ）を算出できる。
【０５２５】
【数２８５】
2007334855.tif 000222
【０５２６】
【数２８６】
2007334855.tif 000223
【０５２７】
なお、各々の行列は前記数２５３と数２５４に対応している。前記第１実施例では、前のｋ−１番目のバッチにおける加工時間（システムパラメータ）が変化しても、再計算が必要であるが、第２実施例では前のバッチのシステムパラメータが含まれないことから、そうした再計算は不要になる。
【０５２８】
次に、第３実施例における再スケジュール生成手段３３について説明する。バックワード型の状態方程式と出力方程式は、次の式に示された通りである。なおこの場合は、対象となるシステムにおいて、入力と出力とを直接接続する構成が存在しないものする。また前述したように、第３実施例では、制御入力ｕ（ｋ）を外部への出力時刻とし、制御出力ｙ（ｋ）を外部からの入力時刻としている。
【０５２９】
【数２８７】
2007334855.tif 000224
【０５３０】
【数２８８】
2007334855.tif 000225
【０５３１】
いま、バッチの加工開始後に何らかの原因で、その出力時刻，加工時間，加工開始時刻などが変化したと仮定する。出力時刻と加工終了時刻については、外部出力時刻ｕ（ｋ）と、該当する工程ｉの加工開始時刻［ｘ-(0)（ｋ）］iにそれぞれ影響を及ぼすことから、これらの外部出力時刻ｕ（ｋ）や開始時刻［ｘ-(0)（ｋ）］iの変化後における状態を、それぞれ記号の上または横にシンボル〜をつけて表わす。また、加工時間に関する変動は、前述のように行列Ｐkにのみ影響を及ぼすことから、この記号の上または横にシンボル〜をつけて表わす。すると第３実施例における再スケジュール生成手段３３は、次の式に基づいて更新後の最遅加工開始時刻ｘ-L〜（ｋ）を算出する。
【０５３２】
【数２８９】
2007334855.tif 000226
【０５３３】
なお、上記式の右辺最終項は、変化分に伴なう追加項である。また特別な場合として、プロセスの加工時間ｄi（ｋ）は変化せず、ある工程ｉの加工開始時刻ｘ-(0)（ｋ）だけが早まったとの入力を受けると、再スケジュール生成手段３３は、次の簡便な計算式によって更新後の最遅加工開始時刻ｘ-L〜（ｋ）を算出する。
【０５３４】
【数２９０】
2007334855.tif 000227
【０５３５】
上記（Ｆ0Ｐk）*は、次の関係式を用いて比較的簡単に計算できる。なお、ここにあるＡkは、ＭＰＬ形式作成手段３１が状態方程式を決定するのに算出したものを、そのまま用いることができる。
【０５３６】
【数２９１】
2007334855.tif 000228
【０５３７】
ここで、次の数式を用いる。
【０５３８】
【数２９２】
2007334855.tif 000229
【０５３９】
すると、（Ｆ0Ｐk）*は、次のように表わせる。
【０５４０】
【数２９３】
2007334855.tif 000230
【０５４１】
また行列表現で表わすならば、次の式のようになる。
【０５４２】
【数２９４】
2007334855.tif 000231
【０５４３】
更新後のボトルネック工程の抽出は、前記数２２１で表わした式に基づき算出できる。
【０５４４】
このように、上記第２実施例や第３実施例では、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を入力パラメータとして取り込む取込部（入力装置１５）と、前記取込部で取り込んだ入力パラメータを記憶する記憶部（ＲＡＭ１２）と、前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換する演算部（ＣＰＵ１１）と、を備えたスケジュール作成装置１において、前記演算部は、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、数２３３〜数２３５，数２４５，数２４６で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0の各要素をそれぞれ決定し、前記行列Ｆ0を用いて、数２４１の行列（ＰkＦ0）*を算出するＭＰＬ形式作成手段３１を備えて構成される。
【０５４５】
また、第２実施例や第３実施例では、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、数２３３〜数２３５，数２４５，数２４６で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0の各要素をそれぞれ前記演算部で決定する第１のステップと、前記行列Ｆ0を用いて、数２４１の行列（ＰkＦ0）*を前記演算部で算出する第２のステップと、を順次実行している。
【０５４６】
また、第２実施例や第３実施例では、一乃至複数の入力，一乃至複数の出力，及び複数の工程を組み合わせてなり、前記入力に投入した処理対象を前記複数の工程で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各工程の実行順序を規定する先行制約関係，及び前記各工程における実行時間を、入力パラメータとしてコンピュータであるスケジュール作成装置１に取り込ませ、この入力パラメータを前記コンピュータに記憶させ、さらに前記離散事象システムの状態を表現するために、前記入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるように前記コンピュータに演算を行なわせるコンピュータプログラム２０において、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各工程ｉにおけるｋ番目の処理工程の実行時間をｄi（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、数２３３〜数２３５，数２４５，数２４６で定義されたシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0の各要素をそれぞれ決定させる第１の手順と、前記行列Ｆ0を用いて、数２４１の行列（ＰkＦ0）*を算出させる第２の手順と、を前記コンピュータに実行させている。
【０５４７】
このようなスケジュール作成装置１，スケジュール作成方法，及びコンピュータプログラム２０であれば、従来技術のようにわざわざ複数の数式（数７９〜数８３）を作成し、そこから任意の数式を適宜代入して、複雑な計算手法によりmax-plus代数上で線形なＭＰＬ形式の式（数７７及び数７８）に含まれる行列Ａ，Ｂ，Ｃを算出しなくても、入力パラメータとして、各工程ｉの実行時間ｄi（ｋ）と工程ｉ間の先行制約関係の各情報がスケジュール作成装置１に記憶されていれば、そこからスケジュール作成装置１が独自のシステム構造を表現する行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0について、その各要素を決定し、さらにここで決定した行列Ｐk，Ｆ0から行列（ＰkＦ0）*を算出して、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ｐk，Ｆ0，Ｂ0，Ｃ0，Ｄ0，（ＰkＦ0）*を簡単に取得することができる。したがって、システムのスケジュール作成をコンピュータで実現する上で、より少ないメモリ消費で、与えられたシステムをＭＰＬシステムとして表現できる形式に簡単に導出することが可能になる。
【０５４８】
さらにこの場合は、システムの構造に依存する行列Ｆo，Ｂo，Ｃo，Ｄ0と、加工時間のパラメータに依存する行列ＰKが明確に分離しており、より簡潔で高速な計算を実現できる。しかも、同じシステムを表現する上で、加工時間のパラメータが減少しており、より簡潔な状態空間表現の導出が可能になる。
【０５４９】
第２実施例におけるスケジュール作成装置は、ｋ番目の工程処理に関して、各工程での処理終了時刻をｘ+（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１及び第２のステップで算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）とを利用して、数２４０に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を算出するように、前記演算部を構成している。
【０５５０】
また、第２実施例におけるスケジュール作成方法は、前記第１及び第２のステップで算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）とを利用して、次の数１７に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を前記演算部で算出する第３のステップをさらに備えている。
【０５５１】
また、第２実施例におけるコンピュータプログラム２０は、ｋ−１番目の前記処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）を取り込ませ、この処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ｐk，Ｂ0，及び（ＰkＦ0）*とを利用して、次の数６１に基づきｋ番目の処理工程の最早終了時刻ｘ+E（ｋ）を算出させる第３の手順を、前記コンピュータに実行させている。
【０５５２】
こうすれば、初期状態の処理終了時刻ｘ+（ｋ−１）及び入力時刻ｕ（ｋ）が取り込まれると、先に算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*を利用して、システムを構成する全ての工程の最早終了時刻ｘ+E（ｋ）を簡単に算出することができる。
【０５５３】
それに加えて第３実施例のスケジュール作成装置は、前記演算部で算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）とを利用して、数２６１に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を算出するように、前記演算部を構成している。
【０５５４】
こうすれば、初期状態の処理終了時刻ｘ+（ｋ＋１）及び入力時刻ｕ（ｋ）が取り込まれると、先に算出した行列Ｐk，Ｂ0，及び（ＰkＦ0）*を利用して、システムを構成する全ての工程の最遅開始時刻ｘ-L（ｋ）を簡単に算出することができる。
【０５５５】
そしてこれは、前記第１及び第２のステップで算出した行列Ｐk，Ｃ0，及び（ＰkＦ0）*と、前記演算部に取り込まれるｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）とを利用して、数２６１に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を前記演算部で算出する第４のステップをさらに備えたスケジュール作成方法や、ｋ＋１番目の前記処理開始時刻ｘ-（ｋ＋１）及び出力時刻ｕ（ｋ）を取り込ませ、このｋ＋１番目の前記処理開始時刻ｘ-（ｋ−１）及び出力時刻ｕ（ｋ）と、前記第１及び第２の手順で算出させた行列Ｐk，Ｃ0，及び（ＰkＦ0）*とを利用して、数２６１に基づきｋ番目の処理工程の最遅開始時刻ｘ-L（ｋ）を算出させる第４の手順を、前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０５５６】
また、ここでのスケジュール作成装置は、前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、これをボトルネック工程として抽出するように、前記演算部を構成している。
【０５５７】
こうすると、全ての工程における最早開始時刻ｘE（ｋ）や最遅開始時刻ｘL（ｋ）が算出されていれば、後は簡単な演算処理によって全ての工程の余裕時間と、ボトルネック工程がどこに存在するのかを簡単に算出することができる。したがって、途中工程の稼動状態や、ボトルネック工程を十分に把握することが可能になる。
【０５５８】
そしてこれは、前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算することで、全工程のトータルフロートを算出すると共に、このトータルフロートの値が０になる工程を検索し、これをボトルネック工程として抽出する第５のステップをさらに備えたスケジュール作成方法や、前記最早終了時刻ｘ+E（ｋ）から算出した最早開始時刻ｘE（ｋ）を、前記最遅開始時刻ｘL（ｋ）から減算させることで、全工程のトータルフロートを算出させると共に、このトータルフロートの値が０になる工程を検索させ、これをボトルネック工程として抽出させる第５の手順を、前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０５５９】
また、第２実施例のスケジュール作成装置は、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させ、前記演算部が前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の入力時刻ｕ（ｋ）〜として前記記憶部に記憶させ、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させ、前記記憶部から行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ+（ｋ−１）と前記演算部で算出した行列Ｆ0，Ｂ0を用いて、数２８３に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出するように、前記演算部を構成している。
【０５６０】
こうすると、システムの稼動開始後に何らかの原因で、その入力時刻や加工時間や加工終了時刻が変化した場合でも、全ての工程における変更後の最早終了時刻ｘ〜+E（ｋ）を適確に且つ効率的に把握することができる。
【０５６１】
そしてこれは、前記演算部が、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させる第６のステップと、前記演算部が前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の入力時刻ｕ（ｋ）〜として前記記憶部に記憶させる第７のステップと、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させる第８のステップと、前記記憶部から行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ+（ｋ−１）と前記第１のステップで算出した行列Ｆ0，Ｂ0を用いて、数２８３に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を前記演算部で算出する第９のステップと、をさらに備えたスケジュール作成方法によっても実現する。
【０５６２】
また、前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算させ、変更後の行列ＰK〜を記憶させる第６の手順と、前記離散事象システムにおける入力時刻ｕ（ｋ）の変更情報を取得させ、これを変更後の入力時刻ｕ（ｋ）〜として記憶させる第７の手順と、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報を取得させ、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として記憶させる第８の手順と、前記行列ＰK〜，ｘ〜+(0)（ｋ），ｕ（ｋ）〜を読み出させ、前記処理終了時刻ｘ+（ｋ−１）と前記行列Ｆ0，Ｂ0を用いて、次の数２８３に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出させる第９の手順と、を前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０５６３】
また、第２実施例におけるスケジュール作成装置は、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させ、前記記憶部から読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっていると判断したときに、数３５６に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出するように、前記演算部を構成している。
【０５６４】
こうすると、より単純な算術手順で、全ての工程における変更後の最早終了時刻ｘ〜+E（ｋ）を簡単に把握することができる。
【０５６５】
そしてこれは、前記演算部が、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得すると、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として前記記憶部に記憶させる第１０のステップと、前記記憶部から読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっていると判断したときに、数３５６に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出する第１１のステップと、をさらに備えたスケジュール作成方法や、前記離散事象システムにおける処理終了時刻ｘ+（ｋ）の変更情報だけを取得させ、これを変更後の処理終了時刻ｘ〜+(0)（ｋ）として記憶させる第１０の手順と、前記読み出した変更後の処理終了時刻ｘ〜+(0)（ｋ）が、元の値よりも大きくなっていると判断したときに、数３５６に基づき変更後の最早終了時刻ｘ〜+E（ｋ）を算出させる第１１の手順と、を前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０５６６】
第３実施例におけるスケジュール作成装置は、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させ、
前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の出力時刻ｕ（ｋ）〜として前記記憶部に記憶させ、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させ、前記記憶部から行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ-（ｋ＋１）と前記演算部で算出した行列Ｆ0，Ｃ0を用いて、数２８９に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出するように、前記演算部を構成している。
【０５６７】
こうすると、システムの稼動開始後に何らかの原因で、その出力時刻や加工時間や加工終了時刻が変化した場合でも、全ての工程における変更後の最遅開始時刻ｘ〜-L（ｋ）を適確に且つ効率的に把握することができる。
【０５６８】
そしてこれは、前記演算部が、前記離散事象システムにおける工程の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算し、変更後の行列ＰK〜を前記記憶部に記憶させる第１２のステップと、前記演算部が前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得すると、これを変更後の出力時刻ｕ（ｋ）〜として前記記憶部に記憶させる第１３のステップと、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させる第１４のステップと、前記記憶部から行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出し、前記演算部に取り込まれる前記処理終了時刻ｘ-（ｋ＋１）と前記第１のステップで算出した行列Ｆ0，Ｃ0を用いて、数２８９に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を前記演算部で算出する第１５のステップと、をさらに備えたスケジュール作成方法でも実現する。
【０５６９】
また、前記離散事象システムにおける工程の加工時間の変更情報を取得させ、この加工時間の変更情報に基づいて、前記行列Ｐkの各要素を再計算させ、変更後の行列ＰK〜を記憶させる第１２の手順と、前記離散事象システムにおける出力時刻ｕ（ｋ）の変更情報を取得させ、これを変更後の出力時刻ｕ（ｋ）〜として記憶させる第１３の手順と、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報を取得させ、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として記憶させる第１４の手順と、前記行列ＰK〜，ｘ〜-(0)（ｋ），ｕ（ｋ）〜を読み出させ、前記処理終了時刻ｘ-（ｋ＋１）と前記行列Ｆ0，Ｃ0とを用いて、数２８９に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出させる第１５の手順と、を前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０５７０】
さらに、第３実施例におけるスケジュール作成装置は、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させ、前記記憶部から読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっていると判断したときに、数２９０に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出するように、前記演算部を構成している。
【０５７１】
こうすると、より単純な算術手順で、全ての工程における変更後の最遅開始時刻ｘ〜-L（ｋ）を簡単に把握することができる。
【０５７２】
そしてこれは、前記演算部が、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得すると、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として前記記憶部に記憶させる第１６のステップと、前記記憶部から読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっていると判断したときに、次の数２２に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出する第１７のステップと、をさらに備えたスケジュール作成方法や、前記離散事象システムにおける処理開始時刻ｘ-（ｋ）の変更情報だけを取得させ、これを変更後の処理開始時刻ｘ〜-(0)（ｋ）として記憶させる第１６の手順と、前記読み出した変更後の処理開始時刻ｘ〜-(0)（ｋ）が、元の値よりも小さくなっていると判断したときに、数２９０に基づき変更後の最遅開始時刻ｘ〜-L（ｋ）を算出させる第１７の手順と、を前記コンピュータにさらに実行させるコンピュータプログラム２０によっても実現する。
【０５７３】
なお、本発明は上記実施例に限定されるものではなく、本発明の要旨の範囲において種々の変形実施が可能である。例えば、実施例中では、複数の工程からなる生産システムを例として採用したが、タスクに順序制約を有するプロジェクト管理などを含むあらゆるシステムや、プロジェクトスケジューリング問題や、物流システムの配送計画問題などにも、そのまま適用が可能である。また、入力や出力が複数箇所存在するような、いわゆるＭＩＭＯ（Multiple Input Multiple Output）型構造を有するシステムへの適用も可能であり、従来知られているＰＥＲＴ（Program Evaluation and Review Technique）による方法よりも、適用範囲が広いことを意味する。
【図面の簡単な説明】
【０５７４】
【図１】本発明の第１実施例におけるスケジュール作成装置の内部構成を示すブロック図である。
【図２】同上、ＭＰＬ形式作成手段の処理手順を示すフローチャートである。
【図３】同上、スケジュール生成手段の処理手順を示すフローチャートである。
【図４】同上、再スケジュール生成手段の処理手順を示すフローチャートである。
【図５】表１に示す生産システムの先行制約や、外部への入出力位置の関係を表わした模式図である。
【図６】スケジュール生成手段が算出した各工程の資源使用計画を示すガントチャート図である。
【図７】生産システムにおける加工順序の一例を示した模式図である。
【図８】工程ｉに関する先行工程や外部入力との関係を示す概略図である。
【図９】出力ｉに関する先行工程や外部入力との関係を示す概略図である。
【図１０】生産システムにおける加工順序の別な一例を示した模式図である。
【図１１】工程ｉの後続工程や外部出力との関係を示す概略図である。
【図１２】外部入力ｉと、これにつながる外部出力および後続工程の関係を示す概略図である。
【符号の説明】
【０５７５】
１  スケジュール作成装置（コンピュータ）
１１  ＣＰＵ（演算部）
１２  ＲＡＭ（記憶部）
１６  出力装置（取込部）
２０  コンピュータプログラム
【図１】
2007334855.tif 000298
【図２】
2007334855.tif 000299
【図３】
2007334855.tif 000300
【図４】
2007334855.tif 000301
【図５】
2007334855.tif 000302
【図６】
2007334855.tif 000303
【図７】
2007334855.tif 000304
【図８】
2007334855.tif 000305
【図９】
2007334855.tif 000306
【図１０】
2007334855.tif 000307
【図１１】
2007334855.tif 000308
【図１２】
2007334855.tif 000309