납기지연최소화 (Tardiness Minimization)

한 줄 정의: 각 작업이 납기일보다 늦게 끝난 정도(지연시간)의 합이나 최댓값 등을 최소화하는 것을 목표로 스케줄을 설계하는 문제입니다.

쉽게 풀면

택배기사가 여러 곳에 물건을 배달해야 하는데, 각 배송지마다 약속한 도착 시간이 있다고 생각해보세요. 어떤 순서로 배달하느냐에 따라 늦는 곳과 늦는 정도가 달라집니다. 납기지연최소화는 이렇게 늦는 시간의 총합이나 가장 심하게 늦는 정도를 최대한 줄이는 배달(작업) 순서를 찾는 문제입니다. 제시간에 끝나거나 일찍 끝난 작업은 지연시간을 0으로 계산하고, 늦게 끝난 작업만 그 늦은 정도를 계산에 반영합니다.

왜 중요한가

고객과의 약속이나 계약상의 납기를 지키는 것은 제조업과 서비스업 모두에서 신뢰와 비용에 직결되는 중요한 문제입니다. 그래서 스케줄링 연구에서 총 지연시간, 최대 지연시간, 지연 작업 수 등 다양한 형태의 지연 관련 목적함수가 널리 연구되고 있습니다.

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

"본 논문은 단일기계 환경에서 총 납기지연시간을 최소화하는 것을 목적함수로 설정하고, 이를 해결하기 위한 분지한계법을 제안한다."

납기지연최소화를 명시적인 목적함수로 삼아 정확해법을 설계한 연구를 설명합니다.

"실험 결과, 제안된 휴리스틱은 기존 방법 대비 평균 납기지연을 현저히 감소시키는 것으로 나타났다."

새로운 스케줄링 방법의 성능을 납기지연 감소 폭으로 평가하는 문장입니다.

조금 더 깊게 보면

지연시간(tardiness)은 보통 '완료시각과 납기일의 차이 중 0과 비교해 더 큰 값'으로 정의되어, 일찍 끝나도 음수가 되지 않고 0으로 처리됩니다. 이는 완료시각이 납기보다 이르든 늦든 그 차이를 그대로 반영하는 편차(lateness)와 구분되는 개념입니다. 목적함수로는 총 지연시간의 합, 지연 작업의 개수, 최대 지연시간 등 다양한 형태가 쓰입니다.

주의할 점

납기지연최소화는 메이크스팬 최소화 등 다른 목표와 상충할 수 있어, 한 목표를 우선하면 다른 목표의 성능이 나빠질 수 있습니다. 또한 다수의 지연 관련 문제는 계산복잡도가 높아 대규모 문제에서는 정확해 대신 휴리스틱이 흔히 사용됩니다.