# The Synchronized and Integrated Two-Level Lot Sizing and Scheduling Problem: Evaluating the Generalized Mathematical Model

Authors: Claudio F. M. Toledo; Alf Kimms; Paulo M. França; Reinaldo Morabito
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper presents the synchronized and integrated two-level lot sizing and scheduling problem (SITLSP). This problem is found in beverage production, foundry, glass industry, and electrofused grains, where the production processes have usually two interdependent levels with sequence-dependent setups in each level. For instance, in the first level of soft drink production, raw materials are stored in tanks flowing to production lines in the second level. The amount and the time the raw materials and products have to be stored and produced should be determined. A synchronization problem occurs because the production in lines and the storage in tanks have to be compatible with each other throughout the time horizon. The SITLSP and its mathematical model are described in detail by this paper. The lack of similar models in the literature has led us to also propose a set of instances for the SITLSP, based on data provided by a soft drink company. Thus, a set of benchmark results for these problem instances are established using an exact method available in an optimization package. Moreover, results for two relaxations proved that the modeling methodology could be useful in real-world applications.


---

## Body

## 1. Introduction

The problem studied in this paper is motivated by a real situation found in soft drink companies. In the bottling industry, production involves two interdependent levels with decisions about raw material storage in tanks and soft drink bottling in lines. In the first level, decisions regarding the amount and time the raw materials have to be stored in each one of the available tanks should be made. Similarly, in the second level, the lot size of each demanded item and its corresponding scheduling in each line should be determined. A capacitated lot sizing and scheduling problem has to be solved on each one of these two levels (Figure1). This problem covers various issues of lot sizing and scheduling that have been dealt with on isolation only in the literature before. The challenging aspect is the combination of all these issues in one interdependent two-level problem. Capacitated lot sizing (and scheduling) is a topic of broad interest and has attracted many researchers. While capacitated lot sizing (and scheduling) is an NP-hard optimization problem [1, 2], the problem of finding a feasible solution is NP-complete already [3], if setup times are present.Figure 1
The two-level production process.One of the few optimal procedures for solving lot sizing and scheduling problems with sequence-dependent setup times can be found in Haase and Kimms [4]. Kovács et al. (2009) presented a more compact model based on the previous one proposed by Haase and Kimms [4], which allows solving larger instances within a reasonable computation time. Luche et al. [5] and Clark et al. [6] presented mixed integer programming (MIP) models for lot sizing and scheduling in the presence of setup times for problems found in electrofused grain and animal nutrition industries. Concerning multilevel lot sizing problems, several publications exist (e.g., [7–10]). The present paper deals with a multilevel lot sizing and scheduling problem, which is difficult to tackle even if the capacity is unlimited [11, 12], and there are parallel machines represented by production lines (Figure 1). The work in de Matta and Guignard [13] deals with rolling production schedules for lot sizing with parallel machines. A study on sequence-dependent setup costs with parallel machines is found in Kang et al. [14]. A lot sizing problem in a semiconductor assembly with parallel machines was described by Kuhn and Quadt [15] and Quadt and Kuhn [16]. A GRASP heuristic with path-relinking intensification was applied by Nascimento et al. [17] to solve instances of the capacitated lot sizing problem with parallel machines.A. R. Clark and S. J. Clark [18] proposed a MIP formulation for a lot sizing and scheduling problem on parallel machines with sequence-dependent setup times. Their complex MIP formulation was solved using approximate models in a rolling horizon basis with a reduced number of binary variables per period. Model reformulations were also presented by Wolsey [19] to make standard software applicable. Clark [20] presented a mathematical model for the planning of a canning line in a drinks manufacturer. He proposed approaches using local search integrated with the solution of approximate MIP models. Gupta and Magnusson [21] presented a model for the capacitated lot sizing and scheduling problem with sequence-dependent setup costs and nonzero setup times. The solver CPLEX was used to find optimal solutions for small sized instances. The authors also determined lower bounds for large sized instances using row aggregation and relaxing the integrality of some model variables. Almada-Lobo et al. [22] proposed models for the same problem tackled by Gupta and Magnusson [21], which were solved using specific-purpose heuristics and the CPLEX solver.A synchronization problem arises in a two-level problem reported by Almada-Lobo et al. [23] and Toledo et al. [24]. Their focus is a glass container industry where the first level deals with the glass color produced in the furnaces and the second level deals with the color of the containers that are produced afterwards. MIP formulations are tailored to tackle this two-level and synchronized production planning problem where metaheuristic approaches are proposed. Baldo et al. [25] studied another two-level problem in the brewery industry: preparing the liquids including fermentation and maturation inside the fermentation tanks and bottling the liquids on the filling lines. The problem differs from soft drink problems mainly due to the relatively long lead times required for the fermentation and maturation processes and because the ready liquid can remain in the tanks for some time before being bottled. The surveys in Drexl and Kimms [26], Karimi et al. [27], Jans and Degraeve [28, 29], and Ramezanian et al. [30] can be referred to for complete overviews in lot sizing problems and industrial modeling for lot sizing problems.A work that comes close to our case is the one described in Meyr [31], which is an extension of Meyr [32]. Meyr [31] considered a lot sizing and scheduling problem with nonidentical parallel machines, inventory costs, production costs, and sequence-dependent setup times and costs. However, the soft drink industry problem in the present paper is more complex in the sense that it has two lot sizing and scheduling problems, each of them similar to Meyr’s problem, one for lines and another for tanks. The problem solution should find simultaneously the lot sizing and scheduling of raw materials in tanks and soft drinks in the bottling lines, because there is interdependence between these two levels, which is not present in Meyr’s approach. Thus, new variables and constraints able to synchronize and integrate these two levels need to be added. There are studies dealing with supply chain synchronization or integration applied to decentralized manufacturers [33]. However, the synchronization aspect dealt with by the present paper is closer to the work of Tempelmeier and Buschkühl [34]. These authors introduced a synchronization problem in a multi-item multimachine lot sizing and scheduling problem. This problem is found in the production system of automobile suppliers. There is a predetermined assignment of products to machines where a common resource is necessary for setup processes on all machines.Bearing in mind the mentioned aspects, the problem studied by the present paper is called synchronized and integrated two-level lot sizing and scheduling problem (SITLSP). Some works related with the specific soft drink industrial situation considered by the SITLSP have been published recently. For instance, in Ferreira et al. [35], a simplified formulation was presented for the SITLSP, where each bottling line has a dedicated tank and each tank can be filled with all liquid flavors needed by this line. Single-stage formulations were presented in Ferreira et al. [36] based on the general lot sizing and scheduling problem (GLSP) and on the asymmetric travelling salesman problem (ATSP). The solutions found using these formulations outperformed those found by solving the formulation described in Ferreira et al. [35]. Toledo et al. [37] introduced a genetic algorithm/mathematical programming approach using Ferreira et al.’s [35] model, which reached competitive or better solutions for the real-world instances solved in Ferreira et al. [36]. All these recent results assume the hypotheses of dedicated tanks. In our formulation, there are no dedicated tanks, as it will be explained later.There are no existing modeling approaches to be directly applicable that include all the issues simultaneously considered: lot sizing, scheduling, setup (time and cost), parallel machines, among others. Thus, formulating a specific model seems to be in order. In Toledo et al. [38] we have already presented a related formulation of this paper (in Portuguese) in a very compact form, but now we spend a lot of effort to explain all the model constraints, providing details about their meanings and interpretations. An effective method to deal with all the aspects considered by the SITLSP was first proposed by Toledo et al. [39]. This method based on a multipopulation genetic algorithm with individuals hierarchically structured in trees was able to solve instances with several levels of difficulty based on data provided by a soft drink industry and the solutions were compared with AMPL/CPLEX solutions reported on that paper.To sum up, the main contributions of this paper are to present in detail a mathematical formulation for the SITLP, to evaluate its performance solving real-world problem instances, and to define sets of benchmark instances for the SITLSP. A mathematical model serves many purposes as to provide an unequivocal definition of the problem better than a textual description can do. The present paper combines ideas from the general lot sizing and scheduling problem (GLSP) with the continuous setup lot sizing problem (CSLP) [26] to describe the SITLSP. The model is coded next and sets of small (artificially created) instances are solved using commercial software packages to find optimum solutions which can be used, for example, as benchmark to evaluate heuristics proposed for the same problem. Finally, medium-to-large instances are created and solved, applying some relaxation over the formulation when the optimal or even a feasible solution can be found by the exact method.In the next section, we describe the industrial problem in detail with some examples that will help us to explain many specific problem issues. In the section on Mathematical Models, a MIP model is presented for the SITLSP. In section on Computational Results, we show some computational results obtained by solving the model with the modeling language AMPL in combination with the CPLEX solver. Finally, in Conclusions we present concluding remarks and discuss perspectives for future research.


## 2. The Industrial Problem

To make the explanation easier, the problem is posed as a soft drink industrial problem. Taking this into account, what it is referred to as product in the problem is the combination of the soft drink flavor and the type of container. Each of the soft drinks is available in one or more bottle types, such as glass bottles, plastic bottles, cans or bag-in-boxes of different sizes. In general, only a subset of the bottling lines is capable of producing a certain product, and products can be produced using production lines in parallel. Various products share a common production line, which cannot produce more than one product at a time. However, whenever the product switches, a setup time (of up to several hours) is required to prepare the production line for the next product. Production lines can maintain the setup state. When the production of a product is preempted for a while and continued after some idle time, then no setup is required. Setup times are sequence-dependent, meaning that the order in which products are produced affects the required time to perform a setup.Let us take an example considering a time horizon of 2 periods for a production process with 5 raw materials, 6 products, 3 tanks, and 3 lines. Each time period has 5 time units of capacity. Suppose the following:(i)
RmA (raw material A) produces P1 (product 1).(ii)
RmB produces P2 and P3.(iii)
RmC produces P4.(iv)
RmD produces P5.(v)
RmE produces P6.(vi)
L1 (line 1) can bottle P1, P2, and P3.(vii)
L2 can bottle P1, P4, and P5.(viii)
L3 can bottle P1 and P6.(ix)
Tk1 (tank 1) can store RmA, RmB, and RmC.(x)
Tk2 can store RmA, RmB, RmC, and RmD.(xi)
Tk3 can store RmE.In the first time period, the demands of products are 100 units ofP1, P4, and P6 and 50 units of P5. In the second time period, the demands are 100 units of P2 and P3 and 50 units of P4 and P5. We are mentioning only relevant data for this example. Figure 2 shows a possible schedule for a production line level taking into account the line constraints as explained before.Figure 2
Schedule for the production line level.The processing time for each product to be produced is shown in Figure2. The assignments satisfied the set of products allowed to be produced in each line and the demands in each period. There are also sequence-dependent setup times from product P2 to P3 in L1 and from P4 to P5 in L2. This schedule only pays attention to the line constraints, but it does not take into account the tank constraints discussed next.The raw material (i.e., the soft drink) that is bottled in a production line comes from a storage tank with limited storage capacity. Different soft drinks cannot be put in a tank simultaneously. Hence, from time to time a tank must be filled with a particular soft drink, which might be another drink or the same as before. Nevertheless, whenever a tank is filled, a significant (sequence-dependent) setup time occurs to clean and fill the tank, even if the same soft drink is filled into the tank as before. For technical reasons, a tank can only be filled up when it is empty. During the time of filling up a tank, nothing can be pumped to a production line from that tank. There is no fixed assignment between tanks and production lines. Every tank can be connected to every production line and a tank can feed more than one production line.In the previous example, let us assume that all tanks have 100 L (liters) of maximum storage capacity. Suppose that 2 L ofRmA is necessary to produce 1 u (unit) of P1, 0.5 L of RmB for 1 u of P2 and 1 u of P3, 1 L of RmC for P4, 2 L of RmD for P5, and 1 L of RmE for P6. Figure 3 shows a possible schedule considering the tank constraints.Figure 3
Schedule for tank level.A total of 200 L ofRmA to produce 100 u of P1 is necessary. Therefore, tank Tk1 must be refilled with RmA and the setup times are shown in Figure 3. The interdependence between the two levels of the problems becomes clear now. The schedule in Figure 3 cannot be created without knowing the line schedule in Figure 2. For instance, it is necessary to know when 100 u of P1 are scheduled on L1 to fill Tk1 with RmA. This also happens in Tk2 where it is necessary to know when P4 is scheduled on L2 to fill Tk2 with RmD. The schedules proposed in Figures 2 and 3 cannot be executed without repairs. The same problem would happen, if we had scheduled the tank level first. Figure 4 illustrates a possible repair that swapped product P4 for P5 from the schedules in Figures 2 and 3.Figure 4
Occupation for tank and line slots.Bottling is usually done to meet a given demand (per week) with a production planning horizon of four weeks in particular soft drink companies. The decision maker has to find out how many units of what product should be produced when and on what production line. To be able to do so, the tanks must be filled appropriately. The objective can include the minimization of the total sum of setups, inventory holding and production costs. Thus, there is a multilevel (two level) lot sizing and scheduling problem with parallel processors (tanks on the first level and lines on the second), capacity constraints, and sequence-dependent setup times and costs. The mathematical model proposed by this paper in the next section has to integrate these two lot sizing and scheduling problems. The production in lines and the storage in tanks must be compatible with each other.


## 3. A Model Formulation

This section introduces the mathematical model formulation for the SITLSP. First, the basic ideas used by our formulation are described. Next, the objective function as well as each one of the model constraints is explained. Finally, an example is used to show the type of information returned by the model solution.


### 3.1. Basic Ideas

The underlying idea for modeling our application combines issues from the general lot sizing and scheduling problem (GLSP) and the so-called continuous setup lot sizing problem (CSLP) (see [26] for a comparison of these models). A set of additional variables and constraints are also included in the model, which can describe the specific issues of the SITLSP.From the GLSP, we adopt the idea of defining a fixed number (S for the production lines and S¯ for the tanks) of slots per (macro-) period, so that at most one product or raw material can be scheduled per slot. What needs to be determined is for what product or raw material, respectively, a particular slot should be reserved in lines and tanks, and what lot size (a lot of size zero is possible) should be effectively scheduled, given a valid slot reservation. Let us take the schedule shown in Figures 2 and 3. Suppose now 2 macro-periods with S=S¯=2 slots per period. Figure 4 shows only the simultaneous slot reservation for lines and tanks in each period.The number of products in lines and raw materials in tanks cannot be greater than the total number of slots (S=S¯=2) in each macro-period. There is not a full slot occupation in Figure 4. For instance, only one slot is effectively occupied by raw materials and products, respectively, in tank Tk3 and line L3 during the first macro-period. In the second macro-period, there is no slot occupied in Tk3 and L3. Following the GLSP idea, these two slots are reserved (P6 in line L3 and RmE in tank Tk3), but nothing is produced.The use of slots in the model enables us to describe lines and tank occupation using variables and constraints indexed by slots. Therefore, we can define decision variables likexjls=1, if slot s in line l can be used to produce product j, 0, otherwise; and uls=1, if a positive production amount is effectively produced in slot s in production line l (0, otherwise). In the same way, we have decision variables like x¯jks = 1, if slot s can be used to fill raw material j in tank k, 0, otherwise; and u¯ks = 1, if slot s is used to fill raw material in tank k, 0, otherwise. These variables (and others) will define constraints for the correct line (or tank) occupation, the reservation of only one product (raw material) per slot, and the effective production (storage) of products (raw materials) (see model constraints (2)–(10) and (30)–(39) in the next subsections).In the SITLSP, the slots scheduled on one level with the slots scheduled on the other level need to be coordinated. For instance, a production line level, which must wait for a setup time on the tank level, requires the tank setup time to be ready at least one small time unit before the production to start in the line level. For that reason, we introduce small micro-periods in a CSLP-like manner. The macro-periods are divided into a fixed number of small micro-periods with the same capacity. This capacity can be partially used, but the same micro-period cannot be occupied by two slots. Let us illustrate this idea in Figure5, which synchronizes lines and tanks from Figure 4.Figure 5
Synchronization between slots in lines and tanks.Each macro-period was divided into 5 micro-periods with the same length. In the first period, the production ofP1, P4, and P6 must start after the initial setup time of RmA, RmC, and RmE, respectively. The raw material must be previously ready in the tank so that the production begins in lines. The setup time needed to refill Tk1 with RmA and Tk2 with RmD leads to an interruption of P1 and P5 production in lines L1 and L2, respectively. In the second period, there is an idle time in L2 after P5. Line L2 is ready to produce P4 after its setup time, but the production has to wait for the RmC setup time in Tk2.Variables and constraints indexed by slots and micro-periods will enable us to describe these situations. Binary variablesx¯lsτB and x¯lsτE indicate the micro-period τ when the production of slot s begins or when it ends in line l, respectively. The analogous variables x¯ksτB and x¯ksτE are used to indicate micro-period τ on slot s of tank k. It is also necessary to define linking variables qkjlsτ, which determine the amount of product j produced in line l in micro-period τ on slot s, using raw material from tank k. These variables (and others) establish constraints which link production lines and tanks and synchronize raw material and product slots (see model constraints (25)–(27), (40), and (64) in the next subsections).The model constraints are formally defined in the next subsections. Table1 has already separated them according to the meaning, making it easier to understand.Table 1
Guideline for line and tank constraints.
Line constraints
Tank constraints
Meaning
(2)
(30)
Assignments not allowed for lines and tanks
(3)
(31)
Assignments of products or raw materials to slots
(4), (16), and (17)
(32)–(34)
Link between the products or raw material assignments and the respective lot size produced or stored.
(7)
(35) and (36)
Products or raw materials changeover.
(8) and (9)
(37) and (38)
Changeover setup time
(10)
(39)
Macro-period capacity
(5) and (6)
(64) and (65)
Inventory balance
(11)–(13)
(41)–(43)
Available capacity between endings of two consecutive slots.
(14) and (15)
(44)–(47)
Define only one beginning and only one ending for each slot.
(18)–(21), (23)–(24)
(51)–(57), (59)–(61)
Define the beginning and the ending for a slot effectively used or not.
(22)
(58)
Define an order for slot occupation
(25), (28), and (29)
(40), (48), (64), and (65)
Synchronize when a slot of raw material is taken from tanks and produced by lines.
(26) and (27)
—
Use of the capacity of the first micro-period of each slot.
—
(62), (63), and (65)
Refilling of tanks


### 3.2. Objective Function

Suppose that we haveJ¯ raw materials and J products, L production lines, and L¯ tanks. The planning horizon is subdivided into T macro-periods. For the modeling reasons explained before, we assume that at most S slots per macro-period can be scheduled on each production line, and at most S¯ slots per macro-period and per tank can be scheduled. These slot values can be set to sufficiently large numbers so that this assumption is not restrictive for practical purposes. Furthermore, for the same modeling reasons explained before, we assume that each macro-period is subdivided into Tm micro-periods. The notation being used in the model description is summarized in the appendix.As usual in lot sizing models, the objective is to minimize the total sum of setup costs, inventory holding costs and production costs. The first three terms in expression (1) represent setup, holding, and production costs for production lines and the next three the same costs for tanks. Notice that a feasible solution, which fulfills all the demand right in time without violating all constraints to be described, may not exist. Hence, we allow that qj0 units of the demand for product j may not be produced to ensure that the model can always be solved (last term in (1)). Of course, a very high penalty M is attached to such shortages so that whenever there is a feasible solution that fulfills all the demands, we would prefer this one:(1)∑i=1J∑j=1J∑l=1L∑s=1T·Ssijlzijls+∑j=1J∑t=1ThjIjt+∑j=1J∑l=1L∑s=1T·Svjlqjls+∑i=1J¯∑j=1J¯∑k=1L¯∑s=1T·S¯s¯ijlz¯ijls+∑j=1J¯∑k=1L¯∑t=1Th¯jI¯jk,t·Tm+∑j=1J¯∑k=1L¯∑s=1T·S¯v¯jlq¯jks+M∑j=1Jqj0.


### 3.3. Production Line: Usual Constraints

First, constraints for the production line level are presented which are usually found in lot sizing and scheduling problems:(2)xjls=0j=1,…,J;l∈1,…,L∖Lj;s=1,…,T·S,(3)∑j=1Jxjls=1l=1,…,L;s=1,…,T·S,(4)pjlqjls≤Cxjlsj=1,…,J;l=1,…,L;s=1,…,T·S,(5)Ij1=Ij0+qj0+∑l=1L∑s=1Sqjls-dj1j=1,…,J;(6)Ijt=Ij,t-1+∑l=1L∑s=t-1S+1t·Sqjls-djtj=1,…,J;t=2,…,T,(7)zijls≥xjls+xil,s-1-1i,j=1,…,J;l=1,…,L;s=1,…,T·S,(8)σls=∑i=1J∑j=1Jσijl′zijlsi,j=1,…,J;l=1,…,L;s=1,…,T·S,(9)ωlt≤σl,t-1S+1l=1,…,L;t=1,…,T;(10)∑s=t-1S+1t·Sσls+∑j=1Jpjlqjls≤C+ωltl=1,…,L;t=1,…,T.A particular product can be produced on some lines, but not on all in general (2) and only one product j is produced in each slot s of line l(3). The available time per macro-period is an upper bound on the time for production (4). The inventory balancing constraints (5) and (6) ensure that all demands are met taking into account the dummy variable qj0. Constraint (7) defines the setup times (zijls indicates this) based on slot reservations (xjls). Thus, it is possible to determine the setup time σls to be included just in front of a certain slot (8). As a result, overlapping setup can happen and, for the first slot of a macro-period t, some setup time ωlt may be at the end of the previous macro-period (9). The capacity C in constraint (10) has to be incremented by ωlt. Thus, the total sum of production and setup times in a certain macro-period must not exceed the macro-period capacity C by constraint (10).


### 3.4. Production Line: Time Slot Constraints

The constraints showed next describe how to integrate the micro-period idea from CLSP and the slot idea from GLSP. The main point here is to define specific constraints for the SITLSP which describe when some slots in lines will be used throughout the time horizon(11)t·C-∑τ=t-1Tm+1t·TmCmτxl,t·S,τE≥ωl,t+1l=1,…,L;t=1,…,T-1,(12)∑τ=t-1Tm+1t·TmCmτxlsτE-∑τ=t-1Tm+1t·TmCmτxl,s-1,τE≥σls+∑j=1Jpjlqjlsl=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(13)∑τ=t-1Tm+1t·TmCmτxl,t-1S+1,τE≥t-1C+σl,t-1S+1-ωlt+∑j=1Jpjlqjl,t-1S+1l=1,…,L;t=1,…,T;s=1,…,T·S,(14)∑τ=t-1Tm+1t·TmxlsτE=1l=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(15)∑τ=t-1Tm+1t·TmxlsτB=1l=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(16)∑j=1Jpjlqjls≤Culsl=1,…,L;s=1,…,T·S,(17)εuls≤∑j=1Jqjlsl=1,…,L;s=1,…,T·S,(18)∑τ=t-1Tm+1t·TmτxlsτE-∑τ=t-1Tm+1t·TmτxlsτB≤Tmulsl=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(19)∑τ=t-1Tm+1t·TmτxlsτB-∑τ=t-1Tm+1t·TmτxlsτE≤ulsl=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(20)∑τ=t-1Tm+1t·TmτxlsτB-∑τ=t-1Tm+1t·Tmτxl,s-1,τE≤Tmulsl=1,…,L;t=1,…,T;s=t-1S+2,…,T·S,(21)∑τ=t-1Tm+1t·Tmτxl,t-1S+1,τB-t-1Tm+1≤Tmul,t-1S+1l=1,…,L;t=1,…,T,(22)uls≥ul,s+1l=1,…,L;t=1,…,T;s=t-1S+1,…,T·S-1,(23)εuls+∑τ=t-1Tm+1t·TmCmτxlsτE-∑τ=t-1Tm+1t·TmCmτxlsτB≤∑j=1Jpjlqjlsl=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(24)∑τ=t-1Tm+1t·TmCmτxlsτE-∑τ=t-1Tm+1t·TmCmτxlsτB≥∑j=1Jpjlqjls-Cml=1,…,L;t=1,…,T;s=t-1S+1,…,T·S.The end of the last lot in some previous macro-periodt must leave sufficient time for the setup time ωlt+1 (11). The same time slot control enables us to constrain that the finishing time of one slot, minus the finishing time of the previous slot, must be at least as large as the production time in the corresponding slot, plus the required setup time in advance (12)-(13). Figure 6 illustrates the situation described by these constraints with S=2 and s=s1,s2,s3,s4; τ=1,2,…,10; t=1,2; Cm=1 and C=5.Figure 6
Keeping enough time between slots.There is only one possible beginning and end for each slot in the time horizon (14)-(15). While xjls indicates whether or not a certain slot is reserved to produce a particular product, uls indicates whether or not that slot is indeed used to schedule a lot. If the slot is not used, then the lot size must be zero (16); otherwise, at least a small amount ε must be produced (17). Time cannot be allocated for slots not effectively used (uls=0), so xlsτB=xlsτE must occur for the same micro-period τ (18)-(19). To avoid redundancy in the model, whenever a slot is not used, it should start as soon as the previous slot ends (20)-(21). The possibly empty slots in a macro-period will be the last ones in that macro-period (22). The start and end of a slot are chosen in such a way that the start indicates the first micro-period in which the lot is produced, if there is a real lot for that slot, and the end indicates the last micro-period (23)-(24). Figure 7 illustrates the situation described by these two constraints.Figure 7
Time window for production.The termε·uls in constraint (23) and the term ∑j=1Jpjlqjls-Cm in constraint (24) only matter for the case when the first and last micro-periods of a slot are the same. Notice that the processing time of P3 in Figure 7 is smaller than the micro-period capacity in constraint (24). However, constraint (23) ensures that a positive amount will be produced because we must have uL1,P3=1 by constraint (16).


### 3.5. Production Line: Synchronization Constraints

The model must describe how the raw materials in tanks are handled by production lines(25)qjls=∑k=1L¯∑τ=t-1Tm+1t·Tmqkjlsτ,l=1,…,L; t=1,…,T; s=t-1S+1,…,T·S, τ=t-1Tm+1,…,t·Tm, (26)δls=∑τ=t-1Tm+1t·TmτxlsτE-∑τ=t-1Tm+1t·Tmτxl,s-1,τB+1Cm-∑j=1Jpjlqjls,l=1,…,L; t=1,…,T; s=t-1S+2,…,T·S, τ=t-1Tm+1,…,t·Tm,(27)∑k=1L¯∑j=1Jpjlqkjlsτ≤Cm-δls+1-xlsτBCm,l=1,…,L; t=1,…,T; s=t-1S+1,…,T·S, τ=t-1Tm+1,…,t·Tm,(28)∑k=1L¯∑j=1Jpjlqkjlsτ≤∑τ′=t-1Tm+1t·TmCmxlsτ′E,l=1,…,L; t=1,…,T; s=t-1S+1,…,T·S, τ=t-1Tm+1,…,t·Tm,(29)∑k=1L¯∑j=1Jpjlqkjlsτ≤∑τ′=t-1Tm+1t·TmCmxlsτ′B,l=1,…,L; t=1,…,T; s=t-1S+1,…,T·S, τ=t-1Tm+1,…,t·Tm.To link production lines and tanks, we figure out which amount of soft drink being bottled on a line comes from which tank (25). In the first micro-period of a lot, sometimes δls are reserved for setup or idle time, while the remaining time is production time (26) and (27). Of course, the soft drink taken from a tank must be taken during the time window in which the soft drink is filled into bottles (28)-(29). Figure 8 illustrates the situation described by these constraints with Cm=1. Let us suppose that RmA is used to produce P2 and P3.Figure 8
Synchronization of line productions with tank storage.Notice that the processing time ofP3 takes from τ=7 to τ=8. This is considered by constraints (28) and (29).


### 3.6. Tanks: Usual Constraints

Now let us focus on usual lot sizing constraints for the tank level(30)x¯jks=0j=1,…,J¯;k∈1,…,L¯∖L¯j;s=1,…,T·S¯,(31)∑j=1Jx¯jks=1k=1,…,L¯;s=1,…,T·S¯,(32)q¯jks≤Q¯kx¯jksj=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(33)q¯jks≤Q¯ku¯ksj=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(34)∑j=1J¯q¯jks≥Q_ku¯ksj=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(35)z¯ijks≥x¯jks+x¯ik,s-1-2+u¯ksi,j=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(36)x¯jks-x¯jk,s-1≤u¯ksj=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(37)σ¯ks=∑i=1J¯∑j=1J¯σ¯ijk′z¯ijksi,j=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(38)ω¯kts≤σ¯k,t-1S+1i,j=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(39)∑s=t-1S+1t·S¯σ¯ks≤C+ϖkti,j=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯.A particular raw material can be stored in some tanks (30) and tanks can store one raw material at a time (31). The tanks have a maximum capacity (32) and nothing can be stored, whenever the tank slot is not effectively used (33). However, a minimum lot size must be stored if a tank slot is used for some raw material (34). The setup state is not preserved in the tanks, that is, a tank must be setup again (cleaned and filled), even if the same soft drink has been in the tank just before. Care must be taken when setups occur in the model only if the tank is really used, because changing the reservation for a tank does not necessarily mean that a setup takes place (35)-(36). Figure 9 illustrates these constraints.Figure 9
Raw material changeover.From the schedule in Figure9, constraints (31)–(34) define x¯RmB,·Tk2,s4=x¯RmB,Tk2,s3=u¯Tk2,s3=1 and x¯RmD,Tk1,s4=x¯RmD,Tk1,s3=u¯Tk1,s4=1. Moreover, the raw materials scheduled will satisfy constraints (35)-(36). As in the production lines, it is also possible to determine the tank slot setup time (37) and the setup time that may be at the end of the previous macro-period (38)-(39). Thus, the setup time in front of lot s, at the beginning of some period, is the setup time value minus the fraction of setup time spent in the previous periods. This value cannot exceed the macro-period capacity C.


### 3.7. Tanks: Time Slot Constraints

The main point here is to keep control when the tank slots are used throughout the time horizon by production lines. This will help to know when a setup time in tanks will interfere with some production line or from which tanks the lines are taking the raw materials:(40)q¯jks=∑τ=t-1Tm+1t·Tmq¯jksτ,j=1,…,J¯, k=1,…,L¯; t=1,…,T; s=1,…,T·S¯,(41)t·C-∑τ=t-1Tm+1t·TmCmτx¯k,t·S,¯τE≥ϖk,t+1,k=1,…,L¯; t=1,…,T-1;(42)∑τ=t-1Tm+1t·TmCmτx¯ksτE-∑τ=t-1Tm+1t·TmCmτx¯k,s-1,τE≥σ¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+1,…,t·S¯,(43)∑τ=t-1Tm+1t·TmCmτx¯k,t-1S¯+1,τE≥t-1C+σ¯k,t-1·S¯+1-ϖkt,k=1,…,L¯; t=1,…,T,(44)∑τ=t-1Tm+1t·Tmx¯ksτE=1,k=1,…,L¯; t=1,…,T; s=t-1S¯+1,…,t·S¯; τ=t-1Tm+1,…,t·Tm,(45)∑τ=t-1Tm+1t·Tmx¯ksτB=1,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(46)∑τ=t-2Tm+1t·Tmx¯k,t-1S¯+1,τB=1,k=1,…,L¯; t=2,…,T,(47)∑τ=1Tmx¯k1τB=1,k=1,…,L¯; t=2,…,T,(48)∑j=1J¯q¯jksτ≤Q¯kx¯ksτE,k=1,…,L¯; t=1,…,T; s=t-1S¯+1,…,t·S¯; τ=t-1Tm+1,…,t·Tm,(49)∑τ=t-1Tm+1t·Tmτx¯ksτE-∑τ=t-1Tm+1t·Tmτx¯ksτB≤Tmu¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(50)∑τ=t-1Tm+1t·Tmτx¯k,t-1S¯+1,τE-∑τ=t-2Tm+1t·Tmτx¯k,t-1S¯+1,τB≤Tmu¯k,t-1S¯+1,k=1,…,L¯; t=2,…,T;(51)∑τ=1Tmτx¯k1τE-∑τ=1Tmτx¯k1τB≤Tmu¯k1,k=1,…,L¯,(52)∑τ=t-1Tm+1t·Tmτx¯ksτB-∑τ=t-1Tm+1t·Tmτx¯ksτE≤u¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(53)∑τ=t-2Tm+1t·Tmτx¯k,t-1S¯+1,τB-∑τ=t-1Tm+1t·Tmτx¯k,t-1S¯+1,τE≤u¯k,t-1S¯+1,k=1,…,L¯; t=2,…,T;(54)∑τ=1Tmτx¯k1τB-∑τ=1Tmτx¯k1τE≤u¯k1,k=1,…,L¯;(55)∑τ=t-1Tm+1t·Tmτx¯ksτB-∑τ=t-1Tm+1t·Tmτx¯k,s-1,τE≤Tmu¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(56)∑τ=t-1Tm+1t·Tmτx¯k,t-1S¯+1,τB-t-1Tm+1≤Tmu¯k,t-1S¯+1,k=1,…,L¯; t=2,…,T;(57)∑τ=1Tmτx¯k1τB-1≤Tmu¯k1,k=1,…,L¯;(58)u¯ks≥u¯k,s+1,k=1,…,L¯; t=1,…,T; s=t-1S¯+1,…,t·S¯-1;(59)Cmu¯ks+∑τ=t-1Tm+1t·TmCmτ¯xksτE-∑τ=t-1Tm+1t·TmCmτ¯xksτB=σ¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(60)Cmu¯k,t-1S¯+1+∑τ=t-1Tm+1t·TmCmτ¯xk,t-1S¯+1,τE-∑τ=t-2Tm+1t·TmCmτ¯xk,t-1S¯+1,τB=σ¯k,t-1S¯+1,k=1,…,L¯; t=2,…,T;(61)Cmu¯k1+∑τ=1TmCmτ¯xk1τE-∑τ=1TmCmτ¯xk1τB=σ¯k1-ω¯k1,k=1,…,L¯,(62)∑j=1J¯I¯jk,τ-1≤Q¯k1-x¯ksτB+1-u¯ks,k=1,…,L¯; t=1,…,T-1; s=t-1S¯+1,…,t·S¯+1; τ=t-1Tm+1,…,t·Tm,(63)∑j=1J¯I¯jk,τ-1≤Q¯k1-x¯ksτB+1-u¯ks,k=1,…,L¯; s=T-1S¯+1,…,T·S¯+1; τ=T-1Tm+1,…,T·Tm.Most of these constraints are similar to those presented for the production line level. The amount that is filled into a tank must be scheduled, so that the micro-period in which the raw material comes into the tank is known (40). Tank slots must be scheduled in such a way that the setup time that corresponds to a slot fits into the time window between the end of the previous slot and the end of the slot under consideration (41)-(42). The setup for the first slot in a macro-period may overlap the macro-period border to the previous macro-period (43). This is the same idea presented by Figure 6 for lines. The finishing time of a scheduled slot must be unique, as must its starting time (44)–(47). The raw material is available for bottling just when the tank setup is done (48). Therefore, we must have x¯Tk2,s3,7E=x¯Tk2,s4,9E=1 in constraint (48) for the example shown in Figure 10.Figure 10
Tank refill before the end of the setup time.The time window in which a slot is scheduled must be positive if and only if that slot is used to set up the tank (49)–(54). Redundancy can be avoided if empty slots are scheduled right after the end of previous slots (55)–(57). More redundancy can be avoided if we enforce that, within a macro-period, the unused slots are the last ones (58).Without loss of generality, we can assume that the time needed to set up a tank is an integer multiple of the micro-period. Hence, the beginning and end of a slot must be scheduled so that this window equals exactly the time needed to set the tank up (59)–(61). Constraint (61) adds up micro-periods τ=1,…,Tm seeking the beginning and end of the tank setup in slot s¯=1. Finally, a tank can only be set up again if it is empty (62)-(63). Notice that a tank slot reservation (x¯ksτB=1) does not mean that the tank should be previously empty (I¯jkτ-1=0). The tank slot also has to be effectively used (u¯ks=1 and x¯ksτB=1) in (62)-(63). Constraint (63) describes this situation for the last macro-period T where the first slot of the next macro-period is not taken into account.Finally, notice that there are group of equations, as for example, (45)–(47), (49)–(51), (52)–(57), (55)–(57), and (59)–(61), that are derived from the same equations, respectively, (45), (49), (52), (55), and (59). These derived equations are necessary to deal with the first slot and sometimes with the last slot in each macro-period.


### 3.8. Tanks: Synchronization Constraints

The model must describe how the products in production lines are handled by tanks:(64)I¯jkτ=I¯jk,τ-1+∑s=t-1S+1t·Sq¯jksτ-∑i=1J∑l=1L∑s=t-1S+1t·Srjiqkilsτ,j=1,…,J¯, k=1,…,L¯; t=1,…,T; τ=t-1Tm+1,…,t·Tm,(65)I¯jkτ≥∑i=1J∑l=1L∑s=t-1S+1t·Srjiqkils,τ+1,j=1,…,J¯, k=1,…,L¯; t=1,…,T; τ=t-1Tm+1,…,t·Tm-1.What is in the tank at the end of a micro-period must be what was in the tank at the beginning of that micro-period, plus what comes into the tank in that micro-period, minus what is taken from that tank for being bottled in production lines (64). To coordinate the production lines and the tanks, it is required that what is taken out of a tank must have been filled into the tank at least one micro-period ahead (65).


### 3.9. Example

This subsection will present an example to illustrate what kind of information is returned by a model solution. Let us start by the solution illustrated in Figure5. This solution is shown again in Figure 11. Figure 12 presents the same solution considering the model assumptions.Figure 11
Possible solution for SITLSP.Figure 12
Possible solution provided by the model.According to the model, the setup times of the tanks are considered as an integer multiple of the time of a micro-period. For example, the setup time ofRmC in Figure 11 goes from the entire τ=1 (micro-period 1) until part of τ=2 and from the entire τ=8 until part of τ=9. These setup times fit into two complete micro-periods in Figure 12 (see constraints (59)–(61)). The same happens with the setup time of RmB (macro-period 2). The setup time of products in lines L1 and L2 are positioned in front of the next slot as required by constraints (8)–(13), and all the productions in the lines start after the tank setup time is finished (constraints (25), (28)-(29), (40), and (48)).The satisfaction of the model constraints imposes that binary variablesxjls, x¯jks, uls, u¯ks, xlsτB, xlsτE, x¯ksτB, and x¯ksτE must be necessarily active (value 1) for lines, tanks, products, and raw materials in the slots and micro-periods shown in Figure 12. These active variables provide enough information about what and when the products and raw materials are scheduled throughout the time horizon. Moreover, the continuous variables qjls, qkjlsτq¯jksτ, q¯jks must be positive for lines, tanks, products, and raw materials in the same slots and micro-periods.For example, based on Figure12, the model solution has positive variables q¯RmC,Tk2,s4,8 and q¯RmC,Tk2,s4,9 and returns the amount of RmC filled in Tk2 during micro-periods τ=8 and τ=9. The total filled in this slot (s4) is provided by q¯RmC,Tk2,s4. The model variable qTk2,P4,L2,10 returns the amount used by P4 in L2 which is taken from q¯RmC,Tk2,s4. In the same way, qTk1,P3,L1,s4,9 and qTk1,P3,L1,s4,10 have the lot sizes of P3 taken from slot s3 in variable q¯RmB,Tk1,s3. In this case, the total lot size P3 is provided by qP3,L1,s4. All these variables returned by the model will provide enough information to build an integrated and synchronized schedule for lines and tanks.


## 3.1. Basic Ideas

The underlying idea for modeling our application combines issues from the general lot sizing and scheduling problem (GLSP) and the so-called continuous setup lot sizing problem (CSLP) (see [26] for a comparison of these models). A set of additional variables and constraints are also included in the model, which can describe the specific issues of the SITLSP.From the GLSP, we adopt the idea of defining a fixed number (S for the production lines and S¯ for the tanks) of slots per (macro-) period, so that at most one product or raw material can be scheduled per slot. What needs to be determined is for what product or raw material, respectively, a particular slot should be reserved in lines and tanks, and what lot size (a lot of size zero is possible) should be effectively scheduled, given a valid slot reservation. Let us take the schedule shown in Figures 2 and 3. Suppose now 2 macro-periods with S=S¯=2 slots per period. Figure 4 shows only the simultaneous slot reservation for lines and tanks in each period.The number of products in lines and raw materials in tanks cannot be greater than the total number of slots (S=S¯=2) in each macro-period. There is not a full slot occupation in Figure 4. For instance, only one slot is effectively occupied by raw materials and products, respectively, in tank Tk3 and line L3 during the first macro-period. In the second macro-period, there is no slot occupied in Tk3 and L3. Following the GLSP idea, these two slots are reserved (P6 in line L3 and RmE in tank Tk3), but nothing is produced.The use of slots in the model enables us to describe lines and tank occupation using variables and constraints indexed by slots. Therefore, we can define decision variables likexjls=1, if slot s in line l can be used to produce product j, 0, otherwise; and uls=1, if a positive production amount is effectively produced in slot s in production line l (0, otherwise). In the same way, we have decision variables like x¯jks = 1, if slot s can be used to fill raw material j in tank k, 0, otherwise; and u¯ks = 1, if slot s is used to fill raw material in tank k, 0, otherwise. These variables (and others) will define constraints for the correct line (or tank) occupation, the reservation of only one product (raw material) per slot, and the effective production (storage) of products (raw materials) (see model constraints (2)–(10) and (30)–(39) in the next subsections).In the SITLSP, the slots scheduled on one level with the slots scheduled on the other level need to be coordinated. For instance, a production line level, which must wait for a setup time on the tank level, requires the tank setup time to be ready at least one small time unit before the production to start in the line level. For that reason, we introduce small micro-periods in a CSLP-like manner. The macro-periods are divided into a fixed number of small micro-periods with the same capacity. This capacity can be partially used, but the same micro-period cannot be occupied by two slots. Let us illustrate this idea in Figure5, which synchronizes lines and tanks from Figure 4.Figure 5
Synchronization between slots in lines and tanks.Each macro-period was divided into 5 micro-periods with the same length. In the first period, the production ofP1, P4, and P6 must start after the initial setup time of RmA, RmC, and RmE, respectively. The raw material must be previously ready in the tank so that the production begins in lines. The setup time needed to refill Tk1 with RmA and Tk2 with RmD leads to an interruption of P1 and P5 production in lines L1 and L2, respectively. In the second period, there is an idle time in L2 after P5. Line L2 is ready to produce P4 after its setup time, but the production has to wait for the RmC setup time in Tk2.Variables and constraints indexed by slots and micro-periods will enable us to describe these situations. Binary variablesx¯lsτB and x¯lsτE indicate the micro-period τ when the production of slot s begins or when it ends in line l, respectively. The analogous variables x¯ksτB and x¯ksτE are used to indicate micro-period τ on slot s of tank k. It is also necessary to define linking variables qkjlsτ, which determine the amount of product j produced in line l in micro-period τ on slot s, using raw material from tank k. These variables (and others) establish constraints which link production lines and tanks and synchronize raw material and product slots (see model constraints (25)–(27), (40), and (64) in the next subsections).The model constraints are formally defined in the next subsections. Table1 has already separated them according to the meaning, making it easier to understand.Table 1
Guideline for line and tank constraints.
Line constraints
Tank constraints
Meaning
(2)
(30)
Assignments not allowed for lines and tanks
(3)
(31)
Assignments of products or raw materials to slots
(4), (16), and (17)
(32)–(34)
Link between the products or raw material assignments and the respective lot size produced or stored.
(7)
(35) and (36)
Products or raw materials changeover.
(8) and (9)
(37) and (38)
Changeover setup time
(10)
(39)
Macro-period capacity
(5) and (6)
(64) and (65)
Inventory balance
(11)–(13)
(41)–(43)
Available capacity between endings of two consecutive slots.
(14) and (15)
(44)–(47)
Define only one beginning and only one ending for each slot.
(18)–(21), (23)–(24)
(51)–(57), (59)–(61)
Define the beginning and the ending for a slot effectively used or not.
(22)
(58)
Define an order for slot occupation
(25), (28), and (29)
(40), (48), (64), and (65)
Synchronize when a slot of raw material is taken from tanks and produced by lines.
(26) and (27)
—
Use of the capacity of the first micro-period of each slot.
—
(62), (63), and (65)
Refilling of tanks


## 3.2. Objective Function

Suppose that we haveJ¯ raw materials and J products, L production lines, and L¯ tanks. The planning horizon is subdivided into T macro-periods. For the modeling reasons explained before, we assume that at most S slots per macro-period can be scheduled on each production line, and at most S¯ slots per macro-period and per tank can be scheduled. These slot values can be set to sufficiently large numbers so that this assumption is not restrictive for practical purposes. Furthermore, for the same modeling reasons explained before, we assume that each macro-period is subdivided into Tm micro-periods. The notation being used in the model description is summarized in the appendix.As usual in lot sizing models, the objective is to minimize the total sum of setup costs, inventory holding costs and production costs. The first three terms in expression (1) represent setup, holding, and production costs for production lines and the next three the same costs for tanks. Notice that a feasible solution, which fulfills all the demand right in time without violating all constraints to be described, may not exist. Hence, we allow that qj0 units of the demand for product j may not be produced to ensure that the model can always be solved (last term in (1)). Of course, a very high penalty M is attached to such shortages so that whenever there is a feasible solution that fulfills all the demands, we would prefer this one:(1)∑i=1J∑j=1J∑l=1L∑s=1T·Ssijlzijls+∑j=1J∑t=1ThjIjt+∑j=1J∑l=1L∑s=1T·Svjlqjls+∑i=1J¯∑j=1J¯∑k=1L¯∑s=1T·S¯s¯ijlz¯ijls+∑j=1J¯∑k=1L¯∑t=1Th¯jI¯jk,t·Tm+∑j=1J¯∑k=1L¯∑s=1T·S¯v¯jlq¯jks+M∑j=1Jqj0.


## 3.3. Production Line: Usual Constraints

First, constraints for the production line level are presented which are usually found in lot sizing and scheduling problems:(2)xjls=0j=1,…,J;l∈1,…,L∖Lj;s=1,…,T·S,(3)∑j=1Jxjls=1l=1,…,L;s=1,…,T·S,(4)pjlqjls≤Cxjlsj=1,…,J;l=1,…,L;s=1,…,T·S,(5)Ij1=Ij0+qj0+∑l=1L∑s=1Sqjls-dj1j=1,…,J;(6)Ijt=Ij,t-1+∑l=1L∑s=t-1S+1t·Sqjls-djtj=1,…,J;t=2,…,T,(7)zijls≥xjls+xil,s-1-1i,j=1,…,J;l=1,…,L;s=1,…,T·S,(8)σls=∑i=1J∑j=1Jσijl′zijlsi,j=1,…,J;l=1,…,L;s=1,…,T·S,(9)ωlt≤σl,t-1S+1l=1,…,L;t=1,…,T;(10)∑s=t-1S+1t·Sσls+∑j=1Jpjlqjls≤C+ωltl=1,…,L;t=1,…,T.A particular product can be produced on some lines, but not on all in general (2) and only one product j is produced in each slot s of line l(3). The available time per macro-period is an upper bound on the time for production (4). The inventory balancing constraints (5) and (6) ensure that all demands are met taking into account the dummy variable qj0. Constraint (7) defines the setup times (zijls indicates this) based on slot reservations (xjls). Thus, it is possible to determine the setup time σls to be included just in front of a certain slot (8). As a result, overlapping setup can happen and, for the first slot of a macro-period t, some setup time ωlt may be at the end of the previous macro-period (9). The capacity C in constraint (10) has to be incremented by ωlt. Thus, the total sum of production and setup times in a certain macro-period must not exceed the macro-period capacity C by constraint (10).


## 3.4. Production Line: Time Slot Constraints

The constraints showed next describe how to integrate the micro-period idea from CLSP and the slot idea from GLSP. The main point here is to define specific constraints for the SITLSP which describe when some slots in lines will be used throughout the time horizon(11)t·C-∑τ=t-1Tm+1t·TmCmτxl,t·S,τE≥ωl,t+1l=1,…,L;t=1,…,T-1,(12)∑τ=t-1Tm+1t·TmCmτxlsτE-∑τ=t-1Tm+1t·TmCmτxl,s-1,τE≥σls+∑j=1Jpjlqjlsl=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(13)∑τ=t-1Tm+1t·TmCmτxl,t-1S+1,τE≥t-1C+σl,t-1S+1-ωlt+∑j=1Jpjlqjl,t-1S+1l=1,…,L;t=1,…,T;s=1,…,T·S,(14)∑τ=t-1Tm+1t·TmxlsτE=1l=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(15)∑τ=t-1Tm+1t·TmxlsτB=1l=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(16)∑j=1Jpjlqjls≤Culsl=1,…,L;s=1,…,T·S,(17)εuls≤∑j=1Jqjlsl=1,…,L;s=1,…,T·S,(18)∑τ=t-1Tm+1t·TmτxlsτE-∑τ=t-1Tm+1t·TmτxlsτB≤Tmulsl=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(19)∑τ=t-1Tm+1t·TmτxlsτB-∑τ=t-1Tm+1t·TmτxlsτE≤ulsl=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(20)∑τ=t-1Tm+1t·TmτxlsτB-∑τ=t-1Tm+1t·Tmτxl,s-1,τE≤Tmulsl=1,…,L;t=1,…,T;s=t-1S+2,…,T·S,(21)∑τ=t-1Tm+1t·Tmτxl,t-1S+1,τB-t-1Tm+1≤Tmul,t-1S+1l=1,…,L;t=1,…,T,(22)uls≥ul,s+1l=1,…,L;t=1,…,T;s=t-1S+1,…,T·S-1,(23)εuls+∑τ=t-1Tm+1t·TmCmτxlsτE-∑τ=t-1Tm+1t·TmCmτxlsτB≤∑j=1Jpjlqjlsl=1,…,L;t=1,…,T;s=t-1S+1,…,T·S,(24)∑τ=t-1Tm+1t·TmCmτxlsτE-∑τ=t-1Tm+1t·TmCmτxlsτB≥∑j=1Jpjlqjls-Cml=1,…,L;t=1,…,T;s=t-1S+1,…,T·S.The end of the last lot in some previous macro-periodt must leave sufficient time for the setup time ωlt+1 (11). The same time slot control enables us to constrain that the finishing time of one slot, minus the finishing time of the previous slot, must be at least as large as the production time in the corresponding slot, plus the required setup time in advance (12)-(13). Figure 6 illustrates the situation described by these constraints with S=2 and s=s1,s2,s3,s4; τ=1,2,…,10; t=1,2; Cm=1 and C=5.Figure 6
Keeping enough time between slots.There is only one possible beginning and end for each slot in the time horizon (14)-(15). While xjls indicates whether or not a certain slot is reserved to produce a particular product, uls indicates whether or not that slot is indeed used to schedule a lot. If the slot is not used, then the lot size must be zero (16); otherwise, at least a small amount ε must be produced (17). Time cannot be allocated for slots not effectively used (uls=0), so xlsτB=xlsτE must occur for the same micro-period τ (18)-(19). To avoid redundancy in the model, whenever a slot is not used, it should start as soon as the previous slot ends (20)-(21). The possibly empty slots in a macro-period will be the last ones in that macro-period (22). The start and end of a slot are chosen in such a way that the start indicates the first micro-period in which the lot is produced, if there is a real lot for that slot, and the end indicates the last micro-period (23)-(24). Figure 7 illustrates the situation described by these two constraints.Figure 7
Time window for production.The termε·uls in constraint (23) and the term ∑j=1Jpjlqjls-Cm in constraint (24) only matter for the case when the first and last micro-periods of a slot are the same. Notice that the processing time of P3 in Figure 7 is smaller than the micro-period capacity in constraint (24). However, constraint (23) ensures that a positive amount will be produced because we must have uL1,P3=1 by constraint (16).


## 3.5. Production Line: Synchronization Constraints

The model must describe how the raw materials in tanks are handled by production lines(25)qjls=∑k=1L¯∑τ=t-1Tm+1t·Tmqkjlsτ,l=1,…,L; t=1,…,T; s=t-1S+1,…,T·S, τ=t-1Tm+1,…,t·Tm, (26)δls=∑τ=t-1Tm+1t·TmτxlsτE-∑τ=t-1Tm+1t·Tmτxl,s-1,τB+1Cm-∑j=1Jpjlqjls,l=1,…,L; t=1,…,T; s=t-1S+2,…,T·S, τ=t-1Tm+1,…,t·Tm,(27)∑k=1L¯∑j=1Jpjlqkjlsτ≤Cm-δls+1-xlsτBCm,l=1,…,L; t=1,…,T; s=t-1S+1,…,T·S, τ=t-1Tm+1,…,t·Tm,(28)∑k=1L¯∑j=1Jpjlqkjlsτ≤∑τ′=t-1Tm+1t·TmCmxlsτ′E,l=1,…,L; t=1,…,T; s=t-1S+1,…,T·S, τ=t-1Tm+1,…,t·Tm,(29)∑k=1L¯∑j=1Jpjlqkjlsτ≤∑τ′=t-1Tm+1t·TmCmxlsτ′B,l=1,…,L; t=1,…,T; s=t-1S+1,…,T·S, τ=t-1Tm+1,…,t·Tm.To link production lines and tanks, we figure out which amount of soft drink being bottled on a line comes from which tank (25). In the first micro-period of a lot, sometimes δls are reserved for setup or idle time, while the remaining time is production time (26) and (27). Of course, the soft drink taken from a tank must be taken during the time window in which the soft drink is filled into bottles (28)-(29). Figure 8 illustrates the situation described by these constraints with Cm=1. Let us suppose that RmA is used to produce P2 and P3.Figure 8
Synchronization of line productions with tank storage.Notice that the processing time ofP3 takes from τ=7 to τ=8. This is considered by constraints (28) and (29).


## 3.6. Tanks: Usual Constraints

Now let us focus on usual lot sizing constraints for the tank level(30)x¯jks=0j=1,…,J¯;k∈1,…,L¯∖L¯j;s=1,…,T·S¯,(31)∑j=1Jx¯jks=1k=1,…,L¯;s=1,…,T·S¯,(32)q¯jks≤Q¯kx¯jksj=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(33)q¯jks≤Q¯ku¯ksj=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(34)∑j=1J¯q¯jks≥Q_ku¯ksj=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(35)z¯ijks≥x¯jks+x¯ik,s-1-2+u¯ksi,j=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(36)x¯jks-x¯jk,s-1≤u¯ksj=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(37)σ¯ks=∑i=1J¯∑j=1J¯σ¯ijk′z¯ijksi,j=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(38)ω¯kts≤σ¯k,t-1S+1i,j=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯,(39)∑s=t-1S+1t·S¯σ¯ks≤C+ϖkti,j=1,…,J¯,k=1,…,L¯;s=1,…,T·S¯.A particular raw material can be stored in some tanks (30) and tanks can store one raw material at a time (31). The tanks have a maximum capacity (32) and nothing can be stored, whenever the tank slot is not effectively used (33). However, a minimum lot size must be stored if a tank slot is used for some raw material (34). The setup state is not preserved in the tanks, that is, a tank must be setup again (cleaned and filled), even if the same soft drink has been in the tank just before. Care must be taken when setups occur in the model only if the tank is really used, because changing the reservation for a tank does not necessarily mean that a setup takes place (35)-(36). Figure 9 illustrates these constraints.Figure 9
Raw material changeover.From the schedule in Figure9, constraints (31)–(34) define x¯RmB,·Tk2,s4=x¯RmB,Tk2,s3=u¯Tk2,s3=1 and x¯RmD,Tk1,s4=x¯RmD,Tk1,s3=u¯Tk1,s4=1. Moreover, the raw materials scheduled will satisfy constraints (35)-(36). As in the production lines, it is also possible to determine the tank slot setup time (37) and the setup time that may be at the end of the previous macro-period (38)-(39). Thus, the setup time in front of lot s, at the beginning of some period, is the setup time value minus the fraction of setup time spent in the previous periods. This value cannot exceed the macro-period capacity C.


## 3.7. Tanks: Time Slot Constraints

The main point here is to keep control when the tank slots are used throughout the time horizon by production lines. This will help to know when a setup time in tanks will interfere with some production line or from which tanks the lines are taking the raw materials:(40)q¯jks=∑τ=t-1Tm+1t·Tmq¯jksτ,j=1,…,J¯, k=1,…,L¯; t=1,…,T; s=1,…,T·S¯,(41)t·C-∑τ=t-1Tm+1t·TmCmτx¯k,t·S,¯τE≥ϖk,t+1,k=1,…,L¯; t=1,…,T-1;(42)∑τ=t-1Tm+1t·TmCmτx¯ksτE-∑τ=t-1Tm+1t·TmCmτx¯k,s-1,τE≥σ¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+1,…,t·S¯,(43)∑τ=t-1Tm+1t·TmCmτx¯k,t-1S¯+1,τE≥t-1C+σ¯k,t-1·S¯+1-ϖkt,k=1,…,L¯; t=1,…,T,(44)∑τ=t-1Tm+1t·Tmx¯ksτE=1,k=1,…,L¯; t=1,…,T; s=t-1S¯+1,…,t·S¯; τ=t-1Tm+1,…,t·Tm,(45)∑τ=t-1Tm+1t·Tmx¯ksτB=1,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(46)∑τ=t-2Tm+1t·Tmx¯k,t-1S¯+1,τB=1,k=1,…,L¯; t=2,…,T,(47)∑τ=1Tmx¯k1τB=1,k=1,…,L¯; t=2,…,T,(48)∑j=1J¯q¯jksτ≤Q¯kx¯ksτE,k=1,…,L¯; t=1,…,T; s=t-1S¯+1,…,t·S¯; τ=t-1Tm+1,…,t·Tm,(49)∑τ=t-1Tm+1t·Tmτx¯ksτE-∑τ=t-1Tm+1t·Tmτx¯ksτB≤Tmu¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(50)∑τ=t-1Tm+1t·Tmτx¯k,t-1S¯+1,τE-∑τ=t-2Tm+1t·Tmτx¯k,t-1S¯+1,τB≤Tmu¯k,t-1S¯+1,k=1,…,L¯; t=2,…,T;(51)∑τ=1Tmτx¯k1τE-∑τ=1Tmτx¯k1τB≤Tmu¯k1,k=1,…,L¯,(52)∑τ=t-1Tm+1t·Tmτx¯ksτB-∑τ=t-1Tm+1t·Tmτx¯ksτE≤u¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(53)∑τ=t-2Tm+1t·Tmτx¯k,t-1S¯+1,τB-∑τ=t-1Tm+1t·Tmτx¯k,t-1S¯+1,τE≤u¯k,t-1S¯+1,k=1,…,L¯; t=2,…,T;(54)∑τ=1Tmτx¯k1τB-∑τ=1Tmτx¯k1τE≤u¯k1,k=1,…,L¯;(55)∑τ=t-1Tm+1t·Tmτx¯ksτB-∑τ=t-1Tm+1t·Tmτx¯k,s-1,τE≤Tmu¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(56)∑τ=t-1Tm+1t·Tmτx¯k,t-1S¯+1,τB-t-1Tm+1≤Tmu¯k,t-1S¯+1,k=1,…,L¯; t=2,…,T;(57)∑τ=1Tmτx¯k1τB-1≤Tmu¯k1,k=1,…,L¯;(58)u¯ks≥u¯k,s+1,k=1,…,L¯; t=1,…,T; s=t-1S¯+1,…,t·S¯-1;(59)Cmu¯ks+∑τ=t-1Tm+1t·TmCmτ¯xksτE-∑τ=t-1Tm+1t·TmCmτ¯xksτB=σ¯ks,k=1,…,L¯; t=1,…,T; s=t-1S¯+2,…,t·S¯;(60)Cmu¯k,t-1S¯+1+∑τ=t-1Tm+1t·TmCmτ¯xk,t-1S¯+1,τE-∑τ=t-2Tm+1t·TmCmτ¯xk,t-1S¯+1,τB=σ¯k,t-1S¯+1,k=1,…,L¯; t=2,…,T;(61)Cmu¯k1+∑τ=1TmCmτ¯xk1τE-∑τ=1TmCmτ¯xk1τB=σ¯k1-ω¯k1,k=1,…,L¯,(62)∑j=1J¯I¯jk,τ-1≤Q¯k1-x¯ksτB+1-u¯ks,k=1,…,L¯; t=1,…,T-1; s=t-1S¯+1,…,t·S¯+1; τ=t-1Tm+1,…,t·Tm,(63)∑j=1J¯I¯jk,τ-1≤Q¯k1-x¯ksτB+1-u¯ks,k=1,…,L¯; s=T-1S¯+1,…,T·S¯+1; τ=T-1Tm+1,…,T·Tm.Most of these constraints are similar to those presented for the production line level. The amount that is filled into a tank must be scheduled, so that the micro-period in which the raw material comes into the tank is known (40). Tank slots must be scheduled in such a way that the setup time that corresponds to a slot fits into the time window between the end of the previous slot and the end of the slot under consideration (41)-(42). The setup for the first slot in a macro-period may overlap the macro-period border to the previous macro-period (43). This is the same idea presented by Figure 6 for lines. The finishing time of a scheduled slot must be unique, as must its starting time (44)–(47). The raw material is available for bottling just when the tank setup is done (48). Therefore, we must have x¯Tk2,s3,7E=x¯Tk2,s4,9E=1 in constraint (48) for the example shown in Figure 10.Figure 10
Tank refill before the end of the setup time.The time window in which a slot is scheduled must be positive if and only if that slot is used to set up the tank (49)–(54). Redundancy can be avoided if empty slots are scheduled right after the end of previous slots (55)–(57). More redundancy can be avoided if we enforce that, within a macro-period, the unused slots are the last ones (58).Without loss of generality, we can assume that the time needed to set up a tank is an integer multiple of the micro-period. Hence, the beginning and end of a slot must be scheduled so that this window equals exactly the time needed to set the tank up (59)–(61). Constraint (61) adds up micro-periods τ=1,…,Tm seeking the beginning and end of the tank setup in slot s¯=1. Finally, a tank can only be set up again if it is empty (62)-(63). Notice that a tank slot reservation (x¯ksτB=1) does not mean that the tank should be previously empty (I¯jkτ-1=0). The tank slot also has to be effectively used (u¯ks=1 and x¯ksτB=1) in (62)-(63). Constraint (63) describes this situation for the last macro-period T where the first slot of the next macro-period is not taken into account.Finally, notice that there are group of equations, as for example, (45)–(47), (49)–(51), (52)–(57), (55)–(57), and (59)–(61), that are derived from the same equations, respectively, (45), (49), (52), (55), and (59). These derived equations are necessary to deal with the first slot and sometimes with the last slot in each macro-period.


## 3.8. Tanks: Synchronization Constraints

The model must describe how the products in production lines are handled by tanks:(64)I¯jkτ=I¯jk,τ-1+∑s=t-1S+1t·Sq¯jksτ-∑i=1J∑l=1L∑s=t-1S+1t·Srjiqkilsτ,j=1,…,J¯, k=1,…,L¯; t=1,…,T; τ=t-1Tm+1,…,t·Tm,(65)I¯jkτ≥∑i=1J∑l=1L∑s=t-1S+1t·Srjiqkils,τ+1,j=1,…,J¯, k=1,…,L¯; t=1,…,T; τ=t-1Tm+1,…,t·Tm-1.What is in the tank at the end of a micro-period must be what was in the tank at the beginning of that micro-period, plus what comes into the tank in that micro-period, minus what is taken from that tank for being bottled in production lines (64). To coordinate the production lines and the tanks, it is required that what is taken out of a tank must have been filled into the tank at least one micro-period ahead (65).


## 3.9. Example

This subsection will present an example to illustrate what kind of information is returned by a model solution. Let us start by the solution illustrated in Figure5. This solution is shown again in Figure 11. Figure 12 presents the same solution considering the model assumptions.Figure 11
Possible solution for SITLSP.Figure 12
Possible solution provided by the model.According to the model, the setup times of the tanks are considered as an integer multiple of the time of a micro-period. For example, the setup time ofRmC in Figure 11 goes from the entire τ=1 (micro-period 1) until part of τ=2 and from the entire τ=8 until part of τ=9. These setup times fit into two complete micro-periods in Figure 12 (see constraints (59)–(61)). The same happens with the setup time of RmB (macro-period 2). The setup time of products in lines L1 and L2 are positioned in front of the next slot as required by constraints (8)–(13), and all the productions in the lines start after the tank setup time is finished (constraints (25), (28)-(29), (40), and (48)).The satisfaction of the model constraints imposes that binary variablesxjls, x¯jks, uls, u¯ks, xlsτB, xlsτE, x¯ksτB, and x¯ksτE must be necessarily active (value 1) for lines, tanks, products, and raw materials in the slots and micro-periods shown in Figure 12. These active variables provide enough information about what and when the products and raw materials are scheduled throughout the time horizon. Moreover, the continuous variables qjls, qkjlsτq¯jksτ, q¯jks must be positive for lines, tanks, products, and raw materials in the same slots and micro-periods.For example, based on Figure12, the model solution has positive variables q¯RmC,Tk2,s4,8 and q¯RmC,Tk2,s4,9 and returns the amount of RmC filled in Tk2 during micro-periods τ=8 and τ=9. The total filled in this slot (s4) is provided by q¯RmC,Tk2,s4. The model variable qTk2,P4,L2,10 returns the amount used by P4 in L2 which is taken from q¯RmC,Tk2,s4. In the same way, qTk1,P3,L1,s4,9 and qTk1,P3,L1,s4,10 have the lot sizes of P3 taken from slot s3 in variable q¯RmB,Tk1,s3. In this case, the total lot size P3 is provided by qP3,L1,s4. All these variables returned by the model will provide enough information to build an integrated and synchronized schedule for lines and tanks.


## 4. Computational Results for Small-to-Moderate Size Instances

The main objectives in this section are to provide a set of benchmark results for the problem and to give an idea about the complexity of the model resolution. The lack of similar models in the literature has led us to create a set of instances for the SITLSP. An exact method available in an optimization package was used as the first approach to solve these instances. Table2 shows the parameter values adopted.Table 2
Parameter values.
Param.
Values
Param.
Values
Param.
Values
Param.
Values
L
2; 3; 4
L
¯
2; 3
h
j
1 ($/u)
h
¯
j
1 ($/u)
J
2; 3; 4
J
¯
1; 2
h
¯
j
1 ($/u)
h
¯
j
1 ($/u)
S
2; 3
S
¯
2
v
j
l
1 ($/u)
v
¯
j
k
1 ($/u)
T
1; 2; 3; 4
T
m
5
Q
_
k
1000 l
Q
¯
k
5000 l
C
5 t.u.
C
m
1 t.u.
min
⁡
D
e
m
500 u
max
⁡
D
e
m
10000 uA combination of parametersL, L¯, J, and J¯ defines a set of instances. These instances are considered of small-to-moderate sizes if compared to the industrial instances found in soft drink companies. Table 3 presents the parameter values that define each combination S1–S9. There are 9 possible combinations for macro-period T=1, 2, 3, and 4. For each one of these sets, 10 replications are randomly generated, resulting in 4 × 9 × 10 = 360 instances in total. The other parameters of the model are randomly generated from a uniform distribution in the interval [a,b], as shown in Table 4. Most of these parameters were defined following suggestions provided by the decision maker of a real-world soft drink company. The setup costs are proportional to setup times with parameter f set to 1000. This provides a suitable tradeoff between the different terms of the objective function.Table 3
Parameter combination for each set of instances.
Comb.
L
/
L
¯
/
J
/
J
¯
Comb.
L
/
L
¯
/
J
/
J
¯
Comb.
L
/
L
¯
/
J
/
J
¯
S
1
2/2/2/1
S
4
3/3/2/1
S
7
4/3/2/1
S
2
2/2/3/2
S
5
3/3/3/2
S
8
4/3/3/2
S
3
2/2/4/2
S
6
3/3/4/2
S
9
4/3/4/2Table 4
Parameter ranges.
Par.
Ranges
Meaning
σ
i
j
l
′
U
[
0.5
;
1
]
Setup time (hours) from producti to j in line l
σ
¯
i
j
k
′
U
[
1
;
2
]
Setup time (hours) from raw materiali to j in tank k
s
i
j
l
s
i
j
l
=
f
⋅
σ
i
j
l
′
Line setup cost
s
¯
i
j
k
s
¯
i
j
k
=
f
⋅
σ
¯
i
j
k
′
Tank setup cost
p
j
l
U
[
1000
;
2000
]
Processing time (units/hour) of producti in line l
r
j
i
U
[
0.3
;
3
]
Liters of raw materiali used to produce one unit of product jThe computational tests ran in a core 2 Duo, 2.66 GHz, and 1.95 GB RAM. The instances were coded using the modeling language AMPL and solved by the branch & cut exact algorithm available in the solver CPLEX 11.0. The optimization package AMPL/CPLEX ran over each instance once during the time limit of one hour. Two kinds of problem solutions were returned: the optimal solution or the best feasible solution achieved up to the time limit. The following gap value was used:(66)Gap(%)=100Z-Z¯Z¯,where Z is the solution value and Z¯ is the lower bound value returned by AMPL/CPLEX. Table 5 presents the computational results for T=1,2. Column Opt. has the number of optimal solutions found in each combination.Table 5
AMPL/CPLEX results for the set of instances withT=1,2.
Comb.
T
=
1
T
=
2
Opt.
Gap(%)
CPU
Opt.
Gap(%)
CPU
S
1
10
0
0.22
10
0.51
1.90
S
2
10
0
0.48
9
0.85
585.87
S
3
10
0
0.60
8
0.61
1271.04
S
4
10
0
0.66
10
0.32
15.49
S
5
10
0
1.46
8
1.52
1414.51
S
6
10
0
12.30
6
3.77
1519.31
S
7
10
0
0.96
10
0.08
525.46
S
8
10
0
4.37
6
0.79
2052.72
S
9
10
0
7.83
5
1.38
1821.96Column Gap(%) shows the average gap of the final solutions returned by AMPL/CPLEX from the lower bound found. The CPU values are the average time spent (in seconds) to return these solutions. Table6 shows the model figures for each combination. In Table 5 notice that the AMPL/CPLEX had no major problems to find solutions for T=1 and T=2. The solver was able to optimally solve all instances for T=1 (90 in 90) and found several optimal solution for T=2 (72 in 90) within the time limit. The required average CPU running times increased from T=1 to T=2, which is expected, based on the number of constraints and variables of the model for each instance (see Table 6).Table 6
Model figures for the set of instances withT=1,2.
Comb.
T
=
1
T
=
2
Var.
Const.
Var.
Const.
Bin.
Cont.
Bin.
Cont.
S
1
100
263
281
210
533
575
S
2
136
499
454
282
1004
919
S
3
142
615
512
294
1235
1039
S
4
150
452
419
315
916
862
S
5
204
880
673
423
1771
1368
S
6
213
1098
764
441
2206
1552
S
7
176
555
498
367
1122
1013
S
8
246
1100
821
507
2211
1641
S
9
258
1390
924
531
2790
1865The AMPL/CPLEX was also able to find optimal solutions forT=3 (43 in 90) and T=4 (26 in 90) within one hour, but this value decreased as shown in Table 7 when compared with those in Table 6. The complexity of the model proposed here, caused by the high number of binary/continuous variables and constraints, as shown in Table 8, explains the hardness faced by the branch and cut algorithm to achieve optimal solutions. Nevertheless, around 64% of the small-to-moderate size instances were optimally solved with 129 nonoptimal (feasible) solutions returned. The average gap from lower bounds, Gap(%), has increased following the complexity of each set of instances. However, gap values are below 7% in all set of instances.Table 7
AMPL/CPLEX results for the set of instances withT=3,4.
Comb.
T
=
3
T
=
4
Opt.
Gap(%)
CPU
Opt.
Gap(%)
CPU
S
1
10
0.72
10.64
9
0.13
535.17
S
2
4
3.38
2177.73
3
5.00
2814.48
S
3
5
1.84
2249.24
2
4.55
3159.17
S
4
9
0.20
461.35
7
0.15
1808.17
S
5
3
4.72
3076.43
1
3.88
3276.78
S
6
2
3.31
3208.99
0
6.52
3600.45
S
7
7
0.33
1150.23
4
0.57
2922.49
S
8
1
4.70
3257.73
0
4.97
3600.33
S
9
2
5.55
2963.03
0
5.06
3600.32Table 8
Model figures for the set of instances withT=3,4.
Comb.
T
=
3
T
=
4
Bin. Var.
Cont. Var.
Const.
Bin. Var.
Cont. Var.
Const.
S
1
320
803
863
430
1073
1163
S
2
574
2014
1835
574
2014
1827
S
3
598
2475
2075
598
2475
2075
S
4
480
1380
1303
645
1844
1752
S
5
642
2662
2071
861
3553
2764
S
6
669
3314
2350
897
4422
3140
S
7
558
1689
1536
749
2256
2039
S
8
768
3322
2466
1029
4433
3335
S
9
804
4190
2799
1077
5590
3735These small-to-moderate size instances were already used by Toledo et al. [39] where the authors proposed a multipopulation genetic algorithm to solve the SITLSP. These instances were solved and these solutions were helpful to adjust and evaluate the evolutionary method performance. The insights provided by this evaluation were also useful to set the evolutionary method to solve real-world instances of the problem.


## 5. Computational Results for Moderate-to-Large Size Instances

The previous experiments with the AMPL/CPLEX have shown how difficult it can be to find proven optimal solutions for the SITLSP within one hour of execution time, even for small-to-moderate size instances. However, they also showed that it is possible to find reasonably good feasible solutions under this computational time. In practical settings, decision makers are usually more interested in obtaining approximate solutions found in shorter times than optimal solutions which require much longer runtimes.For this reason, instead of spending longer time looking for optimal solutions, this section evaluates some alternatives to find reasonably good approximate solutions for moderate-to-large size instances. For this, another combination of parametersL/L¯/J/J¯/T is considered, which defines a more complex and realistic set of instances, namely, L1–L10. Table 9 shows the corresponding parameter values.Table 9
Parameter combination for each set of instances.
Comb.
L
/
L
¯
/
J
/
J
¯
/
T
Comb.
L
/
L
¯
/
J
/
J
¯
/
T
L
1
5/5/10/5/4
L
6
5/6/15/8/8
L
2
5/6/15/8/4
L
7
8/5/10/5/8
L
3
8/5/10/5/4
L
8
8/6/15/8/8
L
4
8/6/15/8/4
L
9
5/5/10/5/12
L
5
5/5/10/5/8
L
10
5/6/15/8/12While the model parameters were changed toC=10t.u, Tm=10, S=5,8, and S¯=3,4, the remaining parameters kept the same values of the ones shown in Tables 2 and 4. For each one of the 10 possible combinations in Table 9, a total of 10 replications was randomly generated resulting in 100 instances. Preliminary experiments with some of these instances showed that even feasible solutions are difficult to find after executing AMPL/CPLEX for one hour. Therefore, two relaxations of the model were investigated: the first relaxation, R1, keeps as binary variable only the model variables uls and u¯ks, whereas the other binary variables are set continuous in the range [0,1]. The second relaxation, R2, keeps uls and u¯ks as binary as well as xjls and x¯jks. A similar idea was used by Gupta & Magnusson [21] to deal with a one-level capacitated lot sizing and scheduling problem.These two relaxation approaches were applied to solve the set of instancesL1–L10 within one hour. The results are shown in Table 10, where Opt. is the number of optimal solutions found by R1 and R2, respectively, Feas. is the number of feasible solutions without penalties, and Penal is the number of feasible solutions with penalties. Remember that nonsatisfied demands are penalized in the objective function of the model (see (1)).Table 10
Relaxation approaches results.
Comb.
R
1
R
2
Opt.
Feas.
Penal
Opt.
Feas.
Penal
L
1
10
—
—
—
10
—
L
2
10
—
—
—
9
1
L
3
9
1
—
—
9
1
L
4
4
6
—
—
2
8
L
5
8
2
—
—
8
2
L
6
4
6
—
—
3
7
L
7
6
4
—
—
3
7
L
8
5
5
—
—
—
10
L
9
7
3
—
—
7
3
L
10
—
5
5
—
4
6Indeed for moderate-to-large size instances, approachR1 succeeded in finding optimal solutions for a total of 63 out of 100 instances. Approach R2 returned only feasible solutions with some of them penalized. A total of  55 out of 100 solutions without penalties were found by R2.Figure13 shows the average CPU time spent by R1 to solve 10 instances on each set L1–L9. This average time was calculated for the whole set of instances, as well as for only that subset of instances with optimal solutions found. All solutions were returned in less than 3000 sec. on average, and optimal solutions took less than 2000 sec. Thus, R1 and R2 approaches returned approximate solutions within a reasonable computational time for these sets of large size instances.Figure 13
Average CPU time to find solutions.


## 6. Conclusions

A great deal of scientific work has been done for decades to study lot sizing problems and combined lot sizing and scheduling problems, respectively. A whole bunch of stylized model formulations has been published under all kinds of assumptions to investigate this class of planning problems. It is well understood that certain aspects make planning become a hard task not only in theory. Among these issues are capacity constraints, setup times, sequence dependencies, and multilevel production processes, just to name a few. Many researchers including ourselves have focused on such stylized models and spent a lot of effort on solving artificially created instances with tailor-made procedures knowing that even small changes of the model would require the development of a new solution procedure. But very often, it remains unclear whether or not the stylized model represents a practical problem. Hence, we feel that it is necessary to move a bit more towards real applications and start to motivate the models being used stronger than before.An attempt to follow this paradigm is presented in this paper. We were in contact with a company that bottles very well-known soft drinks and closely observed the main production process where different flavors are produced and filled into bottles of different sizes. The production planning problem is a lot sizing and scheduling problem with several thorny issues that have been discussed in the literature before, for example, capacity constraints, setup times, sequence dependencies, and multilevel production processes. But in addition to the issues described in existing literature, many specific aspects make this planning problem different from what we know from the literature. Hence, we contributed to the field by describing in detail what the practical problem is so that future researchers may use this problem instead of a stylized one to motivate their research.Furthermore, we succeeded in putting together a model for the practical problem by making use of existing ideas from the literature, that is, we combined two stylized model formulations, the GLSP and the CSLP, to formulate a model for the practical situation. In this manner, this paper contributes to the field, because it provesa posteriori that the stylized models studied before are indeed relevant if used in a proper way which is not obvious. As the focus of this paper is not on sophisticated solution procedures, we used commercial software to solve small and medium sized instances to give the reader a practical grasp on the complexity of the problem. A next step could be to work on model reformulations given that nowadays commercial software is quite strong if provided with a strong model formulation. Future work may also focus on tailor-made algorithms, of course. We believe that heuristics are most appropriate for such real-world problems, but work on optimum solution procedures or lower bounds is relevant, too, because benchmark results will be needed.



---

*Source: 182781-2015-07-09.xml*