순서결정문제 (Sequencing Problem)
한 줄 정의: 여러 개의 작업이나 일을 어떤 순서로 처리할지 결정하여 특정 목표(완료시간, 지연 등)를 최적화하는 문제입니다.
쉽게 풀면
할 일이 여러 개 있을 때, 어떤 것을 먼저 하고 어떤 것을 나중에 할지 정하는 것이 순서결정문제입니다. 순서를 어떻게 정하느냐에 따라 전체적으로 걸리는 시간이나 마감을 못 지키는 정도가 크게 달라질 수 있습니다. 스케줄링의 가장 근본적인 형태로, 작업장스케줄링이나 흐름작업스케줄링처럼 더 구체적인 환경을 다루는 문제들도 결국 이 순서결정문제의 한 종류라고 볼 수 있습니다.
왜 중요한가
순서를 어떻게 정하느냐는 생산, 물류, 서비스 등 거의 모든 운영 현장에서 성과에 직접적인 영향을 미치는 핵심 의사결정입니다. 산업공학에서는 다양한 목적함수(메이크스팬, 납기 지연, 평균 완료시간 등)에 맞춰 최적 또는 근사적으로 좋은 순서를 찾는 방법을 연구합니다.
논문에서는 이렇게 쓰입니다
"본 논문은 단일 기계 순서결정문제에서 총 지연시간을 최소화하는 정수계획법 모형을 제시하였다."
작업 순서를 수학적으로 표현해서 지연시간을 최소로 만드는 방법을 다루었다는 뜻입니다.
"다양한 디스패칭규칙을 순서결정문제에 적용하여 그 성능 차이를 실험적으로 비교하였다."
서로 다른 규칙들이 순서를 정하는 데 있어 어떤 성과 차이를 보이는지 실험으로 확인했다는 의미입니다.
조금 더 깊게 보면
순서결정문제는 처리해야 할 항목 수가 늘어날수록 가능한 순서의 조합이 매우 빠르게 증가하기 때문에, 규모가 커지면 모든 경우를 다 따져보는 방식으로는 풀기 어려워집니다. 이 때문에 최단처리시간규칙, 최소납기우선규칙과 같은 간단한 규칙이나, 메타휴리스틱과 같은 근사적 탐색 기법이 실무에서 널리 활용됩니다.
주의할 점
순서결정문제는 목적함수(무엇을 최소화 또는 최대화할지)에 따라 최적의 순서가 달라지므로, 어떤 지표를 기준으로 삼았는지 반드시 확인해야 합니다.