Information on the types of machines.
Manufacturing cell formation and its balance in just-in-time (JIT) type production environments have usually been studied separately in the literature. This practice is unrealistic since both problems interact and affect each other when the cells are operating. This chapter proposes a methodology to design multiple manufacturing cells and simultaneously balance their workload. The cells considered are U-shaped and process mixed models of product families. A nonlinear integer programming mathematical model is proposed, which integrates cell formation and their balancing, considering various production factors. For illustration, the method is applied to the redesign of a rack manufacturing process.
- manufacturing cells
- assembly line balancing
- N U-lines
- mathematical programming
- mixed model production
Group technology (GT) can be defined as a manufacturing philosophy identifying similar parts and grouping them together to take advantage of their similarities in manufacturing and design [1, 2]. Cellular manufacturing (CM) is an application of GT and has emerged as a promising alternative manufacturing system . When a productive system is changed to make it cellular, it implies solving the manufacturing cell formation problem (MCFP), which means identifying groups of machines and associating them with product families so that the intercellular traffic that the products can have within the productive system is minimized. This problem has been approached historically by analyzing the machine-product incidence matrix (A), where each row represents a machine and each column represents a product, with each element aij equal to one if machine i processes product j, and equal to zero otherwise. When this matrix is partitioned arbitrarily, it is usual to have products that remain outside the diagonal blocks (cells), which are called exceptional elements, since they carry out intercellular movements. Papaioannou and Wilson  reviewed the approaches between 1997 and 2008 to solve the above problem, proposing taxonomy based on the solution methodologies. It must be kept in mind that the latter approaches have started taking into account production factors other than the incidence matrix, like processing time, demanded production volumes, and operation sequences. Most recent works [4, 5, 6, 7] are oriented mainly to the heuristic and metaheuristic approach to solve the problem, without considering other factors that appear when there are exceptional products that carry out intercellular movements, implying that these different production cells are linked with one another due to the precedence restrictions of these exceptional products, without considering their cost and work under way. This means that in most real cases, it is not possible to analyze the manufacturing cells independently at the time of attempting to balance the load of their work stations, and furthermore, since those cells would be related with families of products, it is therefore possible to introduce the balancing concept of multiple manufacturing cells for mixed models. This happens because cellular manufacturing is commonly used in JIT-type productive systems, in which setup times can be reduced in such a way that each cell works by operating over a family of mixed product models. These cells can also be configured in U shape to use the advantages generated by this configuration. An approach to the above situation is the work of Kumar et al. , who propose implementing heuristic cell formation, having the capability to handle production data, operation sequence, production volume, and inter-cell cost simultaneously, taking up some of the previously described elements.
On the other hand, the problem of balancing N U-shaped lines has been studied mainly by Sparling  and Miltenburg , both of whom considered that all the cells operate with a common cycle time (C), but they assume that each cell is independent of the rest and furthermore process a single product. The problem of balancing U-shaped lines for mixed product models (denoted by MiMULBP) was proposed for the first time by Sparling and Miltenburg , who used the classical combined precedence graph proposed by Thomopoulos  and considered as cycle time (C) the quotient of the time period (T) and the total product demand (D). These authors focused only on the problem of balancing a single cell, making in the appendix the observation that it is possible to consider systems with multiple manufacturing cells, although once again they considered that those cells are independent of one another. More recently, in [13, 14], new heuristics are introduced to solve the problem, and Turkay  proposes models of integer linear programming (MILP) considering restrictions that express the precedence of the tasks.
A very recent work  proposes a novel configuration of assembly lines, namely parallel adjacent U-shaped assembly lines (PAUL), but none of the revised works integrate the balancing of U-lines with the design of the manufacturing cell. In the present chapter, what is being sought is to integrate these problems, proposing a methodology that delivers cells more applicable to reality, thereby introducing the problem of the formation and balancing of N in U-shaped cells for mixed models (denoting it by N-MiMUCFBP). The rest of this chapter is organized as follows: Section 2 introduces a methodology based on a mathematical model for the N-MiMUCFBP; Section 3 illustrates the proposed methodology using a real case, showing its results; and Section 4 gives the conclusions of the study.
The proposed methodology is based on formulating a new model for the problem of balanced formation of production cells. From the viewpoint of formation of the cells, the model must consider the aspects associated with their design, such as processing and preparation of machines, inefficiencies in the handling of materials or inventories of products being processed, and cell imbalance , which includes processing times, sequences, and production volumes, directly related with the mixed model assembly line balancing problem (MiMALBP). Because of this, and in agreement with the heuristic proposed by  for the MiMALBP, first it is necessary to group the precedence graphs of each final product in a single combined precedence diagram. This is possible, because in this type of mixed model assembly lines, the products that are processed in each cell have only small differences in processing times or in the elimination or addition of activities but always keeping the consistency among the precedence of these activities for the different product models. Therefore, the idea is for each manufacturing cell to process a family of products. In turn, using this combined precedence diagram will allow reducing the number of variables at the time of tackling the model for the formation of manufacturing cells. The methodology proposed for the N-MiMUCFBP problem considers five consecutive stages that are presented in Figure 1.
2.1 Calculation and assignment of the required machines
First it is necessary to determine the number of machines, qm, required per type of machine m. This number is obtained from (Eq. (1)).
where qm, number of machines of type m; j product number; dj production volume demanded of each product j within the planning horizon (in units); tmj unit processing time for product j that is processed in a type m machine (in hours per unit produced); CAPm capacity of each type of machine m within the planning horizon (in available machine hours).
It should be noted that when a machine of a certain type can work simultaneously on a product together with another machine of the same type and qm > 1, the machines will operate as a single “virtual machine,” i.e., that qm machines of type m (denoted by i = m) will work simultaneously in it and that the unit processing time of each of these machines will be tij = tmj/qm, provided that the products processed on that virtual machine are similar to each other. On the other hand, for that type of machine in which qm > 1 and which furthermore can operate simultaneously on a product together with another machine of its same type, it is necessary to assign first which products will be processed on each machine of type m. For that purpose, let us use the following notation:
= capacity used by machine i.
= leveled reference capacity used by qm machines of type m.
wmj = workload to be assigned of model of product j on the type of machine m.
= fraction assigned to machine i of the demand for product j.
Bm = arrangement that contains the models of products similar to each other processed on type m machine, arranged in decreasing order according to wmj.
tij = Unit processing time on machine i due to product j.
Then the following procedure, shown in Figure 2, is proposed as a formal assignment rule.
In particular, when qm > 1 and the type m machines cannot work simultaneously, the above procedure aims to assign similar products to each of the qm machines, so that they have a workload as close as possible to the leveled load for that type, and it also attempts to have the demand for each product as little fractionated as possible, so that each product is assigned to a single machine when it has sufficient capacity.
This procedure is followed in order to not incorporate directly in the mathematical model the alternative processes and routes, because in this way its complexity and number of variables are reduced. Special care must be taken when assigning similar products (with respect to their precedence relations) to the different machines, to minimize probable intercellular motions.
2.2 Preparation of the extended combined precedence diagram
With the machines required to satisfy the capacity restrictions, and the assignment of each product to them, an extended combined precedence diagram called GUG’ must be created, and the weighted average processing times for each machine must be calculated. The process for preparing this diagram will be described now by combining the precedence diagrams of each model in a single precedence diagram where the nodes represent the operations and the arcs represent the precedence restrictions between the operations. A formal description of the combination of n product models in a combined precedence diagram was made by Macaskill . This procedure, adapted to our problem, is summarized as follows: Represent the precedence diagram of product model j by means of the graph Gj = (Vj, Ej, tj), where the set of nodes Vj represents the set of tasks of product model j, the set of arcs Ej represents the precedence relations (a, b) between tasks a, b∈ Vj, and the weighting vector tj contains the processing times tij of task i ∈ Vj.
As an example, in Figure 3 the precedence diagrams for six models are represented, remarking the virtual machines in which more than one machine operate simultaneously on the products.
Furthermore, by specifying the demanded volumes of each product model within the planning horizon (dj), it is possible to determine the demand fractions df’j of each model j with respect to the total demand D of the product mix, where 0 ≤ df’j ≤ 1 is fulfilled, and they are calculated by the following equation (Eq. (2)):
As a prerequisite for the generation of the combined set of nodes V in Eq. (3), the tasks that are common to different models, even though they have different processing times, receive a consistent number of nodes for all the models. This prevents assigning these tasks to different stations, which otherwise would need multiple investments in the resources required at each station in which a duplicate task has been assigned. Tasks that are not required by a product model receive a processing time (weight of the node) equal to zero, so the average processing times can be calculated simply by weighting every specific task fractionated time according to model with its corresponding demand portion df’j of the model in Eqs. (4) and (5), which determines the combined precedence restrictions by joining the arc sets of each model. This can lead to redundant arcs (a, b), which represent the transitive precedence relations. An arc is redundant and can therefore be deleted without loss of information, if there is another way from node a to node b by means of more than one arc.
The combined precedence diagram for the example is shown in Figure 4. Note that the redundant arcs are denoted by dotted lines.
A particular action should be considered if there is no consistency among the precedence of the activities, i.e., if there are conflictive precedence relations between different models that lead to a cyclic (that repeats itself over and over) combined precedence graph. To allow a single sequence of task operations, those loops must be deleted by means of one of the following actions proposed by Ahmadi and Wurgaft :
The models must be separated into subsets so that two or more acyclic precedence graphs can be formed. In practice, this leads to machine preparation operations that must be performed every time the production changes from one subset of models to another.
With the purpose of assigning the tasks to a single station, the loops in the precedence graphs can be deleted duplicating these nodes. To minimize the number of duplicate nodes and, in this way, reduce the danger of assigning equal tasks to different stations, an optimization problem must be solved .
To model what is related to the problem of balancing the N U-shaped lines, we will consider the concepts developed by Urban  to formulate the problem mathematically. For this we set up an auxiliary graph, connecting it with the original combined precedence graph. This is illustrated in Figure 5, denoting with dotted lines the auxiliary combined precedence graphs. If we start in the middle of this extended graph, it is possible to perform assignments to stations forward through the original graph, backward through the auxiliary graph, or simultaneously in both directions, and in this way, it is possible to create stations that have machines at the beginning and at the end of the “U” line. Special care must be taken when joining the auxiliary precedence diagram with the original. For example, final task 15 is joined only with initial task 5, because task 15 is finished only from task 5 for model 6 (see Figure 3).
2.3 Calculation of the parameters needed for the mathematical model
From the input information and the extended combined precedence diagram produced in the previous point, we must calculate the total costs for intercellular transport between machines i and i’ (cii’), which are determined by means of Eq. (6):
cii’ = cost of intercellular transport between machines i and i’ (within the planning horizon).
coj = intercellular transport cost of product j.
dj = production volume demanded by product model j.
= fraction assigned to machine i of the demand for product j.
= fraction assigned to machine i´ of the demand for product j.
Other parameters to be used in the model, some of which must be calculated, are the following:
cs = unit cost per work station (within the planning horizon).
V = set of machines of the combined precedence diagram, .
E = set of precedence relations between the machines that belong to V, . For example, e = (a, b) is the ordered pair that indicates that machine a precedes machine b immediately,
T = period of time available for planning.
tij = processing time on machine i of product model j.
dj = production volume demanded by product model j.
D = total demand for the product models, .
= common average cycle time, .
dfj = fraction of total demand for product model j, .
= maximum number of production cells to which a multicellular station can belong .
Kmax = maximum number of production cells (Kmax ≤ m). It can be specified based on diagram G, or the maximum bound (K´) proposed by Al Kattan  can be used as reference:
wi = marginal workload of machine i,
W = total workload, .
Kmin = minimum number of production cells. It can be specified based on diagram G, or a modification of the bound proposed by Al Kattan  can be considered:
= weighted average processing time of machine i,
GO = original combined precedence diagram. G = (V, E, ).
GA’ = auxiliary combined precedence diagram. G´ = (V, E′, ).
Mmin = minimum number of machines that a cell must contain, .
Mmax = maximum number of machines that a cell must contain, .
Smin = minimum number of work stations required, .
Smax = maximum number of work stations required (Smax ≤ m).
2.4 Mathematical model
2.4.1 Model assumptions
The assumptions of the proposed model are presented below:
Multiple similar models of a product are produced if possible in a single manufacturing cell.
The processing times of the tasks are known and constant.
Each task of the combined precedence diagram is performed for at least one product model.
The average time of each task is not greater than the average cycle time .
Each machine is assigned to a single work station for each product.
The operators can work in or out of the “U” cell.
In a manufacturing cell, the precedence restrictions are consistent among the different product models produced in it, i.e., if task a precedes task b in some model, then there is no other model in the cell in which task b precedes task a.
The precedence graphs of the product models are not fractionated, i.e., all the tasks to produce a product model are joined together directly or indirectly.
The mix of models, i.e., the demands for models within the planning horizon, is known with certainty (static problem).
There are no buffers between the work stations, so it is not possible for the work stations to operate at different production rates.
The workers are capable of performing any task in the manufacturing cell, i.e., they are capable of operating any machine.
The setup times of the machines are not significant.
The displacement times of the workers in a manufacturing cell are not significant, but not so out of them.
The machines related by some intercellular product movement must belong, if possible, to the same work station.
The following points present the notation and the proposed model:
h = work station (h = 1,…, Smax).
i, i’ = machine (i = 1,…, m).
j = product model (j = 1,…, n).
k = production cells (k = 1,…, Kmax).
xik = .
yk = .
uihG = .
rh = .
fkh = .
gh = .
184.108.40.206 Objective function
The objective of this formulation is to minimize the total cost of intercellular transport between machines, which will appear every time there are finished products between machines i and i’ and they belong to different production cells. Decision variables xik define the set of groups of machines, while the product families will be defined after the solution of this model, supported by the information of the extended combined precedence graph (GOUGA):
Restrictions for the formation of manufacturing cells:
Restrictions for the balance of U-shaped cells:
Linking restrictions between the formation and the balance of the cells:
Restrictions for defining binary variables:
The set of restrictions (8) restricts each machine to a single cell. The set of restrictions (9) restricts each created cell to a maximum of Mmax machines, while the set of restrictions (10) restricts them to a minimum of Mmin machines; the value of yk is equal to one for the first Kmin restrictions, since it is known that these cells are required. As to the balance of the lines, the objective is to minimize the cost per required work station in addition to the theoretical minimum, avoiding the need to have rh variables for stations 1 through . The set of restrictions (11) ensures that each machine is assigned to only one station, either in the original precedence graph or in the auxiliary one . The set of restrictions (12) ensures that for every station, the sum of the weighted average processing times of their assigned machines does not exceed the average cycle time; the values of rh are equal to one for the first restrictions. The set of restrictions (13) and (14) force the precedence restrictions between the machines; these relations are reversed for the auxiliary graph.
The set of restrictions (15) makes each variable fkh be equal to one when cell k is used by station h. The set of restrictions (16) allows a maximum of two multicellular work stations for each manufacturing cell, so that there are not many interferences between stations . The set of restrictions (17) limits to the number of cells to which a multicellular work station can belong, and it also makes every variable gh equal to one when h is a multicellular station. The set of restrictions (18) defines the decision variables xik, yjk, uih, rh, fkh, and gh as binary.
2.5 Assigning the product models to the obtained production cells
With the groups of machines obtained, we must now assign the product models to each resultant cell. For this, let:
Pkj = Number of machines of cell k that process product j,
= Set of cells that have the maximum number of machines that process j,
= Total workload (in hours) of cell k due to product j,
= Set of cells having maximum total workload due to product model j and belonging to ,
Then, to assign to which production cell each product j belongs, the following formal procedure is defined, where three cases can occur:
Case 1: If ; assign each product to the cell where it will be processed by more machines.
Case 2: If ; if there is a tie it must be assigned to the cell in which the product spends most processing time.
Case 3: If , assign j arbitrarily to a cell that belongs to ; if a tie occurs, assign the product to the cell with a smaller number of machines or randomly.
3. Application of the methodology: illustrative case
The company in which the proposed methodology will be applied is of the metalworking type, making storage products (racks) for the retail industry. The final products are assembled at the customer’s facilities, so the work orders are divided considering the final product’s components, which are generally pillars, beams, struts, slotted angles (ANRA), and accessories. Each of them can have various modifications in size, processing times, and complexity in its operations (precedence restrictions), so it is possible to identify them previously as families of products, therefore complying with the observations proposed by Burbidge , who says that a system can be naturally susceptible to be transformed into one of the cellular manufacturing type.
The company has a factory in the commune of Quilicura, in the Metropolitan Region of Chile, and has 31 machines that can be classified into 17 types, processing 67 different product models. The place where the methodology will be applied has a job shop-type configuration.
This study will consider a time planning horizon of 3 months, in which the plant operates 16 h/d from Monday to Saturday. According to the company’s policies, 1 day per month is devoted to preventive maintenance operations of each machine, so it will be considered that each machine has a capacity of 1248 h, within a planning horizon of T = 1296 h. Tables 1 and 2 present general information with respect to the types of machines and the different product models, respectively.
3.1 Step 1: calculating and assigning the required machines
|m (type of machine)||Identification characteristic||Present number||Simultaneous machine|
|1||Sheet metal cutter||3||No|
|4||25 tons press||2||No|
|5||45 tons press||2||No|
|6||55 tons press||2||No|
|7||90 tons press||1||No|
|8||Pneumatic press 160 tons||2||No|
|9||Sheet metal bender 2000 m||2||No|
|10||Sheet metal bender 3000 m||2||No|
|11||Sheet metal bender 4000 m||2||No|
|12||Sheet metal bender 160 ton||2||Yes|
|17||Forming machine ANRA||1||No|
|J (products)||Identification characteristic|
|60–67||Slotted angle (ANRA)|
Comparing these results with the actual values of the number of machines of a given type present in the plant, we get that they are equal for almost all the values of m, except in the following two cases:
m = 3, which means that one more machine must be bought to fulfill the required capacity of this type of machine.
m = 15, where there is currently one extra machine.
Case (a) explains in some way why machine 3 punching machine has become a bottleneck in the plant when “accessory”-type products are made. Maintain, in this study use will be made of the current excess capacity produced by the two type 15 machines (connector welder) reflected in case (b), assigning products to both machines.
Applying the proposed assignment procedure of Figure 2, we get the assignment of machines (i) to the (m) machine types and of products (j), which are presented in Table 4, where the fact that machine 12 will function as a “virtual machine” in which two machines will operate simultaneously is pointed out.
|1||1||1–4, 10–19, and 60–67||17||17||60–67|
|2||2||60–67||18||1||5–9 and 20–34|
|6||6||5–9 and 20–23||22||5||43–51|
|11||11||1–4 and 10–23||27||11||5–9 and 22–29|
|13||13||30–38||29||14||5–9 and 22–29|
|14||14||10–23||30||15||43 and 44|
3.2 Step 2: preparation of the extended combined precedence diagram
With the determination of the number of types of machines, and the assignment of products to machines obtained in the previous stage, the precedence restrictions deliver the extended combined precedence diagram shown in Figure 6, where the virtual machine 12 differs from the rest because in it the two benders with the largest capacity operate simultaneously in the production of pillar-type products. These products have a larger size, so it is advisable to use both benders one next to the other to mechanize the product and, in this way, reduce the processing time of this operation.
3.3 Step 3: calculation of the parameters needed for the mathematical model
The intercellular transport costs are shown in Table 5. The rest of the parameters to be used in the mathematical model were the following: average cycle time gives a value of Smin = 6, and a value of Smax = 10 was also considered. The number of cells obtained from the combined precedence diagram gave values of Kmin = 4 and Kmax = 6, which are adequate for the groups of machines that can be visualized previously, giving values of Mmax = 8 and Mmin = 5, respectively. All this information is presented in Tables 6, 7, 8.
|Kmin||Kmax||Mmax||Mmin||M||A||Smax||cs (MM$)||cb (MM$)|
|E||(8,12), (24,12), (12,16), (12,31), (1,2), (1,4), (2,7), (4,11), (7,17), (11,14), (18,4), (18,6), (18,21), (18,23), (18,5), (6,11), (6,27), (21,27), (23,27), (27,29), (5,10), (3,10), (3,9), (10,13), (9,13), (19,3), (19,22), (19,20), (22,26), (20,26), (20,25), (25,30), (25,15), (26,28), (30,28), (15,28)|
3.4 Step 4: statement and solution of the mathematical model
With the parameters calculated above, we state the mathematical model. The model was then solved using the Extended LINGO© version 8.0 software, getting an optimal global solution in 2 h and 32 min, after 121 iterations, giving as a result 5 manufacturing cells and 9 work stations, 3 of them multicellular, because they process exceptional products. This solution is represented in Figure 7.
3.5 Step 5: assigning the product models to the production cells
With the groups of machines obtained thanks to the model’s solution, the product models were assigned to each of these production cells. This solution is represented in Table 9.
The proposed cellular manufacturing system that results from the application of the methodology shows the resultant cells and the product families assigned to them, where it is seen that cell 1 processes products of the beam and slotted angle type, cells 2 and 3 process only accessories, cell 4 processes only beams, and cell 5 processes only pillars. In this way, it is easier to improve the obtained balance by sequencing mixed product models, because in a cell there are no different types of products that compete for the same resources (machines), but they rather process the same types of products, grouped in families. Only work stations 1, 2, and 8 turn out being multicellular, because they process exceptional products that undergo intercellular movements, most of which are associated with the operation of the cutter type machines, since they are those that are mostly shared by the different products.
To analyze the results, it is necessary to have performance measures of the solution, but since the present study has taken up a new problem that is part of the manufactured cell formation problem (MCFP) and the general assembly line balancing problem (GALBP), we must use measures of performance commonly employed for both problems separately, such as group capability index (GCI), for example, proposed by Seifoddini and Hsu , and the grouping efficacy (GE) proposed by Kumar and Chandrasekharan , as well as balancing measures like “total line imbalance” proposed by Thomopoulos . Table 10 presents a comparison of results of the case study by the proposed methodology versus the model of Won and Currie , considering the latter as an MCFP-type problem. The model of  was chosen because it considers a number of production factors and a complexity level relatively similar to the proposed methodology, and it can be solved in Lingo© in a reasonable computation time.
In Table 10, it is seen that the proposed methodology takes more time to get the global optimal solution as well as a greater number of iterations compared to the model of . This can be explained because in the proposed model of the methodology the first component of the formulation is of a quadratic type, so the LINGO© software uses an algorithm specialized in these types of problems which makes each iteration take longer time; on the other hand, the model of  is of the p-media type, which although linear, in terms of the quality of the solution, it is seen that the proposed methodology gives a group capability index (GCI) greater than the model of . We believe that this is due to the fact that the proposed formulation puts emphasis in minimizing the costs of intercellular product movements, in contrast with the model of Won and Currie , which aims to maximize the similarity between the machines that constitute the production cells. On the other hand, with respect to the grouping efficacy (GE), the proposed methodology is better than the model of . Making a deeper analysis of the results and getting more general conclusions is risky because it is necessary to do further research with study cases in which the indicators and models used can be compared. In relation to the comparison of indicators such as the total imbalance of the line proposed by Thomopoulos  under the viewpoint of the general assembly line balancing problem (GALBP), it was not done, and it is expected to be dealt with in an extension of the present work.
This work has proposed a new way of approaching balancing and cell formation problems, which were previously studied independently. In this way, it is possible to consider aspects that were previously avoided, such as production volumes, processing times, and operation sequences for the MCFP, and the fact that the production cells are not established yet and that they also share information among themselves, for balancing the lines. In the proposed methodology, a model is presented that has advantages at the time of solving it with a commercial software, because it does not need as many variables as other proposals. This approach delivers cells that are more amenable to be used in practice, although it will remain for future research to deliver immediately the layout of the cells as well as to integrate the problem of sequencing mixed models and, in that way, to improve the balance of each station.
In relation to the preliminary results obtained by comparing with another mathematical model from the viewpoint of a type MCFP problem, it must be pointed out that although the grouping efficacy indicators are better, they are not conclusive if a comparative study with more study problems as well as a sensitivity analysis of the parameters of the proposed model is not made. The same comparative study must be made from the viewpoint of a type GALBP problem in relation to the balancing of the resultant line, in such a way that the indicators can be compared with the proposed methodology with the techniques or methods applied separately for the same sets of study problems.
Finally, we believe that the proposed methodology responds to a problem of integrating two problems like the MCFP and GALBP under a same approach which is perfectible insofar as the results can be validated in future comparative work, as well as extending the proposed problem, integrating in the design, and balancing of manufacturing cells configured in “U” the design of the family of products that one wishes to manufacture.
The authors would like to thank for the support of the Universidad de Santiago de Chile (031817 PB DICYT-USACH) and also thank all the teams of the Smart City Lab Program Centre of the same university.