Metaheuristic approach to solving U-shaped assembly line balancing problems using a rule-base coded genetic algorithm
Date
2015
Authors
Martinez-Contreras, Ulises, author
Duff, William S., advisor
Troxell, Wade O., committee member
Labaide, John W., committee member
Sampath, Walajabad S., committee member
Journal Title
Journal ISSN
Volume Title
Abstract
The need to achieve line balancing for a U-shaped production line to minimize production time and cost is a problem frequently encountered in industry. This research presents an efficient and quick algorithm to solve the U-shape line-balancing problem. Heuristic rules used to solve a straight line-balancing problem (LBP) were modified and adapted so they could be applied in a U-shape line-balancing problem model. By themselves, the heuristic rules, which were adapted from straight-line systems, can produce good solutions for the U-shape LBP, however, there is nothing that guarantees that this will be the case. One way to achieve improved solutions using heuristic rules can be accomplished by using a number of rules simultaneously to break ties during the task assignment process. In addition to the use of heuristic and simultaneous heuristic rules, basic genetic operations were used to further improve the performance of the assignment process and thus obtain better solutions. Two genetic algorithms are introduced in this research: a direct-coded and an indirect-coded model. The newly introduced algorithms were compared with well-known problems from literature and their performance as compared to other heuristic approaches showed that they perform well. The indirect-coded genetic algorithm uses the adapted heuristic rules from the LBP as genes to find the solutions to the problem. In the direct-coded algorithm, each gene represents an operation in the LBP and the position of the gene in the chromosome represents the order in which an operation, or task, will be assigned to a workstation. The indirect-coded genetic algorithm introduces sixteen heuristic rules adapted from the straight LBP for use in a U-shape LBP. Each heuristic rule was represented inside the chromosome as a gene. The rules were implemented in a way that precedence is preserved and at the same time, facilitate the use of genetic operations. Comparing the algorithm’s results with known results from literature, it obtained better solutions in 26% of the cases; it obtained an equivalent solution in 62% of the cases (not better, not worse); and a worse solution the remaining 12%. The direct-coded genetic algorithm introduces a new way to construct an ordered arrangement of the task assignation without violating any precedence. This method consists of creating a diagram that is isomorphic to the original precedence diagram to facilitate the construction of the chromosome. Also, crossover and mutation operations are conducted in a way that precedence relations are not violated. The direct-coded genetic algorithm was tested with the same set of problems as the indirect-coded algorithm. It obtained better solutions than the known solutions from literature in 22% of the cases; 72% of the problems had an equivalent solution; and 6% of the time it generated a solution less successful than the solution from literature. Something that had not been used in other genetic algorithm studies is a response surface methodology to optimize the levels for the parameters that are involved in the response model. The response surface methodology is used to find the best values for the parameters (% of children, % of mutations, number of genes, number of chromosomes) to produce good solutions for problems of different sizes (large, medium, small). This allows for the best solution to be obtained in a minimum amount of time, thus saving computational effort. Even though both algorithms produce good solutions, the direct-coded genetic algorithm option requires less computational effort. Knowing the capabilities of genetic algorithms, they were then tested in two real industry problems to improve assembly-line functions. This resulted in increased efficiency in both production lines.
Description
Rights Access
Subject
U-shaped assembly line balancing
genetic algorithm