Level Scheduling for batched JIT supply

Abstract

A mixed-model assembly line requires the solution of a short-term sequencing problem which decides on the succession of different models launched down the line. A famous solution approach stemming from the Toyota Production System is the so-called Level Scheduling, which aims at distributing the part consumption induced by the model sequence evenly over time. Traditional Level Scheduling seeks to closely approximate target demand rates at every production cycle, however, such a strict leveling is only required if parts are directly pulled from a connected feeder line. In real-world assembly lines, parts are predominately delivered in (small) batches at certain points in time. In such a situation, a Just-in-Time supply is already facilitated whenever the cumulative consumption is leveled in accordance with each part’s delivery schedule, while the exact consumption pattern between two delivery points seems irrelevant. The paper on hand provides new Level Scheduling models, proves complexity, presents exact and heuristic solution procedures and shows inferiority of traditional Level Scheduling for such a batched JIT-supply of parts.

Appendix: NP-hardness proof for LSQ

We prove NP-hardness for LS^Q by a reduction from a specific Partition problem. The Balanced Partition problem is NP-Hard (see Garey and Johnson, 1979) and can be stated as follows:

Balanced partition problem: Given 2n positive integers a _i (i = 1, ..., 2n) with $\sum_{i=1}^{2n} {a_i}=2B$ does there exist a partition of the set {1, 2, ..., 2n } into two sets {A₁, A₂ } of equal cardinality |A₁| = |A₂| = n such that $\sum_{i \in A_1} {a_i}= \sum_{i \in A_2} {a_i} = B?$

Reduction from balanced partition to LS^Q: The idea of the reduction is as follows. We will construct an instance of LS^Q with an uneven number of production cycles and force part deliveries to occur exactly at the middle position of the production sequence by using a well-known result of Level Scheduling by Kubiak and Sethi (1991). For this purpose, we introduce two conflicting parts, whose coefficients reflect the integers of Balanced Partition and are adapted in such a way, that whenever the cumulated consumption of one part exceeds its delivery quantity, then the cumulated demand of the other part falls below its delivery quantity, respectively. This will yield the required partition.

Consider an instance of LS^Q with parts P = {1, 2, 3, 4}, T = 2n + 1 production cycles and models M = {1, 2, ..., 2n, 2n + 1} with demands $d_m = 1 \quad \forall m \in M.$ Let the delivery quantities be q ₁ = B, q ₂ =  (n − 1)B, q ₃ = 2n + 1 and q ₄ = 1 and initial inventories be s ₁ = B, s ₂ = (n − 1)B, s ₃ = n and s ₄ = 2n ² + n. The part consumption for the first 2n models is:

$$ \begin{array}{ll}\begin{aligned} a_{1m}& = a_m\\ a_{2m} &= B - a_m\\ a_{3m} &= 1\\ a_{4m} &= m \\ \end{aligned}\end{array}\quad \forall m \in M \backslash \{ 2n+1 \} $$

(23)

The part coefficients of the last model are a _1,2n+1 = a _2,2n+1 = a _4,2n+1 = 0 and a _3,2n+1 = n + 1. Such an LS^Q-instance can be derived from any instance of Balanced Partition polynomially in n, where the first 2n models correspond to the 2n integer values of Balanced Partition.

Notice that due to the definition of parameter values the total numbers of deliveries for the first three parts are equal to $Y_1=\frac{2B-B}{B}=Y_2=\frac{(2n-2)B-(n-1)B} {(n-1)B}=Y_3=\frac{3n+1-n}{2n+1}=1 ,$ where $Y_p = \sum_{t=1}^T {y_{pt}}$ and therefore r ^′₁  = r ^′₂  = r ^′₃  = 1/(2n + 1). The initial inventory of Part 4 is sufficient for satisfying total part consumption, so that $Y_4=\sum_{t=1}^T {y_{t4}}=\frac{2n^2+n-2n^2-n}{1}=0$ and no delivery is required. As a consequence, part 4 does not influence the objective value of solution sequences and we will concentrate on the first three parts in the following.

Kubiak and Sethi (1991) show for the PRV Problem (Miltenburg 1989) that a number of copies of a model family can be evenly distributed in an assembly sequence by computing “ideal due dates” for each copy. This results directly from the fact that the penalty function which measures deviations is nonnegative, convex and takes the value of zero only at zero deviation. It follows that if all copies can be assigned to their respective due date, then the deviation from the target rate is minimal for this model family. The copies of model families directly translate to the number of deliveries per parts. Since we use the same deviation function as in the PRV, we can thus use this insight to derive a sufficient optimality condition for LS ^Q. Let D ^* _p denote the set of ideal delivery points for part p. This set is computed by

$$ D^{\ast}_p = \left\{\left\lceil \frac{2k-1}{2r_p^{\prime}} \right\rceil :k=1,\ldots,Y_p \right\} $$

(24)

As the first three parts all require exactly one delivery, ideal due dates according to (24) are also equal: $D^{\ast}_1 = D^{\ast}_2 = D^{\ast}_3 = \left\{n+1 \right\}.$ In other words, the delivery should ideally be scheduled at the middle position of the production sequence for all three parts. Notice that we can use this insight to compute a tight lower bound for such an LS^Q-instance which we will denote as $\hbox{LB}=\sum_{p=1}^{3} 2 \times \sum_{t=1}^n t \times (r_p')^2 = 6 \times \sum_{t=1}^n t \times \left(1/(2n+1)\right)^2.$ Kubiak and Sethi (1991) further show that (for sequences of uneven lengths) any deviation k′ from this middle position leads to additional deviation penalties per part p of ΔZ _p  = (2k′ − 1) × r ^′ _p . We can thus conclude that for a solution to such an LS ^Q-instance, Z = LB holds if and only if y _1,n+1 = y _2,n+1 = y _3,n+1 = 1.

We will show that the decision problem which answers the question of whether there exists a solution to an LS^Q-instance of the described form with Z ≤LB is at least as hard as Balanced Partition.

The solution of any YES-instance of Balanced Partition can be transformed to a solution of LS^Q by simply arranging the sets A ₁ and A ₂ and the additional last model as follows:

$$ \pi := < A_1 \quad A_2 \quad 2n+1>, $$

where the internal order of members in sets A ₁ and A ₂ can be determined arbitrarily. It can be easily verified that such a solution sequence always allows that delivery points are set to their ideal due date for all relevant parts. As a consequence, the resulting objective value of such a solution will be LB, so that it provides a certificate for a YES-instance of LS^Q.

We further established that for any YES-instance of LS^Q it has to hold that deliveries occur at the ideal middle position for the first three parts. Any early or late delivery would lead to increased deviation penalties. From restrictions (5)–(10) of the LS^Q model we can deduce two necessary conditions which allow such a timely delivery. It has to hold that:

$$ \sum_{t=1}^n \sum_{m \in M}{x_{mt} a_{pm}} \le s_p \wedge \sum_{t=1}^{n+1} \sum_{m \in M}{x_{mt} a_{pm} } > s_p \quad \forall p \in P \backslash \{ 4 \} $$

(25)

If the first condition is violated, part delivery needs to be scheduled earlier than n + 1, if the second condition is violated, deliveries need to be scheduled later. It immediately follows from (25) that model 2n + 1 cannot be scheduled in the first n slots of the sequence, since a _3,2n+1 = n + 1 > s _p  = n. Instead, the first n slots of the sequence need to consist of a subset of size n of the first 2n models. Due to the definition of part coefficients, it holds for any subset M′ of M that the cumulated part consumptions of the first two parts are $\sum_{m \in M^{\prime}} a_{1m} = |M^{\prime}|\times B - \sum_{m \in M^{\prime}} a_{2m} \quad \forall M^{\prime} \subset M.$ As a consequence, it holds for a subset M ^* of size n, that if $\sum_{m \in M^{\ast}} a_{1m} < B$ then $\sum_{m \in M^{\ast}} a_{2m} > (n-1)B.$ In other words, if the total consumption of part 1 up to cycle n is strictly smaller than its initial inventory B, then the total consumption of part 2 violates (25) and vice versa. It follows for a certificate of a YES-instance of LS^Q that $\sum_{t=1}^n\sum_{m \in M}{x_{mt} a_{pm}} = B,$ which directly yields the required balanced partition. We can conclude that an instance of Balanced Partition is a YES-instance, if and only if the corresponding LS^Q-instance is a YES-instance, which completes the proof. □