Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.

Essays on supply chain's flexibility: a real options approach

A presente tese investiga o processo de tomada de decisão na gestão de cadeias de abastecimento, utilizando um quadro de análise de opções reais. Especificamente, estudamos tópicos como o nível de inventário ideal para protecção contra a incerteza da procura, o momento para implementação de capacidade flexível em mercados onde existe complexidade no mix de produtos, o tempo para o reforço do factor trabalho visando requisitos de serviço ao mercado, e as decisões entre integração e outsourcing num ambiente de incerteza. Foram usadas metodologias de tempo discreto e contínuo para identificar o valor ideal e o calendário das opções a adoptar, quando a procura é estocástica. Além disso, foram considerados os efeitos dos requisitos dos mercados, como a complexidade na oferta de produtos e o nível de serviço. A procura é representada recorrendo a diferentes processos estocásticos, o impacto de saltos inesperados também é explorado, reforçando a generalização dos modelos a diferentes condições de negócio. A aplicabilidade dos modelos que apresentamos permite a diversificação e o enriquecimento da literatura sobre a abordagem de opções reais, no âmbito das cadeias de abastecimento. Níveis de inventário flexíveis e capacidades flexíveis são característicos das cadeias de abastecimento e podem ser usados como resposta à incerteza do mercado. Esta tese é constituída por ensaios que suportam a aplicação dos modelos, e consiste num capítulo introdutório (designado por ensaio I) e mais seis ensaios sobre factores que discutem o uso de medidas de flexibilidade nas cadeias de abastecimento, em ambientes de incerteza, e um último ensaio sobre a extensão do conceito de flexibilidade ao tratamento da avaliação de planos de negócio. O segundo ensaio que apresentamos é sobre o valor do inventário num único estádio, enquanto medida de flexibilidade, sujeita ao crescente condicionalismo dos custos com posse de activos. Introduzimos uma nova classificação de artigos para suportar o indicador designado por overstock. No terceiro e quarto ensaio ampliamos a exploração do conceito de overstock, promovendo a interacção e o balanceamento entre vários estádios de uma cadeia de abastecimento, como forma de melhorar o desempenho global. Para sustentar a aplicação prática das abordagens, adaptamos o ensaio número três à gestão do desempenho, para suportar o estabelecimento de metas coordenadas e alinhadas; e adaptamos o quarto ensaio à coordenação das cadeias de abastecimento, como auxiliar ao planeamento integrado e sequencial dos níveis de inventário. No ensaio cinco analisamos o factor de produção “tecnologia”, em relação directa com a oferta de produtos de uma empresa, explorando o conceito de investimento, como medida de flexibilidade nas componentes de volume da procura e gama de produtos. Dedicamos o ensaio número seis à análise do factor de produção “Mão-de-Obra”, explorando as condicionantes para aumento do número de turnos na perspectiva económica e determinando o ponto crítico para a tomada de decisão em ambientes de incerteza. No ensaio número sete exploramos o conceito de internalização de operações, demarcando a nossa análise das demais pela definição do momento crítico que suporta a tomada de decisão em ambientes dinâmicos. Complementamos a análise com a introdução de factores temporais de perturbação, nomeadamente, o estádio de preparação necessário e anterior a uma eventual alteração de estratégia. Finalmente, no último ensaio, estendemos a análise da flexibilidade em ambientes de incerteza ao conceito de planos de negócio. Em concreto, exploramos a influência do número de pontos de decisão na flexibilidade de um plano, como resposta à crescente incerteza dos mercados. A título de exemplo, usamos o mecanismo de gestão sequencial do orçamento para suportar o nosso modelo. A crescente incerteza da procura obrigou a um aumento da agilidade e da flexibilidade das cadeias de abastecimento, limitando o uso de muitas das técnicas tradicionais de suporte à gestão, pela incapacidade de incorporarem os efeitos da incerteza. A flexibilidade é claramente uma vantagem competitiva das empresas que deve, por isso, ser quantificada. Com os modelos apresentados e com base nos resultados analisados, pretendemos demonstrar a utilidade da consideração da incerteza nos instrumentos de gestão, usando exemplos numéricos para suportar a aplicação dos modelos, o que claramente promove a aproximação dos desenvolvimentos aqui apresentados às práticas de negócio.