CP인가 DP인가? 둘 다 하면 안 될까: 부분 작업 스케줄링 문제(PSSP)에 대한 사례 연구

동적 계획법 (Dynamic Programming, DP)과 제약 프로그래밍 (Constraint Programming, CP)은 조합 최적화 문제 (combinatorial optimization problems)를 해결하기 위해 잘 확립된 패러다임입니다. 보통 이 두 가지 접근 방식은 별개로 사용됩니다. 본 논문은 DP가 주요 탐색 프레임워크 역할을 수행하고, CP가 전역 제약 전파 (global constraint propagation)를 활용하기 위한 서브루틴 (subroutine)으로 사용됨으로써 두 방식이 효과적이고 우아하게 결합될 수 있음을 보여주는 것을 목표로 합니다. 본 논문은 순수 DP 방식이 이전에 제안되었고 효율적인 CP 필터링 알고리즘 (filtering algorithms)을 사용할 수 있는 부분 작업 스케줄링 문제 (Partial Shop Scheduling Problem, PSSP)에 대해 이러한 접근 방식을 제시합니다. PSSP는 각 작업 (job)이 임의의 선행 제약 조건 (precedence constraints)을 가진 일련의 연산 (operations)들로 구성된 일반적인 스케줄링 문제입니다. 이 접근 방식은 기존의 DP 알고리즘이 엄격하게 계층별 (layer-wise) 방식으로 작동했던 것과 달리, 애니타임 열 탐색 (anytime column search)과 같은 애니타임 DP (anytime DP) 전략을 수용할 수 있을 만큼 충분히 유연합니다. 또한, CP 모델링의 유연성 덕분에 임의의 선행 제약 조건을 통합하는 것이 용이합니다. 그 결과, 이 모델은 어떠한 선행 그래프 (precedence graph)도 자연스럽게 처리하며, DP 모델을 재사용하고 현재 최적해 (incumbent solution)를 개선하기 위해 재시작 시 부분 순서 스케줄 (partial-order schedules)을 부과하는 대규모 이웃 탐색 (Large Neighborhood Search, LNS) 스킴을 설계하는 것도 가능하게 합니다. 이 특정 문제에 대해 최첨단 순수 CP 솔버 (pure CP solvers)와 경쟁할 수준은 아니지만, 우리의 주요 기여는 이러한 하이브리드 통합의 실행 가능성을 입증하는 데 있습니다.