# Hybrid Petri net modeling and schedulability analysis of high fusion point oil transportation under tank grouping strategy for crude oil operations in refinery

Naiqi Wu, Feng Chu, Mengchu Zhou

► To cite this version:

Naiqi Wu, Feng Chu, Mengchu Zhou. Hybrid Petri net modeling and schedulability analysis of high fusion point oil transportation under tank grouping strategy for crude oil operations in refinery. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2010, 40 (2), pp.159-175. 10.1109/TSMCC.2009.2032661. hal-00645147

HAL Id: hal-00645147

https://hal.science/hal-00645147v1

Submitted on 12 Jul 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Hybrid Petri Net Modeling and Schedulability Analysis of High Fusion Point Oil Transportation Under Tank Grouping Strategy for Crude Oil Operations in Refinery

NaiQi Wu, Senior Member, IEEE, Feng Chu, Chengbin Chu, and MengChu Zhou, Fellow, IEEE

**Abstract**—There are varieties of constraints for a short-term scheduling problem of crude oil operations in a refinery. These constraints are difficult to model and complicate the short-term scheduling problem. Among them, oil residency time and high fusion point crude oil transportation constraints are the challenging ones. With high setup cost for high fusion point oil transportation, it is desired that the volume of high fusion point oil can be transported as much as possible by a single setup. This may result in late transportation of other types of crude oil, leading to the violation of crude oil residency time constraint. These constraints are ignored by existing methods in the literature. To solve this problem, this paper studies the problem in a control theory perspective by viewing an operation decision in the schedule as a control. With this idea, the system is modeled by a hybrid Petri net. With this model and tank grouping strategy, schedulability analysis is carried out and schedulability conditions are presented with tank charging and discharging costs being taken into consideration. These conditions are necessary for determining a refining schedule and can be used to check whether a target-refining schedule is realizable or not. If so, a feasible detailed schedule for the refining schedule can be easily obtained by creating the operation decisions one by one.

**Index Terms**—Crude oil operations, discrete event systems, hybrid system, oil refinery, Petri net.

## I. INTRODUCTION

AS IT can greatly increase profit if a plant is well operated [12], great attention has been paid to the development of effective techniques for the operations of refinery in the

N. Q. Wu is with the Department of Industrial Engineering, School of Mechatronics Engineering, Guangdong University of Technology, Guangzhou 510006, China, and also with the University of Technology of Troyes, Troyes 10000, France (e-mail: nqwu@gdut.edu.cn).

F. Chu is with the Laboratoire d'IBISC FRE CNRS 3190, Université d'Evry Val d'Essonne, CE 1455 Courcouronnes 91020 Evry Cédex, France (e-mail: feng.chu@ibisc.univ-evry.fr).

C. Chu is with the Laboratoire Génie Industriel, Ecole Centrale Paris, Grande voie des Vignes, Châtenay-Malabry Cedex 92295, France (e-mail: chengbin.chu@ecp.fr).

M. C. Zhou is with the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07102-1982 USA, and also with the School of Electro-Mechanical Engineering, Xidian University, Xi'an, 710071, China (e-mail: zhou@njit.edu).

past years. With the installation of advanced control systems for process control and the planning technique well developed by using linear programming-based commercial software [1], [13], there is a gap between the process control level and the planning level [7], [20]. Therefore, to effectively operate an oil refinery plant, it is necessary to integrate process control and production planning by short-term scheduling. A short-term schedule for oil refinery should provide all the activities in every detail for the whole scheduling horizon, it is the detail that makes the short-term scheduling problem so difficult as pointed out by Honkomp et al. [7]. Besides, it is subject to various constraints, including physical and process constraints. If one of the constraints is violated, a short-term schedule becomes infeasible.

However, up to now, it lacks effective techniques and software tools for short-term scheduling problem in oil refinery, because of its extreme complexity. In fact, this job is still done manually by a planner in oil refinery plants. Thus, it is meaningful to search for effective techniques and tools for short-term scheduling, and effort was made to do so in the recent years. The mathematical programming models that are applied to study the scheduling problem of batch processes are modified for short-term scheduling of oil refinery processes and a variety of mathematical programming models are currently available. There are mainly two categories: discrete-time and continuous-time models. The work in [5], [6], [8], [10], [11], [14], and [15] belongs to the former. The main drawback with such models is that there is a huge number of binary variables and makes the problem very difficult to solve.

To overcome the drawback in the discrete-time representation, continuous-time representation is adopted by some researchers [5], [8], [9], and [11]. Although, with these models, the number of discrete variables is reduced significantly, there are nonlinear constraints in it, which makes the problem difficult to solve. Moreover, because of the complexity for the requirement of providing detailed activity, to make the problem solvable, for most of models in both discrete-time and continuous-time models, special assumptions are made, which generally make the solution inefficient or unrealistic for real world cases. Meanwhile, in these models, often some constraints, such as the oil residency time and high fusion point crude oil transportation constraints are ignored. This leads their solutions to be infeasible. Thus, although there is significant progress in theory for the short-term scheduling problem of oil refinery, there is a serious gap
<figure><img src="image_2.png" /><figcaption>Fig. 1. Architecture of short-term scheduling for refinery.</figcaption></figure>

between theory and applications [20]. It is crucial to search for
effective techniques that work well in practical applications.

Short-term scheduling for crude oil operations is one of the
most difficult scheduling problems in operating an oil refin-
ery plant. To reduce the complexity, a new method is proposed
in [21]–[23]. By this method, the problem of short-term schedul-
ing for crude oil operations is decomposed into two subproblems
in a hierarchical way. At the upper level, it finds the refining
schedule to optimize the objectives, such as crude oil inventory
and production rate. At the lower level, it provides the detailed
schedule to realize a given refining schedule. In doing so, it gives
rise to new problems: 1) how can we guarantee that the refining
schedule found is realizable, because, at the upper level, it does
not decide the detailed schedule; and 2) how can we guarantee
that a detailed schedule can be found when a refining schedule is
realizable. In [23], a Petri net (PN)-based heuristic is presented
to check the realizability of a refining schedule, if realizable, a
detailed schedule is found as well. However, if a detailed sched-
ule is not found it cannot guarantee that the refining schedule is
not realizable. Feasibility is essential to the short-term schedul-
ing problem of crude oil operation in a refinery. If schedulability
conditions are known, the upper level subproblem can be solved
by taking these conditions as constraints. In this way, the realiz-
ability of the obtained refining schedule is guaranteed. Thus, if
given a refining schedule, a detailed schedule can be efficiently
obtained with the schedulability conditions, the issue of short-
term scheduling can be resolved. For this purpose, with the archi-
tecture as shown in Fig. 1, schedulability analysis is done in [21]
and [22] and schedulability conditions are presented. These con-
ditions can be used as constraints for finding realizable refining
schedule. At the same time, with these conditions, it is easy to
find detailed short-term schedule for a given refining schedule.

In viewing each operation decision in a short-term schedule as
a control command to the system, its schedulability is analyzed
in a control theory perspective in [21] and [22]. As shown in
Fig. 1, the system is modeled by a hybrid PN. The execution
of an operation decision transfers the system from one state to
another. Thus, if a system is schedulable, the initial state must be
safe and an operation decision should transfer the system from
a safe state to another safe one. Then, a newly reached state
can be seen as an initial state at the time point. This implies

that all the reached states should be safe. Hence, safeness of the
system is equivalent to schedulability [21], [22]. In this way,
with safeness conditions known and the system state given, it
is simple to find an operation decision such that its execution
transfers the system from the given safe state to another safe one,
and the detailed schedule can be obtained by creating operation
decisions one by one given a refining schedule.

In scheduling crude oil operations, there are various con-
straints, including resource and process ones. Resource con-
straints include: 1) the limited number of storage and charging
tanks and the capacity of each tank; 2) the limited flow rate of
oil unloading and pipeline; and 3) the volume of various crude
oil types available in storage and charging tanks and in coming
tankers. Process constraints include: 1) a distiller should be kept
in working all the time uninterruptedly; 2) at least one charging
tank should be dedicated to a distiller at any time for feeding
the latter; 3) a tank cannot be charged and discharged at the
same time; 4) after being charged, the crude oil should stay in
the charged tank for a certain amount of time before it can be
discharged. This is called oil residency time (RT) constraint;
and 5) theoretically, crude oil can be kept in pipeline without
flowing. However, when a type of crude oil with high fusion
point is being transported via a pipeline, such crude oil must be
kept flowing until it goes out of the pipeline; and otherwise the
pipeline will be blocked. This requirement is called high fusion
crude oil transportation constraint. Most of the existing methods
ignore the fourth and fifth process constraints, and there is no
model that deals with the fifth process constraint. This paper
conducts schedulability analysis with all the constraints taken
into account.

With high fusion point crude oil types to be processed, cost
is an important issue and should be considered in scheduling
the system. In crude oil operations, when a tank is discharged
such that there is no oil in the tank can be discharged any more,
this tank is said to be emptied. However, it cannot be really
emptied. Instead there is some oil remaining (usually about 1/6
capacity). Thus, when a tank with oil type *i* in it is emptied,
and is then recharged with oil type *j* with *i*≠*j*, some volume
of high quality oil is likely treated as low quality oil due to
the oil mixture. This leads to a loss, called tank charging and
discharging loss. Therefore, when a tank with oil type *i* in it is
emptied and recharged, it is better to charge the same or similar
type of oil that contains similar components.

Often, different distillers process different types of crude oil
at a time. A distiller may process different crude oil type at
different time. However, these crude oil types processed by
the same distiller at different time are similar. Thus, to reduce
charging and discharging loss, for a time, the charging tanks are
grouped such that each group of charging tanks serve a distiller.
Crude oil to be processed by distiller DSᵢ is charged into the
tanks in the tank group assigned to DSᵢ. We call such strategy
as charging tank grouping. In this paper, this strategy is applied
in analyzing the schedulability so as to reduce scheduling cost
as much as possible.

With the architecture given in Fig. 1, a model that describes
the behavior of the system is necessary. For crude oil oper-
ations, the start and end of crude oil movement are discrete
events and oil flows continuously. Thus, it is a typical hybrid system and should be described by a hybrid model. There are hybrid PN models [2], [3], [4], [16], [24]. However, they cannot be directly used here because they cannot describe the above-mentioned constraints well. The hybrid PN model developed in [21], [22] is modified to model such systems. With it, schedulability conditions are presented that describe the relationship among the number of charging tanks, number of distillers, capacity of charging tanks, production rates, and amount of high fusion point oil that can be transported by a single setup. These conditions provide the base for finding a refining schedule and checking the realizability of a given one. By using them, one can find a detailed schedule for a given realizable refining one.

The contribution of this paper includes: 1) it is the first time that high fusion point crude oil is considered in scheduling crude oil operations; 2) a hybrid PN model is developed to describe such a system; 3) schedulability conditions are presented; 4) with the schedulability conditions, one can derive how much high fusion point crude oil can be transported from storage tanks to charging tanks, which is important in scheduling such systems; and 5) with them, one can easily find a detailed feasible one given a realizable refining schedule.

Next, we briefly introduce the process of crude oil operations and its short-term scheduling problem. The hybrid PN model is developed in Section III. With the PN model, schedulability analysis for systems with one and two distillers is carried out in Section IV. Section V generalizes the results obtained in Section IV into general cases. In Section VI, an industrial case study is presented to show the power and applications of the results obtained. Finally, conclusions are given in Section VII.

## II. PROCESS AND SHORT-TERM SCHEDULING

This section briefly introduces the process of crude oil operations and its short-term scheduling problem. The readers are referred as to [20]–[23] for detail.

In a general refinery process, crude oil is carried to the port by crude oil tankers, where crude oil is unloaded into storage tanks by the port. The crude oil in the storage tanks is transported to charging tanks in the refinery plant through a pipeline. From the charging tanks, oil is fed into distillers for distillation. The middle products from the distillers are then sent to other production units for fractionation and reaction. The products after fractionation and reaction are blended to produce the final products that are ready for delivery. This paper addresses only short-term scheduling problem for crude oil operations from a tanker to distillers.

Often, in a refinery, various types of crude oil are processed. Some crude oil types have fusion point higher than 30 °C, and it is in a solid state under ordinary temperature. To prevent such crude oil from being frozen in the pipeline, the pipeline and the crude oil that is being transported must be kept hot enough. Notice that, generally, a pipeline has tens of kilometers long, it can be heated only by hot crude oil that is flowing through it. Thus, before high fusion point crude oil is to be transported from storage tanks to charging tanks through the pipeline, a certain amount of hot crude oil with low fusion point should

be transported via the pipeline such that the pipeline can be heated first. After it is heated in this way, the heated high fusion point crude oil can be sent to charging tanks through it. After a parcel of such oil is sent to the pipeline, another parcel of crude oil with low fusion point must be sent to it such that the high fusion point crude oil can go out of the pipeline. This results in high set up cost for transporting high fusion point crude oil. Thus, in scheduling crude oil operations, when high fusion point crude oil is transported from storage tanks to charging one, it is desired that it can transport as much as possible, or at least an expected amount by a single setup. Often, in determining a refining schedule, a planner wants to know if a given amount of high fusion crude oil in the storage tanks can be transported to charging tanks for processing by a single setup.

It should be pointed out that when there is crude oil with high fusion point in the pipeline, the oil in it must be kept in flowing; and otherwise the pipeline and oil in it will cool down and the oil will be frozen. This implies that once crude oil with high fusion point is sent to the pipeline there must be enough space in charging tanks to hold the coming crude oil, otherwise, the oil in the pipeline cannot be kept in flowing. With the number of charging tanks limited and there are multiple distillers that process different types of crude oil concurrently, it is a great challenge to schedule the system.

A crude oil operation process is composed of a series of operations. For each operation to take place, a decision should be made. To describe a short-term schedule, we first define an operation decision.

*Definition 2.1:* $OD = (COT, \zeta, S, D, INT = [a, b])$ is defined as an operation decision, where COT is the crude oil type; $\zeta$ is the volume of crude oil to be unloaded from a tanker to a storage tank, or transported from a storage tank to a charging tank, or fed from a charging tank to a distiller; $S$ is the source from which the crude oil is to be delivered; $D$ is the destination to which the crude oil is to be delivered; and $INT$ is a time interval in which $a$ and $b$ are the start and end time points of the operation.

The flow rate in delivering crude oil in $[a, b]$ can be variable. However, in reality, it is kept as a constant for a single operation. Thus, given volume $\zeta$ and time interval $[a, b]$ in an OD, $\zeta/(b-a)$ is determined and used as its flow rate. Each OD is a command that transfers the system from a state to another.

There are three types of ODs: crude oil unloading, transportation, and feeding, denoted by ODU, ODT, and ODF, respectively, and their time interval is denoted as $[\alpha, \beta]$, $[\lambda, \mu]$, and $[\omega, \pi]$, respectively. For ODU, $S$ is a tanker and $D$ is a storage tank. For ODT, $S$ is a storage tank, $D$ is a charging tank, and the transportation must be conducted through a pipeline. For ODF, $S$ is a charging tank and $D$ is a distiller. We use $ODF_{ki}$ to denote the $i$th OD for feeding distiller $k$ during the schedule horizon. Let $\Gamma = [\tau_s, \tau_e]$ be the schedule horizon that often lasts for a week or 10 days and $g = \zeta/(\beta - \alpha)$, $f = \zeta/(\mu - \lambda)$, and $h = \zeta/(\pi - \omega)$ denote flow rates for a tanker unloading, pipeline transportation, and distiller feeding decided by ODs, and $K$ denote index set for the distillers. Given the system state at $\tau_s$, i.e., the inventory of crude oil and state of all the devices, and information of tanker arrival, the short-term scheduling problem
is to find a series of ODs described as follows:

$$SCHD = \{ODU_1, \dots, ODU_w, ODT_1, \dots, \\ ODT_z, ODF_1, \dots, ODF_K\}. \quad (2.1)$$

Subjected to

$$\omega_{k1} = \tau_s, \pi_{k1} = \omega_{k2}, \dots, \pi_{k(i-1)} = \omega_{ki}, \dots, \text{ and } \pi_{kn} = \tau_e, \\ \text{for } \forall k \in K \quad (2.2)$$

the resource and process constraints given in Section I.

Constraint (2.2) requires that the schedule should cover the entire scheduling horizon and a distiller cannot be stopped.

A schedule for crude oil operations may not be feasible. Its feasibility is strongly related to the safeness of the system in a control theory perspective. The execution of an infeasible OD results in an unsafe state. On the other hand, a safe state guarantees the existence of a feasible schedule. This can be explained as follows. An operation decision OD in a schedule is a control that transfers the system from one state to another. If a state is reached such that one or more constraints are violated, this state is said to be an infeasible state. If a state is not infeasible, it must be feasible. Assume that, at time $\tau$, after the action of OD$_1$, OD$_2$, ..., and OD$_i$, the system is transferred from state $M_1$ to $M_i$, and $M_i$ itself is feasible. However, no matter what ODs are applied after time $\tau$, the system will enter an infeasible state. Then, state $M_i$ is called an unsafe state. If a state is not unsafe, it must be safe. If a short-term schedule SCHD = (OD$_1$, OD$_2$, ..., OD$_n$) is obtained such that OD$_1$ transfer the system from $M_1$ to $M_2$, OD$_2$ from $M_2$ to $M_3$, ..., and OD$_n$ from $M_n$ to $M_{n+1}$, and all the states $M_1, M_2, \dots, M_{n+1}$ are safe, the schedule is feasible. On the other hand, at any time, if the system is in a safe state, there must exist a short-term schedule such that the system is always in a safe state.

### III. HYBRID PN MODELING

It follows from the short-term schedule defined in the last section that a hybrid model suitable for short-term scheduling is needed. A hybrid PN is developed for crude oil operations for schedulability analysis in [21] and [22], which consider only the situations without high point crude oil being processed. By modifying it, we present a new hybrid PN model here. We first present the models for devices, e.g., tanks and pipeline. Then, based on the models for devices, the model for the whole system is developed. A reader is referred to [3], [17], [25]–[29] for the basic knowledge of PN.

The PN model used here is a kind of colored-timed PN (CTPN) defined as CTPN = ($P = P_D \cup P_C \cup P_E, T = T_D \cup T_T \cup T_C, I, O, \Phi, M_0$), where $P_D, P_C$, and $P_E$ are sets of discrete, continuous, and enforcing places; $T_D, T_T$, and $T_C$ are sets of discrete, timed, and continuous transitions; $I$ and $O$ are input and output functions; $\Phi(p)$ and $\Phi(t)$ represent the color sets of place $p \in P$ and transition $t \in T$; and $M_0$ is the initial marking. The icons are shown in Fig. 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Icons in the model.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Petri net for a tank.</figcaption></figure>

#### A. Device Modeling

The devices include tanks (storage and charging tanks) and pipeline. A tank is modeled by a PN shown in Fig. 3. A token in a discrete place is a discrete token and acts just as that in ordinary PN. A token in a continuous place represents a type of materials with a real number of volume, called token volume for short. A discrete transition acts just as that in ordinary PN. When a timed transition fires, it delivers a token from a place to another with a constant time delay. When a continuous transition fires, some type of material represented by a token is delivered from a place to another with a known flow rate determined by an OD. Whether the token is completely removed from its input place is determined by its firing duration.

In Fig. 3, continuous places $p_s$ and $p_c$ that can hold at most one token at a time model the state of a tank. A token in either $p_s$ or $p_c$ or both represents that there is crude oil in the tank. However, a token in $p_s$ represents that the oil in the tank is not ready for discharging, and it is ready only if $p_c$ has a token and $p_s$ is empty. Continuous transitions $t_1$ and $t_3$ model the processes of filling to and discharging from a tank. The time delay in $t_2$ models the RT constraint. Thus, when charging oil to a tank stops, a token representing a type of crude oil must stay in $p_s$ for some time. After the time delay specified by $t_2$, a token with a real number of volume moves from $p_s$ to $p_c$, and is ready to be discharged from a tank. Because there is only one token in discrete place $p_4$, only one of transitions $t_1$ and $t_3$ can fire at a time. This guarantees that a tank cannot be filled and discharged at the same time. The self-loop between $p_4$ and $t_2$ together with the inhibitor arc ($p_s, t_3$) guarantees the RT requirement of the oil in the tank before it can be discharged. The volume associated with the token in continuous place $p_3$ models the capacity of
<figure><img src="image_5.png" /><figcaption>Fig. 4. PN model for pipeline.</figcaption></figure>

the tank available at the current marking. Thus, the behavior of the charging and discharging of a tank is exactly described. Thereafter, by $K_i(p_s)$, $K_i(p_c)$, and $K_i(p_s, p_c)$ (or $K_i$ in short) we mean places $p_s, p_c$, and the model for tank $i$.

The PN model in Fig. 4 describes the behavior of a pipeline. It is modeled by a macro transition $t_{\text{pipeline}}$ in which there are continuous places, such as $p_1, p_2$, and $p_3$, connected by discrete transitions in a serial way. A token in a continuous place in $t_{\text{pipeline}}$ represents a segment of crude oil in the pipeline. The tokens in different continuous places represent segments of different crude oil types. When a discrete transition in $t_{\text{pipeline}}$, say $t_1$, is enabled and fires, a token in $p_2$ is removed immediately, and when $t_2$ is enabled and fires, a token enters $p_2$ immediately. Thus, the behavior of a segment in the pipeline for holding one type of crude oil is described by the PN.

The PN model shown in Fig. 4 describes the behavior of the pipeline that can hold three different types of crude oil with continuous places $p_1, p_2$, and $p_3$ in $t_{\text{pipeline}}$. Continuous transitions $t_{I1}$ to $t_{Ik}$ and $t_{O1}$ to $t_{Ok}$ in $t_{\text{pipeline}}$ are used to model the behavior that crude oil flows into and out of the pipeline with a given flow rate. Let $T_I = \{t_{I1}, \dots, t_{Ik}\}$ and $T_O = \{t_{O1}, \dots, t_{Ok}\}$. It should be noticed that, at a time, only one type of crude oil can flow into (out of) the pipeline. This implies that only one transition in $T_I$ and one transition in $T_O$ can fire at a time. When one of transitions in $T_O$ is firing, the token volume in $p_1$ is continuously decreasing until $p_1$ is emptied. When $p_1$ is emptied, $t_1$ is enabled and fires, and the token in $p_2$ is moved into $p_1$ immediately. In this way, one transition in $T_O$ can fire continuously. When one transition in $T_I$, say $t_{I1}$, fires, a token goes into $p_3$ immediately. With the continuous firing of $t_{I1}$, the token volume in $p_3$ increases continuously until $p_3$ is full. The number of continuous places in the model means the number of segments of crude oil of different types in the pipeline. It can be set as the largest number of crude oil segments that may occur. Since the pipeline is modeled as a single macro transition $t_{\text{pipeline}}$, a transition in $T_I$ and another in $T_O$ fire concurrently with the same flow rate. However, the crude oil type flowing into a pipeline may be different from that flowing out of it.

<figure><img src="image_6.png" /><figcaption>Fig. 5. PN model for the whole system.</figcaption></figure>

There is also an enforcing place $p_4$ in $t_{\text{pipeline}}$. Every time, a token enters $p_3$ by firing a transition in $T_I$, a token with the same color and volume goes into $p_4$ too. When there is a token representing a high fusion point crude oil type in $p_4$, it enforces one of transition in $T_O$ to fire, which requires firing of one transition in $T_I$ too. When the token representing a high fusion point crude oil in a continuous place in $t_{\text{pipeline}}$ goes out of $t_{\text{pipeline}}$ by firing a transition in $T_O$, the token in $p_4$ is removed too. For the sake of simplicity, transition $y$ as shown in Fig. 4 is used to represent this process pictorially. Then, a place $p$ in $y$ can be denoted as $p(y)$. When $y$ fires, it implies that one transition in $T_I$ and one transition in $T_O$ fire with the same rate simultaneously, or crude oil is delivered from a storage tank to the pipeline (a place in $y$) by a transition in $T_I$, and at the same time crude oil in $p_1(y)$ is being delivered into a charging tank by a transition in $T_O$.

## B. PN Model for the Whole System

The PN in Fig. 5 gives the illustration for the whole system with two storage and charging tanks, respectively. For the reason of simplicity, we omit the discrete place and its associated arcs, and the inhibitor arc in a tank PN model. Later, we also omit $p_{i3}$. Crude oil in a storage tank is discharged through the pipeline, and then transition $y$ for the pipeline is the discharging transition for every storage tank. Similarly, $y$ is the charging transition for every charging tank. Thus, $\{t_{11}, t_{12}, y, p_{1s}, p_{1c}, p_{13}\}$ and $\{t_{21}, t_{22}, y, p_{2s}, p_{2c}, p_{23}\}$ are for two storage tanks, respectively, and $\{y, t_{31}, t_{32}, p_{3s}, p_{3c}, p_{33}\}$ and $\{y, t_{41}, t_{42}, p_{4s}, p_{4c}, p_{43}\}$ for two charging tanks, respectively. Transition $t_1$ creates a token when a tanker arrives. If a tanker carries $k$ types of crude oil, then $k$ tokens are created with their respective volumes. However, a token can be moved into $p_1$ from $t_1$ only if $p_1$ is empty. Places $p_3$ and $p_4$ represent two distillers. From the definition of a short-term schedule, we know that firing a continuous transition in the PN model must be triggered by an OD. Thus, the dynamics of crude oil flow in the PN model should be governed by the flow rate given in OD. This can be modeled by the transition enabling and firing rules that are defined below.

We use $\bullet t (\bullet p)$ to denote the set of input places of transition $t$ (input transitions of place $p$) and $t^\bullet (p^\bullet)$ the set of output places of $t$ (output transitions of $p$). Let $V(M(p))$ denote the volume of material in $p$ at marking $M$.

**Definition 3.1:** A discrete transition (including discrete ones in $y$) $t$ is said to be enabled at marking $M$, if $M(p) \ge 1$, $\forall p \in \bullet t$ and $M(p) = 0, \forall p \in t^\bullet$. When $t$ fires, $M$ is changed into
$M'$ with $M'(p) = M(p) - 1, \forall p \in t^*$ and $M'(p) = M(p) + 1, \forall p \in t^*$.

Compared with the transition enabling and firing rules for ordinary PN, it requires that $t$'s output places are empty, similarly to that for finite capacity PN. Notice that, in ordinary PN, tokens are discrete, but the tokens in the PN model here may be discrete or continuous. However, to fire a discrete transition, all tokens in the model are treated as discrete one. By Definition 3.1, when some part of oil in $p_1$ in Fig. 4 is discharged, there is still a token in $p_1$ and $t_1$ cannot fire, or a token in $p_2$ cannot go to $p_1$. Only when all the oil in $p_1$ is discharged such that $p_1$ is empty, then $t_1$ can fire and a token in $p_2$ can go to $p_1$. In this way, it guarantees that each continuous place in Fig. 4 can hold one type of crude oil at a time. A timed transition is used only in the PN for a tank to guarantee the RT before oil in a tank can be discharged. Assume that the time associated with a timed transition is $\Psi$. Its enabling and firing rules are defined as follows:

**Definition 3.2:** A timed transition $t$ is said to be enabled at marking $M$ if $M(p_i) \ge 1, \forall p_i \in t^*$. When $t$ starts to fire at time $\tau$, $M$ is changed into $M'$ such that: 1) at $\tau$, $M'(p_i) = M(p_i) - 1$, if $p_i \in t^*$ and $p_i \in P_D$ and $M'(p_i) = M(p_i)$ if $p_i \in t^*$ and $p_i \in P_C$; 2) at $\tau + \Psi$, $M'(p_i) = M(p_i) - 1$ and $V(M'(p_i)) = 0, p_i \in t^*$ and $p_i \in P_C$; and 3) at $\tau + \Psi$, $M'(p_j) = 1$ for $\forall p_j \in t^*$ and $V(M'(p_j)) = V(M(p_j)) + V(M(p_i))$, for $p_j \in t^*$ and $p_j \in P_C$.

Notice that when a timed transition $t$ fires, there may be a token in its output place $p_j$. When the token in the input place $p_i$ moves into $p_j$ these two tokens merge into one with the volume being the sum. This definition is used to describe such a fact that when a tank is neither full nor empty, this tank can still be charged. When it is charged, the volume of oil should be added. Meanwhile, the time delay associated with the timed transition guarantees the RT constraint. In this way, the behavior of a tank is precisely modeled by the PN.

Because there are multiple types of crude oil, it is necessary to distinguish them. To do so, colors are introduced into the PN model. We use $\varphi \in \Phi$ to denote the color of crude oil and say that a token in place $p$ representing crude oil of type $i$ has color $\varphi_i$ and the number of tokens in $p$ with color $\varphi_i$ at marking $M$ is denoted by $M(p, \varphi_i)$, and the volume for this token at $M$ is denoted by $V(M(p, \varphi_i))$. When $V(M(p, \varphi_i)) = 0$, it implies that the number of tokens with color $\varphi_i$ in $p$ is zero. If a continuous transition $t$ is firing to move crude oil type $i$ from a place to another, we say $t$ is firing with color $\varphi_i$. A continuous transition must fire with a color. As discussed above, the volume of a token in $p_3$ in Fig. 3 models the capacity of a tank available. Let $\Theta$ denote the color for such a token. In other words, $p_3$ in each tank's PN model has the same color as the token in $p_3$ and/or $p_c$. Further, let $\Phi_1 \subset \Phi$ be the set of colors for crude oil types with low fusion point and $\Phi_2 \subset \Phi$ be the set of colors for crude oil types with high fusion point with $\Phi_1 \cap \Phi_2 = \emptyset$ and $\Phi_1 \cup \Phi_2 = \Phi$.

**Definition 3.3:** A continuous transition (including transitions in $T_I$ and $T_O$ in $y$) $t$ is said to be enabled with color $\varphi_i$ at marking $M$, if the following conditions are satisfied:

1) $M(p, \varphi_i) \ge 1$ or $M(p, \Theta) \ge 1, \forall p \in t^*$; and

2) $K_j(p_s) \in t^*$ for some $j$, then $M(K_j(p_s), \varphi_i) \ge 1$ or $M(K_j(p_c), \varphi_i) \ge 1$, or $M(K_j(p_s)) = M(K_j(p_c)) = 0$.

By condition 1), it says that, if $p \in P_C$, there must be crude oil with a right color or the tank to be charged must not be full. If $p \in P_E$, it implies that firing $t$ will consume a token in $p$. By 2), it says that the oil in $K_j(p_s)$ has color $\varphi_i$ that is same as that in $p \in t^*$. This implies that if there is crude oil in a tank, only the same type of crude oil can be filled into it. However, if a tank is empty, any type of crude oil can be filled into it. When a continuous transition $t$ is enabled and triggered by an OD, it can then fire. This firing must be associated with a flow rate given in OD, i.e., the flow of crude oil is governed by a flow rate. The transition firing rules below describe this dynamics. We assume that $t$'s firing with color $\varphi_i$ begins at time $\tau_1$, ends at time $\tau_2$, $\tau \in [\tau_1, \tau_2]$, and the flow rate is $f$. Then, the marking changes as follows. At $\tau_1$, if $p \in t^*$ and $p$ is a discrete place

$$M'(p) = M(p) - 1. \quad (3.1)$$

At $\tau_2$, if $p \in t^*$ and $p$ is a discrete place

$$M'(p) = M(p) + 1. \quad (3.2)$$

At $\tau \in [\tau_1, \tau_2]$, if $p \in t^*$ and $p \in P_C$ or $p \in P_E$, and there is a token with color $\varphi_i$ in $p$

$$V(M'(p, \varphi_i)) = V(M(p, \varphi_i)) - (\tau - \tau_1)f. \quad (3.3)$$

If $p \in t^*$ and $p \in P_C$, and there is a token with color $\Theta$ in $p$

$$V(M'(p, \Theta)) = V(M(p, \Theta)) - (\tau - \tau_1)f. \quad (3.4)$$

If $p \in t^*$ and $p \in P_C$ or $p \in P_E$, and there is a token with color $\varphi_i$ in $p$

$$V(M'(p, \varphi_i)) = V(M(p, \varphi_i)) + (\tau - \tau_1)f. \quad (3.5)$$

If $p \in t^*$ and $p \in P_C$ or $p \in P_E$, and there is no token with color $\varphi_i$ in $p$

$$M'(p, \varphi_i) = 1 \quad \text{and}$$

$$V(M'(p, \varphi_i)) = V(M(p, \varphi_i)) + (\tau - \tau_1)f. \quad (3.6)$$

Because any firing of a continuous transition leads to a crude oil operation determined by an OD, expressions (3.1) through (3.6) describe the dynamics of crude oil flow in the PN model for the system. Notice that, with (3.5) and (3.6), when a transition $t$ in $T_I$ in $y$ fires with color $\varphi_i$, a token with color $\varphi_i$ and volume that flows through $t$ is moved into $t$'s output enforcing place. From (3.3), such a token can be removed by firing transitions in $T_O$.

**Definition 3.4:** The PN model for the crude oil operations is live if and only if the following conditions are satisfied.

1) Let $P_{dsl}$ denote the set of places representing the distillers and $|P_{dsl}| = h$. Then, at any time $t$ (or at any marking $M$) for any $p_i \in P_{dsl}$, there exists a $t_i \in t^*$ such that $t_i$ is in firing or enabled and $t_1 \cap t_2 \cap \dots \cap t_h = \emptyset$.

2) If $M(p_4(y), \varphi_i) > 0, \varphi_i \in \Phi_2$, and $p_4(y) \in P_E$, at marking $M$, there exists at least a transition $t \in p_4(y)^*$ is in firing or enabled.
By Definition 3.4, a nonlive state is an infeasible state resulting from an infeasible schedule. Thus, it is necessary to schedule crude oil operations such that the PN model is live. If a schedule can be found such that the PN is live, the system is schedulable. It should be pointed out that the conditions in Definition 3.4 are very easy to check. Thus, the PN model developed here is an effective tool for scheduling the system.

## IV. SCHEDULABILITY WITH ONE AND TWO DISTILLERS

With the PN model developed in the last section, this section analyzes the schedulability and the amount of high fusion point oil that can be transported by a single setup based on charging tank grouping. It assumes that there is always enough crude oil in the storage tanks to be processed, or schedule feasibility is independent of the number of storage tanks and their capacity. Notice that the pipeline always holds some oil in it and we use $C_{pipe}$ to denote its capacity. Hence, when a volume $V_1 > C_{pipe}$ of oil is transported from storage tanks to charging tank CTK$_1$, $C_{pipe}$ of it will remain in the pipeline if there is no other parcel of oil that is transported via the pipeline immediately after $V_1$ volume of oil is transported. Therefore, after transporting a parcel of oil with high fusion point, a parcel of oil with low fusion point and volume $V_2 \ge C_{pipe}$ must be transported immediately. This implies that, after charging CTK$_1$ with $V_1$ of high fusion point oil, there must be a charging tank that can receive at least volume $C_{pipe}$ of oil. Without loss of generality, we assume that the capacity of any charging tanks is greater than $C_{pipe}$. To reduce charging and discharging cost, it is also desired that a tank is charged to capacity when it is charged. Thus, we use the number of tanks to discuss the volume of oil transported.

**Definition 4.1:** A system of crude oil operations with initial state $S_0$ is said to be schedulable if there exists a feasible short-term schedule for a horizon $\Gamma = [0, \infty)$.

Notice that the key here is the schedule horizon $\Gamma = [0, \infty)$, because the operation of distillers cannot be interrupted. The existence of a feasible short-term schedule $SCHD_1 = \{OD_1, OD_2, \dots, OD_n\}$ for a schedule horizon $[0, a]$ does not guarantee that a feasible short-term schedule $SCHD_2 = \{OD_1, OD_2, \dots, OD_n, OD_{n+1}, \dots, OD_{n+k}\}$ with $SCHD_1 \subset SCHD_2$ for schedule horizon $[0, b]$, with $b > a$, can be found.

**Definition 4.2:** A state $M$ of a system of crude oil operations is said to be safe if, with $M$ as initial state, the system is schedulable.

Therefore, with Definitions 4.1 and 4.2, to analyze the schedulability of crude oil operations is to analyze the safeness of the system. In [21] and [22], schedulability conditions are presented by considering oil residency time constraint only. Here, both oil residency time constraint and crude oil types with high fusion point are considered. Thus, the problem addressed here is much more complex than that in [21] and [22].

### A. Case 1: System with One Distiller

Let $f_{p \max}$, $f_{ds}$, and $\Psi$ be the maximal crude oil transportation rate of the pipeline, the feeding rate to the single distiller, and the oil residency time, respectively. It is shown in [21] that if there is only a single charging tank and $\Psi > 0$ the system is not schedulable even if $f_{p \max} = \infty$. Obviously, such a system is

<figure><img src="image_7.png" /><figcaption>Fig. 6. PN model for the proof of Theorem 4.1.</figcaption></figure>

not schedulable for the situation considered in this paper. Nevertheless, it is shown in [21] that if there are two charging tanks and $f_{p \max}$ is large enough the system is schedulable if only oil residency time is considered. However, the following theorem shows that it is not schedulable for the system considered in this paper. Let $\xi = (\Psi \times f_{p \max} \times f_{ds})/(f_{p \max} - f_{ds})$, CTK$_i$ denote charging tanks $i$, $\alpha = f_{ds} \times \Psi$, and $\varphi$ be the color of crude oil type being processed, respectively.

**Theorem 4.1:** Assume that: 1) there is a single distiller with feeding rate $f_{ds}$; 2) there are two charging tanks CTK$_1$ and CTK$_2$ with capacity greater than or equal to $\xi$; 3) the crude oil being processed is a type with high fusion point and its color is $\varphi \in \Phi_2$; 4) $f_{p \max} > f_{ds}$; and 5) initially there is crude oil ready for feeding with volume $\zeta \ge (\Psi \times f_{p \max} \times f_{ds})/(f_{p \max} - f_{ds})$ in tank CTK$_1$ and CTK$_2$ is empty. Then, the system is not schedulable.

*Proof:* This situation can be modeled by the PN shown in Fig. 6. At the beginning (time $\tau_0$), we have $M_0(p_{1c}) = 1$, $M_0(p_{1s}) = M_0(p_{2c}) = M_0(p_{2s}) = 0$, $V(M_0(p_{1c}, \varphi)) = \zeta$, and $M_0(p_4(y), \varphi) = 1$ as shown in Fig. 6(a). Then, $t_{12}$ can fire with rate $f_{ds}$ for feeding $p_1$ (the distiller) and $y$ can fire with rate $f_{p \max}$ to charge $p_{2s}$. At time $\tau_1 = \tau_0 + (\zeta/f_{p \max})$, $M_1$ is reached such that $M_1(p_{2s}) = M_1(p_{1c}) = M_1(p_4(y), \varphi) = 1$, $V(M_1(p_{2s}, \varphi)) = \zeta$, and $V(M_1(p_{1c}, \varphi)) = \zeta - (\tau_1 - \tau_0)f_{ds} > 0$ as shown in Fig. 6(b). At $\tau_1$, if $y$ stops firing, then at time $\tau_2 = \tau_0 + (\zeta/f_{ds})$, $M_2$ is reached such that $M_2(p_{1c}) = 0$ and $V(M_2(p_{1c})) = 0$. This time, we have

$$ \tau_2 - \tau_1 = \frac{\zeta}{f_{ds}} - \frac{\zeta}{f_{p \max}} = \frac{f_{p \max} - f_{ds}}{f_{p \max} \times f_{ds}} \times \zeta \\ \ge \frac{f_{p \max} - f_{ds}}{f_{p \max} \times f_{ds}} \times \frac{\Psi \times f_{p \max} \times f_{ds}}{f_{p \max} - f_{ds}} = \Psi $$

or we have $M_2(p_{2c}) = 1$ and $V(M_2(p_{2c}, \varphi)) = \zeta$, or $t_{22}$ can fire with rate $f_{ds}$ and the distiller can continue its operation without interruption. However, because $M_1(p_4(y), \varphi) = 1$ with $\varphi \in \Phi_2$, at $\tau_1$, $y$ cannot stop firing. Thus, at $\tau_2$, it reaches $M_3$ such that $M_3(p_{1c}) = M_3(p_{2c}) = 0$ as shown in Fig. 6(c). At this marking, both $t_{11}$ and $t_{22}$ cannot fire, or the PN is not live, or this is an infeasible state. Therefore, the system is not schedulable. ■
<figure><img src="image_8.png" /><figcaption>Fig. 7. PN model for a system with three charging tanks and one distiller.</figcaption></figure>

**Theorem 4.1** shows that with high fusion point types of crude oil to be processed more charging tanks are required.

**Theorem 4.2:** Assume that: 1) there is a single distiller with feeding rate $f_{ds}$; 2) there are three charging tanks CTK$_{1-3}$ with capacity $C_j \ge \alpha$, $j \in \{1, 2, 3\}$; 3) the crude oil being processed is a type with high fusion point and its color is $\varphi \in \Phi_2$; and 4) $f_{p\max} \ge f_{ds}$; and 5) initially there is crude oil in CTK$_{1}$ and CTK$_{2}$ with amount $\zeta_1$ and $\zeta_2$, respectively, where $\zeta_1 = \zeta_2 = \min\{C_1, C_2, C_3\}$. The oil in CTK$_{1}$ is ready for feeding and CTK$_{3}$ is empty. Then, the system is schedulable and any number of tanks of high fusion oil can be transported by a single setup.

**Proof:** The PN model is shown in Fig. 7. Initially (at time $\tau_0$, or at marking $M_0$) we have $M_0(p_{1c}) = M_0(p_{2s}) = M_1(p_4(y), \varphi) = 1$ with $\varphi \in \Phi_2$ and $M_0(p_{1s}) = M_0(p_{2c}) = M_0(p_{3s}) = M_0(p_{3c}) = 0$, $V(M_0(p_{1c}, \varphi)) = V(M_0(p_{2s}, \varphi)) = \zeta$, and $V(M_0(p_{1s})) = V(M_0(p_{2c})) = V(M_0(p_{3s})) = V(M_0(p_{3c})) = 0$. This time we fire $t_{12}$ with rate $f_{ds}$ to feed $p_1$, meanwhile $y$ can fire with rate $f_{ds}$ to charge $p_{3s}$, for $f_{p\max} \ge f_{ds}$. At time $\tau_1 = \tau_0 + (\zeta/f_{ds}) \ge \tau_0 + \Psi$, $M_1$ is reached such that $M_1(p_{1c}) = M_1(p_{2s}) = 0$, $M_1(p_{2c}) = M_1(p_{3s}) = M_1(p_4(y), \varphi) = 1$, and $V(M_1(p_{2c}, \varphi)) = V(M_1(p_{3s}, \varphi)) = \zeta$. At this time, $t_{22}$ can fire with rate $f_{ds}$ to feed $p_1$ and $y$ can fire with rate $f_{ds}$ to charge $p_{1s}$. In fact, marking $M_1$ is equivalent to $M_0$, hence, the previous process can be repeated unlimitedly. By doing so, there is always a transition firing to feed $p_1$ and at the same time $y$ keeps firing without interruption. Thus, the PN is live and it is schedulable. At the same time, $y$ can fire with color $\varphi \in \Phi_2$ unlimitedly, or any number of tanks of high fusion oil can be transported. This can be done by a single setup. ■

Obviously, if there are more than three charging tanks, the system is schedulable and any amount of crude oil with high fusion point can be transported by a single setup.

## B. Case 2: System with Two Distillers

When there are multiple distillers in a refinery, often each distiller processes different type of crude oil with different crude oil feeding rate. Thus, we always assume that different distiller processes different type of crude oil at a time. Without loss of generality, we also assume that at any time there is no more than one type of high fusion point crude oil to be processed at a time. Let $f_{ds1}$ and $f_{ds2}$ denote the feeding rate to distiller #1 (DS$_1$) and distiller #2 (DS$_2$), and $\alpha_1 = \Psi \times f_{ds1}$ and $\alpha_2 = \Psi \times f_{ds2}$, respectively.

In crude oil operations, when $f_{p\max} = f_{ds1} + f_{ds2}$ the system reaches its maximal productivity, for $f_{ds1} + f_{ds2}$ cannot be

<figure><img src="image_9.png" /><figcaption>Fig. 8. PN model with five charging tanks for feeding two distillers.</figcaption></figure>

greater than $f_{p\max}$. In this paper, schedulability is discussed under the assumption that $f_{p\max} = f_{ds1} + f_{ds2}$. It is shown in [22] that if there are four charging tanks for feeding two distillers and it requires $f_{p\max} = f_{ds1} + f_{ds2}$ with $f_{ds1} \ne f_{ds2}$, the system is not schedulable. This conclusion must hold here too. We consider the situation that there are five charging tanks. Let $\Pi$ be a real number with $\Pi \ge 1$ and the following conditions are given.

1) **Production condition:** there are two distillers DS$_1$ and DS$_2$ with feeding rates being $f_{ds1}$ and $f_{ds2}$, $f_{ds1} > f_{ds2}$, $\alpha_1 = \Psi \times f_{ds1}$, $\alpha_2 = \Psi \times f_{ds2}$, and $f_{p\max} = f_{ds1} + f_{ds2}$.

2) **Tank capacity:** there are five charging tanks CTK$_{1-5}$ with capacity $C_1 \ge 2\Pi\alpha_1$, $C_2 \ge 2\Pi\alpha_1$, $C_3 \ge 2\Pi\alpha_1$, $C_4 \ge 2\Pi\alpha_2$, and $C_5 \ge 2\Pi\alpha_2$, and CTK$_{1}$, CTK$_{2}$, and CTK$_{3}$ are for DS$_1$, CTK$_{4}$ and CTK$_{5}$ for DS$_2$.

3) **Initial Condition:** the volume of oil type 1 (color $\varphi_1$) in CTK$_{1}$ and CTK$_{2}$ is $\zeta_1 = \zeta_2 = 2\Pi\alpha_1$, and the volume of oil type 2 (color $\varphi_2$) in CTK$_{4}$ is $\zeta_4 = 2\Pi\alpha_2$, CTK$_{3}$ and CTK$_{5}$ are empty, and the oil in CTK$_{1}$ and CTK$_{4}$ is ready for feeding.

4) **Crude oil type switching:** after processing oil in CTK$_{4}$ by DS$_2$, it should process a high fusion point oil type (type #3).

**Theorem 4.3:** If conditions (1)–(4) are satisfied, the system is schedulable and one tank of crude oil of type 3 can be transported by a single setup.

**Proof:** With the PN model shown in Fig. 8, the system can be scheduled as follows. Initially, at marking $M_0$ (time $\tau_0$), we have $M_0(p_{1c}) = M_0(p_{2s}) = M_0(p_{4c}) = 1$, $V(M_0(p_{1c}, \varphi_1)) = V(M_0(p_{2s}, \varphi_1)) = 2\Pi\alpha_1$, $V(M_0(p_{4c}, \varphi_2)) = 2\Pi\alpha_2$, and other places are empty. At this marking, we fire $t_{12}$ and $t_{42}$ with colors $\varphi_1$ and $\varphi_2$ to feed $p_1$ and $p_2$, respectively. At the same time, we fire $y$ with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ during time interval $[\tau_0, \tau_0 + 2\Pi\alpha_2/(f_{ds1} + f_{ds2}))$ to charge $p_{5s}$ and fire $y$ with color $\varphi_1$ and rate $f_{ds1} + f_{ds2}$ during time interval $[\tau_0 + \Pi\alpha_2/(f_{ds1} + f_{ds2}), \tau_0 + 2\Pi\Psi]$ to charge $p_{3s}$. In this way, at $\tau_1 = \tau_0 + 2\Pi\alpha_2/(f_{ds1} + f_{ds2})$, we have $M(p_4(y)) = 1$, but with $M(p_{3s}) = 0$, $y$ can fire. It is a live state. Also, at $\tau_1, t_{51}$ can start to fire and at $\tau_0 + 2\Pi\Psi$, the firing of $t_{51}$ must have ended, because $2\Pi\alpha_2/(f_{ds1} + f_{ds2}) < \Pi(\alpha_1 + \alpha_2)/(f_{ds1} + f_{ds2}) =$
$\Pi(f_{ds1} + f_{ds2})\Psi/(f_{ds1} + f_{ds2}) = \Pi\Psi$. Thus, after $\Pi\Psi \ge \Psi$ time units, at time $\tau_2 = \tau_0 + 2\Pi\Psi$, marking $M_1$ is reached such that $M_1(p_{2c}) = M_1(p_{5c}) = M_1(p_{3s}) = 1$, $V(M_1(p_{2c}, \varphi_1)) = V(M_1(p_{3s}, \varphi_1)) = 2\Pi\alpha_1$, and $V(M_1(p_{5c}, \varphi_3)) = 2\Pi\alpha_2$, and other places are empty. This marking is equivalent to the initial marking $M_0$ or the previous process can be repeated and $y$ can be kept firing in all the time. In other words, the system is schedulable. In this process, one tank of high fusion point oil is transported by firing $y$ uninterruptedly, or by a single setup.

Theorem 4.3's conditions require that $f_{ds1} > f_{ds2}$. This condition guarantees that when $M_1$ is reached such that $M_1(p_{4c}) = 0$, $M_1(p_{5s}) = 0$ and $V(M_1(p_{5s}, \varphi_2)) = 2\Pi\alpha_2$ must hold, such that the oil residency time constraint can be met. If $f_{ds2} > f_{ds1}$, and when a marking $M$ is reached such that $V(M(p_{4c}, \varphi_2)) = \alpha_2$ and $V(M(p_{5s}, \varphi_2)) = 2\Pi\alpha_2$, the oil residency time constraint must also be met. In this case, it requires that $2\Pi\alpha_2/(f_{ds1} + f_{ds2}) \le (2\Pi - 1)\alpha_2/f_{ds2} \Rightarrow 2\Pi\Psi \times f_{ds2}/(f_{ds1} + f_{ds2}) \le (2\Pi - 1)\Psi \times f_{ds2}/f_{ds1} \Rightarrow \Pi \ge (f_{ds1} + f_{ds2})/2f_{ds1}$. In general, $\Psi$ is just several hour long and $\Pi$ can be more than 2 for most charging tanks. Thus, if $f_{ds2} \le 3f_{ds1}$ the condition can be met, or the theorem holds for $f_{ds2} > f_{ds1}$ too. It follows from the proof of Theorem 4.3 that it is impossible to transport two tanks of high fusion point oil by a single setup. Thus, with five charging tanks for feeding two distillers, at most one tank of high fusion point oil can be transported by a single setup. Now we consider the situation with six charging tanks and the following conditions.

5) **Production condition:** there are two distillers $DS_1$ and $DS_2$ with $f_{ds1} \ne f_{ds2}$, $\alpha_1 = \Psi \times f_{ds1}$, $\alpha_2 = \Psi \times f_{ds2}$ and $f_{pmax} = f_{ds1} + f_{ds2}$.

6) **Tank capacity:** there are six charging tanks $CTK_{1-6}$ with capacity $C_1 \ge \Pi\alpha_1$, $C_2 \ge \Pi\alpha_1$, $C_3 \ge \Pi\alpha_1$, $C_4 \ge \Pi\alpha_2$, $C_5 \ge \Pi\alpha_2$, and $C_6 \ge \Pi\alpha_2$, and $\Pi \ge (f_{ds1} + f_{ds2})/f_{ds1}$; $CTK_1$, $CTK_2$, and $CTK_3$ are for $DS_1$; and $CTK_4$, $CTK_5$, and $CTK_6$ for $DS_2$.

7) **Initial condition:** the volume of oil type 1 (color $\varphi_1$) in $CTK_1$ and $CTK_2$ is $\zeta_1 = \zeta_2 = \Pi\alpha_1$, the volume of oil type 2 (color $\varphi_2$) in $CTK_4$ is $\zeta_4 = \Pi\alpha_2$, $CTK_3$, $CTK_5$, and $CTK_6$ are empty, and the oil in $CTK_1$ and $CTK_4$ is ready for feeding.

8) **Crude oil type switching:** after finishing the oil of type 2 in $CTK_4$, $DS_2$ should process oil type 3 (color $\varphi_3$) with high fusion point.

**Theorem 4.4:** If conditions (5)–(8) are satisfied, the system is schedulable and two tanks of crude oil of type 3 can be transported via the pipeline by a single setup.

**Proof:** The PN model for this case is shown in Fig. 9. We first show that when $f_{ds1} > f_{ds2}$ the theorem holds. Initially, at marking $M_0$ (time $\tau_0$), we have $M_0(p_{1c}) = M_0(p_{2s}) = M_0(p_{4c}) = 1$, $V(M_0(p_{1c}, \varphi_1)) = V(M_0(p_{2s}, \varphi_1)) = \Pi\alpha_1$, $V(M_0(p_{4c}, \varphi_2)) = \Pi\alpha_2$, and other places are empty. At this marking, we fire $t_{12}$ with color $\varphi_1$ and rate $f_{ds1}$ to feed $p_1$, and $t_{42}$ with color $\varphi_2$ and rate $f_{ds2}$ to feed $p_2$, respectively. At the same time, we fire $y$ with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{5s}$. At time $\tau_1 = \tau_0 + \Pi\alpha_2/(f_{ds1} + f_{ds2})$, marking

<figure><img src="image_10.png" /><figcaption>Fig. 9. PN model with six charging tanks for feeding two distillers.</figcaption></figure>

$M_1$ is reached such that $M_1(p_{1c}) = M_1(p_{2c}) = M_1(p_{4c}) = M_1(p_{5s}) = M_1(p_4(y), \varphi_3) = 1$ and $V(M_1(p_{5s}, \varphi_3)) = \Pi\alpha_2$. At this marking, we can continue the firing of $t_{12}$ and $t_{42}$ to feed $p_1$ and $p_2$, respectively. Meanwhile, $M_1(p_{6s}) = M_1(p_{6c}) = 0$. Hence, we can fire $y$ with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{6s}$ continuously. Because $f_{ds1} > f_{ds2}$, at time $\tau_2 = \tau_0 + 2\Pi\alpha_2/(f_{ds1} + f_{ds2})$, marking $M_2$ is reached such that $V(M_2(p_{6s}, \varphi_3)) = \Pi\alpha_2$, but $M_2(p_{1c}) = M_2(p_{4c}) = M_1(p_4(y), \varphi_3) = 1$ still holds. At this marking, with $M_2(p_{3s}) = M_1(p_{6c}) = 0$, we can fire $y$ with color $\varphi_1$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{3s}$, and at the same time continue the firing of $t_{12}$ and $t_{42}$ to feed $p_1$ and $p_2$. At time $\tau_3 = \tau_0 + \Pi\Psi$, $M_3$ is reached such that $M_3(p_{5c}) = M_3(p_{2c}) = 1$, $M_3(p_{4c}) = M_3(p_{1c}) = 0$, and $V(M_3(p_{3s}, \varphi_1)) = \Pi(\alpha_1 - \alpha_2)$. The question is if $M_3(p_4(y), \varphi_3) = 1$, which depends on whether $\Pi(\alpha_1 - \alpha_2) \ge C_{pipe}$ or not. However, we can assume that $M_3(p_4(y), \varphi_3) = 1$. At this marking, we can fire $t_{22}$ with color $\varphi_1$ to feed $p_1$, $t_{52}$ with color $\varphi_3$ to feed $p_2$, and fire $y$ with color $\varphi_1$ to charge $p_{3s}$ and $p_{1s}$ with volume $\Pi\alpha_2$ and $\Pi\alpha_1$, respectively. Let $\tau_4 = \tau_0 + 2\Pi\Psi$, we have $\tau_4 - \Pi\alpha_2/(f_{ds1} + f_{ds2}) - \tau_3 = \Pi\Psi - \Pi\Psi \times f_{ds2}/(f_{ds1} + f_{ds2}) \ge \Psi((f_{ds1}+f_{ds2})/f_{ds1} - f_{ds2}/f_{ds1}) = \Psi$. This implies that $t_{31}$'s firing has ended at $\tau_4$. Thus, at time $\tau_4$, marking $M_4$ is reached such that $M_4(p_{6c}) = M_4(p_{3c}) = M_4(p_{1s}) = 1$, $M_4(p_{6s}) = M_4(p_{3s}) = M_4(p_4(y), \varphi_3) = 0$, $V(M_4(p_{3c}, \varphi_1)) = V(M_4(p_{1s}, \varphi_1)) = \Pi\alpha_1$, and $V(M_4(p_{6c}, \varphi_3)) = \Pi\alpha_2$. This marking is equivalent to $M_0$, the previous process can be repeated in a cycle way.

Now we discuss the case with $f_{ds2} > f_{ds1}$. At $M_0$, we fire $t_{12}$ with color $\varphi_1$ and rate $f_{ds1}$ to feed $p_1$, and $t_{42}$ with color $\varphi_2$ and rate $f_{ds2}$ to feed $p_2$, respectively. At the same time, we fire $y$ with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{5s}$. At time $\tau_1 = \tau_0 + \Pi\alpha_2/(f_{ds1} + f_{ds2})$, $M_1$ is reached such that $M_1(p_{1c}) = M_1(p_{2c}) = M_1(p_{4c}) = M_1(p_{5s}) = M_1(p_4(y), \varphi_3) = 1$ and $V(M_1(p_{5s}, \varphi_3)) = \Pi\alpha_2$. At this marking, we can continue the firing of $t_{12}$ and $t_{42}$ to feed $p_1$ and $p_2$, respectively. Meanwhile, $M_1(p_{6s}) = M_1(p_{6c}) = 0$,
the PN is in a live state. Hence we can fire y with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{6s}$. Because $f_{ds2} > f_{ds1}$, at time $\tau_2 = \tau_0 + \Pi\Psi$, $M_2$ is reached such that $V(M_2(p_{6s}, \varphi_3)) = \Pi\alpha_1$, and $p_{1c}$ and $p_{4c}$ are just emptied or $M_2(p_{1c}) = M_2(p_{4c}) = 0$ and $M_2(p_4(y), \varphi_3) = 1$. At this marking, we have $\tau_2 - \tau_1 = \Pi\Psi - \Pi\alpha_2/(f_{ds1} + f_{ds2}) = \Pi\Psi - \Pi\Psi \times f_{ds2}/(f_{ds1} + f_{ds2}) \ge \Psi((f_{ds1} + f_{ds2})/f_{ds1} - f_{ds2}/f_{ds1}) = \Psi$. This implies that, at $\tau_2$, $t_{51}$'s firing has ended or $M_2(p_{5s}) = 0$, $M_2(p_{5c}) = 1$, and $V(M_2(p_{5s}, \varphi_3)) = \Pi\alpha_2$. Thus, at $\tau_2$, we can fire $t_{22}$ and $t_{52}$ to feed $p_1$ and $p_2$, respectively, and at the same time fire $y$ with color $\varphi_1$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{3s}$ and then $p_{1s}$. At $\tau_4 = \tau_0 + 2\Pi\Psi$, $M_4$ is reached such that $M_4(p_{2c}) = M_4(p_{5c}) = M_4(p_4(y), \varphi_3) = 0$. Notice that the volume that is charged to $p_{6s}$ and $p_{35}$ after $\tau_2$ is $\Pi(\alpha_2 - \alpha_1) + \Pi\alpha_1 = \Pi\alpha_2$. Thus, $\tau_4 - (\tau_2 + \Pi\alpha_2/(f_{ds1} + f_{ds2})) = \Pi\Psi - \Pi\alpha_2/(f_{ds1} + f_{ds2}) = \Pi\Psi - \Pi\Psi \times f_{ds2}/(f_{ds1} + f_{ds2}) \ge \Psi((f_{ds1} + f_{ds2})/f_{ds1} - f_{ds2}/f_{ds1}) = \Psi$. This implies that, at $\tau_4$, the firing of $t_{61}$ and $t_{31}$ has ended or $M_4(p_{6s}) = M_4(p_{3s}) = 0$, $M_4(p_{6c}) = M_4(p_{3c}) = M_4(p_{1s}) = 1$, $V(M_4(p_{3c}, \varphi_1)) = V(M_4(p_{1s}, \varphi_1)) = \Pi\alpha_1$, and $V(M_4(p_{6c}, \varphi_3)) = \Pi\alpha_2$. This marking is equivalent to $M_0$, or the previous process can be repeated in a cycle way, or the system is schedulable. In both cases, two tanks of crude oil with high fusion point are transported via the pipeline without being interrupted. Thus, such a parcel of oil can be transported by a single setup. ■

By making $\Pi$ as large as possible, the charging tanks can be charged as full as possible. It follows from Theorem 4.4 that two tanks of oil with high fusion point can be transported from storage tanks to charging tanks by a single setup. At the same time, maximal productivity can be reached. From the proof of Theorem 4.4, it is obvious that it is impossible to transport three tanks of oil with high fusion point if there are three charging tanks for each distiller. From the proof, it is known that CTK$_3$ and CTK$_1$ are charged interruptedly. This implies that two tanks of high fusion point crude oil can be transported by a single setup for any one of the two distillers.

From Theorem 4.2, we notice that when there are three charging tanks for feeding one distiller, unlimited amount of high fusion point oil can be transported by a single setup. However, only two tanks of high fusion point oil can be transported by a single setup when there are two distillers with each distiller having three charging tanks. This implies that, with more distillers in the system, it is more difficult to schedule it. Now we consider the situation with more charging tanks and the following conditions are given.

9) **Tank capacity:** there are eight charging tanks CTK$_{1-8}$ with capacity $C_i \ge \Pi\alpha_1, i = 1, 2, 3$, and $4$, and $C_j \ge \Pi\alpha_2, j = 5, 6, 7$, and $8$, and $\Pi \ge (f_{ds1} + f_{ds2})/f_{ds1}$, CTK$_{1-4}$ are for DS$_1$, and CTK$_{5-8}$ for DS$_2$.

10) **Initial condition:** the volume of oil type 1 (color $\varphi_1$) in CTK$_{1-3}$ is $\zeta_1 = \zeta_2 = \zeta_3 = \Pi\alpha_1$, the volume of oil type 2

<figure><img src="image_11.png" /><figcaption>Fig. 10. PN model with eight charging tanks for feeding two distillers.</figcaption></figure>

(color $\varphi_2$) in CTK$_5$ is $\zeta_5 = \Pi\alpha_2$, CTK$_4$, and CTK$_{6-8}$ are empty, and the oil in CTK$_1$ and CTK$_5$ is ready for feeding.

11) **Crude oil type switching:** after finishing the oil of type 2 in CTK$_5$, DS$_2$ should process oil type 3 (color $\varphi_3 \in \Phi_2$) with high fusion point.

**Theorem 4.5:** If conditions (5), (9)–(11) are satisfied the system is schedulable and three tanks of crude oil of type 3 can be transported via the pipeline by a single setup.

**Proof:** The PN model for this case is shown in Fig. 10. We first show that when $f_{ds1} > f_{ds2}$ the theorem holds. Initially, at marking $M_0$ (time $\tau_0$), we have $M_0(p_{1c}) = M_0(p_{2s}) = M_0(p_{3s}) = M_0(p_{5c}) = 1$, $V(M_0(p_{1c}, \varphi_1)) = V(M_0(p_{2s}, \varphi_1)) = V(M_0(p_{3s}, \varphi_1)) = \Pi\alpha_1$, $V(M_0(p_{5c}, \varphi_2)) = \Pi\alpha_2$, and other places are empty. At this marking, we fire $t_{12}$ with color $\varphi_1$ and rate $f_{ds1}$ to feed $p_1$, and $t_{52}$ with color $\varphi_2$ and rate $f_{ds2}$ to feed $p_2$, respectively. For $y$'s firing, there are three cases: 1) $f_{ds1} < 2f_{ds2}$; 2) $f_{ds1} = 2f_{ds2}$, and 3) $f_{ds1} > 2f_{ds2}$. For Case 1), we fire $y$ with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{6s}$ with volume $\Pi\alpha_2$, then charge $p_{7s}$ with volume $\Pi\alpha_2$, and then charge $p_{8s}$ with volume $\Pi(\alpha_1 - \alpha_2)$. For Case 2), we fire $y$ with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{6s}$, then $p_{7s}$, and then $p_{8s}$, all with volume $\Pi\alpha_2$. For Case (3), we fire $y$ with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{6s}$, then $p_{7s}$, and then $p_{8s}$, all with volume $\Pi\alpha_2$, and then continue to fire $y$ with color $\varphi_1$ to charge $p_{4s}$ with volume $\Pi(\alpha_1 - 2\alpha_2)$. At $\tau_1 = \tau_0 + \Pi\Psi$, $M_1$ is reached such that $M_1(p_{1c}) = M_1(p_{5c}) = 0$, $M_1(p_{2c}) = M_1(p_{3c}) = M_1(p_{6c}) = M_1(p_{4c}(y), \varphi_3) = 1$ for all the three cases; $V(M_1(p_{6c}, \varphi_3)) = V(M_1(p_{7s}, \varphi_3)) = \Pi\alpha_2$, and $V(M_1(p_{8s}, \varphi_3)) = \Pi(\alpha_1 - \alpha_2)$ for Case (1); $V(M_1(p_{6c}, \varphi_3)) = V(M_1(p_{7s}, \varphi_3)) = V(M_1(p_{8s}, \varphi_3)) = \Pi\alpha_2$ for Case (2); and $V(M_1(p_{6c}, \varphi_3)) = V(M_1(p_{7s}, \varphi_3)) = V(M_1(p_{8s}, \varphi_3)) = \Pi\alpha_2$, $V(M_1(p_{4s}, \varphi_1)) = \Pi(\alpha_1 - 2\alpha_2)$ for Case (3). At this marking, we can fire $t_{22}$ with color $\varphi_1$ and rate $f_{ds1}$ to feed $p_1$, and $t_{62}$ with color $\varphi_3$ and rate $f_{ds2}$ to feed $p_2$, respectively. Meanwhile, there is enough space in $p_{4s}$ and $p_{1s}$, the PN is in a live marking. We fire $y$ with color $\varphi_3 \in \Phi_2$ to charge $p_{8s}$ with volume $\Pi(2\alpha_2 - \alpha_1)$, then with $\varphi_1$ to charge $p_{4s}$ with volume $\Pi\alpha_1$, and then with $\varphi_1$ to charge $p_{1s}$ with volume $\Pi(\alpha_1 - \alpha_2)$ for Case (1); fire $y$ with $\varphi_1$ to charge $p_{4s}$ with volume $\Pi\alpha_1$, and then with $\varphi_1$ to charge $p_{1s}$ with volume $\Pi(\alpha_1 - \alpha_2)$ for Case (2); and fire $y$ with $\varphi_1$ to charge
$p_{4s}$ with volume $2\Pi\alpha_2$, and then with $\varphi_1$ to charge $p_{1s}$ with volume $\Pi(\alpha_1 - \alpha_2)$ for Case (3). At $\tau_2 = \tau_0 + 2\Pi\Psi$, $M_2$ is reached such that $M_2(p_{2c}) = M_2(p_{6c}) = M_2(p_4(y), \varphi_3) = 0$, $M_2(p_{3c}) = M_2(p_{7c}) = M_2(p_{8s}) = M_2(p_{4s}) = M_2(p_{1s}) = 1$, $V(M_2(p_{7c}, \varphi_3)) = V(M_2(p_{8s}, \varphi_3)) = \Pi\alpha_2$, $V(M_2(p_{4s}, \varphi_1)) = \Pi\alpha_1$, and $V(M_2(p_{1s}, \varphi_1)) = \Pi(\alpha_1 - \alpha_2)$. At this marking, we fire $t_{32}$ with color $\varphi_1$ and rate $f_{ds1}$ to feed $p_1$, and $t_{72}$ with color $\varphi_3$ and rate $f_{ds2}$ to and $p_2$, respectively. At the same time, we continue to fire $y$ with color $\varphi_1$ to charge $p_{1s}$ with volume $\Pi\alpha_2$ and then charge $p_{2s}$ with volume $\Pi\alpha_1$. Thus, at $\tau_3 = \tau_0 + 3\Pi\Psi$, $M_3$ is reached such that $M_3(p_{3c}) = M_3(p_{7c}) = M_3(p_4(y), \varphi_3) = 0$, $M_3(p_{4c}) = M_3(p_{8c}) = M_3(p_{1s}) = M_3(p_{2s}) = 1$, $V(M_3(p_{1s}, \varphi_1)) = V(M_3(p_{2s}, \varphi_1)) = V(M_3(p_{4c}, \varphi_1)) = \Pi\alpha_1$, and $V(M_3(p_{8c}, \varphi_3)) = \Pi\alpha_2$. This marking is equivalent to $M_0$, or the previous process can be repeated in a cycle way.

Now we discuss the case with $f_{ds2} > f_{ds1}$. There are also three cases: 1) $f_{ds2} < 2f_{ds1}$; 2) $f_{ds2} = 2f_{ds1}$; and 3) $f_{ds2} > 2f_{ds1}$. At $M_0$, we fire $t_{12}$ with color $\varphi_1$ and rate $f_{ds1}$ to feed $p_1$, and $t_{52}$ with color $\varphi_2$ and rate $f_{ds2}$ to feed $p_2$, respectively. At the same time, we fire $y$ with color $\varphi_3 \in \Phi_2$ and rate $f_{ds1} + f_{ds2}$ to charge $p_{6s}$ with volume $\Pi\alpha_2$ and then to charge $p_{7s}$ with volume $\Pi\alpha_1$. Let $\tau_1 = \tau_0 + \Pi\Psi$, we have $\tau_1 - \Pi\alpha_2/(f_{ds1} + f_{ds2}) - \tau_0 = \Pi\Psi - \Pi\Psi \times (f_{ds2}/(f_{ds1} + f_{ds2})) \ge \Psi((f_{ds1} + f_{ds2})/f_{ds1} - f_{ds2}/f_{ds1}) = \Psi$. This implies that $t_{61}$'s firing has ended at $\tau_1$. Thus, at time $\tau_1$, $M_1$ is reached such that $M_1(p_{1c}) = M_1(p_{5c}) = 0$, $M_1(p_{2c}) = M_1(p_{6c}) = M_1(p_{7s}) = M_1(p_4(y)) = 1$, $V(M_1(p_{6c}, \varphi_3)) = \Pi\alpha_2$, and $V(M_1(p_{7s}, \varphi_3)) = \Pi\alpha_1$. At this marking, we fire $t_{22}$ with color $\varphi_1$ and rate $f_{ds1}$ to feed $p_1$, and $t_{62}$ with color $\varphi_3$ and rate $f_{ds2}$ to feed $p_2$, respectively. At the same time, we fire $y$ with color $\varphi_3 \in \Phi_2$ to charge $p_{7s}$ with volume $\Pi(\alpha_2 - \alpha_1)$, then with color $\varphi_3$ to charge $p_{8s}$ with volume $\Pi\alpha_2$, and then with color $\varphi_1$ to charge $p_{4s}$ with volume $\Pi(2\alpha_1 - \alpha_2)$ for Case 1); with color $\varphi_3 \in \Phi_2$ to charge $p_{7s}$ with volume $\Pi(\alpha_2 - \alpha_1)$, then with color $\varphi_3 \in \Phi_2$ to charge $p_{8s}$ with volume $\Pi\alpha_2$ for Case 2); and with color $\varphi_3 \in \Phi_2$ to charge $p_{7s}$ with volume $\Pi(\alpha_2 - \alpha_1)$, then with color $\varphi_3 \in \Phi_2$ to charge $p_{8s}$ with volume $2\Pi\alpha_1$ for Case 3). At $\tau_2 = \tau_0 + 2\Pi\Psi$, $M_2$ is reached such that $M_2(p_{2c}) = M_2(p_{6c}) = 0$ and $M_2(p_{3c}) = M_2(p_{7c}) = M_2(p_4(y), \varphi_3) = 1$ for all the three cases; $V(M_2(p_{7c}, \varphi_3)) = V(M_2(p_{8s}, \varphi_3)) = \Pi\alpha_2$, and $V(M_2(p_{4s}, \varphi_1)) = \Pi(2\alpha_1 - \alpha_2)$ for Case (1); $V(M_2(p_{7c}, \varphi_3)) = V(M_2(p_{8s}, \varphi_3)) = \Pi\alpha_2$ for Case (2); and $V(M_2(p_{7c}, \varphi_3)) = \Pi\alpha_2$ and $V(M_2(p_{8s}, \varphi_3)) = 2\Pi\alpha_1$ for Case (3). At this marking, we fire $t_{32}$ with color $\varphi_1$ and $t_{72}$ with color $\varphi_3$ to feed $p_1$ and $p_2$, respectively. At the same time, there is space in $p_{4s}$, $p_{1s}$, and $p_{2s}$, we fire $y$ with color $\varphi_1$ to charge $p_{4s}$ with volume $\Pi(\alpha_2 - \alpha_1)$, then to charge $p_{1s}$ with volume $\Pi\alpha_1$, and then to charge $p_{2s}$ with volume $\Pi\alpha_1$ for Case (1); fire $y$ with color $\varphi_1$ to charge $p_{4s}$, $p_{1s}$, and $p_{2s}$, sequentially, all with volume $\Pi\alpha_1$ for Case (2); and fire $y$ with color $\varphi_3 \in \Phi_2$ to charge $p_{8s}$ with volume $\Pi(\alpha_2 - 2\alpha_1)$, then with color $\varphi_1$ to charge $p_{4s}$, $p_{1s}$, and $p_{2s}$, sequentially, all with volume $\Pi\alpha_1$ for Case (3). At $\tau_3 = \tau_0 + 3\Pi\Psi$, $M_3$ is reached such that $M_3(p_{3c}) = M_3(p_{7c}) = M_3(p_4(y), \varphi_3) = 0$, $M_3(p_{4c}) = M_3(p_{8c}) = M_3(p_{1s}) = M_3(p_{2s}) = 1$, $V(M_3(p_{1c}, \varphi_1)) = V(M_3(p_{2s}, \varphi_1)) = V(M_3(p_{4c},$

$\varphi_1)) = \Pi\alpha_1$, and $V(M_3(p_{8c}, \varphi_3)) = \Pi\alpha_2$. This marking is equivalent to $M_0$, or the previous process can be repeated in a cycle way.

In both cases, three tanks of high fusion point crude oil are transported via the pipeline without being interrupted. Thus, such a parcel of oil can be transported by a single setup. ■

From Theorems 4.4 and 4.5, it seems that, with one more charging tank adding to each distiller, one more tank of high fusion point crude oil can be transported via the pipeline by a single setup for a distiller to process. It should be noticed that, for Case (2), after charging CTK$_6$ and CTK$_7$ to $\Pi\alpha_2$ by firing $y$, CTK$_5$ has been emptied. Thus, while $p_1$ and $p_2$ are being fed by CTK$_2$ and CTK$_6$, CTK$_8$ and CTK$_5$ can be charged by firing $y$. Then, while $p_1$ and $p_2$ are being fed by CTK$_3$ and CTK$_7$, CTK$_4$ and CTK$_1$ can be charged by firing $y$. In this way, the PN is live. This implies, in some case, that four tanks of high fusion oil can be transported by a single setup.

## V. SCHEDULABILITY FOR SYSTEMS WITH MULTIPLE DISTILLERS

This section discusses schedulability for systems with more than two distillers and generalizes the results obtained in the last section. We assume that there are $K \ge 3$ distillers for the system discussed and the following conditions are given.

12) **Production condition:** there are $K$ distillers $DS_{1-K}$ with feeding rates $f_{ds_i} > f_{ds(i+1)}$, $i = 1, \dots, K-1$, $\alpha_i = \Psi \times f_{ds_i}$, $i = 1, \dots, K$, and $f_{p \max} = f_{ds1} + f_{ds2} + \dots + f_{dsK}$.

13) **Tank capacity:** there are $2K+1$ charging tanks CTK$_{1-(2K+1)}$ with capacity $C_1 \ge K\alpha_1$, $C_2 \ge K\alpha_1$, $C_3 \ge K\alpha_1$; $C_4 \ge K\alpha_2$, $C_5 \ge K\alpha_2$; ..., $C_{2i} \ge K\alpha_i$, $C_{2i+1} \ge K\alpha_i$; ..., $C_{2K} \ge K\alpha_K$, $C_{2K+1} \ge K\alpha_K$. CTK$_{1-3}$ serve $DS_1$ while CTK$_{2i-}$CTK$_{2i+1}$ serve $DS_i$, $2 \le i \le K$.

14) **Initial condition:** the volume of oil type 1 in CTK$_1$ and CTK$_2$ is $\zeta_1 = \zeta_2 = K\alpha_1$, the volume of type 2 in CTK$_4$ is $\zeta_4 = K\alpha_2$, ..., the volume of type $i$ in CTK$_{2i}$ is $\zeta_{2i} = K\alpha_i$, ..., the volume of type $K$ in CTK$_{2K}$ is $\zeta_{2K} = K\alpha_K$, the other tanks are empty, and the oil in CTK$_1$, and CTK$_{2i}$, $2 \le i \le K$ is ready for feeding.

15) **Crude oil type switching:** after finishing the oil of type $K$ in CTK$_{2K}$, distiller $K$ should process another type of crude oil (type $K+1$) that has high fusion point.

**Theorem 5.1:** If conditions (12)–(15) are satisfied the system is schedulable and one tank of crude oil of type $K+1$ can be transported via the pipeline by a single setup.

*Proof:* Let a charging tank CTK$_i$ be modeled by $\{p_{is}, p_{ic}, t_{i1}, t_{i2}\}$ with $t_{i1}$ and $t_{i2}$ being the timed and discharging transitions, respectively, and distiller $DS_i$ be modeled by $p_i$ in the PN model. Then, this system can be scheduled as follows. Initially, at $M_0$ (time $\tau_0$), $M_0(p_{1c}) = M_0(p_{2s}) = 1$, $M_0(p_{(2i)c}) = 1$, $i = 2, 3, \dots, K$, $V(M_0(p_{1c}, \varphi_1)) = V(M_0(p_{2s}, \varphi_1)) = K\alpha_1$, $V(M_0(p_{(2i)c}, \varphi_i)) = K\alpha_i$, $i = 2, 3, \dots, K$, and the other places are empty. At this marking, we fire $t_{12}$ with color $\varphi_1$ to feed $p_1$, and $t_{(2i)2}$ with color $\varphi_i$ to feed $p_i$, $i = 2, 3, \dots, K$, respectively. Meanwhile, we fire $y$ in the
following order: with color $\varphi_{K+1} \in \Phi_2$ to charge $p_{(2K+1)s}$ with volume $K\alpha_K \to$ with color $\varphi_{K-1}$ to charge $p_{(2K-1)s}$ with volume $K\alpha_{K-1} \to \cdots \to$ with color $\varphi_i$ to charge $p_{(2i+1)s}$ with volume $K\alpha_i \to \cdots \to$ with color $\varphi_2$ to charge $p_{5s}$ with volume $K\alpha_2 \to$ with color $\varphi_1$ to charge $p_{3s}$ with volume $K\alpha_1$. It should be pointed out that after firing $y$ for charging $p_{(2K+1)s}$, we have $M(p_4(y), \varphi_{K+1}) = 1$. However, at that marking, there are $K-1$ empty places: $p_{(2K-1)s}, \dots, p_{(2i+1)s}, \dots, p_{5s}$, and $p_{3s}$. Thus, $y$ can continue to fire and after some time $M(p_4(y), \varphi_{K+1}) = 0$ must hold. Notice also that

$$ \frac{K \alpha_1}{f_{p \max}} = \frac{K \times f_{ds1} \times \Psi}{f_{ds1} + \dots + f_{dsK}} \ge \frac{(f_{ds1} + \dots + f_{dsK}) \times \Psi}{f_{ds1} + \dots + f_{dsK}} = \Psi. $$

This implies that charging $p_{5s}$ stops before time $\tau_0 + (K-1)\Psi$. Hence, the firing of $t_{51}$ can start before $\tau_0 + (K-1)\Psi$ and must end before $\tau_1 = \tau_0 + K\Psi$, or oil residency time constraint is met. Thus, at $\tau_1$, marking $M_1$ is reached such that $M_1(p_{2c}) = M_1(p_{3s}) = 1$, $M_1(p_{(2i+1)c}) = 1$, $i = 2, 3, \dots, K$, $V(M_1(p_{2c}, \varphi_1)) = V(M_1(p_{3s}, \varphi_1)) = K\alpha_1$, $V(M_1(p_{(2i+1)c}, \varphi_i)) = K\alpha_i$, $i = 2, 3, \dots, K$, and the other places are empty. This marking is equivalent to $M_0$. Hence, the process can be repeated in a cyclic way and a feasible schedule can be obtained. It can be seen that, in this process, a tank of oil type $K+1$ is transported by a single setup. ■

**Theorem 5.1's conditions** require that the capacity of a charging tank and the volume of crude oil in a charging tank are greater or equal to $K\alpha_i$. It seems that it is difficult to be satisfied. However, in practice, it is not a serious restriction. In practice, in general, there are no more than four distillers in most refineries. Similarly, feeding rate for a distiller is no more than 650 t/h. Generally, $\Psi$ is from 4–6 h. Thus, we have $4 \times 650 \times 6 = 15500$ t that is less than the capacity of a general charging tank. In the theorem, it states that a tank of a high fusion oil type can be transported for DS$_K$. It follows from the proof of the theorem that one tank of high fusion crude oil can be transported for any distiller if the conditions in the theorem are satisfied. However, the cost may be very high if only one tank of high fusion crude oil is transported with one setup, unless the capacity of tank is very large. Now we consider more charging tank situations with the following conditions.

16) **Production condition:** there are $K$ distillers $DS_{1-K}$ with feeding rates $f_{dsi} \neq f_{dsj}$, $i \neq j$, $\alpha_i = \Psi \times f_{dsi}$, $i = 1, \dots, K$, and $f_{p \max} = f_{ds1} + f_{ds2} + \dots + f_{dsK}$.

17) **Tank capacity:** there are $3K$ charging tanks $CTK_{1-3K}$ with capacity $C_{3i-2} \ge \Pi\alpha_i$, $C_{3i-1} \ge \Pi\alpha_i$, and $C_{3i} \ge \Pi\alpha_i$, $i = 1, \dots, K$, and $\Pi \ge (f_{ds1} + \dots + f_{dsK})/(f_{ds1} + \dots + f_{ds(K-1)})$, and $CTK_{3(i-1)+1}$, $CTK_{3(i-1)+2}$, and $CTK_{3(i-1)+3}$ are for $DS_i$, $1 \le i \le K$.

18) **Initial condition:** the volume of oil type 1 in $CTK_1$ and $CTK_2$ is $\zeta_1 = \zeta_2 = \Pi\alpha_1, \dots$, the volume of oil type $i$ in $CTK_{3i+1}$ and $CTK_{3i+2}$ is $\zeta_{3i+1} = \zeta_{3i+2} = \Pi\alpha_{i+1}$, $1 < i \le K-2$, the volume of oil type $K$ in $CTK_{3(K-1)+1}$ is $\zeta_{3(K-1)+1} = \Pi\alpha_K$, the other tanks are empty, and the oil in $CTK_1$, $CTK_{3i+1}$, $1 < i \le K-1$, is ready for feeding;

19) **Crude oil type switching:** after finishing the oil of type $K$ in $CTK_{3(K-1)+1}$, distiller $K$ should process another type of crude oil (type $K+1$) that has high fusion point.

**Theorem 5.2:** Assume that conditions (16) to (19) given above are satisfied, then the system is schedulable and two tanks of

crude oil of type $K+1$ can be transported via the pipeline by a single setup.

**Proof:** There are two cases: 1) $f_{ds1} > f_{dsK}$; and 2) $f_{ds1} < f_{dsK}$. We first show that the theorem holds for Case (1). Initially, at $M_0$ (time $\tau_0$), we have $M_0(p_{1c}) = M_0(p_{2s}) = 1$, $M_0(p_{(3i+1)c}) = M_0(p_{(3i+2)s}) = 1$, $1 \le i \le K-2$, $M_0(p_{(3(K-1)+1)c}) = 1$, $V(M_0(p_{1c}, \varphi_1)) = V(M_0(p_{2s}, \varphi_1)) = \Pi\alpha_1$, $V(M_0(p_{(3i+1)c}, \varphi_{i+1})) = V(M_0(p_{(3i+2)s}, \varphi_{i+1})) = \Pi\alpha_{i+1}$, $1 \le i \le K-2$, $V(M_0(p_{(3(K-1)+1)c}, \varphi_K)) = \Pi\alpha_K$, and other places are empty. At this marking, we fire $t_{(3i-2)2}$ with color $\varphi_i$ to feed $p_i$, $1 \le i \le K$. At the same time, we fire $y$ with the following order: with color $\varphi_{K+1} \in \Phi_2$ and rate $f_{p \max}$ to charge $p_{(3K-1)s}$ with volume $\Pi\alpha_K \to$ with color $\varphi_{K+1} \in \Phi_2$ and rate $f_{p \max}$ to charge $p_{(3K)s}$ with volume $\Pi\alpha_K \to \dots \to$ with color $\varphi_i$ to charge $p_{(3i)s}$ with volume $\Pi\alpha_i$, $K-1 \ge i \ge 2$, $\dots \to$ with color $\varphi_1$ to charge $p_{3s}$ with volume $\Pi(\alpha_1 - \alpha_K)$. It should be pointed out that, after charging $p_{(3K)s}$ with volume $\Pi\alpha_K$, we have $M(p_4(y), \varphi_{K+1}) = 1$. However, with $p_{(3i)s}$, $1 \le i \le K-1$, being empty, $y$ can fire uninterruptedly. Hence, the PN is in a live marking and the previous process is feasible. Then, at $\tau_1 = \tau_0 + \Pi\Psi$, $M_1$ is reached such that $M_1(p_4(y), \varphi_{K+1}) = 0$, $M_1(p_{2c}) = 1$, $M_1(p_{(3i+2)c}) = M_1(p_{(3i+3)s}) = 1$, $1 \le i \le K-1$, $V(M_1(p_{2c}, \varphi_1)) = \Pi\alpha_1$, $V(M_1(p_{(3i+2)c}, \varphi_{i+1})) = V(M_1(p_{(3i+3)s}, \varphi_{i+1})) = \Pi\alpha_{i+1}$, $1 \le i \le K-2$, $V(M_1(p_{(3K-1)c}, \varphi_{K+1})) = V(M_1(p_{(3K)s}, \varphi_{K+1})) = \Pi\alpha_K$, $V(M_1(p_{3s}, \varphi_1)) = \Pi(\alpha_1 - \alpha_K)$, and other places are empty. At this marking, we fire $t_{22}$ with color $\varphi_1$ to feed $p_1$, $t_{(3i-1)2}$ with color $\varphi_i$ to feed $p_i$, $2 \le i \le K-1$, and $t_{(3K-1)2}$ with color $\varphi_{K+1}$ to feed $p_K$. At the same time, we fire $y$ with the following order: with color $\varphi_1$ and rate $f_{p \max}$ to charge $p_{3s}$ with volume $\Pi\alpha_K \to$ with color $\varphi_1$ and rate $f_{p \max}$ to charge $p_{1s}$ with volume $\Pi\alpha_1 \to \dots \to$ with color $\varphi_{i+1}$ to charge $p_{(3i+1)s}$ with volume $\Pi\alpha_{i+1}$, $1 \le i \le K-2$. Let $\tau_2 = \tau_0 + 2\Pi\Psi$, we have $(\tau_2 - \Pi\alpha_K)/(f_{ds1} + \dots + f_{dsK}) - \tau_1 = \Pi\Psi - \Pi\Psi f_{dsK}/(f_{ds1} + \dots + f_{dsK}) = \Pi\Psi(1 - f_{dsK}/(f_{ds1} + \dots + f_{dsK})) \ge \Psi$. This implies that $t_{31}$'s firing has ended at $\tau_2$. Thus, at $\tau_2$, $M_2$ is reached such that $M_2(p_{3c}) = M_2(p_{1s}) = 1$, $M_2(p_{(3i)c}) = M_2(p_{(3i-2)s}) = 1$, $2 \le i \le K-1$, $M_2(p_{(3K)c}) = 1$, $V(M_2(p_{3c}, \varphi_1)) = V(M_2(p_{1s}, \varphi_1)) = \Pi\alpha_1$, $V(M_2(p_{(3i)c}, \varphi_i)) = V(M_2(p_{(3i-2)s}, \varphi_i)) = \Pi\alpha_i$, $2 \le i \le K-1$, $V(M_2(p_{(3K)c}, \varphi_{K+1})) = \Pi\alpha_K$, and other places are empty. This marking is equivalent to $M_0$, and thus the process can be repeated in a cyclic way.

Now we show that the theorem still holds for Case (2). Without loss of generality, we assume that $\alpha_1 + \alpha_2 - \alpha_K > 0$. At $M_0$, we fire $t_{12}$ with color $\varphi_1$ to feed $p_1$, $t_{(3i-2)2}$ with color $\varphi_i$ to feed $p_i$, $2 \le i \le K$. At the same time, we fire $y$ with the following order: with color $\varphi_{K+1} \in \Phi_2$ and rate $f_{p \max}$ to charge $p_{(3K-1)s}$ with volume $\Pi\alpha_K \to$ with color $\varphi_{K+1} \in \Phi_2$ and rate $f_{p \max}$ to charge $p_{(3K)s}$ with volume $\Pi\alpha_K \to$ with color $\varphi_{K-1}$ and rate $f_{p \max}$ to charge $p_{(3K-3)s}$ with volume $\Pi\alpha_{K-1} \to \dots \to$ with color $\varphi_i$ to charge $p_{(3i)s}$ with volume $\Pi\alpha_i$, $3 \le i \le K-2$, $\dots \to$ with color $\varphi_2$ to charge $p_{6s}$ with volume $\Pi(\alpha_1 + \alpha_2 - \alpha_K)$. It should be pointed out that, after charging $p_{(3K)s}$ with volume $\Pi\alpha_K$, we have $M(p_4(y), \varphi_{K+1}) = 1$. However, with $p_{(3i)s}$, $1 \le i \le K-1$, being empty, $y$ can fire
uninterruptedly. Hence, the previous process is feasible. Let $\tau_1 = \tau_0 + \Pi\Psi$, we have $\tau_1 - \Pi\alpha_K / (f_{ds1} + \cdots + f_{dsK}) - \tau_0 = \Pi\Psi - \Pi\Psi f_{dsK} / (f_{ds1} + \cdots + f_{dsK}) = \Pi\Psi (1 - f_{dsK} / (f_{ds1} + \cdots + f_{dsK})) \ge \Psi$. This implies that $t_{(3K-1)1}$'s firing has ended at $\tau_1$. Thus, at $\tau_1$, $M_1$ is reached such that $M_1(p_4(y), \varphi_{K+1}) = 0, M_1(p_{2c}) = 1$, $M_1(p_{(3i+2)c}) = M_1(p_{(3i+3)c}) = 1, 1 \le i \le K-1$, $V(M_1(p_{2c}, \varphi_1)) = \Pi\alpha_1, V(M_1(p_{(3i+2)c}, \varphi_{i+1})) = V(M_1(p_{(3i+3)c}, \varphi_{i+1})) = \Pi\alpha_{i+1}, 2 \le i \le K-2$, $V(M_1(p_{5c}, \varphi_2)) = \Pi\alpha_2, V(M_1(p_{6s}, \varphi_2)) = \Pi(\alpha_1 + \alpha_2 - \alpha_K), V(M_1(p_{(3K-1)c}, \varphi_{K+1})) = V(M_1(p_{(3K)c}, \varphi_{K+1})) = \Pi\alpha_K$, and other places are empty. At this marking, we fire $t_{22}$ with color $\varphi_1$ to feed $p_1$, $t_{(3i-1)2}$ with color $\varphi_i$ to feed $p_i, 2 \le i \le K-1$, and $t_{(3K-1)2}$ with color $\varphi_{K+1}$ to feed $p_K$. At the same time, we fire y with the following order: with color $\varphi_2$ and rate $f_{p\max}$ to charge $p_{6s}$ with volume $\Pi(\alpha_K - \alpha_1) \to$ with color $\varphi_1$ and rate $f_{p\max}$ to charge $p_{3s}$ with volume $\Pi\alpha_1 \to$ with color $\varphi_1$ and rate $f_{p\max}$ to charge $p_{1s}$ with volume $\Pi\alpha_1 \to \cdots \to$ with color $\varphi_{i+1}$ to charge $p_{(3i+1)s}$ with volume $\Pi\alpha_{i+1}, 1 \le i \le K-2$. Notice that, between $\tau_1$ and the time point when it stops charging $p_{3s}$, the total volume of oil charged by firing y is $\Pi\alpha_K$. Hence, let $\tau_2 = \tau_0 + 2\Pi\Psi$, we have $(\tau_2 - \Pi\alpha_K) / (f_{ds1} + \cdots + f_{dsK}) - \tau_1 = \Pi\Psi - \Pi\Psi f_{dsK} / (f_{ds1} + \cdots + f_{dsK}) = \Pi\Psi(1 - f_{dsK} / (f_{ds1} + \cdots + f_{dsK})) \ge \Psi$. This implies that $t_{31}$'s firing has ended at $\tau_2$. Thus, at $\tau_2$, $M_2$ is reached such that $M_2(p_{3c}) = M_2(p_{1s}) = 1, M_2(p_{(3i)c}) = M_2(p_{(3i-2)s}) = 1, 2 \le i \le K-1, M_2(p_{(3K)c}) = 1, V(M_2(p_{3c}, \varphi_1)) = V(M_2(p_{1s}, \varphi_1)) = \Pi\alpha_1, V(M_2(p_{(3i)c}, \varphi_i)) = V(M_2(p_{(3i-2)s}, \varphi_i)) = \Pi\alpha_i, 2 \le i \le K-1, V(M_2(p_{(3K)c}, \varphi_{K+1})) = \Pi\alpha_K$, and other places are empty. This marking is equivalent to $M_0$, and thus the process can be repeated in a cyclic way. ■

In both cases, a feasible schedule can be obtained and two tanks of crude oil of high fusion point type by firing y continuously. This implies that this amount of oil can be transported by just a single setup.

In the proof of the theorem, we assume that $\alpha_1 + \alpha_2 - \alpha_K > 0$. It seems a constraint, in fact it is not. If $\alpha_1 + \alpha_2 - \alpha_K \le 0$, we need only to leave $p_{6s}$ empty and charge $p_{9s}$ with volume $\Pi(\alpha_1 + \alpha_2 + \alpha_3 - \alpha_K)$ during the time interval $[\tau_0, \tau_1]$, then the result is unchanged. It follows from the proof of the theorem that only two tanks of high fusion point oil can be transported by a single setup. For Case (1), when CTK$_{3K-1}$ and CTK$_{3K}$ are charged to $\Pi\alpha_K$, CTK$_{3K-2}$ has not been emptied yet. To charge CTK$_{3K-2}$ after charging CTK$_{3K}$, y should stop firing for some time. This violates the liveness conditions given in Definition 3.4. For Case (2), when CTK$_{3K-1}$ and CTK$_{3K}$ are charged to $\Pi\alpha_K$, CTK$_{3K-2}$ has been emptied. However, by charging CTK$_{3K-2}$ immediately after charging CTK$_{3K}$, oil residency time constraint will be violated. Theorem 5.2 shows that if each distiller has three charging tanks, two tanks of high fusion point oil can be transported for a distiller by a single setup. The following theorem shows that with one more charging tank adding to each distiller, one more tank of high fusion point crude oil can be transported via the pipeline by a single setup. Let $H > 3$ be an integer and the following conditions are given.

20) **Tank capacity:** there are HK charging tanks numbered CTK$_{(i-1)H+1}$, CTK$_{(i-1)H+2}$, ..., CTK$_{iH}$, $1 \le i \le K$,

with CTK$_{(i-1)H+1}$, CTK$_{(i-1)H+2}$, ..., CTK$_{iH}$ for DS$_i$, the capacities of CTK$_{(i-1)H+1}$, CTK$_{(i-1)H+2}$, ..., CTK$_{iH}$, $1 \le i \le K$, are all greater than or equal to $\Pi\alpha_i$, and $\Pi \ge (f_{ds1} + \cdots + f_{dsK}) / (f_{ds1} + \cdots + f_{ds(K-1)})$.

21) **Initial condition:** the volume of oil type i in CTK$_{(i-1)H+1}$, CTK$_{(i-1)H+2}$, ..., CTK$_{(i-1)H+(H-1)}$, $1 \le i \le K-1$, is $\Pi\alpha_i$, the volume of oil type K in CTK$_{(K-1)H+1}$ is $\Pi\alpha_K$, the other tanks are empty, and the oil in CTK$_{(i-1)H+1}$, $1 < i \le K$, is ready for feeding.

22) **Crude oil type switching:** after finishing the oil of type K in CTK$_{(K-1)H+1}$, distiller K should process another type of crude oil (type K + 1) that has high fusion point.

**Theorem 5.3:** Assume that conditions (16) and (20)–(22) given above are satisfied, then the system is schedulable and $H-1$ tanks of crude oil of type K + 1 can be transported via the pipeline by a single setup.

*Proof:* It depends on $(H-1)\alpha_K / (\alpha_1 + \cdots + \alpha_K)$. We have $0 < (H-1)\alpha_K / (\alpha_1 + \cdots + \alpha_K) < H-1$. We first show that the theorem holds when $0 < (H-1)\alpha_K / (\alpha_1 + \cdots + \alpha_K) < 1$. Initially, at $M_0$ (time $\tau_0$), we have $M_0(p_{(i1)c}) = 1$ and $M_0(p_{(ij)s}) = 1, 1 \le i \le K-1$ and $2 \le j \le H-1, M_0(p_{(K1)c}) = 1$; and $V(M_0(p_{(i1)c}, \varphi_i)) = V(M_0(p_{(ij)s}, \varphi_i)) = \Pi\alpha_i, 1 \le i \le K-1$ and $2 \le j \le H-1, V(M_0(p_{(K1)c}, \varphi_K)) = \Pi\alpha_K$, and other places are empty. At this marking, the total capacity in $p_{(Kj)s}, 2 \le j \le H$, and $p_{(iH)s}, 1 \le i \le K-1, i \le j \le H$) with volume $\Pi\alpha_{i+1}, K-1 \ge i > A$ and $0 \le \alpha_1 + \cdots + \alpha_A - (H-1)\alpha_K \le \alpha_A \to$ with color $\varphi_A$ to charge $p_{(AH)s}$ with volume $\Pi((H-1)\alpha_K - (\alpha_1 + \cdots + \alpha_{A-1}))$. It should be pointed out that, after charging $p_{(KH)s}$ with volume $\Pi\alpha_K$, we have $M(p_4(y), \varphi_{K+1}) = 1$. However, with $p_{(iH)s}, 1 \le i \le K-1$, being empty, y can fire uninterruptedly. Hence, the previous process is feasible. Let $\tau_1 = \tau_0 + \Pi\Psi$, we have $\tau_1 - \Pi\alpha_K / (f_{ds1} + \cdots + f_{dsK}) - \tau_0 = \Pi\Psi - (\Pi\Psi \times f_{dsK}) / (f_{ds1} + \cdots + f_{dsK}) = \Pi\Psi(1 - f_{dsK} / (f_{ds1} + \cdots + f_{dsK})) \ge \Psi$. This implies that $t_{(K2)1}$'s firing has ended at $\tau_1$. Thus, at $\tau_1$, $M_1$ is reached such that $M_1(p_4(y), \varphi_{K+1}) = 0, M_1(p_{(i2)c}) = 1, 1 \le i \le K, V(M_1(p_{(i2)c}, \varphi_i)) = \Pi\alpha_i, 1 \le i \le K-1, V(M_1(p_{(iH)s}, \varphi_i)) = \Pi\alpha_i, A+1 \le i \le K-1, V(M_1(p_{(AH)s}, \varphi_A)) = \Pi((H-1)\alpha_K - (\alpha_1 + \cdots + \alpha_{A-1})), V(M_1(p_{(K2)c}, \varphi_{K+1})) = V(M_1(p_{(Kj)s}, \varphi_{K+1})) = \Pi\alpha_K, 3 \le j \le H$, and other places are empty. At this marking, we fire $t_{(i2)2}$ with color $\varphi_i$ to feed $p_i, 1 \le i \le K-1$, and $t_{(K2)2}$ with color $\varphi_{K+1} \in \Phi_2$ to feed $p_K$, respectively. At the same time, we fire y with the following order: with color $\varphi_A$ and rate $f_{p\max}$ to charge $p_{(AH)s}$ with volume $\Pi(\alpha_1 + \cdots + \alpha_A - (H-1)\alpha_K) \to$ with color $\varphi_i$ and rate $f_{p\max}$ to charge $p_{(iH)s}$ with volume $\Pi\alpha_i, A-1 \ge i \ge 1 \to$ with color $\varphi_i$ and rate $f_{p\max}$ to charge $p_{(i1)s}$ with volume $\Pi\alpha_i, K-1 \ge i > B$ and
$0 \le \alpha_1 + \dots + \alpha_B - (H-2)\alpha_K \le \alpha_B \to$ with color $\varphi_B$ to charge $p_{(B1)s}$ with volume $\Pi((H-2)\alpha_K - (\alpha_1 + \dots + \alpha_{B-1}))$. Then, at $\tau_2 = \tau_0 + 2\Pi\Psi$, $M_2$ is reached such that $M_2(p_4(y), \varphi_{K+1}) = 0$, $M_2(p_{(i3)c}) = 1, 1 \le i \le K$, $V(M_2(p_{(i3)c}, \varphi_i)) = V(M_2(p_{(iH)s}, \varphi_i)) = \Pi\alpha_i, 1 \le i \le K-1$, $V(M_1(p_{(K3)c}, \varphi_{K+1})) = \Pi\alpha_K$, the remaining capacity in $p_{(i1)s}, 1 \le i \le B$, is $\Pi(H-2)\alpha_K$. By doing so, at $\tau_F = \tau_0 + F\Pi\Psi, 2 < F < H-1, M_F$ is reached such that $M_F(p_4(y), \varphi_{K+1}) = 0, M_F(p_{(i(F+1)c)}) = 1, 1 \le i \le K$, $V(M_F(p_{(i(F+1)c)}, \varphi_i)) = \Pi\alpha_i, 1 \le i \le K-1$, $V(M_F(p_{(K(F+1)c)}, \varphi_{K+1})) = \Pi\alpha_K$, and $\exists$G such that $0 \le \alpha_1 + \dots + \alpha_G - (H-F)\alpha_K \le \alpha_G$ and the remaining capacity in $p_{(i(F-1)s}, 1 \le i \le G$, is $\Pi(H-F)\alpha_K$. Finally, at $\tau_{H-1} = \tau_0 + (H-1)\Pi\Psi, M_{H-1}$ is reached such that $M_{H-1}(p_{(iH)c}) = 1$ and $M_{H-1}(p_{(ij)s}) = 1, 1 \le i \le K-1$ and $2 \le j \le H-2, M_{H-1}(p_{(KH)c}) = 1$; and $V(M_{H-1}(p_{(iH)c}, \varphi_i)) = V(M_{H-1}(p_{(ij)s}, \varphi_i)) = \Pi\alpha_i, 1 \le i \le K-1$ and $2 \le j \le H-2, V(M_{H-1}(p_{(KH)c}, \varphi_{K+1})) = \Pi\alpha_K$, and other places are empty. This marking is equivalent to $M_0$ and the previous process can be repeated in a cycle way. In this way, a feasible schedule is created and, by such schedule, $H-1$ tanks of high fusion point crude oil are transported for feeding $DS_K$. Because $y$ can fire uninterruptedly whenever $M(p_4(y), \varphi_{K+1}) = 1$, or the transportation of the $H-1$ tanks of high fusion point crude oil can be completed by just a single setup.

When $(H-1)\alpha_K / (\alpha_1 + \dots + \alpha_K) \ge 1$ it can be shown in the similar way and it is omitted. ■

Notice that when there are two distillers and four charging tanks, for each distiller four tanks of high fusion crude oil can be transported by just a single setup. In that case, we have $H-1 > K$. From the proof of Theorems 5.2 and 5.3, it is easy to show that when $H-1 \le K$ only $H-1$ tanks of high fusion crude oil can be transported by just a single setup. In the above theorems, it is required that $\Pi \ge (f_{ds1} + \dots + f_{dsK}) / (f_{ds1} + \dots + f_{ds(K-1)})$. This requirement is to guarantee the satisfaction of oil residency time constraint. In practice, if $\Pi$ is large enough, a charging tank can be charged with volume more than $\Pi\alpha_i$, possibly as full as possible.

In the proof of Theorem 5.3, a streamlined procedure with all the parameters analytically given is presented to obtain a feasible detailed schedule such that $H-1$ tanks of high fusion crude oil can be transported from storage tanks to charging tanks by a single setup. Thus, to do so, almost no computation is necessary. In practice, often $\Pi$ is large enough and a charging tank $CTK_j$ can be charged with volume more than $\Pi\alpha_i$. Thus, we need to determine the volume of oil to be charged into $CTK_j$ such that oil residency time constraint can be satisfied. To do so, it needs to calculate the time when the oil for feeding $DS_i$ is used up. With the state of the system and the feeding rate to $DS_i$ known, this calculation is very simple. In other words, by using the proposed method, no complex computation is required.

## VI. INDUSTRIAL CASE STUDY

This section presents a case study to show the application and power of the results obtained in this paper. This case problem

<table><caption>TABLE I INITIAL STATE FOR THE CHARGING TANKS</caption><thead><tr><th>Tank</th><th>Capacity (Ton)</th><th>Type of oil filled</th><th>Volume (Ton)</th></tr></thead><tbody><tr><td>CT122</td><td>16,000</td><td>Oil #1</td><td>8,000</td></tr><tr><td>CT129</td><td>34,000</td><td>Oil #1</td><td>30,000</td></tr><tr><td>CT115</td><td>34,000</td><td>Oil #3</td><td>30,000</td></tr><tr><td>CT116</td><td>34,000</td><td></td><td></td></tr><tr><td>CT127</td><td>34,000</td><td></td><td></td></tr><tr><td>CT180</td><td>16,000</td><td>Oil #5</td><td>16,000</td></tr><tr><td>CT124</td><td>20,000</td><td>Oil #6</td><td>16,000</td></tr><tr><td>CT181</td><td>16,000</td><td>Oil #6</td><td>6,000</td></tr><tr><td>CT125</td><td>20,000</td><td></td><td></td></tr></tbody></table>

arises from a practical application scenario. The refinery has three distillers $DS_1, DS_2$, and $DS_3$ with nine charging tanks available. Three times each month, a short-term schedule should be created for the next 10 days. The initial state for nine charging tanks is shown in Table I. The maximal flow rate of the pipeline is $f_{pmax} = 1250$ t/h. There is 62 000 t of crude oil of type #2, a type of high fusion point oil, in the storage tanks. Such crude oil is to be processed by distiller $DS_3$. A refining schedule is given as shown in Fig. 11 for the next 10 days with refining rates for distillers $DS_1, DS_2$, and $DS_3$ being 333.3, 291.7, and 625.0 t/h, respectively, where $\#i$ denotes crude oil type $i, i = 1, 2, \dots, 7$. The oil residency time for charging tanks $\Psi$ is 6 h and the capacity of pipeline is $C_{pipe} = 12000$ t. The question is if the refining schedule is realizable and 62 000 t crude oil of type #2 can be transported to charging tanks by a single setup.

According to the schedulability analysis presented above, examine the refining schedule and the initial state of the charging tanks, we find that: 1) $DS_1$ processes 38 000 t of oil type #1 held in charging tanks CT122 and CT129 first and then switches to process crude oil type #5. This implies that charging tanks CT122, CT129, and CT180 can be assigned to $DS_1$; 2) $DS_2$ first processes the crude oil held in tanks CT181 and CT124, then switches to process crude oil type #7, or charging tanks CT124 and CT181 are usable for $DS_2$; 3) $DS_3$ process the oil held in tank CT115 first and then switches to process oil type #2 and then #4, or charging tanks CT115 is usable for $DS_3$; 4) charging tanks CT116, CT127, and CT125, they are free to be used; and 5) the total production rate is equal to the maximal transportation rate of the pipeline. Because $f_{ds3} > f_{ds2}$, we assign CT116 and CT127 to $DS_3$, and CT125 to $DS_2$. Thus, each of the three distillers has three charging tanks with two tanks being empty for $DS_3$, and one for $DS_2$. With $C_{CT125} = 2000$ t > $C_{pipe} = 12000$ t. This implies that two tanks of #2 oil can be transported for $DS_3$ by a single setup. Furthermore, we have $C_{CT116} + C_{CT127} = 68000$ t > 62000 t. Thus, from the results obtained in this paper, it concludes that the refining schedule is realizable and 62 000 t of #2 oil can be transported for $DS_3$ by a single setup.

With the above observation and following the scheduling idea presented in this paper, we find the detailed schedule for this case study as shown in Figs. 12 and 13, where #1 stands for
<figure><img src="image_12.png" /><figcaption>Fig. 11. Refining schedule for the case study.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 12. Detailed charging tank schedule for feeding distillers.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 13. Detailed schedule for filling the charging tanks.</figcaption></figure>

crude oil type #1 and 122 for charging tanks CT122. This is consistent to the analysis given in the last section.

Notice that, in Fig. 13, we only present the charging tank filling schedule up to time point 200H. To this time point, the amount of crude oil of all types filled into the charging tanks is enough for completing the refining schedule. Then, different types of oil may need to fill to the charging tanks for the next scheduling horizon. It is extremely difficult, if not impossible, for any existing mathematical programming methods to obtain a short-term schedule for this presented industrial case.

## VII. CONCLUSION

A short-term schedule for oil refinery should provide all the activities in every detail for the whole scheduling horizon. It is the detail that makes the short-term scheduling problem extremely difficult [7]. There are various constraints including resource and process ones. Some of them are very difficult to model by mathematical programming models. Thus, it is hard to find a feasible schedule that is essential to the short-term scheduling problem for crude oil operations. Moreover, a good

schedule should make operational cost as low as possible, such as minimizing oil inventory cost. Among various costs, high setup cost for high fusion point crude oil transportation via pipeline and the cost resulting from mixing different types of oil in a tank play an important role. Because of the complexity, there is no model in the literature that can be used to reduce such kinds of costs. In viewing an operation decision, which forms a short-term schedule, as a control, we propose to study the short-term scheduling problem for crude oil operations in a control theory perspective. In this way, the short-term scheduling problem can be solved in a hierarchical way. At the upper level, it determines a refining schedule by minimizing oil inventory cost and maximizing productivity, while, at the lower level, a detailed schedule is found to realize it and reduce oil transportation cost and tank charging and discharging cost.

To solve the lower level problem, this paper studies the detailed scheduling problem by taking the setup cost of high fusion point oil transportation and tank charging and discharging cost into consideration. The system is modeled by a hybrid Petri net model. The liveness of the model, which is easy to check,
describes the feasibility of a short-term schedule for the sys-
tem. To reduce the tank charging and discharging cost, a control
strategy is used. By this control strategy, the charging tanks are
grouped such that a group of them serve a distiller. With the
PN model and control strategy, this paper conducts schedulabil-
ity analysis and schedulability conditions are presented. These
conditions reveal the relationship among the number of charg-
ing tanks, number of distillers, capacity of charging tanks, flow
rate of the pipeline, productivity, and volume of high fusion
point crude oil able to be transported by a single setup. They are
necessary for determining a refining schedule at the upper level
and can be used to check its realizability. They are presented
in a structural way, and can be easily used to create its corre-
sponding detailed schedule with setup cost of high fusion point
oil transportation and tank charging and discharging cost being
minimized.

It should be noticed that the volume of high fusion point
crude oil that is able to be transported by a single setup is
obtained under the special control strategy. It is ideal that a
required volume of such oil can be transported by a single setup
under this strategy. However, if not, a control policy and its
corresponding scheduling analysis are necessary because of the
high setup cost for high fusion crude oil transportation. This is
our future work.

REFERENCES

[1] Bechtel, PIMS (Process Industry Modeling System) User's Manual, Bechtel Corp, Houston, TX, 1993, Version 6.0.

[2] H. Chen and H.-M. Hanisch, "Analysis of hybrid system based on hybrid net condition/event system model," *Discr. Event Dyn. Syst.: Theory Appl.*, vol. 11, pp. 163–185, 2001.

[3] R. David and H. Alla, "On hybrid Petri nets," *Discr. Event Dyn. Syst.: Theory Appl.*, vol. 11, pp. 9–40, 2001.

[4] L. Ferrarini and L. Piroddi, "Modular design and implementation of a logic control system for a batch process," *Comput. Chem. Eng.*, vol. 27, no. 7, pp. 983–996, 2003.

[5] C. A. Floudas and X. Lin, "Continuous-time versus discrete-time approaches for scheduling of chemical processes: A review," *Comput. Chem. Eng.*, vol. 28, pp. 2109–2129, 2004.

[6] K. Glismann and G. Gruhn, "Short-term scheduling and recipe optimization of blending processes," *Comput. Chem. Eng.*, vol. 25, pp. 627–634, 2001.

[7] S. J. Honkomp, S. Lombardo, O. Rosen, and J. F. Pekny, "The curse of reality – why process scheduling optimization problems are difficult in practice," *Comput. Chem. Eng.*, vol. 24, pp. 323–328, 2000.

[8] Z. Jia, M. Ierapetritou, and J. D. Kelly, "Refinery short-term scheduling using continuous time formation: Crude oil operations," *Ind. Eng. Chem. Res.*, vol. 42, pp. 3085–3097, 2003.

[9] Z. Jia and M. Ierapetritou, "Efficient short-term scheduling of refinery operations based on a continuous time formulation," *Comput. Chem. Eng.*, vol. 28, pp. 1001–1019, 2004.

[10] H. Lee, J. M. Pinto, I. E. Grossmann, and S. Park, "Mixed integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management," *Ind. Eng. Chem. Res.*, vol. 35, pp. 1630–1641, 1996.

[11] C. A. Mendez, I. E. Grossmann, I. Harjunkoski, and P. Kabore, "A simultaneous optimization approach for off-line blending and scheduling of oil-refinery operations," *Comput. Chem. Eng.*, vol. 30, no. 4, pp. 614–634, 2006.

[12] L. F. L. Moro, "Process technology in the petroleum industry—current situation and future trends," *Comput. Chem. Eng.*, vol. 27, pp. 1303–1305, 2003.

[13] R. Pelham and C. Pharris, "Refinery operation and control: a future vision," *Hydrocarbon Process.*, vol. 75, no. 7, pp. 89–94, 1996.

[14] J. M. Pinto, M. Joly, and L. F. L. Moro, "Planning and scheduling models for refinery operations," *Comput. Chem. Eng.*, vol. 24, pp. 2259–2276, 2000.

[15] N. Shah, "Mathematical programming techniques for crude oil scheduling," *Comput. Chem. Eng.*, vol. 20, Suppl., pp. S1227-S1232, 1996.

[16] M. Silva and L. Recalde, "Petri nets and integrality relaxations: A view of continuous Petri net models," *IEEE Trans. Syst., Man, Cybern., Part C*, vol. 32, no. 4, pp. 314-327, Nov. 2002.

[17] J. Wang, *Timed Petri Nets: Theory and Application*. Boston, MA: Kluwer, 1998.

[18] N. Q. Wu, L. P. Bai, and C. B. Chu, "Hybrid Petri net modeling for refinery process," in *Proc. 2004 IEEE Conf. Syst., Man Cybern.*, pp. 1734-1739.

[19] N. Q. Wu, L. P. Bai, and C. B. Chu, "Modeling and conflict detection of crude-oil operations for refinery process based on controlled-colored-timed Petri net," *IEEE Trans. Syst., Man, Cybern., Part C*, vol. 37, no. 4, pp. 461-472, Jul. 2007.

[20] N. Q. Wu, M. C. Zhou, and F. Chu, "Short-term scheduling for refinery process: bridging the gap between theory and applications," *Int. J. Intell. Control Syst.*, vol. 10, no. 2, pp. 162-174, Jun. 2005.

[21] N. Q. Wu, F. Chu, C. B. Chu, and M. C. Zhou, "Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri nets," *IEEE Trans. Syst., Man, Cybern.: Part C*, vol. 38, no. 6, pp. 765-778, Nov. 2008.

[22] N. Q. Wu, F. Chu, C. B. Chu, and M. C. Zhou, "Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint," *IEEE Trans. Syst., Man, Cybern., Part C*, vol. 39, no. 1, pp. 1-16, Jan. 2009.

[23] N. Q. Wu, M. C. Zhou, and F. Chu, "A Petri net based heuristic algorithm for realizability of target refining schedules in oil refinery," *IEEE Trans. Autom. Sci. Eng.*, vol. 5, no. 4, pp. 661-676, Oct. 2008.

[24] E. C. Yamalidou and J. C. Kantor, "Modeling and optimal control of discrete-event chemical processes using Petri nets," *Comput. Chem. Eng.*, vol. 15, pp. 503–519, 1991.

[25] M. C. Zhou and K. Venkatesh, *Modeling, Simulation and Control of Flexible Manufacturing Systems: A Petri Net Approach*. Singapore: World Scientific, 1998.

[26] M. C. Zhou, F. DiCesare, and A. A. Desrochers, "A hybrid methodology for synthesis of Petri nets for manufacturing systems," *IEEE Trans. Robot. Autom.*, vol. 8, no. 3, pp. 350-361, 1992.

[27] M. C. Zhou and F. DiCesare, *Petri Net Synthesis for Discrete Event Control of Manufacturing Systems*. London, U.K.: Kluwer Academic, 1993.

[28] M. C. Zhou and M. D. Jeng, "Modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems: A Petri net approach," *IEEE Trans. Semicond. Manuf.*, vol. 11, no. 3, pp. 333-357, 1998.

[29] R. Zurawski and M. C. Zhou, "Petri nets and industrial applications: A tutorial," *IEEE Trans. Ind. Electron.*, vol. 41, no. 6, pp. 567-583, Dec. 1994.