최단처리시간규칙 (Shortest Processing Time Rule)
쉽게 풀면
여러 개의 심부름이 있을 때, 시간이 오래 걸리는 것보다 금방 끝낼 수 있는 것부터 처리하면 짧은 시간 안에 더 많은 심부름을 끝낼 수 있습니다. 최단처리시간규칙은 바로 이 원리를 스케줄링에 적용한 것으로, 작업 대기열에서 처리 시간이 가장 짧은 작업을 골라 먼저 처리합니다. 간단한 규칙이지만 평균적으로 작업이 대기하는 시간을 줄이는 데 매우 효과적이라고 알려져 있습니다. 최단처리시간규칙은 대기 중인 여러 작업 가운데 처리에 걸리는 시간이 가장 짧은 작업을 먼저 처리하도록 정하는 작업 배정 규칙입니다.
왜 중요한가
많은 작업이 순서를 기다리는 생산이나 서비스 현장에서, 평균 대기시간이나 평균 완료시간을 줄이는 것은 자원 활용도와 고객 만족도 모두에 중요한 영향을 미칩니다. 산업공학에서는 최단처리시간규칙이 평균 완료시간을 최소화하는 데 이론적으로 우수한 성질을 가진다는 점에서 여러 스케줄링 연구의 비교 기준으로 활용됩니다. 단일 기계 환경에서 이 규칙은 모든 작업의 평균 완료시간과 평균 흐름시간을 최소화하는 최적 규칙임이 수학적으로 증명되어 있어, 스케줄링 이론에서 가장 자주 인용되는 기준 규칙입니다.
논문에서는 이렇게 쓰입니다
기계가 하나뿐인 단순한 상황에서는 이 규칙을 쓰면 평균 완료시간이 가장 짧아진다는 사실을 확인했다는 뜻입니다.
서로 다른 목적을 가진 두 대표적인 규칙을 같은 환경에서 비교해 각각의 장단점을 파악했다는 의미입니다.
조금 더 깊게 보면
최단처리시간규칙은 단일 기계 환경에서 평균 완료시간을 최소화하는 최적 규칙으로 알려져 있으며, 이는 스케줄링 이론에서 자주 인용되는 결과입니다. 다만 다수의 기계가 관련된 복잡한 환경에서는 이 규칙만으로는 최적성이 보장되지 않으며, 다른 규칙과 결합하거나 별도의 최적화 기법이 필요할 수 있습니다. 이 규칙은 평균적인 처리 효율에는 유리하지만, 처리시간이 긴 작업이 계속 뒤로 밀리는 이른바 '기아 현상'을 유발할 수 있어 납기 준수가 중요한 환경에서는 최소납기일우선규칙과 함께 검토됩니다.
주의할 점
처리시간이 긴 작업은 계속 뒤로 밀려 오랫동안 처리되지 못하는 이른바 기아(starvation) 현상이 발생할 수 있어, 납기가 중요한 상황에서는 다른 규칙과 함께 고려해야 합니다.