Quantum Annealing for Staff Scheduling in Educational Environments

기술 요약: 교육 환경의 직원 스케줄링을 위한 양자 어닐링

문제 정의
본 연구는 이탈리아 공립 학교 시스템에 특화된 복잡한 직원 배정 문제를 다루며, 비교과 학교 협력자들의 스케줄링에 초점을 맞춥니다. 이 문제는 세 개의 자치구에 분포된 여러 교육 시설 (유치원, 초등학교, 중학교) 에 걸쳐 이질적인 노동력 (전일제 및 파트타임 직원, 남성과 여성) 을 배정하는 것을 포함합니다. 계획 기간은 오전 및 오후 교대 근무가 있는 표준 5 일 근무 주를 포괄합니다.

이 문제는 다음과 같은 밀집된 운영 및 규제 제약 조건을 특징으로 합니다:

• 커버리지: 모든 시설의 모든 활성 교대 근무는 최소 한 명의 협력자에 의해 충원되어야 합니다.
• 근무 시간 제한: 전일제 직원의 주당 근무 시간은 36 시간, 파트타임 직원은 18 시간으로 제한됩니다.
• 휴식 규칙: 일일 근무 시간이 7.2 시간을 초과할 경우 30 분의 의무 휴식이 필요합니다.
• 성별 제약: 모든 유치원 시설에는 최소 한 명의 여성 협력자가 배정되어야 합니다.
• 연속성 및 선호도: 직원은 특정 시설로의 배정을 의무화하는 구속 조건이나 권장되지만 필수 요건은 아닌 시설 배정에 대한 선호 조건을 가질 수 있습니다.
• 목적: 세 가지 기준을 균형 있게 조정하여 갈등을 최소화하는 것입니다: 다중 시설 배정을 줄여 통근을 제한하고 연속성을 보장하며, 계약상 주당 근무 시간에서의 편차를 최소화하고 직원의 시설 선호도를 존중합니다.

방법론
저자들은 이 문제를 제약 이차 모델 (CQM) 인 조합 최적화 모델로 공식화합니다. 수학적 공식화에는 다음이 포함됩니다:

• 결정 변수: 일일 교대 근무 배정을 위한 이진 변수 ($x_{c,s,d,j}$), 주별 시설 지표 ($y_{c,s}$), 그리고 휴식 지표 ($b_{c,d}$).
• 목적 함수: 세 가지 정규화된 구성 요소의 가중 합:
  1. 다중 시설 근무에 대한 패널티.
  2. 표준 주당 근무 시간에서의 편차에 대한 패널티.
  3. 비선호 시설 배정에 대한 패널티.
• 제약 조건: 선형 제약 조건은 커버리지, 일일 단일 교대 근무 제한, 근무 시간 상한, 성별 요구 사항, 그리고 일일 및 주별 변수 간의 논리적 일관성을 강제합니다.

이 NP-하드 문제를 해결하기 위해 저자들은 D-Wave 의 LeapCQMHybrid 솔버를 사용하여 **양자 어닐링 (QA)**을 적용합니다. 이 하이브리드 접근법은 중첩과 터널링을 활용하는 양자 유도 탐색과 고전적 휴리스틱 기법을 결합하여 해 공간에서 탐색합니다. 실험은 4596 큐비트의 D-Wave Advantage2 시스템에서 수행되었으며, 정확한 Gurobi Optimizer 와 비교되었습니다.

주요 기여

1. 새로운 적용: 이는 이탈리아의 학교 협력자를 위한 구체적인 최적화 모델을 제안한 최초의 연구로, 유치원의 성별 요구 사항 및 다중 캠퍼스 관리와 같은 이 맥락의 고유한 조직적, 공간적, 규제적 특수성을 다루고 있습니다.
2. 실제 사례 연구: 이 모델은 9 개 시설에 걸쳐 있는 20 명의 협력자를 포함하는 Istituto Comprensivo di Cerisano의 실제 데이터를 사용하여 테스트되었습니다.
3. 확장성 분석: 저자들은 구체적인 사례 연구를 넘어 양자 영감 접근법의 견고성과 확장성을 평가하기 위해 더 큰 합성 인스턴스 (최대 40 명까지 확장) 를 생성했습니다.
4. CQM 공식화: 이 작업은 비산업적 공공 부문 환경에서 선형 제약 조건이 있는 혼합 정수 문제에 대한 D-Wave 의 CQM 프레임워크의 실용적 적용을 보여줍니다.

결과

• 실제 인스턴스 (20 명 협력자): LeapCQMHybrid 솔버는 5 회 독립 실행에서 일관되게 최적 해 (Gurobi 로 검증됨) 에 도달했습니다. 목적 함수 값은 0.070602 이었으며, 평균 실행 시간은 약 15.16 초였습니다. 이러한 결과는 모든 제약을 준수하는 균형 잡힌 실현 가능한 스케줄을 생성할 수 있는 모델의 능력을 확인시켜 주었습니다.
• 대규모 인스턴스:
  • 25 명 및 30 명의 협력자의 경우, 솔버는 일관되게 최적 해를 발견했습니다 (100% 성공률).
  • 35 명의 협력자의 경우, 솔버는 고품질 해를 찾았지만 20% 의 실행에서만 진정한 최적 해에 도달하여 증가된 난이도를 나타냈습니다.
  • 40 명의 협력자의 경우, 솔버는 10 초 시간 제한 내에 실현 가능한 해를 생성하지 못하여 매우 큰 인스턴스에 대한 현재 확장성 한계를 강조했습니다.

의의 및 주장
이 논문은 양자 어닐링 기반 하이브리드 최적화 방법이 교육 스케줄링의 복잡한 조합 문제에 실용적으로 적용 가능하다고 주장합니다. 결과는 이러한 방법들이 중간 규모의 실제 인스턴스에 대해 짧은 실행 시간 내에 균형 잡힌 배치를 생성할 수 있음을 보여주는 증거를 제공합니다.

저자들은 이 작업을 이론적 양자 최적화 연구와 실제 조직 계획 간의 격차를 해소하는 단계로 위치시킵니다. 그들은 대규모 인스턴스에 대한 중요한 과제가 남아 있지만, 제안된 접근 방식이 전통적인 산업 영역을 넘어 양자 컴퓨팅 기법의 다양성을 입증한다고 강조합니다. 이 연구는 정확한 방법이 비실용적이 되는 자원 배분 작업에 대해 하이브리드 양자 영감 솔버가 경쟁력 있는 대안을 제공한다고 결론지으며, 현재 하드웨어의 한계가 추가적인 알고리즘 또는 아키텍처 발전 없이는 매우 대규모 인스턴스의 해를 제한한다는 점을 겸손하게 인정합니다.