N Q Wu
email: nqwu@gdut.edu.cn

L P Bai

M C Zhou
email: zhou@njit.edu

F Chu

S Mammar
email: said.mammar@inrets.fr

A Novel Approach to Optimization of Refining Schedules for Crude Oil Operations in Refinery NaiQi Wu, Senior Member, IEEE, Liping Bai, MengChu Zhou, Fellow, IEEE, Feng Chu, Senior Member, IEEE,andSaïd Mammar, Senior Member, IEEE Abstract-Short-term scheduling for crude oil operations is a combinatorial problem and involves extreme detail. Thus, it is very complicated and, up to now, there is no efficient technique and software tool for it. To search for efficient techniques, a twolayer hierarchical solution is proposed for it. At the upper level, one finds a realizable refining schedule to optimize some objectives. At the lower level, a detailed schedule is obtained to realize it. A methodology has been presented to solve the lower level problem from a control perspective by the authors of this paper. In this paper, the upper level problem for finding optimal refining schedules is addressed, and a novel method is proposed based on the results obtained at the lower level. This method solves a linear programming problem to determine the maximal production rate and a transportation problem to optimally assign crude oil types and volume to the distillers. This way, the method is computationally very efficient. An industrial case study is presented to show the application of the proposed method.

Index Terms-Crude oil operations, linear programming, shortterm scheduling, transportation problem.

I. INTRODUCTION

I N recent years, aiming at profit increase, great attention has been paid to the development of effective techniques for the operations of refinery [START_REF] Moro | Process technology in the petroleum industry-Current situation and future trends[END_REF]. There are three levels in operating a plant of refinery: production planning, production scheduling, and process control. Up to now, at the process control level, advanced control systems have been installed for unit control to optimize some production objectives in most oil refineries, resulting in significant productivity gains in the unit level. However, the optimized production units do not imply the global economic optimization of a plant. At the planning level, with the availability of linear-programming-based commercial software for refinery production planning, such as process industry modeling system [START_REF]PIMS (Process Industry Modeling System) User's manual[END_REF], general production plans of a whole refinery can be found. As pointed out by Pelham and Pharris [START_REF] Pelham | Refinery operation and control: A future vision[END_REF], the planning technology can be considered well developed and not much progress should be expected. Short-term scheduling is at the middle level and it lacks effective techniques and software tools. The three levels should work together to effectively operate a process plant [START_REF] Shobrys | Planning, scheduling and control systems: Why can they not work together[END_REF]. Thus, with the well-developed techniques for planning and process control, it is crucial to develop effective techniques for short-term scheduling [START_REF] Gabbar | Formal representation of meta-operation of chemical plants[END_REF], [START_REF] Gabbar | Synthesis of parallel operation for enhanced chemical plant operation[END_REF].

To search for effective techniques for short-term scheduling, in recent years, effort has been made and mathematical programming models are developed for batch processes. For examples, models in [START_REF] Ierapetritou | Effective continuous-time formulation for short-term scheduling, 1. Multipurpose batch processes[END_REF], [START_REF] Ierapetritou | Effective continuous-time formulation for short-term scheduling, 2. continuous and semicontinuous processes[END_REF], [START_REF] Mendez | An efficient MILP continuous time formulation for short-term scheduling of multiproduct continuous facilities[END_REF], [START_REF] Mendez | Dynamic scheduling in multiproduct batch plants[END_REF], and [START_REF] Pinto | A logic-based approach to scheduling problem with resource constraints[END_REF] are representative. These techniques are then modified to solve short-term scheduling problem in refinery. Depending on the time representation, there are mainly two categories of mathematical programming models: discrete-and continuous-time representation ones. The former divides the scheduling horizon into a number of time intervals with uniform time durations. An event, such as start and end of an operation, should happen at the boundary of a time interval. The mixed integer programming models [START_REF] Glismann | Short-term scheduling and recipe optimization of blending processes[END_REF], [START_REF] Jia | Refinery short-term scheduling using continuous time formation: Crude oil operations[END_REF], [START_REF] Lee | Mixed integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management[END_REF], [START_REF] Mendez | A simultaneous optimization approach for off-line blending and scheduling of oil-refinery operations[END_REF], [START_REF] Pinto | Planning and scheduling models for refinery operations[END_REF], [START_REF] Rejowski | Scheduling of a multiproduct pipeline system[END_REF], [START_REF] Saharidisa | Scheduling of loading and unloading of crude oil in a refinery using event-based discrete time formulation[END_REF], [START_REF] Shah | Mathematical programming techniques for crude oil scheduling[END_REF] are the representative ones. The main drawback is that the uniform time interval must be small enough so as to obtain acceptable accuracy, which leads to a huge number of binary variables and makes the problem very difficult to solve [START_REF] Floudas | Continuous-time versus discrete-time approaches for scheduling of chemical processes: A review[END_REF], [START_REF] Wu | Schedulability analysis of short-term scheduling for crude oil operations in refinery with oil residency time and charging-tank-switch-overlap constraints[END_REF]. Continuous-time models are adopted in [START_REF] Jia | Refinery short-term scheduling using continuous time formation: Crude oil operations[END_REF]- [START_REF] Karuppiah | Global optimization for scheduling refinery crude oil operations[END_REF], [START_REF] Shah | Centralizeddecentralized optimization for refinery scheduling[END_REF] to reduce the number of discrete variables. Although the number of discrete variables is significantly reduced, the drawback is that there are nonlinear constraints in it [START_REF] Pinto | Planning and scheduling models for refinery operations[END_REF]. Furthermore, to build such a model, it needs to know the number of events to occur [START_REF] Floudas | Continuous-time versus discrete-time approaches for scheduling of chemical processes: A review[END_REF]. In fact, it is not known before the schedule is created. Moreover, to make the problem solvable, most of discrete-time and continuous-time mathematical programming models make special assumptions, which, unfortunately, make a low-quality or unrealistic solution for real-world cases [START_REF] Mendez | A simultaneous optimization approach for off-line blending and scheduling of oil-refinery operations[END_REF].

For complex scheduling problems, application of heuristics and search algorithms, such as simulated annealing algorithms, genetic algorithms, and tabu algorithms [START_REF] Mattfeld | An efficient genetic algorithm for job shop scheduling with tardiness objectives[END_REF], [START_REF] Ponnambalam | A simulated annealing algorithm for job shop scheduling[END_REF], [START_REF] Sabuncuoglu | Job shop scheduling with beam search[END_REF], [START_REF] Yang | A new adaptive neural network and heuristics hybrid approach for job-shop scheduling[END_REF], is a good choice. These techniques are applicable only for problems where the jobs that are to be scheduled are deterministic at the beginning and solution feasibility is not a problem. However, to generate a short-term schedule for a refinery process, one needs to set the number of jobs, define the detailed activities for each job and the time needed for each activity, and determine their sequence. Meanwhile, there is no simple way to check the feasibility of a schedule. In other words, these techniques are not applicable to short-term scheduling of refinery. Thus, a new method should be developed to solve this problem.

Short-term scheduling for crude oil operations is one of the most difficult scheduling problems in operating an oil refinery plant. To solve this problem, the short-term scheduling for crude oil operations is divided into two subproblems in a hierarchical way in [START_REF] Wu | A Petri net based heuristic algorithm for realizability of target refining schedule for oil refinery[END_REF]. At the upper level, one needs to find a refining schedule by optimizing certain objectives, while, at the lower level, a detailed schedule is created for a given refining one. With this decomposition and a Petri net model [START_REF] Wu | A Petri net based heuristic algorithm for realizability of target refining schedule for oil refinery[END_REF]- [START_REF] Wu | Hybrid Petri net modeling and schedulability analysis of high fusion point oil transportation under tank grouping strategy for crude oil operations in refinery[END_REF], [START_REF]Deadlock Resolution in Computer-Integrated Systems[END_REF]- [START_REF] Zurawski | Petri nets and industrial applications: A Tutorial[END_REF] a heuristic is proposed to check the realizability for a given refining schedule in [START_REF] Wu | A Petri net based heuristic algorithm for realizability of target refining schedule for oil refinery[END_REF]. If realizable, a detailed schedule is created. Nevertheless, by that method, if a detailed schedule is not found, it cannot answer whether the refining schedule is realizable or not. Furthermore, in [START_REF] Wu | A Petri net based heuristic algorithm for realizability of target refining schedule for oil refinery[END_REF], no method is presented for how a realizable refining schedule can be efficiently found.

A schedule should satisfy all the constraints. If so, it is a feasible schedule, and otherwise, it is infeasible one. The shortterm scheduling problem for crude oil operations is studied in a control perspective in [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF]- [START_REF] Wu | Schedulability analysis of short-term scheduling for crude oil operations in refinery with oil residency time and charging-tank-switch-overlap constraints[END_REF]. It is found that a short-term schedule is composed of a series of operation decisions (OD). The execution of an OD transfers the system from a state to another. A state is called safe, if starting with this state, there exists a feasible schedule, and otherwise, it is unsafe. Thus, for a feasible schedule, each OD should transfer the system from a safe state to another safe one. If a system is schedulable, initially, it must be at a safe state. To analyze the schedulability of crude oil operations, an architecture as shown in Fig. 1 is proposed. The crude oil operation process contains both discrete event and continuous variables; hence, it is a hybrid process. Based on the proposed architecture, hybrid Petri net models are developed to describe this process in [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF]- [START_REF] Wu | Schedulability analysis of short-term scheduling for crude oil operations in refinery with oil residency time and charging-tank-switch-overlap constraints[END_REF]. With these models, schedulabilty analysis is made and schedulabilty conditions are presented for different situations. These conditions can be used to check the realizability of a given refining schedule. If schedulable, a detailed schedule can be easily found. These conditions can also be used as constraints to obtain a realizable and optimal refining schedule. However, no method is presented for how to find such a refining schedule in [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF]- [START_REF] Wu | Schedulability analysis of short-term scheduling for crude oil operations in refinery with oil residency time and charging-tank-switch-overlap constraints[END_REF]. If such a refining schedule can be found in an efficient way, the shortterm scheduling problem for crude oil operations can be solved. Based on the schedulabilty conditions, this paper addresses the refining scheduling problem and presents an efficient approach to find a realizable and optimal refining schedule. It is a threephase approach. In phase 1, a linear programming model is built and solved to maximize productivity; in phase 2, a transportation problem is solved to assign crude oil to distillers; and then, in phase 3, the parcels of different crude oil types are sequenced to minimize the number of switching times. This way, a realizable and optimal refining schedule can be easily obtained. By this approach, the following contributions are made: 1) the hybrid optimization problem is decomposed such that each subproblem has only continuous or discrete event variables; 2) in phases 1 and 2, the subproblems are linear programming and transportation problem, respectively, which can be solved very efficiently, and it shows that the problem in phase 3 can be solved by a polynomial algorithm. Thus, the approach is computationally efficient; and 3) multiple objectives are handled effectively.

The remainder of this paper is organized as follows. In Section II, the process of crude oil operations is briefly introduced and statement of a refining scheduling problem is made. Then, the scheduling approach is presented in Section III. Section IV uses an industrial case problem to show the application and efficiency of the proposed approach. Conclusions are given in Section V.

II. CRUDE OIL OPERATIONS AND REFINING SCHEDULE

Before presenting our approach, this section briefly introduces crude oil operations in refinery and defines its refining scheduling problem.

A. Process

A general refinery process is illustrated in Fig. 2. It can be divided into three phases: 1) crude oil operations; 2) production; and 3) final product delivery. Crude oil is carried to the port by crude oil tankers and then 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. This process forms the crude oil operations. The middle products from the distillers are then sent to other production units for fractionation and reaction, which is the second phase. The products after fractionation and reaction are blended to produce the final products. As for short-term scheduling in a refinery, the scheduling problem of crude oil operations is one of the most difficult parts.

There are various types of crude oil processed in a refinery. The components are different given different types of crude oil. Each distiller can process parts of the crude oil types, but not all. Although a type of crude oil may be processed by multiple ones, the effectiveness is different for different ones. One can rank their effectiveness to process a crude oil type.

Because different types of crude oil should be processed by different distiller, a tank (storage or charging tank) can hold one type of crude oil at a time. Thus, crude oil can be unloaded into only an empty storage tank unless the same type of crude oil is in it. Similarly, crude oil in a storage tank can be transported via a pipeline into an empty charging tank or a charging tank with same type of oil in it. After filling a storage or charging tank, crude oil must stay in it for a certain amount of time before it can be discharged. This time delay is called oil residency time. Besides, a tank cannot receive and send oil at the same time for both storage and charging tanks.

Usually, a pipeline takes tens of kilometers long with the capacity of tens of thousand cubic meters. It is full of crude oil all the time and cannot be emptied. Because all types of crude oil are transported from storage tanks to charging tanks via a pipeline, there may be a number of segments of crude oil in the pipeline with different types of oil for different segments.

When crude oil in storage tanks is transported through a pipeline to charging tanks, different types of crude oil may be mixed to obtain suitable components for distillation with the oil transportation. However, we do not consider the mixing here for a mixture can be treated just as a type of crude oil. When a charging tank is feeding a volume ξ of crude oil into a distiller in time interval [τ 1 , τ 2 ] this tank must be dedicated to the distiller and cannot be charged during the time interval. Crude oil can also be mixed when it is fed into distillers. However, by doing so, two or more charging tanks should be used to serve one distiller at the same time. This way, a large number of charging tanks are required for distiller feeding. Hence, such an operational way is not considered because of the limited number of charging tanks. Thus, only one tank is needed to feed one distiller at a time unless it switches from one charging tank to another tank for feeding a distiller.

In feeding a distiller, there is a charging-tank-switch-overlap constraint explained as follows. Assume that charging tank CTK 1 is feeding distiller DS 1 and the oil in CTK 1 will be used up at time τ if the distiller is fed by just CTK 1 . However, the refining process requires that the successor tank CTK 2 ready to feed DS 1 should start working at time τ 1 , i.e., before τ . Thus, in time interval [τ 1 , τ 2 ] with τ 1 <τ <τ 2 , both CTK 1 and CTK 2 are feeding distiller DS 1 . During this time, the remaining oil in charging tank CTK 1 is used up, as well as a certain amount of crude oil in CTK 2 is fed into distiller DS 1 .T h i s is called charging-tank-switch-overlap constraint in distiller feeding.

In summary, the process includes the following resource and process constraints. The former 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. The latter include: 1) a distiller should be kept in working all the time uninterruptedly with upper and lower bounds of its production rate; 2) a type of crude oil should be processed by suitable distillers; 3) at least one charging tank should be dedicated to a distiller at any time for feeding it; 4) a tank cannot be charged and discharged simultaneously; 5) oil residency time constraint must be met; and 6) charging-tank-switch-overlap constraint.

B. Refining Scheduling Problem

Let Γ=[τ s , τ e ] denote the scheduling horizon that often lasts for a week or ten days with τ s and τ e being the start and end time points. A short-term schedule for crude oil operations should provide all the activities in every detail. For general scheduling problems, there are a set of jobs and a number of servers. The jobs are well defined, or they are often assumed to consume deterministic processing time. The scheduling problem is to assign the jobs to servers and determine the processing sequence for each server. For refining scheduling, the servers are the set of distillers in a refinery plant. However, the jobs that are to be scheduled are not known before a schedule is obtained. All the information that we know is the scheduling horizon Γ=[τ s , τ e ] and the initial state of the process at τ s . The initial state is characterized by the following.

1) The production state. For a distiller i,itgives: a) the type of crude oil being processed by distiller i; b) the production rate with which crude oil is being processed by distiller i; c) the charging tank that is feeding distiller i.

2) The state of tanks. A storage or charging tank must be in one of the four states: a) idle and empty; b) idle with oil in it; c) in charging; and d) in discharging: i) for State b, one has the information of the crude oil type and amount in it; ii) for State c, the crude oil type that is being charged, the charging rate, and amount of oil in the tank at the moment are given;

iii) for State d, the crude oil type and amount remained in the tank and the discharging rate are given. 3) The state of a pipeline. A pipeline must be in one of the states: a) idle; and b) transporting crude oil from storage tanks to charging tanks: i) for both states a and b, one has the number of different segments of crude oil in the pipeline, the crude oil type and amount for each segment at the moment; ii) for State b, one has the rate with which crude oil is being transported. 4) The information of tanker arrivals. It includes the number of ships that will arrive during the scheduling horizon, and for each ship, one has a) arrival time; b) the types of crude oil in the ship and the amount of oil for each type; and c) the oil unloading rate. With the initial state for a process, a refining schedule is to determine, at any time point for the entire scheduling horizon, the production rate and the type of crude oil to be processed for every distiller in the system. In a refinery, processing different types of crude oil produces different products. To meet the market demands, various types of crude oil should be processed. Thus, for a distiller, it needs to switch from processing one type of crude oil to another type. Thus, the main decision for a refining scheduling is when such switches take place and the types of crude oil for each switch. To describe a refining schedule, we define a feeding parcel of crude oil (FPCO).

Definition 2.1:

FPCO = (COT, ζ,[ α, β]
) is defined as an FPCO, where COT = crude oil type to be fed into a distiller; ζ = volume of crude oil to be fed into a distiller; and [α, β]isa time interval in which α and β are the start and end time points for feeding this parcel of crude oil.

The flow rate for feeding such a parcel of oil during [α, β] can vary. However, when it changes, the set point for the distillation process should change as well, which leads to some loss. Thus, in practice, the flow rate for an FPCO is set to be a constant and can be calculated by f = ς/(β -α). Thereafter, if the same type of crude oil is fed into a distiller with different flow rate, we can simply treat it as a different FPCO.

Let FPCO ij = (COT ij , ζ ij ,[ α ij , β ij ]
) denote the jth FPCO for feeding distiller i. Assume that it needs Q FPCOs for distiller i during the scheduling horizon. Then, its refining schedule for distiller i can be denoted as RS i = {FPCO i 1 , FPCO i 2 , ..., FPCO iQ }. Furthermore, assume that there are K distillers in the system and let DS = {1, 2, ..., K} be the set of distillers and

f ij = ζ ij /(β ij -α ij ).
Then, the refining scheduling problem is to find an ordered set of FPCOs RS = {RS 1 ,RS 2 , ...,RS K } such that the following conditions are satisfied:

τ s = α i1 ,β i1 = α i2 ,...,β ij = α i(j +1) ,..., β i(Q -1) = α iQ
F i(MIN) ≤ f ij ≤ F i(MAX) ∀i ∈ DS (2.2)
where F i (MIN) and F i (MAX) are the allowable minimal and maximal flow rate for feeding distiller i. An illustrative refining schedule is shown in Fig. 3, where there are three distillers and two FPCOs for each distiller with a ten-day scheduling horizon.

Feasibility is essential for scheduling the crude oil operations. It requires that a refining schedule must be realizable by a detailed schedule. It should be pointed out that conditions (2.1) and (2.2) are not enough to guarantee the feasibility of a refining schedule RS. An oil refining process is a continuous process and it has an operation requirement as follows. If, at the initial state, charging tank A is feeding distiller DS 1 with a type of crude oil #k, a refining process starting from time τ s should be scheduled such that distiller DS 1 should continue to refine crude oil #k in charging tank A until tank A is emptied. If a refining schedule can meet this requirement, it is said that such a refining schedule is compatible with the initial state. Hence, the feasibility of a refining schedule is defined as follows.

Definition 2.2: A refining schedule for crude oil operations in a refinery is said to be feasible if 1) it is compatible with the initial state and 2) there exists a detailed schedule that implements it such that all the constraints given in the previous section are satisfied. In [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF]- [START_REF] Wu | Hybrid Petri net modeling and schedulability analysis of high fusion point oil transportation under tank grouping strategy for crude oil operations in refinery[END_REF], schedulability conditions are presented. With these conditions as constraints, a realizable refining schedule can be found, but it does not know how such a schedule can be found. Up to now, we have described the refining problem. Based on the problem statement, an efficient scheduling approach will be presented in the next section.

III. SCHEDULING METHOD

With the description of refining scheduling in the previous section, this section presents an efficient scheduling approach.

A. Analysis of Refining Scheduling

Some objectives should be optimized when the crude oil operations are scheduled. Thus, we need to determine the objectives first. In the literature, the objectives include: 1) minimization of crude oil inventory cost, tanker waiting cost, and crude oil unloading cost [START_REF] Jia | Refinery short-term scheduling using continuous time formation: Crude oil operations[END_REF], [START_REF] Jia | Efficient short-term scheduling of refinery operations based on a continuous time formulation[END_REF], [START_REF] Lee | Mixed integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management[END_REF]; 2) maximization of production and minimization of the number of tanks used [START_REF] Pinto | Planning and scheduling models for refinery operations[END_REF]; 3) minimization of changeover cost [START_REF] Lee | Mixed integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management[END_REF]; and 4) minimization of heels [START_REF] Shah | Mathematical programming techniques for crude oil scheduling[END_REF]. Among them, the minimization of crude oil inventory and changeover costs, and the maximization of production are related to the refining scheduling, while the others should be pursued at the detailed scheduling level. Note that for refining scheduling, the amount of crude oil available at the beginning of the scheduling horizon and the amount of crude oil that will arrive during the scheduling horizon are independent of the scheduling. Thus, with the initial crude oil inventory and oil arrival information, if the crude oil operations are scheduled such that the production rate is maximized, the crude oil inventory during the scheduling horizon must be minimized. Hence, maximizing the production rate minimizes the crude oil inventory cost at the same time. Besides maximization of production rate and minimization of crude oil inventory, the cost caused by assigning crude oil types to distillers should be minimized when crude oil operations are scheduled. As stated in the previous section, although a type of crude oil can be processed by a number of distillers, the effectiveness is different when it is processed by different distillers. Therefore, it needs to assign crude oil types to appropriate distillers for processing. In this paper, the goal is to find a refining schedule such that production is maximized, and changeover and crude oil type assignment costs are minimized.

As defined in Definition 2.2, to make a refining schedule realizable, schedulability conditions must be satisfied. Such conditions should be taken as constraints in finding a refining schedule. Thus, before developing the approach, we first present the schedulability conditions as follows. Let Ψ denote the oil residency time, f dsi the feeding rate to distiller i, and F p max the maximal flow rate of the pipeline. We have the following schedulability conditions without considering the chargingtank-switch-overlap constraint.

Lemma 3.1 [START_REF] Wu | Hybrid Petri net modeling and schedulability analysis of high fusion point oil transportation under tank grouping strategy for crude oil operations in refinery[END_REF]: Assume that: 1) the feeding rate for the

K distillers DS 1-K is f ds1 >f ds2 > ••• >f dsK , α 1 =Ψ× f ds1 , α 2 =Ψ× f ds2 , ..., and α K =Ψ × f dsK ; 2) there are 2K + 2 charging tanks CTK 1-(2K +2) with capacities ξ 1 ≥ Kα 1 , ξ 2 ≥ Kα 1 , ξ 3 ≥ Kα 1 , ξ 4 ≥ Kα 2 , ξ 5 ≥ Kα 2 , ..., ξ 2 i ≥ Kα i , ξ 2 i+1 ≥ Kα i , ..., and ξ 2 K ≥ Kα K , ξ 2 K +1 ≥ Kα K , ξ 2 K +2 ≥ Kα K ;3 )F p max = f ds1 + f ds2 + ••• + f dsK ; 4) initially, the volume of oil type 1 in CTK 1 and CTK 2 is ζ 1 = ζ 2 = Kα 1 ,the volume of oil type 2 in CTK 4 is ζ 4 = Kα 2 , ..., the volume of oil type i in CTK 2i is ζ 2 i = Kα i , ..., the volume of oil type K in CTK 2K is ζ 2 K = Kα K ,
the other tanks are empty, and the oil in CTK 1 , CTK 4 , ..., CTK 2i , ..., and CTK 2K is ready to feed; 5) the volume of crude oil of type K remaining in storage tanks is β<α K , and after processing this amount of oil type K, distiller DS K should switch to process oil type j. Then, the system is schedulable and the volume β of oil type K can be used up without being mixed with other oil type.

Lemma 3.1 states that for the entire scheduling horizon, if there are three charging tanks for each distiller and there is enough crude oil in the charging tanks at the beginning of the scheduling horizon, a feasible short-term schedule can be found. When the charging-tank-switch-overlap constraint is considered, we can show that if the conditions given in Lemma 3.1 are satisfied, the system is still schedulable. In the following discussion, we show how these conditions are included in the models as constraints such that a feasible refining schedule can be obtained.

It follows from the initial state information that some crude oil arrives at the port at time t with τ s <t<τ e . This implies that only after time point τ>tcan such crude oil be ready to feed a distiller. With time point t, the oil unloading rate, the oil residency time, and the oil transportation rate from a storage tank to a charging tank known, τ can be calculated. Thus, when Q tankers arrive during the scheduling horizon at times t 1 , t 2 , ..., and t Q , respectively, with τ s <t 1 <t 2 < ... < t Q <τ e ,w e can obtain τ 1 , τ 2 , ..., and τ Q with τ s <τ 1 <τ 2 < ... < τ Q <τ e such that the crude oil in the tanker that arrives at t i can be available for feeding after τ i . In this paper, we assume that τ 1 , τ 2 , ..., and τ Q are known. This way, the scheduling horizon is

divided into Q + 1 time buckets [τ s , τ 1 ], [τ 1 , τ 2 ], ...,[ τ Q -1 , τ Q ],
and [τ Q , τ e ]. Alternatively, they can be called buckets 0, 1, ..., and Q, respectively.

To describe the effectiveness to process a crude oil type by a distiller, a cost associated with a type of crude oil and a distiller can be set. If it is the best to process crude oil type i by distiller j, small cost is set. We can order the crude oil types that can be processed by a distiller from the best to the worst and set the cost in an increasing way. If crude oil type i cannot be processed by distiller j, the cost is set to be a very large number.

To develop the refining scheduling approach, we present the following notation. Capacity of the pipeline.

V i-c

Volume of crude oil type i in the charging tanks at time τ s , i ∈ COT.

W ij

Remaining volume of crude oil type i in the charging tank feeding distiller j at time τ s , i ∈ COT and j ∈ DS.

V i-p

Volume of crude oil type i in the pipeline at time τ s , i ∈ COT, with

i∈COT V i(pipe) = V p . V i-s
Volume of crude oil type i in the storage tanks at time τ s , i ∈ COT.

V ik

Volume of crude oil type i that is available for feeding after time τ k , i ∈ COT and k ∈ BUK. F i (MAX)

Maximal feeding rate allowed for distiller i ∈ DS.

F i (MIN)

Minimal feeding rate allowed for distiller i ∈ DS.

F p max

Maximal oil transportation rate via the pipeline.

Ω i

Set of crude oil types that can be processed by distiller i, i ∈ DS; f ij Oil feeding rate to distiller i during bucket j, i ∈ DS and j ∈ BUK.

The proposed scheduling approach is a three-phase one. In phase 1, the production rate to maximize the production is determined. The amount of crude oil to be processed for each distiller during each bucket is, therefore, found. Then, in phase 2, the crude oil types and amount of crude oil are assigned to the distillers to minimize the crude oil type assignment cost. In phase 3, the result obtained in phase 2 is adjusted, and the crude oil parcels and their sequence are determined to minimize the changeover cost.

B. Determination of Production Rate

In this section, a model is presented to solve the problem of phase 1 as follows. To maximize the production is to maximize the crude oil feeding rate for each distiller

Problem P1: Maximize J = Q j =0 i∈DS f ij (3.1)
subject to

F i(MIN) ≤ f ij ≤ F i(MAX) ,i ∈ DS and j ∈ BUK (3.2) i∈DS f ij ≤ F p max ,j ∈ BUK (3.3) i∈Ω j V i-c + i∈Ω j V i-p + i∈Ω j V i-s ≥ (τ 1 -τ s )f j 0 ,j ∈ DS (3.4) i∈COT V i-c + i∈COT V i-p + i∈COT V i-s ≥ (τ 1 -τ s ) j ∈DS f j 0 (3.5) i∈Ω j V i-c + i∈Ω j V i-p + i∈Ω j V i-s + i∈Ω j n k =1 V ik ≥ (τ 1 -τ s )f j 0 + n k =1 (τ k +1 -τ k )f jk ,j ∈ DS and 1 ≤ n ≤ Q -1 (3.6) i∈COT V i-c + i∈COT V i-p + i∈COT V i-s + i∈COT n k =1 V ik ≥ (τ 1 -τ s ) j ∈DS f j 0 + j ∈DS n k =1 (τ k +1 -τ k )f jk , 1 ≤ n ≤ Q -1 (3.7) i∈Ω j V i-c + i∈Ω j V i-p + i∈Ω j V i-s + i∈Ω j Q k =1 V ik ≥ (τ 1 -τ s )f j 0 + Q -1 k =1 (τ k +1 -τ k )f jk +(τ e -τ Q )f jQ , j ∈ DS (3.8) i∈COT V i-c + i∈COT V i-p + i∈COT V i-s + i∈COT Q k =1 V ik -V p ≥ (τ 1 -τ s ) j ∈DS f j 0 + j ∈DS Q -1 k =1 (τ k +1 -τ k )f jk + j ∈DS (τ e -τ Q )f jQ .
(3.9)

Objective (3.1) maximizes the production, and meanwhile, minimizes crude oil inventory cost as well. Constraint (3.2) states that for every distiller the crude oil feeding rate should be in an allowable range. As indicated in Lemma 3.1, the total production rate for the system cannot be greater than the maximal flow rate of the pipeline. This is guaranteed by Constraint (3.3).

In bucket 0, only the crude oil in charging tanks, pipeline, and storage tanks can be usable. Constraint (3.4) says that f j 0 's should be set such that there is enough crude oil to be processed at each distiller, which implicitly gives the constraint that there is enough crude oil in the charging tanks at the beginning of the scheduling horizon as required by Lemma 3.1. Because a type of crude oil can be processed by more than one distiller, the satisfaction of Constraint (3.4) cannot guarantee that there is enough crude oil to be processed for the entire system in bucket 0. Thus, Constraint (3.5) is introduced. Similarly, Constraints (3.6) and (3.7) are introduced to guarantee that there is enough crude oil to be processed for each distiller and the entire system in the buckets 0, 1, ..., n with 1 ≤ n ≤ Q -1. Constraints (3.8) and (3.9) mean that during the entire scheduling horizon, there is enough crude oil for each distiller and the whole system, respectively. Note that at the end of the scheduling horizon, the pipeline should be full of oil; thus, it subtracts V p from the left size in Constraint (3.9). It can be seen that in the model, f ij 's are the decision variables and they are continuous variables and there is no discrete event variable at all. Thus, Problem P1 is formulated as a linear programming and is easy to solve.

C. Assignment of Crude Oil to Distillers

With the production rate obtained by solving Problem P1, the amount of crude oil to be processed by each distiller is known. Then, it needs to divide the amount of crude oil to be processed during the scheduling horizon into a number of parcels and assign these parcels into the distillers. This problem is called Problem P2. Moreover, the number of parcels of crude oil is not known and needs to be determined by the scheduler. Thus, it seems that such a problem is a combinatorial problem and is hard to solve. However, if we treat the types of crude oil as suppliers and the distillers as demanders, this problem can be formulated as a transportation problem. It is sure that by solving such a transportation problem, a number of parcels of crude oil with different types are assigned to each distiller. By merging the parcels of the same type of crude oil, a schedule can be formed for each distiller. This way, this problem can be solved easily.

TABLE I TRANSPORTATION MODEL FOR PROBLEM P2

Let Θ ij , i ∈ DS and j ∈ BUK, denote bucket j of distiller i; Φ i-c , i ∈ COT, crude oil type i in the charging tanks; Φ i-p , i ∈ COT, crude oil type i in the pipeline; Φ i-s , i ∈ COT, crude oil type i in the storage tanks; and Φ ij , i ∈ COT and j ∈ BUK, crude oil type i available after τ j . The transportation problem model for P2 is presented in Table I.

To make a refining schedule feasible, crude oil that is available after τ j cannot be assigned to a distiller for processing in a bucket k with k<j,orΦ ij cannot be assigned to Θ hk with k< j. Thus, big M is set in the intersection of Φ ij and Θ hk . In fact, this is why the scheduling horizon is divided into a number of buckets when the problem is modeled. It should also be pointed out that C ij may be equal to M , meaning that crude oil type i cannot be processed by distiller j.

To make a refining schedule compatible with the initial state, if a charging tank with crude oil type i in it is feeding distiller j at the initial state, the remaining oil in that tank should be fed into distiller j in the schedule. This implies that such crude oil should be assigned into distiller j in the schedule. In a refinery plant, the number of distillers is less than the number of crude oil types. Hence, without loss of generality, we assume that the crude oil type being fed into distiller j is j at the initial state, and the remaining volume is W jj . Further, assume that (τ 1τ s )f j 0 ≥ W jj . Thus, the demand of Θ j 0 is (τ 1 -τ s )f j 0 -W jj as shown in the model. If (τ 1 -τ s )f j 0 ≥ W jj is not satisfied, we can just set the demand of Θ j 0 to be zero and the demand of Θ j 1 to be (τ 2 -τ 1 )f j 1 + (τ 1 -τ s )f j 0 -W jj . Correspondingly, the supply of Φ j -c becomes V j -c -W jj asshowninthe model.

At the end of the scheduling horizon, the pipeline must be full of crude oil. Thus, there is a crude oil demand for filling the pipeline with amount V p .

To guarantee the existence of a solution for a transportation problem, the total demand must be equal to the total supply. By Problem P1, the total supply is greater than or equal to the total demand. Thus, a dummy distiller denoted by DM-DS is necessary and its demand is

Z = i∈COT V i-c + i∈COT V i-p + i∈COT V i-s + i∈COT Q k =1 V ik -V p -(τ 1 -τ s ) j ∈DS f j 0 -j ∈DS Q -1 k =1 (τ k +1 -τ k )f jk -j ∈DS (τ e -τ Q )f jQ .
As discussed previously, the conditions given in Lemma 3.1 should be satisfied to make a refining schedule feasible. According to Lemma 3.1, it needs at least three charging tanks for a distiller to make a refining schedule realizable, which is not included in P1 as a constraint. Hence, this constraint should be considered in P2. In a refinery plant, if all the charging tanks are usable, this condition can be easily satisfied. In general, in a refinery plant, i∈COT V i-c + i∈COT V i-p is less than the total amount for processing during the scheduling horizon. Thus, to guarantee the condition that there are three charging tanks for a distiller to be satisfied, all the charging tanks with oil in it at τ s should be usable during the scheduling horizon. This implies that all the crude oil in the charging tanks at τ s cannot be assigned to the dummy distiller DM-DS, and such crude oil is impossible to assign to the pipeline. The crude oil in the pipeline at τ s takes spaces of charging tanks and cannot be assigned to dummy distiller DM-DS either. Hence, the corresponding costs are set to be big M .

With the aforementioned analysis, by solving the transportation model given in Table I, a feasible refining schedule can be obtained. It is well known that a transportation problem is easier to be solved than a linear programming, and there are standard commercial software tools for this purpose. Thus, Problem P2 can be solved very efficiently. Note that the solution is composed of a number of crude oil parcels distinguished by oil types. It should be pointed out that the great challenge of scheduling crude oil operations results from the hybrid property of the process. Although Problem P2 is a continuous optimization problem, its solution is composed of a number of discrete crude oil parcels. Thus, P2 implicitly solves a hybrid optimization problem.

D. Sequencing Parcels

To minimize the changeover cost, it is best to assign crude oil in a charging tank to a single distiller. However, by solving the transportation problem given in Table I, crude oil in a charging tank at τ s may be assigned to more than one distiller. For example, there is volume V of crude oil in a charging tank at τ s ;i t may assign V 1 to Distiller 1 and V 2 to Distiller 2 with V 1 + V 2 = V . For this case, if possible, it is better to adjust the assignment such that V is assigned to distillers 1 or 2 only. It can be done as follows.

1) Assume that another crude oil type, say type 2, is assigned to distiller DS 1 , and meanwhile, there is crude oil type that can be processed by distiller DS 2 , say type 3, and is assigned to DM-DS with volume V 3 ≥ V 2 . Then, we can reassign the crude oil as follows: a) V is assigned to DS 1 ; b) take V 2 of crude oil type 3 from DM-DS to DS 2 ; and c) take V 2 of crude oil type 2 from DS 1 to DM-DS. 2) Assume that another crude oil type, say type 2, is assigned to DS 1 and crude oil type 2 can be processed by DS 2 too. Then, we can reassign the crude oil as follows: a) V is assigned to DS 1 ; and b) take V 2 of crude oil type 2 from DS 1 to DS 2 . The computational complexity of the aforementioned algorithm can be analyzed as follows. Assume that there are N charging tanks in which there is crude oil at the initial state. By requirement, such crude oil should be processed during the next scheduling horizon. Further, assume that the crude oil type in different charging tank is different, and each type of crude oil can be assigned to at most G distillers with G equal to or less than Π, i.e., the number of distillers in the plant. For a charging tank, only G -1 adjustments are needed to complete the previous algorithm. Thus, there are no more than N × (G -1) adjustments, which are of polynomial complexity.

Note that, in solving the transportation problem given in Table I, the crude oil from the charging tanks, pipeline, storage tanks, and so on is treated as from different suppliers. However, two parcels of crude oil assigned to a distiller from different suppliers may be of the same type. These parcels should be merged if they can be processed one after another such that changeover cost is reduced. Because the number of crude oil types is limited, the parcel merging is very simple.

With crude oil reassigned and parcel merging, we need only to sequence the parcels of crude oil for each distiller according to the order of available time to obtain a feasible refining schedule.

Up to now, we have presented the approach for refining scheduling. By this three-phase approach, we successfully discompose a hybrid optimization problem into subproblems such that each subproblem contains only continuous or discrete event variables. In addition, multiple objectives are effectively handled in different phase. To solve the problem, it needs to solve a linear programming problem, a transportation problem, and adjusting and sequencing the parcels. This way, the subproblems in all the phases can be efficiently solved. Thus, the proposed approach for refining scheduling is computationally efficient and can be used for practical applications. Furthermore, by combining the approaches for a detailed schedule presented in [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF] and [START_REF] Wu | Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint[END_REF], a short-term schedule for crude oil operations can be efficiently found. This is a significant advancement in this research field.

IV. INDUSTRIAL CASE STUDY

This section presents a case study to show the application of the approach that is proposed in this paper. This case problem arises from a practical application scenario of a refinery in China. The refinery has three distillers 1, 2, and 3. Three times each month, a short-term schedule should be created for the next ten days. For the scheduling horizon in this paper, there are six types of crude oil to be processed. Crude oil type #1 can be processed by only Distiller 1 and Crude oil #2 by only Distiller 2. Crude oil #3 can be processed by all three distillers; however, it is best to be processed by Distiller 1, then by Distiller 3, and it is the worst if it is processed by Distiller 2. Crude oil types #4, #5, and #6 can be processed by both Distillers 2 and 3 with different cost. Such cost associated with crude oil types and distillers is given in Table II, where "M " means that a type of oil cannot be processed by the corresponding distiller.

During the scheduling horizon, there are nine charging tanks available. Initially, there is crude oil in Charging Tanks #129, #128, #116, #117, and #115, and the others are empty. At this state, Tanks #129, #128, and #116 are feeding Distillers 1, 2, and 3, respectively. The initial state of the charging tanks is shown in Table III. The capacity of the pipeline is 12 000 tons and the pipeline is full of crude oil type #2. There are 28 000 tons of crude oil #3, 54 000 tons of crude oil #2, and 64 000 tons of crude oil #1 in the storage tanks. During scheduling horizon, a tanker will arrive with 132 000 tons of crude oil #6. Assume that τ s = 0 h. Then we can obtain τ 1 = 96 h, or after time 96 h, the oil in the tanker can be used for distillation. Hence, the scheduling horizon is divided into two buckets [0, 96] and [96,240].

The minimal production rates for the three distillers are 312.5, 205, and 458 tons/h, and maximal production rates are 375, 230, and 500 tons/h, respectively. The maximal flow rate of the pipeline is f p max = 1250 tons/h. Four hours are required for both oil residency time for charging tanks and charging-tank-switchoverlap time.

With the initial state information, according to Lemma 3.1, there is enough crude oil in the charging tanks for obtaining a realizable refining schedule. In addition, if all the oil in the charging tanks is processed during the scheduling horizon, there are enough charging tanks for scheduling the system. Thus, the approach presented in the previous section can be used to find a realizable refining schedule.

By using the initial state information, it is easy to write down the linear programming model for problem P1 for this case. By solving P1, we obtain f 10 = f 11 = 375 tons/h, f 20 = f 21 = 230 tons/h, and f 30 = f 31 = 500 tons/h. This is the maximal production rate for the system and the crude oil inventory is also minimized. With the production rate for each distiller in each bucket, the amount of crude oil to be processed by each distiller in each bucket can be obtained as shown in Table IV.

At the initial state, Charging Tanks #129, #128, and #116 are feeding Distillers 1, 2, and 3, respectively. Thus, to make a refining schedule compatible with the initial state, 27 000 tons of type #3 oil, 30 000 tons of type #2 oil, and 27 000 tons of type #4 oil should be assigned to bucket 0 of Distillers 1, 2, and 3, respectively. With this assignment, the modified amount of crude oil to be processed by each distiller in each bucket is shown in Table V ). After this assignment, 1000 tons of type #1 oil, 54 000 tons of type #2 oil, 28 000 tons of type #3 oil, and 80 800 tons of type #6 oil remain. By P 22 , P 32 , and P 33 , it assigns the oil in Tanks #117 and #115 to more than one distiller such that the oil in one tank is divided into two parcels, leading to the changeover cost. Thus, according to the proposed method, this can be adjusted: 1) move P 22 from Distiller 2 to Distiller 3; 2) create P 24 with 13 200 tons of type #2 oil from the storage tanks; and 3) take 13 200 tons of oil from P 34 . Then, we merge: 1) P 12 and P 13 ;2) P 23 and P 24 with P 23 being processed before P 24 ; and 3) P 32 , P 33 , and P 22 , for they are the same type of crude oil. This way, a realizable refining schedule is obtained as shown in Fig. 4. It can be seen that although it is the best for Distiller 2 to process crude oil type #5, it is assigned to Distiller 3; otherwise, there would not be enough oil for Distiller 3 to process during bucket [0, 96] thereby an infeasible solution. In addition, 28 000 tons of oil type #3 is not used although it can be processed by all the distillers. It is meaningful to keep this type of crude oil for Distiller 1 to process for the next scheduling horizon; otherwise, there is no oil that can be processed by Distiller 1 during that time. Thus, the obtained refining schedule is a very good one.

By using the methods presented in [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF] and [START_REF] Wu | Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint[END_REF], a detailed schedule to realize the refining schedule obtained is easily created. The detailed schedules of distiller feeding and charging tank filling are shown in Figs. 5 and6, respectively. It can be seen that all the constraints, including crude oil residency time and charging-tank-switch-overlap constraints, are satisfied.

It should be pointed out that this case problem is from practical applications with all the constraints considered. It is extremely difficult for an existing mixed integer mathematical programming model to solve such large problems if it is not impossible. By combining the method presented in this paper and that in our previous work [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF], [START_REF] Wu | Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint[END_REF], a short-term schedule can be easily found.

V. C ONCLUSION Short-term scheduling for crude oil operations is a combinatorial problem and involves extreme detail. Thus, it is very complicated and, up to now, there are no efficient technique and software tool in practice. Thus, it is crucial to develop efficient methods to solve this problem. For this purpose, a two-level approach is presented and schedulability conditions are derived in [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF] and [START_REF] Wu | Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint[END_REF]. Based on the schedulability conditions, given a realizable refining schedule, it is easy to find a detailed schedule at the lower level. With the schedulability conditions, this paper solves the upper level problem of finding the optimal and realizable refining schedule. It successfully decomposes a hybrid optimization problem into subproblems such that each subproblem contains continuous or discrete event variables only but not both. In addition, multiple objectives are effectively handled in different phases. Thus, the entire short-term scheduling problem of crude oil operations is solved. The approach proposed in this paper is very efficient, for it needs to solve a linear programming problem, a transportation problem, and adjustment problems. They all can be solved very efficiently.

As pointed out in [START_REF] Wu | Short-term scheduling for refinery process: Bridging the gap between theory and applications[END_REF], there are various objectives that are to be optimized in finding a detailed schedule at the lower level. Although detailed scheduling methods are presented in [START_REF] Wu | Short-term schedulability analysis of crude oil operations in refinery with oil residency time constraint using Petri net[END_REF] and [START_REF] Wu | Short-term schedulability analysis of multiple distiller crude oil operations in refinery with oil residency time constraint[END_REF], the operations are not optimized. Optimization of detailed schedules at the lower level is one of our future studies. Developing methods for short-term scheduling of crude oil operations is not enough. One needs efficient software tools for practical use. It is also our future work to develop such software tools by using the proposed methods.

Fig. 1 .

 1 Fig. 1. Architecture of short-term scheduling for crude oil operations.

Fig. 2 .

 2 Fig. 2. Illustrative view of the refinery process.

  , and β iQ = τ e ∀i ∈ DS(2.1)

Fig. 3 .

 3 Fig. 3. Illustrative refining schedule.

Fig. 4 .

 4 Fig. 4. Refining schedule for the case study.

Fig. 5 .

 5 Fig. 5. Detailed schedule of distiller feeding for the case study.

Fig. 6 .

 6 Fig. 6. Detailed schedule of charging tank filling.

  {0, 1, ..., Q} Set of buckets that begin at τ s , τ 1 , ..., and τ Q , respectively. C

	Λ	Number of crude oil types (COT) to
		be processed during the scheduling
		horizon.
	COT = {1, 2, ..., Λ} Set of crude oil types.
	Π	Number of distillers in the plant
	DS = {1, 2, ..., Π}	Set of distillers.
	Q	Number of tankers that will arrive dur-
		ing the scheduling horizon.
	BUK =

ij Cost if crude oil type i is processed by distiller j, i ∈ COT and j ∈ DS. V p

TABLE II COST

 II ASSOCIATED WITH CRUDE OIL TYPES AND DISTILLERS

TABLE III INITIAL

 III STATE OF THE CHARGING TANKS

TABLE IV AMOUNT

 IV (TON) OF CRUDE OIL TO BE PROCESSED IN EACH BUCKET

TABLE V MODIFIED

 V AMOUNT (TON) OF CRUDE OIL TO BE PROCESSED IN EACH BUCKET

TABLE VI TRANSPORTATION

 VI PROBLEM MODEL FOR PROBLEM P2

  . Notice that 22 080 tons of crude oil to be processed by Distiller 2 in bucket 0 is less than the amount in Charging Tanks #128. Hence, the amount of oil to be processed by Distiller 2 in bucket [96, 240] is modified as 25 200 tons. Distiller 3: 27 000 tons of type #4 oil in Tank #116 (parcel P 31 ), 21 000 and 20 800 tons of type #5 oil in Tanks #117 and #115 (parcels P 32 and P 33 ), and 51 200 tons of type #6 oil (parcel P 34

	Then, we can build the transportation problem model for
	Problem P2 as shown in Table VI. The following result of crude
	oil assignment is obtained by solving P2.
	1) Distiller 1: 27 000 tons of type #3 oil in Tank #129 (parcel
	P 11 ), 9000 tons of type #1 oil from storage tanks (parcel
	P 12 ), and 54 000 tons of type #1 oil from storage tanks
	(parcel P 13 );
	2) Distiller 2: 30 000 tons of type #2 oil in Tank #128 (parcel
	P 21 ), 13 200 tons of type #5 oil in Tanks #117 and #115
	(parcel P 22 ), and 12 000 tons of type #2 oil in the pipeline
	(parcel P 23 );
	3)


D Real
email: real@ific.uv.es

C Bozza

D Calvo

P Musico

P Jansweijer

S Colonges

V Van Beveren

F Versari

T Chiarusi

F Carriò

G Pellegrini

A F Díaz

KM3NeT acquisition: the new version of the Central Logic Board and its related Power Board, with highlights and evolution of the Control Unit

Keywords:

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

A

: The KM3NeT collaboration is currently building two deep sea neutrino telescopes at the bottom of the Mediterranean sea. The acquisition electronics for the first phase of the telescopes has been produced and several Detection Units have already been deployed. For subsequent phases, an improved version of the acquisition electronics has been designed with the goal of reducing the power consumption and improving the long term reliability of the boards. The control software suite, named Control Unit, is also being upgraded, in particular to overcome hardware failures. In this article, we present the last versions of the Central Logic Board and its associated Power Board, together with the evolution of the Control Unit.

Introduction

The KM3NeT Collaboration is building two neutrino telescopes at the bottom of the Mediterranean Sea [START_REF] Díaz | Letter of intent for KM3NeT 2.0[END_REF]. One, called Oscillation Research with Cosmics in the Abyss (ORCA), 40 km away from Toulon and the second one, called Astroparticle Research with Cosmics in the Abyss (ARCA), 100 km away from the southern tip of Sicily. The telescopes, designed to detect neutrinos by means of the Cherenkov photons induced by relativistic charged particles while traveling through the detector, consist in three-dimensional arrays of PhotoMultiplier Tubes (PMTs). Each Detection Unit (DU) is a string, anchored on the sea bed and tightened by a buoy, bearing 18 Digital Optical Modules (DOMs) [START_REF] Leonora | Design and production of the digital optical module of the KM3NeT project[END_REF]. Each DOM houses 31 PMTs together with its acquisition electronics [START_REF] Calvo | Digital optical module electronics of KM3NeT[END_REF], which main acquisition board is the Central Logic Board (CLB), supplied by its ancillary board, the Power Board (PB). The PMT signals are digitized at the PMT base boards. The PMT base board outputs a Low Voltage Differential Signal (LVDS) with a duration equal to the time over a pre-configured threshold, called Time over Threshold (ToT). The LVDS signals are conducted to the CLB by an aggregation board called Signal Collection Board (SCB). Then, the arrival time and the ToT are determined, with one nanosecond resolution, by the Time to Digital Converters (TDCs) implemented in the Field Programmable Gate Array (FPGA) of the CLB. In order to properly determine the trajectory of the Cherenkov photons it is needed to synchronize the different DOMs with a resolution better than one nanosecond. The synchronization of the DOM is performed in the FPGA of the CLB by means of the White Rabbit (WR) protocol [START_REF] Lipinski | White Rabbit: a PTP application for robust sub-nanosecond synchronization[END_REF], which allows the data communication and the synchronization using the optical link available. The shape of the detector changes continuously because of the sea currents. In order to obtain high directional accuracy and time resolution, the position and orientation of each DOM needs to be measured. Acoustic beacons provide reference signals whose arrival times are recorded by hydrophones and sent via the CLB to the shore station. While the main acquisition tasks are performed at the DOM level, specifically at the CLB, the control of the acquisition is performed by the Control Unit (CU), a software suite that allows to handle the DOM functions. It is a highly modular system, designed for scalability and high availability, which orchestrates the operation of the CLB as well as the triggering and data processing system. Section 2 is dedicated to a new version of the acquisition electronics. Section 3 briefly describes the CU and its latest evolution about hardware failure management. Conclusions are presented in section 4.

Acquisition hardware improvements

For the first phase of the project there has been produced enough CLB and PB to manufacture DOMs for 31 DUs, some of which have been already deployed and are currently taking data. Taking into account the return of the experience and in order to increase the performances and the reliability of the boards, new versions of both boards are being developed. The improvement of reliability is of paramount importance as, once deployed the DU, it will be impossible to perform any kind of maintenance. The main PB improvements include a modification of some of the DC/DC converters used to operate the PB more efficiently. This increases in efficiency results in decreasing the power consumption, thermal losses and the temperature inside the DOM and therefore increasing the reliability of the electronics.

Central Logic Board version 4

Several changes have been introduced in this new version of the CLB in order to improve the mechanics coupling with the rest of the DOM mechanics. Also some additional sensors have been introduced, as a pressure sensor, and the clock system has been improved to reduce the phase noise of the CLB clocks which has a great importance to improve the synchronization of the detector. In addition, the layout has been modified to use a new type of optical transceiver with higher reliability and a watchdog system has been introduced in order to further decrease the risk of losing access to the CLB due to an error in the reconfiguration of the acquisition firmware. An extensive list of the main improvements (figure 1) are here reported:

• Two flash memories. In the previous version there was only one Serial Port Interface (SPI) flash memory, while in this version it has been added an extra SPI flash memory. The main objective is to reduce the cycles of write/read in the flash memory storing the image in order to increase the operation life of this memory. The second memory is dedicated to an internal log and its end of life is not critical. The memories wear out of use. Separating the log in a different memory increase the life of the main flash memory.

• A new optical transceiver is used. This transceiver, from Glenair, has a higher reliability and a different layout with respect to the previous one. Therefore, the CLB has been modified to accommodate this new model of transceiver.

• New sensors have been included to the CLB. A pressure sensor has been added, and the compass, accelerometer and gyroscopes are moved from the previous daughter board to the CLB itself. • It has been included a hardware watchdog and the reset system has been updated.

• Two different clock schemes have been included in order to evaluate the best solution for WR from the point of view of stability and phase noise.

Central Logic Board clock generation system

The clock scheme of the CLBv4 is presented in figure 2. In the first system implemented, a clock of 25 MHz is generated by a quartz oscillator, and, in order to generate the needed 125 MHz, a low jitter clock generator is used to increase the frequency to the 125 MHz needed. The same applies for the generation of the 124.992 MHz. Instead, in the second system, the 125 MHz and the 124.99 MHz are generated directly by a quartz oscillator manufactured to oscillate at that frequency. As the quartz creates the frequency exactly it improves the quality of the clock signal. Both frequencies are needed to measure the phase using the Dual Mixer Time Difference (DMTD) technique. Four prototypes of the CLBv4 have been produced, where the new feature including the new clock generation system has been tested. The tests performed (see figure 3), where a CLBv4 connected to a standard WR switch has been turned off and on several times, show the stability of the clock generated when used by WR. The skew of the Pulse Per Second (PPS) presents very low jitter, with values below ± 25 ps standard deviation, a value well below the jitter requirements, of 100 ps. These values include also the effect of the reset and power down of the board as it is in this operation when usually higher differences are obtained. The jitter has been measured with conditions close to the final ones, including the use of fiber with the same length and it is not expected to deteriorate once deployed. The overall results are very promising for their use in KM3NeT.

Power Board version 3

The new version of the PB modifies several of the DC/DC converters in order to improve the global efficiency of the board. In particular, there has been changed the DC/DC converters of the rails of 2.5 V, 3.3 V and 5 V, obtaining an overall decrease in the consumption of 1 Watt when the PB supplies all the DOM acquisition electronics. (See table 1). The reliability of the board has also been improved. The FIDES analysis has been performed and, when compared with the previous version of the board, the Failure In Time (FIT) (given in failures in 10 9 hours) value has decreased to 783 (while the FIT of the previous version of the PB was 947).

Control Unit highlights and evolution

CLBs are driven and operated in a coordinated fashion by higher level software, named the CUs.

The same software is used in detectors deployed in the deep sea as well as in test benches for integration and qualification of PMTs, DOMs and DUs. Figure 4 shows the structure of the CU and how its services relate to the detector, the remote central database and the software used for triggering and data acquisition (TriDAS). The CU is built as a suite of software services. Each one has a certain degree of independence from the others, in the sense that it can work without communicating with other services for some time (minutes or even hours in some cases). Such modular approach has several advantages:

Trigger and Data Acquisition System

• Improved fault tolerance, because a single service getting stopped cannot cause data taking to stop.

• Increased separation of tasks and easier software development and maintenance.

• Ability to upgrade services one by one with the acquisition running, thus minimising the downtime.

Each CU service hosts its own web server that provides a graphical user interface relying on an HTTP layer; the latter is also used for a disconnected remote procedure call protocol, to communicate with each other service. The CU can run all on a single physical machine or can be distributed on several machines. In the following subsections, the various CU components will be described.

The Detector Manager

The Detector Manager (DM) is the CU service that directly controls the CLBs, through a UDPbased network protocol. Each CLB is controlled individually with a closed feedback loop that is asynchronous with respect to all others. This approach allows quick recovery of operation if a CLB loses contact or hangs and must be restarted. During the execution of recovery actions data acquisition can continue with the other CLBs.

The DM sets all operational parameters of the CLBs and continuously reads out monitoring data, including temperature of several devices, humidity, acceleration, compass, power levels and network link strength. The sampling frequency can be tuned in the range 0.1-10 Hz. All such parameters are exploited in two ways:

• They are stored into the so-called datalog files, staged to be later uploaded to the remote central database.

• They are exposed in a Virtual Directory which is accessible via HTTP. This is used by the graphical user interface (figure 5) and can be directly read by external programs or scripts to provide real-time monitoring and reporting. For each CLB, the DM sets up a mirror Finite State Machine (FSM), shown in figure 6, that is used to drive the CLB state machine, using the aforementioned UDP protocol. The state machine is conceptually identical for all components, both hardware and software, of the KM3NeT data acquisition and triggering, providing a single operational paradigm for the whole detector. Some states of the FSM are transient, whereas others correspond to operational targets of the CU:

• Off : PMTs are not powered.

• On: PMTs are powered but neither optical nor acoustic data are generated.

• Run: PMTs are powered, optical and acoustic data are generated.

Idle StandBy

The TriDAS Manager

The TriDAS Manager (TM) controls processes running on a local computer farm that performs triggering and online data acquisition and processing system (TriDAS). They are built on top of the same Finite State Machine as the CLBs. Data from the CLBs are sent to the Data Queues which rearrange them for the Optical and Acoustic Data Filters, so that each Data Filter can apply the triggering algorithms on the full detector. Triggered events are sent to the Data Writer(s) to be saved on permanent storage. Communication between the TM and the TriDAS processes occurs through a TCP-based network protocol (ControlHost) and a dispatcher that provides bidirectional time-ordered streams of messages. Like the DM, the TM fills datalog files that are later written to the remote central database, noting all events, actions performed and running parameters of the TriDAS processes. The same data are also exposed in a Virtual Directory for real-time access by the graphical user interface and possible other programs.

The Master Control Program

The Master Control Program (MCP) coordinates all other CU services. The MCP is the single authority that is responsible for defining:

• The current configuration of the detector (KM3NeT detectors are built incrementally and addition of new DUs causes a change in the detector configuration).

• The current set of operational parameters (defined as runsetup in KM3NeT terminology).

• The current run, i.e. a well defined timespan during which the runsetup does not change. For practical reasons of data management, it is convenient to break a run every few hours, hence forcing a run change even without a runsetup change.

• The current operational target.

• A list of scheduled jobs with a priority system to orderly manage the active time of the detector including routine duty tasks and special tasks such as calibrations or tests for detector development. At each time, the job with the highest priority is executed. A change of the current job causes a run change. A lower priority job may be preempted by a higher priority one and when the latter ends the MCP returns to the previous job if not expired yet, but now with a different run number. The logic is sketched in figure 7. For the convenience of detector operators, jobs can be automatically generated and enqueued in advance. Normal duty data-taking is performed by jobs of equal duration at the priority level above the baseline. Special tasks happen at a higher priority level.

Like other CU services, the MCP also produces datalogs and exposes its state in a Virtual Directory.

The Data Base Interface

The CU services use information provided by the remote central database [START_REF] Arnauld | The relational database system of KM3NeT[END_REF] and use it to book-keep the data acquisition activities and monitoring parameters. A Data Base Interface service is devoted to facilitate the interaction. The DBI polls the central database for user authentication information and user privileges, also considering data taking shifts done by human operators, which are centrally managed. The DBI downloads the detector definition, structure and calibration parameters that are to be applied at a certain time. On the other hand, run book-keeping information, jobs, datalog files and processed acoustic data (Time of Arrival of signals to the hydrophones) are uploaded to the central database when several MBs are available to optimise the transfer. The central database may not be reachable through the Internet because of several reasons, including network malfunctions or software/hardware failure on either end of the communication channel. Acquisition should not be stopped just because the database is temporarily unreachable. The Data Base Interface manages a two-way local cache to make vital information always available locally and to optimise the upload of data to the database. In addition, the DBI frees the local CU services from knowing the inner structure of the database and the SQL queries. If the database schema changes, the DBI is the single point where changes have to be reflected, all other services being left unperturbed. CU services communicate data with the DBI in the form of data files in XML format. The DBI is in charge of performing the translation to/from SQL. This also allows for evolution of the database schema or possible technology change, provided data can still be represented in a way that is convenient to the CU services. The DBI also exposes its status in a Virtual Directory accessible via HTTP.

The Local Authentication Provider

The CU has been designed to work in a protected environment, where security is provided by proper network access rules. Nevertheless, users have to be identified and proper permission sets have to be generated and applied to prevent possibly harmful mistakes. The Local Authentication Provider (LAP) acts as the local authority for authentication and identity management. In addition to this, the LAP used to hold the link between each CU service and the machine where it runs. Recently the tasks of the LAP have been upgraded to provide a full Dynamic Resource Provisioning and Failover. The computational power needed to run the TriDAS largely overwhelms the requirements of the CU, but a hardware failure in the CU can paralyse the acquisition for hours or days if an experienced administrator is not ready on call. This is particularly important in case a failure occurs during a transient neutrino emission, which is too short to wait for administrative intervention to migrate services from the failed machine to a healthy one. In order to make the system resilient and capable of automatic self-reconfiguration, CU services are configured to run on several machines and kept standing by except for one instance that is running. TriDAS services are also handled by the Dynamic Provisioning and normally occupy all available resources. If a failure is detected, the resources allocate to the TriDAS are revoked and used to power the CU services that automatically migrate to an unaffected server. In this working fashion, there is one LAP per server running a Health Checker that periodically diagnoses the ability of the machine to comply to its tasks. If one LAP reports that the machine has a problem, or fails to answer polling by other LAPs, the corresponding server is blacklisted until it comes up again and all the TriDAS and CU services hosted there are migrated elsewhere or run in downgraded mode (e.g. the number of Optical Data Filters is reduced). A complete reconfiguration takes 5-10 s and requires no action from human operators.

Conclusions

This work presents the last version of the main acquisition boards of KM3NeT, the Central Logic Board together with its Power Board, which improve its reliability as well as its functionality. Improvements in reliability and fault-tolerance have been made for the enhanced version of the Control Unit.

Figure 1 .

 1 Figure 1. Prototype of CLBv4 with its main elements that have been improved with respect to the previous version.

Figure 2 .

 2 Figure 2. Clock generator scheme for the WR system of the CLBv4.

Figure 3 .

 3 Figure 3. Tests performed on the CLBv4. The skew of the PPS signal has been measured after the restart of the board. As it can be seen the restart of the board almost does not add skew.

Figure 4 .

 4 Figure 4. Functional overview of the Control Unit and its relationships with physical objects and software components. Only the flow of control information is shown.

  user

Figure 5 .

 5 Figure 5. Screenshot of the DM graphical user interface with the monitor a single DOM superimposed to the overall monitor of five DUs.

Figure 6 .

 6 Figure 6. The FSM (boxes) that defines the states of each component of the data acquisition system and the operational targets (circles) of the Control Unit.

Figure 7 .

 7 Figure7. MCP jobs on three priority levels. The run number changes every time there is a switch from a job to another. A baseline job stands as a fallback to define the detector state in case nothing else is scheduled. Normal duty data-taking is performed by jobs of equal duration at the priority level above the baseline. Special tasks happen at a higher priority level.

Table 1 .

 1 DOM Voltages, currents and efficiency of the PB broken down by power rail. The efficiencies of the previous version of PB are given as well for comparison.

	Volt (V)	Current(A)	Efficiency PB v2.3 (%)	Efficiency PB v3.0 (%)
	1	0.13	80	80
	1.8	0.33	80	80
	2.5	0.33	60	78
	3.3	0.81	65	90
	3.3 PMTs	0.46	90	90
	5	0.10	60	90

Acknowledgments

The authors acknowledge the financial support of the funding agencies: Agence Nationale de la Recherche (contract ANR-15-CE31-0020), Centre National de la Recherche Scientifique (CNRS), Commission Européenne (FEDER fund and Marie Curie Program), Institut Universitaire de France (IUF), IdEx program and UnivEarthS Labex program at Sorbonne Paris Cité (ANR-10-LABX-0023 and ANR-11-IDEX-0005-02), Paris Île-de-France Region, France; Shota Rustaveli National Science Foundation of Georgia (SRNSFG, FR-18-1268), Georgia; Deutsche Forschungsgemeinschaft (DFG), Germany; The General Secretariat of Research and Technology (GSRT), Greece; Istituto Nazionale di Fisica Nucleare (INFN), Ministero dell'Istruzione, dell'Università e della Ricerca (MIUR), PRIN 2017 program (Grant NAT-NET 2017W4HA7S) Italy; Ministry of Higher Education, Scientific Research and Professional Training, Morocco; Nederlandse organisatie voor Wetenschappelijk Onderzoek (NWO), the Netherlands; The National Science Centre, Poland (2015/18/E/ST2/00758); National Authority for Scientific Research (ANCS), Romania; Plan Estatal de Investigación (refs. FPA2015-65150-C3-1-P, -2-P and -3-P, (MINECO/FEDER)), Severo Ochoa Centre of Excellence program (MINECO), Red Consolider MultiDark, (ref. FPA2017-90566-REDC, MINECO) and Prometeo and Grisolía programs (Generalitat Valenciana), "la Caixa" Foundation (ID 100010434) through the fellowship LCF/BQ/IN17/11620019, and the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement no. 713673, Spain.