피드로 돌아가기
Hacker NewsInfrastructure
원문 읽기
CP-SAT Interval Variable 기반 Cloud Host Maintenance 스케줄링 최적화
Using OR-Tools CP-SAT for Scheduling Problems
AI 요약
Context
수십만 대의 Guest VM이 운용되는 하이퍼바이저 호스트의 점검을 위한 VM Migration 스케줄링 필요성 제기. 기존 MIP Solver 기반 접근 방식은 시간 인덱스 모델링 시 변수 수가 기하급수적으로 증가하여 Solver 부하를 초래하는 한계 존재.
Technical Solution
- Resource-Constrained Project Scheduling Problem(RCPSP) 모델을 통한 하이퍼바이저 점검 문제 정의
- CP-SAT의 Interval Variable을 도입하여 Start/End Time과 Duration을 직관적으로 모델링
- AddNoOverlap 제약 조건을 활용해 VM Migration 간의 상충(Conflict) 및 동시성 제어
- AddCumulative 제약 조건을 통해 호스트 및 네트워크의 Capacity 및 Concurrency Limit을 효율적으로 관리
- Big-M 제약 조건 기반의 MIP 선형화 대신 전용 Constraint를 사용하여 모델 복잡도 감소
- Time-indexed formulation 대비 변수 복잡도를 O(n×T)에서 O(n²)로 최적화하여 Solver 성능 확보
실천 포인트
1. 스케줄링 문제 정의 시 Job Shop, RCPSP 등 표준 OR 문제 유형으로 매핑 가능한지 확인
2. 시간축 기반의 변수 생성이 과도한 경우(Long Planning Horizon), Time-indexed 대신 Interval Variable 기반 Solver 검토
3. 복잡한 상호 배제 조건이나 리소스 누적 제약이 필요한 경우 MIP보다 CP-SAT 계열의 Constraint Programming 도구 우선 고려