(57)【特許請求の範囲】
【請求項１】
ジョブ・ショップの繰返し生産におけるスケジュールを計算機上で自動的に作成する方法であって、
製品に関するデータ及び加工工程に関するデータをデータ入力手段に入力する工程、
最短周期演算手段により、１つのジョブ集合を加工するときの機械別使用時間総計を求めて機械別使用時間総計の最大値を最短の繰返し周期として算出する工程、
最短の繰返し周期以上の時間幅をもつ任意の周期を指定周期として指定周期入力手段に入力する工程、
スケジュール割り当て優先順位演算手段により、各製品間及び各工程間に生じる加工順序による順序制約を満たすように、各製品をその加工の順序に従って並べて階層別にグルーピングを行い、各グループに含まれる製品のあらゆる順列とグループの加工順序との組み合せから各製品にスケジュール割り当ての優先順位を付与する工程、
繰返しスケジュール計画手段により、優先順位の高い製品を１つ選び出し、入力された指定周期で作成されたスケジュール表に製品の加工順序に従って工程を割り当て、機械を使用する時間帯が既に同じ機械が使用されている時間帯と重複する場合は、機械競合を回避するように既に使用されている時間帯と重複しないスケジュールに調整し、機械競合が生じず対象工程がボトルネック機械を使用する場合は、ボトルネック機械を使用する時間帯を連続させてボトルネック機械に複数の遊休時間帯を作らないようにし、全ての優先順位の製品についてスケジューリングを行って指定周期の繰返しスケジュールを計画する工程、
計画結果表示・修正手段により、スケジュールの計画結果を表示し、表示されたスケジュールについて、複数の中から選択したり修正又は／及び編集を行う工程、
を含むことを特徴とする繰返し型生産ラインのスケジュール作成方法。
【請求項２】
ジョブ・ショップの繰返し生産におけるスケジュールを作成する装置であって、
製品に関するデータ及び加工工程に関するデータを入力するデータ入力手段と、
１つのジョブ集合を加工するときの機械別使用時間総計を求めて機械別使用時間総計の最大値を最短の繰返し周期として算出する最短周期演算手段と、
最短の繰返し周期以上の時間幅をもつ任意の周期を指定周期として入力する指定周期入力手段と、
各製品間及び各工程間に生じる加工順序による順序制約を満たすように、各製品をその加工の順序に従って並べて階層別にグルーピングを行い、各グループに含まれる製品のあらゆる順列とグループの加工順序との組み合せから各製品にスケジュール割り当ての優先順位を付与するスケジュール割り当て優先順位演算手段と、
優先順位の高い製品を１つ選び出し、入力された指定周期で作成されたスケジュール表に製品の加工順序に従って工程を割り当て、機械を使用する時間帯が既に同じ機械が使用されている時間帯と重複する場合は、機械競合を回避するように既に使用されている時間帯と重複しないスケジュールに調整し、機械競合が生じず対象工程がボトルネック機械を使用する場合は、ボトルネック機械を使用する時間帯を連続させてボトルネック機械に複数の遊休時間帯を作らないようにし、全ての優先順位の製品についてスケジューリングを行って指定周期の繰返しスケジュールを計画する繰返しスケジュール計画手段と、
スケジュールの計画結果を表示し、表示されたスケジュールについて、複数の中から選択したり修正又は／及び編集を行う計画結果表示・修正手段と、
を備えたことを特徴とする繰返し型生産ラインのスケジュール作成装置。
【請求項３】
ジョブ・ショップの繰返し生産におけるスケジュールを作成するためのプログラムを記録した記録媒体であって、
製品に関するデータ及び加工工程に関するデータが入力される手順と、
１つのジョブ集合を加工するときの機械別使用時間総計を求めて機械別使用時間総計の最大値を最短の繰返し周期として算出させる手順と、
最短の繰返し周期以上の時間幅をもつ任意の周期が指定周期として入力される手順と、
各製品間及び各工程間に生じる加工順序による順序制約が満たされるように、各製品をその加工の順序に従って並べて階層別にグルーピングを行わせ、各グループに含まれる製品のあらゆる順列とグループの加工順序との組み合せから各製品にスケジュール割り当ての優先順位を付与させる手順と、
優先順位の高い製品を１つ選び出し、入力された指定周期で作成されたスケジュール表に製品の加工順序に従って工程を割り当て、機械を使用する時間帯が既に同じ機械が使用されている時間帯と重複する場合は、機械競合が回避されるように既に使用されている時間帯と重複しないスケジュールに調整させ、機械競合が生じず対象工程がボトルネック機械を使用する場合は、ボトルネック機械を使用する時間帯を連続させてボトルネック機械に複数の遊休時間帯を作らないようにさせ、全ての優先順位の製品についてスケジューリングを行って指定周期の繰返しスケジュールを計画させる手順と、
スケジュールの計画結果を表示させ、表示させたスケジュールについて、複数の中から選択できたり修正又は／及び編集が行えるようにする手順と、
をコンピュータに実行させることを特徴とする繰返し型生産ラインのスケジュール作成プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ジョブ・ショップの繰返し生産を対象にし、最短の繰返し周期を算出するアルゴリズム、及び指定周期の繰返しスケジュールを計画するアルゴリズムを用いて、計算機（コンピュータ）上で繰返しスケジュールを自動的に作成する方法及び装置、並びに上記の繰返しスケジュールをコンピュータに作成させるプログラムを記録した記録媒体に関するものである。
【０００２】
【従来の技術】
同一種の部品を繰返し生産するラインのスケジューリングについて、フロー・ショップにおける繰返し生産では、最短の繰返し周期をボトルネック機械の総使用時間で決定できる。なお、ボトルネック機械とは、機械別の使用時間総計（各機械で処理するすべての作業時間の和）が最も多い機械である。
そこで、ジョブが最初の工程で加工され始めてから、最終工程で加工が終了するまでを１サイクルとして、ボトルネック機械がフル稼動する１サイクルのスケジュールを考え、それを最短周期で繰返すことで、周期最短の繰返しスケジュールを立てることができる。
しかし、ジョブ・ショップの繰返し生産では、前後のサイクルのスケジュールと機械資源の競合が起こる可能性があるため、上述のようなアプローチを採ることができない。
【０００３】
現在のところ、ジョブ・ショップの繰返し生産を対象とするスケジューリング・ソフトで周期的なスケジュールを生成するものは市販されていない。また、研究レベルでは、ジョブ・ショップの繰返しスケジュール作成を扱ったものがあるが、１製品の加工中にボトルネック機械を使用する回数が１回の場合に限定されている。
例えば、「ボトルネック機械に遊休時間を作らないジョブ・ショップ・スケジューリングに関する研究」（日本経営工学会平成６年度春季大会予稿集、第１６８頁〜第１６９頁）では、ジョブ・ショップの繰返しスケジュール作成問題に対し、機械別負荷時間が最も長いボトルネック機械に遊休時間を作らないスケジュール作成方法を提案し、考察している。具体的なスケジュールの作成方法は、あらかじめ指定したジョブ数の分だけ、先にボトルネック機械を使用する作業のスケジュールを遊休時間を作らないように割り当てた後、ボトルネック機械より前、後の工程を様々な方法（優先順位を決定する方法）で割り当てるようにしている。
【０００４】
【発明が解決しようとする課題】
上述したように、現在、ジョブ・ショップの繰返し生産を対象とする市販スケジューリング・ソフトで周期的なスケジュールを生成するものはなく、仮に繰返し生産のある１つのジョブ集合のみを対象として市販ソフトでスケジューリングし、その結果を周期的に繰返したとしても、その周期が最短となっている保証がないために生産効率の向上は期待できない。
また、ジョブ・ショップの繰返しスケジュール作成問題を扱った上記の研究では、繰返しスケジュールも作成できるが、周期的なものではなく、あらかじめ指定したジョブ数のみを考えており、また、ボトルネック機械より前、後という条件があるから、１製品の加工中にボトルネック機械を使用する回数が１回だけに限定される。したがって、ボトルネック機械が複数回使用される計画問題では、上記の研究の手法は適用できない。さらに、上記の研究では、ボトルネック機械が複数回使用される場合について、ボトルネック機械に遊休時間を作らないことが繰返し周期を最短化することに等価であるという考察がなされていない。
【０００５】
本発明は上記の諸点に鑑みなされたもので、本発明の目的は、ジョブ・ショップの繰返し生産を対象にし、最短の繰返し周期を算出するアルゴリズム、及び指定周期の繰返しスケジュールを計画するアルゴリズムを用いて、計算機（コンピュータ）上で繰返しスケジュールを自動的に作成することにより、各製品間及び各工程間に生じる加工順序による順序制約を満たし、かつ、機械競合が生じるのを回避することができ、ボトルネック機械を使用する回数に関係なくジョブ・ショップの繰返しスケジュールを周期を指定して計画することが可能となる繰返し型生産ラインのスケジュール作成方法及び装置、並びに上記の繰返しスケジュールをコンピュータに作成させるプログラムを記録した記録媒体を提供することにある。
【０００６】
【課題を解決するための手段】
上記の目的を達成するために、本発明の繰返し型生産ラインのスケジュール作成方法は、ジョブ・ショップの繰返し生産におけるスケジュールを計算機上で自動的に作成する方法であって、製品に関するデータ及び加工工程に関するデータをデータ入力手段に入力する工程、最短周期演算手段により、１つのジョブ集合を加工するときの機械別使用時間総計を求めて機械別使用時間総計の最大値を最短の繰返し周期として算出する工程、最短の繰返し周期以上の時間幅をもつ任意の周期を指定周期として指定周期入力手段に入力する工程、スケジュール割り当て優先順位演算手段により、各製品間及び各工程間に生じる加工順序による順序制約を満たすように、各製品をその加工の順序に従って並べて階層別にグルーピングを行い、各グループに含まれる製品のあらゆる順列とグループの加工順序との組み合せから各製品にスケジュール割り当ての優先順位を付与する工程、繰返しスケジュール計画手段により、優先順位の高い製品を１つ選び出し、入力された指定周期で作成されたスケジュール表に製品の加工順序に従って工程を割り当て、機械を使用する時間帯が既に同じ機械が使用されている時間帯と重複する場合は、機械競合を回避するように既に使用されている時間帯と重複しないスケジュールに調整し、機械競合が生じず対象工程がボトルネック機械を使用する場合は、ボトルネック機械を使用する時間帯を連続させてボトルネック機械に複数の遊休時間帯を作らないようにし、全ての優先順位の製品についてスケジューリングを行って指定周期の繰返しスケジュールを計画する工程、計画結果表示・修正手段により、スケジュールの計画結果を表示し、表示されたスケジュールについて、複数の中から選択したり修正又は／及び編集を行う工程を含むように構成されている（図１〜図１０参照）。
【０００７】
本発明の繰返し型生産ラインのスケジュール作成装置は、ジョブ・ショップの繰返し生産におけるスケジュールを作成する装置であって、製品に関するデータ及び加工工程に関するデータを入力するデータ入力手段と、１つのジョブ集合を加工するときの機械別使用時間総計を求めて機械別使用時間総計の最大値を最短の繰返し周期として算出する最短周期演算手段と、最短の繰返し周期以上の時間幅をもつ任意の周期を指定周期として入力する指定周期入力手段と、各製品間及び各工程間に生じる加工順序による順序制約を満たすように、各製品をその加工の順序に従って並べて階層別にグルーピングを行い、各グループに含まれる製品のあらゆる順列とグループの加工順序との組み合せから各製品にスケジュール割り当ての優先順位を付与するスケジュール割り当て優先順位演算手段と、優先順位の高い製品を１つ選び出し、入力された指定周期で作成されたスケジュール表に製品の加工順序に従って工程を割り当て、機械を使用する時間帯が既に同じ機械が使用されている時間帯と重複する場合は、機械競合を回避するように既に使用されている時間帯と重複しないスケジュールに調整し、機械競合が生じず対象工程がボトルネック機械を使用する場合は、ボトルネック機械を使用する時間帯を連続させてボトルネック機械に複数の遊休時間帯を作らないようにし、全ての優先順位の製品についてスケジューリングを行って指定周期の繰返しスケジュールを計画する繰返しスケジュール計画手段と、スケジュールの計画結果を表示し、表示されたスケジュールについて、複数の中から選択したり修正又は／及び編集を行う計画結果表示・修正手段とを備えたことを特徴としている（図１〜図１０参照）。
【０００８】
本発明の繰返し型生産ラインのスケジュール作成プログラムを記録した記録媒体は、ジョブ・ショップの繰返し生産におけるスケジュールを作成するためのプログラムを記録した記録媒体であって、製品に関するデータ及び加工工程に関するデータが入力される手順と、１つのジョブ集合を加工するときの機械別使用時間総計を求めて機械別使用時間総計の最大値を最短の繰返し周期として算出させる手順と、最短の繰返し周期以上の時間幅をもつ任意の周期が指定周期として入力される手順と、各製品間及び各工程間に生じる加工順序による順序制約が満たされるように、各製品をその加工の順序に従って並べて階層別にグルーピングを行わせ、各グループに含まれる製品のあらゆる順列とグループの加工順序との組み合せから各製品にスケジュール割り当ての優先順位を付与させる手順と、優先順位の高い製品を１つ選び出し、入力された指定周期で作成されたスケジュール表に製品の加工順序に従って工程を割り当て、機械を使用する時間帯が既に同じ機械が使用されている時間帯と重複する場合は、機械競合が回避されるように既に使用されている時間帯と重複しないスケジュールに調整させ、機械競合が生じず対象工程がボトルネック機械を使用する場合は、ボトルネック機械を使用する時間帯を連続させてボトルネック機械に複数の遊休時間帯を作らないようにさせ、全ての優先順位の製品についてスケジューリングを行って指定周期の繰返しスケジュールを計画させる手順と、スケジュールの計画結果を表示させ、表示させたスケジュールについて、複数の中から選択できたり修正又は／及び編集が行えるようにする手順とをコンピュータに実行させることを特徴としている。
【０００９】
【発明の実施の形態】
以下、本発明の実施の形態について説明するが、本発明は下記の実施の形態に何ら限定されるものではなく、適宜変更して実施することが可能なものである。図１は、本発明の実施の形態による繰返し型生産ラインのスケジュール作成装置の概略構成を示している。本実施の形態は、ジョブ・ショップの繰返し生産におけるスケジュールについて、最短の繰返し周期を算出するアルゴリズム、及び指定周期の繰返しスケジュールを計画するアルゴリズムを組み込んだ繰返しスケジュール自動作成システムである。図１に示す構成においては、以下の手順でスケジュールを計画する。
【００１０】
（１）  ユーザから、対象問題の製品に関するデータ（製品名称、製品の加工順序等）、工程に関するデータ（工程名称、工程の加工順序、加工時間、使用機械等）などの入力を受け付ける。製品に関するデータ及び工程に関するデータ等のデータは、データ入力部１０から入力され、後述する（２）、（４）、（５）の処理に用いられる。
（２）  最短周期演算部１２で、図２に従って、対象問題の最短周期を計算し、これをユーザに提示する。図２に示すように、１つのジョブ集合を加工するときの機械別使用時間総計を求め、機械別使用時間総計の最大値を最短の繰返し周期とする。また、この値をとる機械をボトルネック機械と呼ぶ。すなわち、１つのジョブ集合を加工するときのボトルネック機械の総使用時間が最短の繰返し周期である。
（３）  ユーザから、（２）で決定した最短周期以上の値を、求める繰返しスケジュールの周期として受け付ける。ユーザが指定した指定周期は指定周期入力部１４に入力され、後述する（４）、（５）の処理で、指定周期の繰返しスケジュールが計画できる。なお、（２）で求めた最短周期の繰返しスケジュールを計画することも勿論可能である。
【００１１】
（４）  スケジュール割り当て優先順位演算部１６では、図３に従って、製品にスケジュールを割り当てる優先順位を導出する。すなわち、図４のように、各製品をその加工の順序に従って並べ、階層別にグルーピングを行う。ここで、図４において、製品ａ→製品ｂは、製品ｂの加工に製品ａを使用することを意味する。このとき、製品ａは製品ｂの加工前に加工を終えている必要があり、製品ａを製品ｂの前製品と呼ぶ。このように、ジョブ・ショップの繰返し生産において、各製品間、各工程間に順序関係が生じる場合は、この順序制約を満たす優先順位をつける必要がある。
したがって、図３に示すように、上記の各グループに含まれる製品のあらゆる順列を考え、各グループ内の優先順位候補とした後、各グループの優先順位候補をグループの加工順に並べ、それらの組み合せをスケジュール割り当て優先順位とする。これにより、各製品に、順序制約を満たす優先順位をつけることができる。通常の場合、順序制約を満たす優先順位は複数通り考えられ、スケジュール割り当て優先順位演算部１６では、スケジュール割り当て優先順位リストが作成される。一例として、図４の場合では、製品３−１の前製品である製品２−１、製品２−２の加工順序が２通り、製品２−１の前製品である製品１−１、製品１−２、製品１−３の加工順序が６通りあるので、１２通りの優先順位が考えられる。
【００１２】
（５）  繰返しスケジュール計画部１８では、（４）で導出した優先順位から１つを選び出して、図６に従って繰返しスケジュールを計画し、（４）で決定した全ての優先順位について、スケジューリング結果が得られるまで（５）を繰り返す。以下、図６に示す繰返しスケジュール計画のアルゴリズムについて説明する。
まず、図５に示すような、（３）で指定した周期の幅をもつスケジュール表を作成し、各製品に対応するタイマ（初期値０）、カウンタ（初期値０）を用意する。割り当て優先順位から最も優先順位の高い製品を１つ選び出し、この製品のカウンタを、前製品のカウンタの最大値にセットする。また、タイマを、カウンタが最大値となる前製品のうち、タイマが最も進んだ値にセットする。ただし、製品に前製品がない場合には、カウンタ、タイマとも０とする。すなわち、図７に示すように、選び出した製品に前製品がある場合、前製品のカウンタの最大値を対象製品のカウンタ値としてリセットする。また、最大値をとる前製品を選び出し、選び出した前製品のタイマの最大値を対象製品のタイマ値としてリセットする。
【００１３】
つぎに、選び出した対象製品の加工順序リストから最も先に着手する工程を選び出し、工程が属する製品のタイマ値を作業開始時刻として仮のスケジュールを割り当てる。そして、工程が属する製品のタイマ値から作業を開始すると機械競合が生じる場合は、図８に示すように、既に機械が使用されている時間帯と重複しない作業開始時刻にタイマ値を調整し、機械競合が生じるのを回避する。この場合、タイマの調整幅が最小となるように調整する。また、機械競合が生じない場合で、工程がボトルネック機械を使用していて、既にボトルネック機械を使用する工程のスケジュールが割り当てられている場合は、図９に示すように、既にボトルネック機械が使用されている時間帯と連続する作業開始時刻にタイマ値を調整し、ボトルネック機械に遊休時間を作らないようにする。
【００１４】
以上のようにして割り当てたスケジュールが、スケジュール表の幅を超える場合は、図１０に示すように、スケジュール表の幅を超えた分だけスケジュールを折り返し、工程が属する製品のカウンタを１つ増加させる。ただし、スケジュールの折り返しをした時に、折り返した部分で上記の機械競合が起こる可能性があるので、この場合は、折り返される部分も含めて機械競合を回避するようにしなければならない。上記の問題は、現時点でのスケジュール表を２つ考え、一方の時刻Ｔ（周期）がもう一方の時刻０に重なるように並べて、機械競合が生じているかどうか判定したいスケジュールの作業開始時刻から時間幅Ｔの間で機械が同時に使用されていないかどうか調べるという手法で解決される。
そして、工程が属する製品のタイマをスケジュールの終了時刻に合わせた後、次に着手する工程を選び出して同じ手順を繰返し、全ての工程について１つの製品のスケジュールが計画できたら、次の優先順位の製品について、同様にスケジュールを計画し、全ての製品のスケジュールが得られるまで、以上の手順を繰返す。こうして得られたスケジュール表を並べて、指定周期の繰返しスケジュールとする。以上の操作を（４）で導出した全ての優先順位について行う。
【００１５】
（６）  計画結果表示・修正部２０では、（５）で得られた繰返しスケジュールの計画結果をガントチャート表示し、ユーザが、スケジュールの作業者負荷山積み図、機械別稼動率等を参考に、複数のスケジュールの中から最も理想的なスケジュールを選択する。さらに、ユーザが、選択したスケジュールを表示画面上で微調整して修正等を加えたり、画面上でスケジュールの編集を行ったりする。
【００１６】
【発明の効果】
本発明は上記のように構成されているので、つぎのような効果を奏する。
（１）  ジョブ・ショップの繰返し生産におけるスケジュール作成において、最短の繰返し周期を自動的に計算でき、かつ、指定周期の繰返しスケジュールを自動的に計画することができる。また、ユーザが、スケジュール計画結果の選択、修正又は／及び編集などを行うことができる。
（２）  ボトルネック機械が１製品の加工中に複数回使用される場合についても、ボトルネック機械に遊休時間を作らない、最短周期の繰返しスケジュールを計画することができる。
（３）  ボトルネック機械を使用する回数に関係なく、ジョブ・ショップの繰返しスケジュールを周期を指定して計画することが可能となる。
（４）  各製品間及び各工程間に生じる加工順序による順序制約を満たし、かつ、機械資源の競合が起こらない繰返しスケジュールを計画することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態による繰返し型生産ラインのスケジュール作成装置を示す概略構成図である。
【図２】図１において、最短周期を求めるアルゴリズムを示すフローチャートである。
【図３】図１において、スケジュール割り当ての優先順位を決定するアルゴリズムを示すフローチャートである。
【図４】図３において、製品のグルーピングの一例を示す構成図である。
【図５】指定周期Ｔの幅をもつスケジュール表を示す概略構成図（ガントチャート）である。
【図６】指定周期の繰返しスケジュールを計画するアルゴリズムを示すフローチャートである。
【図７】図６において、タイマ、カウンタのリセット方法を示すフローチャートである。
【図８】図６において、機械競合が生じる場合のスケジュール調整方法を説明するガントチャートである。
【図９】図６において、機械競合が生じず、かつ、既にボトルネック機械を使用する工程のスケジュールが割り当てられているときに、ボトルネック機械を使用する場合のスケジュール調整方法を説明するガントチャートである。
【図１０】図６において、スケジュール表の幅を超える場合のスケジュール決定方法を説明するガントチャートである。
【符号の説明】
１０  データ入力部
１２  最短周期演算部
１４  指定周期入力部
１６  スケジュール割り当て優先順位演算部
１８  繰返しスケジュール計画部
２０  計画結果表示・修正部
【図１】
0003568831.tif 000002
【図２】
0003568831.tif 000003
【図３】
0003568831.tif 000004
【図４】
0003568831.tif 000005
【図５】
0003568831.tif 000006
【図６】
0003568831.tif 000007
【図７】
0003568831.tif 000008
【図８】
0003568831.tif 000009
【図９】
0003568831.tif 000010
【図１０】
0003568831.tif 000011