IEEJ TRANSACTIONS ON ELECTRICAL AND ELECTRONIC ENGINEERING

IEEJ Trans 2016; 11: 593–603

Published online in Wiley Online Library (wileyonlinelibrary.com). DOI:10.1002/tee.22277

Paper

A Genetic Algorithm Approach to Short-Term Scheduling of Crude Oil

Operations in Refinery
Yan Hou∗ , Non-member
NaiQi Wu∗,∗∗a , Non-member
ZhiWu Li∗∗ , Non-member

As a type of process plant, a refinery is characterized by the interaction of discrete events and continuous processes. To
schedule crude oil operations in a refinery, it is necessary to define and schedule the jobs simultaneously such that heuristics
and meta-heuristics cannot be directly applied. It is very challenging to schedule crude oil operations. To solve this problem, it
is decomposed into two subproblems hierarchically. At the upper level, a refining schedule is found, while at the lower level a
detailed schedule is obtained to realize the refining schedule. Given a refining schedule at the upper level, this paper studies the
detailed scheduling problem at the lower level. Based on a control-theoretic perspective, the problem is innovatively transformed
to a problem of assigning charging tanks to distillers such that meta-heuristic methods can be applied. Then, a genetic algorithm
(GA) approach is developed to solve the problem. In realizing the proposed GA, based on a set of existence conditions of a
feasible schedule, methods are presented to guarantee that each chromosome corresponds to a feasible schedule. An industrial
case study is used to show the application of the proposed method. It shows that the method works well and is applicable to
real-life problems. © 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.

Keywords: crude oil operations; short-term scheduling; genetic algorithm

Received 28 January 2015; Revised 27 September 2015

1. Introduction be defined during the scheduling process, which makes heuris-

tics or meta-heuristics very difficult if not impossible [7]. Hence,
There are mainly two categories of manufacturing systems: dis- up to now, effective techniques and software tools for short-term
crete manufacturing and process production. For process produc- scheduling in oil refinery are lacking. In practice, the scheduling
tion, it is known that there is great potential for benefit gains if a job is still done manually by a planner by trial and error. Thus,
plant is well operated [1]. To do so, the manufacturing execution not only the obtained schedule is nonoptimal but also the job is
system (MES) plays a vital role. In an MES, there are two main very tedious.
modules: production planning and short-term scheduling. For oil In recent years, great efforts have been made for the short-
refinery, the planning technique has been well developed by using term scheduling problems of process industry. With heuristics
linear programming-based commercial software packages such as and meta-heuristics being not applicable, mixed-integer linear
PIMS (process industry modeling system) [2] and RPMS (refin- programming (MILP) or mixed-integer nonlinear programming
ery and petrochemical modeling system) [3]. As pointed out in (MINLP) is used to formulate the short-term scheduling problem
Ref. [4], the expectation for further progress in planning technol- of crude oil operations. The model obtained is solved in an exact
ogy is unrealistic. While techniques for production planning in oil way. With the process being hybrid, by such models the key
refinery are well developed, there are no efficient techniques and is how to describe the time. There are two ways of doing this:
commercial software tools for short-term scheduling [1,5]. discrete-time and continuous-time representation. By discrete-time
For a refinery process, there are both discrete-event and con- representation, the whole scheduling horizon is divided into time
tinuous variables, i.e., the process constitutes a hybrid system. slots with uniform duration such that an event starts and ends
Thus, the short-term scheduling problem of oil refinery belongs to at the boundary of a time slot. With such a model, to obtain
a hybrid optimization problem. Such a problem is combinatorial an acceptable accuracy, the time slots should be small enough.
in nature and is shown to be NP-hard [6]. Short-term schedul- Generally, it is required that a slot should be less than 15 min. The
ing of crude oil operations is one of the most difficult problems work in Refs. [8–14] belongs to this category. With discrete-time
in scheduling an oil refinery. For an NP-hard problem, heuristics representation, an MILP model can be obtained if crude oil mixing
or meta-heuristics are advisable. However, to make heuristics or is not taken into account. However, there are a large number of
meta-heuristics applicable, it is required that the jobs to be sched- binary variables, leading to that it involves prohibitive computation
uled should be well defined and known in advance. For short-term and is not applicable to real-life problems.
In order to overcome the drawbacks of discrete-time represen-
scheduling of crude oil operations, at the beginning, one knows
tation, efforts have been made to model the problem such that the
only the state of the system and the jobs to be scheduled should
start and end time point of an event can be exactly found, leading
to the continuous-time representation. The work in Refs. [15–19]
a
Correspondence to: Naiqi Wu. E-mail: nqwu@must.edu.mo belongs to this category. By doing so, the number of binary
* Department of Industrial Engineering, Guangdong University of Tech- variables in the model is indeed significantly reduced. However,
nology, Guangzhou 510006, China there are nonlinear constraints, or the problem is formulated as an
** Macau Institute of Systems Engineering, Macau University of Science MINLP model that is difficult to solve. By linearization, the solu-
and Technology, Taipa, Macau tion obtained may be infeasible. Furthermore, by continuous-time

© 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.
 Y. HOU, N. WU, AND Z. LI

it is necessary to find an optimal detailed schedule. This paper

Refining Schedule conducts a study on this issue.
With the combinatorial nature, the detailed scheduling prob-
Schedulability lem is still NP-hard, although it is one of the subproblems of
scheduling crude oil operations. For NP-hard problems, one may
prefer heuristics and meta-heuristics if possible. However, in
Detailed Schedule scheduling crude oil operations, at the beginning, the jobs to be
Hybrid Model scheduled are unknown and should be defined during the schedul-
ing process. Hence, as pointed out by Wu et al . [26], heuristics
and meta-heuristics are not applicable to the scheduling prob-
The Plant lem of crude oil operations. To solve this problem, in this paper,
based on the schedulability conditions obtained in our previous
work [25,27–29], the problem is innovatively transformed into a
Fig. 1. Architecture of scheduling for crude oil operations
charging tank assignment problem that is similar to an optimiza-
tion problem of discrete event process. By doing so, it is possible
representation, it requires that the number of discrete events to to use meta-heuristics for the short-term scheduling problem of
happen during the scheduling horizon should be known at the crude oil operations. However, since the feasibility of a schedule
beginning [6]. This is not the case in practice. Moreover, for is sequence-dependent in charging tank assignment, an initial solu-
both discrete- and continuous-time models, special assumptions tion cannot be generated as is done directly by a meta-heuristic.
are made and some constraints are ignored such that the problem Then, a method is proposed to obtain a feasible population. Thus, a
is solvable, which makes the solution unrealistic and infeasible for genetic algorithm (GA) is developed to solve it such that a solution
real-world cases [20]. Consequently, the techniques using MILP can be found efficiently. This is the first attempt to develop such
are hard to use in practical application. a method. As pointed out above, since the jobs to be scheduled
To solve the problem, the short-term scheduling problem of for this problem are not known, originally heuristics and meta-
crude oil operations is modeled by a kind of hybrid Petri heuristics are not applicable to it, and there is no computationally
nets by extending the resource-oriented Petri nets developed in efficient method to solve it. This work makes heuristics and meta-
Refs. [21–24]. Based on such models, the problem is studied in heuristics usable such that the addressed problem can be efficiently
a control-theoretic perspective in Refs. [7,25–30,36] and a novel solved. This is a significant contribution.
approach is presented. By this approach, the short-term scheduling The remainder of this paper is organized as follows. The refinery
problem of crude oil operations is decomposed into two subprob- process is briefly introduced and the refining scheduling problem
lems in a hierarchical way, as shown in Fig. 1. At the upper is presented in Section 2. Section 3 defines the detailed scheduling
level, a refining schedule is found by optimizing some objectives, problem and then transforms it into a charging tank assignment
such as productivity maximization and crude oil inventory min- problem. Based on the results obtained in Section 3, a GA method
imization. At the lower level, a detailed schedule is obtained to is developed to solve the problem in Section 4. An industrial case
realize the refining schedule. To guarantee that a refining sched- study is used to show the application of the proposed method in
ule is realizable by a feasible detailed schedule, a hybrid Petri net Section 5. Section 6 concludes the work.
model is proposed to describe the crude oil operations. With the
Petri net model, schedulability analysis is made from a control-
2. The Processes and Refining Scheduling Problem
theoretic perspective, and schedulability conditions are derived
for different circumstances. If such conditions are met, a feasi- 2.1. Refinery processes Generally, crude oil is carried to
ble schedule exists; otherwise, no feasible schedule can be found. a port near the refinery plant by crude tankers and is unloaded into
These conditions are then used as constraints to obtain an optimal storage tanks by the port. The crude oil in the storage tanks is then
and realizable refining schedule, and a three-stage method is pro- transported to charging tanks in the refinery plant via a pipeline.
posed to find such a schedule in Refs. [31, 37]. By this method, The charging tanks feed crude oil into distillers for distillation.
refining scheduling problem can be efficiently solved mainly based After distillation, various middle products that come out from the
on a linear programming formulation. Also, based on the schedu- distillers are delivered to other production units for fractionation
lability conditions, a safe state is defined in Refs. [7,25–27] and and further reaction such that a variety of components are obtained.
is presented later. A detailed short-term schedule to realize a refin- These components are then blended to form the final products. In
ing schedule is obtained recursively by making the system transfer the viewpoint of production planning and scheduling, there are
from one safe state to another Refs. [7, 25–27, 36]. It is compu- three stages in the refinery processes: (i) crude oil operations;
tationally efficient. (ii) production, including all the reactions, such as distillation,
In operating a refinery, to make it profitable, there are a variety catalysis and cracking, reforming, and storage of middle products;
of objectives to be optimized [32]. When a tank is discharged, it and (iii) the delivery of final products to the market. Short-term
cannot be fully emptied and some oil remains, called heels [13]. If scheduling of crude oil operations is one of the most difficult
a tank is filled with one type of crude oil and then, after discharged, scheduling problems in a refinery [33]. In this paper, we discuss
another type of crude oil is charged into it, the heel is mixed with the short-term scheduling problem of crude oil operations.
the newly filled oil, leading to oil type degradation or cost increase. The process of crude oil operations is illustrated in Fig. 2. In
To reduce such cost requires filling the same type of crude oil or this process, it performs the following operations: (i) crude oil
the type of crude oil with less difference in components. Oil degra- unloading from a tanker at the port into the storage tanks by the
dation also occurs when there is a switch from one type of crude port; (ii) crude oil transportation from storage tanks to charging
oil to another in crude oil transportation via a pipeline. Thus, min- tanks in the refinery plant via a pipeline; and (iii) crude oil feeding
imizing cost due to oil degradation is an objective in scheduling from charging tanks to distillers for distillation. In this process,
crude oil operations, which is relevant to the detailed scheduling there are a variety of constraints, including resource and process
problem. The methods proposed in Refs. [7,25–27, 36] find a fea- constraints. The resource constraints include: (i) the number of
sible schedule only, but do not optimize the schedule to minimize storage and charging tanks and their capacity are limited; (ii) the
the cost resulting from oil degradation. This is not enough, and flow rate of the pipeline should be in a given range; (iii) the

594 IEEJ Trans 11: 593–603 (2016)

 A GENETIC ALGORITHM APPROACH TO SHORT-TERM SCHEDULING

In (1), w and z denote the number of ODUs and ODTs,

respectively. Notice that for ODF ki , INT ki = [ωki , πki ]. Hence,
Constraint (2) guarantees that the schedule covers the entire
scheduling horizon and a distiller operates uninterruptedly. In find-
ing the schedule, some objectives should be optimized [32], which
include (a) maximization of production rate; (b) minimization
of crude oil inventory cost; (c) minimization of the number of
switches from a charging tank to another in feeding the distillers;
Crude oil Storage Charging
(d) minimization of oil mixing in tank charging and discharging;
tanker tanks Pipeline tanks Distillers and (e) minimization of the changeover cost in oil transportation
from the storage tanks to charging tanks via the pipeline.
Fig. 2. Process of crude oil operations
When one type of crude oil goes through the pipeline and then
another type of oil follows, there is bound to be oil type mixing
volume of all oil types in the tanks and the incoming tankers is to a certain extent, and some cost will be incurred because of oil
limited. The process constraints include the following: (i) a distiller type degradation. Objective (e) is to minimize such a cost.
must be kept working continuously without interruption, unless To find such a schedule, initially we know (i) the inventory
maintenance is necessary; (ii) for each distiller, at any time, at of crude oil in the tanks and pipeline; (ii) the information about
least one charging tank should be used to feed crude oil; (iii) a coming tankers, including when a tanker arrives, the types and
tank cannot be charged and discharged simultaneously; (iv) after amount of crude oil in the tanker; and (iii) the current working
a storage or charging tank is charged, the oil in it must stay there states of every production unit, including the state of a distiller,
for a certain amount of time to separate the brine before it can be whether a tank or pipeline is being charged or discharged, and if
discharged for processing (this constraint is called oil residency so, the type of crude oil and the charging or discharging rate. In
time constraint); and (v) the pipeline is full of oil all times with other words, at the beginning, the only information known to us
oil segments of different oil types, though it can be idle at some is the system state, but the ODs (or the jobs) to be scheduled are
time. It is these constraints that make the short-term scheduling unknown and need to be defined during the scheduling process.
problem of crude oil operations very complicated. Thus, no heuristic or meta-heuristic is reported for this scheduling
problem.
2.2. Short-term scheduling problem A short-term
schedule for crude oil operations should provide all the activi- 2.3. The refining scheduling problem To make the
ties for every production facility on the whole scheduling horizon short-term scheduling problem of crude oil operations solvable,
in detail. Such a schedule is composed of a series of operations. this problem is studied from the control-theoretic perspective
A schedule is to decide what operations should be performed in Refs. [7,25,34,36]. By this approach, the process of crude
and when an operation should be performed. Hence, to describe oil operations is modeled by hybrid Petri nets (PNs). With the
a short-term schedule, an operation decision (OD) is defined as PN models, schedulability is analyzed, and the schedulability
follows. conditions under which a feasible schedule exists are derived.
Definition 1 : An operation decision is defined as OD = They are briefly introduced later. Based on the schedulability
(COT, ξ , S , D, INT), where COT = crude oil type; ξ = volume of conditions, the short-term scheduling problem is discomposed into
crude oil to be delivered by the operation; S = the source device subproblems in a hierarchical way, as shown in Fig. 1. At the upper
from which crude oil is to be transferred; D = the destination to level, a refining scheduling problem is solved, while a detailed
which crude oil is to be transferred; and INT = [a, b] is a time schedule is found to realize the refining schedule at the lower level.
interval in which a and b represent the start and end time point of To describe the refining scheduling problem, a feeding parcel (FP)
the operation, respectively. of crude oil is defined as follows:
As pointed out in Ref. [25], in practice, for a single operation, Definition 2 : A feeding parcel of crude oil is defined as FP =
the flow rate in delivering crude oil during [a,b] is set as a constant (COT, ζ , [ε, η]), where COT = crude oil type to be fed into a
and is given as ξ /(b –a). For crude oil operations, there are three distiller; ζ = volume of crude oil to be fed into a distiller; and [ε,
types of ODs: crude oil unloading from a tanker to storage tanks, η] is a time interval in which ε and η are the start and end time
transportation from storage tanks to charging tanks, and feeding points for feeding this parcel of crude oil.
from charging tanks to distillers, denoted by ODU, ODT, and ODF, With Definition 2, let FP ij = (COTij , ζij , [εij , ηij ]) denote the
respectively. Their time durations are denoted as [ρ, δ], [λ, μ], j th FP for feeding Distiller i . Assume that there are Q FPs for
and [ω, π ], respectively. ODF ki is used to denote the i th OD for feeding Distiller i during the scheduling horizon. Then, a refining
feeding distiller k . Let  = [τs , τe ] denote the scheduling horizon, schedule for Distiller i is defined as RSi = {FPi 1 , FP i 2 , . . . ,
g = ξ /(δ –ρ), f = ξ /(μ–λ), and h = ξ /(π –ω) denote flow rates for FP iQ }. With K distillers in the system, let DS = {1, 2, . . . , K } be
tanker unloading, pipeline transportation, distiller feeding decided the index set of distillers and fij = ζij /(ηij –εij ). Then, the refining
by ODs, respectively, and K denote the number of distillers. scheduling problem is to find an ordered set of FPs RS = {RS 1 ,
Given the system state at τs , the short-term scheduling problem is RS 2 , . . . , RS K } such that the following conditions are satisfied.
described as follows:
τs = εi 1 , ηi 1 = εi 2 , . . . , ηij = εi (j +1) , . . . , ηi (Q−1 ) = εiQ ,
SCHD = {ODU1 , . . . , ODUw , ODT1 , . . . ,
and ηiQ = τe , ∀i ∈ DS (3)
ODTz , ODF1 , . . . , ODFK } (1)
Fi (MIN) ≤ fij ≤ Fi (MAX) , ∀i ∈ DS (4)
subject to
where Fi (MIN) and Fi (MAX) are the permissible minimum and
ωk 1 = τs , πk 1 = ωk 2 , . . . , πk (i −1) = ωki , . . . , maximum flow rates for feeding Distiller i , respectively. A sample
and πkn = τe , ∀k ∈ {1, 2, . . . , K } (2) of refining schedule from a real-life refinery is shown in Fig. 3,
where there are three distillers and two FPs for each distiller with
and the above resource and process constraints. a 10-day scheduling horizon.

595 IEEJ Trans 11: 593–603 (2016)

 Y. HOU, N. WU, AND Z. LI

Because of the computational complexity for solving the

Distiller1 Oil #1 Oil #5 detailed scheduling problem by a mixed integer programming for-
mulation, it cannot be solved efficiently by an exact way. A good
Oil #6 Oil #7
choice is to use heuristics or meta-heuristics. However, by such
Distiller2
methods, it requires that the jobs to be scheduled should be known
a priori. As presented by Definition 2, the jobs for the short-term
Distiller3 Oil #3 Oil #4
scheduling problem of crude oil operations are ODs. With COT, ξ ,
Time (H) S , D, and INT being decision variables, the ODs are to be deter-
0
20 40 60 80 100 120 140 160 180 200 220 240 mined by a schedule, but are not known at the beginning of the
scheduling horizon. Thus, to make meta-heuristic applicable to the
Fig. 3. A sample of refining schedule problem addressed, one needs to solve this problem in a different
way. This work converts the problem to a different one such that
Based on the schedulability conditions obtained in GA can be applied.
Refs. [7,25,34,36], an efficient approach is presented in Refs. [31,37]
to find an optimal and realizable refining schedule for optimizing
Objectives (a) and (b). 3.2. Properties of the problem It follows from the
definition in Section 2 that a schedule for crude oil operations
is composed of a series of ODs. By Definition 2, the execution
3. Detailed Scheduling and Its Properties of an OD changes the states of some devices in the system, or it
3.1. Detailed scheduling problem A refining schedule transfers the system from one state to another. To make sure that
is a target in scheduling crude oil operations, and it should be a detailed schedule can be found, the concept of a safe state is
realized by a detailed schedule defined by (1). Examine a refining defined as follows.
schedule RS, an RS i for Distiller i specifies COT ij , ζij , and Definition 3 : An initial state Z at time zero for crude oil
[εij , ηij ], which requires that, at time εij , some amount of oil of operations is said to be safe if there exists a feasible short-term
type COT ij should be in some charging tanks. If, otherwise, the schedule for a scheduling horizon  = [0, ∞].
charging tanks used for feeding Distiller i are occupied by oil type It should be pointed out that, since the operation of distillers
other than type COT ij , the refining schedule cannot be realized. cannot be interrupted, by starting from state Z , one may find a
Thus, to find a detailed schedule for realizing a given refining feasible schedule SCHD 1 for horizon [0, τ1 ]. However, a feasible
schedule is to transport the right types of crude oil with the right schedule SCHD 2 for schedule horizon [0, τ2 ] with τ2 > τ1 may not
volume at the right time to the right charging tanks. Also, we need exist. Hence, in Definition 3, the scheduling horizon is required to
to use the right charging tanks to feed the right distillers at the right be  = [0, ∞]. A state is safe if, at this state, the schedulability
time with the right volume. Notice that, for an FP ij for Distiller i , conditions presented in Refs. [25,27,34] are satisfied. Let denote
no information about charging tanks is specified. Thus, generally the oil residency time, fdsi be the feeding rate to Distiller i , and
it should be realized by several ODFs, i.e., more than one charging Fpmax be the maximum flow rate of the pipeline. We state the
tank is required to sequentially feed the oil specified in FP ij . In schedulability conditions as follows.
other words, the detailed scheduling problem is to find a series of Theorem 1 [25]: Assume that (i) the feeding rate for the K
ODUs, ODTs, and ODFs such that each FP ij is exactly realized distillers DS 1−K is fds1 > fds2 > . . . > fdsK , α1 = × fds1 , α2 =
by a number of ODFs. × fds2 , . . . , and αK = × fdsK ; (ii) there are 2K + 2 charging
One issue for the detailed scheduling problem is whether a given tanks TK 1 – (2K +2) with capacities ξ1 ≥ K α1 , ξ2 ≥ K α1 , ξ3 ≥ K α1 ,
refining schedule is realizable. This can be done with the schedu- ξ4 ≥ K α2 , ξ5 ≥ K α2 , . . . , ξ2i ≥ K αi , ξ2i +1 ≥ K αi , . . . , and ξ2K ≥
lability conditions derived in Refs. [25,34]. Thereafter, we assume K αK , ξ2K +1 ≥ K αK , ξ2K +2 ≥ K αK ; (iii) Fpmax = fds1 + fds2 +
that a given refining schedule is always realizable. To solve the . . . + fdsK ; (iv) initially, the volume of oil type 1 in TK 1 and TK 2 is
detailed scheduling problem, by using the schedulability condi- ζ1 = ζ2 = K α1 , the volume of oil type 2 in TK 4 is ζ4 = K α2 , . . . ,
tions, a feasible detailed schedule is easily found by transferring a the volume of oil type i in TK 2i is ζ2i = K αi , . . . , the volume
system from a safe state to another safe one, as in Refs. [25,34]. of oil type K in TK 2K is ζ2K = K αK ; the other tanks are empty,
By doing so, a detailed schedule can be found OD by OD in and the oil in TK 1 , TK 4 , . . . , TK 2i , . . . , and TK 2K is ready to
a recursive way. Nevertheless, in this way, the obtained detailed feed; (v) the volume of crude oil of type K remaining in storage
schedule is just a feasible one, and no objective is optimized. tanks is β < αK , and after processing this amount of oil type K ,
Notice that, among the objectives for the short-term scheduling distiller DS K should switch to process oil type j . Then, the system
problem of crude oil operations, Objectives (a) and (b) are related is schedulable and the volume β of oil type K can be used up
to the refining scheduling problem, while Objectives (c)–(e) are without being mixed with other oil type.
involved in the detailed scheduling problem. One should optimize By Theorem 1, for a state, the schedulability conditions specify
these objectives in finding a detailed schedule. (i) the crude oil inventory in tanks and the pipeline; (ii) the
Up to now, there is no efficient method for the detailed schedul- operations that are being performed; (iii) the available charging
ing problem of crude oil operations such that the relevant objec- tanks; and (iv) the production rate. They present the boundary for
tives are optimized. Of course, one can formulate the detailed finding a feasible schedule and require that (a) generally it needs
scheduling problem of crude oil operations as a mixed integer three charging tanks for feeding a distiller; (b) the production rate
programming problem as done in the literature. Notice that, by a is bounded by the flow rate of the pipeline; and (c) the amount
detailed schedule, one should provide all the activities in every of oil in the charging tanks at the initial state. In practice, these
detail for all the devices and production units. As pointed out conditions can be well satisfied if the system is properly operated.
by Honkomp et al . [5], it is the detail that makes the short-term By the definition of a refining schedule RS, the production rate
scheduling problem too difficult to be solved. In fact, if a mixed is decided and an FP ij should be realized by a number of ODFs.
integer programming formulation is used, there will be hundreds Given a refining schedule RS, to find a detailed schedule, one
of thousands of binary variables for a real-life application prob- needs to find a series of ODs such that an FP ij in the RS can be
lem [27]. It is impossible to solve such a large problem by an exact realized by dividing it into m ODFs, i.e., ODF ij 1 , ODF ij 2 , . . . , and
way as mathematical programming models do in an acceptable ODF ijm , and the schedulability conditions given in Theorem 1 are
time. satisfied. To simplify the presentation, without loss of generality,

596 IEEJ Trans 11: 593–603 (2016)

 A GENETIC ALGORITHM APPROACH TO SHORT-TERM SCHEDULING

we assume that there is enough storage capacity in storage tanks Property 2 : By the OTR, given a realizable refining schedule,
to unload crude oil from tankers. Also, by assumption, a given a detailed schedule is determined by the assignment of charging
refining schedule is realizable, which implies that there is enough tanks.
crude oil in the storage tanks for realizing the schedule such that Proof : Assume that, at state Zk , charging tank TK h is released
when an ODT is created, one can omit variable S (a storage tank) and assigned to serve for feeding DS i , which results in the creation
in it. Thus, the key is how to transport crude oil from storage tanks of ODT ih . Then, one knows how much oil has been fed into DS i
to charging tanks. Let denote the oil residency time, and fpmax and how much oil is for feeding DS i in the charging tanks at
and fi be the maximum flow rate of the pipeline and the feeding that time. The FP ij that is partially realized by ODT ih and the
rate of Distiller i decided by the refining schedule, respectively. remaining volume ζ1 for FP ij to be transported from the storage
Then, we have the following property. tanks to charging tanks are known too. Further, assume that, in
Property 1: Given a realizable refining schedule, a feasible creating ODT ih , at most volume ζ2 of oil can be transported such
detailed schedule to realize the refining schedule can be found that the resulting state Zk +1 is safe. According to the schedulability
by determining the ODs one by one in a recursive way by using conditions, if one sets ζh ≤ ζ2 in creating ODT ih , the resulting
the schedulability conditions in Refs. [25,27,34]. state is still safe. Thus, in creating ODT ih , by applying OTR we
Proof : By assumption, the given refining schedule is realizable, set ζh = min(ζ1 , ζ2 ). This implies that every time a charging tank
or at initial state Z0 , Conditions (i) and (iii) are satisfied. By is assigned to serve a distiller, an ODT is determined and followed
starting from Z0 , when, for the first time, a charging tank, say Tank by an ODF. In this way, if a charging tank assignment sequence is
#1 denoted as TK 1 , is released, one can decide to assign it to serve determined, a detailed schedule to realize a given refining schedule
for feeding a distiller, say Distiller i denoted as DS i by using the is determined. 
schedulability conditions. Given a refining schedule, the oil type Property 2 shows that the detailed scheduling problem can be
and volume for FP i 1 are COT i 1 and ζi 1 , respectively. Assume that solved by determining the charging tank assignment sequence in a
the volume of oil with type COT i 1 in the charging tanks is ζ0 . At dynamic way. It should be pointed out that, when a charging tank
the same time, we can charge TK 1 with volume ζ1 ≤ ζi 1 –ζ0 such TK h is released, it can be assigned to serve different distillers, and
that the resulting state is safe and the end time of charging TK 1 is the volume and type of oil to be transported from the storage tanks
earlier than ζ0 /fi – . In this way, an ODT i 1 is created by setting to TK h in creating the ODT ih are different as well, which results
COT = COT i 1 , ξ = ζ1 , D = TK1 , and b –a = ζ1 /fpmax . Notice that in different performance. Assume that before the release of TK h ,
a is the moment when TK 1 becomes empty. In this way, a and the oil type in it is #1. If it is assigned to DS i , it is charged with oil
b are decided. With ODT i 1 created, an ODF i 1 for feeding DS i type #2. However, if it is assigned to DS j , it may be charged with
can be created by feeding volume ζ1 in TK 1 after feeding volume oil type #3. This implies that different charging tank assignments
ζ0 . Then, after some time, TK 2 is released and assigned to serve result in different cost for Objective (d). With this observation, we
for feeding DS i again. Hence, ODT i 2 is created for charging TK 2 have the following property.
with ζ2 , and ODF i 2 is created for feeding DS i by TK 2 . In this Property 3: Given a realizable refining schedule, the detailed
way, one can create ODT i 1 , ODT i 2 , . . . , and ODT ig such that scheduling problem is equivalent to finding an optimal charging
ζ1 + ζ2 + . . . + ζg = ζi 1 –ζ0 . Then, when charging tank TK g+1 is tank assignment sequence by using the schedulability conditions.
assigned for feeding DS i , ODT i (g+1) is created to charge TK g+1
By Property 3, the detailed scheduling problem of crude oil
with oil type COT i 2 for FP i 2 and volume ζg+1 ≤ ζi 2 such that
operations is converted to sequencing the charging tank assign-
the end time of charging TK g+1 is earlier than ζi 1 /fi – . Based
ment. With the charging tanks being a kind of resources in a
on the schedulability conditions, this process continues such that,
refinery, this problem is a resource assignment problem, which
given a DS i , every FP ij is realized by a number of ODTs and
is somehow similar to the scheduling problem of discrete man-
ODFs. Similarly, for any DS k , every FP kj can be realized in this
ufacturing processes. Notice that the oil to be processed and the
way. Notice that every OD is created based on the state resulted
tanks available are known at the beginning. Further, sequencing a
from the execution of the previous OD. By doing so, the ODs are
set of resources is an optimization problem for a discrete manufac-
created one by one in a recursive way. 
turing system. Hence, meta-heuristics can be used, or we make the
By Property 1, given a refining schedule, one can find a feasible
short-term scheduling problem of crude oil operations solvable by
detailed schedule in a simple way without solving a mixed integer
meta-heuristics. In this way, we overcome the challenging problem
programming problem. It follows from the proof of Property 1
that meta-heuristics are not applicable to the original short-term
that, when a charging tank is available and is assigned for feeding
scheduling problem of crude oil operations. Since GA is powerful
a distiller, an ODT is created. Then, based on the ODT, an ODF is
in combinatorial optimization, based on this problem conversion,
created. In this way, to find a detailed schedule, the key is to assign
the charging tanks. In creating an ODT for a distiller, to realize a a GA method is presented to solve the problem next.
given refining schedule, the type of oil is already determined and
the variable to be decided is the volume of oil to be charged into 4. Genetic Algorithm for Solution
the charging tank. We present the following rule to determine the
volume for creating an ODT. From the above analysis, the short-term scheduling problem of
Oil transportation rule (OTR): Assume that, at state Zk , charg- crude oil operations is converted to another optimization problem,
ing tank TK h is released and assigned to serve for feeding Distiller i.e. the charging tank assignment and sequencing problem to
i , resulting in the creation of ODT ih to transport volume ζh of oil minimize Objectives (c)–(e). When a charging tank is released,
from the storage tanks to TK h . Then, ζh is set as large as possible it can be assigned to serve for feeding any of distillers if the
such that the resulting state Zk +1 after the execution of ODT ih is schedulability conditions are satisfied. Given a refining schedule,
safe. once such a decision is made, by using the OTR, the type
Notice that, by making ζh as large as possible, we minimize of oil and its volume to be transported via the pipeline for
the number of switches from one type of crude oil to another in charging this tank are also determined. Different charging tank
transporting crude oil from storage tanks to charging tanks via assignments have different effects on the number of COT switches
the pipeline. Also, an ODF ih is created for feeding DS i based on in oil transportation via the pipeline and the number of charging
ODT ih such that volume ζh can be fed into DS i without charging tank switches in distiller feeding, resulting in different cost for
the tank switch. By doing so, one minimizes both Objectives Objectives (c)–(e). An optimization method is necessary to solve
(c) and (e). this problem and a GA approach is presented to do so next. Notice

597 IEEJ Trans 11: 593–603 (2016)

 Y. HOU, N. WU, AND Z. LI

Z0
of crude oil operations. One needs a code to describe the routes
from root Z0 to the leaves. To do so, we define a chromosome
X defined as X = (a1 , a2 , . . . , ai , . . . , aN ), where ai ∈ DS is an
Z1 Z2
integer and N is the number of nodes from the root to the leaf on
ZK
each route. By ai ∈ DS representing a distiller ai , it means that the
i th released charging tank is assigned to feed distiller ai . It follows
Z 11 Z 12
from the above discussion and the OTR that, by ai , an ODT can
Z 1K
be decided and then an ODF. Thus, X = (a1 , a2 , . . . , ai , . . . , aN )
describes a schedule. One problem is how to determine N , the
number of nodes on a route, since it is not known in advance and is
route-dependent. Furthermore, the number of nodes is different for
Fig. 4. The K -tree for the problem
different routes. To solve this problem, unlike general application
of GA, we allow N to vary, or the codes for the solutions can
that, during the scheduling horizon, a charging tank can be charged have variable lengths. With such a code, we present how a GA for
several times and a charging tank can be used to feed any distiller. the detailed short-term scheduling problem of crude oil operations
Due to the feasibility issue and that the charging tanks are not can be implemented next.
available at the beginning, the charging tank sequencing for crude
oil operations is different from general resource sequencing for 4.2. Length of chromosome To implement a GA with
scheduling discrete manufacturing. Hence, we cannot simply apply variable length of code, the problem is how to code the chromo-
the existing methods. The key is how to describe the problem by some. Assume that there are totally  routes in Fig. 4 and the
the GA technique. number of charging tank release times for the i th route is Ni ,
As shown in Fig. 4, assume that, at initial state Z0 , the charging i ∈ {1, 2, . . . , }. Then, for the i th route, a decision of charging
tank TK i is released; it can be assigned to serve for any of the tank assignment should be made for the j th release of a charg-
K distillers if the schedulability conditions can be satisfied, or ing tank with j ≤ Ni . In this case, aj ∈ DS should be decided for
there may be K assignment choices denoted as D1 , D2 , . . . , DK . feeding the distiller. When j > Ni , a schedule has been already
When these different assignment choices are executed, the system obtained and one does not need to create any OD. In this case,
is transferred into different states denoted as Z1 , Z2 , . . . , and ZK , we define aj = 0, indicating that a detailed schedule is already
respectively. Further, when D1 is selected and executed, Z1 is found when node Ni is reached. In this way, the codes for the
reached such that charging tank TK i is charged with the crude problem have different lengths. Let N ≥ max{N1 , N2 , . . . , N } be
oil decided by D1 . Then, TK j is released next. There may also be the length of the chromosome. Then, ∀i ∈ {1, 2, . . . , }, Xi can
K assignment choices denoted as D11 , D12 , . . . , and D1K , which be coded as Xi = (a1 , a2 , . . . , aj , . . . , aN ) such that aj ∈ DS if
transfer the system into different states denoted as Z11 , Z12 , . . . , j ≤ Ni , and aj = 0 if j > Ni . By doing so, every schedule can
and Z1K , respectively. This process can be described by a graph be coded by the above chromosome. One can choose an integer N
shown in Fig. 4. In this graph, from each node (state), there are K that is large enough such that N ≥ max{N1 , N2 , . . . , N } is guaran-
branches and it is called a K -tree. In this graph, there is a route teed. However, an unnecessarily large N can result in unnecessary
from Z0 to each leaf, which forms a schedule. Since different computation in finding a schedule and it is meaningful to set a
charging tank assignments result in different number of charging suitable N . Although max{N1 , N2 , . . . , N } is unknown in advance
tank release times, the number of nodes on different routes is and cannot be exactly calculated, we can obtain a reasonable N as
different. Assume that, at state Zj , charging tank TK i is released, follows. Given a refining schedule and the initial state, the types of
and the assignment choice Dk is selected, i.e. TK i is assigned crude oil and their amount to be transported from the storage tanks
to serve for DS k and would be filled with crude oil decided by to charging tanks via the pipeline are known. Assume that the num-
DK such that ZK is reached. By doing so, the following situation ber of COTs to be transported is n, and their amount is O1 , O2 ,
may occur. At state Zj , before making decision Dk , FP kj has been . . . , and On , respectively. Further, let ζ = min{C1 , C2 , . . . , C }
already realized by a number of ODFs, leading to the fact that Dk and x be the ceiling of x , where Ci is the capacity of charging
is not meaningful. In this case, Dk should be discarded, and the tank i , and  is the number of charging tanks. Then, O1 /ζ +
partial route from Z0 to Zk should be deleted from the K -tree. O2 /ζ + . . . + On /ζ is a reasonable estimation of N . It should
In the K -tree shown in Fig. 4, each route from root Z0 to a leaf be mentioned that, in order to guarantee the realizability of an
corresponds to a detailed schedule with different performance. It obtained refining schedule, the schedulability conditions are taken
can be seen that there may be K n routes in the K -tree, where n is as constraints. Note that improper charging tank assignment may
the number of charging tank release times in a detailed schedule, lead to a situation such that the state of the system reaches the
i.e. the number of schedules is exponential with n. It is inefficient boundary of schedulability conditions. In this case, a charging tank
to find a schedule by enumerating all possible schedules. To solve can be charged to volume ζ such that the number of charging tank
this problem, a GA approach is developed to optimize the detailed release times in a route may be greater than N . Notice that a large
scheduling problem of crude oil operations as follows. N indicates that the number of COT switches in oil transportation
The implementation of GA begins with a population of chromo- via the pipeline and the number of the charging tank switches in
somes (typically generated randomly). One then evaluates these distiller feeding are large, which results in high cost. To improve
chromosomes and allocates reproductive opportunities in such a the performance of the algorithm, when a charging tank assign-
way that the chromosomes representing a better solution to the tar- ment leads to such a case, this assignment is discarded. This is a
get problem are given more chances to reproduce than those that charging tank assignment rule. When a charging tank is released
are poorer [35]. The key here is to design a suitable chromosome and assigned to serve for feeding a distiller, resulting in the cre-
code such that a GA can be implemented. ation of an ODT, one needs to decide the volume ζ of oil to be
charged into the tank. Let ζ1 = min{C1 , C2 , . . . , C } and ζ2 be the
4.1. Chromosome for the problem A chromosome in remaining volume for implementing the corresponding FP. Then,
GA is a code that represents a solution for the problem addressed. the rule is stated as follows:
It follows from the above discussion that a route from root Z0 to Charging tank assignment rule (CTAR): Assume that charging
a leaf represents a solution for the detailed scheduling problem tank TK h is released and assigned to serve for feeding DS i ,

598 IEEJ Trans 11: 593–603 (2016)

 A GENETIC ALGORITHM APPROACH TO SHORT-TERM SCHEDULING

resulting in the creation of ODT ih to transport volume ζh of oil 4.5. Chromosome selection, crossover, and mutation
from the storage tanks to TK h . If ζh decided by the OTR is less With the current population, the next generation is obtained by
than min{ζ1 , ζ2 }, this charging tank assignment is discarded. selection, crossover, and mutation operations. While some of the
With the above discussion, we present the procedure of the GA. current chromosomes are selected to be offspring in the next gen-
eration directly by selection, new ones are generated by crossover
4.3. Initial population With the length of chromosome and mutation. According to Darwin’s evolution theory, the better
determined, initial population should be constructed such that a ones should survive and produce new offspring. The truncation
GA can work. Another important issue is how to ensure the selection method is adopted for selection operation in this paper.
feasibility of a schedule coded by the chromosome. In general, By this method, the chromosomes in the current population are
the chromosomes for the initial population should be generated sorted by their fitness value such that only the excellent ones
randomly. Also, feasibility is essential for a schedule, and a can be selected to be offspring directly. To do so, a param-
member in the population should represent a feasible solution. eter called truncation threshold, denoted as ϕ with 0 < ϕ < 1,
However, with various resource and process constraints for the is set. By the truncation selection method,  = R × ϕ best ones
detailed short-term scheduling problem of crude oil operations, among the current R chromosomes are selected as offspring in the
one cannot guarantee that any chromosome randomly generated next generation population. If Xi is selected, it is renamed as Yi .
represents a feasible schedule. Thus, it is necessary to develop Crossover and mutation are the two basic operations for gener-
a method for generating chromosomes such that both feasibility ating new chromosomes in GA. The uniform crossover method
and randomness are guaranteed. For this purpose, we present the is used for generating new offspring in this work. To imple-
following method to construct an initial population. ment the crossover operation, define an array E = (e1 , e2 , . . . , eN )
Suppose that, at state Zi , TK i is the i th released charging tank. with ei = 0 or 1. For a crossover operation, two chromosomes
Let SD i denote the set of distillers such that at the current state, are randomly selected from the current population as parents, say
according to the schedulability conditions, OTR, and CTAR, TK i X1 = (a11 , a12 , . . . , a1N ) and X2 = (a21 , a22 , . . . , a2N ), for gener-
can be assigned to serve for DS k ∈ SDi . We select a distiller from ating new offspring. With these two selected chromosomes as
SD i , say DS k , and assign TK i to serve for feeding DS k and set parents, according to a given crossover probability, one decides
ai = k . With the schedulability conditions, OTR, and CTAR, an whether a crossover operation should be performed. If not, X1 and
ODT is generated, and then an ODF. After some time, at state Zj , X2 are taken as new offspring, and renamed as Y1 and Y2 . If yes, an
the j th released charging tank is TK j . One can select DS m from array E is randomly generated. Then, for ei = 1, i ∈ {1, 2, . . . , N },
SD j randomly such that TK j is assigned to serve for feeding DS m swap a1i and a2i between X1 and X2 to generate two new offspring
and set aj = m. In this way, a number of aj ’s, j ∈ {1, 2, . . . , Ni }, Y1 and Y2 .
and the corresponding ODTs and ODFs are generated step by step The mutation operation is performed as follows. Rename
until all FP kj are realized by a number of generated ODFs. We Y1 and Y2 that are just obtained by a crossover operation as
then set aj = 0, when Ni < j ≤ N . By doing so, we can obtain H1 = (c11 , c12 , . . . , c1N ) and H2 = (c21 , c22 , . . . , c2N ). For H1 =
a chromosome Xi = (a1 , a2 , . . . , aj , . . . , aN ) that represents a (c11 , c12 , . . . , c1N ), according to a given mutation probability, one
feasible schedule. Notice that, every time when a charging tank decides whether a mutation operation should be performed. If yes,
is released, we randomly select a distiller to be served by the randomly select an index i ∈ {1, 2, . . . , N } and an index j ∈ DS/
released tank. Hence, both feasibility and randomness in generating {c1i }. In H1 , a new chromosome Y1 is generated by setting c1i = j .
a chromosome are guaranteed. With R being the population size, If a mutation should not be performed, H1 is the new offspring and
by the above procedure, R chromosomes X1 , X2 , . . . , and XR can it is renamed as Y1 . In the same way, we can obtain Y2 from H2 .
be generated to form the initial population. By crossover and mutation operations, we generate R –
chromosomes Y1 , Y2 , . . . , Yi , . . . , YR− , where Yi = (b1 , b2 , . . . ,
4.4. Evaluation of fitness function Let Wi denote bj , . . . , bN ) and bj ∈ DS or bj = 0. Together with those obtained
the schedule corresponding to chromosome Xi . When a tank is by selection operation, a new generation with population size
discharged and recharged, if a different oil type is recharged into R is obtained. However, just as above discussed, one can-
the tank, there is a cost; otherwise there is no cost. Thus, for not guarantee that offspring Yi obtained by this means repre-
Objective (d), the cost can be measured by the number of times sents a feasible schedule. One needs to convert Yi to Xi =
for recharging different oil types into tanks. Once a schedule is (a1 , a2 , . . . , aj , . . . , aN ), which corresponds to a feasible solution.
obtained, the type of crude oil that is charged into a charging There are several cases: (i) Yi represents a feasible solution; (ii)
tank is known. When this tank is discharged and recharged, one for Yi , there is at least parameter bj such that FPbj k has been
knows whether a different type of crude oil is recharged to the realized by a number of ODFs; (iii) a partial of Yi with length
tank. In other words, one can count the number of recharging of L< N represents a feasible solution; and (iv) when bN is reached,
different COTs to a charging tank during the scheduling horizon. there is at least one FP kj that has not been realized by a num-
Such a number for all the charging tanks can be calculated. Let ber of ODFs. These cases can be handled as follows to convert
α denote such a number. Similarly, one can count the number of Yi to a feasible chromosome. For Case (ii), start from b1 , just as
COT switches in oil transportation via the pipeline and the number done for the generation of the initial population, and check bi ,
of charging tank switches in distiller feeding for all the distillers. i = 1, . . . , N , to see if bi ∈ SD i . If not, randomly select value j in
They are denoted by β and γ , respectively. SD i and let bi = j , until a feasible chromosome is obtained. For
As discussed in the last section, Objectives (c)–(e) are to be Case (iii), one simply set bj = 0, L < j ≤ N and keep the oth-
optimized for the problem. In other words, this is a multiobjective ers unchanged. For Case (iv), Yi can be simply discarded directly
optimization problem that can be converted to a single-objective since, as discussed above, it is not good. Nevertheless, when Case
optimization problem by using weighted sum. Notice that α, β, and (iv) occurs, one more feasible chromosome should be generated
γ correspond to the indices to be optimized. Notice that, Objectives by using crossover and mutation such that the population size is R.
(c)–(e) are all measured by the number of times. Hence, for In summary, Algorithm 1 is presented to implement the conver-
the GA method, P (Wi ) = ω1 α + ω2 β + ω3 γ is defined as the sion of Yi ’s to feasible Xi ’s. Meanwhile it records the performance
fitness function, with ω1 , ω2 , and ω3 being the constant weighted indices α, β, and γ . In the algorithm, p is used to denote the
coefficients. One can adjust ω1 , ω2 , and ω3 to change the effects position in Yi and Xi ; M0 is a large integer number; and TC is the
of α, β, and γ . set of charging tanks.

599 IEEJ Trans 11: 593–603 (2016)

 Y. HOU, N. WU, AND Z. LI

DS1 #5 #1
114

DS2 #6 #2
72

DS3 #4 #3
48
Time (H)
0
20 40 60 80 100 120 140 160 180 200 220 240

Fig. 5. The refining schedule for the example

Table I. Initial states for charging tanks

Tank Capacity (ton) Type of oil filled Volume (ton)

TK1 16 000 Oil #5 8000
TK2 34 000 Oil #5 30 000
TK3 34 000 Oil #4 30 000
TK4 34 000
TK5 34 000 Oil #3 30 000
TK6 16 000 Oil #1 16 000
TK7 20 000 Oil #6 16 000
TK8 16 000 Oil #6 5000
TK9 16 000
TK10 30 000
TK11 34 000 Oil #7 28 000
TK12 16 000 Oil #7 16 000

The residence time for each charging tank is 6 hours. It is known

that the crude oil in storage tanks is sufficient to realize the target
refining schedule. Thus, to obtain a detailed schedule is to schedule
the oil transportation via the pipeline and the distiller feeding.
According to the initial state shown in Table I and the refining
schedule in Fig. 5, oil type #7 is not used in the scheduling horizon.
In other words, charging tanks TK11 and TK12 are used for oil
When Case (ii) occurs, Statement 6 modifies the genes in the storing only during this scheduling horizon. Also, from the initial
chromosome such that the released charging tank is randomly state and the refining schedule, the crude oil required by FP11 ,
assigned to a distiller, say distiller k such that FP kj has not been FP21 , FP31 , and part of FP12 and FP32 is available in charging
realized yet. Statements 7–10 calculate α, β, and γ , and obtain the tanks. The crude oil required by FP22 , and the other part of FP12
ODTs and ODFs. When Case (iii) occurs, Statement 15 sets aj = and FP32 should be transported from storage tanks to charging
0 when j > Ni . When Case (iv) occurs, Statement 16 sets a large tanks via the pipeline with volume being 25 992, 49 008, and
value M0 to α, β, and γ such that this chromosome is discarded. 90 000 tons, respectively. That is to say, oil types #1, #2, and #3
need to be transported through the pipeline during the scheduling
4.6. Iteration and termination By Algorithm 1, based horizon. Then, the proposed GA method is applied to find the
on the initial population, a new generation can be obtained and at detailed schedule to minimize P (Wi ).
the same time the fitness function is calculated. Then, this process Computational experiments were carried out to examine the
can be repeated until a termination condition is satisfied. We set performance of the presented GA for the problem. It was coded by
the termination conditions as (i) when the number of generations Visual C++ 6.0 and run on Microsoft Windows XP with Intel(R)
exceeds a threshold value, and (ii) if the value of the fitness Celeron(R) CPU 3.06 GHz, 1.25 GB internal memory.
function remains stable for several generations. When one of the Among the charging tanks usable, tanks TK1 , TK6 , TK8 , and
conditions is satisfied, the iteration terminates. TK9 have the smallest capacity ζ = 16 000. Hence, we have N =
25992/16000 + 49008/16000 + 90000/16000 = 12. In the
experiments, different values of truncation threshold for selection
5. Industrial Case Study
operation and probability for crossover and mutation operation
This section uses a practical case scenario of a refinery in China were tested. It was found that when truncation threshold was 0.3,
to show the application of the proposed method. The refinery has crossover probability was 0.8, and mutation probability was 0.1, a
three distillers named DS1 , DS2 , and DS3 with 12 charging tanks. better performance could be achieved.
Three times each month, a short-term scheduling should be found For this case problem, a number of experiments were carried
for the next 10 days. For this case study, a target refining schedule out to test the performance of proposed method for different
is given in Fig. 5. Then, the short-term scheduling problem is to population sizes. In the experiments, we simply set ω1 = ω2 =
find a detailed schedule to realize the given refining schedule such ω3 = 1 for the fitness function P (Wi ) = ω1 α + ω2 β + ω3 γ .
that the objectives given in this paper are minimized. For computational efficiency, generally, the algorithm converged
The initial states for the 12 charging tanks are shown in Table I. quickly, and a solution was found within 5 s as shown in Fig. 6.
The maximum flow rate of the pipeline is 1250 tph (tons per However, the convergence time was dependent on the population
hour), and during the scheduling horizon the refining rates for size, as shown in Fig. 6. When the population size was less than
DS1 , DS2 and DS3 are 333.3, 291.7, and 625 tph, respectively. 200, the convergence time decreased as the size increased. The

600 IEEJ Trans 11: 593–603 (2016)

 A GENETIC ALGORITHM APPROACH TO SHORT-TERM SCHEDULING

5000 Table II. One of the chromosomes whose fitness value is 18

4500 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12
4000
2 2 1 3 3 3 3 3 0 0 0 0
3500 α=4 β=2 γ = 12
Convergence time (ms)

3000

2500
DS1 TK1 TK2 TK6 TK10
2000 #1
#2
1500 DS2 TK8 TK7 TK4 TK9
#3
#4
1000 DS3 TK3 TK5 TK8 TK1 TK3 TK7 TK5
#5
500 #6
Pipeline TK4 TK9 TK10 TK8 TK1 TK3 TK7 TK
5

0 Time(h)
10 50 100 200 500 1000 10 000 0 20 40 60 80 100 120 140 160 180 200 220 240
Population size
Fig. 9. Gantt chart of the detailed schedule for the case study
Fig. 6. Population size versus convergence time
In the sense of solution quality, for a different population size
Best value Worst value Average value and different selection methods, when the algorithm terminates,
40 the same fitness function value P (Wi ) = 18 is achieved, though
different schedules may be obtained. One of the chromosomes
35
whose fitness value is 18, the best one found by the proposed
30 method, is shown in Table II. Also, the corresponding optimal
values of α, β, and γ are shown in Table II.
Fitness value

25
The Gantt chart of the corresponding detailed schedule is shown
20
in Fig. 9, including the detailed schedule of distiller feeding and
15 charging tank filling through the pipeline, where different colors
10
represent different oil types.
By using the schedulability conditions, a feasible detailed
5 schedule can be found to realize the refining schedule in Ref. [27].
0 The objective is P (Wi ) = 21 for the schedule obtained in
0 20 40 60
Ref. [27]. This implies that, by using the proposed GA method,
Generation
the performance is improved by (21–18)/21 ≈ 14%. This is a
Fig. 7. Fitness value by using truncation selection significant improvement.
This case study shows that, given a realizable refining schedule,
a satisfactory detailed schedule can be efficiently found by the
Best value Worst value Average value
proposed GA method. It should be pointed out that this case study
40 is a practical scenario and it is typical in real-life application. This
35
shows that the proposed GA method is applicable to real refineries.

30
6. Conclusions
Fitness value

25
As one of the manufacturing systems, crude oil operations in a
20 refinery involve both discrete events and continuous processes and
are characterized by a hybrid system. With a discrete event pro-
15
cess, the short-term scheduling problem of crude oil operations is
10 inherently combinatorial and is NP-hard [6]. Furthermore, for such
5 a problem, the jobs (operations) to be scheduled should be defined
during the scheduling process. Thus, heuristics and meta-heuristics
0 are very difficult to apply, and thus mathematical programming
0 20 40 60
Generation models are used to study it. By such models, however, one cannot
overcome the problem of computational complexity. To solve this
Fig. 8. Fitness value by using stochastic universal sampling problem, the short-term scheduling problem of crude oil opera-
tions was studied from the control theory perspective by deriving
shortest convergence time occurred when population size was 200. schedulability conditions [25,27,34,36]. Based on the schedulabil-
When the population size was greater than 200, the convergence ity conditions, the problem could be decomposed into two subprob-
time increased as the size increased. lems in a hierarchical way. Then, an efficient approach was pre-
With the population size of 200, we carried out the experiment sented to find the refining schedule at the upper level [31,37]. Also,
using the truncation selection and stochastic universal sampling, with the schedulability conditions, a feasible detailed schedule at
respectively. The trends of the best, worst, and average fitness the lower level could be found recursively without optimizing any
values with respect to the number of generations are shown in objective [25,27,34]. In fact, for detailed scheduling, there are a
Figs. 7 and 8, respectively. As shown in Fig. 7, the best fitness number of objectives to be optimized. These objectives include
value could not be updated after the ninth generation, and a (i) minimization of the number of COT switches in oil transporta-
premature convergence happened when truncation selection was tion via a pipeline; (ii) minimization of COT mixing in charging
applied. As shown in Fig. 8, by using a stochastic universal and discharging a tank; and (iii) minimization of the number of
sampling, the best value remained unchanged after the 25th charging tank switches in crude oil feeding. To optimize a detailed
generation. It shows the convergence of the proposed algorithm. schedule, the detailed scheduling problem was transformed into

601 IEEJ Trans 11: 593–603 (2016)

 Y. HOU, N. WU, AND Z. LI

charging tank assignment and sequencing problem. Then, a method Wi : The schedule corresponding to chromosome Xi .
was proposed to generate a feasible initial schedule such that the P (Wi ): Fitness function of schedule Wi .
initial population could be obtained. To do so, a GA method was α: The number of different COTs in recharging the charging
developed to solve the problem. With a practical case problem, tanks.
experiments showed that the proposed method works well. β: The number of COT switches in oil transportation via the
This work focused on how to make GA applicable to the pipeline.
scheduling problem of crude oil operations. How to improve the γ : The number of charging tank switches in distiller feeding.
performance of a GA is an important issue, which can be pursued φ: Truncation threshold.
in future work. p: Position in chromosome Yi and Xi .
The detailed scheduling problem of crude oil operations is TC: The set of charging tanks.
a multiobjective optimization problem. Nevertheless, this paper X = (a1 , a2 , . . . , ai , . . . , aN ): A chromosome, where ai ∈ DS.
transformed the multiple objectives into a single objective by E = (e1 , e2 , . . . , ei , . . . , eN ): An array with ei = 0 or 1.
using a weighted function. Notice that these objectives may be not Yi = (b1 , b2 , . . . , bi , . . . , bN ): A chromosome, where bi ∈ DS.
consistent. Thus, it is meaningful to explore the effect of different Hi = (ci 1 , ci 2 , . . . cii , . . . , ciN ): A chromosome,
objectives. This is our future work. where cii ∈ DS.

Acknowledgments References
This work was supported partly by the FDCT of Macau under Grants
065/2013/A2 and 078/2015/A3, and NSF of China under grant 61273036. (1) Moro LFL. Process technology in the petroleum refining indus-
try—current situation and future trends. Computers and Chemical
Nomenclature Engineering 2003; 27(8):1303–1305.
(2) Aspen Technology Inc. PIMS System Reference, Version 11.0. Aspen
OD: Operation decision. Technology Inc: Cambridge, MA; 1999.
COT: Crude oil type. (3) Bonner & Moore. RPMS (Refinery and Petrochemical Modeling
ξ : Volume of crude oil to be delivered by an OD. System): A System Descriptive. Bonner & Moore Management
S: Source device from which crude oil is to be transferred. Science: Houston, TX; 1979.
(4) Pelham R, Pharris C. Refinery operation and control: a future vision
D: Destination to which oil is delivered.
Hydrocarbon Processing1996; 75(7):89–94.
INT = [a, b]: Time interval, with a and b being the start and
(5) Honkomp SJ, Lombardo S, Rosen O, Pekny JF. The curse of real-
end time points of an operation. ity—why process scheduling optimization problems are difficult in
ODU: OD for crude oil unloading. practice Computers and Chemical Engineering 2000; 24(2):323–328.
ODT: OD for crude oil transportation via a pipeline. (6) Floudas CA, Lin XX. Continuous-time versus discrete-time appro-
ODF: OD for crude oil feeding to distillers. aches for scheduling of chemical processes: a review. Computers
[ρ, δ]: Time interval for ODU. and Chemical Engineering 2004; 28(11):2109–2129.
[λ, μ]: Time interval for ODT. (7) Wu NQ, Chu F, Chu CB, Zhou MC. Short-term schedulability anal-
[ω, π ]: Time interval for ODF. ysis of crude oil operations in refinery with oil residency time
ODFki : The i th OD for feeding distiller k . constraint using Petri net. IEEE Transactions on Systems, Man, and
 = [τs , τe ]: Schedule horizon, where τs and τe are start and Cybernetics, Part C 2008; 38(6):765–778.
(8) Glismann K, Gruhn G. Short-term scheduling and recipe optimization
end time, respectively.
of blending processes. Computers and Chemical Engineering2001;
g: Flow rate for tanker unloading.
25(4–6): 627–634.
f : Flow rate for pipeline transportation. (9) Kelly JD, Forbes JF. Structured approach to storage allocation
h: Flow rate for distiller feeding. for improved process controllability. AIChE Journal 1998; 55(8):
K : The number of distillers. 1832–1840.
SCHD: Short-term schedule for crude oil operations. (10) Lee H, Pinto JM, Grossmann IE, Park S. Mixed-integer linear pro-
w : The number of ODUs for a schedule. gramming model for refinery short-term scheduling of crude oil
z : The number of ODTs for a schedule. unloading with inventory management. Industrial and Engineering
FP: Feeding parcel of crude oil. Chemical Research 1996; 35(5):1630–1641.
ζ : Volume of crude oil to be fed into a distiller. (11) Pinto JM, Joly M, Moro LFL. Planning and scheduling models for
[ε, η]: Time interval for feeding a parcel of crude oil. refinery operations. Computers and Chemical Engineering 2000;
24(9–10): 2259–2276.
FPij : The j th FP for feeding Distiller i .
(12) Saharidis GKD, Minoux M, Dallery Y. Scheduling of loading and
RSi : Refining schedule for Distiller i .
unloading of crude oil in a refinery using event-based discrete
DS: The set of distillers. time formulation. Computers and Chemical Engineering 2009;
Fi (MIN ) : Permissible minimal flow rate for feeding Distiller i . 33(8):1413–1426.
Fi (MAX ) : Permissible maximal flow rate for feeding Distiller i . (13) Shah N. Mathematical programming techniques for crude oil schedul-
Z : System state. ing. Computers and Chemical Engineering1996; 20:s1227–s1232.
ODFijm : The mth ODF serving for FPij . (14) Yuzgec U, Palazoglu A, Romagnoli JA. Refinery scheduling of
: The oil residency time in tanks. crude oil unloading, storage and processing using a model predic-
fpmax : The maximal flow rate of the pipeline. tive control strategy. Computers and Chemical Engineering 2010;
fi : The feeding rate of Distiller i . 34(10):1671–1686.
TKi : Tank i . (15) Jia Z, Ierapetritou M, Kelly JD. Refinery short-term scheduling using
continuous time formulation: crude oil operations. Industrial and
DSi : Distiller i .
Chemical Engineering Research 2003; 42(13):3085–3097.
Dk : The k th assignment choice.
(16) Jia Z, Ierapetritou M. Efficient short-term scheduling of refinery
: The number of routes in a K -tree. operations based on a continuous time formulation. Computers and
Ni : The number of nodes on the i th route. Chemical Engineering 2004; 28(6–7):1001–1019.
N : Length of the chromosome. (17) Karuppiah R, Furmanb KC,Grossmann IE. Global optimization for
SDi : The set of distillers when the i th tank is released. scheduling refinery crude oil operations. Computers and Chemical
R: Population size. Engineering 2008; 32(11):2745–2766.

602 IEEJ Trans 11: 593–603 (2016)

 A GENETIC ALGORITHM APPROACH TO SHORT-TERM SCHEDULING

(18) Rejowski R, Jr., Pinto JM. A novel continuous time representa- Yan Hou (Non-member) received the B.S. and M.S. degrees, both
tion for the scheduling of pipeline systems with pumping yield in computer science, from the Yangtze Univer-
rate constraints. Computers and Chemical Engineering 2008; 32(4): sity, Jingzhou, China, in 1999 and 2002, respec-
1042–1066. tively; and the Ph. D degree in industrial engi-
(19) Zhen YJ, Marianthi I. Refinery short-term scheduling using continu- neering from Guangdong University of Technol-
ous time formulation: crude-oil operations. Industrial and Engineer-
ogy (GDUT), Guangzhou, China in 2016. Since
ing Chemical Research 2003; 42(13):3085–3097.
2002, she has been with GDUT Guangzhou,
(20) Mendez CA, Grossmann IE, Harjunkoski I, Kabore P. A simultane-
China. Her research interests include production scheduling, infor-
ous optimization approach for off-line blending and scheduling of
oil-refinery operations. Computers and Chemical Engineering 2006; mation systems, and software engineering.
30(4):614–634.
(21) Wu NQ. Necessary and sufficient conditions for deadlock-free oper-
NaiQi Wu (Non-member) received the B.S. degree in electrical
ation in flexible manufacturing systems using a colored Petri net engineering from the Huainan Institute of Min-
model. IEEE Transactions on Systems, Man, and Cybernetics, Part C ing, Huainan, China, in 1982, and the M.S. and
1999; 29(2):192–204. Ph.D. degrees in systems engineering from the
(22) Wu NQ, Zhou MC. Avoiding deadlock and reducing starvation and Xi’an Jiaotong University, Xi’an, China in 1985
blocking in automated manufacturing systems based on a Petri and 1988, respectively. From 1988 to 1995, he
net model. IEEE Transactions on Robotics and Automation 2001; was with the Shenyang Institute of Automation,
17(5):658–669. Chinese Academy of Sciences, Shenyang, China, and from 1995
(23) Wu NQ, Zhou MC, Li ZW. Resource-oriented Petri net for deadlock to 1998 with the Shantou University, Shantou, China. He moved
avoidance in flexible assembly systems. IEEE Transactions on to the Guangdong University of Technology, Guangzhou, China,
System, Man, & Cybernetics, Part A 2008; 38(1):56–69. in 1998. He has been a Visiting Professor at the Arizona State
(24) Wu NQ, Zhou MC. System Modeling and Control with Resource- University and the New Jersey Institute of Technology, USA,
Oriented Petri Nets. CRC Press, Taylor & Francis Group: New York;
and the University of Technology of Troyes and the University
2009.
of Evry, France. He joined the Macau University of Science
(25) Wu NQ, Chu F, Chu CB, Zhou MC. Short-term schedulability anal-
and Technology (MUST), Taipa, Macau, in 2013. He is currently
ysis of multiple distiller crude oil operations in refinery with oil
residency time constraint. IEEE Transactions on Systems, Man, and a Professor at Macau Institute of Systems Engineering, MUST.
Cybernetics, Part C 2009; 39(1):1–16. His research interests include production planning and scheduling,
(26) Wu NQ, Chu F, Chu CB, Zhou MC. Tank cycling and schedul- manufacturing system modeling and control, discrete event sys-
ing analysis of high fusion point oil transportation for crude oil tems, Petri net theory and applications, intelligent transportation
operations in refinery. Computers and Chemical Engineering 2010; systems, and information assurance. He is the author or coauthor
34(4):529–543. of one book, five book chapters, and more than 130 peer-reviewed
(27) Wu NQ, Chu CB, Chu F, Zhou MC. Schedulability analysis of short- journal papers. He was an associate editor of the IEEE Transac-
term scheduling for crude oil operations in refinery with oil residency tions on Systems, Man, & Cybernetics, Part C, IEEE Transactions
time and charging-tank-switch-overlap constraints. IEEE Transac- on Automation Science and Engineering, IEEE Transactions on
tions on Automation Science and Engineering 2011; 8(1):190–204. Systems, Man, and Cybernetics: Systems, and editor-in-chief of
(28) Wu NQ, Bai LP, Chu CB. Modeling and conflict detection of crude- Industrial Engineering Journal. He has served many international
oil operations for refinery process based on controlled-colored-timed conferences as program committee member, such as the program
Petri net. IEEE Transactions on Systems, Man, & Cybernetics, Part
committee co-chair of the 2012 and chair of the 2013 IEEE Inter-
C 2007; 37(4):461–472.
national Conference on Networking, Sensing and Control.
(29) Wu NQ, Chu F, Chu CB, Zhou MC. Hybrid Petri net modeling
and schedulability analysis of high fusion point oil transportation
ZhiWu Li (Non-member) received the B.S., M.S., and Ph.D.
under tank grouping strategy for crude oil operations in refinery.
degrees in mechanical engineering, automatic
IEEE Transactions on Systems, Man, and Cybernetics, Part C 2010;
40(2):159–175. control, and manufacturing engineering, respec-
(30) Wu NQ, Zhou MC, Li ZW. Short-term scheduling of crude-oil oper- tively, from Xidian University, Xi’an, China, in
ations: Petri net-based control-theoretic approach. IEEE Robotics and 1989, 1992, and 1995, respectively. He joined
Automation Magazine 2015; 22(2):64–76. Xidian University in 1992 and now he is also
(31) Wu NQ, Bai LP, Zhou MC, Chu F, Mammar S. A novel approach to with Macau Institute of Systems Engineering,
optimization of refining schedules for crude oil operations in refinery. Macau University of Science and Technology, Taipa, Macau.
IEEE Transactions on Systems, Man, and Cybernetics, Part C 2012; Over the past decade, he was a Visiting Professor at the Univer-
42(6):1042–1053. sity of Toronto, Technion–Israel Institute of Technology, Martin-
(32) Wu NQ, Zhou MC, Chu F. Short-term scheduling for refinery pro- Luther University of Halle–Wittenburg, Conservatoire National
cess: bridging the gap between theory and applications. International des Arts et Métiers (CNAM), and Meliksah Universitesi. His cur-
Journal of Intelligent Control and Systems 2005; 10(2):162–174. rent research interests include Petri net theory and application,
(33) Shah NK, Li ZK, Ierapetritou MG. Petroleum refining operations:
supervisory control of discrete event systems, workflow model-
key issues, advances, and opportunities. Industrial and Chemical
ing and analysis, system reconfiguration, game theory, and data
Engineering Research 2011; 50(3):1161–1170.
and process mining. Dr Li has been a member of Discrete Event
(34) Wu NQ, Zhou MC, Chu F. A petri net based heuristic algorithm for
realizability of target refining schedule for oil refinery. IEEE Trans-
Systems Technical Committee of the IEEE Systems, Man, and
actions on Automation Science and Engineering 2008; 5(4):661–676. Cybernetics Society, and a member of IFAC Technical Commit-
(35) Whitley D. A genetic algorithm tutorial. Statistics and Computing tee on Discrete Event and Hybrid Systems from 2011 to 2014.
1994; 4(2):65–85. He serves as a frequent reviewer for 40+ international journals
(36) Wu NQ, Zhou MC, Bai LP, Li ZW. Short-term scheduling of crude oil including Automatica and a number of the IEEE Transactions as
operations in refinery with high fusion point oil and two transportation well as many international conferences. He is listed in Marquis
pipelines, Enterprise Information Systems 2016; 10(6): 581–610. Who’s Who in the world, 27th Edition, 2010. He is a recipient of
(37) Wu NQ, Bai LP, Zhou MC. An efficient scheduling method for crude an Alexander von Humboldt Research Grant, Alexander von Hum-
oil operations in refinery with crude oil type mixing requirements, boldt Foundation, Germany. He is a senior member of the IEEE
IEEE Transactions on Systems, Man, & Cybernetics: Systems 2016; and is the founding chair of Xi’an Chapter of IEEE Systems, Man,
46(3): 413–426. and Cybernetics Society.

603 IEEJ Trans 11: 593–603 (2016)