Mobile Edition
Print
Get the Mag
Weekly Updates1. Introduction
In a mixed-model assembly line, setup times and costs are reduced sufficiently enough to be ignored, so that different products can be jointly manufactured in inter-mixed product sequences (lot size of one) on the same line (c.f., Schon-berger (1982, ch. 6)). In spite of the tremendous efforts to make production systems more versatile, this usually requires the production processes to be quite homogenous. As a consequence, typically, all models are variations of the same base product and generally only differ in specific customizable product attributes, also referred to as options.
During the configuration planning of an assembly line the so-called Assembly Line Balancing Problem (ALBP) has to be solved which determines the assignment of tasks and all their required resources to the workstations of the line (e.g., Baybars, 1986; Scholl and Becker, 2006; Boysen et al., 2007a, 2008; Becker and Scholl, 2006). For an algorithmic solution and to reflect the usual necessity to assign tasks that are common for several models to the same station, the mixed-model ALBP is regularly transformed to a single-model problem by the use of a joint precedence graph (Thomopoulos, 1970; Macaskill, 1972; Van Zante-de Fokkert and De Kok, 1997). Here, the model-dependent processing times of tasks are averaged with regard to the estimated demand portions (probabilities) of respective models in the model mix and are then used to form a unique precedence graph.
The recent trends of mass customization (Pine, 1993) and assembly to order (Mather, 1989) lead to a tremendously increased product variety, so that, in many fields of business, the product variety is too large to allow consideration of all models and the explicit forecasting of demands. For example, many car manufacturers offer their cars in a huge number of models, which can be configured by combining the options offered. Table 1 (extracted from Pil and Holweg (2004)) shows a selection of car types produced by European car manufacturers together with the number of offered product options (divided into the four groups car bodies, power trains, paint-and-trim-combinations and factory-fitted equipment options) and the number of (theoretically) resulting models. For further information on the product variety of the car manufacturers BMW and Mercedes see Meyr (2004) as well as Roder and Tibken (2006).
Table 1 shows that the number of models grows exponentially with the number of options. For example, if there is a set of n pairwise independent zero/one options, a total of [2.sup.n] models result.
Because only a small selection of these (theoretical) option combinations are actually demanded and, thus, only very few models are repeatedly assembled, there is no adequate basis for estimating future demand rates. This is particularly true for manufacturers of luxury class automobiles who state that only a very few different models are sold more than once a year (Meyr, 2004). Instead, reliable estimations can be provided only for the frequency of option occurrences over all models (option mix), e.g., the percentage of cars equipped with air conditioning. Moreover, a procedure for generating a joint precedence graph, which has to iterate through all possible models, suffers from exceptionally high computational requirements. Consequently, the generation of joint precedence graphs needs to be altered to account for this fundamental change in information and should be based on the options and the respective option mix.
Increasing product variety is not a phenomenon confined to car manufacturers (e.g., Randall and Ulrich (2001)). Although the examples presented throughout this paper all stem from the automobile industry, the proposed approach is highly recommendable for configuration planning of any mixed-model assembly line which is confronted with a high degree of product variety.
The remainder of the paper is structured as follows. Section 2 briefly summarizes the generation of traditional joint precedence graphs based on model mix forecasts, whereas Section 3 describes a modified approach based on an option mix forecast. Section 4 compares both approaches with respect to effort and outcome. In Section 5, the relevance of the introduced approach is compared to common business practice and evaluated by a computational experiment. The insights are then summarized in Section 6.
2. Model-based generation of joint precedence graphs
The traditional generation of a joint precedence graph requires information about the individual precedence graphs [G.sub.m] = ([V.sub.m], [E.sub.m], [t.sub.m]) of each model m [member of] M. The node set [V.sub.m] contains the model-specific tasks, the arc set [E.sub.m] reflects precedence relations (i, j) between tasks i. j [member of] [V.sub.m] and the vector of node weights [t.sub.m] contains the processing times [t.sub.im] of the tasks i [member of] [V.sub.m]. Additionally, demands for each model throughout the planning horizon have to be estimated, so that demand portions 0 [less than or equal to] [P.sub.m] [less than or equal to] 1 for each model m with [[SIGMA].sub.m[member of] M] [P.sub.m] = 1 can be determined. This is usually done by counting model occurrences in the sales database which are adjusted based on market analyses.
The joint precedence graph G = (V, E, [bar.t]) results from the following definitions (e.g., Macaskill, 1972; Van Zante-de Fokkert and De Kok, 1997):
V = [[union] (m[member of]M)][V.sub.m], (1)
[[bar.t].sub.i] = [summation over (m[member of]M)][P.sub.m] x [t.sub.im] [for all]i[member of]V, (2)
E = [[union] (m[member of]M)][E.sub.m]{redundant arcs}. (3)
As a prerequisite for the generation of the joint node set V in Equation (1), tasks which are common to different models, albeit requiring different processing times, receive a model-wide consistent node number. This impedes an assignment of these tasks to different stations, which otherwise would necessitate multiple investments in required resources at each station to which a duplicate task is assigned. Tasks not required by a model receive a processing time (node weight) of zero. Thus, average processing times [[bar.t].sub.i] can be simply calculated by weighting each model-specific task time [t.sub.im] with the respective demand portion [P.sub.m] of the model in Equation (2). Equation (3) determines joint precedence constraints by joining the model-specific arc sets. This can lead to redundant arcs (i, j) which represent transitive precedence relationships. An arc is redundant and can thus be deleted without loss of information, if there exists another path from node i to j with more than one arc.
Further steps have to be performed, if conflicting precedence relations exist between models which lead to cycles in the joint precedence graph. To enable a unique processing sequence of tasks these cycles have to be eliminated by one of the following actions (c.f., Ahmadi and Wurgaft (1994)):
1. The models have to be separated into subsets in such a manner that two or more acyclic joint precedence graphs can be formed. During physical production, this leads to setup operations which have to be performed whenever production changes from one subset of models to another.
2. In order to achieve a unique task station assignment, cycles in the precedence graph can be eliminated by a duplication of nodes. To minimize the number of duplicated nodes and therefore reduce the danger of assigning equal tasks to different stations an optimization problem has to be solved (see Ahmadi and Wurgaft (1994)).
Figure 1 exemplifies the generation of a joint precedence graph based on a model mix forecast.
[FIGURE 1 OMITTED]
All known solution procedures for mixed-model ALBP rely on the joint precedence graph which is, thus, indispensable for solving such problems. However, it is sometimes not sufficient to consider a mixed-model problem as a single-model problem based on average task times and unique task-station assignments only. Therefore, additional approaches have been proposed.
1. Complementing the necessary consideration of average task times, some researchers propose examining and reducing station time variations over the models in order to reduce inefficiencies whenever the short-term model mix deviates from the expected one and to facilitate short-term sequencing (e.g., Thomopoulos (1970), Decker (1993), Domschke et al. (1996)). This approach is called horizontal balancing (Merengo et al., 1999) and requires model-based task times. These times are used as a basis for computing average task times and, thus, are already available without further computation.
2. Sometimes, it is not necessary or even infeasible (due to cycles as discussed above) to assign tasks that are common to several models to the same station. In that case, additional resources are required which have to be considered explicitly in a resource-based model or implicitly based on a cost function. The latter approach is examined by Bukchin and Rabinowitch (2006). Here, information on the additional cost for duplicating tasks is required and the tasks for which this duplication is possible are simply left separate within the joint graph as proposed by Ahmadi and Wurgaft (1994).
Irrespective of the approach chosen, the (huge) number of models restricts the applicability of the model-based problem view. The option-based view presented in the next section is useful in any case, for directly generating the joint precedence graph and also for smoothing station loads and minimizing task duplication cost.
3. Option-based generation of joint precedence graphs
Our modified approach adopts the general procedure and the structure of the joint precedence graph regarding node set V and arc set E of the traditional approach. All tasks and their respective precedence constraints are transferred to an acyclic joint precedence graph. Cycles are resolved by node duplication. The main difference consists in determining the expected joint task times based on the estimated fraction (interpreted as probability) of product units containing certain options (option mix) instead of respective forecasts for the huge number of individual models (model mix) as discussed in Section 2.
FEED