(57)【要約】【課題】作業を人やロボットに再割当てする際に、作業が割当てられる人又はロボットの変更を少なくする。【解決手段】入力受付部１１は、組立ライン上の各工程に配置される担当（人又はロボット）の変更内容と、各工程への割り当て対象とする作業の情報と、再編成前に担当に割り当てられていた作業の情報の入力を受け付け、探索指標設定部１２は、入力受付部１１が受け付けた情報に基づいて、担当に作業を割り当てたときに、再編成前に担当に割り当てられていた作業が、異なる担当に割り当てられた数からペナルティ値を算出する。また、探索部１３は、算出されたペナルティ値に基づいて算出した値（例えば、複数種類のペナルティ値の合計）を最小とする条件の最適化問題を解いて作業を担当へ割り当てる組み合わせの作業編成を探索し、探索結果を出力部１４が出力する。【選択図】図２
2018077591.tif 000002
【特許請求の範囲】
【請求項１】
組立ライン上の各工程に配置される人又はロボットの変更内容と、前記各工程への割り当て対象とする作業の情報と、を含む再編成情報と、再編成前に前記人又は前記ロボットに割り当てられていた作業の情報を含む編成情報と、の入力を受け付ける入力受付部と、
前記再編成情報に基づいて前記人または前記ロボットに前記作業を割り当てたときに、前記編成情報において前記人又は前記ロボットに割り当てられていた作業が、異なる人又はロボットに割り当てられた数から評価値を算出する算出部と、
算出された前記評価値又は該評価値に基づく値を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索する探索部と、
前記探索部が探索した作業編成を出力する出力部と、
を備える作業編成装置。
【請求項２】
前記算出部は、前記再編成情報において新たに追加された人又はロボットへ割当てられた作業、及び前記再編成情報において削除された人又はロボットに割当てられていた作業を、前記異なる人又はロボットに割当てられた作業に含めないことを特徴とする請求項１に記載の作業編成装置。
【請求項３】
前記作業の情報には、前記作業の順序についての制約条件が含まれ、
前記算出部は、さらに、前記人又は前記ロボットに割当てられた作業の順序が、前記人又は前記ロボットの配置順と矛盾する数から評価値を算出することを特徴とする請求項１又は２に記載の作業編成装置。
【請求項４】
前記算出部は、さらに、前記人又は前記ロボットに割当てられた作業に必要な時間のばらつきに関する値から評価値を算出することを特徴とする請求項１〜３のいずれか一項に記載の作業編成装置。
【請求項５】
前記探索部は、算出された複数の前記評価値の合計を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索することを特徴とする請求項３又は４に記載の作業編成装置。
【請求項６】
前記探索部は、算出された複数の前記評価値に予め定められている重み係数を乗じた値の合計を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索することを特徴とする請求項３又は４に記載の作業編成装置。
【請求項７】
前記入力受付部は、さらに、前記評価値の許容範囲と、最大探索時間の入力を受け付け、
前記探索部は、前記評価値が前記許容範囲に入るまで、又は探索に要した時間が前記最大探索時間を超えるまで、探索を実行することを特徴とする請求項１〜６のいずれか一項に記載の作業編成装置。
【請求項８】
前記算出部は、前記再編成情報に基づいて前記人又は前記ロボットに前記作業を割り当てる初期割り当てを複数生成し、
前記探索部は、複数の前記初期割り当てそれぞれに基づいて、前記作業編成を複数探索し、
前記出力部は、前記探索部が探索した複数の作業編成を出力する、ことを特徴とする請求項１〜７のいずれか一項に記載の作業編成装置。
【請求項９】
前記入力受付部が、前記組立ライン上の各工程に配置される人又はロボットの変更内容として、前記各工程に配置される人又はロボットの追加数又は削除数の入力を受け付けた場合に、
前記算出部は、前記人又はロボットを追加する位置を、前記追加数で前記組立ラインを略等分する位置とする、又は、前記組立ライン上から削除する人又はロボットを、前記組立ラインを前記削除数で略等分する位置の人又はロボットとする、ことを特徴とする請求項１〜８のいずれか一項に記載の作業編成装置。
【請求項１０】
組立ライン上の各工程に配置される人又はロボットの変更内容と、前記各工程への割り当て対象とする作業の情報と、を含む再編成情報と、再編成前に前記人又は前記ロボットに割り当てられていた作業の情報を含む編成情報と、の入力を受け付け、
前記再編成情報に基づいて前記人または前記ロボットに前記作業を割り当てたときに、前記編成情報において前記人又は前記ロボットに割り当てられていた作業が、異なる人又はロボットに割り当てられた数から評価値を算出し、
算出された前記評価値又は該評価値に基づく値を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索し、
探索した前記作業編成を出力する、
処理をコンピュータが実行することを特徴とする作業編成方法。
【請求項１１】
組立ライン上の各工程に配置される人又はロボットの変更内容と、前記各工程への割り当て対象とする作業の情報と、を含む再編成情報と、再編成前に前記人又は前記ロボットに割り当てられていた作業の情報を含む編成情報と、の入力を受け付け、
前記再編成情報に基づいて前記人または前記ロボットに前記作業を割り当てたときに、前記編成情報において前記人又は前記ロボットに割り当てられていた作業が、異なる人又はロボットに割り当てられた数から評価値を算出し、
算出された前記評価値又は該評価値に基づく値を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索し、
探索した前記作業編成を出力する、
処理をコンピュータに実行させるための作業編成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、作業編成装置、作業編成方法及び作業編成プログラムに関する。
【背景技術】
【０００２】
従来、製品の組立を行う組立ラインの各工程へ作業を割り当てる作業編成は、各工程における作業順序の遵守や作業量の平準化などを考慮して最適化している。この最適化処理は、手作業では困難なことから、従来から様々なアルゴリズムが提案されてきている。
【０００３】
また、各工程への作業の割当ては、組立ラインを最初に立ち上げるときのみならず、生産変動やリソース変動などにより組立ラインを再編成する際にも必要となる（例えば特許文献１等参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平７−１８２４２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、組立ラインを再編成する場合、作業を担当する人やロボットが変更されると人の再教育やロボットへの再教示等の準備作業が必要となる。この場合、準備作業には手間と時間がかかる。
【０００６】
１つの側面では、本発明は、作業を人やロボットに再割当てする際に、作業が割当てられる人又はロボットの変更を少なくすることが可能な作業編成装置、作業編成方法及び作業編成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
一つの態様では、作業編成装置は、組立ライン上の各工程に配置される人又はロボットの変更内容と、前記各工程への割り当て対象とする作業の情報と、を含む再編成情報と、再編成前に前記人又は前記ロボットに割り当てられていた作業の情報を含む編成情報と、の入力を受け付ける入力受付部と、前記再編成情報に基づいて前記人または前記ロボットに前記作業を割り当てたときに、前記編成情報において前記人又は前記ロボットに割り当てられていた作業が、異なる人又はロボットに割り当てられた数から評価値を算出する算出部と、算出された前記評価値又は該評価値に基づく値を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索する探索部と、前記探索部が探索した作業編成を出力する出力部と、を備えている。
【発明の効果】
【０００８】
作業を人やロボットに再割当てする際に、作業が割当てられる人又はロボットの変更を少なくすることができる。
【図面の簡単な説明】
【０００９】
【図１】一実施形態に係る作業編成装置のハードウェア構成を概略的に示す図である。
【図２】作業編成装置の機能ブロック図である。
【図３】組立ラインを説明する説明図である。
【図４】図４（ａ）、図４（ｂ）は、組立ラインにおける作業の再編成について説明するための図である
【図５】作業ＤＢのデータ構造の一例を示す図である。
【図６】組立ラインにおける作業順序を説明する説明図である。
【図７】作業編成装置による再編成処理の一例を示すフローチャートである。
【図８】図７のステップＳ２２の具体的な処理を示すフローチャートである。
【図９】図９（ａ）〜図９（ｃ）は、図７のステップＳ１４を説明するための図である。
【図１０】変形例を示す図である。
【発明を実施するための形態】
【００１０】
以下、作業編成装置の一実施形態について、図１〜図９に基づいて詳細に説明する。
【００１１】
図１には、一実施形態に係る作業編成装置１０のハードウェア構成が示されている。本実施形態の作業編成装置１０は、例えばＰＣ（Personal Computer）などの情報処理装置であり、図１に示すように、ＣＰＵ（Central Processing Unit）１９０、ＲＯＭ（Read Only Memory）１９２、ＲＡＭ（Random Access Memory）１９４、記憶部（ここではＨＤＤ（Hard Disk Drive））１９６、ネットワークインタフェース１９７、及び可搬型記憶媒体用ドライブ１９９、表示部１９３、入力部１９５等を備えている。表示部１９３は液晶ディスプレイ等を含み、入力部１９５は、キーボードやマウス、タッチパネル等を含む。これら作業編成装置１０の構成各部は、バス９８に接続されている。作業編成装置１０では、ＲＯＭ１９２あるいはＨＤＤ１９６に格納されているプログラム（作業編成プログラムを含む）、或いは可搬型記憶媒体用ドライブ１９９が可搬型記憶媒体１９１から読み取ったプログラム（作業編成プログラムを含む）をＣＰＵ１９０が実行することにより、図２に示す各部の機能が実現される。なお、図２には、作業編成装置１０のＨＤＤ１９６等に格納されている作業ＤＢ（database）２についても図示されている。なお、可搬型記憶媒体１９１は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢ（Universal  Serial  Bus）メモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリなどである。
【００１２】
図２は、作業編成装置１０の機能ブロック図である。作業編成装置１０では、ＣＰＵ１９０がプログラムを実行することにより、図２に示すように、入力受付部１１と、算出部としての探索指標設定部１２と、探索部１３と、出力部１４と、を備える。
【００１３】
作業編成装置１０は、生産変動やリソース変動などにより組立ラインの再編成を行う必要が生じたときに、作業ＤＢ２や再編成条件３などの入力データをもとに、各工程に対して作業を再割り当てする再編成を行い、作業再編成の結果を出力する装置である。
【００１４】
図３は、組立ラインを説明する説明図である。図３に示すように、製品の組み立てを行う組立ライン２０は、一例として、工程Ａから工程Ｄの４工程を有するものとする。
【００１５】
組立ライン２０では、ベルトコンベア（不図示）などにより製品を工程から工程へ搬送する。組立ライン２０の各工程には、ロボット２１Ａまたは作業員２１Ｂ〜２１Ｄが配置される。図３の例では、工程Ａにはロボット２１Ａが配置され、工程Ｂ〜工程Ｄには作業員２１Ｂ〜２１Ｄがそれぞれ配置されている。工程Ａから工程Ｄに配置されたロボット２１Ａまたは作業員２１Ｂ〜２１Ｄは、組立ライン２０において搬送される製品に対して作業編成又は作業再編成により割り当てられた作業を実施して製品を製造する。
【００１６】
なお、組立ライン２０の構成例は、図３に例示した構成に限定するものではない。例えば、組立ライン２０は、４工程以上の工程数を有してもよい。また、ロボット２１Ａの配置位置は工程Ａ以外であってもよく、ロボットは複数あってもよい。
【００１７】
図４（ａ）、図４（ｂ）は、組立ライン２０における作業の再編成について説明するための図である。図４（ａ）は、再編成前の作業割当てを示す図であり、図４（ｂ）は、再編成後の作業割当てを示す図である。図４（ａ）、図４（ｂ）の例では、再編成前には、担当（人又はロボット）の数が３であったのに対し、再編成後には、担当の数が１増え、担当順の３番目に配置されている。本実施形態では、図４（ａ）、図４（ｂ）に示すように、各担当に割当てられる作業の合計作業時間がほぼ均等になるように作業が割当てられる。また、本実施形態では、各担当に割当てられる作業の順番が、担当の並び順と矛盾しないように各担当に作業が割当てられる。更に、本実施形態では、各作業が割当てられる担当が極力変更しないように、すなわち編成前から存在する作業者やロボットに対して、新たな作業が追加されるのが極力少なくなるように作業が割当てられる。
【００１８】
なお、図４（ａ）、図４（ｂ）では、担当の追加について示しているが、担当を削除する場合も本実施形態で説明する再編成処理に含まれる。また、生産変動（作業の数の増減）の場合にも、タクトタイムが増減し、結果として担当の数が増減するため、本実施形態で説明する再編成処理に含まれる。
【００１９】
図２に戻り、入力受付部１１は、ユーザの操作入力などにより再編成条件３の入力を受け付ける。また、入力受付部１１は、作業編成において割り当て対象となる作業についての各種情報が格納された作業ＤＢ２を参照する。ここで、作業ＤＢ２は、図５に示すようなデータ構造を有する。具体的には、作業ＤＢ２は、図５に示すように、「作業ＩＤ」、「先行制約番号組」、「作業時間[ｓ]」、「再編成前の担当番号」、「担当変更によるペナルティ値」の各フィールドを有する。「作業ＩＤ」のフィールドには、作業の識別番号（図４（ａ），図４（ｂ）の「Ｊｏｂ」に続く２桁の番号）が格納される。「先行制約番号組」のフィールドには、作業の親子関係を示す番号組が格納される。先行制約番号組からは、どの作業の次にどの作業を行う必要があるかを認識することができる。なお、先行制約番号組の詳細については後述する。「作業時間[ｓ]」のフィールドには、各作業に要する時間（秒）が格納される。「再編成前の担当番号」のフィールドには、再編成前に各作業が割り振られていた担当の番号が格納される。「担当変更によるペナルティ値」のフィールドには、各作業の担当が変更になった場合のペナルティ値が格納される。このペナルティ値が大きいほど、専門性が高く、担当が変更になると再教育や再教示の手間や時間が多くかかる作業を意味している。
【００２０】
ここで、作業ＤＢ２の先行制約番号組について詳細に説明する。先行制約番号組は、製品を完成品に組み立てあげるまでの作業の順序についての制約条件を示す順序制約を示す番号組である。具体的には、順序制約は、作業の各々をノードとし、完成品に至るまでのノードの順序関係を有向非循環グラフで表現可能な情報である。
【００２１】
図６は、組立ライン２０における作業順序を説明する説明図である。図６において、ノード３０は、作業を表す。また、２つのノード３０間に先行関係がある場合は、先に行う作業（親ノード）からあとに行う作業（子ノード）へ矢印を引いている。図６に示すように、完成品に至るまでのノード３０の順序関係（作業順序）は有向非循環グラフで表現される。
【００２２】
この順序関係を表すため、作業ＤＢ２では、順序制約をもとに、作業（ノード３０）に「♯［ファミリー番号］−［世代番号］」とする番号を付与している。具体的には、親ノードの番号が♯ｉ−ｊである場合に、子ノードに対して♯ｉ−（ｊ＋１）の番号が付与される。また、子ノードが複数ある分岐部分３１では、２つ目以降の子ノードに対して、ｉの代わりに新規にファミリー番号ｋが付与され、親ノードに♯ｋ−０、子ノードに♯ｋ−１が新たに付与される。
【００２３】
また、親ノードが複数ある合流部分３２では、それぞれの親ノードから子ノードに対して複数の番号が付与されるが、その次の子ノードに全ての番号を引き継ぐ必要はない。すなわち、合流部分３２の次の子ノードについては、ファミリー番号の最も若い番号（付与順の古い番号）が付与される。
【００２４】
作業編成装置１０では、この作業（ノード３０）に付与された番号を用いて、「同一ファミリー内の上の世代（親）を下の世代（子）より後の工程に割り当てた場合にペナルティを追加」することで、先行制約に対する違反の有無を評価できる。
【００２５】
図２に戻り、再編成条件３は、作業の再編成を行うための各種条件であり、入力部１９５を介した操作入力などによりユーザより設定される。例えば、再編成条件３には、「各ペナルティ値の重み」、「利用するノルム」、「初期割当てを行うアルゴリズム」、「利用する探索アルゴリズム」、「探索停止条件」が含まれる。ここで、本実施形態では、探索指標設定部１２が算出するペナルティ値が３種類ある。したがって、ユーザは、これらペナルティ値のどれを重要視するかを設定するための重みを設定する。この重みが、再編成条件３に含まれる「各ペナルティ値の重み」である。また、本実施形態では、探索指標設定部１２は、各担当の総作業時間（サイクルタイム）のばらつきを求める際に各担当のサイクルタイムと全担当のサイクルタイムの平均とのノルムを計算する。したがって、ユーザは、ノルムとして、残差平方和（Ｌ２ノルム）や、差の絶対値の総和（Ｌ１ノルム）などのいずれを用いるかを設定する。このノルムが、再編成条件３に含まれる「利用するノルム」である。また、本実施形態では、ユーザは、作業の各工程への初期割り当てを行うアルゴリズムとして、例えばＦｉｒｓｔ  Ｆｉｔ法、Ｓｔｒｏｎｇｅｓｔ  Ｆｉｔ法などから選択する。また、ユーザは、作業を各工程に割り当てる組み合わせを求める際の探索アルゴリズムとして、例えば山登り法、タブーサーチ、焼きなまし法などからを選択する。これら選択されたアルゴリズムが、再編成条件３に含まれる「初期割当てを行うアルゴリズム」、「利用する探索アルゴリズム」である。更に、ユーザは、作業を各工程に割り当てる組み合わせを探索する際の停止条件として、許容ペナルティ値や最大探索時間などを設定する。この停止条件が、再編成条件３に含まれる「探索停止条件」である。
【００２６】
探索指標設定部１２は、再編成条件３および作業ＤＢ２の作業情報をもとに、作業を各工程に再割当てする組み合わせを求める組み合わせ最適化問題を解く際の評価値を算出する。具体的には、探索指標設定部１２は、作業Ｊ１、Ｊ２（ノード３０）に付与された番号を用いて、先行制約に対する違反の有無を評価する評価値（ペナルティ値）を算出する。また、探索指標設定部１２は、各工程（Ａ〜Ｄ）におけるサイクルタイムと、サイクルタイムの平均との差を示す評価値（ペナルティ値）を算出する。また、探索指標設定部１２は、再編成前と異なる担当に割当てられた作業の数に対応する評価値（ペナルティ値）を算出する。
【００２７】
探索部１３は、探索指標設定部１２より算出された評価値に重み係数を乗じて得られる値の和を最小とする条件の最適化問題を解いて作業を各工程（Ａ〜Ｄ）へ割り当てる組み合わせの作業編成を探索する。
【００２８】
出力部１４は、探索部１３より探索された作業編成（再編成結果）をファイル出力やディスプレイへの表示出力などで出力する。
【００２９】
（作業編成装置１０の再編成処理）
次に、本実施形態の作業編成装置１０による再編成処理について、図７、図８のフローチャートに沿って、その他図面を適宜参照しつつ詳細に説明する。
【００３０】
図７の処理では、まず、ステップＳ１０において、入力受付部１１は、再編成条件３や作業ＤＢ２などのデータ入力を受け付ける。
【００３１】
次いで、ステップＳ１２では、探索指標設定部１２が、担当の追加削除位置を計算する。具体的には、探索指標設定部１２は、元々の担当の並び順のどこに新規の担当を追加するか、又は元々の担当の並び順からどの担当を削除するか、を計算する。ここで、担当の追加・削除位置については、なるべく等間隔とする方が、追加された担当に作業を移動させたり、削除された担当から作業を移動させたりするのに都合がよい。したがって、以下のようにして、担当の追加削除位置を計算する。
【００３２】
再編成前の担当数をＮ、増減分をｄとすると、（ｄ＋１）等分する位置に担当を追加したり、（ｄ＋１）等分する位置から担当を削除する。具体的には、ｉ番目の追加の場合には、ｉＮ／（ｄ＋１）の位置（ただし、整数になる場合は直後の位置）に担当を追加する。また、ｉ番目の削除はｉＮ／（ｄ＋１）の小数点以下を繰り上げた位置の担当を削除する。
【００３３】
図９（ａ）には、担当が５である場合に担当を２追加する場合の例、すなわち、Ｎ＝５、ｄ＝２で担当を追加する例が示されている。図９（ａ）の例では、１番目の追加は、１×５／３≒１．７となるので、１番目の追加は、担当１，２の間となる。また、２番目の追加は、２×５／３≒３．３となるので、２番目の追加は、担当３，４の間となる。
【００３４】
一方、図９（ｂ）には、担当が５である場合に担当を２削除する場合の例、すなわち、Ｎ＝５、ｄ＝２で担当を削除する例が示されている。図９（ｂ）の例では、１番目の削除は、１×５／３≒１．７となるので、１番目の削除は、担当２となる。また、２番目の削除は、２×５／３≒３．３となるので、２番目の削除は、担当４となる。
【００３５】
ここで、追加する担当のほうが追加前の担当よりも多い場合（Ｎ＜ｄの場合）もある。このような場合には、追加する担当を最初に列に並べて、追加前のｉ番目の担当をｉｄ／（Ｎ＋１）の位置に追加するようにすればよい。図９（ｃ）には、追加前の担当が２であり、追加する担当が５である場合の例、すなわち、Ｎ＝２、ｄ＝５の場合の例が示されている。図９（ｃ）の例では、最初に追加する担当を列に並べる。そして、追加前の担当の１番目は、ｉｄ／（Ｎ＋１）＝１×５／３≒１．７となるので、追加する担当の列の前から１番目と２番目の間に配置する。また、追加前の担当の２番目は、ｉｄ／（Ｎ＋１）＝２×５／３≒３．３となるので、追加する担当の列の前から３番目と４番目の間に配置する。
【００３６】
図７に戻り、次のステップＳ１４では、探索指標設定部１２が、再編成条件３に含まれる作業の各工程（各担当）への初期割り当てを生成する。具体的には、探索指標設定部１２は、再編成条件３に含まれる初期割り当てを行うアルゴリズムをもとに、例えばＦｉｒｓｔ  Ｆｉｔ法、Ｓｔｒｏｎｇｅｓｔ  Ｆｉｔ法などのヒューリスティック手法を利用して初期割り当てを生成する。
【００３７】
次いで、ステップＳ１６では、探索指標設定部１２は、作業の各工程（各担当）への割り当てから近傍解を生成する。具体的には、探索指標設定部１２は、割り当てられた作業における２つの作業の入れ替えや１つの作業の移動などを行って近傍解を生成する。
【００３８】
次いで、探索指標設定部１２は、組み合わせ最適化問題を解く際の評価値を算出する（Ｓ１８〜Ｓ２２）。
【００３９】
具体的には、ステップＳ１８において、探索指標設定部１２は、先行制約の違反数（例えば「同一ファミリー内の上の世代（親）を下の世代（子）より後の工程に割り当てた場合にペナルティを追加」）から、違反数に対応するペナルティ値を算出する。
【００４０】
次いで、ステップＳ２０では、探索指標設定部１２が、各担当（２１Ａ〜２１Ｄ）に割り当てられた作業の総作業時間（サイクルタイム）と、サイクルタイムの平均との残差平方和（Ｌ２ノルム）から評価値（ペナルティ値）を算出する。
【００４１】
なお、各担当（２１Ａ〜２１Ｄ）のサイクルタイムと、サイクルタイムの平均との評価値は、本実施形態ではＬ２ノルムとしたが、Ｌ１ノルム（サイクルタイムと、サイクルタイムの平均との差の絶対値の総和）であってもよく、特に限定しない。
【００４２】
次いで、ステップＳ２２では、探索指標設定部１２が、再編成前と異なる担当に割当てられた作業の数に対応するペナルティ値を算出する。具体的には、探索指標設定部１２は、図８のフローチャートに沿った処理を実行する。
【００４３】
図８の処理では、まず、ステップＳ５０において、探索指標設定部１２は、作業の割当て状況（未取得のもの）を１つ取得する。次いで、ステップＳ５２では、探索指標設定部１２が、取得した割当て状況において、担当が変更されているか否かを判断する。このステップＳ５２の判断が否定された場合には、ステップＳ５８に移行するが、肯定された場合には、ステップＳ５４に移行する。
【００４４】
ステップＳ５４に移行すると、探索指標設定部１２は、担当の変更が例外に該当するか否かを判断する。ここで、例外とは、担当を追加する場合における、追加する担当への作業の割当てや、担当を削除する場合における、削除した担当の作業の別の担当への割当て、を意味する。この例外に該当する場合には、ペナルティの対象外となる。ステップＳ５４の判断が肯定された場合、すなわち、担当の変更が例外に該当する場合には、ステップＳ５８に移行する。一方、ステップＳ５４の判断が否定された場合には、ステップＳ５６に移行する。
【００４５】
ステップＳ５６に移行すると、探索指標設定部１２は、ペナルティ値を加算する。この場合、探索指標設定部１２は、作業ＤＢ２を参照し、取得した作業の「担当変更によるペナルティ値」のフィールドに格納されている値をペナルティ値に加算する。その後は、ステップＳ５８に移行する。
【００４６】
ステップＳ５８に移行すると、探索指標設定部１２は、全作業の割当て状況を取得済みであるか否かを判断する。ここでの判断が否定されると、探索指標設定部１２は、ステップＳ５０に戻り、ステップＳ５０〜Ｓ５８の処理を繰り返し実行する。一方、ステップＳ５８の判断が肯定された場合には、図８の全処理を終了し、図７のステップＳ２４に移行する。
【００４７】
なお、上記例では、作業ごとにペナルティ値を異ならせる場合について説明したが、これに限らず、再編成後の担当が人かロボットかに応じてペナルティ値を異ならせることとしてもよい。例えば、ロボットに新たな作業を割り当てることになると、再教示が必要で、人を再教育する場合よりも手間と時間がかかる。したがって、再編成後の担当がロボットの場合ほどペナルティ値を大きくするようにしてもよい。
【００４８】
次いで、ステップＳ２４では、探索部１３は、探索指標設定部１２より算出された評価値（ペナルティ値）をもとに、再編成条件３に含まれる探索アルゴリズムにしたがって、近傍解を採用するか否か、すなわち作業の割り当てを更新するか否かを判断する。
【００４９】
例えば、探索部１３は、ステップＳ１８〜Ｓ２２で算出したペナルティ値の合計が小さくなるときは近傍解を採用することとする。この採用のルールについては、山登り法、タブーサーチ、焼きなまし法などの探索アルゴリズムに準じて異なるものとなり、例えばペナルティ値の合計が大きくなる場合でも近傍解を採用してもよい場合もある。
【００５０】
なお、上記においては、ペナルティ値の合計としているが、ペナルティ値を扱う際に、重み（ｗｉ）を導入し、次式（１）のように、各ペナルティ値（Ｐｉ）の重み付き和で全体のペナルティ値（Ｐ）を算出するようにしてもよい。なお、重み（ｗｉ）については、再編成条件３に含まれ、予めユーザにより設定される。
【００５１】
【数１】
2018077591.tif 000003
【００５２】
また、ペナルティ値を扱う場合、優先順位の高い条件から順にペナルティ（Ｐｉ）を改善するようにしてもよい。例えば、順序制約を満たす組み合わせの作業編成を優先するため、ステップＳ１８で求めた先行制約の違反数に対応するペナルティ値を改善する組み合わせ（近傍解）から求めるようにする。次いで、ステップＳ２０またはステップＳ２２で求めたペナルティ値を改善する組み合わせを求めるようにしてもよい。
【００５３】
また、ペナルティ値を扱う方法の一つとしては、上記の２つの方法を組み合わせであってもよい。なお、組み合わせ方については、ユーザ指定として再編成条件３に含まれていてもよい。
【００５４】
ステップＳ２４の判断が否定された場合、すなわち、作業の割り当てを更新しない場合には、新たな近傍解の生成を行うためステップＳ１６に戻る。なお、ステップＳ１６に戻って、新たな近傍解より探索を行う場合、探索部１３は、組立ライン２０上の各工程に配置されるロボット２１Ａの配置位置の変更またはロボット２１Ａを人（作業員）へ変更して組み合わせの探索をおこなってもよい。この場合には、より広範な条件についての、作業の割り当てを求めることができる。
【００５５】
また、ステップＳ２４の判断が肯定された場合、すなわち、作業の割り当てを更新する場合には、ステップＳ２６に移行し、探索部１３は、これまでの処理で求めていた作業の割り当てを、近傍解の割り当てで更新する。
【００５６】
このように、探索部１３は、工程Ａ〜Ｄに配置されたロボット２１Ａ及び作業員２１Ｂ〜２１Ｄにおけるサイクルタイムを平準化するように、組み合わせ最適化問題を解いて作業を各工程に割り当てる組み合わせを探索する。また、探索部１３は、先行制約の違反数に対応するペナルティ値をもとに、作業を各工程へ割り当てる組み合わせの中から順序制約を満たす組み合わせの作業編成を探索する。また、探索部１３は、再編成後に異なる担当に割当てられた作業の数が少なくなる組み合わせ（工程の保存がされている組み合わせ）を探索する。
【００５７】
次いで、探索部１３は、ステップＳ２６において、再編成条件３に含まれる探索の停止条件（許容ペナルティ値、最大探索時間など）をクリアしているか否かを判定する。
【００５８】
例えば、探索部１３は、ステップＳ１８〜Ｓ２２で算出されたペナルティ値が許容ペナルティ値を満たしている（許容範囲に含まれる）場合は停止条件をクリアしたと判定する。また、探索部１３は、図７の処理の開始から要した時間が最大探索時間を超えた場合は、十分に探索し尽くして停止条件をクリアしたと判定する。上記のように、停止条件をクリアしている場合には、ステップＳ２８の判断が肯定され、ステップＳ３０に移行する。一方、停止条件をクリアしていない場合には、ステップＳ１６に戻る。
【００５９】
停止条件をクリアし、ステップＳ３０に移行すると、出力部１４は、求められた作業の割り当ての結果（再編成結果）を出力する。
【００６０】
以上のような図７、図８の処理が実行されることで、作業の再編成を適切に行うことが可能となっている。
【００６１】
以上詳細に説明したように、本実施形態によると、入力受付部１１は、組立ライン上の各工程に配置される担当（人又はロボット）の変更内容と、各工程への割り当て対象とする作業の情報と、再編成前に担当に割り当てられていた作業の情報の入力を受け付け、探索指標設定部１２は、入力受付部１１が受け付けた情報に基づいて、担当に作業を割り当てたときに、再編成前に担当に割り当てられていた作業が、異なる担当に割り当てられた数からペナルティ値を算出する。また、探索部１３は、算出されたペナルティ値に基づいて算出した値（例えば、複数種類のペナルティ値の合計）を最小とする条件の最適化問題を解いて作業を担当へ割り当てる組み合わせの作業編成を探索し、探索結果を出力部１４が出力する。これにより、再編成後に担当の変更が極力少なくなるような作業編成を生成することができるので、再編成後に必要となる再教育又は再教示を極力少なくすることが可能となる。
【００６２】
また、本実施形態によると、探索指標設定部１２は、例外として、新たに追加された担当へ割当てられた作業、及び削除された担当に割当てられていた作業については、ペナルティ値の算出には含めないこととしている。これにより、必然的に生じる担当の変更については、ペナルティ値の算出に含めないことで、ペナルティ値として適切な値を算出することができる。
【００６３】
また、本実施形態によると、探索指標設定部１２は、担当に割当てられた作業の順序が、担当の配置順と矛盾する数、すなわち、先行制約の違反数に基づいてペナルティ値を算出するので、算出したペナルティ値に基づいて再編成を行うことで、先行制約の違反が極力少ない、製品を組み立てる際の作業の順序にしたがった作業編成を生成することができる。
【００６４】
また、本実施形態によると、探索指標設定部１２は、担当に割当てられた作業に必要な時間（サイクルタイム）のばらつきに関する値、すなわち、サイクルタイムと全担当のサイクルタイムの平均とのノルムに基づいてペナルティ値を算出するので、算出したペナルティ値に基づいて再編成を行うことで、サイクルタイムが平準化された作業編成を生成することができる。
【００６５】
また、本実施形態によると、探索部１３は、算出された複数のペナルティ値に予め定められている重みを乗じた値の合計（上式（１）参照）を最小とする条件の最適化問題を解いて作業を担当へ割り当てる組み合わせの作業編成を探索する。これにより、ペナルティ値の重要度を考慮して、作業編成を探索することができる。
【００６６】
また、本実施形態によると、探索部１３は、評価値が許容範囲（許容ペナルティ値）に入るまで、又は探索に要した時間が最大探索時間を超えるまで、探索を実行する。これにより、十分に探索しつくしたと判断できるときに探索を終了することができる。
【００６７】
なお、上記実施形態では、作業編成装置１０が、図２の各機能を有する場合について説明したが、これに限られるものではない。例えば、図２の各機能を、図１０に示すような、インターネットなどのネットワーク８０に接続されたクラウドサーバ１００が有していてもよい。この場合、利用者端末７０から入力された再編成条件をクラウドサーバ１００が受信し、クラウドサーバ１００において図７、図８の処理を実行することで作業編成を生成する。そして、クラウドサーバ１００から利用者端末７０に作業編成を送信し、利用者端末７０にて受信した作業編成を利用する。なお、クラウドサーバ１００は、国内、海外のいずれに設置されてもよい。
【００６８】
なお、上記実施形態では、ステップＳ２２において、図５の作業ＤＢ２に格納されている「担当変更によるペナルティ値」を用いる場合について説明したが、これに限らず、すべての作業のペナルティ値を同値としてもよい。
【００６９】
なお、上記実施形態では、初期割当てを異ならせることにより得られる再編成結果をユーザに提示し、ユーザに適切な再編成結果を選択させるようにしてもよい。初期割当てを異ならせると、探索アルゴリズムの性質上異なる再編成結果が得られるので、複数の再編成結果を提示することで、ユーザは、ペナルティ値では考慮できていない事項について検討し、より適切な再編成結果を選択することが可能となる。
【００７０】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、処理装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体（ただし、搬送波は除く）に記録しておくことができる。
【００７１】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ（Digital Versatile Disc）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）などの可搬型記録媒体の形態で販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【００７２】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【００７３】
上述した実施形態は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【００７４】
なお、以上の実施形態の説明に関して、更に以下の付記を開示する。
（付記１）  組立ライン上の各工程に配置される人又はロボットの変更内容と、前記各工程への割り当て対象とする作業の情報と、を含む再編成情報と、再編成前に前記人又は前記ロボットに割り当てられていた作業の情報を含む編成情報と、の入力を受け付ける入力受付部と、
前記再編成情報に基づいて前記人または前記ロボットに前記作業を割り当てたときに、前記編成情報において前記人又は前記ロボットに割り当てられていた作業が、異なる人又はロボットに割り当てられた数から評価値を算出する算出部と、
算出された前記評価値又は該評価値に基づく値を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索する探索部と、
前記探索部が探索した作業編成を出力する出力部と、
を備える作業編成装置。
（付記２）  前記算出部は、前記再編成情報において新たに追加された人又はロボットへ割当てられた作業、及び前記再編成情報において削除された人又はロボットに割当てられていた作業を、前記異なる人又はロボットに割当てられた作業に含めないことを特徴とする付記１に記載の作業編成装置。
（付記３）  前記作業の情報には、前記作業の順序についての制約条件が含まれ、
前記算出部は、さらに、前記人又は前記ロボットに割当てられた作業の順序が、前記人又は前記ロボットの配置順と矛盾する数から評価値を算出することを特徴とする付記１又は２に記載の作業編成装置。
（付記４）  前記算出部は、さらに、前記人又は前記ロボットに割当てられた作業に必要な時間のばらつきに関する値から評価値を算出することを特徴とする付記１〜３のいずれかに記載の作業編成装置。
（付記５）  前記探索部は、算出された複数の前記評価値の合計を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索することを特徴とする付記３又は４に記載の作業編成装置。
（付記６）  前記探索部は、算出された複数の前記評価値に予め定められている重み係数を乗じた値の合計を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索することを特徴とする付記３又は４に記載の作業編成装置。
（付記７）  前記入力受付部は、さらに、前記評価値の許容範囲と、最大探索時間の入力を受け付け、
前記探索部は、前記評価値が前記許容範囲に入るまで、又は探索に要した時間が前記最大探索時間を超えるまで、探索を実行することを特徴とする付記１〜６のいずれかに記載の作業編成装置。
（付記８）  前記算出部は、前記再編成情報に基づいて前記人又は前記ロボットに前記作業を割り当てる初期割り当てを複数生成し、
前記探索部は、複数の前記初期割り当てそれぞれに基づいて、前記作業編成を複数探索し、
前記出力部は、前記探索部が探索した複数の作業編成を出力する、ことを特徴とする付記１〜７のいずれかに記載の作業編成装置。
（付記９）  前記入力受付部が、前記組立ライン上の各工程に配置される人又はロボットの変更内容として、前記各工程に配置される人又はロボットの追加数又は削除数の入力を受け付けた場合に、
前記算出部は、前記人又はロボットを追加する位置を、前記追加数で前記組立ラインを略等分する位置とする、又は、前記組立ライン上から削除する人又はロボットを、前記組立ラインを前記削除数で略等分する位置の人又はロボットとする、ことを特徴とする付記１〜８のいずれかに記載の作業編成装置。
（付記１０）  組立ライン上の各工程に配置される人又はロボットの変更内容と、前記各工程への割り当て対象とする作業の情報と、を含む再編成情報と、再編成前に前記人又は前記ロボットに割り当てられていた作業の情報を含む編成情報と、の入力を受け付け、
前記再編成情報に基づいて前記人または前記ロボットに前記作業を割り当てたときに、前記編成情報において前記人又は前記ロボットに割り当てられていた作業が、異なる人又はロボットに割り当てられた数から評価値を算出し、
算出された前記評価値又は該評価値に基づく値を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索し、
探索した前記作業編成を出力する、
処理をコンピュータが実行することを特徴とする作業編成方法。
（付記１１）  前記算出する処理では、前記再編成情報において新たに追加された人又はロボットへ割当てられた作業、及び前記再編成情報において削除された人又はロボットに割当てられていた作業を、前記異なる人又はロボットに割当てられた作業に含めないことを特徴とする付記１０に記載の作業編成方法。
（付記１２）  前記作業の情報には、前記作業の順序についての制約条件が含まれ、
前記算出する処理では、さらに、前記人又は前記ロボットに割当てられた作業の順序が、前記人又は前記ロボットの配置順と矛盾する数から評価値を算出することを特徴とする付記１０又は１１に記載の作業編成方法。
（付記１３）  前記算出する処理では、さらに、前記人又は前記ロボットに割当てられた作業に必要な時間のばらつきに関する値から評価値を算出することを特徴とする付記１０〜１２のいずれかに記載の作業編成方法。
（付記１４）  前記探索する処理では、算出された複数の前記評価値の合計を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索することを特徴とする付記１２又は１３に記載の作業編成方法。
（付記１５）  前記探索する処理では、算出された複数の前記評価値に予め定められている重み係数を乗じた値の合計を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索することを特徴とする付記１２又は１３に記載の作業編成方法。
（付記１６）  前記入力を受け付ける処理では、さらに、前記評価値の許容範囲又は最大探索時間の入力を受け付け、
前記探索部は、前記評価値が前記許容範囲に入るまで、又は探索に要した時間が前記最大探索時間を超えるまで、探索を実行することを特徴とする付記１０〜１５のいずれかに記載の作業編成方法。
（付記１７）  組立ライン上の各工程に配置される人又はロボットの変更内容と、前記各工程への割り当て対象とする作業の情報と、を含む再編成情報と、再編成前に前記人又は前記ロボットに割り当てられていた作業の情報を含む編成情報と、の入力を受け付け、
前記再編成情報に基づいて前記人または前記ロボットに前記作業を割り当てたときに、前記編成情報において前記人又は前記ロボットに割り当てられていた作業が、異なる人又はロボットに割り当てられた数から評価値を算出し、
算出された前記評価値又は該評価値に基づく値を最小とする条件の最適化問題を解いて前記作業を前記人又は前記ロボットへ割り当てる組み合わせの作業編成を探索し、
探索した前記作業編成を出力する、
処理をコンピュータに実行させるための作業編成プログラム。
【符号の説明】
【００７５】
１０  作業編成装置
１１  入力受付部
１２  探索指標設定部（算出部）
１３  探索部
１４  出力部
２１Ａ  ロボット
２１Ｂ〜２１Ｄ  作業員（人）
【図１】
2018077591.tif 000004
【図２】
2018077591.tif 000005
【図３】
2018077591.tif 000006
【図４】
2018077591.tif 000007
【図５】
2018077591.tif 000008
【図６】
2018077591.tif 000009
【図７】
2018077591.tif 000010
【図８】
2018077591.tif 000011
【図９】
2018077591.tif 000012
【図１０】
2018077591.tif 000013