(57)【要約】【課題】  スケジューリングやリスケジューリングを迅速に行うことができるスケジューリングシステムを提供する。【解決手段】  前の工程の作業が終わってから次の工程の作業を開始し、且つ各工程の作業を処理する資源が予め決まっている製造工程の生産計画を作成するスケジューリングシステムであって、複数の元注文の中から各資源毎にその資源で行う作業に関する情報を取り出して注文とし、その注文に基づいて各資源毎にスケジューリングを行うときに、各注文に含まれる作業すべてを生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、コース唯一性制約、最短切替時間制約、生産チャンス処理時間制約を用いて、混合整数計画問題として定式化し、この問題を解くことにより全体の生産計画を作成することを特徴とする。【選択図】        図１
2006048088.tif 000002
【特許請求の範囲】
【請求項１】
一の資源で行う作業に関する情報を有する注文に基づいて前記資源のスケジューリングを行うときに、前記資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
各注文に含まれる作業すべてを前記生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、
少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、
混合整数計画問題として定式化し、
この問題を解いて、各作業がどの生産チャンスに割り当てられるかを決め、また、各生産チャンスの開始時刻及び終了時刻を決め、最後に、各生産チャンス毎に任意の作業の順序を決めて前記資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成するスケジューリング手段とを備えることを特徴とするスケジューリングシステム。
【請求項２】
一の資源で行う作業に関する情報を有する注文に基づいて前記資源のスケジューリングを行うときに、前記資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
少なくとも、
各作業について、選択可能な生産チャンスごとに整数変数を用意し、各作業についていずれか一つの整数変数が１となり他の整数変数が０となるように制約し、
最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約し、
各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約して、
混合整数計画問題として定式化し、
この問題を解いて前記資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成するスケジューリング手段とを備えることを特徴とするスケジューリングシステム。
【請求項３】
複数の工程により製品を製造するときに前の工程の作業が終わってから次の工程の作業を開始し、且つ各工程の作業を処理する資源が予め決まっている製造工程の生産計画を作成するスケジューリングシステムであって、
少なくとも各製品毎にその製品の製造に必要な全ての工程の順序と各工程の作業の時間と利用される資源と資源の状態の切替発生要因の情報を有する元注文の情報等が記憶されている情報記憶手段と、
前記情報記憶手段が記憶する複数の元注文の情報の中から各資源毎に、各作業の順序性の情報を含むその資源で行う作業に関する情報を取り出して注文とする注文生成手段と、
前記注文生成手段が生成した注文に基づいて各資源毎にスケジューリングを行うときに、各資源毎に、各資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
各注文に含まれる作業すべてを前記生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、
少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、
混合整数計画問題として定式化し、
この問題を解いて、各作業がどの生産チャンスに割り当てられるかを決め、また、各生産チャンスの開始時刻及び終了時刻を決め、最後に、各生産チャンス毎に任意の作業の順序を決めて各資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成するスケジューリング手段とを備えることを特徴とするスケジューリングシステム。
【請求項４】
前記混合整数計画問題は、各注文ごとに、最初の作業が割り当てられる生産チャンスの開始時刻は与えられた時刻以降になるように制約（最早開始時刻制約）したことを特徴とする請求項１、２又は３記載のスケジューリングシステム。
【請求項５】
前記混合整数計画問題は、各注文ごとに、最後の作業が割り当てられる生産チャンスの終了時刻は与えられた時刻以前になるように制約（最遅終了始時刻制約）したことを特徴とする請求項１、２、３又は４記載のスケジューリングシステム。
【請求項６】
前記混合整数計画問題は、各生産チャンスに作業が割り当てられるか否かを表す変数であり、各生産チャンスごとに一つずつ割り当てられ、作業が一つでも割り当てられる場合１を、作業が一つも割り当てられない場合０を値として持つ変数（生産チャンス変数）を用いたことを特徴とする請求項１、２、３、４又は５記載のスケジューリングシステム。
【請求項７】
前記混合整数計画問題は、最後の生産チャンスの終了時刻の最小化を目的関数としたものであることを特徴とする請求項１、２、３、４、５又は６記載のスケジューリングシステム。
【請求項８】
前記混合整数計画問題は、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間に生じる待ち時間を、早い生産チャンスほど大きく、生産チャンスが一つ進むごとに与えられた一定の比率(rate)で減少していくという重み付けして足し合わせたものの最小化を目的関数としたものであることを特徴とする請求項６記載のスケジューリングシステム。
【請求項９】
前記変数（生産チャンス変数）を足し合わせたものを目的関数として最小化することを特徴とする請求項６記載のスケジューリングシステム。
【請求項１０】
前記混合整数計画問題は、納期の指定されている各注文ごとに、その注文の最後の作業の割り当てられる生産チャンスの終了時刻が、その作業よりあとで他の資源で処理される作業に見込まれる時間をその注文の納期から差し引いた時刻以前となるように制約（最遅終了時刻制約）したことを特徴とする請求項３記載のスケジューリングシステム。
【請求項１１】
前記スケジューリング手段は、作業時間のかかる資源から順次スケジューリングを行うことを特徴とする請求項３又は１０記載のスケジューリングシステム。
【請求項１２】
一の資源で行う作業に関する情報を有する注文に基づいて前記資源のスケジューリングを行うときに、前記資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
各注文に含まれる作業すべてを生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、
少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、
混合整数計画問題として定式化する手順と、
この問題を解いて前記資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成する手順と、
を備えることを特徴とするスケジューリング方法。
【請求項１３】
一の資源で行う作業に関する情報を有する注文に基づいて前記資源のスケジューリングを行うときに、前記資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
少なくとも、
各作業について、選択可能な生産チャンスごとに整数変数を用意し、各作業についていずれか一つの整数変数が１となり他の整数変数が０となるように制約し、
最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約し、
各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約して、
混合整数計画問題として定式化する手順と、
この問題を解いて、各作業がどの生産チャンスに割り当てられるかを決め、また、各生産チャンスの開始時刻及び終了時刻を決め、最後に、各生産チャンス毎に任意の作業の順序を決めて前記資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成する手順と、
を備えることを特徴とするスケジューリング方法。
【請求項１４】
複数の工程により製品を製造するときに前の工程の作業が終わってから次の工程の作業を開始し、且つ各工程の作業を処理する資源が予め決まっている製造工程の生産計画を作成するスケジューリング方法であって、
少なくとも各製品毎にその製品の製造に必要な全ての工程の順序と各工程の作業の時間と利用される資源と資源の状態の切替発生要因の情報を有する複数の元注文の中から各資源毎にその資源で行う作業に関する情報を取り出して注文とし、その注文に基づいて各資源毎にスケジューリングを行うときに、各資源毎に、各資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
各注文に含まれる作業すべてを生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、
少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、
混合整数計画問題として定式化する手順と、
この問題を解いて各資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成する手順と、
を備えることを特徴とするスケジューリング方法。
【請求項１５】
請求項１２、１３又は１４記載の手順を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理対象に対して複数の資源を用いて複数の処理を行う多工程の生産計画を作成するスケジューリングシステム及びスケジューリング方法に関する。
【背景技術】
【０００２】
従来から、例えば、電縫鋼管工場では、造管資源(設備)、口付資源、熱処理資源等を用いて各種の鋼管を製造している。係る電縫鋼管製造工程では、熟練した担当者が過去の実績と経験に基づいて、工場におけるスケジューリングをおこなっている。
【０００３】
また、従来から、生産工程のスケジューリングを行うための各種の生産管理方法が提案されている。
【０００４】
【特許文献１】特開平６−９００９６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の生産管理方法では、スケジューリングのためのアルゴリズムが複雑であるために、スケジューリングやリスケジューリングに時間がかかり、急ぎの注文が入ったり、一部の資源に処理対象がなかったりしたときに、迅速に対応することができないという問題があった。
【０００６】
また、例えば、電縫鋼管工場の熱処理資源の場合、熱処理の温度を変更するのに時間がかかるので、またエネルギー効率を良くする必要があるので、できるだけ同一処理条件の処理対象は、まとめて処理することが望ましい。先行技術としては、例えば特開平６−９００９６号は、電子部品の製造ラインにて、使用する機器の段取り替えを最適化するための技術が開示されている。できるだけ同じような作業をまとめて行なえるよう工夫が成されている。このように同じような作業をまとめるためのスケジューリング方法はいくつか提案されているが、未だスケジューリングの迅速化が望まれているのが現状である。
【０００７】
本発明は上記事情に基づいてなされたものであり、スケジューリングやリスケジューリングを迅速に行うことができるスケジューリングシステム及びスケジューリング方法を提供することを目的とする。
【０００８】
また、本発明は上記事情に基づいてなされたものであり、同一処理条件の処理対象はまとめて処理することができるスケジューリングシステム及びスケジューリング方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、請求項１に係る発明であるスケジューリングシステムは、一の資源で行う作業に関する情報を有する注文に基づいて前記資源のスケジューリングを行うときに、前記資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
各注文に含まれる作業すべてを前記生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、
少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、
混合整数計画問題として定式化し、
この問題を解いて、各作業がどの生産チャンスに割り当てられるかを決め、また、各生産チャンスの開始時刻及び終了時刻を決め、最後に、各生産チャンス毎に任意の作業の順序を決めて前記資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成するスケジューリング手段とを備えることを特徴とするものである。
【００１０】
上記の目的を達成するために、請求項２に係る発明であるスケジューリングシステムは、一の資源で行う作業に関する情報を有する注文に基づいて前記資源のスケジューリングを行うときに、前記資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
少なくとも、
各作業について、選択可能な生産チャンスごとに整数変数を用意し、各作業についていずれか一つの整数変数が１となり他の整数変数が０となるように制約し、
最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約し、
各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約して、
混合整数計画問題として定式化し、
この問題を解いて前記資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成するスケジューリング手段とを備えることを特徴とするものである。
【００１１】
上記の目的を達成するために、請求項３に係る発明であるスケジューリングシステムは、複数の工程により製品を製造するときに前の工程の作業が終わってから次の工程の作業を開始し、且つ各工程の作業を処理する資源が予め決まっている製造工程の生産計画を作成するスケジューリングシステムであって、
少なくとも各製品毎にその製品の製造に必要な全ての工程の順序と各工程の作業の時間と利用される資源と資源の状態の切替発生要因の情報を有する元注文の情報等が記憶されている情報記憶手段と、
前記情報記憶手段が記憶する複数の元注文の情報の中から各資源毎に、各作業の順序性の情報を含むその資源で行う作業に関する情報を取り出して注文とする注文生成手段と、
前記注文生成手段が生成した注文に基づいて各資源毎にスケジューリングを行うときに、各資源毎に、各資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
各注文に含まれる作業すべてを前記生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、
少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、
混合整数計画問題として定式化し、
この問題を解いて、各作業がどの生産チャンスに割り当てられるかを決め、また、各生産チャンスの開始時刻及び終了時刻を決め、最後に、各生産チャンス毎に任意の作業の順序を決めて各資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成するスケジューリング手段とを備えることを特徴とするものである。
【００１２】
上記の目的を達成するために、請求項１２に係る発明であるスケジューリング方法は、一の資源で行う作業に関する情報を有する注文に基づいて前記資源のスケジューリングを行うときに、前記資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
各注文に含まれる作業すべてを生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、
少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、
混合整数計画問題として定式化する手順と、
この問題を解いて前記資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成する手順と、
を備えることを特徴とするものである。
【００１３】
上記の目的を達成するために、請求項１３に係る発明であるスケジューリング方法は、一の資源で行う作業に関する情報を有する注文に基づいて前記資源のスケジューリングを行うときに、前記資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
少なくとも、
各作業について、選択可能な生産チャンスごとに整数変数を用意し、各作業についていずれか一つの整数変数が１となり他の整数変数が０となるように制約し、
最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約し、
各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約して、
混合整数計画問題として定式化する手順と、
この問題を解いて、各作業がどの生産チャンスに割り当てられるかを決め、また、各生産チャンスの開始時刻及び終了時刻を決め、最後に、各生産チャンス毎に任意の作業の順序を決めて前記資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成する手順と、
を備えることを特徴とするものである。
【００１４】
上記の目的を達成するために、請求項１４に係る発明であるスケジューリング方法は、複数の工程により製品を製造するときに前の工程の作業が終わってから次の工程の作業を開始し、且つ各工程の作業を処理する資源が予め決まっている製造工程の生産計画を作成するスケジューリング方法であって、
少なくとも各製品毎にその製品の製造に必要な全ての工程の順序と各工程の作業の時間と利用される資源と資源の状態の切替発生要因の情報を有する複数の元注文の中から各資源毎にその資源で行う作業に関する情報を取り出して注文とし、その注文に基づいて各資源毎にスケジューリングを行うときに、各資源毎に、各資源で行われる作業のうち切替時間で分割できる作業のまとまりを生産チャンスとして定め、
各注文に含まれる作業すべてを生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、
少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、
混合整数計画問題として定式化する手順と、
この問題を解いて各資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成する手順と、
を備えることを特徴とするものである。
【発明の効果】
【００１５】
以上説明したように、本発明によれば、多工程のスケジューリングの問題を、各資源ごとに分割した部分問題に分け、各部分問題の各モデルを混合整数計画問題として定式化して解くことにより、全体の解を求めるので、従来の複雑なアルゴリズムを用いた方法に比べて、求解時間の短縮化を図り、迅速なスケジューリング及びリスケジューリングを行うことができるスケジューリングシステム及びスケジューリング方法を提供することができる。
【００１６】
また、本発明によれば、なるべく生産チャンスの切替が発生しないようにしてエネルギー効率の向上を図ることができるスケジューリングを行うことができるスケジューリングシステム及びスケジューリング方法を提供することができる。
【発明を実施するための最良の形態】
【００１７】
以下に図面を参照して、本発明の一実施形態であるスケジューリングシステムについて説明する。図６は、本実施形態のスケジューリングシステムの概略ブロック図である。本実施形態のスケジューリングシステムは、図６に示すように、コンピュータ本体１０と、本実施形態のプログラムや元注文についてのデータ等が格納された外部記憶装置２１と、キーボードやマウス等の入力装置２２と、ＣＲＴ等の表示装置２３とを備えている。また、コンピュータ本体１０は、システム全体の制御を司るＣＰＵ１１と、ブートプログラムおよび各種データを不揮発的に格納するＲＯＭ１２と、ＣＰＵ１１の処理に利用される作業領域やデータの一時記憶領域として利用されるＲＡＭ１３と、インターフェイス１４〜１６とを備えている。
【００１８】
図７は、本実施形態のスケジューリングシステムの機能ブロック図である。本実施形態のスケジューリングシステムは、外部記憶装置２１が記憶する複数の元注文の情報の中から各資源毎に、各作業の順序性の情報を含むその資源で行う作業に関する情報を取り出して注文とする注文生成部３１と、注文生成部３１が生成した注文に基づいて各資源毎にスケジューリングを行うときに各資源毎に、各資源で行われる作業のうち作業の切替時間で分割できる作業のまとまりを生産チャンスとして定め、各注文に含まれる作業すべてを生産チャンスに割り当てる際における一つの割り当て方をコースとし、前記コースが採用されるか否かを表す整数変数を用い、少なくとも、各注文ごとに、その注文にかかわるコースの内、ただ一つが採用されるように制約(コース唯一性制約)し、最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上となるように制約（最短切替時間制約）し、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和とその生産チャンスの開始時刻を加えたものは、その生産チャンスの終了時刻に等しくなるように制約（生産チャンス処理時間制約）して、混合整数計画問題として定式化し、この問題を解いて各作業がどの生産チャンスに割り当てられるかを決め、また、各生産チャンスの開始時刻及び終了時刻を決め、最後に、各生産チャンス毎に任意の作業の順序を決めて各資源における各作業毎に作業の開始時刻及び終了時刻を決定することにより全体の生産計画を作成するスケジューリング部３２とを備えている。なお、生産チャンスについては、後述する。
【００１９】
以下では、上記の本実施形態のスケジューリングシステムを用いて、多くの作業工程を有する電縫鋼管工場のスケジューリングを行う場合について説明する。電縫鋼管工場のように多工程のスケジューリングを行う場合、全体を一つの問題として捉えると問題が複雑且つ大規模なものとなり、解くのに時間がかかる。そこで、本実施形態では、注文生成部３１により、問題全体を資源（各作業工程での装置や機械のことをいう。）ごとの注文に分割し、スケジューリング部３２により、各資源毎の部分問題として捉え、それぞれの部分問題を解くことにより全体の解を求めるという解法を用いている。そこで先ず、本発明で、全体の問題をどのような問題として捉えているかを説明する。次に、全体の問題をどのように部分問題に分けるかを説明する。更に、部分問題の解からどのようにして全体の解につなげるかを説明する。その後、部分問題用の各モデルについて説明する。
【００２０】
先ず、本発明で、全体の問題をどのような問題として捉えているかを説明する。図１は、電縫鋼管工場における元注文の作業工程を示すブロック図である。元注文(1)は、造管作業、口付作業、冷牽作業、熱処理作業（以下単に、熱作業という。）、矯正作業、ＮＤＩ作業、ＣＦ作業、出荷作業を含むものである。元注文(2)は、造管作業、口付作業、熱作業、冷牽作業、熱作業、矯正作業、ＮＤＩ作業、ＣＦ作業、出荷作業を含むものである。元注文(3)は、造管作業、口付作業、熱作業、冷牽作業、熱作業、矯正作業、ＣＦ作業、ＮＤＩ作業、ＣＦ作業、冷牽作業、熱作業、矯正作業、ＮＤＩ作業、ＣＦ作業、出荷作業を含むものである。造管作業は平板から管を造る作業、口付作業は管を引き延ばすときにつかう器具を管の両端に取り付ける作業、冷牽作業は常温の状態で管を引き延ばす作業、熱作業は処理対象を加熱処理する作業、矯正作業は管の撓み等直して形を整える作業、ＮＤＩ作業は非破壊検査作業、ＣＦ作業は切断処理作業である。
【００２１】
なお、元注文は、各製品毎にその製品の製造に必要な全ての工程の順序と各工程の作業の時間と利用される資源と資源の状態の切替発生要因（例えば、熱処理であれば、熱処理の処理温度の差をいう。）などの情報を有する。「元注文」の特徴は、複数の異なる資源に関わる作業の情報で構成される点である。本実施形態では、元注文と、後に詳述する注文とを区別している。「注文」の特徴は、ある特定の資源に関わる作業の情報のみで構成される点である。各元注文は、作業のリストで構成される。また、元注文のデータは、外部記憶装置２１に記憶されている。作業とは元注文の構成要素であり、各作業にはその作業を行う資源、作業時間、資源の状態の切替発生要因等のデータが与えられる。また、各資源では一種類の作業を行う。資源とは、作業が行われる装置や機械のことである。図１に示す注文(2)のように、熱作業21と熱作業22とがある場合、資源は同じでも作業は二つとなる。本実施形態の場合、造管作業、口付作業、冷牽作業、熱作業、矯正作業、ＮＤＩ作業、ＣＦ作業及び出荷作業を行うための資源が各々一台だけ配置されている場合を考える。したがって、複数の元注文に対して、例えば一つの熱資源を効率良く稼働させるために、どのようなスケジュールを組めば良いかが問題となる。また、工程として同じ種類に分類される場合でも、物理的に異なる装置である場合には、異なる資源とみなす。
【００２２】
スケジューリング部３２の求解対象は、各作業の開始時刻及び終了時刻である。すなわち、図１に示す電縫鋼管工場における各資源における各作業ごとの作業開始時刻及び作業終了時刻を決定することである。評価指標としては、材欠しないこと及びまとめ指向の二種類がある。材欠しないこととは、なるべく各資源で前面在庫がなくならないようにすることである。処理対象がなくなると、資源のスケジュールにあきができ、資源を効率よく稼働することができなくなるからである。まとめ指向とは、稼働条件が同じ処理対象はなるべくまとめて作業することである。すなわち、生産チャンスの切替がなるべく発生しないようにすることである。各資源で行われる作業には作業の切替時間が発生する。切替時間を発生させる要因としては複数のものがあるが、ここでは最も大きな切替時間を発生させる要因に注目し、その要因でおこる切替時間で分割してできる作業のまとまりを生産チャンスという。すなわち、生産チャンスとは、各資源で行われる作業のうち切替時間で分割できる作業のまとまりをいう。この生産チャンスは、後述する方法により、予め各資源毎に決めておく。したがって、まとめ指向というのは、例えば、熱資源での処理温度が９２０℃と６００℃の処理対象がある場合、９２０℃で処理する処理対象と６００℃で処理する処理対象とを交互に処理するのではなく、できるだけ９２０℃で処理する処理対象は連続して処理するようにして、生産チャンスの切替が発生しないようにすることを意味する。
【００２３】
ここで、上述した複数の要因には、たとえば熱処理の場合には温度と、加熱炉の中を動くコンベアの速度がある。つまり、連続する２つの作業の温度が異なる場合やコンベアの速度が異なる場合に、それらの作業の間に切替時間が発生する。しかし、温度が異なることに起因する切替時間に比較すれば、コンベアの速度が異なることに起因する切替時間は小さいため、温度が同じ一連の作業を一つの生産チャンスとし、連続する生産チャンス間の切替時間を、異なる温度の作業間の切替時間と等しいものとしている。同じ生産チャンスに含まれる、速度が異なる作業間の切替時間は、平均的な切替時間を各作業の時間（duration）に含めることによって処理している。また、例えばCF作業やNDI作業の場合は外径が最も大きな切替時間を発生させ、それ以外の要因による切替時間は外径に比較すれば小さい。したがって、CF作業やNDI作業の場合は生産チャンス間の切替時間を外径が異なる作業間の切替時間と等しいものとしている。
【００２４】
次に、主な制約について説明する。主な制約として、資源制約、先行制約及び切替制約の三つがある。資源制約とは、各作業を処理する資源は決まっていることをいう。先行制約とは、各元注文内の作業は、前の作業が終わってからでないと次の作業は開始できないことをいう。すなわち、各元注文内では、作業の手順を入れ換えることはできない。切替制約とは、同一資源で行われる作業の間には決められた切替時間を開けなければならないことをいう。すなわち、生産チャンスの切替を行う場合には、決められた切替時間をあけなければないないという制約である。なお、同一の稼働条件の下で処理される作業時間は、処理対象の入れ換えに要する時間も加味して作業時間が決められるので、同一の稼働条件の下では処理対象の入れ換えのための時間を考慮する必要はない。
【００２５】
次に、全体の問題をどのように部分問題に分けるかを説明する。図２は、全体の問題を部分問題に分割する方法を説明するための図である。まず、複数の元注文に含まれる複数の作業について、各資源ごとに分ける。[1]本実施形態では、このようにして分けた各資源ごとにスケジューリングを行う。対象となる資源は複数であるが、本実施形態では一つの資源を対象とするモデルを考え、このモデルを用いて資源ごとに、例えば熱資源ごとにスケジューリングを行う。[2]ネックとなる資源から順に解く。各資源ごとの作業時間を比較して作業時間の大きい資源から解く。図２に示す場合、資源１、資源２、資源３の順に作業時間が大きいことになり、したがって資源１から順に解く。本実施形態の場合、一番ネックとなるのは、熱資源である。[3]既に解いた資源における作業の開始時刻及び終了時刻を正、すなわち既に与えられている値とする。図２に示す場合、資源２のスケジューリングを行うときには、資源１での作業開始時刻及び終了時刻を考慮する。また、資源３のスケジューリングを行うときに、資源１及び資源２の作業開始時刻及び終了時刻を考慮する。[4]後で解く資源における作業に見込まれる平均的な作業時間をあけておく。図１の元注文(2)の熱作業22の作業時間を決めるときには、冷牽作業の作業時間をバッファとして確保した上で決めなければならない。
【００２６】
すなわち、部分問題に分割するには、まず、複数の元注文に含まれる複数の作業について、各資源ごとに分ける。次に、図２に示すように、先ず一番ネックとなる資源１について、分けられた複数の作業を各生産チャンスへ割り当てる。次に、各生産チャンス内の作業順序を決定する。作業の開始時刻は、もしその作業が同一生産チャンスに割り当てられている作業の中の最初の作業である場合は、生産チャンスの開始時刻と等しくする。生産チャンスの開始時刻は部分問題の変数として存在するため、求解成功時には値が決まっているはずである。作業の終了時刻は作業の開始時刻に処理時間を加えたものとする。また、同一生産チャンスに割り当てられている作業の中で先頭でない作業の開始時刻は直前の作業の終了時刻に切替時間を加えたものとする。同様にして資源２、資源３についても分けられた複数の作業を各生産チャンスに割り当て、各生産チャンス内の作業順序を決定する。
【００２７】
次に、部分問題用の各モデルについて説明する。まず、各モデルに共通の概念を説明する。ここで注文とは、元注文に関する情報の内、対象資源で行う作業に関する情報のみを取り出したものである。例えば、図1の場合、熱資源について複数の元注文のなかから、熱作業1、熱作業21、熱作業22、熱作業31、熱作業32及び熱作業33に関する情報を取り出したものを注文という。この注文には、処理の順序性の情報も含まれている。注文は、モデル中では一つの構造体Order で表現される。ここで、大文字で始まる単数の単語は構造体を表わす（以下、同様である）。構造体Orderは、属性値として、作業数、処理時間、前処理時間、後処理時間、納期等についての値を有する。作業数（nbActivities∈N）は、当該注文に含まれる作業の個数である。ここで、Nは、自然数の集合を表わし、nbで始まる複数形の単語は個数を表わす（以下、同様である）。処理時間(duration [a]∈R, a∈｛1, 2, ・・・, maxNbActivities｝)は作業(単数又は複数)の処理時間(単位は時間)である。a番目の作業の処理時間duration [a]は、Rの要素であり、aは集合｛1, 2, ・・・, maxNbActivities｝の要素である。但し、ここで、Rは実数の集合を表わし、小文字で始まる単数の単語は定数又は変数（配列を含む）を表わす（以下、同様である）。maxNbActivitiesは対象資源で行う一の作業の個数の上限とする。この値は対象資源によって異なり、例えば、熱資源の場合3、ＮＤＩ資源、ＣＦ資源の場合２となる。前処理時間(preProcess[a] ∈R, a∈｛1, 2, ・・・, maxNbActivities｝)のpreProcess[1]はスケジュール開始後、最初の作業が開始できるようになるまでの時間(単位は時間)であり、preProcess[2]は最初の作業終了後２番目の作業が開始できるようになるまでにあけておくべき時間(単位は時間)である。後処理時間(postProcess∈R)は、最後の作業の終了後に納期までの間に空けておくべき時間(単位は時間)である。納期(delivery∈R)は、スケジューリング開始時刻からの時間(単位は時間)によって指定する。納期が指定されていない注文については、この属性値を０とする。
【００２８】
次に、コースについて説明する。同じ注文中の作業の中に、対象資源で処理される作業が複数ある場合がある。このような場合に対象資源で処理される作業すべてに生産チャンスを割り当てる場合の一つの割り当て方をコースと呼ぶ。言い換えれば、各注文に含まれる作業すべてを生産チャンスに割り当てる際における、一つの割り当て方をコースという。一つの注文に対して複数のコースが存在しうるが、その内のちょうど一つのコースのみが採用される。本モデルにおいては、「一つの注文に対応するコースすべてのうち、どれか一つのみを選ぶ」ことによりスケジューリングが行われる。
【００２９】
次に、コースについて図３を参照して具体的に説明する。図３は熱資源についてのコースを説明するための図である。図３では、熱資源についての生産チャンスの枠が生産チャンス１から生産チャンス１１まである。この生産チャンスの順序枠は、予め注文内容を検討して、各生産チャンスを順序立てて並べたものである。生産チャンスの順序枠は各生産チャンスが一定の周期性（サイクル）をもって、一定の頻度で出現するように予め決定する。また、図３は、熱資源であるので、生産チャンスの順序枠は、熱資源のエネルギー効率を考慮して、処理温度の高い方から低い方に変化するように並べた。また、６００℃の生産チャンスは作業量が少ないので、他の温度の生産チャンスと比べて出現頻度が少なくなるように決めてある。生産チャンスの出現頻度は、処理量に応じて決定する。このようにして生産チャンスの順序枠は、各資源ごとに各資源に応じて決定される。しかしながら、ここでは各生産チャンスの処理時間までは決定されていない。各生産チャンスの処理時間は、全ての注文について割り付けが終了したときに決まるものである。
【００３０】
今、図３に示すように熱資源についての注文２が熱作業９２０℃と熱作業９２０℃と熱作業６００℃を有する場合、同図に示すように４つのコースが考えられる。コース４は、生産チャンス１と生産チャンス４と生産チャンス６を用いるものである。コース５は、生産チャンス１と生産チャンス４と生産チャンス９を用いるものである。コース６は生産チャンス１と生産チャンス７と生産チャンス９を用いるものである。コース７は生産チャンス４と生産チャンス７と生産チャンス９を用いるものである。この４つのコースのなかから、一つのコースを決めればよいこととなる。
【００３１】
次に、図４を参照して、複数のコースの中から、一つのコースを選ぶときの方法について説明する。図４は各注文毎に、どのコースが選ばれているのかを示す図である。各四角形は、一のコースを示している。また、各注文について、白い四角形は不採用となったコースであり、塗りつぶした四角形が選択されたコースである。例えば、図３の注文２の場合、コース６が選択され、コース４、コース５及びコース７は不採用とされたことを示している。このように、コースと言う概念を用いることにより、選択の範囲が極めて狭い範囲となると言う特徴がある。コースと言う概念を用いずに、生産チャンスの順序を決めると、図３の注文２の場合、初めの熱作業９２０℃について生産チャンスが３つ、次の熱作業９２０℃について生産チャンスが３つ、熱作業６００℃について生産チャンスが２つあるので、選択の範囲は単純に計算すれば３×３×２となり、合計１８個の中から一つを選ぶこととなる。したがって、選択作業が複雑になるとともに時間がかかる。これに対して、本発明のように、コースの概念を用いることにより、４通りのうちから、一つのコースを選べばよいので、選択作業を簡単且つ迅速に行うことができる。
【００３２】
次に、図５を参照してコースの選択の方法について説明する。各コースを０か１の値をとる整数変数（以下、コース変数という）に対応させることで、混合整数計画問題としてモデリングが可能となる。全てのコースについて、その採用不採用をコース変数の値によって表すことができる。例えば、図４に示す注文の場合、注文１は「０１０」、注文２は「００１０」、注文３は「１０」のように表すことができる。また、図３に示す注文２のコース４は図５の実線で示すコースとなり、コース６は図５の点線で示すコースとなる。注文２の場合、例えばコース４等の採用されなかったコースに含まれる作業の長さは、ゼロを乗ずるので、生産チャンスの長さの一部として組み込まれない。また、採用されたコース６に含まれる作業の長さは、１を乗ずるので、該当する生産チャンスの長さの一部として算入され、各生産チャンス（例えば、図５に示す生産チャンス１など）の長さが決まる。
【００３３】
［熱処理モデル］  以下では、熱資源を対象にして、式を参照して混合整数計画問題としてモデル化したものを説明する。熱資源を対象としたのは、作業の処理時間の合計の観点や、作業数の観点から最も求解が困難な資源であると考えたからである。まず、各モデルで使用する定数及び変数について説明する。定数としては、注文数（nbOrders∈N）、注文ＩＤの集合(Orders=｛1, 2, ・・・, nbOrders｝)、注文の配列(Order order[o], o∈Orders)、生産チャンス数(nbChances∈N)、生産チャンスＩＤの集合(Chances=｛1, 2, ・・・, nbChances｝)、生産チャンスＩＤの集合（最後の一つを除いたもの）(ChancesMinus=｛1, 2, ・・・, nbChances-1｝)、最短切替時間(transitionTime[ch]∈R, ch∈ChancesMinus)、最大スケジューリング時間(horizon∈R)、コース数(nbCourses∈N)、コースＩＤの集合(Courses=｛1, 2, ・・・, nbCourses｝)及びコースの配列(Course course[c], c∈Courses)がある。ここで、注文の配列というのは、注文を表現するための構造体Orderの配列をいう。実際に参照されるときは、集合Ordersの要素がこの配列のインデックスとして使われる。また、コース数はコースの個数のことである。ここでいうコースは特定の注文のみに対するコースではなく、すべての注文に対するコースを合わせたものである。コースの配列courseというのは、図４に示すコース１〜１９のコースを表現するための構造体Courseの配列である。構造体Courseは、当該コースと関連のある注文のＩＤ（order∈Orders）の値、当該コースと関連のある注文中の対象資源で処理する作業の個数を示す作業数(nbActivities∈N)の値及び当該コースが通る生産チャンスの並びである生産チャンスＩＤ(chance[a]∈Chances, a∈｛1, 2, ・・・, maxNbActivities｝)の値を属性値として有する。例えば、図３及び図４に示す注文２のコース５は、Course［５］＝｛ordar=2, nbActivities=3, chance［１］=1, chance［２］=4, chance［３］=9｝で示される。また、注文２の配列は、例えば、order[2] =｛nbActivities = 3,  duration[1] = 1.2,  duration[2] = 1.4,  duration[3] = 0.8,  preProcess[1] = 11.5,  preProcess[2] = 8.4,  preProcess[3] = 6.0,  postProcess = 12.1,  delivery = 240.0｝のように示される。ここで、大文字で始まる複数形の単語は集合を表わしている。実際に参照されるときは、集合Coursesの要素がこの配列のインデックスとして使われる。また、最大スケジューリング時間(horizon∈R)というのは、それまでに全てのスケジュールが完了することが確実な十分に大きな数値をいう。
【００３４】
次に、変数について説明する。変数には、コース変数、開始時刻変数、終了時刻変数がある。コース変数(x[c]∈｛0, 1｝, c∈Courses)は、コースごとに一つずつ割り当てられ、そのコースが採用されるか否かを表す変数である。採用される場合1を、採用されない場合0を値として持つ。開始時刻(startTime[ch]∈[0, horizon], ch∈Chances)は、その生産チャンスの開始時刻を表す変数であり、生産チャンスごとに割り当てられる。終了時刻変数(endTime[ch]∈[0, horizon], ch∈Chances)は、その生産チャンスの終了時刻を表す変数であり、生産チャンスごとに割り当てられる。
【００３５】
目的関数(minimize endTime[nbChances])は、最後の生産チャンスの終了時刻を最小化する（この部分は、請求項７に対応する）。本発明では、目的関数を与えている。この目的関数が最も小さくなる解を求めている。「最終生産チャンス終了時刻を最小化する」というのは、熱資源の場合のように、隙間があきそうに無い資源、即ち前面在庫がなくなってしまうと言うことを心配しなくてもよい資源に対して計画すればよい。前面在庫がなくなるおそれのあるＮＤＩ資源やＣＦ資源の目的関数については後述する。nbChancesは、生産チャンスの個数を表すものであり、1〜nbChancesまでの生産チャンスがあることを表している。
【００３６】
次に、各種の制約について説明する。ここでは、制約のモデル中における表現とそれに対応する説明を併記する形で説明する。モデル上の表現に現れる定数名や変数名は上述したものと同じである。
【００３７】
(1)最早開始時刻制約
最早開始時刻制約は、下記の式(1)で表わすことができる。
(∀o∈Orders, ∀c∈Courses)
o=course[c].order ⇒
order[o].preProcess[1]×x[c]≦startTime[course[c].chance[1]] ・・・(1)
最早開始時刻制約というのは、各注文ごとに、最初の作業が割り当てられる生産チャンスの開始時刻は与えられた時刻以降でなければならないという制約である。この時刻はその作業よりも前に他の資源で行われる作業の終了時刻に、それに続く他の資源で行われる作業の処理に見込まれる時間を加えたものである。
【００３８】
スケジューリングは、例えば今日の零時からのスケジュールを決める場合。図１に示す元注文(1)の造管は終わっているが、元注文(2)の造管は午後７時にならないと終わらないという場合がある。また、注文(3)は午後4時にならないと終わらない場合、熱作業に注目すると、この熱作業は、造管を考慮すると、どんなに早くても、ある一定時間以上より早く開始することはできない。このような開始時刻の制約がある。すなわち、実際に稼働している設備について、途中からスケジューリングを行う場合、係る制約を考慮する必要がある。これを制約式として表したものが式（1）である。
【００３９】
造管のスケジュールは、予め与えられているものとする。今、熱作業に注目すると、他の資源は造管資源のことであり、続く他の資源は口付資源や冷牽資源のことを意味する。熱作業のスケジューリングを行うときの最早開始時刻は、このように熱作業より前の処理の資源に制約される。例えば口付資源のスケジューリングの方が熱作業のスケジューリングよりも後に行われる場合、予め、口付のスケジュールを考慮して熱作業のスケジューリングを行うことを意味する。スケジューリングの順序は、ネックとなる資源(本実施形態の場合、熱資源)から行うので、そのスケジューリングの対象となる資源より、作業の順序が前の資源(口付資源や冷牽資源)のスケジュールを考慮してスケジューリングを行う必要がある。
【００４０】
一の熱作業で、複数の注文の熱作業を同時に行うことも可能である。できるだけ、一の熱作業に複数の注文の同じ条件の熱作業を当てはめて、スケジューリングすることが望ましい。
【００４１】
式(1)のstartTimeは、生産チャンス毎に用意された変数で、整数変数ではなく実数変数である。course[c].chance[1]は、あるコースc の一番目の作業の生産チャンスの番号を意味する。例えば、図３のコース４の一番目の作業が割り当てられる生産チャンスは生産チャンス1で、二番目の作業が割り当てられる生産チャンスは生産チャンス4で、三番目の作業が割り当てられる生産チャンスは生産チャンス6である。このなかの一番目の作業が割り当てられる生産チャンスの番号をstartTime の添え字（式(1)の［course[c].chance[1]］）として使用している。すなわち、各コースの一番目の作業が割り当てられる予定の生産チャンスの開始時刻を意味する。この開始時刻が左辺と等しいか大きくなければならない。
【００４２】
左辺に整数変数ｘがかかっているが、この整数変数x が０のときには、左辺は０となり、したがって右辺は０以上となる。なお、スケジューリングを行うときの基点となる時刻を０としている。したがって、０というのは、基点となる時刻に該当することになる。また、xが1のときには、最早開始時刻preProsessの時刻以後でなければならいということになる。したがって、この式は、当該コースが採用されていなければ、常に成立する式となり、制約式としては無いものと同じことになる。すなわち、０の場合でも、この式は無害なものとなる。x[c]のcによって特定されたコースによって、xの値は、そのコースが採用されていれば1となり、採用されていなければ０となる。各注文を変化させ、更に各注文について、その注文に属するコースを変化させている。最早開始時刻preProsessの値は、構造体Orderの配列orderの中に格納されている定数である。preProcess[1]は、スケジュール開始後、最初に作業が開始できるようになるまでの時間(単位は時間)である。したがって、order[o].preProcess[1]により、各orderに格納されている最早開始時刻を持ってきて、その値以上の値となるように開始時刻を制約している。したがって、式（1）は、各注文について、その注文に属する各コースを総なめにして、各コースの一番目の作業が割り当てられる生産チャンスはきまっているので、その生産チャンスの開始時刻は、注文によって決まっている最早開始時刻以降でなければならないことを意味している。例えば、図３のようにコースが決まると、一番目の作業が割り当てられる生産チャンスが、生産チャンス1、1、1、4のように、決まる。このようにして特定される生産チャンスの開始時刻は、そのコースが属する注文（図３に示す注文２）の最早開始時刻以後でなければならないという制約である。
【００４３】
また、この制約式（1）の一行目は、o∈Orders で、注文oを変化させて、c∈Coursesで、コースを変化させている。このときに、o=course[c].orderによって、その注文oに属するコースのみを対象とするようにしている。つまり、o∈Orders で、図４に示す注文1〜5のどれかを選んで、c∈Coursesでコースを選んでいる。
【００４４】
各注文1〜5は、それぞれ作業数、処理時間、前処理時間、後処理時間等のデータを、例えば構造体形式で持っている。order[o]は、注文を一つずつ動かしていることになる。配列というのは、このような構造体が配列されていることを意味している。
【００４５】
(2)最遅終了時刻制約
最遅終了時刻制約は、下記の式(2)で表わすことができる。
(∀o∈Orders, ∀c∈Courses)
o=course[c].order ∧ order[o].delivery＞0 ⇒
endTime[course[c].chance[order[o].nbActivities]]≦
x[c]×(order[o].delivery-order[o].postProcess-horizon)+horizon・・・(2)
（ただし、deliveryは納期である。）
最遅終了時刻制約というのは、納期の指定されている各注文ごとに、その注文の最後の作業の割り当てられる生産チャンスの終了時刻は、その作業よりあとで他の資源で処理される作業に見込まれる時間をその注文の納期から差し引いた時刻以前でなければならないという制約である。
【００４６】
制約式(2)のendTimeは、各生産チャンスの終了時刻を表すものであり、各生産チャンス毎に割り当てられている。(2)の最下行の項 x[c]×(order[o].delivery-order[o].postProcess-horizon)+horizonは、xが1のときには、括弧がとれて、horizonが消えてorder[o].delivery-order[o].postProcessとなる。したがって、終了時刻に後処理時間を加えた値が納期以前とならなければならない。postProcessは、各注文毎に、最後の作業の終了後、納期までの間に開けておくべき時間である。postProcessは、各注文毎に、且つ各資源毎に予め決められており、各注文の中に予め情報として格納されている。図1の元注文(3)に基づいて具体的に説明する。今、熱作業に着目すると、最後の熱作業の終了時点から、出荷までに見込まれる時間がpostProcessとなる。すなわち、納期からpostProcessを引いたものが、熱作業が終了していなければならないendTimeとなる。このようにpostProcessは、例えば熱作業の場合、その後の矯正作業、ＮＤＩ作業、ＣＦ作業を考慮して設定される。また、ｘが0の場合、括弧の中が0になり、endTimeは、horizon以前であればよいことなる。
【００４７】
つまり、式(2)の
x[c]×(order[o].delivery-order[o].postProcess-horizon)+horizonは、納期の指定されている各注文ごとに、その注文の最後の作業の割り当てられる生産チャンスの終了時刻(endTime)は、その作業よりあとで他の資源で処理される作業に見込まれる時間をその注文の納期から差し引いた時刻以前におこなわなければならないことを表している。最後の作業であるＣＦ作業の終了時刻だけなく、各作業ごとに、endTimeを管理する必要があるので、このように、各作業ごとに、endTimeを考慮している。式(2)の上2行は、各注文の各コース毎に、納期deliveryが0でないものについて処理するためのものである。納期がないものは、deliveryが0になっている。したがって、order[o].delivery>0により、納期が0より大きいものだけが次の行の式の対象となる。
【００４８】
(3)生産チャンス処理時間制約
生産チャンス処理時間制約は、下記の式(3)で表わすことができる。
(∀ch∈Chances)
startTime[ch]+
Σ(c∈Courses, o∈Orders, a∈｛1, 2, ・・・, order[o].nbActivities｝:
course[c].chance[a]=ch ∧ o=course[c].order)
(order[o].duration[a]×x[c])
=endTime[ch]  ・・・(3)
生産チャンス処理時間制約というのは、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間の和とその生産チャンスの開始時刻を加えたものが、その生産チャンスの終了時刻に等しいという制約である。
【００４９】
(∀ch∈Chances)は、各生産チャンスの式が並立してある事を示している。２行目以下の式は、その内の一つに着目した式である。ここで、c∈Coursesは、全てのコースの中から任意のコースを取り出すことを意味する。startTimeは、各生産チャンスの開始時刻、endTimeは各生産チャンスの終了時刻である。図５に示すSTが生産チャンス１のstartTimeであり、この値は予め決まっている。各生産チャンス毎に当該生産チャンスに含まれている作業であって、かつその作業を含むコースのコース変数が１である作業の処理時間を加算した時間が当該生産チャンスの処理時間となる。
【００５０】
ある注文、例えば図３の注文２について、図３に示すようにコースが４〜７までできており、他の注文についても、対応するコースができたとする。今仮に、全てのコースが図４に示すように、１９できたとすると、まず生産チャンス1の処理時間を見積もりたい場合、全てのコースのうち生産チャンス１を通るものを選ぶ。これに基づき、生産チャンス１の処理時間を算出する。同様にして、各生産チャンス（図３に示す場合は、生産チャンス２〜１１）について、処理時間を算出する。
【００５１】
式（3）の2行目と3行目は、開始時刻startTimeにΣで各生産チャンスでかかる処理時間を合計したものを示すものである。この式において、Coursesはコースの番号の集合、Ordersは注文の番号の集合(例えば、図４の1〜5)、nbActivitiesは注文に含まれる作業数である。Orderは、元注文に関する情報の内、対象資源で行う作業に関する情報のみを取り出した構造体であり、この構造体Orderの属性の情報の一つに作業数(nbActivities∈N)がある。この作業数というのは、注文のなかにいくつの作業があるかを示すものである。したがって、熱作業について考えてみると、例えば図１の元注文(3)の場合は3、元注文(2)の場合は2、元注文(1)の場合は1となる。durationは、構造体Orderの属性の情報の一つであり、各作業における処理時間の情報である。例えば、図３注文２の熱作業920℃→熱作業920℃→熱作業600℃→の場合、３つある熱作業それぞれの処理時間の情報である。
【００５２】
Order  order[o], o∈Ordersの大文字のOrderは構造体の名前であり、小文字のorderは注文の数だけの配列を表している。
【００５３】
次に、o∈Orders, a∈｛1, 2, ・・・, order[o].nbActivities｝について説明する。これは小文字のorderのo番目のものドットのnbActivitiesというのは、o番目の注文の作業を１からその作業数nbActivitiesになるまで、aを変化させるものである。oは注文の番号に対応している。ｏとaのペアによって、どれか一つの作業を表現している。まず、o∈Ordersで注文の番号を変化させ、さらに熱作業の注文の場合、例えば図１に示す元注文(2)の熱作業の場合、作業数分、すなわち１〜２まで変化させる。つまり、例えば図1の元注文(2)の熱21の最初の数字2は、oを、２番目の数字1はaを表し、ｏとaのペアによってどれか一つの作業を表している。このようにして、注文と作業を変化させて、ある条件を満たす注文と作業のペアを特定する。
【００５４】
c∈Coursesは、全てのコースを総なめすることを表している。この全てのコースは、例えば図４の１〜１９までのコースを意味する。作業とコースをそれぞれ独立に変化させる。
【００５５】
course[c].chance[a]=ch ∧ o=course[c].orderは、上記のようにして、注文と作業とコースを変化させた後、どれをのこすかの条件を示している。各コースは、コースに含まれる作業毎に生産チャンスの番号を持っている。例えば図３の場合、生産チャンスの各四角形の枠の上に付した番号である。courseは、コースに関する情報が入っている構造体Courseの配列である。course[c]は、コースのc番目のものを持ってくることを意味する。course[c].chance[a]=chは、c番目のコースのa番目の作業の生産チャンスがch、即ち、今、注目している生産チャンスの番号であることを意味する。且つo=course[c].orderであること。o=course[c].orderは、注文も、c番目のコースが含まれる注文と一致していることを意味する。
【００５６】
次に、((order[c].duration[a]＋meanTransitionTime)×x[c]=endTime[ch]について説明する。変数ｘは、各コース毎に存在し、xの値は各コースが採用されるか否かを表す「１」か「０」の値となる。あるコースcが採用されるときには、x[c]の値が1、そのコースが採用されないときには、x[c]の値は0となる。例えば、図４の注文２に着目すると、４つのコースのうち、コース６のみ、即ちx[6]の値が1となり、注文2の他のコース、すなわちｘ[4]、x[5]、x[7]の値は0となる。これにより、コース６に対応する作業の作業時間が加算されることとなる。すなわち、選択されないコース４、コース５及びコース７の作業時間は加算されない。
【００５７】
Coursesは、コースの番号の集合を意味する。図４の場合は、1〜16という番号の集合を意味する。式の2行目のcourseは、コースの構造体の配列を意味し、図４の場合は各コースの上に付した番号であり、整数でインデックスとして1〜16番までを参照している。したがって、[c]のcは1〜16までの整数値をとる。
【００５８】
コースは、ある注文をどのように生産チャンスに割り振るかを表すものである。o=course[c].orderは、コースcがどの注文に属するかを示すものである。この場合のoは、o∈Ordersのoであり、したがって、o=course[c].orderは、注文番号oについてのコースしか考慮しないことを意味する。Σの2行目の条件は、1行目で注文のoを変化させているが、今、着目している注文o についてのコースだけに絞り込み、更にそのコースのa番目の作業の生産チャンスが今注目している生産チャンスであるものを選んでいる。すなわち、c∈Coursesは、コース1〜16のうちの一つを選ぶものである。o∈Orders, a∈｛1, 2, ・・・, order[o].nbActivities｝は、図1に示す熱作業11〜熱作業33のうちのどれか一つを選んでいる。
【００５９】
course[c].chance[a]=chは、図 ３の１〜１１までの各生産チャンスごとに、その生産チャンスを通っているコースを選ぶ。すなわち、全コースのうち、生産チャンス１を通るコースを選び出し、そのコースに対する0或いは1の変数とそのコースが何番目の作業として通っているかによって、その作業時間が決まり、掛け合わせたものを足している。つまり、生産チャンスを一つ選び、その生産チャンスを通る全てのコースを選択して、これに作業時間を掛けものを足している。これにより終了時刻が算出される。
【００６０】
(4)コース唯一性制約
コース唯一制約は、下記の式(4)で表わすことができる。
(∀o∈Orders)
Σ(c∈Courses: course[c].order = o) x[c] = 1  ・・・  (4)
コース唯一性制約というのは、各注文ごとに、その注文にかかわるコースの内ちょうど一つが採用されなければいけないという制約である。式(1)は、注文にかかわるコースのうちただ一つが１で、他の全ては０であるという制約である。すなわち、すべて０であってもいけないし、１が二つあってもいけない。各注文毎にコースは、どれか一つ選択されていなければならないし、二つ以上選択されていてはいけないし、選択されるコースが０であってもいけないという要請を満足するものでなければならない。例えば、図３の注文２の場合、コース1〜4のどれか一つでなければならないことを意味する。但し、この段階では、どれか一つのコースが最終的に選択されたわけではない。
【００６１】
(5)平均工期制約
平均工期制約は、下記の式(5)で表わすことができる。
(∀c∈Courses, ∀o∈Orders, ∀a∈｛1, 2, ・・・, order[o].nbActivities-1｝
o=course[c].order ⇒
endTime[course[c].chance[a]]+order[o].preProcess[a+1]×x[c]
≦endTime[course[c].chance[a+1]]  ・・・  (5)
各注文ごとに、ある作業が割り当てられる生産チャンスの終了時刻とそれにつづく作業が割り当てられる生産チャンスの終了時刻の間隔は与えられた時間だけ離れていなければならない。この時間間隔は2つの作業の間に他の資源において行われるべき作業に見込まれる時間である。
【００６２】
(6)最短切替時間制約
最短切替時間制約は、下記の式(6)で表わすことができる。
(∀ch∈ChancesMinus)
ch≠nbChances/2 ⇒
endTime[ch]+transitionTime[ch]≦startTime[ch+1]
(∀ch∈ChancesMinus) 
ch=nbChances/2 ⇒
endTime[ch]+transitionTime[ch]≦startTime[ch+1]・・・  (6)
最短切替時間制約というのは、最後の生産チャンスを除く各生産チャンスについて、その次の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上なければならないという制約である。
【００６３】
本実施形態では、コースという概念を用いたことにより、ｘという整数変数の個数が少なくなり、また、0・1の変数とすることにより、制約式(3)が表現できるようになった。また、他の種々の制約式がｘの一次式として表現できるようなった。本実施形態では、このようにコースという新しい概念を用いているので、整数変数の個数が少なくなるが、コースの概念を用いないと、整数変数の個数が多くなり、計算に時間がかかる。
【００６４】
［ＮＤＩ、ＣＦモデル］  次に、ＮＤＩ資源或いはＣＦ資源を対象にして、混合整数計画問題としてモデル化したものを式を参照して説明する。まず、各モデルで使用する定数及び変数について説明する。定数としては、注文数（nbOrders∈N）、注文IDの集合(Orders=｛1, 2, ・・・, nbOrders｝)、注文の配列(Order order[o], o∈Orders)、生産チャンス数(nbChances∈N)、生産チャンスIDの集合(Chances=｛1, 2, ・・・, nbChances｝)、生産チャンスIDの集合（最後の一つを除いたもの）(ChancesMinus=｛1, 2, ・・・, nbChances-1｝)、コース数(nbCourses∈N)、コースIDの集合(Courses=｛1, 2, ・・・, nbCourses｝)、コースの配列(Course course[c], c∈Courses)、最短切替時間(minTransitionTime[ch]∈R, ch∈ChancesMinus)、最大切替時間(maxTransitionTime∈R)、平均切替時間(meanTransitionTime∈R)、最大スケジューリング時間(horizon∈R)、重み率(weightRatio∈R)がある。注文の配列(Order order[o], o∈Orders)は、注文を表現するための構造体Orderの配列であり、実際に参照されるときは、集合Ordersの要素がこの配列のインデックスとして使われる。コース数(nbCourses∈N)は、コースの個数であり、ここでいうコースは特定の注文のみに対するコースではなく、すべての注文に対するコースを合わせたものである。コースの配列(Course course[c], c∈Courses)は、コースを表現するための構造体Courseの配列であり、実際に参照されるときは、集合Coursesの要素がこの配列のインデックスとして使われる。最短切替時間(minTransitionTime[ch]∈R, ch∈ChancesMinus)は、各生産チャンスごと（ただし最後の一つを除く）に、次の生産チャンスとの間で最低限あけなければいけない切替時間をいう。最大切替時間(maxTransitionTime∈R)は、生産チャンス間の切替時間としてこれ以上の値をとることはないと思われる値をいう。平均切替時間(meanTransitionTime∈R)は、同一の生産チャンスに割り振られた作業の間で見込まれる平均的な切替時間をいう。最大スケジューリング時間(horizon∈R)は、スケジューリング時間の上限値。すべての生産チャンスがこの時刻までには終了することが明らかとなる程度に十分に大きな値である。重み率(weightRatio∈R)は、目的関数として、各生産チャンスの純粋な待ち時間を重み付けして足し合わせたものを用いているが、隣接する生産チャンスとの間の重みの比率としてこの値が用いられる。つまり、ある生産チャンスの重みをwとすると、その次の生産チャンスの重みをw×weightRatioとする。
【００６５】
次に、変数について説明する。変数には、コース変数、開始時刻変数、終了時刻変数、生産チャンス変数がある。コース変数 (x [c]∈｛0, 1｝ , c∈Courses)は、そのコースが採用されるか否かを表す変数であり、コースごとに一つずつ割り当てられている。採用される場合１を、採用されない場合０を値として持つ。開始時刻変数(startTime[ch]∈[0, horizon], ch∈Chances)は、その生産チャンスの開始時刻を表す変数であり、各生産チャンスごとに割り当てられる。終了時刻変数(endTime[ch]∈[0, horizon], ch∈Chances)は、その生産チャンスの終了時刻を表す変数であり、各生産チャンスごとに割り当てられる。生産チャンス変数(b[ch]∈｛0, 1｝, ch∈Chances)は、その生産チャンスに作業が割り当てられるか否かを表す変数であり、各生産チャンスごとに一つずつ割り当てられる。作業が一つでも割り当てられる場合１を、作業が一つも割り当てられない場合０を値として持つ。このような生産チャンス変数を用いることにより、切替時間自体をこの生産チャンス変数bを掛けたものとしてあつかう。例えば、間にある生産チャンスが抜け落ちている場合、一つも作業が割り当てられていない場合、ほっておくと、二つの最短切替時間を両方足してしまう問題が生じる。熱作業の場合は問題とならない。切替時間が温度差に比例しているので。例えば、920℃から900℃、850℃と落とす場合、20度と50度に分けて落とす場合、それぞれの切替時間を足してものであってもよいし、一度に70℃に落とす場合と切替時間は同じになる。しかしながら、ＮＤＩ作業やＣＦ作業の場合は、切替時間は、一律、切替ごとに、例えば1時間となる。この場合、間に一つも割り当てのない生産チャンスがあると、切替時間が2 倍になったり、3倍になったりするので、これを防ぐために、生産チャンス変数を取り入れている。割り当てが一個でもあるか無いかを示す生産チャンス変数を導入して、この生産チャンス変数と最短切替時間を掛けたものを切替時間としてあける。生産チャンス変数が0の場合、この切替時間を考えなく良いようにしている。最短切替時間制約の制約式にこの生産チャンス変数bが反映されている。
【００６６】
次に、目的関数
minimize Σ(ch∈ChancesMinus)
weightRatioch
×(startTime[ch+1]-endTime[ch]-minTransitionTime[ch]×b[ch+1]))
について説明する。このモデルには線形の目的関数がただ一つ存在する。最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間に生じる待ち時間を重み付けして足し合わせたものを最小化する（この部分は、請求項８に対応するものである）。重み付けの際の重みは早い生産チャンスほど大きく、生産チャンスが一つ進むごとにその重みは与えられた一定の比率(weightRatio)で減少していく。待ち時間は前の生産チャンスとの間の切替時間から、最短の切替時間を差し引いたものである。また、作業の割り当てられない生産チャンスについては足し合わせることがないようにする。
【００６７】
次に、制約について説明する。ここでは、制約モデル中における表現とそれに対応する説明を併記する形で説明する。モデル上の表現に現れる定数名や変数名は上記のものと同じである。
【００６８】
(1)第一生産チャンス非空制約
第一生産チャンス非空制約は、下式で表わすことができる。
【００６９】
b[1]=1
第一生産チャンス非空制約は、第一生産チャンスには必ず作業が割り当てられなければならないという制約である。
【００７０】
(2)コース唯一性制約
コース唯一制約は、下式で表わすことができる。
(∀o∈Orders)
Σ(c∈Courses: course[c].order=o)x[c]=1
コース唯一性制約は、各注文ごとに、その注文にかかわるコースの内ちょうど一つが採用されなければいけないという制約である。
【００７１】
(3)平均工期制約
平均工期制約は、下式で表わすことができる。
(∀c∈Courses, ∀o∈Orders, ∀a∈｛1, 2, ・・・, order[o].nbActivities-1｝)
o=course[c].order ⇒
endTime[course[c].chance[a]]+order[o].preProcess[a+1]×x[c]
≦endTime[course[c].chance[a+1]]
平均工期制約は、各注文ごとに、ある作業が割り当てられる生産チャンスの終了時刻とそれにつづく作業が割り当てられる生産チャンスの終了時刻の間隔は与えられた時間だけ離れていなければならないという制約である。この時間間隔は２つの作業の間に他の資源において行われるべき作業に見込まれる時間である。
【００７２】
(4)最早開始時刻制約
最早開始時刻制約は、下式で表わすことかできる。
(∀c∈Courses, ∀o∈Orders)
o=course[c].order ⇒
order[o].preProcess[1]×x[c]≦startTime[course[c].chance[1]]
最早開始時刻制約は、各注文ごとに、最初の作業が割り当てられる生産チャンスの開始時刻は与えられた時刻以降でなければならないという制約である。この時刻はその作業よりも前に他の資源で行われる作業の終了時刻に、それに続く他の資源で行われる作業の処理に見込まれる時間を加えたものである。
【００７３】
(5)最遅終了時刻制約
最遅終了時刻制約は、下式で表わすことができる。
(∀c∈Courses, ∀o∈Orders)
o=course[c].order ∧ order[o].delivery＞0 ⇒
endTime[course[c].chance[order[o].nbActivities]]
≦x[c]×(order[o].delivery-order[o].postProcess-horizon)+horizon
最遅終了時刻制約は、納期の指定されている各注文ごとに、その注文の最後の作業の割り当てられる生産チャンスの終了時刻が、その作業よりあとでほかの資源で処理される作業に見込まれる時間をその注文の納期から差し引いた時刻以前でなければならないという制約である。
【００７４】
(6)初期生産チャンス非待機制約
初期生産チャンス非待機制約は、下式で表わすことかできる。
startTime[1]=0
初期生産チャンス非待機制約は、最初の生産チャンスの前に待ち時間があってはならないという制約をいう。
【００７５】
(7)最短切替時間制約
最短切替時間制約は、下式で表わすことができる。
(∀ch∈ChancesMinus)
startTime[ch+1]-endTime[ch]≧minTransitionTime[ch]×b[ch+1]
最短切替時間制約は、最初の生産チャンスを除く各生産チャンスについて、もしその生産チャンスに割り当てられる作業が存在する場合は、その前の生産チャンスとの間の切替時間は与件として与えられる最短切替時間以上なければならないという制約をいう。
【００７６】
(8)切替時間０制約
切替時間０制約は、下式で表わすことができる。
(∀ch∈ChancesMinus)
startTime[ch+1]-endTime[ch]≦maxTransitionTime×b[ch+1]
切替時間０制約は、最初の生産チャンスを除く各生産チャンスについて、もしその生産チャンスに割り当てられる作業が存在しない場合は、前の生産チャンスとの間の切替時間は０でなければならないという制約である。
【００７７】
(9)生産チャンス処理時間制約
生産チャンス処理時間制約は、下式で表わすことができる。
(∀ch∈Chances)
startTime[ch]+
Σ(c∈Courses, o∈Orders, a∈｛1, 2, ・・・, order[o].nbActivities｝:
course[c].chance[a]=ch ∧ o=course[c].order)
((order[o].duration[a]+meanTransitionTime)×x[c])
=endTime[ch]
生産チャンス処理時間制約は、各生産チャンスについて、その生産チャンスに割り当てられるすべての作業の作業時間と平均切替時間の和の合計とその生産チャンスの開始時刻を加えたものが、その生産チャンスの終了時刻に等しいという制約をいう。
【００７８】
(10)生産チャンス作業割り当て整合性制約１
生産チャンス作業割り当て整合性制約１は、下式で表わすことができる。
(∀ch∈Chances)
Σ(c∈Courses, a∈｛1, 2, ・・・, course[c].nbActivities｝: course[c].chance[a]=ch) x[c]
≧b[ch]
生産チャンス作業割り当て整合性制約１は、各生産チャンスについて、その生産チャンスに割り当てられる作業が存在するならば、その生産チャンスを通るコースが少なくとも一つ存在するという制約である。言い換えると、その生産チャンスを通るコースが存在しないならば、その生産チャンスに割り当てられる作業は存在しない。
【００７９】
(11)生産チャンス作業割り当て整合性制約２
生産チャンス作業割り当て整合性制約２は、下式で表わすことができる。
(∀ch∈Chances)
(∀c∈Courses, ∀a∈｛1, 2, ・・・, course[c].nbActivities｝) 
course[c].chance[a]=ch ⇒ x[c]≦b[ch]
生産チャンス作業割り当て整合性制約２は、各生産チャンスについて、もしその生産チャンスを通るコースが存在するならば、その生産チャンスに割り当てられる作業が存在するという制約である。言い換えると、もしその生産チャンスに割り当てられる作業が存在しないならば、その生産チャンスを通るコースは存在しない。
【００８０】
なお、上の実施形態では、熱資源、ＮＤＩ資源及びＣＦ資源について、説明したが、他の資源についても同様に、種々の制約を満足する式をコース変数ｘの一次式としてモデリングすることができる。
【００８１】
［実施形態の効果］  上記の本実施形態では、電縫鋼管工場のスケジューリングを、具体的には、熱作業、ＮＤＩ作業及びＣＦ作業について、作業の生産チャンスへの割り当て問題ととらえ、コース変数ｘを用いて各種の制約を一次の制約式として与え、最後の生産チャンスの終了時刻の最小化等を目的関数とした混合整数計画問題として定式化した。かかる混合整数計画問題を解くことにより、各作業がどの生産チャンスに割り当てられるかと、各生産チャンスの開始時刻及び終了時刻が決まる。最後に、各生産チャンス毎に、その生産チャンスに割り当てられている作業の順序を任意に決めることにより、各作業の開始時刻及び終了時刻が決まる。本実施形態のスケジューリングシステムは整数変数を用いた簡単な制約式や目的関数の形で表現されており、複雑なアルゴリズムは用いていないので、例えば、組み合わせ最適化問題等と比較して求解時間の短縮化を図ることができる。すなわち、混合整数計画問題とすることにより、線型の問題に特有な求解エンジンを使用することができ、組み合わせ最適化問題等を解くよりも求解時間を短縮することができる。また、本実施形態によれば、同じ資源を何回も繰り返して使用してものを生産する工程を有する場合でも、最適な解を迅速に得ることができる。
【００８２】
本実施形態のスケジューリングシステムは、毎日、スケジューリングすることを前提にしており、また、計画どおりに作業が実行されていない場合に、簡単にリスケジューリングを行うことができる。また、本実施形態のスケジューリングシステムでは、まとめ指向、すなわち、なるべく生産チャンスの切替が発生しないようにしてスケジューリングを行っている。このまとめ指向は、熱資源だけでなく、注文に応じてローラを交換しなければならい圧延資源等にも有効である。
【００８３】
［他の実施形態］  また、本発明は、上記の実施形態に限定されるものではなく、その要旨の範囲内において種々の変形が可能である。例えば、上記の部分問題用のモデルでは、各種の制約式を使用したが、この制約式は少なくともコース唯一性制約、最短切替時間制約及び生産チャンス処理時間制約があればよく、資源によっては他の制約式は省略することが可能である。
【００８４】
また、上記の実施形態では、目的関数が最後の生産チャンスの終了時刻を最小化するものである場合、或いは目的関数が最初の生産チャンスを除く各生産チャンスについて、その前の生産チャンスとの間に生じる待ち時間を重み付けして足し合わせたものを最小化するものである場合について説明したが、本発明は、これらに限定されるものではなく、生産チャンス変数を足し合わせたものを目的関数として最小化するようにしてもよい。これにより利用する生産チャンスの個数を少なくし、ひいてはまとめ指向を実現することができる。
【００８５】
また、本発明は、スケジューリングを作業の生産チャンスへの割り当て問題として捉えたことで、コース変数を使用しなくても混合整数計画問題としてモデル化することができる。例えば、図３の注文２の最初の作業９２０℃について、生産チャンスの１、４又は８が選択可能であり、次の作業９２０℃についても同様に生産チャンスの１、４又は８が選択可能であり、次の作業６００℃について生産チャンス７と１１とが選択可能である。この対応する生産チャンス毎に一つの整数変数を用意する。これにより、最初の作業９２０℃のうちの3つの整数変数の内のいずれか一つが１となり、他は0となる。次の作業９２０℃についても同様に３つの整数変数のうち、いずれか一つが1となり、他は0となる。次に、作業６００℃についても、２つの整数変数のいずれかが1となり、他は0となる。これにより、３×３×２＝１８通りの式ができるが、この問題を解くことができる。熱資源以外の資源についても同様にして問題を解くことができる。
【００８６】
また、本実施形態のスケジューリングシステムは、ラインが枝分かれしていたり集合したりしない製造ラインであれば、電縫鋼管の製造ラインだけでなく、他の製造ラインにも適用することができる。また、上記の実施形態では、元注文によって、作業内容が異なる場合について説明したが、本発明は各元注文の作業内容が同じ場合にも適用することができる。
【００８７】
また、上記の本実施形態では、複数の資源がある場合のスケジューリングについて説明したが、本発明はこれに限定されるものではなく、一の資源のスケジューリングを行うものであってもよい。
【００８８】
また、以上に説明した実施形態は、コンピュータのＣＰＵあるいはＭＰＵ、ＲＡＭ、ＲＯＭ等で構成されるものであり、ＲＡＭやＲＯＭ等に記録されたプログラムが動作することによって実現できる。したがって、コンピュータが上記機能を果たすように動作させるプログラムを記録媒体に記録し、コンピュータに読み取らせることによっても実現できるものである。記録媒体としては、ＣＤ−ＲＯＭ、ＤＶＤ、フレキシブル・ディスク、ハードディスク、磁気テープ、光磁気テープ、不揮発性のメモリカード等を用いることができる。
【００８９】
また、コンピュータがプログラムを実行し処理を行なうことにより、上述の実施形態が実現されるプログラムプロダクトは、本発明の実施形態に含まれる。上記プログラムプロダクトとしては、上述の実施形態の機能を実現するプログラム自体、上記プログラムが読み込まれたコンピュータ、ネットワークを介して通信可能に接続されたコンピュータに上記プログラムを提供可能な送信装置、および当該送信装置を備えるネットワークシステム等がある。
【００９０】
また、コンピュータが供給されたプログラムを実行することにより上述の実施形態の機能が実現されるだけでなく、そのプログラムコードがコンピュータにおいて稼働しているＯＳ（オペレーティングシステム）あるいは他のアプリケーションソフト等と共同して上述の実施形態の機能が実現される場合にもかかるプログラムコードは本発明の実施形態に含まれる。
【産業上の利用可能性】
【００９１】
以上説明したように、多工程のスケジューリングの問題を、各資源ごとに分割した部分問題に分け、各部分問題の各モデルを混合整数計画問題として定式化して解くことにより、全体の解を求めるので、従来の複雑なアルゴリズムを用いた方法に比べて、求解時間の短縮化を図り、迅速なスケジューリング及びリスケジューリングを行うことができる。したがって、本発明は、例えば各種の作業工程を有する電縫鋼管の製造工程に適用することができる。
【図面の簡単な説明】
【００９２】
【図１】図１は、電縫鋼管工場における注文の作業工程を示すブロック図である。
【図２】図２は、全体の問題を部分問題に分割する方法を説明するための図である。
【図３】図３は熱資源についてのコースを説明するための図である。
【図４】図４は各注文毎に、どのコースが選ばれているのかを示す図である。
【図５】図５はコースを説明するための図である。
【図６】図６は本実施形態のスケジューリングシステムの概略ブロック図である。
【図７】図７は本実施形態のスケジューリングシステムの機能ブロック図である。
【符号の説明】
【００９３】
１１：ＣＰＵ、  １２：ＲＯＭ、  １３：ＲＡＭ、  １４〜１６：インターフェイス、  ２１：外部記憶装置、  ２２：入力装置、  ２３：表示装置、  ３１：注文生成部、  ３２：スケジューリング部、  ＮＤＩ： 非破壊検査作業、  ＣＦ： 切断作業
【図１】
2006048088.tif 000003
【図２】
2006048088.tif 000004
【図３】
2006048088.tif 000005
【図４】
2006048088.tif 000006
【図５】
2006048088.tif 000007
【図６】
2006048088.tif 000008
【図７】
2006048088.tif 000009