Keywords

1 Introduction

Solving lot-sizing problems is of high relevance for many manufacturing companies [3]. The existence of several products with varying demand that have to be processed on the same machines with a finite capacity, results in a complex planning task, referred to as capacitated lot-sizing problem (CLSP). In this study, we discuss a practical CLSP, which arises in injection molding processes for plastic blanks at a large automotive manufacturer in Germany. Different products are manufactured on several, heterogeneous injection molding machines, which use different technologies and have a limited capacity. Each type of product is assigned to one preferred machine, but can be processed on at least one other machine. Thus, besides determining optimal lot sizes and production times for each product, a useful assignment of products to machines has to be found. Before a product can be processed, a sequence-independent setup time is necessary on each machine. Once a machine is equipped for producing a certain type of product, the setup state remains valid for a succeeding period (setup carryover). All setup and processing times are dependent on the product as well as on the assigned machine. Due to a limited number of necessary tools, each product can be produced on only one machine at a time. An additional challenge is that the following production process uses a different shift model. Hence, the two stages injection molding and paint shop are decoupled by a buffer store, which has a limited capacity due to individual storage containers for each product. Since in automotive manufacturing supply reliability is crucial, demands always have to be satisfied and no shortages or back orders are allowed.

The CLSP has been studied widely in literature with various extension [6]. Nevertheless, due to specific organizational or technological requirements arising in real-world manufacturing systems, existing models and solution approaches can often not be applied directly to practice. Mainly, the following modifications of the CLSP are vital to provide a helpful decision support in this case: First, it is characterized by the existence of parallel machines, which were introduced by [4] and discussed, e.g., by [7]. Secondly, a limited buffer capacity of finished goods has to be considered [1]. Furthermore, linked lot-sizes are relevant, i.e. setup states can be carried over to the following time period [5]. Finally, a limited worker capacity for operating the machines and rejects cannot be neglected. We refer to this problem as CLSPL-IBPM, i.e. a CLSP with linked lot sizes (L), inventory bounds (IB) and parallel machines (PM). To the best of our knowledge, some of these requirements as well as its combination have not been considered in literature so far and approaches mentioned above cannot be applied to the given practical case. Therefore, we developed an extended MIP model, which is presented in Sect. 2 and applied for several real-world instances in order to replace current manual planning (see Sect. 3). Finally, the results are summarized in Sect. 4.

2 MIP Formulation of the CLSPL-IBPM

We formulate the studied CLSPL-IBPM problem as MIP model with the notation displayed in Table 1. Its general structure is based on the formulation of [2], that is extended by parallel machines and linked lot-sizes similarly to [6]. Additionally, the restricted worker capacity, rejects and limited storage buffers are integrated. The following assumptions are taken into account: The dynamic demand as well as the production rate are considered to follow a linear course for all products j ∈ N. Each product j can be produced on one of the parallel machines i ∈ M j, with M j being a subset of all machines M. The set of all products that can be produced on machine i is referred to as N i. The length of a period t ∈ T is set to 1 shift, which equals 8 hours. It is possible to split setup times, i.e. to finish a started setup time in the following period.

$$\displaystyle \begin{aligned} \begin{array}{rcl} \text{Min. } C= \sum_{t \in T} &\displaystyle \left( \sum_{j \in N} \sum_{i \in M_j} \left( f_{i,j} \cdot z_{i, j, t}^{*}\right) +\frac{1}{2} \cdot \sum_{j \in N} \left( c_{j} \cdot \left[l_{j,t} + l_{j,t-1} \right]\right) \right. \notag \\ &\displaystyle \ \ \left. +\sum_{j \in N}\sum_{i \in M_j} \left( z_{i, j, t}^{*} \cdot pa_{i} \cdot c^{a}_{j} \right) {} \right) \end{array} \end{aligned} $$
(1)

s.t.:

(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
Table 1 Notation for MIP formulation
Full size table

The objective function (1) consists of three cost components that are summed up for all planning periods. First, sequence-independent setup costs are considered for each changeover. Secondly, holding costs are determined assuming an constant usage of goods in the demand period. Furthermore, reject costs arise during the beginning of every production process. Equation (2) is the inventory balance equation, which ensures that all demands are satisfied. Equation (3) defines that the lot size q i,j,t can only be larger than 0 if the binary production variable z i,j,t = 1. Equations (4) and (5) represent the linking between the variables q i,j,t, z i,j,t and the binary setup variable \(z_{i,j,t}^{*}\). Constraints (6) and (7) ensure that every product is produced and set up only once in each period. This is a limitation of decision space to simplify the considered problem but corresponds to the actual planning of the automotive manufacturer. Equation (8) determines the number of required workers \(w^{ist}_{i, t}\), which is limited by the worker capacity per shift in Eq. (9). Equation (10) determines the required setup time \(t^{r}_{i, t}\) on each machine. It is limited to the length of a period t ∗. The remaining setup time \(t^{rr}_{i, t}\) from a setup starting at period t − 1 is defined in Constraint (11). Equation (12) guarantees that the available time in each period is not exceeded by production and setup processes, while the necessary production time \(t^{z}_{i, t}\) is calculated via Eq. (13), taking the reject rate at each machine into account. According to Constraint (14) all lot sizes have to be an integer multiple of the storage capacity of the individual storage containers, while the maximum buffer capacity is limited by Eq. (15). Initial inventory levels, setup states and remaining setup times from previous periods are excluded by Eq. (16). It has to be noted that the presented formulation is not linear due to Eqs. (5), (8), (10) and (11). But it can be linearized with reasonable effort and is therefore solvable with common mathematical solvers.

3 Computational Results

The proposed model was implemented and tested for 8 real-world instances on a Intel(R) Xenon(R) CPU E5-4627 with 3.3 GHz clock speed and 768 GB RAM using CPLEX 12.6 with max. 4 parallel threads. Each instance represents one week and corresponds to the weekly planning period in practice. In total 25 different products have to be planned on 7 machines. Computation time t CPU has been limited to both 3 and 30 min. The results are displayed in Table 2. It can be seen, that for all instances already after 3 min computation time good results can be obtained with a maximum gap of 5.1%. One instance can even be solved to optimality. This proves the applicability of the proposed approach, since a re-planning can be performed at short notice, e.g. if machine breakdowns or unexpected changes in demand occur. Nonetheless, larger computation times are still viable for the weekly planning. With a time limit of 30 min the results can be further improved from on average 4.1% to 3.0%. However, still no additional instance could be solved to optimality. Due to organizational issues it is difficult to compare the gained results directly to the planned schedules from practice. However, an approximate evaluation indicates a reduction of the cost function by 10 to 20%, at the same time ensuring feasibility of the generated production plan. Moreover, by using the proposed MIP a previously time-consuming and complex manual planning task can be replaced by a quick automated decision support.

Table 2 Computational results for real-world instances
Full size table

4 Conclusions and Future Research

For a successful application of CLSP models in practice, it is often necessary to integrate several real-world requirements. In doing so, the proposed CLSPL-IBPM MIP formulation was able to provide decision support for the production process of plastic blanks in automotive manufacturing. Even within very short computation times good solutions could be generated that simplify the planning process and ensure low costs. Nevertheless, the proposed approach still leaves room for development. Additional technological requirements should be added to the model, such as paired products, that need to be processed together, or variants of specific parts. Furthermore, a balanced demand for workers over all shifts could lead to additional improvements of the production plan. Finally, the length of a period of one shift may not be optimal as within each shift a detailed scheduling is still necessary and buffers may not be sufficient at each moment.