IEEE Robotics & Automation Magazine - June 2015 - 67

that can be developed into a software tool for practical use. It is
possible to extend the proposed approach to the STSPs of other
process industries, which represents a breakthrough in the research field. This article briefly introduces the proposed novel
approach without going into too much technical detail so that
the readers can easily understand how it works.
Mathematical Programming
Methods and Complexity
When operating a refinery, we face discrete events such as the
start and end of charging and discharging a tank as well as continuous processes, such as oil flow and distillation, resulting in a
hybrid system. Unlike widely studied discrete productionscheduling problems, where jobs to be performed are well-defined and the machine capacities are known in advance, when
scheduling the process of crude-oil operations, we only have the
system state information, e.g., crude-oil inventory in the system
and the status of all devices, including the tanks, pipeline, and
distillers. We must first define the jobs and then schedule them.
Intelligent optimization methods such as genetic algorithms,
particle swarm optimization, mussel wandering optimization,
and evolutionary algorithms completely fail to do so since they
cannot even find their initial population (feasible solutions).
By recognizing the difficulty of the problem, researchers have
tried mathematical programming methods. The key issue becomes whether to describe the time as discrete or continuous.
With the former, a scheduling horizon is divided into a number
of slots so that it can happen at the boundary of a slot in any
event. Then, one finds an optimal schedule using an exact solution method [19], [22], [23], [38], which suffers from computational complexity, as shown through the following example.
Assume that T is the number of time slots for a plant with K
distillers, H is the number of oil types, and G is the number of
tanks. Let fij be the production rate of distiller i during time slot
j, and let g j be the flow rate of the pipeline during time slot j.
To further define h j = 1, there is a crude-oil type switch in performing oil transportation through the pipeline at the beginning
of slot j, otherwise it is zero. Let C P be the cost coefficient for
such a switch. We define d ij = 1 if there is a charging tank
switch in feeding distiller i at the beginning of time slot j, otherwise it is zero. Let C DS be the cost coefficient for such a switch.
The main objective is to maximize the production rate, minimize crude-oil inventory cost, and minimize changeover cost.
An MILP is given as follows:
Maximize J = / Ki = 1 / j = 1 fij - C P / j = 1 h j
T

- C DS / Ki = 1 / j = 1 d ij .
T

This is subject to the following:
1) g j should be within the permissive flow rate range of the
pipeline, 6j ! N T = {1, 2, f, T } .
2) fij should be within the permissive feeding rate range of
the distiller i, 6i ! N K and 6j ! N T .
3) Material balance for tankers during slot j, 6j ! N T .
4) Material balance for tank l during slot j, 6l ! N G and
6j ! N T .

5) Material balance for crude-oil type k during slot
j, 6k ! N H and 6j ! N T .
6) Oil residency time constraints for tank l during slot
j, 6l ! N G and 6j ! N T .
7) Charging-tank-switch-overlap constraint, 6i ! N K and
6j ! N T .
Using this model for each time slot and each distiller, one
needs to determine which oil type the distiller should be
charged to or which tank the oil should be discharged from. A
binary variable should be used to describe the occurrence of
such an event. Thus, outside of the binary variables denoting
the occurrence of events for constraints 6 and 7, there are at
least T # G # H # K binary variables. A typical application
scenario has 20 tanks (11 storage and nine charging tanks),
six oil types to be processed, and three distillers with a ten-day
scheduling horizon. To obtain a solution with acceptable accuracy, the application requires a time slot that is less than 15
min when one uses an MILP model with discrete-time representation [19]. Thus, for a ten-day scheduling horizon, there
are 960 time slots and at least 960 # 20 # 6 # 3 = 345,600 binary variables for this scenario. It is extremely difficult, if not
impossible, for an existing commercial software package to
solve such a large problem. Furthermore, a produced solution
may not be applicable or feasible because of the requirement
that an event should be scheduled to happen at the boundary
of a slot. Any reduction of slot length will drastically increase
the number of binary decision variables; e.g., reducing a time
slot from 15 to 10 min will increase the binary variables to
518,400. This implies that such models are not applicable to
real-life industrial practice.
The studies in [1], [6], [18], and [37] have offered continuous
time models. These models drastically reduce the number of binary variables but introduce nonlinear constraints [19], yielding
a nonlinear programming model. Furthermore, the number of
discrete events that are defined by a to-be-found schedule during the horizon needs to be known in advance [2]. Can we use
continuous-time representation to formulate the problem?
Unfortunately, this method is not used in practice; thus, the continuous models are currently theoretically valuable. The last resort for solving this problem is to make special assumptions and
neglect most of the constraints. Using this method, the resulting
models (discrete or continuous) can be successfully solved. This
solution gives decision makers some hints regarding ideal results, which concludes in unrealistic and infeasible solutions. In
conclusion, mathematical programming models cannot be applied to large real-world problems. Therefore, we must seek a
new breakthrough solution to the STSP.
Control-Theoretic and Hybrid PN-Based Approach
Problem Formulation in the Perspective of
Hybrid System Control Theory
The process of crude-oil operations is formed by a series of operations, including unloading oil from tankers, transporting oil
from storage tanks to charging tanks, and feeding oil from
charging tanks to distillers. The start and end of an operation
JUNE 2015

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2015