This research analyzes a class of fixed-cycle production lines. The main concern is the productivity of the lines. Productivity is defined to be the average number of items produced per unit time in the long run. Closed form solutions are derived for the productivity of a two-machine line with dependent machines. These solutions are used to obtain bounds on the productivity of longer lines. The transition matrix associated with an N-machine line is shown to be stochastically monotone yielding monotone increasing lower bounds and monotone decreasing upper bounds which converge to the productivity of the line. These results are then extended to include lines with Markov machines. With the transition matrix in this case having a conditional monotone property, the monotonicity of the bounds is maintained. / Ph. D.

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

Fundação Araucária; RENAULT; Seti / A Pesquisa Operacional investiga as (melhores) formas de se configurar e coordenar sistemas ou operações usando técnicas de otimização. Geralmente, a otimização de um sistema é modelado com base no estado final almejado. Porém, como atingir ou implementar tal estado final em sistemas é pouco retratado na literatura. Esta dissertaçãode mestrado propõe uma nova classe de problema de otimização: a programação das operações entre o estado inicial e o final de um sistema, o Problema de Implementação. A programação das operações é especialmente importante para linhas de montagem. A indústria automobilística é fortemente baseada em linhas de produção que podem ser usadas até 24 horas por dia. Assim, as oportunidades de intervenções para mudar ou otimizar o sistema produtivo são poucas. As condições de implementação aplicadas ao balanceamento de linhas produtivas são discutidas, e as características observadas resultam no proposto Problema de Implementação de Linhas de Montagem (PILM). Na dissertação, um guia de modelagem baseado em Programação Linear Inteira Mista (PLIM) é desenvolvido para a formulação de diversas variações do Problema de Implementação. As instruções de modelagem são usadas para desenvolver um conjunto de modelos PLIM para o Problema de Implementação de Linhas de Montagem. Para a obtenção de resultados, um conjunto de instâncias é proposto. Assim, uma análise de sensibilidade em função de cada um dos parâmetros formadores das instâncias é realizada. As formulações são comparadas, junto com as diferentes formas de apresentar e resolver o problema. Ademais, um método de decomposição é usado para resolver um problema industrial real. A modelagem mostrase correta para a divisão da implementação de mudanças em linhas de montagem. Os resultados mostram que a divisão do esforço de implementação resulta em apenas poucas mudanças a mais (cerca de 7% para os casos pequenos e médios) comparadas com a implementação em uma fase. A possibilidade de programar a implementação em etapas menores aumenta a aplicabilidade de projetos, que, de outra forma, requeririam grande paradas de produção. / Operations Research investigates the (best) ways to configure and coordinate systems or operations with optimization procedures. Usually, the optimization of a system is modeled based on the aimed final configuration. However, little is published about how to reach or implement such optimal configurations in the systems. This master thesis proposes a new class of optimization problem: a scheduling of operations between initial and final states of a system, the Implementation Problem. The scheduling of operations is especially important to assembly lines. The automotive industry strongly relies on production lines that can operate 24 hours a day. Thus, the intervention opportunities to change or optimize the production system are very few. The implementation conditions of balancing on assembly lines are discussed, and the observed characteristics result in the proposal of the Assembly Line Implementation Problem (ALIP). The master thesis proposes a Mixed-Integer Linear Programming (MILP) modeling guide for the formulation of several variations of Implementation Problems. The modeling instructions are used to develop a set of MILP models for the Assembly Line Implementation Problem. For the results, a dataset is proposed and a sensitivity analysis on each of the consistent parameters of the dataset is performed. The proposed formulations are compared, along with the different forms of presenting and solving the problem. Furthermore, a decomposition method is used to solve a real-world industrial problem. The modeling correctly represents the division of the implementation of changes in assembly lines. The results show that the division of the effort in multiple stages only need a few more changes (around 7\% for the small and medium cases) comparing to a straightforward implementation. The possibility of scheduling the implementation in smaller steps increases the applicability of projects that otherwise would require a large system's stoppage time.

Fundação Araucária; RENAULT; Seti / A Pesquisa Operacional investiga as (melhores) formas de se configurar e coordenar sistemas ou operações usando técnicas de otimização. Geralmente, a otimização de um sistema é modelado com base no estado final almejado. Porém, como atingir ou implementar tal estado final em sistemas é pouco retratado na literatura. Esta dissertaçãode mestrado propõe uma nova classe de problema de otimização: a programação das operações entre o estado inicial e o final de um sistema, o Problema de Implementação. A programação das operações é especialmente importante para linhas de montagem. A indústria automobilística é fortemente baseada em linhas de produção que podem ser usadas até 24 horas por dia. Assim, as oportunidades de intervenções para mudar ou otimizar o sistema produtivo são poucas. As condições de implementação aplicadas ao balanceamento de linhas produtivas são discutidas, e as características observadas resultam no proposto Problema de Implementação de Linhas de Montagem (PILM). Na dissertação, um guia de modelagem baseado em Programação Linear Inteira Mista (PLIM) é desenvolvido para a formulação de diversas variações do Problema de Implementação. As instruções de modelagem são usadas para desenvolver um conjunto de modelos PLIM para o Problema de Implementação de Linhas de Montagem. Para a obtenção de resultados, um conjunto de instâncias é proposto. Assim, uma análise de sensibilidade em função de cada um dos parâmetros formadores das instâncias é realizada. As formulações são comparadas, junto com as diferentes formas de apresentar e resolver o problema. Ademais, um método de decomposição é usado para resolver um problema industrial real. A modelagem mostrase correta para a divisão da implementação de mudanças em linhas de montagem. Os resultados mostram que a divisão do esforço de implementação resulta em apenas poucas mudanças a mais (cerca de 7% para os casos pequenos e médios) comparadas com a implementação em uma fase. A possibilidade de programar a implementação em etapas menores aumenta a aplicabilidade de projetos, que, de outra forma, requeririam grande paradas de produção. / Operations Research investigates the (best) ways to configure and coordinate systems or operations with optimization procedures. Usually, the optimization of a system is modeled based on the aimed final configuration. However, little is published about how to reach or implement such optimal configurations in the systems. This master thesis proposes a new class of optimization problem: a scheduling of operations between initial and final states of a system, the Implementation Problem. The scheduling of operations is especially important to assembly lines. The automotive industry strongly relies on production lines that can operate 24 hours a day. Thus, the intervention opportunities to change or optimize the production system are very few. The implementation conditions of balancing on assembly lines are discussed, and the observed characteristics result in the proposal of the Assembly Line Implementation Problem (ALIP). The master thesis proposes a Mixed-Integer Linear Programming (MILP) modeling guide for the formulation of several variations of Implementation Problems. The modeling instructions are used to develop a set of MILP models for the Assembly Line Implementation Problem. For the results, a dataset is proposed and a sensitivity analysis on each of the consistent parameters of the dataset is performed. The proposed formulations are compared, along with the different forms of presenting and solving the problem. Furthermore, a decomposition method is used to solve a real-world industrial problem. The modeling correctly represents the division of the implementation of changes in assembly lines. The results show that the division of the effort in multiple stages only need a few more changes (around 7\% for the small and medium cases) comparing to a straightforward implementation. The possibility of scheduling the implementation in smaller steps increases the applicability of projects that otherwise would require a large system's stoppage time.

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.

Actuellement, les fabricants sont soumis à une pression économique importante et à une concurrence internationale accrue due à la globalisation des marchés. Pour réussir, les fabricants doivent être capables de répondre rapidement aux changements de la demande en adaptant leurs systèmes de production. Cette adaptation aux changements peut être réalisée à travers multiples reconfigurations du système de production.Les travaux présentés dans ce mémoire portent sur l'élaboration des méthodes de recherche opérationnelle permettant d'accompagner le décideur lors de la reconfiguration d'une ligne de transfert ou d'assemblage. Ce problème apparaît lorsqu'un nouveau produit doit être fabriqué par une ligne existante ou lorsqu'il y a eu des changements dans les caractéristiques du produit. Par conséquent, il devient nécessaire de modifier la configuration du système de production tout en minimisant les coûts induits. Ces coûts sont évalués différemment pour les systèmes automatisésou manuels. Dans le premier cas, qui correspond au cas des lignes de transfert, pour limiter les investissements, il est souhaitable de réutiliser au maximum les équipements existants à condition que les contraintes techniques et technologiques soient respectées. Dans le cas des lignes manuelles qui sont représentées dans notre étude par les lignes d'assemblage, l'objectif est de minimiser les coûts liés à l'apprentissage des opérateurs causés par la réaffectation de leurs tâches.Les méthodes de résolution exactes basées sur la modélisation mathématique et la programmation linéaire en nombre mixtes ainsi qu'une méthode de type goal programming sont développées dans ce travail pour argumenter la prise de décisions lors de la reconfiguration des lignes de production. Les méthodes proposées ont été testées avec succès sur des échantillons de problèmes proches des cas industriels et ont montré leur efficacité. / Global competition causes fluctuations in product demand and requires more frequent modifications of product characteristics. As a consequence, the production systems have to be frequently adapted to new production requirements.This work develops new combinatorial optimization methods for supporting decision makers at the reconfiguration stage considered for transfer and assembly lines. If new products have to be manufactured at the line or existing products are modified, then the line has to be reconfigured in order to meet new production requirements. In highly automated lines, as the transfer lines, the reconfiguration problem is focused on the readjustment of the equipment. To reduce the investment costs, the decision makers aim to reuse the available equipment as much as possible. The existence of compatibility constraints between new operations to be performed and existing facilities makes the reconfiguration problem hard and combinatorial.In manual assembly lines also studied in this thesis, the reconfiguration problem mostly concerns the reassignment of tasks to workers ant the minimization of the cost of retraining operators.The developed methods are based on the mathematical modelling and mixed integer programming, a goal programming approach is designed as well. These methods were successfully tested on a dataset of problem instances close to real industrial problems. The obtained results show the effectiveness and the efficiency of the solution methods proposed.

A project report submitted to the Faculty of Engineering, University of the Witwatersrand, Johannesburg, in partial fulfillment of the requirements for the degree of Master of Science in Engineering. Johannesburg, 1996. / This research project is an investigation into the effectiveness of an inspect and rework system called dynamic section control which has the purpose of improving the assembly quality of the BMW-3 series manufacturing in the Rosslyn Plant just outside Pretoria in South Africa, The system was introduced into the assembly plant in February 1995 to improve the assembly quality of the vehicles as quickly as possible. The main motivation behind the need for this system was to bring the quality onto the same level as the German plants in order to become recognised in the international network of BMW's manufacturing plants along with the new manufacturing plant in the USA The origins of the dynamic section control system come from the Munich 3-series plant as well as being based on the principles of poka yoke, a quality philosophy devised by the quality expert from Toyota in Japan, Shigeo Shingo, Defects found on the assembly plant's line, identified by the quality auditor and information from the marketing department regarding warranty claims are entered onto a checklist which is used by reworkers in the plant to inspect and make good the defects that have been found. The checklist is updated on a weekly basis, hence its name: dynamic section control. Seven rework stations, in which the dynamic section control reworkers work, have been strategically positioned in the assembly plant which trims the painted bodies it receives from the paint shop, The effectiveness of the system has been measured by analysing the information from the daily audits as well as investigating the trend of vehicles If rving the assembly plant still requiring rework and repairs off-line. The analyses were divided into three distinct periods. The first being approximately 4 months before the introduction of :he dynamic section control system, and the second and third periods after the introduction of the system. The results show that the dynamic section control system have a positive influence in improving the assembly quality of the vehicles, especially reducing the number of recurring defects. The number of defects that have only occurred once in each of the periods has remained reasonably constant indicating that the system has no impact in reducing the random occurrence of "one-off" defects. Another significant finding was. the increase in the number of vehicles requiring Department of Mechanical Engineering, University of the Witwatersrand repair off-line, attributable to the assembly plant, after the vehicle has left the assembly line. This increase is probably the result of an increased quality awareness within the assembly plant, resulting in reworkers identifying an increasing number of defects for repair off-line. Other factors such as clearer identification of production goals, training and development of a proportion of the assembly plant's workers in the German plants lor three weeks, reorganizing of support. staff by installing "the right people in the right place" and reducing the number of model derivatives in the plant have also contributed to the enormous quality improvement achieved. Further development of the. dynamic section control system is recommended by installing a rework station within each team area, and including the actions of dynamic section control in the work content of that team. Currently, the system uses external workers which are not part of individual teams as the current sections overlap team areas. Finally, it is recommended that the work of the dynandc section control reworker be incorporated as a noma! function within the team and be rotated amongst the team members. / AC2017

Processos de montagem em geral necessitam de instruções para serem executados, desde a montagem de simples brinquedos até máquinas complexas. Tradicionalmente, essas instruções vem na forma de manuais em papel ou meio digital. Seja qual for o modo, os manuais de instruções utilizam desenhos, diagramas ou fotos, além de instruções textuais para indicar a sequência de montagem do início até o estado final. Procurando mudar esse paradigma, esse trabalho propõe um sistema para auxílio à montagem que utiliza realidade aumentada para guiar o usuário no processo. Através de processamento de imagens capturadas por uma câmera o sistema reconhece cada peça e por meio de sinais gráficos é indicado ao usuário qual a peça a ser manipulada e onde deve ser posicionada. Em seguida é feito a verificação do posicionamento das peças e o usuário é alertado quando a tarefa de montagem atinge o estado final. Muitos trabalhos na área utilizam algum tipo de dispositivo customizado como \"head mounted display\" (HMD) e marcadores para auxiliar o rastreamento da câmera e identificação das peças, limitando a popularização dessa tecnologia. Tendo esse último ponto em vista, propõe-se um sistema que não utiliza qualquer dispositivo customizado ou marcadores para rastreamento. Além disso, todos os processos do sistema são executados em software embarcado, não necessitando de comunicação com outros computadores para o processamento de imagens. Como o sistema não faz uso de marcadores para a identificação das peças, inicialmente é proposto a implementação do sistema para guiar o usuário na resolução de um quebra-cabeças plano. O sistema proposto é denominado como MARA (Montagem Assistida por Realidade Aumentada). / Assembly processes for simple toys or complex machines usually requires instructions to be executed. Traditionally, these instructions are written in the form of paper or digital manuals. These manuals contains descriptive text, photos or diagrams to guide the assembly sequence from the beginning to the final state. To change this paradigm, it is proposed in this work an augmented reality system to guide assembly tasks. The system recognizes each assembly piece through image processing techniques and guides the piece placement with graphic signals. Later, the system checks if the pieces are properly assembled and warns the user when the assembly have been finished. In the field of assembly assisted by augmented reality systems, many works use some kind of customized device, like head mounted displays (HMD). Furthermore, markers have been used to track camera position and identify assembly parts. These two features restrict the spread of the technology, thus in the proposed work customized devices and markers to track and identify parts shall not be used. Besides, all the processing are executed on embedded software without the need of communication with other computers to help image processing. The first implementation of the proposed system assists the user on the assembly of a planar puzzle, as the proposed system do not use markers to recognize assembly pieces. This system is being called A3R (Assembly Assisted by Augmented Reality).

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.