O Problema de Balanceamento e Sequenciamento de Linhas de Montagem com Tempos de Setup dependentes da Sequência (SUALBSP, em inglês Setup Assembly Line Balancing and Scheduling) envolve a atribuição de tarefas às estações de trabalho e o sequenciamento destas tarefas dentro da estação à qual foi atribuída. Trabalhos anteriores propuseram soluções heurísticas com excelentes resultados, porém o uso de métodos exatos, por meio de algum resolvedor de Programação Inteira Mista, tem apresentado desempenhos decepcionantes, pois contém um subproblema NP-hard em todas as estações. Enquanto o modelo de Scholl, Boysen e Fliedner (2013) minimiza prioritariamente o número de estações, o modelo proposto neste trabalho parte da premissa que este é um dado definido. A partir de uma estimativa inicial de número de estações, processa-se o modelo com o objetivo de distribuir as tarefas e minimizar o tempo total de estação, que é o segundo objetivo do modelo original. Se este processamento for infactível, incrementa-se o número de estações em uma unidade e reprocessa-se o modelo até se encontrar um resultado factível. Experimentos computacionais em 101 instâncias de dados confirmam o bom desempenho da abordagem proposta, sem qualquer prejuízo à qualidade da solução. Portanto, os resultados apresentados demonstram que há espaço para estudos futuros a partir do uso de matheurísticas. / The Setup Assembly Line Balancing and Scheduling Problem (SUALBSP) involves the assigning of tasks to workstations and the sequencing of these tasks within the station to which they are assigned. Previous work has proposed heuristic solutions with excellent results, but the use of exact methods, by some Mixed-Integer Programming solver, has shown disappointing performance, because it contains an NP-hard sub problems in every station. While the model proposed by Scholl, Boysen and Fliedner (2013) primarily minimizes the numbers of stations, our model assumes it as a parameter. From an initial estimate of the number of stations, we process the model for allocating tasks and minimize station times, which is the second objective of the original model. If this processing is infeasible, we increase the number of stations by one unit and we reprocess the model to find a feasible result. Computational experiments in 101 instances of data set confirm the good performance of the proposed approach, without harming the quality of the solution. Therefore, the results show that there are opportunities for future studies based on the use of matheuristics.

Orientador: Fernando Augusto Silva Marins / Coorientador: Aneirson Francisco da Silva / Banca: Valério Antonio Pamplona Salomon / Banca: Leonardo Antonio Monteiro Pessôa / Resumo: Neste trabalho aplicou-se a Simulação a Eventos Discretos na área de Intra-logística de abastecimento de uma linha de montagem de chassis, de uma indústria multinacional, (na fase de try-out). Objetivou-se desenvolver uma ferramenta gerencial que possibilitasse a identificação, a priori, de possíveis gargalos na linha de montagem, que possam surgir quando da sua implementação em regime de produção. Como delimitação do trabalho, foram simuladas, como variáveis de entrada, apenas os tamanhos de lotes de peças que abastecem as estações do trabalho robotizadas de solda dos subconjuntos dos chassis, adotando-se os dados de uma linha de montagem similar já existente. No desenvolvimento da ferramenta gerencial foi utilizada uma técnica de modelagem dedicada a projetos de simulação e um software comercial de simulação, bem como foram aplicados testes estatísticos não paramétricos na validação do modelo de simulação. O modelo simulado mostrou capacidade de atendimento à linha de montagem com oportunidade de otimização e de melhor balanceamento de mão de obra, dando origem a sugestões de melhoria no processo / Abstract: In this work had been applied the Discrete Events Simulation technique in the Intralogistics area of supply of a chassis assembly line, of a multinational industry, (in the try-out phase). The objective was to develop a management tool that would allow the identification, at first, of possible bottlenecks on the assembly line, which may arise when it is implemented under a production regime. As a delimitation of the work, only the batch sizes of pieces that supply the robotized welding cells of the chassis subassemblies were simulated as input variables, using data from a similar existing assembly line. In the development of the management tool, a modeling technique dedicated to simulation projects and a commercial simulation software were used, as well as nonparametric statistical tests were applied in the validation of the simulation model. The simulated model showed the ability to service the assembly line with the opportunity for optimization and better balancing of labor, giving rise to suggestions for improvement in the process / Mestre

The efficiency of an assembly line depends on how the different tasks are distributed among the work stations that make up the assembly line. Assigning the tasks to the stations is called assembly line balancing (ALB) and is an NP-hard optimization problem. While automating line balancing has the potential to make manufacturing more efficient, and the problem has been studied for many decades, the research has not been widely adopted by industry, where planning is still largely done manually. This thesis discusses reasons for this theory-practice gap and suggests a direction that is more focused on real-world applications. This includes shifting the focus to a decision support system (DSS) rather than considering the ALB solver in isolation. Such a shift places the solver in a new context, where it plays a slightly different role and needs to fulfill slightly different requirements. A framework for building practical ALB solvers within a DSS context is proposed and then evaluated by implementing solvers for two different assembly line models. Increasingly refined versions of the ALB solvers are compared to each other, showing that the most specialized version performs substantially better than the simplest, which demonstrates that this framework allows an effective trade-off between development time and performance. One of the implemented solvers is also pitted against a state-of-the-art solver for the Simple Assembly Line Balancing Problem type 1 (SALBP-1) by comparing its results on a standard set of problem instances against the best published results. The comparison shows that the implemented solver is not just competitive but in some ways superior. On the largest instances, it produces improved solutions for 99 % of the instances that had not already been solved optimally, reducing the number of stations by more than 2 % on average. The solvers also demonstrated the potential to effectively trade off running time and solution quality, which is an important feature in an interactive system that is meant to support an iterative refinement process.

Development, operation, and testing of a heuristic line balancing program for a microcomputer are discussed. Tasks are grouped into work stations along an assembly line such that the number of work stations required is minimized. The model is built primarily using the Hoffman (1963) procedure with modifications described by Gehrlein and Patterson (1975). For purposes of comparison the Rank Positional Weight technique (Helgeson and Birnie, 1961) is also included in the model. Testing included thirty-seven different balances using problems from the literature. For each balance, both Rank Positional Weight and Hoffmann solutions were obtained in the forward and reverse directions. Four measures of performance were considered in this study. These measures of performance were: (1) the average percentage a balance is above the optimum solutions, in terms of number of stations; (2) time to obtain a balance; (3) the best solution in terms of the lowest number of stations and lowest standard deviation of the slack times; and (4) the largest value of minimum station slack time. Overall it was found that the Hoffmann procedure with a delay factor if 1.5 was best suited for the microcomputer application. Further work is recommended to find the optimum delay factor and apply the Modified Hoffmann procedure to solving line balancing problems where the cycle time is minimized given a set of work stations.

With the trend towards greater product customization and shorter delivery time, the use of mixed model assembly lines is increasing. A line balancing approach is needed that can address the complex nature of the mixed model line and produce near optimal solutions to problems of realistic size. Due to the combinatorial nature of the line balancing problem, exact solution techniques are limited to small problems. Heuristic methods, on the other hand, are often too simplistic to find good solutions. Furthermore, many of the existing techniques cannot be expanded to handle the mixed model problem. Simulated Annealing (SA) is a search methodology which has exhibited good results when applied to combinatorial optimization problems. In fact, researchers have found that SA is able to find near-optimal solutions while its processing time increases only as a polynomial function of problem size. However, none of the applications found in the literature fully explore the technique's ability to handle a highly-constrained problem such as line balancing. / Master of Science

A methodology for designing mixed model stochastic assembly line systems and a computer package to implement it for realistic problem sizes were developed. The methodology consists of three major steps: (1) generation of feasible sequences of feeding models into the line, (2) generation of feasible allocations (balances) of work elements to work stations, and (3) generation of combinations of sequences and allocations with the best ordering of elements within stations, calculation of total expected cost for each combination, and selection of the one with the least cost. For generating feasible balances, an exhaustive search procedure with a number of heuristic rules was used to ensure searching the whole feasible region in limited time. A cost model based on labor and incompletion costs is used to calculate the cost of each combination, and a recursive procedure to calculate incompletion probabilities for each element and incorporate them into the cost model was implemented. An example problem, its results, and the computer package listings are included. / Master of Science

The scheduling of material requirements at a factory to maximize profits.or productivity is a difficult mathematical problem. The stochastic nature of most production setups introduces additional complications as a result of the uncertainty involved in vendor reliability and processing times. But in developing the descriptive model for a system, a true representation can only be attained if the variability of these elements is considered. Here we present the development of a normative model based on a new type of descriptive model which considers the element of stochasticity. The arrival time of an assembly part from a vendor is considered to be a normally distributed random variable. We attempt to optimize the system with regard to work-in-process inventory using a dynamic programming algorithm in combination with a heuristic procedure. The decision variable is the prescribed assembly part delivery date. The model is particularly suitable for application in low volume assembly lines, where products are manufactured in discrete batches. / Master of Science

The demand for increased diversity, reduced cycle time, and reduced work-in-process has caused increased popularity of mixed-model assembly lines. These lines combine the productivity of an assembly line and the flexibility of a job shop. The mixed-model assembly line allows setup time between models to be zero. Large lines mixed-model assembly lines require a timely, near-optimal method. A well balanced line reduces worker idle time and simplifies the mixed-model assembly line sequencing problem. Prior attempts to solve the balancing problem have been in-adequate. Heuristic techniques are too simple to find near-optimal solutions and yield only one solution. An exhaustive search requires too much processing time. Simulated Annealing works well, but yields only one solution per run and the solutions may vary because of the random nature of the Simulated Annealing process. Multiple runs are required to get more than one solution, each run requiring some amount of time which depends on problem size. If only one run is performed, the solution achieved may be far from optimal. In addition, Simulated Annealing requires different parameters depending on the size of the problem. The Genetic Algorithm (GA) is a probabilistic heuristic search strategy. In most cases, it begins with a population of random solutions. Then the population is reproduced using crossover and mutation with the fittest solutions having a higher probability of being parents. The idea is survival of the fittest, poor or unfit solutions do not reproduce and are replaced by better or fitter solutions. The final generation should yield multiple near optimal solutions. The objective of this study is to investigate the Genetic Algorithm and its performance compared to Simulated Annealing for large mixed-model assembly lines. The results will show that the Genetic Algorithm will perform comparably to the Simulated Annealing. The Genetic Algorithm will be used to solve various mixed-model assembly line problems to discover the correct parameters to solve any mixed-model assembly line balancing problem. / Master of Science

L'objectif de la thèse est de créer et développer de nouvelles méthodes de résolution efficaces des problèmes combinatoires en configuration des lignes de fabrication. Deux problèmes ont été particulièrement étudiés: le problème d'équilibrage et de choix d'équipement pour des lignes dédiées et le problème de minimisation des coûts de changements de séries pour des lignes multi-produits. Une solution du premier problème consiste en une affectation admissible des ressources à un nombre de stations à déterminer de sorte que le coût total soit minimal. Afin de résoudre ce problème, nous l'avons réduit au problème de partition d'ensemble et l'avons résolu par des heuristiques gloutonnes et une méthode exacte de génération de contraintes. Les expérimentations sur différentes instances ont montré que la nouvelle approche de résolution surclasse les approches antérieures de la littérature en termes de qualité de solution et de temps de calcul. Pour le second problème deux critères sont considérés lexicographiquement : la minimisation du nombre de stations et la minimisation du coût de changement de séries. Nous avons examiné successivement les cas d'exécution parallèle et séquentielle des opérations. Des solutions approchées ont été trouvées par des heuristiques gloutonnes. Ensuite, nous avons proposé deux modèles de programmation linéaire en nombres entiers (PLNE) afin de trouver le nombre de stations minimal et ensuite d'obtenir le coût de changement de séries minimal. Les résultats des expérimentations sur ces nouveaux problèmes se sont avérés prometteurs à la fois en termes de qualité de solution et de temps de calcul. / The objective of this thesis is to create and develop new effective solution methods for production line configuration problems. Two problems were studied: the equipment selection and balancing problem for dedicated lines and the setup cost minimization problem for multi-product lines. A solution for the first problem consists in a feasible assignment of the resources to an unknown number of stations so that the total cost is minimized. In order to solve this problem, we reduced it to the set partitioning problem and solved it by greedy heuristics and an exact method of constraint generation. The computer experiments on different problem instances showed that the new solution approach outperforms the previous methods from the literature both in terms of solution quality and computational time. For the second problem two criteria were considered lexicographically: the minimization of the number of stations and the minimization of the total setup cost. We examined successively the cases with parallel and sequential execution of operations. Approximate solutions were found by greedy heuristics. Then, we proposed two integer programming models in order to obtain the minimal number of stations and then the minimal setup cost. The experimental results for this new problem proved to be promising both in terms of solution quality and computational time.

A diferença entre estações de trabalho é considerada desprezível em linhas de montagem tradicionais. Por outro lado, linhas de montagem heterogêneas consideram o problema de indústrias nas quais os tempos das tarefas variam de acordo com alguma característica a ser selecionada para a tarefa. No Problema de Balanceamento e Atribuição de Trabalhadores em Linhas de Montagem (do inglês Assembly Line Worker Assignment and Balancing Problem, ALWABP), os trabalhadores são responsáveis por estações de trabalho e de acordo com as suas habilidades, eles executam as tarefas em diferentes quantidades de tempo. Em alguns casos, os trabalhadores podem até ser incapazes de executar algumas tarefas. No Problema de Balanceamento de Linhas de Montagem Robóticas (do inglês Robotic Assembly Line Balancing Problem, RALBP), há diferentes tipos de robôs e o conjunto de tarefas de cada estação deve ser executada por um robô. Robôs do mesmo tipo podem ser usados múltiplas vezes. Nós propomos métodos exatos e heurísticos para a minimização do tempo de ciclo destes dois problemas, para um número fixo de estações. Os problemas têm características similares que são exploradas para produzir limitantes inferiores, métodos inferiores, models de programação inteira mista, e regras de redução e dominância. Para a estratégia de ramificação do método de branch-and-bound, entretanto, as diferenças entre os problemas forçam o uso de dois algoritmos diferentes. Uma estratégia orientada a tarefas tem os melhores resultados para o ALWABP-2, enquanto uma estratégia orientada a estações tem os melhores resultados para o RALBP-2. Nós mostramos que os limitantes inferiores, heurísticas, modelos de programação inteira mista e algoritmos de branch-and-bound para estes dois problemas são competitivos com os métodos do estado da arte da literatura. / The difference among workstations is assumed to be negligible in traditional assembly lines. Heterogeneous assembly lines consider the problem of industries in which the task times vary according to some property to be selected for the task. In the Assembly Line Worker Assignment and Balancing Problem (ALWABP), workers are assigned to workstations and according to their abilities, they execute tasks in different amounts of time. In some cases they can even be incapable of executing some tasks. In the Robotic Assembly Line Balancing Problem (RALBP) there are different types of robots and each station must be executed by a robot. Multiple robots of the same type may be used. We propose exact and heuristic methods for minimizing the cycle time of these two problems, for a fixed number of stations. The problems have similar characteristics that are explored to produce lower bounds, heuristic methods, mixed-integer programming models, and reduction and dominance rules. For the branching strategy of the branch-and-bound method, however, the differences among the problem force the use of two different algorithms. A task-oriented strategy has the best results for the ALWABP-2 while a station-oriented strategy has the best results for the RALBP-2. The lower bounds, heuristics, MIP models and branch-and-bound algorithms for these two problems are shown to be competitive with the state-of-the-art methods in the literature.