할당문제 (Assignment Problem)
한 줄 정의: n명의 작업자와 n개의 작업을 1대1로 짝지어 총비용을 최소화하는 최적화 문제입니다.
쉽게 풀면
작업자 네 명과 일 네 가지가 있고, 누가 어떤 일을 하느냐에 따라 걸리는 시간이 다르다고 해 봅시다. 한 사람은 한 가지 일만, 한 가지 일은 한 사람만 맡도록 짝을 지어 전체 시간을 가장 줄이는 것이 할당문제입니다. 비용을 표(행렬)로 정리한 뒤 가장 좋은 짝짓기를 찾는 문제라고 볼 수 있습니다.
왜 중요한가
작업자-기계 배정, 차량-주문 배정, 교대근무 배치 등 현장의 수많은 짝짓기 의사결정이 이 모형으로 표현됩니다. 정수 조건이 있는데도 선형계획으로 풀면 자연스럽게 정수해가 나오는 대표적인 예라서 수리계획법 교과서에서 반드시 다룹니다.
논문에서는 이렇게 쓰입니다
"작업자별 숙련도에 따른 처리시간 행렬을 바탕으로 할당문제를 구성하여 총 처리시간을 12% 단축하는 배정안을 도출하였다."
처리시간 표를 비용으로 보고 1대1 최적 배정을 구했다는 뜻입니다.
조금 더 깊게 보면
할당문제는 공급량과 수요량이 모두 1인 수송문제의 특수한 경우이며, 제약행렬이 완전단모듈러(totally unimodular)이기 때문에 선형계획 완화만으로도 정수 최적해가 얻어집니다. 대표 해법은 헝가리안 기법이며, 작업자 수와 작업 수가 다르면 가상의 작업자나 작업을 추가해 균형을 맞춥니다. 비용 대신 두 배정 사이의 거리·물동량 곱을 고려하면 훨씬 어려운 이차할당문제가 됩니다.
주의할 점
이차할당문제는 시설 간 상호작용(물동량×거리)까지 반영해 NP-난해이지만, 일반 할당문제는 다항시간에 풀린다는 점이 결정적으로 다릅니다. 이름이 비슷하다고 두 문제의 난이도를 같게 보면 안 됩니다.