(57)【要約】ＸＹステージとガルバノスキャナにより位置決めを行なう加工機を用いて加工を行なう際に、加工位置を、ＸＹステージ１２の進行方向と垂直な方向が、加工エリア幅以下の長さの、ワーク１０の配置方向と平行な矩形により分割し、該分割により決定された各加工矩形について、矩形内の総加工時間が最小となるように、ＸＹステージの動作速度及び加工矩形内の加工位置訪問順序を決定し、次いで、前記決定された加工矩形の位置や加工矩形入出口のＸＹステージの動作速度を基に、前記ＸＹステージの動作経路を決定することにより、ＸＹステージの速度、加速度、軌道、及び、加工時の穴開け位置訪問順序を効率良く計画して、加工時間を短縮させる。
2003064107.tif 000002
【特許請求の範囲】
【請求項１】
ワーク上の加工実行箇所を広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画方法であって、
加工位置を、Ｘ又はＹである加工時低速位置決め手段停止方向Ｚの辺長がＤＺ以下であるような矩形により分割する加工矩形分割工程と、
加工矩形分割工程により決定された各加工矩形について、矩形内の総加工時間が最小となるように、加工矩形内の加工位置訪問順序及び低速位置決め手段動作速度を決定する加工位置訪問順序及び低速位置決め手段動作速度最適化工程と、
前記２つの工程により決定された、加工矩形の位置、加工矩形入出口の低速位置決め手段動作速度のうち少なくとも１つをもとに、低速位置決め手段の動作経路を決定する低速位置決め手段動作経路最適化工程と、
を含むことを特徴とする加工計画方法。
【請求項２】
前記加工矩形分割工程が、Ｘ方向又はＹ方向の単純な分割によるものであることを特徴とする請求項１に記載の加工計画方法。
【請求項３】
前記Ｘ方向又はＹ方向の単純な分割を行った後、加工位置が存在しない加工矩形を除くものであることを特徴とする請求項２に記載の加工計画方法。
【請求項４】
前記分割した加工矩形のうち、低速位置決め手段停止方向Ｚの辺長の中で該方向の所定寸の辺長より小さいものがあれば、分割数を変えずに停止方向の辺長を調整して、停止方向辺長の小さな加工矩形を無くすことを特徴とする請求項２に記載の加工計画方法。
【請求項５】
前記加工矩形分割工程が、Ｘ方向又はＹ方向の最少数の分割によるものであることを特徴とする請求項１に記載の加工計画方法。
【請求項６】
前記加工矩形分割工程が、Ｘ方向の分割とＹ方向の分割を両方試行した後、良い方を採択するものであることを特徴とする請求項１に記載の加工計画方法。
【請求項７】
前記加工矩形分割を行った後、各加工矩形において、低速位置決め手段の動作方向に沿って加工位置が、低速位置決め手段の動作方向の所定寸の加工エリアの辺長と速度変化に要する距離の和以上無い箇所が有れば、該矩形を２分することを特徴とする請求項１に記載の加工計画方法。
【請求項８】
前記加工矩形分割を行った後、各加工矩形において、加工位置が低速位置決め手段の動作方向と垂直な方向に対して中央に集まるよう加工矩形の配置を微調整することを特徴とする請求項１に記載の加工計画方法。
【請求項９】
前記加工矩形分割工程が、Ｘ方向の分割とＹ方向の分割を両方試行して加工矩形を確定した後、それらの組合せにより、全体を加工矩形分割するものであることを特徴とする請求項１に記載の加工計画方法。
【請求項１０】
前記加工矩形分割工程が、加工位置の分布パターン及び密度を考慮するようにしたものであることを特徴とする請求項１に記載の加工計画方法。
【請求項１１】
前記加工位置の分布パターン及び密度を考慮した加工矩形分割工程が、
加工位置が密な箇所を識別して加工矩形の配置を確定する工程と、
加工位置が大多数な箇所を識別して加工矩形の配置を確定する工程と、
未だ加工矩形の確定していない加工位置に対して、加工矩形を確定する工程と、
を含むことを特徴とする請求項１０に記載の加工計画方法。
【請求項１２】
前記密な箇所及び大多数な箇所の加工矩形の配置を確定する工程は、
ワーク上の加工領域を格子状に分割して、各格子内の前記加工位置の疎密、もしくは有無の真偽を識別する工程と、
識別された格子の配置を基に、複数の格子群矩形を形成する工程と、
各格子群矩形を被覆するように加工矩形を配置する工程と、
を含むことを特徴とする請求項１１に記載の加工計画方法。
【請求項１３】
前記格子群矩形は、
矩形の外周に当る格子列には必ず真と識別された格子が有って、
矩形の外周の外側に当る格子列の格子は全て偽と識別された格子であることを特徴とする請求項１２に記載の加工計画方法。
【請求項１４】
加工位置が大多数な箇所を識別して加工矩形の配置を確定する工程において、
データ自体にパターンの繰り返しとして記載されている加工位置の広がりを大多数な箇所として識別することを特徴とする請求項１１に記載の加工計画方法。
【請求項１５】
前記各格子群矩形を被覆するように加工矩形を配置する際に、
設定した大きさに満たない格子群矩形は除外して加工矩形配置を決定することを特徴とする請求項１１に記載の加工計画方法。
【請求項１６】
前記各格子群矩形を被覆するように加工矩形を配置する工程において、
格子群矩形の直線状又は格子状の配置を識別して加工矩形配置を決定することを特徴とする請求項１１に記載の加工計画方法。
【請求項１７】
最終的に残った加工位置の存在する箇所が少ない場合は、前記低速位置決め手段を停止させて高速位置決め手段を動作させる低速位置決め手段停止加工を適用することを特徴とする請求項１１に記載の加工計画方法。
【請求項１８】
前記低速位置決め手段停止加工を、低速位置決め手段非停止加工と同じ制御系で実行することを特徴とする請求項１７に記載の加工計画方法。
【請求項１９】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程が、前記高速位置決め手段による移動、位置決め及び加工が可能な加工位置の訪問順序を最適化しつつ、前記低速位置決め手段の等速な速度の最大値を求める、加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程であることを特徴とする請求項１に記載の加工計画方法。
【請求項２０】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程は、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程の後、更に決定された加工位置に対して、加工位置の分布の密度に応じて動作速度を滑らかに変化させる加減速パターンを決定する速度パターン決定工程を行うことを特徴とする請求項１９に記載の加工計画方法。
【請求項２１】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程において、各加工位置の加工タイミングを最早開始時刻及び最遅完了時刻の間に規定する時間枠を、低速位置決め手段動作速度に基づいて定めることを特徴とする請求項１９又は２０に記載の加工計画方法。
【請求項２２】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程において、加工位置間の移動長を、加工位置間の移動量及び低速位置決め手段動作速度に基づいて定めることを特徴とする請求項１９又は２０に記載の加工計画方法。
【請求項２３】
前記各加工位置の時間枠を、
Ｘ又はＹである所定寸の加工エリアの低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺを用いて、
最早開始時刻はＴＳ＋ＰＺ／Ｖで、
最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ）／Ｖで定めることを特徴とする請求項２１に記載の加工計画方法。
【請求項２４】
前記各加工位置の時間枠を、
Ｘ又はＹである所定寸の加工エリアの低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺ、ＤＺより小さい所定の正又は０である値ＤＺＦ、ＤＺＢを用いて、
最早開始時刻はＴＳ＋（ＰＺ＋ＤＺＦ）／Ｖで、
最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ−ＤＺＢ）／Ｖで定めることを特徴とする請求項２１に記載の加工計画方法。
【請求項２５】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程において、
各加工位置の加工開始時刻を、１つ前の加工位置における加工完了後、加工位置間の移動が完了した時刻が、最早開始時刻より早ければ最早開始時刻に、最早開始時刻以降であれば移動が完了した時刻に定めることを特徴とする請求項１９又は２０に記載の加工計画方法。
【請求項２６】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程が、
加工位置訪問順序を発生させる加工位置訪問順序発生工程と、
加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程と、
によることを特徴とする請求項１９又は２０に記載の加工計画方法。
【請求項２７】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程が、
加工位置訪問順序を発生させる加工位置訪問順序発生工程と、
加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程と、
低速位置決め手段動作速度を固定して加工位置訪問順序を改善する加工位置訪問順序改善工程と、
を全て含むことを特徴とする請求項１９又は２０に記載の加工計画方法。
【請求項２８】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程は、
加工位置訪問順序を発生させる加工位置訪問順序発生工程、
加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程、及び、
低速位置決め手段動作速度を固定して加工位置訪問順序を改善する加工位置訪問順序改善工程と該低速位置決め手段動作速度算出工程とを１乃至複数回繰り返す、繰り返し改善工程、
からなる工程であることを特徴とする請求項１９又は２０に記載の加工計画方法。
【請求項２９】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程が、
加工位置訪問順序を発生させる加工位置訪問順序発生工程と、
加工実行可能性の判定を伴わずに加工位置訪問順序改善工程を繰り返し実行する判定なしの加工位置訪問順序改善工程と、
加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程と、
によることを特徴とする請求項１９又は２０に記載の加工計画方法。
【請求項３０】
前記加工位置訪問順序発生工程による加工順序は、
前記低速位置決め手段の動作方向に対して、幅を設定して加工矩形の分割を行い、
該幅内では、該幅に収まる加工位置を、動作方向と垂直な方向にソートして、ある幅内で昇順ソートであれば、その隣の幅内で降順ソートであるようにすることにより、加工位置の訪問経路が蛇行状となるようにした順序であることを特徴とする請求項２６乃至２９のいずれかに記載の加工計画方法。
【請求項３１】
前記低速位置決め手段動作方向に対して幅を設定して帯状の矩形に分割する際の分割幅を、加工矩形内の加工位置の密度に基づいて設定することを特徴とする請求項３０に記載の加工計画方法。
【請求項３２】
前記繰り返し改善工程は、
加工実行不可能な高速側低速位置決め手段動作速度及び可能な低速側動作速度の間の値Ｖについて、まず実行可能かどうかを判定し、
実行可能な場合は低速側動作速度をＶで更新し、
実行不可能な場合は、Ｖについて加工位置訪問順序改善工程を繰り返し実行し、
実行可能となった場合は低速側動作速度をＶで更新、最後まで実行可能とならない場合は高速側動作速度をＶで更新する処理を、繰り返し回数が設定回数より多くなるまで、又は、高速側動作速度と低速側動作速度の差が設定値より小さくなるまで繰り返す工程であることを特徴とする請求項２８に記載の加工計画方法。
【請求項３３】
前記繰り返し改善工程は、
加工実行可能な低速位置決め手段動作速度Ｖについて、加工位置訪問順序改善工程を繰り返し実行し、
改善解が無くなった時点で加工実行可能な動作速度を更新する処理を、繰り返し回数が設定回数より多くなるまで、又は、加工位置訪問順序改善工程の前後で総加工時間が短縮できなくなるまで、又は、加工位置訪問順序改善工程の前後で低速位置決め手段動作速度の改善量が設定値より小さくなるまで繰り返す工程であることを特徴とする請求項２８に記載の加工計画方法。
【請求項３４】
前記加工位置訪問順序改善工程は、時間枠付き非対称ハミルトン路長最小化問題又は時間枠付き対称ハミルトン路長最小化問題の解法を適用することを特徴とする請求項２６乃至２９のいずれかに記載の加工計画方法。
【請求項３５】
前記時間枠付き対称又は非対称ハミルトン路長最小化問題の解法として、Ｏｒ−Ｏｐｔ法を用いることを特徴とする請求項３４に記載の加工計画方法。
【請求項３６】
前記加工位置訪問順序改善工程及び前記低速位置決め手段動作速度算出工程における加工実行可能性は、全ての加工位置の、加工完了時刻及び最遅完了時刻の差に基づいて判定することを特徴とする請求項２６乃至２９のいずれかに記載の加工計画方法。
【請求項３７】
前記加工位置訪問順序改善工程及び前記低速位置決め手段動作速度算出工程における加工実行可能性は、全ての加工位置の加工完了時刻が、加工終了の最も遅いタイミングである最遅完了時刻よりも早ければ実行可能、そうでなければ実行不可能と判定することを特徴とする請求項２６乃至２９のいずれかに記載の加工計画方法。
【請求項３８】
前記加工位置訪問順序改善工程における改善解の判定は、加工矩形内で最後に訪問する加工位置の加工完了時刻及び前記加工実行可能性の少なくとも一方に基づくことを特徴とする請求項２６乃至２９のいずれかに記載の加工計画方法。
【請求項３９】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程が、先ず、矩形内の加工位置訪問順序を決定し、次いで、決定された経路における前記低速位置決め手段の等速動作を最速化するものである請求項１に記載の加工計画方法。
【請求項４０】
前記速度パターン決定工程が、加工矩形内の加工位置の分布が疎な部分における前記低速位置決め手段の動作速度を高速化するものである請求項２０に記載の加工計画方法。
【請求項４１】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程の結果、全ての加工位置における加工完了時刻が前記最遅完了時刻より早ければ、全ての加工位置の加工開始時刻を、全ての加工位置において加工完了時刻が最遅完了時刻より早い範囲で同一時間分遅い時刻方向へシフトすることを特徴とする請求項１に記載の加工計画方法。
【請求項４２】
前記低速位置決め手段動作経路最適化工程が、加工矩形間を移動する時間の総和を最小化するものであることを特徴とする請求項１に記載の加工計画方法。
【請求項４３】
前記低速位置決め手段動作経路最適化工程が、都市が各加工矩形の入口と出口に対応する位置それぞれであって、矩形の入出口に当る都市間の枝に除去禁止の制約を持つ巡回セールスマン問題もしくはハミルトン路長最小化問題を解く工程であることを特徴とする請求項１又は４２に記載の加工計画方法。
【請求項４４】
前記低速位置決め手段動作経路最適化工程が、加工矩形の訪問順序を最適化した後に、各矩形の入出口を決定するものであることを特徴とする請求項１又は４２に記載の加工計画方法。
【請求項４５】
前記低速位置決め手段動作経路最適化工程が、各矩形の入出口を決定した後に、矩形の訪問順序を最適化するものであることを特徴とする請求項１又は４２に記載の加工計画方法。
【請求項４６】
ワーク上の加工実行箇所を、広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画方法であって、
ワーク全体の加工位置の訪問順序を最適化する全加工位置訪問順序最適化工程と、
該全加工位置訪問順序最適化工程で決定された加工位置訪問順序に対して低速位置決め手段の動作パターンを決定する低速位置決め手段動作パターン決定工程と、
を含むことを特徴とする加工計画方法。
【請求項４７】
前記低速位置決め手段動作パターン決定工程が、先ず、加工位置を所定寸矩形と同寸の矩形でグループ分けし、次いで、各グループの加工位置に対応する低速位置決め手段制御目標位置を決定することを特徴とする請求項４６に記載の加工計画方法。
【請求項４８】
ワーク上の加工実行箇所を、広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画方法であって、
加工位置を、Ｘ又はＹである加工時低速位置決め手段停止方向Ｚの辺長がＤＺ以下であるような矩形により分割する加工矩形分割工程と、
該加工矩形分割工程により決定された各加工矩形について、加工位置の訪問順序を最適化する加工位置訪問順序最適化工程と、
該加工位置訪問順序最適化工程により決定された加工位置訪問順序に対して、前記低速位置決め手段の動作パターンを決定する低速位置決め手段動作パターン決定工程と、
を含むことを特徴とする加工計画方法。
【請求項４９】
請求項１乃至４８のいずれかに記載の加工計画方法により決定された加工を行うことを特徴とする加工方法。
【請求項５０】
請求項１乃至４８のいずれかに記載の加工計画方法又は請求項４９に記載の加工方法を実施するためのコンピュータプログラム。
【請求項５１】
ワーク上の加工実行箇所を広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画装置であって、
加工位置を、Ｘ又はＹである加工時低速位置決め手段停止方向Ｚの辺長がＤＺ以下であるような矩形により分割する加工矩形分割手段と、
加工矩形分割手段により決定された各加工矩形について、矩形内の総加工時間が最小となるように、加工矩形内の加工位置訪問順序及び低速位置決め手段動作速度を決定する加工位置訪問順序及び低速位置決め手段動作速度最適化手段と、
前記２つの手段により決定された、加工矩形の位置、加工矩形入出口の低速位置決め手段動作速度のうち少なくとも１つをもとに、低速位置決め手段の動作経路を決定する低速位置決め手段動作経路最適化手段と、
を含むことを特徴とする加工計画装置。
【請求項５２】
前記加工矩形分割手段が、Ｘ方向又はＹ方向の単純な分割を行うようにされていることを特徴とする請求項５１に記載の加工計画装置。
【請求項５３】
前記Ｘ方向又はＹ方向の単純な分割を行った後、加工位置が存在しない加工矩形を除くようにされていることを特徴とする請求項５２に記載の加工計画装置。
【請求項５４】
前記分割した加工矩形のうち、低速位置決め手段停止方向Ｚの辺長の中で該方向の所定寸の辺長より小さいものがあれば、分割数を変えずに停止方向の辺長を調整して、停止方向辺長の小さな加工矩形を無くすことを特徴とする請求項５２に記載の加工計画装置。
【請求項５５】
前記加工矩形分割手段が、Ｘ方向又はＹ方向の最少数の分割を行うようにされていることを特徴とする請求項５１に記載の加工計画装置。
【請求項５６】
前記加工矩形分割手段が、Ｘ方向の分割とＹ方向の分割を両方試行した後、良い方を採択するようにされていることを特徴とする請求項５１に記載の加工計画装置。
【請求項５７】
前記加工矩形分割を行った後、各加工矩形において、低速位置決め手段の動作方向に沿って加工位置が、低速位置決め手段の動作方向の所定寸の加工エリアの辺長と速度変化に要する距離の和以上無い箇所が有れば、該矩形を２分するようにされていることを特徴とする請求項５１に記載の加工計画装置。
【請求項５８】
前記加工矩形分割を行った後、各加工矩形において、加工位置が低速位置決め手段の動作方向と垂直な方向に対して中央に集まるよう加工矩形の配置を微調整するようにされていることを特徴とする請求項５１に記載の加工計画装置。
【請求項５９】
前記加工矩形分割手段が、Ｘ方向の分割とＹ方向の分割を両方試行して加工矩形を確定した後、それらの組合せにより、全体を加工矩形分割するようにされていることを特徴とする請求項５１に記載の加工計画装置。
【請求項６０】
前記加工矩形分割手段が、加工位置の分布パターン及び密度を考慮するようにされていることを特徴とする請求項５１に記載の加工計画装置。
【請求項６１】
前記加工位置の分布パターン及び密度を考慮した加工矩形分割手段が、
加工位置が密な箇所を識別して加工矩形の配置を確定する手段と、、
加工位置が大多数な箇所を識別して加工矩形の配置を確定する手段と、
未だ加工矩形の確定していない加工位置に対して、加工矩形を確定する手段と、
を含むことを特徴とする請求項６０に記載の加工計画装置。
【請求項６２】
前記密な箇所及び大多数な箇所の加工矩形の配置を確定する手段は、
ワーク上の加工領域を格子状に分割して、各格子内の前記加工位置の疎密、もしくは有無の真偽を識別する手段と、
識別された格子の配置を基に、複数の格子群矩形を形成する手段と、
各格子群矩形を被覆するように加工矩形を配置する手段と、
を含むことを特徴とする請求項６１に記載の加工計画装置。
【請求項６３】
前記格子群矩形は、
矩形の外周に当る格子列には必ず真と識別された格子が有って、
矩形の外周の外側に当る格子列の格子は全て偽と識別された格子であるようにされていることを特徴とする請求項６２に記載の加工計画装置。
【請求項６４】
加工位置が大多数な箇所を識別して加工矩形の配置を確定する手段において、
データ自体にパターンの繰り返しとして記載されている加工位置の広がりを大多数な箇所として識別するようにされていることを特徴とする請求項６１に記載の加工計画装置。
【請求項６５】
前記各格子群矩形を被覆するように加工矩形を配置する際に、
設定した大きさに満たない格子群矩形は除外して加工矩形配置を決定するようにされていることを特徴とする請求項６１に記載の加工計画装置。
【請求項６６】
前記各格子群矩形を被覆するように加工矩形を配置する手段において、
格子群矩形の直線状又は格子状の配置を識別して加工矩形配置を決定することを特徴とする請求項６１に記載の加工計画装置。
【請求項６７】
最終的に残った加工位置の存在する箇所が少ない場合は、前記低速位置決め手段を停止させて高速位置決め手段を動作させる低速位置決め手段停止加工を適用するようにされていることを特徴とする請求項６１に記載の加工計画装置。
【請求項６８】
前記低速位置決め手段停止加工を、低速位置決め手段非停止加工と同じ制御系で実行できるようにされていることを特徴とする請求項６７に記載の加工計画装置。
【請求項６９】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化手段が、前記高速位置決め手段による移動、位置決め及び加工が可能な加工位置の訪問順序を最適化しつつ、前記低速位置決め手段の等速な速度の最大値を求める、加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段であることを特徴とする請求項５１に記載の加工計画装置。
【請求項７０】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化手段は、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段の後、更に決定された加工位置に対して、加工位置の分布の密度に応じて動作速度を滑らかに変化させる加減速パターンを決定することを特徴とする請求項６９に記載の加工計画装置。
【請求項７１】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段において、各加工位置の加工タイミングを最早開始時刻及び最遅完了時刻の間に規定する時間枠を、低速位置決め手段動作速度に基づいて定めるようにされていることを特徴とする請求項６９又は７０に記載の加工計画装置。
【請求項７２】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段において、加工位置間の移動長を、加工位置間の移動量及び低速位置決め手段動作速度に基づいて定めるようにされていることを特徴とする請求項６９又は請求項７０に記載の加工計画装置。
【請求項７３】
前記各加工位置の時間枠を、
Ｘ又はＹである所定寸の加工エリアの低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺを用いて、
最早開始時刻はＴＳ＋ＰＺ／Ｖで、
最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ）／Ｖで定めるようにされていることを特徴とする請求項７１に記載の加工計画装置。
【請求項７４】
前記各加工位置の時間枠を、
Ｘ又はＹである所定寸の加工エリアの低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺ、ＤＺより小さい所定の正又は０である値ＤＺＦ、ＤＺＢを用いて、
最早開始時刻はＴＳ＋（ＰＺ＋ＤＺＦ）／Ｖで、
最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ−ＤＺＢ）／Ｖで定めるようにされていることを特徴とする請求項７１に記載の加工計画装置。
【請求項７５】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段において、
各加工位置の加工開始時刻を、１つ前の加工位置における加工完了後、加工位置間の移動が完了した時刻が、最早開始時刻より早ければ最早開始時刻に、最早開始時刻以降であれば移動が完了した時刻に定めるようにされていることを特徴とする請求項６９又は７０に記載の加工計画装置。
【請求項７６】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段が、
加工位置訪問順序を発生させる加工位置訪問順序発生手段と、
加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出手段と、
を含むことを特徴とする請求項６９又は７０に記載の加工計画装置。
【請求項７７】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段が、
加工位置訪問順序を発生させる加工位置訪問順序発生手段と、
加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出手段と、
低速位置決め手段動作速度を固定して加工位置訪問順序を改善する加工位置訪問順序改善手段と、
を全て含むことを特徴とする請求項６９又は７０に記載の加工計画装置。
【請求項７８】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段は、
加工位置訪問順序を発生させる加工位置訪問順序発生手段、
加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出手段、及び、
低速位置決め手段動作速度を固定して加工位置訪問順序を改善する加工位置訪問順序改善手段と該低速位置決め手段動作速度算出手段とを１乃至複数回繰り返して行う、繰り返し改善手段、
からなることを特徴とする請求項６９又は７０に記載の加工計画装置。
【請求項７９】
前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化手段が、
加工位置訪問順序を発生させる加工位置訪問順序発生手段と、
加工実行可能性の判定を伴わずに加工位置訪問順序改善手段を繰り返し実行する判定なしの加工位置訪問順序改善手段と、
加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出手段と、
を含むことを特徴とする請求項６９又は７０に記載の加工計画装置。
【請求項８０】
前記加工位置訪問順序発生手段による加工順序は、
前記低速位置決め手段の動作方向に対して、幅を設定して加工矩形の分割を行い、
該幅内では、該幅に収まる加工位置を、動作方向と垂直な方向にソートして、ある幅内で昇順ソートであれば、その隣の幅内で降順ソートであるようにすることにより、加工位置の訪問経路が蛇行状となるようにした順序であることを特徴とする請求項７６乃至７９のいずれかに記載の加工計画装置。
【請求項８１】
前記低速位置決め手段動作方向に対して幅を設定して帯状の矩形に分割する際の分割幅を、加工矩形内の加工位置の密度に基づいて設定するようにされていることを特徴とする請求項８０に記載の加工計画装置。
【請求項８２】
前記繰り返し改善手段は、
加工実行不可能な高速側低速位置決め手段動作速度及び可能な低速側動作速度の間の値Ｖについて、まず実行可能かどうかを判定し、
実行可能な場合は低速側動作速度をＶで更新し、
実行不可能な場合は、Ｖについて加工位置訪問順序改善手段を繰り返し実行し、
実行可能となった場合は低速側動作速度をＶで更新、最後まで実行可能とならない場合は高速側動作速度をＶで更新する処理を、繰り返し回数が設定回数より多くなるまで、又は、高速側動作速度と低速側動作速度の差が設定値より小さくなるまで繰り返す手段であることを特徴とする請求項７８に記載の加工計画装置。
【請求項８３】
前記繰り返し改善手段は、
加工実行可能な低速位置決め手段動作速度Ｖについて、加工位置訪問順序改善手段を繰り返し実行し、
改善解が無くなった時点で加工実行可能な動作速度を更新する処理を、繰り返し回数が設定回数より多くなるまで、又は、加工位置訪問順序改善手段の前後で総加工時間が短縮できなくなるまで、又は、加工位置訪問順序改善手段の前後で低速位置決め手段動作速度の改善量が設定値より小さくなるまで繰り返す手段であることを特徴とする請求項７８に記載の加工計画装置。
【請求項８４】
前記加工位置訪問順序改善手段は、時間枠付き非対称ハミルトン路長最小化問題又は時間枠付き対称ハミルトン路長最小化問題の解法を適用するようにされていることを特徴とする請求項７６又は７９に記載の加工計画装置。
【請求項８５】
前記時間枠付き対称又は非対称ハミルトン路長最小化問題の解法として、Ｏｒ−Ｏｐｔ法を用いるようにされていることを特徴とする請求項８４に記載の加工計画装置。
【請求項８６】
前記加工位置訪問順序改善手段及び前記低速位置決め手段動作速度算出手段における加工実行可能性は、全ての加工位置の、加工完了時刻及び最遅完了時刻の差に基づいて判定するようにされていることを特徴とする請求項７６乃至７９のいずれかに記載の加工計画方法。
【請求項８７】
前記加工位置訪問順序改善手段及び前記低速位置決め手段動作速度算出手段における加工実行可能性は、全ての加工位置の加工完了時刻が、加工終了の最も遅いタイミングである最遅完了時刻よりも早ければ実行可能、そうでなければ実行不可能と判定するようにされていることを特徴とする請求項７６乃至７９のいずれかに記載の加工計画装置。
【請求項８８】
前記加工位置訪問順序改善手段における改善解の判定は、加工矩形内で最後に訪問する加工位置の加工完了時刻及び前記加工実行可能性の少なくとも一方に基づくようにされていることを特徴とする請求項７６乃至７９のいずれかに記載の加工計画装置。
【請求項８９】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化手段が、先ず、矩形内の加工位置訪問順序を決定し、次いで、決定された経路における前記低速位置決め手段の等速動作を最速化するようにされている請求項１に記載の加工計画装置。
【請求項９０】
前記速度パターン決定手段が、加工矩形内の加工位置の分布が疎な部分における前記低速位置決め手段の動作速度を高速化するようにされている請求項７０に記載の加工計画装置。
【請求項９１】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化手段の結果、全ての加工位置における加工完了時刻が前記最遅完了時刻より早ければ、全ての加工位置の加工開始時刻を、全ての加工位置において加工完了時刻が最遅完了時刻より早い範囲で同一時間分遅い時刻方向へシフトするようにされていることを特徴とする請求項５１に記載の加工計画装置。
【請求項９２】
前記低速位置決め手段動作経路最適化手段が、加工矩形間を移動する時間の総和を最小化するようにされていることを特徴とする請求項６４に記載の加工計画装置。
【請求項９３】
前記低速位置決め手段動作経路最適化手段が、都市が各加工矩形の入口と出口に対応する位置それぞれであって、矩形の入出口に当る都市間の枝に除去禁止の制約を持つ巡回セールスマン問題もしくはハミルトン路長最小化問題を解くようにされていることを特徴とする請求項５１又は９２に記載の加工計画装置。
【請求項９４】
前記低速位置決め手段動作経路最適化手段が、加工矩形の訪問順序を最適化した後に、各矩形の入出口を決定するようにされていることを特徴とする請求項１又は４８に記載の加工計画装置。
【請求項９５】
前記低速位置決め手段動作経路最適化手段が、各矩形の入出口を決定した後に、矩形の訪問順序を最適化するようにされていることを特徴とする請求項５１又は９２に記載の加工計画装置。
【請求項９６】
ワーク上の加工実行箇所を、広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画装置であって、
ワーク全体の加工位置の訪問順序を最適化する全加工位置訪問順序最適化手段と、
該全加工位置訪問順序最適化手段で決定された加工位置訪問順序に対して低速位置決め手段の動作パターンを決定する低速位置決め手段動作パターン決定手段と、
を含むことを特徴とする加工計画装置。
【請求項９７】
前記低速位置決め手段動作パターン決定手段が、先ず、加工位置を所定寸矩形と同寸の矩形でグループ分けし、次いで、各グループの加工位置に対応する低速位置決め手段制御目標位置を決定するようにされていることを特徴とする請求項９６に記載の加工計画装置。
【請求項９８】
ワーク上の加工実行箇所を、広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画装置であって、
加工位置を、Ｘ又はＹである加工時低速位置決め手段停止方向Ｚの辺長がＤＺ以下であるような矩形により分割する加工矩形分割手段と、
該加工矩形分割手段により決定された各加工矩形について、加工位置の訪問順序を最適化する加工位置訪問順序最適化手段と、
該加工位置訪問順序最適化手段により決定された加工位置訪問順序に対して、前記低速位置決め手段の動作パターンを決定する低速位置決め手段動作パターン決定手段と、
を含むことを特徴とする請求項９７に記載の加工計画装置。
【請求項９９】
請求項５１乃至９８のいずれかに記載の加工計画装置を含むことを特徴とする加工装置。
【請求項１００】
請求項５１乃至９８のいずれかに記載の加工計画装置又は請求項９９に記載の加工装置を実現するためのコンピュータプログラム。
【請求項１０１】
請求項５０又は１００に記載のコンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
技術分野
本発明は、ワーク上の加工実行箇所を広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画方法及び装置、前記加工計画方法により決定された加工を行う加工方法、前記加工計画装置を含む加工装置、前記加工計画方法を実施したり前記加工計画装置を実現するためのコンピュータプログラム、及び、該コンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体に関する。
背景技術
近年、電子機器の小型化や高密度実装化の要求に伴い、複数のプリント配線基板を重ね合わせた多層プリント配線基板が提供されるようになってきている。このような多層プリント配線基板では、上下に積層されたプリント配線基板のそれぞれに形成された導電層間を電気的に接続するため、これらの基板に、スルーホールあるいはビアホールと呼ばれる穴が形成される。そして、これらの穴の内部に導電膜を形成することにより、各プリント配線基板の導電層間の接続が行われる。
プリント配線基板に形成される穴は、最近のプリント配線基板の小型化や高機能化に伴って小型化し、直径０．１ｍｍ以下になってきている。このような小径の穴を精度良く形成するために、パルス発振型のレーザビームが用いられている。
従来のパルス発振型レーザを用いたレーザ穴開け機の一般的な構成を図１に示す。本構成例は、図示しないレーザ発振器から照射される、例えばパルス状のレーザ光線２０を、所定の方向（図１では紙面に垂直な方向）に走査するための回転ミラー２３を含む第１ガルバノスキャナ２２と、該第１ガルバノスキャナ２２によって紙面に垂直な方向に走査されたレーザ光線を、該第１ガルバノスキャナ２２による走査方向と垂直な方向（図１では紙面と平行な方向）に走査するための回転ミラー２５を含む第２ガルバノスキャナ２４と、前記第１及び第２ガルバノスキャナ２２、２４により２方向に走査されたレーザ光線を、ＸＹステージ１２上に固定された、基板等の加工対象物（ワークと称する）１０の表面に対して垂直な方向に偏向して照射するためのｆ−θレンズ２６とを備えている。
このように、第１、第２ガルバノスキャナ２２、２４を用いることにより、レーザ光線２０を、スキャナ先端の回転ミラー２３、２５に反射させ、進行方向を任意に変えることができる。ここで、回転ミラー２３、２５は軽量であるため、高速位置決めが可能である。
前記ガルバノスキャナ２２、２４によって偏向したレーザ光線は、ｆ−θレンズ２６を通過して、ワーク１０に集光する。このｆ−θレンズ２６は、一般に高価なものであるために、サイズが限定されてしまい、そのため、あるタイミングにおけるビーム照射範囲（加工エリアと称する）の大きさが数十ｍｍ角程度の長方形に制限されており、一般的なワーク１０の大きさより狭い。
そこで、ＸＹステージ１２によりワーク１０を搬送することにより、広範囲な位置決めを可能としている。但し、ＸＹステージ１２は重量が大きいため、位置決めに費やす時間が大きい。
このようにして、レーザ穴開け機は、高速狭範囲の位置決め装置であるガルバノスキャナ、及び、低速広範囲の位置決め装置であるＸＹステージの２つの位置決め装置を用いることにより、高速広範囲な穴開け位置決めを行っている。
従って、位置決めという観点から、動作形態（制御形態）を、次の２つに大きく分類することができる。
（１）ガルバノスキャナ、ＸＹステージの各単独制御
即ち、ＸＹステージを停止させた状態での加工エリア内のレーザ光走査によるレーザ加工と、ＸＹステージによるワークの搬送とを直列的に行うことにより、基板全体の加工を行う形態であり、通常、ステップアンドリピートと呼ばれる。以下、低速位置決め手段停止加工又はステージ停止加工とも称する。
（２）ガルバノスキャナとＸＹステージの協調制御（同期制御とも称する）
ガルバノスキャナによるレーザ光の走査とＸＹステージによるワークの搬送を並列的に行う形態であり、通常、協調制御又は同期制御と称する。以下、低速位置決め手段非停止加工又はステージ非停止加工とも称する。
前記ステップアンドリピートは、例えば米国特許６０８７６２５、協調制御は、特開平３−２６６００６等に記載されている。
しかしながら、米国特許６０８７６２５は、ステップアンドリピートに関するものであり、本願が対象とする協調制御における加工計画を含むものではなかった。
又、特開平３−２６６００６は、粗動テーブルと微動テーブルを協調制御するものであり、本願が対象とするものとは全く異なる。
発明の開示
本発明は、前記従来の問題点を解消するべくなされたもので、加工を開始する前段階において、ワーク上のレーザ照射位置を狭範囲に移動させることが可能な高速位置決め手段と、広範囲に移動させることが可能な低速位置決め手段の動作を、効率良く計画することを課題とする。
本発明は、ワーク上の加工実行箇所を広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画方法であって、加工位置を、Ｘ又はＹである加工時低速位置決め手段停止方向Ｚの辺長がＤＺ以下であるような矩形により分割する加工矩形分割工程と、加工矩形分割工程により決定された各加工矩形について、矩形内の総加工時間が最小となるように、加工矩形内の加工位置訪問順序及び低速位置決め手段動作速度を決定する加工位置訪問順序及び低速位置決め手段動作速度最適化工程と、前記２つの工程により決定された、加工矩形の位置、加工矩形入出口の低速位置決め手段動作速度のうち少なくとも１つをもとに、低速位置決め手段の動作経路を決定する低速位置決め手段動作経路最適化工程とを含むことにより、前記課題を解決したものである。
又、前記加工矩形分割工程（手段）を、Ｘ方向又はＹ方向の単純な分割によるものとしたものである。
又、前記Ｘ方向又はＹ方向の単純な分割を行った後、加工位置が存在しない加工矩形を除くようにして、低速位置決め手段の動作箇所を加工位置がある所に限定し、加工を高速化して、効率的な協調制御を実現できるようにしたものである。
又、前記分割した加工矩形のうち、低速位置決め手段停止方向Ｚの辺長の中で該方向の所定寸の辺長より小さいものがあれば、分割数を変えずに停止方向の辺長を調整して、停止方向辺長の小さな加工矩形を無くすようにしたものである。
又、前記加工矩形分割工程（手段）を、Ｘ方向又はＹ方向の最少数の分割によるものとしたものである。
又、前記加工矩形分割工程（手段）で、Ｘ方向の分割とＹ方向の分割を両方試行した後、良い方（例えば低速位置決め手段の動作距離の短い方）を採択するようにして、加工を高速化し、効率的な協調制御を実現できるようにしたものである。
又、前記加工矩形分割を行った後、各加工矩形において、低速位置決め手段の動作方向に沿って加工位置が、低速位置決め手段の動作方向の所定寸の加工エリアの辺長と速度変化に要する距離の和以上無い箇所が有れば、該矩形を２分するようにしたものである。
又、前記加工矩形分割を行った後、各加工矩形において、加工位置が低速位置決め手段の動作方向と垂直な方向に対して中央に集まるよう加工矩形の配置を微調整するようにしたものである。
又、前記加工矩形分割工程（手段）で、Ｘ方向の分割とＹ方向の分割を両方試行して加工矩形を確定した後、それらの組合せ（例えば低速位置決め手段の動作距離の短いもの）により、全体を加工矩形分割するようにして、加工を高速化し、効率的な協調制御を実現できるようにしたものである。
又、前記加工矩形分割工程（手段）が、加工位置の分布パターン及び密度を考慮するようにして、加工位置の疎密を考慮した矩形分割により、疎な箇所は疎な箇所で、密な箇所は密な箇所で矩形を特定し、疎な箇所では速い速度、密な箇所では遅い速度で加工を行うことにより、加工を高速化して、効率的な協調制御を実現できるようにしたものである。
又、前記加工位置の分布パターン及び密度を考慮した加工矩形分割工程（手段）が、加工位置が密な箇所を識別して加工矩形の配置を確定する工程（手段）と、加工位置が大多数な箇所を識別して加工矩形の配置を確定する工程（手段）と、未だ加工矩形の確定していない加工位置に対して、加工矩形を確定する工程（手段）とを含むようにしたものである。
又、前記密な箇所及び大多数な箇所の加工矩形の配置を確定する工程（手段）は、ワーク上の加工領域を格子状に分割して、各格子内の前記加工位置の疎密、もしくは有無の真偽を識別する工程（手段）と、識別された格子の配置を基に、複数の格子群矩形を形成する工程（手段）と、各格子群矩形を被覆するように加工矩形を配置する工程（手段）とを含むようにしたものである。
又、前記格子群矩形は、矩形の外周に当る格子列には必ず真と識別された格子が有って、矩形の外周の外側に当る格子列の格子は全て偽と識別された格子であるようにしたものである。
又、加工位置が大多数な箇所を識別して加工矩形の配置を確定する工程（手段）において、データ自体にパターンの繰り返しとして記載されている加工位置の広がりを大多数な箇所として識別するようにしたものである。
又、前記各格子群矩形を被覆するように加工矩形を配置する際に、設定した大きさに満たない格子群矩形は除外して加工矩形配置を決定するようにしたものである。
又、前記各格子群矩形を被覆するように加工矩形を配置する工程（手段）において、格子群矩形の直線状又は格子状の配置を識別して加工矩形配置を決定するようにしたものである。
又、最終的に残った加工位置の存在する箇所が少ない場合は、前記低速位置決め手段を停止させて高速位置決め手段を動作させる低速位置決め手段停止加工を適用するようにして、加工を効率化したものである。
又、前記低速位置決め手段停止加工を、低速位置決め手段非停止加工と同じ制御系で実行できるようにして、設計を容易化したものである。
又、前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程（手段）が、前記高速位置決め手段による移動、位置決め及び加工が可能な加工位置の訪問順序を最適化しつつ、前記低速位置決め手段の等速な速度の最大値を求める、加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）であるようにしたものである。
又、前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程（手段）は、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）の後、更に決定された加工位置に対して、加工位置の分布の密度に応じて動作速度を滑らかに変化させる加減速パターンを決定する速度パターン決定工程を行うようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）において、各加工位置の加工タイミングを最早開始時刻及び最遅完了時刻の間に規定する時間枠を、低速位置決め手段動作速度に基づいて定めるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）において、加工位置間の移動長を、加工位置間の移動量及び低速位置決め手段動作速度に基づいて定めるようにしたものである。
又、前記各加工位置の時間枠を、Ｘ又はＹである所定寸の加工エリアの低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺを用いて、最早開始時刻はＴＳ＋ＰＺ／Ｖで、最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ）／Ｖで定めるようにしたものである。
又、前記各加工位置の時間枠を、Ｘ又はＹである所定寸の加工エリアの低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺ、ＤＺより小さい所定の正又は０である値ＤＺＦ、ＤＺＢを用いて、最早開始時刻はＴＳ＋（ＰＺ＋ＤＺＦ）／Ｖで、最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ−ＤＺＢ）／Ｖで定めるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）において、各加工位置の加工開始時刻を、１つ前の加工位置における加工完了後、加工位置間の移動が完了した時刻が、最早開始時刻より早ければ最早開始時刻に、最早開始時刻以降であれば移動が完了した時刻に定めるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）が、加工位置訪問順序を発生させる加工位置訪問順序発生工程（手段）と、加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程（手段）によるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）が、加工位置訪問順序を発生させる加工位置訪問順序発生工程（手段）と、加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程（手段）と、低速位置決め手段動作速度を固定して加工位置訪問順序を改善する加工位置訪問順序改善工程（手段）と、を全て含むようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）は、加工位置訪問順序を発生させる加工位置訪問順序発生工程（手段）、加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程（手段）、及び、低速位置決め手段動作速度を固定して加工位置訪問順序を改善する加工位置訪問順序改善工程（手段）と該低速位置決め手段動作速度算出工程（手段）とを１乃至複数回繰り返す、繰り返し改善工程（手段）、からなる工程（手段）であるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）が、加工位置訪問順序を発生させる加工位置訪問順序発生工程（手段）と、加工実行可能性の判定を伴わずに加工位置訪問順序改善工程（手段）を繰り返し実行する判定なしの加工位置訪問順序改善工程（手段）と、加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程（手段）とによるようにしたものである。
又、前記加工位置訪問順序発生工程（手段）による加工順序は、前記低速位置決め手段の動作方向に対して、幅を設定して加工矩形の分割を行い、該幅内では、該幅に収まる加工位置を、動作方向と垂直な方向にソートして、ある幅内で昇順ソートであれば、その隣の幅内で降順ソートであるようにすることにより、加工位置の訪問経路が蛇行状となるようにした順序であるようにしたものである。
又、前記低速位置決め手段動作方向に対して幅を設定して帯状の矩形に分割する際の分割幅を、加工矩形内の加工位置の密度に基づいて設定するようにしたものである。
又、前記繰り返し改善工程（手段）は、加工実行不可能な高速側低速位置決め手段動作速度及び可能な低速側動作速度の間の値Ｖについて、まず実行可能かどうかを判定し、実行可能な場合は低速側動作速度をＶで更新し、実行不可能な場合は、Ｖについて加工位置訪問順序改善工程（手段）を繰り返し実行し、実行可能となった場合は低速側動作速度をＶで更新、最後まで実行可能とならない場合は高速側動作速度をＶで更新する処理を、繰り返し回数が設定回数より多くなるまで、又は、高速側動作速度と低速側動作速度の差が設定値より小さくなるまで繰り返す工程（手段）であるようにしたものである。
又、前記繰り返し改善工程（手段）は、加工実行可能な低速位置決め手段動作速度Ｖについて、加工位置訪問順序改善工程（手段）を繰り返し実行し、改善解が無くなった時点で加工実行可能な動作速度を更新する処理を、繰り返し回数が設定回数より多くなるまで、又は、加工位置訪問順序改善工程（手段）の前後で総加工時間が短縮できなくなるまで、又は、加工位置訪問順序改善工程（手段）の前後で低速位置決め手段動作速度の改善量が設定値より小さくなるまで繰り返す工程（手段）であるようにしたものである。
又、前記加工位置訪問順序改善工程（手段）は、時間枠付き非対称ハミルトン路長最小化問題又は時間枠付き対称ハミルトン路長最小化問題の解法を適用するようにしたものである。
又、前記時間枠付き対称又は非対称ハミルトン路長最小化問題の解法として、Ｏｒ−Ｏｐｔ法を用いるようにしたものである。
又、前記加工位置訪問順序改善工程（手段）及び前記低速位置決め手段動作速度算出工程（手段）における加工実行可能性は、全ての加工位置の、加工完了時刻及び最遅完了時刻の差に基づいて判定するようにしたものである。
又、前記加工位置訪問順序改善工程（手段）及び前記低速位置決め手段動作速度算出工程（手段）における加工実行可能性は、全ての加工位置の加工完了時刻が、加工終了の最も遅いタイミングである最遅完了時刻よりも早ければ実行可能、そうでなければ実行不可能と判定するようにしたものである。
又、前記加工位置訪問順序改善工程（手段）における改善解の判定は、加工矩形内で最後に訪問する加工位置の加工完了時刻及び前記加工実行可能性の少なくとも一方に基づくようにしたものである。
又、前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程（手段）が、先ず、矩形内の加工位置訪問順序を決定し、次いで、決定された経路における前記低速位置決め手段の等速動作を最速化するようにしたものである。
又、前記速度パターン決定工程（手段）が、加工矩形内の加工位置の分布が疎な部分における前記低速位置決め手段の動作速度を高速化して、加工を高速化するようにしたものである。
又、前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程（手段）の結果、全ての加工位置における加工完了時刻が前記最遅完了時刻より早ければ、全ての加工位置の加工開始時刻を、全ての加工位置において加工完了時刻が最遅完了時刻より早い範囲で同一時間分遅い時刻方向へシフトするようにしたものである。
又、前記低速位置決め手段動作経路最適化工程（手段）が、加工矩形間を移動する時間の総和を最小化するようにして、加工を高速化したものである。
又、前記低速位置決め手段動作経路最適化工程（手段）が、都市が各加工矩形の入口と出口に対応する位置それぞれであって、矩形の入出口に当る都市間の枝に除去禁止の制約を持つ巡回セールスマン問題もしくはハミルトン路長最小化問題を解くようにしたものである。
又、前記低速位置決め手段動作経路最適化工程（手段）が、加工矩形の訪問順序を最適化した後に、各矩形の入出口を決定するようにしたものである。
又、前記低速位置決め手段動作経路最適化工程（手段）が、各矩形の入出口を決定した後に、矩形の訪問順序を最適化するようにしたものである。
本発明は、ワーク上の加工実行箇所を、広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画方法であって、ワーク全体の加工位置の訪問順序を最適化する全加工位置訪問順序最適化工程（手段）と、該全加工位置訪問順序最適化工程（手段）で決定された加工位置訪問順序に対して低速位置決め手段の動作パターンを決定する低速位置決め手段動作パターン決定工程（手段）と、を含むようにしたものである。
又、前記低速位置決め手段動作パターン決定工程（手段）が、先ず、加工位置を所定寸矩形と同寸の矩形でグループ分けし、次いで、各グループの加工位置に対応する低速位置決め手段制御目標位置を決定するようにしたものである。
又、広範囲に移動させることが可能な低速位置決め手段と、ワーク上の加工実行箇所を、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画方法であって、加工位置を、Ｘ又はＹである加工時低速位置決め手段停止方向Ｚの辺長がＤＺ以下であるような矩形により分割する加工矩形分割工程（手段）と、該加工矩形分割工程（手段）により決定された各加工矩形について、加工位置の訪問順序を最適化する加工位置訪問順序最適化工程（手段）と、該加工位置訪問順序最適化工程（手段）により決定された加工位置訪問順序に対して、前記低速位置決め手段の動作パターンを決定する低速位置決め手段動作パターン決定工程（手段）と、を含むものである。
本発明は、又、前記のいずれかに記載の加工計画方法により決定された加工を行うことを特徴とする加工方法を提供するものである。
又、前記のいずれかに記載の加工計画方法を実施するためのコンピュータプログラムを提供するものである。
又、前記のいずれかに記載の加工計画装置を含む加工装置を提供するものである。
又、前記のいずれかに記載の加工計画装置を実現するためのコンピュータプログラムを提供するものである。
又、前記コンピュータプログラムが記録された、コンピュータ読取り可能な記録媒体を提供するものである。
発明を実施するための最良の形態
以下図面を参照して、ＸＹステージ（低速位置決め手段）とガルバノスキャナ（高速位置決め手段）を備えたレーザ穴開け機により穴を開ける場合に適用した本発明の実施形態を詳細に説明する。
まず、発明の基となる発想を簡単に説明する。
発明者が既に提案した特願２００１−３３１５５０では、ステップアンドリピートによる動作（即ち、低速位置決め手段（ステージ）停止加工）を高速に実現するために、ＸＹステージ（単にステージとも称する）の停止位置、停止位置の訪問順序、及び、ガルバノスキャナの走査軌道等を、加工前に計画するための技術を提案している。
これは、次の３項目に関して最適化を行ったものである。
▲１▼穴開け位置（加工位置）の加工エリア（レーザビームが照射される範囲であれば、形状は矩形に限定されない。）分割（ＸＹステージ動作回数の低減）
▲２▼加工エリア内の穴開け位置訪問順序（スキャナ動作時間の低減）
▲３▼加工エリアの訪問順序（ＸＹステージ動作量の低減）
本発明は、低速位置決め手段停止加工（ここではステージ停止加工）を行うための上記発想を低速位置決め手段非停止加工（ここではステージ非停止加工）に拡張させ、次の４項目に関し最適化するようにしたものである。
（１）穴開け位置の加工矩形分割（ＸＹステージ動作位置の限定）
（２）加工矩形内穴開け位置訪問順序（スキャナ動作時間の低減）
（３）加工矩形通過時のＸＹステージ速度（加減速パターンも含む）（ＸＹステージの待ち時間低減）
（４）加工矩形訪問順序及び加工矩形の出入口（ＸＹステージ動作量の低減）  即ち、ステージ非停止加工のために、ステージ停止加工の▲２▼の最適化が、（２）と（３）の２項目に関する最適化に分かれる形となっている。
ここで、「加工矩形」とは、ＸＹステージが非停止で一方向に直進しながら加工をする際の加工の単位となる領域であって、加工エリアがＸＹステージ動作方向に沿って延ばされた形状（長方形）をしている。
なお、ここでは、低速位置決め手段としてＸＹステージ、高速位置決め手段としてガルバノスキャナを用いた場合を例にとって説明しているが、低速位置決め手段や高速位置決め手段の種類はこれに限定されない。
ステージ非停止加工の（２）の加工矩形内穴開け位置訪問順序に関しては、（３）のＸＹステージ速度の大きさにより、最適な順序が異なってくると考えられる。逆に、（３）のＸＹステージ速度の最大速度は、（２）の加工矩形内穴開け位置訪問順序の良し悪しによって、値が異なってくる。従って、上記４項目のうち、（２）と（３）は密接に関係しているので、独立に最適化するのではなく、一緒に最適化する方が良い。
従って、図２に示すように全体を独立した３つの工程に分ける。
Ａ．穴開け位置の加工矩形分割工程（ステップ１００）
Ｂ．（各加工矩形内の）穴開け位置訪問順序及びＸＹステージ動作速度最適化工程（ステップ１１０）
Ｃ．ＸＹステージ動作経路最適化工程（ステップ１２０）
ステップ１００の穴開け位置の加工矩形分割最適化の概念を図３に示す。本工程は、穴開け位置を、ＸＹステージ進行方向（実際には基板上における加工エリア遷移方向で、ステージは反対方向に動作しているが、図の如く矢印を書く方が判り易いため、ステージ進行方向と書くことにする）と垂直な方向が加工エリアのその方向の辺長以下の長さの、基板の配置方向と平行な矩形（加工矩形）により分割する工程である。
ステップ１１０の各加工矩形内の穴開け位置訪問順序及びＸＹステージ動作速度最適化工程の概念を図４に示す。本工程は、ステップ１００により決定された各加工矩形に関し、加工矩形の加工時間、即ち最後の加工位置の加工（レーザ照射）完了時刻と最初の加工位置の加工開始時刻の差が最小となるように、ＸＹステージの動作速度（一定速度でなくともよい）を最大化しつつ、加工矩形内の穴開け位置訪問順序を最適化する工程である。
即ち、ＸＹステージが等速で動作する場合、加工エリアの大きさの問題で、各穴開け位置に対し、レーザ照射を開始してもよいタイミングと、必ず照射が完了していなければならないタイミングが存在する（時間枠制約と称する）。例えば、ＸＹステージの速度が極めて遅いと、全ての穴開け位置の照射が間に合わないという状況が起こることはないが、加工時間は長くなる。一方、ＸＹステージの速度が速すぎると、ガルバノスキャナの走査による位置決めが間に合わなくなってしまう状況が発生する。
又、ガルバノスキャナの走査は、各走査の走査距離、従って、穴開け位置の訪問順序の良し悪しにより費やす時間が左右される。
以上により、ガルバノスキャナによる走査、位置決め及び照射が可能（以下、加工矩形内の全ての穴開け位置に対し実行可能な照射タイミングが定められることを実行可能と称する）な、穴開け位置の訪問順序、及び、ＸＹステージ最大速度を求める必要がある。
この工程では、穴開け位置の訪問順序、各穴開け位置の照射タイミング、ＸＹステージ速度、加減速度パターン等、決定する必要のある要素が無数にあり、極めて難しい工程であるので、次のような２つの工程に分ける。
Ｂ１．ＸＹステージを等速で動作させる場合の、動作速度が最大となるような加工矩形内の穴開け位置訪問順序を決定する工程（ステップ１１２）。以下、穴開け位置（加工位置）訪問順序最適化並びにＸＹステージ（低速位置決め手段）等速動作速度最大化工程と記す。
Ｂ２．上記決定された穴開け位置に対し、穴開け位置の分布の密度により動作速度を滑らかに変化させるＸＹステージ加減速パターンを決定する工程（ステップ１１４）。
なお、加工精度、基板の穴開け位置のパターン、用いる制御系の設計形態などから、ステージは等速で動作させる方が好適であると判断できる場合は、ステップ１１４はスキップする。
ステップ１２０のＸＹステージ動作経路最適化工程の概念を図５に示す。本工程は、ステップ１００により決定された加工矩形の位置、及び、ステップ１１０により決定された加工矩形入出口のＸＹステージ動作速度を基にして、ＸＹステージの動作経路（加工エリアの加工矩形訪問順序及び各加工矩形上の加工エリア遷移方向）を最適化する工程である。
以下、各工程について詳細に説明する。
前記ステップ１００の穴開け位置の加工矩形分割最適化工程は、穴開け位置を、ＸＹステージ進行方向と垂直な方向が加工エリア幅以下の長さの、基板の配置方向と平行な加工矩形により分割する工程である。
この工程を実施する方法として、次のような５つの方法を考案した。
１．横方向又は縦方向の単純な分割による方法
２．横又は縦の分割であるが、穴の存在しない箇所を除く方法
３．上記１、２に関し、横方向、縦方向を両方試行した後、良い方を採択する方法
４．上記１、２に関し、横方向、縦方向を両方試行して加工矩形を確定した後、それらの加工矩形の組合せにより全体を加工矩形分割する方法
５．同一パターン及び密度を考慮した、より効率的な加工矩形分割方法
以下、それぞれの方法について、具体的に説明する。
１．横方向又は縦方向の単純な分割による方法
図６のように、ＸＹステージの進行方向をＸ方向（横方向）若しくはＹ方向（縦方向）に先決めしておき（図は横方向）、ステージ動作方向（Ｘ方向）と垂直な方向（Ｙ方向）の加工矩形の一辺の大きさは、加工エリアの大きさ以下の値に採り、ステージ進行方向（Ｘ方向）の一辺の大きさは、穴開け位置の最大値から最小値を引いた値に採り、基板の端から順に隙間無く加工矩形を配置する方法である。
必ずしも最適な分割ではないが、実際には図７に示す如く、基板の穴開け位置は万遍無く全体に広がっていることが多いので、最適化を試みてもよい解は得られないこともあるため、本方法も有効な手法である。
状況により、次のような工夫を加えることができる。
ａ．穴開け位置の存在しない加工矩形への対処方法
横方向又は縦方向の単純な分割の場合、穴開け位置の全くない加工矩形が生じる場合がある。そのような加工矩形は不要なため、取り除く処理を行う。
ｂ．ＸＹステージ進行方向と垂直な方向の一辺の大きさの設定方法
ＸＹステージを横（Ｘ）方向に動かす場合を想定する。即ち、ＸＹステージ進行方向を横（Ｘ）とし、ＸＹステージ進行方向と垂直な方向（停止方向）を縦（Ｙ）とする。加工エリアの大きさを加工時進行方向はＤＭ、加工時停止方向はＤＳとし、基板の縦（Ｙ）幅（穴開け位置のＹ座標の最大、最小の差）をＴとする。この手法では、加工矩形の枚数は［（Ｔ−α）／ＤＳ］＋１となる。ここで、［Ａ］は、その数Ａを越えない最大の整数を表わすガウス記号であり、αはＴ、ＤＳと比べて十分に小さく、零に近い正値を指すこととする（αは、Ｔ／ＤＳがちょうど割り切れた場合の対処法である）。例えば、Ｔ＝４６０ｍｍ、ＤＳ＝５０ｍｍの場合、加工矩形の枚数は１０枚であり、Ｔ＝４００ｍｍ、ＤＳ＝４０ｍｍの場合には、α＝０．００１ｍｍとし、やはり１０枚である。
ここで、加工矩形の停止方向の長さと加工エリアの大きさＤＳは、同じである必要はなく、加工矩形の一辺が加工エリアの大きさと同じか若しくは小さい値であればよい。そこで、基板の縦の長さＴを加工矩形の枚数［（Ｔ−α）／ＤＳ］＋１で割った値を、各加工矩形の縦の長さとする。この手法により、例えばＴ＝４６０ｍｍ、Ｄ＝５０ｍｍの基板においては、４６０／１０＝４６ｍｍ毎に区切ることにより、５０ｍｍ毎に区切った場合に最後に１０ｍｍ幅の加工矩形が余ってしまうというような現象が無くなる。機械的な制約または高精度な加工を実現するために、通常ＸＹステージ動作速度の限界が存在するので、幅の狭い加工矩形の加工において、著しくＸＹステージ動作速度が限界速度に近い状態を回避したいが、本手法により、加工矩形の幅が均一化されるので、この点が回避できる。
ｃ．穴開け位置の無い箇所の削除と加工矩形分割
図８（Ａ）に示す例では、加工矩形内において、例えば左から右に向かって穴開け位置を順に辿っていくと、穴開け位置が全く無い箇所が存在する。このような箇所は、ステージを非停止で動作させても無駄なので、図８（Ｂ）に示す如く、加工矩形を分割したい。加工矩形を分割する基準は、例えば次のようにすることができる。
イ．加工矩形の左端又は右端に点が無い場合。
ロ．加工矩形を右方向へ穴開け位置を順に辿っていくとき、「加工エリアの幅ＤＭ＋速度変更に要する距離α」以上の点の無い箇所が存在するとき。
ここで、分割の基準をＤＭ＋α以上の点が無い箇所とする理由は、次のとおりである。即ち、図９（Ａ）に示す如く、穴開け位置の塊が２分されている場合、加工矩形を左右２つの加工矩形に分割できるか否かを調べる。
左の加工矩形の加工終了位置と右の加工矩形の加工開始位置に関して、左の加工矩形の加工終了位置が、右の加工矩形の加工開始位置よりも左に位置する必要があるが、それぞれの位置は、図９（Ｂ）のように、加工矩形の左右に隣接した加工エリアを書いた時の中心位置であるから、最低でも進行方向に並ぶ加工矩形間隔はＤＭ以上あることが必要となる。
更に、左の加工矩形の加工終了位置から、右の加工矩形の加工開始位置へ移る際に、図９（Ｃ）に示す如く、加工矩形内の動作速度を変更する必要がある。従って、いくらかの動作距離αが必要となる（αの値は、用いるステージの特徴により、適切に定める）。
以上を加えて、加工矩形間の間隔は、最低ＤＭ＋α以上必要である。
ｄ．加工矩形位置の微調整方法
加工矩形の進行方向に垂直な方向（ここではＹ方向とする）の配置は、穴開け位置が加工矩形の中央に集まるように上下にずらすことができる。即ち、ある加工矩形に、穴開け位置集合Ｐ＝｛ｐｉ，ｐｉ＋１，…，ｐｊ｝（ｉ≦ｊ）が存在するように矩形分割された場合に、Ｐに属する点のＹ座標値の拡がりの中心（最大値、最小値の平均）を加工矩形の縦方向の中央位置とすることにより、Ｙ方向のガルバノスキャナの動きを中央に集めることが可能となる。あるいは、拡がりの中心ではなく、重心（重心が上若しくは下に偏っている場合は、全ての点が加工矩形から出ない限界位置）を中心とすることもできる。
２．横又は縦の分割であるが、穴の存在しない箇所を除く方法
図１０に示す如く、穴の無い箇所を除いて加工矩形分割する。具体的には、ＸＹステージを横方向に動かす場合を想定すると、この方法では、加工矩形の位置が図１１（Ａ）のような段違いになる配置ではなく、図１１（Ｂ）のように、綺麗に揃っている配置となるようにしたい。そこで、穴開け位置のＹ座標情報のみを用いて、加工矩形の配置を決定する。
具体的には、下記（Ｘ）のような問題（ＳＰＬＩＴと呼ぶこととする）を定義し、下記（Ｙ）のようにＳＰＬＩＴの解法を用いて問題を処理する。
問題（Ｘ）（ＳＰＬＩＴ）：
昇順ソートされたｎ個の数値データの集合、Ａ＝｛ａ１，ａ２，…，ａｎ｝を、最少個数の互いに素な部分集合（互いに素な２つの集合とは集合の要素に同一のものが無いことを指す）Ｂ１，Ｂ２，…，Ｂｍに分割（分割とは、ｉ≠ｊなる任意のｉ、ｊに対し、Ｂｉ∩Ｂｊ＝φ（空集合）が成
2003064107.tif 000003
ートされており、Ｂｋの末尾の要素はＢｋ＋１の先頭の要素より必ず小さく、各部分集合Ｂｋ＝｛ａｓ，…，ａＧ｝は、先頭、末尾の要素に関し｜ａＧ−ａＳ｜＜＝ＤＳを満たす（ＤＳは走査エリアの大きさを表す固定値）。
処理（Ｙ）：
▲１▼基板全体の穴開け位置のＹ座標値（縦軸を分割する場合。横軸を分割する場合はＸ座標値）の重複しないもののみを取り出しソートし、集合Ａの要素とする（Ａ＝｛ａ１，…，ａｎ｝，ａｉ＜ａｉ＋１）。
▲２▼Ａを問題ＳＰＬＩＴの入力と見做し、部分集合Ｂ１…，Ｂｍを得る。
▲３▼各部分集合Ｂ１…，Ｂｍをもとに、穴開け位置をｍ個のグループに分割する。
ＳＰＬＩＴの解法としては、具体的には、問題をグラフの各辺に重みが付加されている時のネットワーク最適化問題の１つである、与えられた節点から全ての節点への最短路を求める最短路問題として捉えて、公知の解法を適用する。全体としては図１２に示すように処理する。
即ち、まずステップ２００で、図１３（Ａ）に示す如く、穴開け位置のＹ座標値の重複しないもののみを取り出しソートし、集合Ａ＝｛ａ１，ａ２，…，ａｎ｝の要素とする（ここでソートとは、１≦ｉ≦ｎ−１なるｉに対しａｉ＜ａｉ＋１となるように並び換えることを指す）。更に、図１３（Ｂ）に示す如く、節点集合Ｖ＝｛ｖ１，ｖ２…ｖｎ｝と置き、Ｖの要素ｖｉは、値としてａｉに対応付けられているものとする。
又、２節点（ｖｉ，ｖｊ）（ｉ＜ｊ）は、下記の場合に隣接しているものとする。
ａｉ＋Ｄ≧ａｊ、
若しくは、
ａｉ＋Ｄ≧ａｊ−１  且つ  ａｉ＋Ｄ＜ａｊ
即ち、ｖｉに隣接するｖｊとは、ｖｉに対応する値ａｉをある加工矩形ＳＱ１の下辺のＹ座標としたときに、ｖｊに対応する値ａｊが下辺のＹ座標であるような加工矩形が、基板におけるＳＱ１に隣り合う加工矩形となり得るものとする。
更に、隣接している２節点（ｖｉ，ｖｊ）（ｉ＜ｊ）対の重みは、全て１とする（重みとは、２点間の枝の長さ（コスト）を指す）。
又、始点をｖ１（Ｙ座標最小の点）、終点候補集合をＶｅ＝｛ｖｋ，…ｖｎ｝（但しｋは、ｋ＝１から昇順に調べてａｋ＋Ｄ≧ａｎとなる最初のものを指す、つまり、終点候補集合の要素を下辺位置とする加工矩形は最大値ａｎをＹ座標に持つ点を含んでいる）とする。
以上により、ステップ２０２で、ｖ１を始点とする有向ネットワークを得ることができる。
得られたネットワークに対し、ステップ２０４で、例えばダイクストラの方法のような、よく知られた手法を用いて、最短路問題を解く。すると、図１３（Ｂ）に示す如く、始点から各節点への最短経路と最短路長が求まる。
なお、ダイクストラの方法などは、真に最短な経路（ここでは、最少の加工矩形）を得ることができる手法である。
次いで、ステップ２０６で、終点候補集合の各節点のうち、最短路長が最小の値を示す節点を選択する。
次いで、ステップ２０８で、その節点への最短経路上の節点に対応する値を下辺のＹ座標値とする加工矩形で分割していけば、図１４（Ｃ）に示す如く、求めたい加工矩形分割が得られている。ここで、最短路長は、（加工矩形数−１）となっている。
又、上記加工矩形縦位置の設定方法は、加工矩形の枚数を最少化することを目的としているが、加工矩形の枚数が同一でも、図１５（Ａ）に示すように、加工矩形被覆により穴開け位置が両端（図の上下）に分断されてしまうことがある。従って、最少な加工矩形枚数である解の中から、最も穴開け位置の分断が無い解を選択するのが望ましい。これを実現するためには、加工矩形枚数が最少である解全てに対して、上記分断のギャップ値が規定値より大きい箇所が加工矩形内にある場合、そのギャップ値を加算していき、ギャップ値の総和が最小となるものを選べばよい。
あるいは別の実現方法として、加工矩形間のギャップ値、即ち加工矩形の最終要素と１段上の加工矩形の最初の要素間のギャップ値を加算していき、ギャップ値の総和が最大となるものを選んでもよい。
なお、本手法においても、前述１のｃ及びｄの様な各加工矩形に対する工夫を加えることは可能である。
上記１、２の方法による加工矩形分割に関しては、図２におけるステップ１２０の加工矩形動作経路最適化処理は簡単である。即ち、加工矩形は段揃いの配置となっているため、ＸＹステージ進行方向が横向きである場合、基板内の縦位置下方に有る加工矩形から順に、ＸＹステージの動作経路（既に説明したとおり、正確には加工エリア遷移経路）が基板下方から上方に向かって蛇行状になるような経路とすれば良い。この場合の全体の処理は、図１６に示す如くとなる。
即ち、ステップ２２０において、１又は２の方法による段の揃った矩形分割を行う。
次いでステップ２２２において、ＸＹステージの動作経路を基板下方から上方に向かって蛇行状になるように決定する。
次いでステップ２２４において、各加工矩形の穴開け位置訪問順序最適化及びＸＹステージ動作速度最大化を行う。
なお、ステップ２２２と２２４は、逆の順序でも構わない。
３．上記１、２に関し、横方向と縦方向を両方試行した後、良い方を選択する方法
この方法においては、図１７に示すように、横方向及び縦方向の両方の加工矩形分割を試行してみて、それぞれの動作距離を求め、動作距離の小さい方を選択する。図１７では、横方向に分割する場合の加工矩形分割の方が動作距離は短いので、横方向の加工矩形分割を選択している。
ここでは、動作距離の小さい方を選択しているが、選択の基準は、例えば穴開け位置の疎密を考慮する方法でもよい。即ち、図１８（Ｃ）に示す如く、加工矩形内において、穴開け位置が疎な箇所と密な箇所が混在する場合、密な箇所ではＸＹステージ動作速度を遅くする必要があり、たとえステージ動作速度を同一加工矩形内で可変にすることができるとしても、どうしても、密な箇所の速度の影響を受けてしまうため、ＸＹステージ動作速度パターン決定が困難となる。
このような状況を回避するために、加工矩形分割をする段階において、穴開け位置が疎な箇所はまとめて１つの加工矩形とし、密な箇所は別にまとめて１つの加工矩形とするのが望ましい。そこで、具体的には、例えば図１９に示すような方法により、加工矩形の疎密の均一度を評価し、縦横良い方を選択する。
即ち、まずステップ３００で、ＸＹステージ進行方向に沿って、累積頻度グラフを作成する。ここで言う累積頻度グラフとは、図２０（Ｃ）に示す如く、横軸は加工矩形の端からのＸＹステージ進行方向への距離、縦軸はＸＹステージ進行方向に沿って穴開け位置を調べ、その加工矩形内の穴数に対して何％出てきているかを表わすパーセンテージとしたグラフを指す。
この累積頻度グラフは、図２０（Ｃ）に示した如く、単調増加となるが、疎密が一様である程、直線状の単調増加となる。従って、直線からどれだけ離れているかにより、疎密の一様性を評価することができる。
よって、ステップ３００で、各加工矩形に対して累積頻度グラフを作成し、ステップ３０２で、それらの平均である累積頻度グラフを求める。
次いでステップ３０４で、直線状の増加からのずれ値を、例えば面積等で評価する。そして、ステップ３０６で、該評価値を縦横両方求め、良い方を選択する。
なお、上記のように、ずれを面積で評価するのではなく、最大ずれの大小で評価するなど、疎密の状況が浮き彫りになる他の手法を用いることも可能である。
あるいは、図１６の処理をＸ及びＹの両方向の分割について行い、ステップ２２４において計算される各加工矩形の加工時間に基づいて、加工時間の総和の小さい方を選択することも可能である。
４．上記１、２に関し、横方向と縦方向を両方試行して加工矩形を確定した後、それらの加工矩形の組合せにより全体を加工矩形分割する方法
この方法においては、図２１に示すように、横方向優先と縦方向優先の両方の加工矩形分割を試行してみて、それぞれの加工矩形が確定した後、それらの中から動作距離が最小となるように両方向の加工矩形の組合せを選択する。
図２１では、左下の部分のみが縦方向への加工矩形分割の方が動作距離が短いので、この部分のみは縦方向に長い加工矩形とし、その他の部分は横方向に長い加工矩形を選択している。
なお、評価の基準を動作距離最小とするのではなく、前述したように密度の一様性で評価してもよい。
又、評価の基準を動作距離最小とするのではなく、前述したように各加工矩形の加工時間の総和で評価してもよい。
５．同一パターン及び分布密度を考慮した、より効率的な加工矩形分割方法
この方法では、分割された加工矩形内の穴開け位置が、ＸＹステージを動作させつつガルバノスキャナによる位置決めを行う場合に不利になるような場合を低減し、より効率的な加工矩形分割を得る。
分割矩形内の穴開け位置の位置が効率的ではない場合としては、図１５（Ａ）に示したように、穴開け位置が上下に２分される場合と、図１５（Ｂ）に示したように、穴開け位置の密度が一定でなく、疎な箇所と密な箇所が混在している場合がある。
即ち、図１５（Ａ）に示す如く、ＸＹステージ進行方向が横向きである場合に、穴開け位置が加工矩形上辺付近及び下辺付近に二極化しており、加工矩形中央付近に無いような場合には、ガルバノスキャナの動作量が縦方向に多いため、加工速度が上がらない。
又、図１５（Ｂ）に示すように、穴開け位置の分布密度が一定でなく、ＸＹステージ進行方向に対し、疎、密、疎、密…と変化が激しい場合には、疎な箇所におけるＸＹステージの動作速度が、密な箇所における動作速度の制約を受け、好適な速度パターンを決定することが困難である。
従って、上記のような穴開け位置の二極化や密度不均一状態は、回避することが望ましい。
又、図２２に見られるように、穴開け位置の分布は、同一若しくは似た形状（同一データの反転等）の穴開け位置群（パターン形状と称する）１１Ａが複数個、及び、それ以外の若干の残った点１１Ｂという分布の仕方をしていることが多い。
加工矩形分割を困難としている理由の１つは、上記若干数の残った点１１Ｂが存在しているためであるが、このような場合、難解な状態のまま加工矩形分割を直接行うのではなく、まず、パターン形状１１Ａを見分け、次にその大多数のパターン形状１１Ａに関して比較的容易に加工矩形分割を行い、その後に、若干数の穴開け位置１１Ｂに対し、加工矩形分割を行う方が、簡単に対処できるばかりでなく、効率的な加工矩形分割となっていることが多い。
以下、図２３を参照して、穴開け位置の加工矩形分割の手順を説明する。
まず、ステップ４００で、ＧＵＩ操作などで予め指示された内容に従って、疎密の分別を行うかどうかを判定する。
判定結果が正である場合には、ステップ４０２に進み、最も疎なグループ以外の穴開け位置に対し、効率的に加工矩形を確定できるものは確定する。
次いでステップ４０４に進み、ＧＵＩ操作などで予め指示された内容に従って、穴位置の大多数／少数分布の分別を行うかどうかを判定する。
判定結果が正である場合は、ステップ４０６に進み、大多数グループの穴開け位置に対し、効率的に加工矩形を確定できるものは確定する。
最後にステップ４０８に進み、未だ加工矩形の確定していない穴開け位置に対し、加工矩形を確定する。
なお、ステップ４０８は、既に述べた、１〜４の加工矩形分割方法のいずれかを用いる。
前出ステップ４０２及びステップ４０６は、図２４（ステップ４０２）及び図２５（ステップ４０６）に示す如く、似た工程を持つ。即ち、
（１）格子分割及び格子識別（ビット割当て）工程（ステップ４１０、４１１）、
（２）格子群矩形化工程（ステップ４１４、４１５）、
（３）格子群矩形位置の微調整工程（ステップ４１８、４１９）、及び
（４）格子群矩形の加工矩形による被覆（加工矩形の配置）工程（ステップ４２０、４２１）
を共にこの順序で持つ。
各工程を大まかに述べる。ステップ４１０、４１１の（１）格子分割及び格子識別（ビット割当て）工程は、基板上の加工領域（即ち、穴開け位置の広がる領域）を格子状に分割し、各格子（以下では、大きさの揃った基板に平行な矩形と言う意味で単に格子と称する）内の加工位置の疎密、あるいは有無を、０又は１（ビット）で識別する工程である（値が１の格子を真と識別された格子、０の格子を偽と識別された格子と称する）。
ステップ４１４、４１５の（２）格子群矩形化工程は、図２６に示すが如く、１を割り当てられた格子を、次のような条件の矩形（格子群矩形と称する）でグループ化する工程である。
イ．矩形の外周にあたる格子列（上下左右４つ）には、必ず１（点有り）が存在する。
ロ．矩形の外周を囲む格子列（上下左右４つ）は、全て０（点無し）である。
又、ステップ４１８、４１９の（３）格子群矩形位置の微調整工程は、（２）格子群矩形化工程では、ＸＹ方向に幅を持つ格子で分けられているため、例えば穴の有無が実際に分かれる点が、定かではないので、より正確に格子群矩形の配置を調整する工程である。
ステップ４２０、４２１の（４）格子群矩形の加工矩形による被覆工程は、得られた格子群矩形が
ハ．直線状配置
ニ．格子状配置
である場合に、加工矩形を確定する工程である。
又、ステップ４１６にて、各格子群矩形の大きさを調べ、もし大きな格子群矩形が無い場合には、ステップ４１９及び４２１は行わないようにする。なお、図２５に示すとおり、ステップ４１９及び４２１は、大きな格子群矩形のみについて行う工程である。
以下に詳細に説明する。
前出ステップ４１０における格子分割及び密格子の識別は、具体的には、図２７に示すような手順で、図２８に示すように行う。
即ち、まず、ステップ５００で基板を格子状に分割し、各格子内の穴数をカウントする。次いで、ステップ５０４で、穴数の度数分布を作成し、度数が著しく異なっている箇所があるかどうかを調べる。
なお、格子状の分割に際しては、元の基板を１つの格子と見て、その格子を縦横２分すれば４つの格子ができるが、このような分割を繰り返すことにより、細分することができる。
即ち、ステップ５００で細分割を反復する毎に、ステップ５０２で格子内穴数をカウントし、ステップ５０４で、「穴数＊以上＊未満の格子が＊個」という要領の度数分布を作成して、ステップ５０６で、該度数分布における最大度数が、ある設定値よりも小さくなるまで反復する。
次いで、ステップ５０８で、密格子に１、疎格子に０を割り振る。
図２９は、基板を格子分割し、穴開け位置の度数をカウントした場合に、密である箇所１１Ｃ又は１１Ｄのみをクロスハッチングした図である。なお、図２９に丸で囲った密な箇所１１Ｄは、図２５のステップ４１６において面積の狭い格子群矩形に属する格子と判断され、加工矩形の決定を、図２３のステップ４０８に後残しにされる格子の例である。
又、前出ステップ４１１における格子分割及び穴有り格子の識別は、具体的には、図３０に示すような手順で、図３１に示すように行うことができる。
即ち、まず、ステップ６０６で、基板を適当な大きさの格子で分割する。次いで、ステップ６１０で、図２６に示した如く、１つでも点のある格子には、１を割り振り、全く無い格子には、０を割り振る。
前出ステップ４１４、４１５における格子群矩形化は、具体的には、図３２に示すような手順で行われる。
即ち、まずステップ６２２で、未だ格子群矩形が確定していない、１を割り振られた格子を任意に選択し、その格子自体を暫定的に１つの格子群矩形とする。
選択された現在の格子群矩形の外周（上下左右）の外側に当たる格子行又は列（矩形の４隅に当たる格子は含まない）それぞれに関し、ステップ６２４で１の格子があると判定されれば、ステップ６２６で、格子群矩形の面積をその方向に拡大する。ステップ６２４で上下左右とも無ければ、ステップ６２８で格子群矩形確定とし、ステップ６３０で１を割り振られた格子が有ると判断された場合には、ステップ６２２に戻り、再びステップ６２２からの処理を続け、無いと判断された場合には処理を終了する。
前出ステップ４１８、４１９における格子群矩形位置の微調整は、具体的には、それぞれ図３３、図３４に示すような手順で行われる。
即ち、まず、それら矩形の、実際の正確な穴開け位置の拡がりを調べるため、全ての矩形に関し、外周にあたる格子列（上下左右）に関し、最も外側にある穴開け位置を調べる。
即ち、大パターン格子群矩形位置の微調整であるステップ４１９を詳細に示す図３４の場合、
左の格子列の穴開け位置のＸ座標最小値（ステップ６４４）、
右の格子列の穴開け位置のＸ座標最大値（ステップ６５０）、
下の格子列の穴開け位置のＹ座標最小値（ステップ６５６）、
上の格子列の穴開け位置のＹ座標最大値（ステップ６６２）、
を求めると、実際の正確な穴開け位置の拡がりが求まる。これら正確な最大、最小値により穴開け位置の存在を示す矩形の座標情報を更新すれば、規則正しい配列の識別が可能となる。既に述べたが、元のデータファイル自体にパターン情報があるような場合には、上記のような処理をする必要はない。
なお、密格子群矩形位置微調整であるステップ４１８を詳細に示す図３３の場合には、疎と判定され０を割り振られた、格子群矩形外周の外側に当る格子列にも穴がある可能性がある。
そこで、ステップ６４０、６４６、６５２、６５８にて格子群矩形外周の外側に当る格子列に穴があるかどうかを調べ、ある場合には外周外側格子列の最大値又は最小値（ステップ６４２、６４８、６５４、６６０）を、無い場合には外周に当る格子列の最大値又は最小値（ステップ６４４、６５０、６５６、６６２）を求めるようにする。
又、前出ステップ４２０、４２１における密又は大きな格子群矩形の加工矩形による被覆（即ち、加工矩形の配置）は、図３５に示すような手順で行われる）。
ここでは、格子群矩形の集合から規則正しい配列を識別し、それら規則的矩形集合を被覆する。
ここで言う規則正しい配列とは、図３６（Ｂ）に示す如く、矩形が直線状に配置されている関係、又は、ＸＹ方向共に直線状に配置された、格子的関係を指す。そこで、次のような処理を行なう。
まず、ステップ６７０でＸ方向、Ｙ方向の直線状の配置を調べる際には、Ｘ方向、Ｙ方向それぞれに関して座標のソートを行い、値が同じものをグループ化する。図３６の例では、Ｘ１｛Ｂ５、Ｂ１０｝、Ｘ２｛Ｂ６、Ｂ１１｝、Ｘ３｛Ｂ７、Ｂ１２｝がＸ方向に、Ｙ１｛Ｂ１，Ｂ２，Ｂ３，Ｂ４｝、Ｙ２｛Ｂ５，Ｂ６，Ｂ７｝、Ｙ３｛Ｂ１０，Ｂ１１，Ｂ１２｝が、Ｙ方向に直線状に配置している。
次に直線状配置がＸ、Ｙ共に複数あった場合には、それらの組み合せで格子状配置が作れるかどうか調べる。即ち、ステップ６７６において、上記グループ化された矩形に関し、Ｘ方向の複数のグループの要素とＹ方向の複数のグループの要素とが一致するような組合せを調べる。この例では、Ｘ方向の３グループＸ１｛Ｂ５，Ｂ１０｝、Ｘ２｛Ｂ６，Ｂ１１｝、Ｘ３｛Ｂ７，Ｂ１２｝と、Ｙ方向の２グループＹ２｛Ｂ５，Ｂ６，Ｂ７｝、Ｙ３｛Ｂ１０，Ｂ１１，Ｂ１２｝とが要素が一致している。このような一致する組み合せを見つけるための実際の方法としては、次のようにする。即ちまず、Ｘ方向のグループを順次選択し（最初はＸ１｛Ｂ５，Ｂ１０｝）、Ｙ方向の中に同じ要素のあるグループがあるかどうかを調べる（Ｂ５に対しＹ２｛Ｂ５，Ｂ６，Ｂ７｝、Ｂ１０に対しＹ３｛Ｂ１０，Ｂ１１，Ｂ１２｝がある）。ある場合は、新しく出てきた要素｛Ｂ６，Ｂ７，Ｂ１１，Ｂ１２｝が、Ｘ方向のＸ１以外のグループＸ２、Ｘ３にあるかどうかを調べればよい。以上の操作で、完全に一致すれば、格子状の配置となっている。
以上により、直線状配置がＹ１｛Ｂ１，Ｂ２，Ｂ３，Ｂ４｝、格子状配置がＸＹ１｛Ｂ５，Ｂ６，Ｂ７，Ｂ１０，Ｂ１１，Ｂ１２｝と求められる。
このようにして求まった格子状位置がある場合にはステップ６８０で、直線状配置がある場合にはステップ６８０より後のステップであるステップ６７４にて、規則的に配置された格子群矩形を被覆するように加工矩形を配置する。
直線状配置の矩形群を被覆する際には、図３６に示す如く、次の点に注意する。
イ．基本的には、図３７（Ａ）に示す如く、直線の延びる方向に従って加工矩形配置を定める。
ロ．図３７（Ｂ）に示す如く、格子群矩形の配置間隔（矩形の最も近い位置の間の距離）が、前記「１．横方向又は縦方向の単純な分割による方法」で記述した（加工エリアの大きさＤＭ＋速度変更に関する距離α）よりも大きければ、複数の加工矩形を配置する。
ハ．図３７（Ｃ）に示す如く、直線方向と垂直な方向の幅が加工エリアの大きさＤＳより広く、１つの加工矩形で被覆できない場合は、２つ以上の加工矩形を配置する。
ニ．図３７（Ｄ）に示す如く、複数の加工矩形を配置する場合で単純に配置すると、穴開け位置が端に２分されるような場合には、被覆加工矩形の中心位置をうまく設定する。具体的には、端から順に加工エリアの幅で被覆するのではなく、穴開け位置の無いギャップの部分を避けるようにして、穴開け位置の有る部分の中心を配置すべき加工矩形の中心と重ね合わせる。
一方、格子状配置の矩形群を被覆する際には、図３８に示す如く、次の点に注意する。
直線状配置の場合と同様、図３８（Ａ）に示す如く、配置間隔がＤ＋αより大きい場合には、矩形群をＸ方向、Ｙ方向共に分割する。この結果、格子状に並んだ格子群矩形は間隔がＤ＋α以下のもののみとなる。図３８（Ｂ）に示すように、それぞれの格子状配置を複数のＸ又はＹ方向の同一の方向の矩形で被覆する。
Ｘ方向、Ｙ方向のいずれを選択するかは、例えば次のような評価基準により決定する。
イ．ＸＹステージの据付（上段、下段）により、上段ステージになった方向。
ロ．矩形枚数が少なくて済む方。
ハ．動作距離（分割矩形の進行方向の辺）の総和が小さい方（図３８（Ｂ）ではＬｘとＬｙの総和比較）、若しくは、分割矩形内の点の存在する矩形同士の間の距離の総和が小さい方（ｄｘとｄｙの総和比較）。
ニ．ガルバノスキャナとＸＹステージの動作をモデル化しておき、適切な動作時間の簡易的なシミュレーションによる選択。
又、図３８（Ｃ）の如く、単純に加工矩形を配置すると、穴開け位置が端に２分されてしまうような加工矩形ができてしまう場合は、穴開け位置の無い部分を避けるようにして、穴開け位置の有る部分の中心を配置すべき加工矩形の中心と重ね合わせる。
前出ステップ４２１における良い矩形で被覆できなかったもの（図３６ではＢ８，Ｂ９，Ｂ１３）に関しては、ここでは矩形を確定せずに、次の図２３のステップ４０８にて最終的に残った穴開け位置の加工矩形配置にて処理する。
最終的に残った穴開け位置が少ない場合は、ステージ停止加工による動作を用いることもできる。即ち、図２２に見られる基板の例では、丸で囲った部分１１Ｂが少数グループである。このような箇所が基板内に万遍なく配置されている場合には、少数グループそれぞれは停止箇所へＸＹステージを動作、整定させ、整定後照射を行なう方が加工時間の点で効率的である可能性がある。
なお、ステージ停止加工は、加工中は速度０、加工エリア間を移動するときは、例えば最大速度に近い高速な一定速度という速度パターンと見なし、ステージ非停止加工の一部として、同じ制御形態でステージ停止加工による加工を実施することが可能である。
図２のステップ１１２の穴開け位置訪問順序最適化並びにＸＹステージ等速動作速度最大化工程は、主に次の３つの基本となる工程を組み合せた処理である。
Ａ．穴開け位置訪問順序発生工程
Ｂ．ステージ動作速度算出工程
Ｃ．穴開け位置訪問順序改善工程
工程Ａ（穴開け位置訪問順序発生工程）は、ＸＹステージを直線状に動かしつつ加工を行ない得るような穴開け位置訪問順序（加工の順序）を、暫定的に１つ定める工程である。本工程は本文以下又は図面において、プログラム上の関数名のように、ｉｎｉｔｉａｌ＿ｓｅｑｕｅｎｃｅ（）と書く。
又、工程Ｂ（ステージ動作速度算出工程）は、ある穴開け位置訪問順序に対して、ＸＹステージを等速動作させつつ加工可能であるような、ステージ動作速度の最大値を求める工程である。本工程は本文以下又は図面において、ｆｉｎｄ＿ｓｐｅｅｄ（）と書く。
又、工程Ｃ（穴開け位置訪問順序改善工程）は、ステージ動作速度をある値に固定して、加工矩形内の（ガルバノスキャナ走査、整定など全てを含めた）総加工時間が短縮されるように、より良い穴開け位置訪問順序を探索し改善する工程である。本工程を可能な限り連続して繰り返し用いる処理＜Ｃ＞（ここでの記号＜＊＞は、処理＊を可能な限り連続して繰り返し用いる場合の記号とした）は、本文以下又は図面において、ｏｐｔ（）と書く。
上記３工程を組み合わせて、最も単純には、図３９に示すように工程Ａ、Ｂのみにより本工程を行なうことができる。
又は、図４０のように、工程Ａ、Ｂ、＜Ｃ＞、Ｂの順に行なうこともできる。
更により好ましくは、図４１に示す如く、工程Ａ、Ｂ、＜＜Ｃ＞、Ｂ＞と行なうこともできる。即ち、工程Ａ、Ｂに続いて、可能な限り、『繰り返し穴開け位置訪問順序の改善、及び、ステージ最大速度算出』を繰り返す。
更に、後述するが、図４２に示す如く、工程Ａ、Ｂ、＜｛Ｃ、Ｂ｝＞と行なうこともできる（ここでの記号｛＊、＊＊｝は、＊あるいは＊＊のいずれかを表わす記号とした）。即ち、工程Ａ、Ｂに続いて、可能な限り、『穴開け位置訪問順序の改善、及び、ステージ最大速度算出のどちらか』を繰り返す。
又は、若干赴きが異なるが、図４３に示すように、工程Ａ、＜Ｃ´＞、Ｂとすることもできる。ここで工程Ｃ´は、工程Ｃがステージ動作速度がある値に固定されているのに対して、ステージ動作速度が０の場合の最適化であり、従って、後述する実行可能性判定処理（ｆｅａｓｉｂｉｌｉｔｙ（））を伴わないものである。具体的には、巡回セールスマン問題の解法を上手く適用する（実際には、ハミルトン路長最小化問題の局所探索法による解法である）。即ち、例えばＬｉｎ−Ｋｅｒｎｉｇｈａｎ法などの巡回セールスマン問題の手法を用いる際に、始点と終点を結ぶ枝は切断してはならないという制約を加えて問題を解く手法である。即ち、図４３を少し具体的にすると、図４４に示す如く、初期経路を発生し、経路の始点と終点を結ぶ枝は切断してはならないという制約付き巡回セールスマン問題を解き、その後にＸＹステージ速度を求めるといった処理を行うことが出来る。
以下に、上記工程Ａ、Ｂ、Ｃについて詳しく説明する。なお、以下の説明においては、穴開け位置を単に点と記す場合もある（もちろん説明上、何ら問題はない）。
工程Ａ（穴開け位置訪問順序発生工程）は、ＸＹステージが等速に動作する場合の発想として、図４５に示すように行なう。即ち、ＸＹステージ動作方向に対して、加工エリアのサイズ以下の幅ｈを設定して短冊状の分割を行ない、その幅ｈについて、該幅ｈに収まる穴開け位置を、動作方向と垂直な方向にソートし、隣り合う幅では、ある幅内で昇順ソートであれば、その隣の幅内では降順ソートであるようにして、穴開け位置の訪問経路が蛇行状となるようにした訪問順序を初期経路とすることができる。
なお、「応用数理計画ハンドブック」（久保幹雄ら編集、朝倉書店、２００２）に記載されているように、このような経路の発生方法は一般にストリップ（ｓｔｒｉｐ）法と称されているが、本発明においては、次のように分割幅ｈを決定する。即ち、図４５に示したように、矩形のＸＹステージ動作方向と垂直な方向の長さをａ、ＸＹステージ動作方向の長さをｂ、矩形内の穴数をＮとし、求めたい分割幅をｈとする。ここで、最適な分割幅、即ち動作時間が最小となりそうな分割幅を、Ｘ方向への移動量とＹ方向の移動量が等しければ無駄が無いという観点から、ＸＹステージ進行方向の移動量の平均値と、ＸＹステージ進行方向と垂直な方向の移動量の平均値という２者が一致するような場合を求めることにより決定したい。
統計的評価のため、矩形内の穴開け位置がランダムに分布していると仮定する。
まず、ＸＹステージ進行方向の移動量の平均は、区間［０，ｈ］内にランダムに発生した２数の差の平均である。その値は、０≦ｘ≦ｈ、０≦ｙ≦ｈを満たす２数ｘ、ｙに対し、２数の差の絶対値
2003064107.tif 000004
を考え、領域０≦ｘ≦ｈ、０≦ｙ≦ｈにおけるｚの値の平均値であり、次式により計算すれば求まる。
2003064107.tif 000005
一方、ＸＹステージ進行方向と垂直な方向の移動量の平均は、幅ａの区間に、平均Ｎ×（ｈ／ｂ）個の穴がランダムに並んだ時の平均間隔であるから、次式となる。
2003064107.tif 000006
従って、両者が一致するのは、図４６に示す如く、次式が成立する時である。
2003064107.tif 000007
これを計算すると、次式となる。
2003064107.tif 000008
ここで、ρは密度である。
工程Ｂ（ステージ動作速度算出工程）は、図４７のような方法を用いる。
まず、ステップ９３０において、後述する加工実行不可能なステージ動作速度算出処理（本処理は本文以下又は図面において、ｍａｘ＿ｓｐｅｅｄ（）と書く）を行ない、実行不可能な速度ｖ２を求める。
次いでステップ９３２において、後述する加工実行可能なステージ動作速度算出処理（本工程は本文以下又は図面において、ｍｉｎ＿ｓｐｅｅｄ（）と書く）を行ない、実行可能な速度ｖ１を求める。
ステップ９３４において反復回数を０で初期化する。
ステップ９３６において、脱出条件が、反復回数がＩＴＥ回に達した場合あるいはｖ２−ｖ１がＴＯＬ以下の値になった場合のループ処理に入る。
ステップ９３６において脱出できなかった場合は、ステップ９３８において、ｖ１とｖ２の中間値ｖを求める。
又、速度ｖに対し、ステップ９４０において、後述する実行可能性判定処理（本工程は本文以下又は図面において、ｆｅａｓｉｂｉｌｉｔｙ（）と書く）を行ない、速度ｖで実行可能かどうか調べる。
ステップ９４２において実行可能かどうかを判定し、実行不可能な場合、ステップ９４４において実行不可能な速度ｖ２をｖで更新し、実行可能な場合、ステップ９４６において実行可能な速度ｖ１をｖで更新する。
ここで、実行不可能なステージ動作速度算出処理ｍａｘ＿ｓｐｅｅｄ（）、実行可能なステージ動作速度算出処理ｍｉｎ＿ｓｐｅｅｄ（）、及び、実行可能性判定処理ｆｅａｓｉｂｉｌｉｔｙ（）について説明する。
まず、実行可能性判定処理ｆｅａｓｉｂｉｌｉｔｙ（）について説明する。穴開け加工の実行可能性は、図４８に示す如く、ＸＹステージの速度が増大するにつれて、実行可能な状態から実行不可能な状態へと移る。そこで、次のような方法で、実行可能性の度合を算出する。即ち、図４９に示す如く、各点に対し、時間枠制約、即ち最早開始時刻と最遅完了時刻を設定する。ここで、最早開始時刻とは、穴開けのためのレーザ照射を開始できる、最も早いタイミングのことであり、最遅完了時刻とは、穴開けのためのレーザ照射が完了していなければならない、最も遅いタイミングのことを指す。具体的には、図４９のように、ＸＹステージの逆方向の動作により加工エリアがＹ方向に速度Ｖで基板上を等速遷移しているとし、時刻０で加工エリアの上限位置が基準点Ｙ＝０を通過するとする。点ＰのＹ座標値（絶対値）をＹｐとすると、最早開始時刻はＹｐ／Ｖ、最遅完了時刻は（Ｙｐ＋Ｄ）／Ｖで求められる。但し、Ｄは、「理想的には」加工エリアの大きさを表わす。
ここで、「理想的には」という表現を用いたが、Ｄの値として、実際には、上記駆動モデルと現実の機械動作との間には、ずれが生じているので、これに対処するため、Ｄの値は、加工エリアの大きさよりも幾分小さめに設定しておく。
即ち、最早開始時刻側に長さＤＦ分のマージンを、最遅完了時刻側に長さＤＢ分（ＤＦ、ＤＢは０以上）のマージンを持たせ、誤差への対処を行なう。この場合、最早開始時刻は（Ｙｐ＋ＤＦ）／Ｖで、最遅完了時刻は（Ｙｐ＋Ｄ−ＤＢ）／Ｖで求めることとなる。
例を数字で示す。例えば図５０に示す如く、Ｙｐ＝３００ｍｍ、Ｄ＝５０ｍｍ、Ｖ＝１００ｍｍ／秒とすると、誤差対処用のマージン無しの場合では、最早開始時刻は３００／１００＝３．０秒、最遅完了時刻は（３００＋５０）／１００＝３．５秒となる。従って、ある穴開け位置の加工完了（即ち、照射完了）時刻が、例えば３．２秒なら可であるが、３．７秒ならなら不可であると判定できる。
今、ｉ番目に訪問する点をＰｉとし、最初に訪問する点Ｐ１の照射開始時刻はＰ１の最早開始時刻とする。各点の照射完了時刻は、照射開始時刻に照射時間を加えた時刻により求められる。
Ｐｉ＋１の照射開始時刻は、Ｐｉの照射完了時刻に、ＰｉからＰｉ＋１への移動時間を加え（この結果である、移動が完了した時刻を到着時刻と称する）、もし、到着時刻がＰｉ＋１の最早開始時刻より早ければＰｉ＋１最早開始時刻を照射開始時刻とし、そうでなければ、到着時刻を照射開始時刻とすることにより、順次求められる。
全ての点の照射完了時刻が、その点の最遅完了時刻より早ければ実行可能、そうでなければ実行不可能と言える。即ち、実行可能性判定処理ｆｅａｓｉｂｉｌｉｔｙ（）は、まず、上述のように各点の照射開始時刻を順次求め、全ての点に対し、（最遅完了時刻−照射完了時刻）を計算する。そして、それらの中で最小のもの（以下ではｆ（又はｆ１、ｆ２）と記している）を判定結果として返すというように行なう。即ち、正又は０であれば実行可能であり、負ならば実行不可能である。又同時に、最後に訪問する点の加工完了時刻（以下ではｅ（又はｅ１、ｅ２）と記している）（加工開始時刻を０に設定するので、総加工時間に等しい）を算出する。なお、本処理ｆｅａｓｉｂｉｌｉｔｙ（）は工程Ｃ（穴開け位置訪問順序改善工程）においても用いられる。
ここで、加工を実行する２点間の移動に費やす時間は、まずＸＹステージ停止加工時のＸ方向、Ｙ方向の各移動時間をモデル化しておく。その上で、ＸＹステージが等速で移動している場合には、上記関数を内部で呼び出す形で、移動距離Ｌ及びＸＹステージ速度Ｖを引数に持つ関数としてモデル化可能である。即ち、図５１に示す如く、求めたい移動時間をＴとすると、この時間Ｔで移動距離ＬのうちＸＹステージがＶＴを移動、ガルバノスキャナが残りの距離Ｌ−ＶＴを時間Ｔで走査するモデルである。ここで、移動方向の正負が異なれば、移動距離は同一でも走査時間が異なることにも注意する。
次に、実行不可能なステージ動作速度算出処理ｍａｘ＿ｓｐｅｅｄ（）、及び、実行可能なステージ動作速度算出処理ｍｉｎ＿ｓｐｅｅｄ（）について説明する。これらの処理は、真のステージ動作最大速度を両側から挟み撃ちにして求めるための、挟み撃ち値の初期値として用いられる（図４７及び図４８参照）。初期値は、ｖ１が実行可能、ｖ２が実行不可能でありさえすればよいので、ｖ１を０より少し大きな値、ｖ２をＸＹステージ最大速度より少し小さな値とすることもできる。しかしながら、解を高速に求めるためには、両者共なるべく解に近い値が望ましい。ここで、実行可能及び不可能なステージ動作速度算出処理は、工程Ａ（穴開け位置訪問順序発生工程）のすぐ後の場合、即ち実行可能速度が求まっていない場合と、工程＜Ｃ＞（穴開け位置訪問順序繰り返し改善工程）のすぐ後の場合、即ち実行可能速度が求まっている場合と、２種類ある。
まず、工程Ａのすぐ後の場合について説明する。加工エリアがＹ方向に速度＋ｖで基板上を等速遷移しているとする。Ａ（ｘｉ，ｙｉ）、Ｂ（ｘｊ，ｙｊ）の２点間の移動を考えると、変位量は、（ｘｊ−ｘｉ，ｙｊ−ｙｉ）＝（ｘｄｉｆ，ｙｄｉｆ）である。
ｔ時間で２点間を動作する場合、ガルバノスキャナの走査量は、ＡからＢへの動作の場合は（ｘｄｉｆ，ｙｄｉｆ−Ｖｔ）であり、ＢからＡの動作の場合は（−ｘｄｉｆ，−ｙｄｉｆ−Ｖｔ）であるが、これらの動作の走査時間は、Ｙ方向の走査が無い場合の動作量（ｘｄｉｆ，０）の場合の走査時間よりも必ず大きい（もしくは等しい）値となる。そこで、実行不可能な初期速度ｖ２を求める関数ｍａｘ＿ｓｐｅｅｄ（）は、次のようにして求める。
図４９のように、加工エリアがＹ方向に基板上を等速遷移しているとして、穴開け位置訪問順序Ｓ上の２点間の移動量（ｘｄｉｆ，ｙｄｉｆ）に対し、移動量（ｘｄｉｆ，０）の場合の走査時間を計算する。そして、それらの総和をτとする。
次いで、ＸＹステージの動作速度ｖ２を、走査エリアの基板上でのＸＹステージ進行方向の移動距離をτで割ったものにより求める。
このようにして、実行不可能な保証のある、実行可能な限界速度に近い速度を求めることができる。
一方、実行可能な初期速度ｖ１を求め、併せて実行不可能な初期速度ｖ２の値を更新する処理ｍｉｎ＿ｓｐｅｅｄ（）は、関数ｍａｘ＿ｓｐｅｅｄ（）のように直接的に求めるのではなく、図５２に示すようにして求める。即ち、ステップ８００で関数ｍａｘ＿ｓｐｅｅｄ（）の戻り値として得られた実行不可能な初期速度ｖ２に対し、ステップ８０２で２で割った値に関して、ステップ８０４で実行可能性をチェックし、実行可能であれば処理を終了する。一方、実行不可能であれば、ステップ８０８でｖ２をｖ１で更新する。上記の手順を実行可能となるまで繰り返す。ここで、ｖ２の値もｍａｘ＿ｓｐｅｅｄ（）で求めた値から変わる可能性が有ることに注意する。
次いで、工程＜Ｃ＞のすぐ後の場合について図５３を用いて説明する。この場合、工程＜Ｃ＞を実行する前段階において、既に実行可能側のステージ動作速度ｖ１は確定している。従って、ｍｉｎ＿ｓｐｅｅｄ（）としては、工程＜Ｃ＞を実行する前段階での値を取得し、ｖ１に設定すればよいだけである。又、実行不可能側の動作速度は、実行可能側の動作速度から大きくかけ離れていないはずであるので、ｆｅａｓｉｂｉｌｉｔｙ（）を実行したとき負の値が返るようになるまで、ｖ１に１より少し大きい係数を掛ける処理を繰り返せばよい。このとき、ｖ１の値もｍｉｎ＿ｓｐｅｅｄ（）で求めた値から変わる可能性が有ることに注意する。
なお、図４２のステップ７１０又は図４７のステップ９３８で新しい速度ｖを求めるに際して、２分法以外に、例えば次式に示すような挟み撃ち法を用いてもよい。
2003064107.tif 000009
この挟み撃ち法は、図５４に例示する如く、ｖ−ｆ平面において、ｖ＝ｖ１のときのｆ値（実行可能性関数ｆｅａｓｉｂｉｌｉｔｙ（）を用いて算出される値）ｆ１と、ｖ＝ｖ２のときのｆ値ｆ２とを直線で結んだ時の、ｆ＝０との交点のｖ値を求めるものであり、２分ではなく比例値となる。
工程Ｃ（穴開け位置訪問順序改善工程）については、言わば『時間枠付き非対称ハミルトン路長最小化問題（Ａｓｙｍｍｅｔｒｉｃ  Ｈａｍｉｌｔｏｎｉａｎ  Ｐａｔｈ  Ｐｒｏｂｌｅｍ  ｗｉｔｈ  Ｔｉｍｅ  Ｗｉｎｄｏｗ）』（以下では略語を用い、ＡＨＰＰ−ＴＷと記す）を解くための解法を適用することができる。ここで非対称性は、２つの穴開け位置間の走査にかかる時間（移動コスト）が、２点のうちどちらを始点と見るかにより異なることに対応し、時間枠は、既に説明した最早開始時刻、最遅完了時刻の制限に対応する。又、穴開け位置の訪問は、各位置１度ずつであり、元の位置に戻らない（巡回しない）経路であり、このような経路は一般にハミルトン路（あるいはハミルトン経路もしくはハミルトンパス）と称されている。
ここで、移動コストが非対称である理由はステージ速度が存在するためである（図５１参照）が、実際にはステージ速度はガルバノ走査速度に比べると緩やかである（図５１は非対称であることが分かりやすいようにデフォルメされている）。そこで、非対称ではなく、時間枠付き対称ハミルトン路長最小化問題（ＨＰＰ−ＴＷと略す）と捉えて解法を適用して、主に移動コスト算出時間を中心として最適化計算時間の高速化を図ることもできることに注意する。ここで、対称コストと見ることで若干の誤差が生じてしまうが、その誤差は、既に述べた時間枠設定における誤差マージン付加処理を用いて処理すればよい。
そこで、工程Ｃとして、局所探索法（あるいは近傍探索法とも称される）による改善方法を適用する。即ち工程Ｃは、主に次の３つの処理からなる。
ａ．改善解探索処理
ｂ．改善判定処理
ｃ．解更新処理
処理ａ（改善解探索処理）は、暫定的な穴開け位置訪問順序（Ｓとする）に対し、Ｓより効率的な穴開け位置訪問順序をＳの近傍Ｎ（Ｓ）から選択する処理である（本処理は本文以下又は図面において、ｃｈｏｏｓｅ（）と書く）。ここで、Ｓの近傍Ｎ（Ｓ）とは、具体的には、一般に近傍操作と呼ばれる、例えばｘ番目に訪問していた穴開け位置をｙ番目（後回し又は先回り）にする等の操作によって実現される別の訪問順序の集合を指す。
ここで、ＡＨＰＰ−ＴＷに適用するのに好適な近傍操作として、次のようなものがある。
イ．図５５に示すような２−ｅｘｃｈａｎｇｅ（交換）近傍。
ロ．図５６（前方（ｆｏｒｗａｒｄ））や図５７（後方（ｂａｃｋｗａｒｄ））に示すようなＯｒ−ｏｐｔ近傍。
ハ．図５８（反転無し）や図５９（反転有り）に示すような挿入近傍。
これらの他にも様々な近傍が考えられるが、近傍の拡大に従い計算時間が増大するので、上記３つの近傍（３番目（ハ）は挿入するノード数が数個程度まで）を用いるのが現実的である。特に、Ｏｒ−ｏｐｔ法は、経路の反転が無いゆえ非対称な問題には向いており、又、近傍操作ルールは、点の経路上別位置への移動であるゆえ、時間枠制約を遵守しているかどうかの判定が容易であるので、非対称且つ時間枠を有する場合には適している。又、図３に示したＸＹステージ動作最小化のための矩形分割において、分割された矩形が重複している場合が考えられるが、そのような場合に２つ以上の経路の同時更新することもできる。その場合の近傍操作としては、例えば、次のようなものがある。
ニ．図６０に示すようなクロス交換近傍。
ホ．図６１に示すような２−ｏｐｔ＊近傍。
これらの他にも様々な近傍が考えられるが、計算時間と計算結果の両方を考慮して、適切な近傍操作を用いることができる。
処理ｂ（改善判定処理）は、暫定的な穴開け位置訪問順序（Ｓとする）に対し、近傍Ｎ（Ｓ）から選択された解Ｓ´が、より効率的な解であるかどうかを判定する処理である。本処理として、既に述べたｆｅａｓｉｂｉｌｉｔｙ（）を適用する。即ち、実行可能性（ｆ）及び総加工時間（ｅ）を計算する。ここで、改善解であるための条件は、実行可能、且つ、総加工時間が短縮されることである。場合により、先に実行可能性だけを見て判断する場合（図４２参照）や、両方の成立を見て判断する場合（図６２参照）がある。
処理ｃ（解更新処理）は、暫定的な穴開け位置訪問順序Ｓを、改善解Ｓ´で更新する処理である。訪問順序と共に、各点の加工開始時刻も更新される。
以上に各工程Ａ、Ｂ、Ｃの詳細を述べたが、ステップ１１２を通しての工程として、工程Ａ、Ｂ、＜｛Ｃ、Ｂ｝＞と行なう場合の工程の具体例を、以下に図４２を用いて説明する。
まず、ステップ７００で、加工位置の訪問順序を１つ発生させる（ｉｎｉｔｉａｌ＿ｓｅｑｕｅｎｃｅ（））。
次いで、ステップ７０２で、点訪問順序の初期解Ｓに対して、実行不可能な高速側のＸＹステージ速度（ｍａｘ＿ｓｐｅｅｄ（））ｖ２を１つ求める。次いでステップ７０４で、同じく点訪問順序の初期解Ｓに対し、実行可能な低速側のＸＹステージ速度（ｍｉｎ＿ｓｐｅｅｄ（））ｖ１を１つ求める。この手順の目的は、実行可能な限界速度を求めることであるが、本実施形態では、実行可能な速度値ｖ１と実行不可能な速度値ｖ２とを逐次更新により十分近い値に近づけることにより実現する。
そこで、脱出条件が、最大反復回数がＩＴＥ回より大きくなった、又は、実行不可能速度と可能速度の速度差（ｖ２−ｖ１）の値が十分小さくなった場合とする第１ループ処理を行なう。
具体的には、ステップ７０６で反復回数ｉの初期値を０とし、ステップ３０８で、反復回数ｉが最大反復回数ＩＴＥより大きくなった、又は、高速側ステージ速度ｖ２と低速側ステージ速度ｖ１の差（ｖ２−ｖ１）が閾値ＴＯＬより小さくなった、のどちらかが成り立ったか否かを判定する。判定結果が否である場合には、ステップ７１０に進み、実行可能性（ｆｅａｓｉｂｉｌｉｔｙ）の判定対象として、ｖ１とｖ２の中間値ｖを設定する（２分法）。そして、ステップ７１２で、その時の速度ｖ及び訪問順序Ｓに応じた実行可能性（最遅完了時刻と照射完了時刻の差の最小値）ｆ１及び総加工時間（最後に訪問する点の照射完了時刻）ｅ１を求め、ステップ７１４で、実行可能であるか否かを判定する。
実行不可能な場合は、脱出条件を、実行可能な訪問順序を発見できた場合、又は、実行可能な訪問順序が近傍に無いと分った場合のいずれかとする無限ループである第２ループ処理を行う。
具体的には、ステップ７１２で求められた実行可能性ｆ１が負であり、実行不可能であるとステップ７１４で判定された場合には、ステップ７１６で、無限ループである第２ループの処理に入り、ステップ７１８で、訪問順序Ｓに近傍操作（例えば順序交換）を加えることにより導かれる訪問順序Ｓ´を求め（ｃｈｏｏｓｅ（））、ステップ７２０で、その近傍内の訪問順序Ｓ´に対し、ｆ１、ｅ１と同様にして実行可能性関数ｆ２及び総加工時間ｅ２の値を求める。
次いで、ステップ７２２で、ｆ２が負であるか否かを判定する。判定結果が正であり、ｆ２が負で実行不可能であると判断された場合には、ステップ７２４に進み、ｅ２がｅ１より大であるか否かを判定する。判定結果が正である場合には、ステップ７２６に進み、より良い訪問順序であると判断されるＳ´でＳを更新する。
ステップ７２６終了後、又はステップ７２４の判定結果が否である場合には、ステップ７２８に進み、訪問順序Ｓ´を近傍Ｎ（Ｓ）から削除する。次いでステップ７３０に進み、近傍内に改善解の可能性の有る訪問順序が無くなったと判断されるときには、ステップ７３２に進み、実行不可能な速度ｖ２を、その時の速度ｖで更新し、第２ループを脱出してステップ７５２に進む。
ステップ７３２終了後、又はステップ７３０の判定結果が否であるときには、第２ループから脱出する。
一方、ステップ７２２の判定結果が否であり、訪問順序Ｓ´と速度ｖが実行可能であると判断されたときには、ステップ７４０に進み、訪問順序ＳをＳ´で更新し、実行可能な限界速度ｖ１をｖで更新して、第２ループから脱出する。
又、前出ステップ７１４の判定結果が否であり、訪問順序Ｓと速度ｖが実行可能であると判断されたときには、ステップ７５０に進み、実行可能な限界速度ｖ１をｖで更新する。
ステップ７３２、ステップ７４０又はステップ７５０終了後、ステップ７５２に進み、ｉをインクリメントして、ステップ７０８に戻り、第１ループを再び実行する。
本例は、ステージ速度を実行不可能な速度に固定して、実行可能になるまで工程Ｃを繰り返し実行する場合の処理の例でもある。
又、ステップ１１２を通しての工程として、工程Ａ、Ｂ、＜＜Ｃ＞、Ｂ＞と行なう場合の工程の具体例を、以下に図６２を用いて説明する。
本例は、ステージ速度を実行可能な速度に固定して、工程Ｃを、改善解がある限り繰り返し実行する場合の処理の例でもある。
まず、ステップ２００２で、加工位置の訪問順序Ｓを発生させる（処理ｉｎｉｔｉａｌ＿ｓｅｑｕｅｎｃｅ（））。
次いで、ステップ２００４で、訪問順序Ｓに対して、加工実行可能なステージ等速最大速度ｖを算出する（処理ｆｉｎｄ＿ｓｐｅｅｄ（））。
更に、ステップ２００６、２００７、２００８で、ステップ２０１０からのループ処理に対して、総加工時間ｅを求めておき（処理ｆｅａｓｉｂｉｌｉｔｙ（））、暫定的な最大速度ｖをｏｌｄｖに、総加工時間ｅをｏｌｄＥ及びｏｌｄｏｌｄＥにコピーしておき、反復回数ｉを０に初期化する。なお、ｏｌｄＥはステップ２０１６の各回の近傍探索における改善解判定にて、ｏｌｄｏｌｄＥはステップ２０２４におけるループ脱出判定にて使用される。
ステップ２０１０から、ステージ速度並びに訪問順序を並行して最適化するための、ループ処理を開始する。ループの脱出（工程の終了に等しい）は、充分なループ反復回数に達したとき（ステップ２０１０）、ループにおいて総加工時間が全く変わらなかったとき（ステップ２０２４）、及び、ループ前及びループ後で、速度の改善が余りにも小さい（設定値ＴＯＬを定めておく）とき（ステップ２０２８）、とする。なお、これらの脱出判定は、全てを用いなくとも構わず、最低１つ用いれば良い。
まず、ループ開始時点（ステップ２０１２）で、Ｓの近傍Ｎ（Ｓ）内から、改善解の可能性の有る解Ｓ’を１つ選択する（処理ｃｈｏｏｓｅ（））。近傍として、例えば既に図５４〜５９に示したものを用いる。
次いで、選択されたＳ’に対して、処理ｆｅａｓｉｂｉｌｉｔｙ（）を用いて、Ｓ’の実行可能性ｆ及び総加工時間ｅを算出する（ステップ２０１４）。
ステップ２０１６において、Ｓ’が改善解であるかどうかを判定する。改善解の条件は、実行可能であり（ｆ≧０）且つ総加工時間が短縮されていること（ｏｌｄＥ＞ｅ）である。
改善解であると判定された場合（ステップ２０１８）、解（暫定的な最適訪問順序）をＳ’で更新し、次回の判定のために総加工時間ｅをｏｌｄＥにコピーしておく。そしてステップ２０１２に戻り再び改善解を探索する。
改善解ではないと判定された場合（ステップ２０２０）、Ｓ’を近傍から取り除き、近傍に未だ改善解探索の余地があるかどうかをステップ２０２２にて調べる。既に全ての近傍解について処理が終了しており、近傍探索の余地が無い場合は、ステップ２０２４にて、ステップ２０１０から始まるループにおいて改善が一度も為されなかったかどうかを判定する。判定条件は例えば、ループ処理実行前の総加工時間ｏｌｄｏｌｄＥがｏｌｄＥと等しいかどうかを見る。
ステップ２０２４において、改善が一度は実行された（即ちｏｌｄｏｌｄＥ≠ｏｌｄＥ）と判定された場合は、ステップ２０２６に進み、実行可能ステージ最大速度ｖを算出する。次いで、ステップ２０２８において、ステージ最大速度ｖがループ処理実行前のステージ最大速度ｏｌｄｖに対して、ほとんど改善されていないと判断できる（設定値ＴＯＬに対して、ｖ−ｏｌｄＶ＜ＴＯＬ）場合、ループ処理から脱出し、工程を終了する。改善が充分である場合は、ステップ２０３０に進み、次のループのために、総加工時間ｅを求めておき（処理ｆｅａｓｉｂｉｌｉｔｙ（））、暫定的な最大速度ｖをｏｌｄｖに、総加工時間ｅをｏｌｄＥ及びｏｌｄｏｌｄＥにコピーしておき（ステップ２０３２）、ループ反復回数ｉを１つインクリメントし（ステップ２０３４）、ステップ２０１０に戻ってループを再開する。
一方、ステップ２０２４において、改善は一度も実行されなかった（即ちｏｌｄｏｌｄＥ＝ｏｌｄＥ）と判定された場合は、工程を終了する。
又、図２のステップ１１２で決定された穴開け位置に対する、ステップ１１４での穴開け位置の分布の密度により動作速度を滑らかに変化させるＸＹステージ加減速パターン最適化（速度パターン決定工程）は、次のようにして行なうことができる。
今、ある加工矩形内において、ある実行可能な穴開け位置訪問順序及びＸＹステージ（等速）動作速度でのガルバノスキャナ、加工エリアの基板上の遷移が、図４９の実例である図６３に示す如くであったとする。この例では、図に示す如く、穴開け位置の散布状態が密の場所と疎の場所が混在している加工矩形となっているが、疎な箇所では、ガルバノスキャナによるレーザビームの照射位置が加工エリアの最早開始時刻側の端で止まり、ＸＹステージの到着を待っている状態となっている。このような穴開け位置散布状況の場合、ＸＹステージの動作速度を、矩形内では等速というのではなく、疎な箇所を高速化することが望ましい。
具体的には、図６４に示す如く、ＸＹステージの動作速度を２つに分ける。即ち、上記で求めた穴開け位置訪問順序と動作速度に対して、穴開け位置訪問順序の連続した部分（シーケンス）のうち、密であるシーケンスを見分け、密なシーケンスに対しては、先に求めた動作速度で対応し、その他の疎な箇所に対しては高速な動作速度で対応する。
密なシーケンスを見分ける際には、例えば、シーケンスの先頭及び末尾を、図６５のようにして選択する。
即ち、まず、ステップ１０００で、先頭の候補として、待ち時間（０と（最早開始時刻−到着時刻）の大きい方）が正の状態から０の状態へと移る最初の点を採択する。そして、先頭からシーケンスを順次見て、ステップ１００２で、待ち時間正の点が現われた場合は、密なシーケンスとは認識せず、ステップ１００６で、次の先頭の候補を選択する。ステップ１００８で、候補が無いと判断されたときは、終了する。又は、ステップ１００４で（最遅完了時刻−照射完了時刻）がある閾値よりも小さい値とならないまま、最後の点に到達したと判定された時は、終了する。
一方、ステップ１００２、１００４共に否である場合には、（最遅完了時刻−照射完了時刻）が、ある閾値よりも小さい値となっている点があるので、ステップ１０１０で（最遅完了時刻−照射完了時刻）がある閾値よりも小さい穴開け位置の中で、最小のものをシーケンスの末尾とする。
このようにして、図６４に示した如く、密なシーケンスを識別できる。
又、疎な箇所の動作速度を最大化して、例えば、疎な箇所を密な箇所よりも高速な一定の速度で動作させるのは、例えば図６６に示す如く行なう。即ち、図６５に示すような方法で見分けた密なシーケンス以外が疎なシーケンスとなるが、速度を変更するための加減速時間が必要となる。そこで、疎なシーケンスそれぞれについて、ステップ１１２について既に説明した方法により、動作速度を最大化する（同時に穴開け位置訪問順序を最適化しても構わないし、あるいはｆｉｎｄ＿ｓｐｅｅｄ（）のみを用いて速度を決定しても良い）。
なお、疎なシーケンスの最大速度算出に関し、加減速時間も疎なシーケンスに含むことにより、加減速時間も等速（高速）動作と考えた場合に実行可能であれば、加減速時間の動作速度は疎なシーケンスの等速動作速度より低速であるため、シーケンス全体が実行可能となるので、問題は生じない。
上記疎なシーケンスは更に高速化できる場合には、図６７（Ｂ）に示す如く、多重的な速度対応をすることができる。即ち、上記疎なシーケンスに対し、再びステップ１１４の手法を適用して、疎なシーケンスと密なシーケンスを見分け、疎なシーケンスを更に高速化することができる。
なお、穴開け位置訪問順序及びステージ動作速度最適化工程（ステップ１１０）の結果、全点の照射完了時刻が最遅完了時刻よりある程度早い場合は、図４９から分かるように、加工エリア下限位置に余裕が有るということである。この場合、加工エリアの中央部分にて加工を行なうために、全ての穴開け位置の加工時刻を、全ての点の照射完了時刻が最遅完了時刻より早い範囲内で同一時間分シフトすることができる。
前出ステップ１２０は、ステップ１００により決定された加工矩形の位置及びステップ１１０により決定された加工矩形入出口の動作速度を元にして、図６７に例示する如く、ＸＹステージの動作経路を最適化する。
この最適化の目的は、ある（穴開け位置の存在する）加工矩形間を移動する時間、即ち、ガルバノスキャナとレーザビームを休止させている時間の総和を最小化することにある。
図６８を参照して、ある加工矩形から別のある加工矩形へのＸＹステージの動作について説明する。加工矩形Ａ、Ｂに関し、ＸＹステージ動作方向が両方向矢印で示されているが、加工矩形の左右の端の位置は、加工エリア遷移経路上の加工矩形への入口及び出口となっている。加工矩形Ａの入出口Ａ１、Ａ２でのＸＹステージの速度は、ステップ１１０の最適化により決定されているが、ＸＹステージ動作方向（右から左又は左から右）に関しては決定されていない。時間及び空間の対称性（完全に逆の動作を行なう）を考えれば、ステップ１１０で一時的に用いた動作方向を逆にし、速度パターン及び穴開け位置訪問順序も全く逆にすることが可能である。従って、ＸＹステージ動作方向も最適化の対象となる。
２点間のＸＹステージの動作時間は、ガルバノスキャナの場合と同じく、モデル化し、関数化しておく。関数の引数としては、座標（Ｘ１，Ｙ１）、速度（Ｖｘ，Ｖｙ）の状態から座標（Ｘ２，Ｙ２）、速度（ＶＸ，ＶＹ）の状態への変位の場合、８つの引数（Ｘ１，Ｙ１，Ｘ２，Ｙ２，Ｖｘ，Ｖｙ，ＶＸ，ＶＹ）を持つことになる。
この問題を、次のように制約付き巡回セールスマン問題（正確には、元に戻ってくる必要はないのでハミルトン路長最小化問題）として捉えて解く。
具体的には、各加工矩形を、一端が入口、一端が出口である２つの都市として考える。そして、都市間を結ぶ線（枝と称する）のうち、図６９に示す如く、加工矩形の入出口を隣接させる枝は取り除いてはならないとする制約を加える。つまり、そのような枝を自前にリストアップしておく。
解の構成法としては、局所探索法等のヒューリステックが挙げられる。計算時間と計算結果の両方を考えて、適切な方法を用いることができる。
なお、前記実施形態では、加工矩形の訪問順序だけではなく、加工矩形の入出口も同時に最適決定する必要があるために、複雑な構成となっているが、加工矩形の訪問順序最適化と加工矩形の入出口（ＸＹステージの進行方向）最適決定を直列に行なうこともできる。
例えば、加工矩形の訪問順序を最適化した後、加工矩形の入口を決定する場合には、図７０に示すように行なうことができる。
即ち、まず、ステップ１１００で加工矩形の訪問順序を最適化する。
具体的には、加工矩形の中心位置を１つの都市として捉え、ハミルトン路長最小化問題の局所探索による解法を用いて、加工矩形の訪問順序を最適化する。
次いで、加工矩形の入出口を決定する。具体的には、ステップ１１０２で、一番最初に訪問する加工矩形の入出口を例えば左側又は下側などのように決定する。又、その加工矩形を現在の加工矩形とする。
次いで、ステップ１１０４で、次の加工矩形の２つの入出口候補のうち、現在の加工矩形の出口から近い方を入口とし、別の方を出口とする。ステップ１１０４を、ステップ１１０６で最後の訪問順序の加工矩形の入出口が決まるまで繰り返す。
あるいは、ステップ１１０４を、次のようにしても良い。即ち、次の次の加工矩形の２つの入出口候補のうち、現在の加工矩形の出口から近い方を仮の入口（次々仮入口）とし、別の方を仮の出口とする。次の加工矩形の２つの入出口候補のうち、現在の出口からの次の入口迄のコストと、次の出口から次々仮入口迄のコストを、次の入口候補の２つに関して計算し、コストの小さい方を次の入口とする。
あるいは、加工矩形の数をＫとおくと、解の組合せ数は２Ｋである。加工矩形の数が多くなければ、全ての可能性を完全列挙することも可能である。あるいは、加工矩形の数が多くても、局所探索法等を用いて良い解を求めてもよい。
又、加工矩形の入出口を決定した後、加工矩形の訪問順序を最適化する際には、図７１に示すようにして行なう。即ち、まず、ステップ１２００で、全ての加工矩形の入出口を決定する。具体的には、
イ．進行方向が左右方向であれば左、上下方向であれば下とする、
ロ．各加工矩形に対し、ランダムに設定する、
等が考えられる。
次に、ステップ１２０２で、加工矩形の訪問順序を最適化する。具体的には、加工矩形１つ１つを都市として捉える。そして、非対称ハミルトン路長最小化問題の局所探索による解法を用い、加工矩形の訪問順序を最適化する。ここで非対称であるのは、加工矩形Ａ（の出口）から加工矩形Ｂ（の入口）への移動と、加工矩形Ｂ（の出口）から加工矩形Ａ（の入口）への移動とが、加工矩形の入出口が既に決まっているので異なるためである。
あるいは、加工矩形の進行方向が全てＸ方向若しくはＹ方向に揃っている場合には、図７２（全ての加工矩形の進行方向がＸ方向の場合）に示す如く、行うことができる。
即ち、最初の加工矩形をＹ座標最小、且つ、同一Ｙ座標のものが複数ある場合は、その中でＸ座標最小のものとする。最初の加工矩形の加工エリアの基板上の遷移方向＋（正）の向きと設定する。
そして、次のように、Ｙ座標の小さなものから順に並べる。この際、同一のＹ座標のものは、加工エリア移動方向も左右同一であるとする。即ち、最も左のものから右方向へ、若しくはその左右逆を採る。一方、Ｙ座標が異なる場合は、基板上において加工エリアが現在の加工矩形を右に遷移する場合、次の加工矩形の左端が現在の加工矩形の右端よりも左であれば、遷移方向を左右変えず、さもなければ遷移方向を逆転する。若しくはその左右逆を採用する。
このようにして、加工矩形はＹ座標の小さいものから大きいものへ、基板上の加工エリアの移動経路が蛇行状になるように無駄なく接続される。
なお前記実施形態においては、図２に示した如く、まず、穴開け位置の加工矩形分割を行ない、次いで各加工矩形内の穴開け位置訪問順序最適化及びＸＹステージ動作速度最適化を行ない、最後にＸＹステージ動作経路の最適化を行なっていたが、図７３に示す第２実施形態のように、まず、ステップ１３００で基板全体の穴開け位置訪問順序を最適化し、次いでステップ１３１０でＸＹステージ制御目標位置（ステージ動作を制御するときの指定位置）を効果的に設定して、ＸＹステージ動作パターンを決定することも可能である。
前出ステップ１３００の基板全体の穴開け位置訪問順序最適化に際しては、例えば、問題を２点ＡＢ間のコストが、Ａから移動の場合とＢから移動の場合とで等しい対称巡回セールスマン問題として捉えて、例えばＬｉｎ−Ｋｅｒｎｉｇｈａｎの算法等の良く知られた手法を用いて、最適化を行なうことができる。
一方、ステップ１３１０のＸＹステージ動作パターン決定については、ＸＹステージの速度や加速度計画は、ステージは直線動作とは限らないため、非常に難しい。そこで、ＸＹステージに対し目標位置を定め、該目標値に向かって進行している間にガルバノスキャナによる走査及びレーザ照射による加工を行なうようにする。この方法において、実行可能な動作を保証するために、ＸＹステージ目標位置を、図７４に示すように設定する。
まず穴開け位置を加工エリアと同寸の矩形でグループ分けすることを考える。前出ステップ１３００により定まった穴開け位置（訪問順にＰ１，Ｐ２，…と順序付け）に対し、ステップ１３１２で、訪問順序の先頭Ｐ１を着目点（ｉ＝１）とする。又、グループを｛Ｄ１，Ｄ２，…｝で表わすこととし、インデックスｋを１に設定する。
そして、ステップ１３１４〜１３２０に示す如く、次の処理を最後の穴開け位置に到達するまで反復することにより、穴開け位置を加工エリアと同寸の矩形でグループ分けすることができる。
即ち、ステップ１３１４で、ｊ（≧ｉ）に関し、｛Ｐｉ，…Ｐｊ｝が全て加工エリアと同寸の矩形に収まるような最大のｊを探し、ステップ１３１６で、｛Ｐｉ，…，Ｐｊ｝を１つのグループＤｋとする。
次いでステップ１３１８で、次の注目点ｉをｊ＋１とし、ｋをインクリメントする。
次いでステップ１３２２で、ＸＹステージの目標位置を、次のように設定する。即ち、Ｄｋにグループ分けされた点集合｛Ｐｉ，…，Ｐｊ｝に対し、｛Ｐｉ，…，Ｐｊ｝の広がりの中心位置を目標位置とする。ここで、広がりの中心とは、｛Ｐｉ，…Ｐｊ｝のうちのＸ方向、Ｙ方向の｛最小値、最大値｝をそれぞれ｛ｘｍｉｎ，ｘｍａｘ｝、｛ｙｍｉｎ，ｙｍａｘ｝とおくと、座標（（ｘｍｉｎ＋ｘｍａｘ）／２，（ｙｍｉｎ＋ｙｍａｘ）／２）で表わせる位置を指す。
このようにして設定された目標位置を用い、ステップ１３３０〜１３５０で、実行可能なステージ非停止加工を実現する。
即ち、ステップ１３３０で、Ｄｋにグループ分けされた点集合｛Ｐｉ，…Ｐｊ｝に関し、Ｄｋの目標位置へとＸＹステージが動作する過程において、ガルバノスキャナによる位置決めとレーザ照射による加工を順次行なう。
ステップ１３４０で、全ての点｛Ｐｉ，…Ｐｊ｝の加工が済み次第、ステップ１３５０で、次の目標位置へＸＹステージを移動させる。
なお、ステップ１３２２では、広がりの中心位置をＸＹステージの目標位置としていたので、簡単であるが、必ずしも最適な設定方法ではない。
そこで、別の設定方法について説明する。まず、図７５を参照して、目標位置の候補となる領域について説明する。点集合｛Ｐｉ，…，Ｐｊ｝の中で、Ｘ方向、Ｙ方向の｛最小値、最大値｝をそれぞれ｛ｘｍｉｎ，ｘｍａｘ｝、｛ｙｍｉｎ，ｙｍａｘ｝とおく。点の広がりは｛ｘｍｉｎ，ｙｍｉｎ｝、｛ｘｍａｘ，ｙｍｉｎ｝、｛ｘｍａｘ，ｙｍａｘ｝、｛ｘｍｉｎ，ｙｍａｘ｝の４点で囲まれる矩形であるが、これらの４点が全て収まる加工エリアの大きさの矩形の中心を目標位置としておけば、照射可能である。従って、加工エリアが正方形であるときの例で加工エリアの一辺をｄとおくと、Ｄｋの目標位置の候補となる矩形Ｃｋの頂点の座標は、
（ｘｍａｘ−ｄ／２，ｙｍａｘ−ｄ／２）、
（ｘｍｉｎ＋ｄ／２，ｙｍａｘ−ｄ／２）、
（ｘｍｉｎ＋ｄ／２，ｙｍｉｎ＋ｄ／２）、
（ｘｍａｘ−ｄ／２，ｙｍｉｎ＋ｄ／２）
である。
ＸＹステージの動作は、ガルバノスキャナの動作と比較して遅いため、少ない方が望ましい。そこで、広がりの中心位置を目標位置とする代わりに、図７５に示す如く設定してもよい。ここで、Ｄｋの目標位置を表わすのにＶｋを用いる。
Ｃ１の４頂点とＣ２の４頂点を結ぶ組合せのうち、最も近い組合せの頂点をＶ１、Ｖ２に設定する。
ｉ＞２に関しては、Ｃｉの４頂点のうちＶｉ−１に最も近い点をＶｉとする。
あるいは、図７７及び図７８（概念図）に示す如く、Ｖｉ−１からＶｉへの距離とＶｉからＶｉ＋１への距離の和が最小となるようなＶｉに設定してもよい。即ち、まず、Ｃ１の４頂点とＣ２の４頂点を結ぶ組合せで、最も近い組合せの頂点のうちＣ１の頂点の方をＶ１に設定する。
次いで、ｉ≧２に関しては、暫定的に、
イ．ＶｉをＣ１の４頂点の内、Ｖｉ−１から最も近い頂点に仮設定する。
ロ．Ｖｉ＋１をＣｉ＋１の４頂点の内、Ｖｉ−１から最も近い頂点に仮設定する。
図７７に示すが如く、説明のためＶｉを原点に採り、Ｖｉ−１が第４象限に有るとする（対称性を考慮すると、一般性は失われない）。
図７７（ａ）に示すが如く、Ｖｉ＋１がどの象限にあるかに応じて、次のような処理を行う。
即ち、
ケースＡ：第１象限にあるときは、［Ｖｉ＋１］をＶｉと同一に設定し、
ケースＢ１：第２象限にあるときは、Ｖｉ＋１をＹ軸に関し対称にとった位置を［Ｖｉ＋１］とし、
ケースＢ２：第４象限にあるときは、Ｖｉ＋１をＸ軸に関し対称にとった位置を［Ｖｉ＋１］とし、
ケースＣ：第４象限にあるときは、Ｖｉを仮に定めた位置で確定する。以下の処理はしない。
次いで、図７７（ｂ）に示すが如く、第１象限に位置する［Ｖｉ＋１］と、第４象限に位置するＶｉ−１をを結ぶ直線をＬとする。矩形Ｃｉと直線Ｌの交差関係に基づき、次のようにＶｉを定める。
即ち、直線Ｌが矩形Ｃｉと、
イ．交差なし且つＬのＹ切片は負の場合、Ｃｉ右下の頂点ＰをＶｉに確定する。
ロ．交差あり且つＬのＹ切片は負の場合、ＣｉとＬの交点Ｑ１、Ｑ２又はその２点間に位置する任意の位置をＶｉに確定する。
ハ．交差あり且つＬのＹ切片は正の場合、ＣｉとＬの交点Ｒ１、Ｒ２又はその２点間に位置する任意の位置をＶｉに確定する。
ニ．交差なし且つＬのＹ切片は正の場合、Ｃｉ左上の頂点ＳをＶｉに確定する。
このように確定すると、Ｖｉ−１からＶｉへの距離とＶｉからＶｉ＋１への距離との和は最小となる。
上記２つの設定方法は、いずれも完全に最適な目標位置を探索する方法ではないが、少ない計算時間で良好な計算結果を得ることができる。あるいは、各目標位置を表わす矩形から目標位置の候補を何箇所か選択しておき、それらの候補の組合せから良い組合せを求める組合せ最適化問題と定義し、例えば局所探索法等のヒューリスティックを用いて良い解を求めるのも可能である。
なお、ＸＹステージに対し目標位置を定め、目標位置に向かって動作している間にガルバノスキャナによる走査及びレーザ照射による加工を行う方法を採用する場合、実際にはＸＹステージの機械特性によっては、精度や追従性等に問題を生じることがある。そこで、第３実施形態のように、ＸＹステージの一方は加工中は停止させておいて、Ｘ方向又はＹ方向の一方のみに、ＸＹステージの目標位置を定める方式のステージ非停止加工を用いることで実現することが考えられる。即ち、既述の加工矩形分割と併用し、図７９に示す如く、工程を分割する。
即ち、ステップ１４００で穴開け位置の加工矩形分割を決定し、ステップ１４１０で加工矩形内の穴開け位置訪問順序を最適化し、ステップ１４２０でＸＹステージの動作パターン、即ち加工矩形内の穴開け位置のグループ化をして各グループのＸＹステージ制御目標位置を設定する。
前記ステップ１４００は、図２のステップ１００と同一である。
ステップ１４１０は、図４４で説明した、初期経路設定法及び始点と終点を結ぶ枝は切断してはならないという制約付の巡回セールスマン問題の解法を用いることができる。
又、ステップ１４２０に関しては、図７３のステップ１３１０と同様のＸＹステージ動作パターン最適化を用いることができる。
このようにして、Ｘ又はＹの一方向へのＸＹステージ動作を行い、その一列の加工が完了すると次の一列を加工するような順序の良い加工により、位置決め精度の良いステージ非停止加工を実現することができる。
又、Ｘ又はＹの一方向へのＸＹステージ動作において、加工矩形分割を穴開け位置の存在する箇所のみにおいて行うことにより、効率的なステージ非停止加工を実現することができる。
又、Ｘ及びＹの一方向へのＸＹステージ動作において、Ｘ及びＹの加工矩形分割の両方を試行し、良い方を選択することにより、効率的なステージ非停止加工を実現することができる。
又、Ｘ及びＹの一方向へのＸＹステージ動作において、Ｘ及びＹの加工矩形分割の両方を試行し、出来た加工矩形分割の内、ＸＹステージの動作距離の小さいものを選択し、ＸＹステージの動作距離最小の加工矩形分割を行うことにより、効率的なステージ非停止加工を実現することができる。
又、Ｘ又はＹ軸方向の最適加工矩形分割により、ＸＹステージの動作箇所を穴開け位置がある箇所のみに限定することができるため、加工高速化が実現できる。
又、穴開け位置の疎密を考慮した加工矩形分割により、疎な箇所は疎な箇所で、密な箇所は密な箇所で加工矩形を特定し、疎な箇所では速い速度、密な箇所では遅い速度で加工を行うことにより、加工高速化が実現できる。
又、ＸＹステージの駆動とガルバノスキャナの走査を共に行うことによる位置決めにおいて、穴開け位置をＸＹステージ動作方向に合わせて適当な幅でグループ分けし、各グループにおいてＸＹステージ進行方向と垂直な方向にソートし、蛇行状に接続することにより無駄の少ない経路での加工が実現できる。
又、ＸＹステージの駆動とガルバノスキャナの走査を共に行うことによる位置決めにおいて、上記適当な幅を、その加工矩形の穴開け位置密度に応じて、設定することにより、より無駄のない経路での加工が実現できる。
又、ＸＹステージの駆動とガルバノスキャナの走査を共に行うことによる位置決めにおいて、ガルバノスキャナの動作時間を予めモデル化しておき、モデル上でのガルバノスキャナの動作時間の総和が最小となるように穴開け位置の訪問順序を繰返し改善することにより、動作時間のより短い加工を実現することができる。
又、ＸＹステージのある方向への駆動とガルバノスキャナの走査を共に行うことによる位置決めにおいて、ＸＹステージの制御目標位置を順次設定し、目標位置に向かって駆動する最中に照射を行うような形態の場合に、事前に目標位置を計画することにより、ステージ非停止加工を効率よく行うことができる。
前記形態において、穴開け位置を、最初に訪問するものから順に走査エリアと同じ大きさの矩形に収まる迄を１つのグループとする処理を順次行うことにより、目標位置を定める方法により良い目標位置を設定できる。
前記目標位置に関して、穴開け位置のグループに属する全ての点が走査エリア収まるような矩形の中心位置を表す矩形領域を目標位置の候補とすることにより、ＸＹステージ駆動量を減らすための融通性を増すことができる。
前記目標位置を渡る経路を最適化する過程において、次の目標位置を前の目標位置から最も近い位置とすることにより、良い目標位置を定めることができる。
あるいは、前記目標位置を渡る経路を最適化する過程において、次の目標位置を定めるときに、次の次の目標位置を前の目標位置から最も近い位置と仮に定め、前の目標位置からのコストと次の次の目標位置迄の移動コストの和を最小化する位置を目標位置とすることにより、良い目標位置を定めることができる。
あるいは、前記目標位置を渡る経路を最適化する過程において、各目標位置の候補をいくつか定め、目標位置の候補の組合せから移動コストの総和を最小化するような組合せを求める組合せ最適化問題と定義し、局所探索法などの手法により優れた目標位置を定めることができる。
又、ＸＹステージの駆動とガルバノスキャナの走査を共に行うことによる位置決めにおいて、ＸＹステージの速度、加速パターンなどを予め設定し、設定通りに駆動させ、駆動中に照射を行うような形態の場合に、事前にＸＹステージの速度、加速パターン等を好適に計画することにより、ステージ非停止加工を効率良く行うことができる。
あるいは、ＸＹステージの駆動とガルバノスキャナの走査を共に行うことによる位置決めにおいて、ＸＹステージの速度、加速パターンなどを予め設定し、設定通りに駆動させ、駆動中に照射を行うような形態の場合に、事前にＸＹステージの等速な動作速度を好適に計画することにより、加工計画時間を削減でき、又、ステージ非停止加工を効率良く精度良く行うことができる。
前記形態において、穴開け位置を分割した各加工矩形に対し、動作速度を決めることにより、加工速度を上げることができる。
前記形態において、ＸＹステージを穴開け加工中は等速に動作させるような実行形式において、計画を行う際に、等速動作における最早照射開始時刻及び最遅照射完了時刻をモデル上で定め、そのタイミング内に照射開始時刻及び照射完了時刻が収まるような最大速度を求めるような方法により、等速動作の最大限界を求めることができる。
前記最大速度は、実行可能な速度と実行不可能な速度をまず決め、間の速度に関し実行可能性を調べ、実行可能であれば実行可能速度を、実行不可能であれば実行不可能な速度を逐次更新することにより、実行可能速度の最大限界を効率的に求めることができる。
前記形態において、ＸＹステージを穴開け加工中でも可変動作させるような実行形式において、まず等速動作の最大値を求め、その動作を制限している密なシーケンスを特定し、疎なシーケンスに関しては、更に高速化することにより、等速動作よりも更にＸＹステージの動作を高速化することができる。
前記形態において、ＸＹステージを穴開け加工中でも可変動作させるような実行形式において、等速動作を行っているシーケンスの中から、密なシーケンスと疎なシーケンスを切り分け、疎なシーケンスに対しては、動作速度を高速化する処理を多重化することにより、よりＸＹステージの動作を高速化することができる。
前記同時最適化において、ある穴開け位置訪問順序とあるＸＹステージ速度に対して実行可能性を調べる関数を作成し、実行可能な点訪問順序とＸＹステージ速度を、ある速度に対し実行可能であれば実行可能速度の上限を上げ、実行不可能であれば穴開け位置訪問順序を改善することにより実行可能になるように探索し、実行可能であれば実行可能速度の上限を上げ、実行不可能であれば実行不可能速度の下限を下げるようにして、効果的に等速動作の最高速度を求めることができる。
あるいは、前記同時最適化において、ある穴開け位置訪問順序とあるＸＹステージ速度に対して実行可能性を調べる関数を用い、ある穴開け位置訪問順序に対するＸＹステージ等速動作速度を最大化する関数を作成し、もしある穴開け位置訪問順序における動作速度より別の訪問順序における動作速度の方が速ければ、実行可能な動作速度及び点訪問順序を更新する処理を可能な限り繰り返すことにより、効果的に等速動作の最高速度を求めることができる。
又、ＸＹステージを動かしつつ照射加工を行う際の穴開け位置の存在する加工矩形に関し、複数の加工矩形を訪問する順序及び加工矩形上を動作する方向（動作経路）を最適に決定することにより、加工速度を高速化することができる。
前記決定法として、もし加工矩形の動作方向が左右もしくは上下に均一化されているならば、ＸＹステージの動作経路が基板の端から蛇行状になるように設定することにより、加工速度を高速化することができる。
あるいは、前記決定法として、まず各加工矩形の中心位置を各都市の座標とし、巡回セールスマン問題又はハミルトン路長最小化問題を適用することにより加工矩形訪問順序を定め、次に各加工矩形上の動作方向を定める際に、注目する加工矩形の次の加工矩形の入口を、入出口の候補２つの内、前の加工矩形の出口からの移動コストの小さいほうを選択することを繰り返すことにより決定する方法で、良いＸＹステージの動作経路を決定することができる。
又、まず注目する加工矩形の次の次の加工矩形の入出口の候補２つの内、注目する加工矩形の出口からの移動コストの小さいほうを仮の入口とし、注目矩形の次の加工矩形の入出口の候補２つの内、注目矩形の入口から次の入口候補の移動コストと次の出口候補と仮の入口との移動コストの和が小さい方を選択することを繰り返すことにより、良いＸＹステージの動作経路を決定することができる。
又、各加工矩形の入口候補が２箇所あるが、加工矩形の数が少ない場合は、全ての可能性に関し移動コストの総和を求め、最小のものを選択するような方法を取ることにより、最良の入出口の選択を決定することができる。
又、各加工矩形の入口候補が２箇所あるが、局所探索法などの手法により、優れた入出口の選択を定めることができる。
前記決定法として、まず各加工矩形のＸＹステージ動作方向を定め、それらの加工矩形の入出口を基に非対称セールスマン問題又はハミルトン路長最小化問題の解法に従って、良いＸＹステージの動作経路を決定することができる。
前記決定法として、各加工矩形の入出口を２つの都市として捉え、入出口を結ぶ枝は取り除いてはならないという制約のもとでの対称巡回セールスマン問題又はハミルトン路長最小化問題の解法を用いて最適化することにより、加工矩形を訪問する順序及び加工エリアが加工矩形上を移動する方向を同時に決定することができる。
又、ステージ非停止加工を行う際に、まず穴開け位置訪問経路を基板全体の各穴開け位置を１つの都市とする対称巡回セールスマン問題又はハミルトン路長最小化問題と定義し、その後に実行可能なＸＹステージの目標位置を決定することにより、ステージ非停止加工を実現することができる。
又、基板全体の穴開け位置を、一辺（進行辺）が加工エリアの幅以下で、他辺（停止辺）が、加工エリアの幅以上の、ＸＹ軸に平行な幾つかの加工矩形に分割することにより、穴開け加工中はＸＹステージをＸ方向又はＹ方向への同一方向の単純な動作を行なわせ、加工が終わると次の加工矩形に高速に移動させることにより、速度、加速度パターンの計画を効率的に行なうことができる。
特に、上記加工矩形分割における各加工矩形を図６又は図１０のように決め、ＸＹステージ動作経路を蛇行状になるように設定した場合には、加工中でない場合の動作が少ない良い経路を得ることができる。
又、上記加工矩形分割で得られた各加工矩形内に、穴開け位置が無い箇所が、図８に示したように進行辺に沿って長い距離存在する場合、その箇所の前後又は左右に走査矩形を２分することにより、穴開け位置の存在しない箇所を加工矩形間を渡る部分と認識でき、ＸＹステージ動作速度計画を容易にすることが可能となる。
又、前記加工矩形分割を、図１０のように、全加工矩形の進行辺と停止辺の向きが統一しており、加工矩形の位置が図１１（Ｂ）のように、互いに段の揃った配置であるような加工矩形分割を行なうことにより、ＸＹステージ動作経路最適化が容易で、ＸＹステージを精度良く動かすことが可能な、実用的なＸＹステージ動作速度計画を行なうことができる。
即ち、前記段の揃った配置は、最短路問題の解法を用いて段の個数を最小化することにより、効率的な加工矩形配置を行なうことができる。
又、前記段の揃った配置は、加工矩形内の穴開け位置が加工エリアの中心に近づくよう各加工矩形の位置を微調整することにより、精度良い加工を実現できる。
更に、前記段の揃った配置は、最適化の結果、段の数が最小の解のうち、各加工矩形内の段のある方向に沿った穴開け位置の存在しないギャップが最小となるようなものを選択することにより、各加工矩形内の穴開け位置配置が加工高速化にとって効率的なものとすることができる。
又、前記加工矩形分割を、図６又は図１０のように加工矩形の進行辺と停止辺の向きが統一したもので計画する際に、Ｘ方向、Ｙ方向の両方について試行し、良い方を選択することにより、加工時間を短縮することができる。
前記良い方の選択基準としては、例えば加工矩形の進行辺の長さの総和の小さい方を選択することにより、無駄の無いＸＹステージ経路を得ることができる。
あるいは、前記良い方の選択基準として、各加工矩形の疎密の均一度を調べることにより、ＸＹステージの動作速度を各加工矩形に対しほぼ一定とすることができ、無駄の無い加工を実現することができる。
更に、前記各加工矩形の疎密の均一度を調べるために、加工矩形の進行辺に沿って累積頻度分布を作成することにより、図１５（Ｂ）に見られる疎密の斑を容易且つ正確に検出することができる。
又、前記加工矩形分割を、図６又は図１０のように加工矩形の進行辺と停止辺の向きが統一したもので計画する際に、図２１に示したように、Ｘ方向、Ｙ方向の両方について試行し、加工矩形箇所を一旦決めた後、それらの加工矩形の良い組合せにより加工矩形の配置を決定することによって、加工時間を短縮することができる。
前記良い組合せの基準としては、例えば加工矩形の進行辺の長さの総和の小さい組合せを選択することにより、無駄の無いＸＹステージ経路を得ることができる。
あるいは、前記良い組合せの基準として、各加工矩形の疎密が均一である組合せを選択することにより、ＸＹステージ動作速度を、各加工矩形に対しほぼ一定として、無駄の無い加工を実現することができる。
又、前記加工矩形分割を、穴開け位置の疎密があるかどうかを判定し、疎な箇所と密な箇所が存在する場合は、疎密の度合に応じて穴開け位置をグループ分けし、最も疎なグループ以外のグループの穴開け位置に関しては、規則性がある箇所については加工矩形位置を先に確定することにより、図２７に示したように加工時の穴開け位置の密度を一様化でき、加工効率を上げることができる。
なお、前記穴開け位置の疎密を判定するために、基板全体を格子状に分割し、各セルの穴開け位置の個数を求め、度数グラフを作成することにより、穴開け位置の疎密を容易且つ正確に検出することができる。
又、前記穴開け位置の各グループの規則性を検出する際に、基板全体を格子状に分割して各セルの穴開け位置の疎密を調べ、その情報に従って、図２６に示したように、全穴開け位置を、穴開け位置の疎なセルのリングにより囲まれた、穴開け位置の密なセルを含んだセル群を覆ういずれかのセル集合矩形で被覆することにより、容易且つ正確に規則性を検出することができる。
又、前記加工矩形分割を、穴開け位置の分布状態若しくはデータファイルの書式を基に、穴開け位置を大多数グループと少数グループに２分できるかどうかを判定し、図３１に示したように、２分できる場合には、大多数グループの穴開け位置に関しては、規則性がある箇所に対して加工矩形位置を確定することにより、段の揃った加工矩形配置方法では少数の穴開け位置の存在のせいで困難であった加工矩形配置を容易に実現することができ、加工効率を上げることができる。
なお、前記穴開け位置の大多数／少数グループの規則性を検出するために、基板全体を格子状に分割して各セルの穴開け位置の有無を調べ、その情報に従って、図２６に示したように、全穴開け位置を、穴開け位置の無いセルのリングにより囲まれた、穴開け位置の有るセルを含んだセル群を覆ういずれかのセル集合矩形で被覆することにより、容易且つ正確に規則性を検出することができる。
更に、得られたセル集合矩形それぞれに関し、矩形の外周側のセル内の最も外側にある点を調べることにより、前記穴開け位置の広がりをより正確に特定でき、規則的配置を容易に検出することが可能となる。
又、前記最も疎なグループ以外のグループ及び大多数グループの規則性は、直線状配置又は格子状配置とすることにより、ＸＹステージを同一の方向に動かすことのできる走査矩形分割を実現することができる。
又、前記最も疎なグループ以外のグループの複数のセル集合矩形及び大多数グループの複数のセル集合矩形から直線状配置を検出し、加工位置を表わす加工矩形をセル集合矩形を覆うように配置する際に、図３７（Ａ）に示した如く、直線状配置を、直線の延びる方向を進行辺とする１つ又は複数の分割矩形で被覆するが、直線状配置をしたセル集合矩形の間隔がある程度大きければ、図３７（Ｂ）に示したように、その箇所の前後に２分することにより、穴開け位置の存在しない箇所を加工矩形間を渡る部分と認識でき、ＸＹステージ動作速度計画を容易にすることが可能となる。
又、直線状配置をしたセル集合矩形の、直線の延びる方向と垂直な方向の大きさが、図３７（Ｃ）に示したように、加工エリアの大きさよりも大きければ、直線状配置を複数の加工矩形を配置することにより、容易に加工矩形を得ることができる。
更に、前記のような複数の加工矩形により被覆する際に、加工矩形の内部に、図１５（Ａ）に示した如く、穴開け位置が２分されてしまう箇所ができる場合に、図３７（Ｄ）に示したように、加工矩形の中心位置を微調整することにより、各加工矩形内の穴開け位置配置を、加工高速化にとって効率的なものとすることができる。
又、前記最も疎なグループ以外のグループの複数のセル集合矩形及び大多数グループの複数のセル集合矩形から格子状配置を検出し、加工位置を表わす加工矩形をセル集合矩形を覆うように配置する際に、図３８に示した如く、格子状配置を１つ又は複数の平行な加工矩形で被覆するが、格子状配置のＸ方向、Ｙ方向それぞれに関し、セル集合矩形の間隔がある程度大きければ、図３８に示したように、矩形群を分断する。その際に、格子状配置のセル集合矩形を覆うように１つ又は複数の平行な加工矩形を配置する際の進行辺の方向の設定方法として、
イ．ＸＹステージの据付（上段、下段）により、上段ステージになった方向で進行辺を設定することにより、ＸＹステージ動作追従性、精度等の良い加工中のＸＹステージ動作経路を得ることができる。
ロ．加工矩形枚数が少なくて済む方で設定することにより、加工矩形間を渡る回数を減らすことができる。
ハ．進行辺の長さの総和が小さい方、又は、セル集合矩形同士の間の距離の総和が小さい方で設定することにより、加工中に穴開け位置が現われない時間を低減することができる。
ニ．ガルバノスキャナやＸＹステージの動作をモデル化しておき、実際に総加工時間を計算し、良い方を選択することで、効率的な加工矩形を得ることができる。
又、上記加工矩形分割を、まず穴開け位置の疎密があるかどうかを判定し、疎な箇所、密な箇所が存在する場合には、疎密の度合に応じて穴開け位置をグループ分けし、最も疎なグループ以外のグループの穴開け位置に関しては規則性がある箇所に対して加工矩形位置を確定し、無い箇所は残しておき、次に穴開け位置の分布状態若しくはデータファイルの書式を基に穴開け位置を大多数グループと少数グループに２分できるかどうかを判定し、２分できる場合には大多数グループの穴開け位置に関しては、規則性が有る箇所に対して加工矩形位置を確定し、無い箇所は残しておき、残った箇所の加工矩形位置を最後に確定することにより、穴開け位置の疎密が揃っていて、パターン形状を無駄なく加工できる、理想的な加工矩形分割が得られ、加工を効率化することができる。
又、前記残った箇所の加工矩形位置確定に際し、図６、図１０、図１７、図２１に示すような、段の揃った加工矩形配置を採用することにより、加工を効率化することができる。
又、前記残った箇所の加工矩形位置確定に際し、残った穴開け位置の存在する箇所が少ない場合は、ステージ停止加工を適用することにより、加工を効率化することができる。
なお、前記ステージ非停止加工を行なう際のステージ停止加工の併用は、ステージ停止加工をステージ非停止加工の一部と捉えることにより、同一の制御系で実現することができ、設計が容易である。
なお、前記実施形態においては、高速位置決め手段がガルバノスキャナとされ、低速位置決め手段がＸＹステージとされていたが、位置決め手段の種類や組合せはこれに限定されず、例えば出願人が特開２０００−７１０８９や特開２０００−３３４６３７で提案したような、リニアモータＸＹステージと高速加工ヘッドを組合せたハイブリッド加工システム（いわゆるスクリーンカットシステムあるいはフラッシュカットシステム）であってもよい。
又、適用対象も、点状の加工を行うレーザ穴開け機に限定されず、線状の加工を行うレーザ切断機、特開平１１−１４９３１７に記載された２ヘッドレーザ加工機やレーザビーム以外の加工手段を用いた一般の加工機（例えば機械式ドリルによる穴開け装置）であって、２つ以上の位置決め装置を同時に駆動させることにより位置決めを高速化することが可能なもの全般にも同様に適用できることは明らかである。
産業上の利用可能性
本発明によれば、加工の事前段階において、加工を効率良く行うための計画が可能となり、位置決め精度の良い低速位置決め手段非停止加工を実現して、加工時間を短縮することが可能になるという優れた効果を有する。
【図面の簡単な説明】
図１は、本発明の適用対象の一例であるレーザ穴開け機の要部構成を示す正面図
図２は、本発明による加工計画の第１実施形態の処理手順を示す流れ図
図３は、本発明による加工矩形分割最適化の概念を示す平面図
図４は、同じく加工矩形内の穴開け位置訪問順序及びＸＹステージ動作速度最適化の概念を示す平面図
図５は、同じく加工矩形動作経路最適化の概念図
図６は、同じく加工矩形分割の一例の概念図
図７は、同じく最適分割が困難な基板の例を示す平面図
図８は、同じく１つの加工矩形を複数に分割する手法の概念図
図９は、同じく加工矩形を分割する際に必要な最小距離を説明するための概念図
図１０は、同じく加工矩形分割の他の例の概念図
図１１は、同じく段の揃った配置の例を示す平面図
図１２は、同じく段の揃った配置の加工矩形分割の手順を示す流れ図
図１３は、同じく段の揃った配置の加工矩形分割の定式化の概念図
図１４は、同じく段の揃った配置の加工矩形分割の定式化の概念を示す線図
図１５は、同じく効率的ではない加工矩形分割の例を示す平面図
図１６は、同じく段の揃った矩形配置の加工矩形分割の場合の加工計画の手順を示す流れ図
図１７は、同じく縦方向優先と横方向優先による分割の後、良い方を選択する手法の概念を示す平面図
図１８は、同じく加工矩形内穴開け位置の疎密とＸＹステージ動作速度の関係の例を示す平面図
図１９は、同じく加工矩形の疎密の均一度による分割方向選択の手順を示す流れ図
図２０は、同じく加工矩形の疎密の一様性を調べるための累積頻度グラフの説明図
図２１は、同じく縦方向優先と横方向優先の組合せによる加工矩形分割の例を示す平面図
図２２は、同じく複数のパターン形状（大多数）とその他の少数の穴開け位置から構成される穴開け位置の配置例を示す平面図
図２３は、穴開け位置の加工矩形分割の工程を示す流れ図
図２４は、前記加工矩形分割工程における密な箇所の加工矩形配置処理を示す流れ図
図２５は、同じく大多数な箇所の加工矩形配置処理を示す流れ図
図２６は、穴開け位置の有無による点存在箇所の加工矩形化の説明図
図２７は、図２４の処理における格子分割及び格子の識別処理を示す流れ図
図２８は、穴開け位置の疎／密の階層分けの概念図
図２９は、穴開け位置の密な格子と疎な格子の分布の例を示す平面図
図３０は、図２５の処理における格子分割及び格子の識別処理を示す流れ図
図３１は、本発明による穴開け位置の大多数／少数のグループ分けの概念図
図３２は、図２４、図２５の処理における格子群矩形化処理を示す流れ図
図３３は、図２４の処理における格子群矩形位置の微調整処理を示す流れ図
図３４は、図２５の処理における格子群矩形位置の微調整処理を示す流れ図
図３５は、図２４、図２５の処理における格子群矩形の加工矩形による被覆（加工矩形の配置）処理を示す流れ図
図３６は、本発明による規則的な並びの配置の識別法の説明図
図３７は、同じく直線状配置の被覆に関する説明図
図３８は、同じく格子状配置の被覆に関する説明図
図３９は、同じく穴開け位置訪問順序決定とＸＹステージ等速動作最大化の手順の例を示す流れ図
図４０は、同じく他の例を示す流れ図
図４１は、同じく更に他の例を示す流れ図
図４２は、同じく更に他の例を示す流れ図
図４３は、同じく穴開け位置訪問順序決定とＸＹステージ等速動作最大化の手順の例を示す流れ図
図４４は、図４３の具体例を示す流れ図
図４５は、穴開け位置訪問の初期経路の説明図
図４６は、同じく分割幅と平均移動量の関係の例を示す線図
図４７は、同じく、ある穴開け位置訪問順序に対し実行可能な最大速度を算出する手順を示す流れ図
図４８は、同じくＸＹステージ等速最大速度を２分法で求める手法の概念図
図４９は、同じく実行可能性の説明図
図５０は、同じく最早開始及び最遅完了の時刻を求める計算例の説明図
図５１は、同じく２点間の移動に費やす時間のモデル例を示す説明図
図５２は、同じく低速側ＸＹステージ速度を求める手順を示す流れ図
図５３は、同じく高速側ＸＹステージ速度を求める手順を示す流れ図
図５４は、同じくＸＹステージ等速最大速度を比例法で求める手法の概念図
図５５は、同じく２交換近傍による経路更新の説明図
図５６は、同じく前方Ｏｒ−ｏｐｔ近傍による経路更新の概念図
図５７は、同じく後方Ｏｒ−ｏｐｔ近傍による経路更新の概念図
図５８は、同じく挿入近傍（反転無し）による経路更新の概念図
図５９は、同じく挿入近傍（反転有り）による経路更新の概念図
図６０は、同じくクロス交換近傍による２つの経路更新の概念図
図６１は、同じく２−ｏｐｔ＊近傍による２つの経路更新の概念図
図６２は、同じく加工位置訪問順序最適化並びに低速位置決め手段等速動作最大化工程の具体例を示す流れ図
図６３は、同じく実基板のある加工矩形でのある穴開け位置訪問順序でのＸＹステージとガルバノスキャナの動作曲線の例を示す線図
図６４は、同じく速度可変対応の概念図
図６５は、同じく密なシーケンスを見分ける手順を示す流れ図
図６６は、同じく速度可変対応の速度を示す線図
図６７は、同じく速度多重化の概念図
図６８は、同じく加工矩形間の動作の説明図
図６９は、同じく加工矩形動作経路最適化の説明図
図７０は、同じく加工矩形の訪問順序最適化と入出口最適決定の手順を示す流れ図
図７１は、同じく加工矩形の入出口決定と訪問順序最適化の手順を示す流れ図
図７２は、同じく加工矩形動作経路の簡単な設定法の概念図
図７３は、同じく加工計画の第２実施形態の処理手順を示す流れ図
図７４は、同じく別の構成例の概念図
図７５は、同じく目標位置の候補となる領域の説明図
図７６は、同じくＸＹステージの目標位置の設定の概念図
図７７は、同じく説明図
図７８は、同じく概念図
図７９は、本発明による加工計画の第３実施形態の処理手順を示す流れ図
【図１】
2003064107.tif 000010
【図２】
2003064107.tif 000011
【図３】
2003064107.tif 000012
【図４】
2003064107.tif 000013
【図５】
2003064107.tif 000014
【図６】
2003064107.tif 000015
【図７】
2003064107.tif 000016
【図８】
2003064107.tif 000017
【図９】
2003064107.tif 000018
【図１０】
2003064107.tif 000019
【図１１】
2003064107.tif 000020
【図１２】
2003064107.tif 000021
【図１３】
2003064107.tif 000022
【図１４】
2003064107.tif 000023
【図１５】
2003064107.tif 000024
【図１６】
2003064107.tif 000025
【図１７】
2003064107.tif 000026
【図１８】
2003064107.tif 000027
【図１９】
2003064107.tif 000028
【図２０】
2003064107.tif 000029
【図２１】
2003064107.tif 000030
【図２２】
2003064107.tif 000031
【図２３】
2003064107.tif 000032
【図２４】
2003064107.tif 000033
【図２５】
2003064107.tif 000034
【図２６】
2003064107.tif 000035
【図２７】
2003064107.tif 000036
【図２８】
2003064107.tif 000037
【図２９】
2003064107.tif 000038
【図３０】
2003064107.tif 000039
【図３１】
2003064107.tif 000040
【図３２】
2003064107.tif 000041
【図３３】
2003064107.tif 000042
【図３４】
2003064107.tif 000043
【図３５】
2003064107.tif 000044
【図３６】
2003064107.tif 000045
【図３７】
2003064107.tif 000046
【図３８】
2003064107.tif 000047
【図３９】
2003064107.tif 000048
【図４０】
2003064107.tif 000049
【図４１】
2003064107.tif 000050
【図４２】
2003064107.tif 000051
2003064107.tif 000052
【図４３】
2003064107.tif 000053
【図４４】
2003064107.tif 000054
【図４５】
2003064107.tif 000055
【図４６】
2003064107.tif 000056
【図４７】
2003064107.tif 000057
【図４８】
2003064107.tif 000058
【図４９】
2003064107.tif 000059
【図５０】
2003064107.tif 000060
【図５１】
2003064107.tif 000061
【図５２】
2003064107.tif 000062
【図５３】
2003064107.tif 000063
【図５４】
2003064107.tif 000064
【図５５】
2003064107.tif 000065
【図５６】
2003064107.tif 000066
【図５７】
2003064107.tif 000067
【図５８】
2003064107.tif 000068
【図５９】
2003064107.tif 000069
【図６０】
2003064107.tif 000070
【図６１】
2003064107.tif 000071
【図６２】
2003064107.tif 000072
2003064107.tif 000073
【図６３】
2003064107.tif 000074
【図６４】
2003064107.tif 000075
【図６５】
2003064107.tif 000076
【図６６】
2003064107.tif 000077
【図６７】
2003064107.tif 000078
【図６８】
2003064107.tif 000079
【図６９】
2003064107.tif 000080
【図７０】
2003064107.tif 000081
【図７１】
2003064107.tif 000082
【図７２】
2003064107.tif 000083
【図７３】
2003064107.tif 000084
【図７４】
2003064107.tif 000085
【図７５】
2003064107.tif 000086
【図７６】
2003064107.tif 000087
【図７７】
2003064107.tif 000088
【図７８】
2003064107.tif 000089
【図７９】
2003064107.tif 000090
【手続補正書】
【提出日】平成15年10月29日(2003.10.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２３
【補正方法】変更
【補正の内容】
【請求項２３】
前記各加工位置の時間枠を、
Ｘ又はＹである所定寸の加工矩形の低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺを用いて、
最早開始時刻はＴＳ＋ＰＺ／Ｖで、
最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ）／Ｖで定めることを特徴とする請求項２１に記載の加工計画方法。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２４
【補正方法】変更
【補正の内容】
【請求項２４】
前記各加工位置の時間枠を、
Ｘ又はＹである所定寸の加工矩形の低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺ、ＤＺより小さい所定の正又は０である値ＤＺＦ、ＤＺＢを用いて、
最早開始時刻はＴＳ＋（ＰＺ＋ＤＺＦ）／Ｖで、
最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ−ＤＺＢ）／Ｖで定めることを特徴とする請求項２１に記載の加工計画方法。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項７３
【補正方法】変更
【補正の内容】
【請求項７３】
前記各加工位置の時間枠を、
Ｘ又はＹである所定寸の加工矩形の低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺを用いて、
最早開始時刻はＴＳ＋ＰＺ／Ｖで、
最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ）／Ｖで定めるようにされていることを特徴とする請求項７１に記載の加工計画装置。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項７４
【補正方法】変更
【補正の内容】
【請求項７４】
前記各加工位置の時間枠を、
Ｘ又はＹである所定寸の加工矩形の低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺ、ＤＺより小さい所定の正又は０である値ＤＺＦ、ＤＺＢを用いて、
最早開始時刻はＴＳ＋（ＰＺ＋ＤＺＦ）／Ｖで、
最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ−ＤＺＢ）／Ｖで定めるようにされていることを特徴とする請求項７１に記載の加工計画装置。
【手続補正５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項８９
【補正方法】変更
【補正の内容】
【請求項８９】
前記加工位置訪問順序及び低速位置決め手段動作速度最適化手段が、先ず、矩形内の加工位置訪問順序を決定し、次いで、決定された経路における前記低速位置決め手段の等速動作を最速化するようにされている請求項５１に記載の加工計画装置。
【手続補正６】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９４
【補正方法】変更
【補正の内容】
【請求項９４】
前記低速位置決め手段動作経路最適化手段が、加工矩形の訪問順序を最適化した後に、各矩形の入出口を決定するようにされていることを特徴とする請求項５１又は９２に記載の加工計画装置。
【手続補正７】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９８
【補正方法】変更
【補正の内容】
【請求項９８】
ワーク上の加工実行箇所を、広範囲に移動させることが可能な低速位置決め手段と、Ｘ方向の辺長ＤＸ及びＹ方向の辺長ＤＹを持つ所定寸の加工エリア内の狭範囲に移動させることが可能な高速位置決め手段を協調動作させながら、ワーク上に散在する複数の加工位置を加工する際の加工計画装置であって、
加工位置を、Ｘ又はＹである加工時低速位置決め手段停止方向Ｚの辺長がＤＺ以下であるような矩形により分割する加工矩形分割手段と、
該加工矩形分割手段により決定された各加工矩形について、加工位置の訪問順序を最適化する加工位置訪問順序最適化手段と、
該加工位置訪問順序最適化手段により決定された加工位置訪問順序に対して、前記低速位置決め手段の動作パターンを決定する低速位置決め手段動作パターン決定手段と、
を含むことを特徴とする加工計画装置。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
な速度の最大値を求める、加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）であるようにしたものである。
又、前記加工位置訪問順序及び低速位置決め手段動作速度最適化工程（手段）は、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）の後、更に決定された加工位置に対して、加工位置の分布の密度に応じて動作速度を滑らかに変化させる加減速パターンを決定する速度パターン決定工程を行うようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）において、各加工位置の加工タイミングを最早開始時刻及び最遅完了時刻の間に規定する時間枠を、低速位置決め手段動作速度に基づいて定めるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）において、加工位置間の移動長を、加工位置間の移動量及び低速位置決め手段動作速度に基づいて定めるようにしたものである。
又、前記各加工位置の時間枠を、Ｘ又はＹである所定寸の加工矩形の低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺを用いて、最早開始時刻はＴＳ＋ＰＺ／Ｖで、最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ）／Ｖで定めるようにしたものである。
又、前記各加工位置の時間枠を、Ｘ又はＹである所定寸の加工矩形の低速位置決め手段動作方向Ｚの辺長ＤＺ、低速位置決め手段動作速度Ｖ、該当加工エリアの加工開始時刻ＴＳにおける加工位置Ｐから所定寸の加工エリアの最も近い辺までの距離ＰＺ、ＤＺより小さい所定の正又は０である値ＤＺＦ、ＤＺＢを用いて、最早開始時刻はＴＳ＋（ＰＺ＋ＤＺＦ）／Ｖで、最遅完了時刻はＴＳ＋（ＰＺ＋ＤＺ−ＤＺＢ）／Ｖで定


【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
めるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）において、各加工位置の加工開始時刻を、１つ前の加工位置における加工完了後、加工位置間の移動が完了した時刻が、最早開始時刻より早ければ最早開始時刻に、最早開始時刻以降であれば移動が完了した時刻に定めるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）が、加工位置訪問順序を発生させる加工位置訪問順序発生工程（手段）と、加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程（手段）によるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）が、加工位置訪問順序を発生させる加工位置訪問順序発生工程（手段）と、加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程（手段）と、低速位置決め手段動作速度を固定して加工位置訪問順序を改善する加工位置訪問順序改善工程（手段）と、を全て含むようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速度最大化工程（手段）は、加工位置訪問順序を発生させる加工位置訪問順序発生工程（手段）、加工位置訪問順序を固定して低速位置決め手段の等速動作速度を算出する低速位置決め手段動作速度算出工程（手段）、及び、低速位置決め手段動作速度を固定して加工位置訪問順序を改善する加工位置訪問順序改善工程（手段）と該低速位置決め手段動作速度算出工程（手段）とを１乃至複数回繰り返す、繰り返し改善工程（手段）、からなる工程（手段）であるようにしたものである。
又、前記加工位置訪問順序最適化並びに低速位置決め手段等速動作速




【国際調査報告】
2003064107.tif 000091
2003064107.tif 000092
2003064107.tif 000093
2003064107.tif 000094