A new approach for scheduling of multipurpose batch processes with unlimited intermediate storage policy

Abstract

The increasing demand of goods, the high competitiveness in the global marketplace as well as the need to minimize the ecological footprint lead multipurpose batch process industries to seek ways to maximize their productivity with a simultaneous reduction of raw materials and utility consumption and efficient use of processing units. Optimal scheduling of their processes can lead facilities towards this direction. Although a great number of mathematical models have been developed for such scheduling, they may still lead to large model sizes and computational time. In this work, we develop two novel mathematical models using the unit-specific event-based modelling approach in which consumption and production tasks related to the same states are allowed to take place at the same event points. The computational results demonstrate that both proposed mathematical models reduce the number of event points required. The proposed unit-specific event-based model is the most efficient since it both requires a smaller number of event points and significantly less computational time in most cases especially for those examples which are computationally expensive from existing models.

Graphical abstract

Keywords

scheduling / multipurpose batch processes / simultaneous transfer / mixed-integer linear programming

1 Introduction

Nowadays, it is more important than ever for multipurpose batch process industry to maximize their productivity by simultaneously minimize their costs, fuel and raw material consumption and ecological footprint to be able to survive in a highly competitive market. Developing optimal schedules is one of the main tools that multipurpose batch process industry can utilize to optimize their processes. Although heuristics-based and spreadsheet-based methods are often used to generate schedules, they are restricted to simple batch processes and often produce suboptimal schedules. Mathematical programming especially mixed-integer programming approaches have been received much attention in the past three decades because they can be used for more complicated batch processes and often provide optimal schedules. Before developing mathematical models, it is crucial to well represent the multipurpose batch process. Two representations have been proposed including state-task network and resource-task network representations. The state-task network representation (STN) is proposed by Kondili et al. [1] in which all materials in the process are represented by states and processing operations in units are treated as tasks. While states are represented with circles (state nodes), tasks are depicted with rectangles (task nodes). The connections between states and task nodes are depicted with arrows. No resources such as processing units, storage tanks, utilities and manpower are demonstrated in the STN representation. Therefore, the resource-task network representation (RTN) is proposed by Pantelides [2] in which resources used by tasks are explicitly included. Based on the STN and RTN representations, several modelling approaches have been proposed for optimal scheduling of multipurpose batch processes resulting in a great number of mathematical models in the last three decades [3‒7]. These modelling approaches include discrete-time [1,8,9], and continuous-time modelling approaches. The continuous-time modelling approaches include slot-based [10‒12], global event-based [13‒15], unit-specific event-based [16‒19] and sequence-based modelling approaches [20‒22]. The slot-based modelling approaches can be further classified into process-slot [11,12] and unit-slot [12,23] modelling approaches.

In the discrete-time modelling approach, the scheduling horizon is divided into time intervals of uniform or nonuniform lengths, where the start and end times of each interval are known and batches, tasks, or activities are assigned to intervals. Mathematical models developed using this modelling approach are often simple and they usually lead to tight mixed-integer linear programming (MILP) relaxation. A batch, task or activity should start or end exactly at the time interval points. The model sizes largely depend on the number of time intervals required. A great number of time intervals are often required to generate exact solutions, leading to computationally intractable model sizes even for small-scale problems since the length of each time interval is equal to the greatest common factor of the processing times of all units. To avoid an intractable number of time intervals required, continuous-time modelling approaches have been proposed in which the scheduling horizon is divided into ordered slots or event points with non-uniform unknown lengths. Batches, tasks, or activities are assigned to slots or event points. A batch, task or activity should start or end exactly at the slot points or event points. The model sizes also largely depend on the number of slots or event points required. The continuous-time modelling approaches require a significantly smaller number of time slots or event points. However, they often lead to worse MILP relaxation than the discrete-time modelling approach mainly due to the fact that they have to introduce a number of big-M terms in sequencing constraints. In the process slot-based and global event-based continuous-time modelling approaches, time slots or event points are common or shared for all processing units in the process. In other words, batches, tasks or activities in all processing units must start or end at the same slots or event points. In the unit-specific event-based and unit-slot modelling approaches, each unit has independent or separate time slots or event points. The same time slots or event points for different units can start or end at different times. Therefore, the unit-specific event-based or unit-slot modelling approaches often require a smaller number of slots or event points compared to the process slot-based and global event-based modelling approaches, leading to smaller model size and less computational time in general. While the unit-specific event-based modelling approach divides the scheduling horizon using event points where the next event point is not necessarily immediately start after its previous event point end, the unit-slot modelling approach divides the scheduling horizon based on slots where the next slot must immediately start after its previous slots end. In general, the unit-slot modelling approach is very similar to the unit-specific event-based modelling approach. Finally, the sequence-based modelling approach employs direct (immediate) or indirect (general) sequencing (precedence) of task-pairs on units to define a schedule. Time is not explicitly modelled in terms of slots or event points. Although it is not necessary for the sequence-based modelling approach to postulate the numbers of slots or event points a priori, they must postulate the number of batches, tasks or activities a priori. In addition, they do suffer from the difficulty in monitoring resource levels.

The capabilities of the unit-specific event-based modelling approach have been well established in the literature [17,24,25] with fewer number of event points and smaller model size, which often lead to smaller computational expenses. In most mathematical models developed using the unit-specific event-based modelling approach, the timing variables are defined based on tasks, not on units. In other words, the independent or separate event points are used for tasks, not for units. Therefore, we call them as task-specific event-based models in this work. Most of these task-specific event-based models still require a high number of event points to generate optimal schedules, leading to large model sizes and computational time. This is because most of these models do not allow consumption and production tasks related to the same states to take place at the same event points, unnecessarily increasing the number of event points required. Recently, Shaik and Vooradi [26] proposed a task-specific event-based model for scheduling of multipurpose batch processes, allowing production and consumption tasks related to the same states to take place at the same event points. However, their model is only applicable to the batch process without any recycling loop.

In this work, we develop two novel mathematical models using the unit-specific event-based modelling approach in which related consumption and production tasks are allowed to take place at the same event points. While we define timing variables based on units in one model (called unit-specific event-based model), the timing variables are defined based on tasks in the other model, (called task-specific event-based model). Both formulations are developed based on the STN representation. To make our models applicable for any batch processes, we introduce a definition of recycling tasks slightly different than the definition of recycling tasks of Li et al. [5]. We only allow non-recycling production and consumption tasks to take place at the same event points to avoid suboptimality. The computational results demonstrate that both proposed mathematical models are very general and can be applied for all batch processes even those with recycling loop and reduce the number of event points required. The proposed unit-specific event-based model is the most efficient since it both requires a smaller number of event points and significantly less computational time in most cases especially for those examples which are computationally expensive from existing models.

2 Problem description

A general multipurpose batch process facility including J (j= 1, 2,…, J) processing units such as reactors, separators and heaters. The STN representation of a multipurpose batch process facility is presented in Fig. 1. These units are used to produce P (p= 1, 2,…, P) final products using F (f= 1, 2,…, F) feeds. I (i= 1, 2,…, I) tasks will be processed in the processing units. Each processing unit can process I_j tasks. At each time, at most one task can be processed in a processing unit. Besides final products, intermediate states are also produced. There are total S (s= 1, 2,…, S) states including feeds, intermediate states, and final products. The feeds are denoted as S^R, the intermediate states are denoted as S^IN, and the final products are included in the set of S^FP. The proportion of each state s produced or consumed by a task i in a unit j is denoted by ${\rho }_{i,j,s}$. While positive values of ${\rho }_{i,j,s}$ denote production of state s during the processing of task i in unit j, negative values of ${\rho }_{i,j,s}$ denote consumption of state s during the processing of task i in unit j. After production, each batch is allowed to be mixed with other batches or split into several batches for further processing. Some intermediate states are also allowed to be recycled back if necessary. Each intermediate state has its dedicated storage. If the storage capacity for an intermediate state is unlimited, then it is called unlimited intermediate storage (UIS) policy. If the storage capacity is limited or finite, then it is called finite intermediate storage (FIS) policy. If there is no intermediate storage, then it is called no intermediate storage (NIS) policy. In this paper, we assume UIS for all states including intermediate states, feeds and final products. After production in a processing unit, an intermediate state may or may not be allowed to remain in this processing unit. If an intermediate state has to be transferred immediately to storage or other processing units after production, it is called zero wait (ZW) policy. If an intermediate state is allowed to remain in a processing unit with unlimited time, then it is called unlimited wait (UW) policy. If an intermediate state is allowed to be held in a processing unit with a certain time, then it is called limited wait (LW) policy. In this paper, we also assume UW policy for all intermediate states. By introducing this, the scheduling problem can be stated as follows, Given: (1) STN representation of a multipurpose batch facility; (2) J units, unit capacities, suitable tasks and their processing times; (3) S states, the portion of states produced or consumed from a task in a processing unit; (4) Product prices; (5) Scheduling horizon. Determine: (1) Optimal production schedule involving task allocations, start and end timings, sequences and batch sizes; (2) Inventory profiles. Operating rules: (1) At most one task can be processed in a processing unit at any time; (2) Batch mixing and splitting is allowed. Assumptions: (1) All parameters are deterministic; (2) The processing time of a task in a processing unit depends on a fixed processing time (denoted as ${\alpha }_{ij}$ plus a variable process time based on the batch sizes, which is denoted as (${\beta }_{ij}\cdot b_{ij}$); (3) Unlimited feed materials are available; (4) Unlimited storage policy for all states; (5) Unlimited resources where required are available; (6) Unlimited wait policy for intermediate states.

The objective is to maximize productivity or minimize makespan. The makespan is defined as the time required to produce a specified demand.

Fig.1 STN representation of a multipurpose batch process facility (Example 2).

Full size|PPT slide

3 Motivating example

Let consider an example whose STN representation is depicted in Fig. 2. In this example, a raw material S1 is converted into a final product S3 through two tasks (i.e., I1 and I2) in two processing units (J1 and J2). The scheduling horizon is 9 h. The objective is to maximize the productivity of product S3. All relevant data for this example are given in Table 1. We use the mathematical model of Shaik and Floudas [25] to solve this example. We obtain the optimal solution of 500.00 cu using 2 events. The optimal schedule is illustrated in Fig. 3. As seen from Fig. 3, the task I1, processed in unit J1, produces 100.00 cu of S2 at event point N1, which is further processed at task I2 in unit J2 to produce final product S3 with 100.00 cu at event point N2. This is because the task I2 in unit J2 is a consuming task of S2 and the task I1 in unit J1 is a production task for S2. Therefore, the task I2 must always start at event point N2 since the production task I1 take place at event point N1 based on the model of Shaik and Floudas [25]. However, we can use one event point for the optimal schedule through analysis. Figure 4 illustrates the optimal schedule with only one event point. From Fig. 4, it can be observed that the consuming task I2 takes place at the same event point as the production task I1, but not in real time. In real time, task I2 still takes place after I1 is completed. By doing this, we can reduce one event point required for generating the optimal solution. As discussed previously, the model size and computational performance largely depend on the number of event points required. This motivates us to develop new mathematical formulations for scheduling of multipurpose batch facilities by allowing consuming and production tasks related to the same states take place at the same event points to reduce the number of event points required.

Fig.2 STN representation of the motivating example.

Full size|PPT slide

Tab.1 Data for motivating example

Unit	Maximum capacity /mu	Minimum capacity /mu	${\alpha }_i$/h	${\beta }_i$/h
J1	100	0	3	0.02
J2	100	0	2	0.01

Fig.3 Optimal schedule for the motivating example using two event points from the model of Shaik and Floudas [25].

Full size|PPT slide

Fig.4 Optimal schedule for the motivating example using one event point.

Full size|PPT slide

4 Definition of recycling tasks

Despite the fact that allowing all related production and consumption tasks take place at the same event points can potentially reduce the number of event points and increase computational efficiency, we could obtain suboptimal solutions in some cases by allowing all production and consumption tasks related to the same states to take place at the same event points. Consider the following example which is depicted in Fig. 5 and Table 2. If production and consumption tasks related to the same states are not allowed to take place at the same event points, the optimal productivity of 1656 cu is generated with four event points from the model of Shaik and Floudas [25]. However, if all production and consumption tasks related to the same states are allowed to take place at the same event points, then the suboptimum productivity of 1511 cu is generated. This occurs from tasks I3, I4 and I5. Note that tasks I4 and I5 produce two states S2 and S4 and task I3 consumes state S2 and produces state S3. If these tasks (i.e., tasks I3, I4, and I5) are allowed to take place at the same event points, it is not possible for these tasks to take place at the same time in real time, which leads to suboptimum solutions.

Fig.5 STN representation of motivating example 2.

Full size|PPT slide

Tab.2 Results for motivating example 2a)

Example	Model	Event points	CPU time /s	RMILP /cu	MILP /cu	Discrete variables	Continuous variables	Equations
1	SF	4	0.094	1800.00	1656.16	20	78	115
(H= 8 h)	T-S	4	0.156	3300.83	1511.66	20	78	121

a) SF: the model of Shaik and Floudas [25]; T-S: the revised model of Shaik and Floudas [25] allowing all production and consumption tasks related to the same states take place at the same event points; CPU: Central processing unit; RMILP: relaxed mixed-integer linear program.

To avoid suboptimality in such cases, a new definition slightly different from that of recycling tasks of Li et al. [5] is introduced. We define a recycling task in a processing unit if it produces a state that can be consumed either by a task in its upstream processing units or by other tasks in the same processing unit. The recycling tasks are included in the set I^R. In Fig. 6, there are four tasks (I1‒I4), two processing units (J1‒J2) and three states (S1‒S3). While tasks I1 and I3 can be processed in unit J1, tasks I2 and I4 can be processed in unit J2. Tasks I1 and I2 consume S1 and produce S2, whilst tasks I3 and I4 consume S2 and produce S1 and S3. Based on this new definition, task I1 is considered as a recycling task because it produces S2 that can be used by task I3 as a raw material in the same unit (i.e., J1). Similarly, tasks I2‒I4 are also recycling tasks. Consequently, all tasks in the example depicted in Fig. 6 are considered as recycling tasks.

Fig.6 Illustration of recycling tasks where all tasks are recycling tasks.

Full size|PPT slide

5 Mathematical formulation

5.1 Time representation

As discussed before, the advantages of the unit-specific event-based modelling approach have been well established in the literature. This modelling approach is used to develop our new models, which are presented below.

5.2 Model M1

In this model, the timing variables are defined based on units. Therefore, this proposed model is called the unit-specific event-based model.

5.2.1 Allocation constraints

To assign tasks to units, we define binary variables $w_{i,j,n,n^{\prime }}$ to denote if a task i is processed in a unit j from event point n to event point n′. We allow a task in a unit to span over Dn event points to make the model general where Dn is a parameter that could be used to control the number of event points that a task can span across. At most one task is allowed to take place in a unit during a time as specified by Constraint (1). If tasks are allowed to span over more than one events (Dn>0), Constraint (1) allows at most one task to be active from event point n to event point n′.

(1)${\displaystyle \sum _{i\in I_j}}{\displaystyle \sum _{n-\Delta n\le n^{\prime }\le n}}{\displaystyle \sum _{n\le n^{″}\le n^{\prime }+\Delta n}}{w}_{i,j,n^{\prime },n^{″}}\le \mathrm{1}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j,n.$

5.2.2 Capacity constraints

We define variables $b_{i,j,n,n^{\prime }}$ to denote the amount of materials (i.e., batch size) processed by a task i in a unit j from event point n to event point n′. If a unit j processes a task i from event point n to event point n′, then the material processed in this unit should be constrained by the minimum ($B_{i,j}^{\min }$) and maximum ($B_{i,j}^{\max }$) capacity limits.

(2)$B_{i,j}^{\min }{w}_{i,j,n,n^{\prime }}\le b_{i,j,n,n^{\prime }}\le B_{i,j}^{\max }{w}_{i,j,n,n^{\prime }}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j,i\in I_j,n\le n\prime \mathrm{}\le n+\mathrm{\Delta }n.$

5.2.3 Material balance

We define $S{T}_{s,n}$ to denote the amount of material s at event point n, which is used to monitor inventory of the materials in storage and ensure no storage capacity violation. Since we allow non-recycling tasks to take place at the same event points as the related consumption tasks, these non-recycling tasks produce materials at event point n. However, recycling tasks have to produce materials at event point (n‒1). With this, the amount of material in a storage at an event point n should be equal to the amount of materials at the previous event point (n-1) plus the material produced from non-recycling tasks at event point n and recycling tasks at event point (n-1) minus the material consumed by consumption tasks at event point n, as indicated in Constraints (3) and (4).

(3)$S{T}_{s,n}=ST{\mathrm{0}}_s+{\displaystyle \sum _j{\displaystyle \sum _{i\in (I_j\cap I_S^P),i\notin I^{\mathrm{R}}}{\rho }_{i,j,s}{\displaystyle \sum _{n-\Delta n\le n^{\prime }\le n}{b}_{i,j,n^{\prime },n}}}}+{\displaystyle \sum _j{\displaystyle \sum _{i\in (I_j\cap I_S^C)}{\rho }_{i,j,s}{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}{b}_{i,j,n,n^{\prime }}}}}\mathrm{\hspace{0.17em}}\forall s,n=\mathrm{}\mathrm{1},$

(4)$S{T}_{s,n}=S{T}_{s,n-\mathrm{1}}+{\displaystyle \sum _j{\displaystyle \sum _{i\in (I_j\cap I_S^P),i\notin I^{\mathrm{R}}}{\rho }_{i,j,s}{\displaystyle \sum _{n-\Delta n\le n^{\prime }\le n}{b}_{i,j,n^{\prime },n}}}}+{\displaystyle \sum _j{\displaystyle \sum _{i\in (I_j\cap I_S^P\cap I^R)}{\rho }_{i,j,s}{\displaystyle \sum _{n-\mathrm{1}-\Delta n\le n^{\prime }\le n-\mathrm{1}}{b}_{i,j,n^{\prime },n-\mathrm{1}}}}}+{\displaystyle \sum _j{\displaystyle \sum _{i\in (I_j\cap I_S^C)}{\rho }_{i,j,s}{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}{b}_{i,j,n,n^{\prime }}}}}\mathrm{\hspace{0.17em}}\forall s,n>\mathrm{}\mathrm{1.}$

5.2.4 Processing duration constraints

Once a batch is processed on a unit, then it must be processed for some duration. A unit is also allowed to be idle after processing. We define $T_{j,n}^{\mathrm{s}}$ and $T_{j,n}^{\mathrm{f}}$ to denote the start and end times of a processing unit j at event point n. The end time of a unit j at event n must be greater than the total processing time, consisting of a fixed term and a variable term depending on the batch size, as indicated in the Constraint (5).

(5)$T_{j,n}^{\mathrm{f}}\ge T_{j,n}^{\mathrm{s}}+{\displaystyle \sum _{i\in {{\rm I}}_j}{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}({\alpha }_{ij}\cdot w_{i,j,n,n^{\prime }}+{\beta }_{ij}\cdot b_{i,j,n,n^{\prime }})}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j,i\in I_j,n\le n\prime \mathrm{}\le n+\mathrm{\Delta }n.$

Note that we do not force the finish time to be equal to the start time plus the total processing time to allow materials produced temporally stored in unit or a unit to be idle after processing, which may lead to a smaller number of event points that is required to generate the optimum solution as claimed by Li and Floudas [17].

5.2.5 Sequencing constraints

Same or different tasks in the same unit: An event point n on a processing unit j must always start after its previous event point on the same unit finishes.

(6)$T_{j,n+\mathrm{1}}^{\mathrm{s}}\ge T_{j,n}^{\mathrm{f}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j,n<N.$

Different tasks in different units: We need to sequence consuming and production tasks related to the same states where the consuming and production tasks are different tasks in different units. Although a consuming task is allowed to take place at the same event points with its related production tasks which are non-recycling tasks, this consuming task must always start after its related production tasks finish in real time. We introduce a new continuous variable $T_{s,n}$, which denotes the time that state s is available to be consumed at event point n. Then we have:

(7)$T_{s,n}\le T_{s,n+\mathrm{1}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall s\in S^{\mathrm{IN}},n.$

The finish time of unit j, which is related with the production of state s should be before the time that state s is available.

(8)$T_{s,n}\ge T_{j,n}^{\mathrm{f}}-M\left(\mathrm{1}-{\displaystyle \sum _{i\in (I_j\cap I_S^P)}{\displaystyle \sum _{n-\mathrm{\Delta }n\le n^{\prime }\le n}{w}_{i,j,n^{\prime },n}}}\right)\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall s\in S^{\mathrm{IN}},j,{\displaystyle \sum _{i\in I_j}{\rho }_{s,i}}>\mathrm{0},n.$

The start time of unit j at event point n, which is related with the consumption of state s should be after the time that the state is available if it was produced by a non-recycling task i′.

(9)$T_{s,n}\le T_{j,n}^{\mathrm{s}}+M\cdot \left(\mathrm{1}-{\displaystyle \sum _{i\in (I_j\cap I_S^C)}{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}{w}_{i,j,n,n^{\prime }}}}\right)\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall s\in S^{\mathrm{IN}},j,{\displaystyle \sum _{j^{\prime }}{\displaystyle \sum _{i^{\prime }\in (I_{j^{\prime }}\cap I_S^P),i\notin I^R}{\rho }_{s,i^{\prime }}}}>\mathrm{0},n.$

If state s is produced by a recycling task i′, the end time of unit j at event point n+1, which is related with the consumption of state s should be after the time that the state is available instead.

(10)$T_{s,n}\le T_{j,n+\mathrm{1}}^{\mathrm{s}}+M\cdot \left(\mathrm{1}-{\displaystyle \sum _{i\in (I_j\cap I_S^C)}{\displaystyle \sum _{n+\mathrm{1}\le n^{\prime }\le n+\mathrm{1}+\Delta n}{w}_{i,j,n+\mathrm{1},n^{\prime }}}}\right)\mathrm{\hspace{0.17em}}\forall s\in S^{\mathrm{IN}},j,{\displaystyle \sum _{j^{\prime }}{\displaystyle \sum _{i^{\prime }\in (I_{j^{\prime }}\cap I_S^P\cap I^R)}{\rho }_{s,i^{\prime }}}>\mathrm{0}},n.$

5.2.6 Objectives

We consider two different objectives. In the first objective, the productivity of a given facility is maximized for a specified scheduling horizon.

(11)$z={\displaystyle \sum _s{p}_s{\displaystyle \sum _j{\displaystyle \sum _{i\in (I_j\cap I_S^P)}{\displaystyle \sum _n{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}{\rho }_{i,j,s}\cdot b_{i,j,n,n^{\prime }}}}}}}.$

The other objective is to minimize makespan (denoted as MS), which is considered as following,

(12)$MS\ge T_{j,n}^{\mathrm{f}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j,\mathrm{}n\mathrm{}=\mathrm{}N.$

In the minimization of makespan problem, it should be also ensured that the total demand is satisfied.

(13)$S{T}_{s,n}+{\displaystyle \sum _j{\displaystyle \sum _{i\in \left(I_S^P\cap I^R\right)}{\rho }_{i,j,s}{\displaystyle \sum _{n-\mathrm{\Delta }n\le n^{\prime }\le n}{b}_{i,j,n^{\prime },n}}}}\ge D_s\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall s\in S^p,n=N.$

We complete our model M1 which comprises of Eqs. (1‒11) if maximization of productivity is considered as objective and Eqs. (1‒10), (12), (13) if minimization of makespan is considered.

5.3 Model M2

In this model, the timing variables are defined based on tasks. The same tasks that can be processed in different units have to be divided into two different tasks. We call this model task-specific event-based model. Production and consumption tasks related to the same states are also allowed to take place at the same event points in this model.

5.3.1 Allocation constraints

Similar to the model M1, at most one task is allowed to take place at each event point.

(14)${\displaystyle \sum _{i\in I_j}{\displaystyle \sum _{n-\Delta n\le n^{\prime }\le n}{\displaystyle \sum _{n\le n^{″}\le n^{\prime }+\Delta n}{w}_{i,n^{\prime },n^{″}}}}}\le \mathrm{1}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j,n.$

5.3.2 Capacity constraints

The batch size of task i from event point n to event point n′ should be constrained by the maximum and minimum capacities if the task is active. Otherwise, it should be equal to zero. This Constraint (15) is the same as that of Shaik and Floudas [25].

(15)$B_i^{\min }{w}_{i,n,n^{\prime }}\le b_{i,n,n^{\prime }}\le B_i^{\max }{w}_{i,n,n^{\prime }}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j,i\in I_j,n\le n\prime \mathrm{}\le n+\mathrm{\Delta }n.$

5.3.3 Material balance constraints

Similar to the model M1, we allow materials that are produced by non-recycling tasks to be consumed by their related consumption tasks at the same event point. However, if the materials are produced by recycling tasks, then they have to be consumed by their related consumption tasks at the next event point.

(16)$S{T}_{s,n}=ST{\mathrm{0}}_s+{\displaystyle \sum _{i\in I_S^P,i\notin I^{\mathrm{R}}}{\rho }_{i,s}{\displaystyle \sum _{n-\Delta n\le n^{\prime }\le n}{b}_{i,n^{\prime },n}}}+{\displaystyle \sum _{i\in I_S^C}{\rho }_{i,s}{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}{b}_{i,n,n^{\prime }}}}\mathrm{\hspace{0.17em}}\forall s,n=\mathrm{}\mathrm{1},$

(17)$S{T}_{s,n}=S{T}_{s,n-\mathrm{1}}+{\displaystyle \sum _{i\in I_S^P,i\notin I^{\mathrm{R}}}{\rho }_{i,s}{\displaystyle \sum _{n-\Delta n\le n^{\prime }\le n}{b}_{i,n^{\prime },n}}}+{\displaystyle \sum _{i\in (I_S^P\cap I^R)}{\rho }_{i,s}{\displaystyle \sum _{n-\mathrm{1}-\Delta n\le n^{\prime }\le n-\mathrm{1}}{b}_{i,n^{\prime },n-\mathrm{1}}}}+{\displaystyle \sum _{i\in I_S^C}{\rho }_{i,s}{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}{b}_{i,n,n^{\prime }}}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall s,n>\mathrm{1.}$

5.3.4 Processing duration constraints

The finish time of a task i should always be greater than the start time of the same task. It should be also greater than the start time of the task plus the total processing time if the task is active.

(18)$T_{i,n^{\prime }}^{\mathrm{f}}\ge T_{i,n}^{\mathrm{s}}+a_i\cdot w_{i,n,n^{\prime }}+{\beta }_i\cdot b_{i,n,n^{\prime }}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall i\in I_j,n\le n\prime \mathrm{}\le n+\mathrm{\Delta }n.$

5.3.5 Sequencing constraints

Same tasks in the same units: A task i taking place at event point n+1 should always start after it finishes at event point n. This Constraint (19) is the same as those of Shaik and Floudas [25].

(19)$T_{i,n+\mathrm{1}}^{\mathrm{s}}\ge T_{i,n}^{\mathrm{f}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall i\in I_j,n.$

Different tasks in the same units: A task i taking place at event point n+1 should always start after all other tasks that can be processed in the same unit finish at event point n.

(20)$T_{i,n+\mathrm{1}}^{\mathrm{s}}\ge T_{i^{\prime },n}^{\mathrm{f}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j,i\in I_j,i\prime \in I_j,ii\prime ,n<N.$

Different tasks in different units: Similar to the model M1, two different sets of constraints are introduced based on whether the production task is a recycling or a non-recycling task.

(21)$T_{i,n}^{\mathrm{s}}\ge T_{i^{\prime },n}^{\mathrm{f}}-M\left(\mathrm{1}-{\displaystyle \sum _{n-\Delta n\le n^{\prime }\le n}{w}_{i^{\prime },n^{\prime },n}}\right)\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j\ne j^{\prime },\mathrm{\hspace{0.17em}}i\in (I_S^C\cap I_j),\mathrm{}\mathrm{\hspace{0.17em}}{i}^{\prime }\in (I_S^P\cap I_{j^{\prime }}),\mathrm{\hspace{0.17em}}{i}^{\prime }\notin I^R,n,$

(22)$T_{i,n+\mathrm{1}}^{\mathrm{s}}\ge T_{i^{\prime },n}^{\mathrm{f}}-M\left(\mathrm{1}-{\displaystyle \sum _{n-\Delta n\le n^{\prime }\le n}{w}_{i^{\prime },n^{\prime },n}}\right)\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j\ne j^{\prime },\mathrm{\hspace{0.17em}}i\in (I_S^C\cap I_j),\mathrm{}\mathrm{\hspace{0.17em}}{i}^{\prime }\in (I_S^P\cap I_{j^{\prime }}\cap I^R),\mathrm{\hspace{0.17em}}n<N.$

5.3.6 Tightening constraint

The duration of all tasks performed in a unit j must not exceed the scheduling horizon.

(23)${\displaystyle \sum _{i\in I_j}{\displaystyle \sum _n{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}({\alpha }_i\cdot w_{i,n,n^{\prime }}+{\beta }_i\cdot b_{i,n,n^{\prime }})}}}\le H\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall j.$

5.3.7 Objectives

Similar to the model M1, two objectives were also considered in this model M2. In the first objective, the productivity of a given facility is maximized for a specified scheduling horizon.

(24)$z={\displaystyle \sum _s{p}_s{\displaystyle \sum _{i\in I_S^P}{\displaystyle \sum _n{\displaystyle \sum _{n\le n^{\prime }\le n+\Delta n}{\rho }_{i,s}{b}_{i,n,n^{\prime }}}}}}.$

The second objective is to minimize makespan.

(25)$MS\ge T_{i,n}^{\mathrm{f}}\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall i,\mathrm{}n=N.$

Finally, in the case of minimization of makespan, the total demand should be satisfied.

(26)$S{T}_{s,n}+{\displaystyle \sum _{i\in \left(I_S^P\cap I^R\right)}{\rho }_{i,s}{\displaystyle \sum _{n-\mathrm{\Delta }n\le n^{\prime }\le n}{b}_{i,n^{\prime },n}}}\ge D_s\mathrm{\hspace{0.17em}}\mathrm{\hspace{0.17em}}\forall s\in S^p,n=\mathrm{}N.$

We complete our model M2 which comprises Eqs. (14‒24) if the maximization of productivity is considered as objective and Eqs. (14‒23), (25), (26) if the minimization of makespan is considered as objective.

6 Computational studies

We solve twelve examples to illustrate the capability of the proposed models M1 and M2. The data for all examples are given in Tables 3‒14. The STN representation of these examples are illustrated in Figs. 1 and 7‒16. Note that the STN representation of Example 2 is illustrated in Fig. 1. Among these twelve examples, Examples 1‒3 and 8‒12 are well-established examples from the literature [1,17,25]. These twelve examples have varying tasks, units, recipe structures, processing times, and scheduling horizons. All examples are solved to zero optimality gap using CPLEX 12/GAMS 24.6.1. on a desktop computer with Intel® Core™ i5-2500 3.3 GHz and 8 GB RAM running Windows 7. The maximum computational time is set as one hour for all examples.

Fig.7 STN representation of Example 1.

Full size|PPT slide

Tab.3 Data for Example 1

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	1.333	0.01333	0	100
2	2	1.333	0.01333	0	150
3	3	1.000	0.00500	0	200
4	4	0.667	0.00445	0	150
5	5	0.667	0.00445	0	150

Tab.4 Data for Example 2

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	0.667	0.00667	0	100
2	2	1.334	0.02664	0	50
3	3	1.334	0.01665	0	80
4	2	1.334	0.02664	0	50
5	3	1.334	0.01665	0	80
6	2	0.667	0.01332	0	50
7	3	0.667	0.008325	0	80
8	4	1.334	0.00666	0	200

Fig.8 STN representation of Example 3.

Full size|PPT slide

Tab.5 Data for Example 3

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	0.667	0.00667	0	100
2	1	1.000	0.01000	0	100
3	2	1.333	0.01333	0	100
4	3	1.333	0.00889	0	150
5	2	0.667	0.00667	0	100
6	3	0.667	0.00445	0	150
7	2	1.333	0.01330	0	100
8	3	1.333	0.00889	0	150
9	4	2.000	0.00667	0	300
10	5	1.333	0.00667	20	200
11	6	1.333	0.00667	20	200

Fig.9 STN representation of Example 4.

Full size|PPT slide

Tab.6 Data for Example 4

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	1.333	0.01333	0	100
2	2	1.333	0.01333	0	150
3	3	1.000	0.00500	0	200
4	4	0.667	0.00445	0	150
5	5	0.667	0.00445	0	150
6	6	1.000	0.00500	0	200

Fig.10 STN representation of Example 5.

Full size|PPT slide

Tab.7 Data for Example 5

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	1.333	0.01333	0	100
2	2	1.333	0.01333	0	150
3	3	1.000	0.00500	0	200
4	4	0.667	0.00445	0	150
5	5	0.667	0.00445	0	150
6	6	1.000	0.00500	0	200
7	7	1.333	0.01333	0	100
8	8	1.333	0.01333	0	150

Fig.11 STN representation of Example 6.

Full size|PPT slide

Tab.8 Data for Example 6

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1‒3	1	1.333	0.01333	0	100
4‒6	2	1.333	0.01333	0	150
7‒9	3	1.000	0.00500	0	200
10‒12	4	0.667	0.00445	0	150
13‒15	5	0.667	0.00445	0	150
16‒18	6	1.000	0.00500	0	200
19‒21	7	1.333	0.01333	0	100
22‒24	8	1.333	0.01333	0	150

Fig.12 STN representation of Example 7.

Full size|PPT slide

Tab.9 Data for Example 7

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	6.000	0	0	200
2	2	5.000	0	0	100
3	3	9.000	0	0	100
4	4	2.000	0	0	50
5	5	3.000	0	0	50
6	6	4.000	0	0	50
7	7	2.000	0	0	100

Fig.13 STN representation of Example 8.

Full size|PPT slide

Tab.10 Data for Example 8

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	1.000	0	0	10
2	2	3.000	0	0	4
3	3	1.000	0	0	2
4	4	2.000	0	0	10

Fig.14 STN representation of Example 9.

Full size|PPT slide

Tab.11 Data for Example 9

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	1.500	0	0	150
2	2	4.500	0	0	60
3	3	1.500	0	0	30
4	4	1.500	0	0	30
5	5	3.000	0	0	150

Fig.15 STN representation of Example 10.

Full size|PPT slide

Tab.12 Data for Example 10

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	17.333	0.866	0	20
2	2	2.667	0.133	0	20
3	3	2.667	0.133	0	20
4	4	4.000	0.200	0	20
5	5	5.333	0.266	0	20
6	6	5.333	0.266	0	20

Fig.16 STN representation of Examples 11 and 12.

Full size|PPT slide

Tab.13 Data for Example 11

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	1.666	0.03335	0	40
2	2	2.333	0.08335	0	20
3	3	0.667	0.06600	0	5
4	4	2.667	0.008325	0	40

Tab.14 Data for Example 12

Task	Processing unit	${\alpha }_i$	${\beta }_i$	$B_i^{\min }$	$B_i^{\max }$
1	1	1.666	0.03335	0	40
2	2	2.333	0.08335	0	20
3	3	0.333	0.06800	0	2.5
4	4	2.667	0.008325	0	40

The computational results from M1 and M2 are presented in Tables 15‒20. While Tables 15‒19 present the results from M1 and M2 with maximization of productivity as the objective, Table 20 presents the results from both models with minimization of makespan as the objective. From Tables 15‒20, it can be observed that both M1 and M2 models are able to generate optimum solutions using less number of event points, which leads to smaller model sizes and less computational time. For instance, both M1 and M2 models require two event points less than the model of Shaik and Floudas [25] to generate the optimal solutions in all instances in Example 1 (see Table 15). More specifically, in Example 1d, the model of Shaik and Floudas [25] requires 9 event points, whereas both models M1 and M2 require 7 event points, resulting in a reduction in binary variables by 20% (45 vs. 35). The optimal schedule for Example 1d using the model M1 is illustrated in Fig. 17. From Fig. 17, it can be observed that the related production and consumption tasks take place at the same event points because all production tasks in this example are treated as non-recycling tasks. For instance, task I1 processed in unit J1 is a non-recycling task, which takes place at event point N1. Its related consumption task is task I3 processed in unit J3 since this task I3 consumes state S2 produced from task I1, which also takes place at the same event point N1.

Tab.15 Computational results for Example 1 using maximization of productivity as objectivea)

Example	Model	Event points	CPU time /s	RMILP /cu	MILP /cu	Discrete variables	Continuous variables	Constraints
1a	SF	4	0.078	2000.00	1840.18	20	78	109
(H= 8 h)	M2	2	0.125	2000.00	1840.18	10	40	57
	M1	2	0.062	2000.00	1840.18	10	47	58
1b	SF	5	0.094	3000.00	2628.19	25	97	137
(H= 10 h)	M2	3	0.109	3000.00	2628.19	15	59	85
	M1	3	0.047	3000.00	2628.19	15	68	90
1c	SF	6	0.109	4000.00	3463.62	30	116	165
(H= 12 h)	M2	4	0.124	4000.00	3463.62	20	78	113
	M1	4	0.078	4000.00	3463.62	20	89	122
1d	SF	9	1.29	6601.65	5038.05	45	173	249
(H= 16 h)	M2	7	1.54	6601.65	5038.05	35	135	197
	M1	7	1.37	6601.65	5038.05	35	152	218

a) Dn = 0 for all cases

Similarly, from Table 18, both mathematical models require 7 event points to generate the optimal solution for Example 4, while the model of Shaik and Floudas [25] requires 10 event points. This leads to 30% reduction in the number of binary variables (60 vs. 42) using the proposed mathematical models. From the optimal schedule for Example 4 using the model M1, which is depicted in Fig. 18, it can be again confirmed that the reduction in the total event points required is due to the fact that all related production and consumption tasks are allowed to take place at the same event points. More specifically, from Fig. 18, it seems that task I4 processed in unit J4, which is a non-recycling, task takes place at event point N3, while its related consumption task is task I6 processed in unit J6 which also takes place at the same event point N3. Briefly, it can be concluded that the proposed models M1 and M2 can be applied to any batch processes even those with recycling loops such as the batch processes in Fig. 1 and Fig. 8.

From Tables 16‒17, we can observe that the proposed formulations M1 and M2 require the same number of event points with the model of Shaik and Floudas [25] for Examples 2‒3. For these examples, M1 and M2 do not reduce the computational time too much because of the same number of event points required. It should be noted though that when tasks have to span over multiple event points, then model M1 can significantly reduce the computational time. This main reason may come from the Constraint (5) which is tighter than those in Shaik and Floudas [25] when a task has to span over multiple event points. For instance, M1 requires 49% less computational time than the model of Shaik and Floudas [25] (5.41 s vs. 2.78 s) to solve Example 2b and 72% less computational time (3159 s vs. 892 s) for Example 3b. On the other hand, even though M2 require slightly less computational time than the model of Shaik and Floudas [25] for both Example 2b (5.41 s vs. 5.10 s) and 3b (3159 s vs. 3141 s), it requires 46% more computational time than the model M1 (2.78 s vs. 5.10 s) to solve Example 2b and 72% more computational time (892 s vs. 3141 s) to solve Example 3b. Therefore, it can be concluded that the proposed model M1 is the most efficient.

Tab.16 Computational results for Example 2 using maximization of productivity as objective

Example	Model	Event points	CPU time /s	RMILP /cu	MILP /cu	Discrete variables	Continuous variables	Constraints
2a	SF	4 (Dn = 0)	0.078	1730.87	1498.57	32	136	211
(H= 8 h)	M2	4 (Dn = 0)	0.141	1730.87	1498.57	32	136	213
	M1	4 (Dn = 0)	0.062	1730.87	1498.57	32	126	180
2b	SF	6 (Dn = 0)	0.889	2730.66	1943.17	48	202	331
(H= 10 h)	M2	6 (Dn = 0)	0.889	2730.66	1943.17	48	202	331
	M1	6 (Dn = 0)	0.827	2730.66	1943.17	48	184	276
	SF	6 (Dn = 1)	5.41	2730.66	1962.69	88	242	737
	M2	6 (Dn = 1)	5.10	2730.66	1962.69	88	242	739
	M1	6 (Dn = 1)	2.78	2730.66	1962.69	88	224	316
2c	SF	7 (Dn= 0)	2.39	3301.03	2658.52	56	235	388
(H= 12 h)	M2	7 (Dn = 0)	2.78	3301.03	2658.52	56	235	390
	M1	7 (Dn = 0)	2.86	3301.03	2658.52	56	213	324
2d	SF	8 (Dn = 0)	5.97	4291.68	3738.38	64	268	447
(H= 16 h)	M2	8 (Dn = 0)	6.30	4291.68	3738.38	64	268	449
	M1	8 (Dn = 0)	3.94	4291.68	3738.38	64	242	372

However, even though the proposed models, especially model M1, are more efficient for most of the examples, it seems that in some special cases they require a bit larger CPU time. For instance, in Example 4 depicted in Table 18 the model of Shaik and Floudas [25] is able to generate the optimum solution in 24.18 s, while models M1 and M2 require 35.88 s and 27.63 s respectively. Nevertheless, the difference is not large, which is in the same magnitude. The main possible reason is that the proposed models M1 and M2 require more CPU time to prove optimality for this example due to different nodes investigated using the branch and bound algorithm. It should also be noted that in Tables 15‒20 only the computational time required to generate the optimal solution using the optimum number of event points and Dn is reported. In practice, an iterative procedure is often used to find the optimal number of event points, Dn and the optimal solution. In this iterative procedure, the problem is solved starting from the minimum number of event points. The number of event points is increased by one until there is no change in the obtained solution. In the iterative procedure, it should be also examined whether allowing one a task to span for more than one event point can lead to the optimal solution. We use the iterative procedure to solve Example 4 with the model of Shaik and Floudas [25] and the proposed model M1. The computational results are given in Table 21. From Table 21 it seems that the model M1 requires less total computational time to locate the optimal solution using the iterative procedure. More specifically for model M1 1281 s are required to prove that the optimal solution is generated by using 7 event points while for Shaik and Floudas [25] significantly more time (2771 s) is required to prove that the optimal solution is generated by using 10 event points.

Tab.17 Computational results for Example 3 using maximization of productivity as objective

Example	Model	Event points	CPU time /s	RMILP /cu	MILP /cu	Discrete variables	Continuous variables	Constraints
3a	SF	5 (Dn = 0)	0.218	2100.00	1583.44	55	235	390
(H= 8 h)	M2	5 (Dn = 0)	0.343	2100.00	1583.44	55	235	390
	M1	5 (Dn = 0)	0.358	2100.00	1583.44	55	229	346
3b	SF	7 (Dn = 0)	6.24	3369.69	2305.55	77	327	560
(H= 10 h)	M2	7 (Dn = 0)	6.42	3369.69	2305.55	77	327	560
	M1	7 (Dn = 0)	10.23	3369.69	2293.46	77	315	494
	SF	8 (Dn = 1)	3159	3618.64	2358.20	165	450	1433
	M2	8 (Dn = 1)	3141	3618.64	2358.20	165	450	1433
	M1	8 (Dn = 1)	892	3618.64	2358.20	165	435	659
3c	SF	7 (Dn = 0)	0.437	3465.63	3041.27	77	327	560
(H= 12 h)	M2	7 (Dn = 0)	0.406	3465.63	3041.27	77	327	560
	M1	7 (Dn = 0)	0.483	3465.63	3041.27	77	315	494
3d	SF	10 (Dn = 0)	7.80	5225.86	4262.80	110	465	815
(H= 16 h)	M2	10 (Dn = 0)	6.99	5225.86	4262.80	110	465	715
	M1	10 (Dn = 0)	8.81	5225.86	4262.80	110	444	716

Tab.18 Computational results for Examples 4‒7 using maximization of productivity as objectivea)

Example	Model	Event points	CPU time /s	RMILP /cu	MILP /cu	Discrete variables	Continuous variables	Constraints
4	SF	10	24.18	6601.65	4305.46	60	232	345
(H= 16 h)	M2	7	27.63	6601.65	4305.46	42	163	246
	M1	7	35.88	6601.65	4305.46	42	188	279
5a	SF	8	0.141	1500.00	1414.18	64	250	369
(H= 16 h)	M2	3	0.156	1500.00	1414.18	24	95	142
	M1	3	0.156	1500.00	1414.18	24	116	159
5b	SF	14	0.343	4500.00	4414.80	112	436	651
(H= 32 h)	M2	9	0.250	4500.00	4414.80	72	281	424
	M1	9	0.296	4500.00	4414.80	72	332	501
6a	SF	57	1.61	25000.00	24927.50	570	2225	3354
(H= 144 h)	M2	50	6.13	25000.00	24927.50	500	1952	2951
	M1	50	1.90	25000.00	24927.50	500	2310	3634
6b	SF	111	13.84	52000.00	51933.10	1110	4331	6540
(H= 288 h)	M2	104	25.72	52000.00	51933.10	1040	4058	6137
	M1	104	12.14	52000.00	51933.10	1040	4794	7576
6c	SF	219	40.82	106000.00	105944.00	2190	8543	12912
(H= 576 h)	M2	212	8.30	106000.00	105944.00	2120	8270	12509
	M1	212	27.97	106000.00	105944.00	2120	9762	15460
7	SF	49	33.81	21000.00	20935.30	1176	4853	8540
(H= 128 h)	M2	42	43.54	21000.00	20935.30	1008	4160	7329
	M1	42	33.59	21000.00	20935.30	1008	3724	5768

a) Dn = 0 for all cases

Tab.19 Computational results for Examples 8‒12 using maximization of productivity as objectivea)

Example	Model	Event points	CPU time /s	RMILP /cu	MILP /cu	Discrete variables	Continuous variables	Constraints
8	SF	5	0.109	14.00	10.00	20	82	117
(H= 6 h)	M2	3	0.078	14.00	10.00	12	40	73
	M1	3	0.062	14.00	10.00	12	46	79
9	SF	5	0.125	300.00	210.00	25	114	160
(H= 9 h)	M2	3	0.109	300.00	210.00	15	60	100
	M1	3	0.062	300.00	210.00	15	80	105
10	SF	5	0.109	80.00	58.99	30	123	175
(H= 76 h)	M2	2	0.125	80.00	58.99	12	51	73
	M1	2	0.046	80.00	58.99	12	61	76
11	SF	6	0.109	400.00	400.00	24	110	153
(H= 10 h)	M2	4	0.109	400.00	400.00	16	74	105
	M1	4	0.093	400.00	400.00	16	95	129
12	SF	10	0.203	400.00	400.00	40	182	257
(H= 5 h)	M2	8	0.093	400.00	400.00	32	146	209
	M1	8	0.093	400.00	400.00	32	183	265

a) Dn = 0 for all cases

Tab.20 Computational results for Examples 1‒3 using minimization of makespan as objective

Example	Model	Event points	CPU time /s	RMILP /h	MILP /h	Discrete variables	Continuous variables	Constraints
1a (H= 50 h)	SF	14	11.45	24.24	27.88	70	268	394
$D_{s\mathrm{4}}$=2000	M2	12	5.30	25.36	27.88	60	230	342
	M1	12	6.96	24.24	27.88	60	254	383
1b (H= 100 h)	SF	23	7.50	48.47	52.07	115	439	646
$D_{s\mathrm{4}}$=4000	M2	21	5.70	50.06	52.07	105	401	594
	M1	21	4.81	48.47	52.07	105	443	671
2a(H= 50 h)	SF	9	96.00	10.78	19.34	72	301	515
$D_{s\mathrm{8}}$=200	M2	9	28.78	10.78	19.34	72	301	515
$D_{s\mathrm{9}}$=200	M1	9	46.58	18.68	19.34	72	265	425
2b(H= 100 h)	SF	19	3600a)	45.57	46.31	152	631	1105
$D_{s\mathrm{8}}$=500	M2	19	3600b)	45.57	46.31	152	631	1107
$D_{s\mathrm{9}}$=400	M1	19	3600c)	45.57	46.31	152	555	905
3a (H= 50 h)	SF	7	0.187	11.07	13.37	77	327	572
$D_{s\mathrm{12}}$=100	M2	7	0.250	11.07	13.37	77	327	572
$D_{s\mathrm{13}}$=200	M1	7	0.374	11.25	13.37	77	306	501
3b (H= 50 h)	SF	10	0.515	12.50	17.03	110	465	827
$D_{s\mathrm{12}}$=250	M2	10	0.374	12.76	17.03	110	465	827
$D_{s\mathrm{13}}$=250	M1	10	0.359	14.27	17.03	110	435	723

a) Relative gap 1.10%; b) Relative gap 1.43%; c) Relative gap 1.58%. Note Dn = 0 for all cases

Fig.17 Optimal schedule of Example 1d using the model M1, with maximization of productivity as the objective.

Full size|PPT slide

Fig.18 Optimal schedule for Example 4 using the model M1 with maximization of productivity as the objective.

Full size|PPT slide

Tab.21 Computational results for Example 4 using the iterative procedure (maximization of productivity)

Event point	CPU time /s
	SF			M1
	(Dn = 0)	(Dn = 1)		(Dn = 0)	(Dn = 1)
n = 1	‒	‒		0.093	0.078
n = 2	‒	‒		0.062	0.078
n = 3	‒	‒		0.078	0.031
n = 4	0.031	0.062		0.078	0.187
n = 5	0.062	0.094		0.218	0.405
n = 6	0.078	0.078		1.36	9.70
n = 7	0.046	0.188		35.88	700
n = 8	0.250	0.421		532.5	‒
n = 9	1.20	19.6		‒	‒
n = 10	24.18	2027		‒	‒
n = 11	698	‒		‒	‒
Total	2771			1281

7 Conclusions

In this paper, we proposed two novel mathematical formulations M1 and M2 using the unit-specific event-based modelling approach. While timing variables in M1 were defined based on units, they were defined based on tasks in M2. In both models, production and consuming tasks related to the same states were allowed to take place at the same event points. To avoid suboptimality in some cases, we proposed a new definition of recycling and non-recycling tasks. Only the non-recycling production tasks and related consuming tasks are allowed to take place at the same event points. The computational results demonstrate that the proposed models M1 and M2 generated optimal solutions for all examples and reduced the number of event points required, leading to smaller model sizes. Both models are applicable to any batch processes even those with recycling loops. Furthermore, the proposed model M1 is the most efficient since it requires the least possible computational time which can reach up to one magnitude in most cases. In the future, we will extend the proposed models M1 and M2 to solve other more complex intermediate storage policies such as FIS and NIS.

References

[1] Kondili E, Pantelides C C, Sargent R W H. A general algorithm for short-term scheduling of batch operations-I MILP formulation. Computers & Chemical Engineering, 1993, 17(2): 211–227

[2] Pantelides C. Unified frameworks for optimal process planning and scheduling. Proceedings of the Second Conference on Foundations of Computer Aided Operations, 1994, 253–274

[3] Floudas C A, Lin X. Continuous-time versus discrete-time approaches for scheduling of chemical processes: A review. Computers & Chemical Engineering, 2004, 28(11): 2109–2129 doi:10.1016/j.compchemeng.2004.05.002

[4] Méndez C A, Cerdá J, Grossmann I E, Harjukoski I, Fahl M. State-of-the-art review of optimization methods for short-term scheduling of batch processes. Computers & Chemical Engineering, 2006, 30(6-7): 913–946

[5] Li J, Susarla N, Karimi I A, Shaik M A, Floudas C A. An analysis of some unit-specific event-based models for the short-term scheduling of noncontinuous processes. Industrial & Engineering Chemistry Research, 2010, 49(2): 633–647

[6] Maravelias C T. General framework and modeling approach classification for chemical production scheduling. AIChE Journal. American Institute of Chemical Engineers, 2012, 58(6): 1812–1828

[7] Harjunkoski I, Maravelias C, Bongers P, Castro P, Engell S, Grossmann I, Hooker J, Méndez C, Sand G, Wassick J. Scope for industrial application of production scheduling models and solution methods. Computers & Chemical Engineering, 2014, 62(5): 161–193

[8] Velez S, Maravelias C T. Multiple and nonuniform time grids in discrete-time MIP models for chemical production scheduling. Computers & Chemical Engineering, 2013, 53(11): 70–85

[9] Lee H, Maravelias C T. Discrete-time mixed integer programming models for short-term scheduling in multipurpose environments. Computers & Chemical Engineering, 2017, 107: 171–183

[10] Pinto J M, Grossmann I E. A continuous time mixed integer linear programming model for short-term scheduling of multistage batch plants. Industrial & Engineering Chemistry Research, 1995, 34(9): 3037–3051

[11] Sundaramoorthy A, Karimi I A. A simpler better slot-based continuous-time formulation for short-term scheduling in multipurpose batch plants. Chemical Engineering Science, 2005, 60(10): 2679–2702

[12] Susarla N, Li J, Karimi I. A novel approach to scheduling multipurpose batch plants using unit-slots. AIChE Journal. American Institute of Chemical Engineers, 2010, 56(7): 1859–1879

[13] Zhang X, Sargent R W H. The optimal operation of mixed production facilities-A general formulation and some approaches for the solution. Computers & Chemical Engineering, 1996, 20(6-7): 897–904

[14] Castro P, Barbosa-Póvoa A P F D, Matos H. An improved RTN continuous-time formulation for the short-term scheduling of multipurpose batch plants. Industrial & Engineering Chemistry Research, 2001, 40(9): 2059–2068

[15] Maravelias C T, Grossmann I E. New general continuous-time state-task network formulation for short-term scheduling of multipurpose batch plants. Industrial & Engineering Chemistry Research, 2003, 42(13): 3056–3074

[16] Ierapetritou M G, Floudas C A. Effective continuous-time formulation for short-term scheduling. 1. Multipurpose batch processes. Industrial & Engineering Chemistry, 1998, 37(11): 4341–4359

[17] Li J, Floudas C. Optimal event point determination for short-term scheduling of multipurpose batch plants via unit-specific event-based continuous-time approaches. Industrial & Engineering Chemistry Research, 2010, 49(16): 7446–7469

[18] Tang Q H, Li J, Floudas C A, Deng M X, Yan Y B, Xi Z H, Chen P H, Kong J Y. Optimization framework for process scheduling of operation-dependent automobile assembly lines. Optimization Letters, 2012, 6(4): 797–824

[19] Li J, Xiao X, Floudas C A. Integrated gasoline blending and order delivery operations: Part I. Short-term scheduling and global optimization for single and multi-period operations. AIChE Journal. American Institute of Chemical Engineers, 2016, 62(6): 2043–2070

[20] Méndez C A, Cerdá J. Optimal scheduling of a resource-constrained multiproduct batch plant supplying intermediates to nearby end-product facilities. Computers & Chemical Engineering, 2000, 24(2-7): 369–376

[21] Hui C, Gupta A, van der Meulen H A J. A novel MILP formulation for short-term scheduling of multi-stage multi-product batch plants with sequence-dependent constraints. Computers & Chemical Engineering, 2000, 24(12): 2705–2717

[22] Méndez C A, Cerdá J. An MILP continuous-time framework for short-term scheduling of multipurpose batch processes under different operation strategies. Optimization and Engineering, 2003, 4(1-2): 7–22

[23] Li J, Karimi I A. Scheduling gasoline blending operations from recipe determination to shipping using unit slots. Industrial & Engineering Chemistry Research, 2011, 50(15): 9156–9174

[24] Shaik M A, Janak S L, Floudas C A. Continuous-time models for short-term scheduling of multipurpose batch plants: A comparative study. Industrial & Engineering Chemistry Research, 2006, 45(18): 6190–6209

[25] Shaik M, Floudas C. Novel unified modeling approach for short-term scheduling. Industrial & Engineering Chemistry Research, 2009, 48(6): 2947–2964

[26] Shaik M, Vooradi R. Short-term scheduling of batch plants: Reformulation for handling material transfer at the same event. Industrial & Engineering Chemistry, 2017, 56(39): 11175–11185

Acknowledgements

Nikolaos Rakovitis would like to acknowledge financial support from the postgraduate award by The University of Manchester. Liping Zhang appreciates financial support from the National Natural Science Foundation of China (Grant No. 51875420).

Open Access

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

RIGHTS & PERMISSIONS

2019 The Author(s) 2019. This article is published with open access at link.springer.com and journal.hep.com.cn