Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction to Production Levelling

One major problem of production planning is caused by the limited flexibility which exists in adapting the output of the production resources to a varying, fluctuating customer demand. In a globalized, highly-competitive market only limited rules for the timing of customer orders can be established. Therefore, a strict following of customer orders by production leads to undesired inefficiencies in production plans. One approach to tackle this issue is proposed by the well-known Toyota Production System with the concept of levelling (also production smoothing or Heijunka) [9]. Levelling decouples customer demand from production orders for a fixed period of time. For this levelling period, a levelling pattern needs to be designed. The pattern determines at which production day, which product, in which quantity (lot-size) and in which position (order) has to be produced. Levelling aims at patterns which are balanced in production volume as well as in production mix [4]. As a result, a reliable, balanced plan and a smoothened production rhythm can be communicated with all suppliers of the underlying supply chain. The impact of the bullwhip effect can be decreased and spare capacity or stocks to cope with demand peaks can be reduced [5].

2 Existing Approaches and Related Problems

The design of levelling patterns is nothing new and many approaches have been described in literature. Existing approaches can be classified into procedure models and optimization models [1]. Procedure models describe systematic approaches which contain a set of structured rules for the design of levelling patterns. Such approaches are presented in [11, 13, 14]. A good summary can be found in [2]. A major disadvantage of all procedure models is the lack of specific analytical descriptions, rules or algorithms for the design of levelling patterns. Therefore, the second class of optimization model tries to close this gap. For large-scale production a lot of research has been published on designing levelling patterns for mixed-model assembly lines. The underlying problem is referred to as Production Smoothing Problem (PSP) or level scheduling. The PSP aims at finding a production sequence which minimizes the deviation from ideal to actual objective values [1]. An excellent literature survey can be found in [3]. But due to the specific assumptions of the PSP (lot-size one and negligible changeover times) a generated production plan will not satisfy the requirements of traditional lot-size production. For the levelling of lot-sizes some existing research focuses on the Batch Production Smoothing Problem (BSP) which still ignores changeover times [7]. For lot-sizes and changeover times a promising approach is presented by [2]. The author uses the Traveling Salesmen Problem (TSP) for the generation of levelling patterns, but the smoothness of the production plan is not assured on a mathematical basis. Therefore, this article closes this research gap by capturing the levelling targets in an optimization model for lot-size production with relevant changeover times.

3 Modeling Approach

The basis of this model is the Distance-Constrained Vehicle Routing Problem (DCVRP), see [8] for an introduction. The DCVRP has been selected due to many analogies between routing and scheduling problems [12]. The following notation is introduced: In \(k\in K\) workdays \(i\in I\) products with a specific demand \(D_i\) must be produced. n denotes the total number of products and \(n_{WD}\) the number of workdays. A dummy product 0 is introduced to represent an idle state at the beginning and end of each day. \(PT_k\) denotes the available production time on day k and \(PTU_k\) models the used production time. \(t_{CT,i}\) denotes the cycle time of i. \(t_{CO,ij}\) denotes the changeover time from i to j. The binary decision variable \(y_{ijk}\) equals 1 if a changeover from i to j is conducted on day k. An integer decision variable \(x_{ik}\) models the production quantity of i on day k. For each product a specific \(EPEI_i\) (Every Part Every Interval) has to be regarded: If \(EPEI_A=1\), the runner product A must be produced every day.

The following assumptions are drawn: The capacity of the production resources is limited. Planning is based on the final product stage (no levelling of subassemblies or components). Demand must be fulfilled and stock-outs are not permitted. A maximum of one lot per product can be produced per day. The changeover status at the end of one production day is not taken over to the next day. All input parameters are deterministic. Stochastic or dynamic influences are not considered. Changeover times are decision-relevant and lot-size one is impossible. The model can now be formulated as:

$$\begin{aligned} \begin{aligned} \min \,\,\,&\lambda _{Uti} \sum _{k= 1}^{|K|-1} \left| \frac{ PTU_{k} }{PT_{k}} - \frac{ PTU_{k+1} }{PT_{k+1}} \right| \quad + \lambda _{CO} \sum _{k\in K} \frac{ \sum _{i\in I} \sum _{j\in V} y_{ijk}\cdot t_{CO,ij}}{PT_k} \\&-\lambda _{Sim} \frac{1}{|K|-1} \sum _{k= 1}^{|K|-1} \frac{ \sum _{i\in I}\sum _{j\in J} y_{ijk}\cdot y_{ijk+1}}{\sum _{i\in I}\sum _{j\in J} sign(y_{ijk}+ y_{ijk+1})} \end{aligned} \end{aligned}$$
(1)
$$\begin{aligned}&s.t.: \nonumber \\&\sum _{j\in I} \sum _{k\in K} y_{0jk} = n_{WD} \end{aligned}$$
(2)
$$\begin{aligned}&\sum _{i\in I} \sum _{k\in K} y_{i0k} = n_{WD} \end{aligned}$$
(3)
$$\begin{aligned}&\sum _{i\in I} y_{ihk} = \sum _{j\in I} y_{hjk}&\forall h \in I,\forall k \in K \end{aligned}$$
(4)
$$\begin{aligned}&\sum _{j\in I} y_{ijk} \le 1&\forall i \in I,\forall k \in K \end{aligned}$$
(5)
$$\begin{aligned}&\sum _{k\in K} x_{ik} = D_i&\forall i \in I \end{aligned}$$
(6)
$$\begin{aligned}&x_{ik}-M \sum _{j\in I} y_{ijk} \le 0&\forall i \in I,\forall k \in K \end{aligned}$$
(7)
$$\begin{aligned}&\sum _{j\in I} \sum _{k= \tilde{k}}^{\tilde{k}+\overline{EPEI_i}-1} y_{ijk} = 1 \qquad \qquad \forall i \in I,&\forall \tilde{k} \in \left\{ K: \right. \tilde{k} \left. \le |K|- \overline{EPEI_i}+1 \right\} \end{aligned}$$
(8)
$$\begin{aligned}&\sum _{i\in I} \sum _{j\in I} (y_{ijk}\cdot t_{CO,ij}+x_{ik}\cdot t_{C,i}) \le PT_k&\forall k \in K \end{aligned}$$
(9)
$$\begin{aligned}&PTU_{k}= \sum _{i\in I} \sum _{j\in J} ( y_{ijk}\cdot t_{CO,ij}+x_{ik}\cdot t_{C,i} )&\forall k \in K \end{aligned}$$
(10)
$$\begin{aligned}&x_{ik}\le UB_i&\forall i \in I, \forall k \in K \end{aligned}$$
(11)
$$\begin{aligned}&u_{0k}=1&\forall k \in K \end{aligned}$$
(12)
$$\begin{aligned}&2\le u_{ik} \le n+1&\forall i \in I, \forall k \in K \end{aligned}$$
(13)
$$\begin{aligned}&u_{ik} - u_{jk} +1 \le n\cdot (1-y_{ijk})&\forall i \in I,\forall j \in I, \forall k \in K \end{aligned}$$
(14)
$$\begin{aligned}&u_{ik} \in \left\{ 2,3,\ldots ,n,n+1 \right\}&\forall i \in I, \forall k \in K \end{aligned}$$
(15)
$$\begin{aligned}&y_{ijk} \in \left\{ 0,1 \right\} , x_{ik} \in \mathbb {Z}_{+}&\forall i \in I, \forall j \in I,\forall k \in K \end{aligned}$$
(16)

The proposed target function (1) combines three levelling targets: The first part assures that the deviations of daily utilizations should be as smooth as possible. The second part minimizes the sum of changeover times relative to the production time. The third part assures that the order of runner-products should be as similar as possible to benefit from economies-of-repetition. A similarity measure for the VRP based on the Jaccard-Index has been proposed by [6] and is adapted in this article for levelling purposes. The sign()-function is taking the value 1 if either \(y_{ijk}\) or \(y_{ijk+1}\) equal 1 and can be modeled with a binary auxiliary variable. As similarity is maximized, the negative sign is used. All three components are weighted with the factors \(\lambda _{Uti}\), \(\lambda _{CO}\) and \(\lambda _{Sim}\).

Constraints (2) and (3) assure that the dummy state is reached at the beginning and end of each day. Equation (4) assures that if a changeover to a product h is planned, a changeover from h to another product must be conducted as well. Equation (5) assures that each product can only be produced once per day. Fulfilling the demand is assured by (6). Equation (7) constrains that product i can only be produced if a changeover from i is conducted (M presents a big number, e.g. the total demand for i). Equation (8) models the EPEI. Example if the EPEI is 3 for 3 production days, production must occur exactly once on either day 1, 2 or 3. Equation (9) is the capacity constraint which assures that the available daily production time is not exceeded. Equation (10) calculates the daily used production time which is necessary for the target function. One disadvantage of solutions of (1) is that lot-sizes on product-level can fluctuate at lot. From the viewpoint of the Lean-Philosophy only a small variance of lot-sizes should be reached to avoid demand peaks for part suppliers. Therefore, restriction (11) captures an upper bound \(UB_i\) for each \(x_i\). For the calculation of \(UB_i\) the demand is spread evenly over the production occurrences: \(UB_i = \left\lceil \frac{D_i}{ \frac{n_{WD}}{EPEI_i} } \right\rceil \)

Equations (12)–(15) represent the subtour elimination constraints to exclude impossible subcyles in the production plan according to the formulation of [10]. \(u_{ik}\) is an auxiliary variable which indicates the position of i in the production sequence on day k. Equation (16) restricts the range of the decision variables.

4 Results and Discussion

With the proposed target function four levelling targets are achieved: Production plans are smooth, repetitive, balanced in production mix and economic (long changeovers are avoided). The following example taken from a lot-size producer in the manufacturing industry demonstrates the desired properties.

Table 1 Product-specific input data
Full size table

For a production line with 17 products a levelling pattern needs to be designed for a fixation horizon of 10 days (2 weeks). 6 runner products with an EPEI of 1 are produced every day. Production orders are placed only in multiples of full pallet-sizes. All product specific input data is presented in Table 1. On each day 630 min are available for production and changeover times; all further OEE-losses are already considered. The weights for the target function \(\lambda _{CO}\), \(\lambda _{Uti}\) and \(\lambda _{Sim}\) are all set to \(\frac{1}{3}\). Initial and final setup times to the dummy product are set to 0. The optimization model has been implemented with Gurobi version 6.0.0 on a standard PC with 3.0 GHZ and 4 GB of RAM in multi thread mode with four cores. Optimization runtime is limited to 1 h. The optimized production plan is visualized in Fig. 1.

Fig. 1
figure 1

Levelled production plan

Full size image
Fig. 2
figure 2

Previous production plan created by myopic changeover heuristic

Full size image

It can easily be seen that all four levelling targets are achieved. All runner products are produced in a repetitive sequence. Except for day 9 the daily production volume is almost perfectly smooth. The deviation on day 9 results due to the uneven demand of pallets which do not match the production days (e.g. demand for product B is 36 pallets, so 3,6 pallets is the ideal production rate per day, but only full pallets are allowed). Moreover, the results reveal that the planned available production time is too high and can be significantly reduced.

Compared to the previous production plan in Fig. 2 calculated by a myopic heuristic only considering changeover times, workload smoothness can be improved by 62 % (first component of (1)), changeover times by 37 % and similarity by 19 %. Due to the production in full pallet-sizes the fluctuation of lot-sizes can’t be improved. For future research the proposed model offers many opportunities for either refinement or more efficient solution methods. Our experiments show that for models up to 100 products the solver can find acceptable solutions with an optimality gap below 10 %. However, due to the exponentially growing number of variables, solutions for bigger problems do not possess the desired properties any more. Therefore, the development of meta-heuristics such as multi-criteria genetic algorithms offers interesting potential for future research.