Optimal Coordination of Batch Processes with Shared Resources

Optimal Coordination Of Batch Processes with Shared Resources Carlos G. Palac´ın ∗Cesar de Prada ∗,∗∗ ∗Dpt. Of Systems Engineering and Automatic Control, Escuela de Ingenier´ıas Industriales, Sede Mergelina, Universidad de Valladolid, C/Real de Burgos, s/n, Valladolid 47011, SPAIN (e-mail: c[email protected]). ∗∗ Institute of Sustainable Processes (IPS), University of Valladolid, C/Real de Burgos, s/n, Valladolid 47011, SPAIN (e-mail: pr[email protected]) Abstract: This paper deals with the scheduling of batch processes that share common resources having consumption profiles that change over time and are subjected to some global constraints. In order to approach the problem, the formulation mixes three different time basis. Scheduling is performed in continuous time, but the description of the shared resources and the global constraints uses discrete values. The method is applied to a challenging problem in a tuna canning factory that mixes continuous flows of cans with the batch operation of a set of sterilizers sharing the steam supply line. Keywords: Process scheduling, shared resources, tuna cans sterilization, process optimization, continuous-batch process scheduling. 1. INTRODUCTION It is widely accepted that increasing efficiency in the operation of industrial sites is an important target in face of the growing competition, regulations, etc. that industry faces today. A key element for improving efficiency are decisions about how to operate production lines and units that, taking into account production constraints, are optimal in a certain way (Biegler and Grossmann, 2004). This calls for methodologies based on models and optimization such as real-time optimization (de Prada and Pitarch, 2018) or scheduling (Grossmann, 2012). There are a large number of approaches and good examples of industrial applications of them bringing substantial benefits, (Palac´ın et al., 2018; Pitarch et al., 2017). Nevertheless, the direct implementation of these methodologies is not easy, due to the variety of configurations and complexity of many processes that require specific formulations in order to obtain robust, efficient and flexible decision making systems . This is the case when, for instance, there are batch units operating besides continuous production lines, or when the units share common resources, which makes the optimization problems more complex and difficult to solve (Harjunkoski et al., 2014). In this paper a type of scheduling problems is considered that correspond to the schematic of Fig.1, where there are some continuous flows of product packs (triangles) that have to be subjected to a batch process in a set of parallel batch units (rectangles). Each unit can fit up to a maximum number of packs in every go, so these may form groups to be processed. A batch requires, according to a time varying profile, the use of one resource that is shared among the batch units with a limited availability. The routes between the production lines and the batch units, and the batch units and the followings, are not shown on the drawing. Batch units Groups & queues Shared resource Products arrival Consumption profiles Fig. 1. Schematic of the type of processes considered. This architecture is common to many industrial plants and the efficient formulation of the optimal operation problem has two main difficulties: one is the selection of the type of time base; and the other one is the formulation of the constraints on the limited shared resource with time changing profiles. Both are not independent and in particular the shared resource problem does not appear very often in the literature. The use of a discrete time formulation facilitates the computation of the resources consumption at a certain time instant, but does not provide good precision when computing the starting times of the batches, unless the time grid is very small, what increases considerably the size of the problem and consequently the solution time. On the contrary, using a continuous time formulation the starting times of the batches can be computed precisely with less variables, but the computation of the shared resources lost precision and it is more difficult. In this paper it is presented a novel approach of the scheduling problem combining continuous and discrete time domains. In order to speed up the resolution the approach is formulated as a mixed-integer linear programming (MILP) optimization. The method is an extension of de Prada et al. (2018) but allowing different shared resource consuming profiles. The method is explained and illustrated with a real case in a tuna canning factory, considering the interface between the continuous production lines of cans and the sterilizers. After this introduction, the rest of the paper is organized as follow: next section describes an industrial use case of a canning factory where the proposed approach is applied; then section 3 explains the mathematical model and section 4 present results of the optimal operation of the factory. The paper ends with some conclusions and references. 2. TUNA CANNING FACTORY The proposed approach is applied to the sterilization section of a canning factory, which has several production lines that generate one continuous flow of cans for every line. There are different types of cans, according to their size and filling product. The cans are stacked in carts at the outcome of the production lines, in order to manipulate them easier. Each cart represent one triangle of previous figure Fig. 1, and each autoclave represent one rectangle. The cans need to be sterilized before going to market to avoid growing of harmful microorganism, this operation being performed in a series of autoclaves or sterilizers. All the autoclaves are identical and are available to be used with all products from the previous lines, working in parallel concurrently. Once the autoclave finishes the operation the carts are carried out to packaging lines, where they are emptied and return to the production lines(Alonso et al., 2013). The sterilization is a batch process, the autoclaves are filled with several carts and then proceed to perform the respective sterilization process. Each product has a different sterilization process (time and temperature). In general, a sterilizer is loaded with carts of the same type, however, in some circumstances, they can be mixed as long as the most severe sterilization recipe of the corresponding cans is fulfilled. The carts wait in front of the sterilizers to be processed and before that, they must be organized into groups that will be processed simultaneously in a sterilizer. Once a can is sealed, which is done right before the sterilization step, there is a maximum waiting time for the cans until they reach certain temperature set point in order to prevent dangerous amines to start growing. Then the sterilization process follows a recipe in which the temperature profile inside the autoclaves has three phases: a heating phase, that increases the temperature of the Fig. 2. Normal profiles of steam demand and temperature in an autoclave. cans as fast as possible, up to a fixed set point; then a plateau phase, where the temperature is maintained; and a cooling phase, needed to empty the autoclave quick, in order to use it again. This temperature profile is obtained using steam as heat source, mainly in the heating phase, but also during the plateau phase, as shown in Fig. 2. The autoclaves operate independently, but they share the incoming steam flow. If many autoclaves demand steam at the same time, the pressure may drop, increasing the length of their heating phases, a good operation should avoid this situation to the extent possible. 3. MATHEMATICAL MODEL Precise operation of the canning plant means taking the right decisions about how organizing the carts in groups, how assigning the groups to the sterilizers and when to start operating each sterilizer. All of that, guaranteeing that the operating constraints of maximum waiting time of the carts before sterilization and total flow, as well as maximum steam consumption, are maintained while some criteria are optimized in terms of costs or makespan. The question is conceived as a scheduling problem that considers the current situation of the production lines and the expected arrival of the different types of carts within a certain future horizon to generate the optimal decisions concerning current and future cart grouping and autoclaves operation. This allows to launch the scheduling software at regular intervals, adapting the operation to the new conditions that may appear, in a similar way as model predictive control is implemented (Camacho and Alba, 2013). In order to facilitate implementation, avoiding contradictory orders between successive executions of the algorithms, some additional constraints are added and some flexibility introduced in the formulation regarding queuing of carts. The problem is formulated as a MILP one facilitating a fast-enough resolution to be applied on-line. The main difficulties in the formulation are linked to the existence of global constraints on the shared resource steam to the sterilizers, which presents additionally a changing over time profile. As mentioned before, in the literature this type of problems are solved quite often using a discrete time formulation; however, this reduce the optimality of the solution as the actions can only be taken in the sample times, unless the grid size is reduced and the size of the problem enlarged significantly. A continuous representation fixes this, nevertheless it is not able to fulfill constraints between the events. This is why the proposed approach mixes three sub-problems with their corresponding time basis: one scheduling problem that uses continuous time; one linear approximation to the non-linear consuming profiles, via a non-regular discrete time formulation; and, finally, the restrained global constraint on the steam consumption formulated in regular discrete time. By combining them, we arrive to a flexible formulation that take advantage of the benefits of every approach. 3.1 Merging carts into groups Each cart has one associated steam consumption profile. Then, the carts are gathered into groups up to the maximum capacity of the autoclaves; they can come from different sources and can be similar or different with respect to the steam profile. We have defined three sets in order to model the scheduling problem: •I: the carts, that are considered as the input, and that arrive with a frequency previously computed by the production planning; •J: the group of carts that are going to be sterilized together, slots, or sterilization processes; •K: the set of autoclaves, which represent the real devices installed in the plant. In order to relate these sets, three binary variables are defined: Xi,j :i∈I, j ∈J, determines if one cart iis part of a group of carts j;Yj1,j2:j1, j2∈Jequals to 1 denotes that the slot j1 is sterilized before j2 in the same equipment; and Zj,k :j∈J, k ∈K, which indicates if the group jis treated in the autoclave k. Additionally, a set of constraints apply to the grouping of carts, these are the typical assignment constraints: •A cart icannot be assigned to more than one group, but can remain unassigned for a certain time: X j∈J (Xi,j)≤1∀i∈I(1) •There is a maximum number of carts (ξ) that can be assigned to a group j: X i∈I (Xi,j)≤ξ∀j∈J(2) •Every sterilization process jmust have assigned at least one cart: X i∈I (Xi,j)≥1∀j∈J(3) 3.2 Scheduling Then, the general precedence formulation is represented in (4), (5), (6), (7) and (8), where we introduce two real variables, tsj:j∈Jand tpj:j∈J. The first one represent the starting time of the slot jsterilization; while the second one determines the duration of the sterilization process for the group j. And where Γ is a parameter big enough in order to use the big M method (Winston and Goldberg, 2004). •A group jmust be processed in a sterilizer and only in one of them: X k∈K (Zj,k) = 1 ∀j∈J(4) •Either j1 precedes j2 or viceversa: Yj1,j2+Yj2,j1≤1∀j1, j2∈J:j16=j2 (5) •If two groups j1,j2 are assigned to the same sterilizer, one must precede the other: Yj1,j2+Yj2,j1≥(Zj1,k +Zj2,k)−1 ∀j1, j2∈J:j16=j2,∀k∈K(6) •If two groups j1,j2 are not assigned to the same sterilizer, then the corresponding variable Yj1,j2must be zero: Yj1,j2≤1−(Zj1,k −Zj2,k) ∀j1, j2∈J:j16=j2,∀k∈K(7) Notice that, ∀j∈J, ∃k∈K:Zj,k = 1 according to (4). •If group j1 precedes j2 in the same sterilizer, then group j2 cannot be sterilized before j1 ends: tsj1+tpj1≤tsj2+ Γ ·(1 −Yj1,j2) ∀j1, j2∈J:j16=j2(8) 3.3 Sterilization process Each sterilization process cannot start until all the carts merged in their respective group have arrived, that is, they have been released from the previous production lines. The arrival time of a cart iis represented by the parameter tai:i∈I. tsj≥tai−Γ·(1 −Xi,j)∀i∈I, ∀j∈J(9) Due to quality and sanitary restrictions, the carts cannot be waiting more than a maximum time, represented by the parameter τ, since they arrive, as it has been already explained. However, not all the carts have to go through the sterilization process before the next run of the optimization problem. This originate a new degree of freedom by choosing an horizon η, which represent the time instant after which the carts no longer are forced to be included in a slot. This waiting time is constrained in (10) and (11). tsj≤tai+τ+ Γ ·(1 −Xi,j)∀i∈I, ∀j∈J(10) tai≥η−Γ·X j∈J (Xi,j)∀i∈I(11) One cart has the type determined by the type of cans that fill it (v.gr. the product or the size of the can). Denoting as Lthe set of types of cans, a binary parameter can be defined (Ui,l :i∈I, l ∈L) indicating that cart i contains type lcans. The time length of the sterilization process required for a cart depends on its type, and can be represented by the parameter tel:l∈L, which is known in advance. Similarly, a group of carts, whenever possible, is formed by carts of the same type, but, in general, the type of a group is the most restrictive one among the carts that compose that group. The types are ordered by rigor, this means: ∀l1, l2∈L:l1l2 =⇒tel1≤tel2, all the carts of type l1 can be sterilized with the profile specific for the type l2, but not the other way round. Now, a binary variable, Vj,l :j∈J, l ∈Lcan be defined denoting that the group of carts jshould be processed according to the requirements of cart type l. Obviously, one group must be processed according to a single type: X l∈L (Vj,l)=1 ∀j∈J(12) Then, the length of the sterilization process that must be applied to a group jof carts, tpj, is given by: tpj=X l∈L (tel·Vj,l)∀j∈J(13) If a cart iof type l1 is assigned to a group j, the group j must be identified as type l1 or as a more restrictive one. Ui,l1≤X l2∈L:l1l2 (Vj,l2)+Γ·(1 −Xi,j) ∀i∈I, ∀j∈J, ∀l1∈L (14) Mixing different types of carts in the same slot damages the quality of the final product; therefore, is a solution that has to be prevented to happen but has to be kept in mind in order to avoid unfeasible scenarios with a high sterilization demand. As the sterilization procedure lengths are directly proportional to the strictness of these processes, the optimizer will automatically assign the less severe profile. 3.4 Shared resource synchronization The time varying steam profiles, similar to the ones of the example presented in Fig. 2, have to be included in the formulation of the problem. In order to keep the linearity of the problem, they are approximated using a piece-wise linear function for each type of cart. In order to maintain an acceptable similarity to the continuous profile with a small number of points, the discretization sampling used is non-regular, this allows to choose the most important points for each profile with a minimum loss of precision. The relative time scale base is shared by all profiles, easing the synchronization of the slots without knowing in advance what sterilization type each slot will have. That time scale is defined by a set of time points, N={−ν, 0,1,2,3, . . . , ν −1, ν}, and their relative value with respect to the process times, Sn:n∈N.S0is time zero, corresponding to the start of the processing in the sterilizer, it has to be synchronized with the starting time of the slot tsj:j∈J. Previous time sample, S−ν, corresponds to the first point, and is a time point far in the past. Then, the rest of ordered time points Sn, of which Sνand Sν−1corresponds to the last one and second to last respectively, fulfilling that in the interval [Sν−1, Sν] the steam consumption is zero for all types of carts, and covering the scheduling horizon. In addition, we will represent with the parameter Qn,l :n∈N, l ∈Lthe value of the steam flow demanded during the processing of a group of type lat the relative time instant Sn, i.e. the piece-wise function. This means that: Q−ν,l =Q0,l =Qν−1,l =Qν,l = 0 ∀l∈L. Some typical profiles are represented in Fig. 3 for four different types of carts. Notice that they cover from S−νto Sν, and that all have the same sample times even thought not all are used for every profile. All data in the graphs have suffered certain scaling to maintain confidentiality. Fig. 3. Linear approximations of steam profiles, associated to different types of sterilizations. In order to compute the total steam flow consumed by the sterilizers in operation at a certain time instant, a third time base is defined, composed by a set Mof regularly spaced time points, tmm:m∈M. Both global time scales, this one and the continuous one used to compute the scheduling, have the current time as the origin ( time = 0 ), i.e. they are directly synchronized. Then, for every tmm instant, we have to determine the corresponding point in all the relative time bases of the different slots; that is, the consumption profiles have to be synchronized with the overall regular time scale. For this purpose two variables have been defined, represented in Fig. 4: •Wm,j,n :m∈M, j ∈J, n ∈N, a binary variable that pictures if the relative time (tmm−tsj) belongs to the interval nof the time base of group j; •and αm,j,n,l :m∈M, j ∈J, n ∈N, l ∈L, real positive, used to represent the percentage of the n interval of the slot jwhere tmmis, located. The type set lis added in order to keep the linearity of the problem. Fig. 4. Global time point tmmand local time scale of two slots j1 and j2. Therefore, the following constraints allow performing the synchronization: One time instant tmmmust be in one and only in one interval of every slot j. Notice that Ncovers all scheduling horizon. The last Wis forced to be zero: X n∈N (Wm,j,n)=1 ∀m∈M, ∀j∈J(15) Wm,j,ν = 0 ∀m∈M, ∀j∈J(16) For each time tmmand slot j,αis forced to be a fraction: X n∈N,l∈L (αm,j,n,l)=1 ∀m∈M, ∀j∈J(17) Referring to Fig. 4, if a global time tmmcorresponds to interval nof a slot j, all α’s are forced to be zero except the ones with sub-indexes of the interval nand the following one n+1, but for the first one that only depends on itself: X l∈L (αm,j,n,l)≤Wm,j,n−1+Wm,j,n ∀m∈M, ∀j∈J, ∀n∈N:n6=−ν (18) X l∈L (αm,j,−ν,l)≤Wm,j,−ν∀m∈M, ∀j∈J(19) The length of the interval (tmm−tsj) is given as a linear combination of the points Sn:tmm∈[n, n + 1) as in Fig. 4: tmm−tsj=X n∈N,l∈L (αm,j,n,l ·Sn) ∀m∈M, ∀j∈J (20) All α’s not corresponding to the type of cans lbeing processed in slot jare forced to be zero: αm,j,n,l ≤Vj,l ∀m∈M, ∀j∈J, ∀n∈N, ∀l∈L(21) Hence, having the lineal combination of the bounds for every sampling time, we can compute the steam consumption using the piece-wise function approximation as: X l∈L (αm,j,n,l ·Qn,l)∀m∈M:tmm∈[n, n + 1) Consequently, denoting Qmax as the maximum steam consumption admissible at any time, tmm: X n∈N,j∈J,l∈L (αm,j,n,l ·Qn,l)≤Qmax ∀m∈M(22) Notice that (21) guarantees that only the profile for the type of the respective slot is used. 3.5 Optimization problem Once the constraints are defined, the optimization problem can be formulated as minimizing a cost function Junder the previous set of constraints (1) - (22). Different cost functions can be defined according to possible different operation aims, in terms of costs, throughput, makespan, etc. In the paper we have considered: J=X j∈J (β·tsj+γ·tpj) (23) that is defined in order to minimize the sterilization processes to the maximum allowable per slot, and to Table 1. Portion of the table that points out the type of the carts and their arrival time. i t1 t2 t3 t4 ta i c35 36.18 c36 36.18 c37 37.10 c38 38.52 c39 40.18 c40 40.62 c41 40.70 c42 40.78 c43 41.20 c44 44.45 c45 45.12 c46 46.12 c47 46.12 c48 46.87 c49 48.88 c50 50.80 c51 52.13 process the groups of carts as soon as possible, minimizing the risk of growing toxic products in the cans due to excessive waiting time, in spite of constraint (10) if, due to external factors, processing delays appear. The parameters γand βare used to weight these objectives respectively. 4. SCHEDULING EXAMPLE For the purpose of demonstrate the usefulness of the algorithm presented, it has been tested in the case study. We have schedule an hour of carts production, forcing to sterilize the carts that arrived in the first three quarters of an hour. There are three autoclaves available to sterilize four types of carts (we use the steam consumption profiles shown in Fig. 3). The carts arrive at random times, with a time interval around one minute, each with a different type. A little sample is shown in the table 1, where some carts, i∈I, are related with their type (L⊇ {t1, t2, t3, t4}) and have an arrival time, tai, expressed in minutes, relative to an initial global time. In order to display some results several tests have been done with different configurations. In the cases that are going to be shown in particular, we have set seven slots that has to be sterilized, with a maximum capacity, ξ, of also seven carts each; this makes a maximum capacity of 54 carts sterilized, which is a little less than the number of carts that arrived. The first schedule, which solution can be seen in the Fig. 5, has a global constraint of 160 ton of maximum steam consumption at each sample time. Secondly, the global steam consumption constraint at each sample time is rise up to 180 ton. This is shown in Fig. 6. In both cases the slots schedule and assignment to autoclaves can be seen in their respective figures. Notice that all the quantities have been scale to maintain confidentiality. It can be seen the rearrange of the slots in the case where more resource is available, in order to minimize the end time, as it can be assumed by the system. Also, the starting time of several slots can coincide as long the maximum peak that correspond with a sample time is below the constraint. Meanwhile, in the lower constraint solution, the starting times are spread throughout the time horizon. Fig. 5. Schedule constrained to 160 ton of steam available, with the steam per autoclave in the vertical axis. Fig. 6. Schedule constrained to 180 ton of steam available, with the steam per autoclave in the vertical axis. In the same way, Fig. 7 show the time evolution of the global steam consumption for both cases. In a continuous line, with square markers, the consumption for a scheduling with a maximum allowable demand of 160 ton and in dotted line, with circle markers, the consumption for a scheduling with a maximum allowable demand of 180 ton. Fig. 7. Global consumption of two scheduling with 160 ton and 180 ton as global constraint. All the test have been run in a personal laptop, in order to prove the flexibility of the program to introduce it in a factory environment. It takes less than ten minutes to reach the optimal solution for every configuration, in a CPU Intel R CoreTM i7-4510U, a processor optimize to reduce the power consumption instead of the speed. It has been coded in GAMS, using the solver Cplex 12.8.0.0. 5. CONCLUSIONS A new formulation of a type of scheduling problems involving continuous and batch processes has been presented. It is based on the use of three different time basis and solves the problem of shared resources. Perhaps the main contribution is related to the fact that it opens a door for the integration of the scheduling of batch units with its optimal operation through time varying profiles. The formulation presented can handle different equipment performances and types of products, improving the functionality of the previous version. As the linearity of the formulation is kept, the problem can be solved using MILP optimization techniques instead of heuristic, which assure that the solution obtained is optimal. An example has been shown in a tune canning factory in order to check the usefulness of the paradigm provided. ACKNOWLEDGEMENTS This research has received funding from the European Union’s Horizon 2020 research and innovation programme (grant number 723575) and from the Spanish Government under project (DPI2015-70975-P MINECO/FEDER) REFERENCES Alonso, A.A., Arias-M´endez, A., Balsa-Canto, E., Garc´ıa, M.R., Molina, J.I., Vilas, C., and Villaf´ın, M. (2013). Real time optimization for quality control of batch thermal sterilization of prepackaged foods. Food Control, 32(2), 392 – 403. doi: https://doi.org/10.1016/j.foodcont.2013.01.002. Biegler, L.T. and Grossmann, I.E. (2004). Retrospective on optimization. Computers & Chemical Engineering, 28(8), 1169 – 1192. doi: https://doi.org/10.1016/j.compchemeng.2003.11.003. Camacho, E.F. and Alba, C.B. (2013). Model predictive control. Springer Science & Business Media. de Prada, C., Mazaeda, R., and Podar, S. (2018). Optimal operation of a combined continuous–batch process. In Computer Aided Chemical Engineering, volume 44, 673– 678. Elsevier. de Prada, C. and Pitarch, J.L. (2018). Real-time optimization (RTO) systems. Resource Efficiency of Processing Plants: Monitoring and Improvement, 265–292. Grossmann, I.E. (2012). Advances in mathematical programming models for enterprise-wide optimization. Computers & Chemical Engineering, 47, 2–18. Harjunkoski, I., Maravelias, C.T., Bongers, P., Castro, P.M., Engell, S., Grossmann, I.E., Hooker, J., M´endez, C., Sand, G., and Wassick, J. (2014). Scope for industrial applications of production scheduling models and solution methods. Computers & Chemical Engineering, 62, 161–193. Palac´ın, C.G., Pitarch, J.L., Jasch, C., M´endez, C.A., and de Prada, C. (2018). Robust integrated productionmaintenance scheduling for an evaporation network. Computers & Chemical Engineering, 110, 140–151. Pitarch, J.L., Palac´ın, C.G., de Prada, C., Voglauer, B., and Seyfriedsberger, G. (2017). Optimisation of the resource efficiency in an industrial evaporation system. Journal of Process Control, 56, 1–12. Winston, W.L. and Goldberg, J.B. (2004). Operations research: applications and algorithms, volume 3. Thomson Brooks/Cole Belmont.