IEEE Robotics & Automation Magazine - June 2015 - 66

We also face the following process constraints:
the uninterrupted operation requirement for distillers
● the occupation requirement of a charging tank in distiller
feeding
● the nonoverlap requirement in tank charging and
discharging
● oil residency time constraint
● charging-tank-switch-overlap constraint.
To schedule the system at the middle level, it needs to define and arrange activities for all the devices and production
units in every detail so that the constraints are satisfied and
the given objectives are optimized.
●

State of the Art
With the nondeterministic polynomial-time (NP)-hard complexity for solving a general scheduling problem, usually
heuristics and metaheuristics are applied for discrete manufacturing systems and batch processes [5], [10], [13], [14],
[21]. Since heuristics and metaheuristics cannot ensure an
optimal solution, the STSP of batch processes is formulated
as mathematical programming models to obtain an optimal
solution [3], [9].
As previously discussed, there are discrete decisions in operating a refinery, just as there are in operating a general process
industry. Hence, an STSP of refinery operations is essentially
combinatorial and belongs to a set of NP-complete problems
[2]. A good way to efficiently solve a complex scheduling problem is to adopt heuristics and metaheuristics for suitable solutions but not exact optimal ones. This method is also used for
scheduling discrete manufacturing systems and batch processes. It is known that, to make these techniques applicable for a
problem, the jobs to be performed should be well-defined and
known before the scheduling process begins, and solution feasibility should not be a major issue. In scheduling a refinery, one
needs to define and sequence the tasks simultaneously, i.e., the
tasks to be scheduled are not known at the beginning.
Furthermore, there are a large number of constraints to be dealt
with. Therefore, it is challenging to find a feasible solution.
Hence, heuristics and metaheuristics are difficult to apply.
Exact solution methods previously developed for batch
processes are applied to the STSP of a refinery using mixed integer linear programming (MILP) and mixed integer nonlinear programming (MINLP) models. With both discrete-event
and continuous variables, the key issue is how to model time.
The existing studies offer two types of models, discrete-time
representation and a continuous-time model [17]. In the discrete-time representation, the horizon is divided into a number of uniform time slots. By this time representation, MILPs
can be obtained as they are in [4], [6], [11], [15], [19], [20],
[22], [23], and [38]. However, this method results in a huge
number of binary variables leading to a problem that is almost
impossible to solve [2], [33].
It seems that, if the number of binary variables can be reduced, the problem becomes easier. Using continuous-time
models and assuming that one knows the discrete events to be
performed during the scheduling horizon, the number of
66

IEEE ROBOTICS & AUTOMATION MAGAZINE

JUNE 2015

binary variables can be significantly reduced. Such models are
adopted in [6]-[8], [12], and [25] to solve the problem.
Nevertheless, nonlinear constraints are introduced in [19],
which drastically complicates the solution process. Knowing
the number of events that will occur in advance is unrealistic
[2], because they are not known before a schedule is obtained.
Moreover, to make the problem solvable, the models of both
types make special assumptions so that some constraints are ignored, leading to an inefficient or unrealistic solution for real
world cases [15]. Thus, it is necessary to search for a new technique so that a software tool for practical use can be developed.
Solving the STSP
A refinery process is a continuous one, and so the short-term
schedule obtained should be compatible with its initial state.
With the dynamic nature of a plant and the insufficiency of sensors, one cannot exactly predict the state of the system in real
time. Therefore, although the scheduling horizon for a refinery
often lasts between a week and ten days (sometimes longer depending on the initial state), in practice, a short-term schedule
should be generated within a few hours. This means that a scheduling tool must work quickly. To make automation possible for
this problem, similar to how it is done for scheduling discrete
manufacturing systems and batch processes, it is important to
have an approximate method for an excellent and feasible solution but not an optimal one, which would take too long to acquire. However, heuristics and metaheuristics that are used in
discrete manufacturing systems and batch processes are not applicable to the problem addressed here.
By examining the STSP of a refinery, one can find that the
feasibility issue and the characteristics of its hybrid nature
make the problem difficult. With a large number of constraints, the feasible space must be small, making it extremely
difficult to find an exact optimal solution since the feasible
space needs to search the whole space. In the control-theoretic
domain, by building a proper model one can control the system so that the undesired states cannot be reached, or one can
determine a feasible solution space. This leads to the problem
addressed here in a control-theoretic perspective instead of the
MILP or MINLP models used in the existing work.
Based on this idea, a hybrid PN is developed to model the
process in this article. Using the PN models, the dynamic behavior is analyzed using the control theory, and schedulability
conditions are successfully derived, which can be checked in a
simple way. Using these conditions, the problem is hierarchically divided into two subproblems: 1) the refining scheduling
problem at the upper level and 2) the detailed scheduling problem at the lower level. By treating these conditions as constraints, this work finds a realizable refining schedule by further
decomposing it into subproblems so that each subproblem contains either discrete or continuous variables. By doing so, one
can separate the discrete variables from the continuous ones
such that the problem can be efficiently solved. In addition,
with the schedulability conditions and the hybrid PN model,
one can find a feasible detailed schedule in a simple way.
Therefore, a computationally efficient methodology is provided

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