(57)【要約】【課題】  複数の部品を吸着して基板に実装していく装着ヘッドを備える部品実装機を対象とした部品カセット並び決定方法であって、より短い時間で、かつ、より最適な実装順序を求めることができる部品カセット並び決定方法等を提供する。【解決手段】  全ての部品を実装するのに使用する最適な１以上のノズルセットを決定するノズルセット決定部３０５ａと、吸着ヘッドの上下回数が小さくなるように最適なノズルパターンおよびＺ配列を決定するノズルパターン・Ｚ配列決定部３０５ｂと、決定されたノズルパターンおよびＺ配列の下で（ノズルパターンとＺ配列を維持したまま）、実装順序を最適化する実装順序最適化部３０５ｃとを備える。【選択図】      図６
2005333098.tif 000002
【特許請求の範囲】
【請求項１】
部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機を対象とし、コンピュータにより部品カセットの並びを決定する部品カセット並び決定方法であって、
前記装着ヘッドには、部品を吸着するための吸着ノズルを最大Ｌ（≧２）個装着することができ、
最適化の対象となる複数の部品には、２以上の異なるタイプの吸着ノズルそれぞれで吸着され得る複数の種類の部品が含まれ、
前記装着ヘッドに装着される吸着ノズルの組み合わせを示すノズルセットを取得するノズルセット取得ステップと、
取得した前記ノズルセットに基づいて、部品カセットの並びを決定する部品配置決定ステップとを含み、
前記部品配置決定ステップは、
前記装着ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、取得した前記ノズルセットを維持したまま、前記部品の実装に必要な全てのタスクについて、前記装着ヘッドを構成する複数のヘッドごとに吸着ノズルのタイプを割り当てたノズルパターンを決定するノズルパターン決定サブステップと、
決定された前記ノズルパターンにおけるそれぞれの吸着ノズルに対して、未配置の部品カセットの中から収納された部品を吸着するための吸着ノズルのタイプが前記吸着ノズルと一致する部品カセットであって、かつ、実装に使用される部品の員数が最大である当該部品を収納した部品カセットを配置するという処理を繰り返し行うことにより、部品カセットの並びを決定する部品カセット並び決定サブステップとを含む
ことを特徴とする部品カセット並び決定方法。
【請求項２】
前記部品カセット並び決定サブステップでは、さらに、前記装着ヘッドに装着される吸着ノズルのタイプと一致するタイプの吸着ノズルが吸着時に使用される部品を収納した部品カセットが存在しない場合には、並びが決定されていない部品カセットのうち実装すべき部品の員数が多いものから順に部品カセットを選択し、選択された部品カセットを当該装着ヘッドに対応する位置に配置することにより部品カセットの並びを決定する
ことを特徴とする請求項１に記載の部品カセット並び決定方法。
【請求項３】
前記部品カセット並び決定サブステップでは、さらに、前記装着ヘッドに装着される吸着ノズルのタイプと一致するタイプの吸着ノズルが吸着時に使用される部品を収納した部品カセットが存在しない場合には、当該装着ヘッドと対応する位置に部品カセットを配置しない
ことを特徴とする請求項１に記載の部品カセット並び決定方法。
【請求項４】
部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機を対象とし、コンピュータにより部品カセットの並びを決定する部品カセット並び決定方法であって、
前記装着ヘッドには、部品を吸着するための吸着ノズルを最大Ｌ（≧２）個装着することができ、
最適化の対象となる複数の部品には、２以上の異なるタイプの吸着ノズルそれぞれで吸着され得る複数の種類の部品が含まれ、
前記装着ヘッドに装着される吸着ノズルの組み合わせを示すノズルセットを取得するノズルセット取得ステップと、
前記装着ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、取得した前記ノズルセットを維持したまま、前記部品の実装に必要な全てのタスクについて、前記装着ヘッドを構成する複数のヘッドごとに吸着ノズルのタイプを割り当てたノズルパターンを、前記ノズルの配置位置をタスク数に従ってソートすることにより決定するノズルパターン決定ステップと、
前記ノズルパターンにおけるそれぞれの吸着ノズルに対して、未配置の部品カセットの中から収納された部品を吸着するための吸着ノズルのタイプが前記吸着ノズルと一致する部品カセットであって、かつ、実装に使用される部品の員数が最大である当該部品を収納した部品カセットを配置するという処理を繰り返し行うことにより、部品カセットの並びを決定する部品配置決定ステップを含む
ことを特徴とする部品カセット並び決定方法。
【請求項５】
前記部品配置決定ステップでは、さらに、前記装着ヘッドに装着される吸着ノズルのタイプと一致するタイプの吸着ノズルが吸着時に使用される部品を収納した部品カセットが存在しない場合には、並びが決定されていない部品カセットのうち実装すべき部品の員数が多いものから順に部品カセットを選択し、選択された部品カセットを当該装着ヘッドに対応する位置に配置することにより部品カセットの並びを決定する
ことを特徴とする請求項４に記載の部品カセット並び決定方法。
【請求項６】
前記部品配置決定ステップでは、さらに、前記装着ヘッドに装着される吸着ノズルのタイプと一致するタイプの吸着ノズルが吸着時に使用される部品を収納した部品カセットが存在しない場合には、当該装着ヘッドと対応する位置に部品カセットを配置しない
ことを特徴とする請求項４に記載の部品カセット並び決定方法。
【請求項７】
さらに、前記ノズルパターンが複数存在する場合には、部品を同時吸着できる可能性が高いノズルパターンを順次選択する最適ノズルパターン選択ステップを含み、
前記部品配置決定ステップでは、前記最適ノズルパターン選択ステップで順次選択されるノズルパターンにおける吸着ノズルのタイプと、収納された部品を吸着するための吸着ノズルのタイプとが一致するように部品カセットの並びを決定する
ことを特徴とする請求項４〜６のいずれか１項に記載の部品カセット並び決定方法。
【請求項８】
さらに、前記部品配置決定ステップで決定された部品カセットの並びを初期解とし、前記吸着ノズルにより部品を吸着する際の前記装着ヘッドの上下動作の回数が最小となるような解を探索することにより、前記部品カセットの並びを最適化する部品カセット並び最適化ステップを含む
ことを特徴とする請求項４〜７のいずれか１項に記載の部品カセット並び決定方法。
【請求項９】
さらに、前記部品配置決定ステップで決定された部品カセットの並びを初期解とし、前記吸着ノズルにより部品を吸着する際の前記装着ヘッドの移動量が最小となるような解を探索することにより、前記部品カセットの並びを最適化する部品カセット並び最適化ステップを含む
ことを特徴とする請求項４〜７のいずれか１項に記載の部品カセット並び決定方法。
【請求項１０】
さらに、前記部品配置決定ステップで決定された部品カセットの並びを初期解とし、前記吸着ノズルにより部品を吸着する際の吸着時間が最小となるような解を探索することにより、前記部品カセットの並びを最適化する部品カセット並び最適化ステップを含む
ことを特徴とする請求項４〜７のいずれか１項に記載の部品カセット並び決定方法。
【請求項１１】
さらに、前記ノズルパターン決定ステップで決定されたノズルパターンを初期解とし、前記吸着ノズルにより部品を吸着する際の前記装着ヘッドの上下動作の回数が最小となるような解を探索することにより、前記ノズルパターンを最適化するノズルパターンを最適化ステップを含む
ことを特徴とする請求項４〜１０のいずれか１項に記載の部品カセット並び決定方法。
【請求項１２】
さらに、前記ノズルパターン決定ステップで決定されたノズルパターンを初期解とし、前記吸着ノズルにより部品を吸着する際の前記装着ヘッドの移動量が最小となるような解を探索することにより、前記ノズルパターンを最適化するノズルパターンを最適化ステップを含む
ことを特徴とする請求項４〜１０のいずれか１項に記載の部品カセット並び決定方法。
【請求項１３】
さらに、前記ノズルパターン決定ステップで決定されたノズルパターンを初期解とし、前記吸着ノズルにより部品を吸着する際の吸着時間が最小となるような解を探索することにより、前記ノズルパターンを最適化するノズルパターンを最適化ステップを含む
ことを特徴とする請求項４〜１０のいずれか１項に記載の部品カセット並び決定方法。
【請求項１４】
部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機を対象とし、コンピュータにより部品カセットの並びを決定する部品カセット並び決定装置であって、
前記装着ヘッドには、部品を吸着するための吸着ノズルを最大Ｌ（≧２）個装着することができ、
最適化の対象となる複数の部品には、２以上の異なるタイプの吸着ノズルそれぞれで吸着され得る複数の種類の部品が含まれ、
前記装着ヘッドに装着される吸着ノズルの組み合わせを示すノズルセットを取得するノズルセット取得手段と、
取得した前記ノズルセットに基づいて、部品カセットの並びを決定する部品配置決定手段とを備え、
前記部品配置決定手段は、
前記装着ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、取得した前記ノズルセットを維持したまま、前記部品の実装に必要な全てのタスクについて、前記装着ヘッドを構成する複数のヘッドごとに吸着ノズルのタイプを割り当てたノズルパターンを決定するノズルパターン決定部と、
決定された前記ノズルパターンにおけるそれぞれの吸着ノズルに対して、未配置の部品カセットの中から収納された部品を吸着するための吸着ノズルのタイプが前記吸着ノズルと一致する部品カセットであって、かつ、実装に使用される部品の員数が最大である当該部品を収納した部品カセットを配置するという処理を繰り返し行うことにより、部品カセットの並びを決定する部品カセット並び決定部とを有する
ことを特徴とする部品カセット並び決定装置。
【請求項１５】
部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機を対象とし、コンピュータにより部品カセットの並びを決定する部品カセット並び決定装置であって、
前記装着ヘッドには、部品を吸着するための吸着ノズルを最大Ｌ（≧２）個装着することができ、
最適化の対象となる複数の部品には、２以上の異なるタイプの吸着ノズルそれぞれで吸着され得る複数の種類の部品が含まれ、
前記装着ヘッドに装着される吸着ノズルの組み合わせを示すノズルセットを取得するノズルセット取得手段と、
前記装着ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、取得した前記ノズルセットを維持したまま、前記部品の実装に必要な全てのタスクについて、前記装着ヘッドを構成する複数のヘッドごとに吸着ノズルのタイプを割り当てたノズルパターンを、前記ノズルの配置位置をタスク数に従ってソートすることにより決定するノズルパターン決定部と、
前記ノズルパターンにおけるそれぞれの吸着ノズルに対して、未配置の部品カセットの中から収納された部品を吸着するための吸着ノズルのタイプが前記吸着ノズルと一致する部品カセットであって、かつ、実装に使用される部品の員数が最大である当該部品を収納した部品カセットを配置するという処理を繰り返し行うことにより、部品カセットの並びを決定する部品配置決定部とを備える
ことを特徴とする部品カセット並び決定装置。
【請求項１６】
部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機であって、
請求項１〜１３のいずれか１項に記載の部品カセット並び決定方法によって並びが決定された部品カセットより部品を吸着し、基板上に装着する
ことを特徴とする部品実装機。
【請求項１７】
部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機を対象とし、コンピュータにより部品の実装順序を最適化するプログラムであって、
請求項１〜１３のいずれか１項に記載の部品カセット並び決定方法に含まれるステップをコンピュータに実行させる
ことを特徴とするプログラム。
【請求項１８】
部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機を対象とし、コンピュータにより部品の実装順序を最適化するプログラムを記録したコンピュータ読取可能な記録媒体であって、請求項１７に記載のプログラムを記録した
ことを特徴とするコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子部品をプリント配線基板等の基板に実装する部品実装機を対象として最適な部品の実装順を決定する方法等に関し、特に、複数の部品を吸着して基板に装着する装着ヘッドを備える部品実装機を対象とする部品実装順序の最適化に関する。
【背景技術】
【０００２】
電子部品をプリント配線基板等の基板に実装する部品実装機では、より短いタクト（実装時間）を実現するために、対象部品の実装順序について、最適化が行われる。最近では、電子機器の機種の多様化等に伴い、複数の部品を同時に装着ヘッドに吸着して基板に実装するというギャングピックアップ方式の装着ヘッドを備える多機能型の部品実装機の需要が増加し、このような部品実装機を対象とした部品実装順序の各種最適化手法が提案されている（例えば、特許文献１および２参照）。
【０００３】
上記特許文献１および２には、装着ヘッドに部品を満載させること、つまり、タスクごとに装着ヘッドに同時吸着される部品の数を最大化させることを優先して部品の実装順序を最適化するという方法が開示されている。ここで、タスクとは、装着ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作、または、１回分の一連動作によって実装される部品群を意味する。このような最適化によって、全ての部品の実装に要するタスクの数が最小化されるので、より短いタクトで部品の実装が完了するというものである。
【特許文献１】特開２００２−５０９００号公報
【特許文献２】特開２００２−１７１０９７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、このような従来の最適化方法は、部品実装機にセットしておく部品カセットの並び（Ｚ配列）、ノズルステーション上のノズル配置、ノズルパターン、実装順序（基板上の実装点を考慮した部品の実装順序）という各種最適化条件を同時に決定していくために、最適化処理に時間がかかるという問題がある。具体的には、上記最適化条件を変更しては、タクトや各種制約条件の具備をチェックし、全体として最適な条件を探索するという手法であるために、例えば、ノズルパターンを組み替えるたびにタクトを計算する必要があり、最適化処理に時間がかかる。ここで、ノズルパターンは、実装順序に従って並べられた各タスクについて、個々のヘッドごとに吸着ノズルのタイプが決定された吸着ノズル列のことである。
【０００５】
また、最適化条件を変更するために、入れ替えの対象となる装着ヘッドのヘッド位置やタスク等を乱数で決定するために、必ずしも最適な解が探索されるとは限らないという問題もある。
【０００６】
そこで、本発明は、複数の部品を吸着して基板に実装していく装着ヘッドを備える部品実装機を対象とした部品カセット並び決定方法であって、より短い時間で、かつ、より最適な実装順序を求めることができる部品カセット並び決定方法等を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本願の発明者らは、全タクトに占める部品実装機の動作を分析したところ、装着ヘッドの上下動作の回数（吸着回数）を減少させることにより部品の実装時間を減少させることができるとの知見を得た。
【０００８】
すなわち、本発明に係る部品カセット並び決定方法は、部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機を対象とし、コンピュータにより部品の実装順序を最適化する部品カセット並び決定方法であって、前記装着ヘッドには、部品を吸着するための吸着ノズルを最大Ｌ（≧２）個装着することができ、最適化の対象となる複数の部品には、２以上の異なるタイプの吸着ノズルそれぞれで吸着され得る複数の種類の部品が含まれ、前記装着ヘッドに装着される吸着ノズルの組み合わせを示すノズルセットを取得するノズルセット取得ステップと、取得した前記ノズルセットに基づいて、部品カセットの並びを決定する部品配置決定ステップとを含むことを特徴とする。好ましくは、前記部品配置決定ステップは、前記装着ヘッドによる部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の一連動作によって実装される部品群をタスクとした場合に、取得した前記ノズルセットを維持したまま、前記部品の実装に必要な全てのタスクについて、前記装着ヘッドを構成する複数のヘッドごとに吸着ノズルのタイプを割り当てたノズルパターンを決定するノズルパターン決定サブステップと、決定された前記ノズルパターンにおけるそれぞれの吸着ノズルに対して、未配置の部品カセットの中から収納された部品を吸着するための吸着ノズルのタイプが前記吸着ノズルと一致する部品カセットであって、かつ、実装に使用される部品の員数が最大である当該部品を収納した部品カセットを配置するという処理を繰り返し行うことにより、部品カセットの並びを決定する部品カセット並び決定サブステップとを含むことを特徴とする。
【０００９】
この方法によると、ノズルパターンにおける吸着ノズルのタイプと、収納された部品を吸着するための吸着ノズルのタイプとが一致するように部品カセットの並びを決定することができる。このため、装着ヘッドの１回の上下動作において、多くの部品を同時吸着できる可能性が高くなる。このため、装着ヘッドの上下動作の回数（吸着回数）を減少させることができ、それにより、部品の実装時間を減少させることができる。よって、最適な実装順序を求めることができる。
【００１０】
好ましくは、上述の部品カセット並び決定方法は、さらに、前記部品配置決定ステップで決定された部品カセットの並びを初期解とし、前記吸着ノズルにより部品を吸着する際の前記装着ヘッドの上下動作の回数が最小となるような解を探索することにより、前記部品カセットの並びを最適化する部品カセット並び最適化ステップを含むことを特徴とする。
【００１１】
上述の方法により求められた部品カセットの並びは、装着ヘッドの上下動作の回数が小さくなるように選択されている。このため、初期解の時点で、最適解に近い解が求められている。よって、部品カセットの並びの最適化を短時間で求めることができる。よって、短い時間で実装順序を求めることができる。
【００１２】
本発明の他の局面に係る部品カセット並び決定方法は、部品を収納した部品カセットの並びから、最大Ｌ（≧２）個の部品を吸着し、基板に実装していく装着ヘッドを備える部品実装機を対象とし、コンピュータにより部品の実装順序を最適化する部品カセット並び決定方法であって、前記装着ヘッドには、部品を吸着するための吸着ノズルを最大Ｌ（≧２）個装着することができ、最適化の対象となる複数の部品には、２以上の異なるタイプの吸着ノズルそれぞれで吸着され得る複数の種類の部品が含まれ、前記装着ヘッドに装着される吸着ノズルの組み合わせを示すノズルセットを取得するノズルセット取得ステップと、取得した前記ノズルセットに基づいて、ノズルパターンを決定するノズルパターン決定ステップとを含むことを特徴とする。好ましくは、上述の部品カセット並び決定方法は、さらに、取得した前記ノズルセットに基づいて、部品カセットの並びを決定する部品配置決定ステップを含むことを特徴とする。
【００１３】
この方法によると、ノズルパターンにおける吸着ノズルのタイプと、収納された部品を吸着するための吸着ノズルのタイプとが一致するように部品カセットの並びを決定することができる。このため、装着ヘッドの１回の上下動作において、多くの部品を同時吸着できる可能性が高くなる。このため、装着ヘッドの上下動作の回数（吸着回数）を減少させることができ、それにより、部品の実装時間を減少させることができる。よって、最適な実装順序を求めることができる。
【００１４】
なお、本発明は、このような特徴的なステップを含む部品カセット並び決定方法として実現することができるだけでなく、特徴的なステップを手段とする部品実装順序最適化装置として実現したり、特徴的な命令を含むプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。
【発明の効果】
【００１５】
本発明によると、より短い時間で、かつ、より最適な実装順序を求めることができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態について図面を用いて詳細に説明する。
図１は、本発明に係る部品実装システム１０全体の構成を示す外観図である。この部品実装システム１０は、上流から下流に向けて回路基板２０を送りながら電子部品を実装していく生産ラインを構成する複数の部品実装機１００、２００と、生産の開始等にあたり、各種データベースに基づいて必要な電子部品の実装順序を最適化し、得られたＮＣ（Numeric Control）データを部品実装機１００、２００にダウンロードして設定・制御する
最適化装置３００とからなる。
【００１７】
部品実装機１００は、同時かつ独立して、または、お互いが協調して（または、交互動作にて）部品実装を行う２つのサブ設備（前サブ設備１１０および後サブ設備１２０）を備える。各サブ設備１１０（１２０）は、直交ロボット型装着ステージであり、部品テープを収納する最大４８個の部品カセット１１４の配列からなる２つの部品供給部１１５ａおよび１１５ｂと、それら部品カセット１１４から最大１０個の部品を吸着し基板２０に装着することができる１０個の吸着ノズル（以下、単に「ノズル」ともいう。）を有する装着ヘッド１１２（１０ノズルヘッド）と、その装着ヘッド１１２を移動させるＸＹロボット１１３と、装着ヘッド１１２に吸着された部品の吸着状態を２次元または３次元的に検査するための部品認識カメラ１１６と、トレイ部品を供給するトレイ供給部１１７等を備える。
【００１８】
なお、「部品テープ」とは、現実は、同一部品種の複数の部品がテープ（キャリアテープ）上に並べられたものであり、リール（供給リール）等に巻かれた状態で供給される。主に、チップ部品と呼ばれる比較的小さいサイズの部品を部品実装機に供給するのに使用される。ただし、最適化処理においては、「部品テープ」とは、同一の部品種に属する部品の集合（それら複数個の部品が仮想的なテープ上に並べられたもの）を特定するデータであり、「部品分割」と呼ばれる処理によって、１つの部品種に属する部品群（1本の部品テープ）が複数本の部品テープに分割される場合がある。また、部品テープによって供給される部品をテーピング部品と呼ぶ。
【００１９】
この部品実装機１００は、ほぼ全ての種類の電子部品（装着対象となる部品として、０．６ｍｍ×０．３ｍｍのチップ抵抗から２００ｍｍのコネクタまで）を装着できるように設計されており、この部品実装機１００を必要台数だけ並べることで、生産ラインを構成することができる。
【００２０】
図２は、図１に示された部品実装機１００の主要な構成を示す平面図である。シャトルコンベヤ１１８は、トレイ供給部１１７から取り出された部品を載せて、装着ヘッド１１２による吸着可能な所定位置まで運搬するための移動テーブル（移動コンベア）である。ノズルステーション１１９は、各種形状の部品種に対応する交換用の吸着ノズルが置かれるテーブルである。
【００２１】
各サブ設備１１０（または１２０）を構成する２つの部品供給部１１５ａおよび１１５ｂは、それぞれ、部品認識カメラ１１６を挟んで左右に配置されている。したがって、部品供給部１１５ａまたは１１５ｂにおいて部品を吸着した装着ヘッド１１２は、部品認識カメラ１１６を通過した後に、基板２０の実装点に移動し、吸着した全ての部品を順次装着していく動作を繰り返す。
【００２２】
なお、各サブ設備に向かって左側の部品供給部１１５ａを「左ブロック」、右側の部品供給部１１５ｂを「右ブロック」とも呼ぶ。また、装着ヘッド１１２による部品の吸着・移動・装着という一連の動作の繰り返しにおける１回分の動作（吸着・移動・装着）、または、そのような１回分の動作によって実装される部品群）を「タスク」と呼ぶ。例えば、本部品実装機１００が備える装着ヘッド１１２によれば、１個のタスクによって実装される部品の最大数は１０となる。なお、ここでいう「吸着」には、ヘッドが部品を吸着し始めてから移動するまでの全ての吸着動作が含まれ、例えば、１回の吸着動作（装着ヘッド１１２の上下動作）で１０個の部品を同時に吸着する場合だけでなく、複数回の吸着動作によって１０個の部品を吸着する場合も含まれる。
【００２３】
図３（ａ）は、装着ヘッド１１２と部品カセット１１４の位置関係を示す模式図である。この装着ヘッド１１２は、「ギャングピックアップ方式」と呼ばれる作業ヘッドであり、独立して部品の吸着・装着を行う最大１０個の吸着ノズル１１２ａ〜１１２ｂ（向かって左端に装着された第１番目の吸着ノズル１１２ａから右端に装着された第１０番目の吸着ノズル１１２ｂまでの合計１０個の吸着ノズル）が着脱可能であり、最大１０個の部品カセット１１４それぞれから部品を同時に（１回の上下動作で）吸着することができる。つまり、装着ヘッド１１２は、部品供給部１１５ａおよび１１５ｂに移動し、部品を吸着する。このとき、例えば、一度に１０個の部品を同時に吸着できないときは、吸着位置を移動させながら複数回、吸着上下動作を行うことで、最大１０個の部品を吸着することができる。
【００２４】
なお、装着ヘッド１１２に装着される１０個の吸着ノズル１１２ａ〜１１２ｂの位置（ヘッド位置）を、部品供給部１１５ａおよび１１５ｂから装着ヘッド１１２を見た場合の装着ヘッド１１２の左端より、ヘッド番号１（Ｈ１）、ヘッド番号２（Ｈ２）、…、ヘッド番号１０（Ｈ１０）と呼ぶ。また、本発明の部品実装順序最適化方法は、図３（ａ）に示されるような一列に吸着ノズルが並べられた一連式装着ヘッドだけに限られず、図３（ｂ）に示されるような２列に吸着ノズルが並べられた２連式装着ヘッドにも適用することができる。
【００２５】
部品カセット１１４の種類には、「シングルカセット」と呼ばれるタイプと、「ダブルカセット」と呼ばれるタイプがある。「シングルカセット」と呼ばれる部品カセット１１４には１つの部品テープだけが装填され、「ダブルカセット」と呼ばれる部品カセット１１４には２つの部品テープ（ただし、送りピッチ（２ｍｍまたは４ｍｍ）が同一の部品テープに限られる）が装填される。また、部品供給部１１５ａおよび１１５ｂにおける部品カセット１１４（または、部品テープ）の位置を「Ｚ軸上の値」または「Ｚ軸上の位置」と呼び、部品供給部１１５ａの最左端を「１」とする連続番号等が用いられる。したがって、テーピング部品の並びを決定することは、部品種（または、部品テープ、部品テープを収納した部品カセット１１４）の並び、つまり、Ｚ配列を決定することに等しい。
【００２６】
図４は、装着ヘッド１１２に装着される吸着ノズル１１２ａ〜１１２ｂの例を示す外観図である。本図に示されるように、吸着ノズルの種類としては、吸着する部品のサイズや重量に応じて、複数のタイプ（Ｓ，Ｍ，Ｌなど）が用意されている。装着ヘッド１１２は、部品の吸着に必要なノズルが装着ヘッド１１２にないときには、その吸着ノズルが置かれたノズルステーション１１９へ移動し、そこでノズル交換を行ったうえで、部品カセット１１４へ移動し、部品を吸着する。
【００２７】
図５は、テーピング部品の例を示す図である。テーピング部品は、図５（ａ）、（ｂ）、（ｃ）、（ｄ）に示される各種チップ形電子部品４２３ａ〜４２３ｄを図５（ｅ）に示されるキャリアテープ４２４に一定間隔で複数個連続的に形成された収納凹部４２４ａに収納し、この上面にカバーテープ４２５を貼付けて包装し、供給用リール４２６に所定の数量分を巻回したテーピング形態（部品テープ）でユーザに供給される。
【００２８】
図６は、本発明の実施の形態における最適化装置３００ａ、つまり、図１に示された最適化装置の一構成例を示すブロック図である。この最適化装置３００ａは、生産ラインを構成する各設備の仕様等に基づく各種制約の下で、対象となる基板の部品実装におけるラインタクト（ラインを構成するサブ設備ごとのタクトのうち、最大のタクト）を最小化するように、部品実装用ＣＡＤ装置等から与えられた全ての部品を対象として、各サブ設備で実装すべき部品および各サブ設備における部品の実装順序を決定し、最適なＮＣデータを生成するコンピュータ装置であり、演算制御部３０１、表示部３０２、入力部３０３、メモリ部３０４、最適化プログラム格納部３０５、通信Ｉ／Ｆ（インターフェース）部３０６およびデータベース部３０７等から構成される。
【００２９】
この最適化装置３００ａは、本発明に係る最適化プログラムをパーソナルコンピュータ等の汎用のコンピュータシステムが実行することによって実現され、部品実装機１００と接続されていない状態で、スタンドアローンのシミュレータ（部品実装順序の最適化ツール）としても機能する。
【００３０】
演算制御部３０１は、ＣＰＵ（Central Processing Unit）や数値プロセッサ等であり、ユーザからの指示等に従って、最適化プログラム格納部３０５からメモリ部３０４に必要なプログラムをロードして実行し、その実行結果に従って、各構成要素３０２〜３０７を制御する。
【００３１】
表示部３０２はＣＲＴ（Cathode-Ray Tube）やＬＣＤ（Liquid Crystal Display）等であり、入力部３０３はキーボードやマウス等であり、これらは、演算制御部３０１による制御の下で、本最適化装置３００ａと操作者とが対話する等のために用いられる。
【００３２】
通信Ｉ／Ｆ部３０６は、ＬＡＮ（Local Area Network）アダプタ等であり、本最適化装置３００ａと部品実装機１００、２００との通信等に用いられる。メモリ部３０４は、演算制御部３０１による作業領域を提供するＲＡＭ（Random Access Memory）等である。
【００３３】
データベース部３０７は、この最適化装置３００ａによる最適化処理に用いられる入力データ（実装点データ３０７ａ、部品ライブラリ３０７ｂおよび実装装置情報３０７ｃ等）や最適化によって生成された実装点データ等を記憶するハードディスク等である。
【００３４】
図７〜図９は、それぞれ、実装点データ３０７ａ、部品ライブラリ３０７ｂおよび実装装置情報３０７ｃの例を示す図である。
実装点データ３０７ａは、実装の対象となる全ての部品の実装点を示す情報の集まりである。図７に示されるように、１つの実装点ｐiは、部品種ｃi、Ｘ座標ｘi、Ｙ座標ｙi、制御データφiからなる。ここで、「部品種」は、図８に示される部品ライブラリ３０７ｂにおける部品名に相当し、「Ｘ座標」および「Ｙ座標」は、実装点の座標（基板上の特定位置を示す座標）であり、「制御データ」は、その部品の実装に関する制約情報（使用可能な吸着ノズルのタイプ、装着ヘッド１１２の最高移動速度等）である。なお、最終的に求めるべきＮＣデータとは、ラインタクトが最小となるような実装点の並びである。
【００３５】
部品ライブラリ３０７ｂは、部品実装機１００、２００が扱うことができる全ての部品種それぞれについての固有の情報を集めたライブラリであり、図８に示されるように、部品種ごとの部品サイズ、タクト（一定条件下における部品種に固有のタクト）、その他の制約情報（使用可能な吸着ノズルのタイプ、部品認識カメラ１１６による認識方式、装着ヘッド１１２の最高速度比等）からなる。なお、本図には、参考として、各部品種の部品の外観も併せて示されている。
【００３６】
実装装置情報３０７ｃは、生産ラインを構成する全てのサブ設備ごとの装置構成や上述の制約等を示す情報であり、図９に示されるように、装着ヘッドのタイプ等に関するヘッド情報、装着ヘッドに装着され得る吸着ノズルのタイプ等に関するノズル情報、部品カセット１１４の最大数等に関するカセット情報、トレイ供給部１１７が収納しているトレイの段数等に関するトレイ情報等からなる。これらの情報は、以下のように呼ばれるデータである。つまり、設備オプションデータ（サブ設備毎）、リソースデータ（設備毎で利用可能なカセット本数とノズル本数）、ノズルステーション配置データ（ノズルステーション付きのサブ設備毎）、初期ノズルパターンデータ（サブ設備毎）、Ｚ軸配置データ（サブ設備毎）等である。
【００３７】
最適化プログラム格納部３０５は、本最適化装置３００ａの機能を実現する各種最適化プログラムを記憶しているハードディスク等である。最適化プログラムは、部品の実装順序を最適化するプログラムであり、機能的に（演算制御部３０１によって実行された場合に機能する処理部として）、ノズルセット決定部３０５ａ、ノズルパターン・Ｚ配列決定部３０５ｂおよび実装順序最適化部３０５ｃから構成される。
【００３８】
ノズルセット決定部３０５ａは、全ての部品を実装するのに使用する最適な１以上のノズルセットを決定する処理部である。ここで、ノズルセットとは、部品の実装のために装着ヘッド１１２に装着される吸着ノズルの組み合わせであり、１０ノズルヘッドの場合、１０個以下の吸着ノズルの種類および個数で特定される。たとえば、ノズルセットの一例として、２個のＳタイプの吸着ノズルと８個のＭタイプの吸着ノズルからなる組み合わせである。このとき、各吸着ノズルが装着される装着ヘッド１１２のヘッド位置は限定されない。このノズルセット決定部３０５ａは、装着ヘッド１１２による吸着ノズルの交換回数（ノズル交換回数）および全部品を実装するのに必要なタスクの数（タスク数）の観点から、より短い時間で全部品の実装を終えることが可能なノズルセットを特定する。
【００３９】
ノズルパターン・Ｚ配列決定部３０５ｂは、ノズルセット決定部３０５ａによって決定されたノズルセットから、最適なノズルパターンおよびＺ配列を決定する。このノズルパターン・Ｚ配列決定部３０５ｂは、ノズルセット決定部３０５ａで決定されたノズルセットについて、各ノズルセットを構成する各種吸着ノズルの位置（装着ヘッド１１２におけるヘッド位置）を決定する（吸着ノズルのタイプと装着ヘッド１１２のヘッド位置とを具体的に対応づける）とともに、ノズルセットの単位で並びを決定することで、ノズルパターンを決定する。また、ノズルパターン・Ｚ配列決定部３０５ｂは、ノズルパターンを決定するのと同時にＺ配列を決定する。
【００４０】
実装順序最適化部３０５ｃは、ノズルパターン・Ｚ配列決定部３０５ｂで決定されたノズルパターンおよびＺ配列の下で（ノズルパターンとＺ配列を維持したまま）、実装順序を最適化し、最終的な成果としてのＮＣデータを生成する。ここでの実装順序の最適化とは、ノズルパターン、Ｚ配列が固定された状況下で、基板上の各実装点を最適に順序付けすることである。なお、実装順序の最適化方法については、各種方法が提案されており、本願の主眼ではない。このため、その詳細な説明はここでは省略する。
【００４１】
このように、最適化プログラムは、ノズルセット決定部３０５ａにより、ノズルセットを決定した後に、ノズルパターン・Ｚ配列決定部３０５ｂにより、ノズルパターンおよびＺ配列を決定し、実装順序最適化部３０５ｃにより、残る実装順序の最適化を行っている。よって、ノズルパターンおよびＺ配列を同時に決定しているため、なるべく、１回の吸着動作で１０個の部品を同時に吸着できるように、部品カセットの並びを決定することができる。このようにすることにより、装着ヘッド１１２の上下動作の回数（吸着回数）を減少させることができ、より最適な実装順序を探索することができる。
【００４２】
次に、以上のように構成された最適化装置３００ａの動作について説明する。
図１０は、ノズルセット決定部３０５ａによるノズルセットの決定手順を示すフローチャートである。ノズルセット決定部３０５ａは、まず、実装の対象となる部品の総員数と装着ヘッド１１２のヘッド数（装着ヘッド１１２に装着されている吸着ノズルの個数、つまり、図３に示された装着ヘッドの場合であれば、１０）から、理想的な最小タスク数Ｘminを算出する（Ｓ１００）。たとえば、いま、実装の対象となる部品が、Ｓタイプの吸着ノズルで実装される部品（このような部品を単に「Ｓタイプの部品」ともいう。）が５０個と、Ｍタイプの吸着ノズルで実装される部品（このような部品を単に「Ｍタイプの部品」ともいう。）が１６７個の合計２１７個とし、装着ヘッドのヘッド数が５とすると、
（５０＋１６７）／５＝４３．４
より、小数点以下を切り上げ、
Ｘmin＝４４
と、算出する。これは、可能な限り装着ヘッド１１２に部品を満載させた状態で部品を実装した場合であっても、全ての部品を実装するのに、最低、４４回のタスクが必要となることを意味する。
【００４３】
次に、ノズルセット決定部３０５ａは、ノズル交換回数Ｎを０から１ずつインクリメントしながら、各ノズル交換回数Ｎにおいて全部品を実装するのに必要なノズルセットとタスク数ＸNを特定する（Ｓ１０１〜Ｓ１０４）。
【００４４】
具体的には、まず、ノズル交換回数Ｎを０（ノズルセットの数を１）とし（Ｓ１０１）、その場合におけるノズルセットとタスク数ＸNを特定する（Ｓ１０２）。なお、ノズル交換回数Ｎとノズルセットの数（ノズルセットの種類）ｎとは、
ｎ＝Ｎ＋１
の関係にある。たとえば、ノズルセット数が１の場合には、装着ヘッド１１２に最初に装着したノズルセットのまま全部品を実装するので、ノズル交換回数Ｎは０となる。また、ノズルセット数が２の場合には、実装の途中において、最初のノズルセットから第２番目のノズルセットに交換する必要があるので、ノズル交換回数Ｎは１となる。
【００４５】
また、このノズルセットとタスク数ＸNの特定（Ｓ１０２）については、後述するように、最小タスク数Ｘminから順に１ずつ増加させながら、全部品の実装が可能か否かの検討（可能解の検討）を行うので、より少ないタスク数で全部品を実装することが可能なノズルセット、および、そのようなタスク数が優先的に決定される。
【００４６】
続いて、後述する一定の終了条件が満たされたか否かを判断し（Ｓ１０３）、そうでない場合には（Ｓ１０３でＮｏ）、ノズル交換回数Ｎを１だけ増加させ（Ｓ１０４）、今度は、ノズル交換回数Ｎが１回（ノズルセット数が２個）において全部品を実装するのに必要なノズルセットとタスク数ＸNとを特定する（Ｓ１０２）。
【００４７】
このようにして、ノズル交換回数Ｎを１ずつインクリメントしながら（Ｎ＝０、１、…）、タスク数ＸNを特定するという処理を繰り返し（Ｓ１０２〜Ｓ１０４）、もし、終了条件が満たされた場合には（Ｓ１０３でＹｅｓ）、このような探索を終了し、最後に、これまでの探索で特定されたノズル交換回数Ｎとタスク数ＸNとの組の中から、一定の評価関数を用いることで、最も少ない時間で部品の実装が完了する組を特定し、特定した組のノズルセットを最適なノズルセットと決定する（Ｓ１０５）。
【００４８】
なお、ステップＳ１０３における終了条件とは、特定したタスク数ＸNが最小タスク数Ｘminに一致した場合、ノズル交換回数Ｎを増加させてもタスク数ＸNが減少しない場合などである。つまり、ノズル交換回数Ｎを増加させても、後述する評価値が小さくなる可能性がないことが明らかとなった状態である。
【００４９】
図１１は、図１０におけるステップＳ１０５（最適なノズルセットを特定）の手順を説明する図である。ここでは、ノズル交換回数Ｎとタスク数ＸNとの組が３組（Ｎ＝０，１，２）求められたケースの例が示されている。ノズルセット決定部３０５ａは、３つの組について、ノズル交換回数Ｎとタスク数ＸNとを図示された評価関数に代入することで、評価値Ｓ0、Ｓ1、Ｓ2を算出し、それら評価値Ｓ0、Ｓ1、Ｓ2の中から最小のものを特定し、そのノズル交換回数Ｎに対応するノズルセットを最適なノズルセットと決定する。
【００５０】
なお、図示された評価関数は、ノズル交換に要する時間とタスクの実行に要する時間の合計値に相当する値を算出する関数である。なお、評価関数中のｈは、１回のノズル交換に要する時間をタスク数に換算する係数であり、例えば、２などの定数である。
【００５１】
このようにして、ノズルセット決定部３０５ａによって、ノズル交換に要する時間と全てのタスクの実行に要する時間の合計が最小となるようなノズルセットが決定される。
図１２は、図１０におけるステップＳ１０２（ノズルセットとタスク数ＸNの特定）の
詳細な手順、つまり、与えられたノズル交換回数Ｎの下で（図１０のステップＳ１０１）、全ての部品を実装するのに必要なタスク数ＸNを特定する手順を示すフローチャートである。ノズルセット決定部３０５ａは、まず、初期設定として、タスク数ＸNが最小タスク数Ｘminに等しいと仮定し（Ｓ１１０）、可能解か否かを検討する（Ｓ１１１）。つまり、与えられたノズル交換回数Ｎの下で、全ての部品をＸmin回のタスクで実装することが可能か否かを検討する。
【００５２】
その結果、可能解でなければ（Ｓ１１１でＮｏ）、タスク数ＸNを１だけ増加させ（Ｓ１１４）、再び、可能解か否かの検討を繰り返す（Ｓ１１１）。一方、可能解であれば、その時のタスク数ＸNを、与えられたノズル交換回数Ｎに対応するタスク数ＸNと決定し（Ｓ１１３）、終了する。
【００５３】
このように、ノズルセット決定部３０５ａは、最小タスク数Ｘminから１ずつインクリメントしながら、与えられたノズル交換回数Ｎの下で、全部品の実装に必要となるタスク数ＸNを特定する。
【００５４】
図１３は、図１２におけるステップＳ１１１（可能解か否かの検討）の詳細な手順、つまり、ノズル交換回数Ｎとタスク数ＸNとが与えられた場合に、そのような条件を満たす実装が可能か否かを判定する手順を示すフローチャートである。ノズルセット決定部３０５ａは、まず、対象となる全部品を吸着ノズルのタイプごとのグループ（例えば、Ｓタイプの部品が５０個と、Ｍタイプの部品が１６７個の場合に、５０個のＳタイプ部品と１６７個のＭタイプ部品の２つのグループ）に分割し、各グループをノズルセットテーブルに配置したものを初期状態として生成する（Ｓ１２０）。ここで、ノズルセットテーブルとは、後述するように、ヘッド位置（ヘッド番号）を桁とし、ノズルセット数（ノズルセット番号）を行とするメモリ上の表である。
【００５５】
次に、各グループを与えられたタスク数ＸNで分割し（Ｓ１２１）、分割によって得られた部品グループを、部品数の多い順に、左の欄および上の行が先に詰められていくように、ノズルセットテーブルに配置していく（Ｓ１２２）。
【００５６】
その結果、ノズルセットテーブルにおいて、与えられたノズルセット数ｎの行内に全ての部品グループが配置されたか否かを判定し（Ｓ１２３）、全ての部品グループが配置された場合には（Ｓ１２３でＹｅｓ）、与えられたノズル交換回数Ｎに対してタスク数ＸNは可能解であると判断し（Ｓ１２４）、そうでない場合には（Ｓ１２３でＮｏ）、与えられたノズル交換回数Ｎに対してタスク数ＸNは可能解でないと判断する（Ｓ１２５）。
【００５７】
図１４は、ノズル交換回数Ｎが０の場合においてタスク数ＸNを特定する具体例を示す図である。いま、前提として、図１４（ａ）に示されるように、実装の対象となる部品の総数が２１７個（うち、Ｓタイプの部品が５０個、Ｍタイプの部品が１６７個）であり、装着ヘッドのヘッド数が５個とする。この条件下において、ノズル交換回数Ｎ＝０の場合に（図１０のステップＳ１０１）、タスク数ＸNの特定（図１０のステップＳ１０２）は、以下のようにして行われる。
【００５８】
まず、図１４（ｂ）に示されるように、ノズルセット決定部３０５ａは、ノズルセットテーブルの初期状態を生成する（図１３のステップＳ１２０）。なお、図１４（ｂ）のノズルセットテーブルにおいて、左欄がノズルセットの番号であり、続く５つの欄（「１」〜「５」）がヘッド番号に対応する欄である。また、テーブル中の「Ｓ（５０）」、「Ｍ（１６７）」は、それぞれ、Ｓタイプの部品が５０個、Ｍタイプの部品が１６７個を意味する。したがって、図１４（ｂ）に示されたノズルセットテーブルは、ヘッド番号１および２の位置に、それぞれ、ＳタイプおよびＭタイプの吸着ノズルを装着した装着ヘッドを用いて、Ｓタイプの部品５０個とＭタイプの部品１６７個を実装することを意味する。ちなみに、可能な限り同時吸着して実装することを前提としているので、このノズルセットテーブルでは、１６７回のタスクによって、全部品の実装が完了することになる。
【００５９】
次に、ノズルセット決定部３０５ａは、初期状態で生成されたグループＳ（５０）およびＭ（１６７）を最小タスク数Ｘmin「４４」で分割し（図１３のステップＳ１２１）、員数の多い部品グループの順に（同数の場合には、例えば、Ｓ（）をＭ（）に優先させて）、ノズルセットテーブルの上から下の行に、左から右の欄に向けて、図１４（ｃ）に示されるノズルセットテーブルのように配置していく（図１３のステップＳ１２２）。
【００６０】
そして、ノズルセット決定部３０５ａは、全ての部品グループが、与えられたノズルセット数ｎ（ここでは、１）分の行内に配置されたか否かを判断する（図１３のステップＳ１２３）。図１４（ｃ）では、２行にわたって部品グループが配置されているので、ノズルセット数「１」に対してタスク数「４４」による実装は不可能と判断する（図１３のステップＳ１２５、図１２のステップＳ１１２）。そして、タスク数を１だけインクリメントし（図１２のステップＳ１１４）、タスク数「４５」とし、再び同様の検討を行う（図１２のステップＳ１１１、図１３のステップＳ１２０〜Ｓ１２５）。つまり、図１４（ｄ）に示されるノズルセットテーブルのように配置し直す。この場合にも、１行に配置されない部品Ｓ（５）が発生するので、タスク数「４５」による実装は不可能と判断する。
【００６１】
以下、同様にして、タスク数を１ずつインクリメントしながらノズルセットテーブルへの部品配置を繰り返し、最終的に、タスク数「５０」として部品を配置したときに、図１４（ｅ）に示されるように、ノズルセットテーブルの第１行に全ての部品が配置されるので、このタスク数「５０」が最小の可能解と判断し（図１３のＳ１２４）、ノズル交換回数０に対するタスク数を「５０」と決定する（図１２のステップＳ１１３）。
【００６２】
続いて、ノズルセット決定部３０５ａは、ノズル交換回数を１だけ増加させ（図１０のステップＳ１０４）、ノズル交換回数Ｎが「１」に対するタスク数Ｘ2を特定する（図１０のステップＳ１０２）。
【００６３】
図１５は、ノズル交換回数Ｎが１以上の場合におけるタスク数ＸNの特定（図１０のステップＳ１０２）の詳細な手順を示すフローチャートである。基本的な流れは、図１２および図１３に示されたノズル交換回数Ｎが０の場合の手順と同様であるが、タスク数を増加させるだけでなく、減少させながら、より小さいタスク数の可能解を探索する手順が付加されている点が異なる。
【００６４】
まず、ノズルセット決定部３０５ａは、初期タスク数と初期状態を特定する（Ｓ１３０）。ここで、初期タスク数は、最小タスク数Ｘminを、与えられた複数のノズルセットそれぞれに分配したものであり、ここでは、第１番目のノズルセットに（Ｘmin−Ｎ）個のタスクを割り当て、残る第２番目以降のノズルセットに対して１個のタスクを割り当てる。
【００６５】
次に、ノズルセット決定部３０５ａは、初期タスク数が可能解か否かを検討する（Ｓ１３１）。つまり、与えられたノズル交換回数Ｎの下で、各ノズル交換回数Ｎに対応する具体的なノズルセットを特定しながら、全ての部品を初期タスク数で実装することができるか否かを検討する。
【００６６】
その結果、可能解であれば（Ｓ１３２でＹｅｓ）、特定した２以上のノズルセットおよび初期タスク数をノズル交換回数Ｎに対する解として終了する。
一方、初期タスク数が可能解でなければ（Ｓ１３２でＮｏ）、総タスク数ＸNを１だけ増加させ（Ｓ１３３）、再び、可能解か否かを検討する（Ｓ１３４）という処理を、可能解が得られるまで繰り返す（Ｓ１３５）。ここで、総タスク数を１だけ増加するときには、２以上のノズルセットのうち、「空打ち」（装着ヘッドに吸着ノズルが装着されているにも拘わらず部品が吸着されることなく、空き状態のヘッドのまま、タスクが実行される場合における空き状態のヘッドのこと）の最も少ないノズルセットのタスクを１だけ増加させ、そのノズルセットを更新する。これは、「空打ち」の少ないノズルセットのタスクを増加させる方が、より多くの部品を実装できる可能性が高い、つまり、与えられたノズルセット数に割り当てることができなかった部品群すべてを割り当てることができる可能性が高いからである。
【００６７】
このようにしてタスクの増加によって可能解が発見された後に、続いて、ノズルセット決定部３０５ａは、これまでとは逆に、総タスク数ＸNを１だけ減少させ（Ｓ１３６）、再び、可能解か否かを検討する（Ｓ１３７）。ここで、総タスク数を１だけ減少させるときには、２以上のノズルセットのうち、「空打ち」の多いノズルセットを優先して、タスクを１だけ減少させ、そのノズルセットを更新する。これは、「空打ち」の多いノズルセットのタスクを減少させる方が、同一ノズルセット内でのヘッドごとの部品数を平準化できる可能性が高い、つまり、ノズルセット数を増加させることなく、タスク数を減少させることができる可能性が高いからである。
【００６８】
その結果、可能解でない場合には（Ｓ１３８でＮｏ）、それ以上のタスクの減少は困難と判断とし、タスクを減少させる直前の状態における複数のノズルセットおよびそれらノズルセットから求まる合計タスク数ＸNをノズルセット数ｎに対する解とし、終了する。
【００６９】
一方、可能解である場合には（Ｓ１３８でＹｅｓ）、続いて、総タスク数が最小タスク数Ｘminであるか否か判断し（Ｓ１３９）、最小タスク数Ｘminであるときには（Ｓ１３９でＹｅｓ）、その状態における複数のノズルセットおよびそれらノズルセットから求まる合計タスク数ＸNをノズル交換回数Ｎに対する解として終了し、そうでないときには（Ｓ１３９でＮｏ）、再び、総タスク数ＸNを１だけ減少させ（Ｓ１３６）、可能解か否かの検討を行う（Ｓ１３７）という処理を繰り返す。
【００７０】
このようにして、ノズル交換回数Ｎが１以上の場合には、総タスク数を最小タスク数Ｘminから１だけインクリメントしながら可能解を探索し、可能解が得られた場合に、続いて、総タスク数を１だけデクリメントしながら可能解を探索することで、最終的に、与えられたノズル交換回数Ｎに対して、最小のタスク数ＸNを特定する。
【００７１】
図１６および図１７は、ノズル交換回数Ｎが１の場合においてタスク数ＸNを特定する具体例を示す図である。いま、前提として、図１６に示されるように、実装の対象となる部品の総数が２１７個（うち、Ｓタイプの部品が５０個、Ｍタイプの部品が１６７個）であり、装着ヘッドのヘッド数が５個とする。最小タスク数Ｘminが４４であるので、ノズルセット決定部３０５ａは、２つのノズルセット（第１および第２番目のノズルセット）に対して、それぞれ、初期タスク数として、「４３」と「１」を割り当てる（図１５のステップＳ１３０）。つまり、ノズル交換回数Ｎにおけるｊ番目のノズルセットに割り当てるタスク数をＸNjとすると、ノズル交換回数Ｎ「１」における第１番目のノズルセットに割り当てる初期タスク数Ｘ11は、ここでは、
Ｘ11＝Ｘmin−Ｎ  （ｊ＝１）
＝４４−１
＝４３
より、「４３」とし、第２番目のノズルセットに割り当てる初期タスク数Ｘ12は、
Ｘ12＝１  （ｊ≧２）
より、「１」と割り当てる。
【００７２】
そして、ノズルセット決定部３０５ａは、まず、図１７（ａ）に示されるような２つの部品グループＳ（５０）およびＭ（１６７）が配置されたノズルセットテーブルを初期状態として生成する（図１５のステップＳ１３０）。
【００７３】
次に、ノズルセット決定部３０５ａは、それら２つの部品グループを上記初期タスク数Ｘ11およびＸ12で分割して配置し直すことで、図１７（ｂ）に示されるノズルセットテーブルのように、部品グループを配置する（図１５のステップＳ１３１）。具体的には、まず、２つの部品グループを第１番目のノズルセット用の初期タスク数Ｘ11（「４３」）で分割し、員数の多い部品グループの順に（ここでは、Ｓ（４３）、Ｍ（４３）、Ｍ（４３）、Ｍ（４３）、Ｍ（３８）の順に）、ノズルセットテーブルの第１行目に並べ、続いて、残る部品Ｓ（７）を第２番目のノズルセット用の初期タスク数Ｘ12（「１」）で分割し、員数の多い部品グループの順に（ここでは、Ｓ（１）、Ｓ（１）、Ｓ（１）、Ｓ（１）、Ｓ（１）の順に）、ノズルセットテーブルの第２行目に並べ、続いて、残る部品Ｓ（２）をノズルセットテーブルの第３行目に配置する。
【００７４】
ノズルセットテーブルの２行分に全ての部品グループを配置することができなかったことから、ノズルセット決定部３０５ａは、タスク数（Ｘ11＝４３，Ｘ12＝１）は可能解でないと判断し（図１５のステップＳ１３２でＮｏ）、タスク数の増加（図１５のステップＳ１３３）と可能解の検討（図１５のステップＳ１３４）を行う。つまり、「空打ち」の少ないノズルセットのタスク数Ｘ12を１だけインクリメントして「２」とし、ノズルセットテーブルの第２行目を配置し直す。具体的には、図１７（ｃ）に示されるように、ノズルセットテーブルの第１行目の配置を終えて残った部品Ｓ（７）をタスク数「２」で分割し、員数の多い部品グループの順に（ここでは、Ｓ（２）、Ｓ（２）、Ｓ（２）、Ｓ（１）の順に）、ノズルセットテーブルの第２行目に並べる。
【００７５】
その結果、全ての部品をノズルセットテーブルの２行分に配置することができたので、タスク数（Ｘ11＝４３，Ｘ12＝２）は可能解であると判断し（図１５のステップＳ１３５でＹｅｓ）、続いて、タスク数の減少（図１５のステップＳ１３６）と可能解の検討（図１５のステップＳ１３７）を行う。つまり、「空打ち」の多いノズルセットのタスク数Ｘ11を１だけデクリメントして「４２」とし、再び、ノズルセットテーブルの第１行目と第２行目を配置し直す。具体的には、図１７（ｄ）に示されるように、初期状態における２つの部品グループを新たなタスク数Ｘ11（「４２」）で分割し、員数の多い部品グループの順に（ここでは、Ｓ（４２）、Ｍ（４２）、Ｍ（４２）、Ｍ（４２）、Ｍ（４１）の順に）、ノズルセットテーブルの第１行目に並べ、続いて、残る部品Ｓ（８）をタスク数Ｘ12（「２」）で分割し、員数の多い部品グループの順に（ここでは、Ｓ（２）、Ｓ（２）、Ｓ（２）、Ｓ（２）の順に）、ノズルセットテーブルの第２行目に並べる。
【００７６】
その結果、全ての部品をノズルセットテーブルの２行分に配置することができたので、可能解であると判断し（図１５のステップＳ１３８でＹｅｓ）、続いて、総タスク数ＸN（＝Ｘ11＋Ｘ12＝４２＋２＝４４）が最小タスク数Ｘmin（＝４４）に等しいか否かを判定する（図１５のステップＳ１３９）。その結果、総タスク数ＸNが最小タスク数Ｘminに等しいので、タスク数の探索処理を終了する。つまり、図１７（ｄ）に示されるタスクセット（総タスク数Ｘ2＝４４）がノズルセット数「２」に対する解と特定する。
【００７７】
なお、以上の具体例、つまり、部品Ｓ（５０）およびＭ（１６７）については、ノズル交換回数Ｎが１の場合に、探索されたタスク数ＸNが最小タスク数Ｘmin「４４」に等しくなったので、ノズルセットの探索についての終了条件が満たされたこととなり（図１０のステップＳ１０３）、続いて、ノズルセット決定部３０５ａは、これまで探索されたノズル交換回数Ｎとタスク数ＸNとの組の中から、最適なものを選択する（図１０のステップ
Ｓ１０５）。具体的には、これまで、探索された組は、図１８の示される２つの組、つまり、（Ｎ＝０、ＸN＝５０）と（Ｎ＝１、ＸN＝４４）であるので、ノズルセット決定部３０５ａは、これらの値ＮおよびＸNを評価関数（ここでは、ｈ＝２とする）に代入することで、評価値Ｓ（「５０」および「４６」）を算出し、それら評価値の中から最小のもの、つまり、ノズル交換回数Ｎが１のときのノズルセットが最適なものと決定する。よって、ノズルセット決定部３０５ａは、部品Ｓ（５０）およびＭ（１６７）に対しては、図１７（ｄ）に示された２種類のノズルセットによって実装することが最適であると決定する。
【００７８】
なお、以上のノズルセットの決定手順では、各種吸着ノズルの個数（ノズルリソース）に制約がないものとして探索してきた。ところが、実際には、ノズルリソースに制約が存在する場合がある。この場合には、これまでの手順において可能解と判断されたノズルセットが可能解でなくなるケースが発生し得る。たとえば、図１４（ｅ）に示されたノズルセットＳ，Ｍ，Ｍ，Ｍ，Ｍは、ノズルリソースとして、１個のＳタイプ吸着ノズルと４個のＭタイプ吸着ノズルを同時に使用できることが前提とされ、もし、Ｓタイプ吸着ノズルが１個でＭタイプ吸着ノズルが３個というノズルリソースの制約が存在する場合には、もはや、可能解ではなくなる。よって、これまで説明してきた手順は、そのままでは、ノズルリソースの制約が存在する場合に適用することができない。
【００７９】
そこで、ノズルリソースの制約が存在する場合には、これまで説明してきた制約のない手順に対して、以下の手順を付加する。
（１）部品をタスク数で分割して得られる部品グループの表現として、これまでのＡ（Ｂ）ではなく、Ａ（Ｂ，Ｃ）とする。
【００８０】
ここで、「Ａ」は、吸着ノズルのタイプであり、例えば、「Ｓ」，「Ｍ」等である。「Ｂ」は、部品の個数である。「Ｃ」は、ノズルリソース条件の範囲内か否かを示すフラグ（１：ＯＫ、０：ＮＧ）である。
【００８１】
なお、「Ｃ」については、ノズルセットテーブルに配置された部品グループについて、テーブルの上から下の行に、左から右の欄に向けて、先頭の部品グループからノズルリソースの範囲内にある部品グループに対して「１」を割り当て、残る部品グループに「０」を割り当てる。このようなフラグ付けは、ノズルリソースの制約が遵守されているか否かの検出を可能にするためのである。
（２）上記手順（１）を行った結果、もし、ノズルセットテーブルの対象となる行に、「Ｃ」の値が「０」である部品グループＡ（Ｂ，０）が存在した場合には、その部品グループを下の行にずらして配置する。つまり、ノズルリソースの制約を遵守するために、制約を超えた部品グループについては、次のノズルセットによる実装の対象とする。
【００８２】
以下、図１９および図２０を用いて、ノズルリソースの制約を考慮した具体的なノズルセットの決定手順を説明する。図１９および図２０は、ノズル交換回数Ｎが１の場合におけるタスク数ＸNの探索手順を示す具体例である。
【００８３】
いま、前提として、図１９に示されるように、実装の対象となる部品は、Ｓタイプの部品が１００個、Ｍタイプの部品が１２０個で構成され、ノズルリソースは、Ｓタイプの吸着ノズルが２個であり、Ｍタイプの吸着ノズルが２個であり、装着ヘッドのヘッド数は５個とする。
【００８４】
これらの前提から、最小タスク数Ｘminは、
Ｘmin＝（１００＋１２０）／５
＝４４
となるので、図１６に示されるケースと同様に、ノズルセット決定部３０５ａは、２つのノズルセット（第１および第２番目のノズルセット）に対して、それぞれ、初期タスク数として、Ｘ11（＝４３）とＸ12（＝１）を割り当てる。
【００８５】
そして、ノズルセット決定部３０５ａは、まず、図２０（ａ）に示されるような２つの部品グループＳ（１００，１）およびＭ（１２０，１）が配置されたノズルセットテーブルを初期状態として生成する。
【００８６】
次に、ノズルセット決定部３０５ａは、それら２つの部品グループを上記初期タスク数Ｘ11で分割して配置し直すことで、図２０（ｂ）に示されるノズルセットテーブルのように、部品グループを配置する。具体的には、まず、２つの部品グループを第１番目のノズルセット用の初期タスク数Ｘ11（「４３」）で分割し、吸着ノズルのタイプごとに員数の多い部品グループの順に（ここでは、Ｓ（４３，１）、Ｓ（４３，１）、Ｓ（１４，０）、Ｍ（４３，１）、Ｍ（４３，１）、Ｍ（３４，０））の順に）、ノズルセットテーブルの第１および第２行目に並べる。なお、ノズルリソース条件のフラグＣについては、Ｓタイプ吸着ノズルが２個というノズルリソースの制約から、最初の２つの部品グループＳ（４３，Ｃ）およびＳ（４３，Ｃ）のフラグＣを１とし、残る部品グループＳ（１４，Ｃ）のフラグＣを０とし、同様に、Ｍタイプ吸着ノズルが２個というノズルリソースの制約からから、最初の２つの部品グループＭ（４３，Ｃ）およびＭ（４３，Ｃ）のフラグＣを１とし、残る部品グループＭ（３４，Ｃ）のフラグＣを０としている。
【００８７】
そして、図２０（ｃ）に示されるように、いま着目している第１行目において、ノズルリソースの制約を超えている部品グループ、つまり、フラグＣが０である部品グループＭ（３４，０）およびＳ（１４，０）を第２行目に移動させ、隙間をつめて配置し直す。
【００８８】
続いて、ノズルセット決定部３０５ａは、第２行目に配置された２つの部品グループＭ（３４，０）およびＳ（１４，０）を初期タスク数Ｘ12で分割し、上述と同様にしてノズルリソースの制約に従ってフラグＣを付与し、フラグＣが０である部品グループが第３行目に位置するように配置し直すことで、図２０（ｄ）に示されるノズルセットテーブルのように、部品グループを配置する。具体的には、まず、２つの部品グループＭ（３４，０）およびＳ（１４，０）を第２番目のノズルセット用の初期タスク数Ｘ12（「１」）で分割し、員数の多い部品グループの順に並べた後にタイプＳおよびＭの最初の２つの部品グループのフラグＣを１にセットするとともに残る部品グループのフラグＣを０にセットすることで、第２行目から第３行目にかけて、Ｍ（１，１）、Ｍ（１，１）、Ｓ（１，１）、Ｓ（１，１）、Ｍ（３２，０）、Ｓ（１２，０）の順に、部品グループを並べる。
【００８９】
その結果、ノズルセットテーブルの２行分に全ての部品グループを配置することができなかったことから、ノズルセット決定部３０５ａは、そのタスク数（Ｘ11＝４３，Ｘ12＝１）は可能解でないと判断し、タスク数の増加と可能解の検討を繰り返す。つまり、「空打ち」の少ない（ここでは、第１および第２番目のノズルセットの「空打ち」が同数であることから、より番号の小さい第１番目の）ノズルセットのタスク数Ｘ11を１だけインクリメントし、タスク数（Ｘ11＝４４，Ｘ12＝１）について同様の検討（図２０（ｂ）〜（ｄ））を行うということを、可能解が探索されるまで、繰り返す。
【００９０】
いま、タスク数Ｘ11のインクリメントを繰り返し、タスク数（Ｘ11＝５９，Ｘ12＝１）での検討に至ったとする。ノズルセット決定部３０５ａは、２つの部品グループＳ（１００，１）およびＭ（１２０，１）をタスク数Ｘ11で分割して配置し直すことで、図２０（ｅ）に示されるノズルセットテーブルのように、部品グループを配置する。具体的には、まず、２つの部品グループを第１番目のノズルセット用のタスク数Ｘ11（「５９」）で分割し、吸着ノズルのタイプごとに員数の多い部品グループの順に（ここでは、Ｓ（５９，１）、Ｓ（４１，１）、Ｍ（５９，１）、Ｍ（５９，１）、Ｍ（２，０））の順に）、ノズルセットテーブルの第１行目に並べる。
【００９１】
そして、図２０（ｆ）に示されるように、いま着目している第１行目において、ノズルリソースの制約を超えている部品グループ、つまり、フラグＣが０である部品グループＭ（２，０）を第２行目に移動させる。
【００９２】
続いて、ノズルセット決定部３０５ａは、第２行目に配置された部品グループＭ（２，０）を初期タスク数Ｘ12で分割し、上述と同様にしてノズルリソースの制約に従ってフラグＣを付与し、配置し直すことで、図２０（ｇ）に示されるノズルセットテーブルのように、部品グループを配置する。具体的には、まず、部品グループＭ（２，０）を第２番目のノズルセット用のタスク数Ｘ12（「１」）で分割し、員数の多い部品グループの順に並べた後にタイプＭの最初の２つの部品グループのフラグＣを１にセットすることで、第２行目に、Ｍ（１，１）、Ｍ（１，１）の順に、部品グループを並べる。
【００９３】
その結果、全ての部品をノズルセットテーブルの２行分に配置することができたので、タスク数（Ｘ11＝５９，Ｘ12＝１）は可能解であると判断する。続いて、タスク数の減少と可能解の検討を行うが、これまでのタスク数の増加と基本的な処理手順は同様である。つまり、ノズルリソースの制約を考慮しない手順に対して、上記２つの手順（１）および（２）を付加することで、ノズルリソースの制約を考慮したノズルセットの決定が可能となる。
【００９４】
以上のようにして、ノズル交換回数Ｎが１におけるノズルリソースの制約を考慮したノズルセットおよび総タスク数の決定が可能となる。なお、ノズルリソースの制約が存在する場合にも、ノズル交換回数と総タスク数との組を特定し、それらの組の中から上述の評価関数に従って算出した評価値が最も小さいものを最適なノズルセットと決定する点は、ノズルリソースの制約がない場合と同様である。
【００９５】
次に、以上のようなノズルセット決定部３０５ａによるノズルセットの決定アルゴリズムについて、各種基板（様々な部品セット）を対象として検証した結果を示す。
図２１および図２２は、各種基板（様々な部品セット）を対象として、ＩＰ（Integer Programming）ソルバーで得られたノズルセットテーブル（表の右に「厳密解」と示された段）と、本実施の形態のアルゴリズムで得られたノズルセットテーブル（表の右に「実施例」示された段）とを示す図である。なお、ＩＰソルバーは、整数計画問題に定式化した最適化問題を時間をかけて解く汎用のプログラムである。
【００９６】
図２１は、各種基板を対象として探索した最適解を示す図であり、（ａ）は、タイプ（吸着ノズルのタイプ）１、２の部品が、それぞれ、２２４個、２個からなる基板を対象とし、（ｂ）は、タイプ１〜５の部品が、それぞれ、１０１個、３２個、４個、１８個、２個からなる基板を対象とし、（ｃ）は、タイプ１、２の部品が、それぞれ、５０個、１６７個からなる基板を対象とし、（ｄ）は、タイプ１〜４の部品が、それぞれ、５個、３４個、２個、２個からなる基板を対象とし、ノズルセット数ｎが１の場合について探索した解を示している。
【００９７】
図２２は、タイプ１〜９の部品が、それぞれ、５０個、１０個、６５０個、５０個、５０個、２００個、２０個、２１５個、１５個からなる基板を対象として探索した解を示す図であり、（ａ）〜（ｄ）は、それぞれ、ノズルセット数ｎが１、２、３、４の場合の解を示している。
【００９８】
図２１および図２２から分かるように、本実施の形態におけるアルゴリズムによれば、厳密解と一致、あるいは、ほぼ一致した解が探索されている。ところが、計算時間については（図示されていないが）、汎用のパーソナルコンピュータを用いた場合に、ＩＰソルバーによれば、１０分以上もかかる基板があったが、本実施の形態のアルゴリズムによれば、いずれの基板についても、１秒以内で算出されている。これらのことから、本実施の形態のアルゴリズムによれば、極めて高速に、厳密解、または、厳密解にほぼ等しい最適な解が求められることが分かる。
【００９９】
なお、以上の実施の形態では、ノズル交換回数Ｎが１以上の場合におけるタスク数の探索方法として、「空打ち」の頻度を考慮しながら、最小タスク数Ｘminから１ずつインクリメントしたり、１ずつデクリメントしたりしながら探索したが、本発明は、このような探索方法に限定されるものではない。たとえば、タスク数の回数についての全ての組み合わせを探索し、その中から最小の総タスク数となる組み合わせを最適な解と決定する総当たり探索法を採用してもよい。ただし、明らかに探索が不要と判明している組み合わせや、可能解が発見されたために探索が不要になった組み合わせについては、探索の対象から除外する。
【０１００】
図２３は、このような総当たり探索法によるタスク数の決定手順を示すフローチャートである。図２４は、その具体例を示す図である。図２４には、総部品数が６０個（うち、タイプ１〜６の吸着ノズル用の部品が、それぞれ、１１，１１，１１，１０，９，８個）であり、装着ヘッドのヘッド数が１０個であることを前提に、ノズル交換回数Ｎが１の場合に採り得るタスク数の全組み合わせ（Ｘ12，Ｘ11）が示されている。たとえば、組み合わせ（１，２）は、第１番目のノズルセットで２回のタスクを実行し、第２番目のノズルセットで１回のタスクを実行することを意味する。
【０１０１】
この総当たり探索法では、まず、全ての組み合わせに対して、探索範囲を限定する（Ｓ１５０）。具体的には、まず、タスク数の対称性に基づく範囲限定をする。たとえば、組み合わせ（１，２）と（２，１）については、いずれかだけを探索すればよいことから、例えば、
Ｘ12≦Ｘ11      （条件１）
を満たす組み合わせ（Ｘ12，Ｘ11）だけを探索範囲とするように限定する。
【０１０２】
続いて、限定された探索範囲に対して、最小タスク数に基づく範囲限定をする。この例では、最小タスク数は、６０／１０＝６  より、総タスク数が６以上、つまり、
Ｘ11＋Ｘ12≧６      （条件２）
を満たす組み合わせ（Ｘ12，Ｘ11）だけを探索範囲とするように限定する。
【０１０３】
さらに、限定された探索範囲に対して、最大タスク数に基づく範囲限定をする。この例では、最大タスク数（ノズルセットとしてタイプ１，２，３，４，５，６の吸着ノズルを使用した場合のタスク数）が１１であることから、総タスク数が１１以下、つまり、
Ｘ11＋Ｘ12≦１１      （条件３）
を満たす組み合わせ（Ｘ12，Ｘ11）だけを探索範囲とするように限定する。以上の３つの条件１〜３を満たす探索範囲は、図２４の実線で囲まれた領域となる。
【０１０４】
次に、以上のステップで限定された探索範囲の組み合わせについて、上から下の行に、左から右の欄に向けて、順に、各組み合わせについて、可能解か否かの検討をする（Ｓ１５１）。具体的には、図２４において、まず、組み合わせ（１，５）について、図１７（ｃ）に示されるように、部品分割と部品グループの配置を試みる。その結果、ノズルセットテーブルの２行に全ての部品が配置されなければ可能解でないと判断し、次に、組み合わせ（１，６）について、同様の検討を行うということを繰り返していく。
【０１０５】
ここで、もし、上記探索範囲の全ての組み合わせに対する探索が完了した場合には（Ｓ１５２でＮｏ）、最後に探索された可能解を探索結果（求めるべきノズルセット）として処理を終了する（Ｓ１５６）。
【０１０６】
一方、探索範囲が残された状態で、かつ、可能解が発見された場合には（Ｓ１５３でＹｅｓ）、総タスク数がより小さい探索範囲が残っているならば（Ｓ１５４でＹｅｓ）、その探索範囲に限定して（Ｓ１５５）、探索を繰り返し（Ｓ１５１）、総タスク数がより小さい探索範囲が残っていないならば（Ｓ１５４でＮｏ）、最後に探索された可能解を探索結果（求めるべきノズルセット）として処理を終了する（Ｓ１５６）。
【０１０７】
たとえば、組み合わせ（１，８）が可能解であると判明した場合には、その総タスク数９よりも小さい総タスク数の組み合わせだけを探索範囲として限定する。その結果、次なる探索対象は、組み合わせ（１，９）ではなく、組み合わせ（２，４）、（２，５）、…となる。同様にして、組み合わせ（２，６）が可能解と判明した場合には、その総タスク数８よりも小さい総タスク数の組み合わせだけ、つまり、組み合わせ（３，３）、（３，４）を探索する。ここで、組み合わせ（３，４）が可能解と判明した場合には、もはや探索範囲が残されていないので、その解（３，４）が最終的な最適解、つまり、ノズル交換回数Ｎが１の場合の最適なノズルセット（総タスク数が７）と決定する。
【０１０８】
このように、総当たり探索法によれば、図１５のフローチャートに示された方法に比べ、探索の対象が増加する分だけ探索時間がわずかに増加するが、可能性のある全ての組み合わせについて漏れなく検討しているので、確実に最適な解（ノズルセットおよび総タスク数）が求まるという利点がある。
【０１０９】
なお、上記図２４は、ノズル交換回数Ｎが１、つまり、タスク数が２次元の場合の例であったが、ノズル交換回数Nが２以上の場合であっても、同様の手順で探索できるのは言うまでもない。つまり、タスク数の次元が増加し、探索領域の次元が増加する点だけが異なり、探索範囲の限定や探索手法については、２次元の場合と同様である。
【０１１０】
また、ノズルセット決定部３０５ａは、このような総当たり探索による手法および上述した最小タスク数から探索する手法のいずれかによって最適なノズルセットを決定するだけでなく、これら２つの探索手法のいずれかを選択的に実行してもよい。たとえば、探索時間を優先する場合には、最小タスク数から探索する手法を採用し、最適化の精度を優先する場合には、総当たり探索による手法を採用するという混在方式であってもよい。
【０１１１】
次に、図６に示された最適化プログラム格納部３０５のノズルパターン・Ｚ配列決定部３０５ｂの詳細な動作を説明する。
ノズルパターン・Ｚ配列決定部３０５ｂは、ノズルセット決定部３０５ａで決定された１以上のノズルセットについて、部品実装時における１１２の上下動作の回数（吸着回数）を少なくするように、各ノズルセットを構成する各種吸着ノズルのヘッド位置を決定するとともに、複数のノズルセットそれぞれの実行順序を決定することで、ノズルパターンを決定する。また、ノズルパターン・Ｚ配列決定部３０５ｂは、ノズルパターンを決定するのと同時にＺ配列を決定する。
【０１１２】
図２５は、ノズルパターン・Ｚ配列決定部３０５ｂによるノズルパターンおよびＺ配列の決定手順を示すフローチャートである。ノズルパターン・Ｚ配列決定部３０５ｂは、まず、ノズルセット決定部３０５ａで求められたノズルセットに基づいて、ノズルパターンおよびＺ配列の初期解を生成する（Ｓ２００）。初期解の生成方法については後述するが、１回の吸着動作でなるべく多くの部品を同時吸着できるように、ノズルパターンおよびＺ配列の初期解が求められる。
【０１１３】
次に、ノズルパターン・Ｚ配列決定部３０５ｂは、生成された初期解に基づいて、ノズルパターンを構成する吸着ノズルのヘッド位置の一部またはＺ配列を構成する部品カセットの並びの一部を変更しながら、吸着回数が最小となるように、ノズルパターンおよびＺ配列の最適解を探索する（Ｓ２０１）。この最適解の探索処理については、後述する。
【０１１４】
図２６は、図２５におけるＳ２００（ノズルパターンおよびＺ配列の初期解生成処理）の詳細な手順を示すフローチャートである。
ノズルパターン・Ｚ配列決定部３０５ｂは、ノズルセット決定部３０５ａで求められた、ｎ個（ｎは自然数）のノズルセットの各々について、ヘッド番号１（Ｈ１）からヘッド番号１０（Ｈ１０）まで、タスク数が降順となるように吸着ノズルのヘッド位置を並び替えることにより、ノズルパターンを作成する（Ｓ２１０）。
【０１１５】
図２７は、ノズルセットテーブルの一例を示しており、（ａ）は、並び替え処理（Ｓ２００）による並び替え前のノズルセットテーブルを示しており、（ｂ）は、並び替え後のノズルセットテーブルを示している。上述したように、左欄がノズルセットの番号を示しており、続く１０個の欄がヘッド番号に対応している。
【０１１６】
図２７（ａ）に示されるように、ノズルセットテーブルには、ｎ個のノズルセットの組が記載されており、各ノズルセットには、吸着ノズルのタイプと当該吸着ノズルで吸着すべき部品の員数（すなわち、タスク数）とが記載されている。たとえば、１番目のノズルセットは、「Ｘ（１４），Ｘ（１１），Ｙ（１４），・・・，Ｄ（１４）」で示される１０個の吸着ノズルにより構成される。ここで、「Ｘ（１４）」は、上述したように、吸着対象としてＸタイプの部品が１４個あることを示している。各ノズルセットにおいて、タスク数が降順となるように、 吸着ノズルのヘッド位置を並び替えると、図２７（ｂ）に示されるようなノズルセットテーブルが得られる。例えば、１番目のノズルセットについて着目すると、「Ｘ（１４），Ｄ（１４），Ｙ（１４），・・・，Ｘ（１１）」のように、吸着対象とされる部品の員数（タスク数）が降順となるように、吸着ノズルのヘッド位置が並び替えられる。これを、１番目のノズルセットにおけるノズルパターンとする。
【０１１７】
なお、ノズルセットを単位とする並びは、評価値Ｖ（ｉ）の大きいもの順であるものとする。なお、評価値Ｖ（ｉ）は以下の式により定義される。
Ｖ（ｉ）＝（ｉ番目のノズルセットにおける同時吸着ノズル本数）
×（ｉ番目のノズルセットにおける最低吸着回数）
ここで、「ｉ番目のノズルセットにおける同時吸着ノズル本数」とは、ｉ番目のノズルセットにおいて、部品供給部１１５ａ（１１５ｂ）より部品を同時に吸着できる可能性のある吸着ノズルの本数を示している。また、「ｉ番目のノズルセットにおける最低吸着回数」とは、上述の「ｉ番目のノズルセットにおける同時吸着ノズル本数」の対象とされた吸着ノズルで吸着される部品の員数の最小値を示す。すなわち、評価値Ｖ（ｉ）は、部品を同時吸着できる吸着ノズルを用いて実行できる最大の部品実装点数を示している。このため、ノズルセットを単位とする並びは、同時吸着可能な部品の個数の多いものの順である。
【０１１８】
次に、ノズルパターン・Ｚ配列決定部３０５ｂは、ノズルパターンの番号を示す変数ｍに１を代入する（Ｓ２１１）。その後、ノズルパターン・Ｚ配列決定部３０５ｂは、ｍ番目のノズルパターンに含まれる吸着ノズルと実装対象となっている部品を基板２０上に装着する際に使用される吸着ノズルとを比較し、吸着ノズルの位置が一致するように、部品カセット１１４をＺ軸上に配置する（Ｓ２１２）。ここで、同じ吸着ノズルを使用する部品カセット１１４が複数ある場合には、実装対象の員数が多い部品カセット１１４から順にＺ軸上に配置を行なう。
【０１１９】
例えば、図２８は、実装対象となっている部品に関する情報を示した部品テーブルの一例を示す図である。部品テーブル４００の左欄は部品名を示しており、中欄は、実装対象の部品の員数を示しており、右欄は、部品実装時に使用する吸着ノズルのタイプを示している。例えば、部品名「ａ」で特定される部品は、基板２０上に「２０個」実装され、かつその部品を吸着する際に使用される吸着ノズルのタイプは「Ｘタイプ」であることが示されている。
【０１２０】
図２９は、部品カセット１１４の配置処理（Ｓ２１２）の具体例を示す図である。（ａ）は、１番目（ｍ＝１）のノズルパターンを示しており、（ｂ）は、部品カセット１１４の配置処理（Ｓ２１２）による配置結果を示している。ここでは、１番目のノズルパターンに一致するように、Ｚ配列の１番目から１０番目までの部品カセット１１４の配置位置が求められる。まず、ヘッド番号１の位置に配置されているＸタイプの吸着ノズルで吸着可能な部品が部品テーブル４００より抽出される。この条件に合致する部品は、部品名「ａ」および「ｇ」の部品である。このうち、員数の多い部品名「ａ」の部品カセット１１４がＺ配列の１番目に配置される。同様にして、ヘッド番号２の位置に配置されているＤタイプの吸着ノズルで吸着可能な部品として、部品名「ｉ」および「ｋ」の部品が抽出される。このうち、員数の多い部品名「ｉ」の部品カセット１１４がＺ配列の２番目に配置される。同様の処理をヘッド番号３〜１０の位置に配置されている吸着ノズルに対しても行なうことにより、Ｚ軸上の各位置に部品カセット１１４が配置される。
【０１２１】
なお、Ｚ配列の６番目および９番目に部品カセット１１４が配置されていないのは、配置可能な部品カセット１１４がないことによる。すなわち、部品テーブル４００より、Ｙタイプの吸着ノズルで吸着可能な部品は、部品名「ｈ」、「ｃ」および「ｂ」の３種類のみであるが、これらの部品の部品カセット１１４は、Ｚ配列の３番目、４番目および５番目にそれぞれ配置済みである。したがって、Ｙタイプの吸着ノズルで吸着可能な部品の部品カセット１１４をＺ配列の６番目に配置することができないからである。Ｚ配列の９番目に部品カセット１１４が配置されていないのも、同様の理由による。
【０１２２】
次に、ノズルパターン・Ｚ配列決定部３０５ｂは、Ｚ配列上に部品カセット１１４の未配置部分があるか否かを調べる（Ｓ２１３）。図２９（ｂ）の例では、６番目および９番目の２箇所に部品カセット１１４が未配置である。
【０１２３】
部品カセット１１４の未配置部分がある場合には（Ｓ２１３でＹｅｓ）、未配置部分に以下の基準に従い、部品カセット１１４を配置する（Ｓ２１４）。すなわち、ノズルパターン・Ｚ配列決定部３０５ｂは、未配置の部品カセット１１４のうち、実装対象となっている部品の員数が多いものから順にＺ配列に配置していく。例えば、図２９に示した例では、上述のようにＺ配列の６番目および９番目に部品カセット１１４が配置されていない。また、Ｚ配列に部品カセット１１４が未配置の部品の部品テーブル４０２が図３０のように示される。したがって、図３１に示すように、Ｚ配列の６番目には、部品テーブル４０２の中から最も員数が大きい部品名「ｊ」の部品を収納した部品カセット１１４が配置される。また、Ｚ配列の９番目には、次に員数が大きい部品名「ｆ」の部品を収納した部品カセット１１４が配置される。このように、部品の員数の多いものから順に部品カセット１１４を配置するようにしたのは、装着ヘッド１１２は、Ｚ配列において番号の小さい方向から大きい方向へ移動する。このため、員数の大きい部品カセット１１４をなるべく番号の小さいＺ位置に配置することにより、装着ヘッド１１２の移動距離を少なくすることができる。よって、部品の吸着に必要な時間を減少させることができ、部品の実装時間を減少させることができるからである。
【０１２４】
部品カセット１１４の未配置部分がなければ（Ｓ２１３でＮｏ）、未配置部分への部品カセット配置処理（Ｓ２１４）は実行されない。ｍ番目のノズルパターンに基づいてＺ配列への部品カセット１１４の配置が行なわれた後、ノズルパターン・Ｚ配列決定部３０５ｂは、ｍ番目のノズルパターンの各吸着ノズルが実行しなければならない残りのタスク数を計算する（Ｓ２１５）。すなわち、各吸着ノズルについて、当該吸着ノズルで吸着すべきタスク数から、当該吸着ノズルと対応するＺ軸上の位置に配置された部品カセット１１４より吸着すべき部品の員数を引いた値を計算する。例えば、図３２（ａ）に示すように、図２９（ａ）に示した１番目のノズルパターンの１番目から１０番目までのヘッド位置に配置された吸着ノズルのタスク数から、図３１に示した１番目から１０番目までのＺ配列を部品の員数をそれぞれ減算すると、図３２（ａ）に示すようなノズルパターンが得られる。例えば、１番目のヘッド位置（１番目のＺ位置）に着目して見ると、Ｘタイプの吸着ノズルで吸着すべき部品の員数「１４」から部品名「ａ」の部品の員数「２０」を減算すると、「−６」となる。なお、減算の結果が負数となった場合には強制的に「０」にする。すなわち、結果の値は、着目している吸着ノズルを使用して吸着しなければならない部品の員数を示している。なお、６番目のヘッド位置（６番目のＺ位置）のように、ヘッド位置に配置された吸着ノズルと部品カセット１１４に搭載された部品を吸着するための吸着ノズルとが一致しない場合には、「ＮＡ」という記号を付す。これにより、後述する評価値Ｖの算出の処理対象から当該吸着ノズルをはずすことにする。
【０１２５】
タスク数計算処理（Ｓ２１５）において、吸着ノズルで吸着すべきタスク数から、当該吸着ノズルと対応するＺ軸上の位置に配置された部品カセット１１４より吸着すべき部品の員数を引いた値を計算しているのは、以下のような理由による。１つのノズルパターンでそのＺ配列から部品を吸着したときに、結果的に部品カセットの部品の員数が残るということは、そのノズルパターンでは、そのＺ配列から部品を吸着しきれなかったことになる（基板２０にその部品カセットの部品を実装しきれないことになる）。したがって、Ｚ配列の部品残数が０になるかを求めるために、ノズルパターンの各ノズルのタスク数からＺ部品配列の部品の員数の減算を行なっている。
【０１２６】
次に、ノズルパターン・Ｚ配列決定部３０５ｂは、タスク数計算処理（Ｓ２１５）での計算結果に対して、ｍ番目のノズルパターンの評価値Ｖ（ｍ）を、上述した評価式に基づいて算出する（Ｓ２１６）。例えば、図３２（ａ）に示す１番目（ｍ＝１）のノズルパターンについて考えると、ｍ番目のノズルパターンに対対応するＺ軸上の位置に配置された部品カセット１１４より部品を吸着した後であっても、他のＺ軸上の位置に配置された部品カセット１１４より部品を同時吸着できる可能性のある吸着ノズルは、タスク数が１以上である４番目、５番目、８番目および１０番目のヘッド位置に配置された４つの吸着ノズルである。このため、「ｍ番目のノズルセットにおける同時吸着ノズル本数」は「４」となる。また、これら４つの吸着ノズルのタスク数の最小値は、図３２（ａ）中矢印で示した４番目のヘッド位置に配置されたＹタイプの吸着ノズルのタスク数「１」である。このため、「ｍ番目のノズルセットにおける最低吸着回数」は「１」となり、
Ｖ（ｍ）＝４×１＝４
となる。
【０１２７】
このように、タスク数計算処理（Ｓ２１５）で求められた減算値に基づき評価値Ｖ（ｍ）の算出を行うというのは、以下のような意味がある。すなわち、当該減算値が０以上になるということは、そのノズルパターンでそのＺ配列の実装に必要な部品をすべて実装できたことになり、評価値Ｖ（ｍ）の値が大きくなる。しかし、マイナスになるということは、そのノズルパターンでは実装しきれないことを意味する。例えば、図２９（ａ）のノズルパターンのヘッド１〜３では減算値がマイナスになっている。したがって、上記減算値（評価値Ｖ（ｍ））がプラスになるということは、そのノズルパターンにより、他のＺ配列から同時吸着できる余力があることになり、評価値Ｖ（ｍ）を求めるということは、この余力がどの程度あるかを計算することに相当する。
【０１２８】
次に、ノズルパターン・Ｚ配列決定部３０５ｂは、（ｍ＋１）番目のノズルパターンの評価値Ｖ（ｍ＋１）を算出する（Ｓ２１７）。評価値Ｖ（ｍ）の算出処理（Ｓ２１６）では、タスク計算処理（Ｓ２１５）で求められた減算値に基づいて評価値Ｖ（ｍ）を求めているのに対して、ここでは、減算を行なう前のタスク数に基づいて評価値Ｖ（ｍ＋１）を算出する。例えば、図３２（ｂ）に示されるように、ｍ＝１としたときの（ｍ＋１）番目（２番目）のノズルパターンについて評価値Ｖ（ｍ＋１）を求めると、「（ｍ＋１）番目のノズルセットにおける同時吸着ノズル本数」は「１０」であり、「（ｍ＋１）番目のノズルセットにおける最低吸着回数」は「１」である。このため、評価値Ｖ（ｍ＋１）は、
Ｖ（ｍ＋１）＝１０×１＝１０
となる。
【０１２９】
ノズルパターン・Ｚ配列決定部３０５ｂは、ｍ番目のノズルパターンに対する評価値Ｖ（ｍ）と（ｍ＋１）番目のノズルパターンに対する評価値Ｖ（ｍ＋１）とを比較する（Ｓ２１８）。すなわち、同時吸着を行った場合に、どちらのノズルパターンがより多くの部品を吸着可能かを調べる。評価値Ｖ（ｍ＋１）の方が評価値Ｖ（ｍ）よりも大きい場合には、（ｍ＋１）番目のノズルパターンを採用して次のＺ配列（例えば、１番目から１０番目までのＺ配列が求められている場合には、１１番目から２０番目までのＺ配列）を求めた方が、同時吸着できる部品が多い可能性があり、それ以外の場合には、ｍ番目のノズルパターンを採用して次のＺ配列を求めた方が、同時吸着できる部品が多い可能性があることを示している。すなわち、評価値Ｖ（ｉ）の大きいノズルパターンが、Ｚ配列に対して同時吸着できる実装点数が多い最適なノズルパターンを示している。したがって、
Ｖ（ｍ＋１）＞Ｖ（ｍ）
なる関係を満たす場合には（Ｓ２１８でＹｅｓ）、ｍを１つインクリメントする（Ｓ２１９）。それ以外の場合には（Ｓ２１８でＮｏ）、インクリメント処理（Ｓ２１９）は、実行しない。
【０１３０】
最後に、すべての実装対象となっている部品の部品カセット１１４をＺ配列に配置したか否かを調べ（Ｓ２２０）、未配置の部品カセット１１４が存在する場合には（Ｓ２２０でＮｏ）、未配置の部品カセット１１４を部品カセット１１４が未配置のＺ軸上の位置に配置するために、部品カセットの配置処理（Ｓ２１２）以降の処理を実行する。例えば、１番目から１０番目までのＺ配列が求められており、部品名「ｄ」および「ｋ」の部品カセット１１４が未配置の場合には、ｍの値は２となっている。このため、Ｓ２１２の処理では、図２７（ｂ）に示される２番目のノズルパターン「Ｚ（２），Ｅ（２），Ｄ（２），・・・，Ｅ（１）」に合致するように、Ｚ配列が求められる。部品名「ｄ」の部品カセット１１４はＺタイプの吸着ノズルで吸着されるため、１１番目のＺ位置に配置される。また、部品名「ｋ」の部品カセット１１４はＤタイプの吸着ノズルで吸着されるため、１３番目のＺ位置に配置される。すなわち、１２番目のＺ位置には部品カセット１１４は配置されない(図５２参照）。すべての部品カセット１１４を配置済みであれば（Ｓ２２０でＹｅｓ）、ノズルパターンおよびＺ配列の初期解生成処理（図２５のＳ２００）を終了する。
【０１３１】
次に、初期解生成処理（図２５のＳ２００、図２６）に基づいて求められたノズルパターンおよびＺ配列の初期解に基づいて、吸着回数が最小となるようにノズルパターンおよびＺ配列の最適解を探索する処理（図２５のＳ２０１）について、詳細に説明する。
【０１３２】
図３３は、図２５におけるＳ２０１（ノズルパターンおよびＺ配列の最適解探索処理）の詳細な手順を示すフローチャートである。
ノズルパターン・Ｚ配列決定部３０５ｂは、Ｚ配列を固定させた上で、ノズルパターンを構成する吸着ノズルのヘッド位置を一部入れ替えながら、最も吸着回数が小さくなるようなノズルパターンの局所解を探索する（Ｓ２３０）。ノズルパターンの局所解探索処理（Ｓ２３０）については、後述する。
【０１３３】
次に、ノズルパターン・Ｚ配列決定部３０５ｂは、ノズルパターンを固定させた上で、Ｚ配列を構成する部品カセットの並びを一部入れ替えながら、最も吸着回数が小さくなるようなＺ配列の局所解を探索する（Ｓ２３１）。Ｚ配列の局所解探索処理（Ｓ２３１）については、後述する。
【０１３４】
ノズルパターン・Ｚ配列決定部３０５ｂは、Ｚ配列の局所解探索（Ｓ２３１）において吸着回数の減少が見られたか否かを調べる（Ｓ２３２）。吸着回数の減少が見られない場合には（Ｓ２３２でＮｏ）、再度、ノズルパターンの局所解探索およびＺ配列の局所解探索を行なったとしても、吸着回数の減少は見られない、すなわち、ノズルパターンおよびＺ配列の局所解が求められたと判断し、ノズルパターンおよびＺ配列の最適解探索処理（図２５のＳ２０１）を終了する。
【０１３５】
吸着回数の減少が見られた場合には（Ｓ２３２でＹｅｓ）、ノズルパターン・Ｚ配列決定部３０５ｂは、上述のノズルパターンの局所解探索処理（Ｓ２３０）と同様の処理を実行する（Ｓ２３３）。その後、ノズルパターン・Ｚ配列決定部３０５ｂは、ノズルパターンの局所解探索処理（Ｓ２３３）において、吸着回数の減少が見られたか否かを調べる（Ｓ２３４）。吸着回数の減少が見られない場合には（Ｓ２３４でＮｏ）、再度、Ｚ配列の局所解探索およびノズルパターンの局所解探索を行なったとしても、吸着回数の減少は見られない、すなわち、ノズルパターンおよびＺ配列の局所解が求められたと判断し、ノズルパターンおよびＺ配列の最適解探索処理（図２５のＳ２０１）を終了する。
【０１３６】
吸着回数の減少が見られた場合には（Ｓ２３４でＹｅｓ）、ノズルパターン・Ｚ配列決定部３０５ｂは、上述のＺ配列の局所解探索処理（Ｓ２３１）を再度実行する。以上のように、Ｚ配列を固定させた状態でのノズルパターンの局所解探索（Ｓ２３０、Ｓ２３３）と、ノズルパターンを固定させた状態でのＺ配列の局所解探索（Ｓ２３１）とを交互に繰り返し実行し、解が収束した時点で処理を終了させることにより、吸着回数を最小とするようなノズルパターンおよびＺ配列の最適解を求めることができる。
【０１３７】
図３４〜図３９は、図３３に示したノズルパターンおよびＺ配列最適解探索処理（図２５のＳ２０１）の手順を概念的に示した図である。図３４〜図３９に示すグラフの縦軸は、装着ヘッド１１２の上下動作の回数（吸着回数）を示しており、横軸は、処理の反復回数（吸着ノズルのヘッド位置の入れ替え回数および部品カセットの並びの入れ替え回数）を示している。
【０１３８】
図３４に示すように、初期解生成処理（図２５のＳ２００、図２６）に基づいて求められたノズルパターンおよびＺ配列の初期解４１０に基づいて、Ｚ配列を固定させた上で、ノズルパターンを構成する吸着ノズルのヘッド位置を入れ替えながら、ノズルパターンの局所解を探索する（図３３のＳ２３０）。探索途中のノズルパターンの解４１２に基づいて、吸着ノズルのヘッド位置をどのように入れ替えたとしても、解４１２と比較して吸着回数の大きな解４１４しか求めることができなくなった場合には、図３５に示すように、解４１２をノズルパターンの局所解４１２とする。
【０１３９】
次に、図３６に示すように、当該局所解４１２を初期解として、ノズルパターンを固定させた上で、Ｚ配列を構成する部品カセットの並びを入れ替えながら、Ｚ配列の局所解を探索する（図３３のＳ２３１）。探索途中のＺ配列の解４１６に基づいて、Ｚ配列を構成する部品カセットの並びをどのように入れ替えたとしても、解４１６と比較して吸着回数の大きな解４１８しか求めることができなくなった場合には、図３７に示すように、解４１６をＺ配列の局所解４１６とする。
【０１４０】
次に、図３８に示すように、当該局所解４１６を初期解として、ノズルパターンおよび局所解探索（図３３のＳ２３３）とＺ配列の局所解探索（図３３のＳ２３１）とを交互に繰り返し実行する。繰り返し実行の途中で求められた局所解４２０を初期解４２０として、吸着ノズルのヘッド位置または部品カセットの並びをどのように入れ替えたとしても、初期解４２０と比較して吸着回数の大きな解４２２しか求めることができなくなった場合には（図３３のＳ２３２でＮｏまたはＳ２３４でＮｏ）、図３９に示すように、解４２０を吸着回数が最小となるノズルパターンおよびＺ配列の最適解とする。
【０１４１】
次に、ノズルパターンの局所解探索処理（図３３のＳ２３０、Ｓ２３３）について詳細に説明する。図４０は、図３３におけるＳ２３０およびＳ２３３（ノズルパターンの局所解探索処理）の詳細な手順を示すフローチャートである。
【０１４２】
ノズルパターン・Ｚ配列決定部３０５ｂは、現在のノズルセットテーブルＸ、すなわち初期解のノズルセットテーブルＸに含まれるノズルパターンに基づいて、Ｚ配列に並んだ部品カセット１１４より部品を吸着した場合の吸着回数ｆ（Ｘ）を計算する（Ｓ２４１）。次に、ノズルパターンに含まれる吸着ノズルを２つ選択し、それらのノズル位置を交換する（Ｓ２４４）。例えば、図４１（ａ）に示すようなノズルパターンにおいて、３番目および７番目のノズル位置にそれぞれ位置するＹタイプおよびＺタイプの吸着ノズルが選択された場合には、図４１（ｂ）に示すように、ＹタイプおよびＺタイプの吸着ノズルのノズル位置が交換され、３番目および７番目のノズル位置に、ＺタイプおよびＹタイプのノズルがそれぞれ位置するノズルパターンが生成される。
【０１４３】
ノズルパターン・Ｚ配列決定部３０５ｂは、吸着ノズルのノズル位置交換後のノズルセットテーブルＹにおける吸着回数ｆ（Ｙ）を計算する（Ｓ２４５）。次に、ノズルパターン・Ｚ配列決定部３０５ｂは、ノズル位置交換前の吸着回数ｆ（Ｘ）とノズル位置交換後の吸着回数ｆ（Ｙ）との大小を比較する（Ｓ２４６）。吸着回数ｆ（Ｙ）が吸着回数ｆ（Ｘ）よりも等しいか大きい場合には（Ｓ２４６でＮｏ）、ノズル位置を交換しても吸着回数が小さくならない。このため、そのような状態が続く限り、すべてのノズル位置の組み合わせについて、ノズル位置の交換を行なう（ループＢ（Ｓ２４３〜Ｓ２４８）およびループＡ（Ｓ２４２〜Ｓ２４９））。ノズルセットテーブルＸに含まれるすべてのノズルパターンについて、すべてのノズル位置の組み合わせについてノズル位置の交換を行なっても、吸着回数が小さくならない場合には、そのときのノズルセットテーブルＸに含まれるノズルパターンを局所解として、ノズルパターンの局所解探索処理（図３３のＳ２３０、Ｓ２３３）を終了する。
【０１４４】
吸着回数ｆ（Ｙ）が吸着回数ｆ（Ｘ）よりも小さい場合には（Ｓ２４６でＹｅｓ）、ノズル位置を交換することにより吸着回数が小さくなっている。このため、ノズル位置交換後のノズルパターンテーブルＹを新たにノズルパターンテーブルＸとして、ノズルパターンの局所解探索処理（Ｓ２４２〜Ｓ２４９）を行なう。
【０１４５】
以上のようにして、ノズルパターンの局所解が求められる。
次に、Ｚ配列の局所解探索処理（図３３のＳ２３１）について詳細に説明する。図４２は、図３３におけるＳ２３１（Ｚ配列の局所解探索処理）の詳細な手順を示すフローチャートである。
【０１４６】
ノズルパターン・Ｚ配列決定部３０５ｂは、現在求められているノズルパターンを用いて、現在のＺ配列Ｘ、すなわち初期解のＺ配列Ｘに並べられた部品カセット１１４より部品を吸着した場合の吸着回数ｆ（Ｘ）を計算する（Ｓ２５１）。次に、Ｚ配列Ｘに含まれる部品カセット１１４を２つ選択し、それらの並びを交換する（Ｓ２５３）。例えば、図４３（ａ）に示すようなＺ配列において、２番目および５番目のＺ位置にそれぞれ配置されている部品名「ｉ」および部品名「ｂ」の部品カセット１１４が選択された場合には、図４３（ｂ）に示すように、２つの部品カセット１１４の並びが入れ替えられ、３番目および５番目のＺ位置に部品名「ｂ」および部品名「ｉ」の部品カセット１１４がそれぞれ配置されたＺ配列が生成される。
【０１４７】
ノズルパターン・Ｚ配列決定部３０５ｂは、部品カセット１１４の並び入れ替え後のＺ配列における吸着回数ｆ（Ｙ）を計算する（Ｓ２５４）。次に、ノズルパターン・Ｚ配列決定部３０５ｂは、部品カセット１１４のＺ位置入れ替え前の吸着回数ｆ（Ｘ）とＺ位置入れ替え後の吸着回数ｆ（Ｙ）との大小を比較する（Ｓ２５５）。吸着回数ｆ（Ｙ）が吸着回数ｆ（Ｘ）よりも等しいか大きい場合には（Ｓ２５５でＮｏ）、Ｚ位置を入れ替えても吸着回数が小さくならない。このため、そのような状態が続く限り、すべての部品カセット１１４の組み合わせについて、Ｚ位置の交換を行なう（ループＡ（Ｓ２５２〜Ｓ２５７））。Ｚ配列Ｘに含まれるすべての部品カセット１１４の組み合わせについてＺ位置の入れ替えを行なっても、吸着回数が小さくならない場合には、Ｚ配列Ｘを局所解として、Ｚ配列の局所解探索処理（図３３のＳ２３１）を終了する。
【０１４８】
吸着回数ｆ（Ｙ）が吸着回数ｆ（Ｘ）よりも小さい場合には（Ｓ２５５でＹｅｓ）、部品カセット１１４のＺ位置を入れ替えることにより吸着回数が小さくなっている。このため、Ｚ位置入れ替え後のＺ配列Ｙを新たなＺ配列Ｘとして、Ｚ配列の局所解探索処理（Ｓ２５２〜Ｓ２５７）を行なう。
【０１４９】
以上のようにして、Ｚ配列の局所解が求められる。
本願の発明者は、上述の手法を用いて部品の実装順序の最適化を行った場合の部品の実装時間および最適化処理に要する時間を計測する実験を行なった。図４４〜図４８は、上述した部品実装順序最適化方法の実験結果を示す図である。ここでは、５種類の実験を行なった。図４４は、１番目の実験結果を示す図であり、（ａ）は実験の前提条件を示しており、（ｂ）は実験結果を示している。図４４（ａ）に示すように基板２０上に実装する部品の員数が「３６２」個であり、実装部品の種類が「２０」種類であり、かつ吸着ノズルの種類が「３」種類であるという前提条件の下で実験を行なった。図４４（ｂ）は、上述した前提条件の下で実験を行なった結果を示しており、従来の最適化手法（特許文献１または特許文献２に記載の最適化手法）と、本発明の最適化手法とを比較している。同図に示すようにタスク数は４０回から３７回へと減少しているものの、ノズル交換回数は０回から４回に増加している。しかし、吸着回数は、１３３回から７１回に大幅に減少している。これは、吸着回数が小さくなるような最適解の探索処理（図２５のＳ２０１）を行なったからである。実装時間は、従来１２７．８６０秒でかかっていたものが１０９．４７５秒に減少しており、実装時間が約１４．４％向上している。また、最適化処理に要する時間は、３２８秒から０．１秒以下に大幅に減少している。これは、初期解生成処理（図２５のＳ２００）において、なるべく部品を同時吸着できるようにノズルセットとＺ配列とを決定しているからである。このため、最適解に近い初期解を生成することができ、その初期解から最適解を探索しているため、探索時間がかからないことによる。
【０１５０】
図４５は、２番目の実験結果を示す図であり、（ａ）は実験の前提条件を示しており、（ｂ）は実験結果を示している。図４５（ａ）に示すように基板２０上に実装する部品の員数が「３７０」個であり、実装部品の種類が「２０」種類であり、かつ吸着ノズルの種類が「４」種類であるという前提条件の下で実験を行なった。図４５（ｂ）は、上述した前提条件の下で実験を行なった結果を示しており、従来の最適化手法と本発明の最適化手法とを比較している。同図に示すように、タスク数は３９回から３８回へ、ノズル交換回数は１１回から４回へ、吸着回数は１３５回から８２回へそれぞれ減少している。また、実装時間は、１４１．１４２秒かかっていたものが１１４．２８０秒に減少しており、実装時間が約１９．０％向上している。また、最適化処理に要する時間は、７２８秒から０．１秒以下に大幅に減少している。これは、図４４に示した実験結果と同様の理由によるものである。
【０１５１】
図４６は、３番目の実験結果を示す図であり、（ａ）は実験の前提条件を示しており、（ｂ）は実験結果を示している。図４６（ａ）に示すように基板２０上に実装する部品の員数が「４４０」個であり、実装部品の種類が「２１」種類であり、かつ吸着ノズルの種類が「１」種類であるという前提条件の下で実験を行なった。図４６（ｂ）は、上述した前提条件の下で実験を行なった結果を示しており、従来の最適化手法と本発明の最適化手法とを比較している。同図に示すように、タスク数は両手法において４４回と変化がなく、また、ノズル交換回数もノズルの種類が１種類しかないため０回と変化がない。しかし、吸着回数は６１回から５２回へ減少している。このため、実装時間が１２１．７６２秒から１１７．９１７秒に減少しており、実装時間が約３．２％向上している。また、最適化処理に要する時間は７秒から０．１秒以下に大幅に減少している。これは、図４４に示した実験結果と同様の理由によるものである。
【０１５２】
図４７は、４番目の実験結果を示す図であり、（ａ）は実験の前提条件を示しており、（ｂ）は実験結果を示している。図４７（ａ）に示すように基板２０上に実装する部品の員数が「４５６」個であり、実装部品の種類が「２２」種類であり、かつ吸着ノズルの種類が「１」種類であるという前提条件の下で実験を行なった。図４７（ｂ）は、上述した前提条件の下で実験を行なった結果を示しており、従来の最適化手法と本発明の最適化手法とを比較している。同図に示すように、タスク数は両手法において４６回と変化がなく、また、ノズル交換回数もノズルの種類が１種類しかないため０回と変化がない。しかし、吸着回数は５９回から５２回へ減少している。このため、実装時間が１２５．４７５秒から１２１．８７１秒に減少しており、実装時間が約２．９％向上している。また、最適化処理に要する時間は６秒から０．１秒以下に大幅に減少している。これは、図４４に示した実験結果と同様の理由によるものである。
【０１５３】
図４８は、５番目の実験結果を示す図であり、（ａ）は実験の前提条件を示しており、（ｂ）は実験結果を示している。図４８（ａ）に示すように基板２０上に実装する部品の員数が「４７８」個であり、実装部品の種類が「２」種類であり、かつ吸着ノズルの種類が「１」種類であるという前提条件の下で実験を行なった。図４８（ｂ）は、上述した前提条件の下で実験を行なった結果を示しており、従来の最適化手法と本発明の最適化手法とを比較している。同図に示すように、タスク数は両手法において４８回と変化がなく、また、ノズル交換回数もノズルの種類が１種類しかないため０回と変化がない。しかし、吸着回数は６５回から５９回へ減少している。このため、実装時間が１３１．８３７秒から１２８．５６７秒に減少しており、実装時間が約２．５％向上している。また、最適化処理に要する時間は７秒から０．１秒以下に大幅に減少している。これは、図４４に示した実験結果と同様の理由によるものである。
【０１５４】
以上説明した実験結果によると、本発明の最適化手法では、従来の最適化手法と比べ、一部の実験においてノズル交換回数が増加しているものの、すべての実験において吸着回数が減少している。このため、結果的にはすべての実験において実装時間が減少している。また、上述したように、効果的に初期解の生成を行なっている。このため、最適化処理に要する時間が大幅に減少している。
【０１５５】
以上説明したように、本実施の形態における部品実装順序最適化方法によれば、より多くの部品の同時吸着が可能な最適なノズルパターンおよび部品カセットの並び（Ｚ配列）が決定され、これに伴い、部品の吸着回数および実装時間が短縮されるとともに、部品実装順序の最適化に要する時間が短縮される。
【０１５６】
以上、本発明の実施の形態に係る部品実装順序最適化方法について、実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。
例えば、図２６のＳ２１４（未配置部分への部品カセット１１４配置処理）では、未配置部分には実装対象となっている部品の員数の多い順に部品カセット１１４を配置するようにしているが、未配置部分に部品カセット１１４を配置せずに、空けたままにしておいてもよい。このようにしておくことにより、（ｍ＋１）番目以降のノズルパターンにおいて、部品を同時吸着できる可能性が増す。よって、（ｍ＋１）番目以降のノズルパターンにおいて部品を吸着するために吸着ヘッド１１２がＺ配列を左右に移動する移動距離を少なくすることができる。よって、部品の吸着に必要な時間を減少させることができ、部品の実装時間を減少させることができる。
【０１５７】
また、上述の実施の形態では、ノズルパターンの局所解探索処理（図３３のＳ２３０、Ｓ２３３、図４０）およびＺ配列の局所解探索処理（図３３のＳ２３１、図４２）において、吸着回数、すなわち装着ヘッド１１２の上下動作の回数を評価関数として、当該評価関数の値が小さくなるように、最適解を探索した。しかし、吸着回数を小さくする代わりに、装着ヘッド１１２の移動量（以下、「ヘッド移動量」という。）または部品の吸着時間（吸着回数とヘッド移動量とを時間換算した値）が小さくなるように、最適解の探索をするようにしてもよい。以下に、その理由を説明する。
【０１５８】
図４９は、ヘッド移動量と吸着回数との関係を示すグラフであり、横軸は吸着回数を、縦軸はヘッド移動量を示している。このグラフには、１０２４点のサンプリング結果が示されている。このグラフからもわかるように、吸着回数とヘッド移動量との間には相関が見られ、吸着回数が減ると、ヘッド移動量が減ることがわかる。なぜならば、吸着回数が減るということは、１回に多くの部品を吸着できることを意味している。このため、ヘッド移動量は当然減少するからである。
【０１５９】
図５０は、３つの評価関数を、総吸着時間を尺度として比較したグラフである。ここで、手法Ａは、上述の実施の形態で述べた吸着回数を評価関数として、最適解を求める方法である。手法Ｂは、ヘッド移動量を評価関数として、最適解を求める方法である。手法Ｃは、吸着時間を評価関数として最適解を求める方法である。図５０に示されるように、手法Ｂまたは手法Ｃの方が手法Ａに比べて、総吸着時間（すべての実装対象部品を吸着するのに必要な時間）がほぼ少ないことが分かる。
【０１６０】
この理由について図５１を参照して説明する。上述の実施の形態では、ノズルパターンおよびＺ配列の初期解５０１は、吸着回数を小さくするように求められている。このため、手法Ａのように、当該初期解を出発点として、さらに吸着回数を小さくしようとしても、初期解でほぼ解が収束しているため、ほとんど解の更新が行なわれない。解の更新を矢印で表すと、矢印５０２の方向に最適解を求めているのと等しくなる。
【０１６１】
これに対し、手法ＢまたはＣでは、上述の初期解を出発点として、ヘッド移動量が小さくなるように最適解を求めている。このように、最適解を求める際の評価関数を初期解を求める際に使用した評価関数と異なる評価関数としているため、解の更新が手法Ａに比べて起こりやすくなるものと考えられる。解の更新を矢印で表すと、手法Ｂでは矢印５０３の方向に最適解を求めているのと等しくなる。よって、手法Ａに比べ、手法Ｂまたは手法Ｃの方が解の更新が繰り返し行なわれることになる。このため、ヘッド移動量が大幅に減ることとなり、これに伴い、吸着回数も減少するので、総吸着時間が手法Ａに比べて減少する。このような理由により、手法Ｂまたは手法Ｃの方が手法Ａに比べて、総吸着時間が少なくなっているものと思われる。
【０１６２】
以上のように、本発明により、ギャングピックアップ方式の部品実装機について、より高度な最適化レベルで、より高速に、部品の実装順序が最適化され、多種多様な携帯電話機等の基板が短納期で求められる今日において、本発明の実用的意義は極めて大きい。
【産業上の利用可能性】
【０１６３】
本発明に係る部品カセット並び決定方法は、電子部品をプリント配線基板等の基板に実装する部品実装機を対象として最適な部品の実装順序を決定する部品カセット並び決定装置として、また、部品実装順序を決定するコントローラを備える部品実装機あるいは部品実装システムとして、さらに、部品実装機と接続されていない状態で部品の実装順序を決定し評価するスタンドアローンのシミュレータ（部品実装順序の最適化ツール）等として、利用することができる。
【図面の簡単な説明】
【０１６４】
【図１】本発明に係る部品実装システム全体の構成を示す外観図である。
【図２】同部品実装システムにおける部品実装機の主要な構成を示す平面図である。
【図３】同部品実装機の装着ヘッドと部品カセットの位置関係を示す模式図である。
【図４】吸着ノズルの例を示す外観図である。
【図５】（ａ）〜（ｄ）は、実装の対象となる各種チップ形電子部品の例を示す図であり、（ｅ）は、部品を収めたキャリアテープ及びその供給用リールの例を示す図である。
【図６】最適化装置の構成を示すブロック図である。
【図７】図６に示された実装点データの内容例を示す図である。
【図８】図６に示された部品ライブラリの内容例を示す図である。
【図９】図６に示された実装装置情報の内容例を示す図である。
【図１０】図６に示されたノズルセット決定部によるノズルセットの決定手順を示すフローチャートである。
【図１１】図１０におけるステップＳ１０５（最適なノズルセットを特定）の手順を説明する図である。
【図１２】図１０におけるステップＳ１０２（ノズルセットとタスク数ＸNの特定）の詳細な手順を示すフローチャートである。
【図１３】図１２におけるステップＳ１１１（可能解か否かの検討）の詳細な手順を示すフローチャートである。
【図１４】ノズル交換回数Ｎが０の場合においてタスク数ＸNを特定する具体例を示す図である。
【図１５】ノズル交換回数Ｎが１以上の場合におけるタスク数ＸNの特定（図１０のステップＳ１０２）の詳細な手順を示すフローチャートである。
【図１６】ノズル交換回数Ｎが１の場合においてタスク数ＸNを特定する具体例における前提条件を示す図である。
【図１７】ノズル交換回数Ｎが１の場合においてタスク数ＸNを特定する具体例を示す図である。
【図１８】図１７に示された具体例において、探索されたノズル交換回数Ｎとタスク数ＸNとの組の中から、最適なものを選択する処理を説明する図である。
【図１９】ノズルリソースの制約を考慮した具体例における前提条件を示す図である。
【図２０】ノズルリソースの制約を考慮した具体例を示す図である。
【図２１】ＩＰソルバーで得られたノズルセットテーブル（表の右に「厳密解」と示された段）と、本実施の形態のアルゴリズムで得られたノズルセットテーブル（表の右に「実施例」示された段）とを比較して示す図である。
【図２２】ＩＰソルバーで得られたノズルセットテーブル（表の右に「厳密解」と示された段）と、本実施の形態のアルゴリズムで得られたノズルセットテーブル（表の右に「実施例」示された段）とを比較して示す図である。
【図２３】総当たり探索法によるタスク数の決定手順を示すフローチャートである。
【図２４】総当たり探索法の具体例を示す図である。
【図２５】ノズルパターン・Ｚ配列決定部３０５ｂによるノズルパターンおよびＺ配列の決定手順を示すフローチャートである。
【図２６】図２５におけるＳ２００（ノズルパターンおよびＺ配列の初期解生成処理）の詳細な手順を示すフローチャートである。
【図２７】ノズルセットテーブルの一例を示す図である。
【図２８】実装対象となっている部品に関する情報を示した部品テーブルの一例を示す図である。
【図２９】部品カセットの配置処理（図２６のＳ２１２）の具体例を示す図である。
【図３０】未配置の部品の部品テーブルの一例を示す図である。
【図３１】部品カセットの配置処理（図２６のＳ２１２）の具体例を示す図である。
【図３２】部品カセットの配置処理（図２６のＳ２１２）の具体例を示す図である。
【図３３】図２５におけるＳ２０１（ノズルパターンおよびＺ配列の最適解探索処理）の詳細な手順を示すフローチャートである。
【図３４】図３３に示したノズルパターンおよびＺ配列最適解探索処理（図２５のＳ２０１）の手順を概念的に示した図である。
【図３５】図３３に示したノズルパターンおよびＺ配列最適解探索処理（図２５のＳ２０１）の手順を概念的に示した図である。
【図３６】図３３に示したノズルパターンおよびＺ配列最適解探索処理（図２５のＳ２０１）の手順を概念的に示した図である。
【図３７】図３３に示したノズルパターンおよびＺ配列最適解探索処理（図２５のＳ２０１）の手順を概念的に示した図である。
【図３８】図３３に示したノズルパターンおよびＺ配列最適解探索処理（図２５のＳ２０１）の手順を概念的に示した図である。
【図３９】図３３に示したノズルパターンおよびＺ配列最適解探索処理（図２５のＳ２０１）の手順を概念的に示した図である。
【図４０】図３３におけるＳ２３０およびＳ２３３（ノズルパターンの局所解探索処理）の詳細な手順を示すフローチャートである。
【図４１】ノズルパターンの局所解探索処理の具体例を示す図である。
【図４２】図３３におけるＳ２３１（Ｚ配列の局所解探索処理）の詳細な手順を示すフローチャートである。
【図４３】Ｚ配列の局所解探索処理の具体例を示す図である。
【図４４】部品実装順序最適化方法の実験結果を示す図である。
【図４５】部品実装順序最適化方法の実験結果を示す図である。
【図４６】部品実装順序最適化方法の実験結果を示す図である。
【図４７】部品実装順序最適化方法の実験結果を示す図である。
【図４８】部品実装順序最適化方法の実験結果を示す図である。
【図４９】ヘッド移動量と吸着回数との関係を示すグラフである。
【図５０】３つの評価関数を、総吸着時間を尺度として比較したグラフである。
【図５１】総吸着時間の違いが発生する理由を説明するためのグラフである。
【図５２】図２６に示すノズルパターンおよびＺ配列の初期解生成処理実行後のＺ配列の一例を示す図である。
【符号の説明】
【０１６５】
１０    部品実装システム
２０    回路基板
１００    部品実装機
１１０，１２０    サブ設備
１１２    装着ヘッド
１１２ａ、１１２ｂ  吸着ノズル
１１３    ＸＹロボット
１１４    部品カセット
１１５ａ、１１５ｂ  部品供給部
１１６    部品認識カメラ
１１７    トレイ供給部
１１８    シャトルコンベア
１１９    ノズルステーション
３００    最適化装置
３０１    演算制御部
３０２    表示部
３０３    入力部
３０４    メモリ部
３０５    最適化プログラム格納部
３０５ａ  ノズルセット決定部
３０５ｂ  ノズルパターン・Ｚ配列決定部
３０５ｃ  実装順序最適化部
３０６    通信Ｉ／Ｆ部
３０７    データベース部
３０７ａ  実装点データ
３０７ｂ  部品ライブラリ
３０７ｃ  実装装置情報
【図１】
2005333098.tif 000003
【図２】
2005333098.tif 000004
【図３】
2005333098.tif 000005
【図４】
2005333098.tif 000006
【図５】
2005333098.tif 000007
【図６】
2005333098.tif 000008
【図７】
2005333098.tif 000009
【図８】
2005333098.tif 000010
【図９】
2005333098.tif 000011
【図１０】
2005333098.tif 000012
【図１１】
2005333098.tif 000013
【図１２】
2005333098.tif 000014
【図１３】
2005333098.tif 000015
【図１４】
2005333098.tif 000016
【図１５】
2005333098.tif 000017
【図１６】
2005333098.tif 000018
【図１７】
2005333098.tif 000019
【図１８】
2005333098.tif 000020
【図１９】
2005333098.tif 000021
【図２０】
2005333098.tif 000022
【図２１】
2005333098.tif 000023
【図２２】
2005333098.tif 000024
【図２３】
2005333098.tif 000025
【図２４】
2005333098.tif 000026
【図２５】
2005333098.tif 000027
【図２６】
2005333098.tif 000028
【図２７】
2005333098.tif 000029
【図２８】
2005333098.tif 000030
【図２９】
2005333098.tif 000031
【図３０】
2005333098.tif 000032
【図３１】
2005333098.tif 000033
【図３２】
2005333098.tif 000034
【図３３】
2005333098.tif 000035
【図３４】
2005333098.tif 000036
【図３５】
2005333098.tif 000037
【図３６】
2005333098.tif 000038
【図３７】
2005333098.tif 000039
【図３８】
2005333098.tif 000040
【図３９】
2005333098.tif 000041
【図４０】
2005333098.tif 000042
【図４１】
2005333098.tif 000043
【図４２】
2005333098.tif 000044
【図４３】
2005333098.tif 000045
【図４４】
2005333098.tif 000046
【図４５】
2005333098.tif 000047
【図４６】
2005333098.tif 000048
【図４７】
2005333098.tif 000049
【図４８】
2005333098.tif 000050
【図４９】
2005333098.tif 000051
【図５０】
2005333098.tif 000052
【図５１】
2005333098.tif 000053
【図５２】
2005333098.tif 000054