Autor(es):
Pimentel, Carina 
Data: 2011
Identificador Persistente: http://hdl.handle.net/1822/12401
Origem: RepositóriUM - Universidade do Minho
Detalhes do Documento
Modelos e métodos para problemas de dimensionamento de lotes e escalonamento
Descrição
Tese de doutoramento em Engenharia Industrial e de Sistemas O trabalho que se apresenta nesta tese relaciona-se com o desenvolvimento de modelos e de métodos para a resolução de dois problemas de planeamento da produção de médio/curto prazo. A principal motivação consiste na exploração e comparação de diferentes abordagens, baseadas em programação inteira mista, em modelos/métodos de decomposição e em métodos heurísticos, para os problemas em estudo. O primeiro problema, é um problema clássico de dimensionamento de lotes, que está associado às decisões de planeamento da produção de médio-prazo. O problema consiste na determinação de um plano de produção para vários produtos finais ao longo de um determinado horizonte temporal, que minimize todos os custos envolvidos e respeite restrições de procura e de capacidade. Para este problema desenvolve-se um novo modelo exacto, que resulta da aplicação dos princípios da decomposição de Dantzig-Wolfe múltipla a uma formulação de programação inteira mista para o problema. Os princípios gerais de aplicação desta decomposição são também apresentados neste trabalho. A potencial mais valia deste modelo relaciona-se com a obtenção de limites inferiores de boa qualidade. O modelo que resulta da decomposição de Dantzig-Wolfe múltipla é comparado com dois modelos de decomposição alternativos, que se obtêm aplicando directamente os princípios da decomposição de Dantzig-Wolfe, e com o modelo de programação inteira mista, resolvido directamente através de um software de estado-da-arte. Para determinar a solução óptima inteira dos modelos de decomposição aplica-se o método de partição e geração de colunas (branchand- price). São apresentados resultados computacionais partindo de um conjunto de instâncias da literatura, para os vários modelos e métodos. O segundo problema estudado neste trabalho surge associado ao planeamento de curto-prazo e combina as decisões de dimensionamento de lotes, com as decisões de afectação e escalonamento desses lotes. Este estudo foi motivado por um problema real da indústria têxtil, no qual se pretende definir um plano de produção para uma secção de tricotagem, onde os principais componentes dos produtos finais são realizados num conjunto de máquinas paralelas idênticas. Para este problema propõe-se um novo modelo de programação inteira mista, que se resolve através de um software de estadoda- arte. Paralelamente, propõem-se vários métodos heurísticos. Duas das heurísticas propostas são: uma heurística de fluxos em rede e escalonamento e uma heurística de ordenação e escalonamento. Estas heurísticas visam a obtenção de soluções com alguma qualidade em pouco tempo. Propõem-se ainda quatro algoritmos de pesquisa local, que têm em consideração características específicas do problema e que tentam melhorar a qualidade das soluções das heurísticas anteriores. Atendendo ao desempenho dos algoritmos de pesquisa local, estes são combinados através de mudanças sistemáticas das vizinhanças, dando origem a duas meta-heurísticas: uma de descida em vizinhanças variáveis e outra de pesquisa em vizinhanças variáveis. Para avaliar as soluções do modelo de programação inteira mista e dos métodos heurísticos sugere-se uma função de avaliação inovadora, que minimiza os atrasos totais e os níveis em curso de fabrico entre duas etapas sucessivas do processo produtivo. É ainda sugerida uma nova função de avaliação nos métodos heurísticos, também baseada na minimização dos atrasos totais e na minimização dos níveis em curso de fabrico. A principal vantagem desta segunda medida de avaliação é contabilizar de um modo mais rigoroso os níveis em curso de fabrico. Para avaliar o desempenho e a qualidade das soluções do modelo de programação inteira mista e dos métodos heurísticos, desenvolveu-se um gerador de instâncias, que gera instâncias semelhantes às do problema real. This work is associated with the development of models and methods for two medium/short term production planning problems. Our main motivation is the exploration and comparison of different approaches, based on mixed integer programming, on decomposition models and methods and on heuristics, for those two problems. The first one is a classical lot sizing problem associated with the medium-term production planning decisions. The problem consists of finding a production plan for several final items over a given planning horizon that minimizes the overall costs involved, while respecting demand and capacity constraints. An exact model based on a multiple Dantzig-Wolfe decomposition is developed. The general principles of this decomposition are presented in this work too. The potential benefit of this decomposition is the achievement of good quality lower bounds, although our purpose is to obtain integer optimal solutions. The resulting model of multiple Dantzig-Wolfe decomposition is compared with two alternative decomposition models that are obtained when applying directly the Dantzig-Wolfe decomposition principles, and is also compared with an integer programming formulation solved by a state-of-art software. The integer optimal solutions of all the decomposition models are obtained through branch-and-price algorithms. We present computational results for a set of instances from the literature. The second problem studied in this work is a short-term production planning problem that integrates lot sizing, assignment and scheduling decisions. This study was motivated by a real problem from a textile industry. The aim is to define a production plan for a knitting section where the main components of the final items are processed on a set of identical parallel machines. A new mixed integer programming model is proposed for this problem, as well as several heuristics. Two of those heuristics are: a network flow and scheduling heuristic and an ordering and scheduling heuristic. The purpose of these heuristics is to find good quality solutions quickly. Four local search based algorithms that consider specific characteristics of the problem are developed too, in order to try to improve the solutions of the previous heuristics. Taking into account the performance of the four local search heuristics, we combine them through systematic changes of neighborhoods, testing two metaheuristics: variable neighborhood descent and variable neighborhood search. To evaluate the mixed integer programming model solutions and the solutions of all the heuristics, an innovative evaluation function that minimizes a weighted sum of total tardiness and work-in-process levels between two successive production processes is suggested. We study another new evaluation function for the heuristic methods, which is related to the previous one. The main advantage of the second evaluation function over the first one is that it calculates in a more precise way the levels of workin- process inventory. The performance and quality of solutions of all the above presented methods for the second problem are evaluated using a set of instances that are similar to the real ones. Those instances were generated by an instance generator developed by us.
Tese de doutoramento em Engenharia Industrial e de Sistemas O trabalho que se apresenta nesta tese relaciona-se com o desenvolvimento de modelos e de métodos para a resolução de dois problemas de planeamento da produção de médio/curto prazo. A principal motivação consiste na exploração e comparação de diferentes abordagens, baseadas em programação inteira mista, em modelos/métodos de decomposição e em métodos heurísticos, para os problemas em estudo. O primeiro problema, é um problema clássico de dimensionamento de lotes, que está associado às decisões de planeamento da produção de médio-prazo. O problema consiste na determinação de um plano de produção para vários produtos finais ao longo de um determinado horizonte temporal, que minimize todos os custos envolvidos e respeite restrições de procura e de capacidade. Para este problema desenvolve-se um novo modelo exacto, que resulta da aplicação dos princípios da decomposição de Dantzig-Wolfe múltipla a uma formulação de programação inteira mista para o problema. Os princípios gerais de aplicação desta decomposição são também apresentados neste trabalho. A potencial mais valia deste modelo relaciona-se com a obtenção de limites inferiores de boa qualidade. O modelo que resulta da decomposição de Dantzig-Wolfe múltipla é comparado com dois modelos de decomposição alternativos, que se obtêm aplicando directamente os princípios da decomposição de Dantzig-Wolfe, e com o modelo de programação inteira mista, resolvido directamente através de um software de estado-da-arte. Para determinar a solução óptima inteira dos modelos de decomposição aplica-se o método de partição e geração de colunas (branchand- price). São apresentados resultados computacionais partindo de um conjunto de instâncias da literatura, para os vários modelos e métodos. O segundo problema estudado neste trabalho surge associado ao planeamento de curto-prazo e combina as decisões de dimensionamento de lotes, com as decisões de afectação e escalonamento desses lotes. Este estudo foi motivado por um problema real da indústria têxtil, no qual se pretende definir um plano de produção para uma secção de tricotagem, onde os principais componentes dos produtos finais são realizados num conjunto de máquinas paralelas idênticas. Para este problema propõe-se um novo modelo de programação inteira mista, que se resolve através de um software de estadoda- arte. Paralelamente, propõem-se vários métodos heurísticos. Duas das heurísticas propostas são: uma heurística de fluxos em rede e escalonamento e uma heurística de ordenação e escalonamento. Estas heurísticas visam a obtenção de soluções com alguma qualidade em pouco tempo. Propõem-se ainda quatro algoritmos de pesquisa local, que têm em consideração características específicas do problema e que tentam melhorar a qualidade das soluções das heurísticas anteriores. Atendendo ao desempenho dos algoritmos de pesquisa local, estes são combinados através de mudanças sistemáticas das vizinhanças, dando origem a duas meta-heurísticas: uma de descida em vizinhanças variáveis e outra de pesquisa em vizinhanças variáveis. Para avaliar as soluções do modelo de programação inteira mista e dos métodos heurísticos sugere-se uma função de avaliação inovadora, que minimiza os atrasos totais e os níveis em curso de fabrico entre duas etapas sucessivas do processo produtivo. É ainda sugerida uma nova função de avaliação nos métodos heurísticos, também baseada na minimização dos atrasos totais e na minimização dos níveis em curso de fabrico. A principal vantagem desta segunda medida de avaliação é contabilizar de um modo mais rigoroso os níveis em curso de fabrico. Para avaliar o desempenho e a qualidade das soluções do modelo de programação inteira mista e dos métodos heurísticos, desenvolveu-se um gerador de instâncias, que gera instâncias semelhantes às do problema real. This work is associated with the development of models and methods for two medium/short term production planning problems. Our main motivation is the exploration and comparison of different approaches, based on mixed integer programming, on decomposition models and methods and on heuristics, for those two problems. The first one is a classical lot sizing problem associated with the medium-term production planning decisions. The problem consists of finding a production plan for several final items over a given planning horizon that minimizes the overall costs involved, while respecting demand and capacity constraints. An exact model based on a multiple Dantzig-Wolfe decomposition is developed. The general principles of this decomposition are presented in this work too. The potential benefit of this decomposition is the achievement of good quality lower bounds, although our purpose is to obtain integer optimal solutions. The resulting model of multiple Dantzig-Wolfe decomposition is compared with two alternative decomposition models that are obtained when applying directly the Dantzig-Wolfe decomposition principles, and is also compared with an integer programming formulation solved by a state-of-art software. The integer optimal solutions of all the decomposition models are obtained through branch-and-price algorithms. We present computational results for a set of instances from the literature. The second problem studied in this work is a short-term production planning problem that integrates lot sizing, assignment and scheduling decisions. This study was motivated by a real problem from a textile industry. The aim is to define a production plan for a knitting section where the main components of the final items are processed on a set of identical parallel machines. A new mixed integer programming model is proposed for this problem, as well as several heuristics. Two of those heuristics are: a network flow and scheduling heuristic and an ordering and scheduling heuristic. The purpose of these heuristics is to find good quality solutions quickly. Four local search based algorithms that consider specific characteristics of the problem are developed too, in order to try to improve the solutions of the previous heuristics. Taking into account the performance of the four local search heuristics, we combine them through systematic changes of neighborhoods, testing two metaheuristics: variable neighborhood descent and variable neighborhood search. To evaluate the mixed integer programming model solutions and the solutions of all the heuristics, an innovative evaluation function that minimizes a weighted sum of total tardiness and work-in-process levels between two successive production processes is suggested. We study another new evaluation function for the heuristic methods, which is related to the previous one. The main advantage of the second evaluation function over the first one is that it calculates in a more precise way the levels of workin- process inventory. The performance and quality of solutions of all the above presented methods for the second problem are evaluated using a set of instances that are similar to the real ones. Those instances were generated by an instance generator developed by us.
Tipo de Documento
Tese de Doutoramento
Idioma Português
Orientador(es) Alvelos, Filipe Pereira e; Carvalho, J. M. Valério de
Idioma Português
Orientador(es) Alvelos, Filipe Pereira e; Carvalho, J. M. Valério de
| Financiadores do RCAAP | |||||||
|
|
|
|
|
|
||