An Improvement-Path Framework and an Exact Algorithm for Single-Machine Scheduling with Release Times

운영 연구(Operations Research)의 세계, 즉 복잡한 시스템을 최대한 원활하게 작동시키는 데 전념하는 분야에는 '단일 기계 스케줄링(single-machine scheduling)'이라 불리는 근본적인 과제가 존재합니다. 하나의 공장 기계, 단 하나의 컴퓨터 프로세서, 또는 일련의 과업을 수행해야 하는 고독한 외과의사를 상상해 보십시오. 각 과업은 '출시 시간(release time)'이라고 불리는 특정 시점에 도착하며, 완료하는 데 특정 시간이 소요됩니다. 목표는 이 과업들을 수행할 순서를 결정하는 것입니다. 아이디어 자체는 단순해 보이지만, 현실은 매우 까다롭습니다. 기계가 과업이 도착하기를 기다리며 유휴 상태로 있으면 시간이 낭비됩니다. 반대로 과업이 지연되면 대기 시간이 발생하며, 이 대기 시간은 계속 쌓이게 됩니다. 모든 사람이 기다리는 총 시간을 최소화하기 위해 완벽한 순서를 찾아내는 수학적 문제는 악명 높을 정도로 어렵습니다. 이 문제는 과업의 수가 많아지면 가장 빠른 컴퓨터조차 완벽하게 해결하는 데 어려움을 겪는 매우 복잡한 문제 범주에 속하며, 이로 인해 계획가들은 종종 절대적인 최적해 대신 '충분히 괜찮은 수준'의 추측값에 안주하게 됩니다.

산둥 대학교의 한 연구팀은 이 문제를 바라보는 새로운 방식을 개발하였으며, 이는 완벽한 스케줄링을 가로막는 장애물을 이해하는 방식을 변화시켰습니다. 연구진은 이 문제를 네 가지 서로 다른 변수가 얽힌 복잡한 그물망으로 취급하는 대신, 전체 상황을 더 단순한 2차원적 관점으로 압축하는 방법을 찾아냈습니다. 기계가 유휴 상태로 있는 시간을 '음의 대기 시간(negative waiting time)'의 한 형태로 취급함으로써, 그들은 대기와 유휴라는 개념을 하나의 프레임워크로 통합했습니다. 이러한 전환을 통해 그들은 문제의 구조를 훨씬 더 명확하게 파악할 수 있었습니다. 그들은 스케줄이 아직 완벽하지 않은 이유가 대개 '큐 불연속성(queue discontinuity)'이라 부르는 특정한 구조적 흐름의 단절 때문이라는 것을 발견했습니다. 이는 기계가 새로운 과업을 기다리느라 작동을 멈춤으로써, 작업의 연속적인 사슬을 효과적으로 끊어버릴 때 발생합니다.

연구진은 아직 최적이 아닌 모든 스케줄에 대해, 더 나은 스케줄로 나아갈 수 있는 명확한 이론적 경로가 존재함을 증명했습니다. 그들은 이러한 경로를 '이상적인 방향(ideal directions)'이라고 정의했는데, 이는 최적의 순서에 도달하기 위해 필요한 구체적인 움직임을 나타냅니다. 그러나 그들은 이러한 이상적인 움직임이 바로 그들이 만들어낸 큐 불연속성에 의해 종종 차단된다는 사실도 발견했습니다. 과업을 더 나은 위치로 옮길 때, 그것이 결과적으로 시퀀스의 나중에 기계를 다시 멈추게 하여 이득을 상쇄해 버릴 수 있기 때문입니다. 연구진은 이러한 차단 현상이 무작위로 발생하는 것이 아니라, 오직 스케줄의 개선을 막고 있는 유일한 요소임을 보여주었습니다. 결정적으로, 이러한 차단 문제는 복잡하고 조율된 해결책을 필요로 하지 않는다는 점을 입증했습니다. 각 문제는 독립적인 단위로서 스스로 수리될 수 있습니다.

이를 해결하기 위해 저자들은 완벽한 스케줄을 찾는 것이 보장되는 단계별 절차인 정밀 알고리즘(exact algorithm)을 설계했습니다. 이 방법은 이러한 구조적 단절을 반복적으로 식별하고, 이를 해결하기 위한 구체적인 수리 규칙을 적용하는 방식으로 작동합니다. 만약 어떤 움직임이 단절을 일으키면, 알고리즘은 새로운 단절을 만들지 않으면서 기존의 단절을 수리할 수 있는 다른 과업을 교체하여 투입합니다. 연구진은 이 과정이 반드시 유한한 단계 내에 종료되며 결코 루프(loop)에 빠지지 않을 것임을 증명했습니다. 국소 최적해(local solution)—즉, 최선은 아니지만 좋아 보이는 상태—에 갇힐 수 있는 기존의 방식들과 달리, 이 프레임워크는 스케줄이 전역 최적해(global optimum), 즉 단 하나의 가장 완벽한 배열에 도달할 때까지 계속해서 개선되도록 보장합니다. 이 연구는 완벽한 스케줄을 찾을 수 있다는 엄격한 수학적 보장을 제공하며, 겉보기에 불가능해 보이는 퍼즐을 논리적인 수리의 연속적인 과정으로 바꾸어 놓는 새로운 분석적 관점을 제시합니다.