Task Scheduling Optimization with Direct Constraints from a Tensor Network Perspective

본 논문은 지시된 제약 조건 하에서 산업 공장의 작업 일정을 최적화하고 실행 비용을 최소화하기 위한 정확한 해법을 제공하는 새로운 양자 영감을 받은 텐서 네트워크 방법을 소개하며, 이는 계산 복잡성을 줄이기 위해 세 가지 고유한 알고리즘과 공개된 구현을 특징으로 합니다.

핵심

이 글은 간단한 언어와 일상적인 비유를 사용하여 해당 논문을 설명한 것입니다.

큰 그림: 공장 퍼즐

드릴, 용접기, 페인팅기 등 여러 대의 기계가 있는 분주한 공장을 상상해 보세요. 각 기계는 수행할 수 있는 다양한 작업 목록을 가지고 있으며, 각 작업은 서로 다른 시간이 소요됩니다.

목표는 모든 기계에 하나씩 작업을 할당하여 전체 작업 완료 시간을 가능한 한 짧게 만드는 것입니다.

하지만 함정이 하나 있습니다. 기계들은 다른 기계들이 무엇을 하고 있는지에 따라 할 수 있는 작업에 대한 규칙이 있습니다.

• 규칙 예시: "기계 A 가 드릴을 뚫고 있다면, 기계 B 는 반드시 페인팅을 해야 합니다. 하지만 기계 A 가 용접을 하고 있다면, 기계 B 는 페인팅을 할 수 없습니다."

이는 고전적인 '스케줄링 퍼즐'입니다. 기계가 너무 많고 규칙이 너무 많다면, 모든 가능성을 하나씩 확인하여 완벽한 일정을 찾는 것은 해변의 모래알 하나하나를 하나씩 살펴보다가 특정 모래알을 찾는 것과 같습니다. 끝없이 시간이 걸립니다.

새로운 해결책: '양자 영감' 지도

이 논문의 저자들은 이 퍼즐을 해결하는 새로운 방법을 개발했습니다. 그들은 아직 매우 노이즈가 많고 실험적인 단계인 실제 양자 컴퓨터를 사용하지 않았습니다. 대신 **텐서 네트워크 (Tensor Networks)**를 사용했습니다.

텐서 네트워크를 모든 기계와 규칙을 연결하는 거대한 다차원 지도나 흐름도로 생각하세요.

• 지도: 한 번에 하나의 일정을 확인하는 대신, 이 지도는 모든 가능한 일정을 한 번에 표현합니다.
• 규칙: 그들은 지도 안에 특별한 '문지기'를 만들었습니다. 일정 (위의 드릴/페인팅 규칙과 같은) 이 규칙을 위반하면, 문지기가 문을 닫아 해당 경로의 값을 0 으로 만듭니다.
• 비용: 지도는 설계상 '최고의'(가장 빠른) 일정이 가장 밝게 빛나고, 느린 일정은 어둡게 보이도록 만들어졌습니다.

이 지도를 보면 컴퓨터는 모든 경로를 하나씩 걸어보지 않고도 가장 밝은 경로 (최고의 해결책) 가 무엇인지 즉시 확인할 수 있습니다.

어떻게 더 빠르게 만들었는지 ('응축' 트릭)

실제 공장을 위한 이 거대한 지도를 만드는 것은 여전히 일반 컴퓨터에게는 너무 무겁습니다. 메모리가 부족해질 것입니다. 따라서 저자들은 몇 가지 '압축' 트릭을 추가했습니다.

1. 전처리 (공구함 정리): 지도를 만들기 전에 기계들을 재배열했습니다. 서로 자주 소통하는 기계들을 지도에서 서로 바로 옆에 배치했습니다. 이렇게 하면 기계들을 연결하는 데 필요한 '와이어' 수가 줄어들어 지도가 작아집니다.
2. 규칙 그룹화 (묶음 거래): 100 개의 규칙을 하나씩 확인하는 대신, 이를 묶을 수 있는 방법을 찾았습니다. 100 개의 신호등이 있다고 가정해 보세요. 각각을 개별적으로 확인하는 대신, 모두를 한 번에 통제하는 단일 '교통 구역'으로 그룹화합니다. 이렇게 하면 지도의 크기가 극적으로 줄어듭니다.
3. 스마트 추출 (탐정): 지도가 완성되면 전체를 한 번에 보지 않습니다. 먼저 기계 1 의 작업을 파악합니다. 기계 1 의 작업이 결정되면, 다른 기계들에게 더 이상 관련이 없는 모든 규칙을 삭제할 수 있습니다. 크로스워드 퍼즐을 푸는 것과 같습니다. 첫 번째 단어를 채우면 다음 단어에 대한 불가능한 글자들을 지울 수 있습니다.

테스트한 세 가지 알고리즘

이 논문은 이 지도를 사용하는 세 가지 방법을 제시합니다.

1. 주요 알고리즘 (정확한 솔버): 이 방법은 전체 지도를 구축하여 수학적으로 완벽한 답을 찾습니다. 작은 문제에는 잘 작동하지만, 거대한 문제에는 너무 느려집니다.
2. 반복 알고리즘 ('단계별' 솔버): 이것이 이 방법의 주인공입니다. 모든 규칙을 한 번에 지도에 올리는 대신, 처음에는 몇 개만 넣습니다.
   • 해결책을 찾습니다.
   • 그 해결책이 규칙을 위반하면, 그 규칙 하나만 지도에 추가하고 다시 시도합니다.
   • 해결책이 완벽해질 때까지 규칙을 하나씩 추가해 나갑니다.
   • 결과: 테스트에서 이 방법은 종종 모든 규칙을 확인할 필요가 없었기 때문에 주요 알고리즘보다 훨씬 빨랐습니다.
3. 유전 알고리즘 ('시행착오' 솔버): 진화를 모방하도록 설계되었습니다. 무작위 일정들을 여러 개 생성하고, 좋은 것들을 유지하며, 이를 섞은 후 다시 시도합니다.
   • 결과: 저자들은 이 특정 유형의 공장 문제에 대해서는 이 방법이 잘 작동하지 않았다고 발견했습니다. 다른 두 가지 방법에 비해 유효한 일정을 찾는 데 어려움을 겪었습니다.

그들이 발견한 것

• 성공: '반복' 방식이 매우 잘 작동했습니다. 최고의 일정을 찾기 위해 모든 규칙을 확인할 필요가 종종 없다는 것을 증명했습니다.
• 한계: 이러한 트릭이 있더라도 공장이 매우 크고 규칙이 극도로 복잡하면 컴퓨터는 여전히 압도당합니다. 최악의 상황에서는 문제를 해결하는 데 걸리는 시간이 여전히 매우 빠르게 (지수적으로) 증가할 수 있습니다.
• 가용성: 저자들은 코드를 Python 으로 작성하여 GitHub 에서 누구나 무료로 사용할 수 있도록 공개했습니다.

요약

이 논문은 공장 스케줄링 문제를 해결하기 위해 '양자 영감' 지도를 사용하는 교묘한 방법을 소개합니다. 규칙을 지능적으로 조직하고 필요할 때만 하나씩 추가함으로써 이전보다 훨씬 빠르게 최적의 일정을 찾을 수 있습니다. 이는 모든 가능한 문제에 대한 만능 해결책은 아니지만, 산업 계획 분야에서 중요한 진전입니다.

기술 요약

"텐서 네트워크 관점에서의 직접적 제약 조건을 활용한 작업 스케줄링 최적화" 논문의 상세한 기술적 요약은 다음과 같습니다.

1. 문제 정의

이 논문은 산업 환경에서의 **지향적 제약 조건 작업 스케줄링 문제 (Directed Constraint Task Scheduling Problem)**를 다룹니다. 목표는 $m$개의 머신 집합 내의 각 머신에 특정 작업을 할당하여 다음 조건을 만족하는 것입니다:

• 목적: 총 실행 비용 (개별 작업 실행 시간의 합) 을 최소화합니다.
• 제약 조건: 할당은 일련의 지향적 논리적 제약 조건을 만족해야 합니다. 이러한 조건들은 "머신 0 이 작업 A 를 수행하고 머신 1 이 작업 B 를 수행한다면, 머신 2 는 반드시 작업 C 를 수행해야 한다"와 같은 조건부 규칙입니다.
• 복잡도: 이는 머신과 작업의 수에 따라 검색 공간이 기하급수적으로 확장되는 조합 최적화 문제 (NP-하드) 입니다. 전통적인 정확한 방법들 (정수 계획법 등) 은 확장성에서 어려움을 겪는 반면, 휴리스틱 방법들 (유전 알고리즘 등) 은 최적성이나 실행 가능성을 보장하지 못하는 경우가 많습니다.

2. 방법론: DCTSTN 접근법

저자들은 **지향적 제약 조건 작업 스케줄러 텐서 네트워크 솔버 (DCTSTN)**를 제안합니다. 이는 양자에서 영감을 받은 고전 알고리즘으로, **텐서 네트워크 (TN)**를 활용하여 해 공간과 제약 조건을 명시적으로 표현합니다.

A. 핵심 수학적 공식화

문제는 모든 가능한 작업 조합을 인코딩하는 텐서 네트워크로 매핑됩니다.

1. 초기화 및 비용 인코딩:
   • 초기 균일 텐서 $\psi_0$는 모든 가능한 작업 조합을 나타냅니다.
   • 비용에 따라 가중치를 부여하기 위해 허수 시간 진화 (imaginary time evolution) 연산자가 적용됩니다: $\psi_1 \propto e^{-\tau C(\vec{x})}$. 여기서 $\tau$는 감쇠 상수입니다. 비용이 낮은 조합은 기하급수적으로 더 큰 진폭을 부여받습니다.
2. 제약 조건 강제:
   • 제약 조건은 **프로젝터 레이어 (행렬 곱 연산자 - MPO)**로 구현됩니다.
   • 특정 텐서 유형 ($Ctrl, Cctrl, cProj, CcProj, Id$) 이 네트워크를 통해 "신호"를 전파하는 데 사용됩니다. 조건이 충족되면 신호가 통과하고, 그렇지 않으면 불일치하는 상태의 진폭이 0 으로 투영됩니다.
   • 이로 인해 최종 텐서 $\psi_2$가 생성되는데, 여기서 0 이 아닌 요소들은 비용으로 가중치가 부여된 유효한 제약 조건 만족 조합에 유일하게 해당합니다.
3. 해 추출:
   • 최적 해는 텐서 내 최대 요소의 위치를 식별함으로써 찾아집니다.
   • 이는 **반쪽 부분 트레이스 (Half Partial Traces)**를 통해 달성됩니다. 하나의 인덱스를 제외한 모든 인덱스에 대해 합산함으로써, 특정 머신에 대한 각 작업의 주변 확률을 결정합니다.
   • 정리 1은 $\tau \to \infty$로 갈 때, 주변 분포의 argmax 가 고유한 전역 최소 비용 해로 수렴함을 증명합니다.

B. 실용적 계산을 위한 최적화

텐서 수축의 기하급수적 확장을 완화하기 위해 저자들은 여러 압축 및 전처리 기법을 도입했습니다:

• 전처리: 비용의 정규화 및 머신 재배열을 통해 제약 조건에 자주 등장하는 머신들을 그룹화하여 네트워크의 "본드 차원 (연결성)"을 최소화합니다.
• 제약 조건 응축: 여러 제약 조건을 단일 MPO 레이어로 병합합니다. 조건부 머신을 공유하는 제약 조건들을 그룹화함으로써 본드 차원을 $d$개의 제약 조건에 대해 $2^d$에서 $d+1$로 줄여 메모리 요구 사항을 크게 낮춥니다.
• 반복적 변수 결정: 모든 변수에 대해 전체 네트워크를 수축하는 대신, 알고리즘은 변수를 순차적으로 결정합니다. 한 번 변수가 고정되면, 이에 의존하는 제약 조건은 단순화되거나 제거되어 후속 단계에서 네트워크 크기가 축소됩니다.

C. 제안된 알고리즘

논문은 세 가지 계산적 접근법을 제시합니다:

1. 주 알고리즘 (정확): 모든 제약 조건을 포함한 전체 텐서 네트워크를 구성하고 수축을 수행합니다. 정확한 최적해를 보장하지만 최악의 경우 복잡도가 높습니다.
2. 반복 알고리즘 (근사/정확 하이브리드): 완화된 문제 (적은 수의 제약 조건) 로 시작합니다. 해가 원래 모든 제약 조건을 만족할 때까지 필요한 최소한의 제약 조건을 반복적으로 추가합니다. 이는 많은 실제 시나리오에서 최적 해에 실제로 활성화되는 제약 조건이 부분집합에 불과하다는 사실에 기반합니다.
3. 유전 알고리즘 (하이브리드): 반복적 텐서 방법과 유전 알고리즘을 결합합니다. "부분 문제" (축소된 작업 집합 및 제약 조건) 의 집단을 진화시켜 각 부분 문제를 텐서 네트워크를 사용하여 해결합니다.

3. 주요 기여

• 정확한 텐서 방정식: 지향적 제약 조건을 가진 최소 비용 스케줄링 문제를 정확하게 해결하는 명시적인 텐서 네트워크 방정식을 유도했습니다.
• 새로운 제약 조건 레이어링: Grover 의 오라클에서 영감을 받았으나 고전 TN 에 맞게 적응된 논리적 함의를 텐서 네트워크 내에서 인코딩하기 위한 특수한 텐서 세트 ($Ctrl, Cctrl$ 등) 를 도입했습니다.
• 제약 조건 응축: 여러 제약 조건을 단일 텐서 레이어로 병합하여 본드 차원과 계산 복잡도를 제약 조건 수에 대해 기하급수적에서 선형으로 줄이는 기법 (균일 가정 하) 입니다.
• MeLoCoToN 의 첫 적용: 특정 텐서 네트워크 형식주의인 MeLoCoToN 프레임워크를 제약 최적화 문제에 적용한 최초의 연구입니다.
• 오픈 소스 구현: 저자들은 TensorNetwork 라이브러리를 사용한 공개 Python 구현과 Streamlit 애플리케이션을 제공합니다.

4. 실험 결과

알고리즘은 다양한 수의 머신, 작업, 제약 조건을 가진 시뮬레이션된 산업 인스턴스에서 테스트되었습니다.

• 반복 대 일반: 반복 알고리즘은 표준 전체 제약 조건 수축보다 훨씬 뛰어난 성능을 보였습니다. 최적 해를 작은 부분집합의 제약 조건으로 해결하는 경우가 많았기 때문에 솔버를 여러 번 호출해야 하더라도 훨씬 빨랐습니다.
• 확장성: 반복 방법의 실행 시간은 머신 수가 증가함에 따라 감소했습니다 (고정된 작업/제약 조건). 이는 더 큰 시스템일수록 제약 조건 제한이 느슨해지는 경향이 있기 때문입니다.
• 유전 알고리즘 성능: 하이브리드 유전 알고리즘은 성능이 저조했습니다. 많은 경우 호환 가능한 해를 찾지 못했으며, 이는 특정 텐서 네트워크 솔버와 유전 탐색의 결합이 추가적인 정교화가 필요함을 시사합니다.
• 매개변수 민감도: 감쇠 매개변수 $\tau$는 100 으로 설정되었으며, 이는 테스트된 인스턴스에서 최적 해를 비최적 해와 분리하기에 충분했습니다.

5. 의의 및 결론

• 산업적 관련성: 이 방법은 표준 휴리스틱으로 모델링하기 어려운 **지향적 제약 조건 (머신 간의 의존성)**을 가진 복잡한 스케줄링 문제를 해결할 수 있는 방법을 제공합니다.
• 양자에서 영감을 받은 이점: 고전 텐서 네트워크가 허수 시간 진화, 투영과 같은 양자 유사 과정을 시뮬레이션하여 NP-하드 문제를 효율적으로 해결할 수 있음을 보여주며, 실제 양자 하드웨어 (NISQ 한계) 가 필요하지 않음을 입증했습니다.
• 향후 방향: 저자들은 반복적 접근법이 유망하지만 유전적 결합은 개선이 필요하다고 제안합니다. 향후 작업에는 양방향 제약 조건으로 방법 확장, 행렬 곱 상태 (MPS) 압축 적용, 그리고 외판원 문제와 같은 다른 NP-하드 문제에 대한 테스트가 포함됩니다.

요약하자면, 이 논문은 양자에서 영감을 받은 텐서 네트워크와 고전 최적화를 연결하여, 본래 처리하기 어려운 제약 조건이 있는 조합 문제에 대한 정확한 해를 위한 실현 가능한 경로를 제공하는 엄격하고 수학적으로 근거 있는 산업 작업 스케줄링 프레임워크를 제공합니다.