Nothing Special   »   [go: up one dir, main page]

KR101617689B1 - 계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템 - Google Patents

계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템 Download PDF

Info

Publication number
KR101617689B1
KR101617689B1 KR1020130091886A KR20130091886A KR101617689B1 KR 101617689 B1 KR101617689 B1 KR 101617689B1 KR 1020130091886 A KR1020130091886 A KR 1020130091886A KR 20130091886 A KR20130091886 A KR 20130091886A KR 101617689 B1 KR101617689 B1 KR 101617689B1
Authority
KR
South Korea
Prior art keywords
plan
feature vector
situation
database
situation feature
Prior art date
Application number
KR1020130091886A
Other languages
English (en)
Other versions
KR20150015884A (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 KR1020130091886A priority Critical patent/KR101617689B1/ko
Publication of KR20150015884A publication Critical patent/KR20150015884A/ko
Application granted granted Critical
Publication of KR101617689B1 publication Critical patent/KR101617689B1/ko

Links

Images

Classifications

    • G—PHYSICS
    • G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
    • G16Z—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS, NOT OTHERWISE PROVIDED FOR
    • G16Z99/00—Subject matter not provided for in other main groups of this subclass

Landscapes

  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

본 발명은 자원 할당 계획 방법 및 시스템에 관한 것으로서, 구체적으로는 다양한 상황에 대하여 미리 생성한 계획 데이터베이스를 이용하여, 주어진 문제 상황과 유사한 경우의 계획을 검색한 후, 다시 검색된 계획을 수정하여 주어진 문제 상황에 대한 계획을 도출함으로써 단시간 내에 계획을 생성할 수 있는 계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템에 관한 것이다.
본 발명은 (a) 주어진 문제 상황에 대해 문제 상황 특징 벡터를 생성하는 단계; (b) 계획 데이터베이스를 검색하여, 상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대해 기 생성해 놓은 계획을 검출하는 단계; 및 (c) 상기 유사 상황 특징 벡터에 대해 기생성해 놓은 계획을 수정하여 상기 문제 상황에 대한 계획을 산출하는 단계를 포함하는 것을 특징으로 하는 자원 할당 계획 방법을 개시하며, 본 발명에 따르면, 주어진 자원 할당 문제에 대한 계획을 산출함에 있어, 미리 생성된 계획 데이터베이스에서 상기 문제 상황에 대한 유사 상황을 검출하고, 그에 따르는 유사 계획을 수정하여 상기 문제 상황에 대한 계획을 도출함으로써, 특정한 문제 상황에 대한 효율적인 자원 할당 계획을 실시간 또는 짧은 시간 내에 산출할 수 있는 자원 할당 계획 방법 및 시스템을 제공하는 효과를 갖는다.

Description

계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템 {A method and system for fast resource allocation planning using plan retrieval and repair}
본 발명은 자원 할당 계획 방법 및 시스템에 관한 것으로서, 구체적으로는 다양한 상황에 대하여 미리 생성한 계획 데이터베이스를 이용하여, 주어진 문제 상황과 유사한 경우의 계획을 검색한 후, 다시 검색된 계획을 수정하여 주어진 문제 상황에 대한 계획을 도출함으로써 단시간 내에 계획을 생성할 수 있는 계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템에 관한 것이다.
자원 할당 계획 문제는 한정된 자원들(resources)과 이들을 필요로 하는 활동들(activities)이 주어졌을 때, 원하는 성능이 최적화 되도록 자원들을 활동들에 할당하여 사용하는 계획을 수립하는 문제이다. 여기서 자원과 활동이란 추상적인 개념들로서, 통상적으로 수행해야 할 업무, 공장에서의 제조 공정, 물건의 배송 등과 같이 해야 할 일이 활동에 해당되며, 이들의 수행을 위해서 필요한 인력, 기계, 시설 등과 같은 것들이 자원에 해당된다.
활동이 수행되는 방식은 다양하게 지정될 수 있는 바, 하나의 활동이 여러 개의 세부 활동들(sub-activities)로 구성되어 세부 활동들이 순차적(sequential)으로 수행되어야 하는 경우도 있고, 세부 활동들이 병렬적(parallel)으로 수행되어야 하는 경우도 있으며, 이들이 혼합된 형태로서 일부 세부 활동들은 순차적으로, 다른 세부 활동들은 병렬적으로 수행될 수 있는 경우도 존재한다.
또한, 하나의 세부 활동을 수행하기 위해서 필요한 자원 요구 사항은 자원 유형(resource type) 및 개수의 관점에서 다양하게 정의될 수 있는데, 하나의 세부 활동은 하나의 자원 유형에 속하는 한 개 이상의 자원을 필요로 할 수도 있고, 여러 개의 자원 유형으로부터 각각 한 개 이상의 자원을 필요로 할 수도 있으며, 하나의 세부 활동에 대해, 이러한 자원 요구 사항이 하나 이상의 대안으로 여러 개 존재할 수도 있다.
즉, 하나의 활동 유형(activity type)은 앞서 설명한 세부 활동들의 수행 순서와 각 세부 활동들의 자원 요구 사항들을 명시함으로써 정의되고, 하나의 자원 할당 계획 문제에는 한 개 이상의 활동 유형과 각 활동 유형 별로 요구되어지는 수행 개수, 한 개 이상의 종류의 자원 유형과 각 자원 유형별로 가용한 자원의 개수들이 포함되며, 활동 유형들 및 자원 유형들에 대한 정의는 자원 할당 계획 문제의 해를 구함에 있어서 제약식(constraint)으로서의 역할을 하게 된다.
자원 할당 계획 문제의 성능으로는 통상적으로 주어진 계획 기간 동안 해야 할 활동을 모두 수행하면서 자원의 가동율을 최대화 또는 비용을 최소화하거나, 활동들에 요구되는 완료 예정일(due date)을 최대한 만족시키거나, 요구되는 활동을 모두 수행하는 데에 걸리는 시간을 최소화하는 등의 다양한 형태의 성능 목표가 존재할 수 있으며, 이를 자원 계획 할당 문제의 목적 함수라고 부른다.
예를 들어, 공급망 관리(supply chain management) 문제 중, 마스터 계획(master planning) 문제에서는 주별 예측 수요가 주어졌을 때, 총 생산 비용, 재고 유지 비용, 운송 비용, 납기 지연에 따른 비용, 주문을 만족시키지 못할 경우에 대한 비용들을 최소화하기 위한 각 공장에서의 주별 생산량, 각 공장으로부터 각 유통센터까지의 주별 운송량, 각 유통센터로부터 고객으로까지의 주별 운송량 등을 결정하는 바, 고객의 수요가 활동에 해당하고, 공장에서의 생산 작업 및 공장, 유통 센터, 고객 간의 운송 작업이 수요를 처리하기 위한 세부 활동에 해당되며, 한정된 생산 용량을 가진 공장과 한정된 운송 능력을 가진 여러 가지 운반 수단들이 자원에 해당된다.
또 다른 예로서, 유통 문제 중에서, 매대 진열 문제는 소매 매장의 진열대에 어떠한 상품들을 진열하는가를 결정하는 문제로서, 매일의 공간 활용을 최대로 함과 동시에 상품 판매를 최대화할 수 있는 상품 진열 계획을 생성하는 문제를 들 수 있다. 이 문제의 경우, 유한한 개수의 매대의 상품 진열 위치가 자원에 해당되며, 각 상품의 진열이 자원인 매대의 상품 진열 위치를 필요로 하는 활동에 해당된다.
좀 더 구체적으로 자원 할당 계획 문제를 설명하기 위해서, 본 발명에서는 다음과 같이 스케줄링(scheduling) 문제를 예로 들어 설명하고자 한다.
스케줄링 문제는 종래 컴퓨터 시스템에서의 프로세스 관리를 비롯하여, 제조 시스템에서의 공정 관리, 물류 시스템, 병원 등 한정된 자원에 대한 효율적 운용이 필요한 상황에서 광범위하게 적용되어 왔으며, 이에 대한 다양한 기법들이 존재한다.
이처럼 스케줄링 문제라 함은 처리하고자 하는 과업(job)들이 존재할 때, 주어진 자원(resource)들을 언제 어떻게 사용하여 어떤 과업을 처리하는지를 결정하는 문제를 말하며, 이에 대한 해를 스케줄이라고 부른다. 즉, 스케줄링 문제에서의 과업은 자원 할당 계획 문제에서의 활동에 해당된다.
구체적으로 스케줄링 문제는 하나 이상 종류의 자원 유형과 한가지 이상의 과업 유형으로 구성되며, 각 과업은 하나 또는 그 이상의 처리해야 할 작업(operation)들로 정의된다. 하나의 작업은 하나 이상의 자원 유형을 필요로 할 수 있으며, 각 자원 유형에서 하나 이상의 자원을 필요로 할 수도 있다. 또한, 하나의 작업에는 여러 가지의 대체 자원들이 존재할 수 있다. 하나의 과업에 속한 작업들 간에는 가능한 작업 순서(route)를 표현하는 선후 관계(precedence) 제약이 존재할 수 있으며, 이때 선후 관계는 직렬적이거나 병렬적일 수 있으며, 하나 이상의 대체(alternative) 작업 순서가 존재할 수도 있다.
예를 들어, A 반도체 라인에 대한 스케줄을 생성하는 문제를 고려해 보면, A 반도체 라인에서 사용되는 장비로 R1 1대, R2 2대, R3 3대가 있으며, 상기 라인에서 생산되는 제품은 J1 제품과 J2제품이 있는데, J1 제품의 생산을 위해서는 O11 → O12, 또는 O11 → O13의 대체 작업 순서를 가질 수 있고, J2의 경우는 <O21, O22> → O23의 작업 순서를 가질 수 있다고 하자. 여기서 <O21, O22>는 두 개의 작업이 동시 수행 가능함을 나타낸다. 또한, 각 작업들의 수행에 필요한 자원들은 O11 = {R1, R2}, O12 = {2R2}, O13 = {R1, 2R3}, O21 = {R3}, O22 = {2R2}, O23 = {R1}과 같이 다중 집합(multi-set)의 형태로 나타낼 수 있다. 예를 들어, 상기 작업 O13은 R1 유형의 자원 1개와 R3 유형의 자원 2개가 필요함을 나타낸다.
스케줄 생성의 예로서, 상기와 같은 경우에 대하여 주어진 계획 기간 동안J1과 J2의 총 생산량을 최대로 하는 스케줄을 작성하는 경우 등을 생각해 볼 수 있다. 또한, 스케줄링 문제에는 다양한 목적 함수가 사용될 수 있는 바, 자원의 가동율 최대화, 과업 완료 총시간의 최소화, 과업에 대한 납기 준수율 최대화 등이 많이 사용되는 목적 함수의 예이다. 또한, 하나의 목적 함수만을 사용하는 것이 아니라, 여러 개의 목적 함수에 가중치를 주고 결합하여 최적화하는 방식도 많이 사용되고 있다.
그런데 위와 같은 스케줄링 작업에는 많은 어려움이 따르는 것이 사실이다. 예를 들어 반도체 패키징 라인의 경우, 생산해야 할 패키지에 따라 필요한 작업들과, 작업 순서가 다르고 각 작업을 수행할 수 있는 여러 종류의 대체 장비들이 존재한다. 또한, 하나의 장비가 하나의 작업을 수행한 후 다른 작업을 수행하고자 할 경우, 상황에 따라서는 장비의 설정 변경(setup change)에 따른 시간 소요가 발생할 수도 있다. 따라서, 상기와 같은 제약들을 고려함과 동시에 정의된 목적 함수를 최적화하기 위해서, 주어진 패키지들에 대해 생산 라인에 있는 모든 장비들에 대한 스케줄을 생성해야 할 경우, 많은 종류의 자원과 과업에 대하여 그 제약 조건을 고려하는 스케줄을 생성하여야 하는 바, 여기에 상당한 시간과 노력이 투입되어야 하는 문제가 발생한다.
더군다나, 상기한 반도체 패키징 라인과 같은 대규모 장비 산업 등의 경우, 불시에 특정 장비가 고장이 나는 등의 원인으로 신속한 재스케줄링(re-scheduling) 작업이 필요함에도 스케줄링에 오랜 시간이 필요할 경우, 그에 따른 손실이 매우 커질 수 있다. 또한, 앞서 예시한 공급망 관리에서나 유통에서의 자원 할당 계획 문제들과 같이 자원의 효율적 할당이 회사의 경쟁력과 직결될 수 있는 경우에도 신속한 자원 할당 계획에 대한 요청을 간과할 수 없다. 이렇듯, 특정한 문제 상황에 따르는 자원 할당 계획 작업을 실시간 또는 짧은 시간 내에 수행할 수 있는 방법 및 시스템이 요구되고 있으나, 기존의 방법들은 성능이 좋은 계획을 생성하기 위해서는 많은 시간이 걸리거나, 빠른 시간 내에 계획을 생성하기 위해서는 결과로 산출된 계획의 성능이 만족스럽지 않은 문제가 있는 바, 아직 이에 대한 적절한 해법이 제시되지 못하고 있다.
본 발명은 상기와 같은 종래 기술의 문제점을 해결하기 위해 창안된 것으로, 특정한 문제 상황에 따르는 효율적인 자원 할당 계획 생성을 실시간 또는 짧은 시간 내에 수행할 수 있는 자원 할당 계획 방법 및 시스템을 제공하는 것을 목적으로 한다.
상기 과제를 해결하기 위한 본 발명의 한 측면에 따른 자원 할당 계획 방법은 (a) 주어진 문제 상황에 대해 문제 상황 특징 벡터를 생성하는 단계; (b) 계획 데이터베이스를 검색하여, 상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대해 기생성 해놓은 계획을 검출하는 단계; 및 (c) 상기 유사 상황 특징 벡터에 대해 기생성 해놓은 계획을 수정하여 상기 문제 상황에 대한 계획을 산출하는 단계를 포함하며, 상기 계획 데이터베이스에는 복수의 상황 특징 벡터와 그에 대해 기생성된 계획들이 저장되어 관리되는 것을 특징으로 한다.
여기서, 상기 (a) 단계에 앞서, (p) 복수의 상황 특징 벡터에 대한 계획을 미리 생성해서 저장해놓기 위해서, 다양한 상황 특징 벡터를 입력으로 받아 별도의 계획 생성기(planner)를 사용하여 계획을 생성함으로써, 상기 계획 데이터베이스를 생성하는 단계를 더 포함한다.
여기서, 상기 (p) 단계에서, 상기 계획 데이터베이스를 생성함에 있어, 문제 상황이 복수로 존재하는 경우 상기 문제 상황을 소정의 규칙을 사용하여 하나 이상의 문제 상황의 대표치를 사용함으로써 상기 계획 데이터베이스의 용량을 줄일 수 있다.
여기서, 상기 (p) 단계에서, 문제 상황이 중대하게 변경되는 경우에 대한 계획 데이터베이스를 미리 생성할 수 있다.
여기서, 상기 (b) 단계는, 유사 상황 특징 벡터 추천기를 사용하여, 상기 계획 데이터베이스에 저장되어 있는 상황 특징 벡터들에 대한 계획 중에서, 상기 계획이 계획 수정기를 거쳐 산출되는 수정된 계획과, 상기 문제 상황 특징 벡터가 계획 생성기를 거쳐 산출되는 계획을 비교할 때, 주어진 항목의 성능치가 가장 비슷할 것으로 예측되는 유사 상황 특징 벡터들과 그들에 대한 계획들을 검출하는 단계이며, 이때 상기 계획 데이터베이스에는 상기 상황 특징 벡터에 대한 계획의 성능치도 저장되어 관리될 수 있다.
여기서, 상기 (b) 단계는, 유사 상황 특징 벡터 추천기를 사용하여, 상기 계획 데이터베이스에서 상기 문제 상황 특징 벡터와 가장 유사한 한개 이상의 상황 특징 벡터를 검출하는 단계일 수 있다.
여기서, 상기 (b) 단계에 앞서, (q) 복수의 상황 특징 벡터 및 그에 대한 계획에 대하여, 기계 학습(machine learning) 기법을 적용하여 상기 유사 상황 특징 벡터 추천기를 생성하는 단계를 더 포함할 수 있다.
여기서, 상기 기계 학습 기법은 써포트 벡터 기계(support vector machine) 또는 k-NN(k-Nearest Neighbor) 기법을 포함할 수 있다.
여기서, 상기 (b) 단계는, 상기 계획 데이터베이스 중 일부 상황 특징 벡터 만을 검색하여 상기 유사 상황 특징 벡터를 검출하도록, 사전에 상기 계획 데이터베이스의 상황 특징 벡터를 필터링하는 단계를 포함할 수 있다.
여기서, 상기 계획 데이터베이스에는 복수의 상황 특징 벡터와 그에 대해상기 계획 생성기를 이용하여 미리 생성한 계획의 전부 또는 계획의 주요 일부 정보가 저장되어 관리되고, 상기 (b) 단계에서는, 계획 데이터베이스의 상황 특징 벡터를 검색하여, 상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대한 계획의 전부 또는 일부 정보를 상기 유사 상황 특징 벡터 추천기로부터 추천받고, 상기 (c) 단계에서는, 상기 유사 상황 특징 벡터에 대한 계획의 전부 또는 일부 정보를 수정하여 상기 문제 상황에서의 계획을 생성할 수 있다.
여기서, 상기 (b) 단계는, 계획 데이터베이스의 상황 특징 벡터 및 파생 상황 특징 벡터를 검색하여, 상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대한 계획을 상기 유사 상황 특징 벡터 추천기를 이용하여 검출하는 단계이며, 상기 계획 데이터베이스에는 복수의 상황 특징 벡터 및 그에 대한 계획에 더하여, 복수의 파생 상황 특징 벡터 및 그에 대한 계획이 함께 저장되어 관리될 수 있다.
여기서, 상기 (c) 단계는, 계획 수정기를 사용하여, 상기 유사 상황 특징 벡터 및 그에 대해 계획 생성기를 이용하여 미리 생성한 계획 및 상기 문제 상황 특징 벡터를 입력으로 하여, 상기 문제 상황 특징 벡터에 대한 계획을 산출하는 단계일 수 있다.
여기서, 상기 계획 수정기는, 유사 상황 특징 벡터 추천기가 한개 이상의 유사 상황 특징 벡터를 추천하는 경우, 각 유사 상황 특징 벡터에 따르는 계획을 수정하여 그 중 계획 성능치가 가장 좋은 계획을 산출 할 수 있다.
여기서, 상기 계획 수정기는, 상기 유사 상황 특징 벡터에 대해 미리 생성된 계획을 상기 문제 상황 특징 벡터에 적합하도록 수정한 계획과, 상기 문제 상황 특징 벡터를 입력으로 상기 계획 생성기를 이용하여 자원 할당 계획을 직접 생성한다고 가정했을 때에 도출되는 계획과의 성능 차이를 최소화할 수 있는 방식에 따라 계획을 수정하는 것이거나 상기 문제 상황 특징 벡터에 대해 최적의 성능이 달성될 수 있도록 상기 유사 상황 특징 벡터에 대해 미리 생성된 계획을 수정하는 것일 수 있다.
여기서, 상기 계획 수정기는, 복수의 상황 특징 벡터에 대해서 기존의 계획 생성기를 활용하여 생성된 계획들을 학습 데이터로 이용함으로써, 상기 계획 수정기의 상기 기존의 계획 생성기를 모사하도록, 기계 학습을 적용하여 생성된 것일 수 있다.
여기서, 상기 기계 학습 기법은 온라인 학습(on-line learning), 써포트 벡터 기계(support vector machine), 강화학습(reinforcement learning) 기법을 포함할 수 있다.
여기서, 상기 복수의 파생 상황 특징 벡터에 대한 계획을 생성함에 있어 계획 수정기를 사용하는 경우, 상기 계획 데이터베이스에는 상기 계획 수정기가 상기 유사 상황 특징 벡터의 계획을 수정할 때에 소요된 계획 수정 횟수도 함께 기록되어 관리되고, 추후 상기 계획 수정 횟수 정보를 상기 계획 수정기에 의한 계획 수정 작업시에 이용할 수 있다.
여기서, 상기 문제 상황 특징 벡터는, 가용 자원의 유형, 가용 자원의 유형별 개수, 활동의 유형, 활동의 유형별 개수, 각 활동 유형에서 세부 활동간의 선후 관계, 대체 자원, 대체 경로, 활동간 우선 순위, 활동별 완료 요구일, 자원의 설정 변경시의 제약, 자원의 설정 상태, 활동 및 세부 활동과 관련된 비용 및 시간 정보, 계산된 계획 정보, 계획 성능치, 목적함수 중 하나 이상을 포함할 수 있다.
여기서, 상기의 유사 상황 특징 벡터 추천기가 유사 상황 특징 벡터를 검출함에 있어, 소정의 방법으로 산정한 오류 가능성이 특정한 임계치를 넘는 경우, 계획 수정기를 이용하지 않고 별도의 계획 생성기를 사용하여 상기 문제 상황에 대한 계획을 직접 산출할 수 있다.
본 발명의 다른 측면에 따른 자원 할당 계획 시스템은 복수의 상황 특징 벡터 및 그에 대해 별도의 계획 생성기를 사용하여 생성된 계획과 계획 성능치를 저장하고 관리하는 계획 데이터베이스; 상기 계획 데이터베이스를 검색하여 상기 문제 상황 특징 벡터와 가장 유사한 상황 특징 벡터를 검출하거나, 상기 계획 데이터베이스에 저장되어 있는 상황 특징 벡터들에 대한 계획 중에서, 상기 계획이 계획 수정기를 거쳐 산출되는 수정된 계획과, 상기 문제 상황 특징 벡터가 상기 계획 생성기를 거쳐 산출되는 계획을 비교할 때, 주어진 항목의 성능치가 가장 비슷할 것으로 예측되는 유사 상황 특징 벡터와 그에 대한 기생성된 계획을 도출하는 유사 상황 특징 벡터 추천기; 및 상기 하나 이상의 유사 상황 특징 벡터에 대한 계획을 수정하여 상기 주어진 문제 상황에 대한 계획을 산출하는 계획 수정기를 포함하는 것을 특징으로 한다.
여기서, 상기 유사 상황 특징 벡터 추천기는 복수의 상황 특징 벡터 및 그에 대한 계획에 대하여, 써포트 벡터 기계(support vector machine) 또는 k-NN(k-Nearest Neighbor)와 같은 기계 학습(machine learning) 기법을 적용하여 생성될 수 있다.
여기서, 상기 계획 수정기는, 상기 문제 상황 특징 벡터, 그에 대한 상기 유사 상황 특징 벡터 및 상기 유사 상황 특징 벡터에 대한 계획을 고려하여, 상기 계획의 수정에 따른 수정된 계획과 상기 문제 상황 특징 벡터를 입력으로 상기 계획 생성기를 이용하여 자원 할당 계획을 직접 생성한다고 가정했을 때에 도출되는 계획과의 성능치의 차이를 최소화할 수 있는 방식에 따라 계획을 수정 것일 수 있다.
여기서, 상기 계획 수정기는, 복수의 상황 특징 벡터에 대해서 기존의 계획 생성기를 활용하여 생성된 계획들을 학습 데이터로 이용함으로써, 임의의 문제 상황 특징 벡터가 주어졌을 때, 계획 수정기의 수정 결과가 기존의 계획 생성기가 생성한 계획을 모사하도록, 기계 학습을 적용하여 생성된 것일 수 있다.
여기서, 상기 계획 데이터베이스는, 문제 상황이 복수로 존재하는 경우 상기 문제 상황을 소정의 규칙을 사용하여 하나 이상의 문제 상황의 대표치를 사용함으로써 상기 계획 데이터베이스의 용량을 줄여 생성된 것일 수 있다.
여기서, 상기 계획 데이터베이스는, 상기 계획 데이터베이스를 생성함에 있어 문제 상황이 중대하게 변경되는 경우에 대한 계획 데이터베이스를 미리 생성해 둔 것일 수 있다.
여기서, 상기 유사 상황 특징 벡터 추천기는, 상기 계획 데이터베이스 중 일부 상황 특징 벡터만을 검색하여 상기 유사 상황 특징 벡터를 검출하도록, 사전에 상기 계획 데이터베이스의 상황 특징 벡터를 필터링할 수 있다.
여기서, 상기 계획 데이터베이스에는 복수의 상황 특징 벡터와 그에 대해 상기 계획 생성기를 이용하여 미리 생성된 계획의 전부 또는 계획의 주요 일부 정보가 저장되어 관리되고, 상기 유사 상황 특징 벡터 추천기는, 계획 데이터베이스의 상황 특징 벡터를 검색하여, 상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대한 계획의 전부 또는 일부 정보를 추출하며, 상기 계획 수정기는, 상기 유사 상황 특징 벡터에 대한 계획의 전부 또는 일부 정보를 수정하여 상기 문제 상황에서의 계획을 생성할 수 있다.
여기서, 상기 유사 상황 특징 벡터 추천기는, 계획 데이터베이스의 상황 특징 벡터 및 파생 상황 특징 벡터를 검색하여, 상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대한 계획을 검출하며, 상기 계획 데이터베이스에는 복수의 상황 특징 벡터 및 그에 대한 계획에 더하여, 복수의 파생 상황 특징 벡터 및 그에 대한 계획이 함께 저장되어 관리될 수 있다.
여기서, 상기 복수의 파생 상황 특징 벡터에 대한 계획을 생성함에 있어, 계획 수정기를 사용하는 경우, 상기 계획 데이터베이스에는 상기 계획 수정기가 상기 유사 상황 특징 벡터의 계획을 수정할 때에 소요된 계획 수정 횟수도 함께 기록되어 관리하고, 추후 상기 계획 수정 횟수 정보를 상기 계획 수정기에 의한 계획 수정 작업시에 이용할 수 있다.
여기서, 상기 문제 상황 특징 벡터는, 가용 자원의 유형, 가용 자원의 유형별 개수, 활동의 유형, 활동의 유형별 개수, 각 활동 유형에서 세부 활동간의 선후 관계, 대체 자원, 대체 경로, 활동간 우선 순위, 활동별 완료 요구일, 자원의 설정 변경시의 제약, 자원의 설정 상태, 활동 및 세부 활동과 관련된 비용 및 시간 정보, 계산된 계획 정보, 계획 성능치, 목적함수 중 하나 이상을 포함할 수 있다.
여기서, 상기의 유사 상황 특징 벡터 추천기가 유사 상황 특징 벡터를 검출함에 있어, 소정의 방법으로 산정한 오류 가능성이 특정한 임계치를 넘는 경우, 계획 수정기를 사용하지 않고 별도의 계획 생성기를 사용하여 상기 문제 상황에 대한 계획을 직접 산출할 수 있다.
본 발명에 따르면, 주어진 자원 할당 문제 상황에 대한 계획을 산출함에 있어, 미리 생성된 계획 데이터베이스에서 상기 문제 상황에 대한 유사 상황을 검출하고, 그에 따르는 유사 계획을 수정하여 상기 문제 상황에 대한 계획을 도출함으로써, 특정한 문제 상황에 따르는 효율적인 자원 할당 계획을 실시간 또는 짧은 시간 내에 산출할 수 있는 자원 할당 계획 방법 및 시스템을 제공하는 효과를 갖는다.
본 발명에 관한 이해를 돕기 위해 상세한 설명의 일부로 포함되는, 첨부도면은 본 발명에 대한 실시예를 제공하고, 상세한 설명과 함께 본 발명의 기술적 사상을 설명한다.
도 1은 본 발명의 일 실시예에 따른 계획 검색 및 수정 기법을 이용한 자원 할당 계획 방법의 순서도.
도 2은 본 발명의 일 실시예에 따른 계획 데이터베이스 생성시의 데이터 흐름 도해.
도 3은 본 발명의 일 실시예에 따른 파생 상황 특징 벡터를 포함하는 계획 데이터베이스 생성시의 데이터 흐름 도해.
도 4는 본 발명의 일 실시예에 따른 유사 상황 특징 벡터 추천기 생성시의 데이터 흐름 도해.
도 5는 본 발명의 일 실시예에 따른 문제 상황에 대한 계획 산출시의 데이터 흐름 도해.
도 6는 본 발명의 일 실시예에 따른 계획 검색 및 수정 기법을 이용한 자원 할당 계획 시스템의 블록도.
본 발명은 다양한 변환을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 이하에서는 특정 실시예들을 첨부된 도면을 기초로 상세히 설명하고자 한다.
본 발명을 설명함에 있어서 관련된 공지 기술에 대한 구체적인 설명이 본 발명의 요지를 흐릴 수 있다고 판단되는 경우 그 상세한 설명을 생략한다.
제1, 제2 등의 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 상기 구성요소들은 상기 용어들에 의해 한정되는 것은 아니며, 상기 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다.
본 발명은 종래 기술에 따라 반도체 생산 공정 등 다양한 활동과 자원으로 구성된 복잡한 문제 상황에 대하여 자원 할당 계획을 산출할 경우 많은 시간이 소요될 수 있고 이에 따라 상당한 손실을 초래할 수 있다는 문제점에 대하여, 주어진 문제 상황에 대한 계획을 산출함에 있어, 상기 문제 상황에 대한 문제 상황 특징 벡터를 산정한 후, 미리 생성된 계획 데이터베이스(610)에서 상기 문제 상황 특징 벡터와 가장 유사한 유사 상황 특징 벡터 및 그에 대한 기생성된 계획을 검출하고, 상기 검출된 계획을 수정하여 상기 문제 상황에 대한 계획을 도출함으로써, 특정한 문제 상황에 대한 계획 작업을 실시간 또는 짧은 시간 내에 수행할 수 있는 자원 할당 계획 방법 및 시스템을 제공하는 것을 특징으로 한다.
여기서 문제 상황(Problem Context)이라 함은 풀고자 하는 자원 할당 계획 문제를 정의하는 데이터로서 자원 할당 문제를 정의하는 데에 필요한 모든 데이터를 포함한다. 예를 들어, 자원 할당 문제의 목적 함수, 가용 자원의 유형, 각 자원의 유형별 가용 자원 개수, 활동의 유형 및 처리해야 하는 각 활동 유형별 개수, 각 활동 유형에서 세부 활동간의 선후 관계, 대체 자원, 대체 경로, 활동간 우선 순위, 활동별 완료 요구일, 자원의 설정 변경시의 제약, 자원의 설정 상태, 활동 및 세부 활동과 관련된 비용 및 시간 정보 등이 포함될 수 있다.
좀더 구체적으로 살피기 위하여 앞의 A 반도체 라인의 예로 돌아가, J1 제품 2개와 J2 제품 3개를 생산하기 위해서 스케줄을 생성하는 경우를 고려해 보면, 상기한 과업의 유형 및 숫자로서 2J1, 3J2, 가용 자원의 유형 및 숫자로서 1R1, 2R2, 3R3, 각 작업의 선후 관계 및 대체 작업으로서 O11 → O12, 또는 O11 → O13, 그리고 <O21, O22> → O23, 각 작업의 소요 시간 등이 모두 상기 자원 할당 계획 문제를 정의하고 제약하는 조건으로서 기능하는 바, 상기한 문제 상황을 구성하게 된다.
또한, 상기 문제 상황 특징 벡터(Context Feature Vector)는 상기 문제 상황의 데이터 중 가변적인 속성을 가지는 데이터들을 포함하여 구성되는 벡터로서, 아래에서 유사 상황 특징 벡터의 산정 및 다양한 상황 특징 벡터의 구성 등을 위하여 사용될 수 있다.
앞서 살핀 예에서 본다면, 하나의 반도체 라인에서, 각 작업의 선후 관계, 작업 소요 시간 및 대체 작업 등 시간별 자원 할당 계획의 관점에서 변동 가능성이 적은 항목들을 제외하고, 가변적인 속성을 가지는 과업의 숫자 또는 그에 따른 각 작업의 숫자, 장비의 종류와 숫자 등을 포함하여 상기 문제 상황 특징 벡터를 구성할 수 있다. 따라서, 시간별 스케줄링의 관점에서 변동 가능성이 큰 과업의 종류와 숫자 및 투입 장비의 종류와 숫자를 중심으로 하여, 2개의 J1 및 3개의 J2, R1 1대, R2 2대, R3 3대를 포함하는 (2J1, 3J2, 1R1 2R2, 3R3)가 문제 상황 특징 벡터가 될 수 있다.
그러나, 여기서 가변적인 속성이란 스케줄링의 계획 주기 및 기간의 정의에 따라 상대적인 것으로서, 스케줄링이 매 시간이 아니고 매 주 수행된다면, 작업 소요 시간과 같이 시간별 스케줄링에서는 변하지 않는 것으로 가정된 상황 특징도 주별 스케줄링에서는 가변적인 것으로 취급되어 문제 상황 특징 벡터에 포함될 수도 있다.
또한, 상기 계획 데이터베이스(610)는 복수의 상황 특징 벡터 및 그에 대한 계획 및 계획의 성능치를 포함하여 구성될 수도 있는데, 여기서 상기 상황 특징 벡터라 함은 상기 문제 상황 특징 벡터의 과거 데이터들을 적절하게 변동시키면서 생성된 다양한 가상 상황에 대한 벡터를 말한다.
이에 대하여 쉽게 설명하기 위하여, 다시 앞의 예로 돌아가, 상기 문제 상황 특징 벡터를 기준으로 각 항목의 값들을 적절하게 변동시키는 방식을 설명한다. 이에 따라 장비 R1이 1대, 2대, 4대인 경우 및 R2가 2대, 3대, 4대인 경우, J1을 1개, 2개, 5개인 경우, J2가 2대, 3대, 6대인 경우 등이 만들어 질 수 있고, 이를 각각 조합하면, 예컨대 상기 문제 상황 특징 벡터에서 J1이 감소된 (1J1, 3J2, 1R1 2R2, 3R3) 경우와 같은 다양한 상황 특징 벡터를 구성할 수 있게 된다. 또한 각 상황 특징 벡터 및 그에 대한 계획 및 계획의 성능치를 상기 자원 할당 계획생성기를 통하여 구한 후, 상기 계획 데이터베이스(610)에 저장하고 관리하게 된다.
또한, 상기 유사 상황 특징 벡터라 함은 상기 스케줄 데이터베이스(610)에 저장되어 있는 복수의 상황 특징 벡터 중에서 상기 문제 상황 특징 벡터와 가장 유사한 상황 특징 벡터 또는 상기 문제 상황 특징 벡터의 요구 사항에 맞도록 상기 계획 수정기(630)를 이용하여 수정하였을 경우, 성능의 차이가 가장 근소할 것으로 예측되는 상황 특징 벡터를 말한다.
다시 앞의 예에서, 문제 상황 특징 벡터가 변경되어 R1이 1대, R2가 2대, R3가 3대 있고, J1는 1개 생산하게 되는데 반하여, J2은 5개를 생산하여야 하는 상황을 고려할 경우, 이에 가장 유사한 상황 특징 벡터를 상기 계획 데이터베이스(610)에서 검색해 보면 (1J1, 6J2, 1R1 2R2, 3R3)가 될 수 있고 따라서 이 값이 유사 상황 특징 벡터가 될 수 있다.
이렇게 검출된 유사 상황 특징 벡터 및 그에 대한 계획은 상기 문제 상황 특징 벡터와 상기 유사 상황 특징 벡터의 차이를 고려하여, 상기 계획 데이터베이스(610) 내에 상기 유사 상황 특징 벡터에 대해 저장된 계획을 계획 수정기(630)로 수정함으로써 상기 문제 상황에 대한 자원 할당 계획으로서 사용될 수 있다.
또한 여기서 상기 저장된 계획이라 함은, 주어진 상황에 대하여 별도의 계획 생성기(220)를 사용하여 도출한 계획을 말하며, 상기 저장된 계획을 아래에서 살필 계획 수정기(630)를 사용하여 수정함으로써, 통상 상기 저장된 계획과 매우 근사하거나 더 높은 성능값을 가진 계획을 도출할 수 있다.
도 1은 본 발명의 일 실시예에 따른 계획 검색 및 수정 기법을 이용한 자원 할당 계획 방법의 순서도를 도시하고 있다. 도 1에서 볼 수 있듯이, 본 발명의 일 실시예에 따른 계획 검색 및 수정 기법을 이용한 자원 할당 계획 방법은 계획 데이터베이스(610) 생성 단계(S110), 유사 상황 특징 벡터 추천기(620) 생성 단계(S120), 문제 상황을 입력 받는 단계(S130), 문제 상황 특징 벡터를 산정하는 단계(S140), 유사 상황 특징 벡터를 검출하는 단계(S150), 상기 유사 상황 특징 벡터에 대한 계획을 수정하여 상기 문제 상황에 대한 계획을 도출하는 단계(S160)를 포함하여 구성될 수 있다.
먼저 상기 계획 데이터베이스(610)를 생성하는 단계(S110)에 대하여 살핀다. 계획 데이터베이스(610)를 생성함에 있어서는, 우선 적절한 문제 상황을 선정하는 것이 중요하다. 실제 상황에서 발생할 개연성이 큰 문제 상황을 중심으로 계획 데이터베이스(610)를 생성함으로써, 데이터베이스의 양을 줄여 계산 시간을 단축시킴과 동시에, 보다 성능이 높은 계획을 도출해 낼 수 있게 된다.
문제 상황을 적절하게 선정하기 위한 한 방편으로, 기존에 당해 문제에 대해 존재하였던 다양한 문제 상황에 대한 데이터를 수집하여 사용하는 방법을 들 수 있다. 이러한 문제 상황이 너무 많을 경우 상기 문제 상황의 데이터를 소정의 규칙을 적용하여, 문제 상황의 대표치를 사용하거나 문제 상황의 데이터를 클러스터링(clustering)하여 사용함으로써 상기 계획 데이터베이스(610)의 양을 조절하고 계산 시간을 단축시킬 수 있다. 상기의 예로서 복수의 문제 상황 데이터에 대한 중간값(median)을 사용하는 방법, 문제 상황의 발생 빈도를 기준으로 문제 상황을 추리는 방법 등을 들 수 있다.
또한, 상기 문제 상황을 선정함에 있어, 기존에 당해 문제에서 존재하였던 상황에 대한 문제 상황과 별도로, 향후 문제 상황이 중대하게 변경될 것으로 예상되는 경우에 대한 문제 상황을 포함하여 계획 데이터베이스(610)를 미리 생성하는 방법도 가능하다.
상기 문제 상황이 주어지면, 그에 대하여 문제 상황 특징 벡터를 산정하고, 그 값들을 조금씩 변경해 가면서 복수의 상황 특징 벡터를 구성한 후, 이에 대한 계획들을 종래의 계획 생성기(220)를 사용하여 도출한다. 상기 문제 상황 특징 벡터는 상기 문제 상황의 항목 중 변동이 가능한 항목들을 포함하여 구성될 수 있으며, 또한 이는 앞서 살핀 경우와 유사하게 기존의 문제에서 존재하였던 다양한 상황을 바탕으로 그 변동 가능성 및 변동치를 산정하는 것이 바람직하다. 상기 종래의 계획 생성기(220)는 적절한 계획이 도출될 수 있는 것이라면 최적해의 생성이 보장된 것이 아니더라도 그 종류에 무관하게 특별히 제약 없이 사용할 수 있다.
이때, 상기 문제 상황 특징 벡터는 해당 자원 할당 문제를 정의하는 데에 필요한 모든 데이터를 대상으로 하는 바, 가용 자원의 유형, 가용 자원의 유형별 개수, 활동의 유형, 활동의 유형별 개수, 각 활동 유형에서 세부 활동 간의 선후 관계, 대체 자원, 대체 경로, 활동간 우선 순위, 활동별 완료 요구일, 자원의 설정 변경시의 제약, 자원의 설정 상태, 활동 및 세부 활동과 관련된 비용 및 시간 정보, 계산된 계획 정보, 계획 성능치, 목적함수 등의 데이터 중에서 하나 이상을 포함하여 구성될 수 있다.
또한, 문제 상황이 주어지고, 그에 대한 문제 상황 특징 벡터를 산정한 후, 상기 계획 데이터베이스(610)에서 유사 상황 특징 벡터를 검출하는 경우, 유사 상황 특징 벡터에 대한 계획을 상기 계획 수정기(630)를 통하여 수정하였을 때의 계획 성능치가, 상기 문제 상황 특징 벡터를 입력으로 계획 생성기(220)를 수행한다고 가정했을 때에 예상되는 계획 성능치에 가장 근접하는 유사 상황 특징 벡터를 검출하는 것이 적절하므로, 상기 계획 데이터베이스(610)에는 또한 상기 상황 특징 벡터에 따른 계획과 함께 그에 대한 계획 성능치도 함께 포함되는 것이 바람직하다.
이때, 상기 계획 성능치라 함은 자원 할당 계획 문제의 목적 함수에 대한 성능 수치를 말하며, 예를 들어 자원 할당 계획 문제의 목적 함수로서 장비 가동률 최대화를 설정하였다면 상기 장비 가동률이 계획 성능치가 되고, 자원 할당 계획 문제의 목적 함수로서 생산 소요 시간 최소화를 스케줄링 목적 함수로 잡았다면 상기 생산 소요 시간 수치가 계획 성능치가 된다.
도 2는 본 발명의 일 실시예에 따른 계획 데이터베이스(610) 생성시의 데이터 흐름을 보여주고 있다. 도 2에서 볼 수 있듯이, 문제 상황 생성기(210)에서 적절하게 선택된 문제 상황이 도출되고, 그에 대한 문제 상황 특징 벡터가 선정되면, 이 값들은 계획 생성기(220)로 전달되어 그에 대한 계획 및 계획 성능치가 도출되게 된다. 또한, 상기 문제 상황 특징 벡터에 대하여 앞서 살핀 바와 같이 기존의 해당 문제에서 존재하였던 다양한 상황을 바탕으로 그 변동 가능성 및 변동치를 고려하여 그 값들을 조금씩 변경해 가면서 복수의 상황 특징 벡터를 구성한 후, 이에 대한 계획 및 계획 성능치들도 도출할 수 있으므로, 이를 포함하여 상기 계획 데이터베이스(610)을 구성할 수 있다.
상기한 일련의 과정을 통하여 상기 계획 데이터베이스(610)는 상기 상황 특징 벡터 및 그에 대한 계획을 포함하여 구성될 수 있고, 또한 상기 상황 특징 벡터에 포함된 항목 이외에 상기 문제 상황에 포함된 항목도 변동 가능성이 전혀 없다고 볼 수는 없으므로, 상기 계획 데이터베이스(610)에는 상기 문제 상황도 포함하여 구성하는 것이 바람직하다.
덧붙여, 상기한 바와 같이 계획 데이터베이스(610)를 생성하여 이를 사용하는 것도 가능하나, 반드시 자원 할당 계획 담당자가 상기 계획 데이터베이스(610)를 직접 생성하여야 하는 것은 아니다. 상기 계획 데이터베이스(610)는 별개로 제작되어 담당자에게 양도되거나 경우에 따라서는 소정의 표준품으로서 제작된 후 환경에 맞게 일부 수정되어 사용되는 것도 가능할 수 있다.
또한, 상기한 일련의 과정을 통하여 계획 데이터베이스(610)를 구성한 다음에는, 상기의 상황 특징 벡터에 대하여 그 파생값들을 산출하고 그에 대한 계획을 생성하여 이를 상기 계획 데이터베이스(610)에 포함시킴으로써, 상기 계획 데이터베이스(610)를 보다 세밀하게 구성하는 것도 가능하다.
상기와 같이 상황 특징 벡터가 만들어지면, 이에 대한 파생 상황 특징 벡터를 산출하기 위하여 상황 특징 벡터 파생기(perturbator)(310)를 사용하는 것도 가능하다. 상기 파생 상황 특징 벡터를 생성함에 있어서는, 계획 수정기(630)를 통하여 계획을 산정할 때에 최소한의 수정으로 좋은 계획을 산출할 수 있도록 고려하여 생성하는 것이 바람직하다. 예를 들자면, 생산 공정의 경우에는 생산요구량 기준치를 약간 상회하는 계획을 미리 생성하여 두고, 이를 줄이는 방향으로 계획을 수정하도록 하는 것이 최소한의 수정으로 기존 계획에 대한 변동을 최소화하면서 적절한 계획을 산정해 내는 데에 유리할 수 있다. 이러한 경우 상기 상황 특징 벡터 파생기(310)는 파생 상황 특징 벡터를 산출함에 있어 기준치를 약간 상회하는 생산 계획을 도출하는 방식으로 동작하는 것이 바람직하다.
이렇게 산출된 파생 상황 특징 벡터에 대한 계획을 생성하여 상기 계획 데이터베이스(610)에 포함시킬 수 있는데, 이때 종래의 별도로 준비된 계획 생성기(220)를 사용할 수도 있으나, 이 경우 그 계획 생성 시간이 너무 길어질 수 있으므로, 아래에서 살펴볼 계획 수정기(630)를 사용하여 상기 파생 상황 특징 벡터에 대한 계획을 산출하는 것도 가능하다.
도 3은 본 발명의 일 실시예에 따른 파생 상황 특징 벡터를 포함하는 계획 데이터베이스(610) 생성시의 데이터 흐름을 도시하고 있다. 도 3에서 볼 수 있듯이, 상황 특징 벡터가 상황 특징 벡터 파생기(310)에 전달되면, 그에 대한 파생 상황 특징 벡터가 도출되게 되고, 이는 상기 상황 특징 벡터에 대한 계획과 함께 계획 수정기(630)에 전달되어 상기 파생 상황 특징 벡터에 대한 계획과 계획 성능치를 도출해 내게 된다.
다음으로, 유사 상황 특징 벡터 추천기(620) 생성 단계(S120)에 대하여 살핀다. 여기서 유사 상황 특징 벡터 추천기(620)는, 문제 상황에 따르는 문제 상황 특징 벡터에 맞도록 계획 데이터베이스(610)에 있는 유사 상황 특징 벡터의 계획을 계획 수정기(630)를 통하여 수정하였을 때의 계획 성능치가, 상기 문제 상황 특징 벡터를 입력으로 계획 생성기(220)를 수행한다고 가정했을 때에 예상되는 계획 성능치에 가장 근접하는 유사 상황 특징 벡터를 상기 계획 데이터베이스(610)로부터 검출하는 역할을 하게 된다.
상기 유사 상황 특징 벡터 추천기(620)는 써포트 벡터 기계(support vector machine) 또는 k-NN(k-Nearest Neighbor)와 같은 종래의 알려진 기계 학습 기법으로 구현이 가능하며, 구체적으로 상기 유사 상황 특징 벡터 추천기(620)는 상황 특징 벡터와 파생 상황 특징 벡터 쌍을 독립 변수로, 그에 따르는 각 계획의 성능치 값을 종속 변수로 하여, 이들을 학습 데이터로 사용하여 생성될 수 있다. 또한, 앞서 살핀 바와 같이 상황 특징 벡터 및 그에 대한 파생 상황 특징 벡터는 상황 특징 벡터 파생기(310)를 사용하여 산출할 수 있고, 그에 대한 각 계획의 성능치는, 상황 특징 벡터의 경우는 종래의 계획 생성기(220)로, 파생 상황 특징 벡터의 경우는 계획 수정기(630)를 사용하여 도출할 수 있으므로, 이들을 상기 학습 데이터로 사용하여 상기 유사 상황 특징 벡터 추천기(620)를 생성하는 것이 가능하다.
도 4는 본 발명의 일 실시예에 따른 유사 상황 특징 벡터 추천기(620) 생성시의 데이터 흐름을 도시하고 있다. 도 4에서 볼 수 있는 바와 같이, 상황 특징 벡터와 파생 상황 특징 벡터 쌍을 독립 변수로, 그에 따르는 각 계획 성능치 값을 종속 변수로 하여, 이들에 대하여 기계 학습 기법을 적용함으로써 상기 유사 상황 특징 벡터 추천기(620)를 생성할 수 있게 된다.
이어서, 문제 상황을 입력 받는 단계(S130)와 문제 상황 특징 벡터를 산정하는 단계(S140)에 대하여 살핀다. 본 발명의 일 실시예에 따라 자원 할당 계획 이용자로부터 문제 상황을 입력받은 후, 상기 문제 상황으로부터 가변적인 속성을 가지는 항목들을 중심으로 문제 상황의 특성을 고려하여 문제 상황 특징 벡터를 산정한다.
이때, 상기 문제 상황 특징 벡터는 해당 자원 할당 문제를 정의하는 데에 필요한 모든 데이터를 대상으로 하는 바, 가용 자원의 유형, 가용 자원의 유형별 개수, 활동의 유형, 활동의 유형별 개수, 각 활동 유형에서 세부 활동 간의 선후 관계, 대체 자원, 대체 경로, 활동간 우선 순위, 활동별 완료 요구일, 자원의 설정 변경시의 제약, 자원의 설정 상태, 활동 및 세부 활동과 관련된 비용 및 시간 정보, 계산된 계획 정보, 계획 성능치, 목적 함수 등의 데이터 중에서 하나 이상을 포함하여 구성될 수 있다.
특히, 상기 문제 상황 특징 벡터의 항목 중 자원의 설정 상태에 대하여 살핀다면, 각 자원들은 적절한 동작을 위하여 일정한 설정 작업이 필요한 경우가 있는데, 이에 따라 이를 설정하고 동작시키기 위하여 일정한 시간이 소요될 수 있다. 따라서, 상기한 자원의 설정 상태에 따라서는 특정 세부 활동에 투입되기 전에 설정 작업이 선행되어야 하는 경우의 시간 지연을 고려하여 자원 할당 작업이 이루어져야 한다. 이와 유사하게 상기 자원의 설정 변경시의 제약의 경우에도, 특정한 자원에 따라서는 특정한 설정 작업에 인위적인 혹은 기계적인 제한이 가해질 수 있으므로 자원 할당 계획 작업에 있어 이를 고려해야 하는 경우가 생길 수 있다.
다음으로, 유사 상황 특징 벡터를 검출하는 단계(S150)에서는 상기 문제 상황 특징 벡터에 대한 계획 생성을 위해서, 계획 수정기(630)의 입력으로 사용할 계획에 대한 유사 상황 특징 벡터의 검출을 목표로 하는 바, 계획 데이터베이스(610)에 있는 상황 특징 벡터의 계획을 계획 수정기(630)를 통하여 수정하였을 때의 계획 성능치가, 상기 문제 상황 특징 벡터를 입력으로 자원 할당 계획 생성기(220)를 수행한다고 가정했을 때에 예상되는 계획 성능치에 가장 근접하는 유사 상황 특징 벡터를 상기 스케줄 데이터베이스(610)에서 검출하게 된다. 이때 앞서 살핀 유사 성능 특징 벡터 추천기(620)를 사용하여 상기 유사 성능 특징 벡터를 산출하는 것도 가능하다.
경우에 따라서는, 상기 계획 데이터베이스(610)에 포함되어 있는 상황 특징 벡터 중 일부분에 대해서만 검색하여 상기 유사 상황 특징 벡터를 검출하게 할 수도 있다. 예를 들어, 계획 데이터베이스(610)의 용량이 너무 커서 데이터베이스의 모든 영역을 검색하는 것이 비효율적인 경우, 또는 수정 작업을 고려할 때, 문제 상황 특징 벡터를 기준으로 특정 항목이 더 크거나 작은 경우만을 대상으로 검색하는 것이 적절한 경우 등을 들 수 있다. 구체적인 예를 든다면, 소정의 물품 생산 공정에 있어서, 목적 함수가 가동율의 최대화일 경우, 100개의 과업에 대한 생산 스케줄을 도출하고자 할 때에는 101개의 과업에 대한 스케줄에서 1개를 덜 생산하는 방향으로 스케줄을 수정하는 방향이 보다 쉬울 수 있고, 목적 함수가 납기 준수일 경우, 기계 100대를 사용하는 생산 스케줄을 도출하고자 할 때에는 기계 99대에 대한 생산 스케줄에서 1대의 기계를 추가하는 방향으로 스케줄을 수정하는 것이 바람직하다. 이러한 경우 상기 계획 데이터베이스(610)에 대한 사전 필터링 작업을 통하여 상기 검색 작업의 범위를 한정할 수 있다. 또한, 상기 계획 데이터베이스(610) 중에서 파생 상황 특징 벡터를 제외하고, 상황 특징 벡터만을 검색 범위로 한정하는 것도 가능하다.
덧붙여, 상기 유사 상황 특징 벡터를 검출함에 있어, 소정의 방법으로 산정한 오류 가능성이 특정한 임계치를 넘는 경우, 앞서 살핀 일련의 방법을 사용하지 않고, 기존의 계획 생성기(220)를 사용하여 상기 문제 상황에 대한 계획을 직접 산출하는 방식으로 오류 발생을 방지하는 것도 가능하다.
마지막으로, 상기 유사 상황 특징 벡터에 대한 계획을 수정하여 상기 문제 상황에 대한 계획을 도출하는 단계(S160)에서는 상기 유사 상황 특징 벡터 및 그에 대한 계획과 함께 상기 문제 상황 특징 벡터를 고려하여, 상기 유사 성능 특징 벡터에 대한 기존 계획을 수정함으로써 상기 문제 상황에 대한 계획을 도출하게 된다. 이때, 상기 유사 성능 특징 벡터에 대한 계획을 수정함에 있어서는 계획 수정기(630)를 사용하는 것도 가능하다.
상기 계획 수정기(630)는 계획의 수정에 따른 기존 계획으로부터의 계획 성능치 차이를 최소화 하거나 수정된 계획 성능을 최대화하는 방식에 따라 계획을 수정하게 된다.
또한, 앞서 살핀 유사 상황 특징 벡터 추천기(620)의 경우와 유사하게, 복수의 상황 특징 벡터에 대해서 기존의 계획 생성기(220)를 활용하여 생성된 계획들을 학습 데이터로 이용함으로써, 임의의 문제 상황 특징 벡터가 주어졌을 때, 계획 수정기(630)의 수정 결과가 기존의 계획 생성기(220)가 생성한 계획과 유사하도록, 온라인 학습(on-line learning), 써포트 벡터 기계(support vector machine), 강화학습 (reinforcement learning) 등의 기계 학습을 적용하여 상기 계획 수정기(630)를 구성하는 것도 가능하다. 덧붙여, 상기 계획 수정기(630)가 수정된 계획에 더하여 그에 대한 계획 성능치를 함께 산출하도록 하는 것도 가능하다.
또한, 상기 계획의 수정 작업에 있어서, 입력으로 사용하는 계획의 정보 중에서 전체가 아닌 일부만을 고려하여 계획 수정 작업을 진행하도록 구성할 수도 있다. 예를 들어, 스케줄링 문제의 경우 작업 시간은 고려하지 않고 작업 순서만을 고려하여 스케줄 수정 작업을 진행하도록 구성할 수 있다. 이러한 경우, 상기 계획 데이터베이스(610)는 상기 계획 정보 중 작업 순서 정보만을 포함하는 것도 가능하다.
덧붙여, 앞서 살핀 계획 수정기(630)를 사용하여 임의의 상황 특정 벡터로부터 도출된 파생 상황 특징 벡터에 대한 계획을 산정하는 경우, 상기 계획 데이터베이스(610)에 상기 계획 수정기(630)에 의한 계획 수정 횟수도 함께 기록하여 두었다가, 상기 계획 수정기(630)에 의한 계획 수정 작업시에 상기 계획 수정 횟수를 참고하여 유사 상황 특징 벡터를 검출하는 것도 가능하다.
도 5는 본 발명의 일 실시예에 따른 문제 상황에 대한 계획 산출시의 데이터 흐름을 개괄적으로 도시하고 있다. 도 5에서 볼 수 있는 바와 같이, 문제 상황에 따르는 문제 상황 특징 벡터가 유사 상황 특징 벡터 추천기(620)에 전달되면, 상기 유사 상황 특징 벡터 추천기(620)는 상기 계획 데이터베이스(610)를 검색하여, 수정 생성기(630)를 사용한 계획 수정 작업 후의 성능치가, 상기 문제 상황 특징 벡터를 입력으로 상기 계획 생성기를 이용하여 자원 할당 계획을 직접 생성한다고 가정했을 때에 도출되는 계획의 성능치와 가장 근접할 것으로 예측되는 계획과 그에 해당하는 유사 상황 특징 벡터를 검출하고, 이들은 다시 계획 수정기(630)에 전달되며, 상기 계획 수정기(630)는 이들과 함께 상기 문제 상황 특징 벡터를 고려하여 문제 상황에 대한 계획을 산출해 내게 된다.
도 6은 본 발명의 일 실시예에 따른 계획 검색 및 수정 기법을 이용한 자원 할당 계획 시스템(600)의 블록도를 도시하고 있다. 상기 도 6에서 알 수 있듯이, 본 발명의 일 실시예에 따른 스케줄 검색 및 수정 기법을 이용한 계획 시스템(600)은 계획 데이터베이스(610), 유사 상황 특징 벡터 추천기(620) 및 계획 수정기(630)를 포함하여 구성될 수 있다.
먼저 본 발명의 일 실시예에 따른 상기 계획 데이터베이스(610)는 앞서 살핀 바와 갈이, 적절하게 선정된 문제 상황에 대한 문제 상황 특징 벡터를 산정하고 그 구성 항목의 값들을 조금씩 변경해 가면서 계획 생성기(220)를 이용하여 생성된 상황 특징 벡터에 대한 각 계획 및 계획의 성능치를 포함하게 된다. 또한 이에 더하여, 상기 상황 특징 벡터로부터 만들어진 파생 상황 특징 벡터 및 그에 대한 계획 및 계획의 성능치도 함께 포함하여 관리할 수 있다.
다음으로, 유사 상황 특징 벡터 추천기(620)도 앞서 살핀 바와 같이, 주어진 문제 상황에 따르는 문제 상황 특징 벡터에 대하여 계획 생성기(220)를 직접 사용하여 생성할 경우의 계획의 성능치와 가장 근접한 성능치를, 계획 수정기(630)를 통하여 산출할 수 있을 것으로 예측되는 계획을 가진 유사 상황 특징 벡터를 상기 계획 데이터베이스(610)에서 검출하거나, 계획 수정기(630)를 통하여 가장 높은 성능치를 가지는 계획을 산출할 수 있을 것으로 예측되는 계획을 가진 유사 상황 특징 벡터를 상기 계획 데이터베이스(610)에서 검출해 내게 된다.
이어서, 상기 계획 수정기(630)도 앞서 살핀 바와 마찬가지로, 상기 유사 상황 특징 벡터에 대한 계획을 수정하여 상기 문제 상황에 대한 계획을 도출해 내게 된다.
이상의 설명은 본 발명의 기술 사상을 예시적으로 설명한 것에 불과한 것으로서, 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자라면 본 발명의 본질적인 특성에서 벗어나지 않는 범위에서 다양한 수정 및 변형이 가능할 것이다. 따라서 본 발명에 기재된 실시예들은 본 발명의 기술 사상을 한정하기 위한 것이 아니라 설명하기 위한 것이고, 이러한 실시예에 한정되는 것은 아니다. 본 발명의 보호 범위는 아래의 청구범위에 의해서 해석되어야 하며, 그와 동등한 범위 내에 있는 모든 기술 사상은 본 발명의 권리범위에 포함되는 것으로 해석되어야 할 것이다.
210 : 문제 상황 생성기
220 : 계획 생성기
310 : 상황 특징 벡터 파생기
600 : 계획 검색 및 수정 기법을 이용한 자원 할당 계획 시스템
610 : 계획 데이터베이스
620 : 유사 상황 특징 벡터 추천기
630 : 계획 수정기

Claims (31)

  1. (a) 주어진 문제 상황에 대해 문제 상황 특징 벡터를 생성하는 단계;
    (b) 계획 데이터베이스를 검색하여,
    상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대해 기 생성 해놓은 계획을 검출하는 단계; 및
    (c) 상기 유사 상황 특징 벡터에 대해 기생성해 놓은 계획을 수정하여 상기 문제 상황에 대한 해로서 계획을 산출하는 단계를 포함하며,
    상기 계획 데이터베이스에는 복수의 상황 특징 벡터와 그에 대해 기생성된 계획들이 저장되어 관리되는 것을 특징으로 하는 자원 할당 계획 방법.
  2. 제1항에 있어서,
    상기 (a) 단계에 앞서,
    (p) 복수의 상황 특징 벡터에 대한 계획을 미리 생성해서 저장해놓기 위해서, 다양한 상황 특징 벡터를 입력으로 받아 별도의 계획 생성기(planner)를 사용하여 계획을 생성함으로써,
    상기 계획 데이터베이스를 생성하는 단계를 더 포함하는 것을 특징으로 하는 자원 할당 계획 방법.
  3. 제2항에 있어서,
    상기 (p) 단계에서,
    상기 계획 데이터베이스를 생성함에 있어,
    문제 상황이 복수로 존재하는 경우 상기 복수의 문제 상황을 대표할 수 있는 대표치를 사용하거나 상기 복수의 문제 상황의 데이터를 클러스터링(clustering)하여 사용함으로써 상기 계획 데이터베이스의 용량을 줄이는 것을 특징으로 하는 자원 할당 계획 방법.
  4. 제2항에 있어서,
    상기 (p) 단계에서,
    기존에 존재하였던 문제 상황으로부터 미리 정해진 기준 이상으로 변경되는 문제 상황을 포함하여 계획 데이터베이스를 미리 생성하는 것을 특징으로 하는 자원 할당 계획 방법.
  5. 제1항에 있어서,
    상기 (b) 단계는,
    유사 상황 특징 벡터 추천기를 사용하여,
    상기 계획 데이터베이스에 저장되어 있는 상황 특징 벡터들에 대한 계획 중에서,
    상기 계획이 계획 수정기를 거쳐 산출되는 수정된 계획과,
    상기 문제 상황 특징 벡터가 계획 생성기를 거쳐 산출되는 계획을 비교할 때,
    주어진 항목에 대한 성능치의 차이가 가장 적을 것으로 예측되는 유사 상황 특징 벡터들과 그들에 대한 계획들을 검출하는 단계이며,
    이때 상기 계획 데이터베이스에는 상기 상황 특징 벡터에 대한 계획의 성능치도 저장되어 관리되는 것을 특징으로 하는 자원 할당 계획 방법.
  6. 제5항에 있어서,
    상기 (b) 단계는,
    유사 상황 특징 벡터 추천기를 사용하여,
    상기 계획 데이터베이스에서 상기 문제 상황 특징 벡터와 가장 유사한 한개 이상의 상황 특징 벡터를 검출하는 단계인 것을 특징으로 하는 자원 할당 계획 방법.
  7. 제6항에 있어서,
    상기 (b) 단계에 앞서,
    (q) 복수의 상황 특징 벡터 및 그에 대한 계획에 대하여,
    기계 학습(machine learning) 기법을 적용하여 상기 유사 상황 특징 벡터 추천기를 생성하는 단계를 더 포함하는 것을 특징으로 하는 자원 할당 계획 방법.
  8. 제7항에 있어서
    상기 기계 학습 기법은 써포트 벡터 기계(support vector machine) 또는 k-NN(k-Nearest Neighbor) 기법을 포함하는 것을 특징으로 하는 자원 할당 계획 방법.
  9. 제1항에 있어서,
    상기 (b) 단계는,
    상기 계획 데이터베이스 중 일부 상황 특징 벡터만을 검색하여 상기 유사 상황 특징 벡터를 검출하도록,
    사전에 상기 계획 데이터베이스의 상황 특징 벡터를 필터링하는 단계를 포함하는 것을 특징으로 하는 자원 할당 계획 방법.
  10. 제1항에 있어서,
    상기 계획 데이터베이스에는 복수의 상황 특징 벡터와 그에 대해 상기 계획 생성기를 이용하여 미리 생성한 계획의 전부 또는 계획의 주요 일부 정보가 저장되어 관리되고,
    상기 (b) 단계에서는,
    계획 데이터베이스의 상황 특징 벡터를 검색하여,
    상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대한 계획의 전부 또는 일부 정보를 유사 상황 특징 벡터 추천기로부터 추천받고,
    상기 (c) 단계에서는,
    상기 유사 상황 특징 벡터에 대한 계획의 전부 또는 일부 정보를 수정하여 상기 문제 상황에서의 계획을 생성하는 것을 특징으로 하는 자원 할당 계획 방법.
  11. 제1항에 있어서,
    상기 (b) 단계는,
    계획 데이터베이스의 상황 특징 벡터 및 파생 상황 특징 벡터를 검색하여,
    상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대한 계획을 유사 상황 특징 벡터 추천기를 이용하여 검출하는 단계이며,
    상기 계획 데이터베이스에는 복수의 상황 특징 벡터 및 그에 대한 계획에 더하여,
    복수의 파생 상황 특징 벡터 및 그에 대한 계획이 함께 저장되어 관리되는 것을 특징으로 하는 자원 할당 계획 방법.
  12. 제1항에 있어서,
    상기 (c) 단계는,
    계획 수정기(repairer)를 사용하여,
    상기 유사 상황 특징 벡터 및 그에 대해 계획 생성기를 이용하여 미리 생성한 계획 및 상기 문제 상황 특징 벡터를 입력으로 하여,
    상기 문제 상황 특징 벡터에 대한 계획을 산출하는 단계인 것을 특징으로 하는 자원 할당 계획 방법.
  13. 제12항에 있어서,
    상기 계획 수정기는,
    유사 상황 특징 벡터 추천기가 한개 이상의 유사 상황 특징 벡터를 추천하는 경우,
    각 유사 상황 특징 벡터에 따르는 계획을 수정하여 그 중 계획 성능치가 가장 좋은 계획을 산출하는 것을 특징으로 하는 자원 할당 계획 방법.
  14. 제13항에 있어서,
    상기 계획 수정기는,
    상기 유사 상황 특징 벡터에 대해 미리 생성된 계획을 상기 문제 상황 특징 벡터에 적합하도록 수정한 계획과 상기 문제 상황 특징 벡터를 입력으로 상기 계획 생성기를 이용하여 자원 할당 계획을 직접 생성한다고 가정했을 때에 도출되는 계획과의 성능 차이를 최소화 할 수 있는 방식에 따라 계획을 수정하는 것이거나,
    상기 문제 상황 특징 벡터에 대해 최적의 성능이 달성될 수 있도록 상기 유사 상황 특징 벡터에 대해 미리 생성된 계획을 수정하는 것을 특징으로 하는 자원 할당 계획 방법.
  15. 제13항에 있어서,
    상기 계획 수정기는,
    복수의 상황 특징 벡터에 대해서 기존의 계획 생성기를 활용하여 생성된 계획들을 학습 데이터로 이용함으로써,
    상기 계획 수정기의 상기 기존의 계획 생성기를 모사하도록,
    기계 학습을 적용하여 생성된 것임을 특징으로 하는 자원 할당 계획 방법.
  16. 제15항에 있어서,
    상기 기계 학습 기법은 온라인 학습(on-line learning), 써포트 벡터 기계(support vector machine), 강화학습 (reinforcement learning) 기법을 포함하는 것을 특징으로 하는 자원 할당 계획 방법.
  17. 제15항에 있어서,
    상기 복수의 파생 상황 특징 벡터에 대한 계획을 생성함에 있어 계획 수정기를 사용하는 경우,
    상기 계획 데이터베이스에는 상기 계획 수정기가 상기 유사 상황 특징 벡터의 계획을 수정할 때에 소요된 계획 수정 횟수도 함께 기록되어 관리되고,
    추후 상기 계획 수정 횟수 정보를 상기 계획 수정기에 의한 계획 수정 작업시에 이용하는 것을 특징으로 하는 자원 할당 계획 방법.
  18. 제1항에 있어서,
    상기 문제 상황 특징 벡터는,
    가용 자원의 유형, 가용 자원의 유형별 개수, 활동의 유형, 활동의 유형별 개수, 각 활동 유형에서 세부 활동간의 선후 관계, 대체 자원, 대체 경로, 활동간 우선 순위, 활동별 완료 요구일, 자원의 설정 변경시의 제약, 자원의 설정 상태, 활동 및 세부 활동과 관련된 비용 및 시간 정보, 계산된 계획 정보, 계획 성능치, 목적함수 중 하나 이상을 포함하는 것을 특징으로 하는 자원 할당 계획 방법.
  19. 제6항에 있어서,
    상기 유사 상황 특징 벡터 추천기가 유사 상황 특징 벡터를 검출함에 있어,
    상기 검출되는 유사 상황 특징 벡터의 오류 가능성이 특정한 임계치를 넘는 경우,
    계획 수정기를 이용하지 않고 별도의 계획 생성기를 사용하여 직접 상기 문제 상황에 대한 계획을 산출하는 것을 특징으로 하는 자원 할당 계획 방법.
  20. 복수의 상황 특징 벡터 및 그에 대해 별도의 계획 생성기를 사용하여 생성된 계획과 계획 성능치를 저장하고 관리하는 계획 데이터베이스;
    주어진 문제 상황으로부터 문제 상황 특징 벡터를 생성한 후,
    상기 계획 데이터베이스를 검색하여 상기 문제 상황 특징 벡터와 가장 유사한 상황 특징 벡터를 검출하거나, 상기 계획 데이터베이스에 저장되어 있는 상황 특징 벡터들에 대한 계획 중에서, 상기 계획이 계획 수정기를 거쳐 산출되는 수정된 계획과, 상기 문제 상황 특징 벡터가 상기 계획 생성기를 거쳐 산출되는 계획을 비교할 때, 주어진 항목에 대한 성능치의 차이가 가장 적을 것으로 예측되는 유사 상황 특징 벡터와 그에 대한 기생성된 계획을 도출하는 유사 상황 특징 벡터 추천기; 및
    상기 하나 이상의 유사 상황 특징 벡터에 대한 계획을 수정하여 상기 주어진 문제 상황에 대한 해로서 계획을 산출하는 계획 수정기를 포함하는 것을 특징으로 하는 자원 할당 계획 시스템.
  21. 제20항에 있어서,
    상기 유사 상황 특징 벡터 추천기는,
    복수의 상황 특징 벡터 및 그에 대한 계획에 대하여,
    기계 학습(machine learning) 기법을 적용하여 생성된 것임을 특징으로 하는 자원 할당 계획 시스템.
  22. 제20항에 있어서,
    상기 계획 수정기는,
    상기 문제 상황 특징 벡터, 그에 대한 상기 유사 상황 특징 벡터 및 상기 유사 상황 특징 벡터에 대한 계획을 고려하여,
    상기 계획의 수정에 따른 수정된 계획과 상기 문제 상황 특징 벡터를 입력으로 상기 계획 생성기를 이용하여 자원 할당 계획을 직접 생성한다고 가정했을 때에 도출되는 계획과의 성능치의 차이를 최소화할 수 있는 방식에 따라 계획을 수정하는 것을 특징으로 하는 자원 할당 계획 시스템.
  23. 제22항에 있어서,
    상기 계획 수정기는,
    복수의 상황 특징 벡터에 대해서 기존의 계획 생성기를 활용하여 생성된 계획들을 학습 데이터로 이용함으로써,
    임의의 문제 상황 특징 벡터가 주어졌을 때,
    계획 수정기의 수정 결과가 기존의 계획 생성기가 생성한 계획을 모사하도록,
    기계 학습을 적용하여 생성된 것임을 특징으로 하는 자원 할당 계획 시스템.
  24. 제20항에 있어서,
    상기 계획 데이터베이스는,
    문제 상황이 복수로 존재하는 경우 상기 복수의 문제 상황을 대표할 수 있는 대표치를 사용하거나 상기 복수의 문제 상황의 데이터를 클러스터링(clustering)하여 사용함으로써 상기 계획 데이터베이스의 용량을 줄여 생성된 것임을 특징으로 하는 자원 할당 계획 시스템.
  25. 제20항에 있어서,
    상기 계획 데이터베이스는,
    기존에 존재하였던 문제 상황으로부터 미리 정해진 기준 이상으로 변경되는 문제 상황을 포함하여 미리 생성되는 것을 특징으로 하는 자원 할당 계획 시스템.
  26. 제20항에 있어서,
    상기 유사 상황 특징 벡터 추천기는,
    상기 계획 데이터베이스 중 일부 상황 특징 벡터만을 검색하여 상기 유사 상황 특징 벡터를 검출하도록,
    사전에 상기 계획 데이터베이스의 상황 특징 벡터를 필터링하는 것을 특징으로 하는 자원 할당 계획 시스템.
  27. 제20항에 있어서,
    상기 계획 데이터베이스에는 복수의 상황 특징 벡터와 그에 대해 상기 계획 생성기를 이용하여 미리 생성된 계획의 전부 또는 계획의 주요 일부 정보가 저장되어 관리되고,
    상기 유사 상황 특징 벡터 추천기는,
    계획 데이터베이스의 상황 특징 벡터를 검색하여,
    상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대한 계획의 전부 또는 일부 정보를 추출하며,
    상기 계획 수정기는,
    상기 유사 상황 특징 벡터에 대한 계획의 전부 또는 일부 정보를 수정하여 상기 문제 상황에서의 계획을 생성하는 것을 특징으로 하는 자원 할당 계획 시스템.
  28. 제20항에 있어서,
    상기 유사 상황 특징 벡터 추천기는,
    계획 데이터베이스의 상황 특징 벡터 및 파생 상황 특징 벡터를 검색하여,
    상기 문제 상황 특징 벡터에 대한 유사 상황 특징 벡터 및 그에 대한 계획을 검출하며,
    상기 계획 데이터베이스에는 복수의 상황 특징 벡터 및 그에 대한 계획에 더하여,
    복수의 파생 상황 특징 벡터 및 그에 대한 계획이 함께 저장되어 관리되는 것을 특징으로 하는 자원 할당 계획 시스템.
  29. 제28항에 있어서,
    상기 복수의 파생 상황 특징 벡터에 대한 계획을 생성함에 있어 계획 수정기를 사용하는 경우,
    상기 계획 데이터베이스에는 상기 계획 수정기가 상기 유사 상황 특징 벡터의 계획을 수정할 때에 소요된 계획 수정 횟수도 함께 기록되어 관리하고,
    추후 상기 계획 수정 횟수 정보를 상기 계획 수정기에 의한 계획 수정 작업시에 이용하는 것을 특징으로 하는 자원 할당 계획 시스템.
  30. 제20항에 있어서,
    상기 문제 상황 특징 벡터는,
    가용 자원의 유형, 가용 자원의 유형별 개수, 활동의 유형, 활동의 유형별 개수, 각 활동 유형에서 세부 활동 간의 선후 관계, 대체 자원, 대체 경로, 활동간 우선 순위, 활동별 완료 요구일, 자원의 설정 변경시의 제약, 자원의 설정 상태, 활동 및 세부 활동과 관련된 비용 및 시간 정보, 계산된 계획 정보, 계획 성능치, 목적함수 중 하나 이상을 포함하는 것을 특징으로 하는 자원 할당 계획 시스템.
  31. 제20항에 있어서,
    상기의 유사 상황 특징 벡터 추천기가 유사 상황 특징 벡터를 검출함에 있어,
    상기 검출되는 유사 상황 특징 벡터의 오류 가능성이 특정한 임계치를 넘는 경우,
    계획 수정기를 사용하지 않고 별도의 계획 생성기를 사용하여 상기 문제 상황에 대한 계획을 직접 산출하는 것을 특징으로 하는 자원 할당 계획 시스템.
KR1020130091886A 2013-08-02 2013-08-02 계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템 KR101617689B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020130091886A KR101617689B1 (ko) 2013-08-02 2013-08-02 계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020130091886A KR101617689B1 (ko) 2013-08-02 2013-08-02 계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템

Publications (2)

Publication Number Publication Date
KR20150015884A KR20150015884A (ko) 2015-02-11
KR101617689B1 true KR101617689B1 (ko) 2016-05-04

Family

ID=52573040

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020130091886A KR101617689B1 (ko) 2013-08-02 2013-08-02 계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템

Country Status (1)

Country Link
KR (1) KR101617689B1 (ko)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102124454B1 (ko) * 2018-11-30 2020-06-19 한국생산기술연구원 기술 정보의 구조화를 통한 유사 기술 제공 방법 및 장치

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000259712A (ja) 1999-03-04 2000-09-22 Mitsubishi Electric Corp 介護計画作成支援装置および介護計画作成支援装置における介護計画作成方法
JP2008299847A (ja) 2007-05-29 2008-12-11 Palo Alto Research Center Inc 照会ベースでコンポーネント実行可能命令を使用するモデルベース・プランニング

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000259712A (ja) 1999-03-04 2000-09-22 Mitsubishi Electric Corp 介護計画作成支援装置および介護計画作成支援装置における介護計画作成方法
JP2008299847A (ja) 2007-05-29 2008-12-11 Palo Alto Research Center Inc 照会ベースでコンポーネント実行可能命令を使用するモデルベース・プランニング

Also Published As

Publication number Publication date
KR20150015884A (ko) 2015-02-11

Similar Documents

Publication Publication Date Title
US11928647B2 (en) System and method to predict service level failure in supply chains
Graves et al. Supply chain design: safety stock placement and supply chain configuration
Lin et al. Build-to-order supply chain network design under supply and demand uncertainties
Simchi-Levi et al. Performance evaluation of stochastic multi‐echelon inventory systems: A survey
Cui et al. Additive manufacturing-enabled supply chain: Modeling and case studies on local, integrated production-inventory-transportation structure
Barros et al. A combinatorial approach to level of repair analysis
Tsai et al. A simulation optimization approach for a two-echelon inventory system with service level constraints
EP3477565A1 (en) Inventory control and ordering device, inventory control and ordering method, and computer program
Modrák et al. Impacts of RFID implementation on cost structure in networked manufacturing
US20230196238A1 (en) Image-Based Decomposition for Fast Iterative Solve of Complex Linear Problems
KR20220146313A (ko) 아이템 폐기와 관련된 정보 제공 방법 및 그 장치
US20230117588A1 (en) Systems and methods for use of a global registry with automated demand profiling via machine learning to optimize inventory management
US20240428187A1 (en) Domain-Aware Decomposition for Supply Chain Master Planning using Linear Programming
Rohaninejad et al. Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches
WO2023278800A1 (en) Order fulfillment system
Samaranayake Improving manufacturing lead time using holistic approach to planning and execution with integrated data structures: numerical simulation and comparison
KR101617689B1 (ko) 계획 검색 및 수정 기법을 이용한 고속 자원 할당 계획 방법 및 시스템
JP7040441B2 (ja) 機会損失算出システム、機会損失算出方法および機会損失算出プログラム
US11948163B2 (en) User interface for visualizing output from supply chain replenishment simulation
Fani et al. Optimizing production allocation with simulation in the fashion industry: A multi-company case study
US10109004B1 (en) Assortment pack planning
US20230281747A1 (en) Image-Based Analytics of Supply Chain Optimization Problems
JP2023013359A (ja) 物流作業最適化装置および物流作業最適化方法
Singh et al. A modified EOQ model using purchase dependency and partial backordering
Song et al. Dynamic pricing and inventory control of substitutable products in a nonstationary environment

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20130802

PA0201 Request for examination
N231 Notification of change of applicant
PN2301 Change of applicant

Patent event date: 20140407

Comment text: Notification of Change of Applicant

Patent event code: PN23011R01D

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

Comment text: Notification of reason for refusal

Patent event date: 20141017

Patent event code: PE09021S01D

PG1501 Laying open of application
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: 20150728

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20160427

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20160428

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20200401

Start annual number: 5

End annual number: 5

PR1001 Payment of annual fee

Payment date: 20210616

Start annual number: 6

End annual number: 6

PR1001 Payment of annual fee

Payment date: 20230321

Start annual number: 8

End annual number: 8