IEEE Robotics & Automation Magazine - June 2015 - 68

form the discrete events. In addition, the process constraints are
also related to a discrete-event process. A natural idea is to describe this process with a dynamic hybrid model so that a scheduling problem can be formulated from the perspective of the
hybrid system control theory. When scheduling such a process,
we should decide when an operation should take place, what
should be done, and how it should be done. Therefore we propose an important concept called an operation decision (OD).
Definition 3.1
Define OD = (COT, g, S, D, a, b), where COT represents
crude-oil type; g represents the amount of oil to be delivered
by the OD; S is the source from which the oil comes; D represents the destination where the oil is delivered; and a and b
are the starting and ending time of the OD. For a single operation, the flow rate is generally a constant and described as
g/ (b - a) . In the definition, COT, S, and D are discrete variables, while g and flow rate g/ (b - a) are continuous variables. When an OD is executed, the state of the system is
transformed to another. Hence, using a hybrid control theory,
an OD can be seen as a control command.
There are oil unloading ODs (ODU), oil transportation
ODs (ODT), and oil feeding ODs (ODF). We use [a, b],[m, n],
and [~, r] to represent their time interval, respectively. For
ODU, S is a tanker and D is a storage tank. Similarly, we can
identify variables S and D for ODT and ODF. It should be
pointed out that an ODT must be executed by a pipeline. Let
ODFki be the i- th OD for feeding distiller k; let
g = g/ (b - a), f = g/ (n - m), and h = g/ (r - ~) be flow
rates for ODU, ODT, and ODF, respectively; let C =[x s, x e] be
the scheduling horizon (typically a week or ten days); and let
K be the number of distillers. Initially we only know the oil inventory, the status of all the devices, and the tanker arrival information. Then, given the initial state information at x s, in
the view of hybrid control theory, to schedule the system is to
find a series of ODs with multiple objectives being optimized.
This is described as
SCHD: A series of ODs: ODU 1, f, ODU w, ODT1, f,
ODTx, ODF1, f, ODFK .
(1)
It is subject to all the constraints given in the "Oil Refinery
and Short-Term Scheduling" section, where w is the number
of ODUs, x is the number of ODTs, both of which are unknown; ODFk = {ODFk1, f, ODFk2, f, ODFknk}, k ! N K
consists of all the ODFs for the feeding of distiller k during
C = [x s, x e] .
The objectives to be optimized include productivity maximization, minimization of inventory, minimization of the
number of crude-oil type switches for transporting oil through
a pipeline, and minimization of the number of charging tank
switches in distiller feeding.
Solution Architecture
Feasibility is especially important when solving the STSP of
crude-oil operations. The problem with this formulation is
68

IEEE ROBOTICS & AUTOMATION MAGAZINE

JUNE 2015

that a large number of constraints exist and any violation of
them results in an infeasible solution. With a large number of
constraints, on the one hand, the feasible solution space is
small, which makes it challenging to obtain a feasible solution
by an exact enumeration-solution method using mathematical
programming models. On the other hand, finding a feasible
solution becomes easier if the search is done in a small, feasible
space. In regards to the scheduling horizon, in addition to the
feasibility issue, a schedule must present all actions in detail,
which makes the problem large and too difficult to solve.
A control-theoretic solution architecture with a two-level hierarchy is proposed as a breakthrough solution. To guarantee
solution feasibility with this architecture, we can take advantage
of the control theory. We first describe the processes of crudeoil operations with a hybrid dynamical model called a hybrid
PN. Then, we simply model the constraints via its structure,
transition enabling and firing rules, and its properties, e.g., liveness. Based on the hybrid control theory, we convert the liveness conditions into schedulability conditions and feasible
solution space. Consequently, we need to find a solution in the
feasible space, which will drastically simplify the problem.
This proposed architecture offers us a novel strategy to hierarchically decompose a large problem into two small subproblems. Using this architecture, one needs to find a refining
schedule at the upper level, which is then realized by a detailed
schedule at the lower level. The key here is that the obtained
refining schedule must be realizable by a detailed schedule.
This is possible since the schedulability conditions can be formulated as constraints into the model to find a refining schedule. Furthermore, one can further decompose the refining
schedule problem into subproblems with each subproblem
containing either continuous variables or discrete variables in
the same formulation. In other words, we innovatively decouple the interaction of discrete and continuous variables such
that one can efficiently obtain a realizable refining schedule.
In finding a detailed schedule to realize a refining schedule
by using the schedulability conditions as constraints, the solution feasibility can be guaranteed by making the system transform from one allowed state to another. An allowed state
implies that it can evolve to a feasible schedule if the system is
properly scheduled as shown in [29], [30], [33], and [35].
Thus, a feasible schedule to realize a given refining schedule
can be found sequentially in a one-OD-by-one-OD way.
Heuristics and metaheuristics can be applied to optimize
these objectives. By optimizing these objectives one can efficiently find a short-term schedule for crude-oil operations.
Hybrid PN and Modeling of Operations
We first present a hybrid PN and use it to model the process. The
concept of a basic PN can be found in [34], [39], and [40]. The PN
used in this work is extended from a resource-oriented PN developed in [34] and [40]. It is defined as PN = ^P, T, I, O, M, K h,
where P is a finite set of places; T is a finite set of transitions,
P , T ! z, P + T = z; I: P # T " N = {0, 1, 2, f}; O: P # T
" N; M: P " N is a marking with M 0 being the initial marking;
and K: P " N \ {0} with K ( p) being the largest number of

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