(57)【要約】【課題】加工する穴の数が多い場合であっても、精度の良い近似解を短時間で得ることができ、加工能率を向上させることができる加工装置を提供すること。【解決手段】空間探索木生成手段２ｃが生成する空間探索木を用いて、指定された領域内の加工位置を探索する空間探索手段２ｂを設ける。加工順序最適化手段２ａは、空間探索手段２ｂによって探索された加工位置を対象にして、加工経路の長さまたは加工手段の移動時間が短くなるように加工順序を最適化する。【選択図】図１
2008044102.tif 000002
【特許請求の範囲】
【請求項１】
加工手段と、この加工手段を加工位置に位置決めする移動手段と、予め定められた加工領域内の加工経路の長さまたは前記加工手段の移動時間が短くなるように加工順序を最適化する加工順序最適化手段と、指定された領域内の加工位置を探索する空間探索手段と、指定された加工領域を分割する空間探索木を生成する空間探索木生成手段と、を備え、
前記加工順序最適化手段は前記空間探索手段の探索結果を用いて加工順序を最適化し、
前記空間探索手段は前記空間探索木生成手段が生成した空間探索木を用いて前記指定された加工領域に含まれる前記加工位置を探索する加工装置において、
前記空間探索木生成手段は、
前記加工位置を示す多次元の座標の各次元の座標値についてその値の大きさの順序を示すソートテーブルと、
前記加工位置の番号を第１の軸、前記加工領域を分割する分割段数を第２の軸としたマトリクス状のテーブルであって、前記テーブルの各要素を前記ソートテーブルのいずれかに示す加工位置の順序にしたがって０または１が記載される分割用フラグテーブルと、を有し、
前記分割用フラグテーブルには、前記第２の軸の１番目の位置のデータについては、所定の分割方向に対応した前記ソートテーブルに示される順序に基づいて前記加工位置を前半部と後半部で２分し、一方に０を、他方に１をそれぞれ書き込み、前記第２の軸のｉ番目の位置のデータについては、前記第２の軸の１番目からｉ−１番目のデータが同一であるものについて、それぞれ所定の分割方向に対応した前記ソートテーブルに示されるの順序に基づいて前記加工位置を前半部と後半部で２分し、一方に０を、他方に１をそれぞれ書き込むことにより加工位置番号に対応した各分割段のデータが書き込まれ、前記分割用フラグテーブルの前記加工位置の番号に対応した第１の軸の位置において第２の軸の方向にデータの１番目からｉ番目までを２進数として読み出した値を親ノード番号、１番目からｉ＋１番目までを２進数として読み出した値を子ノード番号とする２分木構造を構成し、１番目から最後までを２進数として読み出した値をノード番号とするノードに前記加工位置を対応付けることにより空間探索木を構成するものであることを特徴とする加工装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子機器に使用するプリント基板等に穴等を加工する加工装置に関する。
【背景技術】
【０００２】
プリント基板には、搭載する電子部品の端子を挿入するためのスルーホールや、基板内に多層に構成された配線の層間を接続する回路を形成するためのビアホール等、多数の穴を加工する必要がある。これらの穴は、一般にドリルやレーザ光を用いた加工装置によって加工される。これらの穴を加工する順序が適切でないと、ドリルやレーザスポットの移動距離（巡回路）が長くなり、加工時間が長くなる。このため、ドリルやレーザスポットの巡回路ができるだけ短くなるように加工順序を最適化する必要がある。
【０００３】
加工順序の最適化問題は、与えられた訪問箇所を一度ずつ巡回する最短の経路を求める巡回セールスマン問題の一種と考えることができるが、この種の問題はＮＰ困難な問題と呼ばれ、訪問箇所が多い場合に真に最短な経路を実用的な計算時間で求める方法は発見されていない。そこで、真に最短ではないが、それに近い解を求める近似解法として、局所探索法、シミュレーテッドアニーリング法、遺伝的アルゴリズムなど種々の方法が提案されている。
【０００４】
そして、局所探索法では、初期値として任意の巡回路を用意し、その巡回路の一部を変更した時に元の巡回路より経路長が短くなる場合は巡回路を修正するという操作を繰り返して近似解を求める。
【０００５】
図８は、局所探索法の一つである２−ｏｐｔ法による最適化手順を説明する図である。図において４０は穴の加工位置、４１は穴の加工経路であり、矢印の向きに従って順次穴を加工していく。
【０００６】
今、同図（ａ）に示す巡回路が与えられているとき、任意の穴加工位置ｉとｊの接続先をつなぎ替えた場合に、元の巡回路より経路長が短くならないなら何もせず、短くなるならつなぎかえを実施して、同図（ｂ）に示す巡回路にする。この操作をｉとｊの全ての組合せについて実施し、いずれの組合せでつなぎかえても経路長が短くならなくなったところで処理を終了する。このように、２−ｏｐｔ法では加工位置の全ての組合せについて探索を行うため、穴の数をＮとするとＮ×（Ｎ−１）／２回、すなわちＮの二乗のオーダーの探索処理を行う必要がある。
【０００７】
また、シミュレーテッドアニーリング法では、局所探索法における修正操作を元の巡回路より経路長が短くなる場合だけでなく、短くならない場合にも不規則に実施する。さらに、このような特殊な修正が行われる確率を時間とともに変化させることにより、探索操作が局所解に留まることを改善して近似解を求める。
【０００８】
また、遺伝的アルゴリズムでは、複数の巡回路の候補を生成し、これらを生物の遺伝子に見たてて、交配、突然変異、淘汰などの操作を繰り返すことにより、優れた近似解を求める。
【０００９】
従来の穴加工機は、上記の近似解法によって加工順序を最適化しており、例えば、特許文献１では、初期値として与えられる巡回路の中の一つあるいは複数の穴の順序を入れ替える局所探索法により最短に近い巡回路を求めて、加工順序を決定している。
【特許文献１】特開平８−６６２５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
従来は、単一の製品を大量に生産することが多く、電子装置の基板も単一パターンの基板を多数加工すればよかった。このため、始めに十分な時間をかけて最適な穴加工順序を計算し、後は同一の加工データを繰り返し使用することができた。しかし、近年では多品種を小量生産することが多く、多種の基板パターンに迅速に対応するため、計算時間が短く、かつ精度の良い近似解を得ることができる近似解法が必要になってきた。
【００１１】
上記従来の近似解法では、一般に加工すべき穴の数が多くなるほど計算に時間がかかる。例えば、局所探索法の一つである２−ｏｐｔ法の場合、計算時間は概略穴の数の二乗に比例するため、穴の数が１０倍になると計算時間は約１００倍になってしまう。近年、電子装置の高密度実装技術が発達し、一つの基板上で加工すべき穴の数は飛躍的に増大し、実用的な時間内で最適化の計算ができなくなるという問題が生じつつある。
【００１２】
上記したように、２−ｏｐｔ法では穴の数の二乗のオーダーの探索処理を行う必要がある。しかし、図９に示すように、探索範囲を限定すれば、探索処理時間の高速化を図ることができる可能性がある。すなわち、加工位置ｉ，ｊにおいて接続先を同図（ａ）に示す加工位置ｉと加工位置ｉ＋１および加工位置ｊと加工位置ｊ＋１から、同図（ｂ）に示す加工位置ｉと加工位置ｊおよび加工位置ｉ＋１と加工位置ｊ＋１につなぎかえた時に経路長が短くなるとする。このような場合のほとんどは、加工位置ｉと加工位置ｉ＋１間の距離より加工位置ｉと加工位置ｊ間の距離が短いか、または加工位置ｊと加工位置ｊ＋１間の距離より加工位置ｉと加工位置ｊ間の距離が短い。したがって、加工位置ｉを基準に考えると、つなぎ替えによって経路長が短くなる相手先の候補は、ほとんどの場合、加工位置ｉと加工位置ｉ＋１間の距離を半径とする円４２内にあると考えることができる。すなわち、加工位置ｉに関して、円４２内に含まれる加工位置だけを探索することにより、２−ｏｐｔ法を用いる場合であっても、最適化処理の計算時間をＮのオーダーに短縮することができる。この場合、加工位置ｉと円４２外の他の加工位置とを接続する方が加工位置ｉと円４２内の他の加工位置に接続するよりも加工経路全体が短くなる場合もあり得るが、そのような場合が発生する確率は一般的にかなり低いものであり、実用上無視することができる。
【００１３】
しかし、上記のように探索範囲を制限したとしても、基板上の全ての加工位置から円４２内に含まれる穴加工位置を単純に見出そうとすると、Ｎのオーダーの計算時間が必要になる。すなわち、探索範囲を制限するだけでは計算時間がＮ×Ｎとなり、すなわちＮの二乗のオーダーになってしまうため、処理時間を短縮することができない。
【００１４】
本発明の目的は、上記従来技術における課題を解決し、加工する穴の数が多い場合であっても、精度の良い近似解を短時間で得ることができ、加工能率を向上させることができる加工装置及び加工方法を提供するにある。
【課題を解決するための手段】
【００１５】
前記目的を達成するため、第１の発明は、加工手段と、この加工手段を加工位置に位置決めする移動手段と、予め定められた加工領域内の加工経路の長さまたは前記加工手段の移動時間が短くなるように加工順序を最適化する加工順序最適化手段と、を備える加工装置において、指定された領域内の加工位置を探索する空間探索手段を設け、前記加工順序最適化手段が前記空間探索手段の探索結果を用いて加工順序を最適化することを特徴とする。
【００１６】
この場合、指定された加工領域を分割する空間探索木生成手段をさらに設け、前記空間探索手段が前記空間探索木生成手段によって生成された空間探索木を用いて前記指定された加工領域に含まれる前記加工位置を探索するようにするとよい。
【００１７】
その際、前記空間探索木生成手段は、前記指定された加工領域内の加工位置を行または列とし、分割段数を列または行とする分割用フラグテーブルと、前記指定された加工領域内の前記加工位置を位置座標に基づいて並べ替える第１の手段と、前記並べ替えた後、それぞれに含まれる前記加工位置の数が略等しくなるように、前記指定された加工領域をＸまたはＹ方向に二分することを指定回数繰り返して、前記指定された加工領域を細分化する第２の手段と、前記細分化した後、前記分割用フラグテーブルの各欄に、分割方向および並べ替えの結果に基づいて０または１を記入する第３の手段と、前記分割用フラグテーブルの各欄に記入された数字列を２値数として前記各加工位置を最小区分領域にまとめる第４の手段とを備え、前記第１ないし第４の手段によって前記空間探索木を生成するようにする。
【００１８】
また、第２の発明は、加工手段と、この加工手段を加工位置に位置決めする移動手段と、予め定められた加工領域内の加工経路の長さまたは前記加工手段の移動時間が短くなるように加工順序を最適化する加工順序最適化手段とを備え、指定された加工領域を分割して加工順序を最適化する加工方法において、前記指定された加工領域内の前記加工位置を位置座標に基づいて並べ替える第１の工程と、それぞれに含まれる前記加工位置の数が略等しくなるように、前記指定された加工領域をＸまたはＹ方向に二分することを指定回数繰り返して、前記指定された加工領域を細分化する第２の工程と、前記分割用フラグテーブルの各欄に、分割方向および並べ替えの結果に基づいて０または１を記入する第３の工程と、前記分割用フラグテーブルの各欄に記入された数字列を２値数として前記各加工位置を最小区分領域にまとめる第４の工程とを含み、前記第１の工程から第４の工程まで、この順序で実行することにより加工順序を最適化することを特徴とする。
【発明の効果】
【００１９】
本発明によれば、指定された領域内の加工位置を探索する空間探索手段を設け、加工順序最適化手段が空間探索手段の探索結果を用いて加工順序を最適化するので、加工する穴の数が多い場合であっても、精度の良い近似解を短時間で得ることが可能となり、加工能率を向上させることができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明を図示の実施形態に基づいて説明する。
【００２１】
図１は本発明の実施形態に係る加工装置の構成図である。
【００２２】
同図において、座標データ記憶手段１は、基板上のＸＹ座標で表記された穴の中心の座標データ（すなわち加工位置）を記憶する。加工データ生成手段２は、座標データ記憶手段１に記憶されている座標データに基づいて後述するスキャンエリアを設定した後、加工順序最適化手段２ａの演算結果により加工データを生成する。高速空間探索手段２ｂは、加工順序最適化手段２ａにより指定された範囲に含まれる加工位置を、空間探索木生成手段２ｃが生成した空間探索木を用いて探索する。加工データ記憶手段３は、加工データ生成手段２が生成した加工データを記憶する。加工制御信号生成手段４は、加工データに従って加工装置を制御する制御信号を生成する。加工制御信号生成手段４で生成された制御信号は、ミラー制御手段５、レーザ光源制御手段６およびＸＹテーブル制御手段７に出力され、ガルバノミラー装置８、９、レーザ光源１１およびＸＹテーブル１４を制御する。ガルバノミラー装置８、９はミラー８ａ、９ａを任意の回転角度に位置決めする。また、直動型駆動装置１２、１３は、ＸＹテーブル１４を任意の位置に位置決めする。なお、座標データ記憶手段１および加工データ記憶手段３は書き込み読み出し自在なメモリからなり、大量の記憶容量が必要な場合には、例えばＨＤＤ装置が使用される。また、加工データ生成手段２、加工順序最適化手段２ａ、高速空間探索手段２ｂおよび空間探索木生成手段２ｃは、図示しない１つのＣＰＵから構成され、図示しないＲＯＭに書き込まれたプログラムにしたがって図示しないＲＡＭをワークエリアとして使用しながら前記プログラムを実行することにより、前記各手段として機能する。
【００２３】
次に、この加工装置の基本的な動作について説明する。
【００２４】
レーザ光源１１から出力されたレーザ光は、ミラー８ａ、９ａで反射され、ｆ−θレンズ１０を介してＸＹテーブル１４上に設置された基板１５上に照射される。照射スポットの位置は、ミラー８ａ、９ａの回転角度とＸＹテーブル１４の位置によって決定される。
【００２５】
一般に、ガルバノミラー装置８、９がレーザ光をスキャンできる領域はｆ−θレンズ１０の大きさで決まる。そこで、基板上の加工領域をガルバノミラー装置８、９がスキャンできる領域（以下、「スキャンエリア」と呼ぶ）に分割し、スキャンエリア内の照射スポットの移動はガルバノミラー装置８、９で行い、スキャンエリア間の移動は、ＸＹテーブル１４で行う。
【００２６】
次に、加工データ生成手段２の動作について説明する。
【００２７】
加工データ生成手段２は、先ず、座標データ記憶手段１から加工位置（穴）の座標データを読込み、基板の全領域あるいは加工領域をｆ−θレンズの大きさで決まる矩形領域に分割してスキャンエリアとする。
【００２８】
加工順序最適化手段２ａは、各加工位置において図８に示す円４２の半径を定め、２−ｏｐｔ法によりスキャンエリア内の加工順序を最適化する（詳細は後述する）。
【００２９】
次に、高速空間探索手段２ｂの動作について説明する。
【００３０】
図２は、加工位置と空間探索木との関係を示す図である。ここでは、同図（ａ）に示すように、８個の加工位置５１を含む領域（空間）５０が探索対象（すなわちスキャンエリア）であるとする。
【００３１】
先ず、それぞれの領域に含まれる加工位置の数がほぼ等しくなるようにして、領域５０の長辺に垂直な直線（境界線）５２により、領域５０を二分割する。こうして得られたそれぞれの領域について同様の処理を繰り返して、１個の加工位置５１を含む領域１００〜１０７（以下、「最小区分領域」という。）に分割する。
【００３２】
以上の分割処理過程を木構造で表したものが同図（ｂ）であり、木構造の分岐点（ノード）５３はそれぞれ分割処理過程で生成される空間領域に対応する。すなわち、第０段のノード０は領域５０に、第１段のノード０は境界線５２により二分割された左側領域に、ノード１は右側領域に、それぞれ対応する。そして、最下段（図における３段）のノード０からノード７（エンドノード）は、それぞれ同図（ａ）の最小区分領域１００〜１０７に対応する。
【００３３】
ここで、一つの領域に含まれる加工位置の数は、分割処理の繰り返し回数によって決まり、最小区分領域に複数の加工位置が含まれるようにしてもよい。
【００３４】
次に、加工位置を表すデータ構造について説明する。
【００３５】
図３は、高速空間探索手段２ｂにおけるデータの構造を示す図である。
【００３６】
木構造の段数が０〜Ｍ段の場合、０〜Ｍ−１段のノード５３は、構造体データ５４で表される。構造体データ５４は、カバー領域（ノードに対応する領域）を表すカバー領域データ５６と、下段ノードへの第１のポインタ５７と、下段ノードへの第２のポインタ５８と、このノードがエンドノードであるか否かを識別するためのノード識別コード５９と、から構成されている。
【００３７】
また、最下段（Ｍ段）のエンドノードは、構造体データ５５で表される。構造体データ５５は、カバー領域を表すカバー領域データ６０と、このカバー領域に含まれる先頭の加工位置データへのポインタ６１と、加工位置数６２と、ノード識別コード６３と、から構成されている。
【００３８】
穴加工位置データへのポインタ６１は、インデックス６４の要素番号を示すものであり、インデックス６４の中身は実際の穴データへのポインタとなっている。前記要素番号から穴加工位置の数６２だけ連続した要素の本他が、ノード５５のカバー領域に含まれる穴加工位置のデータを示す。
【００３９】
次に、このような探索木を用いて、任意に指定された探索領域Ｓ（図９の円４２の領域）に含まれる加工位置を求める手順を説明する。
【００４０】
図４は、高速空間探索手段２ｂの動作を示すフローチャートである。
【００４１】
先ず、ノードポインタｔｐを第０段のノード０（スタートノード）にすると共に、候補リストＬの内容をクリアする（ｓ１）。次に、ノードポインタｔｐに対応するカバー領域と探索領域Ｓの間に重なる領域があり、このノードがエンドノードでない場合は、そのノードから分岐している下段のノード（サブツリー）について探索を続ける（ｓ２、ｓ３、ｓ５、ｓ６）。すなわち、ノードポインタｔｐをノード構造体５４の第１のノードポインタ５７あるいは第２のノードポインタ５８として、図４に点線で囲んで示す手順ｓ７を再帰的に繰り返す。また、ノードのカバー領域と探索領域Ｓとの間に重なる領域が無い場合は、そのノードから分岐している下段のノードの探索は行わない。そして、最下段のエンドノードに達した場合は（ｓ３）、そのノードに含まれる加工位置を候補リストＬに追加する（ｓ４）。
【００４２】
以上の探索手順により、探索領域Ｓに含まれる加工位置の候補が最小区分領域の単位で絞り込まれて候補リストＬに集められる。そこで、候補リストＬの中から実際に探索領域Ｓに含まれる加工位置を探索する。
【００４３】
ここで、全加工位置の数がＮの場合、探索木の段数ＭをＭ＝Ｌｏｇ２Ｎにすると、最小区分領域に含まれる加工位置の数を１〜２個程度にすることができる。
【００４４】
また、Ｍ段の探索木を探索する計算時間はＭのオーダーになる。したがって、空間探索木を用いた２−ｏｐｔ法による最適化処理の計算時間はＮ×Ｍ＝ＮＬｏｇ２Ｎのオーダーになる。
【００４５】
ところで、空間探索木を構成するためには、各カバー領域に含まれる加工位置の数がほぼ等しくなるように空間分割位置を定める必要がある。このようにするためには、例えば加工位置の座標値を縦方向あるいは横方向に小さい順に並べ替えて、中間となる座標値を求めるソーティング処理が必要となる。
【００４６】
ｎ個の要素をクイックソート法を用いてソーティング処理する場合、ステップ数はｎｌｏｇ２ｎで表される。したがって、Ｎ個の加工位置に対してＭ段（ただし、Ｍ＝ｌｏｇ２Ｎ）の探索木を構成する場合、ステップ数は式１で表される。
【数１】
2008044102.tif 000003
【００４７】
しかし、分割処理を行う毎に加工位置のソーティング処理を実施するのでは時間がかかり過ぎる。
【００４８】
そこで、空間探索木生成手段２ｃにより空間探索木を短時間で生成する。
【００４９】
次に、空間探索木生成手段２ｃの動作について説明する。
【００５０】
図５は、加工位置のソート結果と分割用フラグテーブルおよび割付テーブルの関係を示す図であり、図２（ａ）の領域５０に対応するものである。
【００５１】
Ｘ座標ソートテーブル７０（以下、「Ｔｘテーブル」という。）には、Ｘ座標値の小さい順にソートした加工位置の番号が、また、Ｙ座標ソートテーブル７１（以下、「Ｔｙテーブル」という。）には、Ｙ座標値の小さい順にソートした加工位置の番号が、それぞれ格納されている。
【００５２】
分割用フラグテーブル７２は加工位置を最小区分領域に割り付けるためのテーブルであり、加工位置の数をＮ、探索木の段数をＭとするＮ行×Ｍ列の配列変数として構成され、行番号が加工位置の番号に対応している。
【００５３】
そして、分割用フラグテーブル７２内の各欄に記載されている０または１は、以下のようにして記載される。
【００５４】
先ず、第１段目の分割方向が例えばＸ方向であったとする。この場合、分割用フラグテーブル７２の第１列（Ｆ１）の各欄に対し、Ｔｘテーブルに格納されている加工位置（穴）番号の前半分（図では、０、７、６、１）には０を、後半分（図では、２、５、４、３）には１を入れる。これにより、各加工位置はＦ１の値により二つのグループに分類され、０または１が分割された二つの領域に対応するものとなる。
【００５５】
次に、第２段目の分割方向が、列Ｆ１の０に対応する領域についてはＸ方向であり、１に対応する領域についてはＹ方向であるとする。この場合、列Ｆ２の各欄に対し、列Ｆ１の値が０である穴番号についてはＴｘテーブルの前半分（図では、０、７）を０、後半分（図では、６、１）を１、また、列Ｆ１の値が１である穴番号についてはＴｙテーブルの前半分（図では、２、３）を０、後半分（図では、５、４）を１とする。
【００５６】
以下、上記の処理を第Ｍ段まで繰り返して分割用フラグテーブル７２の全ての欄を０または１で埋める。このようにすると、各行（穴番号）についてＦ１〜ＦＭ欄に記入された０／１のコードを得ることができる。これを２進数として解釈し、対応する値を記したものが割付テーブル７３である。割付テーブル７３の値は、各加工位置が割り付けられたエンドノードの番号に対応しており、これは図２（ａ）に示す領域５０における最小区分領域１００〜１０７に対応している。
【００５７】
このように、空間探索木生成手段２ｃは、分割用フラグテーブル７２を用いてＴｘテーブルおよびＴｙテーブルを再利用することにより、１回のソート処理で空間探索木を生成する。
【００５８】
上記した空間探索木の生成手順をさらに詳しく説明する。
【００５９】
図６は、空間探索木の生成手順を示すフローチャートである。なお、第ｋ（ただし、ｋ＝０〜Ｍ）段のノードｂをＮＤ（ｋ，ｂ）で表し、分割用フラグテーブル７２のｉ行ｋ列目（すなわちｉ行ｋ段目）の欄をＦ（ｉ，ｋ）で表す。また、第ｋ段のノード数をＮＢ（ｋ）で表す。
【００６０】
先ず、加工位置のＸ座標値とＹ座標に関してソート処理によりＴｘテーブルとＴｙテーブルを作成し（ｓ１０）、配列要素Ｎ（ｋ）（ここでは、Ｎ（０））を全穴数（加工位置）として、探索木の段数ｋ＝０からスタートする（ｓ１１）。
【００６１】
次に、ｋ段のノードｂのカバー領域のＸ方向とＹ方向の長さを比較し、長い方を分割方向に定める。そして、分割方向を保存するための配列Ｄ（ｂ）の値を、Ｘ方向で分割する場合は０、Ｙ方向で分割する場合は１とする（ｓ１２）。
【００６２】
そして、ｉを０にしてから（ｓ１４）、Ｘ方向に関してテーブルＴｘの順に分割用フラグテーブルの欄Ｆ（ｉ，ｋ）に値をセットする（ｓ１４〜ｓ２２）。すなわち、Ｔｘのｉ番目の要素をｉｘとする時、欄Ｆ（ｉｘ，０）〜Ｆ（ｉｘ，ｋ−１）を２進数として読んだ値ｂ（なお、ｋ＝０の場合、ｂの値は０であるとする。）が第ｋ段における加工位置ｉｘの属するノード番号となる（ｓ１５）。そして、配列Ｄ（ｂ）の値が０（すなわち分割方向がＸ方向）の場合は、分割用フラグの設定を行い、その他の場合はＴｘの次の要素に移る（ｓ１６）。Ｃ（ｂ）はｋ段のノードｂに対応するカウンターであり、この値が第ｋ段のノードの最大値Ｎ（ｂ）／２よりも小さい場合は欄Ｆ（ｉｘ，ｋ）に０をセットし（ｓ１８）、大きいか等しい場合は１をセットする（ｓ１９）。そして、カウンターＣ（ｂ）を１増加させる（ｓ２０）。Ｔｘの全ての要素について上記の処理が終わると、第ｋ段目のノードｂについてＸ方向の分割に関するフラグテーブルの設定が終了する（ｓ２２）。
【００６３】
同様にして、Ｙ方向についても分割用フラグテーブルの設定を行う（ｓ２３）。これは、図中点線で囲んで示す手順ｓ２７においてｓ１５のＴｘ（ｉ）の代わりにＴｙ（ｉ）を用い、ｓ１６の条件をＤ（ｂ）＝０に代えてＤ（ｂ）＝１とした手順を実施することにより達成される。
【００６４】
第ｋ段のノードｂの分割処理が終わったら、新しくできた第ｋ＋１段のノードｂについて、対応するカバー領域の情報や穴数Ｎ（ｂ）の設定を行う（ｓ２４）。以下、同様にして、予め指定された段数まで、スキャン領域を細分する（ｓ２５、ｓ２６）。
【００６５】
以上の手順により、Ｎ個の穴加工位置に対する空間探索木は、Ｎｌｏｇ２Ｎのオーダーの計算時間で生成することができる。
【００６６】
最後に、加工順序最適化手段２ａの動作について説明する。
【００６７】
図７は、加工順序最適化手段２ａの動作を示すフローチャートである。なお、加工位置ｉの次に巡回すべき穴加工位置をｉ  ｉｎｃ  １で表記し、加工位置ｉとｊの間の距離をｄｉｓｔ（ｉ，ｊ）で、表記する。
【００６８】
まず、最適化の対象となるスキャンエリアに関する空間探索木を空間探索木生成手段２ｃを用いて生成し（ｓ３０）、スキャンエリア内の初期巡回路を生成する（ｓ３１）。ここで、初期巡回路は、例えば単純に穴データの入力順に巡回する巡回路でよい。
【００６９】
次に、探索対象を表す配列Ａ（ｉ）の値を全て１とする（ｓ３２）。配列Ａ（ｉ）の要素番号は加工位置の番号に対応しており、Ａ（ｉ）の値が１である加工位置が以下の探索処理の対象となる（ｓ３４）。
【００７０】
まず、加工位置ｉに関してｉを中心とする半径がｄｉｓｔ（ｉ，ｉ  ｉｎｃ  １）の円に含まれる穴のリストＬを高速空間探索手段２ｂを用いて生成する（ｓ３５）。そして、リストＬに含まれる加工位置の中に、ｓ３８の条件を満たし、かつ、つなぎ替えによって経路の長さが短くなる加工位置ｊが見つかった場合、すなわち、つなぎ替えの前後の経路長の差Δが負になる場合は（ｓ３９、ｓ４０）、つなぎ替えを実施し（ｓ４１、ｓ４２）、つなぎ替えに関わった加工位置ｉ  ｉｎｃ  １，ｊ，ｊ  ｉｎｃ  １を再び探索対象として（ｓ４３）、再び先頭から探索を実施する。一方、つなぎ替えによって経路長が短くなる加工位置が見つからなかった加工位置ｉは探索対象から外す（ｓ４６）。
【００７１】
以下、上記の探索処理を繰り返し、探索対象がなくなったら（Ａ（ｉ）の全ての要素が０となったら）、処理を終了する（ｓ４８）。
【００７２】
なお、この実施形態では、加工位置の番号を行とし、分割段数を列にしたが、分割段数を行とし、加工位置の番号を列にしてもよい。
【００７３】
また、上記の実施例では、加工順序最適化の方法として２−ｏｐｔ法を用いたが、これはこれに限定されるものではない。例えば、３−ｏｐｔ法を用いる場合は、三つの穴加工位置ｉ，ｊ，ｋの間でのつなぎ替えにより最適化を図るが、ｉに対するｊの探索範囲をｉを中心とする半径ｄｉｓｔ（ｉ，ｉ  ｉｎｃ  １）の円内とし、ｊに対するｋの探索範囲をｊを中心とする半径ｄｉｓｔ（ｊ，ｊ  ｉｎｃ  １）の円内とすることにより、計算時間をＮの三乗のオーダーからＮ（ｌｏｇ２Ｎ）２オーダーにすることができる。
【００７４】
また、局所探索法をベースとするシミュレーテッドアニーリング法においても同様の計算時間の短縮効果を得ることができる。
【００７５】
また、上記では加工順序最適化手段２ａによりスキャンエリア内の加工順序を最適化するようにしたが、基板全体の穴の加工順序を最適化するようにしてもよい。
【００７６】
以上説明したように、本実施形態によれば、加工順序最適化の方法として、例えば２−ｏｐｔ法を用いる場合でも、従来Ｎ２乗のオーダーであった計算時間をＮｌｏｇ２Ｎのオーダーとすることができ、これにより、加工位置が多い場合であっても、精度の良い近似解を短時間で得ることが可能となる。
【図面の簡単な説明】
【００７７】
【図１】本発明の実施形態に係る加工装置の構成図である。
【図２】加工位置と空間探索木との関係を示す図である。
【図３】高速空間探索手段２ｂにおけるデータの構造を示す図である。
【図４】高速空間探索手段２ｂの動作を示すフローチャートである。
【図５】加工位置のソート結果と分割用フラグテーブルおよび割付テーブルの関係を示す図である。
【図６】空間探索木の生成手順を示すフローチャートである。
【図７】加工順序最適化手段２ａの動作を示すフローチャートである。
【図８】局所探索法の一つである２−ｏｐｔ法による最適化手順を説明する図である。
【図９】２−ｏｐｔ法において探索範囲を限定する場合の説明図である。
【符号の説明】
【００７８】
２ａ  加工順序最適化手段
２ｂ  空間探索手段
２ｃ  空間探索木生成手段
【図１】
2008044102.tif 000004
【図２】
2008044102.tif 000005
【図３】
2008044102.tif 000006
【図４】
2008044102.tif 000007
【図５】
2008044102.tif 000008
【図６】
2008044102.tif 000009
【図７】
2008044102.tif 000010
【図８】
2008044102.tif 000011
【図９】
2008044102.tif 000012