(57)【要約】【課題】既存のＭＰＬ状態空間表現を拡張して、単一設備内だけでなく、任意の領域内における処理対象の最大容量を、ＭＰＬ状態空間表現の中で容量制約として考慮することが可能なスケジュール作成方法，スケジュール作成装置，およびコンピュータプログラムを提供する。【解決手段】入力パラメータとして、各設備ｉの実行時間ｄｉ（ｋ）と設備ｉ間の先行制約関係の各情報の入力パラメータに基づき、独自のシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），Ｂｏの各要素を決定し、ここで決定した行列Ｆｏから行列Ｆｏ＊を算出して、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ｐｋ，Ｆｏ＊，Ｈｏ（ｈ），Ｂｏを取得し得、かくして、既存のＭＰＬ状態空間表現を拡張して、単一設備内だけでなく、任意の領域内における処理対象の最大容量を、ＭＰＬ状態空間表現の中で容量制約として考慮することが可能となる。【選択図】図１
2009015597.tif 000002
【特許請求の範囲】
【請求項１】
一乃至複数の入力，一乃至複数の出力，および複数の設備を組み合わせてなり、前記入力に投入した処理対象を前記複数の設備で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す各前記設備の実行順序を規定する先行制約関係，および各前記設備における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、各前記設備ｉにおけるｋ番目の処理設備の実行時間をｄｉ（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数１〜数６で定義されたシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），Ｂｏ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ前記演算部で決定する第１のステップと、
【数１】
2009015597.tif 000147
【数２】
2009015597.tif 000148
【数３】
2009015597.tif 000149
（但し、ｎを設備数とし、ｈ＝１のとき、
【数４】
2009015597.tif 000150
ｈ≧２のとき、
【数５】
2009015597.tif 000151
とする）
【数６】
2009015597.tif 000152
前記行列Ｆｏを用いて、次の数７の行列―Ｆｋ＊（但し、ｓは、１≦ｓ≦ｎ）を前記演算部で算出する第２のステップと、
【数７】
2009015597.tif 000153
を順次実行することを特徴とするスケジュール作成方法。
【請求項２】
前記第１のステップは、
前記ｈ＝１のとき、前記数４の行列―Ｈｏ（１）に替えて、次の数８（ＧＯ−は処理開始時点での順序制約の有無を表わすパラメータであり、ＧＯ＋は処理終了時点での順序制約の有無を表わすパラメータである）を前記演算部で決定することを特徴とする請求項１記載のスケジュール作成方法。
【数８】
2009015597.tif 000154
但し、前記数８のＧＯ−およびＧＯ＋は、
【数９】
2009015597.tif 000155
【数１０】
2009015597.tif 000156
（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）である
【請求項３】
ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１および第２のステップで算出した行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，および―Ｆｋ＊と、前記演算部に取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）とを利用して、次の数１１に基づき設備の最早開始時刻および最早終了時刻を表わす行列ｘＥ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を前記演算部で算出する第３のステップをさらに備えたことを特徴とする請求項１または２記載のスケジュール作成方法。
【数１１】
2009015597.tif 000157
【請求項４】
第１のステップは、
前記記憶部から読み出した入力パラメータに基づいて、次の数１２で定義されたシステム構造を表現する行列ＣＯの要素をさらに前記演算部で決定し、
【数１２】
2009015597.tif 000158
前記ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）、出力時刻をｙ（ｋ）としたときに、前記第１および第２のステップで算出した行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，―Ｆｋ＊，ＣＯと、前記演算部に取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）と、前記出力時刻ｙ（ｋ）とを利用して、次の数１３に基づき設備の最遅開始時刻および最遅終了時刻を表わす行列ｘＬ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を前記演算部で算出する第４のステップをさらに備えたことを特徴とする請求項１または２記載のスケジュール作成方法。
【数１３】
2009015597.tif 000159
【請求項５】
前記演算部が、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に前記行列Ｆｋ＊の変更後の行列Ｆ〜ｋ＊を計算して前記記憶部に記憶する第５のステップと、
前記ｋ番目の設備処理に関して、各設備での処理終了時刻をｘ（＋０）（ｋ）としたときに、前記離散事象システムにおける処理終了時刻ｘ（＋０）（ｋ）（ここで（＋０）は逐次的に計算を行うための初期値であることを表わす）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜（＋０）（ｋ）として前記記憶部に記憶する第６のステップと、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（＋０）（ｋ）と、前記行列Ｈｏ（ｈ），Ｂｏと、入力時刻ｕ〜（ｋ）とを用いて、次の数１４に基づき変更後の設備の最早開始時刻および最早終了時刻を表わす行列ｘ〜Ｅ（ｋ）を前記演算部で算出する第７のステップと、
【数１４】
2009015597.tif 000160
をさらに備えたことを特徴とする請求項３記載のスケジュール作成方法。
【請求項６】
前記演算部が、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に求めた変更後の行列Ｆ〜ｋ＊を前記記憶部に記憶させる第８のステップと、
前記ｋ番目の設備処理に関して、各設備での処理開始時刻をｘ（−０）（ｋ）としたときに、前記離散事象システムにおける処理開始時刻ｘ（−０）（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜（−０）（ｋ）として前記記憶部に記憶させる第９のステップと、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（−０）（ｋ）と、前記行列Ｈｏ（ｈ），ＣＯと、出力時刻をｙ〜（ｋ）とを用いて、次の数１５に基づき変更後の設備の最遅開始時刻および最遅終了時刻を表わす行列ｘ〜Ｌ（ｋ）（但し、Ｔは転置行列）を前記演算部で算出する第１０のステップと、
【数１５】
2009015597.tif 000161
をさらに備えたことを特徴とする請求項４記載のスケジュール作成方法。
【請求項７】
一乃至複数の入力，一乃至複数の出力，および複数の設備を組み合わせてなり、前記入力に投入した処理対象を前記複数の設備で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各設備の実行順序を規定する先行制約関係，および前記各設備における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記演算部は、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各設備ｉにおけるｋ番目の処理設備の実行時間をｄｉ（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数１６〜数２１で定義されたシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），Ｂｏ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ決定し、
【数１６】
2009015597.tif 000162
【数１７】
2009015597.tif 000163
【数１８】
2009015597.tif 000164
（但し、ｎを設備数とし、ｈ＝１のとき、
【数１９】
2009015597.tif 000165
ｈ≧２のとき、
【数２０】
2009015597.tif 000166
とする）
【数２１】
2009015597.tif 000167
前記行列Ｆｏを用いて、次の数２２の行列―Ｆｋ＊（但し、ｓは、１≦ｓ≦ｎ）を算出するように構成したことを特徴とするスケジュール作成装置。
【数２２】
2009015597.tif 000168
【請求項８】
前記演算部は、
前記ｈ＝１のとき、前記数１９の行列―Ｈｏ（１）に替えて、次の数２３（ＧＯ−は処理開始時点での順序制約の有無を表わすパラメータであり、ＧＯ＋は処理終了時点での順序制約の有無を表わすパラメータである）を決定することを特徴とする請求項７記載のスケジュール作成装置。
【数２３】
2009015597.tif 000169
但し、前記数２３のＧＯ−およびＧＯ＋は、
【数２４】
2009015597.tif 000170
【数２５】
2009015597.tif 000171
（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）である
【請求項９】
ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，および―Ｆｋ＊と、前記演算部に取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）とを利用して、次の数２６に基づき設備の最早開始時刻および最早終了時刻を表わす行列ｘＥ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を算出するように、前記演算部を構成したことを特徴とする請求項７または８記載のスケジュール作成装置。
【数２６】
2009015597.tif 000172
【請求項１０】
前記記憶部から読み出した入力パラメータに基づいて、次の数２７で定義されたシステム構造を表現する行列ＣＯの要素をさらに決定し、
【数２７】
2009015597.tif 000173
前記ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）、出力時刻をｙ（ｋ）としたときに、前記行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，―Ｆｋ＊，ＣＯと、前記演算部に取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）と、前記出力時刻ｙ（ｋ）とを利用して、次の数２８に基づき設備の最遅開始時刻および最遅終了時刻を表わす行列ｘＬ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を算出するように、前記演算部を構成したことを特徴とする請求項７または８記載のスケジュール作成装置。
【数２８】
2009015597.tif 000174
【請求項１１】
前記離散事象システムにおける設備の処理時間の変更情報を前記演算部が取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に前記行列Ｆｋ＊の変更後の行列Ｆ〜ｋ＊を計算して前記記憶部に記憶し、
前記ｋ番目の設備処理に関して、各設備での処理終了時刻をｘ（＋０）（ｋ）としたときに、前記離散事象システムにおける処理終了時刻ｘ（＋０）（ｋ）（ここで（＋０）は逐次的に計算を行うための初期値であることを表わす）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜（＋０）（ｋ）として前記記憶部に記憶し、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（＋０）（ｋ）と、前記行列Ｈｏ（ｈ），Ｂｏと、入力時刻ｕ〜（ｋ）とを用いて、次の数２９に基づき変更後の設備の最早開始時刻および最早終了時刻を表わす行列ｘ〜Ｅ（ｋ）を算出するように、前記演算部を構成したことを特徴とする請求項９記載のスケジュール作成装置。
【数２９】
2009015597.tif 000175
【請求項１２】
前記離散事象システムにおける設備の処理時間の変更情報を前記演算部が取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に求めた変更後の行列Ｆ〜ｋ＊を前記記憶部に記憶し、
前記ｋ番目の設備処理に関して、各設備での処理開始時刻をｘ（−０）（ｋ）としたときに、前記離散事象システムにおける処理開始時刻ｘ（−０）（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜（−０）（ｋ）として前記記憶部に記憶し、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（−０）（ｋ）と、前記行列Ｈｏ（ｈ），ＣＯと、出力時刻をｙ〜（ｋ）とを用いて、次の数３０に基づき変更後の設備の最遅開始時刻および最遅終了時刻を表わす行列ｘ〜Ｌ（ｋ）（但し、Ｔは転置行列）を算出するように、前記演算部を構成したことを特徴とする請求項１０記載のスケジュール作成装置。
【数３０】
2009015597.tif 000176
【請求項１３】
一乃至複数の入力，一乃至複数の出力，及び複数の設備を組み合わせてなり、前記入力に投入した処理対象を前記複数の設備で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各設備の実行順序を規定する先行制約関係，及び前記各設備における実行時間を、入力パラメータとしてコンピュータに取り込ませ、この入力パラメータを前記コンピュータに記憶させ、さらに前記離散事象システムの状態を表現するために、前記入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるように前記コンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各設備ｉにおけるｋ番目の処理設備の実行時間をｄｉ（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数３１〜数３６で定義されたシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），Ｂｏ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ決定する第１の手順と、
【数３１】
2009015597.tif 000177
【数３２】
2009015597.tif 000178
【数３３】
2009015597.tif 000179
（但し、ｎを設備数とし、ｈ＝１のとき、
【数３４】
2009015597.tif 000180
ｈ≧２のとき、
【数３５】
2009015597.tif 000181
とする）
【数３６】
2009015597.tif 000182
前記行列Ｆｏを用いて、次の数３７の行列―Ｆｋ＊（但し、ｓは、１≦ｓ≦ｎ）を算出する第２の手順と、
【数３７】
2009015597.tif 000183
を前記コンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項１４】
前記ｈ＝１のとき、前記数３４の行列―Ｈｏ（１）に替えて、次の数３８（ＧＯ−は処理開始時点での順序制約の有無を表わすパラメータであり、ＧＯ＋は処理終了時点での順序制約の有無を表わすパラメータである）を決定する前記第１の手順を、前記コンピュータに実行させることを特徴とする請求項１３記載のコンピュータプログラム。
【数３８】
2009015597.tif 000184
但し、前記数３８のＧＯ−およびＧＯ＋は、
【数３９】
2009015597.tif 000185
【数４０】
2009015597.tif 000186
（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）である
【請求項１５】
ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１および第２の手順で算出した行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，および―Ｆｋ＊と、前記コンピュータに取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）とを利用して、次の数４１に基づき設備の最早開始時刻および最早終了時刻を表わす行列ｘＥ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を算出する第３の手順を、前記コンピュータに実行させることを特徴とする請求項１３または１４記載のコンピュータプログラム。
【数４１】
2009015597.tif 000187
【請求項１６】
前記第１の手順は、
前記記憶部から読み出した入力パラメータに基づいて、次の数４２で定義されたシステム構造を表現する行列ＣＯの要素をさらに決定し、
【数４２】
2009015597.tif 000188
前記ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）、出力時刻をｙ（ｋ）としたときに、前記第１および第２の手順で算出した行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，―Ｆｋ＊，Ｃｏと、前記コンピュータに取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）と、前記出力時刻ｙ（ｋ）とを利用して、次の数４３に基づき設備の最遅開始時刻および最遅終了時刻を表わす行列ｘＬ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を算出する第４の手順を、前記コンピュータに実行させることを特徴とする請求項１３または１４記載のコンピュータプログラム。
【数４３】
2009015597.tif 000189
【請求項１７】
前記コンピュータが、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に前記行列Ｆｋ＊の変更後の行列Ｆ〜ｋ＊を計算して前記記憶部に記憶する第５の手順と、
前記ｋ番目の設備処理に関して、各設備での処理終了時刻をｘ（＋０）（ｋ）としたときに、前記離散事象システムにおける処理終了時刻ｘ（＋０）（ｋ）（ここで（＋０）は逐次的に計算を行うための初期値であることを表わす）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜（＋０）（ｋ）として前記記憶部に記憶する第６の手順と、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（＋０）（ｋ）と、前記行列Ｈｏ（ｈ），Ｂｏと、入力時刻ｕ〜（ｋ）とを用いて、次の数４４に基づき変更後の設備の最早開始時刻および最早終了時刻を表わす行列ｘ〜Ｅ（ｋ）を算出する第７の手順と、を前記コンピュータに実行させることを特徴とする請求項１５記載のコンピュータプログラム。
【数４４】
2009015597.tif 000190
【請求項１８】
前記コンピュータが、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に求めた変更後の行列Ｆ〜ｋ＊を前記記憶部に記憶させる第８の手順と、
前記ｋ番目の設備処理に関して、各設備での処理開始時刻をｘ（−０）（ｋ）としたときに、前記離散事象システムにおける処理開始時刻ｘ（−０）（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜（−０）（ｋ）として前記記憶部に記憶させる第９の手順と、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（−０）（ｋ）と、前記行列Ｈｏ（ｈ），ＣＯと、出力時刻をｙ〜（ｋ）とを用いて、次の数４５に基づき変更後の設備の最遅開始時刻および最遅終了時刻を表わす行列ｘ〜Ｌ（ｋ）（但し、Ｔは転置行列）を算出する第１０の手順と、を前記コンピュータに実行させることを特徴とする請求項１６記載のコンピュータプログラム。
【数４５】
2009015597.tif 000191
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の設備を経て作業が行なわれる離散事象システムのスケジュール作成方法，スケジュール作成装置，およびコンピュータプログラムに関する。
【背景技術】
【０００２】
生産システムの設備管理や、交通システムの運行管理など、複数の設備を経て作業（タスク）が行なわれるシステムを検討対象として、そのシステムの定式化をコンピュータ上で実現できるようにしたスケジュール作成方法やスケジュール作成装置が知られている。ここで検討対象となるシステムは、（１）同期，（２）同時実行，（３）非競合などの構造や制約を有するクラスの離散事象システムであり、特に（１）と（２）の構造を有するシステムは、Folk-Joinシステム等とも呼ばれている。
【０００３】
従来、上記離散事象システムの振る舞いは、Dioid代数を用いて簡潔に記述できることが知られている。とりわけmax-plus代数上での線型方程式を用いて、生産システムや交通システム等の事象の最早発生時刻を求めるスケジューリング問題に適用した事例が、先行研究において数多く報告されている。
【０００４】
max-plus代数は、別名（max，＋）代数とも呼ばれており、離散事象システムのモデリング，解析，制御のための代表的なアプローチとして研究が進められている。離散事象システムの典型的な事象生起条件は、（１）複数の離散現象の同期（synchronization）。すなわち、全て生起することが別な離散現象の生起条件となる。（２）事象生起後、一定時間が経過した後に別の事象が生起する。以上の２つの条件が挙げられるが、max-plus代数では、（１）の条件を事象生起時刻のmax演算で記述し、（２）の条件を事象生起時刻と経過時間の＋演算で記述することができる。
【０００５】
max-plus代数の一番大きな特徴は、前記max演算を加算，＋演算を乗算と定義することで、本来は非線形演算となるmax演算に、ある種の線形特性を持たせることができる点にある。そのため、通常の（＋，×）代数系で成立する交換則や分配則が、スカラーや行列の演算において成立するなど、興味深い性質を持つ。特に、ＭＰＬ（max-plus線形）形式と呼ばれるmax-plus代数系での線形方程式を用いて表現できる離散事象システムでは、そのmax-plus代数系での線形方程式が、現代制御理論におけるシステムの状態空間表現に類似した形式となっている。このため、内部モデル制御やモデル予測制御など、現代制御理論における研究成果を応用する試みも行なわれている。
【０００６】
ところで、実システムでのスケジューリングをコンピュータ上で実現させようとする場合、スケジュール作成装置で使用するプログラムのアルゴリズムは、システムに課せられた複雑な制約条件も可能であり、また動的なオンラインスケジューリングが可能であるなどの要請に対応できることが望ましい。例えば、非特許文献１には、内部ノードが有限のバッファ容量を持つシステムに対して、システムの状態変化の最早発生時刻を求める方法が提示されている。また別な非特許文献２では、ジョブの稼動開始後に関連パラメータが変化した時の、再スケジューリング方法について検討を行なっている。
【非特許文献１】エヌ．クリブリン（N.Krivulin），「キューイングネットワークにおけるmax-plus代数モデル（Max-plus algebra models of queueing networks）」，離散事象システムに関する国際ワークショップ９６の論文集（Proc. Int. Workshop Discrete Event Syst.(WODES) '96），ｐｐ．７６〜８１，１９９６年
【非特許文献２】五島  洋行、増田  士朗（H.Goto and S.Masuda），「max-plus線形表現を利用したＭＩＭＯ（多入力多出力）型離散事象システム用のスケジューリング方法（Scheduling Method for MIMO-type Discrete Event Systems Utilizing Max-Plus Linear Representation）」，アジア太平洋経営工学システム論文集（Proc. Asia Pacific Ind. Eng. Manage. Syst.），ｐｐ．１０２９〜１０３６，２００６年
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述した非特許文献１，２の他に、これまでの様々な研究成果によって、ＭＰＬシステムに対応した記述能力の拡張や、計算負荷軽減のための方法が検討され、スケジューリングが可能なモデルの適用範囲が広がってきている。しかし、これまでのスケジューリング作成方法では、バッファ容量の最大値が単一の設備（ノード）内で１、隣接する設備間で無限大という仮定をおいており、実システムへの適用範囲が制限されていることから、適用分野によっては新たな考慮が必要な要素が幾つか残されている。
【０００８】
具体的な例として、例えば生産システムにおいては、一つの建物（施設）内に複数の加工設備が存在し、建物内に保管できる生産品の在庫数には上限値がある。ここで、任意の複数の加工設備間で、収容可能な仕掛り数の上限値を考慮したシステムの定式化ができれば、現実の生産システムに即したスケジューリングが可能になる。また交通システムの一種である鉄道システムにおいては、列車間の混雑や衝突を避けるために、一定区間内に運行が可能な列車本数は自ずと制限される。この場合も、任意の区間内における列車数の上限値を考慮したシステムの定式化が可能になれば、より安全な運行計画を容易に立案することができる。つまり、任意の領域内において、生産品や列車などの処理対象の容量を、容量制約として設定できれば、こうした制約条件を持つシステムを検討対象としたモデリング（定式化）も容易になる。
【０００９】
また、もう一つの主な検討内容は、Event-Varying型システムに特有な順序制約の考慮である。Event-Varying型システムとは、システムパラメータである設備の使用時間が、ジョブ番号毎に変化するようなシステムをいう。こうしたシステムでは、ある設備内における処理対象の最大容量が１よりも大きく、かつそこでの使用時間がジョブ番号によって異なる場合に、次のジョブの使用時間が前のジョブの使用時間よりも短いと、前のジョブの加工中に、次のジョブの加工が終了するいわゆるジョブ順序の逆転が発生し得る。このような場合、システムによってはジョブの追い越しが発生しないように、次のジョブの加工開始時間を遅らせる必要がある。鉄道システムを例にすると、各駅停車の列車と急行列車とでは、駅での停車時間や駅間の所要時間が異なるので、列車間の追い越しが可能な特定の区間で、意図的に追い越しの発生を禁止する順序制約を加えながら、これらの列車間で混雑や衝突が起きないような計画を立てる必要がある。つまり、Event-Varying型システムの容量制約が課せられた設備に対して、ジョブの追い越しが発生しないような順序制約を必要に応じて設定できれば、容量制約および順序制約の二点の制約条件を持つシステムを検討対象としたモデリング（定式化）も容易になる。
【００１０】
本発明は上記の問題点に鑑みなされたもので、その第１の目的は、既存のＭＰＬ状態空間表現を拡張して、単一設備内だけでなく、任意の領域内における処理対象の最大容量を、ＭＰＬ状態空間表現の中で容量制約として考慮することが可能なスケジュール作成方法，スケジュール作成装置，およびコンピュータプログラムを提供することにある。
【００１１】
また本発明の第２の目的は、Event-Varying型システムの容量制約が課せられた設備に対して、ジョブの追い越しが発生しないような順序制約を、必要に応じてＭＰＬ状態空間表現の中で考慮することが可能なスケジュール作成方法，スケジュール作成装置，およびコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明は、一乃至複数の入力，一乃至複数の出力，および複数の設備を組み合わせてなり、前記入力に投入した処理対象を前記複数の設備で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す各前記設備の実行順序を規定する先行制約関係，および各前記設備における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成方法において、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、各前記設備ｉにおけるｋ番目の処理設備の実行時間をｄｉ（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数４６〜数５１で定義されたシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），Ｂｏ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ前記演算部で決定する第１のステップと、
【００１３】
【数４６】
2009015597.tif 000003
【００１４】
【数４７】
2009015597.tif 000004
【００１５】
【数４８】
2009015597.tif 000005
【００１６】
（但し、ｎを設備数とし、ｈ＝１のとき、
【００１７】
【数４９】
2009015597.tif 000006
【００１８】
ｈ≧２のとき、
【００１９】
【数５０】
2009015597.tif 000007
【００２０】
とする）
【００２１】
【数５１】
2009015597.tif 000008
【００２２】
前記行列Ｆｏを用いて、次の数５２の行列―Ｆｋ＊（但し、ｓは、１≦ｓ≦ｎ）を前記演算部で算出する第２のステップと、
【００２３】
【数５２】
2009015597.tif 000009
【００２４】
を順次実行するスケジュール作成方法である。
【００２５】
また、本発明は、上記方法において、前記ｈ＝１のとき、前記数４９の行列―Ｈｏ（１）に替えて、次の数５３（ＧＯ−は処理開始時点での順序制約の有無を表わすパラメータであり、ＧＯ＋は処理終了時点での順序制約の有無を表わすパラメータである）を前記演算部で決定してもよい。
【００２６】
【数５３】
2009015597.tif 000010
【００２７】
但し、前記数５３のＧＯ−およびＧＯ＋は、
【００２８】
【数５４】
2009015597.tif 000011
【００２９】
【数５５】
2009015597.tif 000012
【００３０】
（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）である
さらに、本発明は、上記方法において、ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１および第２のステップで算出した行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，および―Ｆｋ＊と、前記演算部に取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）とを利用して、次の数５６に基づき設備の最早開始時刻および最早終了時刻を表わす行列ｘＥ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を前記演算部で算出する第３のステップをさらに備えている。
【００３１】
【数５６】
2009015597.tif 000013
【００３２】
さらに、上記方法において、第１のステップは、前記記憶部から読み出した入力パラメータに基づいて、次の数５７で定義されたシステム構造を表現する行列ＣＯの要素をさらに前記演算部で決定し、
【００３３】
【数５７】
2009015597.tif 000014
【００３４】
前記ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）、出力時刻をｙ（ｋ）としたときに、前記第１および第２のステップで算出した行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，―Ｆｋ＊，ＣＯと、前記演算部に取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）と、前記出力時刻ｙ（ｋ）とを利用して、次の数５８に基づき設備の最遅開始時刻および最遅終了時刻を表わす行列ｘＬ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を前記演算部で算出する第４のステップをさらに備えている。
【００３５】
【数５８】
2009015597.tif 000015
【００３６】
さらに、本発明は、上記方法において、前記演算部が、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に前記行列Ｆｋ＊の変更後の行列Ｆ〜ｋ＊を計算して前記記憶部に記憶する第５のステップと、
前記ｋ番目の設備処理に関して、各設備での処理終了時刻をｘ（＋０）（ｋ）としたときに、前記離散事象システムにおける処理終了時刻ｘ（＋０）（ｋ）（ここで（＋０）は逐次的に計算を行うための初期値であることを表わす）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜（＋０）（ｋ）として前記記憶部に記憶する第６のステップと、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（＋０）（ｋ）と、前記行列Ｈｏ（ｈ），Ｂｏと、入力時刻ｕ〜（ｋ）とを用いて、次の数５９に基づき変更後の設備の最早開始時刻および最早終了時刻を表わす行列ｘ〜Ｅ（ｋ）を前記演算部で算出する第７のステップと、
【００３７】
【数５９】
2009015597.tif 000016
【００３８】
をさらに備えている。
【００３９】
さらに、本発明は、上記方法において、前記演算部が、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に求めた変更後の行列Ｆ〜ｋ＊を前記記憶部に記憶させる第８のステップと、
前記ｋ番目の設備処理に関して、各設備での処理開始時刻をｘ（−０）（ｋ）としたときに、前記離散事象システムにおける処理開始時刻ｘ（−０）（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜（−０）（ｋ）として前記記憶部に記憶させる第９のステップと、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（−０）（ｋ）と、前記行列Ｈｏ（ｈ），ＣＯと、出力時刻をｙ〜（ｋ）とを用いて、次の数６０に基づき変更後の設備の最遅開始時刻および最遅終了時刻を表わす行列ｘ〜Ｌ（ｋ）（但し、Ｔは転置行列）を前記演算部で算出する第１０のステップと、
【００４０】
【数６０】
2009015597.tif 000017
【００４１】
をさらに備えている。
【００４２】
さらに、本発明は、一乃至複数の入力，一乃至複数の出力，および複数の設備を組み合わせてなり、前記入力に投入した処理対象を前記複数の設備で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各設備の実行順序を規定する先行制約関係，および前記各設備における実行時間が取込部で入力パラメータとして取り込まれると、この取込部で取り込んだ入力パラメータを記憶部で記憶し、さらに前記離散事象システムの状態を表現するために、前記記憶部から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に演算部が変換するスケジュール作成装置において、
前記演算部は、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各設備ｉにおけるｋ番目の処理設備の実行時間をｄｉ（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数６１〜数６６で定義されたシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），Ｂｏ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ決定し、
【００４３】
【数６１】
2009015597.tif 000018
【００４４】
【数６２】
2009015597.tif 000019
【００４５】
【数６３】
2009015597.tif 000020
【００４６】
（但し、ｎを設備数とし、ｈ＝１のとき、
【００４７】
【数６４】
2009015597.tif 000021
【００４８】
ｈ≧２のとき、
【００４９】
【数６５】
2009015597.tif 000022
【００５０】
とする）
【００５１】
【数６６】
2009015597.tif 000023
【００５２】
前記行列Ｆｏを用いて、次の数６７の行列―Ｆｋ＊（但し、ｓは、１≦ｓ≦ｎ）を算出するように構成したスケジュール作成装置である。
【００５３】
【数６７】
2009015597.tif 000024
【００５４】
さらに、上記装置において、前記演算部は、前記ｈ＝１のとき、前記数６４の行列―Ｈｏ（１）に替えて、次の数６５（ＧＯ−は処理開始時点での順序制約の有無を表わすパラメータであり、ＧＯ＋は処理終了時点での順序制約の有無を表わすパラメータである）を決定してもよい。
【００５５】
【数６８】
2009015597.tif 000025
【００５６】
但し、前記数６８のＧＯ−およびＧＯ＋は、
【００５７】
【数６９】
2009015597.tif 000026
【００５８】
【数７０】
2009015597.tif 000027
【００５９】
（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）である
さらに、本発明は、上記装置において、ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，および―Ｆｋ＊と、前記演算部に取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）とを利用して、次の数７１に基づき設備の最早開始時刻および最早終了時刻を表わす行列ｘＥ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を算出するように、前記演算部を構成している。
【００６０】
【数７１】
2009015597.tif 000028
【００６１】
さらに、本発明は、上記装置において、前記記憶部から読み出した入力パラメータに基づいて、次の数７２で定義されたシステム構造を表現する行列ＣＯの要素をさらに決定し、
【００６２】
【数７２】
2009015597.tif 000029
【００６３】
前記ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）、出力時刻をｙ（ｋ）としたときに、前記行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，―Ｆｋ＊，ＣＯと、前記演算部に取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）と、前記出力時刻ｙ（ｋ）とを利用して、次の数７３に基づき設備の最遅開始時刻および最遅終了時刻を表わす行列ｘＬ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を算出するように、前記演算部を構成している。
【００６４】
【数７３】
2009015597.tif 000030
【００６５】
さらに、本発明は、上記装置において、前記離散事象システムにおける設備の処理時間の変更情報を前記演算部が取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に前記行列Ｆｋ＊の変更後の行列Ｆ〜ｋ＊を計算して前記記憶部に記憶し、
前記ｋ番目の設備処理に関して、各設備での処理終了時刻をｘ（＋０）（ｋ）としたときに、前記離散事象システムにおける処理終了時刻ｘ（＋０）（ｋ）（ここで（＋０）は逐次的に計算を行うための初期値であることを表わす）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜（＋０）（ｋ）として前記記憶部に記憶し、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（＋０）（ｋ）と、前記行列Ｈｏ（ｈ），Ｂｏと、入力時刻ｕ〜（ｋ）とを用いて、次の数７４に基づき変更後の設備の最早開始時刻および最早終了時刻を表わす行列ｘ〜Ｅ（ｋ）を算出するように、前記演算部を構成している。
【００６６】
【数７４】
2009015597.tif 000031
【００６７】
さらに、本発明は、上記装置において、前記離散事象システムにおける設備の処理時間の変更情報を前記演算部が取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に求めた変更後の行列Ｆ〜ｋ＊を前記記憶部に記憶し、
前記ｋ番目の設備処理に関して、各設備での処理開始時刻をｘ（−０）（ｋ）としたときに、前記離散事象システムにおける処理開始時刻ｘ（−０）（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜（−０）（ｋ）として前記記憶部に記憶し、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（−０）（ｋ）と、前記行列Ｈｏ（ｈ），ＣＯと、出力時刻をｙ〜（ｋ）とを用いて、次の数７５に基づき変更後の設備の最遅開始時刻および最遅終了時刻を表わす行列ｘ〜Ｌ（ｋ）（但し、Ｔは転置行列）を算出するように、前記演算部を構成している。
【００６８】
【数７５】
2009015597.tif 000032
【００６９】
さらに、本発明は、一乃至複数の入力，一乃至複数の出力，及び複数の設備を組み合わせてなり、前記入力に投入した処理対象を前記複数の設備で処理し、その処理結果を出力に送り出す離散事象システムに関し、前記処理対象を受け渡す前記各設備の実行順序を規定する先行制約関係，及び前記各設備における実行時間を、入力パラメータとしてコンピュータに取り込ませ、この入力パラメータを前記コンピュータに記憶させ、さらに前記離散事象システムの状態を表現するために、前記入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式に変換できるように前記コンピュータに演算を行なわせるコンピュータプログラムにおいて、
前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、前記各設備ｉにおけるｋ番目の処理設備の実行時間をｄｉ（ｋ）としたときに、前記記憶部から読み出した入力パラメータに基づいて、次の数７６〜数８１で定義されたシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），Ｂｏ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれ決定する第１の手順と、
【００７０】
【数７６】
2009015597.tif 000033
【００７１】
【数７７】
2009015597.tif 000034
【００７２】
【数７８】
2009015597.tif 000035
【００７３】
（但し、ｎを設備数とし、ｈ＝１のとき、
【００７４】
【数７９】
2009015597.tif 000036
【００７５】
ｈ≧２のとき、
【００７６】
【数８０】
2009015597.tif 000037
【００７７】
とする）
【００７８】
【数８１】
2009015597.tif 000038
【００７９】
前記行列Ｆｏを用いて、次の数８２の行列―Ｆｋ＊（但し、ｓは、１≦ｓ≦ｎ）を算出する第２の手順と、
【００８０】
【数８２】
2009015597.tif 000039
【００８１】
を前記コンピュータに実行させるコンピュータプログラムである。
【００８２】
また、本発明は、上記コンピュータプログラムにおいて、前記ｈ＝１のとき、前記数７９の行列―Ｈｏ（１）に替えて、次の数８３（ＧＯ−は処理開始時点での順序制約の有無を表わすパラメータであり、ＧＯ＋は処理終了時点での順序制約の有無を表わすパラメータである）を決定する前記第１の手順を、前記コンピュータに実行させている。
【００８３】
【数８３】
2009015597.tif 000040
【００８４】
但し、前記数８３のＧＯ−およびＧＯ＋は、
【００８５】
【数８４】
2009015597.tif 000041
【００８６】
【数８５】
2009015597.tif 000042
【００８７】
（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）である
さらに、本発明は、上記コンピュータプログラムにおいて、ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）としたときに、前記第１および第２の手順で算出した行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，および―Ｆｋ＊と、前記コンピュータに取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）とを利用して、次の数８６に基づき設備の最早開始時刻および最早終了時刻を表わす行列ｘＥ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を算出する第３の手順を、前記コンピュータに実行させている。
【００８８】
【数８６】
2009015597.tif 000043
【００８９】
さらに、上記コンピュータプログラムにおいて、前記第１の手順は、前記記憶部から読み出した入力パラメータに基づいて、次の数８７で定義されたシステム構造を表現する行列ＣＯの要素をさらに決定し、
【００９０】
【数８７】
2009015597.tif 000044
【００９１】
前記ｋ番目の設備処理に関して、各設備での処理開始時刻および処理終了時刻を表わす行列をｘ（ｋ）とし、入力時刻をｕ（ｋ）、出力時刻をｙ（ｋ）としたときに、前記第１および第２の手順で算出した行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，―Ｆｋ＊，Ｃｏと、前記コンピュータに取り込まれる行列ｘ（ｋ）と、前記入力時刻ｕ（ｋ）と、前記出力時刻ｙ（ｋ）とを利用して、次の数８８に基づき設備の最遅開始時刻および最遅終了時刻を表わす行列ｘＬ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）を算出する第４の手順を、前記コンピュータに実行させている。
【００９２】
【数８８】
2009015597.tif 000045
【００９３】
さらに、本発明は、上記コンピュータプログラムにおいて、前記コンピュータが、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に前記行列Ｆｋ＊の変更後の行列Ｆ〜ｋ＊を計算して前記記憶部に記憶する第５の手順と、
前記ｋ番目の設備処理に関して、各設備での処理終了時刻をｘ（＋０）（ｋ）としたときに、前記離散事象システムにおける処理終了時刻ｘ（＋０）（ｋ）（ここで（＋０）は逐次的に計算を行うための初期値であることを表わす）の変更情報を取得すると、これを変更後の処理終了時刻ｘ〜（＋０）（ｋ）として前記記憶部に記憶する第６の手順と、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（＋０）（ｋ）と、前記行列Ｈｏ（ｈ），Ｂｏと、入力時刻ｕ〜（ｋ）とを用いて、次の数８９に基づき変更後の設備の最早開始時刻および最早終了時刻を表わす行列ｘ〜Ｅ（ｋ）を算出する第７の手順と、を前記コンピュータに実行させている。
【００９４】
【数８９】
2009015597.tif 000046
【００９５】
さらに、本発明は、上記コンピュータプログラムにおいて、前記コンピュータが、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この処理時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に求めた変更後の行列Ｆ〜ｋ＊を前記記憶部に記憶させる第８の手順と、
前記ｋ番目の設備処理に関して、各設備での処理開始時刻をｘ（−０）（ｋ）としたときに、前記離散事象システムにおける処理開始時刻ｘ（−０）（ｋ）の変更情報を取得すると、これを変更後の処理開始時刻ｘ〜（−０）（ｋ）として前記記憶部に記憶させる第９の手順と、
前記記憶部から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（−０）（ｋ）と、前記行列Ｈｏ（ｈ），ＣＯと、出力時刻をｙ〜（ｋ）とを用いて、次の数９０に基づき変更後の設備の最遅開始時刻および最遅終了時刻を表わす行列ｘ〜Ｌ（ｋ）（但し、Ｔは転置行列）を算出する第１０の手順と、を前記コンピュータに実行させている。
【００９６】
【数９０】
2009015597.tif 000047
【発明の効果】
【００９７】
請求項１の方法，請求項７の装置，及び請求項１３のコンピュータプログラムによれば、入力パラメータとして、各設備の実行時間と設備間の先行制約関係の各情報が予め記憶されていれば、そこから独自のシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），およびＢｏについて、その各要素を決定し、さらにここで決定した行列Ｆｏから行列―Ｆｏ＊を算出して、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ｐｋ，―Ｆｏ＊，Ｈｏ（ｈ），およびＢｏを簡単に取得することができる。かくして、既存のＭＰＬ状態空間表現を拡張して、単一設備内だけでなく、任意の領域内における処理対象の最大容量を、ＭＰＬ状態空間表現の中で容量制約として考慮することが可能なスケジュール作成方法，スケジュール作成装置，およびコンピュータプログラムを提供できる。
【００９８】
また、容量制約および順序制約を有するシステムのスケジュール作成をコンピュータで実現する上で、より少ないメモリ消費で、与えられたシステムを、容量制約および順序制約を考慮したＭＰＬシステムとして表現できる形式に簡単に導出することが可能になる。
【００９９】
請求項２の方法，請求項８の装置，及び請求項１４のコンピュータプログラムによれば、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ｐｋ，―Ｆｏ＊，Ｈｏ（ｈ），およびＢｏを簡単に取得することができると共に、選択的に設定した順序制約を考慮したＨｏ（ｈ）についても簡単に取得することができる。かくして、Event-Varying型システムの容量制約が課せられた設備に対して、ジョブの追い越しが発生しないような順序制約を、必要に応じてＭＰＬ状態空間表現の中で考慮することが可能なスケジュール作成方法，スケジュール作成装置，およびコンピュータプログラムを提供できる。
【０１００】
請求項３の方法，請求項９の装置，及び請求項１５のコンピュータプログラムによれば、処理開始時刻および処理終了時刻を表わす行列ｘ（ｋ）と入力時刻ｕ（ｋ）が取り込まれれば、先に算出した行列Ｐｋ，―Ｆｏ＊，Ｈｏ（ｈ），およびＢｏを利用して、行列ｘＥ（ｋ）を簡単に算出することができ、かくして行列ｘＥ（ｋ）によって、システムを構成する全ての設備での最早開始時刻および最早終了時刻を把握することができる。
【０１０１】
請求項４の方法，請求項１０の装置，及び請求項１６のコンピュータプログラムによれば、処理開始時刻および処理終了時刻を表わす行列ｘ（ｋ）と入力時刻ｕ（ｋ）と出力時刻ｙ（ｋ）とが取り込まれれば、先に算出した行列Ｐｋ，―Ｆｏ＊，Ｈｏ（ｈ），Ｂｏ，およびＣｏを利用して、行列ｘＬ（ｋ）を簡単に算出することができ、かくして行列ｘＬ（ｋ）によって、システムを構成する全ての設備での最遅開始時刻および最遅終了時刻を適確に且つ効率的に把握することができる。
【０１０２】
請求項５の方法，請求項１１の装置，及び請求項１７のコンピュータプログラムによれば、システムの稼動開始後に何らかの原因で、その入力時刻や処理時間、処理終了時刻が変化した場合でも、算出される行列ｘ〜Ｅに基づいて、全ての設備における変更後の最早開始時刻および最早終了時刻を適確に且つ効率的に把握することができる。
【０１０３】
請求項６の方法，請求項１２の装置，及び請求項１８のコンピュータプログラムによれば、システムの稼動開始後に何らかの原因で、その入力時刻や処理時間、処理開始時刻が変化した場合でも、算出される行列ｘ〜Ｌに基づいて、全ての設備における変更後の最遅開始時刻および最遅終了時刻を適確に且つ効率的に把握することができる。
【発明を実施するための最良の形態】
【０１０４】
以下、添付図面に基づいて、本発明における好適な各実施例を詳細に説明する。
【実施例１】
【０１０５】
図１は、本発明の第１実施例におけるスケジュール作成方法を実現するスケジュール作成装置１の内部構成を示すブロック図である。スケジュール作成装置１は、パーソナルコンピュータ又はサーバ装置などの汎用コンピュータを用いて構成されている。スケジュール作成装置１は、演算を行なうＣＰＵ（演算部）１１と、演算に伴って発生する一時的な情報などを記憶するＲＡＭ（記憶部）１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備えている。ＣＰＵ１１は、ＣＤ−ＲＯＭ等の記録媒体２から本発明のコンピュータプログラム２０を外部記憶装置１３にて読み取り、読み取ったコンピュータプログラム２０を内部記憶装置１４に記憶させる。コンピュータプログラム２０は必要に応じて内部記憶装置１４からＲＡＭ１２へロードされ、ロードされたコンピュータプログラム２０に基づいてＣＰＵ１１はスケジュール作成装置１に必要な処理を実行する。
【０１０６】
スケジュール作成装置１は、オペレータの操作により情報が入力されるキーボード等の装置，又は図示しない外部の装置からスケジュール作成のために必要な情報が入力される装置からなる取込部としての入力装置１５を備えている。またスケジュール装置１は、ＣＲＴディスプレイ等の表示装置，プリンタ装置，または作成したスケジュールを図示しない外部の装置へ出力する装置からなる出力装置１６を備えている。
【０１０７】
なお、本発明のコンピュータプログラム２０は、スケジュール作成装置１に接続された図示しない外部のサーバ装置からスケジュール作成装置１へロードされて内部記憶装置１４に記憶される形態であってもよい。
【０１０８】
本発明のスケジュール作成装置１が行なう処理の目的は、作業プロセスの最適なスケジュールを作成することであり、より具体的には、ＭＰＬ形式作成手順と、スケジュール生成手順と、再スケジュール生成手順とをコンピュータプログラム２０に含んでいる。
【０１０９】
ここでＭＰＬ形式作成手順，スケジュール生成手順，および再スケジュール生成手順について簡単に説明する。ＭＰＬ形式作成手順は、オペレータが入力装置１５から入力した各種パラメータと、容量制約および順序制約とに基づいて、ＭＰＬシステムに適合する作業プロセスの状態を表現した式を、スケジュール作成装置１に作成させ得るようになされている。
【０１１０】
スケジュール生成手順は、前記ＭＰＬ形式作成手順の途中で導入された行列を利用して、システムの全設備における最早開始時刻，最早終了時刻，最遅開始時刻，および最遅終了時刻をスケジュール作成装置１に決定させ得るようになされている。
【０１１１】
再スケジュール生成手順は、材料の投入（以下、入力とも呼ぶ）時刻，加工（以下、処理とも呼ぶ）時間，加工開始時刻，または加工終了時刻の変動値を入力したときに、前記スケジュール生成手順で決定した最早開始時刻，最早終了時刻，最遅開始時刻，および最遅終了時刻が、どのように変化するのかを、前記ＭＰＬ形式作成手順の途中で導入された容量制約行列Ｈｏ（後述する）を利用して、スケジュール作成装置１に決定させ得るようになされている。
【０１１２】
そして、このようなコンピュータプログラム２０を記憶した記憶媒体２を外部記憶手段１３に装着すると、スケジュール作成装置１のＣＰＵ１１は当該コンピュータプログラム２０をＲＡＭ１２に自動的にロードし、内蔵する上記各手順を処理実行する。つまりスケジュール作成装置１のＣＰＵ１１は、ソフトウェア上の機能として、オペレータが入力装置１５から入力した各種パラメータと、設備間の容量制約とに基づいて、ＭＰＬシステムに適合する作業プロセスの状態を表現した式を作成するＭＰＬ形式作成手段３１と、前記ＭＰＬ形式作成手段３１がＭＰＬシステムに適合する作業プロセスの状態を表現した式を作成する途中で導入した各行列を利用して、システムの全設備における最早開始時刻，最早終了時刻，最遅開始時刻，および最遅終了時刻を決定するスケジュール生成手段３２と、材料投入時刻，加工時間，加工開始時刻，または加工終了時刻の変動値を入力したときに、前記スケジュール生成手順で決定した最早開始時刻，最早終了時刻，最遅開始時刻，および最遅終了時刻がどのように変化するのかを、前記ＭＰＬ形式作成手順の途中で導入された容量制約行列Ｈｏを利用して決定する再スケジュール生成手段３３と、を備えている。
【０１１３】
ここでは先ず始めに、ＭＰＬ形式作成手順に用いるＭＰＬ（max-plus線形）形式と呼ばれるmax-plus代数について、具体的に説明する。max-plus代数とは、或るクラスの離散事象システムの記述に適した代数系であり、ここでは実数体をＲと表し、フィールドＤ＝Ｒ∪｛±∞｝において、ｘ，ｙ∈Ｄのとき、４つの基本演算式を次のように定義する。
【０１１４】
【数９１】
2009015597.tif 000048
【０１１５】
【数９２】
2009015597.tif 000049
【０１１６】
なお、この加算や乗算の演算子は、通常の代数系での演算子と区別するために、「＋」や「×」のシンボルを丸印で囲んで表現するが、乗算については混乱のない限り演算子の表記を省略する。これらの演算子の間には、通常の代数系と同様に、交換法則，結合法則，分配法則が成り立ち、式の変形など通常の代数系と同様の計算を行なうことができる。なお、上記max関数は、括弧内で最大の値を算出することを意味し、min関数は、括弧内で最小の値を算出することを意味する。加算演算子（丸印内に＋）、乗算演算子（（丸印内に×）および演算子「∧」の単位元を、それぞれε（＝−∞）、ｅ（＝０）およびＴ（＝＋∞）と定義すると、複数の数に対する演算子は、ｍ≦ｎのときに、次のように記述される。
【０１１７】
【数９３】
2009015597.tif 000050
【０１１８】
【数９４】
2009015597.tif 000051
【０１１９】
max-plus代数では、Ｄの元を要素に持つ行列に対しても、同様の演算子を用いて定義することができる。ここでは、ｍ行ｎ列の行列Ｘ（Ｘ∈Ｄｍ×ｎ）に対し、ＸＴは行列Ｘの転置行列を表し、［Ｘ］ijはｉ行ｊ列の成分（要素）を表わすものとする。また、ｍ行ｎ列の行列Ｘ，Ｙ（Ｘ，Ｙ∈Ｄｍ×ｎ）において、全てのｉおよびｊに対して（但し、１≦ｉ≦ｍ，１≦ｊ≦ｎ）、［Ｘ］ij≦［Ｙ］ijが成立するときに、Ｘ≦Ｙと表わす。このとき、Ｘ，Ｙ∈Ｄｍ×ｎに対して、次式に示す演算式を定義する。
【０１２０】
【数９５】
2009015597.tif 000052
【０１２１】
【数９６】
2009015597.tif 000053
【０１２２】
また、ｍ行ｌ列の行列Ｘと、ｌ行ｐ列の行列Ｙ（Ｘ∈Ｄｍ×ｌ，Ｙ∈Ｄｌ×ｐ）に対して、次の式に示す演算式を定義する。
【０１２３】
【数９７】
2009015597.tif 000054
【０１２４】
【数９８】
2009015597.tif 000055
【０１２５】
なお、丸印内に「×」の乗算演算子、「＼」の演算子および丸印内に「・」の演算子の優先順位は、丸印内に「＋」の加算演算子および「∧」の演算子よりも高いとする。さらに、加算の単位元はεｍｎと表記し、これはεｍｎ∈Ｄｍ×ｎにおいて、全ての成分がεであることを意味する。また乗算の単位元はｅｍと表記し、これはｅｍ∈Ｄｍ×ｍにおいて、対角成分のみｅで、それ以外の非対称成分は全てεであることを意味する。Ｘ，Ｙ∈Ｄl×m、Ｚ∈Ｄm×l、v，w∈Ｄl×mに対しては、次の関係式が成り立つ。
【０１２６】
【数９９】
2009015597.tif 000056
【０１２７】
また、ｖ≧ｗの表記は次の関係式と等価である。
【０１２８】
【数１００】
2009015597.tif 000057
【０１２９】
以上の定義により、max-plus代数において、線形性を有する行列演算が可能となる。ここでスケジュール作成装置１は、背景技術で説明したFork-join型構造を有すると仮定し、ｎ個の設備と、ｍ個の外部入力と、ｐ個の外部出力とを有する構成とする。
【０１３０】
また、このスケジュール作成装置１においては、各設備間の輸送時間が無視できる場合と、当該輸送時間が無視できない場合とがあるが、先ず始めに各設備間の輸送時間が無視できる場合について説明し、加工順序に関して課せられる条件を、次のように設定する。
・各ジョブ共に全ての設備を使用し、かつ各設備の加工回数は一回である。すなわち、非サイクリック構造である。
・先行設備を有する設備は、それらの先行設備での加工が終了しないと、加工を開始できない。
・外部入力のある設備は、必要材料が投入されるまで、その加工を開始できない。
・容量制約が課された設備は、領域内のジョブ数が、指定された値以下になるまで加工を開始できない。
・全ての設備において、加工の開始と終了とはジョブ番号の順に行われる。つまり第１実施例では、同一の設備内でジョブの追い越しが発生しないように制約条件を課している。
【０１３１】
ＭＰＬ形式作成手段３１は、スケジュールを作成しようとする作業プロセスにおいて、設備ｉ（１≦ｉ≦ｎ）におけるｋ番目のジョブの加工時間をｄｉ（ｋ）（≧０）、加工開始時刻および加工終了時刻を、それぞれ［ｘＳ（ｋ）］ｉおよび［ｘＣ（ｋ）］ｉとして定義する。また、外部入力ｉ（１≦ｉ≦ｍ）に対し、材料の投入時刻を［ｕ（ｋ）］ｉと定義し、外部出力ｉ（１≦ｉ≦ｐ）に対し、材料の出力時刻を［ｙ（ｋ）］ｉと定義する。なお、以下、最早時刻および最遅時刻を表すときにはそれぞれ下添え字ＥおよびＬを付加する。
【０１３２】
本発明においては、前のイベント（ジョブ）との非競合を考慮して、当該イベントの内部状態が、前のイベントの内部状態の関数で表現されるフォワード型のＭＰＬ状態空間表現を導くシステム構造と、後続イベントとの非競合を考慮して、当該イベントの内部状態が、後続イベントの内部状態の関数で表現されるバックワード型のＭＰＬ状態空間表現とを導くシステム構造があり、ここでは先ず始めにフォワード型のＭＰＬ状態空間表現を導くシステム構造について説明した後、バックワード型のＭＰＬ状態空間表現を導くシステム構造について説明する。
【０１３３】
ＭＰＬ形式作成手段３１は、これらフォワード型およびバックワード型のシステム構造を表現するために、入力された各種パラメータから、次の新たに導入されたパラメータ行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ）∈Ｄｎ×ｎ，Ｂｏ∈Ｄｎ×ｍ，およびＣｏ∈Ｄｐ×ｎの各要素を算出し決定する。
【０１３４】
【数１０１】
2009015597.tif 000058
【０１３５】
【数１０２】
2009015597.tif 000059
【０１３６】
【数１０３】
2009015597.tif 000060
【０１３７】
【数１０４】
2009015597.tif 000061
【０１３８】
【数１０５】
2009015597.tif 000062
【０１３９】
特に、上記数１０３に示す行列Ｈｏ（ｈ）は本発明独自のもので、これを容量制約行列として呼ぶこととする。フォワード型のＭＰＬ状態空間表現を導くシステム構造において、スケジュール生成手段３２は、これら数１０１〜数１０５を利用して、全ての行程（設備）について最早開始時刻［ｘＥＳ（ｋ）］ｉおよび最早終了時刻［ｘＥＣ（ｋ）］ｉを算出し得るようになされている。ここで最早開始時刻［ｘＥＳ（ｋ）］ｉとは、その設備ｉが最も早く加工を開始できる時刻であり、最早終了時刻［ｘＥＣ（ｋ）］ｉとは、その設備ｉが最も早く加工を終了できる時刻である。具体的には、設備ｉ（但し、１≦ｉ≦ｎである）の最早開始時刻［ｘＥＳ（ｋ）］ｉおよび最早終了時刻［ｘＥＣ（ｋ）］ｉはそれぞれ次のように表記できる。
【０１４０】
【数１０６】
2009015597.tif 000063
【０１４１】
【数１０７】
2009015597.tif 000064
【０１４２】
但し、Ｑは、システムに課される容量制約の容量の最大値である。
【０１４３】
次に、これら数１０６および数１０７についてどのような意味を持つのかを考察する。数１０６および数１０７は任意のｉ（１≦ｉ≦ｎ）に対して成り立つことに留意し、これら数１０６および数１０７をまとめて行列表現すると次のようになる。
【０１４４】
【数１０８】
2009015597.tif 000065
【０１４５】
但し、次のような拡大ベクトルおよび行列を導入する。
【０１４６】
【数１０９】
2009015597.tif 000066
【０１４７】
なお、上述したように、最早時刻および最遅時刻を表すときにはそれぞれ下添え字ＥおよびＬを付加することから、ｘ（ｋ）の行列は、それぞれｘＥ（ｋ）（［］内は、最早開始時刻ｘＥＳ（ｋ），最早終了時刻ｘＥＣ（ｋ））と、ｘＬ（ｋ）（［］内は、最遅開始時刻ｘＬＳ（ｋ），最遅終了時刻ｘＬＣ（ｋ））とで表わされる。第１実施例では、全ての位置でＦＩおよびＦＯ条件を課すという、より強い制約を持たせるために、行列−Ｈ０（１）の対角成分がｅｎとなっている。そのため、全ての設備ｉの加工開始および加工終了時点で、順序制約を強制的に設定する場合には、数１０９の行列表現が適用される。数１０８はｘＥ（ｋ）に関する陰的な表現になっているので、これを陽的な形式に変換すると、次のように表わすことができる。
【０１４８】
【数１１０】
2009015597.tif 000067
【０１４９】
ここで、―Ｆｋ＊は次のように定義する。
【０１５０】
【数１１１】
2009015597.tif 000068
【０１５１】
この数１１１において、定数ｓ（１≦ｓ≦ｎ）はシステムの先行制約関係に依存するものである。また、（ＦｏＰｋ）＊と（ＰｋＦｏ）＊は次のような関係で結ばれている。
【０１５２】
【数１１２】
2009015597.tif 000069
【０１５３】
この数１１０の式は、各設備での順序制約を強制的に設定しつつ、任意の二設備間の最大容量を考慮することのできる、拡張されたフォワード型のＭＰＬ状態空間表現である。これはＭＰＬ形式作成手段３１が、各設備ｉにおけるｋ番目のジョブの使用時間ｄｉ（ｋ）を取り込んで、数１０１の行列を算出し、各設備ｉの実行順序を規定する先行制約関係を取り込んで、個々の設備ｉにおける外部入力ｊおよび先行設備ｊの有無を判断することにより、数１０２および数１０４の各行列を算出し、設備ｉと下流設備ｊとの間に存在可能なジョブ数の最大値ｈを取り込んで、数１０３の行列を算出し、次にこれらの算出結果から、数１０９に示す拡大ベクトルおよび行列を算出し、さらに数１１１を算出することで、数１１０の各要素を決定することができる。また、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で作成された数１１０から、材料の投入時刻ｕ（ｋ）を取り込んで、各設備の最早加工開始時刻ｘＳＥ（ｋ）と、最早加工終了時刻ｘＣＥ（ｋ）を求めることができる。
【０１５４】
また、このときの最早出力時刻ｙＥ（ｋ）を求める出力方程式については、次に式で与えられる。
【０１５５】
【数１１３】
2009015597.tif 000070
【０１５６】
この数１１３は、上記数１１０と同じ状態変数を用いて表現すると、当該数１１３と同様、次の式に示すような現代制御理論の状態空間表現に類似した形式で表される。
【０１５７】
【数１１４】
2009015597.tif 000071
【０１５８】
なお、ｘ（ｋ）は加工開始時刻ｘＳ（ｋ）および加工終了時刻ｘＣ（ｋ）の両者を示す行列である。但し、−Ｃｏは、次の数１１５の行列で表される。
【０１５９】
【数１１５】
2009015597.tif 000072
【０１６０】
次に容量制約と順序制約を考慮し、設備ｉの最遅加工開始時刻ｘｓＬ（ｋ）と最遅加工終了時刻ｘＣＬ（ｋ）を求めるバックワード型のＭＰＬ状態空間表現について以下説明する。ここでは先ず始めにスケジュール作成手段３２が計算に利用する状態方程式と出力方程式とについて考察する。なお、ここで用いるパラメータ行列は、上述したＰｋ，Ｆｏ，Ｈｏ（ｈ）∈Ｄｎ×ｎ，Ｂ０∈Ｄｎ×ｍ，およびＣｏ∈Ｄｐ×ｎと同じである。
【０１６１】
図２は、設備ｉ（１≦ｉ≦ｎ）に関する制約関係を模式的にあらわしたものであり、ここで使用するＳｉは後続設備の集合を意味し、Ｐｉは接続された外部出力番号の集合を意味する。また、設備ｉでの加工終了時点と、その上流方向に存在する設備ｊの加工開始時点との間に存在可能な最大ジョブ数が設定され、かつその数がｈとなるような設備番号ｊの集合をＮｉｊとする。設備ｉにおけるｋ番目のジョブの最遅加工開始時刻および最遅加工終了時刻を、それぞれ［ｘＬＳ（ｋ）］ｉおよび［ｘＬＣ（ｋ）］ｉとして定義する。
【０１６２】
上記定義のもと、スケジュール作成手段３２は、バックワード型のＭＰＬ状態空間表現を利用して、設備ｉでの最遅時刻（すなわち、最遅加工開始時刻［ｘＬＳ（ｋ）］ｉおよび最遅加工終了時刻［ｘＬＣ（ｋ）］ｉ）を算出し得るようになされている。ここで最遅開始時刻［ｘＬＳ（ｋ）］ｉとは、ある設備ｉにおいて、最早開始時刻で加工を行なった場合と同一の出力時刻を実現することが可能な、最も遅い加工開始時刻であり、最遅終了時刻［ｘＬＣ（ｋ）］ｉとは、その設備ｉが最も遅く加工を終了する時刻である。但し、設備ｉにおけるジョブの加工終了時刻は、下記の４つの時刻以前でなければならないと定義する。
・後続設備ｊ∈Ｓｉでの最遅加工開始時刻［ｘＬＳ（ｋ）］ｊ
・外部出力ｊ∈Ｐｉへのジョブの出力時刻［ｙ（ｋ）］ｊ
・上流設備ｊ∈Ｎｉｈにおけるｋ＋ｈ番目のジョブの加工開始時刻［ｘＳ（ｋ＋ｈ）］ｊ
・次のジョブの加工終了時刻［ｘＣ（ｋ＋１）］ｉ
上記定義のもと、スケジュール生成手段３２において算出する設備iの最遅加工終了時刻［ｘＬＣ（ｋ）］ｉは、次のように表される。
【０１６３】
【数１１６】
2009015597.tif 000073
【０１６４】
また、設備ｉにおけるジョブの加工開始時刻は、次の両方の時刻以前でなければならないと定義する。
・設備での加工終了時刻から、ｄｉ（ｋ）を減じた時刻
・次のジョブの加工開始時刻［ｘｓ（ｋ＋１）］ｉ
上記定義のもと、スケジュール生成手段３２において算出する設備iの最遅加工開始時刻［ｘＬｓ（ｋ）］ｉは、次のように表すことができる。
【０１６５】
【数１１７】
2009015597.tif 000074
【０１６６】
ここで最遅加工開始時刻［ｘＬｓ（ｋ）］ｉおよび最遅加工終了時刻［ｘＬｃ（ｋ）］ｉについて考察すると、数１１６および数１１７は、任意のｉ（１≦ｉ≦ｎ）に対して成り立ち、これらをまとめて行列表示すると、次のように表される。
【０１６７】
【数１１８】
2009015597.tif 000075
【０１６８】
この数１１８は、上記数１０９および数１１５で用いた拡大行列を用いると、次のような簡略化された表現が得られる。
【０１６９】
【数１１９】
2009015597.tif 000076
【０１７０】
ここでこの数１１９は、ｘＬ（ｋ）に関する陰的な関係式となっているので、これを陽的な形に変換する。数１１９の右辺第１項に現れるｘＬ（ｋ）に対して、数１１９自身（すなわち右辺全体）を代入し、上記数９９の関係式を用いて同様な手順を繰り返すと、次の式が得られる。
【０１７１】
【数１２０】
2009015597.tif 000077
【０１７２】
第１実施例では、全ての位置でＦＩおよびＦＯ条件を課すという、より強い制約を持たせるために、行列−Ｈ０（１）の対角成分がｅｎとなっている。そのため、全ての設備ｉの加工開始および加工終了時点で、順序制約を強制的に設定する場合には、第１実施例における数１０９の行列表現が適用される。
【０１７３】
この数１２０の式は、各設備での順序制約を強制的に設定しつつ、任意の二設備間の最大容量を考慮することのできる、拡張されたバックワード型のＭＰＬ状態空間表現である。これはＭＰＬ形式作成手段３１が、各設備ｉにおけるｋ番目のジョブの使用時間ｄｉ（ｋ）を取り込んで、数１０１の行列を算出し、各設備ｉの実行順序を規定する先行制約関係を取り込んで、個々の設備ｊにおける外部出力ｉおよび設備ｉにおける先行設備ｊの有無を判断することにより、数１０２および数１０５の各行列を算出し、設備ｉと下流設備ｊとの間に存在可能なジョブ数の最大値ｈを取り込んで、数１０３の行列を算出し、次にこれらの算出結果から、数１０９に示す拡大ベクトルおよび行列と、数１１５の行列を算出し、さらに数１１１を算出することで、数１２０の各要素を決定することができる。また、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で作成された数１２０から、ジョブの出力時刻ｙ（ｋ）を取り込んで、各設備の最遅加工開始時刻ｘＳＬ（ｋ）と、最遅加工終了時刻ｘＣＬ（ｋ）を求めることができる。
【０１７４】
次にスケジュール作成手段３２において最遅投入（入力）時刻［ｕＬ（ｋ）］ｉを算出する場合について説明する。図３は、外部入力ｉにかかわる制約関係を表した模式図である。Ｗｉは外部入力ｉに接続された後続設備の集合である。後続設備ｊ∈Ｗｉにおけるｋ番目のジョブの加工開始時刻は［ｘｓ（ｋ）］ｊであることから、当該ジョブの最遅投入時刻［ｕＬ（ｋ）］ｉは次のように表わされる。
【０１７５】
【数１２１】
2009015597.tif 000078
【０１７６】
［ｕＬ（ｋ）］ｉは任意のｉ（１≦ｉ≦ｍ）に対して成り立ち、上記数１１０と同じ状態変数を用いて表現すると、次の式になる。
【０１７７】
【数１２２】
2009015597.tif 000079
【０１７８】
以上のようにして、最遅時刻を表す状態方程式である数１２０と、出力方程式である数１２２とを導くことができる。
【０１７９】
ＭＰＬ形式作成手段３１は、各設備ｉの実行順序を規定する先行制約関係を取り込んで、個々の設備ｉにおける外部入力ｊの有無を判断することにより、数１０４の行列を算出し、次にその算出結果から、数１０９における行列−Ｂ０を算出して、数１２２の各要素を決定することができる。また、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で作成された数１２２から、数１０９における行列ｘ（ｋ）を取り込んで、最遅入力時刻ｕＬ（ｋ）を求めることができる。
【０１８０】
次に設備間のバッファ容量を指定する容量制約行列Ｈｏ（ｈ）の生成方法について説明する。状態空間表現を算出するためには、最大Ｑ個の行列を与える必要があるが、これを別々に指定することは煩雑である。そこで、バッファ容量に関する制約は、次のようなパラメータ行列で指定する。
【０１８１】
【数１２３】
2009015597.tif 000080
【０１８２】
この場合の下流設備ｊは、設備ｉ自身すなわちｉ＝ｊであってもよい。このとき次の関係式が成り立つ。
【０１８３】
【数１２４】
2009015597.tif 000081
【０１８４】
従って、行列Ｈｏ（ｈ）は全てのｈ（１≦ｈ≦Ｑ）に対して次のように定義することで生成できる。
【０１８５】
【数１２５】
2009015597.tif 000082
【０１８６】
なお、単一設備内での最大バッファ容量が１、隣接設備間で無限大とするシステムでは、パラメータ行列をＱ＝ｅｎとした時と等価である。さらにＱの定義より、ｉ＝ｊに対して、次に式が成り立つ。
【０１８７】
【数１２６】
2009015597.tif 000083
【０１８８】
以上設備間の移動時間が無視できる場合について説明したが、次に設備間の移動時間が無視できない場合について考察する。まず、移動時間を定数とし、ジョブ番号ｋに依存しない場合について説明する。このとき、移動途中にジョブの追い抜きは発生しないため、新たに順序制約を考慮する必要はない。移動時間は、上記数１０２のＦｏ（以下、これを隣接行列Ｆｏと呼ぶ）が［Ｆｏ］ｉｊ＝ｅとなる成分（ｉ，ｊ）について、ｅの代わりに設備ｊからｉまでの移動時間を設定することで考慮できる。
【０１８９】
一方、設備間での移動時間がジョブ番号ｋに依存する場合には、新たに順序制約を考える必要がある。この場合、隣接する二設備間には仮想的な設備（以下、これを仮想設備と呼ぶ）を設置する。図４に示すように、例えば設備ｂとａとの間の輸送時間が、ジョブ番号ｋに依存する場合、当該輸送時間をτａｂ（ｋ）とする。このとき、前後のジョブ同士で追い抜きが発生しないように、順序制約を考慮する必要がある。そのため、設備ｂとａとの間には、ｋ番目のジョブの占有時間をτａｂ（ｋ）（≡ｄＳ（ｋ））とするような仮想設備ｓを設置する。これに伴いＭＰＬ形式作成手段３１は、上記数１０２の隣接行列Ｆｏを修正し、修正した新たな隣接行列Ｆ^o(1)∈Ｄ（ｎ＋1）×（ｎ＋１）の要素を算出し決定する。なお、修正された隣接行列をＦ^oと表す
ここで、数１０２に示した元の隣接行列Ｆｏでは、次の関係式が成立している。
【０１９０】
【数１２７】
2009015597.tif 000084
【０１９１】
これに対して、仮想設備ｓの設置によりＭＰＬ形式作成手段３１において修正した新たな隣接行列Ｆ^o(1)∈Ｄ（ｎ＋1）×（ｎ＋１）では、次の関係が成立している。
【０１９２】
【数１２８】
2009015597.tif 000085
【０１９３】
但し、ｖａは次のように定義する。
【０１９４】
【数１２９】
2009015597.tif 000086
【０１９５】
また、ＭＰＬ形式作成手段３１は、上述した数１０１のパラメータ行列Ｐｋを修正し、次のような修正した新たなパラメータ行列Ｐ^ｋ(1)の要素を算出し決定する。
【０１９６】
【数１３０】
2009015597.tif 000087
【０１９７】
ＭＰＬ形式作成手段３１は、以下同様の手続きを輸送時間がジョブ番号
に依存するパス全てについて行うことで、新たな隣接行列を生成することができる。このようにして設置した仮想設備の数をｇとし、このときＭＰＬ形式作成手段３１は、他のシステム行列を次のように修正し、修正した新たな行列Ｈ^ｏ(ｈ)，Ｂ^ｏ，およびＣ^ｏの各要素を算出し決定する。
【０１９８】
【数１３１】
2009015597.tif 000088
【０１９９】
従って、設備間の移動時間が無視できない場合には、数１０１から数１０５のパラメータ行列に替えて、数１２８，数１３０，および数１３１のパラメータ行列を算出し、数１１０および数１２０の各要素を決定することができる。
【０２００】
また、スケジュール作成手段３２は、材料の投入（入力）時刻ｕ（ｋ）を取り込んで、ＭＰＬ形式作成手段３１で修正された数１１０から、各設備の最早加工開始時刻ｘＳＥ（ｋ）と、最早加工終了時刻ｘＣＥ（ｋ）を求めることができる。さらに、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で修正された数１２０から、ジョブの出力時刻ｙ（ｋ）を取り込んで、各設備の最遅加工開始時刻ｘＳＬ（ｋ）と、最遅加工終了時刻ｘＣＬ（ｋ）を求めることができる。
【０２０１】
このように本発明では、最早加工終了時刻ｘＣＥ（ｋ）や最遅加工開始時刻ｘＳＬ（ｋ）に関して閉じた方程式系を構成することができ、両者は現代制御理論における双対システムの関係に類似した形で表される。この方法の大きな利点の一つは、フォワード型とバックワード型の状態空間表現の状態方程式の両方で共通なシステム行列を用いることができ、計算時間が短縮できることである。これは特に大規模なシステムに対して，オンラインでのスケジューリングを行う時に有効である。
【０２０２】
ところで、本発明で扱うシステムは、バッファ容量がより柔軟に考慮できるようになっているので、設備内でジョブの追い越しが発生しないように、順序制約を課すことが必要となる。この結果、例えばフォワード型の状態方程式においては、最早加工終了時刻ｘＣＥ（ｋ）や最遅加工開始時刻ｘＳＬ（ｋ）のみで閉じた状態方程式系を構成することができず、両方を含んだ状態変数ｘＥ（ｋ）を用いることによって、拡大系での状態空間表現を行うことになる。これはバックワード型の状態空間表現でも同様であるが、拡大系の状態空間表現を用いることにより、数１０６，数１０７，数１２０，数１２２は、互いに双対な形で表現することができ、本質的に−Ｆｋ＊，−Ｈｏ（ｈ），−Ｂｏ，−Ｃｏの四つの表現行列だけですべて計算できる．このうち，ジョブ番号に依存するのは、−Ｆｋ＊のみで、特にEvent-varying型システムの場合、これをいかに効率的に計算するかが重要な関心事となる。拡大系の状態空間表現の構成により、システム行列の要素数が四倍に増加したが、数１１２でも言及したように、（ＰｋＦｏ）＊を求めれば、−Ｆｋ＊を構成する残りの三ブロックは、すべて簡単な代数演算で求めることができる。従って、本論文で導いた拡大系の状態空間表現は、特に最早・最遅時刻両方の計算が必要なオンラインスケジューリングに用いる際に有効であることがわかる。
【０２０３】
次に、再スケジュール生成手段３３の具体的な構成について説明する。ここで、再スケジュールについては、上述と同様に、フォワード型のＭＰＬ状態空間表現と、バックワード型のＭＰＬ状態空間表現とを用いたシステム構造があり、ここでは先ず始めにフォワード型のＭＰＬ状態空間表現における再スケジューリングの説明をした後、バックワード型のＭＰＬ状態空間表現における再スケジューリングの説明をする。
【０２０４】
上述のスケジュール生成手段３２は、外部からの材料の投入時刻ｕや、各設備ｉの加工時間ｄｉなど、システムの稼動が全て決められた通りに実行される状況を仮定しているが、あるジョブが稼動を開始した後に、加工の遅延や材料投入の遅れ等関連するシステムパラメータに変化が生じた場合、残りのプロセスのスケジュールを予測することは、特にオンラインスケジューリングの際に重要である。
【０２０５】
再スケジュール生成手段３３は、加工開始時刻，加工終了時刻，材料投入時刻などの変更情報を入力として、各設備ｉにおける最早開始時刻ｘＥＳおよび最早終了時刻ｘＥＣがどのように変化したのかを再度見直すフォワード型の再スケジュール機能を有している。
【０２０６】
ここではジョブの稼動開始後にシステムパラメータや、前のジョブの状態変数の値に何らかの原因で変化が生じたと仮定する。この場合、加工時間と、加工開始時刻と、加工終了時刻と、材料投入時刻とについてそれぞれ影響を及ぼすことから、これらのシステム行列Ｐ（ｋ）や、材料の投入時刻ｕ、加工開始時刻および加工終了時刻の両時刻ｘ（ｋ）の変化後における状態を、それぞれ記号の上または横にシンボル〜をつけて次の式のように表わす。
【０２０７】
【数１３２】
2009015597.tif 000089
【０２０８】
ジョブ番号ｋのジョブの状態変数の第ｉ成分が、次のように変化したものとする。
【０２０９】
【数１３３】
2009015597.tif 000090
【０２１０】
ここで、変化する成分ｉは一つでなく、複数存在してもよい。値が変化せず、再計算が必要な成分にはεを設定する。上添え字（＋０）は、逐次的に計算を行うための初期値であることを表わす。ところで、上記数１０６および数１０７は、最早時刻の計算結果がシステムの下流方向に伝播していく様子を定式化したものである。従って、上記数１０８にならい、一ステップ下流における最早時刻は、次の式により表せる。
【０２１１】
【数１３４】
2009015597.tif 000091
【０２１２】
但し、Ｆ〜ｋは次のように表せる。
【０２１３】
【数１３５】
2009015597.tif 000092
【０２１４】
数１３４に示した式は、簡素化のため、成分番号の表記を省略しているが、変化が発生した設備の一ステップ下流の成分のみについて成り立つ。以下同様にして、最早時刻を下流方向に逐次的に求めると、ｊステップ下流では次の関係式が成立する。
【０２１５】
【数１３６】
2009015597.tif 000093
【０２１６】
これを（１≦ｊ≦２・ｓ）に対して計算し、次の自明な関係式と共に辺々加算演算子（丸印内に＋）を施す。
【０２１７】
【数１３７】
2009015597.tif 000094
【０２１８】
これにより、次の関係式が得られる。
【０２１９】
【数１３８】
2009015597.tif 000095
【０２２０】
この数１３８は、ジョブｋの稼動開始後に状態変化が発生した時にも適用できる、一般化されたフォワード型のＭＰＬ状態空間表現の状態方程式である。なお、Ｆ〜ｋ＊は、数１０９の―Ｆｋが数１３５のＦ〜ｋと置き換わり、数１１１の―Ｆｋ＊の算出方法と同様にして求められる。全ての成分で再計算が必要な場合には次の関係式が成り立つので、数１３８は数１１０に一致する。
【０２２１】
【数１３９】
2009015597.tif 000096
【０２２２】
特殊な場合として、途中設備において初期スケジュールよりも遅れが発生した場合について考える。このとき、状態変数の初期値としては、遅れが発生した成分には最新の値を設定し、遅れが発生していない成分には、初期の計算結果をそのまま設定すると、次の式が成り立つ。
【０２２３】
【数１４０】
2009015597.tif 000097
【０２２４】
従って、数１３８は次のように簡略化される。
【０２２５】
【数１４１】
2009015597.tif 000098
【０２２６】
かくして、再スケジュール生成手段３３は、初期スケジュールからの遅れのみを仮定する場合、数１４１に示すように、最新の値を設定した状態変数ｘ〜（＋０）（ｋ）に対して、次の数１４２を施すだけで再スケジューリング結果を算出することができる。
【０２２７】
【数１４２】
2009015597.tif 000099
【０２２８】
これは数１３８と比較して簡潔な計算方法であり、リアルタイムでの進捗管理等、オンラインスケジューリングに適した一つの簡便法を提供することができる。
【０２２９】
このように、本実施例における再スケジュール生成手段３３は、変動した材料投入時刻，ある設備における加工時間，またはある設備における加工開始時刻および加工終了時刻が、変動パラメータとして入力されたのを受けて、数１４１に基づいて、更新後の最早時刻ｘ〜Ｅを算出する。これによって、例えばシステムの稼動中にスケジュール生成処理に影響を及ぼしうる変動が発生した場合でも、各設備ｉ毎における最早開始時刻ｘ〜ＥＳや最早終了時刻ｘ〜ＥＣの算出を適確に抽出することができる。
【０２３０】
なお、変動パラメータの入力は、例えばオペレータが入力装置１５を介して入力するのではなく、各設備ｉ毎に製品の移動状況を感知するセンサを備え、このセンサから得られた感知情報と、内蔵する計時手段とにより、人手を介さず自動的に入力できる構成としてもよい。
【０２３１】
次に、バックワード型のＭＰＬ状態空間表現における再スケジューリングの説明をする。あるジョブが稼動を開始した後に、ステムパラメータや状態変数の値が、次のように変化するものとする。
【０２３２】
【数１４３】
2009015597.tif 000100
【０２３３】
また、ジョブ番号ｋのジョブにおいて、状態変数の第ｉ成分が、次のように変化するものとする。
【０２３４】
【数１４４】
2009015597.tif 000101
【０２３５】
なお、ここで該当する成分ｉは複数存在してもよい。また、値が変化せずに、再計算が必要な成分には、転置行列を表わす添え字Ｔを設定する。上添え字（−０）は、逐次的に計算を行うための初期値であることを表わす。数１１６および数１１７は、最遅時刻の計算結果がシステムの上流方向に伝播していく様子を定式化したものである。数１１９にならい、一ステップ上流における最遅時刻は、次のように表わせる。
【０２３６】
【数１４５】
2009015597.tif 000102
【０２３７】
但し、Ｆ〜ｋは数１３５と同じである。この数１４５は、表記の簡素化のため成分番号を省略しているが、変化が発生した設備の一ステップ上流の成分のみについて成り立つものである。以下同様にして、最遅時刻を上流方向に逐次的に計算すると、ｊステップ上流では次の式が成立する。
【０２３８】
【数１４６】
2009015597.tif 000103
【０２３９】
この数１４６を（１≦ｊ≦２・ｓ）に対して計算し、次の自明な関係式と共に辺々∧を施す。
【０２４０】
【数１４７】
2009015597.tif 000104
【０２４１】
これにより次の式が得られる。
【０２４２】
【数１４８】
2009015597.tif 000105
【０２４３】
この数１４８は、ジョブｋの稼動開始後に状態が変化した時にも適用可能な、一般化されたバックワード型のＭＰＬ状態空間表現の状態方程式である。全ての成分で再計算する場合、次の式が成り立つので、数１４８は数１２０と一致する。
【０２４４】
【数１４９】
2009015597.tif 000106
【０２４５】
また、特別な場合として、途中設備において初期スケジュールよりも前倒しが発生した場合について考える。状態変数の初期値としては、前倒しが発生した成分には最新の値を設定し、前倒しが発生してない成分には、初期の計算結果をそのまま設定する。このとき、次の関係が成り立つ。
【０２４６】
【数１５０】
2009015597.tif 000107
【０２４７】
従って、数１４８は次のように簡略化できる。
【０２４８】
【数１５１】
2009015597.tif 000108
【０２４９】
かくして、再スケジュール生成手段３３は、初期スケジュールからの前倒しのみを仮定する場合、数１４１に示すように、最新の値を設定した状態変数ｘ〜（−０）（ｋ）に対して、次の数１５２を施すだけで再スケジューリング結果を算出することができる
【０２５０】
【数１５２】
2009015597.tif 000109
【０２５１】
これは数１４８と比較して簡潔な計算方法であり、リアルタイムでの進捗管理等、オンラインスケジューリングに適した一つの簡便法を提供することができる。このように、本実施例における再スケジュール生成手段３３は、変動した材料投入時刻，ある設備における加工時間，またはある設備における加工開始時刻および加工終了時刻が、変動パラメータとして入力されたのを受けて、数１５１に基づいて、更新後の最遅時刻ｘ〜Ｌを算出する。これによって、例えばシステムの稼動中にスケジュール生成処理に影響を及ぼしうる変動が発生した場合でも、各設備ｉ毎における最遅開始時刻ｘ〜ＬＳや最遅終了時刻ｘ〜ＬＣの算出を適確に抽出することができる。
【０２５２】
かくして、再スケジュール生成手段３３は、このようにして求められたフォワード型・バックワード型の両方についての、容量制約を考慮したEvent-varying型の再スケジューリング用の状態空間表現を用いて、再スケジューリングを行うことができる。
【０２５３】
次に、第１実施例におけるスケジュール作成装置１の動作例を説明し、この実施例で提示したＭＰＬ状態表現空間の妥当性を確認する。図５は、ある二つの入力，一つの出力，四つの設備Ｆ１〜Ｆ４を有する生産システムである。なお、各設備Ｆ１〜Ｆ４の上側に示した()は、ジョブの加工時間を表わし、各設備Ｆ１〜Ｆ４や設備Ｆ２および設備Ｆ３間、設備Ｆ１および設備Ｆ４間に示した［］は、バッファ容量を表わす。すなわち、例えば設備Ｆ２および設備Ｆ３では、図５中に［２］と表示されていることから、同時に二つまでのジョブを処理できることを表わしている。このとき、関連する表現行列は、次のように表わされる。
【０２５４】
【数１５３】
2009015597.tif 000110
【０２５５】
設備Ｆ１から設備Ｆ３への運搬時間は有限であり、次の関係式で示すように、ジョブ番号に依存して周期的に変化するものとする。
【０２５６】
【数１５４】
2009015597.tif 000111
【０２５７】
上述したように、輸送時間を考慮する場合、設備Ｆ１と設備Ｆ３との間に新たに仮想的な設備（仮想設備）Ｆ５を設置し、関連する表現行列を修正する。加工する部品数をｋ＝１６とし、時刻ｔ＝０において全ての材料が用意されているものとする。すなわち、ｕ（ｋ）＝［０ ０］Ｔ（１≦ｋ≦１６）である。さらに初期状態は空とし、ｘ（０）＝ε１０１とする。
【０２５８】
このとき、設備Ｆ１〜Ｆ４における最早加工開始時刻［―ｘＥＳ（ｋ）］ｉ（１≦ｉ≦４，１≦ｋ≦１６）を表したものが、図６である。図６において、横軸はジョブ番号ｋを表わす。システム全体で見たときは、最も処理能力の高い設備は設備Ｆ１で、最も低い設備は設備Ｆ４である。設備Ｆ１では、１≦ｋ≦６までは、設備Ｆ１自身の加工能力に依存しているが、ｋ≧７では、設備Ｆ４との間に課されたバッファ容量の制約により、設備Ｆ４での加工終了時刻に依存するスケジュールとなっている。設備Ｆ２では同時に２つまでのジョブを処理できるが、１≦ｋ≦４では設備Ｆ２自身の処理能力に依存して加工を行っている。ところがｋ≧５では、設備Ｆ３との間に課された容量制約の影響を受け、設備Ｆ３の処理能力に依存している。設備Ｆ３は同時に２つまでのジョブを処理できるため、実質的なスループットは設備Ｆ４より高い。従って、ｋが大きくなり、定常状態に近づいてくると、全設備のスループットは、最も処理能力の低い設備Ｆ４に近づいていくことが分かる。
【０２５９】
次に、再スケジューリングについて検討する。いま、設備Ｆ３でジョブｋ＝３の処理中に設備が故障し、加工終了時刻が１０だけ遅延したものとする。数１４１に基づいて、ｋ＝３の再スケジューリングを行い、ｋ≧４については、数１１０を用いて再計算を行った結果を図７に示す。この場合、まずｋ≧３において後続設備Ｆ４が影響を受け、次いで設備Ｆ３との間に容量制約が課された設備Ｆ２がｋ≧７で影響を受けている。さらに、設備Ｆ４との間に容量制約が課された設備Ｆ１が、ｋ≧９で影響を受けている。ｋ＝１０での各設備Ｆ１〜Ｆ４での加工開始時刻の相対的な関係は、図６におけるｋ＝２のものと類似しており、この後の各設備Ｆ１〜Ｆ４におけるスループットは、設備Ｆ４に従属していくものと想定される。
【０２６０】
さらに、フォワード型とバックワード型両方の状態空間表現を用いて、オンラインでの状態把握を試みる。図８は、出力時刻を図６の場合と同一に与えたときの、各設備Ｆ１〜Ｆ４における余裕時間を示したものである。ここでの余裕時間は，最遅開始時刻と最早開始時刻との差で与え、負の値は余裕時間がゼロであることを表わす。最下流に位置する設備Ｆ４では、ｋ＝３における遅延の影響を直ちに受けているが、上流に位置する設備Ｆ１〜Ｆ３では、遅延の影響を受けるのは、いくつかのジョブを処理した後となる。ジョブ番号が進むにつれて、設備Ｆ１〜Ｆ３では再び正の余裕時間を持つようになるが、同時に二つのジョブが処理できる設備Ｆ２が最も大きな余裕時間を持つようになる。設備Ｆ１における実質的なスループットは、設備Ｆ２と同じであるが、同時に一つのジョブしか処理できないため、設備Ｆ３と同程度の余裕時間しか持てないことがわかる。
【０２６１】
以上の構成によれば、一乃至複数の入力，一乃至複数の出力，および複数の設備を組み合わせてなり、前記入力に投入した加工対象を前記複数の設備で処理し、その加工結果を出力に送り出す離散事象システムに関し、前記加工対象を受け渡す各前記設備の実行順序を規定する先行制約関係，および各前記設備における実行時間が入力装置１５で入力パラメータとして取り込まれると、この入力装置１５で取り込んだ入力パラメータをＲＡＭ１２で記憶し、さらに前記離散事象システムの状態を表現するために、前記ＲＡＭ１２から読み出した入力パラメータに基づいて、max-plus代数上で線形なＭＰＬ形式にＣＰＵ１１が変換するスケジュール作成装置１において、前記max-plus代数上で線形なＭＰＬ形式を導出できるようにするために、各前記設備ｉにおけるｋ番目の処理設備の実行時間をｄｉ（ｋ）としたときに、前記ＲＡＭ１２から読み出した入力パラメータに基づいて、上述した数１０１〜数１０４および数１０９で定義されたシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），Ｂｏ（但し、［Ｘ］ijは行列Ｘにおけるｉ行ｊ列の要素である）の各要素をそれぞれＣＰＵ１１で決定し、前記行列Ｆｏを用いて、上述した数１１１により行列―Ｆｋ＊（但し、ｓは、１≦ｓ≦ｎ）をＣＰＵ１１で算出するようにした。
【０２６２】
従って、入力パラメータとして、各設備の実行時間と設備間の先行制約関係の各情報が予め記憶されていれば、そこから独自のシステム構造を表現する行列Ｐｋ，Ｆｏ，Ｈｏ（ｈ），およびＢｏについて、その各要素を決定し、さらにここで決定した行列Ｆｏから行列―Ｆｏ＊を算出して、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ｐｋ，―Ｆｏ＊，Ｈｏ（ｈ），およびＢｏを簡単に取得することができる。
【０２６３】
これにより、既存のＭＰＬ状態空間表現を拡張して、単一設備内だけでなく、任意の領域内における処理対象の最大容量を、ＭＰＬ状態空間表現の中で容量制約として考慮することが可能なスケジュール作成方法，スケジュール作成装置１，およびコンピュータプログラム２０を提供できる。
【０２６４】
また、容量制約および順序制約を有するシステムのスケジュール作成をコンピュータで実現する上で、より少ないメモリ消費で、与えられたシステムを、容量制約および順序制約を考慮したＭＰＬシステムとして表現できる形式に簡単に導出することが可能になる。
【０２６５】
また、ｋ番目の設備処理に関して、各設備での加工開始時刻および加工終了時刻を表わす行列をｘ（ｋ）とし、材料の投入時刻をｕ（ｋ）としたときに、行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，および―Ｆｋ＊と、ＣＰＵ１１に取り込まれる行列ｘ（ｋ）と、投入時刻ｕ（ｋ）とを利用して、上述した数１１０に基づき設備の最早開始時刻および最早終了時刻を表わす行列ｘＥ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）をＣＰＵ１１で算出するようにした。
【０２６６】
これにより、加工開始時刻および加工終了時刻を表わす行列ｘ（ｋ）と投入時刻ｕ（ｋ）が取り込まれれば、先に算出した行列Ｐｋ，―Ｆｏ＊，Ｈｏ（ｈ），およびＢｏを利用して、行列ｘＥ（ｋ）を簡単に算出することができ、かくして行列ｘＥ（ｋ）によって、システムを構成する全ての設備での最早開始時刻および最早終了時刻を把握することができる。
【０２６７】
さらに、ＲＡＭ１２から読み出した入力パラメータに基づいて、上述した数１０５によりシステム構造を表現する行列ＣＯの要素をさらにＣＰＵ１１で決定し、ｋ番目の設備処理に関して、各設備での加工開始時刻および加工終了時刻を表わす行列をｘ（ｋ）とし、投入時刻をｕ（ｋ）、出力時刻をｙ（ｋ）としたときに、行列Ｐｋ，Ｈｏ（ｈ），Ｂｏ，―Ｆｋ＊，ＣＯと、ＣＰＵ１１に取り込まれる行列ｘ（ｋ）と、投入時刻ｕ（ｋ）と、出力時刻ｙ（ｋ）とを利用して、上述した数１２０に基づき設備の最遅開始時刻および最遅終了時刻を表わす行列ｘＬ（ｋ）（但し、Ｑは前記離散事象システムに課される容量制約の容量の最大値）をＣＰＵ１１で算出するようにした。
【０２６８】
これにより、加工開始時刻および加工終了時刻を表わす行列ｘ（ｋ）と投入時刻ｕ（ｋ）と出力時刻ｙ（ｋ）とが取り込まれれば、先に算出した行列Ｐｋ，―Ｆｏ＊，Ｈｏ（ｈ），Ｂｏ，およびＣｏを利用して、行列ｘＬ（ｋ）を簡単に算出することができ、かくして行列ｘＬ（ｋ）によって、システムを構成する全ての設備での最遅開始時刻および最遅終了時刻を適確に且つ効率的に把握することができる。
【０２６９】
さらに、ＣＰＵ１１が、前記離散事象システムにおける設備の処理時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に前記行列Ｆｋ＊の変更後の行列Ｆ〜ｋ＊を計算してＲＡＭ１２に記憶し、ｋ番目の設備処理に関して、各設備での加工終了時刻をｘ（＋０）（ｋ）としたときに、前記離散事象システムにおける加工終了時刻ｘ（＋０）（ｋ）（ここで（＋０）は逐次的に計算を行うための初期値であることを表わす）の変更情報を取得すると、これを変更後の加工終了時刻ｘ〜（＋０）（ｋ）としてＲＡＭ１２に記憶し、当該ＲＡＭ１２から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（＋０）（ｋ）を用いて、上述した数１４１に基づき変更後の設備の最早開始時刻および最早終了時刻を表わす行列ｘ〜Ｅ（ｋ）を前記演算部で算出するようにした。
【０２７０】
これにより、システムの稼動開始後に何らかの原因で、その投入時刻や加工時間、加工終了時刻が変化した場合でも、算出される行列ｘ〜Ｅに基づいて、全ての設備における変更後の最早開始時刻および最早終了時刻を適確に且つ効率的に把握することができる。
【０２７１】
さらに、ＣＰＵ１１が、前記離散事象システムにおける設備の加工時間の変更情報を取得すると、この加工時間の変更情報に基づいて、前記行列Ｐｋ，Ｆｏ，Ｆｋ＊の各要素を再計算し、該各要素を基に求めた変更後の行列Ｆ〜ｋ＊をＲＡＭ１２に記憶し、ｋ番目の設備処理に関して、各設備での加工開始時刻をｘ（−０）（ｋ）としたときに、前記離散事象システムにおける加工開始時刻ｘ（−０）（ｋ）の変更情報を取得すると、これを変更後の加工開始時刻ｘ〜（−０）（ｋ）としてＲＡＭ１２に記憶し、当該ＲＡＭ１２から読み出した前記行列Ｆ〜ｋ＊，ｘ〜（−０）（ｋ）を用いて、上述した数１５１に基づき変更後の設備の最遅開始時刻および最遅終了時刻を表わす行列ｘ〜Ｌ（ｋ）（但し、Ｔは転置行列）をＣＰＵ１１で算出するようにした。
【０２７２】
これにより、システムの稼動開始後に何らかの原因で、その投入時刻や加工時間、加工開始時刻が変化した場合でも、算出される行列ｘ〜Ｌに基づいて、全ての設備における変更後の最遅開始時刻および最遅終了時刻を適確に且つ効率的に把握することができる。
【実施例２】
【０２７３】
次に、本発明の第２実施例におけるスケジュール作成方法と、それを実現するスケジュール作成装置１について説明する。なお、上記第１実施例と同一部分には同一符号を付し、その共通する箇所の説明は重複を避けるため極力省略する。
【０２７４】
スケジュール作成装置１の内部構成は、図１で示すものと共通している。但し、コンピュータプログラム２０に含まれるＭＰＬ形式作成手順，スケジュール作成手順，および再スケジュール作成手順と、こうした手順を各々処理実行するＭＰＬ形式作成手段３１，スケジュール作成手段３２，および再スケジュール作成手段３３の機能構成は、各実施例で異なっている。
【０２７５】
この実施例では、既存のＭＰＬ状態空間表現を拡張し、容量制約のみならず順序制約をも考慮することのできる表現形式を、ＭＰＬ形式作成手段３１が処理実行するＭＰＬ形式作成手順で作成できるようになっている。ここでは、スケジュール作成装置１の検討対象となるシステム構造について説明し、次いで第１実施例と同様に好適なフォワード型およびバックワード型の状態空間表現を送出する。
【０２７６】
まず、本実施例で取り扱うシステム構造を説明すると、検索対象となるシステムは第１実施例で説明したFolk-Join型構造を有するものとし、処理対象を受け渡す各設備の実行順序（加工順序）には、次のような制約関係があると仮定する。
・設備数はｎで、外部入力数はｍ，外部出力数はｐとする。
・各ジョブ（バッチ）共に全ての設備を通過し、かつ加工回数は一回である。すなわち、一回加工したら、その設備に再度戻ることはない非サイクリック構造である。
・先行設備を有する設備は、それらの先行設備の加工が終了しないと、加工を開始できない。
・外部入力のある設備は、処理対象となる必要材料が投入されるまで、その加工を開始できない。
・容量制約が課せられた設備は、当該領域内におけるジョブ数が、容量制約で指定された値以下になるまで加工を開始できない。
・順序制約は、容量制約が課せられた設備と同一の設備に課すことができる。
【０２７７】
つまり第１実施例では、同一の設備内でジョブの追い越しが発生しないように、全ての設備において、加工の開始と終了がジョブ番号の順番に行なわれる制約条件を課していたが、第２実施例ではそうした制約条件に代わり、容量制約が課せられた設備に関し、その設備でジョブの追い越しを可能にするか否かを選択できる別な制約条件を課している。したがって、第２引用例で検討対象とするシステムは、容量制約が課せられた設備に対し、必要に応じて順序制約を課すことができるという点で、第１実施例よりもより柔軟性を有する。
【０２７８】
なお、ここでも簡素化のために、設備間の輸送時間は無視できるものとして扱う。また、以下の説明で、設備ｉ（１≦ｉ≦ｎ）に対して、ｋ番目のジョブの使用時間をｄｉ（ｋ）とし、またその設備ｉでの加工開始時刻と加工終了時刻を、［ｘ−（ｋ）］ｉ，［ｘ＋（ｋ）］ｉなる状態変数としてそれぞれ割り付ける（第１実施例における添え字の「ｓ」，「ｃ」は、添え字「−」，「＋」と同じ意味である）。それ以外の記号や添え字は、第１実施例と共通している。
【０２７９】
図９は、設備ｉと、それに関連する外部入力，先行設備，後続設備との関係を表している。同図において、Ｒｉ，Ｍｉ，Ｈｉｈは、それぞれ先行設備番号の集合，外部入力番号の集合，最大容量がｈである下流設備番号の集合を意味する。
【０２８０】
ここで、設備ｉ（１≦ｉ≦ｎ）の最早加工終了時刻［ｘ＋Ｅ（ｋ）］ｉについて考える。ｋ番目のジョブは、下記の両方の条件を満たした時刻以降に加工が終了する。
・当該設備ｉにおける加工開始時刻［ｘ−Ｅ（ｋ）］ｉから、そのジョブの使用時間ｄｉ（ｋ）だけ経過した時刻
・順序制約が課される場合は、前のジョブ（ｋ−１）における加工終了時刻［ｘ＋（ｋ−１）］ｉ
上記両方の条件が揃うと直ちに加工を終了するものとすれば、設備ｉにおけるｋ番目のジョブの最早終了時刻［ｘ＋Ｅ（ｋ）］ｉは、max-plus代数系でこれら２つの条件を加算したものとなり、次のように表わせる。
【０２８１】
【数１５５】
2009015597.tif 000112
【０２８２】
ここでは、ＦＩ（First Input）およびＦＯ（First Output）条件を適切に考慮して、加工終了時点で順序制約を課すか否かをmax-plus代数で表現するために、次の式のパラメータｇｉ＋を導入した点が注目される。
【０２８３】
【数１５６】
2009015597.tif 000113
【０２８４】
次に、設備ｉ（１≦ｉ≦ｎ）の最早加工開始時刻［ｘ−Ｅ（ｋ）］ｉについて考える。設備ｉにおけるｋ番目のジョブは、下記の全ての条件を満たした時刻以降に加工が開始できる。
・先行設備ｊ∈Ｒｉにおける加工終了時刻［ｘ＋（ｋ）］ｊ
・外部入力ｊ∈Ｍｉにおける材料投入時刻［ｕ（ｋ）］ｊ
・容量制約が課された下流設備ｊ∈Ｈｉｈにおける加工終了時刻［ｘ＋（ｋ−ｈ）］ｉ
・順序制約が課される場合は，前のジョブ（ｋ−１）における加工開始時刻［ｘ−（ｋ−１）］ｉ
上記の条件が全て揃った時に、直ちに加工を開始するものとすれば、ｋ番目のジョブにおける最早開始時刻［ｘ−Ｅ（ｋ）］ｉは、次のように表される。
【０２８５】
【数１５７】
2009015597.tif 000114
【０２８６】
ここでＱは、システムに課される容量制約の容量の最大値であり、ｇｉ−は加工開始時点に関する順序制約の有無を表すパラメータで、上記パラメータｇｉ＋と同様に定義する。すなわち、パラメータｇｉ−は次の数１５８となる。
【０２８７】
【数１５８】
2009015597.tif 000115
【０２８８】
さらに、第１実施例と同様なパラメータ行列を次のように導入する。
【０２８９】
【数１５９】
2009015597.tif 000116
【０２９０】
【数１６０】
2009015597.tif 000117
【０２９１】
【数１６１】
2009015597.tif 000118
【０２９２】
【数１６２】
2009015597.tif 000119
【０２９３】
こうしたパラメータ行列によって、この実施例で仮定する容量制約と順序制約の関係は、加工開始時点と加工終了時点でそれぞれ次のように表現できる。
【０２９４】
【数１６３】
2009015597.tif 000120
【０２９５】
さらに、順序制約に関する表現形式を簡素化するために、次のようなパラメータ行列を考える。
【０２９６】
【数１６４】
2009015597.tif 000121
【０２９７】
すると、上記数１５５と数１５７は、それぞれ次の式のように行列表現することができる。
【０２９８】
【数１６５】
2009015597.tif 000122
【０２９９】
【数１６６】
2009015597.tif 000123
【０３００】
上記数１６５と数１６６は、任意の設備ｉ（１≦ｉ≦ｎ）に対して成り立つことに留意し、これらをまとめて行列表現することを考える。そのために、次のような拡大ベクトルおよび行列を導入する。
【０３０１】
【数１６７】
2009015597.tif 000124
【０３０２】
この数１６７と、第１実施例における数１０９とを比較すると、行列−Ｈ０（１）の対角成分だけが異なっていることがわかる。つまり本実施例では、任意の位置にＦＩおよびＦＯ条件を適切に設定できるように、行列−Ｈ０（１）の対角成分に順序制約の有無を選択できるパラメータＧ０＋，Ｇ０−が存在するが、第１実施例では、全ての位置でＦＩおよびＦＯ条件を課すという、より強い制約を持たせるために、行列−Ｈ０（１）の対角成分がｅｎとなっている。そのため、全ての設備ｉの加工開始および加工終了時点で、順序制約を強制的に設定する場合には、第１実施例における数１０９の行列表現を適用すればよく、また容量制約が課せられる箇所のみに、順序制約を選択的に設定する場合には、本実施例における数１６７の行列表現を適用すればよい。この数１６７を用いると、上記数１６５および数１６６は、次のように簡略化して表現できる。
【０３０３】
【数１６８】
2009015597.tif 000125
【０３０４】
上記数１６８は、第１実施例の数１０８と同じものである。数１６８は、左辺の−ｘＥ（ｋ）に関する陰的な表現になっているので、これを陽的な表現に変換する。先に示したシステム構造の前提条件より、行列Ｂｏと共にシステムの構造（実行順序関係）のみに依存する行列Ｆｏは、非サイクリック構造の隣接行列を表していることから、次の式を満たす定数ｓ（１≦ｓ≦ｎ）が存在することが知られている。
【０３０５】
【数１６９】
2009015597.tif 000126
【０３０６】
また、ｋ番目のジョブの加工時間ｄｉ（ｋ）のみに依存する行列Ｐｋは対角行列であるので、ＰｋＦ０およびＦ０Ｐｋは、それぞれＦ０の各行および列に非負値の重み付けを行った行列となる。従って、次の式が成立する。
【０３０７】
【数１７０】
2009015597.tif 000127
【０３０８】
ここでは、次の式のように、Kleene star operatorと呼ばれる、べき乗の和を表す演算子を利用している。
【０３０９】
【数１７１】
2009015597.tif 000128
【０３１０】
一方、前記数１６７で提示した行列−Ｆｋについては、定数ｌ（１≦ｌ≦ｓ）に対して次の式が成立する。
【０３１１】
【数１７２】
2009015597.tif 000129
【０３１２】
従って、−Ｆｋ＊は次のように求められる。
【０３１３】
【数１７３】
2009015597.tif 000130
【０３１４】
上記の式を用いて、数１６８を陽的な形式にすると、次の通りに表わすことができる。
【０３１５】
【数１７４】
2009015597.tif 000131
【０３１６】
この数１７４の式は、任意の二設備間の最大容量と、各設備での順序制約を考慮することのできる、拡張されたフォワード型のＭＰＬ状態空間表現である。これはＭＰＬ形式作成手段３１が、各設備ｉにおけるｋ番目のジョブの使用時間ｄｉ（ｋ）を取り込んで、数１５９の行列を算出し、各設備ｉの実行順序を規定する先行制約関係を取り込んで、個々の設備ｉにおける外部入力ｊおよび先行設備ｊの有無を判断することにより、数１６０および数１６１の各行列を算出し、設備ｉと下流設備ｊとの間に存在可能なジョブ数の最大値ｈを取り込んで、数１６２の行列を算出し、さらに設備ｉに関し、順序制約があるか否かの情報を取り込んで、数１６４の行列を算出し、次にこれらの算出結果から、数１６７に示す拡大ベクトルおよび行列を算出し、さらに数１７１に基づき数１７３を算出することで、数１７４の各要素を決定することができる。また、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で作成された数１７４から、材料の投入時刻ｕ（ｋ）を取り込んで、各設備の最早加工開始時刻ｘ−Ｅ（ｋ）と、最早加工終了時刻ｘ＋Ｅ（ｋ）を求めることができる。
【０３１７】
なお前述したように、この実施例で仮定した順序制約よりも強い、全ての設備での加工開始および加工終了時点で順序制約を課す場合には、前記数１６７における行列−Ｈ０（１）の対角成分として、次の式を与えればよい。
【０３１８】
【数１７５】
2009015597.tif 000132
【０３１９】
上記数１７３の式で、行列の対角成分である（Ｆ０Ｐｋ）＊と（ＰｋＦ０）＊は、それぞれ独立に計算する必要があるが、両者は通常の代数系において、簡潔な関係で結ばれている。ここでは、次の式に着目する。
【０３２０】
【数１７６】
2009015597.tif 000133
【０３２１】
上記数１７６の式で、左辺の第（ｉ，ｊ）成分は、次の式のようになる。
【０３２２】
【数１７７】
2009015597.tif 000134
【０３２３】
また、上記数１７６の式で、その右辺に対しても同様の考察を行なうと、次のような関係が得られる。
【０３２４】
【数１７８】
2009015597.tif 000135
【０３２５】
従って、（Ｆ０Ｐｋ）＊か（ＰｋＦ０）＊のいずれか一方が求められれば、他方はｎ×ｎ回の少ない計算量で求めることができる。これは、特に問題のサイズが大きいときに有利である。
【０３２６】
最早出力時刻ｙＥ（ｋ）を求める出力方程式については、第１実施例と同様であり、設備と外部出力との間には容量制約や順序制約は課されないものとする。従って、当該出力方程式は、次のようになる。
【０３２７】
【数１７９】
2009015597.tif 000136
【０３２８】
ここで、−Ｃｏは、次の数１８０の行列で表される。
【０３２９】
【数１８０】
2009015597.tif 000137
【０３３０】
また、数１８０における行列Ｃｏは、第１実施例でも説明したとおり、次のように表わせる。
【０３３１】
【数１８１】
2009015597.tif 000138
【０３３２】
ＭＰＬ形式作成手段３１は、各設備ｊの実行順序を規定する先行制約関係を取り込んで、個々の設備ｊにおける外部出力ｉの有無を判断することにより、数１８１の行列を算出し、次にその算出結果から、数１７９の各要素を決定することができる。また、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で作成された数１７９から、数１６７における行列−ｘ（ｋ）を取り込んで、最早出力時刻ｙＥ（ｋ）を求めることができる。
【０３３３】
なお、設備間の輸送時間が無視できない場合の考慮は、第１実施例で説明したとおりであり、ここではその説明を省略する。
【０３３４】
次に、設備ｉの最遅加工開始時刻ｘｓＬ（ｋ）と最遅加工終了時刻ｘＣＬ（ｋ）を求めるバックワード型の状態空間表現について説明する。容量制約と順序制約を考慮したバックワード型の状態空間表現は、第１実施例で詳述しているので、ここではその導出について再度説明はしない。第２実施例では、前記数１５６のパラメータおよびこのパラメータから求められる数１６４のパラメータ行列から、前記第１実施例の数１１６と数１１７を、フォワード型の状態空間表現を導出したのと同じ手法で、次のように表わすことが可能である。
【０３３５】
【数１８２】
2009015597.tif 000139
【０３３６】
【数１８３】
2009015597.tif 000140
【０３３７】
ここで、添え字Ｔは転置行列を表わす。上記数１８２および数１８３は、任意の設備ｉ（１≦ｉ≦ｎ）に対して成り立つことから、これらの式をまとめて行列表現すると、次の式のように表わすことができる。
【０３３８】
【数１８４】
2009015597.tif 000141
【０３３９】
さらに、前記数１６７と数１８０を用いた拡大行列を用いると、第１実施例の数１１９と同様の次の簡略化された表現が得られる。
【０３４０】
【数１８５】
2009015597.tif 000142
【０３４１】
上記数１８５を陽的な形に変換すると、次のようなＭＰＬ状態空間表現の式が得られる。
【０３４２】
【数１８６】
2009015597.tif 000143
【０３４３】
つまり、この第２実施例におけるバックワード型のＭＰＬ状態空間表現の状態方程式では、任意の位置にＦＩおよびＦＯ条件を適切に設定できるように、行列−Ｈ０（１）の対角成分に順序制約の有無を選択できるパラメータＧ０＋，Ｇ０−が存在するが、第１実施例では、全ての位置でＦＩおよびＦＯ条件を課すという、より強い制約を持たせるために、行列−Ｈ０（１）の対角成分がｅｎとなっている。そのため、全ての設備ｉの加工開始および加工終了時点で、順序制約を強制的に設定する場合には、第１実施例における数１０９の行列表現を適用すればよく、また容量制約が課せられる箇所のみに、順序制約を選択的に設定する場合には、本実施例における数１６７の行列表現を適用すればよい。
【０３４４】
この数１８６の式は、任意の二設備間の最大容量と、各設備での順序制約を考慮することのできる、拡張されたバックワード型のＭＰＬ状態空間表現である。これはＭＰＬ形式作成手段３１が、各設備ｉにおけるｋ番目のジョブの使用時間ｄｉ（ｋ）を取り込んで、数１５９の行列を算出し、各設備ｉの実行順序を規定する先行制約関係を取り込んで、個々の設備ｊにおける外部出力ｉおよび設備ｉにおける先行設備ｊの有無を判断することにより、数１８１および数１６１の各行列を算出し、設備ｉと下流設備ｊとの間に存在可能なジョブ数の最大値ｈを取り込んで、数１６２の行列を算出し、さらに設備ｉに関し、順序制約があるか否かの情報を取り込んで、数１６４の行列を算出し、次にこれらの算出結果から、数１６７に示す拡大ベクトルおよび行列と、数１８０の行列を算出し、さらに数１７１に基づき数１７３を算出することで、数１８６の各要素を決定することができる。また、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で作成された数１８６から、ジョブの出力時刻ｙ（ｋ）を取り込んで、各設備の最遅加工開始時刻ｘＳＬ（ｋ）と、最遅加工終了時刻ｘＣＬ（ｋ）を求めることができる。
【０３４５】
なお、ジョブの最遅投入（入力）時刻［ｕＬ（ｋ）］ｉを求めるためのもう一つのバックワード型の出力方程式は、前記数１２２と同じく次の式で表わせる。
【０３４６】
【数１８７】
2009015597.tif 000144
【０３４７】
ＭＰＬ形式作成手段３１は、各設備ｉの実行順序を規定する先行制約関係を取り込んで、個々の設備ｉにおける外部入力ｊの有無を判断することにより、数１６０の行列を算出し、次にその算出結果から、数１６７における行列−Ｂ０を算出して、数１８７の各要素を決定することができる。また、スケジュール作成手段３２は、ＭＰＬ形式作成手段３１で作成された数１８７から、数１０９における行列ｘ（ｋ）若しくは数１６７における行列−ｘ（ｋ）を取り込んで、最遅入力時刻ｕＬ（ｋ）を求めることができる。
【０３４８】
なお、第１実施例で説明した再スケジューリング以降の構成や動作は、第２実施例でも共通であるため、その説明を省略する。
【０３４９】
次に、第２実施例におけるスケジュール作成装置１の動作例を説明し、この実施例で提示したＭＰＬ状態表現空間の妥当性を確認する。図１０は、一つの入力，一つの出力，二つの設備１，２を備えた直列型の生産システムである。ここでは、設備１の加工開始時点と設備２の加工終了時点との間に、最大容量３の制約が課され、設備１の加工開始時点と設備２の加工終了時点に順序制約が課されるものの、設備１の加工終了時点と設備２の加工開始時点は順序制約が課されないものとする。また、設備１と設備２との間の移動時間を０．５とする。
【０３５０】
上記システムを検討対象とするスケジュール作成装置１のＭＰＬ形式作成手段３１は、入力装置１５からこうしたシステムの諸情報を入力して、次の式のパラメータ行列Ｆｏ，Ｂｏ，Ｃｏ，Ｈｏ（１），Ｈｏ（２），Ｈｏ（３）を算出することができる。
【０３５１】
【数１８８】
2009015597.tif 000145
【０３５２】
ここで、加工する部品数は１２（１≦ｋ≦１２）であり、全ての材料は時刻ｔ＝０に用意されているものとする。また、各設備１，２の使用時間は次のように周期的に変化するものとする。
【０３５３】
【数１８９】
2009015597.tif 000146
【０３５４】
これらの情報が、入力装置１５からＭＰＬ形式作成手段３１に与えられることで、ＭＰＬ形式作成手段３１は前述の数１６８の式を特定し、そこから各設備１，２の最早加工開始時刻［−ｘＥ（ｋ）］１，［−ｘＥ（ｋ）］２と最早加工終了時刻［−ｘＥ（ｋ）］３，［−ｘＥ（ｋ）］４をそれぞれ算出することができる。
【０３５５】
図１１は、設備１，２において、各ジョブ番号すなわち加工する部品ｋ毎の時間経緯をグラフで示したものである。同図において、順序制約が課せられる設備１の加工開始時点［−ｘＥ（ｋ）］１と、設備２の加工終了時点［−ｘＥ（ｋ）］４は、ジョブ番号ｋに対する増加関数となっている。一方、順序制約が課されない設備１の加工終了時点［−ｘＥ（ｋ）］２と、設備２の加工開始時点［−ｘＥ（ｋ）］３は、ジョブ番号ｋ＝２，３，６において、［−ｘＥ（ｋ）］ｉ＜［−ｘＥ（ｋ−１）］ｉとなっている。これにより、数１６８の式によるｍｐｌ状態空間表現が、システムの容量制約と順序制約の両方を柔軟に考慮できていることがわかる。
【０３５６】
以上の構成によれば、スケジュール作成装置１では、ｈ＝１のとき、上述した実施例１における数１０９の行列―Ｈｏ（１）に替えて、上述した数１６７の行列―Ｈｏ（１）（ＧＯ−は処理開始時点での順序制約の有無を表わすパラメータであり、ＧＯ＋は処理終了時点での順序制約の有無を表わすパラメータである）をＣＰＵ１１で決定するようにした。
【０３５７】
これにより、max-plus代数上で線形なＭＰＬ形式を導出するための行列Ｐｋ，―Ｆｏ＊，Ｈｏ（ｈ），およびＢｏを簡単に取得することができると共に、選択的に設定した順序制約を考慮したＨｏ（ｈ）についても簡単に取得することができる。かくして、Event-Varying型システムの容量制約が課せられた設備に対して、ジョブの追い越しが発生しないような順序制約を、必要に応じてＭＰＬ状態空間表現の中で考慮することが可能なスケジュール作成方法，スケジュール作成装置，およびコンピュータプログラムを提供できる。
【０３５８】
また、実施例２においても、システムの稼動開始後に何らかの原因で、その入力時刻や加工時間、加工開始時刻、加工終了時刻が変化した場合でも、上述した実施例１と同様に再スケジュールを作成するような構成にすることで、全ての設備における変更後の最早開始時刻，最早終了時刻，最遅開始時刻，および最遅終了時刻を適確に且つ効率的に把握することができる。
【０３５９】
なお、本発明は上記実施例に限定されるものではなく、本発明の要旨の範囲において種々の変形実施が可能である。例えば、設備で行われる処理として、加工を適用したが、製造や修理、修正などのこの他種々の処理を適用しても良い。
【０３６０】
また、実施例中では、複数の設備からなる生産システムを例として採用したが、タスクに順序制約を有するプロジェクト管理などを含むあらゆるシステムや、プロジェクトスケジューリング問題や、物流システムの配送計画問題などにも、そのまま適用が可能である。また、入力や出力が複数箇所存在するような、いわゆるＭＩＭＯ（Multiple Input Multiple Output）型構造を有するシステムへの適用も可能であり、従来知られているＰＥＲＴ（Program Evaluation and Review Technique）による方法よりも、適用範囲が広いことを意味する。
【図面の簡単な説明】
【０３６１】
【図１】本発明のスケジュール作成装置の内部構成を示すブロック図である。
【図２】本発明の第１実施例において、ｉ番目の設備に関する設備や外部出力との関係を示す概略図である。
【図３】本発明の第１実施例において、ｉ番目の設備に関する設備や外部入力との関係を示す概略図である。
【図４】設備間に仮想設備を設けたときの様子を示す概略図である。
【図５】同上、生産システムの一例を示す概略図である。
【図６】同上、図５のシステムを検討対象として、ジョブ番号と各設備の最早加工開始時刻との関係を示すグラフである。
【図７】同上、図５のシステムを検討対象として、再スケジュールを行ったときのジョブ番号と各設備の時間経緯との関係を示すグラフである。
【図８】同上、図５のシステムを検討対象として、ジョブ番号と各設備Ｆ１〜Ｆ４における余裕時間との関係を示すグラフである。
【図９】本発明の第２実施例において、ｉ番目の設備に関する設備や外部入力との関係を示す概略図である。
【図１０】同上、直列型生産システムの一例を示す概略図である。
【図１１】同上、図１０のシステムを検討対象として、ジョブ番号と各設備の時間経緯との関係を示すグラフである。
【符号の説明】
【０３６２】
１  スケジュール作成装置（コンピュータ）
１１  ＣＰＵ（演算部）
１２  ＲＡＭ（記憶部）
１５  入力装置（取込部）
２０  コンピュータプログラム
【図１】
2009015597.tif 000192
【図２】
2009015597.tif 000193
【図３】
2009015597.tif 000194
【図４】
2009015597.tif 000195
【図５】
2009015597.tif 000196
【図６】
2009015597.tif 000197
【図７】
2009015597.tif 000198
【図８】
2009015597.tif 000199
【図９】
2009015597.tif 000200
【図１０】
2009015597.tif 000201
【図１１】
2009015597.tif 000202