[go: up one dir, main page]

KR101287528B1 - 자동반송시스템의 작업 할당 장치 및 그 방법 - Google Patents

자동반송시스템의 작업 할당 장치 및 그 방법 Download PDF

Info

Publication number
KR101287528B1
KR101287528B1 KR1020060090873A KR20060090873A KR101287528B1 KR 101287528 B1 KR101287528 B1 KR 101287528B1 KR 1020060090873 A KR1020060090873 A KR 1020060090873A KR 20060090873 A KR20060090873 A KR 20060090873A KR 101287528 B1 KR101287528 B1 KR 101287528B1
Authority
KR
South Korea
Prior art keywords
cost
optimal solution
cost table
initial
statistics
Prior art date
Application number
KR1020060090873A
Other languages
English (en)
Other versions
KR20080025994A (ko
Inventor
박태은
Original Assignee
삼성전자주식회사
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 삼성전자주식회사 filed Critical 삼성전자주식회사
Priority to KR1020060090873A priority Critical patent/KR101287528B1/ko
Priority to US11/771,206 priority patent/US8731697B2/en
Priority to JP2007202785A priority patent/JP4675360B2/ja
Publication of KR20080025994A publication Critical patent/KR20080025994A/ko
Application granted granted Critical
Publication of KR101287528B1 publication Critical patent/KR101287528B1/ko

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05B—CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS
    • G05B19/00—Programme-control systems
    • G05B19/02—Programme-control systems electric
    • G05B19/418—Total factory control, i.e. centrally controlling a plurality of machines, e.g. direct or distributed numerical control [DNC], flexible manufacturing systems [FMS], integrated manufacturing systems [IMS] or computer integrated manufacturing [CIM]
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q30/00—Commerce
    • G06Q30/02—Marketing; Price estimation or determination; Fundraising
    • G06Q30/0201—Market modelling; Market analysis; Collecting market data
    • G06Q30/0206—Price or cost determination based on market factors

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Strategic Management (AREA)
  • Development Economics (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Economics (AREA)
  • Finance (AREA)
  • Accounting & Taxation (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Marketing (AREA)
  • Game Theory and Decision Science (AREA)
  • Quality & Reliability (AREA)
  • Data Mining & Analysis (AREA)
  • Educational Administration (AREA)
  • Operations Research (AREA)
  • Tourism & Hospitality (AREA)
  • Manufacturing & Machinery (AREA)
  • General Engineering & Computer Science (AREA)
  • Automation & Control Theory (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • General Factory Administration (AREA)

Abstract

본 발명은 작업 할당을 위하여 작성된 코스트 테이블로부터 초기 최적해를 구한 후 통계량을 이용하여 변환한 코스트 테이블로부터 단일한 최적해를 구할 수 있는 자동반송 시스템의 작업할당 장치 및 그 방법을 제공한다. 이를 위해 본 발명은 최적해를 구하기 위해 이용하는 헝가리언 알고리즘을 툴 저장부에 저장하고 있으며, 초기 작성한 테이블의 코스트로를 변환하기 위해 통계량을 연산하는 통계량 연산부, 및 연산한 통계량에 기초하여 초기 작성된 코스트 테이블의 코스트 변환하는 코스트 테이블 변환기를 포함한다.

Description

자동반송시스템의 작업 할당 장치 및 그 방법{Job Assignment Apparatus Of Automatic Material Handling System And Method Thereof}
도 1은 본 발명에 따른 자동반송시스템의 작업 할당 장치의 블록구성도이다.
도 2는 본 발명예 따른 자동반송시스템의 작업 할당을 설명하기 위한 예로서 AGV 시스템에서 단일 경로에서 2대의 반송차와 2개의 작업이 존재하는 경우의 레이아웃을 나타낸 도면이다.
도 3은 본 발명에서 적용하는 통계량으로서 정규화된 코스트(δij)가 평균 코스트(μ)에 가까울수록 작고 평균 코스트(μ)에 멀어질수록 커지는 것을 나타내는 그래프이다.
도 4는 본 발명에 따른 자동반송시스템의 작업 할당을 설명하기 위한 예로서 AGV 시스템에서 단일 경로에서 3대의 반송차와 3개의 작업이 존재하는 경우의 레이아웃을 나타낸 도면이다.
도 5는 본 발명에 따른 자동반송시스템의 작업 할당 방법을 설명하기 위한 순서도이다.
도 6은 본 발명에 따라 단일의 최적해를 구하기 위하여 APSolver 프로그램을 이용하여 시뮬레이션하는 경우의 예를 보인 화면이다.
*도면의 주요 부분에 대한 부호 설명
101 : 코스트 테이블 작성기
103 : 통계량 연산부
104 : 코스트 테이블 변환기
본 발명은 다수의 반송차에 다수의 작업을 할당하는데 있어 헝가리언 법(hungarian method)을 이용하여 최적의 할당을 하기 위한 자동반송 시스템의 작업할당 장치 및 그 방법에 관한 것이다.
반도체 및 LCD 제조공정과 같이 복잡한 설비를 제어하기 위한 설비 제어 공정은 다수의 스토커(stocker), OHT(Overhead Hoist Transport system), OHS(Overhead Shuttle system), RGV(Rail Guided Vehicle system), AGV(Automatic Guided Vehicle system) 등의 물류 반송 시스템들의 연결에 의해 공정 설비간 물류 반송이 이루어지며, 이들 개별 물류 반송 시스템은 각각의 반송 제어 시스템들에 의해 제어된다.
제어시스템의 가장 중요한 것은 복수의 작업(job)에 복수의 반송차(vehicle)을 최적으로 할당하는 것이다.
설비 제조 공정은 생산 능력(capacity)이 증가하는 추세에 맞추어 볼 때 반송차(vehicle)의 개수보다는 작업(job)의 개수가 항상 많은 것이 일반적이다.
다수의 작업을 다수의 반송차에 할당하는 문제는 수학적으로 NP-hard(non-deterministic polynomial-time hard) 이므로 모든 경우를 나열하여 해결할 수 없다.
다수의 작업을 다수의 반송차에 할당하는 기존의 방법은 우선순위(priority)에 의한 방법, 반송차(vehicle)에 가장 가까운 작업 할당 방법, 가장 한가한(idle) 반송차 할당 방법, 탐색적(heuristic) 할당 방법 등이 있다.
기존의 방법에 따르면 시스템에 실제 적용하기 어려운 것과 전체 최적해(global optimum)가 아닌 일정 범위내의 지역 최적해(local optimum)를 제공하는 역할에 국한되었다.
본 발명의 목적은 작업 할당을 위하여 작성된 코스트 테이블로부터 초기 최적해를 구한 후 통계량을 이용하여 변환한 코스트 테이블로부터 단일한 최적해를 구할 수 있는 자동반송 시스템의 작업할당 장치 및 그 방법을 제공하는데 있다.
상기 목적을 달성하기 위한 본 발명은, 다수의 반송차에 다수의 작업을 할당하기 위한 자동 반송시스템의 작업 할당 장치에 있어서, 상기 반송차와 작업에 대응되는 코스트를 이용하여 테이블을 작성하는 코스트 테이블 작성기; 및 상기 작성된 코스트 테이블의 코스트에 대하여 헝가리언 알고리즘을 이용하여 최적해를 얻기 위한 최적해 연산부를 포함한다.
상기 헝가리언 알고리즘을 저장하기 위한 툴 저장부를 더 포함한다.
상기 코스트 테이블 작성기는 다음 식-A)을 만족하는 경우에 코스트 테이블을 작성한다.
Figure 112006067707120-pat00001
식-A)
여기서 Cij는 작업(j)에 대하여 할당된 반송차(i)의 코스트이고, xij는 작업(j)에 대하여 할당된 반송차(i)이고, N은 반송차의 대수이며, M은 작업들의 개수이다.
상기 코스트 테이블 작성기는 작성된 코스트 테이블의 로(row)의 개수와 컬럼(column)의 개수가 같도록 작성한다.
상기 코스트 테이블 작성기는 로(row)의 개수와 컬럼(column)의 개수가 같지 않으면 부족한 개수만큼 더미 코스트 값으로 "0"을 설정한다.
상기 목적을 달성하기 위한 본 발명은 다수의 반송차에 다수의 작업을 할당하기 위한 자동 반송시스템의 작업 할당 장치에 있어서, 상기 반송차와 작업에 대응되는 코스트를 이용하여 테이블을 초기 작성하는 코스트 테이블 작성기; 상기 작성된 코스트 테이블의 코스트에 대하여 헝가리언 알고리즘을 이용하여 초기 최적해를 얻기 위한 제1최적해 연산부; 상기 초기 최적해와 초기 작성된 코스트 테이블의 코스트에 관계된 통계량을 연산하는 통계량 연산부; 상기 연산한 통계량을 이용하여 초기 작성된 코스트 테이블을 변환하는 코스트 테이블 변환기; 및 상기 변환된 코스트 테이블의 코스트에 대하여 헝가리언 알고리즘을 이용하여 단일의 최적해를 얻기 위한 제2최적해 연산부를 포함한다.
상기 통계량 연산부는 초기 최적해가 다수 개인 경우에 통계량을 연산한다.
상기 통계량 연산부는 다수 개의 초기 최적해 중 어느 하나를 설정하기 위하여 초기 최적해와 초기 작성된 코스트 테이블의 코스트로부터 정규화된 코스트를 연산한다.
상기 통계량 연산부는 정규화된 코스트(δij)와 초기 작성된 코스트 테이블의 각 코스트에 정규화된 코스트(δij)를 더한 새로운 코스트(NCij)를 다음 식-B)에 따라 구한다.
Figure 112006067707120-pat00002
.. 식-B)
여기서, μ는 초기 최적해를 평균한 평균 코스트이고, R은 전체 코스트(Cij)의 범위이다.
상기 목적을 달성하기 위한 본 발명은, 다수의 반송차에 다수의 작업을 할당하기 위한 자동 반송시스템의 작업 할당 방법에 있어서, 상기 반송차와 작업에 대응되는 코스트를 이용하여 초기 코스트 테이블을 작성하는 단계; 초기 작성된 코스트 테이블에 대하여 헝가리언 알고리즘을 이용하여 초기 최적해를 얻는 단계; 상기 초기 최적해와 초기 작성된 코스트 테이블의 코스트에 관계된 통계량을 연산하는 단계; 상기 연산한 통계량을 이용하여 초기 작성한 코스트 테이블의 코스트를 변환하는 단계; 및 상기 변환된 코스트 테이블의 코스트에 대하여 헝가리언 알고리즘을 이용하여 단일의 최적해 얻는 단계를 포함한다.
상기 초기 최적해가 다수 개인 경우, 상기 통계량을 연산한다.
상기 통계량은 초기 최적해와 초기 작성된 코스트 테이블의 코스트로부터 정규화된 코스트를 포함한다.
상기 통계량은 정규화된 코스트 이외에 초기 작성된 코스트 테이블의 각 코스트에 정규화된 코스트를 더한 새로운 코스트를 포함한다.
상기 초기 코스트 테이블 작성하는 경우 코스트 테이블의 로의 개수와 컬럼의 개수가 같도록 작성한다.
상기 초기 코스트 테이블의 로의 개수와 컬럼의 개수가 같지 않으면 부족한 개수만큼 더미 코스트 값으로 "0"을 설정한다.
이하, 본 발명에 따른 실시 예를 첨부도면을 참조하여 설명한다.
본 발명은 다수의 반송차에 다수의 작업을 할당하기 위한 최적해를 구하는데 있어 코스트 테이블을 작성하고 헝가리언 법을 이용한다. 코스트 테이블은 작업을 수행하기 위한 비용을 수치화하여 나타낸 것이다. 여기서, 비용은 반송차가 할당된 작업을 수행하기 위하여 요구되는 작업 시간이 대표적인 예이다. 다른 예로서 작업 라인에서 생산 모델과 작업자를 할당하는 경우에 코스트는 작업 시간이 된다. 공장 내 설비들을 4곳의 후보지에 설치하려고 하는 경우 코스트는 설치 비용이며, 컨베 이 라인에서 공정별 작업자를 할당하고자 하는 경우 코스트는 작업시간이다.
임의의 반송차에 임의의 작업을 할당하는 경우를 토대로 작성된 코스트 테이블에서 전체 비용을 최소로 할 수 있는 즉, 최적해를 구하는 경우에 있어서, 헝가리언 법을 적용하기 위해서 일반적으로 식1)을 만족하도록 하고있다.
여기서 Cij는 작업(j)에 대하여 할당된 반송차(i)의 코스트이고, xij는 작업(j)에 대하여 할당된 반송차(i)이고, N은 반송차의 대수이며, M은 작업들의 개수이다.
Figure 112006067707120-pat00003
식-1)
본 발명에 따른 자동반송 시스템의 작업할당 장치는, 도 1에 도시한 바와 같이, 위 식-1)을 만족하는 경우 코스트 테이블을 작성하기 위한 코스트 테이블 작성기(101)를 구비한다. 이때 작성된 코스트 테이블은 로(row)의 개수와 컬럼(column)의 개수가 같도록 한다. 만약 같지 않으면 더미 코스트 값으로 "0"을 설정하도록 한다.
툴 저장부(106)는 최적해를 구하기 위한 툴(tool)을 저장하며, 이 툴은 헝가리언 알고리즘을 이용하여 최적해를 연산하는 과정을 포함한다.
코스트 테이블 작성기(101)로부터 작성된 코스트 테이블을 제공받은 경우, 제1최적해 연산부(102)는 툴 저장부(106)에 저장된 툴을 제공받고, 이 툴을 이용하여 초기 최적해를 구한다.
이때 제공받은 툴인 헝가리언 법을 이용하여 초기 최적해를 구하는 동작을 보기 1을 들어 설명한다.
*** 보기 1 ***
AGV 시스템에서 5대의 반송차(V1, V2, V3, V4, V5)에 5개의 작업(J1, J2, J3, J4, J5)을 할당하기 위한 각각의 코스트 행렬을 토대로 [테이블1]을 작성한다.
[테이블1]
Figure 112006067707120-pat00004
위 [테이블 1]의 각 로우(row)에서 최소 값(1, 3, 6, 10, 2)으로 각각 뺀다. 그 결과 [행렬 1]을 얻는다.
[행렬 1]
Figure 112006067707120-pat00005
위 [행렬 1]의 각 칼럼(column)에서 최소 값(0, 0, 2, 0, 5)으로 각각 뺀다. 그 결과 [행렬 2]을 얻는다.
[행렬 2]
Figure 112006067707120-pat00006
위 [행렬 2]에서 0을 가장 많이 포함하는 행과 열을 사선으로 표시한다. 그 결과 [행렬 3]을 얻는다.
[행렬3]
Figure 112006067707120-pat00007
위 [행렬 3]에서 사선이 없는 값 중에서 최소값으로 뺀다. 그 결과 [행렬 4] 를 얻는다.
[행렬 4]
Figure 112006067707120-pat00008
위[행렬 4]에서 최적으로 할당된 조합은 (V1, J2)(V2, J5)(V3, J3)(V4, J1)(V5, J4)이고, 이 조합에 따라 [테이블 1]에서 최소 코스트 합계(total minimum cost)는 32가 된다.
상기 [보기 1]에서 기술한 바와 같이, 헝가리언 알고리즘을 이용하면 최적해를 보장할 수 있다.
그런데 최적해가 여러 개인 경우로서 코스트 테이블에서 얻어지는 최소 코스트 합계가 같은 경우가 복수로 존재하고 이에 따른 최적 할당 조합이 여러 개 존재할 때는 어떤 해가 최적 해인지를 보장받을 수 없게 된다.
최적 해의 보장 문제를 감안하여, 본 발명에 따른 자동 반송시스템의 작업 할당 장치는 통계량을 연산하는 통계량 연산부(103), 통계량 연산부(103)에서 연산한 통계량에 기초하여 초기 작성된 코스트 테이블의 코스트 변환하는 코스트 테이블 변환기(104) 및 변환기(104)로부터 변환된 코스트 테이블을 제공받아 툴 저장부(106)에 저장된 헝가리언 알고리즘을 이용하여 단일한 최적 해를 구하는 제2최적해 연산부(102)를 포함한다.
초기 최적해를 구한 후 통계량에 따라 변환된 코스트 테이블에 대하여 헝가리언 알고리즘을 이용하여 단일의 최적해를 구하는 동작을 보기 2에 따라 설명한다.
*** 보기 2 ***
반송차가 물건을 이송하기 위한 물류시스템에서 헝가리언 알고리즘을 적용하였을 때 다수의 최적해가 존재할 때는 어떤 해가 물류시스템에서 가장 좋은 해인지 구별할 필요가 있다.
예를 들어, 도 2에 도시한 바와 같이, AGV 시스템에서 단일 경로(path)에서 2대의 반송차(V1, V2)과 2개의 작업(J1, J2)이 존재할 때 이동거리(distance)를 코스트로 한다.
이러한 상황이 식1)을 만족하는 경우, 코스트 테이블 작성기(102)에 의해 [테이블 2]가 작성된다.
[테이블 2]
Figure 112006067707120-pat00009
위 [테이블 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)를 확보할 수 있어서 제2반송차(V2)는 제1작업(J1)을 수행한다. 이에 따라 작업의 이송 시간(delivery time)이 지연된다.
위 [테이블 2]에서와 같이 최적해가 여러 개 인 경우, 통계량을 이용하여 최적해를 구할 필요가 있다. 이때 초기 최적 해 중에서 표준편차가 가장 최소인 해가 가장 좋은 해가 된다.
통계량 연산부(103)는 초기 최적해를 평균한 평균 코스트(μ)와 전체 코스트(Cij)의 범위(R)를 식-2)에 따라 구한다.
Figure 112006067707120-pat00010
... 식-2)
여기서, 헝가리언 알고리즘을 이용하여 얻은 초기 최적해의 총비용(TC), n은 칼럼의 개수(M)와 로우의 개수(N) 중 작은 값, CMAX는 전체 코스트 중 최대값, CMin는 전체 코스트 중 최소값이다.
또한 통계량 연산부(103)는 정규화된 코스트(δij)와 초기 작성된 코스트 테이블의 각 코스트에 정규화된 코스트(δij)를 더한 새로운 코스트(NCij)를 다음 식-3)에 따라 구한다.
Figure 112006067707120-pat00011
... 식-3)
코스트 테이블 변환기(104)는 통계량 연산부(103)에서 구한 새로운 코스트(NCij)를 토대로 코스트 테이블을 변환한다.
제2최적해 연산부(105)는 변환된 코스트 테이블에 대하여 헝가리언 알고리즘을 이용하여 단일의 최적해를 구할 수 있다. 이해를 돕기위해, 도 3을 참고하면, 평균 코스트(μ)에 가까울수록 정규화된 코스트(δij)가 작고 평균 코스트(μ)에 멀어질수록 정규화된 코스트(δij)가 커지게 되므로, 새로 변환된 코스트 테이블로부터 단일의 최적해를 얻을 수 있다.
초기 최적해가 여러 개인 경우 표준편차의 최소값이 해가 되는 이유를 수학적으로 증명하면 다음과 같다.
1) 평균(μ)와 범위(R)를 새로운 코스트 테이블을 작성한다(단, A+D=B+C).
Figure 112006067707120-pat00012
2) 대각선의 합의 크기를 비교한다.
Figure 112006067707120-pat00013
3) A+D=B+C일 때, ｜A-D｜<｜B-C｜이면 A2+D2<B2+C2이다.
즉,
Figure 112006067707120-pat00014
따라서 표준편차가 작은 A와 D가 최적해가 된다.
위에서 설명한 방법을 [테이블2]에 적용하여 단일의 최적해를 구하는 동작을 설명한다.
제1최적해 연산부(102)는 [테이블 2]에 대해 헝가리언 알고리즘을 이용하여 초기 최적해 (V1, J2)(V2, J1)를 구한다.
통계량 연산부(103)는 평균 코스트(μ)와 전체 코스트(Cij)의 범위(R)를 구한다.
μ = (6+14)/2 = 10,
R = 14-6 = 8
코스트 테이블 변환기(104)는 평균 코스트(μ)와 전체 코스트(Cij)의 범위(R)와 정규화된 코스트(δij)와 초기 작성된 코스트 테이블의 각 코스트에 정규화된 코스트(δij)를 더한 새로운 코스트(NCij)를 토대로 초기 작성된 코스트 테이블을 변환하여 [테이블 3]을 얻는다.
[테이블3]
Figure 112006067707120-pat00015
제2최적해 연산부(105)는 변환된 [테이블 3]의 코스트에 대하여 헝가리언 알고리즘을 이용하여 최적해를 구하며, 그 결과 최적으로 할당된 조합으로 (V2, J1)(V1, J2)가 얻어진다.
이하에서는 보기 2보다 좀더 복잡한 경우의 예를 설명한다.
*** 보기 3 ***
도 4에 도시한 바와 같이, AGV 시스템에서 단일 경로(path)에서 3대의 반송차(V1, V2, V3)과 3개의 작업(J1, J2, J3)이 존재할 때 이동거리(distance)를 코스트로 한다.
코스트에 대한 작업 할당에 있어서 식-1)을 만족하는 경우, 코스트 테이블 작성기(101)는 [테이블4]를 작성한다.
[테이블 4]
Figure 112006067707120-pat00016
제1최적해 연산부(102)는 툴 저장부(106)로부터 제공받은 헝가리언 알고리즘을 이용하여 초기 최적해를 구한다. 그 결과 초기 최적해로서 (V1, J3)(V2, J1)(V3, J2)를 얻는다.
통계량 연산부(103)는 평균 코스트(μ)와 전체 코스트(Cij)의 범위(R)를 구한다.
μ = (5+14+15)/3 = 11,
R = 16-5 = 11
코스트 테이블 변환기(104)는 평균 코스트(μ)와 전체 코스트(Cij)의 범위(R)와 정규화된 코스트(δij)와 초기 작성된 코스트 테이블의 각 코스트에 정규화된 코스트(δij)를 더한 새로운 코스트(NCij)를 토대로 초기 작성된 코스트 테이블을 변환하여 [테이블 5]을 얻는다.
[테이블 5]
Figure 112006067707120-pat00017
제2최적해 연산부(105)는 변환된 [테이블 5]의 코스트에 대하여 헝가리언 알고리즘을 이용하여 최적해를 구하며, 그 결과 최적으로 할당된 조합으로 (V1, J1)(V2, J2)(V3, J3)가 얻어진다.
상기와 같이 다수의 반송차에 다수의 작업을 할당하는 방법을 요약하면 도 5와 같이 순서도로 나타낼 수 있다.
먼저, 작업 코스트에 대하여 식-1)과 같이 수식화가 가능하면 코스트 테이블을 작성한다(201). 이때 작성된 코스트 테이블은 반송차의 대수(M)와 작업의 개수(N)가 같은지를 비교한다(202). 그 비교 결과 반송차의 대수(M)가 작업의 개수(N)보다 크면 부족한 개수(M-N)만큼 더미 코스트 값으로 "0"을 설정하도록 한다(203). 그 비교 결과 반송차의 대수(M)가 작업의 개수(N)보다 작으면 부족한 개수(N-M)만큼 더미 코스트 값으로 "0"을 설정하도록 한다(204).
그 비교 결과 반송차의 대수(M)가 작업의 개수(N)와 같거나 더미 코스트를 설정한 경우, 제1최적해 연산부(102)는 툴 저장부(106)에 저장된 헝가리언 알고리즘을 이용하여 초기 최적해를 구한다(205).
통계량 연산부(103)은 초기 최적해와 초기 작성된 코스트 테이블의 코스를 토대로 통계량을 구한다. 이 통계량은 최적해가 다수 개인 경우 표준편차가 작은 해를 구하기 위한 것으로서, 평균 코스트(μ)와 전체 코스트(Cij)의 범위(R)와 정규화된 코스트(δij)와 초기 작성된 코스트 테이블의 각 코스트에 정규화된 코스트(δij)를 더한 새로운 코스트(NCij)를 포함한다(206).
코스트 테이블 변환기(104)는 통계량을 이용하여 초기 작성한 코스트 테이블을 변환하는데, 그러한 예는 보기 2 및 3에 설명한 바와 같다(207).
마지막으로 제2최적해 연산부(105)는 변환된 코스트 테이블에 대하여 헝가리언 알고리즘을 이용하여 단일의 최적해를 구하게 된다(208).
이와 같이 초기 최적해를 구하고 나서 통계량을 이용하여 단일의 최적해를 구하는 방법은 APSolver 프로그램을 이용하여 충분히 많은 횟수(백만번 이상)만큼 시뮬레이션을 하여 검증을 하여 본 결과 최적해를 구하는 기존의 방법보다 월등하게 빠르게 수행됨을 알 수 있었으며, 그러한 시뮬레이션 화면의 예가 도 6에 도시되어 있다.
이상과 같이 본 발명은 물류시스템에서 다수의 반송차에 다수의 작업을 할당함에 있어서 헝가리언 알고리즘을 이용하여 최적해를 구할 수 있다.
본 발명은 초기 최적해가 복수로 존재하는 경우 통계량을 이용하여 변환한 코스트 테이블에 대하여 헝가리언 알고리즘을 적용하여 단일의 최적해를 구할 수 있다. 따라서 본 발명은 다수의 반송차에 다수의 작업을 할당하는데 있어 헝가리언 법을 이용하여 최적의 할당을 위한 최적해를 구함으로서 반송차간 간섭을 줄이고 반송효율을 향상할 수 있으며, 특히 작업 할당이 최적화되지 않을 때 작업 스와핑(Job Swapping)의 문제에 효과적으로 대처할 수 있다.

Claims (15)

  1. 다수의 반송차에 다수의 작업을 할당하기 위한 자동 반송시스템의 작업 할당 장치에 있어서,
    상기 반송차와 작업에 대응되는 코스트를 이용하여 테이블을 초기 작성하는 코스트 테이블 작성기;
    상기 작성된 코스트 테이블의 코스트에 대하여 헝가리언 알고리즘을 이용하여 초기 최적해를 얻기 위한 제1 최적해 연산부;
    상기 초기 최적해와 초기 작성된 코스트 테이블의 코스트에 관계된 통계량을 연산하는 통계량 연산부;
    상기 연산한 통계량을 이용하여 초기 작성된 코스트 테이블을 변환하는 코스트 테이블 변환기; 및
    상기 변환된 코스트 테이블의 코스트에 대하여 헝가리언 알고리즘을 이용하여 단일의 최적해를 얻기 위한 제2최적해 연산부를 포함하는 자동 반송시스템의 작업 할당 장치.
  2. 제1항에 있어서, 상기 헝가리언 알고리즘을 저장하기 위한 툴 저장부를 더 포함하는 자동 반송시스템의 작업 할당 장치.
  3. 제1항에 있어서, 상기 코스트 테이블 작성기는 다음 식-A)을 만족하는 경우에 코스트 테이블을 작성하는 자동 반송시스템의 작업 할당 장치.
    Figure 112006067707120-pat00018
    식-A)
    여기서 Cij는 작업(j)에 대하여 할당된 반송차(i)의 코스트이고, xij는 작업(j)에 대하여 할당된 반송차(i)이고, N은 반송차의 대수이며, M은 작업들의 개수이다.
  4. 제1항에 있어서, 상기 코스트 테이블 작성기는 작성된 코스트 테이블의 로(row)의 개수와 컬럼(column)의 개수가 같도록 작성하는 자동 반송시스템의 작업 할당 장치.
  5. 제4항에 있어서, 상기 코스트 테이블 작성기는 로(row)의 개수와 컬럼(column)의 개수가 같지 않으면 부족한 개수만큼 더미 코스트 값으로 "0"을 설정하는 자동 반송시스템의 작업 할당 장치.
  6. 삭제
  7. 제1항에 있어서, 상기 통계량 연산부는 초기 최적해가 다수 개인 경우에 통계량을 연산하는 자동 반송시스템의 작업 할당 장치.
  8. 제7항에 있어서, 상기 통계량 연산부는 다수 개의 초기 최적해 중 어느 하나를 설정하기 위하여 초기 최적해와 초기 작성된 코스트 테이블의 코스트로부터 정규화된 코스트를 연산하는 자동 반송시스템의 작업 할당 장치.
  9. 제8항에 있어서, 상기 통계량 연산부는 정규화된 코스트(δij)와 초기 작성된 코스트 테이블의 각 코스트에 정규화된 코스트(δij)를 더한 새로운 코스트(NCij)를 다음 식-B)에 따라 구하는 자동 반송시스템의 작업 할당 장치,
    Figure 112012085388368-pat00019
    .. 식-B)
    여기서, μ는 초기 최적해를 평균한 평균 코스트이고, R은 전체 코스트(Cij)의 범위이다.
  10. 다수의 반송차에 다수의 작업을 할당하기 위한 자동 반송시스템의 작업 할당 방법에 있어서,
    상기 반송차와 작업에 대응되는 코스트를 이용하여 초기 코스트 테이블을 작성하는 단계;
    초기 작성된 코스트 테이블에 대하여 헝가리언 알고리즘을 이용하여 초기 최적해를 얻는 단계;
    상기 초기 최적해와 초기 작성된 코스트 테이블의 코스트에 관계된 통계량을 연산하는 단계;
    상기 연산한 통계량을 이용하여 초기 작성한 코스트 테이블의 코스트를 변환하는 단계; 및
    상기 변환된 코스트 테이블의 코스트에 대하여 헝가리언 알고리즘을 이용하여 단일의 최적해 얻는 단계를 포함하는 자동 반송시스템의 작업 할당 방법.
  11. 제10항에 있어서, 상기 초기 최적해가 다수 개인 경우, 상기 통계량을 연산하는 자동 반송시스템의 작업 할당 방법.
  12. 제11항에 있어서, 상기 통계량은 초기 최적해와 초기 작성된 코스트 테이블의 코스트로부터 정규화된 코스트를 포함하는 자동 반송시스템의 작업 할당 방법.
  13. 제11항에 있어서, 상기 통계량은 정규화된 코스트(δij)에 이외에 초기 작성된 코스트 테이블의 각 코스트에 정규화된 코스트(δij)를 더한 새로운 코스트(NCij)를 포함하는 자동 반송시스템의 작업 할당 방법.
  14. 제10항에 있어서,
    상기 초기 코스트 테이블 작성하는 경우 코스트 테이블의 로의 개수와 컬럼의 개수가 같도록 작성하는 자동 반송시스템의 작업 할당 방법.
  15. 제11항에 있어서, 상기 초기 코스트 테이블의 로의 개수와 컬럼의 개수가 같지 않으면 부족한 개수만큼 더미 코스트 값으로 "0"을 설정하는 자동 반송시스템의 작업 할당 방법.
KR1020060090873A 2006-09-19 2006-09-19 자동반송시스템의 작업 할당 장치 및 그 방법 KR101287528B1 (ko)

Priority Applications (3)

Application Number Priority Date Filing Date Title
KR1020060090873A KR101287528B1 (ko) 2006-09-19 2006-09-19 자동반송시스템의 작업 할당 장치 및 그 방법
US11/771,206 US8731697B2 (en) 2006-09-19 2007-06-29 Job assignment apparatus of automatic material-handling system and method thereof
JP2007202785A JP4675360B2 (ja) 2006-09-19 2007-08-03 自動搬送システムの作業割当装置及びその方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020060090873A KR101287528B1 (ko) 2006-09-19 2006-09-19 자동반송시스템의 작업 할당 장치 및 그 방법

Publications (2)

Publication Number Publication Date
KR20080025994A KR20080025994A (ko) 2008-03-24
KR101287528B1 true KR101287528B1 (ko) 2013-07-19

Family

ID=39189686

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020060090873A KR101287528B1 (ko) 2006-09-19 2006-09-19 자동반송시스템의 작업 할당 장치 및 그 방법

Country Status (3)

Country Link
US (1) US8731697B2 (ko)
JP (1) JP4675360B2 (ko)
KR (1) KR101287528B1 (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11815909B2 (en) 2021-01-18 2023-11-14 Samsung Display Co., Ltd. System for and method of controlling driving of automated guided vehicle

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9571400B1 (en) * 2014-02-25 2017-02-14 Google Inc. Weighted load balancing in a multistage network using hierarchical ECMP
CN107871218B (zh) * 2016-09-27 2021-01-08 杭州海康机器人技术有限公司 一种跨仓储搬运控制方法、装置及系统
CN108829105A (zh) * 2018-06-21 2018-11-16 浙江工业大学 一种基于km算法和人工势场法的仓储物流调度避障优化方法
CN118780578B (zh) * 2024-09-10 2024-11-05 北京氢远质投新能源汽车有限公司 一种启发式新能源物流车辆动态补能调度方法

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0573142A (ja) * 1991-05-10 1993-03-26 Shinko Electric Co Ltd 移動ロボツトシステムにおける制御方法

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5648912A (en) * 1993-04-12 1997-07-15 International Business Machines Corporation Interconnection resource assignment method for differential current switch nets
US5963911A (en) * 1994-03-25 1999-10-05 British Telecommunications Public Limited Company Resource allocation
CN1218260C (zh) * 1996-11-22 2005-09-07 维杜斯有限公司 用于任务分配的设备和方法
US6276533B1 (en) 2000-02-16 2001-08-21 Brian Kaplan Weight-specific elixir dosage calculation reference
JP4052624B2 (ja) 2001-03-30 2008-02-27 株式会社東芝 搬送システム及び搬送システムの制御方法
CN1312659C (zh) 2001-10-19 2007-04-25 皇家飞利浦电子股份有限公司 正弦模型参数的频率差分编码方法和设备
US7664561B1 (en) * 2002-04-25 2010-02-16 Taiwan Semiconductor Manufacturing Company, Ltd. Task queuing methodology for reducing traffic jam and to control transmission priority in an automatic material handling system
WO2005114499A1 (en) 2004-05-24 2005-12-01 Matsushita Electric Industrial Co., Ltd Method and apparatus for allocating data paths
KR20050002692A (ko) 2004-10-27 2005-01-10 나수영 가금류 이동·가공 차량
CA2551467A1 (en) * 2006-07-04 2008-01-04 University Of New Brunswick System and method for optimizing linehaul operations

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0573142A (ja) * 1991-05-10 1993-03-26 Shinko Electric Co Ltd 移動ロボツトシステムにおける制御方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
Alan Holland et al., ‘Fast vickrey-pricing for the assignment problem’, Proc. of ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, 2003*
Alan Holland et al., 'Fast vickrey-pricing for the assignment problem', Proc. of ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, 2003 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11815909B2 (en) 2021-01-18 2023-11-14 Samsung Display Co., Ltd. System for and method of controlling driving of automated guided vehicle

Also Published As

Publication number Publication date
US8731697B2 (en) 2014-05-20
JP4675360B2 (ja) 2011-04-20
JP2008077638A (ja) 2008-04-03
US20080071404A1 (en) 2008-03-20
KR20080025994A (ko) 2008-03-24

Similar Documents

Publication Publication Date Title
Gen et al. Evolutionary techniques for optimization problems in integrated manufacturing system: State-of-the-art-survey
Tayur Structural properties and a heuristic for kanban-controlled serial lines
KR101287528B1 (ko) 자동반송시스템의 작업 할당 장치 및 그 방법
Ng et al. Quay crane scheduling in container terminals
CN107235276A (zh) 货物搬运方法和装置
Zhao et al. Integrated facility layout design and flow assignment problem under uncertainty
Levitin et al. Optimal routing of multiple-load AGV subject to LIFO loading constraints
JP5444622B2 (ja) 置場運用計画装置および運用方法
Jahed et al. Mathematical modeling for a flexible manufacturing scheduling problem in an intelligent transportation system
Lee et al. Operation sequence and tool selection in flexible manufacturing systems under dynamic tool allocation
Tanizaki et al. Scheduling algorithms using metaheuristics for production processes with crane interference
Mahadevan et al. Determination of unit load sizes in an AGV-based material handling system for an FMS
Yener et al. Simulation of re-arrangement and healing in robotic compact bin-storage system
Odior et al. Determining feasible solutions of a multicriteria assignment problem.
Ono et al. Routing problem of multiple mobile robots with human workers for pickup and dispatch tasks in warehouse
Qi et al. An optimal layout pattern-based solution approach to the extended machine layout problem with multirow multicolumn structure
Ben-Salem et al. A simulation-based approach for an effective AMHS design in a legacy semiconductor manufacturing facility
Sarker et al. Locating sets of identical machines in a linear layout
Behjat et al. Quay cranes and yard trucks scheduling problem at container terminals
JP2004206309A (ja) 工程編成装置、工程編成方法および工程編成プログラム
WO2018193585A1 (ja) 搬送作業管理装置、システム、方法および記録媒体
Cho et al. Dynamic Crane Scheduling with Reinforcement Learning for a Steel Coil Warehouse
Takahama et al. A determination method of product allocation schedule for warehouse management
Joseph et al. Simulation modelling and analysis of routing flexibility of a flexible manufacturing system
JP7513045B2 (ja) 倉庫設備設定方法及び倉庫設備設定装置

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20060919

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20110315

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20060919

Comment text: Patent Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20120821

Patent event code: PE09021S01D

E90F Notification of reason for final refusal
PE0902 Notice of grounds for rejection

Comment text: Final Notice of Reason for Refusal

Patent event date: 20130208

Patent event code: PE09021S02D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20130628

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20130712

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20130715

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
FPAY Annual fee payment

Payment date: 20160630

Year of fee payment: 4

PR1001 Payment of annual fee

Payment date: 20160630

Start annual number: 4

End annual number: 4

FPAY Annual fee payment

Payment date: 20170630

Year of fee payment: 5

PR1001 Payment of annual fee

Payment date: 20170630

Start annual number: 5

End annual number: 5

FPAY Annual fee payment

Payment date: 20180629

Year of fee payment: 6

PR1001 Payment of annual fee

Payment date: 20180629

Start annual number: 6

End annual number: 6

FPAY Annual fee payment

Payment date: 20190628

Year of fee payment: 7

PR1001 Payment of annual fee

Payment date: 20190628

Start annual number: 7

End annual number: 7

PR1001 Payment of annual fee

Payment date: 20200630

Start annual number: 8

End annual number: 8

PR1001 Payment of annual fee

Payment date: 20210628

Start annual number: 9

End annual number: 9

PC1903 Unpaid annual fee

Termination category: Default of registration fee

Termination date: 20230423