In this thesis, we define a new problem area for assembly lines. In the literature, there are various studies on assembly line balancing, but none of them consider multi-manned tasks, task to which at least two operators have to be assigned. Two mathematical models and one constraint programming model are developed for both Type-I and Type-II ALB problems. The objective of Type-I problem is to minimize the number of stations whereas the objective of Type-II problem is to minimize the cycle time. In addition to this, valid inequalities are introduced to make models more efficient. Moreover, heuristic algorithms for both types are developed for large-sized problems. All formulations are applied to a real case study and then experimental analysis are conducted for all formulations to see the effects of problem parameters on performance measures. Exact models are compared each other and performance of heuristic algorithms are compared against the lower bounds.

ABSTRACT FLEXIBLE ASSEMBLY LINE DESIGN PROBLEM WITH FIXED NUMBER OF WORKSTATIONS Barut&ccedil / uoglu, Sirin M.S. Department of Industrial Engineering Supervisor: Prof. Dr. Meral Azizoglu July 2009, 70 pages In this thesis, we study a Flexible Assembly Line Design problem. We assume the task times and equipment costs are correlated in the sense that for all tasks the cheaper equipment gives no smaller task time. Given the cycle time and number of workstations we aim to find the assignment of tasks and equipments to the workstations that minimizes the total equipment cost. We study a special case of the problem with identical task times. For the general case, we develop a branch and bound algorithm that uses powerful lower bounds and reduction mechanisms. We test the performance of our branch and bound algorithm on randomly generated test problems. The results of our experiments have revealed that we are able to solve large-sized problem instances in reasonable times.

Thesis (M. Sc.)--University of Hong Kong, 1978. / Typescript.

In this thesis, we develop an exact algorithm for an assembly line balancing problem with equipment selection decisions. Two objectives are considered: minimizing the total equipment costs and the number of workstations. Our aim is to choose the type of the equipment(s) in every workstation and determine the assignment of the tasks to each workstation and equipment type. We aim to propose a set of efficient solutions for each problem and leave the choice of the best solution to the decision maker&rsquo / s preferences. A branch and bound algorithm is developed whose efficiency is increased with some dominance rules and powerful lower bounds. Moreover, modified ranked positional weight heuristic method is used as initial upper bound. The effectiveness of the proposed procedure is demonstrated by computational analysis in which the effects of changing certain parameter values are investigated. We find that our algorithm is capable of solving the problem instances with up to 25 tasks and 5 equipments.

Thesis (M.S.)--Brigham Young University. School of Technology, 2004. / Includes bibliographical references (p. 61-62).

Thesis (doctoral)--Technische Hochschule Darmstadt, 1995. / Includes bibliographical references (p. [283]-300) and index.

Thesis (doctoral)--Technische Hochschule Darmstadt, 1995. / Includes bibliographical references (p. [283]-300) and index.

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 / Banca: José Roberto Dale Luche / Banca: Roberto Campos Leoni / Resumo: O objetivo geral da pesquisa foi desenvolver um modelo de simulação a eventos discretos para ser aplicado ao balanceamento de uma linha de montagem de componentes numa empresa do setor automotivo, buscando aumentar a produtividade da linha e utilizando menores quantidades de insumos. Na situação estudada há muitos elementos com comportamento estocástico, que podem influenciar na produtividade da linha, além da diversidade de insumos que abastecem a montagem, o que torna o balanceamento da linha uma tarefa complexa e favorece o uso da Simulação como procedimento de solução. Na modelagem conceitual do problema estudado adotou-se o método IDEF-SIM e para a simulação foi utilizado o software ProModel®. Como resultados tem-se um modelo conceitual e implementado para uma linha de montagem que possibilitou informações interessantes sobre o problema, tais como: juntar funções de dois postos de trabalhos, eliminar excesso de movimentação e eliminar gargalos / Abstract: The overall objective of the research was to develop a simulation model discrete event to be applied to balancing an assembly line components in automotive company, seeking to increase line productivity and using lower amounts of inputs. In the situation studied for many elements with stochastic behavior, which may influence the productivity of the line beyond the range of products that supply assembly, which makes the balancing line a complex task and promotes the use of the simulation procedure as a solution. In conceptual modeling of the studied problem adopted the IDEF-SIM method and for the simulation we used the ProModel® software. As results has a conceptual model and implemented for an assembly line that has enabled interesting information about the problem, such as joining functions of two posts jobs, eliminate excess movement and eliminate bottlenecks / Mestre

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.