Job shop 환경 하에서의 총 작업시간을 최소화하기 위한 분산 스케듈링 방법

• 영문명: A Distributed Scheduling Methodology to Minimize Total Completion Time in Job Shop Environments
• 발행기관: 한국산업경영시스템학회
• 저자명: 임승빈 정인재
• 간행물 정보: 『한국산업경영시스템학회 학술대회』2005년 추계학술대회 논문집, 58~62쪽, 전체 5쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2005.10.01

국문 초록

  본 논문은 여러 개의 하위 생산시스템이 존재하고 설비가 공유되어있는 job shop에 관한 문제를 다루고 있다. 여러 개의 하위 생산시스템은 총 작업완료 시간을 최소화하는 것을 지역적 목적식으로 가지고, job shop의 설비를 공유하는 분산 생산시스템 상황을 가정하고 있다. 중앙 통제 환경의 생산시스템에서는 한 명의 의사 결정자에게 모든 정보가 가용한 상태이다. 만약 중앙 통제 환경 생산시스템이 job shop 환경하의 작업완료 시간 최소화문제, 즉 J<SUB>m</SUB>∥∑C이면 이는 잘 알려진 NP-hard문제 이다. 그러나 분산 생산시스템 환경에서는 각각의 하위 생산 시스템이 지역적 목적식 (총 작업완료 시간 최소화)과 지역적 데이터 (생산시간, 지역적 제약식)만을 가지고 서로간의 협업과 communication에 의해 의사 결정이 형성된다. 본 논문의 목적은 분산 생산시스템 환경에서하위 생산시스템들이 독립적인 의사 결정을 할 수 있는 독자성을 최대한 유지하면서, 부분적인 정보를 공유하여 전체 생산시스템의 최적화를 이루는 하위 생산시스템과 설비에이전트들간의 협업체계를 설계하는데 있다.
  본 연구의 이론적 배경은 [1]에 의해서 제안된 Cooperative Interaction via Coupling Agents(CICA)모델에 기반을 두고 있다. CICA모델은 수학적으로 모델링된 분산 조직(Distributed organization)과 전체 시스템의 최적화를 유도하는 가상 agent들로 구성되며 전체 최적화는 조직 간의 협업에 의해 달성된다. CICA모델은 단일설비를 공유한 분산 생산시스템 상황([2]), 두 대의 설비로 이루어진 flow-shop을 공유한 분산 생산시스템 상황([3])에 성공적으로 적용되었다.
  본 연구와 관련된 분산 모형들에 대한 연구는 decomposition method, auction/bidding algorithm, constraint-directed heuristic search(CHS)가 있다. Decomposition method에서 [4], [5]은 price directive decomposition에 관한 연구이고 [6]은 resource directive decomposition에 관한 연구이다 [7], [8]는 자원의 배분과정을 경제적 과정으로 이해하려고한 auction algorithm에 관한 연구이다. CHS는 컴퓨터 공학, 인공지능 분야에서 설비 스케듈링 문제를 다루는 분야 중 하나이며, [9]에 이에 관한 연구가 잘 나타나 있다.

영문 초록

  This paper considers a job shop environment where machines are shared by several sub-production systems. The local objective of a sub-production system is the minimization of total completion time. In a centralized environment, a single decision maker has complete information of processing time, job routing and local objectives. In this case, the problem is a traditional job shop scheduling problem to minimize the total completion time which is well-known NP-hard problem. Meanwhile, it is assumed that no sub-production system has a complete view of the entire system in a distributed environment. This paper proposes a distributed scheduling methodology that maintains autonomy of each sub-production system while pursuing system-wide performance in job shop environment. The proposed method is compared to the performance of centralized solutions.

목차

Abstract
1. 개요
2. 문제 상황
3. CICA를 통한 연구 방법론
4. 실험 및 성능 평가
5. 결론
참고문헌

키워드

sub-production system total completion time local objective