Production manufacturing scheduling problem has been the center of interest for the last decades. As all production systems are integrated into a scheme, the supply of raw material becomes a principle problem in production management system. This problem is more critical in petroleum industry because crude oil has various characteristics and the final product are changed according to crude oil supplied.
Petroleum industry consists of a serious of related areas such of oil production, delivery of crude oils, refining operation, and marketing of refined products. Production planning determines aggregated production quantity for each final product while satisfying various firm's constraints. Production planning is supported by a NLP system called RPMS(Refinery Petrochemical Modeling System). Crude oil daily delivery scheduling problem is tried to solve under the assumption that the monthly total charging quantity of each crude oil is given by the master production plan.
In this study, a compound backtrack search algorithm using the existing AI search and intelligent backtracking technique is presented. This heuristic algorithm solved the problem in each subproblems. In advance, the combinations of crude oils that can be delivered simultaneously are composed in order to backtrack at deadend situation easily. The backjumping technique is used for the backtracking and minimizes the occurrence of deadend on the daily delivery scheduling. The quantity of each crude oil at purchasing time is determined at the last subproblem finally.
The prototype of crude oil delivery scheduling algorithm is developed and tested.
지난 수십년간 학자들은 제품생산 Scheduling 에 관심을 가져왔지만, 점차 통합된 생산 시스템으로 나아감에 따라 원자재 도입문제도 중요성이 커지기 시작했다. 복잡한 정제과정을 거치게 되는 석유사업에 있어서는 원유도입 Scheduling 이 석유제품 생산에 미치는 영향은 더욱 심각하다.
석유제품 생산은 원유도입, 원유혼합, 증류의 과정을 거친다. 현업에서는 전반적인 생산계획을 석유산업을 위한 NLP System - RPMS (Refinery Petrochemical Modeling System) - 으로 지원하고 있다. 이번 연구는 RPMS 에 의해 구해진 전반적인 생산계획을 최적의 해로 보고, 주어진 일별 생산계획하에서 생산계획에 차질을 주지 않는 원유의 도입계획을 찾는 문제를 그 대상으로 하고 있다.
기존의 연구에서도 이러한 문제를 해결하기 위해 수학적인 접근방법이나, Search 를 이용한 접근방법들을 사용하고 있으나, 그렇게 좋은 성과를 내고 있지는 못하다. 그래서 이 연구에서는 기존의 Search Algorithm 들과 Intelligent Backtracking Technique 을 응용한 새로운 휴리스틱 알고리즘을 개발하였다. 이 휴리스틱 알고리즘은 Backtracking 을 용이하게 하기 위하여 동시에 수송 가능한 원유들을 미리 조합하고 있으며, 이 원유조합을 결정하는데 있어서 수송비용의 최적화를 보장하고 있다. 또한 DeadEnd 상황의 발생을 가능한한 줄이기 위해 Backjumping Technique을 응용하고 있다.
이번 휴리스틱 알고리즘의 개발은 Intelligent Backtracking Technique 이 Delivery Scheduling 에 처음 적용되었다는 의미는 갖지만, 좀 더 일반적인 응용을 위해서는 앞으로 더 많은 연구노력이 필요할 것이다.