図面 (/)

技術 自動搬送システムの作業割当装置及びその方法

出願人 三星電子株式会社
発明者 朴泰銀
出願日 2007年8月3日 (13年4ヶ月経過) 出願番号 2007-202785
公開日 2008年4月3日 (12年8ヶ月経過) 公開番号 2008-077638
状態 特許登録済
技術分野 総合的工場管理
主要キーワード コスト行列 生産モデル 関数プログラム 作業ライン 作業割当 工程設備 局所最適解 単一経路
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2008年4月3日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (7)

課題

作業割当によって作成されたコストテーブルに基づいて初期最適解を求めたのち、統計量を用いて変換したコストテーブルに基づいて単一の最適解を求める自動搬送システム作業割当装置を提供する。

解決手段

最適解を求めるためのハンガリーアルゴリズムをツール保存部に保存しており、初期コストテーブルコストを他のコストに変換するために統計量を演算する統計量演算部と、演算した統計量に基づいて初期コストテーブルのコストを変換するコストテーブル変換器とを備える。

概要

背景

半導体及びLCD製造工程のように複雑な設備を制御するための設備制御工程は、複数のストッカー(stocker)、OHT(Overhead Hoist Transport system)、OHS(Overhead Shuttle system)、RGV(Rail Guided Vehicle system)、AGV(Automatic Guided Vehicle system)などの物流搬送システム相互接続によって工程設備物流搬送がなされ、これらの個別物流搬送システムはそれぞれの搬送制御システムによって制御される。

制御システムにおいて最も重要とされているのは、複数の作業(job)に複数の搬送車(vehicle)を最適に割り当てることである。

設備製造工程は、生産能力(capacity)の増加に伴って、搬送車の数よりは作業の数が大きいのが一般的である。

複数の作業を複数の搬送車に割り当てる問題は、数学的にNP−hard(non−deterministic polynomial−time hard)であるから全ての場合を羅列することによっては解決不可能である。

複数の作業を複数の搬送車に割り当てる既存の方法には、優先順位(priority)による方法、最も近くにある搬送車への作業割当方法、最も暇な(idle)搬送車への割当方法、探索的(heuristic)割当方法などがある。

既存の方法は、システムに実際に適用し難いとか、全域最適解(global optimum)ではなく一定範囲内の局所最適解(local optimum)を提供する役割に限定されるという問題があった。

概要

作業割当によって作成されたコストテーブルに基づいて初期最適解を求めたのち、統計量を用いて変換したコストテーブルに基づいて単一の最適解を求める自動搬送システム作業割当装置を提供する。 最適解を求めるためのハンガリーアルゴリズムをツール保存部に保存しており、初期コストテーブルコストを他のコストに変換するために統計量を演算する統計量演算部と、演算した統計量に基づいて初期コストテーブルのコストを変換するコストテーブル変換器とを備える。

目的

本発明は上記の問題点を解決するためのもので、その目的は、作業割当のために作成されたコストテーブルから初期最適解を求めた後、統計量を用いて変換したコストテーブルから単一の最適解を求めることができる自動搬送システムの作業割当装置及びその方法を提供することにある。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

複数の搬送車に複数の作業を割り当てる自動搬送システムに用いられる作業割当装置であって、前記搬送車と作業に対応するコストを用いてコストテーブルを作成するコストテーブル作成器と、前記作成されたコストテーブルのコストにハンガリーアルゴリズムを適用して最適解を求める最適解演算部と、を備える、動搬送システムの作業割当装置。

請求項2

前記ハンガリーのアルゴリズムを保存するためのツール保存部をさらに備える、請求項1に記載の自動搬送システムの作業割当装置。

請求項3

前記コストテーブル作成器は、下記の式を満足する場合にコストテーブルを作成する、請求項1に記載の自動搬送システムの作業割当装置。式中、Cijは、作業(j)に割り当てられた搬送車(i)のコストを表し、xijは、作業(j)に割り当てられた搬送車(i)を表し、Nは、搬送車の台数を表し、Mは、作業の個数を表す。

請求項4

前記コストテーブル作成器は、前記コストテーブルのローの個数とカラムの個数を同一にする、請求項3に記載の自動搬送システムの作業割当装置。

請求項5

前記コストテーブル作成器は、ローの個数とカラムの個数が異なると、ローの個数とカラムとの差に対応するダミーコスト値を“0”と設定する、請求項4に記載の自動搬送システムの作業割当装置。

請求項6

複数の搬送車に複数の作業を割り当てる自動搬送システムの作業割当装置であって、前記搬送車と作業に対応するコストを用いる初期コストテーブルを作成するコストテーブル作成器と、前記初期コストテーブルのコストにハンガリーのアルゴリズムを適用して初期最適解を求める第1最適解演算部と、前記初期最適解と前記初期コストテーブルのコストに関連した統計量を演算する統計量演算部と、前記演算1統計量を用いて前記初期コストテーブルを変換するコストテーブル変換器と、前記変換されたコストテーブルのコストにハンガリーのアルゴリズムを適用して単一の最適解を得る第2最適解演算部と、を備える、自動搬送システムの作業割当装置。

請求項7

前記統計量演算部は、初期最適解が複数個ある場合に統計量を演算する、請求項6に記載の自動搬送システムの作業割当装置。

請求項8

前記統計量演算部は、複数個の初期最適解のうちのいずれか一つを設定するために初期最適解と初期作成されたコストテーブルのコストから正規化したコストを演算する、請求項7に記載の自動搬送システムの作業割当装置。

請求項9

前記統計量演算部は、正規化したコスト(δij)と、初期作成されたコストテーブルの各コストに正規化したコスト(δij)を加算した新しいコスト(NCij)とを、下記の式によって求める、請求項8に記載の自動搬送システムの作業割当装置。式中、μは初期最適解を平均した平均コストを表し、Rは、全体コスト(Cij)の範囲を表す。

請求項10

複数の搬送車に複数の作業を割り当てる自動搬送システムの作業割当方法であって、前記搬送車と作業に対応するコストを用いて初期コストテーブルを作成する段階と、前記初期コストテーブルにハンガリーのアルゴリズムを適用して初期最適解を求める段階と、前記初期最適解と前記初期コストテーブルのコストに関連した統計量を演算する段階と、前記演算した統計量を用いて前記初期コストテーブルのコストを変換する段階と、前記変換されたコストテーブルのコストにハンガリーのアルゴリズムを適用して単一の最適解を求める段階と、を含む、自動搬送システムの作業割当方法。

請求項11

前記初期最適解が複数個の場合に前記統計量を演算する段階をさらに含む、請求項10に記載の自動搬送システムの作業割当方法。

請求項12

前記統計量は、初期最適解と前記初期コストテーブルのコストから得た正規化したコストとを含む、請求項11に記載の自動搬送システムの作業割当方法。

請求項13

前記統計量は、正規化したコスト(δij)、及び前記初期コストテーブルの各コストと正規化したコスト(δij)との和で表示される新しいコスト(NCij)を含む、請求項11に記載の自動搬送システムの作業割当方法。

請求項14

前記初期コストテーブルの作成は、コストテーブルのローの個数とカラムの個数が同一となるようにして行う、請求項10に記載の自動搬送システムの作業割当方法。

請求項15

前記初期コストテーブルのローの個数とカラムの個数が異なると、ローの個数とカラムとの差に対応するダミーコスト値を“0”と設定する段階をさらに含む、請求項14に記載の自動搬送システムの作業割当方法。

技術分野

0001

本発明は、行列最適解を求めるハンガリー法(hungarian method)を用いて複数の搬送車に複数の作業を最適に割り当てる自動搬送システム作業割当装置及びその方法に関する。

背景技術

0002

半導体及びLCD製造工程のように複雑な設備を制御するための設備制御工程は、複数のストッカー(stocker)、OHT(Overhead Hoist Transport system)、OHS(Overhead Shuttle system)、RGV(Rail Guided Vehicle system)、AGV(Automatic Guided Vehicle system)などの物流搬送システム相互接続によって工程設備物流搬送がなされ、これらの個別物流搬送システムはそれぞれの搬送制御システムによって制御される。

0003

制御システムにおいて最も重要とされているのは、複数の作業(job)に複数の搬送車(vehicle)を最適に割り当てることである。

0004

設備製造工程は、生産能力(capacity)の増加に伴って、搬送車の数よりは作業の数が大きいのが一般的である。

0005

複数の作業を複数の搬送車に割り当てる問題は、数学的にNP−hard(non−deterministic polynomial−time hard)であるから全ての場合を羅列することによっては解決不可能である。

0006

複数の作業を複数の搬送車に割り当てる既存の方法には、優先順位(priority)による方法、最も近くにある搬送車への作業割当方法、最も暇な(idle)搬送車への割当方法、探索的(heuristic)割当方法などがある。

0007

既存の方法は、システムに実際に適用し難いとか、全域的最適解(global optimum)ではなく一定範囲内の局所最適解(local optimum)を提供する役割に限定されるという問題があった。

発明が解決しようとする課題

0008

本発明は上記の問題点を解決するためのもので、その目的は、作業割当のために作成されたコストテーブルから初期最適解を求めた後、統計量を用いて変換したコストテーブルから単一の最適解を求めることができる自動搬送システムの作業割当装置及びその方法を提供することにある。

課題を解決するための手段

0009

上記目的を達成するための本発明は、複数の搬送車に複数の作業を割り当てる自動搬送システムに用いられる作業割当装置であって、前記搬送車と作業に対応するコストを用いてコストテーブルを作成するコストテーブル作成器と、前記作成されたコストテーブルのコストにハンガリーのアルゴリズムを適用して最適解を得る最適解演算部と、を備える構成とした。

0010

前記装置は、前記ハンガリーのアルゴリズムを保存するためのツール保存部をさらに備えることができる。

0011

前記コストテーブル作成器は、下記の式を満足する場合にコストテーブルを作成することができる。

0012

式中、Cijは、作業(j)に割り当てられた搬送車(i)のコストを表し、xijは、作業(j)に割り当てられた搬送車(i)を表し、Nは、搬送車の台数を表し、Mは、作業の個数を表す。

0013

前記コストテーブル作成器は、前記コストテーブルのロー(row)の個数とカラム(column)の個数を同一にすることができる。

0014

前記コストテーブル作成器は、ローの個数とカラムの個数が異なると、ローの個数とカラムとの差に対応するダミーコスト値を“0”と設定することができる。

0015

上記目的を達成するための本発明は、複数の搬送車に複数の作業を割り当てる自動搬送システムの作業割当装置であって、前記搬送車と作業に対応するコストを用いる初期コストテーブルを作成するコストテーブル作成器と、前記初期コストテーブルのコストにハンガリーのアルゴリズムを適用して初期最適解を求める第1最適解演算部と、前記初期最適解と前記初期コストテーブルのコストに関連した統計量を演算する統計量演算部と、前記演算1統計量を用いて前記初期コストテーブルを変換するコストテーブル変換器と、前記変換されたコストテーブルのコストにハンガリーのアルゴリズムを適用して単一の最適解を得る第2最適解演算部と、を備える構成とした。

0016

前記統計量演算部は、初期最適解が複数個ある場合に統計量を演算することができる。

0017

前記統計量演算部は、複数個の初期最適解のうちのいずれか一つを設定するために初期最適解と初期作成されたコストテーブルのコストから正規化したコストを演算することができる。

0018

前記統計量演算部は、正規化したコスト(δij)と、初期作成されたコストテーブルの各コストに正規化したコスト(δij)を加算した新しいコスト(NCij)とを、下記の式によって求めることができる。

0019

式中、μは初期最適解を平均した平均コストを表し、Rは、全体コスト(Cij)の範囲を表す。

0020

上記の目的を達成するための本発明は、複数の搬送車に複数の作業を割り当てる自動搬送システムの作業割当方法であって、前記搬送車と作業に対応するコストを利用して初期コストテーブルを作成する段階と、前記初期コストテーブルにハンガリーのアルゴリズムを適用して初期最適解を求める段階と、前記初期最適解と前記初期コストテーブルのコストに関連した統計量を演算する段階と、前記演算した統計量を用いて前記初期コストテーブルのコストを変換する段階と、前記変換されたコストテーブルのコストにハンガリーのアルゴリズムを適用して単一の最適解を求める段階と、を含む構成とした。

0021

前記方法は、前記初期最適解が複数個の場合に前記統計量を演算する段階をさらに含むことができる。

0022

前記統計量は、初期最適解と前記初期コストテーブルのコストから得た正規化したコストとを含むことができる。

0023

前記統計量は、正規化したコスト(δij)、及び前記初期コストテーブルの各コストと正規化したコスト(δij)との和で表示される新しいコスト(NCij)を含むことができる。

0024

前記初期コストテーブルの作成は、コストテーブルのローの個数とカラムの個数が同一となるようにして行うことができる。

0025

前記方法は、前記初期コストテーブルのローの個数とカラムの個数が異なると、ローの個数とカラムとの差に対応するダミーコスト値を“0”と設定する段階をさらに含むことができる。

0026

上記の目的を達成するための本発明は、自動搬送システムにおいて複数の搬送車に複数の作業を割り当てる作業割当方法を行うコンピュータプログラムを有するコンピュータ可読記録媒体であって、前記方法が、前記搬送車と作業に対応するコストを用いて初期コストテーブルを作成する段階と、前記初期コストテーブルにハンガリーのアルゴリズムを適用して初期最適解を求める段階と、前記初期最適解と前記初期コストテーブルのコストに関連した統計量を演算する段階と、前記演算した統計量を用いて前記初期コストテーブルのコストを変換する段階と、前記変換されたコストテーブルのコストにハンガリーのアルゴリズムを適用して単一の最適解を求める段階と、を含む構成とした。

発明の効果

0027

本発明は、AGVシステムにおいて複数の搬送車に複数の作業を割り当てる際にハンガリーのアルゴリズムを用いて最適解を求めることができる。

0028

本発明によれば、初期最適解が複数個存在する場合、統計量によって変換されたコストテーブルにハンガリーのアルゴリズムを適用して単一の最適解を求めることができ、したがって、搬送車間干渉を減らし、且つ、物流搬送システムの搬送効率を向上させることが可能になる。特に、作業割当が最適化されないとき、作業スワッピング(Job Swapping)の問題に效果的に立ち向かうことができる。

発明を実施するための最良の形態

0029

以下、本発明の好適な実施の形態を、添付の図面を参照しつつ詳細に説明する。図面中、同一の構成要素については可能な限り同一の参照符号を共通使用するものとする。

0030

本発明は、複数の搬送車に最適に複数の作業を割り当てるためのもので、最適解を求めるためにコストテーブルを作成し且つハンガリー法を用いる。コストテーブルは、作業を行うコストを数値化して表したものである。したがって、コストの代表例には、搬送車が割り当てられた作業を行うのにかかる作業時間がある。なお、作業ラインから生産モデル作業者を割り当てる場合には、コストが作業時間または労働時間を表す。工場内の設備を4箇所に設置しようとする場合にコストは設置コストとなり、搬送ラインから工程別に作業者を割り当てようとする場合にコストは作業時間となる。

0031

任意の搬送車に任意の作業を割り当てる場合に基づいて作成されたコストテーブルにおいて全体コストを最小化する最適解を求める場合、ハンガリー法を適用するためには下記の式(1)を満足しなければならない。

0032

式中、Cijは、作業(j)に割り当てられた搬送車(i)のコストを表し、xijは、作業(j)に割り当てられた搬送車(i)を表し、Nは、搬送車の台数を表し、Mは、作業の個数を表す。

0033

本発明による自動搬送システムの作業割当装置は上記の式(1)を満足する場合、図1に示すようにコストテーブルを作成するためにコストテーブル作成器101を備えることができる。したがって、作成されたコストテーブルは、ローの個数とカラムの個数を同一にすることができる。もし、ローとカラムの数が同一でなければ、当該作業割当装置はダミーコスト値を“0”と設定する。

0034

ツール保存部106は、最適解を求めるためのツール(tool)を保存し、このツールはハンガリー法を用いて最適解を演算する過程を含む。

0035

コストテーブル作成器101から作成されたコストテーブルを受け取った場合、第1最適解演算部102は、ツール保存部106に保存されているツールを受信し、このツールを用いて初期最適解を求める。

0036

したがって、上記のハンガリー法を用いて初期最適解を求める方法を、下記の実施例1
で説明すると、次の通りである。

0037

AGV(Automatic Guided Vehicle)システムにおいて5台の搬送車(V1,V2,V3,V4,V5)に5個の作業(J1,J2,J3,J4,J5)を割り当てるための個別のコスト行列に基づいてそれぞれ[テーブル1]が作成される。したがって、[テーブル1]は、複数のコスト値で形成された5×5行列を表す。

0038

上記の[テーブル1]において、複数の各ロー(第1乃至第5のロー)にそれぞれ該当する個別の最小コスト値(1,3,6,10,2)を、各ローから減算し、下記の[行列1]を得る。したがって、最小コスト値1を[テーブル1]の第1ローの各値から減算し、最小コスト値3を[テーブル1]の第2ローの各値から減算し、最小コスト値6を[テーブル1]の第3ローの各値から減算し、最小コスト値10を[テーブル1]の第4ローの各値から減算し、最小コスト値2を[テーブル1]の第5ローの各値から減算することによって、下記の[行列1]を得る。

0039

上記の[行列1]において、複数の各カラム(第1乃至第5のカラム)にそれぞれ該当する個別の最小コスト値(0,0,2,0,5)を各カラムから減算して、下記の[行列2]を得る。したがって、最小コスト値0を[行列1]の第1カラムの各値から減算し、最小コスト値0を[行列1]の第2カラムの各値から減算し、最小コスト値2を[行列1]の第3カラムの各値から減算し、最小コスト値0を[行列1]の第4カラムの各値から減算し、最小コスト値5を[行列1]の第5カラムの各値から減算することによって、下記の[行列2]を得る。

0040

上記の[行列2]において、“0”値を持つロー及びカラムに水平線及び垂直線を引き、下記の[行列3]を得る。ここで、水平線及び垂直線は、可能な限り少ない線を用いて“0”値を全部カバーできるような方式で引く。

0041

上記の[行列3]において、最小コスト値(例えば、[行列3]のコスト値“3”)を、線の引かれていないコスト値から減算して、下記の[行列4]を得る。

0042

“0”値の位置は可能な最適割当組合を表示し、各ローはただ一つの“0”値を要求する。なお、2以上の最適割当組合を見出すことができるが、合計最小値はいずれの組合においても同一でなければならない。上記の[行列4]において、最適割当組合は、[テーブル1]の(V1,J2)、(V2,J5)、(V3,J3)、(V4,J1)及び(V5,J4)の位置にそれぞれ該当するコスト値を含む。[テーブル1]の最小コスト合計は、[テーブル1]の(V1,J2)、(V2,J5)、(V3,J3)、(V4,J1)及び(V5,J4)の位置にそれぞれ該当するコスト値の合計と同一である。したがって、該コスト値の合計は、“1”+“11”+“8”+“10”+“2”=“32”となる。

0043

上記の実施例1からわかるように、ハンガリー法を用いることによって最適割当組合から最適解を保障することができる。

0044

しかしながら、最適割当組合が複数個あると、いずれの最適割当組合が最適解を生成する最高のものかが保障不可能になる。

0045

最高の最適割当組合を保障するために、本発明による自動搬送システムの作業割当装置は、図1に示すように、統計量を演算する統計量演算部103、統計量演算部103で演算された統計量に基づいて初期作成されたコストテーブルのコストを変換するコストテーブル変換器104、及び、変換器104から変換されたコストテーブルを受信し、ツール保存部106に保存されたハンガリーのアルゴリズム(Hungarian algorithm)を用いて単一の最適解を求める第2最適解演算部105と、を備える。この詳細については、下記の実施例2で説明する。

0046

搬送車が物を搬送するための物流システムにおいてハンガリーのアルゴリズムを適用したときに、複数の最適割当組合が検出された場合には、どの最適割当組合が物流システムに最高のものかを判別する必要がある。

0047

例えば、図2に示すように、AGVシステムの単一経路(path)において2台の搬送車(V1,V2)と2個の作業(J1,J2)が存在するときに、移動距離(distance)をコストとする。

0048

このような状況が上記の式(1)を満足する場合、コストテーブル作成器101によって[テーブル2]が作成される。

0049

上記の[テーブル2]においてハンガリーのアルゴリズムに基づいて得られた最適割当組合は、(V1,J2)、(V2,J1)及び(V1,J1)、(V2,J2)となる。このようにハンガリーのアルゴリズムで得られた2対の該当する初期最適解のうち、どれが最高のものかがわからない。例えば、一番目の組合(V1,J2)、(V2,J1)を最適解に設定する場合、第1搬送車V1が第2作業J2を行う間に、第2搬送車V2は待機しなければならない。すなわち、第1搬送車V1が第2作業J2を終えて始めて作業経路(path)が確保されるため、第1搬送車V1の第2作業J2後に、第2搬送車V2は第1作業J1が行え、結果として作業の移送時間(delivery time)が遅延されてしまう。

0050

上記の[テーブル2]のように最適解が複数存在する場合には、統計量を用いて最適解を求める必要がある。したがって、複数の初期最適解のうち、最小の標準偏差を持つ特定の最適解が最高の最適解として判別されることができる。

0051

統計量演算部103は、初期最適解を平均した平均コスト(μ)と全体コスト(Cij)の範囲(R)を、下記の式(2)で求める。

0052

式中、TCは、ハンガリーのアルゴリズムから得た初期最適解の総コストを表し、nはカラムの個数(M)とローの個数(N)のうち、小さい値を表し、Cmaxは全体コストのうちの最大値を表し、Cminは全体コストのうちの最小値を表す。

0053

また、統計量演算部103は、正規化したコスト(δij)と、初期作成されたコストテーブルの各コストに正規化したコスト(δij)を加算した新しいコスト(NCij)を、下記の式(3)で求める。

0054

コストテーブル変換器104は、統計量演算部103で求めた新しいコスト(NCij)に基づいてコストテーブルを変換する。

0055

第2最適解演算部105は、変換されたコストテーブルに対してハンガリーのアルゴリズムを用いて単一の最適解を求めることができる。図3を参照すると、平均コスト(μ)に近付くほど正規化したコスト(δij)が小さくなり、平均コスト(μ)と値(Cij)間の距離が長くなるほど正規化したコスト(δij)が大きくなるので、変換されたコストテーブルから単一の最適解を得ることができる。

0056

初期最適解が複数個ある場合、標準偏差の最小値が解となることができる。これについて詳細に説明すると、次の通りになる。

0057

変換されたコストテーブルは、下記の式(4)で表すように、A+D=B+Cのときに平均コスト(μ)と範囲(R)で作成されることができる。

0058

一つの対角線の和は、下記の式(5)で表すように、他の対角線の和と比較されることができる。

0059

下記の式(6)で表すように、A+D=B+Cのとき、|A−D|<|B−C|であればA2+D2<B2+C2である。

0060

したがって、上記式(6)のAとDの値が最適解となる。

0061

上記の式(4),(5)及び(6)に示す方法を[テーブル2]に適用して単一の最適解を求める方法について説明すると、下記の通りである。

0062

第1最適解演算部102は、[テーブル2]に対してハンガリーのアルゴリズムを用いて(V1,J2)及び(V2,J1)に該当する初期最適解を求めることができる。

0063

統計量演算部103は、下記の式(7)によって、平均コスト(μ)と全体コスト(Cij)の範囲(R)を求めることができる。

0064

コストテーブル変換器104は、平均コスト(μ)、全体コスト(Cij)の範囲(R)、及び正規化したコスト(δij)と初期作成されたコストテーブルの各コストとの和で表示される新しいコスト新しいコスト(NCij)に基づき、初期作成されたコストテーブルを他のコストテーブルに変換し、下記の[テーブル3]を生成する。

0065

第2最適解演算部105は、[テーブル3]のコストにハンガリーのアルゴリズムを適用して最適解を求めることができ、その結果、(V2,J1)及び(V1,J2)で表示される最適割当組合が得られる。

0066

以下、実施例3を参照して、上記の実施例2によりも詳細な場合について説明する。

0067

図4に示すように、AGVシステムの単一経路(path)において3台の搬送車V1,V2,V3と3個の作業J1,J2,J3が存在するとき、移動距離(distance)がコストとして設定される。

0068

コストへの作業割当において上記の式(1)を満足する場合、コストテーブル作成器101は[テーブル4]を作成する。

0069

第1最適解演算部102は、ツール保存部106から提供されたハンガリーのアルゴリズムを用いて初期最適解を求めることができ、その結果、(V1,J3)、(V2,J1)及び(V3,J2)に該当する初期最適解が得られる。

0070

統計量演算部103は、下記の式(8)によって平均コスト(μ)と全体コスト(Cij)の範囲(R)を求める。

0071

コストテーブル変換器104は、平均コスト(μ)、全体コスト(Cij)の範囲(R)、及び正規化したコスト(δij)と初期作成されたコストテーブルの各コストとの和で表示される新しいコスト(NCij)に基づき、初期作成されたコストテーブルを他のコストテーブルに変換し、下記の[テーブル5]を生成する。

0072

第2最適解演算部105は、変換された[テーブル5]のコストにハンガリーのアルゴリズムを適用して最適解を求めることができ、その結果、(V1,J1)、(V2,J2)及び(V3,J3)に該当する最適割当組合が得られる。

0073

以下、複数の搬送車に複数の作業を割り当てる方法を、図5を参照して説明する。

0074

まず、作業コストを上記式(1)で表すことができれば、コストテーブルが作成される(ステップ201)。したがって、該コストテーブルは、搬送車の台数(M)と作業の個数(N)とを比較する(ステップ202)。搬送車の台数(M)が作業の個数(N)よりも大きいと、(M−N)の数に該当するダミーコスト値を“0”と設定する(ステップ203)。搬送車の台数(M)が作業の個数(N)よりも小さいと、(N−M)の数に該当するダミーコスト値を“0”と設定する(ステップ204)。

0075

搬送車の台数(M)が作業の個数(N)と同一である、ま たは、ダミーコストが設定された場合、第1最適解演算部102は、ツール保存部106に保存されたハンガリーのアルゴリズムを用いて初期最適解を求める(ステップ205)。

0076

統計量演算部103は、初期最適解と初期作成されたコストテーブルのコストに基づいて統計量を求める。この統計量は、最適解が複数個である規定に基づく標準偏差のより小さい解を求めるためのもので、平均コスト(μ)、全体コスト(Cij)の範囲(R)、及び正規化したコスト(δij)と初期作成されたコストテーブルの各コストとの和で表示される新しいコスト(NCij)を含む(ステップ206)。

0077

コストテーブル変換器104は、上記の統計量を用いて、初期作成されたコストテーブルを他のコストテーブルに変換する(ステタップ207)。その詳細は、上記実施例2及び3で既に説明した通りである。

0078

第2最適解演算部105は、変換されたコストテーブルにハンガリーのアルゴリズムを適用して単一の最適解を求める(ステップ208)。

0079

したがって、本発明の実施の形態による初期最適解を求めてから統計量を用いて単一の最適解を求める方法は、APSolverプログラムを用いて十分な回数(百万回以上)シミュレーションをして検証した結果、最適解を求める既存の方法に比べて格段に速く行われたことがわかり、そのシミュレーション画面の例を、図6に示す。

0080

本発明はまた、コンピュータ可読記録媒体上のコンピュータ可読コードとしても具現可能である。コンピュータ可読記録媒体は、データの記録が可能で、かつ、以降コンピュータシステムによって記録されたデータを読み出し可能な全てのデータ保存装置を含む。コンピュータ可読記録媒体の例には、ROM(read only memory)、RAM(random access memory)、CD−ROMs、磁気テープフロッピディスク、光データ保存装置及び搬送波(carrier
waves)(例えば、インターネットを通じたデータ転送)がある。また、コンピュータ可読記録媒体は、コンピュータ可読コードが分散された形態に保存及び実行されることができるように、ネットワークで結合されたコンピュータシステムに分散されても良い。また、本発明によって成し遂げられる関数プログラム、コード、コードセグメントは、本発明の属する分野に熟練したプログラマによって容易に解析されることができる。

図面の簡単な説明

0081

本発明の一実施の形態による自動搬送システムの作業割当装置を示すブロック図である。
本発明の一実施の形態による自動搬送システムの作業割当を例示する図で、AGVシステムの単一経路において2台の搬送車と2個の作業が存在する場合のレイアウトである。
本発明の一実施の形態で適用する統計量として正規化したコスト(δij)が、平均コスト(μ)に近付くにつれて小さくなり、平均コスト(μ)から遠ざかるにつれて大きくなる様子を示すグラフである。
本発明の一実施の形態による自動搬送システムの作業割当を例示する図で、AGVシステムの単一経路において3台の搬送車と3個の作業が存在する場合のレイアウトである。
本発明の一実施の形態による自動搬送システムの作業割当方法を説明するフローチャートである。
本発明の一実施の形態によって単一の最適解を求めるためにAPSolverプログラムを用いてシミュレーションする方法を説明するための画面を例示する図である。

符号の説明

0082

101コストテーブル作成器
103統計量演算部
104コストテーブル変換器

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 日本電産株式会社の「 設備管理システム、設備管理方法」が 公開されました。( 2020/10/29)

    【課題】共通の生産工程に使用する複数の設備の稼動状況を監視するときに、設備の違いによる煩雑さを生じさせないようにする。【解決手段】本発明の一実施形態は、第1設備と、第2設備と、第1設備および第2設備の... 詳細

  • ファナック株式会社の「 更新システム」が 公開されました。( 2020/10/29)

    【課題】より容易にソフトウェアの更新可能な更新システムを提供する。【解決手段】数値制御装置に設定されているソフトウェアを新たなソフトウェアに更新する更新システムであって、数値制御装置が保持する固有の情... 詳細

  • ダイキン工業株式会社の「 目標未達情報提示システム及び目標未達情報提示プログラム」が 公開されました。( 2020/10/29)

    【課題】原因の分析の精度を向上する。【解決手段】目標未達情報提示システム(1)は、目標設定部(21)と、データ取得部(22)と、情報提示部(23)とを備える。目標設定部(21)は、所定のテーマに対して... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ