순열 플로우샵의 발견적 방법에 대한 고찰(A comprehensive review and evaluation of permutation flowshop heuristics)

전문가 제언

□ 본 연구는 순열플로우샵일정계획문제(PFSP)에 관해 지금까지 제시되었던 전통적인 발견적 방법과 변이(meta)발견적 방법을 포괄적으로 검토하고 평가하였다. 모두 25가지 알고리즘을 가지고 Taillard가 만들어 놓은 120개 사례를 벤치마크로 하여 실험을 해보았다.

□ 우선 배정 규칙(dispatching rules)은 나쁘게 나왔으나 CPU시간은 평균 0.5 이내로 나왔다. 가장 좋은 두 발견적 방법은 Suliman의 개량방법과 NEH발견적 방법이다.

□ Tabu Search, Simulated Annealing 그리고 유전적 알고리즘은 PFSP해결에 아주 우수한 변이발견적 방법임이 밝혀졌다. 그러나 이 방법도 최초 모집단을 잘 구성하고, 문제영역에 관한 지식을 잘 갖추어야 좋은 결과를 얻을 수 있다.

□ 따라서 우선배정규칙(dispatching rules)은 Taillard의 benchmark로 평가하면 가장 간단한 랜덤 규칙(random rules)보다 나쁜 것으로 나타났으나 현실적으로 전문적인 software로 많은 산업체의 관리자가 사용하고 있는 실정이다.

□ 앞으로 우선배정규칙을 보다 정교하게 잘 다듬어 보다 성능이 우수한 발견적 방법을 개발한다면 활용성이 뛰어날 것이다. 일부 Tabu Search 변이(meta)발견적 방법은 블록을 형성하여 해를 구하였는데 블록을 Clustering algorithm을 적용하면 좋은 결과를 얻을 수 있을 것으로 생각된다.

저자

Ruiz, R; Maroto, C

자료유형

학술정보

원문언어

영어

기업산업분류

과학기술일반

연도

2005

권(호)

165(2)

잡지명

European Journal of Operational Research

과학기술
표준분류

과학기술일반

페이지

479~494

분석자

김*영

분석물

• 순열 플로우샵의 발견적 방법에 대한 고찰.pdf [268,000 byte]

이미지변환중입니다.