Slots Startup Synchronization with Shared Resources Dependency

CHEMICAL ENGINEERING TRANSACTIONS VOL. 76, 2019 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Guest Editors: Sauro Pierucci, Jiří Jaromír Klemeš, Laura Piazza Copyright © 2019, AIDIC Servizi S.r.l. ISBN 978-88-95608-73-0; ISSN 2283-9216 Slots Start-up Synchronization with Shared Resources Dependency Carlos G. Palacína,*, Carlos A. Méndezb, Cesar de Pradaa,c aDpt. 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 bCenter for Advanced Process Systems Engineering (CAPSE), INTEC (UNL - CONICET), Industrial Engineering Dpt., Güemes 3450 - Santa Fe (3000), Argentina cInstitute of Sustainable Processes (IPS), University of Valladolid, C/Real de Burgos, s/n, Valladolid 47011, SPAIN corresponding.carlos[email protected]a.es In this work the authors present a new formulation that allows an optimal schedule of batch processes with length dependence on the synchronization of the startup of the processes. It is also keep into account the distribution of shared resources among the devices. 1. Introduction In the majority of the industrial sites the continuous processes represent a huge percentage of the actions and decisions that have to be made. However, it is also important to assign equipment and resources to each process, to determine the starting times and duration of some of those or to manage the maintenance procedures for the devices or pipes, among other important decisions. In order to obtain good performance feasible solutions these problems can be tackle from different angles: using graphs (Osz and Hegyhati, 2018), automata theory (Abdeddaïm et at., 2006), evolutionary algorithms (Safaei et al., 2008) or heuristics (Eles et al.,2018)(Veeragan et al., 2018)(Ren et al., 2018), for example. Even though scheduling is a well know problem in the operational research field, there are yet many open problems in the industrial sector, where, the search for the optimality depends in good measure of the formulation chosen (Harjunkoski et al., 2014). In the food industry environment, frequently appears batch processes in the middle of continuous production lines. If the equipment required for these discontinuous processes are shared among some lines, a scheduling problem arises. These problems can be more complex if the slots have different processing time depending on the device that fulfills them, or the production line that has free them, or the slot size or composition. Usually, they can be solved efficiently with a general precedence formulation (Méndez et al. (2006)), that determines in which device and order each slot shall be initiated. The batch processes normally can be divided in three stages, one startup stage, one main process stage, and one closing stage. Each one will required different resources that can have different natures, as equipment, raw material, or personal, among others. With the classical approach, the resources are reserve when the stage starts, and free again when it finishes. However, there are shared resource that cannot be reserved, as steam or electricity. If the availability of those are enough, the batch processes can be independent from each other, nevertheless, if the steam consumption has a peak in one stage, it may affect other slots in the same stage, as the system has been scale for the normal consume. There are two main strategies to deal with this dependency. One is to set a maximum affordable amount of shared resource, and to synchronize the consuming profiles of the slots (de Prada et al. (2018)). The other one is to approximate the variation that the slots have in each other and to solve the scheduling optimization problem taking into account this alteration. In this work we develop an algorithm in order to synchronize batch processes with a shared resource that affects the duration of the slots. And, we show a practical implementation in a tuna canning factory, where the steam available can only fulfill the requirements of one device startup at a time. The rest of the paper is structured as follows: next section summarises the real case that has motivated this work. Section 3 describe the mathematical formulation developed. Last sections show some results and conclusions with future work. 2. Industrial case study The algorithm has been implemented for a real use case in a tuna canning factory. Once the tuna is cooked, it is introduced in the cans, which are fill up with different food preservatives, as oil or pickled sauce for example, and then sealed. Afterward the cans have to be sterilized by a procedure that maintains certain temperature during a fixed time. This procedure depends on the type of raw material, can and preservative, which create several different recipes (calling recipe to sterilization program) for each combination. After the sterilization, the cans are packed and send to storage, before being distributed to the clients. Either the filling and sealing process like the packaging one is a continuous process; however, the sterilization is a batch process. In order to keep the rhythm from previous production lines, the sterilization is done to a huge amount of cans at the same time. The cans are placed in big industrial metal carts, which are introduced by groups up to the maximum capacity of the sterilizers. The carts are filled up directly at the ending of the production lines, this makes that each cart only contains one type of final product, which means only one of recipe is related to each full cart. Once a cart is release from a production line, it is pushed to an available autoclave or to an input buffer in front of the autoclaves. Then, a count-down starts; each can have to have its sterilization started within a security gap, which has the same duration for all the types of products, in order to prevent microorganism from growing. When one autoclave is full, or if there are not carts with the same sterilization program expected before the maximum waiting time of all the carts introduced goes by, it is closed and the sterilization process started. Once it has finished, the carts are pull out of the autoclaves and placed in the entrance of the packaging processing lines or in the input buffers if they are already busy. 2.1 Problem definition Usually, the operators wait until they have an autoclave full of the same type of carts, meaning the associated recipe by type of cart. However, some types of cans differ only on the packaging and have the same sterilization process associated and can be merged in the same group to be sterilized. On the other hand, if a few carts are going to surpass their security gap, it’s preferable to introduce them with other carts which don’t differ with their recipe, instead of losing the carts. The mixed group would have to be submitted to the most severe sterilization process, in order to assure the microorganism lethality for all the cans. This will harm some of the products, so this option has to be avoided as long as it’s possible. All the sterilization processes consist in three phases (see Figure 1a): a heating phase, when the temperature is increased as quickly as possible up to the set point fixed by the recipe; a plateau phase, when the temperature is maintain for the time set on the sterilization program; and a cooling phase, that takes place in order to reduce the time needed to empty the autoclaves. The temperature is controlled using raw steam to heat the system, which is a shared resource among all the autoclaves. The incoming flow of steam in the heating phase is huge, which makes the pressure in the pipes drop. This means that, if more than one heating phase occurs simultaneously, the durations of these phases are increased. Meanwhile, the plateau phase and the cooling phase have no effects on the rest of autoclaves, and they are not modified by them either. Therefore a scheduling problem appears, where the carts have to be merged in groups and sterilized, preventing a maximum waiting time to be surpassed for each cart, and trying to reduce mixed groups. Nonetheless, the synchronization of starts up appear as a main issue due to resource availability limit, as this directly influences on the starting time of each sterilization. (a) Independent process (b) Several processes influence Figure 1: Temperature and steam consumption profiles for sterilization processes 3. Mathematical formulation The problem has been formulated as a MILP problem, in order to been able to use the efficient MILP solvers. Due to the high amount of carts and their arrival frequency, a typical scheduling solution would require too much computational power to solve it, and would be impossible to implement the solution in the factory. Therefore, a real-time optimisation problem is defined, that will give a solution for a relative short horizon (hours), within which the optimisation will be run again. It has been defined three sets: the carts that have to be sterilized, called 𝐼; the group of carts that are going to be sterilized in the same autoclave at the same time or slots, named 𝐽; and the autoclaves 𝐾. Then, two binary variables have been defined to represent the relations between the sets: 𝑋𝑖∈𝐼,𝑗∈𝐽, that sets that one cart 𝑖 belongs to one slot 𝑗; and 𝑍𝑗∈𝐽,𝑘∈𝐾, that express that one slot 𝑗 is proceed in one device 𝑘. These can be seen in the following equations. Eq(1) assures that one cart can only be assigned to one slot; however, as this tool is a RTO, and it will be run recurrently, one cart doesn’t have to be assigned to be sterilized if its maximum waiting time is not reached within the prediction horizon. Eq(2) and Eq(3) make that each sterilization process will have at least one cart assigned, and that the capacity of the autoclaves are not surpassed. And, Eq(4) forces each slot to be related to one and only one autoclave. ∑𝑋𝑖,𝑗≤1 𝑗∈𝐽 ∀𝑖∈𝐼 (1) ∑𝑋𝑖,𝑗 𝑖∈𝐼 ≤𝐶 ∀𝑗∈𝐽 (2) ∑𝑋𝑖,𝑗 𝑖∈𝐼 ≥1 ∀𝑗∈𝐽 (3) ∑𝑍𝑗,𝑘 𝑗∈𝐽 =1 ∀𝑘∈𝐾 (4) There are two input parameters defined for each cart 𝑖, 𝑡𝑎𝑖∈𝐼 and 𝑡𝑒𝑖∈𝐼. The first one represent the time instant when a cart is release from the sealing line, and the second is the duration of the plateau phase plus the cooling one needed for the cart. With those inputs, we can defined 𝑡𝑝𝑗∈𝐽 as the duration of the maintaining and cooling procedures for a slot, and 𝑡𝑠𝑗∈𝐽 as the start time of a sterilization process. It has to be also defined one parameter 𝑇 that represents the maximum waiting time for each cart, and one parameter 𝑆 for the maximum clearance allowed among the sterilization process duration of carts in the same slot. Eq(5) and Eq(6) bound the starting time for a slot, between the arrival of the carts introduced in it, and the maximum waiting time of them. In order to keep the linearity of the problem an artificial parameter sufficiently large is introduced (𝑀), that makes the constraints idle when it is not cancelled, and vice versa. The so called big M method to translate logical predicates into mathematical formulation (Winston, 2008). Eq(7) and Eq(8) bound the duration of the process between the minimum and maximum durations of the sterilization process of the carts included in the slot, whit a maximum difference of 𝑆. 𝑡𝑠𝑗≥𝑡𝑎𝑖−𝑀⋅(1−𝑋𝑖,𝑗) ∀𝑖∈𝐼,∀𝑗∈𝐽 (5) 𝑡𝑠𝑗≤𝑡𝑎𝑖+𝑇+𝑀⋅(1−𝑋𝑖,𝑗) ∀𝑖∈𝐼,∀𝑗∈𝐽 (6) 𝑡𝑝𝑗≥𝑡𝑒𝑖⋅𝑋𝑖,𝑗 ∀𝑖∈𝐼,∀𝑗∈𝐽 (7) 𝑡𝑝𝑗≤𝑡𝑒𝑖+𝑆+𝑀⋅(1−𝑋𝑖,𝑗) ∀𝑖∈𝐼,∀𝑗∈𝐽 (8) As it has been said, the carts are only forced to be included in one slot, if they arrive before a time horizon, coded as the parameter 𝐻. This can be seen in Eq(9), which is only active if the cart 𝑖 is not assigned. 𝑡𝑎𝑖+𝑀⋅∑𝑋𝑖,𝑗 𝑗∈𝐽 ≥𝐻 ∀𝑖∈𝐼 (9) Once the groups are done, the problem has to deal with the scheduling of the sterilizations. First, it is defined one binary variable (𝑊𝑗1∈𝐽,𝑗2∈𝐽) that defines that two slots (𝑗1 and 𝑗2) share steam during the heating phase. In order to reduce the complexity of the problem this variable is only defined for half of the combinations, as if one slot affects another, it happens also the other way around. However, this creates a huge amount of constraints, making the problem heavy and slow to solve. In order to prevent this, we suggest defining an artificial pre-order for the slots which doesn’t affect the result. It is a fact that each slot will start before or at the same time than a previous one, except for the first one. Then we defined an order in the set of slots, which will define the order they shall follow; as none slot is preassigned to any autoclave or cart, this assumption doesn’t affect the result. This new formulation let the problem deal with the synchronization easily taking into account the shared resources. This order is express in Eq(10), where one slot 𝑗2 starts after or at the same time that another 𝑗1 if they have this order in the set. 𝑡𝑠𝑗1≤𝑡𝑠𝑗2 ∀𝑗1,𝑗2∈𝐽∶𝑂𝑅𝐷(𝑗1)<𝑂𝑅𝐷(𝑗2) (10) Then, the general precedence formulation is modified, as the typical binary variable that sets the order between two slots in the same equipment, is no longer needed. Now, the order is already know, and the formulation only have to check the equipment they are assigned to, as it can be seen in Eq(11), where it is introduced a new real variable 𝑡ℎ𝑗∈𝐽, the heating time required for a slot 𝑗. In this particular case, the heating time of a slot, which is the start-up time of a slot in a general formulation, has a constant minimum value (κ) plus a term proportional to the number of slots that coincide in this phase, shown in Eq(12) where it can be seen that the binary variable is only defined for the inferior triangular matrix form by the combination of slots. Eq(13) reduce the options to the solver removing impossible combinations; if one slot doesn’t affect a previous one, none of the successive will. 𝑡𝑠𝑗1+𝑡ℎ𝑗1+𝑡𝑝𝑗1≤𝑡𝑠𝑗2+𝑀⋅(2−(𝑍𝑗1,𝑘+𝑍𝑗2,𝑘)) ∀𝑗1,𝑗2∈𝐽∶𝑂𝑅𝐷(𝑗1)<𝑂𝑅𝐷(𝑗2),∀𝑘∈𝐾 (11) 𝑡ℎ𝑗=𝜅+𝛼⋅( ∑ 𝑊𝑗𝐴,𝑗 𝑗𝐴∈𝐽∶𝑂𝑅𝐷(𝑗𝐴)<𝑂𝑅𝐷(𝑗)+ ∑ 𝑊𝑗,𝑗𝐵 𝑗𝐵∈𝐽∶𝑂𝑅𝐷(𝑗)<𝑂𝑅𝐷(𝑗𝐵)) ∀𝑗∈𝐽 (12) 𝑊𝑗,𝑗1≥𝑊𝑗,𝑗2 ∀𝑗,𝑗1,𝑗2∈𝐽∶𝑂𝑅𝐷(𝑗)<𝑂𝑅𝐷(𝑗1)<𝑂𝑅𝐷(𝑗2) (13) Eq(14) and Eq(15) constraint the synchronization of the slots. The first one represents when two slots doesn’t coincide, 𝑊𝑗1,𝑗2 will be zero, therefore the start of the second slot will happened after the heating phase of the first one. On the other hand, if the binary variable is equal to one, this equation will have to effect, and Eq(15) will force the start of the second slot to happen before the heating is over, keep in mind that the starts are already force to happen one after the other. 𝑡𝑠𝑗1+𝑡ℎ𝑗1≤𝑡𝑠𝑗2+𝑀⋅𝑊𝑗1,𝑗2 ∀𝑗1,𝑗2∈𝐽∶𝑂𝑅𝐷(𝑗1)<𝑂𝑅𝐷(𝑗2) (14) 𝑡𝑠𝑗1+𝑡ℎ𝑗1≥𝑡𝑠𝑗2−𝑀⋅(1−𝑊𝑗1,𝑗2) ∀𝑗1,𝑗2∈𝐽∶𝑂𝑅𝐷(𝑗1)<𝑂𝑅𝐷(𝑗2) (15) Finally, the ending time of the overall schedule is defined in Eq(16) in a new variable 𝑡𝑓 in order to be able to minimize the makespan. 𝑡𝑓≥𝑡𝑠𝑗+𝑡ℎ𝑗+𝑡𝑝𝑗 ∀𝑗∈𝐽 (16) 4. Results The problem has been solved in a laptop computer, with a i7-4510U processor, optimized to reduce energy consumption instead of computing power, which make it a good system to test tools that are going to be installed in an industrial site. Coded in GAMS 25.1.1, using Cplex 12.8.0.0 as MILP solver. First optimization option is to minimize the makespan of the system, Eq(17). However, when the production is key to meet deadlines, the objective could be increasing the number of carts sterilized Eq(18), even though it could reduce the quality of some carts, preventing exceeding the maximum waiting time. min 𝑋𝐼,𝐽,𝑍𝐽,𝐾,𝑊𝐽,𝐽,𝑡𝑠𝐽,𝑡𝑝𝐽,𝑡ℎ𝐽𝑡𝑓 (17) max 𝑋𝐼,𝐽,𝑍𝐽,𝐾,𝑊𝐽,𝐽,𝑡𝑠𝐽,𝑡𝑝𝐽,𝑡ℎ𝐽∑∑𝑋𝑖,𝑗 𝑗∈𝐽𝑖∈𝐼 (18) One example can be seen in Figure 1, where the schedule of two hundred carts with five different recipes is shown, minimizing the makespan. There have been set sixteen autoclaves, and fifteen slots have to be sterilized. However the optimizer has found a solution, using only thirteen devices, in less than one minute; which makes the algorithm suitable to use in a real-time software schedule support system. Figure 2: Real scheduling solution example 5. Conclusions A new approach to deal with the schedule of slots which duration depends on the synchronization with others has been presented in this work. This formulation increases the speed of resolution without losing optimality. It tackles the scheduling of processes which lengths depends on the synchronization itself and shared resources consumption. It can be extended for more resources or more phases by adding more binary variables, but keeping the kernel of the formulation similar. It has been tested in a real use case, proving its efficiency and the possibility of including it in RTO tools. Nevertheless, the algorithm has to be improved in order to increase the prediction horizon and to be able to modify the perturbations profile between the heating processes. It can also be included uncertainty in the production lines frequency and resource availability using an stochastic approach. Acknowledgments This research has received funding from the European Union Horizon 2020 research and innovation programme (grant number 723575) and from the Spanish Government under project (DPI2015-70975-P MINECO/FEDER). References Abdeddaïm, Y., Asarin, E., Maler, O., 2006, Scheduling with timed automata, Theoretical Computer Science, 354(2), pp.272-300. Eles A., Cabezas H., Heckl I., 2018, Heuristic algorithm utilizing mixed-integer linear programming to schedule mobile workforce, Chemical Engineering Transactions, 70, 895-900 DOI:10.3303/CET1870150 Harjunkoski, I., Maravelias, C.T., Bongers, P., Castro, P.M., Engell, S., Grossmann, I.E., Hooker, J., Méndez, C., Sand, G. and Wassick, J., 2014. Scope for industrial applications of production scheduling models and solution methods. Computers & Chemical Engineering, 62, pp.161-193. Méndez, C. A., Cerdá, J., Grossmann, I. E., Harjunkoski, I., Fahl, M., 2006, State-of-the-art review of optimization methods for short-term scheduling of batch processes, Computers & Chemical Engineering, 30(6-7), 913-946 Osz O., Hegyhati M., 2018, An s-graph based approach for multi-mode resource-constrained project scheduling with time-varying resource capacities, Chemical Engineering Transactions, 70, 1165-1170 DOI:10.3303/CET1870195 de Prada, C., Mazaeda, R., Podar, S., 2018, Optimal Operation of a Combined Continuous–Batch Process, In Computer Aided Chemical Engineering, 44, 673-678 Ren C., Zhao J., Chen L., Huang Y., 2018, Application of firefly algorithm in scheduling optimization of combined cooling, heating and power with multiple objectives, Chemical Engineering Transactions, 67, 829-834 DOI: 10.3303/CET1867139 Safaei, N., Banjevic, D., Jardine, A.K., 2008. Multi-objective simulated annealing for a maintenance workforce scheduling problem: a case study. In Simulated annealing. InTech Veeraragavan S., Chan W.M., Chew I.M., Foo D.C.Y., 2018, Task-based shift scheduling through process integration technique , Chemical Engineering Transactions, 70, 1057-1062 DOI:10.3303/CET1870177 Winston, W.L., 1987, Operations Research: Applications and Algorithms, PWS-Kent, Boston, Massachusetts