Αυτή η εργασία διαπραγματεύεται τη θεωρία της διοίκησης έργου, από μια τεχνική κυρίως οπτική, εξού και το «μια αλγοριθμική προσέγγιση» του τίτλου. Για το σκοπό αυτό, η εργασία ξεκινάει με μια εισαγωγή στην έννοια του έργου, η οποία ακολουθείται από την ανάλυση των βασικών στοιχείων της θεωρίας της διοίκησης έργου και τους ορισμούς των σχετικών όρων και λειτουργιών που εμπλέκονται, στο Κεφάλαιο 1. Στο Κεφάλαιο 2, αναλύεται ο Χρονικός Προγραμματισμός του έργου, που αποτελεί το σκελετό για όλη τη διαδικασία της διοίκησης ενός έργου. Παρουσιάζονται αναλυτικά οι βασικές τεχνικές της δικτυωτής απεικόνισης ενός έργου και οι βασισμένες σε αυτό τεχνικές χρονικού προγραμματισμού Κρίσιμου Μονοπατιού (Critical Path Method – CPM) και η στοχαστική τεχνική PERT (Program Evaluation and Review Technique). Στην ίδια κατηγορία ανήκει και η σχετικά νέα τεχνική της Κρίσιμης Αλυσίδας (Critical Chain Method), που παρουσιάζει σημαντικές καινοτομίες και αναπτύσσεται διεξοδικά. Στο κεφάλαιο 3 μεταβαίνουμε από την απλουστευτική περίπτωση των εργασιών με μόνο χαρακτηριστικό τους χρόνους εκτέλεσής τους στην πιο ρεαλιστική περίπτωση όπου απαιτούν τη χρήση κάποιων πόρων για την εκτέλεσή τους. Παρουσιάζεται η έννοια των πόρων και το πώς οι περιορισμοί στη χρονική ή/και ποσοτική διαθεσιμότητά τους επηρεάζει το χρονικό προγραμματισμό. Ιδιαίτερη έμφαση δίνεται στο πρόβλημα του χρονικού προγραμματισμού με περιορισμένους πόρους και εκτενής ανάλυση γίνεται στις επιστημονικές τεχνικές που υπάρχουν και είναι δόκιμες για την αντιμετώπιση του προβλήματος, που είναι πολύ δύσκολο να λυθεί με βέλτιστο τρόπο. Το κεφάλαιο 4 ασχολείται με το πρακτικότερο θέμα των ειδικών για τη διοίκηση έργου προγραμμάτων λογισμικού που κυκλοφορούν. Γίνεται συσχέτιση των λειτουργιών που πρέπει να διαθέτουν με τις αντίστοιχες λειτουργίες που επιτελούνται κατά τις διάφορες φάσεις του κύκλου ζωής ενός έργου και παρουσιάζονται με κριτική άποψη τα πιο διαδεδομένα προγράμματα αυτής της κατηγορίας. Τέλος, στο κεφάλαιο 5 παρουσιάζεται ένα παράδειγμα εταιρίας που οι ανάγκες του έκαναν απαραίτητη την εφαρμογή των αρχών και τεχνικών της διοίκησης έργου. Πρόκειται για την ΕΡΓΟΣΕ Α.Ε., την θυγατρική εταιρία του ΟΣΕ που έχει αναλάβει να διεκπεραιώνει το κατασκευαστικό έργο που αφορά το σιδηροδρομικό δίκτυο και στο τελικό αυτό κεφάλαιο βλέπουμε πως έχει δομήσει ένα ολοκληρωμένο μηχανογραφικό σύστημα βασισμένο σε ένα πρόγραμμα διοίκησης έργου. / The present diploma thesis is dealing with the theory of project management, under a mostly technical perspective- which justifies the “an algorithmic approach” end of this thesis’ title. For this purpose, this thesis begins with an introduction to the notion of “project”, which is followed by an analysis of the fundamental elements of the project management theory and the definitions of the relevant terms and functions involved, in Chapter 1. In Chapter 2, project scheduling is being analyzed. Project scheduling is the framework for the entire function of project management. Extensive analysis of the basic techniques of network representation and the techniques of time scheduling that are based on it (namely, Critical Path Method – CPM, and Program Evaluation and Review Technique – PERT) are presented. To the same category of scheduling techniques belongs the Critical Chain Method as well, therefore it is thoroughly analyzed in this chapter. In Chapter 3, we move from the simplified case of the project tasks which are characterized only by the time they need so as to complete, to the more realistic case of tasks needing various resources. The notion of resources and the way their possible time/quantity availability constraints affect project scheduling are presented. Special emphasis is laid on the resource constrained project scheduling problem, which is a very hard problem to solve in an optimal way, and extensive analysis of the suitable scientific techniques available is offered. Chapter 4 deals with the more practical issue of the project management software. A correlation of the necessary functions of the software programs to the respective ones of the project life cycle is made, and some of the most popular software programs are presented under a critical perspective. Finally, Chapter 5 illustrates the example of a company whose needs make the application of project management principles and techniques necessary. This company is ERGOSE S.A., which is the affiliated company of the mother organization OSE (the Greek rail organization) and has undertaken the construction task of Greek railroads. In this final chapter the company’s integrated information system that is based on a project management software program is presented.

Made available in DSpace on 2016-06-02T19:51:46Z (GMT). No. of bitstreams: 1 3393.pdf: 4478459 bytes, checksum: 69570a1820f1617b090f2e79453e5ec4 (MD5) Previous issue date: 2010-12-15 / Financiadora de Estudos e Projetos / The pursuit of excellence in customer service drives companies to investigate strategies that help to produce satisfactory solutions to the market, as is the case of beverage companies. One of the obstacles faced by this sector is the difficulty in distributing the demanded products within regular working hours due to long service times in each demand site. An alternative for reducing violations of route time consists in including the assignment of extra deliverymen to the usual routing and scheduling decisions. Such treatment is hardly often explored in the literature and it was not found any evidence of commercial softwares that consider it. In this sense, the current work addresses the Vehicle Routing Problem with the assignment of extra deliverymen, with the aim of generating routes in which the number of unserved clients in regular working hours is minimized. To this end, we propose an extension of Clarke and Wright heuristic. The proposed extension is applied to sets of examples generated based on classic instances of Solomon (1987) and Christofides et al. (1979). The results of the application are compared to those provided by the heuristic of Clarke and Wright according to a set of performance criteria. / A busca pela excelência no atendimento aos clientes faz com que empresas investiguem estratégias que auxiliem a obtenção de soluções satisfatórias no mercado, como é o caso das empresas do setor de bebidas. Um dos obstáculos enfrentados por este setor é a dificuldade em distribuir os produtos demandados dentro da jornada de trabalho estabelecida, em função dos altos tempos de serviço existentes em cada ponto de demanda. Uma alternativa para reduzir violações de tempo de rota consiste em incluir a designação de entregadores extras às decisões de roteamento e programação. Este tratamento é pouco explorado na literatura e não foi encontrada nenhuma evidência de softwares comerciais que o considerem. Neste sentido, o corrente trabalho aborda o Problema de Roteamento de Veículos com designação de entregadores extras, com o objetivo de gerar rotas em que o número de clientes não atendidos em uma dada jornada de trabalho seja minimizado. Para tal, é proposta uma extensão da heurística de Clarke e Wright. A extensão proposta é aplicada a conjuntos de exemplos gerados com base nas instâncias clássicas de Solomon (1987) e Christofides et al. (1979). Os resultados obtidos nestas aplicações são comparados aos fornecidos pela heurística de Clarke e Wright segundo um conjunto de critérios de desempenho.

In this thesis we report several of delivery problems. Here it is mostly describe Vehicle Routing Problem and Split Delivery Problem as suitable methods for the case study of the company Baťa a.s.In this thesis we used one of the most sofisticated software Roadnet Transportation Suite as effective program for distribution and planning routes.Finally we construct analysis as a support to find the optimal solution for the final strategical decision of the company Baťa a.s.

The diploma thesis deals with the use of heuristic methods for solving messenger problems. The first part focuses on the proposed vehicle routing problems, especially on travelling salesman problems and the messenger problems. For individual problems are theoretically discussed mathematical models for variants with one or more vehicles and the expansion of the use of time windows and capacity constraints. The second part introduces heuristic algorithms for the method of nearest neighbour, savings method, insertion method and the exchange method on the travelling salesman problems. Then all of the mentioned algorithms are modified for use in three variants of messenger problem. First, the disposition of one vehicle, the second allows more messengers in the same starting point and the last option is more messengers at different starting points. The last part describes computational experiments and comparison of results provided by different methods. The diploma thesis includes application for solving messenger problems using savings methods programmed in Visual Basic for Application in MS Excel.

O problema de empacotamento de cilindros em níveis é comumente encontrado nas indústrias de cerâmica. Solucionar este problema significa encontrar o posicionamento ideal dos itens cerâmicos cilíndricos dentro do forno de modo que o menor número de fornos seja utilizado e os itens não se sobreponham e obedeçam aos limites do recipiente. Também é considerado o uso de prateleiras para que haja uma melhor ocupação do espaço do forno. Propomos uma formulação matemática não-linear inteira mista e métodos de resolução heurísticos e exato para o problema. Os métodos heurísticos consistem em escolher uma estratégia de ordenação, posicionar os itens em cada nível por meio da heurística Bottom-Left e posicionar os níveis no recipiente utilizando as estratégias Best-Fit, First-Fit ou Worst-Fit. Ao total, propomos seis variações heurísticas para resolução do problema. O método exato consiste em estimar o número de níveis e recipientes necessários e resolver o problema por meio de um solver de otimização global. Os experimentos computacionais foram realizados para um conjunto de instâncias que criamos. Os resultados mostraram que o método exato é capaz de encontrar a solução ótima em um curto período de tempo para instâncias de pequeno porte e que as heurísticas são capazes de resolver o problema em um tempo computacional baixo, para instâncias de pequeno, médio e grande porte, sendo que algumas heurísticas apresentam melhor desempenho que outras. / The cylinder packing problem in levels is commonly found in ceramic industries. Solving this problem consists in finding the ideal position of items inside furnaces so that the minimum number of furnaces is used and the items do not overlap and obeying furnaces size. In this case, it is possible to add levels to the furnace. We proposed a non-linear integer mixed mathematical model for the problem and heuristic and exact resolution methods. Heuristic methods consist of choosing a sorting strategy, packing the items at each level by a Bottom-Left heuristic, and positioning the levels in the furnace using Best-Fit, First- Fit or Worst-Fit strategy. In total, it is proposed six heuristic variations to solve the problem. The exact method consists in solving the problem by a global optimization solver. The computational experiments were run over a set of new proposed instances. The results have shown that the exact method is able to find an optimal solution in a short period of time for small instances and that the proposed heuristics are capable of solving the problem in a low computational time for small, medium and large instances. Furthermore, some of them have performed better than others.

A consideração de condicionantes espaciais em modelos de otimização matemática para lidar com o manejo de florestas públicas e privadas é cada vez mais comum. Um desses condicionantes é a imposição de corredores de conectividade para o abrigo e movimentação da fauna e flora, principalmente devido ao elevado grau de fragmentação das áreas de vegetação nativa, o qual exerce um forte impacto na probabilidade de sobrevivência de várias espécies no longo prazo. O objetivo deste trabalho é o desenvolvimento de metodologias auxiliares que permitam ao gestor florestal garantir uma conectividade mínima entre fragmentos de vegetação nativa utilizando unidades de manejo da floresta de produção com determinadas características, interligando fragmentos adjacentes a floresta de produção concomitantemente com a produção de bens e serviços florestais. Duas técnicas foram consideradas; um modelo matemático de programação linear inteira mista e uma heurística denominada heurística da RazãoR. Os dois métodos consideraram o estabelecimento de corredores de conectividade em todos os períodos do horizonte de planejamento simultaneamente, e as equações inseridas permitem ao gestor controlar a qualidade das unidades de manejo aptas a formar o corredor. O modelo de programação linear inteira mista proposto para resolução desse problema faz uso de uma importante propriedade da programação em redes, permitindo a inserção das restrições de conectividade sem adicionar variáveis binárias além daquelas necessárias ao modelo sem conectividade. A solução ótima foi obtida tanto o problema com incorporação de conectividade como para o problema sem conectividade, sendo a diferença entre valores das respectivas funções objetivo o custo de oportunidade do estabelecimento dos corredores. Na heurística da RazãoR, utilizou-se um algoritmo recursivo baseado na Teoria de Grafos e na programação dinâmica para se avaliar o déficit de conectividade das soluções. Dois estudos de caso foram utilizados para a aplicação das técnicas propostas, uma fazenda de uma empresa de celulose do estado de São Paulo, denominada Fazenda Empresarial, e o Parque Estadual Anhanguera. Os dois métodos alcançaram o objetivo de elaborar planos otimizados de manejo florestal estabelecendo uma conectividade mínima entre os fragmentos de vegetação nativa. O custo avaliado para o estabelecimento da conectividade da Fazenda Empresarial foi de 0,051% do valor da função objetivo do problema sem conectividade. A heurística mostrou-se eficaz em encontrar ótimas soluções viáveis, com valores da função objetivo variando de 99,71% a 99,83% do valor encontrado pelo modelo de programação linear inteira mista, após um número médio de 48 iterações. Entretanto, o tempo médio para a heurística encontrar uma solução para o problema foi de dez minutos e vinte e cinco segundos, sendo cinco vezes superior ao tempo necessário para o modelo matemático retornar a solução ótima (um minuto e cinqüenta e quatro segundos). A provável causa do baixo desempenho da heurística em termos de tempo para encontrar uma solução se encontra no método de programação que não buscou gerar um código rápido, deixando espaço no futuro para melhorias quando problemas de maior escala precisem ser resolvidos e a solução de grandes problemas de programação linear inteira mista não possa ser encontrada pelos softwares convencionais. / The consideration of spatial constraints into mathematical optimization models to deal with the management of public and private forests is increasingly common. Due to the increasing fragmentation of natural forests and decreasing species survival\'s probability, an important constraint considers the existence of corridors that work as shelters to allow for the movement and exchange of fauna and flora species. The aim of this paper is the development of auxiliary methodologies to support forest manager in creating a minimal net of corridors formed by industrial forest stands with certain characteristics that connect industrial stands and still conciliate production and environmental concerns. Two techniques were considered; a mixed integer linear programming model and a heuristic procedure called the R-ratio method. Both techniques dealt with the simultaneous incorporation of connectivity corridors over all planning periods in the planning horizon, and allowed the manager to control the quality of the forest stands that can take part of the corridors. The mixed integer linear programming model created to solve this problem relies on an important property of network optimization models, allowing the insertion of the connectivity restrictions without increasing the number of binary variables already present in the model with no connectivity constraints. The optimal solution was achieved in both models, and the difference between the two objective functions revealed the opportunity cost of establishing the corridors. In the R-ratio heuristic, a recursive algorithm based on Graph Theory and on dynamic programming was used. The technique was applied in two cases, a farm of a owned by a pulpwood company in the State of São Paulo, referred to as the Company Farm, and the Anhanguera Forest State Park. Both methods optimized the objective and produced forest management plans that resulted in minimal connectivity among all fragments of native forests. The cost of creating corridor on the Company Farm represents 0,051% of the total objective function value for the no connectivity formulation. The R-ratio heuristic was effective in finding good viable solutions to the problem, with values to the objective function varying from 99,71% to 99,83% of the value found to the optimal solution of a mixed integer linear programming, after an average of 48 iterations. Meanwhile, the heuristic took an average time of ten minutes and twenty five seconds to find a viable good viable solution, representing five times the time required by the mixed integer formulation to find an optimal solution. The probable cause of this low performance in terms of time to find a solution is that the heuristic was not programmed to efficiently generate fast executable codes, leaving space for future improvements if necessary when dealing with large scale problems and in the absence of conventional software capable of dealing with large scale mixed integer linear programming problems.

Este trabalho trata o problema multi-estágios de programação da produção em ambientes Flow Shop com máquinas paralelas, apresentando um estágio de produção dominante (máquina única), no qual os tempos de preparação (setup) da máquina são assimétricos e dependentes da seqüência de execução das tarefas. Tal ambiente é constituído de k estágios de produção, com k = {4, 7}, divididos em três etapas assim definidas: na etapa um, o número de estágios de produção pode variar de um até cinco e cada estágio será constituído de m1 máquinas paralelas idênticas , com m1 &#8712 {2, 3, 4}, o que determina m1 flow shops paralelos. A etapa dois constitui o estágio dominante d, cuja localização oscila dependendo do número de estágios das etapas um e três. Por ultimo, a etapa três, semelhante à etapa um, possui m2 máquinas paralelas idênticas, onde m2 &#8712 {2, 3, 4} e m1 e m2 são gerados aleatoriamente. Todas as tarefas são processadas nas três etapas e o critério de desempenho é a otimização da duração total da programação (makespan) e também a análise do deslocamento do estágio dominante. A programação das tarefas é feita separadamente em cada uma das etapas. Na primeira etapa foi utilizado o método heurístico N&M para cada um dos m1 flow shops paralelos. Para segunda etapa foram desenvolvidos quatro regras e dois métodos heurísticos construtivos com base nos problemas do caixeiro viajante (TSP). Na última etapa, a alocação das tarefas é feita por ordem de chegada na máquina disponível ou com menor carga. Não foram encontrados na literatura trabalhos que retratassem ambientes dessa natureza, logo os métodos desenvolvidos foram comparados entre si. A experimentação computacional analisou os resultados obtidos por meio da porcentagem de sucesso de cada regra, desvio relativo entre os resultados de cada regra, deslocamento da posição do estágio dominante, influência das ordens de grandeza dos tempos de processamento e setup e tempo médio de computação. / This dissertation deals with problem multi-periods of production scheduling of the in Flow Shop environment with parallel machines, presenting a period of dominant production (single machine), in which the setup times for the processing of the jobs is asymmetric and sequence dependent on the execution of the jobs. Such environment is constituted by k periods of production, with k = {4, 7} divided in to three stages defined as: First stage: In stage one the number of production periods can vary from one to five, and each period will be constituted of m1 &#8712 {2, 3, 4} identical parallel machines, determining m1 parallel flow shops. Stage two - It constitutes the dominant period d, whose localization oscillates between the periods of stages one and three. Finally stage three it is similar to stage one, and has m2 &#8712 {2, 3, 4} identical parallel machines, where m1 and m2 Randomly generated. All the jobs are processed in the three stages and the objective is to optimize the total time to complete the scheduling (makespan) and also to analyze the displacement of the dominant period position. The scheduling of the jobs was performed separately in each of the stages. In the first stage the heuristic method N&M was used for each m1 parallel flow shops. In the second stage four constructive rules and two heuristic methods were developed based on traveling salesman problems (TSP). In the last stage the allocation of the jobs was performed according to the arrival time of the available machine or with lesser load. This type of work has not been found in literature; therefore the developed methods were compared among themselves. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation and average computational time. The displacement of the dominant period position as well as the influence of the relation of setup-times and processing-times, were also studied. The results of computational experience are discussed.

O problema de empacotamento de cilindros em níveis é comumente encontrado nas indústrias de cerâmica. Solucionar este problema significa encontrar o posicionamento ideal dos itens cerâmicos cilíndricos dentro do forno de modo que o menor número de fornos seja utilizado e os itens não se sobreponham e obedeçam aos limites do recipiente. Também é considerado o uso de prateleiras para que haja uma melhor ocupação do espaço do forno. Propomos uma formulação matemática não-linear inteira mista e métodos de resolução heurísticos e exato para o problema. Os métodos heurísticos consistem em escolher uma estratégia de ordenação, posicionar os itens em cada nível por meio da heurística Bottom-Left e posicionar os níveis no recipiente utilizando as estratégias Best-Fit, First-Fit ou Worst-Fit. Ao total, propomos seis variações heurísticas para resolução do problema. O método exato consiste em estimar o número de níveis e recipientes necessários e resolver o problema por meio de um solver de otimização global. Os experimentos computacionais foram realizados para um conjunto de instâncias que criamos. Os resultados mostraram que o método exato é capaz de encontrar a solução ótima em um curto período de tempo para instâncias de pequeno porte e que as heurísticas são capazes de resolver o problema em um tempo computacional baixo, para instâncias de pequeno, médio e grande porte, sendo que algumas heurísticas apresentam melhor desempenho que outras. / The cylinder packing problem in levels is commonly found in ceramic industries. Solving this problem consists in finding the ideal position of items inside furnaces so that the minimum number of furnaces is used and the items do not overlap and obeying furnaces size. In this case, it is possible to add levels to the furnace. We proposed a non-linear integer mixed mathematical model for the problem and heuristic and exact resolution methods. Heuristic methods consist of choosing a sorting strategy, packing the items at each level by a Bottom-Left heuristic, and positioning the levels in the furnace using Best-Fit, First- Fit or Worst-Fit strategy. In total, it is proposed six heuristic variations to solve the problem. The exact method consists in solving the problem by a global optimization solver. The computational experiments were run over a set of new proposed instances. The results have shown that the exact method is able to find an optimal solution in a short period of time for small instances and that the proposed heuristics are capable of solving the problem in a low computational time for small, medium and large instances. Furthermore, some of them have performed better than others.

Thesis (M.S.)--Air Force Institute of Technology, 2003. / Title from title screen (viewed Oct. 28, 2003). "March 2003." Vita. "AFIT/GOR/ENS/03-04." Includes bibliographical references (leaves 69-70). Also issued in paper format.

Este trabalho trata o problema multi-estágios de programação da produção em ambientes Flow Shop com máquinas paralelas, apresentando um estágio de produção dominante (máquina única), no qual os tempos de preparação (setup) da máquina são assimétricos e dependentes da seqüência de execução das tarefas. Tal ambiente é constituído de k estágios de produção, com k = {4, 7}, divididos em três etapas assim definidas: na etapa um, o número de estágios de produção pode variar de um até cinco e cada estágio será constituído de m1 máquinas paralelas idênticas , com m1 &#8712 {2, 3, 4}, o que determina m1 flow shops paralelos. A etapa dois constitui o estágio dominante d, cuja localização oscila dependendo do número de estágios das etapas um e três. Por ultimo, a etapa três, semelhante à etapa um, possui m2 máquinas paralelas idênticas, onde m2 &#8712 {2, 3, 4} e m1 e m2 são gerados aleatoriamente. Todas as tarefas são processadas nas três etapas e o critério de desempenho é a otimização da duração total da programação (makespan) e também a análise do deslocamento do estágio dominante. A programação das tarefas é feita separadamente em cada uma das etapas. Na primeira etapa foi utilizado o método heurístico N&M para cada um dos m1 flow shops paralelos. Para segunda etapa foram desenvolvidos quatro regras e dois métodos heurísticos construtivos com base nos problemas do caixeiro viajante (TSP). Na última etapa, a alocação das tarefas é feita por ordem de chegada na máquina disponível ou com menor carga. Não foram encontrados na literatura trabalhos que retratassem ambientes dessa natureza, logo os métodos desenvolvidos foram comparados entre si. A experimentação computacional analisou os resultados obtidos por meio da porcentagem de sucesso de cada regra, desvio relativo entre os resultados de cada regra, deslocamento da posição do estágio dominante, influência das ordens de grandeza dos tempos de processamento e setup e tempo médio de computação. / This dissertation deals with problem multi-periods of production scheduling of the in Flow Shop environment with parallel machines, presenting a period of dominant production (single machine), in which the setup times for the processing of the jobs is asymmetric and sequence dependent on the execution of the jobs. Such environment is constituted by k periods of production, with k = {4, 7} divided in to three stages defined as: First stage: In stage one the number of production periods can vary from one to five, and each period will be constituted of m1 &#8712 {2, 3, 4} identical parallel machines, determining m1 parallel flow shops. Stage two - It constitutes the dominant period d, whose localization oscillates between the periods of stages one and three. Finally stage three it is similar to stage one, and has m2 &#8712 {2, 3, 4} identical parallel machines, where m1 and m2 Randomly generated. All the jobs are processed in the three stages and the objective is to optimize the total time to complete the scheduling (makespan) and also to analyze the displacement of the dominant period position. The scheduling of the jobs was performed separately in each of the stages. In the first stage the heuristic method N&M was used for each m1 parallel flow shops. In the second stage four constructive rules and two heuristic methods were developed based on traveling salesman problems (TSP). In the last stage the allocation of the jobs was performed according to the arrival time of the available machine or with lesser load. This type of work has not been found in literature; therefore the developed methods were compared among themselves. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation and average computational time. The displacement of the dominant period position as well as the influence of the relation of setup-times and processing-times, were also studied. The results of computational experience are discussed.