This thesis presents mathematical optimization models and new efficient solution methods for the production planning and scheduling problems of real size processes under process uncertainty using mixed integer programming.
First, a heuristic scheduling algorithm based on an optimal control theory is proposed for large scale industrial problems. The main feature of this idea lies in a two-level hierarchical structure consisting of a reference model and a rigorous model, respectively. Numerous heuristic algorithms have been developed because scheduling for industrial processes is usually an NP-hard problem. However, such methodologies are not viable solutions from the operator’s point of view due to the fact that they cannot leave enough flexibility to react to unexpected events. In order to perform on-line scheduling in real production plants under process uncertainty, an efficient solution method is required for rapid rescheduling. As a fair compromise between the excess of decision detail and long-range planning inspiration, a simplified or relaxed model is addressed to derive optimal trajectories. A main advantage of this approach is that it can reduce the computational time remarkably. The optimal trajectories are then used as reference trajectories to be tracked in real time. A refinery short-term scheduling model of crude oil unloading with inventory management, a scheduling model of batch and continuous chemical processes, and a scheduling model of primary steelmaking processes have been developed to show the performance of the proposed method. The proposed method is shown to enhance solution performance compared with the traditional mixed integer model.
Next, a new scheduling framework is developed to handle correlated forms of uncertainty in a dynamic manufacturing environment using parameter estimation technique. When variability in batch data is encountered during execution of a schedule, the information is typically used in a reactive mode to reschedule the plant, to avoid infeasibilities or sub-optimalities in resource allocation induced by the actual batch conditions. However, these `reactive scheduling` methodologies seldom seek to model correlation in processing data and use them to anticipate future variations in scheduling parameters in revising the schedule. This is in contrast to control, where stochastic models containing space/time correlation information is used with an optimal estimation technique (e.g., Kalman filtering) for optimal prediction and predictive control. The main idea of the proposed method is to use observations made at the current time to obtain conditional expectations of future processing parameters. A deterministic scheduling problem is solved repeatedly to revise the schedule as the parameters are continually updated by a Kalman filter based on the information coming from actual execution of the schedule. The proactive scheduling approach has been tested on a general multipurpose batch chemical scheduling problem and it has shown superior performance compared with general deterministic and reactive scheduling method.
Last, in this thesis, it is presented how to develop the integrated system model for monitor glass making processes as the engine of the integrated production, inventory and logistics decision supporting system. The production plan, inventory control, and logistics, which include all processes from production to supply for customer, are all very critical decision making processes in manufacturing firms. But the isolation and absence of efficient decision making system between departments can create some problems of production scheduling by unreasonable shipping plans and complexity of business process. The proposed model consists of production planning model and scheduling model. The production planning model supports the decision making according to monthly manufacturing plan of production sites, sales plan on customers and transportation policy. And the scheduling model is divided into 2 models. The first is the short-term scheduling model of the pressing process to minimize job changes, keep the due date and maintain the adequate inventory along the production amounts determined by the production planning model. And the other is the short-term scheduling model of the polishing process to minimize the WIP (warehouse in process) amounts produced from the pressing process or coming from other production sites.
본 논문에서는 정유공정, 회분식 화학공정, 철강제조공정 등과 같은 공정 산업에서의 생산계획 및 일정계획에 대한 의사 결정 지원 방법으로서 혼합정수 계획법을 이용하여 수학적 최적화 모델의 정립하고 모델의 계산 성능 향상 및 불확실성을 고려한 효율적 풀이법을 연구하였다.
논문의 첫 주제로서 혼합정수계획법의 해를 효율적으로 구할 수 있는 two-step 방법을 제안하였으며 이 방법의 성능을 검증하기 위해 정유공장의 원유 하역 및 재고 관리를 위한 단기 일정계획, 회분 및 연속 화학공정에서의 일정계획, 철강제조공정에서의 각 생산품의 효율적 생산을 위한 일정계획 모델을 적용하였다. 일반적으로 실제 산업 공정에 대한 혼합정수계획법은 NP-hard 한 문제로 알려져 있으며 이 때문에 실제 현장 운전자들에게는 실용적인 해법으로 응용될 수가 없었다. 즉, 불확실성이 많이 존재하는 실제 현장에서 온라인 일정 계획이 실행되기 위해서는 신속하게 일정을 재수립할 수 있는 방법이 필요하다. 이를 위해 참조해(reference solution)를 구하기 위한 단순화된 모델과 이 모델을 이용하여 구한 참조해를 따라가게끔 최적 일정을 수립하게 하는 완전모델로 구성된 두 단계 구조의 heuristic 방법을 개발하였다. 단순화된 모델에서는 정수를 연속 변수로 가정하여 선형계획법으로 relaxed된 해를 구하게 되며 이 해는 두 번째 단계에서 참조해로 이용된다. 두 번째 단계에서는 기존의 목적함수에 참조해와의 차이에 대한 페널티 항을 추가 함으로써 최적화 모델이 이 참조해 부근의 최적해를 구해주게 된다. 이 방법은 branch and bound 연산법에 기초를 둔 혼합정수계획법 풀이에 있어 node와 iteration 수를 줄여 줌으로써 계산시간을 크게 향상시키는 방법이다. 사례 연구로서 진행된 정유공정, 회분식 화학공정, 그리고 철강공정의 일정계획 모사 결과는 기존의 일반적인 혼합정수계획법에 비해서 매우 향상된 계산 성능을 보였다. 제안된 two-step 방법은 구성이 간단하고 실행하기가 간편한 장점이 있으며 빠른 시간안에 global optimum에 근접한 해를 구할 수 있다.
두 번째 주제로서 동적인 실제 생산 환경에서 상관관계를 지닌 불확실성을 극복하기 위해 매개 변수 추정을 이용한 새로운 일정계획법을 제안하였다. 공정 시간, 생산 수율 등과 같은 매개변수의 불확실성을 처리하기 위해 reactive scheduling 과 같은 연구가 진행되었으나 이러한 연구들은 공정데이타의 상호 관계를 모델링하고 이를 이용해 미래의 생산 일정을 교정하지는 못했다. 이 연구의 메인 아이디어는 현재까지 측정된 정보를 이용하여 미래의 공정 매개변수를 예측하는 것이다. 제안된 방법은 처음 구해진 일정에 의해 공정을 진행하는 동안 측정된 실제 정보에 기초한 Kalman filtering에 의해 계속적으로 매개 변수를 갱신하게 된다. 갱신된 매개 변수를 이용하여 일정 계획 문제를 반복해서 풀어 일정을 계속 교정해 나가는 것이다. 이 방법의 성능을 분석하기 위해 일반적인 다목적 회분 화화공정 문제에 적용하였으며 기존의 deterministic scheduling method와 reactive scheduling method에 비해 효율적으로 일정관리를 할 수 있음을 보여 주었다.
세 번째로 모니터 브라운관 생산 공정에 대한 글로벌 생산, 재고 출하 및 물류 관리 통합 시스템 모델을 제안하였다. 생산, 재고, 출하 및 물류 관리는 제조업체들의 중요한 의사 결정 문제이다. 특히, 요즘과 같이 소비가 생산을 리드하고, 수요와 생산이 글로벌화 되는 시점에서 이들의 효율적인 의사 결정이 회사 전체의 이윤 증가 및 비용의 최소화에 기여하는 효과는 아주 크다. 제안된 시스템 모델에서 핵심 추론 엔진이 되는 최적화 모델링은 연간 및 월간 생산계획 모델의 가지로 이루어 지며, 재무, 영업 및 생산데이타를 통합하여 최적의 전사 이윤 및 조업 비용을 발생하는 생산, 판매, 물류 및 재고 정책을 제안하였다. 일정관리 모델은 두 가지 모드로 나누어져 차례로 풀리는데 먼저 성형 계획 모델에서는 생산계획에 의해서 정해진 라인별, 제품별 월간 생산 할당량을 최대한 맞추면서 일별 납기를 준수하고, 적정 재고 수준을 지키며 job change를 최소화 하는 정수혼합계획 모델이 제시되었다. 연마 계획 모델에서는 성형 계획에 의해서 생산되거나 타 산업장으로부터 유입되는 반제품의 재고를 최소화 하는 방안을 제시하였다.