https://www.sciencedirect.com/science/article/pii/S0925527322001001
Abstract
capital-intensive manufacturing industry에서는 energy-saving을 위해 생산성을 희생하는 것은 매력적이지 않다.
그러나 same productivity를 유지하면서도 energy-cost을 상당히 줄일 수 있을 가능성이 있다.
본 논문은 시간대별 요금제(Time-of-Use pricing)와 계획된 정지시간(scheduled downtime)을 고려한 flexible job shop scheduling 문제를 다루며, makespan과 총 에너지 비용을 최소화하는 것을 목표로 한다.
- 정수선형계획(Integer Linear Programming) 모델을 제안한다.
- 제약계획(Constraint Programming) 모델을 제안한다.
- 경영적 시사점을 도출한다.
실험 결과, 대규모 벤치마크 인스턴스에서 평균 6.9%의 에너지 비용을 절감하면서도 최대 생산성을 유지할 수 있음을 보여준다.
Introduction
제조업에서는 에너지 절감과 생산성 사이의 균형이 항상 중요한 문제로 여겨진다. 특히 자동차나 반도체와 같은 자본집약적인 산업에서는 생산성이 조금이라도 떨어질 경우 그 손실이 매우 크기 때문에, 에너지 절약을 위해 생산성을 희생하는 접근은 현실적으로 받아들여지기 어렵다. 이러한 배경에서 이 논문은 “생산성을 유지하면서도 에너지 비용을 줄일 수 있는가”라는 질문을 중심으로 문제를 설정한다.
논문에서는 시간대별로 전기요금이 달라지는 Time-of-Use(TOU) 환경을 고려한 유연 잡샵 스케줄링(Flexible Job Shop Scheduling Problem, FJSP)을 다룬다. FJSP는 각 작업이 여러 기계 중 하나에서 수행될 수 있기 때문에, 어떤 기계를 선택할지뿐만 아니라 작업의 순서와 시작 시점까지 동시에 결정해야 하는 복잡한 문제이다. 여기에 더해, 본 연구는 기계가 일정 시간 동안 사용 불가능한 scheduled downtime까지 반영하여 실제 생산 환경에 가까운 모델을 구성한다. 최종적으로는 전체 작업 완료 시간인 makespan과 총 에너지 비용을 동시에 최소화하는 것을 목표로 한다.
이 문제를 해결하기 위해 논문은 두 가지 접근법을 제안한다.
- 정수선형계획(ILP) 모델: 문제를 수학적으로 정확하게 표현하여 최적해를 도출할 수 있지만 계산 복잡도가 높다는 단점
- 제약계획(Constraint Programming, CP) 모델: 제약 조건을 기반으로 해를 빠르게 탐색할 수 있어 대규모 문제에서 더 효율적인 성능을 보인다.
특히 CP를 FJSP와 TOU 환경에 적용한 점은 기존 연구 대비 의미 있는 기여로 볼 수 있다.
이 논문의 핵심 아이디어는 매우 직관적이다. 전기요금이 비싼 시간대에는 가능한 한 생산을 줄이고, 상대적으로 저렴한 시간대에 작업을 집중시키는 것이다. 다만 현실에서는 단순히 작업을 이동시키는 것만으로 해결되지 않는다. 기계의 유휴 상태에서도 일정한 전력이 소비되고, 작업 간 선후 관계와 기계 선택 제약이 존재하기 때문이다. 따라서 이러한 요소들을 모두 고려한 최적화 모델을 통해 스케줄을 재구성해야 한다.
실험 결과는 이 접근의 효과를 잘 보여준다. 제안된 모델을 활용하면 전체 생산 완료 시간(makespan)을 유지하면서도 에너지 비용을 평균 약 6.9% 절감할 수 있는 것으로 나타났다. 이는 기존의 “에너지를 절약하려면 생산성을 희생해야 한다”는 인식과 달리, 두 목표를 동시에 달성할 수 있음을 보여준다는 점에서 의미가 크다. 특히 생산성 저하 없이 비용만 줄일 수 있다는 점은 실제 산업 현장에서 해당 방법이 채택될 가능성을 높여준다.
이 연구의 의의는 단순한 스케줄링 최적화를 넘어, 생산 의사결정에 에너지 요소를 통합했다는 데 있다.
시간대별 전기요금이라는 현실적인 요소를 반영함으로써 산업 적용 가능성을 높였고, 생산성과 비용 절감이라는 두 목표를 동시에 달성할 수 있는 방향을 제시했다. 다만 전기요금이 사전에 결정되어 있고 변동성이 없다는 가정은 실제 환경과 차이가 있을 수 있으며, 향후에는 수요 변동이나 실시간 가격을 반영한 확장 연구가 필요할 것으로 보인다.
결론적으로 이 논문은 제조 스케줄링 문제에서 에너지 비용을 효과적으로 고려할 수 있는 방법을 제시하며, 생산성과 비용 사이의 기존의 trade-off를 완화할 수 있음을 보여준다. 이는 향후 데이터 기반 의사결정이나 강화학습 기반 스케줄링과 결합될 경우 더욱 발전 가능성이 높은 연구 방향으로 이어질 수 있다.
2. Literature review
2.1. Flexible job shop scheduling problem
Flexible Job Shop Scheduling Problem(FJSP)은 지난 50년 동안 광범위하게 연구되어 왔다. 이 문제를 해결하기 위해 정확해법부터 휴리스틱까지 다양한 기법들이 사용되어 왔다. 정확해법에는 branch-and-bound 알고리즘, 혼합정수선형계획(MILP), 라그랑주 완화법 등이 포함되며, 휴리스틱 방법으로는 개미 군집 최적화, 인공 벌 군집, 인공 면역 시스템, 진화 알고리즘, 탐욕적 랜덤 적응 탐색 절차(GRASP), 이웃 탐색, 입자 군집 최적화, 시뮬레이티드 어닐링, 타부 탐색, 그리고 다양한 하이브리드 기법 등이 있다. FJSP에 대한 종합적인 리뷰는 Chaudhry and Khan (2016)을 참고할 수 있다.
본 논문에서는 특히 MILP 모델에 초점을 맞춘다.
FJSP를 위한 MILP 모델은 주요 이진 결정 변수에 따라 네 가지 유형으로 분류된다.
- machine-position formulation(MPF): 각 작업이 어떤 기계의 어느 위치에서 처리될지를 결정하는 방식
- general precedence formulation(GPF): 동일한 기계에서 한 작업이 다른 작업보다 먼저 수행되는지를 결정한다. 이때 두 작업이 반드시 바로 연속해서 수행될 필요는 없다.
- immediate precedence formulation(IPF): 한 작업이 다른 작업 바로 직전에 수행되는지를 결정한다.
- time-indexed formulation(TIF): 각 작업이 시작되는 시간을 기준으로 모델링하는 방식이다.
Demir and Isleyen (2013)은 이러한 기준에 따라 FJSP의 수리모형들을 분류하고, MILP 모델들의 계산 성능을 비교하였다.
2.2. Energy-efficient scheduling under time-of-use pricing
에너지 효율적인 스케줄링에 관한 연구는 에너지 절감 방법에 따라 네 가지로 분류할 수 있다.
- 불필요한 유휴시간(idle time)을 줄이는 방법
- 유휴 상태의 기계를 종료하는 것으로, 유휴 시간이 충분히 길 경우 기계를 꺼서 에너지를 절약할 수 있다. 이 경우 언제 기계를 종료할지를 기존 스케줄링 모델에 추가적으로 결정해야 한다.
- 에너지 소비가 기계 속도에 의존할 때, 기계 속도를 조정하는 방법
- 오프피크 생산(off-peak production)이다. 전력 사용이 많은 시간대에는 전기요금이 높고 오염물질도 많기 때문에, 비피크 시간대에 생산을 수행하면 전기요금 절감과 환경 개선 효과를 동시에 얻을 수 있다.
에너지 효율적 스케줄링에 대한 전반적인 리뷰는 기존 연구들을 참고할 수 있다.
이후 본 논문에서는 TOU 요금제를 고려한 오프피크 생산에 초점을 맞춘다.
단일 기계 스케줄링의 경우, Aghelinejad et al. (2018)은 기계 상태와 TOU 요금을 동시에 고려한 통합 모델을 제안하고 유전 알고리즘을 적용하였다. 그러나 단순히 전기요금이 낮은 시간대로 작업을 이동시키는 것이 항상 경제적인 것은 아니며, 이러한 시간대는 종종 인건비가 더 높을 수 있다.
- Gong et al. (2019)은 이러한 문제를 해결하기 위해 에너지 비용과 인건비 간의 trade-off를 고려하였다.
- 또한 Cheng et al. (2017)은 단일 기계 배치 스케줄링 문제에서 기계 on/off 전략과 TOU 요금을 동시에 고려한 이목적 MILP 모델을 제안하고, ε-constraint 기반의 정확한 최적해를 도출하였다.
- 병렬 기계 환경에서는 Moon et al. (2013)이 생산 스케줄과 시간 의존적 전기요금을 가중합 형태로 통합한 모델을 제안하고, 이를 해결하기 위해 유전 알고리즘 기반의 하이브리드 방법을 제시하였다.
- Ding et al. (2016) 역시 유사한 문제를 다루며 MILP 모델과 column generation 기반 휴리스틱을 개발하였다.
- Flow-Shop 환경에서는 Luo et al. (2013)이 하이브리드 플로우샵 문제를 위해 개미 군집 기반 메타휴리스틱을 제안하였다.
- Wang and Li (2014)는 버퍼 용량이 제한된 플로우샵에서 다양한 모델 파라미터의 영향을 분석하였다.
- Zhang et al. (2014)는 전기요금을 최소화하면서 생산성과 CO₂ 배출 간의 균형을 유지하기 위한 time-indexed 정수계획 모델을 제안하였고, Zhang et al. (2019)는 유연 플로우샵 문제에 대해 MILP 모델과 Pareto 기반 진화 알고리즘을 개발하였다.
- 가장 복잡한 형태인 유연 잡샵 환경에서는 Moon and Park (2014)가 혼합정수 비선형계획 모델을 제안하고 이를 제약계획으로 해결하였다.
- Kim et al. (2017)은 시뮬레이션 기반 스케줄링을 제안하였으며,
- Gong et al. (2019)는 makespan, 에너지 비용, 인건비 등 다목적 최적화를 다루었다.
- Masmoudi et al. (2019)는 잡샵 문제에서 에너지 고려를 포함한 두 개의 ILP 모델과 휴리스틱을 제안하였다.
본 연구 역시 이러한 흐름에 속한다.
한편, 기존의 스케줄링 문제는 일반적으로 기계가 항상 사용 가능하다고 가정하지만, 실제로는 고장이나 예방 정비로 인해 일정 시간 동안 기계를 사용할 수 없는 경우가 존재한다. 이러한 문제는 기계 가용성 제약이나 예방정비 스케줄링 등의 형태로 연구되어 왔다. 본 논문에서는 이러한 요소를 반영하여 TOU 환경에서의 FJSP에 계획된 정지시간을 함께 고려한다.
2.3. Constraint programming
Hillier와 Lieberman (2015)은 최근에는 혼합정수선형계획(MILP)의 기본 개념을 설명할 때 제약계획(Constraint Programming, CP)을 함께 소개하지 않으면 불완전하다고 언급하며, CP가 문제를 모델링하고 해결하는 능력을 크게 확장시킬 수 있는 유망한 방법이라고 설명하였다. CP는 제약 전파(constraint propagation) 기법을 활용하여 기존 제약으로부터 새로운 제약을 도출하고, 동시에 변수의 가능한 값의 범위를 줄여나가는 방식으로 문제를 해결한다.
CP는 다양한 스케줄링 문제에 적용되어 왔으며, 특히 FJSP에도 활용된 바 있다 (Ham and Cakici, 2016; Ham, 2020). 그러나 TOU 요금제를 고려한 FJSP(FJSP-TOU)에는 아직 CP가 직접적으로 적용된 사례는 없다. Moon and Park (2014)는 혼합정수 이차 제약 문제를 해결하기 위해 CP solver를 사용하였지만, 문제 자체를 CP 형태로 모델링하지는 않았다.
IBM CPLEX에서는 “using CP” 옵션을 통해 선형/비선형 혼합정수 모델뿐 아니라 CP 모델도 CP solver로 해결할 수 있다.
본 논문에서는 FJSP-TOU 문제에 대해 CP 기반 모델을 처음으로 제안한다.
3. Problem description and solutions
다양한 기계들의 집합 (k∈K)과 작업들의 집합 (i∈I)으로 구성된 유연 Job-shop 환경을 고려한다. 각 작업 i는 여러 개의 공정들 (Ji={1,…,ni})로 이루어져 있다. 각 공정은 주어진 작업에 대해 정해진 순서(선후 관계 제약, precedence constraints)에 따라 처리되어야 한다. 하나의 기계는 동시에 하나의 공정만 수행할 수 있다. 또한 각 공정 o∈O는 해당 공정을 처리할 수 있는 기계들의 집합 Ko 중 하나의 기계에서 수행되어야 한다.
표준 FJSP 문제 외에도, 에너지 고려 스케줄링 접근에서는 총 에너지 비용(TC)을 함께 고려한다. 특히 전기요금은 이산적인 시간 구간에 따라 변동한다. 핵심 아이디어는 총 에너지 비용을 최소화하기 위해 생산을 비피크(off-peak) 시간대로 이동시키는 것이다. 이를 위해 먼저 makespan을 최소화하고, 그 다음으로 총 에너지 비용을 최소화하는 정수선형계획 모델을 제안한다.
3.1. Integer linear programing model
- Parameters
- Decision Variables
- objective function
- 두 가지 목적을 결합한 lexicographic(계층적) 목표
- makespan을 최소화 + energy-cost 최소화
- (A1) makespan 최소화하고 M이 큰 숫자일 때 생산, 유휴, 공통으로 소비되는 총에너지인 TC를 최소화
- 두 가지 목적을 결합한 lexicographic(계층적) 목표
- makespan을 최소화 + energy-cost 최소화
- (A2) 각 공정은 정확히 하나의 기계에서 한 번 처리
- (A3) 선행 공정이 완료된 후에야 후속 공정이 시작
- (A4) 각 기계는 주어진 시간 간격 동안 최대 하나의 공정만 처리
- (A5)-(A6) makespan과 공정의 시작 시간을 연결
- (A7)-(A8) 결정 변수가 이진 변수
- (A9)-(A11) 생산, 유휴, 시스템 가동 중 발생하는 총 에너지 비용을 계산
- (A10) 기계가 가동 중일 때의 유휴 비용, 생산 중의 유휴 비용, 유지보수 활동 중의 비용을 포함
- (A12) 예약된 가동 중단 시간 동안에는 공정 처리를 금지
Fig.2 전통적인 스케줄링 방식과 energy-aware 스줄링 방식을 비교
- energy-aware 스케줄링은 특히 대규모 투자 제조업에서 생산성 저하 없이 에너지 비용을 절감할 수 있는 잠재력
- 각각 두 개의 작업과 세 개의 작업으로 구성된 인스턴스에 대한 스케줄 (예방 정비 없다고 가정)
- 히트맵: 2019년 1월 30일의 시간별 당일 TOU 가격/mWh
- 실선 상자: 생산 작업 / 점선: 유휴시간 / 빨간색: 관련 비용 표시
이 ILP 모델은 자동차나 반도체와 같은 자본집약적 제조 산업에는 직접적으로 적용되기 어렵다. 이는 총 에너지 비용(TC)이 기업이 얻는 수익에 비해 상대적으로 매우 작기 때문에, 이들 산업의 최우선 목표는 생산성을 극대화하는 데 있기 때문이다. 그러나 동일한 생산성을 유지하면서도 TC를 크게 줄일 수 있다면, 에너지 기반 생산 스케줄링은 산업 현장에서 충분히 수용될 수 있을 것이다.
한편, 자본집약적이지 않은 산업의 경우에는 서버, 소프트웨어 라이선스, 개발 비용 등을 포함해 약 50만 달러 수준에 달하는 고급 스케줄링 시스템과 이를 운영하기 위한 인건비를 감당하기 어려울 수도 있다.
따라서 본 논문에서는 (A1)에서 사전식(lexicographic) 최적화 접근을 제안한다. 첫 번째 목표는 makespan을 최소화하는 것으로, 이는 가장 중요한 요소로 간주되며, 이 목표의 개선은 다른 목표에서의 손실을 감수할 만큼 중요하다. 두 번째 목표는 총 에너지 비용(TC)을 최소화하는 것이다. 즉, 생산성을 저해하지 않는 범위 내에서 TC를 줄이고자 한다.
만약 시스템 전체의 makespan이 아니라 각 작업의 총 완료시간에 관심이 있다면, (A1)의 식 대체:
3.2. Constraint programming
- Parameters
- objective function (B1): makespan을 먼저 최소화하고, 그 다음으로 생산, 유휴, 공통 상태에서 소비되는 총 에너지 비용(TC)을 최소화하는 것을 목표로 함.
- (B2) 각 공정이 반드시 하나의 기계에서 처리되도록 보장함. intensity: 예방 정비로 인해 설정된 기계의 비가동 시간 동안에는 작업이 수행되지 않도록 함.
- (B3) 각 공정이 이전 공정이 완료된 이후에 시작되도록 하여 선후 관계 만족시킴.
- (B4) 동일한 기계에서 작업 구간들이 서로 겹치지 않도록 함.
- (B5)-(B6) makespan의 시작과 종료 시점 정의
- (B7)-(B9) 각각 생산, 유휴, 공통 상태에서의 에너지 비용 계산
- startEval과 endEval은 구간의 시작과 종료 시점에서 구간별 선형 함수를 평가하기 위한 수식
Fig. 2 작은 벤치마크 문제에 대한 최적 스케줄
- (a)는 makespan 최소화를 목표로 한 스케줄
- (b)는 동일 생산성을 유지하면서 총 에너지 비용을 최소화한 스케줄
- The job (J2 O2) in Fig. 2a starts processing at time 18 and completes at 33, spending $78+$80 … +$44 = $709 per each energy consumption per hour.
- The job (J2 O2) in Fig. 2b starts processing at time 21 and completes at 36, spending $73+$63 … +$47 = $609 only.
이와 같이 energy-aware 스케줄링 모델은
- 유휴 상태에서의 전력 소비가 상대적으로 작다는 점을 이용해 불가피한 idle 시간을 전기요금이 높은 시간대로 이동시키고,
- 실제 생산 작업은 전기요금이 낮은 시간대로 이동시킴으로써,
전체 완료 시간은 유지하면서도 총 에너지 비용을 약 3.1% 절감할 수 있음.
4. Computational experiments
본 절에서는 제안된 모델의 효과를 검증한다. ILP, CP, 그리고 flow control 모델은 모두 IBM OPL 20.1.0을 사용하여 구현되었으며, Intel® Core i7-4770 CPU와 16GB RAM을 갖춘 개인용 컴퓨터에서 실험이 수행되었다.
4.1. Problem instances
- Mong et al. (2019): 기존의 대표적 벤치마크 인스턴스인 SFJS01-10과 MFJS01-10(Fattahi et al., 2007)을 기반으로, 에너지 소비를 고려한 테스트 인스턴스 제안
- 본 연구에서는 동일한 인스턴스 사용
- SFRS01-10: 소규모 문제
- MFJS01-10: 중간 규모 문제
- 모든 인스턴스에서 공통 전력 소비량(P0)은 10으로 설정
- 작업 수행 시 전력 소비량은 [3,5] 구간의 균등분포에서 추출, 유휴 상태 전력(Dk)은 {1,2,3} 중 무작위로 생성
- TOU(시간대별 전기요금): 2019년 1월 30일의 시간별 데이터로 계획 기간동안 반복해 사용
- 시간 단위 스케일을 맞추기 위해, 테스트 인스턴스의 처리 시간은 10으로 나눈 뒤 가장 가까운 정수로 변환
4.2. Results
- Table 1: Fattahi 인스턴스에 대해 제안된 CP 모델과 ILP 모델을 비교한 결과
- 소규모 인스턴스에서는 CP가 모든 경우에서 최적해를 찾은 반면, ILP는 mfjs07~10 인스턴스에서 실패
- 다수의 이진 변수를 포함한 다목적 문제에서 ILP의 계산 효율이 떨어지기 때문이며, 특히 변수 수가 증가할수록 성능 저하가 두드러짐.
자본집약 산업에서는 에너지 비용이 수익에 비해 상대적으로 작기 때문에 생산성 극대화가 더 중요한 목표이다.
그러나 생산성을 유지하면서도 에너지 비용을 크게 줄일 수 있다면,
이러한 에너지 기반 스케줄링은 산업 현장에서 충분히 활용될 수 있다.
- Table 2: 기존 스케줄링과 energy-aware scheduling 비교한 결과
- 기존 방식은 makespan을 최소화에 초점
- energy-aware 방식은 동일한 makespan을 유지하면서 TC 최소화
- 결과적으로 평균 약 3.7%의 비용 절감이 가능했으며, 이는 사용된 인스턴스의 특성으로 인해 절감 폭이 다소 제한된 것으로 해석
보다 큰 규모의 문제를 분석하기 위해 Behnke and Geiger (2012)가 제안한 FJSP 벤치마크 인스턴스를 추가로 사용함. 총 60개의 인스턴스 중 15개를 선택하고, Meng et al. (2019)과 동일한 방식으로 에너지 파라미터를 추가함.
- 이 대규모 인스턴스에서도 CP는 ILP보다 우수한 성능을 보였으며, TOU를 고려한 경우 생산성 유지하면서 평균 약 6.9%의 에너지 비용 절감이 가능함을 확인. Fattahi 인스턴스보다 절감 폭이 더 크게 나타난 이유는 문제 규모가 커질수록 스케줄을 조정할 수 있는 유연성이 증가하기 때문.
- 다만 Behnke6 이상의 인스턴스에서는 CP와 ILP 모두 최적해를 증명하지 못했기 때문에, Table 4에는 Behnke1~5 인스턴스에 대한 결과만 제시
5. Conclusion
본 논문에서는 시간대별 전기요금(TOU)과 계획된 정지시간을 고려한 에너지 효율적 FJSP 문제를 다루었다. 특히 전기요금이 시간 구간에 따라 달라지는 환경에서, 에너지 비용을 최소화하기 위해 생산을 비피크 시간대로 이동시키는 것이 핵심 아이디어이다.
이를 위해 정수선형계획(ILP)과 제약계획(CP) 모델을 제안하였으며, 계산 실험을 통해 제안된 모델이 생산성을 저해하지 않으면서도 평균 약 6.9%의 에너지 비용 절감이 가능함을 확인하였다. 이는 에너지 고려 생산 스케줄링이 자본집약적 제조 산업에서도 충분히 활용될 수 있음을 시사한다.
향후 연구로는 공정 시간 자체를 조절할 수 있는 경우와 TOU 요금제를 동시에 고려하는 통합 모델을 개발하는 것이 흥미로운 방향이 될 것이다.