Single station MILP scheduling in discrete and continuous time

Vol.:(0123456789) Central European Journal of Operations Research https://doi.org/10.1007/s10100-024-00905-4 1 3 Single station MILP scheduling indiscrete andcontinuous time María‑LuisaMuñoz‑Díaz1 · AlejandroEscudero‑Santana1 · AntonioLorenzo‑Espejo1 · RoelLeus2 Accepted: 15 January 2024 © The Author(s) 2024 Abstract This article focuses on production planning in the metallurgical sector. This study undertakes a detailed comparative study of mixed-integer linear programming models using different time representations: continuous and discrete. The analysis shows that the continuous model consistently outperforms its discrete counterpart in all evaluated scenarios. The key difference between the continuous and discrete models is the continuous model’s ability to deliver better makespan results, achieving an improvement of up to 15% compared to the discrete model. This advantage holds even in complex environments with a high number of tasks and machines, where the continuous model consistently outperforms the discrete model by over 6% in the scenario with the highest number of tasks and machines. This preference extends beyond makespan considerations. The continuous model also maintains an edge in terms of runtime efficiency, achieving better times with a 99% improvement over the discrete model in all scenarios except one. These findings provide concrete evidence for the use of continuous models, which promise more effective production planning in analogous manufacturing domains. Alejandro Escudero-Santana, Antonio Lorenzo-Espejo and Roel Leus have contributed equally to this work. * María-Luisa Muñoz-Díaz [email protected] Alejandro Escudero-Santana [email protected] Antonio Lorenzo-Espejo [email protected] Roel Leus [email protected] 1 Department ofIndustrial Organisation andBusiness Management II, University ofSeville, Camino de los Descubrimientos, s/n, 41092Seville, Spain 2 Research group ORSTAT , Faculty ofEconomics andBusiness, Naamsestraat 69, 3000Leuven, Belgium M.-L.Muñoz-Díaz et al. 1 3 Keyword Scheduling, MILP, Single station, Continuous, Discrete 1 Introduction The last few decades have seen significant advances in computing power, as well as increased pressure to optimise the efficiency of all aspects of production processes and reduce associated costs. This has naturally led to a significant increase in interest in production planning techniques, both in industry and academia. In general terms, production planning is a decision-making process aimed at determining when, where, how, and what to produce from a given set of products that have defined characteristics and requirements. This process is carried out by managing a set of finite resources and is in most cases subject to time constraints from the outset, as indicated in the reference (Floudas and Lin 2004). Mathematical programming, especially Mixed Integer Linear Programming (MILP), is widely used for production scheduling processes due to its rigour, versatility, and extensive modelling capabilities (Floudas and Lin 2005). Models assessing scheduling for a single station are commonly encountered in this field, mainly because they are highly applicable in three primary scenarios. The initial challenge lies with intricate multi-stage problems that can be deconstructed into simpler, self-reliant, or loosely connected single-stage problems (Pinto and Grossmann 1995); thus, handling production planning in a modular manner. The second application area is in systems where a station acts as a significant bottleneck. In such cases, production planning for the particular station is critical for the entire system. Consequently, this planning can be extended to the remaining stations (Díaz-Ramírez and Huertas 2018; Elekidis etal. 2019; Marchetti and Cerdá 2009a). Ultimately, it is relevant to issues with a solitary station (Aguirre and Papageorgiou 2018; Méndez and Cerdá 2002). When developing mathematical models, one of the initial decisions to consider is how time should be represented (Floudas and Lin 2005; Sung and Maravelias 2009). Consequently, three primary classes of MILP models are identified: those formulated with a complete planning horizon in discrete time, those formulated in continuous time, and hybrid models. Despite the extensive literature dealing with such problems, there are no studies that analyse, for the same problem, the response of a continuous model and that of a discrete model. Acknowledging the relevance of such problems and the existing gap in the literature to date, this study will introduce two MILP mathematical models to solve the same single station problem, one with continuous time representation and the other with discrete representation. Both models will be tested using a database containing actual time estimates from a factory with these characteristics. The results of this experiment will be presented and compared. The structure of this paper is as follows. Section 2 defines the core problem and situates it within the existing literature. Section3 presents the continuous and discrete models and is further divided into two subsections, one dedicated to each model. Section 4 presents a comprehensive analysis of the results obtained by 1 3 Single station MILP scheduling indiscrete andcontinuous… applying these models and draws important conclusions. Finally, the last section provides a list of all references cited throughout this document. 2 Problem definition As noted previously, there exist three categories of models that are established on the basis of representative time: continuous, discrete, and hybrid models. In the continuous formulation, the planning horizon is partitioned as a component of the optimisation process, allowing the placement of tasks at any point in the timeline (Roslöf et al. 2001; Harjunkoski and Grossmann 2002; He et al. 2017). On the contrary, discrete models are founded on dividing the timeline into different intervals or time units of generally equal size (Liu et al. 2010b; Lee etal. 2002; Mouret et al. 2011). The model is constrained to schedule tasks at specific time points due to this discretization. Less frequently, there are mixed formulations in which discrete periods, such as weeks, are already predetermined within the temporal horizon (Aguirre and Papageorgiou 2018; Liu et al. 2010a; Chen et al. 2008). However, in each of these periods, there is a continuous representation in use. However, according to the review of the literature on MILP models of a single station conducted by Muñoz-Díaz etal. (2022), there are no articles that develop continuous and discrete representations to solve the same problem. This study presents and encodes both versions for future comparison. Once the difference in time representation has been established, the remaining characteristics of the issue and models are specified. This will be identical for both the continuous and the discrete versions. It is essential to note that the problem described in this work is based on a real factory within the metallurgical sector. This factory and its processes have already been studied in the literature (Muñoz-Díaz et al. 2024; Lorenzo-Espejo et al. 2022). Therefore, this research contributes not only to the existing scientific literature, but also to the decision-making process for production planning in an actual facility. Starting with the machinery, in the station under consideration there are parallel machines, all of which have to perform the same operation. However, these machines are not identical, and their production speeds are not proportional. In other words, the production speed depends not only on the machine on which a task is performed but also on the nature of the specific task being performed. This distinction is a key factor that distinguishes single-station models with parallel machines. In this scenario, we encounter a problem with Unrelated Parallel Machines (Brucker 2007), where all machines are capable of processing all jobs. In terms of the objectives of the models, the ultimate goal is always to obtain the assignment of tasks to machines and the sequencing within each machine. However, there are many feasible solutions that fulfil this objective, so it is necessary to establish a criterion for optimisation among all the possible options. This criterion is the objective function of the model and is generally divided into two categories: economic functions and time-based functions (Merchan and Maravelias 2014). In this case, it is a time-based function, specifically minimising the maximum M.-L.Muñoz-Díaz et al. 1 3 completion time or makespan. In other words, the objective is to minimise the time that elapses between the start of processing the first task and the completion of the last. At this point, it is important to emphasise that we are not dealing with batches but with individual units. This implies that there is no need to include the batch formation process in either the model or the objective function, contrary to the approach taken by other authors in similar problems (Berber etal. 2007; Méndez and Cerdá 2003). With the criterion for selecting a production schedule now established, we will proceed to explain the most relevant features in the context of the current problem. The first characteristic to consider is the presence of setups. In production planning models, there are different types of setups: those that depend on the sequence (Liu etal. 2008; Chen etal. 2008), on the machine where the task is to be performed (Sun and Xue 2009; He etal. 2017), on the specific tasks to be processed (Mouret et al. 2011) or on certain resources specific to real plants (Méndez and Cerdá 2002). In this case, we will work with task-dependent setups, specifically based on the sequence of these tasks. In addition, there will be specific mandatory precedence, i.e. there will be pairs of jobs that must be processed on the same machine and in immediate succession. Finally, there will be no consideration of delivery times for jobs, and it will be assumed that the machines are fully available. With all this, we have an Unrelated Parallel Machine Scheduling Problem that can be classified according to Graham et al. (1979) as a R|prec|Cmax , where R means that the machines are Unrelated Parallel Machines, prec refers to the fact that compulsory precedence relations are specified, and finally, Cmax indicates the Objective Function of the problem, minimising the maximum completion time. 3 Mixed integer linear programming models In this section we present the mathematical formulation of the problem described above. First, for the continuous time representation (subsection3.1), and second, for the discrete representation (subsection 3.2). Before that, the common parameters, indices and variables for both models are listed below (Table1). 3.1 Continuous model This section presents the Mixed Linear Programming model in its continuous time representation. As mentioned earlier, this formulation splits the time horizon as part of the optimisation process. In this representation, there are different approaches, typically classified as global-event based (Shaik et al. 2006), unit-specific-event based (Floudas and Lin 2004), slot based (Pan etal. 2009), and precedence based (Marchetti and Cerdá 2009b). In this case, we will focus on the last approach, which 1 3 Single station MILP scheduling indiscrete andcontinuous… Table 1 Common parameters, indices and variables in both MILP models Parametersand indices indices Table 2 Specific variables of the continuous MILP model Table 3 Specific parameters, index and variables of the discrete MILP model M.-L.Muñoz-Díaz et al. 1 3 uses specific variables to represent the start or finish of tasks and binary variables to represent direct precedence relationships between different tasks. The variables used exclusively for this formulation are presented below(Table2). This is followed by the MILP model in its continuous formulation and, finally, an explanation of each of the constraints. The objective function to minimize is stated in Constraint (1) and the Makespan is obtained in Constraints (2). A dummy task is introduced in Constraints (3), which indicate that the dummy task 0 is placed at the beggining of each machine. Constraints (4) ensure that each task has only one immediately previous task, only one immediately subsequent task and is assigned to only one machine, except task 0, the dummy task. Balance equations are included through Constraints (5). Constraints (6) are enforced to guarantee that the mandatory sequences between certain pairs of tasks are fulfilled. Constraints (7) and (8) define the completion (1) Min Cmax (2) s.a. Cmax ≥ Ci∀i=1, 2, ..., T (3) T ∑ j =1 y0jk =1∀ k (4) M ∑ k=1 ∑ i∈T⟍{j} yijk =1∀j=1, 2, ..., T (5) ∑ i∈T⟍{j} yijk = ∑ l∈T⟍{j} yjlk ∀j=1, 2, ..., T;∀k (6) M ∑ k=1 yijk ≥zij ∀i,j=1, 2, ..., T (7) Cj≥Ci+pjk −E(1−yijk)∀j=1, 2, ..., T;∀i;∀k (8) C0=0 (9) yijk ∈{0, 1}∀i,j,k (10) Ci≥0∀i (11) Cmax ≥0 1 3 Single station MILP scheduling indiscrete andcontinuous… time of all tasks. Finally, Constraints (9), (10) and (11) are the basic restrictions on the decision variables. In assessing the scale of the mathematical model under consideration, the order of magnitude of the number of constraints and variables deserves attention. The number of constraints can be expressed as T2 ⋅M+T2+4⋅T⋅M+3⋅T+2⋅M+3 , while the number of variables can be given by T2 ⋅M+2⋅T⋅M+T+M+2 . This implies a polynomial growth pattern where the number of constraints in the model has a complexity of O(T2 ⋅ M) and the number of variables has a complexity of O(T2 ⋅ M) . Such a characterisation illustrates the increase in constraints and variables concerning the dimensions T and M within the model. 3.2 Discrete model In this section we present the Mixed Linear Programming model in its discrete time representation. As mentioned earlier, in these models the partitioning of the time horizon is a task that takes place before and outside of the optimisation process. This implies constraints on the times at which each job can start (Burkard and Hatzl 2005), as the points on the horizon where the start of each job can be planned are fixed and no intermediate points can be chosen. In this case, for this discretisation, a practical upper bound ( Wmax ) is used to determine the length of the time horizon. In addition, a time period (U) is used to define the size of each time interval within the horizon, [U−1, U] . In this research, U corresponds to a time interval of 30min. Next, we present the parameters, index and variables used exclusively for this discrete formulation (Table 3). We then present the MILP model in its discrete formulation, and finally, an explanation of each of the constraints. (12) Min Cmax (13) s.a. Cmax ≥Ci∀i (14) M ∑ k =1 ∑ u∈W ik yiuk =1∀ i (15) T ∑ i =1 u ∑ v = u − pik +1 yivk ≤1∀k;∀u∈{1, ..., Wmax } (16) y ( i +1)( u + pik ) k≥yiuk −E(1−zi ( i +1) )∀i∈{1, ..., T−1},∀k,∀u; M.-L.Muñoz-Díaz et al. 1 3 The objective function to minimize is stated in Constraint (12) and the Makespan is obtained in Constraints (13). Constraints (14) require each task to be started exactly once and Constraints (15) ensure that at a given time period u, only one task can be executed on each machine. Constraints (16) are enforced to guarantee that the mandatory sequences between certain pairs of tasks are fulfilled. Constraints (17) define the completion time of all tasks and Constraints (18), (19) and (20) are the basic restrictions on the decision variables. When assessing the scale of the mathematical model under consideration, the order of magnitude of the number of constraints and variables needs to be examined. The number of constraints is expressed as T ⋅M⋅W max +T 2 ⋅M+4⋅T+ 1 , while the number of variables is given by T ⋅ M ⋅ Wmax +T+1 . This implies a polynomial growth pattern, where the number of constraints has a complexity of O (T⋅M⋅W max) , since Wmax is necessarily greater than T, and the number of variables has a complexity of O (T⋅M⋅W max) . Such a characterisation illustrates the increasing constraints and variables concerning the dimensions T, M and Wmax within this model. 4 Results andconclusions As mentioned above, the problem described is based on a real production planning problem in a metallurgical plant. This has allowed the use of time estimations derived from the actual historical data of the factory. In addition to the time estimations, the priority relationships are also based on a real project, and the different configurations represent situations of interest to this industry. These configurations are characterised by the number of machines available for task processing, shown in the column M, and the number of tasks to be scheduled, shown in the column T. Configurations with 2, 4 and 6 machines were chosen, and for each of these 20, 40, 80 and 160 tasks were considered, giving a total of 12 configurations. All were run for both models, with the same processing times for each task and the same priority relationships for each configuration. A time limit of 2h was also implemented as a time constraint for model execution. When this limit was reached, the model stopped and returned the best solution achieved up to that point, together with the corresponding makespan. In cases where this measure was implemented, the column Runtime in Table4 contains the (17) C i= [M ∑ k=1 ∑ u∈W ik yiuk.(u+pik) ] −1∀ i (18) yijk ∈{0, 1}∀i,j,k (19) Ci≥0∀i (20) Cmax ≥0 1 3 Single station MILP scheduling indiscrete andcontinuous… abbreviation LR (limit reached). In order to facilitate the interpretation of the results, for each of the twelve configurations, the best result in terms of makespan, i.e. the lowest maximum completion time between both models, has been highlighted in bold. Both models have been implemented in Python and solved on an Intel® Core™ i7-4790 CPU at 3.60 GHz with 12 GB of RAM using Gurobi Optimizer v9.1.1. These results are analysed in more detail in the following, with the aim of responding to as wide a range of situations as possible. Strictly considering the makespan, which is the only objective in both objective functions (Constraints 1 and 12), it is evident that the continuous model gives better results in all cases. In fact, the results show that the makespan of the discrete model is higher than that of the continuous model, ranging from 3.2% (M = 4, T = 20 and M = 6, T = 40) to 18% (M = 2, T = 160). This result is consistent with the implications of the time discretisation itself, because even if both models were to choose exactly the same scheduling, it is highly likely that the discrete model would result in a higher makespan. This is due to the losses incurred in assigning tasks with real processing times, which may not be multiples of U, to time intervals of duration U. In most cases, this will result in idle times in the last interval in which each task is assigned in the discrete model. To illustrate this concept, consider a simple example Table 4 Comparison of Makespans (hours) and runtimes (seconds) obtained for the 12 configurations in the continuous and discrete models. LR: limit reached (2h/7200s) M T Continuous model Discrete model Makespan (h) Runtime (s) Makespan (h) Runtime (s) 2 20 47.3897 0.1359 49.5000 3.8118 40 98.6939 0.6057 104.5000 69.3254 80 190.5366 26.2331 204.0000 LR 160 375.4440 LR 443.0000 LR 4 20 40.6574 0.1659 42.0000 2.6155 40 48.0537 0.6876 51.5000 52.6859 80 87.5284 4.4235 91.0000 1686.0407 160 173.8521 LR 202.0000 LR 620 31.7948 0.2019 34.5000 3.8138 40 40.6575 0.8925 42.0000 54.7838 80 62.2815 9.0968 69.0000 1070.8293 160 99.4577 LR 106.0000 5148.3380 Fig. 1 Gantt chart of the continuous and discrete models for two identical tasks (A1 and A2) following the same sequence