AI 예측(prediction)을 활용해 NP-난해(NP-hard) 조합 최적화 문제를 더 빠르게 풀어내는 학습 강화(learning-augmented) 알고리즘 연구가 새롭게 발표됐다. 이번 연구는 Antoniadis 외 연구진이 ICLR 2025에서 제안한 프레임워크를 확장해, 선택 문제(selection problem) 이외의 중요한 NP-난해 문제로 적용 범위를 넓힐 수 있는지 묻는 미해결 과제에 답한다.
연구팀은 비동질 다중 기계 환경에서의 완료 시간(makespan) 최소화 문제, 표기로는 R|C_max에 초점을 맞췄다. 이 문제는 각 기계가 서로 다른 처리 속도를 가질 때 작업 집합을 어떻게 분배해야 전체 완료 시간을 최소화할 수 있는지를 묻는 전형적인 스케줄링 문제다. 핵심 아이디어는 ‘무거운 작업(heavy job)’의 배정 위치에 대한 AI 예측을 활용해 탐색 공간을 줄이는 것이다. 예측이 정확할 때에는 다항식 시간 내에 (1+ε)-근사를 달성하며, 예측 오차가 커질수록 최악의 경우 최적값의 2배를 보장하는 2-근사로 부드럽게 성능이 저하되는 구조다.
이 설계의 핵심은 ‘부드러운 성능 저하(graceful degradation)’에 있다. 예측이 완벽하지 않더라도 오차 크기에 비례해 근사 비율이 점진적으로 나빠질 뿐, 갑작스러운 성능 붕괴가 없다. 연구팀은 이론적 분석과 함께 실증적 평가도 수행해, 제안된 알고리즘이 실제 벤치마크 데이터에서도 이론적 보장에 부합하는 결과를 보인다고 밝혔다.
이 연구는 기계 학습과 알고리즘 설계를 결합하는 방향을 탐색하는 학습 강화 알고리즘 분야의 적용 범위를 스케줄링으로 확대했다는 점에서 의미가 있다. 선택 문제에 집중됐던 기존 프레임워크가 보다 광범위한 조합 최적화 문제에도 적용 가능하다는 가능성을 열어주며, 클라우드 자원 배분·제조 공정 일정 수립 등 실세계 다기계 스케줄링 문제에도 응용될 전망이다.
