가중최단처리시간 규칙 (Weighted Shortest Processing Time Rule)

한 줄 정의: 처리시간을 가중치로 나눈 값이 작은 작업부터 처리해 단일기계의 가중완료시간 합을 최소화하는 규칙입니다.

쉽게 풀면

작업마다 걸리는 시간과 중요도(가중치)가 다를 때, '중요도에 비해 짧게 끝나는 일'을 먼저 하는 규칙입니다. 각 작업의 처리시간 ÷ 가중치를 계산해 작은 순서로 줄 세우면 됩니다. 가중치가 모두 같으면 짧은 일부터 하는 SPT 규칙과 같아집니다.

왜 중요한가

기계 한 대에서 가중완료시간 합을 최소화하는 문제의 최적해를 정확히 주는 간단한 규칙이라, 스케줄링 이론의 출발점이자 복잡한 휴리스틱의 부품으로 쓰입니다. 우선순위 디스패칭 규칙을 설계하는 논문에서도 비교 기준으로 자주 쓰입니다.

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

"주문별 긴급도를 가중치로 설정하고 WSPT 규칙으로 작업 순서를 결정한 결과 가중 평균완료시간이 감소하였다."

긴급도 대비 처리시간이 짧은 주문을 앞에 배치해 가중 완료시간을 줄였다는 뜻입니다.

조금 더 깊게 보면

스미스(W. E. Smith)가 1956년에 최적성을 보여 스미스 규칙이라고도 합니다. 스케줄링의 3필드 표기로는 1||ΣwⱼCⱼ 문제의 최적 규칙이며, 인접한 두 작업의 순서를 바꿨을 때 비용이 줄지 않음을 보이는 '인접 교환 논법'으로 증명합니다. 작업마다 도착시간이 다르거나, 선행관계가 있거나, 기계가 여러 대이면 일반적으로 최적성이 보장되지 않습니다.

주의할 점

SPT 규칙은 모든 작업을 똑같이 중요하게 보고 처리시간만 비교하는 반면, WSPT는 가중치를 반영한다는 점이 다릅니다. 납기 준수가 목표라면 이 규칙보다 EDD 같은 납기 기반 규칙을 검토해야 합니다.