Korean J. Chem. Eng., 19(4), 545-551 (2002) 545 †To whom correspondence should be addressed. E-mail: swpark@mail.kaist.ac.kr ‡This paper is dedicated to Professor Wha Young Lee on the occasion of his retirement from Seoul National University. Development of Refinery Scheduling System Using Mixed Integer Programming and Expert System Jin-Kwang Bok, Heeman Lee*, Jay Woo Chang** and Sunwon Park***† Samsung SDS Co., Ltd., 707-19 Yeoksam-dong, Gangnam-gu, Seoul 135-918, Korea *Technoleaders Co., Ltd., ***Department of Chemical and Biomolecular Engineering, KAIST, 373-1 Guseong-dong, Yuseong-gu, Daejeon 305-701, Korea **SK Engineering & Construction Co., Ltd., 192-18 Gwanhun-dong, Jongno-gu, Seoul 110-300, Korea (Received 22 January 2002 • accepted 8 March 2002) Abstract−−−−This paper presents a hybrid refinery scheduling system combining mathematical programming model and expert system. Mixed-integer linear programming models for crude oil movement between units are merged into the expert system that is for qualitative issues concerning crude vessel unloading operations. The target problem ranging from the crude unloading to the crude charging to distillation towers is decomposed into several module problems for efficiency. Compared with existing scheduling approaches for oil movement, the proposed hybrid refinery schedul- ing system is very effective in dealing with timing decisions involving vessel unloading operations due to the advan- tages of an expert system. Since the proposed scheduling system can generate solutions so fast, it is expected to play a key role in the real processes. Key words: Refinery Scheduling System, Mixed-Integer Programming, Expert System, Oil Movement INTRODUCTION The main role of a refining operation is to convert crude oil mix into a variety of marketable products through a number of refining processes. The major scheduling objective is to provide crude mix- ing with desired sulfur levels which will yield required distillates [Lee et al., 1996]. It is difficult to achieve this due to scheduling constraints imposed by large shipment sizes and pipeline capacity limits between the charge tank and the refinery tower. Scheduling of crude receiving, blending, and CDU operations to meet distillate and fuel oil production requirements currently drives the refinery management problem [Lee et al., 1992]. While long-term refinery planning problems have been exten- sively studied and the developed algorithms have been commer- cially implemented through the software such as RPMS [Bonner and Moore Corps., 1979] and PIMS [Bechtel Corps., 1993], it is quite recent that mathematical programming approaches were applied to the short-term scheduling of refinery processes that are mainly related to the crude oil unloading and inventory management [Lee et al., 1996; Shah, 1996]. Lee et al. [1996] presented a mixed-in- teger linear programming model for crude-unloading operation, oil movement between tanks, and crude-charging schedule, but the ser- ious shortcoming of the model is the large computational expense. The complication is mainly invoked by a large number of 0-1 var- iables regarding the timing decision of vessel unloading over the discrete time domain, whihch makes industrial implementation of the developed model difficult. Furthermore, it cannot take into ac- count the operational contingency that is ubiquitous in the real in- dustry. Shah [1996] also addressed the crude oil management prob- lem using the two-stage mathematical programming model. How- ever, the model did not support the timing decisions with respect to the vessel operation and the mixing operation that is of practical importance in the refinery processes relying on many different crude types imported overseas. In order to overcome the shortcomings that appeared in the previous literature, this paper proposes a hy- brid scheduling system combining a mathematical programming approach and an expert system that is one of the AI-based ap- proaches. For the required amount of crude processed in CDUs given in the planning stage, the mathematical optimization formulation yields the amount of oil movement between units: storage tank- charge tank and charge tank-crude distillation unit (CDU). The move- ment timings between units are determined by the expert rules in order that the number of changeovers involving significant costs should be minimized. The decision concerning vessel docking and crude unloading, where the so-called fast-unloading heuristics are prevailing to reduce demurrage cost in the field, is also established by the expert system. Even though the expert system cannot neces- sarily provide the optimal solution, it significantly contributes to reducing computation time and coping with the operational contin- gencies. In particular, it is also renowned as potentially capable of handling large-sized real problems. This paper is organized as follows. First, the nature of refinery processes with the information flow for decision making in the as- pect of oil movement is outlined. The decision problem is divided into several event-based modules according to distinct operation features. Next, the proposed methodologies implemented in this scheduling algorithm follow. For each module, a mathematical pro- gramming model or expert rules are described. Finally, the devel- oped scheduling system is demonstrated through simulating an indus- 546 J.-K. Bok et al. trial scaled refinery process. NATURE OF OIL MOVEMENT IN REFINERY PROCESS The refinery planning and scheduling department has the respon- sibility for satisfying requirements for product shipment ensured by management headquarters. That is, operation under the short- term scheduling should output the operation results meeting the target established in the planning level. The major detailed activities for scheduling are as follows: • Crude receiving and mixing • Process unit operations scheduling • Offsite inventory management and product blending and ship- ping The scope of the target problem with respect to movement and inventory control is depicted in Fig. 1. The refinery system consists of a storage tank group, a charge tank group and a CDU group. Most of the refinery companies have limited the number of tanks or CDUs due to the initial investment. Crude vessels route many oil produc- ing countries, such as Middle East, South East, Red Sea, West Africa, Fig. 1. Oil movement scheme in the refinery process. Table 1. Specification of each crude oil (per Barrel) Crude name Origin Crude type Component Properties MVOL1RC QSUL1RC QCST1RC ALG Algerian COND 0.0121 0.1713 15.0200 ATK Attaka COND 0.1676 0.2801 156.1000 AMB Arimbi L/S 0.5574 0.4200 320.0000 ORI Oriente L/S 0.4835 1.8400 1591.0000 ARH Arabian Heavy H/S 0.4783 3.6800 3190.6000 KWT Kuwait H/S 0.4078 4.4600 1075.0000 COND: Condensate crude oil MVOL1RC: Yields of reduced crude L/S: Low sulfur crude oil QSUL1RC: Contained sulfur in reduced crude H/S: High sulfur crude oil QCST1RC: Contained viscosity of reduced crude July, 2002 Development of Refinery Scheduling System Using Mixed Integer Programming and Expert System 547 North America, etc., with the lead time of crude delivery ranging from a few weeks to three months or more. The purchased crude oil consists of a complex mixture of hydrocarbons. The mixture from different sources has different properties as shown in Table 1. Delivery vessels arrive at the docking place linking to storage tanks by pipes for the purpose of crude unloading. The demurrage cost is so much greater than the inventory cost, not less than thou- sands-time in the order of magnitude, that the arriving vessel should start operation promptly. One refiner usually incurs demurrage cost of $2 million/year [King, 1993]. When no dock is available due to the occupation by the other previous vessel, the present vessel should wait for the next turn. The delivered crude is unloaded to storage tanks. Each storage tank is managed according to tank characteris- tics, i.e., the concentration of specific component in the tank. The crude in a storage tank should be mixed in a charge tank in order to provide the requirement for distillation. In contrast with the blend- ing of intermediate products, crude mixing has rarely been regarded as an optimization problem [Lee et al., 1996]. The mixed crude blend with the strict range of sulfur concentration is fed into the distilla- tion tower. Thereafter, for complete refinery products, the crude dis- tillate from CDU should go through the other remaining steps that have been presented by many other researchers [Gifford, 1955; Lee, 1992]. HYBRID SCHEDULING MODEL FOR CRUDE OIL UNLOADING AND INVENTORY MANAGEMENT Seward et al. [1985] suggested that Hierarchical Production Plan- ning (HPP) can be more widely applicable in capacity-oriented com- panies such as primary metals and chemical processing rather than Material Requirement Planning (MRP). In such a context, total pro- duction planning in an oil refinery company is viewed at different hi- erarchical levels: aggregated production planning, operational sched- uling, and process operation. The operational scheduling of our con- cern receives information such as monthly distillation amount for each CDU from the aggregated production planning levels in order to provide guidance for the daily process operation. The oil movement problem can be represented as several module problems: docking of vessel, crude unloading, transferring and mix- ing of crude, and feeding to CDU. Each module problem is treated autonomously with the objective specific to the module and with the algorithm efficient to the module. For instance, the crude un- loading module, whose objective is to unload the crude from the vessel as fast as possible adopts an expert system that decides the most adjustable storage tank for each crude set by taking the in- ventory and the characteristic of the tank into consideration. The decision flow in the view of oil movement is shown in Fig. 2. Oper- ation level for each CDU is computed based on the amount of crude processed in CDUs over the horizon given by the aggregated pro- duction planning. Next, the optimization on mixing operation is per- formed to maximize the inventory efficiency of charging. Note that the concentration of a specific component in each charge tank should be kept within the specified range. In the crude unloading module, the crude that is purchased by routing the several oil-producing coun- Fig. 2. Decision flows in the proposed algorithm. Fig. 3. Event-based time representation. Fig. 4. Independence between each module operation. Korean J. Chem. Eng.(Vol. 19, No. 4) 548 J.-K. Bok et al. tries and transported by vessel without being mixed is unloaded to storage tanks. As shown in Fig. 3 each module operation is event-based, and in general two or three module operations can be carried out sim- ultaneously. In spite of these overlapped operations, each module works independently from the other modules since neither storage nor charge tanks involve simultaneous oil inflow and outflow op- eration. This is illustrated in Fig. 4. Fig. 5 shows the framework of the proposed scheduling system. The proposed scheduling system is implemented by the real time expert system G2 [Gensym, 1995] that provides a built-in rule-based inference engine as well as simulation and monitoring functions. The mathematical optimization in the modules is carried out through GAMS [Brooke et al., 1992]. 1. Docking of the Vessel Generally, the demurrage cost is so high that the vessel arriving at the wharf should search for a docking place as soon as possible. The docking decision is made based on the fact that each docking place is designed for accommodating the specified range of vessel size. As Fig. 6 shows, the arrival time is determined considering whether there is any other vessel on the docking place that is suitable for the current vessel, or not. 2. Crude Feeding to CDU The movement amount is obtained through a mixed integer linear programming optimization and the movement time is determined by the expert system implementing operation rules. The deviation of the amount of crude processed in each CDU from the specified amount in the upper planning level is taken as the objective func- tion to be minimized subject to a set of constraints. (1) Subject to (2) (3) The weight factor for each CDU accounts for the different signif- icance of satisfying the target amount of crude processed in each CDU established in the aggregated planning. Note that the amount of crude processed in each CDU below the target amount is taken into account in accordance with the practical sense as shown in Eqs. (2) and (3). (1) Amount of Distillation Product from Crude Feeding (4) (5) The amount of product p at CDU k is computed by Eq. (4). The yield data of each charge tank j to produce product p at CDU k, apjk is reasonably assumed to be constant if the sulfur composition of each charge tank is kept within the specified range. YDij denotes whether charge tank j is connected to CDU k or not. Only when charge tank j is assigned to CDU k, the transferring amount CRjk has the meaning that Eq. (5) implies. CRmax, jk is bounded by the pump capacity between the charge tank j and CDU k and CRmin, jk is zero. (2) Changeover Constraint (6) For each decision, each CDU k should be connected to one of charge tanks since the cost involved in changeovers from a charge tank to another is high. (3) Distillation Capacity Limitation (7) For CDU k, the amount of distilled should be less than the maxi- mum capacity. (4) Charging Amount Limitation (8) The summation of amounts charged to all CDUs from a charge tank j cannot exceed the initial inventory. The timing of assignment of charge tanks to CDUs is determined by the expert rule that prefers selecting a charge tank with the largest Minimize ωk∆k k ∑ ∆k Qk* − Qpk p ∑≥ k∀ ∆k 0≥ k∀ Qpk = ap jkCRjk j ∑ p∀ k∀, CRm in jk, YDjk CRjk CRm ax jk, YDjk≤ ≤ p∀ k∀, YDjk = 1 j ∑ k∀ Qpk Qmax k,≤ j ∑ k∀ CRjk ICOj≤ k ∑ k∀ Fig. 5. Information flows between the optimization solver and the expert system. Fig. 6. Vessel docking module. July, 2002 Development of Refinery Scheduling System Using Mixed Integer Programming and Expert System 549 moving amount for each CDU so as to reduce the number of chang- eovers. 3. Crude Mixing in the Charge Tank In order to prepare a CDU with the crude blend having the spe- cified sulfur composition, the crudes from the storage tanks should be mixed properly in the charge tank. The inventory level of the charge tank should be maintained high enough to provide the crude blend for the CDU with the minimum number of changeovers and to lower the inventory of storage tank in order to ensure enough space for the crude unloading. A mixed integer linear programming model for maximizing the quantity of available crude from storage tanks is introduced: (9) Subject to (1) Sulfur Composition Range For each crude tank, the crude should be mixed within a speci- fied composition range. (10) The nonlinear inequality, which can be linearized by using stan- dard arithmetic techniques, gives two linear inequalities as follows: (10a) (10b) (2) Inventory Mass Balance (11) (12) For each charge tank, the inventory after mixing operation is obtained by adding the transferred amount from storage tanks to the initial amount. Tmax, ij is bounded by the pump capacity between storage tank i and charge tank j and Tmin, ij is zero. (3) Assignment of Storage Tank to Charge Tank (13) Each charge tank j that is not assigned to CDU k should be con- nected to a storage tank that is not involved in crude unloading. (4) Transferring Limitation (14) The maximum transferable amount cannot exceed the initial inven- tory of each storage tank. (5) Inventory Capacity Limitation (15) Each charge tank has a capacity limitation. 4. Crude Unloading to the Storage Tank The target unloading tank and unloading time for the crude on the vessel is determined by considering the assay data of the crude and the state of storage tanks. The main idea in this algorithm is intimately associated with so called fast-unloading. All the storage tanks are classified into several logical groups according to the qual- ity of the present crude in the tank: high sulfur, low sulfur, etc. The concentration calculation is performed under the assumption that two different kinds of crude are perfectly mixed regardless of the density. The implemented rules represent that each crude set should be unloaded to the storage tank with the minimum inventory in the corresponding tank group. EXAMPLE The proposed scheduling system is applied to a general refinery process: 6 storage tanks, 6 charge tanks, and 3 CDUs. Fig. 7 shows the result of unloading scheduling by the expert system. For each set of crudes on the vessel, the start and the end time of unloading and the best suitable unloading place are determined by expert rules. With the movement amount and movement timing obtained from the optimization models and expert rules, respectively, the sched- ule for oil movement is illustrated in Fig. 8. Fig. 9 shows the sulfur concentration trend that should be maintained within specified range. Maximize Tij j ∑ j ∑ SCLj SSiTij + SCjICj i ∑ Tij + ICj i ∑ ---------------------------------------- SCUj≤ ≤ i∀ SSi − SCLj( )Tij + SC j − SCLj( )ICj 0≥ i ∑ j∀ SSi − SCUj( )Tij + SC j − SCUj( )ICj 0≤ i ∑ j∀ ICj = ICOj + Tij i ∑ j∀ Tm in ij, YCij Tij Tm ax ij, YCij≤ ≤ i∀ j∀, YCij = 1 i i Ic{ }∉ ∑ j∀ − Jk{ } Tij ISOi≤ j ∑ i∀ ICj ICmax j,≤ j∀ Fig. 7. Scheduling result of crude unloading. Fig. 8. Inventory trend in inventory tanks 1, 2 and 3. Korean J. Chem. Eng.(Vol. 19, No. 4) 550 J.-K. Bok et al. CONCLUSIONS A hybrid refinery scheduling system combining a mixed integer programming model and an AI-based expert system was developed. Quantitative decisions such as determining the amount of crude mix- ing or the amount of crude charging were made through the mixed integer linear programming models, and qualitative complications regarding vessel unloading operation and the movement timing be- tween the units were resolved with the expert system. For the monthly amount of distillation products given in the aggregated plan- ning step, the amount of crude that should be processed in each CDU is determined. Then, a decision is made on the mixing in charge tanks in order to provide crude to each CDU. The storage tank with the minimum inventory in the corresponding logical group is se- lected for crude unloading. The simulation study indicates that the proposed scheduling system can be applied to industrial scale refin- ery problems. ACKNOWLEDGMENT This work was partially supported by the Brain Korea 21 pro- ject and SK Engineering & Construction Co., Ltd. NOMENCLATURE (a) Indices b : buoy i : storage tank j : charge tank k : CDU v : vessel (b) Sets Ic : storage tanks that receive crude c Jk : charge tanks that is connected to CDU k (c) Variables CRjk : amount of crude transferred from charge tank j to CDU k ICj : available inventory of charge tank j Qpk : total quantity of product p from CDU k SSi : sulfur composition of storage tank i Tij : crude amount transferred from storage tank i to charge tank j YCij : binary variable denoting if storage tank i is connected to charge tank j YDjk : binary variable denoting if charge tank j is connected to CDU k ∆k : deviation of the amount of the crude in each CDU k from the amount given by the aggregated planning step (d) Parameters apjk : yield of product p from charge tank j in CDU k CRmax, jk : maximum transferable amount from charge tank j to CDU k CRmin, jk : minimum transferable amount from charge tank j to CDU k ICmax, j: inventory limitation of charge tank j ICOj : initial inventory of charge tank j Qmax, k : maximum capacity of CDU k SCLj : lower sulfur limit in charge tank j SCUj : upper sulfur limit in charge tank j Tmax, ij : maximum transferable amount from storage tank i to charge tank j Tmin, ij : minimum transferable amount from storage tank i to charge tank j ωk : weight factor that accounts for penalizing deviation of dis- tillation amount REFERENCES An, D. M., Hou, B. K. and Hwang, K. S., “Automatic Synthesis of Op- erating procedures for Safe Emergency Operation,” HWAHAK KONGHAK, 39, 30 (2001). An, D. M. and Hwang, K. S., “A Study on the Expert System for Pre- dicting Hazardous Conditions of Chemical Process,” HWAHAK KONGHAK, 34, 727 (1996). Anthony, B., David, K. and Alexander, M., “GAMS A USER’S GUIDE,” Boyd & Fraser Publishing Company, Massachusetts, USA (1992). Bechtel Corp., PIMS User’s manual, ver.6.0, Houston, USA (1993). Bonner and Moore Management Science, RPMS A system description, Houston, USA (1979). Chae, H., Yoon, Y. H. and Yoon, E. S., “Safety Analysis Using an Ex- pert System in Chemical Processes,” Korean J. Chem. Eng., 11, 153 (1994). Choi, T. H. and Yoon, E. S., “An Expert System to Aid Blast Furnace Operation Using Artificial Neural Network Techniques,” HWAHAK KONGHAK, 29, 270 (1991). Gensym, G2 Reference Manual, version 4.0; Gensym Corp., USA (1995). Hou, B. K., An, D. M. and Hwang, K. S., “An Expert System for Pre- venting Hazardous Conditions in Boiler Plants,” HWAHAK KONG- HAK, 34, 750 (1996). King, M., “Automation of Oil Movement Systems Prevents Mistakes, Saves Money,” Oil & Gas J., 76 (1993). Kim, C. J., Oh, J. K. and Yoon, E. S., “A Fault Diagnostic Expert Sys- tem Using the Symptom Tree Model,” HWAHAK KONGHAK, Fig. 9. Sulfur concentration trend in charge tanks 1, 2 and 3. July, 2002 Development of Refinery Scheduling System Using Mixed Integer Programming and Expert System 551 28, 417 (1990). Kim, Y. J. and Kang, S. K., “Prediction of Binary Azeotrope Formation in Hydrocarbon Mixtures Using a Knowledge-based Expert Sys- tem,” Korean J. Chem. Eng., 12, 306 (1995). Lee, H., Pinto, J. M., Grossmann, I. E. and Park, S., “MILP Model for Refinery Short Term Scheduling of Crude Oil Unloading with In- ventory Management,” Ind. & Eng. Chem. Res., 35(5), 1630 (1996). Lee, J. K., Kim, M. Y., Song, Y. W. and Yoon, H. S., “UNIK-YUKONG: Refinery Scheduling Expert System,” KYOUNGYOUNG KWA- KHAK, 121 (1992). Lee, K. H., Yang, G., Jung, J. Y. and Lee, I. B., “Development of an Ex- pert System for Functional Group Analysis in Group Contribution Method,” HWAHAK KONGHAK, 31, 647 (1993). Seward, S. M., Taylor, S. G. and Bolander, S. F., “Progress in Integrat- ing and Optimizing Production Plans and Schedules,” Int. J. Prod. Res., 23(3), 609 (1985). Shah, N., “Mathematical Programming Techniques for Crude Oil Sched- uling,” Com. Chem. Eng., 20, S1227 (1996). Song, J. and Park, S., “Intellite3: A Knowledge Based Expert System for Control Structure Synthesis,” Korean J. Chem. Eng., 7, 198 (1990). Yoo, C. K., Kim, D. S., Cho, J. H., Choi, S. W. and Lee, I. B., “Process System Engineering in Wastewater Treatment Process,” Korean J. Chem. Eng., 18, 408 (2001). Yoon, B. S., Oh, J. K. and Yoon, E. S., “Knowledge Base Representa- tion for the Fault Diagnostic Expert System Using the Fault-Conse- quence Digraph,” HWAHAK KONGHAK, 29, 19 (1991). Korean J. Chem. Eng.(Vol. 19, No. 4) Development of Refinery Scheduling System Using Mixed Integer Programming and Expert System Jin-Kwang Bok, Heeman Lee*, Jay Woo Chang** and Sunwon Park***† Samsung SDS Co., Ltd., 707-19 Yeoksam-dong, Gangnam-gu, Seoul 135-918, Korea *Technoleaders Co., ... Abstract�-�This paper presents a hybrid refinery scheduling system combining mathematical program... Key words:�Refinery Scheduling System, Mixed-Integer Programming, Expert System, Oil Movement INTRODUCTION NATURE OF OIL MOVEMENT IN REFINERY PROCESS HYBRID SCHEDULING MODEL FOR CRUDE OIL UNLOADING AND INVENTORY MANAGEMENT EXAMPLE CONCLUSIONS ACKNOWLEDGMENT NOMENCLATURE REFERENCES