단일기계 총 지체일정 문제: 고찰 및 확장

전문가 제언

○ 일반적으로 일정문제(scheduling problem)는 세 가지 분야로 특정하고 있다. 첫 번째는 기계 환경, 가운데는 작업의 특성, 세 번째가 목적함수이다. 따라서 단일기계 총(평균) 지체일정 문제는 1//로 표시된다. 1//문제는 해결하기 위한 계산상으로 볼 때 ordinary NP-hard (non-deterministic polynomial-time hard)이다. 1//문제는 일정계획 문헌에서 가장 광범위하게 연구되고 있는 문제 중에 하나이다.

○ 본 연구는 단일기계 총 지체 1// 일정문제를 해결하기 위한 최신 이론적 개발을 고찰하여 이들 이론 가운데 일부 해법에 대해 확장을 제안하고 있다. 먼저 1// 일정문제에 대한 정확한 알고리즘, 완전 다항적 근접 기법, 발견적 알고리즘, 특별 경우와 일반적인 경우에 대해 고찰한다. 1// 일정문제 이론과 실제적 관점 모두에 상당히 관심을 가지고 연구를 계속하고 있는 분야임을 알 수 있었다. 이 문제는 ordinery NP-hard임에도 불구하고 현재 알고리즌 기법은 500 작업까지 해결할 수 있는 능력으로 확장하고 있다.

○ 1// 문제에 관한 가장 중요한 이론적 개발은 Emmons(1969)의 지배/우세 조건(dominance condition)과 Lawler(1977)의 분해원리(decomposition principle)이다. 1//문제에 대한 정확한 알고리즘의 대부분은 동적계획법(Dynamic Programming, 이후, DP), 분지한계(Branch and Bound, 이후, BB) 또는 PD와 BB 혼합접근 방법이다. 1//문제를 해결하기 위한 가장 정확한 알고리즘은 최근에 개발한 분해이론을 사용하는 BB 알고리즘이다.

○ 1//문제의 복잡성을 해결하기 위한 개략적 알고리즘은 대체적으로 구조(construction), 국부탐색(local search), 분해기반(decomposition -based) 그리고 유사발견적(meta-heuristic) 알고리즘으로 분류할 수 있다. 모든 발견적 방법을 실험한 결과 PSK와 NBR를 복합하여 하위문제를 생성하여 해결하는 식으로 문제를 푼 분해 발견적 방법이 1//문제를 해결하는 데 매우 좋은 발견적 알고리즘으로 결론을 내리고 있다.

저자

Christos Koulamas

자료유형

학술정보

원문언어

영어

기업산업분류

과학기술일반

연도

2010

권(호)

202(1)

잡지명

European Journal of Operational Research

과학기술
표준분류

과학기술일반

페이지

1~7

분석자

김*영

분석물

• 단일기계 총 지체일정 문제-고찰 및 확장.pdf [476,491 byte]

이미지변환중입니다.