최소납기우선규칙 (Earliest Due Date Rule)

한 줄 정의: 납기일이 가장 임박한 작업을 우선적으로 처리하도록 순서를 정하는 스케줄링 규칙입니다.

쉽게 풀면

여러 개의 숙제가 있을 때, 마감일이 가장 가까운 숙제부터 먼저 처리하는 방식이라고 생각하면 됩니다. 최소납기우선규칙은 처리해야 할 작업이 여러 개 있을 때, 남은 시간이 얼마인지를 따져서 납기일이 가장 빠른 것부터 순서대로 처리하도록 정하는 방법입니다. 간단하지만 납기를 지키는 데 효과적이라는 이유로 실제 현장에서도 널리 사용됩니다.

왜 중요한가

납기를 지키지 못하면 고객 신뢰나 계약상의 불이익으로 이어질 수 있기 때문에, 스케줄링 문제에서 납기 준수는 매우 중요한 목표입니다. 산업공학에서는 최소납기우선규칙을 기준선(baseline)으로 삼아 다른 정교한 스케줄링 기법과 성능을 비교하는 경우가 많습니다.

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

"본 연구는 최소납기우선규칙을 적용했을 때 최대 지연시간이 크게 감소함을 확인하였다."

납기가 임박한 작업을 먼저 처리하는 규칙을 사용했더니 가장 늦게 끝나는 작업의 지연 정도가 줄었다는 뜻입니다.

"제안된 알고리즘의 성능을 최소납기우선규칙 등 기존 디스패칭규칙과 비교하여 우수성을 입증하였다."

새로 제안한 방법을 이미 널리 쓰이는 간단한 규칙과 비교해 얼마나 더 나은지 검증했다는 의미입니다.

조금 더 깊게 보면

최소납기우선규칙은 지연 작업의 수나 최대 지연시간과 같은 납기 관련 지표를 개선하는 데 효과적인 것으로 알려져 있습니다. 다만 처리시간이 긴 작업의 납기가 임박한 경우 다른 작업들이 뒤로 밀려 전체적인 메이크스팬이 늘어날 수 있어, 목표에 따라 다른 규칙과 함께 검토되기도 합니다.

주의할 점

최소납기우선규칙은 납기 준수에는 강점이 있지만, 전체 완료시간이나 설비 활용률 같은 다른 목표에서는 항상 최선의 결과를 보장하지는 않습니다.