A GRASP for simultaneously assigning and sequencing product families on flexible assembly lines

Abstract

This paper introduces a new model and solution methodology for a real-world production scheduling problem arising in the electronics industry. The production environment is a high volume, just-in-time, make-to-order facility with volatile demand over many product families that are assembled on flexible lines. A distinguishing characteristic of the problem is the presence of non-traditional sequence-dependant setup costs, which complicate our ability to find high-quality solutions. The scheduling problem arose when product variety exceeded the mix that the existing lines could accommodate. A nonlinear integer programming formulation is presented for the problem of minimizing setup costs, and a greedy randomized adaptive search procedure (GRASP) is developed to find solutions. To select the GRASP parameter values, an efficient, space-filling experimental design method is used based on nearly orthogonal Latin hypercubes. The proposed methodology is tested on actual factory data and compared to a prior heuristic presented in the literature; our heuristic provides a cost savings in 7 out of the 10 cases examined, and an average improvement of 17.39 % which is shown to be highly statistically significant. This improvement is due in part to the introduction of a pre-processing step to determine preferential and non-preferential line assignment information.

Appendix: Triangle inequality proof

Using the same notation as in Sect. 3, let G=(V,A) be an undirected graph representing an instance of the assignment and sequencing components of the full scheduling problem. Recall that the nodes in V correspond to each possible set of families that can be on a single line at the same time and the arcs in A correspond to feasible transitions between nodes. Two nodes i and j are connected if and only if they differ by a single family. The arc cost c _ij is equivalent to the number of parts that must be placed on the line plus those that must be removed when some family in node i is removed and the new family is added, where the new family is the family in node j that is not already on the line. Parts not needed for any family in node j must be removed implying the symmetric relationship c _ij =c _ji .

Also note that the node set V does not contain the depot. The constraints that define the problem restrict the path of any line to only go through the depot node O once, and the arcs leaving the depot are uniquely predetermined by the families on lines at the beginning of the shift. Therefore, it is not possible for node O to appear at an intermediate point along a path which prevents the use of a path through node O to obtain a lower cost than the cost of a path whose only difference is the exclusion of node O. The triangle inequality (TI) then only needs to hold for graph G.

Proposition 1

The triangle inequality with respect to the cost matrix c=(c _ij ) holds for the graph G=(V,A).

Proof

Without loss of generality, consider the three-node subgraph in Fig. 6 for the five families A, B, C, D, E. We need to show that c ₁₃≤c ₁₂+c ₂₃ (the other cases in the subgraph admit identical arguments).

Fig. 6

Three-node subgraph

The arc cost c _ij is the sum of the setup costs for each individual part, where the setup cost for part p is $c^{p}_{ij}$. It is therefore sufficient to prove that

$$ c_{13}^{1} + c_{13}^{2} + \cdots + c_{13}^{n} \le c_{12}^{1} + c_{12}^{2} + \cdots + c_{12}^{n} + c_{23}^{1} + c_{23}^{2} + \cdots + c_{23}^{n} $$

(2)

is true for every positive integer n.

For n=1, which is the case where a single part contributes to the setup costs:

For the TI to be violated for two paths 1→3 and 1→2→3, we must have $c_{13}^{1} > c_{12}^{1} + c_{23}^{1}$ which is only possible if $c_{13}^{1} = 1$ and $c_{12}^{1} = c_{23}^{1} = 0$. For any single part, there are two possible cases that can result in $c_{13}^{1} = 1$: either family C needs the part and family D does not, or family D needs the part and family C does not. In addition, we need to consider whether or not family E requires the part which, in combination with the first two cases, gives us four cases.

Case 1: Families A, B, D and E do not require the part and family C does require the part.

Since one of the families in node 1 requires the part, and no family in node 2 requires the part, the part must be removed from the line on arc 1→2 so $c_{12}^{1} = 1$ and the TI is not violated.

Case 2: Families A, B and D do not require the part and families C and E do require the part.

In this case families in both nodes 1 and 2 require the part so $c_{12}^{1} = 0$. However, none of the families in node 3 require the part so the part must be removed on arc 2→3, so $c_{23}^{1} = 1$ and the TI is not violated.

Case 3: Families A, B, C and E do not require the part and family D does require the part.

In this case none of the families in nodes 1 or 2 require the part so $c_{12}^{1} = 0$. However, family D does require the part so the part must be added on arc 2→3, so $c_{23}^{1} = 1$ and the TI is not violated.

Case 4: Families A, B, and C do not require the part and families D and E do require the part.

Since none of the families in 1 require the part, but a family in 2 requires the part, the part does need to be added on arc 1→2 so $c_{12}^{1} = 1$ and the TI is not violated.

Therefore there is no possible case for which the TI can be violated when n=1.

Now we assume the TI holds for k:

$$ c_{13}^{1} + c_{13}^{2} + \cdots + c_{13}^{k} \le c_{12}^{1} + c_{12}^{2} + \cdots + c_{12}^{k} + c_{23}^{1} + c_{23}^{2} + \cdots + c_{23}^{k} $$

(3)

where k is a positive integer.

So for the TI to hold we need to prove that

(4)

In light of (3), the inequality in (4) reduces to $c_{13}^{k + 1} \le c_{12}^{k + 1} + c_{23}^{k + 1}$ which we now must show is true. However, this reduced inequality is equivalent to the case where n=1, which we have shown above to be true.

Hence, by the principle of mathematical induction, (2) is true for every positive integer n and therefore the TI holds for G. □