CRAFT 알고리즘 (CRAFT (Computerized Relative Allocation of Facilities Technique))
한 줄 정의: 초기 배치안을 입력으로 받아 부서 쌍의 위치를 교환하며 물류 이동비용(거리×물동량×단위비용의 합)을 줄여 나가는 개선형 컴퓨터 설비배치 기법입니다.
쉽게 풀면
공장의 부서들을 어떻게 놓아야 물건이 오가는 거리가 짧아질까를 다루는 방법입니다. CRAFT는 일단 현재 배치에서 시작해 '두 부서의 자리를 바꾸면 총 이동비용이 얼마나 줄까'를 모든 쌍에 대해 계산하고, 가장 많이 줄어드는 교환을 실행합니다. 더 이상 나아지지 않을 때까지 이를 반복합니다.
왜 중요한가
1963년 Armour와 Buffa가 개발한 CRAFT는 설비배치에 컴퓨터 최적화를 도입한 선구적 기법으로, 이후 개선형 배치 알고리즘(COFAD, MULTIPLE 등)의 기준점이 되었습니다. 출발-도착표와 거리 행렬만 있으면 적용할 수 있어 교육과 실무에서 지금도 널리 쓰입니다.
논문에서는 이렇게 쓰입니다
"현 배치를 초기해로 CRAFT 알고리즘(CRAFT algorithm)을 적용하여 부서 간 총 자재이동비용을 14.2% 절감하는 개선안을 도출하였다."
현재 배치에서 출발해 부서 자리를 바꿔 가며 운반비용을 줄이는 안을 얻었다는 뜻입니다.
"CRAFT는 초기해 의존성이 커 서로 다른 세 개의 초기 배치에서 출발한 결과를 비교하였다."
출발점에 따라 결과가 달라지므로 여러 출발점을 시험했다는 의미입니다.
조금 더 깊게 보면
CRAFT는 부서 면적이 같거나 인접한 부서 쌍만 교환 대상으로 삼고, 부서 중심 간 직선거리(또는 직교거리)로 비용을 추정하므로 교환 후 실제 형상이 불규칙해질 수 있습니다. 이는 이차할당문제(QAP)에 대한 쌍교환 국소탐색 휴리스틱으로 해석되며, 국소최적에 빠지기 쉬워 이후 타부탐색, 담금질 기법과 결합한 변형이 제안되었습니다.
주의할 점
정량적 물류비용만 고려하므로 활동상관관계도표로 표현되는 정성적 근접 요구(소음, 안전 등)는 반영되지 않습니다. 결과 배치의 부서 형상이 실제로 사용 가능한지 사후 조정이 반드시 필요하며, 개선형 기법이므로 초기해 품질에 크게 좌우됩니다.