(57)【特許請求の範囲】
【請求項１】
所定の高速走査エリア内で高速移動可能な高速位置決め手段と、前記高速走査エリアを越えて移動可能な低速位置決め手段を用いて、前記低速位置決め手段による高速走査エリアの位置決めを行なった後、前記高速位置決め手段による高速走査エリア内の位置決めを行なって、ワーク上に散在する加工位置を加工する際の加工計画方法であって、
ワーク全体の加工位置の第１の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第１の集合の要素ａ1,…,ａnとする第１の抽出工程と、
該第１の集合を、高速走査エリアの幅を用いて、互いに素な第１の部分集合に分割する第１の分割工程と、
前記第１の部分集合をもとに、加工位置を複数のグループに分ける工程と、
各グループ内の加工位置の第２の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第２の集合の要素とする第２の抽出工程と、
該第２の集合を、高速走査エリアの幅を用いて、互いに素な第２の部分集合に分割する第２の分割工程と、
前記第２の部分集合をもとに、加工位置を複数のグループに分ける工程と、
により、高速走査エリアの配置を決定することを特徴とする加工計画方法。
【請求項２】
前記第１の分割工程が、
前記第１の抽出工程により得られた第１の集合の各要素の値ａ1,…,ａn及び高速走査エリアの幅Ｄに基づいて、節点間の隣接の有無を判定することにより、仮想の有向ネットワークを構築する工程と、
得られた有向ネットワークに対し、第１の要素ａ1に該当する節点から他の節点への最短経路と最短路長を求める工程と、
前記有向ネットワークの終点の候補の集合である終点候補集合の節点に至る経路の中で、経路長が最短の経路を選択する工程と、
該最短経路上の節点に基づいて第１の部分集合に分割する工程と、
を含むことを特徴とする請求項１に記載の加工計画方法。
【請求項３】
前記第１の分割工程により高速走査エリア数が最少となる分割方法が複数得られた場合に、部分集合内に規定値以上のギャップの有るデータのギャップ値の総和が最小になるものを選ぶことを特徴とする請求項１又は２に記載の加工計画方法。
【請求項４】
前記第１の座標軸方向と直交する第２の座標軸方向の複数の高速走査エリアの第１の座標軸方向の両端の座標値を、同一とすることを特徴とする請求項１乃至３のいずれかに記載の加工計画方法。
【請求項５】
前記第２の分割工程が、
前記第２の抽出工程により得られた第２の集合の各要素の値ａ1,…,ａn及び高速走査エリアの幅Ｄに基づいて、節点間の隣接の有無を判定することにより、仮想の有向ネットワークを構築する工程と、
得られた有向ネットワークに対し、第１の要素ａ1に該当する節点から他の節点への最短経路と最短路長を求める工程と、
前記有向ネットワークの終点の候補の集合である終点候補集合の節点に至る経路の中で、経路長が最短の経路を選択する工程と、
該最短経路上の節点に基づいて第２の部分集合に分割する工程と、
を含むことを特徴とする請求項１に記載の加工計画方法。
【請求項６】
前記第２の分割工程により高速走査エリア数が最少となる分割方法が複数得られた場合に、部分集合内に規定値以上のギャップの有るデータのギャップ値の総和が最小になるものを選ぶことを特徴とする請求項５に記載の加工計画方法。
【請求項７】
前記仮想の有向ネットワークを構築する工程において、ａj-1−ａi≦Ｄ（ｉ＜ｊ）を満たす要素ｉ，ｊに該当する節点間を隣接と判定することを特徴とする請求項２又は５に記載の加工計画方法。
【請求項８】
前記第１の座標軸方向の複数の高速走査エリアの第２の座標軸方向の両端の座標値を、同一とすることを特徴とする請求項５乃至７のいずれかに記載の加工計画方法。
【請求項９】
前記両端の座標値を、加工位置が高速走査エリアから外れない限度で、高速走査エリアの中央に集まるように微調整することを特徴とする請求項４又は８に記載の加工計画方法。
【請求項１０】
前記第１の座標軸の方向を、複数の座標軸の方向についての高速走査エリアの配置を試行した後、高速走査エリアの数が少ない方に決定することを特徴とする請求項１乃至９のいずれかに記載の加工計画方法。
【請求項１１】
請求項１乃至１０のいずれかに記載の加工計画方法により決定した加工計画を用いて加工を行なうことを特徴とする加工方法。
【請求項１２】
所定の高速走査エリア内で高速移動可能な高速位置決め手段と、前記高速走査エリアを越えて移動可能な低速位置決め手段を用いて、前記低速位置決め手段による高速走査エリアの位置決めを行なった後、前記高速位置決め手段による高速走査エリア内の位置決めを行なって、ワーク上に散在する加工位置を加工する際の加工計画を作成するためのコンピュータプログラムであって、
ワーク全体の加工位置の第１の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第１の集合の要素ａ1,…,ａnとする第１の抽出ステップと、
該第１の集合を、高速走査エリアの幅を用いて、互いに素な第１の部分集合に分割する第１の分割ステップと、
前記第１の部分集合をもとに、加工位置を複数のグループに分けるステップと、
各グループ内の加工位置の第２の座標軸方向の座標値を、重複する値は１として取り出してソートし、第２の集合の要素とする第２の抽出ステップと、
該第２の集合を、高速走査エリアの幅を用いて、互いに素な第２の部分集合に分割する第２の分割ステップと、
前記第２の部分集合をもとに、加工位置を複数のグループに分けるステップと、
により、高速走査エリアの配置を決定することを特徴とするコンピュータプログラム。
【請求項１３】
所定の高速走査エリア内で高速移動が可能な高速位置決め手段と、前記高速走査エリアを越えて移動可能な低速位置決め手段を用いて、前記低速位置決め手段による高速走査エリアの位置決めを行なって後、前記高速位置決め手段による高速走査エリア内の位置決めを行なって、ワーク上に散在する加工位置を加工する際の加工計画装置であって、
ワーク全体の加工位置の第１の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第１の集合の要素ａ1,…,ａnとする第１の抽出手段と、
該第１の集合を、高速走査エリアの幅を用いて、互いに素な第１の部分集合に分割する第１の分割手段と、
前記第１の部分集合をもとに、加工位置を複数のグループに分ける手段と、
各グループ内の加工位置の第２の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第２の集合の要素とする第２の抽出手段と、
該第２の集合を、高速走査エリアの幅を用いて、互いに素な第２の部分集合に分割する第２の分割手段と、
前記第２の部分集合をもとに、加工位置を複数のグループに分ける手段と、
該グループにより、高速走査エリアの配置を決定する手段と、
を備えたことを特徴とする加工計画装置。
【請求項１４】
請求項１３に記載の加工計画装置を含み、該加工計画装置により決定された加工計画に従って加工を行なうことを特徴とする加工装置。
【請求項１５】
請求項１２に記載のコンピュータプログラムが記録された、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、所定の高速走査エリア（以下、単に走査エリアとも称する）内で高速移動可能な高速位置決め手段と、前記走査エリア範囲を超えて移動可能な低速位置決め手段を用いて、前記低速位置決め手段による走査エリアの位置決めを行なった後、前記高速位置決め手段による走査エリア内の位置決めを行なって、ワーク上に散在する多数の加工位置を加工する際の加工計画方法、装置、加工方法、装置、コンピュータプログラム及びコンピュータ読み取り可能な記録媒体に係り、特に、レーザビームを照射してプリント配線基板等に複数の穴開け加工を行なうレーザ穴開け機に用いるのに好適な、穴開け等の加工位置の２次元平面における分布状態を数学的に捉えて、ＸＹステージの速度、加速度、軌道やガルバノスキャナの穴開け位置訪問順序等の機器の動作を効率良く計画することにより、加工時間を短縮することが可能な加工計画方法、該加工計画方法により決定された加工を行なう加工方法、同様な加工計画装置、該加工計画装置を含む加工装置、前記加工計画方法を実施するためのコンピュータプログラム、及び、該コンピュータプログラムが記録された、コンピュータ読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
近年、電子機器の小型化や高密度実装化の要求に伴い、複数のプリント配線基板を重ね合わせた多層プリント配線基板が提供されるようになってきている。このような多層プリント配線基板では、上下に積層されたプリント配線基板のそれぞれに形成された導電層間を電気的に接続するため、これらの基板に、スルーホールあるいはビアホールと呼ばれる穴が形成される。そして、これらの穴の内部に導電膜を形成することにより、各プリント配線基板の導電層間の接続が行われる。
【０００３】
プリント配線基板に形成される穴は、最近のプリント配線基板の小型化や高機能化に伴って小型化し、直径０．１ｍｍ以下になってきている。このような小径の穴を精度良く形成するために、パルス発振型のレーザビームが用いられている。
【０００４】
従来のパルス発振型レーザを用いたレーザ穴開け機の一般的な構成を図１に示す。本構成例は、図示しないレーザ発振器から照射される、例えばパルス状のレーザ光線２０を、所定の方向（図１では紙面に垂直な方向）に走査するための回転ミラー２３を含む第１ガルバノスキャナ２２と、該第１ガルバノスキャナ２２によって紙面に垂直な方向に走査されたレーザ光線を、該第１ガルバノスキャナ２２による走査方向と垂直な方向（図１では紙面と平行な方向）に走査するための回転ミラー２５を含む第２ガルバノスキャナ２４と、前記第１及び第２ガルバノスキャナ２２、２４により２方向に走査されたレーザ光線を、ＸＹステージ１２上に固定された、基板等の加工対象物（ワークと称する）１０の表面に対して垂直な方向に偏向して照射するためのｆ−θレンズ２６とを備えている。
【０００５】
前記ＸＹステージ１２は、例えば紙面と垂直な方向に移動可能なＹステージ１２Ｙの上に、紙面と平行な方向に移動可能なＸステージ１２Ｘが設けられている。
【０００６】
このように、第１、第２ガルバノスキャナ２２、２４を用いることにより、レーザ光線２０を、スキャナ先端の回転ミラー２３、２５に反射させ、進行方向を任意に変えることができる。ここで、回転ミラー２３、２５は軽量であるため、高速位置決めが可能である。
【０００７】
前記ガルバノスキャナ２２、２４によって偏向したレーザ光線は、ｆ−θレンズ２６を通過して、ワーク１０に集光する。このｆ−θレンズ２６は、一般に高価なものであるために、あるタイミングにおけるビーム走査による照射可能範囲（一般に走査エリアと称する）の大きさが数十ｍｍ角程度の正方形に制限されており、一般的なワーク１０の大きさより狭い。
【０００８】
そこで、ＸＹステージ１２によりワーク１０を搬送することにより、広範囲な位置決めを可能としている。但し、ＸＹステージ１２は重量が大きいため、位置決めに費やす時間が大きい。
【０００９】
このようにして、レーザ穴開け機は、高速狭範囲の位置決め装置であるガルバノスキャナ、及び、低速広範囲の位置決め装置であるＸＹステージの２つの位置決め装置を用いることにより、高速広範囲な穴開け位置決めを行っている。
【００１０】
この際、ＸＹステージを目的の加工位置へ動作、整定させた後、ガルバノスキャナにより穴開け位置へ移動するようなステップアンドリピートと称される加工を行なうことが一般的である。このステップアンドリピートによる加工における走査エリアの配置方法の計画に関しては、例えば特開平８−１７４２５６や特開平１１−１４９３１７に記載された方法が考えられている。
【００１１】
即ち、特開平８−１７４２５６には、図２に示す如く、基板１０全体の穴開け位置の拡がりを表わす矩形を、走査エリア８の大きさの格子状に分割し、各格子を１つの走査エリアとすることが記載されている。走査エリアの訪問順序は、エリアの端から順に、８Ｓから８Ｅまで、横若しくは縦に１列、折り返して次の１列、…と繰り返して、隣接したエリアを順に加工する方法を採っている。
【００１２】
しかしながら、この方法は、穴開け位置の分布によらず走査エリアを配置しており、ＸＹステージの動作及び整定という時間のかかる処理を行なう回数が多く、計画機能としては、決して優れたものとは言えなかった。
【００１３】
一方、特開平１１−１４９３１７には、図３に示す如く、加工位置が存在しない走査エリアを訪問対象から外すことにより、走査エリアの配置枚数を特開平８−１７４２５６よりも減らすことが記載されている。
【００１４】
【発明が解決しようとする課題】
この特開平１１−１４９３１７の方法による走査エリアの配置では、ＸＹステージを座標軸の方向である縦又は横方向に動かすだけでなく、斜めを含む３６０°全ての方向へ移動させる可能性があるが、ＸＹステージの機械構成、制御構成、制御ロジック等、諸要因のために、斜め方向に移動させる場合には、各回の移動に費やす時間が、特開平８−１７４２５６のように隣接する縦又は横のエリアへの移動時間と比較して長くなり、エリアの枚数（従ってＸＹステージの動作回数）が低減しても、全体としての移動時間短縮という効果があまり期待できないことがあった。
【００１５】
本発明は、前記従来の問題点を解消するべくなされたもので、加工を開始する前段階において、ガルバノのスキャナのような狭範囲にしか移動できない高速位置決め手段と、ＸＹステージのような広範囲に移動可能な低速位置決め手段の動作を、効率良く計画して、加工時間を短縮することを課題とする。
【００１６】
【課題を解決するための手段】
本発明は、所定の高速走査エリア内で高速移動可能な高速位置決め手段と、前記高速走査エリアを越えて移動可能な低速位置決め手段を用いて、前記低速位置決め手段による高速走査エリアの位置決めを行なった後、前記高速位置決め手段による高速走査エリア内の位置決めを行なって、ワーク上に散在する加工位置を加工する際の加工計画方法であって、ワーク全体の加工位置の第１の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第１の集合の要素ａ1,…,ａnとする第１の抽出工程と、該第１の集合を、高速走査エリアの幅を用いて、互いに素な第１の部分集合に分割する第１の分割工程と、  前記第１の部分集合をもとに、加工位置を複数のグループに分ける工程と、各グループ内の加工位置の第２の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第２の集合の要素とする第２の抽出工程と、該第２の集合を、高速走査エリアの幅を用いて、互いに素な第２の部分集合に分割する第２の分割工程と、前記第２の部分集合をもとに、加工位置を複数のグループに分ける工程と、により、高速走査エリアの配置を決定するようにして、前記課題を解決したものである。
【００２１】
又、前記第１の分割工程が、前記第１の抽出工程により得られた第１の集合の各要素の値ａ1,…,ａn及び高速走査エリアの幅Ｄに基づいて、節点間の隣接の有無を判定することにより、仮想の有向ネットワークを構築する工程と、得られた有向ネットワークに対し、第１の要素ａ1に該当する節点から他の節点への最短経路と最短路長を求める工程と、前記有向ネットワークの終点の候補の集合である終点候補集合の節点に至る経路の中で、経路長が最短の経路を選択する工程と、該最短経路上の節点に基づいて第１の部分集合に分割する工程と、を含むようにしたものである。
【００２４】
又、前記第１の分割工程により高速走査エリア数が最少となる分割方法が複数得られた場合に、部分集合内に規定値以上のギャップの有るデータのギャップ値の総和が最小になるものを選ぶようにして、高速位置決め手段の動作量が少ないエリア配置が得られるようにしたものである。
又、前記第１の座標軸方向と直交する第２の座標軸方向の複数の高速走査エリアの第１の座標軸方向の両端の座標値を、同一としたものである。
又、前記第２の分割工程が、前記第２の抽出工程により得られた第２の集合の各要素の値ａ1,…,ａn及び高速走査エリアの幅Ｄに基づいて、節点間の隣接の有無を判定することにより、仮想の有向ネットワークを構築する工程と、得られた有向ネットワークに対し、第１の要素ａ1に該当する節点から他の節点への最短経路と最短路長を求める工程と、前記有向ネットワークの終点の候補の集合である終点候補集合の節点に至る経路の中で、経路長が最短の経路を選択する工程と、該最短経路上の節点に基づいて第２の部分集合に分割する工程と、を含むようにしたものである。
又、前記第２の分割工程により高速走査エリア数が最少となる分割方法が複数得られた場合に、部分集合内に規定値以上のギャップの有るデータのギャップ値の総和が最小になるものを選ぶようにしたものである。
又、前記仮想の有向ネットワークを構築する工程において、ａj-1−ａi≦Ｄ（ｉ＜ｊ）を満たす要素ｉ，ｊに該当する節点間を隣接と判定するようにしたものである。
又、前記第１の座標軸方向の複数の高速走査エリアの第２の座標軸方向の両端の座標値を、同一としたものである。
又、前記両端の座標値を、加工位置が高速走査エリアから外れない限度で、高速走査エリアの中央に集まるように微調整するようにしたものである。
又、前記第１の座標軸の方向を、複数の座標軸の方向についての高速走査エリアの配置を試行した後、高速走査エリアの数が少ない方に決定するようにしたものである。
【００２５】
本発明は、又、前記の加工計画方法により決定した加工計画を用いて加工を行なう加工方法を提供するものである。
【００２６】
又、所定の高速走査エリア内で高速移動可能な高速位置決め手段と、前記高速走査エリアを越えて移動可能な低速位置決め手段を用いて、前記低速位置決め手段による高速走査エリアの位置決めを行なった後、前記高速位置決め手段による高速走査エリア内の位置決めを行なって、ワーク上に散在する加工位置を加工する際の加工計画を作成するためのコンピュータプログラムであって、ワーク全体の加工位置の第１の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第１の集合の要素ａ1,…,ａnとする第１の抽出ステップと、該第１の集合を、高速走査エリアの幅を用いて、互いに素な第１の部分集合に分割する第１の分割ステップと、前記第１の部分集合をもとに、加工位置を複数のグループに分けるステップと、各グループ内の加工位置の第２の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第２の集合の要素とする第２の抽出ステップと、該第２の集合を、高速走査エリアの幅を用いて、互いに素な第２の部分集合に分割する第２の分割ステップと、前記第２の部分集合をもとに、加工位置を複数のグループに分けるステップと、により、高速走査エリアの配置を決定することを特徴とするコンピュータプログラムを提供するものである。
【００２７】
本発明は、所定の高速走査エリア内で高速移動が可能な高速位置決め手段と、前記高速走査エリアを越えて移動可能な低速位置決め手段を用いて、前記低速位置決め手段による高速走査エリアの位置決めを行なって後、前記高速位置決め手段による高速走査エリア内の位置決めを行なって、ワーク上に散在する加工位置を加工する際の加工計画装置であって、ワーク全体の加工位置の第１の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第１の集合の要素ａ1,…,ａnとする第１の抽出手段と、該第１の集合を、高速走査エリアの幅を用いて、互いに素な第１の部分集合に分割する第１の分割手段と、前記第１の部分集合をもとに、加工位置を複数のグループに分ける手段と、各グループ内の加工位置の第２の座標軸方向の座標値を、重複する値は１つとして取り出してソートし、第２の集合の要素とする第２の抽出手段と、該第２の集合を、高速走査エリアの幅を用いて、互いに素な第２の部分集合に分割する第２の分割手段と、前記第２の部分集合をもとに、加工位置を複数のグループに分ける手段と、該グループにより、高速走査エリアの配置を決定する手段と、を備えることにより、同じく前記課題を解決したものである。
【００２８】
本発明は、又、前記の加工計画装置を含み、該加工計画装置により決定された加工計画に従って加工を行うことを特徴とする加工装置を提供するものである。
【００３０】
本発明は、又、前記コンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体を提供するものである。
【００３１】
【発明の実施の形態】
以下図面を参照して、低速位置決め手段としてのＸＹステージと、高速位置決め手段としてのガルバノスキャナを備えたレーザ穴開け機により穴を開ける場合に適用した、本発明の実施形態を詳細に説明する。
【００３２】
本発明にかかる矩形分割により得られる走査エリアの例を図４に示す。このような矩形分割を実現するために、昇順ソートされたｎ個のデータの集合Ａ＝｛ａ1，ａ2，…ａn｝を、最小個数の互いに素な（即ち、集合の要素に同一のものが無い）部分集合Ｂ1，Ｂ2，…Ｂmに分割する問題を考える。但し、集合Ｂkの要素はソートされており、Ｂkの末尾の要素は、Ｂk+1の先頭の要素より必ず小さく、各部分集合Ｂk＝｛ａS，…ａG｝は、先頭、末尾の要素に関し、｜ａG−ａs｜≦Ｄ（Ｄは固定値）を満たすようにする。
【００３３】
以下、図５を参照して、解くべき問題を具体的に説明する。
【００３４】
図５のような基板１０の穴開け位置配置例において、穴開け位置のＹ座標値のうち、データの重複しないものを１つのデータとし、そのようなものがｎ個見つかったとし、小さいものから順にａ1，…ａnとする。走査幅をＤとすると、ＸＹステージは、本発明により横方向（Ｘ方向）にのみ駆動させ、縦に１段上がって横方向（逆向）に駆動させるものとすれば、ａ1…ａnを、要素の差がＤ以下のものでグループ化すれば、各グループの要素は、同一の段において加工するものと想定できる。
【００３５】
この問題の解法を、ここではＳＰＬＩＴと称することにする。このＳＰＬＩＴは、ソートされた値の集合Ａ（及び分割値Ｄ）を入力とし、分割された互いに素な部分集合を出力する。
【００３６】
このＳＰＬＩＴを用いて、図６に示すような流れに従って、最適化を行なう。
【００３７】
具体的には、図７に手順を示す如く、まずステップ１００で、基板（ワーク）全体の穴開け位置のＹ座標値の重複しないデータのみを取り出してソートし、集合Ａの要素とする（Ａ＝｛ａ1，…ａn｝、ａi＜ａi+1）。
【００３８】
次いで、ステップ１０２に進み、集合ＡをＳＰＬＩＴに入力し、mが最小になるような部分集合Ｂ1，…，Ｂmを得る。
【００３９】
次いでステップ１０４に進み、各部分集合Ｂ1，…，Ｂmを元に、穴開け位置をｍ個のグループに分割する。
【００４０】
次いで、各グループに対し、次の手順を実行する。
【００４１】
即ち、まず、ステップ１０６で、各グループ内の穴開け位置のＸ座標値の重複しないもののみを取り出してソートし、集合Ａ´の要素とする。
【００４２】
次いで、ステップ１０８で、集合Ａ´をＳＰＬＩＴに入力し、部分集合Ｂ1´，…，Ｂm′´を得る。
【００４３】
次いでステップ１１０で、各部分集合Ｂ1´，…，Ｂm′´を元に、穴開け位置をm´個のグループに分割する。
【００４４】
このようにして、全ての穴開け位置が、いずれかの走査エリアに属するようにされた走査エリアの配置を確定することができる。
【００４５】
ここで、前記ＳＰＬＩＴに関して説明する。即ち、前記問題を、ネットワーク最適化問題の１つである最短路問題（与えられた節点から全ての節点への最短路を求める問題）として捉え、図８及び図９に示すように考える（ここで、図８（Ｂ）に示すような節点及び節点対の集合をネットワークと呼ぶ）。
【００４６】
具体的には、節点集合Ｖ＝｛ｖ1，ｖ2，…，ｖn｝に対し、要素ｖiの値をａiとする。ここで、ａiはソートされている。即ち、１≦ｉ≦ｎ−１なるｉに対し、ａi＜ａi+1。
【００４７】
又、２節点（ｖi，ｖj）（ｉ＜ｊ）は、次の場合に隣接しているものとする。
【００４８】
ａi＋Ｄ≧ａj  若しくは
ａi＋Ｄ≧ａj-1  且つ  ａi＋Ｄ＜ａj
【００４９】
即ち、ｖiに隣接するｖjは、ａiを部分集合Ｂtの先頭要素としたとき、Ｂt+1の先頭要素となり得る値ａjを持つ。つまり、ｊは、Ｂt＝｛ａi，…，ａj-1｝が一つの部分集合と成り得るようなものを意味する。
【００５０】
更に、隣接している２節点（ｖi，ｖj）（ｉ＞ｊ）対の重み（２節点間の距離）は、全て１とする。
【００５１】
又、始点をｖ1（値はａ1）、終点候補集合をＶe＝｛ｖk，…，ｖn｝（但しｋは、ａk＋Ｄ≧ａnとなる最初のものを指す。つまり、終点候補集合の要素ｖi（ｋ≦ｉ≦ｎ）を先頭とする集合は最大値ａnを含むことが可能であるため、最後の部分集合Ｂmと言える）とする。
【００５２】
以上により、図１０のステップ２００に示す如く、ｖ1を始点とする有向ネットワークを得ることができる。即ち、始点Ｖ1から終点候補集合の要素ｖi（ｋ≦ｉ≦ｎ）への任意パスは、そのパス上の節点を部分集合の先頭とする部分集合への分割に対応している。
【００５３】
次いでステップ２０２で、得られたネットワークに対し、最短路問題を解くと、始点から各節点への最短経路と最短路長が求まる。
【００５４】
次いでステップ２０４で、終点候補集合の節点のうち、最短路長（節点対の重みが全て１ゆえ、パス上の節点数−１に等しい）が最小な値を示す節点を選択する。
【００５５】
次いでステップ２０６で、その節点への最短経路上の節点ｖsの値ａsを、部分集合Ｂtの先頭要素とすれば、求めたい互いに素な部分集合による分割が得られている。
【００５６】
なお、最短路問題は、例えばダイクストラ（Dijkstra）のような公知の手法で解くことができる。
【００５７】
このようにして、ＸＹステージを斜め方向にできる限り動かさないような、走査エリア数が最小なエリア配置を求めることができる。これにより、ＸＹステージ動作時間が短縮される。
【００５８】
なお、図１に示したｆ−θレンズ２６の精度等の関係で、走査エリアの矩形の配置を、穴開け位置が矩形の中央に集まるように微調整すると、ガルバノスキャナの振れ角が０に近い位置となり、穴開け精度が向上する。ここで、矩形とは、図６（Ｂ）のように、Ｙ方向のグループ分けが確定した時点（図７のステップ１０６開始時）、及び、図６（Ｃ）のように、各Ｙ方向のグループに対してＸ方向のグループ分けが確定し、走査エリアが確定した時点（図７のステップ１１２終了時）の矩形を指す。
【００５９】
微調整の具体的な方法としては、（１）図１１に示す如く、広がりの中心（最大値、最小値の平均）を矩形の中心とする方法や、（２）図１２に示す如く、重心（重心が上若しくは下に偏っている場合は、穴開け位置が矩形から出ない限界値）を中心とすることができる。
【００６０】
更に、前記ＳＰＬＩＴにおいて、計算量削減のために、候補となりそうな値ａを幾つか抽出しておき、その集合から解を導出することもできる。幾何学的に考察すると、候補となる位置は、一つ前の点からのギャップが大きい点（ａi−ａi-1の値が大きい点ａi）が相応しい。そこで、そのようなものを幾つか抽出しておき、それらを中心に最短路問題を考えると、計算量を削減できる。
【００６１】
なお、上記矩形縦位置の設定法は、矩形の枚数を最小化することを目的としているが、矩形の枚数が同一でも、図１３に示す如く、矩形被覆により穴開け位置が２箇所以上に分断されてしまうことがある。従って、最小の矩形枚数である解の中から、最も穴開け位置の分断のない解を選択するのが望ましい。これを実現するためには、最小の矩形枚数である解全てに対し、上記と同じくギャップＧが大きい箇所が矩形内にある場合は、そのギャップ値を加算していき、ギャップ値の総和が最小となるものを選べば良い。もしくは、部分集合Ｂtの末尾の要素とＢt+1の先頭の要素との差の総和が最大となるようなものを選んでも良い。このようにして、ガルバノスキャナの動作量が元々少ない走査エリア配置を得ることができる。
【００６２】
各走査エリアの訪問順序は、図１４に示す如く、全体に蛇が、Ｙが正の方向に進行するような順序とすれば、最短となる。
【００６３】
更に、最短路長問題は、最適化を実用的な時間で求めることができる問題である。従って、上記手法を用いることにより、図１５に示す如く、段の揃った配置を行なう場合の最適解を得ることが可能である。
【００６４】
なお、これまでの説明では、図１に示したように、Ｘ方向が上段ステージ、Ｙ方向が下段ステージであるＸＹステージを想定し、Ｘ方向のステージ動作を優先して加工するために、まず、縦方向に矩形分割を行ない、ついで、得られた矩形分割各々に対し、横方向に矩形分割を行なうという処理を行なっている。
【００６５】
しかしながら、分割矩形枚数最小化という観点からみれば、基板によっては、まず、横方向に矩形分割を行ない、通常得られた分割矩形各々に対し、縦方向に矩形分割を行なうという処理による矩形分割の方が、分割矩形の枚数が少ないこともある。
【００６６】
そのような場合には、次のような選択が可能である。
（１）ステージをＹ方向に優先的に動かす。即ち、走査エリアの訪問順序を、蛇が、Ｘが正の方向に進行するような順序とする。
（２）基板を９０°回転させることにより、ステージ動作をＸ方向優先で行なう。この場合、加工計画プログラムは、加工当事者に基板配置方向の変更の必要性を知らせる。
【００６７】
又、（２）の選択は、自動化することが望ましい。即ち、図１６に示すような手順で自動化を達成することができる。
【００６８】
まずステップ３００で、Ｘ方向を優先的に動かす場合の最適化を行ない、ここでのステージ動作回数Ｃxをカウントする。
【００６９】
次いで、ステップ３０２で、Ｙ方向を優先的に動かす場合の最適化を行ない、ここでのステージ動作回数Ｃyをカウントする。
【００７０】
次いでステップ３０４で、Ｃｘ≦Ｃｙならば、そのままとし、Ｃｘ＞Ｃｙならば、ステップ３０６で、基板を９０°回転させる。
【００７１】
なお、（１）の選択は、（２）の選択が自動化できれば、不要である。
【００７２】
なお、前記実施形態においては、高速位置決め手段がガルバノスキャナとされ、低速位置決め手段がＸＹステージとされていたが、位置決め手段の種類や組合せはこれに限定されず、例えば出願人が特開２０００−７１０８９や特開２０００−３３４６３７で提案したような、リニアモータＸＹステージと高速加工ヘッドを組合せたハイブリッド加工システム（いわゆるスクリーンカットシステムあるいはフラッシュカットシステム）であってもよい。
【００７３】
又、適用対象も、点状の加工を行なうレーザ穴開け機に限定されず、線状の加工を行なうレーザ切断機、特開平１１−１４９３１７に記載された２ヘッドレーザ加工機やレーザビーム以外の加工手段を用いた一般の加工機（例えば機械式ドリルによる穴開け装置）であって、２つ以上の位置決め装置を用いることにより位置決めを高速化することが可能なもの全般にも同様に適用できることは明らかである。
【００７４】
【発明の効果】
本発明によれば、加工の事前段階において、加工を効率良く短時間で行なうための計画が可能となり、位置決め精度のよいステップアンドリピート制御を実現して、加工時間を短縮することが可能になるという優れた効果を有する。
【図面の簡単な説明】
【図１】本発明の適用対象の一例であるレーザ穴開け機の要部構成を示す正面図
【図２】特開平８−１７４２５６で提案された走査エリアの配置を示す平面図
【図３】特開平１１−１４９３１７で提案された走査エリアの配置及びＸＹステージの移動方向を示す平面図
【図４】本発明によって得られる走査エリアの例を示す平面図
【図５】本発明により解くべき問題の説明図
【図６】本発明の実施形態の概念を示す平面図
【図７】前記実施形態における処理手順を示す流れ図
【図８】前記実施形態で用いられるＳＰＬＩＴの概念の一例を示す図
【図９】同じく他の例を示す図
【図１０】ＳＰＬＩＴの処理手順を示す流れ図
【図１１】前記実施形態における広がりの中心を矩形の中心とする微調整の方法を示す平面図
【図１２】同じく重心を矩形の中心とする微調整の方法を示す平面図
【図１３】同じく穴開け位置がエリアの端に分断されている例を示す平面図
【図１４】同じく走査エリア訪問順序の概念を示す平面図
【図１５】同じく段の揃った配置を示す平面図
【図１６】同じく基板配置方向最適化の手順を示す流れ図
【符号の説明】
８、８s、８e…走査エリア
１０…加工対象物（ワーク）
１２…ＸＹステージ
１２Ｘ…Ｘステージ
１２Ｙ…Ｙステージ
２０…レーザ光線
２２、２４…ガルバノスキャナ
２３、２５…回転ミラー
２６…ｆθレンズ
【図１】
0004053774.tif 000002
【図２】
0004053774.tif 000003
【図３】
0004053774.tif 000004
【図４】
0004053774.tif 000005
【図５】
0004053774.tif 000006
【図６】
0004053774.tif 000007
【図７】
0004053774.tif 000008
【図８】
0004053774.tif 000009
【図９】
0004053774.tif 000010
【図１０】
0004053774.tif 000011
【図１１】
0004053774.tif 000012
【図１２】
0004053774.tif 000013
【図１３】
0004053774.tif 000014
【図１４】
0004053774.tif 000015
【図１５】
0004053774.tif 000016
【図１６】
0004053774.tif 000017