トップ :: G 物理学 :: G05 制御;調整




【発明の名称】 被作業体の分配方法および配置方法
【発明者】 【氏名】勘定 義弘
【住所又は居所】東京都千代田区丸の内一丁目１番２号 日本鋼管株式会社内

【氏名】阿瀬 始
【住所又は居所】東京都千代田区丸の内一丁目１番２号 日本鋼管株式会社内
【要約】 【課題】作業区画上に同時配置するワーク、及びその配置位置の適正化を図る。

【解決手段】ワーク５２を作業区画５１の上に互いに重なり合わないように配置し、それ以降は、配置された各ワーク５２の作業終了後に、作業済のワーク５２の代わりに、未作業のワーク５２のうちの一部を、作業区画５１の上に互いに重なり合わないように配置し、この配置された各ワーク５２の作業終了後に、作業済みの各ワーク５２の代わりに、未作業のワーク５２のうちの一部を、作業区画５１の上に互いに重なり合わないように配置する工程を繰り返すことによって、全ワーク５２の作業を完了させる場合に、作業区画５１に同時配置するワーク５２の組み合わせを決定するためのワーク５２の配置方法であって、同時配置されるワーク５２の組み合わせから構成される各ワークグループの作業時間の合計が最短になるように、各ワークグループを構成するワーク５２の組み合わせを決定する。
【特許請求の範囲】
【請求項１】 複数の被作業体を、予め備えられた所定の作業区画に分配し、分配された各作業区画の作業時間の合計が最短となるように、かつ前記各作業区画毎の作業時間のバラツキが最小となるように、前記被作業体を分配する組合せを決定するようにしたことを特徴とする被作業体の分配方法であって、前記被作業体のそれぞれに、固有の被作業体番号と、各被作業体の配置方向を示す配置方向情報と、同一の所定の作業区画に配置することを意味する区画番号を付して、前記各被作業体の被作業体番号と配置方向情報と区画番号とからなる初期被作業体配置情報列を生成する初期被作業体配置情報列生成段階と、前記初期被作業体配置情報列生成段階において作成された初期被作業体配置情報列について、前記被作業体番号か前記配置方向情報かのいずれかを入れ替えることにより複数の被作業体親配置情報列を第１の所定個数生成する被作業体親配置情報列生成段階と、前記被作業体親配置情報列生成段階において生成された被作業体親配置情報列の中から、前記被作業体番号か前記配置方向情報かのいずれかをランダムに変更することにより、被作業体子配置情報列を第２の所定個数生成する被作業体子配置情報生成段階と、前記被作業体子配置情報生成段階において生成された各被作業体子配置情報列に基づいて、前記区画番号に対応する作業区画毎の作業時間を計算し、前記被作業体子配置情報列に含まれる全ての作業区画毎の作業時間の合計を求める総作業時間計算段階と、前記総作業時間計算段階において計算された各作業区画毎の作業時間のバラツキ度を示す分散係数を計算する作業時間分散度計算段階と、前記総作業時間計算段階において求められた各作業区間毎の作業時間と、前記作業時間分散度計算段階において計算された各作業区間毎の分散係数とからなる最適化度合いに基づき、前記最適化度合いの高い被作業体子配置情報列ほど高い確率で抽出する被作業体配置情報抽出段階と、前記被作業体配置情報抽出段階における抽出結果に基づいて、前記最適化度合いの改善が見られなくなった場合には、この被作業体子配置情報列を最終結果と判定し、前記最適化度合いの改善が見られる場合には、前記被作業体親配置情報列生成段階から前記被作業体配置情報抽出段階までの一連の処理を繰り返す最適化処理終了判定段階とからなることを特徴とする被作業体の分配方法。
【請求項２】 所定の作業区画に分配された複数の被作業体について、複数の機械あるいは作業員により作業する場合において、前記各機械あるいは作業員によってなされる作業量がほぼ均等になるように、前記各被作業体が配置される配置場所を、前記所定の作業区画に基づいて調整するようにしたことを特徴とする被作業体の配置方法であって、前記被作業体のならびと配置方向、配置位置座標からなる初期配置情報列を、配置可能な全ての組み合わせについて生成する初期配置情報列生成段階と、前記初期配置情報列生成段階において生成された初期配置情報列のうちのいずれか１つの初期配置情報列を取り出し、前記各被作業体の配置位置座標を配置初期値として設定する初期値設定段階と、前記被作業体に与えられている複数の作業を複数の機械あるいは作業員に分配する作業分配段階と、前記作業分配段階において機械あるいは作業員ごとに分配された作業量の合計、作業量の分散、最大作業量を求める作業量計算段階と、前記被作業体の配置位置を、特定の制約条件のもと、徐々に変化させながら、目的関数である作業量の分散が最小となる配置位置あるいは、もう一つの目的関数である最大作業量が最小となる最適な被作業体の配置位置を求めるべく、非線形計画問題式として定式化する非線形問題定式化段階と、前記初期配置情報列生成段階において生成された初期配置情報列に対して、前記非線形問題定式化段階において定式化された非線形計画式の解を、所定のアルゴリズムに基づいて求める非線形問題解法段階と、前記初期値設定段階から非線形問題解法段階までの各処理を全ての初期配置情報列について行った被作業体配置結果を記憶する記憶段階と、全ての初期配置情報列について前記各処理が完了したことを判定する完了判定段階と、前記記憶段階において記憶された前記被作業体配置結果の中から、いずれかの目的関数の値が最小になった被作業体配置結果を最適被作業体配置として選択する最適解選択段階とからなることを特徴とする被作業体の配置方法。
【請求項３】 各被作業体のそれぞれに被作業体固有の被作業体番号を付して、未決定被作業体集合として認識するとともに、作業区画を前記被作業体の数作成し、更に前記未決定被作業体集合を前記被作業体の数作成する第１の段階と、前記未決定被作業体として認識された前記各被作業体をそれぞれひとつずつ、前記作成された各作業区画に割付け、割付られた被作業体が、この作業区画に配置可能な場合には、前記被作業体番号とその被作業体の配置可能な配置方向を示す配置方向情報との組み合わせから構成されてなる区画配列情報を作成し、作成した区画配列情報を初期の子個体として認識する第２の段階と、前記子個体毎に、それぞれの未決定被作業体集合からランダムに１つの被作業体を選択して前記作業区画に追加割り付けし、この割り付けられた被作業体がこの作業区画に配置可能な場合には、前記区画配列情報の配置可能な位置に前記被作業体番号と配置可能な配置方向を示す配置方向情報との組み合わせを追加し新たな子個体として認識する、また配置可能でない場合には、前記区画配列情報を変更しないまま子個体として認識する、という前記未決定被作業体集合から前記作業区画への被作業体の追加を実施する第３の段階と、前記区画配列情報に基づいて前記作業区画毎の作業量を計算する第４の段階と、前記第４の段階において作業量が計算された区画配列情報に対応する子個体の中から、前記作業量の多いものほど高い確率で、第１の所定個数の子個体を抽出し、抽出した子個体を親個体とする第５の段階と、前記第５の段階において親個体とされた中で、その作業量が所定作業量以上である場合、あるいは前記第５の段階において抽出された回数が所定回数に達した場合には、前記第５の段階において親個体とされたもののうち、作業量が最も多い親個体に含まれる被作業体を１つの作業区画に割り付ける被作業体群とし、この被作業体群を全ての前記未決定被作業体集合から除外する第６の段階と、前記第５の段階において親個体として抽出されたもののいずれの作業量も前記所定作業量未満であるか、あるいは前記第５の段階において親個体として抽出された回数が所定回数未満である場合には、前記親個体に対応する区画配列情報を構成しているいずれかの１つあるいは複数の前記被作業体の前記作業体番号と配置方向情報とを、別の作業体番号と配置方向情報とに入れ替えること、あるいは前記親個体に対応する区画配列情報を構成しているいずれか１つあるいは複数の前記被作業体の配置方向情報のみを、別の配置方向情報とに入れ替えることにより、新たな区画配列情報を前記第１の所定個数よりも多い第２の所定個数作成し、作成した区画配列情報を子個体として認識する第７の段階と、前記第７の段階において作成された第２の所定個数の子個体の全てに対して、同一の作業区画に割付けられた前記被作業体を、当該作業区画に配置可能かを確認し、配置可能な場合には、前記第３の段階に移行する第８の段階と、前記第７の段階において作成された第２の所定個数の子個体のうち、同一の作業区画に前記被作業体が配置できない場合には、前記第７の段階において作成された子個体を構成する区画配列情報のうち、ランダムに選択した１つの被作業体番号を削除するとともに、対応する未決定被作業体集合の中からランダムに１つの被作業体番号を選択し、選択された被作業体番号に対応する被作業体がこの作業区画において配置可能な場合には、前記区画配列情報の配置可能な位置に前記被作業体番号と、配置可能な配置方向を示す配置方向情報との組み合わせを追加する一方、配置可能でない場合には、前記区画配列情報を変更しないまま前記第４の段階に移行する第９の段階と、前記第６の段階において、全ての被作業体が前記未決定被作業体集合から除外された場合には終了し、そうでない場合には、前記第２の段階に移行する第１０の段階とからなることを特徴とする被作業体の配置方法。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、例えば溶接作業や加工作業のように、複数の被作業体を定盤と呼ばれる所定の作業平面上に配置して複数の機械や作業者により一斉に作業を行わせる場合において、それらの作業が繰り返し実施されるような繰り返し作業における被作業体を組合せて配置する被作業体の分配・配置方法に関するものである。
【０００２】また、本発明は、例えば組立作業や加工作業のように、被作業体を工程から工程へ移動させる場合に、搬送用のパレットないしはこれに類する搬送機材を用いて搬送し、パレットないしは搬送機材に分配された被作業体群ごとに、複数の機械や作業者により作業が繰り返えされるような工程における被作業体を組合せて搬送機材に分配し、複数の機械や作業者が効率的に作業できるよう配置する被作業体の分配・配置方法に関するものである。
【０００３】さらには、本発明は、例えば物品の搬送作業のように、物品を目的地に移動させる場合において、箱、ケース、パレットなど何らかの搬送機材を用いる場合に、物品を重量、容量、重心位置、その他何らかの制約に基づいて搬送機材内に分配する場合の被作業体の分配・配置方法に関するものである。
【０００４】
【従来の技術】例えば、溶接作業や加工作業のように、複数の被作業体（以下「ワーク」と称する）の一部を作業平面上に配置し、配置したワークに対して複数の溶接機械や加工機械を用いて作業を行い、その作業終了後に、作業を完了したワークを取り除き、未実施のワークのうちの一部を作業平面上に配置して作業することを繰り返すことによって全てのワークの作業を完了させる場合において、複数の機械がいずれも均等の作業時間内に分担された作業を完了する場合において、それぞの被作業体の組合せを決定する方法、さらには、被作業体の配置位置関係においては、機械同士の干渉が発生するような場合における被作業体の配置方法に関しては、熟練作業者の経験にたよる部分が多かった。また、対応品種が限定されている場合には数理計画法などなんらかのスケジューリング技術が利用されてきた。しかしながら、社会ニーズの多様化により、組立あるいは加工業における多品種少量生産化は一段と進み、より汎用的な被作業体の組合せ方法、配置方法が望まれていた。本発明は、かかるニーズに基づくものである。
【０００５】また、複数のワークを作業用のパレットに分配し、パレット単位で複数の加工機械に作業を分配する場合においても、多品種少量生産においては、分配に関する詳細な作業計画は立案出来ていないのが現実である。
【０００６】その一例として、図７に示すように、作業区画５１上の空き領域５３が極力少なくなるように、できるだけ稠密に各ワーク５２を配置し、しかる後に、同時に配置したワーク５２について、複数の溶接機械や加工機械（ともに図示せず）を用いて溶接や加工などの所定の作業を行う。そして、作業区画５１上に同時に配置した全てのワーク５２についての作業が終了すると、図８に示すように作業区画５１上に配置しているワーク５２を作業区画５１上から取り除き、図９に示すように、代わりに未作業のワーク５２の一部が配置されている。
【０００７】この未作業のワーク５２の配置においても、上述同様に、作業区画５１上の空き領域５３が極力少なくなるように、図９にその一例を示すように、できるだけ稠密に配置され、しかる後に複数の溶接機械や加工機械による作業が行われている。
【０００８】このような作業区画５１上へのワーク５２の配置、および配置されたワーク５２に対する複数機械を用いた作業を繰り返すことによって、全てのワーク５２に対する作業が行われる。このような場合に、ワーク５２が多数ある場合であっても、ワークの組合せをうまく考慮すれば、作業区画５１上へのワーク５２の配置回数を最小限にすることができる。
【０００９】また、このような作業平面が複数連続する場合には、各組合せにおける作業量のバラツキを最小限にすることが、ボトルネックを発生させない効率的生産に適していることは周知の事実である。
【００１０】
【発明が解決しようとする課題】しかしながら、このような従来の被作業体（ワーク）の分配方法および配置方法では、以下のような問題がある。
【００１１】分配方法に関しては、形状、大きさの異なる様々な対象ワークの中から、作業区画（作業定盤あるいはパレット）の大きさの制約の基、トータルの作業時間が最小となる最適なワークの組み合わせを求めること、さらに、組み分けされた作業区画ごとの作業時間のバラツキを最小とすることは、繰り返し作業におけるボトルネックの発生の解消に効果があるが、このような組み合わせを求めることは一般的に困難とされている。
【００１２】配置方法に関しては、複数の機械あるいは作業者が作業区画５１に対して、それぞれの担当区域がある場合に、作業区画５１に割り付けられた複数のワーク５２に対して、全ての機械ができるだけ均等の作業負荷を持ち、すなわち、最大負荷となる機械の作業時間が最小となる複数のワーク５２の配置方法を求めることは、一般的に困難とされている。
【００１３】さらに加えて、上述したように作業区画５１上に可能な限り稠密させてワーク５２を配置させた状態において複数の機械を作動させると、ワーク５２同士が接近しすぎているために、各機械同士の作業動作の干渉が頻繁に発生するようになる。このような各機械同士の作業動作の干渉が発生した場合には、一方の機械の作業動作が干渉エリアから出て行くまで、もう片方の機械はその作業動作を停止していなければならない。
【００１４】パレットからワークを取り出す機械が複数あるような場合においても、同様の機械同士の相互干渉が発生する。
【００１５】このような待ち時間の発生のために、作業区画５１上に配置されたワーク５２の全ての作業が終了するまでに要する時間が長引いてしまい、結果的に、全てのワーク５２の作業を完了するまでに要する時間も長引いてしまうので作業効率が低下するという問題がある。
【００１６】本発明はこのような事情に鑑みてなされたものであり、所定の作業区画へのワーク配置と、作業区画上に同時に配置されたワークに対する作業を複数機械あるいは作業者を用いて行う工程とを繰り返すことによって全てのワークに対する作業を行う場合、作業区画上に同時に配置するワークの組み合わせ、およびその配置位置の適正化を図り、もって、全てのワークの作業を完了するまでに要する時間を短縮し、作業効率の向上を図ることが可能な被作業体の分配方法および配置方法を提供することを目的とする。
【００１７】さらには、本発明は、例えば物品の搬送作業のように、物品を目的地に移動させる場合において、箱、ケース、パレットなどなんらかの搬送機材を用いる場合に、搬送機材のひとつひとつを作業区画と考え、作業区画の有する制約である積載重量、容量、重心位置、その他なんらかの制約に基づいて機材内に分配する場合においても、搬送機材数の最小化と、積載重量、容量、重心位置などの均一化を図り、もって、搬送作業の効率化を図ることが可能な被作業体の分配方法および配置方法を提供することを目的とする。
【００１８】
【課題を解決するための手段】上記の目的を達成するために、本発明では、以下のような手段を講じる。
【００１９】すなわち、請求項１の発明は、複数の被作業体を、予め備えられた所定の作業区画に分配し、分配された各作業区画の作業時間の合計が最短となるように、かつ各作業区画毎の作業時間のバラツキが最小となるように、被作業体を分配する組合せを決定するようにしたことを特徴とする被作業体の分配方法であって、初期被作業体配置情報列生成段階と、被作業体親配置情報列生成段階と、被作業体子配置情報生成段階と、総作業時間計算段階と、作業時間分散度計算段階と、被作業体配置情報抽出段階と、最適化処理終了判定段階とからなる。
【００２０】初期被作業体配置情報列生成段階では、被作業体のそれぞれに、固有の被作業体番号と、各被作業体の配置方向を示す配置方向情報と、同一の所定の作業区画に配置することを意味する区画番号を付して、各被作業体の被作業体番号と配置方向情報と区画番号とからなる初期被作業体配置情報列を生成し、被作業体親配置情報列生成段階は、初期被作業体配置情報列生成段階において作成された初期被作業体配置情報列について、被作業体番号か配置方向情報かのいずれかを入れ替えることにより複数の被作業体親配置情報列を第１の所定個数生成する。
【００２１】また、被作業体子配置情報生成段階では、被作業体親配置情報列生成段階において生成された被作業体親配置情報列の中から、被作業体番号か配置方向情報かのいずれかをランダムに変更することにより、被作業体子配置情報列を第２の所定個数生成し、総作業時間計算段階では、被作業体子配置情報生成段階において生成された各被作業体子配置情報列に基づいて、区画番号に対応する作業区画毎の作業時間を計算し、被作業体子配置情報列に含まれる全ての作業区画毎の作業時間の合計を求め、作業時間分散度計算段階では、総作業時間計算段階において計算された各作業区画毎の作業時間のバラツキ度を示す分散係数を計算する。
【００２２】更に、被作業体配置情報抽出段階では、総作業時間計算段階において求められた各作業区間毎の作業時間と、作業時間分散度計算段階において計算された各作業区間毎の分散係数とからなる最適化度合いに基づき、最適化度合いの高い被作業体子配置情報列ほど高い確率で抽出し、最適化処理終了判定段階では、被作業体配置情報抽出段階における抽出結果に基づいて、最適化度合いの改善が見られなくなった場合には、この被作業体子配置情報列を最終結果と判定し、最適化度合いの改善が見られる場合には、被作業体親配置情報列生成段階から被作業体配置情報抽出段階までの一連の処理を繰り返す。
【００２３】請求項２の発明は、所定の作業区画に分配された複数の被作業体について、複数の機械あるいは作業員により作業する場合において、各機械あるいは作業員によってなされる作業量がほぼ均等になるように、各被作業体が配置される配置場所を、所定の作業区画に基づいて調整するようにしたことを特徴とする被作業体の配置方法であって、初期配置情報列生成段階と、初期値設定段階と、作業分配段階と、作業量計算段階と、非線形問題定式化段階と、非線形問題解法段階と、記憶段階と、完了判定段階と、最適解選択段階とからなる。
【００２４】初期配置情報列生成段階では、被作業体のならびと配置方向、配置位置座標からなる初期配置情報列を、配置可能な全ての組み合わせについて生成し、初期値設定段階では、初期配置情報列生成段階において生成された初期配置情報列のうちのいずれか１つの初期配置情報列を取り出し、各被作業体の配置位置座標を配置初期値として設定する。
【００２５】また、作業分配段階では、被作業体に与えられている複数の作業を複数の機械あるいは作業員に分配し、作業量計算段階では、作業分配段階において機械あるいは作業員ごとに分配された作業量の合計、作業量の分散、最大作業量を求め、非線形問題定式化段階では、被作業体の配置位置を、特定の制約条件のもと、徐々に変化させながら、目的関数である作業量の分散が最小となる配置位置あるいは、もう一つの目的関数である最大作業量が最小となる最適な被作業体の配置位置を求めるべく、非線形計画問題式として定式化する。
【００２６】更に、非線形問題解法段階では、初期配置情報列生成段階において生成された初期配置情報列に対して、非線形問題定式化段階において定式化された非線形計画式の解を、所定のアルゴリズムに基づいて求め、記憶段階では、初期値設定段階から非線形問題解法段階までの各処理を全ての初期配置情報列について行った被作業体配置結果を記憶し、完了判定段階では、全ての初期配置情報列について各処理が完了したことを判定し、最適解選択段階では、記憶段階において記憶された被作業体配置結果の中から、いずれかの目的関数の値が最小になった被作業体配置結果を最適被作業体配置として選択する。
【００２７】請求項３の発明による被作業体の配置方法は、各被作業体のそれぞれに被作業体固有の被作業体番号を付して、未決定被作業体集合として認識するとともに、作業区画を被作業体の数作成し、更に未決定被作業体集合を被作業体の数作成する第１の段階と、未決定被作業体として認識された各被作業体をそれぞれひとつずつ、作成された各作業区画に割付け、割付られた被作業体が、この作業区画に配置可能な場合には、被作業体番号とその被作業体の配置可能な配置方向を示す配置方向情報との組み合わせから構成されてなる区画配列情報を作成し、作成した区画配列情報を初期の子個体として認識する第２の段階と、子個体毎に、それぞれの未決定被作業体集合からランダムに１つの被作業体を選択して作業区画に追加割り付けし、この割り付けられた被作業体がこの作業区画に配置可能な場合には、区画配列情報の配置可能な位置に被作業体番号と配置可能な配置方向を示す配置方向情報との組み合わせを追加し新たな子個体として認識する、また配置可能でない場合には、区画配列情報を変更しないまま子個体として認識する、という未決定被作業体集合から作業区画への被作業体の追加を実施する第３の段階と、区画配列情報に基づいて作業区画毎の作業量を計算する第４の段階と、第４の段階において作業量が計算された区画配列情報に対応する子個体の中から、作業量の多いものほど高い確率で、第１の所定個数の子個体を抽出し、抽出した子個体を親個体とする第５の段階と、第５の段階において親個体とされた中で、その作業量が所定作業量以上である場合、あるいは第５の段階において抽出された回数が所定回数に達した場合には、第５の段階において親個体とされたもののうち、作業量が最も多い親個体に含まれる被作業体を１つの作業区画に割り付ける被作業体群とし、この被作業体群を全ての未決定被作業体集合から除外する第６の段階と、第５の段階において親個体として抽出されたもののいずれの作業量も所定作業量未満であるか、あるいは第５の段階において親個体として抽出された回数が所定回数未満である場合には、親個体に対応する区画配列情報を構成しているいずれかの１つあるいは複数の被作業体の作業体番号と配置方向情報とを、別の作業体番号と配置方向情報とに入れ替えること、あるいは親個体に対応する区画配列情報を構成しているいずれか１つあるいは複数の被作業体の配置方向情報のみを、別の配置方向情報とに入れ替えることにより、新たな区画配列情報を第１の所定個数よりも多い第２の所定個数作成し、作成した区画配列情報を子個体として認識する第７の段階と、第７の段階において作成された第２の所定個数の子個体の全てに対して、同一の作業区画に割付けられた被作業体を、当該作業区画に配置可能かを確認し、配置可能な場合には、第３の段階に移行する第８の段階と、第７の段階において作成された第２の所定個数の子個体のうち、同一の作業区画に被作業体が配置できない場合には、第７の段階において作成された子個体を構成する区画配列情報のうち、ランダムに選択した１つの被作業体番号を削除するとともに、対応する未決定被作業体集合の中からランダムに１つの被作業体番号を選択し、選択された被作業体番号に対応する被作業体がこの作業区画において配置可能な場合には、区画配列情報の配置可能な位置に被作業体番号と、配置可能な配置方向を示す配置方向情報との組み合わせを追加する一方、配置可能でない場合には、区画配列情報を変更しないまま第４の段階に移行する第９の段階と、第６の段階において、全ての被作業体が未決定被作業体集合から除外された場合には終了し、そうでない場合には、第２の段階に移行する第１０の段階とからなる。
【００２８】
【発明の実施の形態】以下に、本発明の各実施の形態について図面を参照しながら説明する。
【００２９】なお、以下の各実施の形態の説明に用いる図中の符号は、図７から図９と同一部分については同一符号を付して示すことにする。
【００３０】（第１の実施の形態）本発明の第１の実施の形態に係る被作業体の分配方法および配置方法について、図１から図３を用いて説明する。
【００３１】本実施の形態に係る被作業体の分配方法および配置方法は、図７に示すように、まず一部のワーク５２を、予め備えられた所定の作業区画５１の上に互いに重なり合わないように配置する。このように配置された各ワーク５２について、複数の機械（図示せず）によって作業が行われると、図８に示すように、作業がなされた各ワーク５２を作業区画５１上から取り除き、代わりに、図９に示すように、未作業のワーク５２のうちの一部のワーク５２を、前述同様にして作業区画５１の上に互いに重なり合わないように配置する。
【００３２】そして、この配置された未作業の各ワーク５２についても、複数の機械を用いて所定の作業がなされた後には、前述同様に作業区画５１上から取り除き、代わりに、未作業のワーク５２のうちの一部のワーク５２を、作業区画５１の上に互いに重なり合わないように配置する。このような未作業のワーク５２の作業区画５１への配置、作業、作業済みのワーク５２の取り除きからなる工程を繰り返すことによって、全てのワーク５２の作業を完了させる。
【００３３】本実施の形態では、作業区画５１に同時に配置するワーク５２の組み合わせ、および配置を、遺伝的アルゴリズムを用いて決定する。これによって、全てのワークの作業の完了までに要する時間を短縮する。さらには、作業区画の制約条件として考えられる作業区画ごとの作業時間のバラツキを最小にする。
【００３４】図１は、上述したような、遺伝的アルゴリズムを適用した本実施の形態に係る被作業体（ワーク）の分配方法および配置方法の流れを示すフローチャートである。
【００３５】すなわち、本実施の形態に係る被作業体（ワーク）の分配方法および配置方法は、図１のフローチャートに示す流れに従って、遺伝的アルゴリズムを用いて、作業区画５１上に同時に配置するワーク５２の組み合わせ、および配置場所を決定する。
【００３６】以下、このような遺伝的アルゴリズムを用いた本実施の形態に係る被作業体（ワーク）の分配方法および配置方法について説明する。
【００３７】遺伝的アルゴリズムを用いて解を得るためには、数値解析を行うので、考慮する全ての情報を数値情報で表現した遺伝子表現を作成する必要がある。したがって、まず、作業区画５１に配置されたワ−ク５２を処理する複数（ｎ台）の機械のおのおのにＲ１、・・・、Ｒｎと記号を付ける。一方、各ワ−クには番号Ｗ１、・・・、ＷＩを付ける。このＩ個のワ−クをいくつかの「組」（Ｇ１、・・・、ＧＮ）に分け、各組単位で、組の中のすべてのワ−クを、横の長さＬｘ、縦の長さＬｙの長方形の作業区画５１の上に重ならないように配置する。すなわち、ここでいう「組」とは、作業区画５１に同時に配置するワークの組み合わせのことである。
【００３８】各ワ−クにはいずれかの機械（Ｒ１、・・・、Ｒｎ）に処理させるいくつかの仕事であるタスクが含まれている。ここで、組Ｇｉの全ワ−クに含まれるこれらのタスクがすべて終了する時間をＴ(ｉ)とする。仮に、Ｎ組存在する場合、全ワ−ク、すなわち全組（Ｇ１、・・・、ＧＮ）の処理が完了する時間は、Ｔ（１）＋・・・・・＋Ｔ（Ｎ） となる。同様に、組Ｇｉのワークの配置および回収作業に要する段取り時間をＳ(ｉ)とし、全組の段取り時間は、Ｓ（１）＋・・・・・＋Ｓ（Ｎ）となる。したがって、本実施の形態に係る被作業体の分配方法および配置方法の目的は、Ｔ（１）＋・・・・・＋Ｔ（Ｎ） と Ｓ（１）＋・・・・・＋Ｓ（Ｎ） との総和が最小となるようなワークの組、および各組における作業区画５１上のワーク配置を求めることである。さらには、作業区画５１毎の作業時間のバラツキ度合いを（作業時間のバラツキでなくても、重量、容量、重心位置など、どのような制約条件のバラツキでもよい）Ｄ(ｉ)とし、バラツキは、その総和であるＤ（１）＋・・・・・＋Ｄ（Ｎ）が最小となるようにすることも目的とする。
【００３９】図２に、このようなワークの組、および各組における作業区画５１上のワーク配置を求めるための遺伝子表現の一例を示す。
【００４０】各ワークは、ワ−ク並びＰと配置方向Ｄという２種類の遺伝子からなり、さらに組の区切り位置Ｋという情報を持っている。ワ−ク並びＰは、作業区画５１に配置するワ−ク番号Ｗ１、・・・、ＷＩの数値（１、・・・、Ｉ）を記載したものである。配置方向Ｄは、ワ−クを作業区画５１の上に配置するときに、縦横が元の状態であれば「０」、９０度回転して縦横の関係を入れ替える場合は「１」という値をとる。図２に示す組１（Ｇ１）を例にとると、ワ−クＷ７とワークＷ５とワークＷ１６とは縦横入れ替え、ワ−クＷ１は縦横は元の状態で配置するということになる。
【００４１】本実施の形態においては、説明を簡単にするために長方形に近似できるワークを対象としているが、複雑形状ワークの場合には、長方形の組み合わせからなるワークと考えれば、類似処理で対応できる。例えば、ワークの配置方向に関しても、０度、９０度に加えて１８０度、２７０度の配置方向を加えることで、対称形状でない複雑形状ワークにも対応できる。
【００４２】ワ−ク並びＰの順番は、ワ−クを、以下に説明するワ−ク配置ル−ルに従って作業区画５１の上に配置することを意味する。ワ−ク配置ル−ルとは、ワ−クを作業区画５１の左下隅側からできるかぎり詰めて配置するという考え方であり、その手順を以下に示す。ここで、長方形の作業区画５１の横方向をｘ軸、縦方向をｙ軸とし、作業区画５１の左下隅を原点(0,0)とする。
【００４３】すなわち、ワーク配置ルールとは、１）ワ−クを各辺がｘ軸あるいはｙ軸に平行になるように配置する。
２）最初のワ−クは左下頂点が原点になるように配置する。
３）２番目以降のワ−クを配置する場合、ワ−クの左下頂点のｘ座標が最も小さくなるように配置する。なお、このような配置方法が１通りでない場合には、さらにそのｙ座標が最小になるように配置する。ただし、そのワ−ク５２の左下頂点のｘ座標はこれまでに置いたワ−クの左下頂点のｘ座標より小さくはならないように配置する。
【００４４】このようなワーク配置ルールにしたがって配置した組１（Ｇ１）の配置例について図３を用いて説明する。図３（ａ）は、組１（Ｇ１）に配置する４つのワーク５２であるワークＷ１、ワークＷ５、ワークＷ７、ワークＷ１６である。
【００４５】まず、ワーク並びＰが１番目であるワークＷ７を原点から配置する。このとき、ワークＷ７の配置方向Ｄは「１」であるので９０度回転させ、図３（ｂ）のように配置する。次に、ワーク並びＰが２番目であるワークＷ５を、ワーク配置ルール３）にしたがって、その左下頂点のｘ座標が最も小さくなるように、すなわち、左端を作業区画５１の左端にあわせ、かつ、ワークＷ７の上に配置する。ワークＷ５の配置方向Ｄもまた「１」であるので９０度回転させて、図３（ｂ）のように配置する。
【００４６】次に、ワーク並びＰが３番目であるワークＷ１を配置する。この場合、その左下頂点のｘ座標が最も小さくなるように、すなわち、左端を作業区画５１の左端にあわせ、かつ、ワークＷ５の上に配置しようとすると、ワークＷ１の上部が作業区画５１から出てしまうので、ワーク配置ルール３）にしたがって、そのｙ座標が最小になるように、つまり、そのワークＷ１の下端を作業区画５１の下端にあわせ、かつ、ワークＷ７の右側に配置する。ワークＷ１の配置方向Ｄは「０」であるので、回転させること無くそのまま配置する。
【００４７】そして、ワークの並びＰが４番目であるワークＷ１６を、ワーク配置ルール３）にしたがって、その左下頂点のｘ座標が最も小さくなるように、すなわち、左端をワークＷ７の右端にあわせ、かつ、ワークＷ１の上に配置する。ワークＷ１６の配置方向Ｄもまた「１」であるので９０度回転させて、図３（ｂ）のように配置する。
【００４８】また、以下に、組の区切り位置Ｋについて説明する。図２に示す遺伝子表現の例では、４番目に配置されたワーク番号Ｗ１６と５番目に配置されたワーク番号Ｗ３との間、９番目に配置されたワーク番号Ｗ４と１０番目に配置されたワーク番号Ｗ２との間、・・・・、に組の区切り位置Ｋがあるという情報を持っている。したがって、ワ−ク並びＰの１番目から４番目までが組１（Ｇ１）、５番目から９番目までが組２（Ｇ２）、・・・、と認識する。
【００４９】このような遺伝子表現を用いて、遺伝的アルゴリズムによって、全てのワークの作業完了までに要する時間を短縮する「組」を求める手順について、図１に示すフローチャートを用いて説明する。
【００５０】（ステップＳＴ１：初期個体生成）まず、初期個体の生成を行う。初期個体とは、各組を構成するワーク番号Ｗｉとその配置方向Ｄとの組み合わせからなる数値データのことである。このような初期個体は、ワ−クをワーク番号Ｗｉ順に並べ、組の区切り位置Ｋを１番目、２番目、３番目…とする。この場合、各組は、１つのワ−クのみから構成する。すなわち、ワ−クは全部でＩ（Ｗ１、・・・、ＷＩ）個あるので、組もＩ個できる。配置方向Ｄはランダムに設定する。このように作成した初期個体を、世代数＝１の初期個体として以下に示すステップＳＴ２の処理を行う。
【００５１】（ステップＳＴ２：交叉）ステップＳＴ２では、入力された遺伝子表現である各親に対し交叉によって第２り所定個数の子を作る。交叉はワ−ク並びＰか、または配置方向Ｄかのどちらかに対して行う。
【００５２】ワ−ク並びＰに対する交叉は、ワ−ク並びＰに関する遺伝子データを１個ないしは複数個移動させる。移動させる遺伝子、およびその移動先はランダムに選ぶ。ワ−ク並びＰに関する遺伝子が移動するときは、それに対応する配置方向Ｄの遺伝子も同じ所へ移動する。こうしていくつかの子ができる。一方、配置方向Ｄに対する交叉は、配置方向Ｄに関する遺伝子の部分列をランダムに選び、部分列の０／１デ−タを入れ替える。すなわち、０なら１に、１なら０に置き替える。
【００５３】ワ−ク並びＰに関する遺伝子の移動先は（組番号、挿入位置）をそれぞれランダムに選ぶ。交叉前の個体の遺伝子表現における組数がＮのとき、組番号は（Ｎ＋１）まで選ぶことができる。仮に、組番号として（Ｎ＋１）を選んだ場合は、新しい組番号（Ｎ＋１）を作ることを意味する。選ばれた移動先の組が今と同じ組なら組内での入れ替え、異なる組なら異なる組への移し替えになる。異なる組への移動により元の組にワ−クがなくなる場合は、その組から後の組の番号を１ずつ繰り下げる。同じ組内への移動で位置も全く変わらない場合は同一遺伝子表現になるので、そのような交叉は無効とする。また、新しい組（Ｎ＋１）への移動で元の組のワ−クがなくなる場合も本質的に同じ遺伝子表現になるのでそのような交叉は無効とする。
【００５４】（ステップＳＴ３：作業領域内の配置可能性のチェック）ここでは、ステップＳＴ２において交叉によって作られた子の遺伝子表現に対応するワ−クの組がすべて、上述したワ−ク配置ル−ルに従って作業区画５１に配置可能かどうかを調べる。配置可能な場合にはステップＳＴ４へ移行する。一方、配置できない場合にはその子は致死遺伝子として以降の処理は行わない。
【００５５】（ステップＳＴ４：ワ−クの処理完了時間の計算）ステップＳＴ３によってチェックされた結果に基づいて、致死遺伝子を除く全ての遺伝子表現されたワーク配置に対し、作業動作シミュレーションを行い、作業完了時間を計算する。作業完了時間は、ワ−クの組がＮ個ある場合、まず、各々のワーク（１、・・・、Ｎ）の組毎の完了時間の総和Ｔ（１）＋・・・＋Ｔ（Ｎ）と段取り時間の総和Ｓ（１）＋・・・・・＋Ｓ（Ｎ）の合計により求める。
【００５６】（ステップＳＴ５：作業完了時間のバラツキ度合いの計算）ステップＳＴ３によってチェックされた結果に基づいて、致死遺伝子を除く全ての遺伝子表現されたワーク配置に対し、作業動作シミュレーションを行い、作業完了時間を計算する。作業完了時間は、ワ−クの組がＮ個ある場合、まず、各々のワーク（１、・・・、Ｎ）の組毎の作業完了時間のＴ（ｉ）と段取り時間Ｓ（ｉ）の和を各組毎に求め、平均値との差の２乗した値、すなわち分散Ｄ（ｉ）を、各組毎に求める。
【００５７】なお、各遺伝子表現されたワーク配置の目的関数Ｆとしては、ａ（（Ｔ（１）＋・・・＋Ｔ（Ｎ））＋（Ｓ（１）＋・・・・・＋Ｓ（Ｎ）））＋ｂ（Ｄ（１）＋・・・＋Ｄ（Ｎ））の合計とする。ここで、ａ，ｂは重み付け係数であり、試行錯誤的、経験的に決定するパラメータとする。
【００５８】（ステップＳＴ６：淘汰）ステップＳＴ４で計算された遺伝子表現毎の適応度の結果に基づいて、適応度の大きい順に順位をつける。この順位に従い、以下に示すようにして次の世代の親となる遺伝子表現を選ぶ。親の数の半数の遺伝子表現は順位１位から順番に選ぶ。一方、残りの半数の遺伝子表現は、順位が先のものほど選ばれやすいようにしながら、順位に従ってとびとびに選ぶ。
【００５９】（ステップＳＴ７：終了判定）ステップＳＴ６で選ばれた順位が１位の遺伝子表現における処理完了時間が、指定された条件を満たしているか、あるいはステップＳＴ２からステップＳＴ６までの処理がなされた回数である世代数が、あらかじめ指定された上限値に達した場合（ＳＴ７：Ｙｅｓ）には、遺伝的アルゴリズムによる遺伝子表現のパターンサーチを終了する。一方、そうでない場合（ＳＴ７：Ｎｏ）には、ステップＳＴ８で世代数を１増やしてステップＳＴ２へ戻る。
【００６０】上述したように、本実施の形態に係る被作業体の分配方法および配置方法においては、上記のような作用により、所定の作業区画５１上へのワークの配置と、作業区画５１上に同時に配置されたワーク５２に対する作業を複数の機械を用いて行う工程とを繰り返すことによって全てのワーク５２に対する作業を行う場合、作業区画５１上に同時に配置するワーク５２の組み合わせを、遺伝的アルゴリズムを適用し、全てのワーク５２の作業を完了するまでに要する時間を最小にし、かつ作業時間のバラツキを最小とするような目的関数の元、パターンサーチ、および動作シミュレーションによる各パターンにおける作業時間に基づく淘汰を繰り返すことによって決定することができる。
【００６１】以上により、全てのワーク５２の作業を完了するまでに要する時間を短縮し、かつ組ごとの作業時間バラツキも最小とすることができ、もって、作業効率の向上を図ることが可能な被作業体の分配方法および配置方法を実現することが可能となる。
【００６２】なお、本実施の形態においては、作業区画５１を平面とし、平面上にワーク５２が重ならないように配置する作業方法についてのみ示したが、立体の作業区画に段積みする場合においても、あるいは、パレットのような搬送機材にワーク５２をパッキングするような場合においても、全く同様の遺伝子表現を用いて、作業時間の最小化、作業時間のバラツキ最小化、段取り時間の最小化、作業区画数の最小化を実現することが可能となる。
【００６３】（第２の実施の形態）本発明の第２の実施の形態に係る被作業体の分配方法および配置方法について、図４から図５を用いて説明する。
【００６４】第１の実施の形態では、遺伝的アルゴリズムで得られた遺伝子表現のパターンに基づいて動作シミュレーションを行い、処理完了時間を計算する必要がある。しかしながら、この動作シミュレーションには、相当の計算時間がかかる。もちろん、計算時間を十分かけることができる状況ではこれでよい。しかしながら、多少の厳密性には目をつぶって短時間で相当の解を得たいという状況もある。そのような場合には、動作シミュレーションを行わずとも処理完了時間を概算することが可能な本実施の形態に係る被作業体の分配方法および配置方法は効果的である。
【００６５】本実施の形態に係る被作業体の分配方法および配置方法では、ワ−クの組（Ｇ１、・・・、ＧＮ）を、動作シミュレーションによる処理完了時間を求めること無く決定する。これは、あるワ−クの組Ｇを決めるとき、その時点でまだワ−クの組Ｇに入っていないワ−クＷｉの中からいくつかのワ−クＷを選び、与えられた作業区画５１の上にそれらのワ−クＷの仕事量の合計が最も多くなるようにワ−クの組Ｇを次々に決定する方法である。さらには、作業区画５１毎の作業時間のバラツキを最小とする場合には、本処理方法において決定したワークの組み合わせ結果を初期固体として、第１の実施の形態に示す遺伝子操作を実施することで、バラツキの減少を図ることができる。
【００６６】本実施の形態においてもワ−クの組Ｇは遺伝的アルゴリズムを応用して決定する。ワ−クの組Ｇに対応する個体の遺伝子表現の一例を図４に示す。図４に示すように、各個体はワ−ク並びＰと配置方向Ｄという２種類の遺伝子からなる。
【００６７】ワ−ク並びＰは、作業区画５１に配置するワ−ク番号Ｗｉを並べたものである。配置方向Ｄは、ワ−クを作業区画５１の上に配置するときに、縦横が元の状態であれば０、９０度回転して縦横の関係を入れ替える場合は１という値をとる。図４の例では、ワ−クＷ７とワークＷ８とは縦横入れ替え、ワ−クＷ５とワ−クＷ１とは縦横は元の状態で配置することを示している。ワ−ク並びＰの順番は、ワ−クを第１の実施の形態で説明したワ−ク配置ル−ルに従って作業区画５１の上に配置する順序を意味している。
【００６８】このような遺伝的アルゴリズムを応用した本実施の形態に係る被作業体（ワーク）の分配方法および配置方法の動作手順は、図５のフローチャートに示す通りである。以下に、このフローチャートの流れに沿って、本実施の形態に係る被作業体の分配方法および配置方法について説明する。
【００６９】（ステップＳＴ１１：未決定ワ−ク集合の初期設定）まず、未決定ワーク集合の初期設定を行う。ここでは、未決定ワ−ク集合Ｓ０＝｛Ｗ１、・・・、ＷＩ｝とする。さらに、未決定ワ−クのそれぞれと対になるようにＳ０と同じ集合Ｓｉ（Ｓ１，Ｓ２，・・・ＳＩ）を各初期個体と対となるように作成する。
【００７０】（ステップＳＴ１２：初期個体の生成）ステップＳＴ１１で設定された未決定ワ−ク集合Ｓｉから、ランダムにワ−クを１つずつ取り出し、それをワ−ク並びＰに入れて初期個体を生成する。したがって、初期個体は、未決定ワ−ク集合の中の要素の数Ｉだけできる。同時に未決定ワ−ク集合Ｓｉ（Ｓ１，Ｓ２，・・・ＳＩ）から各初期個体として取り出したワークを除く。なお、ここで配置方向Ｄはランダムに設定する。
【００７１】（ステップＳＴ１３：ワーク追加）初期固体ｉについて未決定ワ−ク集合Ｓｉの中から、個体の遺伝子表現のワ−ク並びＰにないワ−クをランダムに１つ選択する。更に、選択されたワ−クを、この個体のワ−ク並びＰに挿入することができるかどうかを調べる。選ばれたワ−クをワ−ク並びＰの１番目にする場合、２番目にする場合、・・・、と順番に全部のワ−クがワ−ク配置ル−ルに従って作業区画５１に入るかどうかを調べる。配置方向Ｄは２通りとも調べる。作業領域に入ることがわかった場合は、この調べはそこで打ち切り、そのワ−ク並びＰおよび配置方向Ｄを新しい遺伝子表現とする個体を作る。最後まで調べてできないということがわかった場合は、新しい個体は作らずに元の個体を残す。このように作成した遺伝子表現の世代数を更新する。
【００７２】（ステップＳＴ１４：仕事量の和の計算）親と子の全ての個体に対し、表現するワ−ク組合せの仕事量の和を求める。
【００７３】（ステップＳＴ１５：淘汰）ステップＳＴ１４で求められた仕事量の和について、大きい順にすべての個体に対し順位をつける。この順位に従い、次のようにして次の世代の親を第１の所定個数選ぶ。親の数の半数は順位１位から順番に選ぶ。残りの半数は、順位が先のものほど選ばれやすいように、順位に従ってとびとびに選ぶ。
【００７４】（ステップＳＴ１６：遺伝アルゴリズムの終了判定）順位１位の個体の仕事量の和が指定された条件を満たしている場合か、あるいは世代数があらかじめ指定された上限値に達した場合（ＳＴ１６：Ｙｅｓ）には、ステップＳＴ２１の処理を行う。そうでない場合（ＳＴ１６：Ｎｏ）には、世代数を１増やして（ＳＴ１７）、ステップＳ１８の処理を行う。
【００７５】（ステップＳＴ１８：交叉）ここでは、各親の遺伝子表現に基づいて交叉処理を行い子の遺伝子表現を作成する。この交叉は、ワ−ク並びＰの遺伝子か、あるいは配置方向Ｄの遺伝子かのどちらかに対して行う。ワ−ク並びＰに対する交叉は、ワ−ク並びＰの遺伝子の部分列の移動である。まず、部分列の先頭、最後および移動先を、ランダムに選択する。ワ−ク並びＰの遺伝子の部分列を移動するときは、対応する配置方向Ｄも対応する部分列を同じ位置へ移動させる。配置方向Ｄに対する交叉は、配置方向Ｄの遺伝子の部分列をランダムに選択し、部分列の０／１デ−タを入れ替える。すなわち、０なら１に、１なら０にそれぞれ置き替える。
【００７６】（ステップＳＴ１９：作業領域内の配置可能性のチェック）ここでは、ステップＳＴ１８の交叉処理によって作成された子に対応するワ−ク組合せが、第１の実施の形態で説明したワ−ク配置ル−ルに従って作業区画５１内に配置できるかどうかを調べる。作業区画５１に配置することができる場合にはステップＳＴ１３に移行し、作業区画５１に配置することができない場合には、ステップＳＴ２０の処理を行う。
【００７７】（ステップＳ２０：ワ−クの入れ替え）未決定ワ−ク集合Ｓの中から、個体の遺伝子表現のワ−ク並びＰにないワ−クを１つランダムに選ぶ。同時に、個体の遺伝子表現の中のワ−ク並びＰからワ−クを１つランダムに選び削除する。そして、削除されたワ−ク並びＰに、先に選んだワ−クを挿入することができるかどうかを調べる。選ばれたワ−クをワ−ク並びＰの１番目に挿入する場合、２番目に挿入する場合、・・・、と順番に全部のワ−クが、第１の実施の形態で説明したワ−ク配置ル−ルに従って作業区画５１に入るかどうかを調べる。
【００７８】一方、配置方向Ｄに関しては、「０」を「１」にする場合、「１」を「０」にする場合の２通りとも調べる。作業区画５１に配置できることがわかった場合には、この調べはそこで打ち切り、そのワ−ク並びＰおよび配置方向Ｄを新しい遺伝子表現とする個体を作成する。最後まで調べて、配置できないことがわかった場合には、個体は元のままとする。そして、上述した処理を行った後に、ステップＳＴ１４に移行する。
【００７９】（ステップＳＴ２１：未決定ワ−ク集合の更新）ステップＳＴ１６において、順位１位の個体の仕事量の和が指定された条件を満たしている場合か、あるいは世代数があらかじめ指定された上限値に達した場合には、未決定ワ−ク集合Ｓｉ（Ｓ１，Ｓ２，・・・ＳＩ）から、順位１位の個体の遺伝子表現のワ−ク並びＰにあるワ−クをすべて削除し、ステップＳＴ２２の処理を行う。
【００８０】（ステップＳＴ２２：終了判定）未決定ワ−ク集合Ｓｉが空集合なら終了し、そうでない場合には、ステップＳＴ１２へ戻る。
【００８１】上述したように、本実施の形態に係る被作業体の分配方法および配置方法においては、上記のような作用により、所定の作業区画５１上へのワークの配置と、作業区画５１上に同時に配置されたワークに対する作業を複数の機械を用いて行う工程とを繰り返すことによって全てのワークに対する作業を行う場合、作業区画５１上に同時に配置するワークの組み合わせの結果、各組の仕事量が極力多くなるように、遺伝的アルゴリズムを適用し、パターンサーチを繰り返すことによって決定することができる。
【００８２】この方法によって決定された作業区画５１上に同時に配置されるワークの組み合わせは、同程度の作業量のワークを同一の作業区画５１上に配置するものであるために、必ずしも全てのワーク５２の作業完了までに要する作業時間を最短にするパターンとは限らないものの、動作シミュレーションを行う必要が無いので、短時間で解を得ることができる。
【００８３】（第３の実施の形態）本発明の第３の実施の形態に係る被作業体の分配方法および配置方法について、図６を用いて説明する。
【００８４】本実施の形態に係る被作業体の分配方法および配置方法は、作業区画５１に配置すべきワ−クＷ１、・・・、ＷＩが与えられた場合に、ワ−クＷ１、・・・、ＷＩの配置方向と配置場所とを最適に決めることにより、これらのワ−クＷ１、・・・、ＷＩを処理する複数の機械の作業量を平準化する。この場合、ワ−クＷ１、・・・、ＷＩの形状を長方形と見なし、一方、配置方向Ｄとしては、元の縦横の状態、９０度回転した状態、１８０度回転した状態、２７０度回転した状態の４通りを考慮する。
【００８５】このような本実施の形態に係る被作業体（ワーク）の分配方法および配置方法の動作手順は、図６のフローチャートに示す通りである。以下に、このフローチャートの流れに沿って、本実施の形態に係る被作業体の分配方法および配置方法について説明する。
【００８６】（ステップＳＴ３１：初期値集合作成）ワ−クＷ１、・・・、ＷＩを、配置方向Ｄとして４通りを考慮して、第１の実施の形態で説明したワ−ク配置ル−ルに従って、配置可能なワーク並びＰと配置方向Ｄとを全て求める。なお、このとき、各ワ−クの左下頂点の座標と、配置方向Ｄとを後述するステップＳＴ３３における初期値とするので、これらを初期値の集合に入れる。ワ−ク並びＰ１、・・・、ＰＩで、配置方向Ｄ１、・・・、ＤＩが作業区画５１に配置可能であったとすると、初期値はワ−クＷ１の左下頂点の座標、・・・、ワ−クＷＩの左下頂点の座標、配置方向Ｄ１、・・・、ＤＩである。これが初期値集合の１つの要素となる。配置可能な組合せが全部でｎ通りあったとすると、初期値集合はこのような形の要素ｎ個からなる。
【００８７】（ステップＳＴ３２：初期値設定）ステップＳＴ３１で作成された初期値集合から要素を１つ取り出す。そして、その要素を初期値集合から除く。この取り出した要素である初期値に対応するＩ個のワ−クをずらして作業区画５１内に置くとき、それらの左下頂点の座標を(ｘ(１),ｙ(１))、・・・、(ｘ(Ｉ),ｙ(Ｉ))と表すことにする。(ｘ(１),ｙ(１))、・・・、(ｘ(Ｉ),ｙ(Ｉ))の現在の値が初期値である。配置方向Ｄは仕事量の計算には用いるが一定とし、変数とはしない。
【００８８】（ステップＳＴ３３：非線形計画問題の作成）各ワ−クＷ１、・・・、ＷＩは複数の仕事を含み、それらはワ−ク内のどこにあるかはわかっている。作業区画５１はｎ台の機械に対応してｎ個の領域に分割している。そこで、ワ−クを、その配置方向Ｄを変えないで平行移動だけでずらして配置位置を決めると、ワ−ク内の各仕事はどの機械の分割領域に属するかがわかる。ワ−ク内の仕事には仕事量が与えられているので、このとき各分割領域に属する仕事量の合計が計算可能となる。
【００８９】ワ−ク内の仕事が複数の分割領域にまたがる場合には、按分して仕事量を求める。すなわち、機械ｋが処理すべき仕事量の合計をｆ(ｋ)とすると、ｆ(ｋ)はＩ個のワ−クの左下頂点の座標(ｘ(１),ｙ(１))、・・・、(ｘ(Ｉ),ｙ(Ｉ))の関数ということになる。目的はワ−クを複数の機械各々の仕事量ができるだけ均等に近くなるように、あるいは複数の機械の中で最も仕事量が多くなる機械の仕事量ができるだけ少なくなるように、決められた作業領域の中に最適に配置することである。したがって、つぎのようにして目的関数を作る。
目的関数＝ｆ(１)、・・・、ｆ(Ｎ) の分散、あるいは 目的関数＝ｆ(１)、・・・、ｆ(Ｎ) の中で１番大きいものとする。
【００９０】この場合、ワ−クを、その配置方向Ｄを変えないで平行移動だけでずらすのであるが、自由自在にずらすことができるとも限らない。どのワ−クも与えられた作業領域内に入っていなければならないし、どの２つのワ−クも重なってはいけない。これらは制約条件と呼ばれる。
【００９１】よって、配置方向Ｄから決まる各ワ−クの横の長さをａ(１)、・・・、ａ(Ｉ)、縦の長さをｂ(１)、・・・、ｂ(Ｉ)、作業領域の横の長さをＬｘ、縦の長さをＬｙとすると、これらの制約条件はつぎのように書ける。すべてのｉ＝１、・・・、Ｉに対して０≦ｘ(ｉ)≦Ｌｘ−ａ(ｉ)０≦ｙ(ｉ)≦Ｌｙ−ｂ(ｉ)ｉに等しくないすべてのｊに対してＵ(|(x(i)＋a(i)／2)−(x(j)＋a(j))|−(a(i)＋a(j))／2)＋Ｕ(|(y(i)＋b(i)／2)−(y(j)＋b(j))|−(b(i)＋b(j))／2)≧0上の不等式で用いた関数Ｕ＝Ｕ(t)はｔ＜０ではＵ(t)＝ｔ、ｔ≧０ではＵ(t)＝０という関数である。
【００９２】（ステップＳＴ３４：非線形計画問題を解く）上述したようにステップＳＴ３３で作成した目的関数と制約条件とは、いずれもＩ個のワ−クの左下頂点の座標(ｘ(１),ｙ(１))、・・・、(ｘ(Ｉ),ｙ(Ｉ))の関数である。そして、その意味は制約条件のもとで目的関数を最小にするように変数(ｘ(１),ｙ(１))、・・・、(ｘ(Ｉ),ｙ(Ｉ))を決定することである。これは、数理計画法の分野でいう非線形計画問題である。そこで、非線形計画法の適当なアルゴリズムを使って答えを求める。
【００９３】（ステップＳＴ３５：解の格納）上記ステップＳＴ３４で得た解のうち、目的関数値を目的関数値集合に入れる。また、変数(ｘ(１),ｙ(１))、・・・、(ｘ(Ｉ),ｙ(Ｉ))と配置方向Ｄ１、・・・、ＤＩを解集合に入れる。
【００９４】（ステップＳＴ３６：終了判定）ここでは、判定終了を行い、初期値集合が空集合の場合には次のステップＳＴ３７へ移行し、初期値集合が空集合ではない場合には、ステップＳＴ３２へ戻る。
【００９５】（ステップＳＴ３７：最適解抽出）ここでは、目的関数値集合の要素の中で最小のもの（目的関数）を見つける。その最小の目的関数に対応する変数(ｘ(１),ｙ(１))、・・・、(ｘ(Ｉ),ｙ(Ｉ))と配置方向Ｄ１、・・・、ＤＩを解集合から取り出す。これが目的とする最適解である。
【００９６】上述したように、本実施の形態に係る被作業体の分配方法および配置方法においては、上記のような作用により、所定の作業区画５１上へのワークの配置と、作業区画５１上に同時に配置されたワークに対する作業を複数の機械を用いて行う工程とを繰り返すことによって全てのワークに対する作業を行う場合、作業区画５１上に同時に配置するワークの組み合わせについての配置場所を、非線形計画問題の解法を適用して決定することができる。
【００９７】本実施の形態に係る被作業体の分配方法および配置方法は、第１の実施の形態や、第２の実施の形態において、作業区画５１上で同時に配置されるワークの組み合わせが遺伝的アルゴリズムを用いて決定された後段として用いる。つまり、第１の実施の形態および第２の実施の形態では、作業区画５１上で同時配置可能という観点からワークの組み合わせが決定されている。そして、配置に関しては、他のワークとの隣接関係のみが定義されているだけであり、配置場所の詳細までは決定されない。したがって、本実施の形態を用いて作業区画５１上におけるワークの詳細な配置場所を決定することによって、作業時間を更に短縮することが可能となる。
【００９８】以上、本発明の好適な実施の形態について、添付図面を参照しながら説明したが、本発明はかかる構成に限定されない。特許請求の範囲の発明された技術的思想の範疇において、当業者であれば、各種の変更例及び修正例に想到し得るものであり、それら変更例及び修正例についても本発明の技術的範囲に属するものと了解される。
【００９９】
【発明の効果】以上説明したように、本発明によれば、所定の作業区画上へのワーク配置と、作業区画上に同時に配置されたワークに対する作業を複数機械を用いて行う工程とを繰り返すことによって全てのワークに対する作業を行う場合、作業区画上に同時に配置するワークの組み合わせ、およびその配置位置の適正化を図ることができる。
【０１００】以上により、全てのワークの作業を完了するまでに要する時間を短縮し、もって、作業効率の向上を図ることが可能な被作業体の分配方法および配置方法を実現することができる。
【出願人】 【識別番号】０００００４１２３
【氏名又は名称】日本鋼管株式会社
【住所又は居所】東京都千代田区丸の内一丁目１番２号
【出願日】 平成１３年１１月５日（２００１．１１．５）
【代理人】 【識別番号】１０００５８４７９
【弁理士】
【氏名又は名称】鈴江 武彦 （外４名）
【公開番号】 特開２００３−１４０７３０（Ｐ２００３−１４０７３０Ａ）
【公開日】 平成１５年５月１６日（２００３．５．１６）
【出願番号】 特願２００１−３３９６５１（Ｐ２００１−３３９６５１）