(57)【要約】　　　（修正有）【課題】タイムシェア方式の２軸加工機において、ステップアンドリピート方式で動かす場合に、各走査エリア内においてスキャナの走査完了後の待ち時間を少なくあるいは無くして加工時間を短縮する。【解決手段】レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画方法において、各加工ヘッド毎に設定した走査エリアの加工時間を最小化する際に、各回の走査時間の加工時間からの超過量を求め、該超過量の総和が最小若しくは０となるように加工を計画する。【選択図】　　　図６
2004141952.tif 000002
【特許請求の範囲】
【請求項１】
レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画方法において、
各回の走査時間の加工時間からの超過量を求め、
該超過量の総和が最小若しくは０となるように加工を計画して、各加工ヘッド毎に設定した走査エリアの加工時間を最小化することを特徴とするレーザ加工機の加工計画方法。
【請求項２】
前記加工計画は、
暫定的な経路を発生する暫定経路発生工程と、
暫定的な経路における各回の走査時間の加工時間からの超過量を計算する超過量計算工程と、
改善解を探索するための探索の基準点を採択する基準点採択工程と、
暫定解に対し解の近傍内で改善解を探索する近傍探索工程と、
改善解が見つかった場合は経路を更新する経路更新工程と、
暫定解の総超過量が０の場合は最適解発見として計画を終了する最適解終了工程と、
を含むことを特徴とする請求項１に記載のレーザ加工機の加工計画方法。
【請求項３】
前記最適解終了工程において、各穴に対し、その穴へ及びその穴からの２つの走査が超過しているかどうかを記憶する超過判定用変数を付随させることを特徴とする請求項２に記載のレーザ加工機の加工計画方法。
【請求項４】
前記基準点採択工程において、各穴に対し、その穴へ又はその穴からの走査は近傍探索により改善すべき余地が有るかどうかを記憶する要探索判定用変数を付随させることを特徴とする請求項２に記載のレーザ加工機の加工計画方法。
【請求項５】
前記近傍探索工程における近傍は、２−ｏｐｔ近傍、３−ｏｐｔ近傍、リンカーニハン近傍、Ｏｒ−ｏｐｔ近傍、ダブルブリッジ近傍のいずれかであることを特徴とする請求項２に記載のレーザ加工機の加工計画方法。
【請求項６】
前記加工計画が、更に、前記要探索判定用変数が全て０になった際に、
暫定解で計画を終了する暫定解終了工程と、
計画を終了せずに近傍を新たなものに切り替える近傍更新工程と、
を含むことを特徴とする請求項４に記載のレーザ加工機の加工計画方法。
【請求項７】
前記加工計画が、更に、各穴に対し、近傍探索を高速に実現するためにリスト長が各点に依存するような可変近傍リストを予め作成しておくことを特徴とする請求項２に記載のレーザ加工機の加工計画方法。
【請求項８】
レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画方法において、
各回の加工穴間の移動コストを、各回の走査時間に対し、走査時間に依存するペナルティ関数を掛け合わせたものとして、各加工ヘッド毎に設定した走査エリア内の加工時間を最小化することを特徴とするレーザ加工機の加工計画方法。
【請求項９】
前記ペナルティ関数は、加工時間に対して、該加工時間より走査時間の方が大きい場合は大きな正数、さもなければ小さな正数とすることを特徴とする請求項８に記載のレーザ加工機の加工計画方法。
【請求項１０】
前記加工計画上の加工時間を、実際の時間より小さめに設定することを特徴とする請求項２又は９に記載のレーザ加工機の加工計画方法。
【請求項１１】
前記加工ヘッド数がＮ（Ｎ≧３）である時に、前記加工時間を、加工時間のＮ−１倍と読み替えることを特徴とする請求項２又は９に記載のレーザ加工機の加工計画方法。
【請求項１２】
請求項１乃至１１のいずれかに記載の加工計画方法により決定された加工を行なうことを特徴とする加工方法。
【請求項１３】
レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えたＮ台の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工方法において、
各回の走査時間が、各回の加工時間のＮ−１倍以下であることを特徴とするレーザ加工機の加工方法。
【請求項１４】
請求項１乃至１１のいずれかに記載の加工計画方法又は請求項１２又は１３に記載の加工方法を実現するためのコンピュータプログラム。
【請求項１５】
レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画装置において、
各回の走査時間の加工時間からの超過量を求める手段と、
該超過量の総和が最小若しくは０となるように加工を計画して、各加工ヘッド毎に設定した走査エリアの加工時間を最小化する手段と、
を備えたことを特徴とするレーザ加工機の加工計画装置。
【請求項１６】
レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画装置において、
各回の加工穴間の移動コストを、各回の走査時間に対し、該走査時間に依存するペナルティ関数を掛け合わせたものとして、各加工ヘッド毎に設定した走査エリア内の加工時間を最小化する手段を備えたことを特徴とするレーザ加工機の加工計画装置。
【請求項１７】
請求項１５又は１６に記載の加工計画装置を含むことを特徴とする加工装置。
【請求項１８】
レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えたＮ台の加工ヘッドに供給するようにしたレーザ加工装置において、
各回の走査時間を、各回の加工時間のＮ−１倍以下とする手段を備えたことを特徴とするレーザ加工装置。
【請求項１９】
請求項１５又は１６に記載の加工計画装置又は請求項１７又は１８に記載の加工装置を実現するためのコンピュータプログラム。
【請求項２０】
請求項１４又は１９に記載のコンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、レーザ加工機の加工計画方法及び装置に係り、特に、レーザ発振器から出力されたレーザ光を時分割して、ビームスキャナのような走査手段を備えた２台の加工ヘッドに供給するようにしたタイムシェア方式の２軸加工機において、走査エリア毎にＸＹステージのような低速位置決め手段を止めて、高速位置決め手段である走査手段のみを動かす、いわゆるステップアンドリピート方式で加工する場合に用いるのに好適な、各走査エリア内におけるスキャナの走査待ち時間を少なくして、加工時間を短縮することが可能なレーザ加工機の加工計画方法、装置、該加工計画方法、装置を用いた加工方法、装置、これらを実施したり、実現するためのコンピュータプログラム、該コンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体に関する。
【０００２】
【従来の技術】
２台の加工ヘッドを備えた２軸加工機には、レーザ発振器の数が１台のものと２台のものがある。レーザ発振器が２台のものは、２軸の同期をとる必要がないため、加工計画の構成は容易であるが、製品コストが高くなる。一方、レーザ発振器が１台のものについては、レーザビームのエネルギをハーフミラー等を用いて分割するエネルギシェア方式と、スイッチング素子を用いて時分割するタイムシェア方式がある。
【０００３】
このうちタイムシェア方式では、図１のような構成により、レーザビームの進路を時間に応じて切り替えている。即ち、レーザ発振器１０から直線偏光（例えばＰ波）で得られるレーザ光１１を、例えば電気光学格子（ＥＯＭ）１２によりスイッチングして、直線偏光の向きを時間毎に変えてＰ波とＳ波が交互に出るようにし、前記ＥＯＭ１２の出側に設置した偏光ビームスプリッタ（ポラライザとも称する）１４により、Ｐ波とＳ波に２分岐する。
【０００４】
前記ポラライザ１４により分岐されたレーザ光１５、１７は、直接又はミラー１６で方向を変えて、それぞれ第１軸（Ｚ１軸と称する）加工用のガルバノスキャナ（以下Ｚ１ガルバノと称する）１８を含む第１の加工ヘッドと、第２軸（Ｚ２軸と称する）加工用のガルバノスキャナ（以下Ｚ２ガルバノと称する）２０を含む第２の加工ヘッドに供給される。レーザ光１５、１７は、狭範囲内で高速位置決めが可能な走査手段である前記ガルバノ１８、２０にそれぞれ含まれる例えば２枚のガルバノミラー２６、２８（図２参照）により、加工対象物（ワークと称する）８上の加工位置に対応して、例えば紙面に垂直なＸ軸方向及び紙面と平行なＹ軸方向に走査され、ｆθレンズ２２、２４を介してワーク８の表面に当てられて、該ワーク８を加工する。図において、６は、ワーク８を広範囲にわたって低速で位置決めするためのＸＹステージである。
【０００５】
前記ガルバノ１８、２０には、それぞれ図２に詳細に示す如く、ポラライザ１４により分岐されたレーザ光１５、１７を紙面に垂直なＸ軸方向に走査するための第１ガルバノミラー２６と、該第１ガルバノミラー２６によりＸ軸方向に走査されたビームを、Ｘ軸方向と直交する、紙面に平行なＹ軸方向に走査して、ｆθレンズ２２、２４に入射するための第２ガルバノミラー２８が備えられている。図において、２７、２９は、それぞれガルバノミラー２６、２８を回転するためのモータである。
【０００６】
このような時分割による加工に際しては、図３に示す如く、レーザ発振器１０で発振されたレーザ光が、ＥＯＭ１２によりＳ波とＰ波に時分割され、例えばＳ波はＺ１ガルバノ１８に供給されて、その下にある走査エリアを加工し、Ｐ波はＺ２ガルバノ２０に供給されて、その下にある走査エリアを加工する。ここで、Ｚ１軸加工中にＺ２ガルバノ２０を移動し、逆にＺ２軸加工中にＺ１ガルバノを走査するこによって、高効率な加工が可能となる。
【０００７】
ところで出願人は、特願２００１−３３１５５０において、ステップアンドリピート方式による場合の加工計画に際して、幾つかの効率化の方法を提案している。例えば、［０１７１］〜［０１９１］段に記載の巡回セールスマン問題（ＴＳＰ）の適用や応用、及び、［０１８７］、［０１８８］段に記載の、左右のスキャナ走査時間均等化（マッチングと称している）等が挙げられる。
【０００８】
【発明が解決しようとする課題】
ところが、タイムシェア２軸加工機においては、Ｚ１（Ｚ２）のスキャナ走査と、Ｚ２（Ｚ１）の加工が同期するが、このため、巡回セールスマン問題の解法を適用することによって、一巡する際のスキャナの総走査時間を短縮しても、必ずしも各回の加工時間がスキャナ走査時間より長くなるとは限らず、一方の軸で加工が終わったにも拘らず、他方の軸でスキャナ走査が完了しないということが起こっていた。ここで各回の加工時間とは、図４に示す如く、実際の照射及び照射インタバル、照射前後の通信等に消費する時間などを含めるものとする。即ち、前の穴からの走査完了時刻と、次の穴への走査開始時刻の差をもって加工時間とする。
【０００９】
又、タイムシェア２軸加工機は、エネルギシェア２軸加工機のように、左右のスキャナ走査のタイミングは同期しないため、マッチングは意味をなさない。
【００１０】
なお、各走査エリアにおけるガルバノスキャナの走査時間を短縮するための巡回セールスマン問題の解法適用例は、他に特許文献１や特許文献２が挙げられる。しかしながら、これらにはタイムシェア２軸加工機に関する記載は見当たらない。
【００１１】
【特許文献１】
特開２００１−３４８３７３号公報
【特許文献２】
特開平５−２１１３９８号公報
【００１２】
一方、特許文献３には、タイムシェア２軸加工機に関する記載があるが、ここでの記載は、ビーム偏光手段やビーム矩形成形手段等であり、加工計画に関する記載は見当たらない。
【００１３】
【特許文献３】
特開２０００−２６３２７１号公報
【００１４】
本発明は、前記従来の問題点を解消するべくなされたもので、タイムシェア方式の２軸加工機において、ステップアンドリピード方式で動かす場合に、各走査エリア内においてスキャナの走査完了後の待ち時間を少くあるいは無くして、加工時間を短縮することを課題とする。
【００１５】
【課題を解決するための手段】
本発明は、レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画方法において、各回の走査時間の加工時間からの超過量を求め、該超過量の総和が最小若しくは０となるように加工を計画し、各加工ヘッド毎に設定した走査エリアの加工時間を最小化するようにして、前記課題を解決したものである。
【００１６】
又、前記加工計画が、暫定的な経路を発生する暫定経路発生工程と、暫定的な経路における各回の走査時間の加工時間からの超過量を計算する超過量計算工程と、改善解を探索するための探索の基準点を採択する基準点採択工程と、暫定解に対し解の近傍内で改善解を探索する近傍探索工程と、改善解が見つかった場合は経路を更新する経路更新工程と、暫定解の総超過量が０の場合は最適解発見として計画を終了する最適解終了工程と、を含むようにしたものである。
【００１７】
又、前記最適解終了工程において、各穴に対し、その穴へ及びその穴から２つの走査が超過しているかどうかを記憶する超過判定用変数を付随させることにより、超過の有無を高速に判定できるようにしたものである。
【００１８】
又、前記基準点採択工程において、各穴に対し、その穴へ又はその穴からの走査は近傍探索により改善すべき余地が有るかどうかを記憶する要探索判定用変数を付随させることにより、高速に採択できるようにしたものである。
【００１９】
又、前記近傍探索工程における近傍を、２−ｏｐｔ近傍、３−ｏｐｔ近傍、リンカーニハン近傍、Ｏｒ−ｏｐｔ近傍、ダブルブリッジ近傍のいずれかとしたものである。
【００２０】
又、前記加工計画が、更に、前記要探索判定用変数が全て０になった際に、暫定解で計画を終了する暫定解終了工程と、計画を終了せずに近傍を新たなものに切り替える近傍更新工程と、を含むようにしたものである。
【００２１】
又、前記加工計画が、更に、各穴に対し、近傍探索を高速に実現するためにリスト長が各点に依存するような可変近傍リストを予め作成しておくようにしたものである。
【００２２】
本発明は、又、レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画方法において、各回の加工穴間の移動コストを、各回の走査時間に対し、走査時間に依存するペナルティ関数を掛け合わせたものとし、各加工ヘッド毎に設定した走査エリア内の加工時間を最小化するようにして、前記課題を解決したものである。
【００２３】
又、前記ペナルティ関数を、加工時間に対して、該加工時間より走査時間の方が大きい場合は大きな正数、さもなければ小さな正数とするようにしたものである。
【００２４】
又、前記加工計画上の加工時間を、実際の時間より小さめに設定するようにしたものである。
【００２５】
又、前記加工ヘッド数がＮ（Ｎ≧３）である時に、前記加工時間を、加工時間のＮ−１倍と読み替えるようにしたものである。
【００２６】
本発明は、又、前記の加工計画方法により決定された加工を行なうことを特徴とする加工方法を提供するものである。
【００２７】
又、レーザ発振器から出力されたレーザ光を時分割して、Ｎ台の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工方法において、各回の走査時間が、各回の加工時間のＮ−１倍以下であることを特徴とするレーザ加工機の加工方法を提供するものである。
【００２８】
又、前記の加工計画方法又は加工方法を実現するためのコンピュータプログラムを提供するものである。
【００２９】
本発明は、又、レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画装置において、各回の走査時間の加工時間からの超過量を求める手段と、該超過量の総和が最小若しくは０となるように加工を計画して、各加工ヘッド毎に設定した走査エリアの加工時間を最小化する手段とを備えることにより、前記課題を解決したものである。
【００３０】
又、レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えた複数の加工ヘッドに供給するようにしたレーザ加工機の各走査エリア内の穴あけ位置訪問順序を計画する加工計画装置において、各回の加工穴間の移動コストを、各回の走査時間に対し、該走査時間に依存するペナルティ関数を掛け合わせたものとして、各加工ヘッド毎に設定した走査エリア内の加工時間を最小化する手段を備えることにより、前記課題を解決したものである。
【００３１】
本発明は、又、前記の加工計画装置を含むことを特徴とする加工装置を提供するものである。
【００３２】
又、レーザ発振器から出力されたレーザ光を時分割して、走査手段を備えたＮ台の加工ヘッドに供給するようにしたレーザ加工装置において、各回の走査時間を、各回の加工時間のＮ−１倍以下とする手段を備えたことを特徴とするレーザ加工装置を提供するものである。
【００３３】
又、前記の加工計画装置又は加工装置を実現するためのコンピュータプログラムを提供するものである。
【００３４】
又、前記のコンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体を提供するものである。
【００３５】
【発明の実施の形態】
以下図面を参照して、ＸＹステージとガルバノスキャナを備えたレーザ穴開け機により穴を開ける場合に適用した、本発明の実施形態を詳細に説明する。
【００３６】
本実施形態は、図５に示す如く、レーザ穴開け機３０と、例えばハードディスクやフレキシブルディスク等の外部メモリに記憶された、前記レーザ穴開け機３０が加工を行なうための加工データファイル群４２、該加工データファイル群４２を変換する加工データ変換プログラム（Ｐｒｇ）４４、例えば内部メモリに記憶された加工データ４６、例えば外部メモリに記録された動作モデルファイル４８、該動作モデルファイル４８を読み込むための動作も出るファイル読込みプログラム（Ｐｒｇ）５０、例えば内部メモリに記憶された動作モデルデータ５２、本発明に係る加工計画プログラム（Ｐｒｇ）５４、前記レーザ穴開け機３０を制御する加工制御プログラム（Ｐｒｇ）５６を含む、前記レーザ穴開け機３０と通信可能なパソコン（ＰＣ）４０とを備えている。
【００３７】
なお、図５では、加工を制御する加工制御プログラム５６と、加工を計画する加工計画プログラム５４が、同じＰＣ４０内に収まっており、加工計画がオンラインで処理されるが、これらは別個でもよい。即ち、加工計画プログラム５４は、オフラインで実行可能である。
【００３８】
前記レーザ穴開け機３０は、図１に示したように、レーザ発振器１０が１つの２軸加工機とされている。又、レーザビーム１１の進行方向をＥＯＭ１２及びポラライザ１４等を用いて切り替えるタイムシェア方式とされている。なお、後述するが、本発明の適用対象の軸数は２に限定されず、複数であれば適用可能である。
【００３９】
以下、レーザ穴開け機のオンライン形態の場合について説明する。なお、オフラインでも作用は同じである。
【００４０】
本実施形態において、ＰＣ４０と通信可能なレーザ穴開け機３０は、加工データ４６に従って、加工制御プログラム５６により制御され、加工を行なう。加工データ４６は、通常、ハードディスクやフレキシブルディスク等の外部メモリにある加工データファイル群４２を、加工データ変換プログラム４４で変換することにより得られる。加工データ４６は、レーザ穴開け機３０を効率良く動かすために、加工計画プログラム５４により更新される。この加工計画プログラム５４は、内部機器（ガルバノスキャナ及びＸＹステージ）の動作をモデル化した動作モデル５２を用いる。この動作モデル５２は、通常、内部メモリに常駐していないので、外部メモリにある動作モデルファイル４８を、動作モデルファイル読込みプログラム５０を用いて読み込むことにより得る。
【００４１】
前記レーザ穴開け機３０は、前記加工データファイル群４２の内容に従って動作する。加工開始命令の後、レーザ穴開け機３０の動作を制御するのは、前記加工制御プログラム５６である。即ち、当事者は、加工に際して加工データファイル群４２を用意し、加工制御プログラム５６に加工開始命令を与えて、レーザ穴開け機３０を動作させる。
【００４２】
前記加工データファイル群４２の内容は、構成機器（ガルバノスキャナ及びＸＹステージ）の動作順序が最適でないようなことも有り得る。従って、前記加工計画プログラム５４は、加工データを最適化する。本発明は、この加工計画プログラム５４における穴開け位置訪問順序最適化機能に関するものである。より詳しくは、特願２００１−３３１５５０における穴開け位置訪問順序確定工程Ｅ（図１２参照）等のように、加工位置が属するエリアが決まった段階での、各走査エリアにおけるガルバノスキャナの走査経路を効率化する際の方法である。
【００４３】
以下、詳細に説明する。
【００４４】
タイムシェア２軸加工機においては、Ｚ１（Ｚ２）のスキャナ走査と、Ｚ２（Ｚ１）の加工が同期するが、このことは、１穴当たりの加工時間が、加工時間とスキャナ走査時間の長い方であることを意味する。即ち、各回の走査時間を全て、一定である加工時間以下とすれば、それ以上加工時間を短縮することはできない。なお、以下では、加工時間をＴで表わす。
【００４５】
従って、タイムシェア２軸加工機における加工計画の目的は、「各回の走査時間を加工時間Ｔ以下にすること。不可能ならば、Ｔを超過する時間の総和を最小化すること」にある。
【００４６】
この目的のために、次の２つの方法を用いる。
【００４７】
方法１：通常の局所探索法の範疇に入る方法について、目的関数、改善ルールに工夫を加える。
【００４８】
方法２：通常の局所探索法の範疇に入る方法について、移動コストにペナルティを与える。
【００４９】
なお、両方法は、いずれも図６に示す局所探索法を適用するものである。この局所探索法は、近傍内を、探索ルールに従って解を逐次改善するような方法の一般名称である。ＴＳＰにおいては、近傍の名に因んで、例えば２−ｏｐｔ法、３−ｏｐｔ法、Ｏｒ−ｏｐｔ法、リンカーニハン（Ｌｉｎ−Ｋｅｒｎｉｇｈｈａｎ）法等の解法が広く用いられている。これらの近傍の概念を図７乃至図１１に示す。なお、図では、巡回路長が長くなるように見えるが、これは、近傍を分かり易く示すためである。例えば図７に示す２−ｏｐｔ法の場合、「削除する２本の枝長（２点間距離）の和−追加する２本の枝長の和が正である」ことが解の更新の条件である。
【００５０】
なお、近傍探索及び改善ルールを用いた（含んだ）他の方法、例えば反復局所探索法、遺伝アルゴリズム（ＧＡ）、シミュレーテッドアニーリング（ＳＡ）を用いる場合でも、局所探索法を部分的に用いるに際して、上記方法１、方法２の考えは容易に適用できる。
【００５１】
以下、方法１、方法２に分けて詳細に説明する。
【００５２】
まず、目的関数、改善ルールに工夫を加えた方法１を用いる本発明の第１実施形態について説明する。
【００５３】
図１２に手順を示す第１実施形態は、加工時間Ｔに対し、走査時間が超過している量の総和を０まで削減するための仕組である。基本は既に図５に示した局所探索法と同じであるが、計算の高速化を考慮して、データ構造や処理の詳細に関し、詳しく記述している。なお、以下に続くアルゴリズムの説明に際しては、穴あけ位置のことを単に点と記す。
【００５４】
以下、図１２に従って説明する。まずステップ１０１０において、リンカーニハン法等の公知のＴＳＰ解法を用いて、通常のように走査エリア内の巡回路長を最小化する（穴数が多いと、完全に最適となる保証はない）。ここで、ステップ１０１０の目的は、巡回路長最小化であり、各回の走査時間はＴの大小を考慮していない。又、ここではリンカーニハン法を例に挙げたが、他の方法を用いて初期解を発生させても、何ら問題は無い。
【００５５】
次いでステップ１０２０で、各回の走査時間の超過量を計算する。超過量は、２数ｐ、ｑの大きい方をｍａｘ（ｐ，ｑ）で表わすと、走査時間Ｓに対しｍａｘ（Ｓ−Ｔ，０）である。
【００５６】
それらが全て０である場合、加工時間が走査時間より常に長いということであるので、これ以上の最適化の余地はない。従って、ステップ１０３０で全て０であるかを判定し、０であれば終了する。
【００５７】
０でないものである場合、計算高速化の工夫のため、ステップ１０４０で、各点に付随される次の２つの変数を設定する。
【００５８】
超過フラグ：現在の巡回路において、その点への走査及びその点からの走査の２つのうち、Ｔより長いものの数（「両方長い」：２、「どちらか一方が長い」：１、「どちらも短い」：０）。この超過フラグは、最適解発見の判定や探索ビットの更新に利用する。
【００５９】
探索ビット：現在の巡回路において、その点は未だ改善解を探索するための探索の基準点となるかどうかを判定するための符号（なる：１、ならない：０）。
【００６０】
これらの処理は、処理高速化のための仕組であり、場合によっては省略することもできる。
【００６１】
続くステップ１０５０は、各点に付随される近傍リスト（リスト長は各点毎に異なる）の（再）作成である。ここで括弧付きで「再」と記したのは、ステップ１０１０でリンカーニハン法を適用した場合等は、既に（リスト長固定の）近傍リストを作っているからである。このステップ１０５０の処理は、ステップ１０７０における改善解の探索において、探索を高速に実行するための前処理である。後にステップ１０７０の説明の際に再度説明する。なお、固定長リストで良い場合など、探索の仕方によっては、この処理は省略することもできる。
【００６２】
ステップ１０６０は、ステップ１０７０における探索において、探索の基準点となる点の選択である。ここで探索の基準点の候補は、例えばキュー（ｑｕｅｕｅ）で管理することもできる。超過量が大きい順に並べた優先度付キュー（ｐｒｉｏｒｉｔｙｑｕｅｕｅ）でもよい。
【００６３】
ステップ１０７０は、良い経路（改善解）の探索である。用いる近傍は、概念的には既に図７乃至図１１に示した２−ｏｐｔ（図７）、３−ｏｐｔ（図８）、Ｏｒ−ｏｐｔ（図９）、リンカーニハン（図１０）等であるが、良い解を探索するための手順は一通りではない。そこで、以下に、本方法における探索ルールを、図１３乃至図１５を用いて説明する。
【００６４】
各点には番号が１つ割り振られている。今、図１３に示す如く、巡回路が９９３番→５５番→１１９番→２７８番→…と繋がっているとする。そして５５番→１１９番の走査時間は、Ｔより長いので、このままの経路だと、この走査は他軸加工の完了に間に合わない。そこで、５５番→１１９番の枝（都市対間を結ぶ線）を削除して、良い経路に離したい。
【００６５】
説明を、ステップ１０６０又は１１５０において、キューの先頭要素であった５５番の点が探索の基準点（ｂで表わす）となった時点から開始する（ｂ＝５５）。後点（ｎ（ｂ）で表わす）は１１９番である（ｎ（ｂ）＝１１９）。図１３には、ｎ（ｂ）を中心とした半径Ｔの円（ここで、実際には走査時間が同一である境界線は、綺麗な真円ではなく、例えば矩形である）が描かれているが、ｎ（ｂ）の前点、後点は、この円の内部にある点であることが重要である。この円を利用した探索方法を、ここでボール探索（ｂａｌｌ　ｓｅａｒｃｈ）と称する。そこで、各点に対し、走査時間がＴ以内の点によるリスト（図１４）を付随させ、このリストを用いて探索を行なえば、無駄な点を探索しなくていいので高速である。このようなリストの大きさは、各点毎に異なる。例えば１１９番の点の近傍リストの大きさは、図１３に示す如く、１１９番の点を中心としたボール内の点数である、６である。又、探索の高速化のため、リストの大きさに制限を付加してもよい。探索のルールは、ｎ（ｂ）に近いものを、リストの先頭から順に、６０番、４８番、２７８番、…と見ていく。例えば、近傍が２−ｏｐｔの場合（図１５）、ｂ＝５５とした（ｎ（ｂ）＝１１９がボールの中心の）探索において、６０番が最初に見つかる。新たに追加する他の枝は１０５番と５５番の間の枝であるが、これはＴ以下なので、改善解である。この場合、ステップ１１００において経路の更新を行なう。
【００６６】
なお、図１６、図１７に示すＯｒ−ｏｐｔ近傍、リンカーニハン近傍における探索ルールについても、簡単に説明する。なお、３−ｏｐｔ近傍に関しては、リンカーニハン近傍の説明に含まれるので省略する。
【００６７】
Ｏｒ−ｏｐｔ近傍の説明図である図１６において、探索の基準点ｂと次の点ｎ（ｂ）との間の枝長が長いとき、ｎ（ｂ）中心のボール探索で、近傍リストを用いてボール内の点を２つ探す。ここで探すべき２点は経路上で隣同士である。又、リンカーニハン近傍の説明図である図１７において、探索の基準点ｂと次の点ｎ（ｂ）との間の枝長が長いとき、ｎ（ｂ）中心のボール探索で、近傍リストを用いてボール内の点を１つ探す。見つかった点の前の点とｂ、及び、見つかった点とｎ（ｂ）を仮に繋げる。ここで、見つかった点の前の点とｂを繋ぐ枝長がＴより大きいときは、探索を続ける必要がある。そこで、見つかった点の前の点（仮に繋げた経路ではｂの次の点ｎ（ｂ）となっている）を、次の探索におけるボールの中心とする。この反復（２−ｏｐｔ移動（ｍｏｖｅ）と称する）を、見つかった点の前の点とｂを繋ぐ枝長がＴより小さくなるまで繰り返す。ｎ回の２−ｏｐｔ移動で処理が終了するとき、ｎ＋１本の枝が削除され、同数の枝が追加される。
【００６８】
又、図１１に示したダブルブリッジ近傍を用いることもできる。追加する４本の枝の長さが全てボールの半径以下ならば、経路の更新を行なう。
【００６９】
なお、以上では、近傍探索における経路更新の判定ルールとして、追加する枝の長さが全てボールの半径以下であるとしたが、そうではなく、「（追加する枝の内、長さがボール半径以下のもの）−（削除する枝のうち、長さがボール半径以下のもの）」が正数であれば、超過する走査である枝数を削減できるので、このように判定してもよい。
【００７０】
ステップ１０８０は、ステップ１０７０で改善解が見つかるかどうかの処理分岐である。見つからなかった場合はステップ１０９０に進み、見つかった場合はステップ１１００に進む。
【００７１】
ステップ１０９０において、探索の基準点ｂのビットを０にし、ステップ１１１０に進む。
【００７２】
ステップ１１１０で探索ビットを調べ、探索ビットが全て０となった場合、ステップ１１２０に進む。その近傍における探索の基準点はもう無いので、ステップ１１２０で近傍を変えて処理を続けるかどうか選択する。これ以上の探索を続けない場合は、最適解ではないが処理を終了する。
【００７３】
探索を続ける場合、ステップ１１３０で近傍を更新し、ステップ１１４０で超過フラグの値に従って探索ビットを再設定し、ステップ１１５０で探索の基準点を定め、経路の探索ステップ１０７０に戻る。
【００７４】
一方、ステップ１１１０で探索ビットが全て０でなければ、ステップ１１５０で探索の基準点を変え、経路の探索ステップ１０７０に戻る。
【００７５】
続いて、ステップ１０７０において改善解が発見されたときの、ステップ１１００以後を説明する。ステップ１１００で経路を更新した後、ステップ１１６０で超過フラグを更新する。このとき、超過フラグが全て０なら（ステップ１１７０）、それは最適解が見つかったことを意味する。即ち、処理を終了する。
【００７６】
一方、ステップ１１７０で０でないものがあるならば、ステップ１１８０で新たな経路での超過量を計算（更新）し、ステップ１１９０で探索ビットを更新し、探索の基準点を定め、経路の探索ステップ１０７０に戻る。
【００７７】
なお、Ｔの値は、加工時間に対し、やや小さめに設定しておくこともできる。そうすると、最適化の制約は厳しくなるが、動作モデルの誤差や機差を吸収できるので、最適解が定まった場合は、常に走査時間を実際の加工時間より短いようにすることができる。
【００７８】
次に、ペナルティ関数を適用・応用した方法２を用いる本発明の第２実施形態について説明する。
【００７９】
本実施形態は、図６に示した局所探索法に属するＴＳＰの解法をそのまま適用する。但し、移動コスト（２点間の移動を行なうときの枝長）を、走査時間のモデルではなく、走査時間に応じてペナルティを掛け合わせたものとする。即ち、走査時間ｔに応じたペナルティ関数をＰ（ｔ）とすると、方法２の移動コストをｔ×Ｐ（ｔ）で定義する。
【００８０】
図１８乃至図２１にペナルティ関数Ｐ（ｔ）の例を示す。
【００８１】
図１８は、走査時間がＴ未満の場合はペナルティ無し（１）、以上の場合は大きなペナルティ（例えば１００）を与えたものである。
【００８２】
ほぼ同様な例として、図１９は、Ｔより小さい値ＴＴを閾値としたもので、これによれば、動作モデルの誤差や機差を吸収することができる。
【００８３】
図２０は、ＴＴとＴの間の部分を直線で補間したもので、これによれば、誤差や機差のためにグレイな部分（ＴとＴＴの間）をグレイなままにしておくことができる。
【００８４】
図２１は、シグモイド関数としたものである。
【００８５】
図２２、図２３は、更にＴＴ以下の箇所、Ｔ以上の箇所に傾斜を付けたものである。図２２によれば、大きな走査に対するペナルティが強まるため、大きな走査が減少し、小さな走査が増大する。図２３によれば、ＴＴより若干小さい走査が優先されるため、大きな走査、小さな走査が共に減少する。
【００８６】
なお、ペナルティ関数はこれらに限定されず、計算機実験や実機加工結果等を通して、相応しいものを設定することができる。
【００８７】
なお、これまでの説明では、タイムシェア２軸加工機について説明されていたが、図２４に示すような構成とすれば、３軸以上の場合でもタイムシェア方式の複数軸加工が可能である。この場合、図２４の如く、ＥＯＭ１２Ａ、１２Ｂの偏光を切り替えることにより、各ガルバノの処理（走査又は待機中、又は、照射中）が切り替わる。
【００８８】
図２５にタイムチャートを示す。上段（Ａ）は、ＥＯＭ１２ＡがＳ波に偏光している場合で、Ｚ１ガルバノ領域が加工中（「加工」の部分）である。中段（Ｂ）は、ＥＯＭ１２ＢがＳ波に偏光している場合で、Ｚ２ガルバノ領域が加工中である。下段（Ｃ）は、ＥＯＭ１２ＡがＰ波に、ＥＯＭ１２ＢがＰ波に偏光している場合で、Ｚ３ガルバノ領域が加工中である。
【００８９】
このような切り替わりの場合、加工時間をＴとすると、各ガルバノが走査可能なのは、加工中の時間に挟まれた２Ｔ時間である。即ち、上記２つの方法においてＴとしたところを２Ｔ（Ｎ軸なら（Ｎ−１）Ｔ）とすれば、共に適用可能である。
【００９０】
なお、前記実施形態においては、走査手段（高速位置決め手段）がスキャナとされ、低速位置決め手段がステージとされていたが、走査手段と位置決め手段の種類や組合せは、これに限定されず、例えば出願人が特開２０００−７１０８９や特開２０００−３３４６３７で提案したような、リニアモータＸＹステージと高速加工ヘッドを組み合わせたスクリーンカットシステムあるいはフラッシュカットシステムであってもよい。
【００９１】
又、適用対象も、点状の加工を行なうレーザ穴開け機に限定されず、線状の加工を行なうレーザ切断機、特開平１１−１４９３１７に記載された２ヘッドレーザ加工機や、機械式ドリルによる穴あけ装置、フューズ溶断機、マーキング装置、露光装置等にも同様に適用できる。
【００９２】
【発明の効果】
本発明によれば、各走査エリア内においてスキャナの走査完了後の待ち時間を少なくあるいは無くして、加工時間を短縮することができる。従って、タイムシェア複数軸機の加工高速化が図れる。
【図面の簡単な説明】
【図１】時分割によるレーザ穴開け機の構成を示す光路図
【図２】前記レーザ穴開け機で用いられるガルバノスキャナの具体的構成例を示す正面図
【図３】前記レーザ穴開け機の各部信号波形の例を示すタイムチャート
【図４】同じく加工時間を示すタイムチャート
【図５】本発明が適用されるレーザ穴開け機の全体構成を示すブロック図
【図６】巡回セールスマン問題における局所探索法の一般的な適用例を示す流れ図
【図７】２−ｏｐｔ近傍の概念を示す線図
【図８】３−ｏｐｔ近傍の概念を示す線図
【図９】Ｏｒ−ｏｐｔ近傍の概念を示す線図
【図１０】リン−カーニハン近傍の概念を示す線図
【図１１】ダブルブリッジ近傍の概念を示す線図
【図１２】本発明に係る第１実施形態の全体構成を示す流れ図
【図１３】第１実施形態におけるボール探索の概念を示す平面図
【図１４】同じく点１１９の近傍リストの例を示す線図
【図１５】同じく点５５を基準点とする探索において、近傍リストを使用する方法を示す平面図
【図１６】Ｏｒ−ｏｐｔ近傍でのボール探索による探索手順を示す平面図
【図１７】リンカーニハン近傍でのボール探索による探索手順を示す平面図
【図１８】本発明の第２実施形態で用いられるペナルティ関数の一例を示す線図
【図１９】同じくペナルティ関数の他の例を示す線図
【図２０】同じくペナルティ関数の更に他の例を示す線図
【図２１】同じくペナルティ関数の更に他の例を示す線図
【図２２】同じくペナルティ関数の更に他の例を示す線図
【図２３】同じくペナルティ関数の更に他の例を示す線図
【図２４】３軸以上のレーザ穴開け機への適用方法を示すブロック図
【図２５】同じく各部信号波形の例を示す線図
【符号の説明】
１０…レーザ発振器
１２、１２Ａ、１２Ｂ…電気光学結晶（ＥＯＭ）
１４、１４Ａ、１４Ｂ…偏光ビームスプリッタ（ポラライザ）
１８、２０…ガルバノスキャナ
３０…レーザ穴開け機
４０…ＰＣ（パソコン）
４２…加工データファイル群
４４…加工データ変換プログラム
４６…加工データ
４８…動作モデルファイル
５０…動作モデル読込みプログラム
５２…動作モデルデータ
５４…加工計画プログラム
５６…加工制御プログラム
【図１】
2004141952.tif 000003
【図２】
2004141952.tif 000004
【図３】
2004141952.tif 000005
【図４】
2004141952.tif 000006
【図５】
2004141952.tif 000007
【図６】
2004141952.tif 000008
【図７】
2004141952.tif 000009
【図８】
2004141952.tif 000010
【図９】
2004141952.tif 000011
【図１０】
2004141952.tif 000012
【図１１】
2004141952.tif 000013
【図１２】
2004141952.tif 000014
【図１３】
2004141952.tif 000015
【図１４】
2004141952.tif 000016
【図１５】
2004141952.tif 000017
【図１６】
2004141952.tif 000018
【図１７】
2004141952.tif 000019
【図１８】
2004141952.tif 000020
【図１９】
2004141952.tif 000021
【図２０】
2004141952.tif 000022
【図２１】
2004141952.tif 000023
【図２２】
2004141952.tif 000024
【図２３】
2004141952.tif 000025
【図２４】
2004141952.tif 000026
【図２５】
2004141952.tif 000027