최소여유시간규칙 (Least Slack Time Rule)

한 줄 정의: 작업의 납기까지 남은 시간에서 남은 처리시간을 뺀 값인 '여유시간(slack)'이 가장 작은 작업을 먼저 처리하도록 우선순위를 정하는 스케줄링 규칙입니다.

쉽게 풀면

여러 개의 숙제가 있을 때, 단순히 마감일이 빠른 순서가 아니라 '마감까지 남은 시간에서 그 숙제를 끝내는 데 걸리는 시간을 뺀 나머지'가 가장 적은 숙제부터 하는 것과 같습니다. 예를 들어 마감이 이틀 남았지만 하루만 걸리는 숙제보다, 마감이 하루 남았고 정확히 하루가 걸리는 숙제가 더 급합니다. 여유시간이 0에 가깝거나 음수라면 그 작업은 지금 당장 처리하지 않으면 늦어질 가능성이 매우 큽니다. 이렇게 여유가 없는 작업을 먼저 챙기는 것이 이 규칙의 핵심입니다.

왜 중요한가

단순히 납기일 순서로만 작업을 처리하면 처리시간이 긴 작업이 실제로는 더 급함에도 뒤로 밀릴 수 있습니다. 최소여유시간규칙은 남은 처리시간까지 함께 고려하므로 현실적인 긴급도를 더 정확히 반영합니다. 그래서 생산현장이나 프로젝트 관리에서 납기 준수를 목표로 하는 스케줄링 문제에 널리 연구되고 적용됩니다.

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

"본 연구에서는 최소여유시간규칙(LST)을 기준으로 작업 우선순위를 결정하고, 이를 기존 SPT 규칙과 비교하여 납기 준수율의 차이를 분석하였다."

여러 우선순위 규칙 중 하나로 최소여유시간규칙을 적용해 다른 규칙과 성능을 비교하는 실험 설계를 설명하는 문장입니다.

"동적 작업장 환경에서 여유시간이 음수인 작업이 발생할 경우, 최소여유시간규칙은 해당 작업을 최우선으로 배정함으로써 지연을 최소화하고자 하였다."

실시간으로 작업이 계속 들어오는 상황에서 여유시간이 부족한 작업을 즉시 처리하도록 규칙을 적용한 사례를 설명합니다.

조금 더 깊게 보면

여유시간은 일반적으로 '납기일 - 현재시각 - 남은 처리시간'으로 계산되며, 이 값이 작을수록 우선순위가 높아집니다. 여러 공정을 거치는 작업의 경우 아직 거쳐야 할 모든 공정의 처리시간 합을 남은 처리시간으로 사용합니다. 이 규칙은 동적으로 재계산될 수 있어, 시간이 지남에 따라 우선순위가 계속 바뀌는 특징이 있습니다.

주의할 점

여유시간 계산에는 처리시간에 대한 정확한 추정이 필요한데, 실제 현장에서는 처리시간이 변동하므로 이 추정이 부정확하면 규칙의 효과가 떨어질 수 있습니다. 또한 모든 상황에서 다른 규칙보다 항상 우수한 것은 아니며, 목표(납기지연 최소화, 처리량 극대화 등)에 따라 적합한 규칙이 달라집니다.