(57)【要約】【課題】穴あけ位置を基板に平行な矩形（加工矩形、走査矩形又は走査エリア）で分割する際に、加工矩形間移動時間の和や加工矩形内加工時間の和を最小化する加工矩形の配置を決定する。【解決手段】各加工矩形を配置するときの評価値（加工矩形間の移動時間と加工矩形内の加工時間の和、加工矩形間の移動時間の和、又は、加工矩形内の加工時間の和）の総和を最小化するように加工矩形を配置する。【選択図】      図１３
2004272791.tif 000002
【特許請求の範囲】
【請求項１】
加工位置を複数の加工矩形に分割して、加工矩形内の加工位置連続加工と次の加工矩形への矩形間移動を繰り返すような加工を行なうための加工計画において、
各加工矩形を配置するときの評価値の総和を最小化するように加工矩形を配置することを特徴とする加工矩形の配置方法。
【請求項２】
前記評価値として、加工矩形間の移動時間と加工矩形内の加工時間の和を用いることを特徴とする請求項１に記載の加工矩形の配置方法。
【請求項３】
前記評価値として、加工矩形間の移動時間を用いることを特徴とする請求項１に記載の加工矩形の配置方法。
【請求項４】
前記評価値として、加工矩形内の加工時間を用いることを特徴とする請求項１に記載の加工矩形の配置方法。
【請求項５】
前記加工矩形内の加工時間を、加工位置間移動の平均移動距離予想値を基にして算出することを特徴とする請求項２又は４に記載の加工矩形の配置方法。
【請求項６】
前記平均移動距離予想値は、加工矩形内の加工位置密度に基づいて評価することを特徴とする請求項５に記載の加工矩形の配置方法。
【請求項７】
前記加工位置密度の基づき方は、密度の逆数の１／２乗に比例するようにすることを特徴とする請求項６に記載の加工矩形の配置方法。
【請求項８】
前記加工矩形内の加工時間を、加工位置間移動の平均移動距離の予想分布を基にして算出することを特徴とする請求項２又は４に記載の加工矩形の配置方法。
【請求項９】
前記平均移動距離の予想分布は、正規分布又は対数正規分布であることを特徴とする請求項８に記載の加工矩形の配置方法。
【請求項１０】
加工位置を複数の走査矩形に分割して、走査矩形内の加工位置連続加工と次の走査矩形への矩形間移動を繰り返すような加工を行なうための加工計画であって、
矩形間移動優先方向を決めて加工計画をする際に、
各走査矩形を配置するときの評価値の総和を最小化するように走査矩形を配置することを特徴とする走査矩形の配置方法。
【請求項１１】
前記評価値として、走査矩形間の移動時間と走査矩形内の加工時間の和を用いることを特徴とする請求項１０に記載の走査矩形の配置方法。
【請求項１２】
前記評価値として、走査矩形間の移動時間を用いることを特徴とする請求項１０に記載の走査矩形の配置方法。
【請求項１３】
前記評価値として、走査矩形内の加工時間を用いることを特徴とする請求項１０に記載の走査矩形の配置方法。
【請求項１４】
前記走査矩形内の加工時間を、加工位置間移動の平均移動距離予想値を基にして算出することを特徴とする請求項１１又は１３に記載の走査矩形の配置方法。
【請求項１５】
前記平均移動距離予想値は、走査矩形内の加工位置密度に基づいて評価することを特徴とする請求項１４に記載の走査矩形の配置方法。
【請求項１６】
前記加工位置密度の基づき方は、密度の逆数の１／２乗に比例するようにすることを特徴とする請求項１５に記載の走査矩形の配置方法。
【請求項１７】
前記加工矩形内の加工時間を、加工位置間移動の平均移動距離の予想分布を基にして算出することを特徴とする請求項１１又は１３に記載の走査矩形の配置方法。
【請求項１８】
前記平均移動距離の予想分布は、正規分布又は対数正規分布であることを特徴とする請求項１７に記載の走査矩形の配置方法。
【請求項１９】
加工位置を複数の走査エリアに分割して、走査エリア内の加工位置連続加工と次の走査エリアへの矩形間移動を繰り返すような加工を行なうための加工計画であって、
矩形間移動優先方向を決めて加工計画をする際に、
矩形間移動非優先方向に走査矩形を配置する第１ステップにおいて、各走査矩形を配置するときの評価値の総和を最小化して、
各走査矩形それぞれについて矩形間移動優先方向に走査エリアを配置する第２ステップにおいて、各走査エリアを配置するときの評価値の総和を最小化するようにして、走査エリアを配置することを特徴とする走査エリアの配置方法。
【請求項２０】
前記評価値として、走査エリア間又は走査矩形間の移動時間と走査エリア内又は走査矩形内の加工時間の和を用いることを特徴とする請求項１９に記載の走査エリアの配置方法。
【請求項２１】
前記評価値として、走査エリア間又は走査矩形間の移動時間を用いることを特徴とする請求項１９に記載の走査エリアの配置方法。
【請求項２２】
前記評価値として、走査エリア内又は走査矩形内の加工時間を用いることを特徴とする請求項１９に記載の走査エリアの配置方法。
【請求項２３】
前記走査エリア内又は走査矩形内の加工時間を、加工位置間移動の平均移動距離予想値を基にして算出することを特徴とする請求項２０又は２２に記載の走査エリアの配置方法。
【請求項２４】
前記平均移動距離予想値は、走査エリア内又は走査矩形内の加工位置密度に基づいて評価することを特徴とする請求項２３に記載の走査エリアの配置方法。
【請求項２５】
前記加工位置密度の基づき方は、密度の逆数の１／２乗に比例するようにすることを特徴とする請求項２４に記載の走査エリアの配置方法。
【請求項２６】
前記走査矩形と走査エリアで比例定数をそれぞれ設定することを特徴とする請求項２５に記載の走査エリアの配置方法。
【請求項２７】
加工位置を複数の走査エリアに分割して、矩形間移動停止中の走査エリア内の加工位置連続加工と次の走査エリアへの矩形間移動を繰り返すような加工を行なうための加工計画であって、
矩形間移動優先方向を決めて加工計画をする際に、
矩形間移動非優先方向に走査矩形を配置するときに、
該走査矩形について走査エリア間移動優先方向に走査エリアを配置するときの評価値の総和を最小化するように走査矩形を配置することを特徴とする走査エリアの配置方法。
【請求項２８】
前記走査矩形を配置するときの評価値として、走査エリアの数を用いることを特徴とする請求項２７に記載の走査エリアの配置方法。
【請求項２９】
前記走査矩形を配置するときの評価値として、加工時間の総和、走査エリア間移動時間の総和、又は、走査エリア内加工位置加工時間の総和を用いることを特徴とする請求項２７に記載の走査エリアの配置方法。
【請求項３０】
請求項１乃至２９のいずれかに記載の配置方法により配置が決定された加工矩形、走査矩形又は走査エリアにより加工を行なうことを特徴とする加工方法。
【請求項３１】
請求項１乃至２９のいずれかに記載の配置方法又は請求項３０に記載の加工方法を実施するためのコンピュータプログラム。
【請求項３２】
加工位置を複数の加工矩形に分割して、加工矩形内の加工位置連続加工と次の加工矩形への矩形間移動を繰り返すような加工を行なうための加工計画において、
各加工矩形を配置するときの評価値の総和を最小化するように加工矩形を配置する手段を備えたことを特徴とする加工矩形の配置装置。
【請求項３３】
加工位置を複数の走査矩形に分割して、走査矩形内の加工位置連続加工と次の走査矩形への矩形間移動を繰り返すような加工を行なうための加工計画であって、
矩形間移動優先方向を決めて加工計画をする際に、各走査矩形を配置するときの評価値の総和を最小化するように走査矩形を配置する手段を備えたことを特徴とする走査矩形の配置装置。
【請求項３４】
加工位置を複数の走査エリアに分割して、走査エリア内の加工位置連続加工と次の走査エリアへの矩形間移動を繰り返すような加工を行なうための加工計画であって、
矩形間移動優先方向を決めて加工計画をする際に、矩形間移動非優先方向に走査矩形を配置する第１ステップにおいて、各走査矩形を配置するときの評価値の総和を最小化する手段と、
各走査矩形それぞれについて矩形間移動優先方向に走査エリアを配置する第２ステップにおいて、各走査エリアを配置するときの評価値の総和を最小化するようにして、走査エリアを配置する手段と、
を備えたことを特徴とする走査エリアの配置装置。
【請求項３５】
加工位置を複数の走査エリアに分割して、矩形間移動停止中の走査エリア内の加工位置連続加工と次の走査エリアへの矩形間移動を繰り返すような加工を行なうための加工計画であって、
矩形間移動優先方向を決めて加工計画をする際に、
矩形間移動非優先方向に走査矩形を配置する手段と、
該走査矩形について走査エリア間移動優先方向に走査エリアを配置するときの評価値の総和を最小化するように走査矩形を配置する手段と、
を備えたことを特徴とする走査エリアの配置装置。
【請求項３６】
請求項３２乃至３５のいずれかに記載の配置装置を含むことを特徴とする加工装置。
【請求項３７】
請求項３２乃至３５のいずれかに記載の配置装置又は請求項３５に記載の加工装置を実現するためのコンピュータプログラム。
【請求項３８】
請求項３１又は３７に記載のコンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、加工矩形の配置方法及び装置に係り、特に、レーザ穴あけ機加工時のＸＹステージやガルバノスキャナの動作を最適に計画する加工計画プログラムに関して、穴あけ位置を基板に平行な矩形（加工矩形、走査矩形又は走査エリア）で分割する工程において、加工矩形間移動時間の和や加工矩形内加工時間の和を最小化するような加工矩形の配置を決定することが可能な、加工矩形の配置方法及び装置、該配置方法や装置を用いた加工方法及び加工装置、該加工方法を実施するためのコンピュータプログラム、前記加工装置を実現するためのコンピュータプログラム、及び、該コンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体に関する。
【０００２】
【従来の技術】
一般的には、レーザ穴あけ加工機による加工は、基板上の加工位置に対して、低速であるが広範囲に位置決め可能であるＸＹステージ（以下では単に「ステージ」と呼ぶ）と、狭範囲であるが高速に位置決め可能なガルバノスキャナ（以下では単に「スキャナ」と呼ぶ）を用いて位置決めを行ない、位置決め完了後に照射を行なう加工方法を採っている。
【０００３】
併用の仕方により、加工方法は、各回の位置決めにおいてステージとスキャナを併用することはないステップアンドリピート（ステージ停止加工）と、併用する協調制御（ステージ非停止加工）に分かれる。
【０００４】
ところで、レーザ穴あけ機の市場価値の１つとして、加工速度が挙げられ、そのための手段の１つとして、加工実行前段階における加工計画が適用されることがある。
【０００５】
ここでは、ステップアンドリピート加工、ステージ非停止加工に拘わらず、一連して加工中（順次穴あけ中）の状態と、加工箇所間を加工を伴わずに移動中の状態を、交互に繰り返すような加工方法の際の加工計画を想定する（大体の加工計画は、これに当たる）。ここで、ステップアンドリピート加工では、一連して加工する穴は、走査エリア、即ち、ガルバノのみを振って加工する際の加工可能領域に広がるよう、限定される。又、ここで想定するステージ非停止加工では、穴あけ位置の加工中にＸＹステージがＸ、Ｙいずれかの方向に移動しながら加工を行なうような加工方法の場合を考える。このとき、一連して加工する穴は、ステージが停止している方向の幅は（その方向の）走査エリア幅以下の範囲に広がるよう限定される。以下では、この限定範囲（ステージ非停止加工では、ステージ移動方向の範囲は、その方向に最大値を持つ穴あけ位置と最小値を持つ穴あけ位置の間の範囲とする）を「加工矩形（停止加工では走査エリア、非停止加工ては走査矩形と称す）」と称する。
【０００６】
このような限定の上で、加工計画は大略次の３つのステップを持つことができる。
【０００７】
［ステップ１］基板上の穴あけ位置を複数の加工矩形で分割する。
［ステップ２］各加工矩形内の加工時間が最小となるように、最適化を行なう。
［ステップ３］ＸＹステージの移動経路を決定する。
【０００８】
ここで、［ステップ２］と［ステップ３］は、場合によっては逆順でもよい。
【０００９】
ステップアンドリピート加工に適用される場合、次のように処理される（図１参照）。
【００１０】
［ステップ１ａ］基板上の穴あけ位置を複数の走査エリアで分割する。
［ステップ２ａ］各走査エリア内の加工時間が最小となるように、穴あけ位置訪問順序を最適化する。
［ステップ３ａ］走査エリア（中心）位置の訪問順序を最適化する。
【００１１】
このような加工計画の先行技術として、特許文献１が挙げられる。
【００１２】
又、ステージ非停止加工に適用する場合、次のように処理することが考えられる（図２参照）。
【００１３】
［ステップ１ｂ］基板上の穴あけ位置を、複数の走査矩形で分割する。
［ステップ２ｂ］各走査矩形内の加工時間が最小となるように、ＸＹステージ動作速度を最大化しつつ穴あけ位置訪問順序を最適化する。
［ステップ３ｂ］走査矩形の訪問順序、及び、各走査矩形の加工開始側が矩形両端のいずれか、を最適化する。
【００１４】
なお、図１、図２では、基板が固定されていて、走査エリアが移動するような図になっているが、実際にはそうではなく、既に説明した装置構成の如く走査エリアが固定されていて、基板が載せられたＸＹステージが図で示した方向とは逆に移動することに注意が必要である。
【００１５】
以下に、これらの加工計画が３ステップである場合の先行技術を説明する。
【００１６】
特許文献１によれば、図３に示す如く、まず基板を走査エリアの大きさ毎に端から割って暫定的に走査エリアを定め（点線）、次いでそれら暫定的な走査エリアに、「配置作業」を行なう順序を定め（番号を付加した）、次いでその順序に従って、各走査エリアのＸ座標最小値ＸＭＩＮとＹ座標最小値ＹＭＩＮを検索して、座標（ＸＭＩＮ，ＹＭＩＮ）が走査エリアの４隅のうち、Ｘ座標、Ｙ座標が最小な点に一致するようにエリアを確定していく。この方法による配置では、エリア数は暫定的な配置と比較して、同一あるいは運がよければ減少する。しかし、エリア数を削減できても、ステージ移動時間を削減できるとは限らない。即ち、このようなエリア配置では、移動方向や距離が均一でなくなるため、場合によっては、ステージ移動時間を削減できないことも有り得た。
【００１７】
ステージ非停止加工に適用することを示した図２の例についても、図２から察しがつけられるように、全く同様の点に問題があった。即ち、エリア配置位置にステージ移動時間を削減するための工夫がないので、エリア数が少なくてもステージ移動時間が短いとは限らなかった。
【００１８】
上記のようではなく、最初から斜め移動が無いように、ＸＹステージの優先的な移動方向をＸ又はＹに揃えてしまう方法を採ることも考えられる。即ち、図４に示すようなＸＹステージの優先移動方向をＸに揃えた例のように、基板の一端から優先方向に向かって順次加工し、もう一端に突き当たったら、非優先方向に１ステップ移動して、今度は優先方向に逆向きに順次加工していく。ステージ移動経路は、ステップアンドリピート加工でもステージ非停止加工でも蛇行状となる。つまり、ステージ移動優先方向を決めている場合は、２ステップで十分である。
【００１９】
このような２ステップで十分な場合の加工計画の先行技術として、ステップアンドリピート加工としては特許文献２はこの技術を含み、又、ステージ非停止加工としては、特許文献３、４等はこの技術を含んでいる。
【００２０】
以下に、これらの加工計画が２ステップである場合の先行技術を説明する。
【００２１】
図５に示す特許文献２によれば、「ＸＹステージを固定した状態で…第１の矩形平面領域（走査エリアに等しい）内へ、照射した後、Ｘ軸ステージ又はＹ軸ステージを移動させ、前記第１の矩形平面領域と重なることなく、隣接した、前記第１の矩形平面領域と同一形状からなる第２の矩形平面領域への所定のレーザ光線照射が行なわれ」るが、重なることなく隣接した配置では、ステージの移動距離は最小ではない。つまり、この技術はエリア配置の加工計画とは言えない。次いで、ステージ非停止加工の技術である特許文献３、４についても、やはり、走査矩形の配置に関して言及されていない。なお、図６に示す特許文献４の［図７］からは、加工矩形の配置に関して、加工時間を最小化するための工夫を見出すことができない。
【００２２】
一方、図７に示す如く、まずライン数を最小化し、ステージ非停止加工における（個数最小の）走査矩形の配置を暫定的に定めて（第１のステップ）、次いで各ラインにおける走査エリア数を最小化する（第２のステップ）ことも考えられる。この際、ライン数を最小化する問題及び各ラインにおける走査エリア数を最小化する問題を、同一の問題であると認識し、その問題を「ＳＰＬＩＴ」と仮名し、問題ＳＰＬＩＴを、最短路問題として定式化することが考えられる。最短路問題は最適解を得ることができる問題として知られている。従って、問題ＳＰＬＩＴの最適解を得ることができる。
【００２３】
【特許文献１】
特開２０００−３４３２６０号公報
【特許文献２】
特許第３０７７５３９号
【特許文献３】
特開２０００−１００６０８号公報
【特許文献４】
特開２００２−１５６７号公報
【００２４】
【発明が解決しようとする課題】
しかしながら、この方法は、未だ次のような問題を抱えていた。
【００２５】
［課題１］問題ＳＰＬＩＴは、集合を部分集合に分割するときの部分集合の数のみを最小化することを目的としている。即ち、ＸＹステージ移動時間最小化や各走査エリア内の加工時間最小化等への考慮が不足している。
［課題２］数の最小化だけが目的なら、もっと簡単な方法がある。
［課題３］ラインの数を最小化する際に、各ラインを配置する際の評価
（効果）が考慮されていない。
【００２６】
補足しておくが、［課題１］については、数の最小化以外にも、各部分集合内の要素に値のギャップが無いように工夫することもできる。しかし、加工時間を削減するための直接的な手段ではなく、改善の余地がある。
【００２７】
又、［課題２］については、図８に示すように、エリアの重複が無いように端から定めていけば、エリア数自体は必ず最小となる。このような簡単な決め方があるにも拘わらず、わざわざ最短路問題の解法を用いている。
【００２８】
又、［課題３］については、図９に比較を示す如く、左図（Ａ）、右図（Ｂ）共にラインの数は同一であり、最小数である。従って、左右の図は共に、ＳＰＬＩＴの解であり得る。しかし、各ラインを走査エリアに分割した結果、右図（Ｂ）の走査エリア配置では左図（Ａ）の配置と比べてステージ移動回数が多くなってしまうが、ＳＰＬＩＴの定義及び解法によれば、左図（Ａ）のような走査エリア数が最小の分割が得られる保証は無い。
【００２９】
一方、ステージ非停止加工に関しても、図１０に示す如く、走査矩形の数を最小化することが考えられる。しかし、この工程は、既に図７に示したライン数最小化の工程と同一であり、図７の例と全く同一の課題を有していた。
【００３０】
本発明は、前記従来の問題点を解決するべくなされたもので、加工矩形間の移動時間の和や加工矩形内加工時間の和を最小化するような加工矩形、走査矩形又は走査エリアの配置を決定することを課題とする。
【００３１】
【課題を解決するための手段】
本発明は、加工位置を複数の加工矩形に分割して、加工矩形内の加工位置連続加工と次の加工矩形への矩形間移動を繰り返すような加工を行なうための加工計画において、各加工矩形を配置するときの評価値の総和を最小化するように加工矩形を配置して、前記課題を解決したものである。
【００３２】
又、前記評価値として、加工矩形間の移動時間と加工矩形内の加工時間の和、加工矩形内の移動時間、又は、加工矩形内の加工時間を用いるようにしたものである。
【００３３】
又、前記加工矩形内の加工時間を、加工位置間移動の平均移動距離予想値を基にして算出するようにしたものである。
【００３４】
又、前記平均移動距離予想値を、加工矩形内の加工位置密度に基づいて評価するようにしたものである。
【００３５】
又、前記加工位置密度の基づき方を、密度の逆数の１／２乗に比例するようにしたものである。
【００３６】
又、前記加工矩形内の加工時間を、加工位置間移動の平均移動距離の予想分布を基にして算出するようにしたものである。
【００３７】
又、前記平均移動距離の予想分布は、正規分布又は対数正規分布であるようにしたものである。
【００３８】
本発明は、又、加工位置を複数の走査矩形に分割して、走査矩形内の加工位置連続加工と次の走査矩形への矩形間移動を繰り返すような加工を行なうための加工計画であって、矩形間移動優先方向を決めて加工計画をする際に、各走査矩形を配置するときの評価値の総和を最小化するように走査矩形を配置するようにして、前記課題を解決したものである。
【００３９】
又、前記評価値として、走査矩形間の移動時間と走査矩形内の加工時間の和、走査矩形間の移動時間、又は、走査矩形内の加工時間を用いるようにしたものである。
【００４０】
又、前記走査矩形内の加工時間を、加工位置間移動の平均移動距離予想値を基にして算出するようにしたものである。
【００４１】
又、前記平均移動距離予想値を、走査矩形内の加工位置密度に基づいて評価するようにしたものである。
【００４２】
又、前記加工位置密度の基づき方を、密度の逆数の１／２乗に比例するようにしたものである。
【００４３】
又、前記加工矩形内の加工時間を、加工位置間移動の平均移動距離の予想分布を基にして算出するようにしたものである。
【００４４】
又、前記平均移動距離の予想分布は、正規分布又は対数正規分布であるようにしたものである。
【００４５】
本発明は、又、加工位置を複数の走査エリアに分割して、走査エリア内の加工位置連続加工と次の走査エリアへの矩形間移動を繰り返すような加工を行なうための加工計画であって、矩形間移動優先方向を決めて加工計画をする際に、矩形間移動非優先方向に走査矩形を配置する第１ステップにおいて、各走査矩形を配置するときの評価値の総和を最小化して、各走査矩形それぞれについて矩形間移動優先方向に走査エリアを配置する第２ステップにおいて、各走査エリアを配置するときの評価値の総和を最小化するようにして、走査エリアを配置するようにして、前記課題を解決したものである。
【００４６】
又、前記評価値として、走査エリア間又は走査矩形間の移動時間と走査エリア内又は走査矩形内の加工時間の和、走査エリア間又は走査矩形間の移動時間、又は、走査エリア内又は走査矩形内の加工時間を用いるようにしたものである。
【００４７】
又、前記走査エリア内又は走査矩形内の加工時間を、加工位置間移動の平均移動距離予想値を基にして算出するようにしたものである。
【００４８】
又、前記平均移動距離予想値を、走査エリア内又は走査矩形内の加工位置密度に基づいて評価するようにしたものである。
【００４９】
又、前記加工位置密度の基づき方を、密度の逆数の１／２乗に比例するようにするしたものである。
【００５０】
又、前記走査矩形と走査エリアで比例定数をそれぞれ設定するようにしたものである。
【００５１】
本発明は、又、加工位置を複数の走査エリアに分割して、矩形間移動停止中の走査エリア内の加工位置連続加工と次の走査エリアへの矩形間移動を繰り返すような加工を行なうための加工計画であって、矩形間移動優先方向を決めて加工計画をする際に、矩形間移動非優先方向に走査矩形を配置するときに、該走査矩形について走査エリア間移動優先方向に走査エリアを配置するときの評価値の総和を最小化するように走査矩形を配置するようにするしたものである。
【００５２】
又、前記走査矩形を配置するときの評価値として、走査エリアの数、加工時間の総和、走査エリア間移動時間の総和、又は、走査エリア内加工位置加工時間の総和を用いるようにするしたものである。
【００５３】
本発明は、又、前記の配置方法により配置が決定された加工矩形により加工を行なうことを特徴とする加工方法を提供するものである。
【００５４】
又、前記の配置方法又は加工方法を実施するためのコンピュータプログラムを提供するものである。
【００５５】
本発明は、又、加工位置を複数の加工矩形に分割して、加工矩形内の加工位置連続加工と次の加工矩形への矩形間移動を繰り返すような加工を行なうための加工計画において、各加工矩形を配置するときの評価値の総和を最小化するように加工矩形を配置する手段を備えたことを特徴とする加工矩形の配置装置を提供するものである。
【００５６】
又、加工位置を複数の走査矩形に分割して、走査矩形内の加工位置連続加工と次の走査矩形への矩形間移動を繰り返すような加工を行なうための加工計画であって、矩形間移動優先方向を決めて加工計画をする際に、各走査矩形を配置するときの評価値の総和を最小化するように走査矩形を配置する手段を備えたことを特徴とする走査矩形の配置装置を提供するものである。
【００５７】
又、加工位置を複数の走査エリアに分割して、走査エリア内の加工位置連続加工と次の走査エリアへの矩形間移動を繰り返すような加工を行なうための加工計画であって、矩形間移動優先方向を決めて加工計画をする際に、矩形間移動非優先方向に走査矩形を配置する第１ステップにおいて、各走査矩形を配置するときの評価値の総和を最小化する手段と、各走査矩形それぞれについて矩形間移動優先方向に走査エリアを配置する第２ステップにおいて、各走査エリアを配置するときの評価値の総和を最小化するようにして、走査エリアを配置する手段と、を備えたことを特徴とする走査エリアの配置装置を提供するものである。
【００５８】
又、加工位置を複数の走査エリアに分割して、矩形間移動停止中の走査エリア内の加工位置連続加工と次の走査エリアへの矩形間移動を繰り返すような加工を行なうための加工計画であって、矩形間移動優先方向を決めて加工計画をする際に、矩形間移動非優先方向に走査矩形を配置する手段と、該走査矩形について走査エリア間移動優先方向に走査エリアを配置するときの評価値の総和を最小化するように走査矩形を配置する手段と、を備えたことを特徴とする走査エリアの配置装置を提供するものである。
【００５９】
本発明は、又、前記の配置装置を含むことを特徴とする加工装置を提供するものである。
【００６０】
又、前記の配置装置又は加工装置を実現するためのコンピュータプログラムを提供するものである。
【００６１】
又、前記のコンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体を提供するものである。
【００６２】
【発明の実施の形態】
以下図面を参照して、ＸＹステージとガルバノスキャナを備えたレーザ穴あけ機により穴をあける場合に適用した、本発明の実施形態を詳細に説明する。
【００６３】
本実施形態は、図１１に示す如く、レーザ穴あけ機３８と、例えばハードディスクやフレキシブルディスク等の外部メモリに記憶された、前記レーザ穴あけ機３８が加工を行なうための加工データファイル群４２、該加工データファイル群４２を変換する加工データ変換プログラム（Ｐｒｇ）４４、例えば内部メモリに記憶された加工データ４６、例えば外部メモリに記録された動作モデルファイル４８、該動作モデルファイル４８を読み込むための動作モデルファイル読込みプログラム（Ｐｒｇ）５０、例えば内部メモリに記憶された動作モデルデータ５２、本発明に係る加工計画プログラム（Ｐｒｇ）５４、前記レーザ穴あけ機３８を制御する加工制御プログラム（Ｐｒｇ）５６を含む、前記レーザ穴あけ機３８と通信可能なパソコン（ＰＣ）４０とを備えている。
【００６４】
なお、図１１では、加工を制御する加工制御プログラム５６と、加工を計画する加工計画プログラム５４が、同じＰＣ４０内に収まっており、加工計画がオンラインで処理されるが、これらは別個でもよい。即ち、加工計画プログラム５４は、オフラインで実行可能である。
【００６５】
前記レーザ穴あけ機３８は、例えば、レーザ発振器１０が１つの２軸加工機とされている。なお、本発明の適用対象の軸数は２に限定されず、１又は３以上であっても良い。又、上記構成は、ステップアンドリピート加工、ステージ非停止加工に拘わらない。
【００６６】
以下、レーザ穴あけ機のオンライン形態の場合について説明する。なお、オフラインでも作用は同じである。
【００６７】
本実施形態において、加工制御プログラム５６の収まるＰＣ４０と通信可能なレーザ穴あけ機３８は、加工データ４６に従って、加工制御プログラム５６により制御され、加工を行なう。加工データ４６は、通常ハードディスクやフレキシブルディスク等の外部メモリに有る加工データファイル群４２を、加工データ変換プログラム４４で変換することにより得られる。加工データ４６は、レーザ穴あけ機３８を効率良く動かすために、加工計画プログラム５４により更新される。この加工計画プログラム５４は、内部機器（ガルバノスキャナ及びＸＹステージ）の動作をモデル化した動作モデル５２を用いる。この動作モデル５２は、通常、内部メモリに常駐していないので、外部メモリにある動作モデルファイル４８を、動作モデルファイル読込みプログラム５０を用いて読み込むことにより得る。
【００６８】
前記ＰＣ４０は、前記加工データファイル群４２、加工データ変換プログラム４４、動作モデルファイル４８、動作モデルファイル読込みプログラム５０、動作モデルデータ５２、加工計画プログラム５４、加工制御プログラム５６を含み（加工データファイル群４２及び動作モデルファイル４８は、読込みが可能という意味で含むとする）、プログラム４４、５０、５４、５６を実行可能である。
【００６９】
以下、詳細に説明する。
【００７０】
図７に示した例の問題ＳＰＬＩＴは、実数（加工位置（ここでは穴あけ位置）の分割する方向の座標値）の有限集合を、次のような部分集合に分割（ここで言う分割とは、集合を、互いに素、且つ合併が元の集合に等しいような部分集合に、分けることを意味する）する問題である（図１２に例を示す）：
・各部分集合の要素の範囲（範囲とは、最大値と最小値の差を意味する）が所定値以下、且つ、
・２つの部分集合Ａｉ、Ａｊについて、Ａｉの任意の要素がＡｊの任意の要素より小さければ（大きければ）、Ａｉの最大値はＡｊの最小値より小さく（大きく）、
・部分集合の個数が最小である。
【００７１】
ここで所定値とは、スキャンエリアのサイズである。
【００７２】
問題ＳＰＬＩＴは、最短路問題に帰着させることができる。即ち、ｎ要素の順序集合（昇順ソート済みの集合）Ａ＝｛ａ１，ａ２，…，ａｎ｝（各ａｉは穴あけ位置の分割する方向の座標値を表わす（重複するデータは取り除く））に対し、次のようなネットワークを考える（図１３に例を示す）：
１）集合Ａの各要素ａ１は、それぞれｎ＋１頂点からなるネットワークの頂点Ｖ＝｛ｖ１，ｖ２，…，ｖｎ，  ｖｎ＋１｝の要素ｖｉに対応付けられている。
２）ネットワークの始点は頂点ｖ１である。
３）ネットワークの終点は頂点ｖｎ＋１であって、ａｔ＋ｄ≧ａｎを満たす頂点ｖｔ、ｖｎ＋１が接続されている（ｄはスキャンエリアのサイズを表わす）。
４）ａｊ＋ｄ≧ａｋ−１を満たす頂点ｖｊ，ｖｋ（ｊ＜ｋ）が接続されている。
５）頂点ｖｊ，ｖｋ（ｊ＜ｋ）を接続する枝のコストは、全て１（又は同一の正値）である。
【００７３】
このようなネットワークの最短路問題を解いて、最短路上の頂点に対応する要素毎にソートされた集合を区切り、各区間を１つの部分集合とすれば、最小個数の分割を得ることができる。
【００７４】
これに対して、次のような、問題ＳＰＬＩＴを進展させた問題、ＡＤＶ−ＳＰＬＩＴを考える：
・各部分集合の要素の範囲が所定値以下、且つ、
・２つの部分集合Ａｉ、Ａｊについて、Ａｉの任意の要素がＡｊの任意の要素より小さければ（大きければ）、Ａｉの最大値はＡｊの最小値より小さく（大きく）、
・部分集合それぞれに設定される評価値の合計が最小である、
ような部分集合分割を求める問題。
【００７５】
ＳＰＬＩＴとＡＤＶ−ＳＰＬＩＴの違いは、上記箇条の第３の文の「部分集合それぞれに設定される評価値の合計が最小」とする点のみである。この評価値に関しては、後述する。なお、評価値が全て１であるＡＤＶ−ＳＰＬＩＴはＳＰＬＩＴと同一である。
【００７６】
このＡＤＶ−ＳＰＬＩＴもＳＰＬＩＴと同じく、最短路問題に帰着させることができる。即ち、ｎ要素の昇順の順序集合Ａ＝｛ａ１，ａ２，…，ａｎ｝に対し、次のようなネットワークを考える：
１）集合Ａの各要素ａ１は、それぞれｎ＋１頂点からなるネットワークの頂点Ｖ＝｛ｖ１，ｖ２，…，ｖｎ，ｖｎ＋１｝の要素ｖｉに対応付けられている。
２）ネットワークの始点は頂点ｖ１である。
３）ネットワークの終点は頂点ｖｎ＋１であって、ａｔ＋ｄ≧ａｎを満たす頂点ｖｔ、ｖｎ＋１が接続されている（ｄはスキャンエリアのサイズを表わす）。
４）ａｊ＋ｄ≧ａｋ−１を満たす頂点ｖｊ，ｖｋ（ｊ＜ｋ）が接続されている。
５）頂点ｖｊ，ｖｋ（ｊ＜ｋ）を接続する枝のコストは、適切な評価値である。
【００７７】
このネットワークとＳＰＬＩＴの場合のネットワークとの違いは、上記箇条の５文の「適切な評価値」という点のみである。違いは枝コストの設定方法のみなので、解法は同一でよい。即ち、最短路問題の任意の解法を利用する。
【００７８】
次に、評価値、即ち、頂点ｖｊ，ｖｋ（ｊ＜ｋ）を接続する枝のコストについて説明する。評価値の設定方法として、次の２つを挙げる。
【００７９】
［方法１］
上記２つのネットワークの始点から終点への全てのパスは、それぞれ１つの部分集合分割を表わす。パスが頂点ｖｊ，ｖｋ（ｊ＜ｋ）を通る場合、ａｊ以上ａｋ未満の値を要素とする集合Ａｊ＝｛ａｊ，…，ａｋ−１｝が、分割された結果の１つの部分集合である。そして、図１４の如く、この部分集合Ａｊ（，Ａｋ）を基に加工矩形を配置する。このとき、加工矩形が走査エリアならば、次の工程では巡回セールスマン問題（又はハミルトン路長最小化問題）として、走査矩形であっても、次の工程では移動コストや時間枠に制約を加えて巡回セールスマン問題を複雑にした問題として捉えて、加工矩形内の最適化を実行する。
【００８０】
ところで、面積Ａの領域にランダムにｎ個の点が配置している場合の最短巡回路長Ｌ（ｎ）（即ち、巡回セールスマン問題の最適解）は、ｎ→∞に対しβ√（Ａｎ）に収束する（βは適切な定数）ことが、Ｂｅａｒｄｗｏｏｄ−Ｈａｌｔｏｎ−Ｈａｍｍｅｒｓｌｅｙによって理論的に証明（ＢＨＨ定理）され（Ｊ．Ｂｅａｒｄｗｏｏｄ，  Ｊ．Ｈａｌｔｏｎ，ａｎｄ  Ｊ．Ｈａｍｍｅｒｓｌｅｙ．Ｔｈｅ  ｓｈｏｒｔｅｓｔ  ｐａｔｈ  ｔｈｒｏｕｇｈ  ｍａｎｙ  ｐｏｉｎｔｓ．Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｃａｍｂｒｉｄｇｅ  Ｐｈｉｌｏｓｏｐｈｉｃａｌ  Ｓｏｃｉｅｔｙ，５：２９９−３２７，１９５９．参照）、又、他の研究者らによって実験で確かめられている（実験的解析によると、βの値は約０．７２程度であるという）。従って、各回の移動距離の平均値は、ｎ→∞に対しβ√（Ａ／ｎ）に収束する。穴数ｎを面積Ａで割った値である密度という言葉を用いて言い換えると、穴数の増大につれて、移動距離の平均値は密度の逆数の１／２乗に比例定数βを掛けた値に漸近してくるということである。
【００８１】
本発明が主対象とする基板において、走査エリア又は走査矩形内の穴数の平均は、概ね数百から数万の範囲であって、無数に多くはないが、百を超える値である。従って十分大きいと判断し、移動距離の予測値が密度の逆数の１／２乗に比例すると仮定して、これを適用することを考える。
【００８２】
なお、走査矩形の場合は、巡回セールスマン問題ではなく、それより複雑な問題であるが、その場合でも、βの値が異なるが、やはり各回の移動距離の平均値がβ√（Ａ／ｎ）に近づくことが想像できるので、そのように仮定する。即ち、比例定数βとして、走査エリアに適用する場合と走査矩形に適用する場合とを別々に用意しておけばよい。あるいは、密度の逆数の１／２乗に比例ではなく、βの値が穴あけ位置の数ｎに応じて設定されるように、計算機実験により、例えば次式のように求めておいて、それを用いても構わない。
【００８３】
β（ｎ）＝α０＋α１／ｎ０．５＋α２／ｎ＋α３／ｎ１．５
ここで、α０〜α３は定数。
【００８４】
即ち、図１４のように、分割する方向の座標値ａがａｊ≦ａ≦ａｋ−１であるようなｎ（ｊ，ｋ）個の穴あけ位置をカバーするように加工矩形を配置するとき、その加工矩形内の加工時間Ｇ（ｊ，ｋ）を、次の式で評価する：
Ｇ（ｊ，ｋ）＝（ｎ（ｊ，ｋ）−１）＊ｔ（ｘバー）
【００８５】
ここで、面積Ｄ＊（ａｋ−１−ａｊ）、穴あけ位置数ｎ（ｊ，ｋ）に対して、平均移動距離の予想値は、（ｘバー）＝β√｛Ｄ＊（ａｋ−１−ａｊ）／ｎ（ｊ，ｋ）｝であるので、各点毎の予想値の加工時間（移動時間と照射時間の和）の平均値ｔ（ｘバー）は、
ｔ（ｘバー）＝ｇ（β√｛Ｄ＊（ａｋ−１−ａｊ）／ｎ（ｊ，ｋ）｝）＋ＳＴ
である。ここで、ｇ（ｘ）は、移動距離がｘであるときのガルバノ走査時間、Ｄは、走査エリアの一辺の長さ、ＳＴは、穴あけ加工のための照射などの作業時間を意味する。
【００８６】
又、このように加工矩形を配置するときの、次の加工矩形へ移動する際のステージ移動時間Ｓ（ｊ，ｋ）を、次の式で評価する：
Ｓ（ｊ，ｋ）＝ｓ（ａｋ−ａｊ）
【００８７】
ここで、ｓ（ｘ）は、移動距離がｘであるときの矩形間移動時間（ここではＸＹステージを用いている）を意味する。但し、次に移動すべき加工矩形が無い場合は、０とする。
【００８８】
そして、このように加工矩形を配置するときの評価Ｔ（ｊ，ｋ）を次の式で定義する：
Ｔ（ｊ，ｋ）＝Ｇ（ｊ，ｋ）＋Ｓ（ｊ，ｋ）
【００８９】
この評価式を用いて、各加工矩形を配置する際の評価を行い、評価値の合計を最小化するようにすれば、加工時間を最小化するような加工矩形配置を得ることができる。
【００９０】
なお、加工矩形の加工時間の総和のみを最小化したい場合は、Ｔ（ｊ，ｋ）の代わりにＧ（ｊ，ｋ）を、ステージの移動時間の総和のみを最小化したい場合は、Ｔ（ｊ，ｋ）の代わりにＳ（ｊ，ｋ）を、評価式として用いればよい。
【００９１】
又、加工矩形内の加工時間Ｇ（ｊ，ｋ）の評価式として、平均移動距離の予想値（１つの値）ではなく、移動距離の予想分布を用いることも可能である。即ち、移動距離ｘの分布が、密度関数ｆ（ｘ）に従っているとすれば、
【数１】
2004272791.tif 000003
のようにして計算することができる。
【００９２】
ｆ（ｘ）としては、最短巡回路における移動距離の分布であるから、次式のような、正規分布：
【数２】
2004272791.tif 000004
【００９３】
又、次式のような、正規分布の最頻値が０の側に寄った形をしている、対数正規分布：
【数３】
2004272791.tif 000005
などが適切である（最短巡回路における距離分布の実例を図１５に示す）ので、どちらかに当てはめる。平均値μは、例えばＢＨＨ定理に従って定めることができる、又、標準偏差σは、理論的あるいは実験的解析を通じて適当に定めることができる。
【００９４】
［方法２］
図７に示す如く、ステップアンドリピート加工における走査エリア分割は、走査矩形分割（ライン分割）をする第１のステップと、各走査矩形を走査エリアに分割する第２のステップによる。本方法は、この第１のステップの評価値に関する発案である。
【００９５】
図８に示したように、各ラインを走査エリアに分割する場合の分割数は、端から順にエリアの重複が無いように分割すれば最小となる（この最小分割数は即座に計算可能である）。即ち、図１６に示すように、第１ステップの評価値を、ラインから走査エリアへの最小分割数に設定して、その評価値に従ってＡＤＶ−ＳＰＬＩＴを定義して、最短路問題を解けば、ステージ移動優先方向が定まっている場合での基板全体の走査エリア分割数を、完全に最小化することができる。
【００９６】
あるいは、方法１で説明したように、第１ステップの評価値を、ラインから走査エリアへ分割する際の、加工時間の総和、又は、走査エリア間ステージ移動時間の総和、又は、走査エリア内加工位置加工時間の総和などとすることも可能である。
【００９７】
なお、前記実施形態においては、高速位置決め手段がガルバノとされ、低速位置決め手段がステージとされていたが、位置決め手段の種類や組合せはこれに限定されず、例えば出願人が特開２０００−７１０８９や特開２０００−３３４６３７で提案したような、リニアモータＸＹステージと高速加工機とを組み合わせたスクリーンカットシステム、あるいはフラッシュカットシステムであってもよい。
【００９８】
又、適用対象も、点状の加工を行なうレーザ穴あけ機に限定されず、線状の加工を行なうレーザ切断機、機械式ドリルの穴開け機、ヒューズ溶断機、マーキング装置、露光装置等にも同様に適用できる。
【００９９】
【発明の効果】
本発明によれば、矩形間移動優先方向がＸ又はＹに統一されたステップアンドリピート加工におけるラインの配置及び各ラインの走査エリアの配置を、より加工機に適合するように最適に定めることができる。又、加工中の移動方向がＸ又はＹに統一された矩形間移動中加工における走査矩形の配置を、より加工機に適合するように最適に定めることができる。
【図面の簡単な説明】
【図１】加工計画をステップアンドリピート加工に用いた場合の従来例を示す図
【図２】加工計画をステージ非停止加工に用いた場合の比較例を示す図
【図３】特開２０００−３４３２６０を説明するための図
【図４】ステージ優先移動方向を定めた場合の加工順序を示す平面図
【図５】特許第３０７７５３９号を説明するための図
【図６】特開２００２−１５６７号を説明するための図
【図７】走査矩形数を最小化した後、各走査矩形における走査エリアを最小化する比較例を示す図
【図８】端から重複がないようにエリアを配置する例を示す図
【図９】同一ライン数でも走査エリアの配置数が異なる例を示す図
【図１０】走査矩形数の最小化例を示す図
【図１１】本発明が適用されるレーザ穴あけ機の全体構成を示すブロック図
【図１２】本発明の実施形態における分割の説明図
【図１３】同じくネットワークの説明図
【図１４】同じく加工矩形の配置と評価式の説明図
【図１５】同じく移動距離の度数分布の例を示す図
【図１６】同じく、ラインの最小分割数を評価値とする場合のネットワークの例を示す図
【符号の説明】
３８…レーザ穴あけ機
４０…パソコン（ＰＣ）
５４…加工計画プログラム（Ｐｒｇ）
【図１】
2004272791.tif 000006
【図２】
2004272791.tif 000007
【図３】
2004272791.tif 000008
【図４】
2004272791.tif 000009
【図５】
2004272791.tif 000010
【図６】
2004272791.tif 000011
【図７】
2004272791.tif 000012
【図８】
2004272791.tif 000013
【図９】
2004272791.tif 000014
【図１０】
2004272791.tif 000015
【図１１】
2004272791.tif 000016
【図１２】
2004272791.tif 000017
【図１３】
2004272791.tif 000018
【図１４】
2004272791.tif 000019
【図１５】
2004272791.tif 000020
【図１６】
2004272791.tif 000021