Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

기술 요약: 양자 어닐링을 이용한 모직물 산업의 분산형 유연 직업 숍 스케줄링 문제 해결

문제 정의
본 논문은 모직물 산업의 맥락에서 분산형 유연 직업 숍 스케줄링 문제(Distributed Flexible Job Shop Scheduling Problem, DFJSP)를 다룹ون다. 전통적인 직업 숍 스케줄링 문제(JSSP)나 일반적인 유연 직업 숍 스케줄링 문제(FJSP)와 달리, DFJSP는 지리적으로 분산된 생산 사이트를 포함하며, 단일 생산 주문(job)이 여러 공장에서 수행되어야 하는 작업을 가질 수 있다. 실제 모직물 제조 기업에서 도출된 이 특정 사례는 독특한 복잡성을 도입한다. 즉, 생산 주문이 여러 사이트에 분산되어 있을 뿐만 아니라, 단일 작업의 개별 생산 단계(operation) 또한 분산될 수 있다는 점이다. 결과적으로 모델은 표준 처리 시간 및 기계 제약 조건 외에도 서로 다른 공장에 위치한 기계 간의 운송 시간을 고려해야 한다. 목적 함수는 선행 제약 조건을 충족하고, 작업이 한 번만 시작되도록 보장하며, 기계 중복을 방지하면서 메이크스팬(makespan, 총 완료 시간)을 최소화하는 것이다. 이 문제는 NP-hard로 식별되며, 공장 간 운송 시간의 포함은 조합적 복잡성을 크게 증가시킨다.

방법론
저자들은 확장된 DFJSP를 D-Wave Advantage System 4.1 양자 어닐러(QPU)를 사용하여 해결하기 위해 이차 무제약 이진 최적화(Quadratic Unconstrained Binary Optimization, QUBO) 문제로 정식화한다.

1. QUBO 정식화: 문제를 작업 $i$의 작업 $o$가 시간 $t$에 기계 $m$에서 시작되는지를 나타내는 이진 변수 $x_{i,o,m,t}$로 매핑한다. 비용 함수 $H(x)$는 제약 조건(선행, 작업 1회 수행, 중복 방지)에 대한 페널티 함수와 메이크스팬 최소화를 위한 목적 함수의 가중 합으로 구성된다.
2. 변수 가지치기(Variable Pruning): QPU의 물리적 한계 내에서 문제 크기를 관리하기 위해, 저자들은 최소 선행 시간과 최대 메이크스팬 제한을 기반으로 작업 시작 시간의 하한 및 상한을 계산하여 유효하지 않은 스케줄에 해당하는 이진 변수를 제거하는 변수 가지치기를 적용한다.
3. 파라미터 결정: 중요한 방법론적 단계는 제약 항을 위한 라그랑주 파라미터($\alpha, \beta, \gamma$)를 체계적으로 계산하는 것이다. 시행착오에 의존하는 대신, 저자들은 특정 문제 인스턴스의 최대 가능한 메이크스팬($t_{max}$)을 기반으로 이 가중치들을 수학적으로 도출한다. 이는 유효한 솔루션의 에너지가 유효하지 않은 솔루션의 에너지보다 낮음을 보장한다.
4. 임베딩 및 구성: 논리적 QUBO 변수는 체인(chain) 형태의 큐비트를 사용하여 물리적 QPU 토폴로지에 임베딩된다. 저자들은 솔루션 품질에 미치는 "체인 강도"(체인 내 큐비트 간 결합 강도)의 영향을 조사하였으며, 시스템 에너지와 끊어진 체인의 비율 사이의 트레이드오프를 분석하여 최적값을 결정하였다.
5. 비교: 양자 어닐링(QA) 결과는 D-Wave Ocean SDK를 사용한 시뮬레이티드 어닐링(SA)과 벤치마킹된다. 두 방법 모두 테스트된 QPU에서 임베딩 가능한 최대 크기인 50~250개의 변수를 가진 문제 인스턴스에 대해 테스트되었으며, SA는 기준선을 설정하기 위해 더 큰 인스턴스(최대 400개 변수)까지 테스트되었다.

주요 기여
본 논문은 세 가지 주요 기여를 제시한다:

1. QA를 적용한 확장된 DFJSP 모델: 저자들은 생산 주문과 개별 생산 단계가 모두 여러 공장에 분산되어 있고, 공장 간 운송 시간을 명시적으로 모델링한 확장된 DFJSP에 양자 어닐링을 적용한 첫 사례를 제시한다.
2. 체계적인 파라미터 계산: 본 논문은 시행착오 방식의 휴리스틱 접근법에서 벗어나, 문제의 수학적 정식화에 기반하여 라그랑주 파라미터와 QPU 구성 설정(특히 체인 강도)을 결정하는 방법을 상세히 설명한다.
3. 경제적 및 성능 평가: 연구는 산업 특화형 분산 스케줄링을 위한 QA 사용의 잠재적 속도 이점을 평가하며, 솔루션 품질과 계산 시간을 고전적 SA와 비교한다.

결과

• 솔루션 품질: 최대 150개의 변수를 가진 문제 인스턴스에 대해 QA는 일관되고 유효한 솔루션(제약 위반 없음)을 생성했으나, 시뮬레이티드 어닐링(SA)이 일반적으로 약간 더 낮은 에너지(더 나은 최적성)를 가진 솔루션을 반환했다. 문제 크기가 200 및 250개 변수로 증가함에 따라, QA 솔루션은 깨진 제약 조건(각각 1개 및 2개의 위반)을 나타내기 시작했으며, 이는 더 높은 에너지 값으로 이어졌다. 이러한 저하는 물리적 QPU 그래프에 더 큰 논리적 문제를 임베딩하는 난이도가 높아짐에 따라 체인이 길어지고 체인 단절율이 높아지는 것에 기인한다.
• 메이크스팬: 대부분의 문제 크기에 대해 QA 솔루션은 가능한 메이크스팬 범위의 하위 절반에 위치하여 실행 가능한 생산 스케줄임을 보여주었다. 그러나 250개 변수 인스턴스의 경우, 메이크스팬은 상위 절반에 위치했다.
• 계산 시간: SA는 작은 문제 인스턴스에서 더 빠른 계산 시간을 보여주었다. 그러나 SA의 CPU 시간은 문제 크기에 따라 기하급수적으로 증가했다. 반면, QA의 QPU 액세스 시간은 감소하는 비율(로그 속도)로 증가했다. 현재 하드웨어는 QA를 250개 변수까지의 임베딩 문제로 제한하고 있지만, 이 추세는 더 큰 인스턴스(300개 변수 이상으로 외삽 시)에 대해 QA가 SA에 비해 상당한 속도 이점을 제공할 수 있음을 시사한다.

의의 및 주장
본 논문은 현재의 양자 어닐링 하드웨어가 대규모 문제를 임베딩하고 소규모 인스턴스에 대한 고전적 휴리스틱에 비해 전역 최솟값(global minima)을 달하는 데 한계가 있지만, 모직물 산업의 특정 DFJSP 과제에 대해 상당한 잠재력을 가지고 있다고 주장한다. 저자들은 QA가 문제 크기에 따른 유리한 계산 시간 스케일링 덕분에 대규모 분산 스형 스케줄링을 위한 유망한 대안을 제공한다고 단언한다. 저자들은 향-후 하드웨어 개선(더 많은 큐비트, 더 나은 연결성 및 안정성)과 함께, QA가 약 300개 이상의 변수를 가진 문제 인스턴스에 대해 결정적인 속도 향상 이점을 제공함으로써 복잡한 실제 다중 공장 생산 계획을 위한 실행 가능한 도구가 될 수 있다고 결론짓는다. 본 연구는 QA의 성공적인 적용이 페널티 가중치의 수학적 도출 및 임베딩 파라미터 최적화와 같은 세심한 문제 정식화에 크게 의존함을 강조한다.