Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

기술 요약: 시간대별 에너지 요금제(TOU) 및 기계 상태를 고려한 자원 제약 프로젝트 스케줄링

1. 문제 정의

본 논문은 시간대별(Time-of-Use, TOU) 에너지 요금제와 기계 상태 전이를 통합한 **자원 제약 프로젝트 스케줄링 문제(RCPSP)**의 변형 모델을 다룬다. 이 문제는 선행 관계 제약 조건과 제한된 자원 용량 하에서 비선점(non-preemptive) 작업들을 스케줄링하는 문제를 포함한다.

주요 특징은 다음과 같다:

• 에너지 집약적 자원: 특정 자원($R_0$)은 단위 용량을 가지며 에너지 집약적이다. 이 자원은 가동(proc), 대기(idle), 또는 **정지(off)**의 세 가지 상태로 존재할 수 있다.
• 상태 전이: 상태 간의 전이는 특정 소요 시간과 에너지 비용을 발생시킨다. 예를 들어, 기계를 켜거나 끄는 것은 상당한 에너지와 시간을 소비한다. 기계는 반드시 off 상태에서 시작하고 종료되어야 한다.
• 작업 분류: 작업은 에너지 집약적 작업(가동 상태인 $R_0$를 필요로 함)과 비에너지 집약적 작업( $R_0$를 사용하지 않음)으로 나뉜다.
• 목적 함수: 목표는 **총 에너지 비용(TEC)**과 **메이크스팬(Makespan, $C_{max}$)**의 볼록 결합(convex combination)을 최소화하는 것이다. TEC는 시간에 따라 변하며 심지어 음수 값을 가질 수도 있는 TOU 요금제를 기준으로 계산된다. 목적 함수는 TEC와 $C_{max}$의 독립적인 최적화를 통해 도출된 하한값을 사용하여 정규화된다.

2. 방법론

저자들은 세 가지 서로 다른 모델링 접근 방식을 제안하고 비교한다:

A. 단일 모델 (Monolithic Models)
문제를 전체적으로 해결하기 위해 두 가지 압축된 모델이 공식화된다:

1. 단일 ILP (Monolithic ILP): 시간 인덱스 변수를 사용하는 정수 선형 계획법(Integer Linear Programming) 모델이다. 기계 상태를 처리하기 위해 가동 구간 사이의 사전 계산된 최적 전이 비용(SPACES 알고리즘 활용)을 포함한다.
2. 단일 CP (Monolithic CP): 선택적 구간 변수(optional interval variables)를 활용하는 제약 프로그래밍(Constraint Programming) 모델이다. 이 방식은 작업 처리와 최적의 상태 전이를 구간 변수로 표현하여, 솔버가 전이의 횟수와 배치를 동적으로 결정할 수 있게 한다.

B. 논리 기반 벤더스 분해 (Logic-Based Benders Decomposition, LBBD)
주요 기여는 문제를 두 개의 결합된 하위 문제로 분해하는 하이브리드 LBBD 접근법이다:

• 마스터 문제 (Master Problem, ILP): 기계 상태 및 에너지 비용 최적화를 해결한다. 이는 에너지 집약적 작업의 시작 시점과 상태 전이의 순서를 결정한다. 전이 비용을 계산하기 위해 수정된 SPACES 그래프를 활용한다.
• 하위 문제 (Subproblem, CP): RCPSP 구성 요소에 대한 타당성 검사(feasibility check)를 수행한다. 마스터 단계에서 고정된 에너지 집약적 작업의 시작 시점을 바탕으로, 자원 용량과 선행 관계 제약을 준수하면서 나머지 비에너지 집약적 작업들을 스케줄링할 수 있는지 확인한다.
• 절단 평면 (Cutting Planes):
  • 타당성 컷 (Feasibility Cuts): 하위 문제가 불가능할 때 생성되며, 마스터가 동일하게 충돌하는 에너지 집약적 작업의 시작 시점 집합을 다시 선택하지 않도록 방지한다.
  • 최적성 컷 (Optimality Cuts): 하위 문제가 가능하지만 마스터의 추정치와 다른 메이크스팬을 산출할 때 생성된다. 이 컷은 리소스-플로우 그래프의 임계 경로(critical path)를 사용하여 마스터 문제에 메이크스팬의 하한을 강제한다.

3. 주요 기여

1. 문제 공식화: 기계 상태 역학(proc, idle, off)을 TOU 요금제와 결합한 새로운 RCPSP 변형 모델을 도입하였으며, 이는 기존의 단일 기계 연구를 다중 자원 프로젝트 스케줄링 맥락으로 확장한 것이다.
2. 새로운 LBBD 프레임워크: 에너지 관리(마스터)와 조합적 스케줄링(하위 문제)을 분리하는 분해 전략을 개발하였다. 저자들은 기계 상태와 RCPSP 제약 간의 상호작용에 특화된 특정 벤더스 컷을 도출하였다.
3. 일반화: 제안된 LBBD 아키텍처가 다음과 같은 다른 스케줄링 문제에도 적용 가능함을 입증하였다:
   • 블로킹 시간(blocking times)과 총 가중 완료 시간(total weighted tardiness) 목적 함수를 가진 RCPSP.
   • 유연한 작업 숍 스케줄링(Flexible Job Shop Scheduling, FJSS).

4. 실험 결과

실험은 에너지 집약적 작업의 밀도(Sparse, Standard, Dense)와 에너지 비용과 메이크스팬 사이의 가중치 매개변수($\alpha$)를 달리하여 PSPLLIB 데이터셋에서 파생된 인스턴스들을 대상으로 수행되었다.

• 단일 모델과의 성능 비교:
  • 두 가지 단일 모델(ILP 및 CP) 모두 LBBD에 의해 성능이 뒤처졌으며, 특히 대규모 인스턴스(최대 480개 작업)와 메이크스팬 기준이 덜 지배적일 때($\alpha \to 1$) 그러했다.
  • LBBD 방식은 단일 CP보다 훨씬 빠르게 최적해에 도달하였는데, 단일 CP는 거대한 탐색 공간으로 인해 어려움을 겪었다.
  • 단일 ILP는 준수한 성능을 보였으나 일반적으로 LBBD보다 느렸다.
• 매개변수의 영향:
  • $\alpha = 1$ (에너지 전용): LBBD는 매우 뛰어난 성능을 보였다. 이는 하위 문제가 순수 타당성 검사로 축소되어 CP 솔버가 효율적으로 처리할 수 있기 때문이다.
  • $\alpha < 1$ (혼합 목적 함수): LBBD는 Standard 및 Dense 인스턴스에서 우위를 유지했다. 그러나 낮은 $\alpha$ (높은 메이크스팬 가중치)를 가진 Sparse 인스턴스에서는 LBBD의 하위 문제 시간 제한이 탐색 공간 확장을 저해할 수 있어, 단일 CP가 LBBD보다 나은 성능을 보이기도 했다.
• 일반화 결과:
  • 블로킹 시간이 있는 RCPSP에서 LBBD는 30분 이내에 인스턴스의 거의 90%에 대해 최적해를 찾아낸 반면, 단일 CP는 5% 미만에 그쳤다.
  • 유연한 작업 숍(FJSP) 문제에서 LBBD는 시간 제한 내에 단일 ILP(120회 중 83회)보다 더 빈번하게(120회 중 107회) 실행 가능한 해를 찾아냈다.

5. 의의 및 주장

본 논문은 제안된 LBBD 접근법이 복잡한 기계 상태를 포함하는 에너지 인식 스케줄링 문제에 있어 중요한 진전을 의미한다고 주장한다. 핵심적인 의의는 연속적인 에너지 비용 최적화와 이산적인 조합 스케줄링 제약을 분리함으로써, 각 문제를 가장 적합한 솔버(에너지는 ILP, 스케줄링은 CP)로 해결할 수 있게 한 데 있다.

저자들은 이러한 분해 방식이 특정 RCPSP-TOU 문제에만 효과적인 것이 아니라, 에너지 집약적 활동을 나머지 자원 할당 로직과 분리할 수 있는 모든 스케줄링 문제에 적용 가능한 일반화된 프레임워크라고 강조한다. 본 연구는 단일 모델이 직관적이기는 하지만 규모와 복잡성이 커짐에 따라 실패하는 경우가 많은 반면, LBBD 방식은 다양한 인스턴스 밀도와 목적 함수 가중치 전반에 걸쳐 견고함을 유지한다는 점을 보여준다.

결론적으로, 향후 연구에서는 다중 에너지 집약적 자원, 더 복적인 상태 전이, 에너지 저장 장치 또는 온사이트 발전의 통합, 그리고 에너지 요금제의 불확실성에 미치는 영향 등을 탐구할 수 있을 것이라고 언급하였다.