메이크스팬최소화 (Makespan Minimization)

한 줄 정의: 모든 작업이 시작되고 나서 마지막 작업이 끝날 때까지 걸리는 전체 시간(메이크스팬)을 최소화하는 것을 목표로 삼는 스케줄링 문제입니다.

쉽게 풀면

여러 대의 세탁기와 여러 벌의 빨래가 있다고 할 때, 모든 빨래가 다 끝나는 시점을 최대한 앞당기고 싶다면 어떤 순서로 빨래를 세탁기에 넣어야 할지 정하는 문제와 같습니다. 이때 전체가 끝나는 시점, 즉 가장 늦게 끝나는 작업의 완료시각을 메이크스팬이라고 부릅니다. 메이크스팬최소화는 개별 작업의 납기 여부와 관계없이, 전체 작업이 얼마나 빨리 마무리되는지에 초점을 맞춥니다. 기계나 설비를 최대한 놀리지 않고 효율적으로 돌리는 것이 핵심입니다.

왜 중요한가

메이크스팬은 생산현장이나 프로젝트에서 전체 처리 능력과 설비 가동률을 나타내는 대표적인 지표로, 이를 줄이면 동일한 설비로 더 많은 일을 처리할 수 있게 됩니다. 그래서 플로우숍, 잡숍 등 다양한 스케줄링 환경에서 가장 널리 다뤄지는 목적함수 중 하나입니다.

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

"본 연구는 병렬기계 환경에서 메이크스팬을 최소화하기 위한 혼합정수계획법 모형을 제시하고, 소규모 문제에 대해 최적해를 구하였다."

메이크스팬 최소화를 수리 모형의 목적함수로 설정한 연구를 설명합니다.

"존슨규칙으로 구한 초기해의 메이크스팬을 시뮬레이티드 어닐링으로 추가 개선하여 대규모 문제에서도 효율적인 해를 도출하였다."

메타휴리스틱을 활용해 메이크스팬을 더욱 줄이는 개선 과정을 설명하는 문장입니다.

조금 더 깊게 보면

메이크스팬은 수학적으로 모든 작업의 완료시각 중 최댓값(max Cj)으로 정의됩니다. 단일기계 환경에서는 작업 순서와 무관하게 메이크스팬이 일정하지만, 여러 기계나 여러 단계를 거치는 환경에서는 작업 순서에 따라 메이크스팬이 크게 달라지므로 최적화의 의미가 커집니다. 대부분의 다기계 메이크스팬 최소화 문제는 계산복잡도가 매우 높아, 대규모 문제에서는 휴리스틱이나 메타휴리스틱이 흔히 활용됩니다.

주의할 점

메이크스팬만 줄이는 데 집중하면 개별 작업의 납기 준수나 재공품 재고 등 다른 성과 지표가 나빠질 수 있어, 실제 적용 시에는 여러 목표를 함께 고려하는 경우가 많습니다.