یک الگوریتم ژنتیک چند هدفه برای توازن دوباره مخلوط مدل خط مونتاژ

When demand structure or production technology changes, a mixed-model assembly line (MAL) may have to be reconfigured to improve its efficiency in the new production environment. In this paper, we address the rebalancing problem for a MAL with seasonal demands. The rebalancing problem concerns how to reassign assembly tasks and operators to candidate stations under the constraint of a given cycle time. The objectives are to minimize the number of stations, workload variation at each station for different models, and rebalancing cost. A multi-objective genetic algorithm (moGA) is proposed to solve this problem. The genetic algorithm (GA) uses a partial representation technique, where only a part of the decision information about a candidate solution is expressed in the chromosome and the rest is computed optimally. A non-dominated ranking method is used to evaluate the fitness of each chromosome. A local search procedure is developed to enhance the search ability of moGA. The performance of moGA is tested on 23 reprehensive problems and the obtained results are compared with those by other authors.

Assembly lines are special flow-line production systems that are of great importance in the industrial production of high-volume standardized commodities (Scholl, 1999). During the assembly process, workpieces visit stations successively along the line by some kind of transportation system, e.g., a conveyor belt. At each station, certain tasks are performed by one operator regarding the cycle time. The least complex configuration of an assembly line is the single-model assembly line. The simple assembly line balancing (SALB) problem consists in the assignment of assembly tasks to each station with precedence constraints among these tasks. There are two basic versions of the problem. The type I SALB (SALB-I) problem consists in finding an assignment of tasks to workstations such that the number of required workstations is minimized for a predetermined cycle time. The type II SALB (SALB-II) problem consists in allocating tasks to a given number of workstations in order to minimize the cycle time. Both versions of the problems are NP-hard (Gutjahr & Nemhauser, 1964). Recently, changing market requirements are leading more and more industries to diversify their product mix, with more models and optional features being offered. In these situations, mixed-model assembly line (MAL), which can produce several models of a standardized commodity simultaneously, has been widely used in many industries, such as cars, TVs, computers and VCRs. The mixed-model assembly line balancing (MALB) problem involves the assignment of tasks of all models to workstations. This problem is much more complex because it entails the additional considerations of interactions between the assembled models. Since it was firstly investigated by Thomopoulos, 1967 and Thomopoulos, 1970, many works have been published to treat various versions of the problem. Representative papers include Macaskill, 1972, Chakravarty and Shtub, 1985, Erel and Gokcen, 1999, Merengo et al., 1999, Matanachai and Yano, 2001, Vilarinho and Simaria, 2002 and Zhao et al., 2004. Extensive papers on MALB problems were well reviewed by Becker and Scholl (2006) and Boysen et al., 2007 and Boysen et al., 2008. In a MAL, each model has its own precedence diagram, and a task may need different processing times depending on the model assembled. The task that is common to several models may be duplicated in more than one station. Robert and Villa (1970) and Bukchin and Rabinowitch (2006) considered MALB problems with task duplications. In contrast, most research assumes that each common task should be restricted to a single workstation due to machinery and tools sharing (Becker and Scholl, 2006). Subject to this restriction, the precedence diagrams for the various models are combined into a joint one, and the processing time of a common task is calculated by summing up its weighted task times for the various models (Boysen et al., 2008). In this way, the balancing procedure becomes similar to that used for solving SALB problems. In order to avoid excessive capacities, the cycle time of a MAL is generally determined such that it is observed on average over all models. Consequently, the processing times of some models are higher than the cycle time, whereas those of others are lower. Overload may occur when a worker deals several work-intensive models successively. A rather restrictive problem is to impose the cycle time restriction for every model (Kara & Tekin, 2009). In such cases, no overload or sequencing problem occurs. However, this may lead to a poor efficiency, because compensation effects between the models cannot be utilized (Becker & Scholl, 2006). In order to minimize the amount of incomplete units, Thomopoulos (1970) managed to smooth out the workload of different models at each station (i.e., horizontal balancing) when the line is balanced. However, perfect horizontal balancing may not be able to be achieved, especially when the variability of task time for different models is large. Merengo et al. (1999) proposed to simultaneously balance both the average workloads at different stations of the line (vertical balancing) and the workload for different models at each station. Vilarinho and Simaria (2002) addressed MALB problems with assignment restrictions and parallel stations. A two-stage simulated annealing approach is proposed to minimize both vertical and horizontal imbalance. The aforementioned works considered the balancing problems in assembly lines that have not ever been deployed. However, within the lifetime of a MAL, the balancing problems do not occur only once prior to its construction, but rather continuously as rebalancing (Schofield, 1979). Whenever the demand structure or production technology changes, the MAL needs to be reconfigured (Boysen et al., 2007). Especially for MALs that produce seasonal products, demands are likely to undergo remarkable changes over seasons, and the joint task time may change a lot. In this case, the initially balanced line may become unbalanced and inefficient, and therefore should be rebalanced. However, few studies dealt with the short-term rebalancing problems of existing lines. Reassignment of tasks may lead to worker retraining, machine tools and work in process (WIP) buffer movement. Therefore, line rebalancing should consider both productivity and adjustment cost. As it is hard to evaluate the adjustment cost, most researchers considered reconfiguration by introducing assignment restrictions (Ramirez-Campos et al., 2006 and Watkins and Cochran, 1995). Corominas, Pastor, and Plans (2008) treated the rebalancing problem at a motorcycle-assembly plant, which needs to increase production volume by hiring temporary workers in the summer months. These temporary workers take longer to perform tasks than permanent workers, and must always work alongside at least one permanent (and skilled) worker. The rebalancing problem concerns how to assign tasks and determine worker types for each station. The goal is to minimize the number of temporary workers, given the cycle time and the team of workers on staff. Gamberini, Grassi, and Rimini (2006) and Gamberini, Gamberini, Grassi, and Regattieri (2009) dealt with rebalancing problems in single-model manual assembly lines, where operators should be retrained to perform new tasks. They used two separate objective functions concerning expected completion costs and the degree of similarity between initial and new task assignments. Gamberini et al. (2006) proposed a single-pass heuristic with a multi-criteria decision-making technique to solve this problem. Gamberini et al. (2009) developed a multiple single-pass heuristic algorithm for this problem. When a manual assembly line is rebalanced, operators have to be retrained for new assigned tasks, which may lead to efficiency loss and quality problems, especially at the beginning of the new line. Generally, the training cost depends on two aspects: (a) quantity of reassigned tasks, and (b) difficulty level of the reassigned tasks. Therefore, the mean similarity factor (MSF) used by Gamberini et al. (2006) and Gamberini et al. (2009) cannot exactly reflect these rebalancing costs. In this paper, a new objective function is proposed to measure rebalancing cost from these two aspects. Then, the type II mixed-model assembly line rebalancing (MALRB-II) problem is formulated to optimize three objectives: vertical balancing, horizontal balancing and rebalancing cost. A multi-objective genetic algorithm (moGA) is then proposed to find effective solutions for the problem. The MALRB-II problem is formulated in Section 2. Section 3 presents the representation, decoding procedure and genetic operators of the genetic algorithm (GA). The local search procedures that are used to enhance the search ability of GA are also given in this section. In Section 4, an extensive computational study is provided. Some concluding remarks are provided in Section 5.

A balanced mixed-model assembly line may need to be rebalanced when demands change over seasons. The MALRB-II problem concerns how to reassign the tasks and operators to candidate stations given the required cycle time. Because most assembly lines need manual work, rebalancing generally leads to retraining. Therefore, the MALRB-II problem minimizes not only the number of stations and workload variation at each station for different models, but also the rebalancing cost. In this study, a new rebalancing cost function is proposed. Then, the problem is formulated as a three-objective combinatorial optimization problem. In this study, a moGA was proposed to solve the problem. Only partial decision information about the candidate solutions is expressed in the chromosome and the rest is computed optimally. As a result, the length of the chromosome is reduced, and the coding space only contains part of the candidate solutions. A non-dominated ranking method is used to evaluate the fitness of each chromosome. In order to strengthen the search ability, a local search procedure is integrated under the framework of GA. The performance of the proposed method is tested on 23 representative MALRB-II problems. Compared with Merengo et al.’s algorithm for MALB problems, the proposed approach finds out better solutions. For future research, robust mixed-model assembly line balancing with uncertain demands may be of interest.