(57)【要約】  【課題】  複数の作業工程からなる複数のサブプロセスが選択的に並行している作業プロセスのスケジュールを容易に作成することができるスケジュール作成方法、スケジュール作成装置及びコンピュータプログラムを提供する。  【解決手段】  作業プロセスは、互いに並行して作業を行うことが可能な第１〜第ｎサブプロセスを含み、第ｉサブプロセスは作業工程Ｐi,1 〜Ｐi,s(i)のｓ（ｉ）個の作業工程を有し、いずれかのサブプロセスで作業が行われる。本発明では、作業を行うべく選択されたサブプロセスについて値がｅ（＝０）、その他のサブプロセスについて値がε（＝−∞）となる選択パラメータを用いることにより、線形性を保ったmax-plus代数で作業プロセスを記述する。選択パラメータを決定し、作業対象が投入される時刻（時点）を線形性を保ったmax-plus代数で記述された計算式により計算して、スケジュールが作成される。【選択図】        図１０
2005339178.tif 000002
【特許請求の範囲】
【請求項１】
互いに並行して作業を行うことが可能な複数のサブプロセスを含み、各サブプロセスは、外部から投入される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を外部へ供出する作業順に並んだ一又は複数の作業工程からなり、いずれのサブプロセスに作業対象が投入されるかを選択することができる作業プロセスについて、作業対象が投入されるサブプロセスの選択及び作業対象の投入時点をmax-plus代数により定めて、前記作業プロセスでの作業のスケジュールを作成する方法において、
特定の作業を行うサブプロセスとして選択されたサブプロセスについて値が０となり、その他のサブプロセスについて値が−∞となる選択パラメータを用いることにより線形性を保ったmax-plus代数で記述された計算式を用いて、前記投入時点を計算することを特徴とするスケジュール作成方法。
【請求項２】
互いに並行して作業を行うことが可能な第１サブプロセス〜第ｎサブプロセス（但し、ｎは自然数）を含み、第ｉサブプロセス（但し、ｉは自然数で１≦ｉ≦ｎ）は、外部から投入される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を外部へ供出する作業順に並んだｓ（ｉ）個（但し、ｓ（ｉ）は自然数）の作業工程からなり、いずれのサブプロセスに作業対象が投入されるかを選択することができる作業プロセスについて、記憶部及び演算部を備えるコンピュータを用い、作業対象が投入されるサブプロセスの選択及び作業対象の投入時点をmax-plus代数により定めて、前記作業プロセスでの作業のスケジュールを作成する方法において、
現在の時点ｔ0 、各サブプロセスに含まれる１〜ｓ（ｉ）番目の各作業工程でｋ番目の作業を開始する時点｛ｘi,j （ｋ）：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝（但し、ｊは自然数）、各サブプロセスに含まれる各作業工程での作業に必要な作業時間｛ｄi,j ：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝、及びｋ＋１，…，ｋ＋Ｎ番目の作業における作業結果が供出される時点の期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝（但し、ｍ，Ｎは自然数）を前記記憶部で記憶するステップと、
ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ｅ（但し、ｅ＝０）となり、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセス以外のサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ε（但し、ε＝−∞）となる選択パラメータ｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の値を前記演算部で決定する選択パラメータ決定ステップと、
各成分の値がｔ0 であるＮ行一列の行列Ｔ0 、下記式で与えられるＮ行一列の行列Ｒ（ｋ＋１）、
Ｒ（ｋ＋１）＝［ｒ（ｋ＋１）  ｒ（ｋ＋１）  …  ｒ（ｋ＋ｍ）］T 
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列ｘ（ｋ）、
ｘ（ｋ）＝［ｘ1,1 （ｋ）  ｘ1,2 （ｋ）  …  ｘ1,s(1)（ｋ）  ｘ2,1（ｋ）  …  
ｘ2,s(2)（ｋ）  …  ｘn,1 （ｋ）  …  ｘn,s(n)（ｋ）］T
max-plus代数の乗算（丸に×）及び加算（丸に＋）を内部に含み、ｓ（ｉ）行ｓ（ｉ）列の行列Ａi’を含んだ下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ａk 、
【数１】
2005339178.tif 000070
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列Ｂk 、
【数２】
2005339178.tif 000071
（ｓ（ｉ）−１）個のεの成分とｄi,s(i)及びδi （ｋ）がmax-plus代数の乗算で乗された成分とを交互に含んだ下記式で与えられる一行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ｃk、
【数３】
2005339178.tif 000072
下記式で与えられる行列Γk 、
【数４】
2005339178.tif 000073
並びに下記式で与えられる行列Δk を用い、
【数５】
2005339178.tif 000074
ｋ＋１，…，ｋ＋Ｎ番目の作業対象が投入される時点｛ｕ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を、max-plus代数のΘ演算を含む下記式により前記演算部で計算するステップと
【数６】
2005339178.tif 000075
を含むことを特徴とするスケジュール作成方法。
【請求項３】
前記選択パラメータ決定ステップでは、前記演算部は、選択パラメータの値を決定することによって確定する作業結果の供出の予定時点が前記期限よりも遅れることに対するペナルティと作業に要する作業コストとを含んでなる評価関数の値が最小になるように選択パラメータの値を決定し、
前記選択パラメータ決定ステップでは、一部の値を固定した選択パラメータより得られる前記評価関数の下界値と暫定的に得られている前記評価関数の最小値である暫定最小値とを比較して選択パラメータの値の組み合わせを選別する分枝限定法により、ｎN 通りの選択パラメータの値の組み合わせの中から前記評価関数の最小値を与える選択パラメータの値の組み合わせを前記演算部で探索するステップを含むこと
を特徴とする請求項２に記載のスケジュール作成方法。
【請求項４】
ｋ＋１番目の作業対象が投入される時点ｕ（ｋ＋１）を、一行Ｎ列の行列［ｅ  ε  …  ε］を含む下記式により前記演算部で計算するステップと、
【数７】
2005339178.tif 000076
下記式により得られる行列ｘ（ｋ＋１）を前記演算部で計算するステップと、
【数８】
2005339178.tif 000077
前記演算部で計算したｘ（ｋ＋１）を新たなｘ（ｋ）として前記記憶部で記憶するステップと、
新たな現在の時点ｔ0 及び新たな前記期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を前記記憶部で記憶するステップと、
δi （ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし（但し、１≦ｍ≦Ｎ−１）、δi（ｋ＋Ｎ）を新たなδi （ｋ＋Ｎ）とした選択パラメータより得られる前記評価関数の値を、前記暫定最小値の初期値として前記演算部で記憶するステップと、
前記記憶部で記憶した値を用いてスケジュールを前記演算部で再度作成するステップと
を更に含むことを特徴とする請求項３に記載のスケジュール作成方法。
【請求項５】
互いに並行して作業を行うことが可能な第１サブプロセス〜第ｎサブプロセス（但し、ｎは自然数）を含み、第ｉサブプロセス（但し、ｉは自然数で１≦ｉ≦ｎ）は、外部から投入される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を外部へ供出する作業順に並んだｓ（ｉ）個の作業工程（但し、ｓ（ｉ）は自然数）からなり、いずれのサブプロセスに作業対象が投入されるかを選択することができる作業プロセスについて、作業対象が投入されるサブプロセスの選択及び作業対象の投入時点をmax-plus代数により定めて、前記作業プロセスでの作業のスケジュールを作成する装置において、
現在の時点ｔ0 、各サブプロセスに含まれる１〜ｓ（ｉ）番目の各作業工程でｋ番目の作業を開始する時点｛ｘi,j （ｋ）：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝（但し、ｊは自然数）、各サブプロセスに含まれる各作業工程での作業に必要な作業時間｛ｄi,j ：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝、及びｋ＋１，…，ｋ＋Ｎ番目の作業における作業結果が供出される時点の期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝（但し、ｍ，Ｎは自然数）を記憶する記憶手段と、
ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ｅ（但し、ｅ＝０）となり、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセス以外のサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ε（但し、ε＝−∞）となる選択パラメータ｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の値を決定する選択パラメータ決定手段と、
各成分の値がｔ0 であるＮ行一列の行列Ｔ0 、下記式で与えられるＮ行一列の行列Ｒ（ｋ＋１）、
Ｒ（ｋ＋１）＝［ｒ（ｋ＋１）  ｒ（ｋ＋１）  …  ｒ（ｋ＋ｍ）］T 
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列ｘ（ｋ）、
ｘ（ｋ）＝［ｘ1,1 （ｋ）  ｘ1,2 （ｋ）  …  ｘ1,s(1)（ｋ）  ｘ2,1（ｋ）  …  
ｘ2,s(2)（ｋ）  …  ｘn,1 （ｋ）  …  ｘn,s(n)（ｋ）］T
max-plus代数の乗算（丸に×）及び加算（丸に＋）を内部に含み、ｓ（ｉ）行ｓ（ｉ）列の行列Ａi’を含んだ下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ａk 、
【数９】
2005339178.tif 000078
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列Ｂk 、
【数１０】
2005339178.tif 000079
（ｓ（ｉ）−１）個のεの成分とｄi,s(i)及びδi （ｋ）がmax-plus代数の乗算で乗された成分とを交互に含んだ下記式で与えられる一行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ｃk、
【数１１】
2005339178.tif 000080
下記式で与えられる行列Γk 、
【数１２】
2005339178.tif 000081
並びに下記式で与えられる行列Δk を用い、
【数１３】
2005339178.tif 000082
ｋ＋１，…，ｋ＋Ｎ番目の作業対象が投入される時点｛ｕ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を、max-plus代数のΘ演算を含む下記式により計算する手段と
【数１４】
2005339178.tif 000083
を備えることを特徴とするスケジュール作成装置。
【請求項６】
前記選択パラメータ決定手段は、
選択パラメータの値を決定することによって確定する作業結果の供出の予定時点が前記期限よりも遅れることに対するペナルティと作業に要する作業コストとを含んでなる評価関数の値が最小になるように選択パラメータの値を決定すべくなしてあり、
一部の値を固定した選択パラメータより得られる前記評価関数の下界値と暫定的に得られている前記評価関数の最小値である暫定最小値とを比較して選択パラメータの値の組み合わせを選別する分枝限定法により、ｎN 通りの選択パラメータの値の組み合わせの中から前記評価関数の最小値を与える選択パラメータの値の組み合わせを探索する手段を含むこと
を特徴とする請求項５に記載のスケジュール作成装置。 
【請求項７】
ｋ＋１番目の作業対象が投入される時点ｕ（ｋ＋１）を、一行Ｎ列の行列［ｅ  ε  …  ε］を含む下記式により計算する手段と、
【数１５】
2005339178.tif 000084
下記式により得られる行列ｘ（ｋ＋１）を計算する開始時点計算手段とを更に備え、
【数１６】
2005339178.tif 000085
前記記憶手段は、
前記開始時点計算手段が計算したｘ（ｋ＋１）を新たなｘ（ｋ）として記憶する手段と、
新たな現在の時点ｔ0 及び新たな前記期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を記憶する手段と、
δi （ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし（但し、１≦ｍ≦Ｎ−１）、δi（ｋ＋Ｎ）を新たなδi （ｋ＋Ｎ）とした選択パラメータより得られる前記評価関数の値を、前記暫定最小値の初期値として記憶する手段と
を有し、
前記記憶手段が記憶する値を用いてスケジュールを再度作成する手段を更に備えること
を特徴とする請求項６に記載のスケジュール作成装置。
【請求項８】
互いに並行して作業を行うことが可能な第１サブプロセス〜第ｎサブプロセス（但し、ｎは自然数）を含み、第ｉサブプロセス（但し、ｉは自然数で１≦ｉ≦ｎ）は、外部から投入される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を外部へ供出する作業順に並んだｓ（ｉ）個（但し、ｓ（ｉ）は自然数）の作業工程からなり、いずれのサブプロセスに作業対象が投入されるかを選択することができる作業プロセスについて、現在の時点ｔ0 、各サブプロセスに含まれる１〜ｓ（ｉ）番目の各作業工程でｋ番目の作業を開始する時点｛ｘi,j （ｋ）：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝（但し、ｊは自然数）、各サブプロセスに含まれる各作業工程での作業に必要な作業時間｛ｄi,j ：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝、及びｋ＋１，…，ｋ＋Ｎ番目の作業における作業結果が供出される時点の期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝（但し、ｍ，Ｎは自然数）を記憶するコンピュータに、作業対象が投入されるサブプロセスの選択及び作業対象の投入時点をmax-plus代数により定めて、前記作業プロセスでの作業のスケジュールを作成させるコンピュータプログラムにおいて、
コンピュータに、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ｅ（但し、ｅ＝０）となり、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセス以外のサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ε（但し、ε＝−∞）となる選択パラメータ｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の値を決定させる選択パラメータ決定手順と、
コンピュータに、各成分の値がｔ0 であるＮ行一列の行列Ｔ0 、下記式で与えられるＮ行一列の行列Ｒ（ｋ＋１）、
Ｒ（ｋ＋１）＝［ｒ（ｋ＋１）  ｒ（ｋ＋１）  …  ｒ（ｋ＋ｍ）］T 
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列ｘ（ｋ）、
ｘ（ｋ）＝［ｘ1,1 （ｋ）  ｘ1,2 （ｋ）  …  ｘ1,s(1)（ｋ）  ｘ2,1（ｋ）  …  
ｘ2,s(2)（ｋ）  …  ｘn,1 （ｋ）  …  ｘn,s(n)（ｋ）］T
max-plus代数の乗算（丸に×）及び加算（丸に＋）を内部に含み、ｓ（ｉ）行ｓ（ｉ）列の行列Ａi’を含んだ下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ａk 、
【数１７】
2005339178.tif 000086
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列Ｂk 、
【数１８】
2005339178.tif 000087
（ｓ（ｉ）−１）個のεの成分とｄi,s(i)及びδi （ｋ）がmax-plus代数の乗算で乗された成分とを交互に含んだ下記式で与えられる一行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ｃk、
【数１９】
2005339178.tif 000088
下記式で与えられる行列Γk 、
【数２０】
2005339178.tif 000089
並びに下記式で与えられる行列Δk を用い、
【数２１】
2005339178.tif 000090
ｋ＋１，…，ｋ＋Ｎ番目の作業対象が投入される時点｛ｕ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を、max-plus代数のΘ演算を含む下記式により計算させる手順と
【数２２】
2005339178.tif 000091
を含むことを特徴とするコンピュータプログラム。
【請求項９】
前記選択パラメータ決定手順は、
コンピュータに、選択パラメータの値を決定することによって確定する作業結果の供出の予定時点が前記期限よりも遅れることに対するペナルティと作業に要する作業コストとを含んでなる評価関数の値が最小になるように選択パラメータの値を決定させる手順であり、
コンピュータに、一部の値を固定した選択パラメータより得られる前記評価関数の下界値と暫定的に得られている前記評価関数の最小値である暫定最小値とを比較して選択パラメータの値の組み合わせを選別する分枝限定法により、ｎN 通りの選択パラメータの値の組み合わせの中から前記評価関数の最小値を与える選択パラメータの値の組み合わせを探索させる手順を含むこと
を特徴とする請求項８に記載のコンピュータプログラム。
【請求項１０】
コンピュータに、ｋ＋１番目の作業対象が投入される時点ｕ（ｋ＋１）を、一行Ｎ列の行列［ｅ  ε  …  ε］を含む下記式により計算させる手順と、
【数２３】
2005339178.tif 000092
コンピュータに、下記式により得られる行列ｘ（ｋ＋１）を計算させる手順と、
【数２４】
2005339178.tif 000093
コンピュータに、計算したｘ（ｋ＋１）を新たなｘ（ｋ）とさせる手順と、
コンピュータに、現在の時点ｔ0 及び前記期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を更新させる手順と、
コンピュータに、δi （ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし（但し、１≦ｍ≦Ｎ−１）、δi（ｋ＋Ｎ）を新たなδi （ｋ＋Ｎ）とした選択パラメータより得られる前記評価関数の値を、前記暫定最小値の初期値として設定させる手順と、
コンピュータに、スケジュールの作成を再度行わせる手順と
を更に含むことを特徴とする請求項９に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の作業工程を経て作業を行う作業プロセスのスケジュールを作成する方法、スケジュール作成装置、及びコンピュータプログラムに関する。
【背景技術】
【０００２】
製品を生産するための生産システム、又は物流システム等の作業プロセスは複数の作業工程により構成されており、それらの作業工程間には順序関係が存在する。また各作業工程では固有の作業時間が必要となる。このような複数の作業工程からなる作業プロセスでのスケジュールは、作業工程間の順序関係及び各作業工程での固有の作業時間の制約に従いつつも納期遅れを出さないように計画する必要がある。従来、ガントチャートを作成してスケジュールを作成する方法が用いられている。納期により最終の作業工程の終了時刻が規定され、納期から逆算して各作業工程の開始時刻が決定される。ガントチャートは、手作業による作成、又は組み合わせ最適化を用いた計算方法による作成などの方法で作成され、作成されたガントチャートに従って作業プロセスのスケジュールが管理される。
【０００３】
作業プロセスのスケジュールを作成するための他の方法として、max-plus代数を用いた方法がある。この方法は例えば非特許文献１に開示されている。実数体をＲと表してＤ＝Ｒ∪｛±∞｝とし、ｘ，ｙ∈Ｄであるｘ及びｙに対して、max-plus代数では加算（丸に＋）及び乗算（丸に×）を下記式で定義する。
【０００４】
【数１】
2005339178.tif 000003
【０００５】
ここで、ｍａｘ｛ｘ，ｙ｝は、ｘ及びｙの内の大きい方の値を演算の結果とすることを示す。max-plus代数の加算及び乗算の単位元は、（１）式の定義により夫々−∞及び０となり、夫々を下記のようにε及びｅで表す。
加算の単位元：−∞＝ε
乗算の単位元：０＝ｅ
また（１）式以外に、２つの演算子∧及び＼も下記式で定義する。
【０００６】
【数２】
2005339178.tif 000004
【０００７】
ここで、ｍｉｎ｛ｘ，ｙ｝は、ｘ及びｙの内の小さい方の値を演算の結果とすることを示す。max-plus代数の加算及び乗算の演算子は、通常の代数と同様に乗算が加算よりも優先度が高いとする。max-plus代数系においても、通常の代数系と同様に分配法則が成り立ち、式の変形等の通常の代数系と同様の代数計算を行うことができる。また、行列に対しても同様な演算子を定義する。Ｍ行ｎ列の行列Ａ，Ｂ、及びｎ行ｐ列の行列Ｃに対して、下記の行列計算を定義する。
【０００８】
【数３】
2005339178.tif 000005
【０００９】
ここで、［Ｘ］ijは行列Ｘのｉ行ｊ列成分を表している。以上の定義により、max-plus代数において、線形性を有する行列演算が可能となる。以上の如きmax-plus代数を用いて、作業プロセス内で順に行われる作業の順番（以下、イベントカウンタと言う）を独立変数とし、作業プロセス内で作業が行われる時刻をイベントカウンタの関数として記述し、スケジュールを作成することができる。
【００１０】
図７は、作業プロセスである生産システムの例を示す模式図である。図中に示す生産システムは、機械Ｍ１，機械Ｍ２，機械Ｍ３を生産設備として備えている。機械Ｍ１，Ｍ２は、夫々に材料となる部品を投入されてこの部品を加工し、機械Ｍ３は、機械Ｍ１，Ｍ２の夫々において加工された部品を投入され、機械Ｍ１及びＭ２から投入された部品を更に加工して一の部品を供出する。部品の投入及び受け渡しは次々に繰り返され、部品が加工されていく。この生産システムに対して、下記の変数を定義する。
【００１１】
ｘ1（ｋ），ｘ2（ｋ），ｘ3（ｋ）
：機械Ｍ１，Ｍ２，Ｍ３がｋ番目の部品の加工を開始する時刻
ｕ1（ｋ），ｕ2（ｋ）
：機械Ｍ１，Ｍ２にｋ番目の部品が投入される時刻
ｙ（ｋ）：機械Ｍ３において、ｋ番目の部品の加工が終了する時刻
ｄ1（ｋ），ｄ2（ｋ），ｄ3（ｋ）
：機械Ｍ１，Ｍ２，Ｍ３におけるｋ番目の部品の加工時間
ここで、ｋはイベントカウンタであり、この生産システムにおいては部品番号に相当する。
【００１２】
また、図７に示した生産システムには、以下の如き制約条件が存在する。
・機械Ｍ１及び機械Ｍ２は、ｋ番目の部品の加工が終了し、しかも（ｋ＋１）番目の部品が投入されてから、（ｋ＋１）番目の部品の加工を開始することが可能となる。
・機械Ｍ３は、ｋ番目の部品の加工が終了し、しかも機械Ｍ１及び機械Ｍ２から（ｋ＋１）番目の部品を受け付けてから、（ｋ＋１）番目の部品の加工を開始することが可能となる。
【００１３】
以上の制約条件より、例えば機械Ｍ１が（ｋ＋１）番目の部品の加工を開始する時刻ｘ1 （ｋ＋１）は、ｋ番目の部品の加工を終了した時刻と、（ｋ＋１）番目の部品が投入された時刻との内の遅い方の時刻に定められることになる。従って、以上の制約条件は通常の代数式で下記式の如く記述することができる。
【００１４】
【数４】
2005339178.tif 000006
【００１５】
（４）式は、ｍａｘ及び＋で構成されているため、max-plus代数の加算および乗算を用いて表すことができる。従って、（４）式は下記式で表現することができる。
【００１６】
【数５】
2005339178.tif 000007
【００１７】
（５）式の第３式に、第１式および第２式を代入して整理することで、（５）式は下記式で表すことができる。
【００１８】
【数６】
2005339178.tif 000008
【００１９】
但し、図７に示した生産システムの場合、ｘ（ｋ），Ａk ，Ｂk ，ｕ（ｋ＋１），Ｃk ，は下記式で表される。
【００２０】
【数７】
2005339178.tif 000009
【００２１】
（６）式は、作業プロセスにおける作業の開始時刻及び終了時刻に関する一般的な表現となっている。生産システムにおいて、機械の数をｎ、その中で材料となる部品を外部から投入される機械の数をＭ、加工した部品を外部へ供出する機械の数をＰとすると、Ａk はｎ×ｎの行列、Ｂk はｎ×Ｍの行列、ＣkはＰ×ｎの行列である。（６）式を繰り返し用いて（ｋ＋１）番目以降についての同様の式を計算すると、下記式が得られる。
【００２２】
【数８】
2005339178.tif 000010
【００２３】
（７）式の各式の両辺に、夫々Ｃk+1 ，Ｃk+2 ，…，Ｃk+N を前から乗ずることにより、下記式を得ることができる。
【００２４】
【数９】
2005339178.tif 000011
【００２５】
ここで、εPMは、各要素の値がεであるＰ×Ｍの行列である。（８）式は、生産システムにおいて、未来の部品の加工が終了する時刻Ｙ（ｋ＋１）が、現在の内部状態ｘ（ｋ）と未来の部品の投入時刻Ｕ（ｋ＋１）とから計算されることを示している。従って、生産システムの内部状態ｘ（ｋ）が定まっており、生産システムにおける納期である望ましい終了時刻Ｒ（ｋ＋１）をＹ（ｋ＋１）として定めたとき、納期遅れを出すことがない適切な部品の投入時刻Ｕ（ｋ＋１）を求めることができる。適切な入力Ｕ（ｋ＋１）を求めるためには、（８）式のＹ（ｋ＋１）にＲ（ｋ＋１）を代入した下記式を満たすＵ（ｋ＋１）を求めれば良い。
【００２６】
【数１０】
2005339178.tif 000012
【００２７】
（９）式は、右辺の第１項又は第２項のどちらか大きい方が左辺と等しいことを示している。右辺の第１項が左辺以下の大きさである場合は、右辺の第２項が左辺と等しくなるので、（９）式より下記式が成り立つ。
【００２８】
【数１１】
2005339178.tif 000013
【００２９】
また、（９）式の右辺の第１項が左辺よりも大きい場合は、（９）式を満たすＵ（ｋ＋１）は存在せず、現在の内部状態では納期遅れが避けられない状態である。この場合は、Ｕ（ｋ＋１）の値をどのような値にしても、避けることができない最小限の遅れ以上の納期遅れが発生する。この場合の部品の投入時刻は、最小限の遅れを発生させる投入時刻の内、最も遅いものとすることが望ましい。この場合の加工の終了時刻は（９）式の右辺で得られることとなり、Ｕ（ｋ＋１）を変化させても（９）式の右辺第１項は変化しないので、Ｕ（ｋ＋１）を変化させて（９）式の右辺第２項を（９）式の右辺第１項よりも小さくさせたときに、最小限の遅れを伴う終了時刻が得られることとなる。Ｕ（ｋ＋１）を増加させるのに従って（９）式の右辺第２項は増加するので、最小限の遅れを発生させる部品の投入時刻Ｕ（ｋ＋１）の内の最大のＵ（ｋ＋１）は、（９）式の右辺第１項と（９）式の右辺第２項とが等しいときに得られる。即ち、この場合の最適なＵ（ｋ＋１）に対して、下記式が成り立つ。
【００３０】
【数１２】
2005339178.tif 000014
【００３１】
（１０）式および（１１）式をまとめることにより、下記式が得られる。
【００３２】
【数１３】
2005339178.tif 000015
【００３３】
（１２）式は、max-plus代数系でのＵ（ｋ＋１）に対する連立一次方程式の形式となっている。この式は、max-plus代数における最大部分解の解法を利用することができる。最大部分解とは、下記の（１３）式で与えられるＺについての連立一次方程式において、式を満たす解が求められる場合にはその解を与え、式を満たす解が求められない場合には右辺の値を超えない範囲で最大の左辺の値を与える解である。（１３）式の最大部分解は、下記の（１４）式で与えられる。
【００３４】
【数１４】
2005339178.tif 000016
【００３５】
従って、（１２）式の最大部分解は下記式で与えられる。
【００３６】
【数１５】
2005339178.tif 000017
【００３７】
（１５）式は、生産システムにおいて定められた納期の時刻Ｒ（ｋ＋１）に対して、納期の時刻丁度に製品を完成させることができる場合は納期の時刻丁度に製品を完成させるような部品の投入時刻Ｕ（ｋ＋１）を求め、納期の時刻丁度に製品を完成させることが不可能な場合は、製品の完成が納期に遅れず、しかも最も遅い投入時刻Ｕ（ｋ＋１）を求めていることを示している。（１５）式では、イベントカウンタがｋ＋１，ｋ＋２，…，ｋ＋Ｎである全ての場合について投入時刻を求めているが、投入時刻は、下記の（１６）式を用いて、イベントカウンタがｋ＋１の場合のみを求める。
【００３８】
【数１６】
2005339178.tif 000018
【００３９】
ｋ＋２以降の投入時刻は、イベントカウンタを１インクリメントしつつ再計算することにより求まる。（１６）式を用いることにより、生産システムにおける適切な投入時刻即ち作業プロセスの適切な作業開始時刻を求めることが可能となり、作業プロセスのスケジュールを作成することができる。
【非特許文献１】シャッター（B. De Schutter），ブーン（T. van den Boom）「モデル  プレディクティブ  コントロール  フォア  マックス−プラス−リニア  ディスクリート  イベント  システムズ（Model predictive control for max-plus-linear discrete event systems）」，（英国），オートマティカ（Automatica），２００１年  ３７巻  ７号  ｐ．１０４９−１０５６
【非特許文献２】バチェリ（F. Baccelli ）他２名「フリーチョイス  ペトリネッツ−アン  アルジェブライック  アプローチ（Free-Choice Petri Nets - An Algebraic Approach）」，（米国），アイトリプルイー  トランザクションズ  オン  オートマティック  コントロール（IEEE Trans. Autom. Control），１９９６年  ４１巻  １２号  ｐ．１７５１−１７７７
【発明の開示】
【発明が解決しようとする課題】
【００４０】
前述の如く、max-plus代数は複数の作業工程が同期して作業結果が得られる作業プロセスをうまく記述することができる。しかし、複数の作業工程が選択的に並行している場合には、作業プロセスでの作業の過程を記述することが困難である。
【００４１】
図８は、複数の作業工程が選択的に並行している作業プロセスである生産システムの例を示す模式図である。図中に示す生産システムは、機械Ｍ１，Ｍ２，Ｍ３を生産設備として備えており、各機械は互いに並行して作業を行うことができる。更に、機械Ｍ１，Ｍ２，Ｍ３の前の工程として、選択器が備えられている。この生産システムに対して材料である部品が投入されると、選択器が機械Ｍ１，Ｍ２，Ｍ３のいずれかを選択し、選択器が選択した機械へ部品が投入され、選択された機械は投入された部品を加工して加工された部品を供出する。図８中では、現在機械Ｍ１が選択されている。複数の作業工程が選択的に並行している作業プロセスのその他の例としては、互いに並行した経路を有する物流又は通信システム、複数の受付窓口で来客を受け付ける受付システム等が挙げられる。
【００４２】
複数の作業工程が選択的に並行している作業プロセスを記述する方法の例としては、非特許文献２に開示された、max-plus代数に他の演算を取り入れた方法がある。しかし、この方法では、max-plus代数の特徴である線形性が失われるという難点があるので、作業プロセスの記述が複雑となり、スケジュールの作成が困難であるという問題がある。
【００４３】
本発明は、斯かる事情に鑑みてなされたものであって、その目的とするところは、線形性を保ったmax-plus代数で作業プロセスを記述することにより、複数の作業工程が選択的に並行している作業プロセスのスケジュールを容易に作成することができるスケジュール作成方法、スケジュール作成装置及びコンピュータプログラムを提供することにある。
【００４４】
また本発明の他の目的とするところは、作業プロセスのスケジュールを作成するための計算時間を短縮することができるスケジュール作成方法、スケジュール作成装置及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００４５】
第１発明に係るスケジュール作成方法は、互いに並行して作業を行うことが可能な複数のサブプロセスを含み、各サブプロセスは、外部から投入される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を外部へ供出する作業順に並んだ一又は複数の作業工程からなり、いずれのサブプロセスに作業対象が投入されるかを選択することができる作業プロセスについて、作業対象が投入されるサブプロセスの選択及び作業対象の投入時点をmax-plus代数により定めて、前記作業プロセスでの作業のスケジュールを作成する方法において、特定の作業を行うサブプロセスとして選択されたサブプロセスについて値が０となり、その他のサブプロセスについて値が−∞となる選択パラメータを用いることにより線形性を保ったmax-plus代数で記述された計算式を用いて、前記投入時点を計算することを特徴とする。
【００４６】
第２発明に係るスケジュール作成方法は、互いに並行して作業を行うことが可能な第１サブプロセス〜第ｎサブプロセス（但し、ｎは自然数）を含み、第ｉサブプロセス（但し、ｉは自然数で１≦ｉ≦ｎ）は、外部から投入される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を外部へ供出する作業順に並んだｓ（ｉ）個（但し、ｓ（ｉ）は自然数）の作業工程からなり、いずれのサブプロセスに作業対象が投入されるかを選択することができる作業プロセスについて、記憶部及び演算部を備えるコンピュータを用い、作業対象が投入されるサブプロセスの選択及び作業対象の投入時点をmax-plus代数により定めて、前記作業プロセスでの作業のスケジュールを作成する方法において、現在の時点ｔ0 、各サブプロセスに含まれる１〜ｓ（ｉ）番目の各作業工程でｋ番目の作業を開始する時点｛ｘi,j（ｋ）：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝（但し、ｊは自然数）、各サブプロセスに含まれる各作業工程での作業に必要な作業時間｛ｄi,j ：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝、及びｋ＋１，…，ｋ＋Ｎ番目の作業における作業結果が供出される時点の期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝（但し、ｍ，Ｎは自然数）を前記記憶部で記憶するステップと、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセスが選択される場合にδi（ｋ＋ｍ）＝ｅ（但し、ｅ＝０）となり、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセス以外のサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ε（但し、ε＝−∞）となる選択パラメータ｛δi（ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の値を前記演算部で決定する選択パラメータ決定ステップと、各成分の値がｔ0 であるＮ行一列の行列Ｔ0、下記式で与えられるＮ行一列の行列Ｒ（ｋ＋１）、
Ｒ（ｋ＋１）＝［ｒ（ｋ＋１）  ｒ（ｋ＋１）  …  ｒ（ｋ＋ｍ）］T 
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列ｘ（ｋ）、
ｘ（ｋ）＝［ｘ1,1 （ｋ）  ｘ1,2 （ｋ）  …  ｘ1,s(1)（ｋ）  ｘ2,1 （ｋ）  …  
ｘ2,s(2)（ｋ）  …  ｘn,1 （ｋ）  …  ｘn,s(n)（ｋ）］T
max-plus代数の乗算（丸に×）及び加算（丸に＋）を内部に含み、ｓ（ｉ）行ｓ（ｉ）列の行列Ａi’を含んだ下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ａk 、
【００４７】
【数１７】
2005339178.tif 000019
【００４８】
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列Ｂk 、
【００４９】
【数１８】
2005339178.tif 000020
【００５０】
（ｓ（ｉ）−１）個のεの成分とｄi,s(i)及びδi （ｋ）がmax-plus代数の乗算で乗された成分とを交互に含んだ下記式で与えられる一行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ｃk、
【００５１】
【数１９】
2005339178.tif 000021
【００５２】
下記式で与えられる行列Γk 、
【００５３】
【数２０】
2005339178.tif 000022
【００５４】
並びに下記式で与えられる行列Δk を用い、
【００５５】
【数２１】
2005339178.tif 000023
【００５６】
ｋ＋１，…，ｋ＋Ｎ番目の作業対象が投入される時点｛ｕ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を、max-plus代数のΘ演算を含む下記式により前記演算部で計算するステップと
【００５７】
【数２２】
2005339178.tif 000024
【００５８】
を含むことを特徴とする。
【００５９】
第３発明に係るスケジュール作成方法は、前記選択パラメータ決定ステップでは、前記演算部は、選択パラメータの値を決定することによって確定する作業結果の供出の予定時点が前記期限よりも遅れることに対するペナルティと作業に要する作業コストとを含んでなる評価関数の値が最小になるように選択パラメータの値を決定し、前記選択パラメータ決定ステップでは、一部の値を固定した選択パラメータより得られる前記評価関数の下界値と暫定的に得られている前記評価関数の最小値である暫定最小値とを比較して選択パラメータの値の組み合わせを選別する分枝限定法により、ｎN 通りの選択パラメータの値の組み合わせの中から前記評価関数の最小値を与える選択パラメータの値の組み合わせを前記演算部で探索するステップを含むことを特徴とする。
【００６０】
第４発明に係るスケジュール作成方法は、ｋ＋１番目の作業対象が投入される時点ｕ（ｋ＋１）を、一行Ｎ列の行列［ｅ  ε  …  ε］を含む下記式により前記演算部で計算するステップと、
【００６１】
【数２３】
2005339178.tif 000025
【００６２】
下記式により得られる行列ｘ（ｋ＋１）を前記演算部で計算するステップと、
【００６３】
【数２４】
2005339178.tif 000026
【００６４】
前記演算部で計算したｘ（ｋ＋１）を新たなｘ（ｋ）として前記記憶部で記憶するステップと、新たな現在の時点ｔ0 及び新たな前記期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を前記記憶部で記憶するステップと、δi（ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし（但し、１≦ｍ≦Ｎ−１）、δi （ｋ＋Ｎ）を新たなδi（ｋ＋Ｎ）とした選択パラメータより得られる前記評価関数の値を、前記暫定最小値の初期値として前記演算部で記憶するステップと、前記記憶部で記憶した値を用いてスケジュールを前記演算部で再度作成するステップとを更に含むことを特徴とする。
【００６５】
第５発明に係るスケジュール作成装置は、互いに並行して作業を行うことが可能な第１サブプロセス〜第ｎサブプロセス（但し、ｎは自然数）を含み、第ｉサブプロセス（但し、ｉは自然数で１≦ｉ≦ｎ）は、外部から投入される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を外部へ供出する作業順に並んだｓ（ｉ）個の作業工程（但し、ｓ（ｉ）は自然数）からなり、いずれのサブプロセスに作業対象が投入されるかを選択することができる作業プロセスについて、作業対象が投入されるサブプロセスの選択及び作業対象の投入時点をmax-plus代数により定めて、前記作業プロセスでの作業のスケジュールを作成する装置において、現在の時点ｔ0 、各サブプロセスに含まれる１〜ｓ（ｉ）番目の各作業工程でｋ番目の作業を開始する時点｛ｘi,j（ｋ）：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝（但し、ｊは自然数）、各サブプロセスに含まれる各作業工程での作業に必要な作業時間｛ｄi,j ：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝、及びｋ＋１，…，ｋ＋Ｎ番目の作業における作業結果が供出される時点の期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝（但し、ｍ，Ｎは自然数）を記憶する記憶手段と、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセスが選択される場合にδi（ｋ＋ｍ）＝ｅ（但し、ｅ＝０）となり、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセス以外のサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ε（但し、ε＝−∞）となる選択パラメータ｛δi（ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の値を決定する選択パラメータ決定手段と、各成分の値がｔ0 であるＮ行一列の行列Ｔ0、下記式で与えられるＮ行一列の行列Ｒ（ｋ＋１）、
Ｒ（ｋ＋１）＝［ｒ（ｋ＋１）  ｒ（ｋ＋１）  …  ｒ（ｋ＋ｍ）］T 
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列ｘ（ｋ）、
ｘ（ｋ）＝［ｘ1,1 （ｋ）  ｘ1,2 （ｋ）  …  ｘ1,s(1)（ｋ）  ｘ2,1 （ｋ）  …  
ｘ2,s(2)（ｋ）  …  ｘn,1 （ｋ）  …  ｘn,s(n)（ｋ）］T
max-plus代数の乗算（丸に×）及び加算（丸に＋）を内部に含み、ｓ（ｉ）行ｓ（ｉ）列の行列Ａi’を含んだ下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ａk 、
【００６６】
【数２５】
2005339178.tif 000027
【００６７】
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列Ｂk 、
【００６８】
【数２６】
2005339178.tif 000028
【００６９】
（ｓ（ｉ）−１）個のεの成分とｄi,s(i)及びδi （ｋ）がmax-plus代数の乗算で乗された成分とを交互に含んだ下記式で与えられる一行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ｃk、
【００７０】
【数２７】
2005339178.tif 000029
【００７１】
下記式で与えられる行列Γk 、
【００７２】
【数２８】
2005339178.tif 000030
【００７３】
並びに下記式で与えられる行列Δk を用い、
【００７４】
【数２９】
2005339178.tif 000031
【００７５】
ｋ＋１，…，ｋ＋Ｎ番目の作業対象が投入される時点｛ｕ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を、max-plus代数のΘ演算を含む下記式により計算する手段と
【００７６】
【数３０】
2005339178.tif 000032
【００７７】
を備えることを特徴とする。
【００７８】
第６発明に係るスケジュール作成装置は、前記選択パラメータ決定手段は、選択パラメータの値を決定することによって確定する作業結果の供出の予定時点が前記期限よりも遅れることに対するペナルティと作業に要する作業コストとを含んでなる評価関数の値が最小になるように選択パラメータの値を決定すべくなしてあり、一部の値を固定した選択パラメータより得られる前記評価関数の下界値と暫定的に得られている前記評価関数の最小値である暫定最小値とを比較して選択パラメータの値の組み合わせを選別する分枝限定法により、ｎN 通りの選択パラメータの値の組み合わせの中から前記評価関数の最小値を与える選択パラメータの値の組み合わせを探索する手段を含むことを特徴とする。
【００７９】
第７発明に係るスケジュール作成装置は、ｋ＋１番目の作業対象が投入される時点ｕ（ｋ＋１）を、一行Ｎ列の行列［ｅ  ε  …  ε］を含む下記式により計算する手段と、
【００８０】
【数３１】
2005339178.tif 000033
【００８１】
下記式により得られる行列ｘ（ｋ＋１）を計算する開始時点計算手段とを更に備え、
【００８２】
【数３２】
2005339178.tif 000034
【００８３】
前記記憶手段は、前記開始時点計算手段が計算したｘ（ｋ＋１）を新たなｘ（ｋ）として記憶する手段と、新たな現在の時点ｔ0 及び新たな前記期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を記憶する手段と、δi（ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし（但し、１≦ｍ≦Ｎ−１）、δi （ｋ＋Ｎ）を新たなδi（ｋ＋Ｎ）とした選択パラメータより得られる前記評価関数の値を、前記暫定最小値の初期値として記憶する手段とを有し、前記記憶手段が記憶する値を用いてスケジュールを再度作成する手段を更に備えることを特徴とする。
【００８４】
第８発明に係るコンピュータプログラムは、互いに並行して作業を行うことが可能な第１サブプロセス〜第ｎサブプロセス（但し、ｎは自然数）を含み、第ｉサブプロセス（但し、ｉは自然数で１≦ｉ≦ｎ）は、外部から投入される作業対象を受け付け、受け付けた作業対象に対する作業を行い、作業結果を外部へ供出する作業順に並んだｓ（ｉ）個（但し、ｓ（ｉ）は自然数）の作業工程からなり、いずれのサブプロセスに作業対象が投入されるかを選択することができる作業プロセスについて、現在の時点ｔ0 、各サブプロセスに含まれる１〜ｓ（ｉ）番目の各作業工程でｋ番目の作業を開始する時点｛ｘi,j（ｋ）：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝（但し、ｊは自然数）、各サブプロセスに含まれる各作業工程での作業に必要な作業時間｛ｄi,j ：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝、及びｋ＋１，…，ｋ＋Ｎ番目の作業における作業結果が供出される時点の期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝（但し、ｍ，Ｎは自然数）を記憶するコンピュータに、作業対象が投入されるサブプロセスの選択及び作業対象の投入時点をmax-plus代数により定めて、前記作業プロセスでの作業のスケジュールを作成させるコンピュータプログラムにおいて、コンピュータに、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセスが選択される場合にδi（ｋ＋ｍ）＝ｅ（但し、ｅ＝０）となり、ｋ＋ｍ番目の作業を行うサブプロセスとして第ｉサブプロセス以外のサブプロセスが選択される場合にδi （ｋ＋ｍ）＝ε（但し、ε＝−∞）となる選択パラメータ｛δi（ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の値を決定させる選択パラメータ決定手順と、コンピュータに、各成分の値がｔ0 であるＮ行一列の行列Ｔ0、下記式で与えられるＮ行一列の行列Ｒ（ｋ＋１）、
Ｒ（ｋ＋１）＝［ｒ（ｋ＋１）  ｒ（ｋ＋１）  …  ｒ（ｋ＋ｍ）］T 
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列ｘ（ｋ）、
ｘ（ｋ）＝［ｘ1,1 （ｋ）  ｘ1,2 （ｋ）  …  ｘ1,s(1)（ｋ）  ｘ2,1 （ｋ）  …  
ｘ2,s(2)（ｋ）  …  ｘn,1 （ｋ）  …  ｘn,s(n)（ｋ）］T
max-plus代数の乗算（丸に×）及び加算（丸に＋）を内部に含み、ｓ（ｉ）行ｓ（ｉ）列の行列Ａi’を含んだ下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ａk 、
【００８５】
【数３３】
2005339178.tif 000035
【００８６】
下記式で与えられる（ｓ（１）＋…＋ｓ（ｎ））行一列の行列Ｂk 、
【００８７】
【数３４】
2005339178.tif 000036
【００８８】
（ｓ（ｉ）−１）個のεの成分とｄi,s(i)及びδi （ｋ）がmax-plus代数の乗算で乗された成分とを交互に含んだ下記式で与えられる一行（ｓ（１）＋…＋ｓ（ｎ））列の行列Ｃk、
【００８９】
【数３５】
2005339178.tif 000037
【００９０】
下記式で与えられる行列Γk 、
【００９１】
【数３６】
2005339178.tif 000038
【００９２】
並びに下記式で与えられる行列Δk を用い、
【００９３】
【数３７】
2005339178.tif 000039
【００９４】
ｋ＋１，…，ｋ＋Ｎ番目の作業対象が投入される時点｛ｕ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を、max-plus代数のΘ演算を含む下記式により計算させる手順と
【００９５】
【数３８】
2005339178.tif 000040
【００９６】
を含むことを特徴とする。
【００９７】
第９発明に係るコンピュータプログラムは、前記選択パラメータ決定手順は、コンピュータに、選択パラメータの値を決定することによって確定する作業結果の供出の予定時点が前記期限よりも遅れることに対するペナルティと作業に要する作業コストとを含んでなる評価関数の値が最小になるように選択パラメータの値を決定させる手順であり、コンピュータに、一部の値を固定した選択パラメータより得られる前記評価関数の下界値と暫定的に得られている前記評価関数の最小値である暫定最小値とを比較して選択パラメータの値の組み合わせを選別する分枝限定法により、ｎN 通りの選択パラメータの値の組み合わせの中から前記評価関数の最小値を与える選択パラメータの値の組み合わせを探索させる手順を含むことを特徴とする。
【００９８】
第１０発明に係るコンピュータプログラムは、コンピュータに、ｋ＋１番目の作業対象が投入される時点ｕ（ｋ＋１）を、一行Ｎ列の行列［ｅ  ε  …  ε］を含む下記式により計算させる手順と、
【００９９】
【数３９】
2005339178.tif 000041
【０１００】
コンピュータに、下記式により得られる行列ｘ（ｋ＋１）を計算させる手順と、
【０１０１】
【数４０】
2005339178.tif 000042
【０１０２】
コンピュータに、計算したｘ（ｋ＋１）を新たなｘ（ｋ）とさせる手順と、コンピュータに、現在の時点ｔ0 及び前記期限｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝を更新させる手順と、コンピュータに、δi（ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし（但し、１≦ｍ≦Ｎ−１）、δi （ｋ＋Ｎ）を新たなδi（ｋ＋Ｎ）とした選択パラメータより得られる前記評価関数の値を、前記暫定最小値の初期値として設定させる手順と、コンピュータに、スケジュールの作成を再度行わせる手順とを更に含むことを特徴とする。
【０１０３】
本発明においては、max-plus代数の線形性を保ちながら、複数の作業工程が選択的に並行している作業プロセスを記述することを可能とした。作業プロセスの例として図８に示す生産プロセスを用いて、線形性を保ったmax-plus代数により作業プロセスを記述する方法を説明する。
【０１０４】
まず、図８に示す生産プロセスにおける機械Ｍ１を考える。（ｋ＋１）番目の部品を加工する機械として機械Ｍ１が選択器に選択された場合、機械Ｍ１が（ｋ＋１）番目の部品の加工を開始する時刻（時点）ｘ1 （ｋ＋１）は、ｋ番目の部品の加工を終了した時刻と、（ｋ＋１）番目の部品が投入された時刻ｕ1（ｋ＋１）との内の遅い方の時刻に定められることになるので、下記式で表される。
【０１０５】
【数４１】
2005339178.tif 000043
【０１０６】
ここで、ｄ1 は機械Ｍ１での部品の加工時間である。また、（ｋ＋１）番目の部品を加工する機械として機械Ｍ１が選択器に選択されない場合、機械Ｍ１が（ｋ＋１）番目の部品の加工を開始する時刻ｘ1（ｋ＋１）の値は、ｋ番目の部品の加工を開始する時刻ｘ1 （ｋ）の値を受け継ぐこととする。即ち、下記式が成り立つ。
【０１０７】
【数４２】
2005339178.tif 000044
【０１０８】
ここで、下記式に示すように選択パラメータδi （ｋ）を定義する。
【０１０９】
【数４３】
2005339178.tif 000045
【０１１０】
図８に示す生産プロセスでは、（ｋ＋１）番目の部品を加工する機械として機械Ｍ１が選択器に選択された場合、δ1 （ｋ）＝ｅ，δ2 （ｋ）＝δ3（ｋ）＝εとなる。この選択パラメータを用いて（１７）式及び（１８）式を統合すると、下記式が成り立つ。
【０１１１】
【数４４】
2005339178.tif 000046
【０１１２】
ｄ1 の値は０以上であるので、（１９）式に含まれる｛｝の中の表式について、下記式が成り立つ。
【０１１３】
【数４５】
2005339178.tif 000047
【０１１４】
従って、（１９）式を整理すると、下記式となる。
【０１１５】
【数４６】
2005339178.tif 000048
【０１１６】
機械Ｍ２が（ｋ＋１）番目の部品の加工を開始する時刻ｘ2 （ｋ＋１）及び機械Ｍ３が（ｋ＋１）番目の部品の加工を開始する時刻ｘ3（ｋ＋１）についても、ｄ2 ，ｄ3 を機械Ｍ２，Ｍ３での部品の加工時間であるとして、同様に下記式が成り立つ。
【０１１７】
【数４７】
2005339178.tif 000049
【０１１８】
更に、ｋ番目の部品の加工が終了する時刻ｙ（ｋ）について、下記式が成り立つ。
【０１１９】
【数４８】
2005339178.tif 000050
【０１２０】
（２０）式〜（２３）式をまとめることにより、従来と同様の（６）式が得られる。但し、図８に示した生産システムの場合は、（６）式中のｘ（ｋ），Ａk ，Ｂk ，Ｃk ，は下記式で表される。
【０１２１】
【数４９】
2005339178.tif 000051
【０１２２】
次に、より一般的な作業プロセスを考える。図９は、複数の作業工程が選択的に並行している作業プロセスである生産システムの他の例を示す模式図である。図９（ａ）に示す生産システムは、選択器が選択可能な生産ラインを三本備えており、１番目のラインは機械Ｍ１を備え、２番目のラインは機械Ｍ２を備え、３番目のラインは機械Ｍ３１及び機械Ｍ３２を直列に備えている。この生産システムに対して材料である部品が投入されると、選択器が三本のラインのいずれかを選択し、選択器が選択したラインへ部品が投入され、部品が加工される。３番目のラインが選択された場合は、まず機械Ｍ３１が部品を加工し、更にその部品を機械Ｍ３２が加工し、加工された部品を供出する。機械Ｍ１が（ｋ＋１）番目の部品の加工を開始する時刻ｘ1 （ｋ＋１）及び機械Ｍ２が（ｋ＋１）番目の部品の加工を開始する時刻ｘ2（ｋ＋１）は、夫々（２０）式及び（２１）式により得られる。機械Ｍ３１が（ｋ＋１）番目の部品の加工を開始する時刻ｘ31（ｋ＋１）は、（２２）式より、ｄ31を機械Ｍ３１での部品の加工時間であるとして、下記式で表される。
【０１２３】
【数５０】
2005339178.tif 000052
【０１２４】
機械Ｍ３２が（ｋ＋１）番目の部品の加工を開始する時刻ｘ32（ｋ＋１）は、機械Ｍ３２がｋ番目の部品の加工を終了した時刻と、機械Ｍ３１が（ｋ＋１）番目の部品の加工を終了した時刻との内の遅い方の時刻に定められることになるので、下記式で表される。
【０１２５】
【数５１】
2005339178.tif 000053
【０１２６】
ここで、ａ∈Ｄであるａについて、下記式を定義する。
【０１２７】
【数５２】
2005339178.tif 000054
【０１２８】
また、ｄ31＞０であるので、下記式が成り立つ。
【０１２９】
【数５３】
2005339178.tif 000055
【０１３０】
従って、（２５）式に（２４）式を代入して整理することにより、（２５）式は下記式となる。
【０１３１】
【数５４】
2005339178.tif 000056
【０１３２】
また、ｋ番目の部品の加工が終了する時刻ｙ（ｋ）について、下記式が成り立つ。
【０１３３】
【数５５】
2005339178.tif 000057
【０１３４】
（２１），（２２），（２４），（２６），（２７）式をまとめることにより、（６）式が得られる。但し、図９（ａ）に示した生産システムの場合は、（６）式中のｘ（ｋ），Ａk ，Ｂk ，Ｃk ，は下記式で表される。
【０１３５】
【数５６】
2005339178.tif 000058
【０１３６】
図９（ｂ）に示す生産システムは、より一般的な生産システムであり、３番目のラインは、機械Ｍ３１〜機械Ｍ３ｓのｓ個の機械を直列に備えている。この生産システムも、同様に（６）式により記述することができる。機械Ｍ３ｊが（ｋ＋１）番目の部品の加工を開始する時刻をｘ3,j（ｋ＋１）とし、機械Ｍ３ｊでの部品の加工時間をｄ3,j として、この場合の（６）式中のｘ（ｋ），Ａk ，Ｂk ，Ｃk ，は下記式で表される。
【０１３７】
【数５７】
2005339178.tif 000059
【０１３８】
ここで、行列Ａk は（ｓ＋２）×（ｓ＋２）の行列である。また行列Ａkに含まれる行列Ａ’3 はｓ×ｓの行列であり、通常の代数における下三角行列に対応する行列である。また行列Ａk に含まれるε1,s，εs,1 は、各要素の値がεである夫々１×ｓ，ｓ×１の行列である。また行列ｘ（ｋ）及びＢk は（ｓ＋２）×１の行列であり、行列Ｃkは１×（ｓ＋２）の行列である。
【０１３９】
図１０は、複数の作業工程が選択的に並行している一般的な作業プロセスを示す模式図である。作業プロセスは、互いに並行して作業を行うことが可能な第１サブプロセス〜第ｎサブプロセスのｎ個のサブプロセスを含み、第ｉサブプロセスは作業工程Ｐi,1 〜Ｐi,s(i)のｓ（ｉ）個の作業工程を有している。各サブプロセスの作業の流れの前には、セレクタが備えられており、作業を行う際には、セレクタがいずれかのサブプロセスを選択し、選択されたサブプロセス内で作業が行われる。第ｉサブプロセスが有する各作業工程Ｐi,jは、全段の他の作業工程Ｐi,j-1 から作業対象を投入され、作業対象に対する作業を行い、作業結果を後段の他の作業工程Ｐi,j+1へ投入するように、作業順に並んでいる。なお第ｉサブプロセスが含む作業工程Ｐi,1 〜Ｐi,s(i)の内、初段の作業工程Ｐi,1はセレクタから作業対象を投入され、最終段の作業工程Ｐi,s(i)は第ｉサブプロセスの最終的な作業結果を供出する。この作業プロセスも、同様に（６）式により記述することができる。選択パラメータδi（ｋ）は、ｋ番目の作業が第ｉサブプロセスで行われる場合にδi （ｋ）＝ｅ、ｋ番目の作業が第ｉサブプロセス以外のサブプロセスで行われる場合にδi（ｋ）＝εとする。この場合の（６）式中のｘ（ｋ），Ａk ，Ｂk ，Ｃk ，は下記式で表される。
【０１４０】
【数５８】
2005339178.tif 000060
【０１４１】
ここで、ｘi,j（ｋ）は作業工程Ｐi,j がｋ番目の作業を開始する時刻であり、ｄi,j は作業工程Ｐi,j での作業時間である。また、行列Ａkは（ｓ（１）＋…＋ｓ（ｎ））×（ｓ（１）＋…＋ｓ（ｎ））の行列である。また行列Ａk に含まれる行列Ａ’i は、ｓ（ｉ）×ｓ（ｉ）の行列であり、通常の代数における下三角行列に対応する行列である。また行列Ａkに含まれるεa,b は、各要素の値がεであるａ×ｂの行列である。また行列ｘ（ｋ）及びＢk は（ｓ（１）＋…＋ｓ（ｎ））×１の行列であり、行列Ｃkは１×（ｓ（１）＋…＋ｓ（ｎ））の行列である。
【０１４２】
以上の如く、選択パラメータを導入することによって、複数の作業工程が選択的に並行している作業プロセスを従来と同様の線形性を保ったmax-plus代数により（６）式で記述することが可能となる。従って、従来と同様に（１５）式及び（１６）式を用いることにより、複数の作業工程が選択的に並行している作業プロセスにおいて適切な作業対象の投入時刻ｕ（ｋ＋１）を求めることが可能となり、作業プロセスのスケジュールを作成することができる。但し、この場合のΔkは下記式で表される。
【０１４３】
【数５９】
2005339178.tif 000061
【０１４４】
第１、第２、第５及び第８発明においては、選択パラメータを用いて（６）式のｘ（ｋ），Ａk ，Ｂk ，Ｃk を表すことにより、複数の作業工程が選択的に並行している作業プロセスにおける作業対象の投入時刻（時点）を計算する計算式が、線形性を保ったmax-plus代数で記述され、選択パラメータを決定した計算式を用いて作業対象の投入時刻を計算する。
【０１４５】
第３、第６及び第９発明においては、納期遅れのペナルティと作業コストとを含んでなる評価関数の値が最小となるような最適な選択パラメータの値の組み合わせを、分枝限定法を用いて探索する。
【０１４６】
第４、第７及び第１０発明においては、イベントカウンタｋ＋１における作業対象の投入時刻ｕ（ｋ＋１）を計算し、ｋをカウントアップさせたスケジュールを作成する際には、１≦ｍ≦Ｎ−１の範囲でδi （ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし、δi（ｋ＋Ｎ）を新たなδi （ｋ＋Ｎ）として得られる評価関数の値を、分枝限定法で用いる評価関数の暫定最小値の初期値として利用する。
【発明の効果】
【０１４７】
第１、第２、第５及び第８発明にあっては、選択パラメータ｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝を用いて（６）式のｘ（ｋ），Ａk ，Ｂk ，Ｃkを表すことにより、複数の作業工程が選択的に並行している作業プロセスを、線形性を保ったmax-plus代数で記述することができる。従って、選択パラメータの値を決定し、線形性を保ったmax-plus代数で記述された計算式に選択パラメータの値を代入して作業対象の投入時刻（時点）を計算することによって、作業プロセスのスケジュールを容易に作成することができる。
【０１４８】
第３、第６及び第９発明にあっては、評価関数の値が最小となるような最適な選択パラメータの値の組み合わせを探索する分枝限定法を用いることによって、評価関数を計算するまでもなく明らかに最適ではない選択パラメータの組み合わせを除外しながら最適な選択パラメータを探索するので、最適な選択パラメータを探索するための計算時間を短縮することができる。
【０１４９】
第４、第７及び第１０発明にあっては、先に得られた最適値のδi （ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし、先の最適値のδi （ｋ＋Ｎ）を新たなδi（ｋ＋Ｎ）とした選択パラメータは、ｋをカウントアップさせた作業プロセスでの最適な選択パラメータに近い値である可能性が高いので、評価関数の暫定最小値の初期値が評価関数の最小値に極めて近い値となる可能性が高く、分枝限定法による最適な選択パラメータを探索するための計算時間が更に短縮される等、本発明は優れた効果を奏する。
【発明を実施するための最良の形態】
【０１５０】
以下本発明をその実施の形態を示す図面に基づき具体的に説明する。
図１は、本発明のスケジュール作成装置１の内部構成を示すブロック図である。スケジュール作成装置１は、パーソナルコンピュータ又はサーバ装置などの汎用コンピュータを用いて構成されている。スケジュール作成装置１は、演算を行うＣＰＵ（演算部）１１と、演算に伴って発生する一時的な情報を記憶するＲＡＭ（記憶部）１２と、ＣＤ−ＲＯＭドライブ等の外部記憶装置１３と、ハードディスク等の内部記憶装置１４とを備えている。ＣＰＵ１１は、ＣＤ−ＲＯＭ等の記録媒体２から本発明のコンピュータプログラム２０を外部記憶装置１３にて読み取り、読み取ったコンピュータプログラム２０を内部記憶装置１４に記憶させる。コンピュータプログラム２０は必要に応じて内部記憶装置１４からＲＡＭ１２へロードされ、ロードされたコンピュータプログラム２０に基づいてＣＰＵ１１はスケジュール作成装置１に必要な処理を実行する。
【０１５１】
スケジュール作成装置１は、キーボード等のオペレータの操作により情報が入力される装置、又は図示しない外部の装置からスケジュール作成のために必要な情報が入力される装置からなる入力装置１５を備えている。またスケジュール装置１は、ＣＲＴディスプレイ等の表示装置、プリンタ装置、又は作成したスケジュールを図示しない外部の装置へ出力する装置からなる出力装置１６を備えている。
【０１５２】
なお、本発明のコンピュータプログラム２０は、スケジュール作成装置１に接続された図示しない外部のサーバ装置からスケジュール作成装置１へロードされて内部記憶装置１４に記憶される形態であってもよい。
【０１５３】
本発明のスケジュール作成装置１が行う処理の目的は、作業プロセスの最適なスケジュールを作成することであるが、選択パラメータδi （ｋ＋ｍ）の値が定まると（１５）式及び（１６）式により作業対象の投入時刻（時点）ｕ（ｋ＋１）を求めることができるので、最適なスケジュールを得るためにはδi（ｋ＋ｍ）の最適な値を求める必要がある。生産プロセスが含むサブプロセスの数をｎとし、ｕ（ｋ＋１）の計算の際に何ステップ先までのイベントカウンタまでを含めて計算を行うかを示すステップ数をＮとする。このとき、δi（ｋ＋ｍ）∈｛ε，ｅ｝，１≦ｉ≦ｎ，１≦ｍ≦Ｎである。また、ｍの値をｍ＝Ｎ0 に固定した場合、δi （ｋ＋Ｎ0）が取り得る値は、ｎ個のδi （ｋ＋Ｎ0 ）の内のいずれか唯一つの値がｅとなり、その他の値がεとなる。従って、ｍの値をｍ＝Ｎ0に固定した場合にδi （ｋ＋Ｎ0 ）が取り得る値の組み合わせはｎ通りである。即ち、選択パラメータδi（ｋ＋ｍ）が取り得る値の組み合わせはｎN 通りである。
【０１５４】
本発明では、ｎN 通りのδi （ｋ＋ｍ）の組み合わせの中から最適な組み合わせを選択する方法として分枝限定法を用いる。分枝限定法とは、δi（ｋ＋ｍ）の組み合わせを評価するための評価関数を定義しておき、評価関数の値に基づいてｎN 通りのδi （ｋ＋ｍ）の組み合わせの中から最適な組み合わせを探索する方法である。例えばｍ＝１〜Ｎ0までのδi （ｋ＋ｍ）の値を暫定的に定め、この場合に取り得る評価関数の範囲を求める。求めた評価関数の範囲が評価関数の最適暫定値よりも良い値を含まない場合は、ｍ＝Ｎ0＋１以降のδi （ｋ＋ｍ）の値がどのような組み合わせでも最適値は得られない。従って、暫定的に定めた値の組み合わせを含むδi（ｋ＋ｍ）の組み合わせのこれ以上の評価を停止し、その他の組み合わせの評価を行う。求めた評価関数の範囲が評価関数の最適暫定値よりも良い値を含む場合は、暫定的に定めた値の組み合わせを含むδi（ｋ＋ｍ）の組み合わせの中に最適な組み合わせが存在する可能性がある。従って、更にｍ＝Ｎ0 ＋１のδi （ｋ＋ｍ）の値を定め、同様に取り得る評価関数の範囲を求める。以上の処理を繰り返してｍ＝１〜Ｎのδi（ｋ＋ｍ）の値が暫定的に定まった場合は、評価関数を計算し、計算した評価関数の値が暫定最適値よりも良い値であるときには、暫定最適値を更新し、この場合のδi（ｋ＋ｍ）の組み合わせを暫定的な最適組み合わせとする。分枝限定法では、以上の如くにして、評価する必要のない組み合わせを除外しつつδi （ｋ＋ｍ）の組み合わせを評価し、最適な評価関数の値を与えるδi（ｋ＋ｍ）の組み合わせを最適な組み合わせとする。
【０１５５】
本発明では、分枝限定法の評価関数として、下記式で定義されるＪを用いる。
【０１５６】
【数６０】
2005339178.tif 000062
【０１５７】
ここで、α及びβは共に正の定数である。またｒ（ｋ＋ｍ）は、イベントカウンタｋ＋ｍでの作業の納期に対応する。またｙ（ｋ＋ｍ）は、（１５）式で求められるＵ（ｋ＋１）を用いて（８）式により計算されるＹ（ｋ＋１）に含まれる要素の値であり、イベントカウンタｋ＋ｍでの作業終了予定時刻である。従って、（３０）式の第２項は納期遅れが発生した場合のペナルティを示す。また（３０）式の第１項は、作業プロセスで作業を行う際の作業コストを示し、本発明では、作業に長い時間を要するサブプロセスであるほど作業コストが低いと仮定する。従って、（３０）式の第１項は、作業を行うべく選択されたサブプロセスでの作業時間が長いほど値が小さくなる。本発明で最適なδi （ｋ＋ｍ）の組み合わせを探索する際には、（３０）式で定義されるＪの値の最小値を与えるδi（ｋ＋ｍ）の組み合わせを探索する。
【０１５８】
図２は、本発明のスケジュール作成装置１が行う処理の手順を示すフローチャートである。スケジュール作成装置１は、図１０に示す如き作業プロセスに対して適切な作業対象の投入時刻ｕ（ｋ＋１）を求める処理を行う。スケジュール作成装置１のＣＰＵ１１は、ＲＡＭ１２にロードした本発明のコンピュータプログラム２０に従って以下の処理を実行する。
【０１５９】
スケジュール作成装置１のＣＰＵ１１は、まず、スケジュール作成の処理に必要な初期パラメータを設定する（Ｓ１）。このとき、ＣＰＵ１１は、現在時刻ｔ0 ，イベントカウンタｋにおける各作業工程Ｐi,j の作業開始時刻｛ｘi,j（ｋ）：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝を成分とする（２８）式で定義される状態変数ｘ（ｋ），各作業工程Ｐi,j での作業時間であるシステムパラメータ｛ｄi,j：１≦ｉ≦ｎ，１≦ｊ≦ｓ（ｉ）｝，ステップ数Ｎ，イベントカウンタｋ＋ｍでの作業終了時刻の期限である最新の納期｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝，評価関数Ｊの暫定最小値Ｊminの初期値を設定する。ＣＰＵ１１は、これらの値を入力装置１５にて外部から受け付けるか、又は予め内部記憶装置１４で記憶している値をＲＡＭ１２へ読み出すことで初期パラメータを設定する。なお、暫定最小値Ｊminの初期値を設定する際には、選択パラメータ｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の値を所定の値にして得られる評価関数Ｊの値を暫定最小値Ｊminの初期値として設定してもよい。また、スケジュール作成装置１は、現在時刻ｔ0 を計時する手段を備える形態であってもよい。
【０１６０】
ＣＰＵ１１は、次に、選択パラメータδi （ｋ＋ｍ）の最適な組み合わせを求める選択パラメータ最適化処理を行う（Ｓ２）。図３及び図４は、ステップＳ２の選択パラメータ最適化処理のサブルーチンの処理手順を示すフローチャートである。ＣＰＵ１１は、まずｍ＝１とする（Ｓ２０１）。
【０１６１】
ＣＰＵ１１は、次に、ｍが定められた｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ｝の内の唯一の値をｅとしてその他の値を全てεにすることによって、各δi （ｋ＋ｍ）の値を固定する（Ｓ２０２）。ＣＰＵ１１は、次に、ｍ＝Ｎであるか否かを判定する（Ｓ２０３）。ｍの値がＮよりも小さい値であった場合は（Ｓ２０３：ＮＯ）、ＣＰＵ１１は、現在のｍをＮ0として、ｍ＝１〜Ｎ0 で固定した値の組み合わせを含む選択パラメータδi （ｋ＋ｍ）の組み合わせにより得られる評価関数Ｊの値の下限値である下界値Ｊ’を計算する（Ｓ２０４）。
【０１６２】
ここで下界値Ｊ’の計算方法について説明する。まず（３０）式の第１項を考える。（３０）式の第１項に含まれるｄi は、第ｉサブプロセスに含まれるｓ（ｉ）個の作業工程の作業時間の合計である。ｎ個のｄiの中での最大値をｄM とすると、ｄi ＞０であるので、ｊ1 （ｋ＋ｍ）の定義より、ｊ1（ｋ＋ｍ）≧−ｄM が成り立つ。これは、最も作業に時間を要するサブプロセスを選んだ場合に最も作業コストが低くなることを示す。従って、（３０）式の第１項に対して下記式が成り立つ。
【０１６３】
【数６１】
2005339178.tif 000063
【０１６４】
次に（３０）式の第２項を考える。（８）式は、右辺の第１項と第２項との内、より大きい方の値が左辺の値に等しいということを示している。従って、（８）式より下記式が成り立つ。
【０１６５】
【数６２】
2005339178.tif 000064
【０１６６】
これにより、Ｙ（ｋ＋１）及びΓk を各要素に分解することによって、更に下記式が成り立つ。
【０１６７】
【数６３】
2005339178.tif 000065
【０１６８】
またｊ2 ’（ｋ＋ｍ）を下記式で定義する。
【０１６９】
【数６４】
2005339178.tif 000066
【０１７０】
（３２）式、（３３）式、及び（３０）式の第２項に含まれるｊ2 （ｋ＋ｍ）の定義により、ｊ2 （ｋ＋ｍ）≧ｊ2’（ｋ＋ｍ）が成り立つ。従って、（３０）式の第２項に対して、下記式が成り立つ。
【０１７１】
【数６５】
2005339178.tif 000067
【０１７２】
従って、ｍ＝１〜Ｎ0 で固定した値の組み合わせを含む選択パラメータδi （ｋ＋ｍ）の組み合わせにより得られる評価関数Ｊの値の下界値Ｊ’を下記式で定義する。
【０１７３】
【数６６】
2005339178.tif 000068
【０１７４】
（３１）式及び（３４）式により、Ｊ≧Ｊ’となり、評価関数Ｊの値は常に下界値Ｊ’以上の値となる。ステップＳ２０４で、ＣＰＵ１１は、（３５）式で定義される下界値Ｊ’を計算する。
【０１７５】
ＣＰＵ１１は、次に、計算した下界値Ｊ’の値が評価関数Ｊの現在の暫定最小値Ｊmin の値よりも小さいか否かを判定する（Ｓ２０５）。下界値Ｊ’の値が暫定最小値Ｊminの値よりも小さい場合は（Ｓ２０５：ＹＥＳ）、ｍ＝１〜Ｎ0 で固定した値の組み合わせを含む選択パラメータδi （ｋ＋ｍ）の組み合わせの中に暫定最小値Ｊminよりも小さい評価関数Ｊの値を与える組み合わせが存在する可能性があるので、固定した値の組み合わせを含むより良い組み合わせを探索すべく、ＣＰＵ１１は、ｍの値をインクリメントし（Ｓ２０６）、処理をステップＳ２０２へ戻して更にδi（ｋ＋ｍ）の値を固定する。
【０１７６】
下界値Ｊ’の値が暫定最小値Ｊmin の値以上である場合は、ｍ＝１〜Ｎ0 で固定した値の組み合わせを含む選択パラメータδi （ｋ＋ｍ）の組み合わせの中には暫定最小値Ｊminよりも小さい評価関数Ｊの値を与える組み合わせは存在しないので、固定した値の組み合わせを含む組み合わせは最適な組み合わせの探索範囲から除外される。
【０１７７】
ステップＳ２０５で下界値Ｊ’の値が暫定最小値Ｊmin の値以上である場合は（Ｓ２０５：ＮＯ）、ＣＰＵ１１は、｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ｝の内の唯一の値をｅとしてその他の値を全てεにするｎ個のδi（ｋ＋ｍ）の組み合わせは全て試行したか否かを判定する（Ｓ２０７）。ｎ個のδi （ｋ＋ｍ）の組み合わせの内、まだ試行していない組み合わせがある場合は（Ｓ２０７：ＮＯ）、ＣＰＵ１１は、各δi（ｋ＋ｍ）の値をまだ試行していない他の組み合わせで固定し（Ｓ２０８）、処理をステップＳ２０３へ戻す。
【０１７８】
ステップＳ２０３でｍ＝Ｎである場合は（Ｓ２０３：ＹＥＳ）、選択パラメータ｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の値が全て固定されている場合であるので、ＣＰＵ１１は、（３０）式で定義される評価関数Ｊを計算する（Ｓ２１１）。ＣＰＵ１１は、次に、計算した評価関数Ｊの値が暫定最小値Ｊminの値よりも小さいか否かを判定する（Ｓ２１２）。評価関数Ｊの値が暫定最小値Ｊmin の値以上である場合は（Ｓ２１２：ＮＯ）、現在の選択パラメータδi（ｋ＋ｍ）の組み合わせは最適な組み合わせではないので、新たな選択パラメータの組み合わせを探索すべく、処理をステップＳ２０７へ進める。
【０１７９】
ステップＳ２１２で評価関数Ｊの値が暫定最小値Ｊmin の値よりも小さい場合は（Ｓ２１２：ＹＥＳ）、ＣＰＵ１１は、（２８）式及び（２９）式を用いた（１５）式による最大部分解に基づく入力Ｕ（ｋ＋１）を、各成分の値がｔ0であるＮ×１の行列Ｔ0 を用いた下記式により計算する（Ｓ２１３）。
【０１８０】
【数６７】
2005339178.tif 000069
【０１８１】
Ｕ（ｋ＋１）はイベントカウンタｋ＋１〜ｋ＋Ｎにおける作業対象の投入時刻であり、現在時刻ｔ0 よりも作業対象の投入時刻を早めることはできないので、（３６）式が成り立つ。
【０１８２】
ＣＰＵ１１は、次に、（２８）式及び（２９）式を用いた（８）式にＵ（ｋ＋１）を代入することにより、作業終了予定時刻Ｙ（ｋ＋１）を計算する（Ｓ２１４）。ＣＰＵ１１は、次に、現在の選択パラメータδi （ｋ＋ｍ）の組み合わせは実行可能な解であるか否かを判定する（Ｓ２１５）。このとき、ＣＰＵ１１は、計算したＵ（ｋ＋１）及びＹ（ｋ＋１）について、下記の関係が成り立つか否かを判定する。
ｕ（ｋ＋ｍ＋１）≧ｕ（ｋ＋ｍ），１≦ｍ≦Ｎ
ｙ（ｋ＋ｍ＋１）≧ｙ（ｋ＋ｍ），１≦ｍ≦Ｎ            …（３７）
【０１８３】
これらの関係が成り立たない場合は、各イベントカウンタでの作業対象の投入時刻又は作業終了時刻がイベントカウンタの順に並んでいない場合であり、この場合の選択パラメータδi （ｋ＋ｍ）の組み合わせは実行不可能な解である。ステップＳ２１５で現在の選択パラメータδi（ｋ＋ｍ）の組み合わせが実行不可能な解である場合は（Ｓ２１５：ＮＯ）、ＣＰＵ１１は、現在の選択パラメータδi （ｋ＋ｍ）の組み合わせは最適な組み合わせではないとして、新たな選択パラメータの組み合わせを探索すべく、処理をステップＳ２０７へ進める。
【０１８４】
ステップＳ２１５で現在の選択パラメータδi （ｋ＋ｍ）の組み合わせが実行可能な解である場合は（Ｓ２１５：ＹＥＳ）、ＣＰＵ１１は、評価関数Ｊの値を新たな暫定最小値Ｊminの値として暫定最小値Ｊmin の値を更新する（Ｓ２１６）。ＣＰＵ１１は、次に、現在の選択パラメータδi （ｋ＋ｍ）の組み合わせ及びＵ（ｋ＋１）を暫定解としてＲＡＭ１２に記憶させ（Ｓ２１７）、新たな選択パラメータの組み合わせを探索すべく、処理をステップＳ２０７へ進める。
【０１８５】
ステップＳ２０７でｎ個のδi （ｋ＋ｍ）の組み合わせを全て試行している場合は（Ｓ２０７：ＹＥＳ）、ＣＰＵ１１は、ｍ＝１であるか否かを判定する（Ｓ２０９）。ｍの値が１より大きい場合は（Ｓ２０９：ＮＯ）、値が固定されている選択パラメータδi（ｋ＋ｍ）を減らして他の組み合わせを評価すべく、ＣＰＵ１１は、ｍの値を１だけデクリメントし（Ｓ２１０）、処理をステップＳ２０７へ戻す。ｍ＝１である場合は（Ｓ２０９：ＹＥＳ）、ステップＳ２の選択パラメータ最適化処理のサブルーチンを終了し、処理をメインルーチンへ戻す。選択パラメータ最適化処理のサブルーチンが終了したときの暫定最小値Ｊminに対応してＲＡＭ１２に記憶されている選択パラメータδi （ｋ＋ｍ）の組み合わせ及びＵ（ｋ＋１）が、評価関数Ｊの最小値を与える最適解となる。
【０１８６】
ステップＳ２の選択パラメータ最適化処理のサブルーチンが終了した後は、ＣＰＵ１１は、最適解のＵ（ｋ＋１）を代入した（１６）式によりイベントカウンタｋ＋１における作業対象の投入時刻ｕ（ｋ＋１）を計算し（Ｓ３）、イベントカウンタｋ＋１における選択パラメータδi （ｋ＋１）の最適解、及び計算したｕ（ｋ＋１）を出力部で出力する（Ｓ４）。このようにして出力された選択パラメータδi（ｋ＋１）及び作業対象の投入時刻ｕ（ｋ＋１）に基づいて、作業プロセスで作業が行われる。ＣＰＵ１１は、次に、スケジュール作成の処理を終了するか否かを判定し（Ｓ５）、スケジュール作成の処理を終了する場合は（Ｓ５：ＹＥＳ）、処理を終了する。スケジュール作成の処理を終了しない場合は（Ｓ５：ＮＯ）、ＣＰＵ１１は、イベントカウンタをインクリメントした次のステップの処理を行うべく、次のステップでのスケジュール作成の処理に必要なパラメータを作成するパラメータ更新処理を行う（Ｓ６）。
【０１８７】
図５は、ステップＳ６のパラメータ更新処理のサブルーチンの処理手順を示すフローチャートである。ＣＰＵ１１は、ステップＳ３で計算したｕ（ｋ＋１）を用いた（７）式の第１式により、イベントカウンタｋ＋１における状態変数ｘ（ｋ＋１）を計算する（Ｓ６０１）。ＣＰＵ１１は、次に、イベントカウンタをカウントアップさせるべく、計算したｘ（ｋ＋１）の値を最新の状態変数ｘ（ｋ）の値とすることによって、最新の状態変数ｘ（ｋ）を設定する（Ｓ６０２）。ＣＰＵ１１は、次に、現在時刻ｔ0 及びイベントカウンタｋ＋ｍでの作業終了時刻の期限である納期｛ｒ（ｋ＋ｍ）：１≦ｍ≦Ｎ｝の値を更新する（Ｓ６０３）。このとき、ＣＰＵ１１は、ｒ（ｋ＋ｍ＋１）をｒ（ｋ＋ｍ）とすることにより各ｒ（ｋ＋ｍ）の値を更新してもよく、また納期に変更があった場合は、入力装置１５で受け付けた納期の値を最新のｒ（ｋ＋ｍ）の値として設定する。
【０１８８】
ＣＰＵ１１は、次に、最適解としてＲＡＭ１２に記憶されている選択パラメータδi （ｋ＋ｍ）の組み合わせを用いて、最適解でのδi （ｋ＋ｍ＋１）の値を新たなδi（ｋ＋ｍ）の値とし、最適解でのδi （ｋ＋Ｎ）の値を新たなδi （ｋ＋Ｎ）の値として設定した選択パラメータ｛δi（ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝の組み合わせを作成する（Ｓ６０４）。ＣＰＵ１１は、次に、作成した選択パラメータの組み合わせを用いて、（３６）式によりＵ（ｋ＋１）を計算し、（８）式によりＹ（ｋ＋１）を計算する（Ｓ６０５）。ＣＰＵ１１は、次に、計算したＵ（ｋ＋１）及びＹ（ｋ＋１）について（３７）式が成り立つか否かを判定することにより、選択パラメータの組み合わせが実行可能解であるか否かを判定する（Ｓ６０６）。
【０１８９】
ステップＳ６０６で選択パラメータの組み合わせが実行可能解である場合は（Ｓ６０６：ＹＥＳ）、ＣＰＵ１１は、（３０）式により評価関数Ｊを計算する（Ｓ６０７）。ＣＰＵ１１は、次に、計算した評価関数Ｊの値を新たな暫定最小値Ｊmin の値とすることにより、暫定最小値Ｊmin の初期値を設定する（Ｓ６０８）。ＣＰＵ１１は、次に、現在の選択パラメータδi（ｋ＋ｍ）の組み合わせ及びＵ（ｋ＋１）を暫定解としてＲＡＭ１２に記憶させ（Ｓ６０９）、ステップＳ６のパラメータ更新処理のサブルーチンを終了し、処理をメインルーチンへ戻す。ステップＳ６０６で選択パラメータの組み合わせが実行可能解ではない場合は（Ｓ６０６：ＮＯ）、ＣＰＵ１１は、所定の値に暫定最小値Ｊminの初期値を設定し（Ｓ６１０）、ステップＳ６のパラメータ更新処理のサブルーチンを終了し、処理をメインルーチンへ戻す。
【０１９０】
ステップＳ６のパラメータ更新処理のサブルーチンが終了した後は、ＣＰＵ１１は、処理をステップＳ２へ戻し、更新されたパラメータを用いて新たなスケジュール作成の処理を行う。
【０１９１】
以上詳述した如く、本発明においては、選択パラメータ｛δi （ｋ＋ｍ）：１≦ｉ≦ｎ，１≦ｍ≦Ｎ｝を用いてｘ（ｋ），Ａk ，Ｂk ，Ｃkを表すことにより、複数の作業工程が選択的に並行している作業プロセスを、線形性を保ったmax-plus代数で記述することができる。従って、選択パラメータの値を決定し、決定した選択パラメータの値を（３６）式及び（１６）式に代入して作業対象の投入時刻ｕ（ｋ＋１）を計算することによって、作業プロセスのスケジュールを容易に作成することができる。
【０１９２】
また、本発明においては、選択パラメータの最適な値を決定する際に、分枝限定法を用いて最適な値を探索する。選択パラメータの一部の値を固定して得られる評価関数Ｊの下界値Ｊ’に基づいて、評価関数Ｊを計算するまでもなく明らかに最適ではない選択パラメータの組み合わせを除外しつつ最適な選択パラメータを探索するので、最適な選択パラメータを探索するための計算時間を短縮することができる。また、（３５）式により下界値Ｊ’を計算するために必要な計算量が評価関数Ｊを計算するための計算量に比べて大幅に少ないので、最適な選択パラメータを探索するための計算時間がより短縮される。
【０１９３】
更に本発明においては、イベントカウンタをカウントアップさせたｕ（ｋ＋１）を計算する際に、先に得られた選択パラメータの最適値を用いて、δi （ｋ＋ｍ＋１）を新たなδi （ｋ＋ｍ）とし、δi（ｋ＋Ｎ）を新たなδi （ｋ＋Ｎ）として得られる評価関数の値を、分枝限定法で用いる評価関数Ｊの暫定最小値Ｊmin の初期値として利用する。最適値を再利用した新たな選択パラメータは、イベントカウンタをカウントアップさせた作業プロセスでの最適な選択パラメータに近い値である可能性が高い。従って、暫定最小値Ｊminの初期値が評価関数Ｊの最小値に極めて近い値となる可能性が高く、分枝限定法による最適な選択パラメータを探索するための計算時間が更に短縮される。
【０１９４】
図６は、本発明を用いてスケジュール作成の処理を行った計算時間の例を示す図表である。図９（ａ）に示す生産システムについて、所定のパラメータの値を用い、イベントカウンタをカウントアップさせながら６０回のスケジュール作成の処理を行った。この図表では、Ｎの値を１〜７として、分枝限定法を用いずに選択パラメータの全ての組み合わせをしらみつぶしに探索して選択パラメータの最適値を決定した場合と、分枝限定法を用いて選択パラメータを決定した場合と、更にイベントカウンタをカウントアップさせるときに選択パラメータの最適値を利用した場合との計算時間を比較して示している。図表中に数字で示した計算時間は、夫々の場合で複数回の処理を行った計算時間の平均を相対値で示している。Ｎの値が大きくなるに従って、分枝限定法を使用した場合の計算時間がつらみつぶしの場合よりも短くなり、カウントアップ時に選択パラメータの最適値を利用する場合の計算時間は更に短くなっている。Ｎの値を大きくすることによって、より遠い未来までの納期に基づいてスケジュールを先読みし、納期遅れがより小さくなるスケジュールを作成することができる。従って、より良いスケジュールを作成する際に、本発明を用いることによって計算時間を短縮できることが明らかである。
【図面の簡単な説明】
【０１９５】
【図１】本発明のスケジュール作成装置の内部構成を示すブロック図である。
【図２】本発明のスケジュール作成装置が行う処理の手順を示すフローチャートである。
【図３】ステップＳ２の選択パラメータ最適化処理のサブルーチンの処理手順を示すフローチャートである。
【図４】ステップＳ２の選択パラメータ最適化処理のサブルーチンの処理手順を示すフローチャートである。
【図５】ステップＳ６のパラメータ更新処理のサブルーチンの処理手順を示すフローチャートである。
【図６】本発明を用いてスケジュール作成の処理を行った計算時間の例を示す図表である。
【図７】作業プロセスである生産システムの例を示す模式図である。
【図８】複数の作業工程が選択的に並行している作業プロセスである生産システムの例を示す模式図である。
【図９】複数の作業工程が選択的に並行している作業プロセスである生産システムの他の例を示す模式図である。
【図１０】複数の作業工程が選択的に並行している一般的な作業プロセスを示す模式図である。
【符号の説明】
【０１９６】
１  スケジュール作成装置
１１  ＣＰＵ（演算部）
１２  ＲＡＭ（記憶部）
２  記録媒体
２０  コンピュータプログラム
【図１】
2005339178.tif 000094
【図２】
2005339178.tif 000095
【図３】
2005339178.tif 000096
【図４】
2005339178.tif 000097
【図５】
2005339178.tif 000098
【図６】
2005339178.tif 000099
【図７】
2005339178.tif 000100
【図８】
2005339178.tif 000101
【図９】
2005339178.tif 000102
【図１０】
2005339178.tif 000103