최소납기우선규칙 (Earliest Due Date Rule)
쉽게 풀면
여러 개의 숙제가 있을 때, 마감일이 가장 가까운 숙제부터 먼저 처리하는 방식이라고 생각하면 됩니다. 최소납기우선규칙은 처리해야 할 작업이 여러 개 있을 때, 남은 시간이 얼마인지를 따져서 납기일이 가장 빠른 것부터 순서대로 처리하도록 정하는 방법입니다. 간단하지만 납기를 지키는 데 효과적이라는 이유로 실제 현장에서도 널리 사용됩니다. 최소납기일우선규칙은 여러 작업이 처리를 기다리고 있을 때, 처리시간과 무관하게 납기일이 가장 임박한 작업을 먼저 처리하도록 정하는 작업 배정 규칙입니다.
왜 중요한가
납기를 지키지 못하면 고객 신뢰나 계약상의 불이익으로 이어질 수 있기 때문에, 스케줄링 문제에서 납기 준수는 매우 중요한 목표입니다. 산업공학에서는 최소납기우선규칙을 기준선(baseline)으로 삼아 다른 정교한 스케줄링 기법과 성능을 비교하는 경우가 많습니다. 이 규칙은 최대 지연시간을 최소화하는 데 이론적으로 최적임이 증명되어 있어, 납기 준수가 중요한 실무 환경에서 우선순위 배정의 기본 원칙으로 널리 채택됩니다.
논문에서는 이렇게 쓰입니다
납기가 임박한 작업을 먼저 처리하는 규칙을 사용했더니 가장 늦게 끝나는 작업의 지연 정도가 줄었다는 뜻입니다.
새로 제안한 방법을 이미 널리 쓰이는 간단한 규칙과 비교해 얼마나 더 나은지 검증했다는 의미입니다.
조금 더 깊게 보면
최소납기우선규칙은 지연 작업의 수나 최대 지연시간과 같은 납기 관련 지표를 개선하는 데 효과적인 것으로 알려져 있습니다. 다만 처리시간이 긴 작업의 납기가 임박한 경우 다른 작업들이 뒤로 밀려 전체적인 메이크스팬이 늘어날 수 있어, 목표에 따라 다른 규칙과 함께 검토되기도 합니다. 처리시간이 짧은 작업을 우선 처리해 평균 대기시간을 줄이는 최단처리시간규칙과 달리, 최소납기일우선규칙은 작업의 소요시간이 아니라 오직 납기일의 임박도만을 기준으로 순서를 정한다는 차이가 있습니다.
주의할 점
최소납기우선규칙은 납기 준수에는 강점이 있지만, 전체 완료시간이나 설비 활용률 같은 다른 목표에서는 항상 최선의 결과를 보장하지는 않습니다.