근사동적계획법을 이용한 플래닝과 스케쥴링 통합 최적화

Abstract

이 논문은근사동적계획법을이용하여플래닝과스케쥴링의통합을 위한 근사적 방법을 제시하였다. 이러한 근사적 방법 이전에 일반적으로 많이 사용되는 최적화 기법들이 플래닝에 어떻게 적용될 수 있는지에 대해 논의해보고, 화학 플랜트에는 왜 적용하지 못하는 지, 근사적 방법이 필요한지에 대해 논의해본다. 먼저 첫번째로, 플래닝의 예시로서 에너지 시스템에서의 플래닝의 수학적 프레임워크를 제시하였다. 제시한 모델은 전체 에너지 자원 최적화 문제를 두 개개의 형태, 전통적 자원과 신재생 에너지 자원 플래닝 문제로 각각 나누었으며,최적화를적용하였다.신재생 에너지 문제의경우, 정부에 의해 정해진 할당량을 채울 만큼에 한해서 최적화가 이루어지게 되며, 이렇게 문제를 풀게 되는 경우, 각 변수에 대한 민감도 분석을 시행하기도 훨씬 유리하며, 최적화하기에도 유리하다. 에너지 플래닝의 다른 기법과 비교하여 보았을 때, 각 지역의 특성을 반영하고 에너지 자원의 흐름들을 살펴볼 수 있도록, 하위 시스템을 정의하는 등 조금 더 개선된 방법을 제시하였다고 볼 수 있다. 두 번째로는, 송수관 최적 관리를 위한 플래닝 기법에 대해 제시하였다. 도시 내 배수관망에서의 송수관이 파손되면, 경제적으로나 사회적으로나 매우 극심한 피해를 불러일으킬수있다.제한된 예산내에서 배수관 의 최적 교체 계획에 대한 기존의 방법들을 각각의 노후화된 파이프를 선정하는데 실제적으로 활용하는 것은 굉장히 어렵다. 이 장에서는 이러한 최적 선정 문제를 랭킹 혹은 우선순위 결정 문제로 재구성하고, 두 개의 랭킹으로 구성된 순위 문제로 제시하였다. 이 제시된 방법은 또한 배수관망에서의 파이프라 부서질 때 비용적이나 수리적인 측면에서 생길 수 있는 손실을 고려하게된다.이를위해,다양한 중요한 랭크들을상 수도관망의 교체 순위를 최종적으로 결정하기 위해 랭크 집합 방법을 이용한다.이 제시된 기법에서는 랭킹 집합 방법을 통해 교체를 위한 현재 설치된 파이프들의 우선순위를 결정하게 되며, 이 때 상수도관망의 신뢰성, 비용등을 고려하게 되는 것이다. 하지만 화학 플랜트에서는 이러한 플래닝 기법들을 적용하지 못하며, 스케쥴링 단계까지 고려할 필요가 있기 때문에, 근사적 방법들을 제시하게 되었다. 이를 위해, 스케쥴링 관점에서 이전의 기법들을 기반으로 하여 새로운 포뮬레이션 기법을 제사였다. 스케쥴링은 화학 공정의 제조 시스템에서 핵심 단계이나, 다양한 불확실성들이 영향을 준다. 이 불확실성은 단순히, 스케쥴링에서의 실행가능성 뿐만 아니라 제조 공정에서의 다른단계,플래닝과 컨트롤에도영향을주게된다.그러므로,이러한 불확실성을 배제하게 된 스케쥴링은 실제 문제를 다루기에는 적절치 못하다. 그러므로, 이를 다룰 수 있기 위해 근사동적계획법을 제시하였다. Kondili에서 제시된 기존 예시를 사용하였으며, 가장 먼저 STN 형태의 기존의 MILP를 바탕으로 마르코프 체인을 형성하였다. 다음으로 가격을 최소화하는 목적 함수 대신 장치 고장과 추가적인 수요를 고려한 불확실성까지 고려하여 최종 생산물을 최대화하는 문제를 새로 만들었다. 이 때의 의사 결정시점은 장비의 이용가능한 여부에 따라 결정되게 된다. 또한 이 때의 가치 함수는 추계학적 스케쥴링에 대한 최적 정책을 이끌어내며, 또한 불확실한 상황이 발생하게되면,이를상태전이로 간주하여,실질적으로 온라인상으로 최적 정책을 만들어낼 수 있다. 이러한 가치 함수는 불확실한 상황이 발생하였을 때, 실행가능성에 대해 논의하는 데 도움을 준다. 마지막으로 위에 제시된 방법들을 기반으로 통합된 프레임워크를 제시하게 된다 스케쥴링은 플래닝 단계에서의 실행가능성을 생산할 수 있는지에 대해 판단하며, 플래닝 단계에서는 스케쥴링에 어느 만큼 생산을 해야하는 지에 대해 결정을 하며 논의하게 된다. 이러한 정보의 상호교환은 추가적인 시간 소모를 거의 하지 않으며, 실질적으로 정보를 실시간으로 업데이트하게 하는 것도 용이하다. 즉 이러한 불확실성을 대비할뿐 만 아니라,불확실한 상황이 발생할때마다 대처할수있음을 확인할수 있었다.