(57)【特許請求の範囲】
【請求項１】
各利用分割母材に引き当てる各製品の条数又は前記各利用分割母材のカッティングパターンの何れか一方、並びに、一又は複数の母材の分割数を変数として含み、前記変数への値の割り当て方の組合せの集合から成る解空間の解探索処理を行う解探索処理手段を有し、
前記解探索処理手段は、前記解空間の解探索処理において、前記各利用分割母材に引き当てられる前記各製品の合計幅が該当する母材の幅以下である旨の制約条件を充足する値を前記変数に割り当てるとともに、前記解探索処理手段は、最小生産注文日数を前記変数として更に含み、初期情報に含まれる所定の最小生産注文日数の最大日数の値を初めに割り当て、次いで、割り当てる値を減少させる方向で前記最小生産注文日数へ値を割り当て、前記最小生産注文日数に該当する制約条件を最初に充足する値に決定し、且つ、前記最小生産注文日数までの前記各製品の出荷予定量の累積値が該当する製品の条数の合計値以下である旨の制約条件を充足する値を前記変数に割り当てることを特徴とする情報処理装置。
【請求項２】
前記解探索処理手段は、前記利用分割母材の総数である合計利用分割母材数を前記変数として更に含み、割り当てる値を増加させる方向で前記合計利用分割母材数への値の割り当てを行うことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記解探索処理手段は、更に、前記合計利用分割母材数の後に前記最小生産注文日数への値の割り当てを行うことを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記解探索処理手段は、最大生産注文日数を前記変数として更に含み、前記初期条件に含まれる所定の最大生産注文日数の最小日数の値を初めに割り当て、次いで、割り当てる値を増加させる方向で前記最大生産注文日数への値の割り当てを行い、前記最大生産注文日数に該当する制約条件を最初に充足する値に決定し、且つ、前記最大生産注文日数までの前記各製品の出荷予定量の累積値が該当する製品の条数の合計値以上である旨の制約条件を充足する値を前記変数に割り当てることを特徴とする請求項１又は２に記載の情報処理装置。
【請求項５】
前記解探索処理手段は、最大生産注文日数を前記変数として更に含み、割り当てる値を増加させる方向で前記最大生産注文日数への値の割り当てを行い、且つ、前記最大生産注文日数までの前記各製品の出荷予定量の累積値が該当する製品の条数の合計値以上である旨の制約条件を充足する値を前記変数に割り当て、更に、前記合計利用分割母材数及び前記最小生産注文日数の後に、前記最大生産注文日数への値の割り当てを行うことを特徴とする請求項２又は３に記載の情報処理装置。
【請求項６】
前記解探索処理手段は、条数変数又はカッティングパターン変数以外の少なくとも前記最小生産注文日数を含む変数に先に値を割り当て、前記値を先に割り当てられた変数を固定した上で、利用分割母材に対する製品の面積歩留りが最も大きい値をとるように前記条数変数又は前記カッティングパターン変数の値を変化させることを特徴とする請求項１乃至５の何れか１項に記載の情報処理装置。
【請求項７】
面積歩留りを目的関数とし、前記目的関数の値が与えられた閾値を越える或いは与えられた時間を経過するまで前記目的関数の値が高い解の探索を続ける最適解検出手段を更に有することを特徴とする請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項８】
情報処理装置による情報処理方法であって、
各利用分割母材に引き当てる各製品の条数又は前記各利用分割母材のカッティングパターンの何れか一方、並びに、一又は複数の母材の分割数を変数として含み、前記変数への値の割り当て方の組合せの集合から成る解空間の解探索処理を実行する際に、前記各利用分割母材に引き当てられる前記各製品の合計幅が該当する母材の幅以下である旨の制約条件を充足する値を前記変数に割り当てるとともに、最小生産注文日数を前記変数として含み、初期情報に含まれる所定の最小生産注文日数の最大日数の値を初めに割り当て、次いで、割り当てる値を減少させる方向で前記最小生産注文日数へ値を割り当て、前記最小生産注文日数に該当する制約条件を最初に充足する値に決定し、且つ、前記最小生産注文日数までの前記各製品の出荷予定量の累積値が該当する製品の条数の合計値以下である旨の制約条件を充足する値を前記変数に割り当てることを特徴とする情報処理方法。
【請求項９】
前記解探索処理は、前記利用分割母材の総数である合計利用分割母材数を前記変数として更に含み、割り当てる値を増加させる方向で前記合計利用分割母材数への値の割り当てを行うことを特徴とする請求項８に記載の情報処理方法。
【請求項１０】
前記解探索処理は、更に、前記合計利用分割母材数の後に最小生産注文日数への値の割り当てを行うことを特徴とする請求項９に記載の情報処理方法。
【請求項１１】
前記解探索処理は、最大生産注文日数を前記変数として更に含み、前記初期条件に含まれる所定の最大生産注文日数の最小日数の値を初めに割り当て、次いで、割り当てる値を増加させる方向で前記最大生産注文日数への値の割り当てを行い、前記最大生産注文日数に該当する制約条件を最初に充足する値を決定し、且つ、前記最大生産注文日数までの前記各製品の出荷予定量の累積値が該当する製品の条数の合計値以上である旨の制約条件を充足する値を前記変数に割り当てることを特徴とする請求項８又は９に記載の情報処理方法。
【請求項１２】
前記解探索処理は、最大生産注文日数を前記変数として更に含み、割り当てる値を増加させる方向で前記最大生産注文日数への値の割り当てを行い、且つ、前記最大生産注文日数までの前記各製品の出荷予定量の累積値が該当する製品の条数の合計値以上である旨の制約条件を充足する値を前記変数に割り当て、更に、前記合計利用分割母材数及び前記最小生産注文日数の後に、前記最大生産注文日数への値の割り当てを行うことを特徴とする請求項９又は１０に記載の情報処理方法。
【請求項１３】
前記解探索処理は、条数変数又はカッティングパターン変数以外の少なくとも前記最小生産注文日数を含む変数に先に値を割り当て、前記値を先に割り当てられた変数を固定した上で、利用分割母材に対する製品の面積歩留りが最も大きい値をとるように前記条数変数又は前記カッティングパターン変数の値を変化させることを特徴とする請求項８乃至１２の何れか１項に記載の情報処理方法。
【請求項１４】
面積歩留りを目的関数とし、前記目的関数の値が与えられた閾値を越える或いは与えられた時間を経過するまで前記目的関数の値が高い解の探索を続けることを特徴とする請求項８乃至１３の何れか１項に記載の情報処理方法。
【請求項１５】
請求項８乃至１４の何れか１項に記載の情報処理方法をコンピュータに実行させるためのプログラム。
【請求項１６】
請求項１乃至７の何れか１項に記載の情報処理装置の機能をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、変数への値の割り当て方の組合せから成る解空間から最適解を求める最適化問題を演算する技術に関するものである。
【背景技術】
【０００２】
従来、板状の鋼板（コイル状の鋼板を含む）（以下、単に製品と称す）の製造においては、図１３に示すように、コイル状の鋼板（以下、母材と称す）を切断装置（スリッタ）１２０３を用いて母材を幅方向に切断しながら、切断装置（レベラー）１２０１を用いて長手方向に切断して、最終的な製品Ｐ１〜Ｐ４を製造することが多い。尚、レベラーにより分割された母材の各部分１２０４を分割母材と呼ぶ。一方、切断の仕方を決定する過程においては、母材を切断装置（レベラー）１２０１を用いて長手方向に切断する仕方を先に決定した後に、切断装置（スリッタ）１２０３を用いて幅方向に切断する仕方を決定することが多い。
【０００３】
また、母材に製品を引き当てる際には、なるべく高い歩留りで製品が製造できるように計画されることが望ましい。例えば、特許文献１には、高い歩留りの製品引き当て計画を最適解として算出するものが開示されている。また、このような問題を解くアルゴリズムとして制約伝播技術が知られている。例えば非特許文献１に開示される制約伝播技術とは、制約充足問題（最適化問題を含む）の求解を行う際に、探索の効率を高めるための技術である。制約充足問題の求解中に、ある変数ｘのドメイン（取り得る値の集合）が縮小された時に、変数ｘを含む制約を介して他の変数ｙのドメインが縮小される。変数ｙを含む制約を介してさらに他の変数のドメインが縮小される。同様のことが次々と連鎖的に行われていく。たとえば、変数ｘ、ｙ、ｚがあり、夫々のドメインが｛１，２｝、｛１，２，…，１０｝、｛１，２，…，５｝であるとする。制約として、５ｘ＋ｙ≦１５（制約１）、ｙ≧２ｚ（制約２）が課されているとする。変数ｘのドメインが｛１，２｝から｛２｝へと変化したとき（つまりｘ＝２となったとき）、制約１を介してｙのドメインから６，７，８，９，１０が取り除かれてｙのドメインは｛１，２，…，１０｝から｛１，２，…，５｝へと変化する。さらに制約２を介して、ｚのドメインから３、４、５が取り除かれてｚのドメインは｛１，２，…，５｝から｛１，２｝へと変化する。制約伝播技術の効果として、上記のように制約を介してある変数のドメインが縮小されることに伴って他の変数のドメインが縮小されることによって、探索木の中で本来であれば探索される可能性のあった枝が刈り取られ、探索空間が縮小し、結果的に探索時間の短縮が期待される。
【０００４】
【特許文献１】特許第３０３９３４８号公報
【非特許文献１】草刈 君子、外３名、「最適化の基盤としての制約伝播技術の利用について」、２０００年１１月９日、（社）日本オペレーションズリサーチ学会第１２回ＲＡＭＰシンポジウム論文集、ｐ．５３−６０、インターネット＜URL: HYPERLINK "http://www.e-optimization.com/resources/uploads/RAMPdoc.pdf" http://www.e-optimization.com/resources/uploads/RAMPdoc.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に開示された発明は、製品の一つの母材のみを対象としており、複数の母材を対象とした製品の引き当て方法を算出することができない。従って、当日製品の引き当てに利用可能な母材が複数ある場合においても、複数の母材間にわたって高い歩留りを確保できる最適な製品の引き当て方法を決定することができず、製品の製造現場の実状に則した最適な製品引き当て方法を決定する上で未だ開発の余地を残すものであった。
【０００６】
従って、本発明は、複数の母材間に亘る製品の引き当て方法を決定することを可能とし、製品の製造現場の実状に則した製品引き当て方法を立案できる情報処理装置、情報処理方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
斯かる目的を達成するために、本発明の情報処理装置は、各利用分割母材に引き当てる各製品の条数又は前記各利用分割母材のカッティングパターンの何れか一方、並びに、一又は複数の母材の分割数を変数として含み、前記変数への値の割り当て方の組合せの集合から成る解空間の解探索処理を行う解探索処理手段を有し、前記解探索処理手段は、前記解空間の解探索処理において、前記各利用分割母材に引き当てられる前記各製品の合計幅が該当する母材の幅以下である旨の制約条件を充足する値を前記変数に割り当てるとともに、前記解探索処理手段は、最小生産注文日数を前記変数として更に含み、初期情報に含まれる所定の最小生産注文日数の最大日数の値を初めに割り当て、次いで、割り当てる値を減少させる方向で前記最小生産注文日数へ値を割り当て、前記最小生産注文日数に該当する制約条件を最初に充足する値に決定し、且つ、前記最小生産注文日数までの前記各製品の出荷予定量の累積値が該当する製品の条数の合計値以下である旨の制約条件を充足する値を前記変数に割り当てることを特徴とする。
【０００８】
本発明の情報処理方法は、情報処理装置による情報処理方法であって、各利用分割母材に引き当てる各製品の条数又は前記各利用分割母材のカッティングパターンの何れか一方、並びに、一又は複数の母材の分割数を変数として含み、前記変数への値の割り当て方の組合せの集合から成る解空間の解探索処理を実行する際に、前記各利用分割母材に引き当てられる前記各製品の合計幅が該当する母材の幅以下である旨の制約条件を充足する値を前記変数に割り当てるとともに、最小生産注文日数を前記変数として含み、初期情報に含まれる所定の最小生産注文日数の最大日数の値を初めに割り当て、次いで、割り当てる値を減少させる方向で前記最小生産注文日数へ値を割り当て、前記最小生産注文日数に該当する制約条件を最初に充足する値に決定し、且つ、前記最小生産注文日数までの前記各製品の出荷予定量の累積値が該当する製品の条数の合計値以下である旨の制約条件を充足する値を前記変数に割り当てることを特徴とする。
【０００９】
本発明のプログラムの第１の態様は、前記情報処理方法をコンピュータに実行させることを特徴とする。
【００１０】
本発明のプログラムの第２の態様は、前記情報処理装置の機能をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、複数の母材間に亘る製品の引き当て方法が求められ、製品の製造現場の実状に則した製品引き当て方法を決定することが可能となるとともに、変数（最小生産注文日数）を減少させる方向で解空間の探索処理を行うことにより、できるだけ最小生産注文日数が多い日数となり、それに伴い次回の製品の製造（切り出し作業）までできるだけ日数を空けられる解を検出することが可能となる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。以下の説明において「問題を解く」とは、「満たすべき制約を守りながら、問題中に現れる全ての変数について、変数への値の割り当て方を決定すること」である。つまり、全ての変数に対する値の割り当て方が１通り決まると、解が一つ求まったことになる。
【００１３】
図１は、本発明の一実施形態に係る情報処理装置の機能構成を示したブロック図である。
図１に示されるように、本実施形態に係る情報処理装置１００は、機能的な構成として、初期情報記憶部１０１、制約条件導出部１０２、解探索処理部１０３、最適解検出部１０４及び出力制御部１０５を備える。
【００１４】
初期情報記憶部１０１は、ユーザによりキーボード等の入力手段を用いて入力される初期情報を記憶する。この初期情報の具体例としては、例えば当日利用可能な母材の個数、各母材の幅や長さ、製造する製品の数、各製品の幅や各製品の長さの上限値及び下限値等が挙げられる。
【００１５】
制約条件導出部１０２は、初期情報記憶部１０１に記録される初期情報や後述する解探索処理部１０３の探索処理結果に基づいて、例えば、後述する制約条件（１）〜（２４）等のような種々の制約条件を導出する。解探索処理部１０３は、探索を行い、一部の変数について変数への値の割り当て方を決定し、決定された一部の変数への値の割り当て結果を最適解検出部１０４に渡す。
【００１６】
最適解検出部１０４は、解探索処理部１０３の探索結果である、一部の変数への値の割り当て結果に基づいて値が決まっていない変数について、所定の目的関数の値が最も大きくなるような値の割り当て方を探索し、解探索処理部１０３において決定した変数への値の割り当て方と併せたものを最適解として検出する。出力制御部１０５は、最適解検出部１０４により検出された最適解を表示パネル等の出力手段を用いて出力させる。
【００１７】
図２は、本発明の一実施形態に係る情報処理装置１０１のシステム構成を示した図である。本実施形態に係る情報処理装置１０１は以下に説明するようにＰＣ（パーソナル・コンピュータ）等によって構成可能である。
【００１８】
２００は、ユニット間のデータ並びに制御情報を伝送する伝送路であるシステムバスである。情報処理装置の筐体内に存在する各ユニットはシステムバス２００によって接続される。以下、各ユニットについて説明する。中央処理装置（以下、ＣＰＵという）２０１は、本情報処理装置の各種制御および演算などを行い、図１の制約条件導出部１０２、解探索処理部１０３、最適解検出部１０４及び出力制御部１０５に相当する機能を担う。
【００１９】
ランダムアクセスメモリ（以下、ＲＡＭという）２０２は、ＣＰＵ２０１の主メモリとして、また実行プログラムの格納領域、プログラムの実行エリアならびにデータエリアとして機能する他、初期情報記憶部１０１に相当する機能を有する。読み取り専用メモリ（以下、ＲＯＭという）２０３は、情報処理装置内の各ユニットの制御を行う基本プログラム、すなわちＢＩＯＳ（Basic Input/Output System）や、本情報処理装置を稼働するために必要な情報などを記憶する。
【００２０】
データ入出力を行うユニット群（以下、単にＦＤＤという）２０４は、フレキシブルディスクやＣＤ−ＲＯＭなど、取り外し可能な外部記憶媒体のデータ入出力を行う。ネットワークインタフェース（以下、単にＮＥＴＩＦという）２０５は、後述するモデム２０６を介して外部ネットワークに接続し、または後述するＬＡＮ２０７に接続する。ＮＥＴＩＦ２０５は、ネットワークを介して情報処理装置間のデータ転送を行うための制御や接続状況の診断を行う。
【００２１】
モデム２０６は、外部ネットワークと本情報処理装置とを電話回線を介して接続するための機器であって、モデムやＩＳＤＮ接続用のターミナルアダプタを含む。ＬＡＮ２０７は、イーサネット（Ｒ）などのネットワークシステムである。本実施形態に係る情報処理装置は、モデム２０６又はＬＡＮ２０７上に接続されているルータやゲートウェイ等の通信機器を用いて外部ネットワークに接続し、外部装置とのデータの送受信を可能とする。
【００２２】
ビデオＲＡＭ（以下、ＶＲＡＭという）２０８は、後述するＣＲＴ２０９に表示する画像データを展開し、表示の制御を行う。ＣＲＴ２０９は、ディスプレイなどの表示装置である。このＣＲＴ２０９は、情報処理装置の内部に含む構成としても良いし、或いはその外部に接続した構成としても良い。
【００２３】
キーボードコントローラ（ＫＢＣ）２１０は、キーボード（ＫＢ）２１１およびマウス２１２からの入力信号を制御する。ＫＢ２１１は、情報処理装置の利用者が入力操作を行うためのキーボードである。マウス２１２は、情報処理装置の利用者が入力操作を行うためのポインティングデバイスである。このキーボード２１１及びマウス２１２は夫々、情報処理装置の内部に含む構成としても良いし、その外部に接続した構成といても良い。
【００２４】
ハードディスクドライブ（ＨＤＤ）２１３は、アプリケーションプログラムや各種データなどの保存に用いられる。アプリケーションプログラムとは、本実施形態に係る情報処理方法を本情報処理装置に実行させるためのソフトウェアプログラムのことをいう。外部ネットワーク等のデータの伝送媒体、ＣＤ−ＲＯＭ等のデータの記録媒体等を介して情報処理装置がアプリケーションプログラムを得る構成も本発明の技術的思想の範疇に含まれる。
【００２５】
コントローラ（ＩＯＣ）２１４は、外部に接続されるプリンタ（ＰＲＴ）２１５やスキャナ１１６等に対する情報の入出力制御を行うことを可能とする。また本図には示していないが、ＩＯＣ２１４は、プリンタ２１５やスキャナ２１６以外に、例えば、同様に外部に接続されるＨＤＤやＭＯドライブ等と情報の入出力制御を行うことが可能である。
【００２６】
図３は、母材に製品を引き当てた状態を模式的に示した図である。以下では、図３に示すように、当日利用可能な母材をＭj（j＝１，２，３，・・・，ｍ）、母材Ｍjを分割することにより得られる分割母材をＭjk（k＝１，２，３，・・・，ｎ）と表記する。また、図３中のＭjWは母材Ｍjの幅、ＭjLは母材Ｍjの長さ、ＰiWは製品Ｐiの幅を示している。
【００２７】
図１２は、変数（条数）は分割母材と製品の組に対して与えられていることを示す図である。分割母材Ｍjkに引き当てられる製品Ｐi（ｉ＝１，２，３，・・・，ｌ）の条数を表す変数をＰＭjkiと表記する。
【００２８】
図３では、母材Ｍ1については、切断装置であるレベラーを用いて母材Ｍ1を長手方向に２等分することにより、母材Ｍ1から２つの分割母材（Ｍ11、Ｍ12）が得られる状態を示し、母材Ｍ2については、同じくレベラーを用いて母材Ｍ2を長手方向に６等分することにより、母材Ｍ2から６つの分割母材（Ｍ21、Ｍ22、Ｍ23、Ｍ24、Ｍ25、Ｍ26）が得られる状態を示している。
【００２９】
また、本実施形態の解探索処理の過程の一断面においては、母材Ｍ1については、母材Ｍ1の全分割母材(Ｍ11、Ｍ12)が利用分割母材とされているため、分割母材Ｍ11、Ｍ12には夫々少なくとも一つの製品が引き当てられる。同じく、母材Ｍ2については、母材Ｍ2の分割母材のうちＭ21、Ｍ22、Ｍ23が利用分割母材とされているため、分割母材Ｍ21、Ｍ22、Ｍ23には夫々少なくとも一つの製品が引き当てられる。図３の例では、分割母材Ｍ11及び分割母材Ｍ12には夫々、製品Ｐ1が４条引き当てられており（ＰＭ111＝ＰＭ121＝４、ＰＭ112＝ＰＭ122＝０）、分割母材Ｍ21及び分割母材Ｍ22には製品Ｐ2が５条引き当てられ（ＰＭ211＝ＰＭ221＝０、ＰＭ212＝ＰＭ222＝５）、分割母材Ｍ23には、製品Ｐ1が１条、製品Ｐ2が３条引き当てられている（ＰＭ231＝１、ＰＭ232＝３）。
【００３０】
次に、本実施形態に係る情報処理装置の動作について説明する。
先ず、ユーザは、キーボード等の入力手段を用いて、本情報処理装置１００に対して初期情報を入力する。ここでいう初期情報には、既に説明したように、当日利用可能な母材の個数、各母材の幅及び長さ、製品種類、各製品の幅、製品の長さの上限値及び下限値、各製品の出荷予定情報等が含まれる。以下に本実施形態における初期情報の一部を具体的に示す。尚、製品Ｐ1、Ｐ2の長さの上限値及び下限値の代わりに、製品Ｐ1、Ｐ2をコイル状としたときの製品Ｐ1、Ｐ2の外径の最大値及び最小値を入力してもよい。この場合、製品Ｐ1、Ｐ2の厚み及び内径は一定の値をとることが前提となる。
・母材個数：２（Ｍ1、Ｍ2）
・Ｍ1の幅：１２００ｍｍ
・Ｍ1の長さ：３００ｍ
・Ｍ2の幅：１１００ｍｍ
・Ｍ2の長さ：６６０ｍ
・製品種類：２（Ｐ1、Ｐ2）
・Ｐ1の幅：３００ｍｍ
・Ｐ2の幅：２２０ｍｍ
・Ｐ1の長さの上限値：１５０ｍ
・Ｐ1の長さの下限値：１００ｍ
・Ｐ2の長さの上限値：１２０ｍ
・Ｐ2の長さの下限値：８０ｍ
【００３１】
図８は、出荷予定情報の一例を示した図である。図８に示した出荷予定情報上では、製品Ｐ1、Ｐ2の出荷予定日が定められている。即ち、製品Ｐ1については、当日(日数"０")には８本、１日後（日数"１"）には１本、２日後（日数"２"）には０本、３日後（日数"３"）には２本、４日後（日数"４"）には０本の出荷予定数量が定められており、また、製品Ｐ2については、当日(日数"０")には１２本、１日後（日数"１"）には０本、２日後（日数"２"）には３本、３日後（日数"３"）には０本、４日後（日数"４"）には０本の出荷予定数量が定められている。
【００３２】
続いて、初期情報記憶部１０１は、入力された初期情報を記憶する。次に、解探索処理部１０３は、分枝限定法による解探索処理を実行する。本解探索処理部１０３の解探索処理の対象となる解空間を図９及び図１０に示す。これらに示される解空間は探索木とも称される。本解探索処理では、図９及び図１０に示すように、次の（ａ）〜（ｊ）の変数順序で解探索を行う。
（ａ）合計利用分割母材数、（ｂ）母材Ｍ1の利用母材フラグ、（ｃ）母材Ｍ2の利用母材フラグ、（ｄ）母材Ｍ1の分割数、（ｅ）母材Ｍ2の分割数、（ｆ）母材Ｍ1の利用分割母材数、（ｇ）母材Ｍ2の利用分割母材数、（ｈ）最小生産注文日数、（ｉ）最大生産注文日数、（ｊ）条数
【００３３】
上記の各変数（ａ）〜（ｊ）は、事前に本情報処理装置１００に対して設定されるものであり、また、各変数の探索順序も優先順位に応じて本情報処理装置１００の解探索処理に対して設定されるものである。
【００３４】
続いて、解探索処理部１０３による制約充足問題の解法について説明する。図１１は、上記変数（ａ）〜（ｊ）、基準面積、利用面積及び歩留り等の変数と制約条件との関係を示した図であり、図１１中、各制約条件に対応付けて、制約条件中に現れる変数には丸印が記されている。本制約充足問題では、上記変数（ａ）〜（ｊ）及びその他の変数に対して図１１で示される制約条件がかけられた上で、上記変数（ａ）〜（ｊ）夫々に対して与えられたドメイン内の値を変数に割り当てることによって解を求める。
【００３５】
−合計利用分割母材数の決定−
次に、本実施形態に係る制約充足問題の解法を、図４〜図７のフローチャートを参照しながら説明する。図４〜図７は、本実施形態に係る情報処理装置の動作の流れを示したフローチャートである。
【００３６】
先ず、解探索処理部１０３は変数（合計利用分割母材数）の値を決定する。本実施形態においては、変数（合計利用分割母材数）について与えられたドメインのうち最も小さい値（＝１）を初めに設定し、次いで、値を増加させる方向で順次値を設定していく（ステップＳ４０１）。ここでは、いま、変数（合計利用分割母材数）の値として"５"が設定されているものとする。
【００３７】
本実施形態の解探索処理においては、上記のように、変数（合計利用分割母材数）に割り当てる値を増加させる方向で解探索処理を行っている。つまり、合計利用分割母材数が少ないところから解探索を行っていくことで、解が検出されると、その解は解空間の中で合計利用分割母材数ができるだけ少ない値をとる解になる。それに伴い製品在庫もできるだけ少なくする解を検出することが可能となる。
【００３８】
−利用母材の決定−
続いて、解探索処理部１０３は、当日利用可能な母材Ｍ1〜Ｍnから利用対象母材の最大インデックス値を決定する。利用対象母材の最大インデックス値に割り当てる値として１、２、・・・Ｍｎと小さい方から順に試す。ここでは、最大インデックス値が"２"と決定されたものとする。次に、解探索処理部１０３は、最大インデックス値以下のインデックス値に該当する母材Ｍ1、Ｍ2の利用母材フラグを決定する。具体的には、最大インデックス値の母材Ｍ2の利用母材フラグの値は"１"とする。次に最大インデックス値未満のインデックス値の母材について、インデックス値の若い順に、その利用母材フラグの値"１"を先に試し、次に"０"を試す。今、最大インデックス値はＭ2なので、最大インデックス値未満のインデックス値の母材としてはＭ1のみが該当する。次に、母材Ｍ1、Ｍ2を製品生産に利用するか否かを決定する一方で、最大インデックス値より大きなインデックス値に該当する母材Ｍ3〜Ｍmの利用母材フラグを全て"０"とする(ステップＳ４０２)。
【００３９】
利用母材フラグに"０"が設定された場合は、ステップＳ４０９において該当する母材には製品の引き当てがなされず、その母材から製品Ｐ1、Ｐ2の何れも生産されないことになる。一方、利用母材フラグに"１"が設定された場合は、ステップＳ４０９において該当する母材には少なくとも製品Ｐ1、Ｐ2の何れか一つが引き当てられることになる。ここでは、変数（利用母材フラグ（Ｍ1））、変数(利用母材フラグ（Ｍ2）)の双方について"１"（利用する）が設定されているものとする。
【００４０】
−各母材の分割数の決定−
続いて、解探索処理部１０３は、母材Ｍ1の分割数を示す変数（母材Ｍ1の分割数）を決定する（ステップＳ４０３）。変数（母材Ｍ1の分割数）には、次の制約条件（１）、（２）が課せられている。
制約条件（１）「分割数制約」：母材Ｍ1の分割数≦母材Ｍ1の最大分割数（＝３）
制約条件（２）「長さ制約」：母材Ｍ1の分割数×製品Ｐ1の長さの下限値≦母材Ｍ1の長さ≦母材Ｍ1の分割数×製品Ｐ1の長さの上限値
即ち、変数（母材Ｍ1の分割数）のドメインは、制約伝播技術における枝刈りにより、
変数（母材Ｍ1の分割数）∈[２，３]
に制限される。
【００４１】
本実施形態においては、変数（母材Ｍ1の分割数）の値として初めにそのドメイン内における最小値"２"を選択し、次いで、値を増加させる方向で順次値を選択していく。ここでは、いま、変数（母材Ｍ1の分割数）の値として"２"が選択されているものとする。なお、母材Ｍ1の最大分割数は初期情報に含まれる数値情報である。
【００４２】
続いて、解探索処理部１０３は、母材Ｍ2の分割数を示す変数（母材Ｍ2の分割数）を決定する。変数(母材Ｍ2の分割数)には、次の制約条件(３)、（４）、(５)が課せられている。
制約条件（３）「分割数制約」：母材Ｍ2の分割数≦母材Ｍ2の最大分割数（＝８）
制約条件（４）「長さ制約」：母材Ｍ2の分割数×製品Ｐ1の長さの下限値≦母材Ｍ2の長さ≦母材Ｍ2の分割数×製品Ｐ1の長さの上限値
制約条件（５）「長さ制約」：母材Ｍ2の分割数×製品Ｐ2の長さの下限値≦母材Ｍ2の長さ≦母材Ｍ2の分割数×製品Ｐ2の長さの上限値
【００４３】
即ち、変数（母材Ｍ2の分割数）がとり得るドメインは、制約伝播技術における枝刈りにより、
変数（母材Ｍ2の分割数）∈［６］
に制限される。従って、解探索処理部１０３は、変数（母材Ｍ2の分割数）の値として"６"を設定する。なお、母材Ｍ2の最大分割数は初期情報に含まれる数値情報である。
【００４４】
−各母材の利用分割母材数の決定−
続いて、解探索処理部１０３は、各母材Ｍmの利用分割母材数を設定する（ステップＳ４０５）。先ず、解探索処理部１０３は、ステップＳ４０２において利用母材フラグを"０"とした母材（母材Ｍ3〜Ｍm）の利用分割母材数を"０"とする。続いて、解探索処理部１０３は、母材Ｍ1の利用分割母材数を示す変数（母材Ｍ1の利用分割母材数）を設定する。変数（母材Ｍ1の利用分割母材数）には、次の制約条件（６）、（７）、（８）が課せられている。
制約条件（６）「利用母材フラグの定義」：変数（母材Ｍ1の利用母材フラグ）＝"１"であれば、変数（母材Ｍ1の利用分割母材数）≧１
制約条件（７）「合計利用分割母材数の定義」：変数（合計利用分割母材数）＝全母材の利用分割母材数の総和＝変数（母材Ｍ1の利用分割母材数）＋変数（母材Ｍ2の利用分割母材数）
制約条件（８）「合計母材数上限制約」：変数（母材Ｍ1の利用分割母材数）≦変数（母材Ｍ1の分割数）
即ち、変数（母材Ｍ1の利用分割母材数）のドメインは、制約伝播技術における枝刈りにより、
変数（母材Ｍ1の利用分割母材数）∈［１，２］
に制限される。
【００４５】
本実施形態においては、変数（母材Ｍ1の利用分割母材数）の値として初めにそのドメイン内における最大値"２"を割り当て、次いで、値を減少させる方向で順次値を割り当てていく。ここでは、いま、変数（母材Ｍ1の利用分割母材数）の値として"２"が割り当てられているものとする。
【００４６】
続いて、解探索処理部１０３は、母材Ｍ2の利用分割母材数を示す変数（母材Ｍ2の利用分割母材数）を決定する。変数（母材Ｍ2の利用分割母材数）には、次の制約条件（９）、（１０）、（１１）が課せられている。
制約条件（９）「利用母材フラグの定義」：変数（母材Ｍ2の利用母材フラグ）＝"１"であれば、変数（母材Ｍ2の利用分割母材数）≧１
制約条件（１０）「合計利用分割母材数の定義」：変数（合計利用分割母材数）＝全母材の利用分割母材数の総和＝変数（母材Ｍ1の利用分割母材数）＋変数（母材Ｍ2の利用分割母材数）
制約条件（１１）「分割母材数上限制約」：変数（母材Ｍ2の利用分割母材数）≦変数（母材Ｍ2の分割数）
即ち、変数（母材Ｍ2の利用分割母材数）のドメインは、制約伝播技術における枝刈りにより、
変数（母材Ｍ2の利用分割母材数）∈［３］
に制限される。従って、解探索処理部１０３は、変数（母材Ｍ2の利用分割母材数）の値として"３"を割り当てる。
【００４７】
次に、解探索処理部１０３は、利用されない分割母材に対応する変数（条数）を"０"に設定する（ステップＳ４０６）。いま、変数（母材Ｍ1の分割数）の値として"２"、変数（母材Ｍ1の利用分割母材数）の値として"２"、変数（母材Ｍ2の分割数）の値として"６"、変数（母材Ｍ2の利用分割母材数）の値として"３"が割り当てられているため、分割母材Ｍ24、分割母材Ｍ25、分割母材Ｍ26に対応する変数（条数ＰＭ241）、変数（条数ＰＭ242）、変数（条数ＰＭ251）、変数（条数ＰＭ252）、変数（条数ＰＭ261）、変数（条数ＰＭ262）に"０"が割り当てられる。
【００４８】
−最小生産注文日数の決定−
続いて、解探索処理部１０３は、変数（最小生産注文日数）の値を決定する（ステップＳ４０７）。変数（最小生産注文日数）については、初期情報に含まれる所定の最小生産注文日数の最大日数（＝５）を初めに割り当て、次いで、値を減少させる方向で順次値を割り当てていく。ここでは、いま、変数（最小生産注文日数）の値として"１"が選択されているものとする。
【００４９】
ここで、最小生産注文日数とは、図８の出荷予定情報上において最低何日先までの各製品Ｐ1、Ｐ2の出荷予定量を生産する旨の条件の「何日先」に相当する製品Ｐ1、Ｐ2に共通の日数情報である。なお、最小生産注文日数が"０"であるとは、当日分の各製品の出荷予定量を生産する旨を表す。また、本実施形態の解探索処理においては、変数（最小生産注文日数）を減少させる方向で解空間の探索処理を行っている。これは、最小生産注文日数が多いところから解探索を行っていき、解が検出されると、その解は解空間のなかで最小生産注文日数が極力高い値をとることになる。従って、変数（最小生産注文日数）を減少させる方向で解空間の探索処理を行うことにより、できるだけ最小生産注文日数が多い日数となり、それに伴い次回の製品の製造（切り出し作業）までできるだけ日数を空けられる解を検出することが可能となる。
【００５０】
−最大生産注文日数の決定−
続いて、解探索処理部１０３は、変数（最大生産注文日数）の値を決定する（ステップＳ４０８）。変数（最大生産注文日数）については、初期情報に含まれる所定の最大生産注文日数の最小日数（＝１）を初めに割り当て、次いで、値を増加させる方向で順次値を割り当てていく。ここでは、いま、変数（最大生産注文日数）の値として"２"が選択されているものとする。
【００５１】
ここで、最大生産注文日数とは、図８の出荷予定情報上において最大でも何日先までの製品Ｐ1、Ｐ2の出荷予定量しか生産してはならない旨の条件の「何日先」に相当する製品Ｐ1、Ｐ2に共通の日数情報である。また、本実施形態の解探索処理においては、変数（最大生産注文日数）を上記最小生産注文日数の値から増加させる方向で解空間の探索処理を行うことにより、製品間において製品の引き当て日数を揃えた最適解を検出することが可能となる。ところで、本実施形態では、変数（合計利用分割母材数）、変数（最小生産注文日数）、変数（最大生産注文日数）の変数順序で解探索処理を行っている。これは、「製品在庫をできるだけ少なくしたい」、「次回の製品の製造（切り出し作業）までの日数をできるだけ空けたい」、「製品間の引き当て日数を揃えたい」の優先順位でユーザの要求を最適解に反映させるためである。
【００５２】
図５は、図４のステップＳ４０１、Ｓ４０２、Ｓ４０３、Ｓ４０５、Ｓ４０７及びＳ４０８における解探索処理部１０３の詳細動作を示したフローチャートである。
先ず、解探索処理部１０３は、現在探索している変数のドメインが空集合であるか否かを判断し（ステップＳ５０１）、ドメインが空集合であれば一つ上のレベルの変数にバックトラックする（ステップＳ５０２）。ここでいう「バックトラック」とは、値を割り当てる対象を探索木において一つルートに近い側に位置する変数に戻すことである。
【００５３】
一方、現在探索している変数のドメインが空集合でなければ、そのうちの一つの値を選択し（ステップＳ５０３）、選択した値を変数の値とする（ステップＳ５０４）。続いて、解探索処理部１０３は、選択した値を当該変数が関連する制約条件を通じて制約伝播を行い、他の何れかの変数のドメインが空になる場合は矛盾が発生したものと判断し（ステップＳ５０５）、選択した値をドメインから取り除く（ステップＳ５０７）。このように、制約条件に矛盾する数値はドメインから取り除かれ、ドメインが縮小されることになる。一方、当該変数が関連する制約条件に矛盾しない場合は、探索木において一つルートから遠い側に位置する変数に解探索処理を移行する（ステップＳ５０６）。
【００５４】
−条数の決定−
以上のように、各変数（（ａ）合計利用分割母材数、（ｂ）母材Ｍ1の利用母材フラグ、（ｃ）母材Ｍ2の利用母材フラグ、（ｄ）母材Ｍ1の分割数、（ｅ）母材Ｍ2の分割数、（ｆ）母材Ｍ1の利用分割母材数、（ｇ）母材Ｍ2の利用分割母材数、（ｈ）最小生産注文日数、（ｉ）最大生産注文日数）の値が定まると、解探索処理部１０３は、歩留りが最大となるような各利用分割母材上における各製品に係る変数（条数）の値の組を探索する（ステップＳ４０９）。この最適化は、条数以外の変数の値が固定された状況で行われる。そして、最適解検出部１０４は、この最適化の試行により得られる解のうち最良の歩留りを実現する解を最適解として検出する。
【００５５】
いま、Ｍ1については２つの利用分割母材（Ｍ11,Ｍ12）、Ｍ2については３つの利用分割母材（Ｍ21,Ｍ22,Ｍ23）が決定されている。よって、解探索処理部１０３は、ＰＭ111、ＰＭ112、ＰＭ121、ＰＭ122、ＰＭ131、ＰＭ132、ＰＭ211、ＰＭ212、ＰＭ221、ＰＭ222、ＰＭ231、ＰＭ232の各変数（条数）について解探索処理を実行する。本実施形態では、各変数（条数）が次の値をとるときに最適解が検出された場合を想定するものとし、以下の例を用いて変数（条数（ＰＭjki））に係る制約充足問題の解法から最適化問題の解法までを、図６及び図７のフローチャートを参照しながら説明する。図７は、図４のステップＳ４０９の詳細を示すフローチャートであり、図６は、図７のステップＳ７０１の詳細を示すフローチャートである。
条数ＰＭ111：４，条数ＰＭ112：０，条数ＰＭ121：４，条数ＰＭ122：０，条数ＰＭ211：１，条数ＰＭ212：３，条数ＰＭ221：０，条数ＰＭ222：４，条数ＰＭ231：０，条数ＰＭ232：４
【００５６】
解探索処理部１０３は、各変数（条数）には、次の制約条件が課せられている。
制約条件（１２）「割当フラグの定義」：母材Ｍjにおける製品Ｐiの変数（割り当てフラグ）が"１"であれば、母材Ｍjにおける分割母材の何れかには製品Ｐｉが少なくとも一つは引き当てられ、"０"であれば、母材Ｍｊにおける分割母材のいずれにも製品Ｐｉは引き当てられない。
制約条件（１３）「条数０制約」：母材Ｍjにおける利用分割母材数が"０"であれば、母材Ｍjに引き当てられる条数は"０"である。
制約条件（１４）「利用幅の定義」：分割母材Ｍjkの利用幅＝分割母材Ｍjkにおける製品Ｐ1の条数×製品Ｐ1の幅＋分割母材Ｍjkにおける製品Ｐ2の条数×製品Ｐ2の幅
制約条件（１５）「母材幅制約」：分割母材Ｍjkの利用幅≦母材Ｍjの母材幅
制約条件（１６）「生産量の定義」：製品Ｐiの生産量＝分割母材11における製品Ｐiの条数＋分割母材12における製品Ｐiの条数＋・・・＋分割母材23における製品Ｐiの条数
制約条件（１７）「生産量上限値の定義」：製品Ｐiの生産量上限値＝最小生産注文日数分の製品Ｐiの出荷予定量
制約条件（１８）「生産量下限値の定義」：製品Ｐiの生産量下限値＝最大生産注文日数分の製品Ｐiの出荷予定量
制約条件（１９）「生産量上下限制約」：製品Ｐiの生産量下限値≦製品Ｐiの生産量≦製品Ｐiの生産量上限値
制約条件（２０）「基準面積の定義」：基準面積＝母材Ｍ1の幅×母材Ｍ1の長さ×母材Ｍ1の利用分割母材数／母材Ｍ1の分割母材数＋母材Ｍ2の幅×母材Ｍ2の長さ×母材Ｍ2の利用分割母材数／母材Ｍ2の分割母材数＋・・・＋母材Ｍmの幅×母材Ｍmの長さ×母材Ｍmの利用分割母材数／母材Ｍmの分割母材数
制約条件（２１）「利用面積の定義」：利用面積＝(母材Ｍ1の長さ×製品Ｐ1の幅／母材Ｍ1の分割母材数)×条数[1,1,1]＋(母材Ｍ1の長さ×製品Ｐ2の幅／母材Ｍ1の分割母材数)×条数[1,1,2]＋・・・＋(母材Ｍ2の長さ×製品Ｐ1の幅／母材Ｍ2の分割母材数)×条数［2,3,1］＋(母材Ｍ2の長さ×製品Ｐ2の幅／母材Ｍ2の分割母材数)×条数[2,3,2]
制約条件（２２）「歩留りの定義」：歩留り（目的関数値）＝利用面積／基準面積
制約条件（２３）「歩留りmin制約」：歩留り（目的関数値）≧歩留り最小値
制約条件（２４）：歩留り（目的関数値）＞既知の最良の解の歩留り（目的関数値）
【００５７】
解探索処理部１０３は、先ず、全条数（ＭＰ111、ＭＰ112、ＭＰ121、ＭＰ122、ＭＰ211、ＭＰ212、ＭＰ221、ＭＰ222、ＭＰ231、ＭＰ232）の値が既に決定されているか否かを判断する（ステップＳ６０１）。解探索処理部１０３は、この判断において、全条数の値が未だ決定されていないと判断した場合、値が決定されていない条数のうちドメインの要素の数が最も小さい変数（条数）を選択する（ステップＳ６０２）。
【００５８】
本実施形態においては、ＰＭ112及びＰＭ122を除いて（母材Ｍ1における製品Ｐ2の割当フラグが"０（割り当てない）"であることを想定している）、ドメインが最も小さい変数（条数）はＰＭ232である。従って、解探索処理部１０３は、変数(条数ＰＭ232)の値を他の変数（条数ＰＭjki）より優先的に決定する。
【００５９】
続いて、解探索処理部１０３は、変数（条数ＰＭ232）についてドメインから最も小さい値を選択し（ステップＳ６０３）、変数（条数ＰＭ232）の値として設定する（ステップＳ６０４）。次いで、解探索処理部１０３は、変数（条数ＰＭ232）につき設定した値が制約条件（１２）〜（２３（又は２４））に矛盾するか否かを判断する（ステップＳ６０５）。変数（条数ＰＭ232）につき設定した値が制約条件（１２）〜（２３（又は２４））に矛盾する場合は、設定した値を変数（条数ＰＭ232）のドメインから取り除き（ステップＳ６０６）、当該ドメインが空集合となれば、解探索処理部１０３は、バックトラックが可能であるか否かを判断し、バックトラックが可能であれば一つ上のレベルの変数（条数）にバックトラックする（ステップＳ６０７、Ｓ６０８、Ｓ６１０）。ここでは、変数（条数ＰＭ232）につき設定した値が制約条件（１２）〜（２３（又は２４））に矛盾しないため、ステップＳ６０１からの次のレベルの変数（条数）の解探索処理に移行する。また、ステップＳ６０７において空集合と判断されたドメインが最も上のレベルの変数であれば、バックトラック不可と判断され、"解なし"として解探索処理を終了することになる（ステップＳ６０８、Ｓ６０９）。ステップＳ６０５における矛盾発生の判定方法としては、当該変数に当該値を割り当て、制約伝播が行われた結果、何れかの変数のドメインが空集合となった場合に矛盾が生じたものと判定される。
【００６０】
なお、ステップＳ６０８においては、当該ドメインが空集合となれば探索木において一つ変数（最大生産注文日数）に近い側に位置する変数（条数）にバックトラックすると説明したが、当該変数が探索木において最も変数（最大生産注文日数）の近くに位置する変数（条数）であれば（ここでは、変数（条数ＰＭ112））、ステップＳ６０９において解なしとして扱われ、ステップＳ７０２においてＮｏの方向へ分岐することとなる。
【００６１】
以降、解探索処理部１０３は、ドメインに含まれる値の個数が少ない変数（条数）から優先的に値を決定していく。
【００６２】
以上の手順により、各変数への値の割り当て方の組合せから成る解を算出する。図９、図１０に示すように、ここで算出された解を次に列挙する。
・合計利用分割母材数：５
・利用母材フラグ（Ｍ1）：１
・利用母材フラグ（Ｍ2）：１
・分割数（Ｍ1）：２
・分割数（Ｍ2）：６
・利用分割母材数（Ｍ1）：２
・利用分割母材数（Ｍ2）：３
・最小生産注文日数：１
・最大生産注文日数：２
・条数（ＰＭ111）：４
・条数（ＰＭ112）：０
・条数（ＰＭ121）：４
・条数（ＰＭ122）：０
・条数（ＰＭ211）：０
・条数（ＰＭ212）：５
・条数（ＰＭ221）：０
・条数（ＰＭ222）：５
・条数（ＰＭ231）：１
・条数（ＰＭ232）：３
【００６３】
次に、本実施形態における最適解検出方法について説明する。
先ず、上記のように、解探索処理部１０３が図６のステップＳ６０１〜Ｓ６０９の処理を経ることにより制約充足問題の解が算出されると（ステップＳ７０１）、最適解検出部１０４は、解有りと判断し（ステップＳ７０２）、初めに算出された解は、制約条件（２６）を課せられることなく、当該解＝「既知の最良の解」、当該解に基づく目的関数値（歩留り）＝「既知の最良の解の目的関数値」として無条件に最適解検出部１０４によりＲＡＭ２０２に記録される（ステップＳ７０３）。
【００６４】
このように、「既知の最良の解」及び「既知の最良の解の目的関数値」が一旦ＲＡＭ２０２に記録されると、以降の解探索処理においては、解の目的関数値が「既知の最良の解の目的関数値」より大きな値でなければならない、という制約条件（２４）が制約条件導出部１０２によって更に導出される（ステップＳ７０４）。従って、ステップＳ７０１において次に算出される解は、初めに算出された解（既知の最良の解）より高い目的関数値をとる解となる。この場合、ステップＳ７０４では、「既知の最良の解」及び「既知の最良の解の目的関数値」は次の解に基づく数値に更新され、制約条件（２４）の内容も同様に更新される。この処理の流れは、図７に示す最適化問題を解き終えるまで実行され、最後までＲＡＭ２０２に記録されている「既知の最良の解」が最適解とされる（ステップＳ７０６）。
【００６５】
ユーザは、上記の最適解が表示パネル等に出力されることによって、少なくとも次の事項を把握することが可能となる。
・当日利用可能な母材のうちどの母材を使用するか
・使用対象の母材をそれぞれ何分割するか
・各母材につき分割母材のうち幾つを利用分割母材とするか
・各利用分割母材に夫々どの製品を幾つ引き当てるか
【００６６】
また、本実施形態では、複数の母材の各利用分割母材に引き当てる各製品の条数を変数として含む解空間を解探索処理の対象としている。従って、本実施形態によれば、当日利用可能な母材が複数存在する場合であっても、それら母材間にわたって高い歩留りを確保できる製品の引き当て方法を算出することが可能となり、製品の製造現場の実状に則した製品引き当て計画を立てることができる。
【００６７】
尚、本実施形態では、変数（条数）の値のみを変化させて、歩留りの局所的最適化を行っており、このモデルは全体として見ると最適化問題ではなく、制約充足解として捉えることができる。従って、このモデルは一つの制約充足解を得る目的に利用される。このモデルに対してさらに目的関数（歩留り）を与え、目的関数値がある閾値を越えるまで歩留りの高い解の探索を続けるという実施形態も考えられる。また、その最適化に時間制限を設けて、当該時間制限内の解探索処理により得られた解のうち上記目的関数の値が最大となる解を最適解として検出することも考えられる。
【００６８】
以下に、今回のモデルに登場した変数を補足的に説明する。
・基準面積：問題全体で一つのみ存在する。利用分割母材の面積の合計を表す。
・利用分割母材数：各母材毎に存在する。当該母材の分割母材のうち、利用される分割母材の個数を表す。
・分割数：各母材毎に存在する。母材を長さ方向に何分割するかを表す。
・利用面積：問題全体で一つのみ存在する。生産される製品の面積の合計を表す。
・歩留り：問題全体で一つのみ存在する。利用分割母材の面積の合計に対する生産される製品の面積の合計の比率を表す。
・利用幅：各分割母材毎に存在する。当該分割母材から生産する製品幅の合計を表す。
・条数：各分割母材毎、各製品毎に存在する。当該分割母材から当該製品を切る条数を表す。
・生産量下限値：各製品毎に存在する。当該製品の最小生産日数分の出荷予定量を表す。
・最小生産注文日数：問題全体で一つのみ存在する。各製品の生産量が何日目までの出荷予定量を満たすべきであるかを表す。つまり、各製品は、最小生産注文日数分の出荷予定量を満たすように生産されることになる。最小生産日数は各製品毎に別のものではなく、各製品に共通のものである。
・生産量上限値：各製品毎に存在する。当該製品の最大生産注文日数分の出荷予定量を表す。
・最大生産注文日数：問題全体で一つのみ存在する。各製品の生産量が何日目までの出荷予定量までしか満たしてはいけないかを表す。つまり、各製品は、最大でも最大生産注文日数分の出荷予定量しか生産されないことになる。最大生産日数は各製品毎に別のものではなく、各製品に共通のものである。
・利用母材フラグ：各母材毎に存在する。当該母材を利用するか否かを表す。
・合計利用分割母材数：問題全体で一つのみ存在する。利用する分割母材の総数を表す。
・生産量：各製品毎に存在する。当該製品の生産量を表す。
・割当フラグ：各母材毎、各製品毎に存在する。当該母材から当該製品を生産するか否かを表す。
【００６９】
尚、本発明においては、変数（条数ＰＭjki）の代わりに分割母材毎に、当該分割母材のカッティングパターンを表す変数を用いることもできる。カッティングパターンとは、当該母材幅に収まる範囲の利用幅となる製品の組合せのパターンである。例えば、母材幅が1200mm、製品の種類が300mm、220mmであるとすると、表１に示すようにカッティングパターンは１６通りある。
【００７０】
【表１】
0004843201.tif 000002
【図面の簡単な説明】
【００７１】
【図１】本発明の一実施形態に係る情報処理装置の機能構成を示したブロック図である。
【図２】本発明の一実施形態に係る情報処理装置のシステム構成を示した図である。
【図３】母材に製品を引き当てた状態を模式的に示した図である。
【図４】本発明の一実施形態に係る情報処理装置の動作の流れを示したフローチャートである。
【図５】本発明の一実施形態に係る情報処理装置の動作の流れを示したフローチャートである。
【図６】本発明の一実施形態に係る情報処理装置の動作の流れを示したフローチャートである。
【図７】本発明の一実施形態に係る情報処理装置の動作の流れを示したフローチャートである。
【図８】出荷予定情報の一例を示した図である。
【図９】解探索処理の対象となる解空間を模式的に示した図である。
【図１０】解探索処理の対象となる解空間を模式的に示した図である。
【図１１】変数と制約条件との関係を示した図である。
【図１２】変数（条数）は分割母材と製品の組に対して与えられていることを示す図である。
【図１３】一般的な板状の綱板製品の製造工程を示した図である。
【符号の説明】
【００７２】
１０１  初期情報記憶部
１０２  制約条件導出部
１０３  解探索処理部
１０４  最適解検出部
１０５  出力制御部
【図１】
0004843201.tif 000003
【図２】
0004843201.tif 000004
【図３】
0004843201.tif 000005
【図４】
0004843201.tif 000006
【図５】
0004843201.tif 000007
【図６】
0004843201.tif 000008
【図７】
0004843201.tif 000009
【図８】
0004843201.tif 000010
【図９】
0004843201.tif 000011
【図１０】
0004843201.tif 000012
【図１１】
0004843201.tif 000013
【図１２】
0004843201.tif 000014
【図１３】
0004843201.tif 000015