O planejamento da produção é uma atividade que avalia decisões para um melhor uso dos recursos disponíveis, visando satisfazer aos objetivos produtivos da empresa ao longo de um horizonte de planejamento. Este trabalho enfoca o problema de dimensionamento de lotes com restrições de capacidade (PDLC), que é uma das tarefas centrais envolvidas no planejamento da produção. O PDLC visa determinar o tamanho dos lotes a serem produzidos em períodos de tempo de um horizonte de planejamento. Os PDLC estudados neste trabalho contemplam duas características importantes: a presença de múltiplos itens e a existência de tempos de preparação para as máquinas. Além disso, são consideradas restrições de capacidade e situações onde o atraso para atender a demanda é permitido (backlogging). Alguns dos modelos estudados permitem que a preparação do ambiente de produção para um dado item possa ser mantida de um período para o seguinte, o que propiciaria a economia de até uma preparação a cada período. Esta característica é chamada de preservação de preparação (carry-over). Também existem situações onde a preparação de uma máquina começa em um período e termina no período seguinte. Na literatura, esta característica é chamada de set-up crossover. Este trabalho tem três metas centrais: a) avaliar diferentes configurações do software comercial ILOG CPLEX 11 para a solução dos PDLC estudados; b) estudar a influência na solução dos PDLC quando se acrescenta a possibilidade de atraso na demanda, de preservação de preparação e de set-up crossover; c) aplicar local branching para resolver os problemas estudados. Para resolver as instâncias propostas, foram utilizados o software comercial ILOG CPLEX 11 e um programa em C++ que foi desenvolvido neste trabalho. Foram utilizados exemplos encontrados na literatura para avaliar as propostas, e bons resultados foram obtidos / The production planning is an activity that evaluates the decision for a better use of the available resources, in order to satisfy the productive objectives of the company over a planning horizon. This work focuses on the capacitated lot-sizing problem (CLSP), which is one of the central tasks involved in production planning. The CLSP means to determine the size of the lots to be produced in time periods of a planning horizon. The CLSP studied in this work contemplate two complicating characteristics: the presence of multiple items and the existence of set-up times for the machines. Besides that, capacity constraints and situations where backlog of the demand is allowed are also considered (backlogging). Some of the studied models allow the set-up of the production environment for a given item to be carried over to the next period, which could result in economy of a set-up in each period (carry-over). There are situations where the set-up of a machine starts in one period and crosses over to the next period (set-up crossover). This work has three main goals: a) evaluate different configurations of the commercial software ILOG CPLEX 11 to solve the different kinds of CLSP studied; b) study the influence of the solution of the CLSP when you consider the possibility of backlogging, set-up carry-over and set-up crossover; c) apply local branching to solve the studied problems. To solve the proposed instances, we used the commercial solver ILOG CPLEX 11 and the program in C++ developed in this work. The examples used to test both programs are found in the literature, and good results were obtained

O setor de fundições é importante para a economia, pois produz componentes básicos para muitos outros setores, de modo que seu bom desempenho tem repercussão nos demais. Um modelo de programação inteira mista para uma fundição de mercado de pequeno porte, que visa principalmente minimizar atrasos na entrega dos pedidos, foi proposto na literatura. Neste trabalho é feito um estudo do modelo e é proposta uma nova abordagem, independente de qualquer software comercial, baseada na decomposição do problema em dois subproblemas: o planejamento da produção das ligas e o planejamento da produção dos itens. Ambos foram resolvidos por uma heurística lagrangiana baseada em transferêrencias. Testes computacionais mostraram que a abordagem proposta é capaz de gerar soluções de boa qualidade, em tempo computacional aceitável / The foundry sector is important to the economy as it produces basic components for many other sectors, to such an extent that its performance has a repercussion in other sectors. A recently published mixed integer-programming model for small market-driven foundries, which aims to minimize delays when delivering orders, was proposed in the literature. In this work, a study of this model was undertaken and a new approach is put forward, regardless of any commercial software, based on dealing with the problem in two sub problems: production planning of alloys and production planning of items. Both sub problems were solved by a Lagrangian heuristic based on transfers. Computational tests show that the approach proposed is able to generate solutions of good quality in acceptable computational time

Este texto trata de um dos temas fundamentais no planejamento de produção, o problema de dimensionamento de lotes de um único item. Uma descrição sucinta e informal do problema segue abaixo. Considere um intervalo de tempo dividido em períodos e que a cada período de tempo está associada a demanda de um item. Dados os custos e as eventuais restrições na produção e no armazenamento, determine os períodos em que se produzirá e em que quantidade para que as demandas sejam atendidas com o menor custo possível, respeitando as restrições impostas. Apresentamos aqui resultados sobre a estrutura ótima do problema, sobre complexidade e algoritmos para os casos básicos do problema / This text studies one of the core subjects in production planning, the single-item lot-sizing problem. A brief and informal description of this problem follows below. Considering a time interval split into time periods and that there is a demand of an item associated with each time period. Given production and holding costs and possibly production and holding restrictions, determine in which periods the production must occur and in which quantity, in order to attend the demands with a minimum cost, without violate any restriction. Here, it will be shown some results about the optimal structure of the problem, about the complexity and algorithms for the simpler cases

Este texto trata de um dos temas fundamentais no planejamento de produção, o problema de dimensionamento de lotes de um único item. Uma descrição sucinta e informal do problema segue abaixo. Considere um intervalo de tempo dividido em períodos e que a cada período de tempo está associada a demanda de um item. Dados os custos e as eventuais restrições na produção e no armazenamento, determine os períodos em que se produzirá e em que quantidade para que as demandas sejam atendidas com o menor custo possível, respeitando as restrições impostas. Apresentamos aqui resultados sobre a estrutura ótima do problema, sobre complexidade e algoritmos para os casos básicos do problema / This text studies one of the core subjects in production planning, the single-item lot-sizing problem. A brief and informal description of this problem follows below. Considering a time interval split into time periods and that there is a demand of an item associated with each time period. Given production and holding costs and possibly production and holding restrictions, determine in which periods the production must occur and in which quantity, in order to attend the demands with a minimum cost, without violate any restriction. Here, it will be shown some results about the optimal structure of the problem, about the complexity and algorithms for the simpler cases

Estágio orientado na empresa, pelo Eng. Nuno Filipe Correia de Melo Ferreira de Almeida / Tese de mestrado integrado. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2012

Orientador: Adriana Cristina Cherri Nicola / Banca: Silvio Alexandre de Araujo / Banca: Sonia Cristina Poltroniere Silva / Resumo: Este trabalho aborda o Problema de Redimensionamento de Lotes (PRL) capacitado, com múltiplos produtos e máquinas paralelas. O redimensionamento de lotes é uma variação do problema de dimensionamento de lotes que pode ser identificado em sistemas produtivos com elevada taxa de interrupções, como quebras, refugos, entre outros, fazendo com que o plano de produção seja prejudicado, necessitando de atualizações a medida que ocorrem as interrupções. São considerados três parâmetros de interrupção: manutenção corretiva, mão de obra insuficiente e indisponibilidade de matéria-prima. É permitido o atendimento da demanda nos períodos com atrasos e utilização de hora extra. O problema tem por objetivo minimizar os custos de preparação, estoque, atraso e hora extra. Baseado em um modelo matemático proposto na literatura para resolver problemas de dimensionamento de lotes, um modelo matemático para representar o PRL foi proposto. O PRL foi formulado como um problema de programação linear inteira mista (PLIM) e resolvido através do método exato branch and bound. Testes computacionais foram realizados com exemplares adaptados da literatura e abrangem os três parâmetros de interrupção / Abstract: This work approaches the capacitated Lot Resizing Problem (LRP) with multi-products and parallel machines. The lot resizing problem is a lot sizing problem variation which can be identified in productive systems with high rate of interruptions, as breaks, refuse, and others, impairing the planning production and making update needed as soon as interruptions happens. Three parameters for interruption were considered: corrective maintenance, insufficient man power and unavailability of raw material. Demand can be performed with back-orders and overtime requests. This work has the objective of minimize inventory holding costs, back-orders, setup and overtime costs. Based on a mathematical model proposed in the literature to solve the lot sizing problem, a mathematical model to represent the LRP was proposed. The LRP was formulated as a mixed integer problem and solved by branch and bound exact method. Computational experiments were performed with adapted literature instances embracing the three parameters of interruption / Mestre

DIAS, Fábio Carlos Sousa. Problema de Árvore Geradora Mínima com Restrição de Grau Mínima e Centrais e Terminais Fixos. 2014. 132 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T19:49:19Z No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Approved for entry into archive by José Jairo Viana de Sousa (jairo@ufc.br) on 2016-07-14T23:17:13Z (GMT) No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Made available in DSpace on 2016-07-14T23:17:13Z (GMT). No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) Previous issue date: 2014 / The Min-Degree Constrained Minimum Spannig Tree - MD-MST is to find a minimum spanning tree of a graph where each vertex is a leaf of the tree or satisfies a constraint of minimum degree. The leaf vertices are called terminals and the others are the central vertices. We define and study a variation of this problem, which we denote MDF-MST, where the terminal and central vertices are fixed. We show that the problem is NP-Hard and is in FPT, parameterized by the number of central vertices. We also identify cases where the problem becomes polynomial. We propose several integer programming formulations for the problem and compare the quality of lower bound generated by their linear relaxations. We propose and teste a Lagrangian Relaxation for the problem, which we also use to define Lagrangian heuristics. We define greedy heuristics, a VND Local search and a VNS heuristic. We present a Benders’s Decomposition. We propose a new general heuristic that combines ingredients from the Benders’s decomposition with subgradient method, which we call subgradient heuristic. We apply this heuristic to the MDF-MST. All these algorithms have been implemented, tested and compared among them and with the CPLEX solver. The computational efficiency of the proposed algorithms, especially the Lagrangian heuristics, is comparable with that of CPLEX, and even better in several cases. Some of these algorithms were adapted for the MD-MST and DC-MST (inthelatter,thedegreeconstraintisofmaximumdegree). Whencomparingthecomputational results with the literature, we conclude that the algorithms are competitive. / O Problema de Árvore Geradora Mínima com Restrição de Grau Mínimo (Min-Degree Constrained Minimum Spannig Tree - MD-MST) consiste em encontrar uma árvore geradora mínima de um grafo onde cada vértice ou é folha da árvore ou satisfaz uma restrição de grau mínimo. Os vértices folhas são chamados terminais e os demais são os centrais. Definimos e estudamos uma variação desse problema, que denotamos MDF-MST, onde os terminais e centrais são definidos a priori. Mostramos que o problema é NP-Difícil e está na Classe FPT, parametrizado pelo número de centrais. Identificamos também casos onde o problema torna-se polinomial. Propomos várias formulações de programação inteira para o problema e comparamos teórica e computacionalmente a qualidade do limite inferior gerado por suas relaxações lineares. Propomos e testamos uma relaxação lagrangeana para o problema, que usamos também para definir heurísticas lagrangenas. Definimos heurísticas gulosas, uma busca VND e uma heurística VNS. Apresentamos uma decomposição de Benders. Propomos uma nova heurística geral que combina ingredientes da decomposição de Benders com método de subgradientes, a qual denominamos Heurística de Subgradientes. Aplicamos tal heurística ao MDF-MST. Todos esses algoritmos foram implementados, testados, comparados entre si e com o solver CPLEX. A eficiência computacional dos algoritmos propostos, especialmente a relaxação lagrangeana, é competitiva com a do CPLEX, e superior em vários casos. Alguns desses algoritmos foram adaptados para o problema MD-MST e seu correlato DC-MST (este último onde a restrição sobre os centrais é de grau máximo). Quando comparamos os resultados computacionais com a literatura.

CAMPOS, Victor Almeida. Um estudo do politopo e dos limites inferiores gerados pela formulação de coloração dos representantes. 2005. 108 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2005. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:37:10Z No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:41:39Z (GMT) No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) / Made available in DSpace on 2016-07-22T12:41:39Z (GMT). No. of bitstreams: 1 2005_dis_vacampos.pdf: 624425 bytes, checksum: 13eb092def3e5c973c883bf32b893ba8 (MD5) Previous issue date: 2005 / The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value. / O problema de coloração de vértices é considerado um dos modelos mais estudados em teoria dos grafos pela sua relevância em campos práticos e teóricos. Do ponto de vista teórico, o problema de coloração é NP - Difícil. Além disto, foi classificado entre os problemas mais difíceis de NP, no sentido de que achar uma aproximação para o número cromático também é NP - Difícil. A importância do problema de coloração tem incentivado a investigar métodos para encontrar limitantes inferiores próximos do número cromático. Historicamente, os primeiros limitantes inferiores utilizados para resolvê-lo lidavam com cliques maximais. Mais recentemente, popularizou-se a utilização de relaxações lineares de formulações de programação inteira. Uma formulação que mostrou bons limitantes inferiores foi a formulação por conjuntos independentes, cujo valor de relaxação equivale ao número cromático fracionário. No presente trabalho, fazemos uma comparação entre as formulações de programação inteira conhecidas para indicar a escolha pela formulação dos representantes. Revisamos a formulação para remover simetrias existentes e apresentamos um estudo parcial do politopo associado ao fecho convexo de suas soluções inteiras. Discutimos como é possível utilizar a formulação dos representantes para gerar limites inferiores para o número cromático fracionário. Realizamos a implementação de um método de planos de corte para aproximar o número cromático fracionário e mostramos que podemos gerar limitantes inferiores que normalmente não diferem em mais de uma unidade.

VIANA, Luiz Alberto do Carmo. Árvore geradora com dependências mínima. 2016. 69 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-09-09T12:32:49Z No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2016-09-27T17:45:27Z (GMT) No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) / Made available in DSpace on 2016-09-27T17:45:27Z (GMT). No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) Previous issue date: 2016 / We introduce the Dependency Constrained Minimum Spanning Tree Problem, DCMST(G,D,w), defined over a graph G(V,E) and a digraph D(E,A), whose vertices are the edges of G and whose arcs describe dependency relations between these edges. Such problem consists of finding, among the spanning trees of G(V,E) satisfying the dependency constraints imposed by D(E,A), that one whose cost is minimum, according to a edgeweight function w. The dependency constraints impose that an edge e of G can be part of a solution either if it is a source in D or if some other edge e′, such that the arc (e′, e) is in D, is part of it as well. We prove that deciding whether there is a feasible solution to DCMST(G,D,w) is an NP-complete problem, even if G is a chordal cactus and D is a union of arborescences of height at most 2. NP-completeness also applies if G is bipartite, the dependency constraints occur only between adjacent edges of G and their related arcs describe arborescences whose height is at most 2. The same results are obtained for the problem variants which demand that, instead of “some”, “exactly one”or “all”dependencies be part of a solution. To solve the problem, we introduce some integer programming formulations and some valid inequalities. We propose a strategy to reduce the problem dimension by excluding some edges of G according to the structure of D. We evaluate the introduced models and algorithms using randomly generated instances. Computational results are reported. / Introduzimos o problema de Árvore Geradora com Dependências Mínima, AGDM(G,D,w), definido sobre um grafo G(V,E) e um digrafo D(E,A), cujos vértices são as arestas de G e cujos arcos definem dependências entre tais arestas. O problema consiste em encontrar, dentre as árvores geradoras do grafo G(V,E) que satisfaçam as restrições de dependência impostas pelo digrafo de entrada D(E,A), uma que tenha custo mínimo, segundo a ponderação w das arestas de G. As restrições de dependência exigem que uma aresta e de G só pode fazer parte de uma solução se for uma fonte em D ou se fizer parte da solução alguma outra aresta é tal que o arco (e′, e) esteja em D. Provamos que decidir se há solução viável para AGDM(G,D,w) é um problema NP-completo, mesmo quando G é um cacto cordal e D é a união de arborescências de altura no máximo 2. Sua NP-completude também é mostrada ainda que G seja bipartido, as restrições de dependência ocorram apenas entre arestas adjacentes de G e formem arborescências de altura no máximo 2. Resultados idênticos são obtidos para as variantes do problema onde, nas restrições de dependência, substitui-se o requisito “alguma” por “exatamente uma” ou “toda”. Para resolver o problema, apresentamos algumas formulações de programação inteira e desigualdades válidas. Propomos uma estratégia para reduzir a dimensão do problema, excluindo arestas de G com base na estrutura de D. Avaliamos os modelos e algoritmos propostos usando instâncias geradas aleatoriamente. Resultados computacionais são reportados.

FIGUEIREDO, Tatiane Fernandes. Problema de Formação de Equipes Sociotécnicas: Complexidade, Formulações Matemáticas e Resultados Computacionais. 2016. 86 f. Dissertação (mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-03-22T19:14:08Z No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-04-25T12:32:53Z (GMT) No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) / Made available in DSpace on 2016-04-25T12:32:53Z (GMT). No. of bitstreams: 1 2016_dis_tffigueiredo.pdf: 1148121 bytes, checksum: a25818a809d3426e9eb1ee56535c6361 (MD5) Previous issue date: 2016 / Using concepts of the socio-technical systems theory, this dissertation defines mathematically the problems of cooperative teams formation considering social and technical constraints separately, and then presents their computational complexity. Mainly, it is defined and studied the central problem in this work, which jointly considers social and technical requirements for creating teams of cooperative work, to be called FEST (Socio-Technical Teams Formation Problem). Two mathematical formulations and a meta-heuristic are proposed for FEST. One formulation uses a cubic number of variables and constraints, whereas the second one has a quadratic number of variables but an exponential number of constraints. The proposed heuristic is based on the Non-monotonic Simulated Annealing meta-heuristic with local search using swap-like operators. The correctness of both formulations is proved. A polynomial algorithm to separate the constraints of the second formulation is presented. It is proved that the two formulations provide the same linear programming bound, and valid inequalities to strengthen it are proposed. For the compact formulation, some classes of valid inequalities are shown to be facet-inducing under suitable hypotheses. Finally, it is statistically analyzed the performance of the presented formulations and meta-heuristic. Real and random generated instances are used in the computational experiments. / Utilizando conceitos da Teoria dos Sistemas Sociotécnicos, este trabalho define matematicamente os problemas de formação de equipes cooperativas considerando separadamente restrições sociais e técnicas e apresenta a complexidade computacional dos mesmos. Sobretudo, é definido e estudado o problema central deste trabalho, que considera conjuntamente requisitos sociais e técnicos para criação de equipes de trabalho cooperativo, denominado FEST (Problema de Formação de Equipes Sociotécnicas). Duas formulações matemáticas e uma meta-heurística para o FEST são propostas. Uma formulação utiliza um número cúbico de variáveis e restrições, enquanto a segunda formulação possui um número quadrático de variáveis, mas um número exponencial de restrições. A meta-heurística proposta é baseada no Simulated Annealing Não-Monotônico com busca local que usa operadores tipo swap. A corretude de ambas as formulações é provada. Um algoritmo polinomial para separar as restrições da segunda formulação é apresentado. Mostra-se que as duas formulações fornecem o mesmo limite de programação linear, e desigualdades válidas para fortalecê-lo são propostas. Para a formulação compacta, algumas classes de desigualdades válidas são demonstradas indutoras de facetas sob hipóteses apropriadas. Por fim, foi analisado estatisticamente o desempenho das formulações e da meta-heurística apresentadas. Instâncias reais e geradas aleatoriamente são usadas nos experimentos computacionais.