(57)【要約】  本発明は、少なくとも一つのガラス板から、長方形の複数のガラス片のバッチを、裁断機を使って裁断するための、最適化された裁断計画を決定することができる、コンピューターによって行われる方法に関する。裁断後に、複数のガラス片は、少なくとも一つのフレーム上に積み重ねられ、任意の一つのフレームのための複数のガラス片は、ガラス板上に、それぞれのフレームについてあらかじめ定められた順番で配置される。  本発明の方法は、以下を含む：  −  最適化基準と共に、複数のガラス片の裁断制約及び位置決め制約を定義するための初期化工程（Ｅ５）；  −  ルートと複数のリーフとを含むツリーを作成すること（Ｅ１０、Ｅ３５）、ここで、複数のリーフは、それぞれ、バッチの複数のガラス片のすべてを裁断することを可能にする全裁断計画を示し、ツリーの互いのノードは、部分的裁断計画を示し、ツリーのノードを伴う裁断計画は、このノードの親ノードを伴う部分的裁断計画を付加することによって得られ（Ｅ３５）、かつ上記制約に従って、フレームのためにあらかじめ定められた順番に従って、一つのフレームの次のガラス片が決定される；及び  −  最適化基準に応じた、ツリーのリーフを伴う全裁断計画を選択するための選択工程（E１００）。
2019535053.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つのガラス板から、長方形の複数のガラス片のバッチを、裁断機を使って裁断するための、最適化された裁断計画を決定するためのコンピューターによって行われる方法であって、複数の前記ガラス片は、いったん裁断されると、少なくとも一つのフレーム（Ｃｉ）上に積み重ねられ、任意の一つのフレームのための複数の前記ガラス片は、裁断される前記少なくとも一つのガラス板上に、そのフレームについてあらかじめ定められた順番で配置され、前記方法は以下を含む：
−  最適化基準と共に、複数の前記ガラス片の裁断制約及び位置決め制約を定義するための初期化工程（Ｅ５）；
−  ルートと複数のリーフを含むツリー（Ｔ）を作成すること（Ｅ１０、Ｅ３５）、ここで、前記複数のリーフは、それぞれ、前記バッチの複数の前記ガラス片のすべてを裁断することを可能にする全裁断計画を示し、前記ツリーの互いのノードは、部分的裁断計画を示し、前記ツリーのノードを伴う前記裁断計画は、前記ノードの親ノードを伴う前記部分的裁断計画を付加することによって得られ（Ｅ３５）、かつ前記制約に従って、前記フレームのためにあらかじめ定められた順番に従って、前記一つのフレームの次のガラス片が決定される；及び
−  前記最適化基準に応じた、前記ツリーのリーフを伴う全裁断計画を選択するための選択工程（E１００）。
【請求項２】
前記最適化基準が、以下から選択される、請求項１に記載の方法：
−  使用されるガラス板の数を最小にしようとする基準；及び
−  裁断によって生じる損失面積の合計を最小にしようとする基準。
【請求項３】
前記裁断制約を、以下から選択することができる、請求項１又は２に記載の方法：
−  裁断レベルの最大数；
−  スクラップの最小幅；
−  裁断レベルの最大幅；及び
−  最初の分割の方向。
【請求項４】
前記位置決め制約は、ガラス板における複数の前記ガラス片の方向、それらのレベルに応じた、単一のガラス板における複数の前記ガラス片の相対的位置、前記少なくとも一つのガラス板の最大数のなかから選択することができる、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記ツリーのノードが、最大で９ｍの子ノードを有しており、ここで、ｍは、フレームの数であり、それぞれのフレームのための新たなガラス片は、そのフレームの位置決め制約に従って選択することができ、かつ前記ツリーのノードには、以下の９つの異なる様式で、部分的な裁断計画を付加することができる、請求項１〜４のいずれか一項に記載の方法：
−  水平方向又は垂直方向のいずれかで、先行するガラス片の右側に（裁断レベル３で）；
−  最後の２つのガラス片が同じ幅を有する場合に、先行するガラス片の上方に（新たな裁断レベル４で）、ここで、水平方向及び垂直方向のそれぞれの位置、すなわち、先行するガラス片の幅に等しい幅の位置は、十分なものである；
−  水平方向又は垂直方向のいずれかで、現在の幅の左端で、先行するガラス片の上方に（新たな裁断レベル２で）；
−  水平方向又は垂直方向のいずれかで、新たな幅に（新たな裁断レベル１で）；及び
−  水平方向又は垂直方向のいずれかで、新たなガラス板に。
【請求項６】
前記ツリーの前記作成は、以下を含む、請求項１〜５のいずれか一項に記載の方法：
−  前記ルートの下で、前記フレーム（Ｃ１、Ｃ２）のそれぞれのために、前記制約に従いながら、前記フレームの最初のガラス片の許容される位置のそれぞれについて、部分的裁断計画を伴うノードを作成することから構成される工程（Ｅ１０）；並びに
−  それぞれが以下を含む、少なくとも一回の反復：
−  そのノードによって示される部分的裁断計画の特徴に応じて、前記ツリーのカレントノードを選択する選択工程（Ｅ３０）；及び
−  前記カレントノードの少なくとも一つの子ノードを作成するための作成工程（Ｅ３５）、ここで、前記子ノードを伴う裁断計画は、前記カレントノードを伴う部分的な裁断計画を付加することによって得られ（Ｅ３５）、かつ前記制約に従いながら、前記一つのフレームの次のガラス片を、そのフレームについてあらかじめ定められた順番に従って取得する。
【請求項７】
前記方法の実行時間が、所定の時間（ＤＭＡＸ）よりも長いとき、前記反復を停止する工程（Ｅ６０）を含む、請求項６に記載の方法。
【請求項８】
前記カレントノードが、以下のとおり選択される（Ｅ３０）、請求項６又は７に記載の方法：
−  損失面積を、前記裁断計画の複数の前記ガラス片によって占められる全面積で割った割合が、最小となる前記裁断計画を伴うノードを選択することから構成される、「最小スクラップ基準」と称される第一の基準に従って、選択されるか；又は
−  最も大きい有効面積を有する前記裁断計画を伴うノードを選択することから構成される、「最大面積基準」と称される第二の基準に従って、選択される。
【請求項９】
前記最適化基準を最大限に生かす、前記全裁断計画を伴う前記リーフのみを保存し（Ｅ５０）、そのほかの複数のリーフは消去する、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記リーフを伴う全裁断計画から、得られたスクラップ面積が損失面積よりも大きい部分的裁断計画を伴う前記ツリーの前記ノードを、消去する工程（Ｅ６０）を含む、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
同型の部分的裁断計画に相当するノードを作成することを回避する又は最小にするために、前記位置決め制約が、前記フレームの数に関する少なくとも一つの辞書式制約を含む、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
ノードが作成されるそれぞれの時点で、前記ノードが、そのノードによって示される裁断計画の少なくとも一つの特徴に応じて分類され、前記少なくとも一つの特徴は、前記全裁断計画を選択するために十分である、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
前記分類のために使用される前記少なくとも一つの特徴が、前記ツリーの前記カレントノードを選択する前記工程の間で使用される前記少なくとも一つの特徴である、請求項６〜１２のいずれか一項に記載の方法。
【請求項１４】
少なくとも一つのガラス板（ＰＬＦ）から、長方形の複数のガラス片のバッチを、裁断機を使って裁断するための、最適化された裁断計画を決定するための装置であって、複数の前記ガラス片は、いったん裁断されると、少なくとも一つのフレーム（Ｃｉ）上に積み重ねられ、任意の一つのフレームのための複数の前記ガラス片は、裁断のための前記少なくとも一つのガラス板上に、そのフレームについて、あらかじめ定められた順番で配置され、前記装置は以下を含む：
−  最適化基準と共に、複数の前記ガラス片のための裁断制約及び位置決め制約を定義するための初期化モジュール；
−  ルートと複数のリーフを含むツリー（Ｔ）を作成するためのモジュール、ここで、前記複数のリーフは、それぞれ、前記バッチの複数の前記ガラス片のすべてを裁断することを可能にする全裁断計画を示し、前記ツリーの互いのノードは、部分的裁断計画を示し、前記ツリーのノードを伴う前記裁断計画は、前記ノードの親ノードを伴う前記部分的裁断計画を付加することによって得られ（Ｅ３５）、かつ前記制約に従って、前記フレームのためにあらかじめ定められた順番に従って、前記一つのフレームの次のガラス片が決定される；及び
−  前記最適化基準に応じた、前記ツリーのリーフを伴う全裁断計画を選択するための選択モジュール。
【請求項１５】
コンピュータープログラム（ＰＧ）であって、前記プログラムがコンピューターによって実行されるときに、最適化された裁断計画を決定するために、請求項１〜１３のいずれか一項に記載の方法の工程を実行するための指示を含む、コンピュータープログラム。
【請求項１６】
コンピューター（１００）によって読み出すことができ、かつ最適化された裁断計画を決定するために、請求項１〜１３のいずれか一項に記載の方法の工程を実行するための指示を含むコンピュータープログラム（ＰＧ）を保存している、データ媒体（１０３）。
【請求項１７】
少なくとも一つのガラス板から、長方形の複数のガラス片のバッチを、裁断機を使って裁断するための、以下を含む裁断方法：
−  最適化された裁断計画を決定するために、請求項１〜１３のいずれか一項に記載の方法を行うこと；及び
−  前記ガラス板を裁断する段階の間及び前記ガラス板を分割する段階の間に、前記最適化された計画を用いること。
【請求項１８】
前記バッチは、最適化された裁断計画を決定するために、請求項１〜１３のいずれか一項に記載の方法を行うことによって決定される、請求項１７に記載の裁断方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ガラスを裁断する方法の分野に属し、より詳細には、そのような裁断を最適化するための方法及び装置に関する。
【０００２】
本発明の方法及びプロセスは、特に、工場で裁断されるガラスのバッチ（複数枚のガラス片の束）を作り出すときに、ガラスの損失を減らすことに役立つ。
【背景技術】
【０００３】
裁断機で、長方形の複数枚のガラス片のバッチ（長方形の複数枚のガラス片の束）を裁断するための計画には、この複数枚のガラス片が、それぞれのフレームについて特定されている、あらかじめ定められた順番で、１又は複数のフレーム（枠、支持構造体）上に積み重ねられる、という事実を考慮する必要がある。
【０００４】
現在の技術水準では、ガラスの損失を最小限にしながら、裁断計画の設計を最適化し、かつ配置の制約に適合することができるような、いかなるソフトウェアも存在しない。
【０００５】
特に、この目的のために現在使用されているソフトウェアは、配置の制約に従った裁断計画について、限られた数しか構築することができない。したがって、平行して複数のソフトウェアを使用し、その上、これらの様々な複数のソフトウェアによって生み出される裁断計画のなかから、ガラスの損失を最小限にする計画を選択するためには、オペレーターは熟練していることが必要になる。
【０００６】
文献「Ａｎ  ｅｘａｃｔ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｇｅｎｅｒａｌ，  ｏｒｔｈｏｇｏｎａｌ，  ｔｗｏ−ｄｉｍｅｎｓｉｏｎａｌ  ｋｎａｐｓａｃｋ  ｐｒｏｂｌｅｍｓ，Ｅｕｒｏｐｅａｎ  Ｊｏｕｒｎａｌ  ｏｆ  Ｏｐｅｒａｔｉｏｎａｌ  Ｒｅｓｅａｒｃｈ，Ｖｏｌ．８３，Ｎｏ．１，１９９５年５月１８日，Ｈａｄｊｉｓｃｏｎｓｔａｎｔｉｎｏｕ及びその他」には、単一のシート（板）から複数の部分を切り取る方法が記載されている。この方法は、複数の部分が、非常に異なる寸法であり得るものであって、その複数の部分を、複数のフレーム上に、それぞれのフレームについてあらかじめ定められた順番で積み重ねることができるような、裁断機による裁断方法には適用できない。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、上記の欠点が存在しない裁断計画を決定するための方法及び装置を提供することを目的とするものである。
【課題を解決するための手段】
【０００８】
より詳細には、第一の実施形態において、本発明は、少なくとも一つのガラス板から、長方形の複数のガラス片のバッチを、裁断機を使って裁断するための、最適化された裁断計画を決定するためのコンピューターによって行われる方法であって、
複数のガラス片は、いったん裁断されると、１又は複数のフレーム上に積み重ねられ、任意の一つのフレームのための複数のこのガラス片は、裁断されるガラス板上に、そのフレームについてあらかじめ定められた順番で配置され、
この方法は以下を含む：
−  最適化基準と共に、複数のガラス片の裁断制約及び位置決め制約を定義するための初期化工程；
−  ルートと複数のリーフを含むツリーを作成すること、ここで、複数のリーフは、それぞれ、バッチの複数のガラス片のすべてを裁断することを可能にする全裁断計画を示し、ツリーの互いのノードは、部分的裁断計画を示し、ツリーのノードを伴う裁断計画は、このノードの親ノードを伴う部分的裁断計画を付加することによって得られ、かつ所定の制約に従って、フレームのためにあらかじめ定められた順番に従って、一つのフレームの次のガラス片が決定される；
及び
−  最適化基準に応じた、ツリーのリーフを伴う全裁断計画を選択するための選択工程。
【０００９】
本発明は、複数のガラス片が、少なくとも二つのフレーム上に、それぞれのフレームについてあらかじめ定められた順番で積み重ねられるときに、好ましくは適用される。
【００１０】
また、本発明は、少なくとも二つのガラス板を使用するときに、好ましくは適用される。
【００１１】
したがって、一般的な方法で、本発明は、複雑な複数のバッチを含む、多数の全裁断計画（多数の完全な裁断計画）を立案することを可能にする方法を提供することを目的とする。本発明の方法は、制約に従って、複数のガラス片を一つずつ配置することによって、漸進的に部分的裁断計画のツリー（データ構造における木構造）を構築するという点で優れている。
【００１２】
本発明によれば、部分的裁断計画及び全裁断計画における複数のガラス片は、実際に複数のフレーム上に積み重ねられる複数のガラス片の、複数の寸法を有しており；それぞれの全裁断計画は、すべてのフレームために必要な複数のガラス片の数を正確に有している。このことは、Ｈａｄｊｉｓｃｏｎｓｔａｎｔｉｎｏｕ及びその他による上記文献に記載されている方法と比較して、根本的な違いを構成するものであり、このことによって、所定の制限に従って変化する多数のガラス片を裁断することを可能にするものである。
【図面の簡単な説明】
【００１３】
【図１】図１は、複数のガラス片を有しているフレームを示す。
【図２Ａ】図２Ａは、図１のフレーム上のすべての複数のガラス片を裁断するために適した全裁断計画を示す。
【図２Ｂ】図２Ｂは、図１のフレーム上のすべての複数のガラス片を裁断するために適した全裁断計画を示す。
【図３】図３は、本発明の第一の特定の実施態様に従う決定方法の、主となる工程を示した、フローチャートである。
【図４】図４は、本発明によって得ることができる、部分的裁断計画を示す。
【図５】図５は、本発明の第二の特定の実施態様に従う決定方法の、主となる工程を示した、フローチャートである。
【図６】図６は、図５の決定方法によって行われる最適化機能の、主となる工程を示した、フローチャートである。
【図７】図７は、部分的裁断計画を示す。
【図８】図８は、本発明の特定の実施態様における部分的裁断計画を伴うノードを保存するバッファーメモリーを示す。
【図９】図９は、同型の部分的裁断計画を示す。
【図１０】図１０は、本発明の特定の実施態様に従う決定装置の、ハードウェアアーキテクチャを示す略図である。
【発明を実施するための形態】
【００１４】
ツリー（データ構造における木構造）を用いる当業者にとって、「レベル」という概念を使用することは、通常の手段である。ルートは、ツリーの第一のレベルを構成し、ルートの複数の子ノードは、ツリーの第二のレベルを構成し、これらの子ノードの複数の子ノードは、ツリーの第三のレベルを構成する、等々である。
【００１５】
本発明の方法は、平行して行うことを容易にするという利点も提示する。
【００１６】
本発明の方法は、制約及び最適化基準を入力することから本質的に構成されるオペレーターの仕事を、大いに容易なものとする。
【００１７】
最適化基準は、裁断の結果としての、損失となる総面積を最小にしようとするものである。その変形としては、オペレーターは、いくつかのそのほかの最適化基準、例えば、使用されるガラス板の数を最小にするといったような基準を定義することができる。
【００１８】
特定の実施態様では、裁断制約は、以下のもののなかから選択される：
−  裁断レベルの最大数；
−  スクラップの最小幅、例えば、ガラス板の厚さの２倍よりも大きい；
−  最初の分割の方向、例えば、ガラス板の幅方向、又は裁断レベルの最大幅、例えば、取扱制約のために、３メートルである。
【００１９】
「ツリーにおけるレベル」の概念と、「裁断レベル」の概念とは、完全に独立したものであって、混同しないことが重要であることに注意すべきである。
【００２０】
特定の実施態様では、位置決め制約は、ガラス板における複数のガラス片の方向、それらのレベルに応じた、単一のガラス板における複数のガラス片の相対的位置、少なくとも一つのガラス板の最大数のなかから、選択することができる。
【００２１】
特定の実施態様では、ツリーのノードは、最大で９ｍの子ノードを有しており、ここで、ｍは、フレームの数である。特に、それぞれのフレームのために、位置決め制約に従って選択される新たなガラス片には、部分的裁断計画を付加することができ、このことは、以下の９つの異なる様式でなすことができる。すなわち、
−  水平方向又は垂直方向のいずれかで、先行するガラス片の右側に（裁断レベル３で）；
−  最後の２つのガラス片が同じ幅を有する場合に、先行するガラス片の上方に（新たな裁断レベル４で）、ここで、水平方向及び垂直方向のそれぞれの位置、すなわち、先行するガラス片の幅に等しい幅の位置は、十分なものである；
−  水平方向又は垂直方向のいずれかで、現在の幅の左端で、先行するガラス片の上方に（新たな裁断レベル２で）；
−  水平方向又は垂直方向のいずれかで、新たな幅に（新たな裁断レベル１で）；及び
−  水平方向又は垂直方向のいずれかで、新たなガラス板に。
【００２２】
最適化された変形の実施形態では、ツリーの作成は、以下を含む：
−  ルートの下で、それぞれのフレームのために、上述した制約に従いながら、フレームの最初のガラス片の許容される位置のそれぞれについて、部分的裁断計画を伴うノードを作成することから構成される工程；並びに
−  それぞれが以下を含む、少なくとも一回の反復：
−  そのノードによって示される部分的裁断計画の特徴に応じて、ツリーのカレントノードを選択する選択工程；及び
−  カレントノードの少なくとも一つの子ノードを作成するための作成工程、ここで、この子ノードを伴う裁断計画は、カレントノードを伴う部分的裁断計画を付加することによって得られ、かつ上述した制約に従って、フレームの次のガラス片を、そのフレームについてあらかじめ定められた順番に従って取得する。
【００２３】
この変形は、それぞれの反復において、カレントノードを選択する工程を含み、ここで、子ノードが、このノードによって示される部分的裁断計画の特徴に応じて作成される、という点で優れている。
【００２４】
この特徴は、最適な解に到達するための最も有望であるカレントノードを選択することを可能にし、それによって、この方法は、通常、最適な解に、より迅速に到達することになる。
【００２５】
したがって、特定の実施態様では、この方法を実行する時間が、所定の時間よりも長いときには、オペレーターが最適な解又は良好な解決法を合理的な時間の範囲内で認識することができるように、この方法は、上記反復を停止する工程を含むことが有利である。
【００２６】
特定の実施態様では、本発明の方法は、この方法を実行し続けることができ、より良い解を発見する可能性を有しながら、使用者に、いつでも最善の解を認識させることを可能にする。
【００２７】
特定の実施態様では、カレントノードが、以下のとおり選択される：
−  損失面積を、有効面積で割った割合が、最小となる裁断計画を伴うノードを選択することから構成される、「最小スクラップ基準」と称される第一の基準に従って、選択されるか；又は
−  最も大きい有効面積を有する裁断計画を伴うノードを選択することから構成される、「最大面積基準」と称される第二の基準に従って、選択される。
【００２８】
ツリーを探索するこの方策、言い換えれば、カレントノードを選択するこの方策は、「最小スクラップ」及び「最大面積」という２つの基準を交互に繰り返すことから構成される。
【００２９】
例えば、「最小スクラップ基準」は、定められた時間の長さの間、又は反復の所定の回数の間、又はコンピューターのＲＡＭのある一定の割合が占められるまで（約２００万ノードがオープンになるまで）、使用することができる。
【００３０】
「最小スクラップ」基準を適用することは、作成される部分的計画が、最小のスクラップを有するものであって、かつほぼ最適な解である全裁断計画を導くことができるようなツリーの有望な領域を探索することを可能にする。それでもなお、この基準を適用することは、多数の新しいノードが作成されることにつながるので、仮に何ら制限を設けなければ、機械のメモリーが飽和してしまうリスクがある。
【００３１】
したがって、有利には、本発明のこの実施態様では、上述した限度に到達したときには（時間、反復の回数、又はＲＡＭの占有割合の観点から）、「最大面積」の基準を適用するために、探索の方策が変更される。
【００３２】
この「最大面積」の基準は、既に配置されている複数のガラス片の面積が最も大きいものである部分的計画を選択することによって、その部分的計画が、ほぼ完全な裁断計画となるようなノードを選択することにつながる。このことは、全裁断計画に、より迅速に到達すること、及びこれまでに得られた最良の全裁断計画を改善することを可能にする。
【００３３】
特定の実施態様では、メモリースペースを節約するために、最適な基準を最大限に生かす全裁断計画を伴うリーフのみを保存し、そのほかの複数のリーフは消去する。言い換えれば、得られた最初のリーフが保存され、新たなリーフが得られたときに、より良い全裁断計画を伴うリーフのみがメモリーに保持される。
【００３４】
特定の実施態様では、本発明の方法は、リーフを伴う全裁断計画から、得られたスクラップ面積が、損失面積よりも大きいような、部分的裁断計画を伴うツリーのノードを消去する工程を含む。
【００３５】
この実施態様は、有利には、「最小スクラップ基準」及び「最大面積基準」を交互に繰り返す上記の実施態様と組み合わせることができる。
【００３６】
特に、より良い裁断計画が得られた場合は、より良い全裁断計画に到達することができない、有望でないノードを消去するために、カレントノードのすべてについて、枝刈り作業を行う。これは、まだ探索していないノードの幾何学的喪失と、これまでに得られた最善の解の喪失とを、比較することによってなされ；言い換えれば、ノードの喪失が、最善のノードを喪失することよりも好まれる場合には、そのノードは消去される。このことは、探索される残ったノードの数を減らすことができ、これによってメモリーを開放することができる。また、この基準は、ある一定の時間の長さにおいて、又は所定の回数の反復において適用され、かつ新たな有望なノードを作成するために、もう一度「最小スクラップ」基準が適用される。
【００３７】
この手順は、これらの２つの基準を交互に繰り返すこと、すなわち、新しい有望なノードを作成することと、改善された新しい解を入手して、より有望ではないノードを削除することとを、交互に繰り返すことから構成される。
【００３８】
この「得られたスクラップ」という概念は、部分的裁断計画ＰＤＰを示す、図７に準拠するそのほかの概念と一緒に要約することができる。
【００３９】
この特定の計画では、以下の３つの種類の面積（領域）を定義することが知られている。すなわち、
−  ガラス片を含む有効面積、図７では、ガラス片が置かれるフレームの番号で、ガラス片は番号付けされている；
−  得られたスクラップ（斜線部分）、つまり、使用されない領域であって、そこには任意の新たなガラス片を追加することができない領域（面積）；及び
−  続く追加のガラス片を配置するために、まだ使用することができる面積（小さな斑点を付けた領域）（薄灰色のところ）。
【００４０】
したがって、特定の実施態様では、ツリーのノードが、得られたスクラップ面積が既に全裁断計画の損失面積よりも大きいような部分的裁断計画を伴う、と判明したときには、より良い解を提供する全裁断計画を生じさせることができる状況にないため、このノードは消去することができる、ということがわかる。
【００４１】
この特定の実施態様は、ツリーを枝刈りすることを可能にし、かつこの方法の実行時間を著しく減少させることを可能にする。
【００４２】
特定の実施態様では、本発明による最適化方法は、同型である部分的な裁断計画、すなわち、同じ複数のガラス片を含み、かつ得られたスクラップ面積も同じである裁断計画に相当するツリー中のノードを、回避し又は最小限にする。例示として、図９における部分的な裁断計画であるＰＤＰＡとＰＤＢＰとは、同型である。
【００４３】
したがって、特定の実施態様では、位置決め制約は、同型である部分的な裁断計画に相当するノードを作成することを回避し又は最小限にするために、フレームの数に関する少なくとも一つの辞書式制約を含む。
【００４４】
例えば、位置決め制約は、以下の２つの辞書式制約を含むことができる：
−  最後のガラス片が、先行するガラス片の上方に置かれる場合には、最後のガラス片のフレーム番号は、先行するガラス片のフレーム番号よりも小さいものでなければならない；
−  最後のガラス片が、先行するガラス片の右側に置かれる場合には、先行するガラス片のフレーム番号よりも大きいものであるか、又は等しいものでなければならない。
【００４５】
特定の実施態様では、ノードが作成されるたびごとに、ノードは、そのノードによって示される裁断計画の少なくとも一つの特徴に応じて分類され、この一つの又はこれら複数の特徴は、全裁断計画を選択するために十分なものである。
【００４６】
この特徴は、好ましくは、最適化された実施態様の変形では、ツリーのカレントノードを選択する工程の間に使用される特徴である。
【００４７】
この実施態様では、最適化された全裁断計画を選択するために、かつ最適化された実施態様の変形でカレントノードを選択するために、ツリー全体を通して、もう一度スキャンする必要性を回避することができる。
【００４８】
特定の実施態様では、その複数のリーフを含むツリーのそのほかの複数のノードは、最後に配置されるガラス片のフレーム番号によって、及び最後のガラス片が配置された方向によって、メモリー中に示される。
【００４９】
この実施態様は、メモリーの占拠を最小にするのに役立つ。
【００５０】
本発明は、また、少なくとも一つのガラス板から、長方形の複数のガラス片のバッチを、裁断機を使って裁断するための、最適化された裁断計画を決定するための装置であって、複数のガラス片は、いったん裁断されると、少なくとも一つのフレーム上に積み重ねられ、任意の一つのフレームのための複数のガラス片は、裁断のためのガラス板上に、そのフレームについてあらかじめ定められた順番で配置され、この装置は以下を含む：
−  最適化基準と共に、複数のガラス片のための裁断制約及び位置決め制約を定義するための初期化モジュール；
−  ルートと複数のリーフを含むツリーを作成するためのモジュール、ここで、複数のリーフは、それぞれ、バッチの複数のガラス片のすべてを裁断することを可能にする全裁断計画を示し、ツリーの互いのノードは、部分的裁断計画を示し、ツリーのノードを伴う裁断計画は、このノードの親ノードを伴う部分的裁断計画を付加することによって得られ、かつ上述した制約に従って、フレームのためにあらかじめ定められた順番に従って、フレームの次のガラス片が決定される；及び
−  最適化基準に応じた、ツリーのリーフを伴う全裁断計画を選択するための選択モジュール。
【００５１】
本発明の方法によって得られる裁断計画は、特に以下のとおり使用することができる：
−  裁断ラインよりも上流で、最適化された裁断バッチを作り出すために、使用することができる；
−  裁断計画に応じた順番で、主にガラスに亀裂が伝搬することから構成される裁断であるような、適切な裁断の間に、使用することができる；及び
−  様々なフレーム上に配置される複数のガラス片を得るために、ガラス板を分割しながらも、オペレーターを手助けするために、使用することができる。
【００５２】
したがって、本発明はまた、少なくとも一つのガラス板から、長方形の複数のガラス片のバッチを、裁断機を使って裁断するための裁断方法を提供するものであり、この方法は、以下を含むことを特徴とする：
−  上述したとおりの、最適化された裁断計画を決定する方法を行うこと；及び
−  ガラス板を裁断する段階の間及びガラス板を分割する段階の間に、最適化された計画を用いること。
【００５３】
本発明の方法の特定の実施態様では、このバッチは、上記した最適化された裁断計画を決定する方法を行うことによって、それ自体決定される。
【００５４】
特定の実施態様では、本発明の最適化された裁断計画を決定する方法の様々な工程は、コンピュータープログラムの指示によって決定される。
【００５５】
したがって、本発明はまた、データ媒体上のコンピュータープログラムを提供し、このプログラムは、本発明の最適化された裁断計画を決定する方法を実行する工程に適合した支持を含む。
【００５６】
プログラムは、任意のプログラム言語を使用することができ、かつソースコード、オブジェクトコード、又はソースコードとオブジェクトコードの中間のコードの形式とすることができ、例えば、部分的にコンパイルされた形式、又は任意のほかの望ましい形式とすることができる。
【００５７】
また、本発明は、上記のようなコンピュータープログラムの指示を含む、コンピューターで読み出しことができる、データ媒体を提供する。
【００５８】
データ媒体は、プログラムを保存することができる任意の実体又は装置とすることができる。例えば、媒体は、読み出し専用メモリー（ＲＯＭ）、例えば、コンパクトディスク（ＣＤ）ＲＯＭ又は超小型電子回路ＲＯＭのような、保存手段を含んでよく、あるいは、例えば、ハードディスクのような磁気記録媒体を実際に含んでいてもよい。
【００５９】
さらに、データ媒体は、電気的又は光学的ケーブルを介して、無線で、又はそのほかの手段で伝達することができる、電気的な又は光学的なシグナルのような伝達性媒体であってもよい。本発明のプログラムは、特に、インターネットの類型のネットワークからダウンロードすることもできる。
【００６０】
あるいは、データ媒体は、プログラムが組み込まれた集積回路とすることもでき、この回路は、本発明の方法を実行するのに適合しているか、又は本発明の方法の実行において使用されるのに適合している。
【００６１】
本発明のその他の特徴及び利点は、添付の図面を参照してなされる以下の記載に示されている。図面は、実施態様を示すものであって、何ら本発明の特徴を制限するものではない。
【００６２】
本発明の第一の実施態様の詳細な説明
図１を参照すると、この図は、本発明の説明に従うものであって、裁断機で、５つの長方形の複数のガラス片、Ｐ１１、Ｐ１２、Ｐ１３、Ｐ２１及びＰ２２のバッチを裁断するための最適化された計画を決定するために、本発明の第一の特定の実施態様において行われるものであり、ここで、複数のガラス片は、２つのフレームＣ１及びＣ２上に積み重ねられ、この計画は、裁断損失を最小にしながら一定数の制約に従う必要がある。
【００６３】
この方法は、図１０に示すような本発明に従う決定装置１００によって行うことができる。この装置は、コンピューターのハードウェアアーキテクチャを示している。特に、この装置は、プロセッサ１０１、ＲＯＭ１０２、ランダムアクセスメモリ（ＲＡＭ）１０３、キーボード１０４、スクリーン１０５、及びハードディスク１０６を含む。
【００６４】
ＲＯＭ１０２は、本発明の意味するところにおいて、媒体を構成する。ＲＯＭ１０２は、最適化された裁断計画を決定するための本発明の方法のステップを実行するための指示を含む、コンピュータープログラムであるＰＧを含む。
【００６５】
この実施例では、プログラムＰＧは、図３に示される工程を実行するための指示を含む。
【００６６】
プログラムは、少なくとも一つのガラス板から、裁断機によって、Ｐ１１からＰ２２までの複数のガラス片を裁断するための最適化計画を決定するのに役立つ。
【００６７】
プログラムは、オペレーターが、最適化基準と共に、複数のガラス片のための裁断制約及び位置決め制約を装置１００に与えるために、キーボード又は任意のそのほかの手段を使用することを可能にする入力モジュールを含む。このデータは、ハードディスク１０６に保存することができる。
【００６８】
また、プログラムは、ルートと複数のリーフを有するツリーを作成するための作成モジュールを有しており、部分的裁断計画を示す、ツリーの互いのノードと一緒に、複数のリーフはそれぞれ、バッチの複数のガラス片のすべてを裁断するために適した全裁断計画を示し、ツリーのノードを伴う裁断計画は、そのノードの親ノードを伴う部分的裁断計画を付加することによって得られ、かつ上記制約に従って、フレームの一つの次のガラス片が、そのフレームのためにあらかじめ定められた順番で決定される。
【００６９】
ここで記載した実施態様では、ツリーのノードは、ＲＡＭ１０３に保存される。
【００７０】
プログラムＰＧはまた、ハードディスク１０６に保存された最適化基準に応じて、ツリーのリーフを伴う全裁断計画を選択するための選択モジュールを有する。
【００７１】
ここで記載した実施態様では、オープンノード、すなわち、部分（ピース）の拡張が検討されていない部分的裁断計画を示すノードは、ＲＡＭのバッファーに保存される。
【００７２】
ここで記載した実施態様では、図８に示すとおり、バッファーメモリーは、２入力表ＭＴの形式で構成され、ここで、
−  横の列は、関係する裁断計画からの損失面積の割合によってノードを分類するのに役立ち；かつ
−  縦の列は、関係する裁断計画の有効面積の割合によってノードを分類するのに役立つ。
【００７３】
図８の例では、表は、２０の横列と２０の縦列を有しており、つまり、５％ずつ増加している。この増加の値は変えることができ、かつ横列と縦列とで異なっていてもよい。
【００７４】
したがって、例示として、９１％の有効面積と６％の損失面積を示す裁断計画は、Ｔ１のボックスに保存される。
【００７５】
表は、ノードが作成されるたびごとに、更新される。
【００７６】
ここで記載した実施態様では、それぞれのオープンノードは、以下によって特徴づけられる；
−  それぞれのフレームで、次に入手されるガラス片がどれであるかを示す表；
−  図７にそれぞれｘ１ｌ及びｘ１ｒと書かれた、最も右側の裁断機１の左側及び右側の位置；
−  それぞれｙ２ｆ及びｙ２ｃと書かれた、最も上部の裁断機２の床側及び天井側の位置；
−  ｘ３と書かれた、最後に配置されたガラス片の右側の位置；及び
−  ｙ４と書かれた、最後に配置されたガラス片の最上部の位置。
【００７７】
クローズドノードは、最後に配置されたガラス片のフレーム番号、及びそれが配置された方向によって、メモリーに示される。
【００７８】
ここで記載した実施態様では、位置決め制約は、特に、以下を要求するものである：
−  ガラス片Ｐ１１、Ｐ１２、及びＰ１３は、この順番でフレームＣ１上に配置される；及び
−  ガラス片Ｐ２１及びＰ２２は、この順番でフレームＣ２上に配置される。
【００７９】
そして、裁断制約は、以下を要求する：
−  最大で４つの裁断レベル；
−  スクラップの最小幅；及び
−  その大きさ（又はレベル）の最大幅。
【００８０】
図２Ａ及び２Ｂは、２つの許容される裁断計画ＰＤ１及びＰＤ２示したものであり、すなわち、（図２Ａの）第一の裁断計画ＰＤ１では、すべての複数のガラス片は同じガラス板ＰＬＦ１上に位置しており、（図２Ｂの）第二の裁断計画ＰＤ２では、複数のガラス片は、２つのガラス板ＰＬＦ２及びＰＬＦ３上に配置されている。
【００８１】
例示として、図２Ａの裁断計画ＰＤ１では、以下のことがわかる：
−  ２つのレベル１が、ｄ１、ｄ２と書かれたところを裁断する；
−  ２つのレベル２が、ｄ３、ｄ４と書かれたところを裁断する；及び
−  １つのレベル３が、ｄ５と書かれたところを裁断する。
【００８２】
この例では、斜線で示されているように、生じるスクラップの面積が最小になるために、図２Ａの裁断計画ＰＤ１は、図２Ｂの裁断計画ＰＤ２よりも好ましい。
【００８３】
図３は、ガラスの裁断を最適化するための、本発明の第一の実施態様に従った方法の主な工程を示したものである。
【００８４】
図３を参照すると、この方法は、最適化基準と共に、複数のガラス片のための裁断制約及び位置決め制約を定義する、工程Ｅ５を含む。この工程Ｅ５は、以下を有している方法を初期化するのに役立つ：
−  フレームの数、特に、２つ；
−  これらのフレーム上のガラス片Ｐ１１〜Ｐ１３及びＰ２１〜Ｐ２２の順番；
−  それぞれのガラス片の寸法；
−  ガラス板の寸法；
−  裁断レベルの最大数、特に、４つ；
−  スクラップの最小幅；
−  その大きさの最大幅；及び
−  最適化基準。
【００８５】
初期化工程Ｅ５に続いて、裁断計画のツリーＴの第一段階Ｌ１を作成する作成工程Ｅ１０が行われる。
【００８６】
本発明に従って、複数の全裁断計画が、ツリーの複数のリーフによって示され、全裁断計画を示す複数のリーフの複数の親ノードは、それ自体で部分的裁断計画ＰＤＰを示し、全裁断計画に到達することを可能にする、ということが思い起こされるべきである。
【００８７】
したがって、本発明に従って、ツリーＴのルートから出発して、それぞれの（子）ノードは、位置決め制約及び裁断制約を順守しながら、親ノードによって示される部分的裁断計画に、追加の部分（ピース）を付加することによって、先行する（親）ノードから得られる。
【００８８】
ツリーの第一段階Ｌ１での、許容できる部分的計画のセットは、フレームＣ１又はＣ２のそれぞれの最初のガラス片を、すなわち、ガラス片Ｐ１１又はガラス片Ｐ２１を、ガラス板の一角に配置することによって得ることができる部分的裁断計画のセットによって、構築される。
【００８９】
図４に示されているように、この手順は、ＰＤＰ１〜ＰＤＰ４の４つの部分的裁断計画を含み、ここで、ガラス片Ｐ１１又はＰ２１は位置を定められ、かつガラス片は水平方向（横方向）又は垂直方向（縦方向）のいずれかで置かれる。第一段階Ｌ１で、部分的裁断計画（破線で示されている）は、それぞれ、一つだけのガラス板ＰＬＦ１（実線で示されている）を有している。
【００９０】
工程Ｅ３５の間に、段階Ｌ１におけるそれぞれのノードの子ノードが作成され、これらのノードが、ツリーＴの段階Ｌ２を構築する。
【００９１】
図４では、ノードＰＤＰ１の子ノードＰＤＰ１／１〜ＰＤＰ１／１２が詳細に示されており、その一方、ノードＰＤＰ２〜ＰＤＰ４の子ノードＰＤＰ２／１〜ＰＤＰ４／１２は、単に記号で省略して記載されている。
【００９２】
部分的な裁断計画ＰＤＰ１／ｉは、以下の事項を考慮することによって、部分的裁断計画ＰＤＰ１から得られる：
−  部分的計画ＰＤＰ１で位置を定められたガラス片は、フレームから引き出されているということを考慮することによって；及び
−  位置決め制約及び裁断制約を順守しながら、裁断計画ＰＤＰ１に、考慮されたフレームＣ１、Ｃ２に対するそれぞれのガラス片を付加することによって得られた、すべての裁断計画を考慮することによって、得られる。
【００９３】
図４の例では、部分的計画ＰＤＰ１の終わりで、フレームＣ１及びＣ２に対するガラス片は、フレームＣ１についてガラス片１２であり、フレームＣ２についてガラス片２１である。この例では、ガラス片１２又はガラス片２１の位置を定めることによって、部分的計画ＰＤＰ１から得られる、許容される裁断計画は以下のとおりである：
−  ガラス片１２を、垂直な位置（縦方向）で、ガラス片１１の右側に配置することによって得られる裁断計画ＰＤＰ１／１、この計画は一つだけのガラス板ＰＬＦ１を有している；
−  ガラス片１２を、水平な位置（横方向）で、ガラス片１１の右側に配置することによって得られる裁断計画ＰＤＰ１／２、この計画は一つだけのガラス板ＰＬＦ１を有している；
−  ガラス片１２を、水平な位置（横方向）で、ガラス片１１の上部に配置することによって得られる裁断計画ＰＤＰ１／３、この計画は一つだけのガラス板ＰＬＦ１を有している；
−  ガラス片１２を、垂直な位置（縦方向）で、ガラス片１１の上部に配置することによって得られる裁断計画ＰＤＰ１／４、この計画は一つだけのガラス板ＰＬＦ１を有している；
−  ガラス片２１を、垂直な位置（縦方向）で、ガラス片１１の右側に配置することによって得られる裁断計画ＰＤＰ１／５、この計画は一つだけのガラス板ＰＬＦ１を有している；
−  ガラス片２１を、水平な位置（横方向）で、ガラス片１１の右側に配置することによって得られる裁断計画ＰＤＰ１／６、この計画は一つだけのガラス板ＰＬＦ１を有している；
−  ガラス片２１を、垂直な位置（縦方向）で、ガラス片１１の上部に配置することによって得られる裁断計画ＰＤＰ１／７、この計画は一つだけのガラス板ＰＬＦ１を有している；
−  ガラス片２１を、水平な位置（横方向）で、ガラス片１１の上部に配置することによって得られる裁断計画ＰＤＰ１／８、この計画は一つだけのガラス板ＰＬＦ１を有している；
−  ＰＦＬの垂直な位置（縦方向）にガラス片１２を含む、新たなガラス板ＰＬＦ２を作成することによって得られる裁断計画ＰＤＰ１／９；
−  水平な位置（横方向）にガラス片１２を含む、新たなガラス板ＰＬＦ２を作成することによって得られる裁断計画ＰＤＰ１／１０；
−  垂直な位置（縦方向）にガラス片２１を含む、新たなガラス板ＰＬＦ２を作成することによって得られる裁断計画ＰＤＰ１／１１；及び
−  水平な位置（横方向）にガラス片２１を含む、新たなガラス板ＰＬＦ２を作成することによって得られる裁断計画ＰＤＰ１／１２。
【００９４】
この例では、段階Ｌ２はまた、以下を含む：
−  ガラス片１２又は２１を、部分的裁断計画ＰＤＰ２に付加することによって得ることができる、許容される部分的裁断計画ＰＤＰ２／１〜ＰＤＰ２／１２のすべて；
−  ガラス片１１又は２２を、部分的裁断計画ＰＤＰ３に付加することによって得ることができる、許容される部分的裁断計画ＰＤＰ３／１〜ＰＤＰ３／１２のすべて；及び
−  ガラス片１１又は２２を、部分的裁断計画ＰＤＰ４に付加することによって得ることができる、許容される部分的裁断計画ＰＤＰ４／１〜ＰＤＰ４／１２のすべて。
【００９５】
フレームＣ１及びＣ２のすべてにガラス片が完全に存在しなくなるまで、反復方式で、このプロセスを繰り返すことによって、５つの段階を有するツリーＴが得られ、ここで、複数のリーフのそれぞれは、裁断及び位置の制約を満足する全裁断計画に対応している。図２Ａ及び２Ｂの、全裁断計画ＰＤ１及びＰＤ２は、これら複数のリーフのうちの、いくつかを構成する。
【００９６】
この第一の実施態様における方法は、工程Ｅ１００を含んでおり、工程Ｅ１００の間に、ツリーＴの複数のリーフのすべてのなかから、スクラップの面積を最小にする全裁断計画を得るための選択がなされる。
【００９７】
この裁断計画は、フレームＣ１及びＣ２を構成するために、ガラス板の裁断を最適化するのに役立つ。
【００９８】
本発明の第二の実施態様の詳細な説明
ガラス片のバッチが複雑であるときには、本発明の第一の実施態様に従って全ツリーＴを作成するために必要とされる計算時間は、過度に長いものとなり得る。
【００９９】
図５を参照しながら以下に説明する本発明の第二の実施態様では、この方法が実行される全継続時間が制限され、かつツリーのすべてのノードを作成することは、それぞれの反復について、既に作成されたツリーのノードのなかから、子ノードが作成された有望な部分的裁断計画を示すカレントノードを選択することによって、中止される。
【０１００】
この方法は、図１０に示されている本発明に従った決定装置１００によって行うことができるが、この例では、プログラムＰＧは、図５に示される工程を実行する指示を含む。
【０１０１】
ここで記載した実施態様では、オープンノードのそれぞれはまた、以下によって特徴付けられる：
−  フレームの数、配置方向、及び最後に配置されるガラス片の置き方；
−  最後に配置されるガラス片のない、部分的裁断計画に相当する親ノード；及び
−  ツリーの経路を導くために更新される一連の二次的属性、すなわち、得られるスクラップ；幾何学的損失について、部分的計画での複数のガラス片の面積の合計に相当する、ガラス板の占められる面積；使用されるガラス板の数；先行するガラス片に対するその位置（その右側又はその上部という位置）。
【０１０２】
ここで記載した実施態様では、この方法は、有望な部分的裁断計画を選択するために、２つの選択基準、すなわち、以下の選択基準を有する：
−  既に作成された部分的裁断計画のすべてのなかから、損失面積を有効面積で割った割合が最小となる計画を選択することから構成される、「最小スクラップ基準」；及び
−  既に作成された部分的裁断計画のすべてのなかから、有効面積が最大となる裁断計画を選択することから構成される、「最大面積基準」。
【０１０３】
ここで記載した実施態様では、第一段階Ｌ１（第一の実施態様の工程Ｅ１０参照）を作成した後で、選択基準は、工程Ｅ２０の間に「最小スクラップ基準」に初期化される。この同じ工程２０の間に、カウント時間は、ゼロに初期化される。
【０１０４】
ここで記載した実施態様では、それぞれの反復は、一般的工程Ｅ２５を含み、工程Ｅ２５の間に、選択基準を変更することが適切であるかどうかが確認される。
【０１０５】
このＥ２５の工程は、本発明の特定の実施態様では、図６を参照して記載される。
【０１０６】
工程Ｅ２５１の間、ＴＭＡＸ（Ｔｍａｘ）の値は、現在の選択基準に応じて初期化される。この例では、現在の選択基準が「最小スクラップ基準」であれば、ＴＭＡＸは１０秒に等しいものとなり、現在の選択基準が「最大面積基準」であれば、ＴＭＡＸは２０秒に等しいものとなる。
【０１０７】
工程Ｅ２５２の間、工程Ｅ２０で初期化されたカウント時間ｔは、その継続時間ＴＭＡＸよりも大きいかどうかが確認される。そうでない場合には、一般工程Ｅ２５は、選択基準を変更せず、かつカウント時間ｔを再初期化せずに、終了する。
【０１０８】
カウント時間が、継続時間ＴＭＡＸよりも大きい場合は、工程Ｅ２５３において、作成される子ノードのための次のノードを選択するために、どの選択基準を使用すべきであるのかを決定する。ここで記載した実施態様では、以下のとおりである：
−  現在の選択基準が「最小スクラップ基準」であるか、又はツリーＴのノードの数が、所定の値ＮＭＡＸ（Ｎｍａｘ）よりも大きい場合には、「最大面積基準」が保持される（工程Ｅ２５４）。このために、この実施態様では、グローバル変数Ｎｏ ノードが使用され、ＲＡＭ１０３に、ツリーＴのノードの数が保存される。この例では、この変数は、第一段階Ｌ１を作成する工程Ｅ１０の終わりで、値４を有している；あるいは、
−  そうでなければ、「最小スクラップ基準」が保持される（工程２５５）。
【０１０９】
カウント時間ｔは、工程Ｅ２５６の間にゼロに再初期化され、基準を変更するための一般工程Ｅ２５は終了する。
【０１１０】
図５に戻ると、工程Ｅ３０の間に、既に作成されたツリーのノードのなかから、工程Ｅ２５で保持された選択基準に応じて、カレントノードを得るための選択がなされる：
−  選択基準が「最小スクラップ基準」である場合には、選択されるツリーのノードは、損失面積を有効面積で割った割合が最小となる裁断計画のためのノードである。図８の特定の実施態様では、これは、表の最も高い位置にあるボックスに保存されるノードを選択することを意味する。いくつかの可能性が得られる場合には、ノードは、右側に最も離れている（すなわち、有効面積の割合が最も大きい）ボックスから選択される；
−  選択基準が「最大面積基準」である場合には、選択されるツリーのノードは、有効面積が最大となる裁断計画を示す。図８の特別な実施形態では、これは、表の右側に最も離れているボックスに保存されるノードを選択することを意味する。複数の可能性が得られる場合には、ノードは、最も高い位置にある（すなわち、損失面積の割合が最も小さい）ボックス中で選択される。
【０１１１】
工程Ｅ３５の間に、カレントノードについて、子ノードが作成される。この工程は、図３を参照して説明した工程Ｅ３５と同じである。この同じ工程の間に、属性が計算され、作成されたノードのそれぞれが保存され、かつツリーにおけるノードの数を表す変数である、Ｎｏ ノードが更新される。
【０１１２】
この実施態様では、カレントノードは、工程Ｅ４０の間に消去される。
【０１１３】
工程Ｅ４５の間に、工程Ｅ３５で作成された１又は複数のノードが、ツリーの（１又は複数の）リーフであるかどうかを確認する、言い換えれば、工程Ｅ３５で作成された１又は複数のノードが、フレームのすべての複数のガラス片を含むかどうかを確認する。
【０１１４】
そうであるならば、工程Ｅ５０において、これまでに得られた最善の解に相当する全裁断計画を伴うリーフをメモリーに保存する。すなわち、この例では、スクラップの面積を最小にするノードである。そのほかの（１又は複数の）リーフは削除することができる。第一のリーフが得られたときに、このリーフはメモリーに保存される。
【０１１５】
工程Ｅ５５の間に、工程Ｅ３５で得られたリーフは、改善された解に相当するかどうかを確認し、そうであるならば、工程Ｅ６０の間に、このリーフについての損失面積よりも大きいスクラップ面積を有している、得られたノードのすべては、ツリーＴから消去される。
【０１１６】
ここで記載した実施態様では、この最適化方法は工程Ｅ６５を含み、工程Ｅ６５の間に、この方法を実行する全継続時間が、所定の継続時間ＤＭＡＸ（Ｄｍａｘ）、例えば、１時間を超えていないことを確認する。このために、工程Ｅ５で初期化される、グローバルカウント時間である、ｔｉｍ＿ｃａｌｃを使用することができる。
【０１１７】
工程Ｅ６５において、継続時間ＤＭＡＸに到達していなかったと判断された場合には、この方法は、次のノードのための選択基準を決定する工程Ｅ２５にループバックすることによって継続される。
【０１１８】
継続時間ＤＭＡＸに到達したと判断された場合には、工程Ｅ７０において、この方法は、工程Ｅ５０で保存された最善の解に相当する全裁断計画に戻る。
【０１１９】
本発明の第三の実施態様の詳細な説明
特定の実施形態では、本発明の最適化法は、同型である部分的裁断計画に相当するツリーＴのノードの作成、すなわち、同じ複数のガラス片を含んでおり、得られたスクラップ面積が同じで、かつｘ１ｌ、ｘ３、ｘ１ｒ、ｙ２ｆ、ｙ４及びｙ２ｃについて同じ値を示すような裁断計画に相当するツリーＴにおけるノードの作成を、回避するか又は最小にする。
【０１２０】
ここで記載した第三の実施態様では、それぞれのノードの作成工程Ｅ３５で、ノードを作成する前に、そのノードが、ツリーに既に作成されたノードを伴う裁断計画と同型である部分的裁断計画又は全裁断計画を示すものではない、ということが保証される。
【０１２１】
これを行うために、ここで記載した実施態様では、辞書式の規定が、位置決め制約に付加される。例えば、以下の２つの規定を追加することができる：
−  最後のガラス片が、先行するガラス片の上方に置かれるのであれば、この最後のガラス片のフレーム番号は、先行するガラス片のフレーム番号よりも小さいものでなければならない；及び
−  最後のガラス片が、先行するガラス片の右側に置かれるのであれば、この最後のガラス片のフレーム番号は、先行するガラス片のフレーム番号よりも大きいものであるか、又は先行するガラス片のフレーム番号に等しいものでなければならない。
【０１２２】
同型の裁断計画が保存されるリスクを低減するために、例として、以下の２つの条件のうち少なくとも一つを満足するときにのみ、新しいレベル１を開くことを決定する、ということもまた可能である：
−  条件１：Ｋ個の先行するレベル１が、同じフレームに置かれる少なくとも一つのガラス片を含む。例えば、図２Ａの状況では、Ｋ＝２であり、２つの先行するレベル１の複数のガラス片とは、それぞれ、｛Ｐ１１、Ｐ２１、Ｐ２２｝及び｛Ｐ１２、Ｐ１３｝であり；したがって、これらのレベル１のそれぞれが、フレームＣ１の少なくとも一つのガラス片を含み、したがって、条件１を満足する；及び
−  条件２：最後のＱ個のレベル１について、最後に配置されたガラス片のフレームの順番が増加する。例として、図２Ａの状況では、Ｑ＝２であり、２つのレベル１で最後に置かれたガラス片は、それぞれ、Ｐ２２及びＰ１３であり；フレーム（Ｃ２、Ｃ１）は、順番が減少しており、したがって、条件２を満足しない。
【符号の説明】
【０１２３】
Ｃｉ、Ｃ１、Ｃ２    フレーム
Ｐ１１、Ｐ１２、Ｐ１３、Ｐ２１、Ｐ２２    ガラス片
ＰＬＦ１、ＰＬＦ２、ＰＬＦ３    ガラス板
ＰＤ１、ＰＤ２    全裁断計画
ＰＤＰ    部分的裁断計画
ｄ１、ｄ２、ｄ３、ｄ４、ｄ５    裁断部分
１００    決定装置（コンピューター）
１０１    プロセッサ
１０２    ＲＯＭ
１０３    ＲＡＭ
１０４    キーボード
１０５    スクリーン
１０６    ハードディスク
ＰＧ    コンピュータープログラム
ｘ１ｌ    最も右側の裁断機１の左側の位置
ｘ１ｒ    最も右側の裁断機１の右側の位置
ｙ２ｃ    最も上部の裁断機２の天井側の位置
ｙ２ｆ    最も上部の裁断機２の床側の位置
ｘ３    最後に配置されたガラス片の右側の位置
ｙ４    最後に配置されたガラス片の最上部の位置
ＭＴ    ２入力表
Ｔ１    ボックス
【図１】
2019535053.tif 000003
【図２Ａ】
2019535053.tif 000004
【図２Ｂ】
2019535053.tif 000005
【図３】
2019535053.tif 000006
【図４】
2019535053.tif 000007
【図５】
2019535053.tif 000008
【図６】
2019535053.tif 000009
【図７】
2019535053.tif 000010
【図８】
2019535053.tif 000011
【図９】
2019535053.tif 000012
【図１０】
2019535053.tif 000013
【国際調査報告】
2019535053.tif 000014
2019535053.tif 000015
2019535053.tif 000016
2019535053.tif 000017
2019535053.tif 000018
2019535053.tif 000019