와그너-휘틴 알고리즘 (Wagner-Whitin Algorithm)

한 줄 정의: 기간별로 변동하는 확정 수요에 대해 발주비용과 재고유지비용의 합을 최소화하는 기간별 생산·발주량을 동적계획법으로 구하는 동적 로트사이징 알고리즘입니다.

쉽게 풀면

앞으로 12개월 동안 매달 필요한 수량이 다를 때, '이번 달에 몇 달치를 한꺼번에 만들어 둘까'를 정하는 방법입니다. 한 번에 많이 만들면 준비비용은 아끼지만 재고비용이 늘고, 매달 조금씩 만들면 그 반대가 됩니다. 와그너-휘틴은 '생산은 재고가 0일 때만 한다'는 성질을 이용해 모든 가능한 조합 중 가장 싼 것을 효율적으로 찾아냅니다.

왜 중요한가

경제적주문량(EOQ)이 수요가 일정하다고 가정하는 것과 달리, 실제 MRP 환경의 수요는 기간마다 다릅니다. 와그너-휘틴은 이런 시변 수요에서 이론적 최적해를 제공하므로, 실무에서 널리 쓰이는 근사 기법(부분기간균형법, 실버-밀 휴리스틱 등)의 성능을 평가하는 기준이 됩니다.

논문에서는 이렇게 쓰입니다

"자재소요계획의 로트사이징 단계에 와그너-휘틴 알고리즘(Wagner-Whitin algorithm)을 적용하여 총 비용 기준 최적 발주 계획을 도출하였다."

MRP에서 기간별 발주량을 정할 때 이 알고리즘으로 비용 최소 계획을 구했다는 뜻입니다.

"실버-밀 휴리스틱의 해는 와그너-휘틴 최적해 대비 평균 2.3%의 비용 초과를 보였다."

간단한 근사법이 이론적 최적해에 비해 얼마나 손해인지를 비교했다는 의미입니다.

조금 더 깊게 보면

핵심은 '무재고 생산 성질(zero-inventory property)', 즉 최적해에서는 생산하는 기간의 기초재고가 0이라는 정리입니다. 이 덕분에 계획기간 T에 대해 O(T²) 동적계획법으로 풀리며, 이후 O(T log T) 및 O(T) 알고리즘도 개발되었습니다. 생산능력 제약이 추가되면 NP-난해한 용량제약 로트사이징 문제(CLSP)가 되어 별도의 해법이 필요합니다.

주의할 점

수요가 확정적이라는 가정과 '미래 수요 정보가 전부 알려져 있다'는 가정이 전제입니다. 수요 예측이 수정되면 전체 계획이 크게 바뀌는 계획 불안정(nervousness) 문제가 있어, 실무에서는 롤링 계획과 함께 동결 기간을 두는 보완이 필요합니다.