[pt] A dissertação estuda o problema do sequenciamento de uma única máquina com tempos de preparação dependentes da sequência da produção e penalidades por antecipação e atraso. Ilustra um método com uma aplicação a um exemplo de processo de fabricação por usinagem. Dessa forma, pretende-se reunir as metodologias de resolução e os trabalhos existentes na literatura sobre o Problema do Sequenciamento e aplicar ao caso específico de um dos Processos de Fabricação mais comuns existentes na indústria. / [en] The dissertation studies the single machine scheduling problem with sequence dependent setup times, with earliness and tardiness penalties, applied to an example of Machining Process Manufacturing. Thus, it is intended to collect the methodologies of resolution and main studies in the literature about the Problem of Sequencing and apply to the specific case of one of the most common manufacturing processes existing in the industry.

[pt] Tradicionalmente, o processo de desenvolvimento de sistemas paralelos enfatiza o desempenho em detrimento de melhores abstrações de programação, o que acarreta problemas como excessiva complexidade de código e redução da manutenibilidade do software. Novas técnicas tem se mostrado interessantes na construção de software paralelo, tais como as tecnologias de componentes de software. Este trabalho realizou um estudo do mecanismo de comunicação paralela entre componentes conhecido como Interfaces Coletivas. Como parte desse estudo, foi realizada uma implementação desse mecanismo no middleware de componentes SCS, onde foram projetados e implementados dois conectores para sincronizaçãoe comunicação paralela. Essa implementação viabilizou uma análise dos requisitos para a integração das Interfaces Coletivas em um middleware orientado a componentes e possibilitou a identificação dos desafios de implementar esse mecanismo em uma linguagem como C++, amplamente usada em aplicações científicas. / [en] Traditionally, the development process of parallel systems emphasizes performance at the expense of better programming abstractions, which causes problems such as excessive code complexity and reduced software maintainability. New techniques have shown expressive results in building parallel software, such as software components technologies. This work conducted a study of the mechanism of parallel communication between components known as Collective Interfaces. As part of this study, we performed an implementation of this mechanism in the SCS middleware, where two connectors were designed and implemented for parallel synchronization and communnication. This implementation allowed us to analyze the requirements for the integration of Collective Interfaces in a component oriented middleware and to identify the challenges of implementing this mechanism in a language as C++, widely used in scientific applications.

[pt] A penetração crescente de geração de energia renovável combinada com o desenvolvimento de baterias eficazes, capazes de estocar energia no curto prazo, demandam a representação horária (ou até sub horária) de modelos de despacho de operação. A necessidade de representar intervalos de tempo tão curtos implicaria no aumento significativo da dimensão do problema, possivelmente o tornando intratável computacionalmente. Nesta dissertação, é proposto um método capaz de levar em consideração tais pequenos intervalos de tempo, evitando o aumento considerável de esforço computacional para problemas de despacho hidrotérmico. Este método consiste em calcular a representação analítica da função custo imediato que é então aplicada no contexto de programação dinâmica dual estocástica (SDDP). A função representa os custos operativos imediatos em função da decisão ótima de geração hidrelétrica total. Como a função de custo imediato é linear por partes, ela possui estrutura muito semelhante à utilizada para aproximar a função de custo futuro (conjunto de cortes). São apresentados resultados da aplicação do método em sistemas de energia reais. / [en] The increasing penetration of renewable generation plants in electric systems, combined with the development of effective short-term energy storage batteries, demand scheduling to be represented on an hourly basis or even in smaller time intervals. Multistage stochastic optimization in such time resolution would imply in the increase of the problem s dimension, which might result in the impossibility of solving such problems. This work presents a method that is able to take into account such small time intervals while avoiding the considerable increase of computational effort. This method consists in calculating the analytical representation of the immediate cost function that is applied in the context of stochastic dual dynamic programming (SDDP). The function represents immediate operation costs as a function of the total hydroelectric generation optimal decision. As the immediate cost function is piecewise linear, it leads to a structure very similar to the one used to approximate the future cost function (cut sets). Results of the application of the method in real electric systems are presented.

[pt] Neste trabalho defenderemos a tese de que funções e continuações como valores de primeira classe constituem uma boa base para construção de abstrações que se beneficiem do comportamento assíncrono da programação distribuída orientada a eventos.Propomos e desenvolvemos o sistema ORFEO, baseado na linguagem LUA 34, que atribui às funções remotas o mesmo status de primeira classe de funções locais.O sistema também possui a propriedade de tratar continuações como valores de primeira classe, permitindo capturar o que resta a ser executado do processamento de um evento.A aplicação dessas duas propriedades, funções remotas e continuações como valores de primeira classe, em um contexto de comunicação por eventos permite que um desenvolvedor possa construir abstrações de objetos distribuídos e de sincronização sem precisar de primitivas especiais no sistema.O resultado une a expressividade de uma linguagem procedural de técnicas funcionais e mecanismos de extensão presentes na linguagem LUA.

[pt] O aumento da produção de petróleo brasileiro e o consequente aumento na demanda por transporte marítimo levaram a PETROBRAS a buscar ferramentas para aumentar a eficiência de seu transporte marítimo. Neste sentido, a atividade de programação de navios busca alocar os navios a um conjunto de cargas definido a priori, respeitando as restrições comerciais e operacionais, a fim de transportá-las com o menor custo possível. Com o intuito de auxiliar o programador nesta atividade, esta dissertação propõe um sistema de suporte à decisão (SSD) baseado em otimização para a programação de navios. O SSD proposto foi desenhado especificamente para a atividade de longo curso de navios de petróleo da PETROBRAS, sendo este gerado a partir da adaptação de modelos disponíveis na literatura acadêmica. Os testes comparativos realizados com o protótipo do SSD na atividade de longo curso de navios de petróleo mostraram que a ferramenta tem um significativo potencial de redução de custo. O SSD proposto se apresentou como uma opção viável para auxiliar a programação de navios da companhia na busca pela redução de custos de transporte marítimo. / [en] The increasing production of Brazilian oil and the consequent increase in the demand for shipping, led PETROBRAS to seek tools to increase the efficiency of its shipping. In this sense, the activity of ship scheduling seeks to assign vessels to a set of cargos, respecting business and operational restrictions in order to transport them with the lowest possible cost. To assist the ship scheduling planner in this activity, this dissertation proposes an optimization based decision support system (DSS) for ship scheduling. The proposed DSS was designed specifically for the long-term tanker scheduling activity at PETROBRAS and it was implemented based on models available in the academic literature. The comparative tests using the DSS prototype proposed in this dissertation showed that it has a potential for significant cost reduction. The proposed DSS was considered a viable tool to assist the ship scheduling planners in reducing shipping costs.

[pt] Uma maneira de localizar uma informação em uma base de dados grande e caótica como a Internet é utilizar um índice hierárquico que respeita alguma maneira de categorizar os dados. Exemplos desta hierarquia são os serviços de diretório, comuns em sites de busca. Porém, esta abordagem pode apresentar algumas desvantagens, como a necessidade de percorrer muitas páginas até chegar em uma informação muito acessada. Uma maneira de tratar este problema é o uso de hotlinks, hyperlinks adicionais que servem como atalho em uma busca. Estudamos algoritmos eficientes para atribuir hotlinks em um diretório web, de modo a reduzir o número máximo ou o número médio de acessos em uma busca. Fornecemos para o problema de minimização do número máximo de acessos um algoritmo (14/3)-aproximado e um algoritmo polinomial exato baseado em programação dinâmica. Por outro lado, para o problema de minimizar o número médio de acessos, adaptamos o algoritmo exato do problema anterior. Entretanto, este algoritmo adaptado é polinomial apenas para sites representados por árvores com altura O(log n). Por isso, introduzimos um parâmetro que permite ao usuário reduzir o tempo de execução em detrimento da qualidade da solução. Para este problema de minimizar o número médio de acessos, realizamos também experimentos comparando nosso algoritmo, um modelo em programação inteira, e alguns algoritmos propostos por outros autores. Introduzimos modificações práticas que melhoraram a performance do nosso algoritmo. / [en] An approach to search an information in a large and chaotic data base like the Internet is to use a hierarquical index regarding some categorization of the data. As an example, we have the web directories, usually found in search engines. However, this approach may have problems, as the need of visiting too many web pages to find a very accessed information. A way to address this problem is the use of hotlinks, which are hyperlinks added to the web site and used as shortcuts in a search. We studied efficient algorithms to assign hotlinks in web directories, in such a way to minimize the maximum or the average number of accesses to find an information. For the problem of minimizing the maximum number of accesses, we provide an (14/3)-approximation algorithm and an exact polinomial time algorithm based on dynamic programming. On the other hand, for the problem of minimizing the expected number of accesses, we adapted the previous exact algorithm. However, this adapted algorithm is polinomial only for web sites represented by trees with height O(log n). So, we introduce a parameter that allows the user to reduce the execution time under the cost of reducing the solution quality. For this problem of minimizing the expected number of accesses, we also made experiments comparing our algorithm, an integer programming model, and some algorithms proposed by other authors. We introduce pratical changes that improved the performance of our algorithm.

[pt] As despesas anuais em saúde para a maioria dos países são crescentes. Segundo a Organização Mundial de Saúde (OMS), em 2011 o Brasil gastou aproximadamente 10 porcento do produto interno bruto em saúde. Consequentemente, incrementar a eficiência na prestação de serviços médicos está se tornando cada vez mais importante. Em um hospital as salas de cirurgia representam um dos principais centros de custos e de rendimentos. As salas de cirurgia são um aspecto difícil de gerenciar devido à prioridade das partes envolvidas no processo, nomeadamente, pacientes, cirurgiões, staff, pessoal administrativo, e a escassez de recursos como leitos, salas de cirurgia, equipamentos especiais, etc. A presente dissertação aborda um problema real de programação de salas de cirurgia para pacientes eletivos de um hospital em Lisboa, onde é proposta uma reformulação do modelo de PLI proposto por Marques et al. (2012). Esta reformulação é baseada no problema da mochila, com o objetivo de encontrar soluções mais eficientes em termos computacionais. De acordo com os testes realizados, uma modificação no modelo que quebre sua simetria além de fornecer uma solução mais eficiente computacionalmente, melhora a solução original pois diminui o gap inicial de 782,59 porcento para 2,25 porcento. Também foi proposto um modelo de simulação no que foram criados vários cenários para avaliar a incerteza envolvida, nos quais a duração média das cirurgias foi submetida a valores majorados. Esta simulação pode servir como ferramenta de apoio na tomada de decisões, pois de acordo com o grau de conservadorismo de quem toma as decisões, podem ser estabelecidas políticas de programação das Salas de Cirurgia. / [en] For most countries annual health expenditures are increasing. According to the World Health Organization (WHO), in 2011, Brazil expends about 10 percent of its gross domestic product on health. Hence, improving health care efficiency is becoming increasingly important. Within a hospital, the Operating Rooms represent a major cost and incomes center. Operating Rooms are a difficult aspect to manage because many stakeholders involved in the process, namely, patients, surgeons, staff, hospital manager, and the scarcity of resources like beds, operating rooms, especial equipment, etc. This dissertation deals with a real problem of operating rooms programming for elective patients in a Lisbon hospital. For this problem, we propose a reformulation of the integer programming model proposed by Marques et al. (2012). This reformulation is based on the knapsack problem, in order to find a more efficient solution in terms of time. According to tests carried out, a reformulation in the model that breaks symmetry, computationally provides a more efficient solution and enhance the original solution because it reduces the initial gap from 782.59 percent to 2.25 percent. In addition, a simulation model was proposed to create various scenarios to assess the involved uncertainty, mainly due to surgery duration variation. This simulation can serve as a support tool in decision-making, according to the degree of conservatism of the decision maker, Operating Rooms scheduling policies can be established.

[pt] A atividade de Planejamento de Suprimento de Petróleo é um elo importante para a integração da Cadeia de Suprimento de Petróleo na PETROBRAS, uma vez que é responsável por refinar as informações do planejamento estratégico a ser implementado no nível operacional. Nesta tese, esse problema é definido e explicado em detalhes e um modelo de programação Inteira Mista é proposto para resolvê-lo. Embora os resolvedores de problemas de programação Inteira Mista tenham evoluído de forma surpreendente na última década, para esta aplicação em particular, com o modelo inicial proposto não é possível obter soluções com qualidade satisfatória em tempo computacional aceitável. Desta forma, a linha de pesquisa desta tese consistiu em investigar, em detalhe, a estrutura deste problemaa fim de encontrar reformulações mais adequadas e novos algoritmos para a solução deste problema. O foco principal desta tese é resolver de forma eficiente o problema de planejamento de suprimento de petróleo na PETROBRAS, no entanto, como subprodutos desse esforço são propostos um novo algoritmo de decomposição e reformulações que podem ser aplicados a uma ampla gama de problemas. No que diz respeito à realização do objetivo principal, todos os casos testados foram resolvidos de maneira eficiente através dos desenvolvimentos propostos. O novo algoritmo de decomposição se mostrou o método mais adequado para resolver as instâncias com mais de duas classes de navios operando em cada plataforma. Já para os casos com uma ou duas classes de navios, a formulação denominada Hull Relaxation, que tem como base uma estrutura definida neste trabalho como Cascading Knapsack Inequalities, é a melhor alternativa de solução. Tendo em vista estas alternativas de soluções, é implementado um algoritmo geral que automaticamente escolhe a melhor opção de solução, em função da estrutura do problema. Para a situação onde o número de classes de navios operando nas diversas plataformas varia entre um e quatro, pode-se usar mais de uma abordagem em paralelo e considerar como solução a alternativa mais rápida ou com melhor resultado. Este modelo está sendo testado na PETROBRAS e tem-se mostrado uma ferramenta eficaz para a integração de sua cadeia de suprimentos de petróleo, bem como permitindo a análise de cenários para a obtenção de soluções alternativas até então não exploradas. / [en] The Petroleum Supply Planning activity is an important link for the integration of the Petroleum Supply Chain at PETROBRAS as it is responsible for refining the strategic supply planning information to be used at the operational level. In this thesis we set the ground for understanding this important problem and we propose a mathematical model to solve it. Although the solvers in the last decade have evolved enormously, for this particular application we cannot get solutions with satisfactory quality in reasonable computational time with only the initial proposed model. This directed the line of research of this thesis into investigating, in detail, the structure of this problem in order to find more suitable reformulations and algorithms to tackle it. Our primary goal is to solve efficiently the petroleum supply planning problem at PETROBRAS. Nevertheless as a by-product of this endeavor, we propose a novel decomposition algorithm and reformulations based on a cascading knapsack structures that turn out to be applicable in a wide range of problems. Concerning the achievement of the main objective, we obtain good results for all instances we tested. We show that the novel decomposition algorithm is the most fitted method to solve the petroleum supply planning problem if we consider more than two tankers to offload each platform. In the case of one or two tankers to offload each platform, the hull relaxation formulation based on the cascading knapsack structure introduced after an inventory reformulation at platforms is the best option if one is to solve this problem. For the real application, these solution alternatives allow to implement a general algorithm that automatically switches to the best solution option depending on the structure of the problem. For the mixed situation, i.e., number of tanker varying from one to four, one can use more than one approaches in parallel and take the fastest or the best result obtained. This model is being tested at PETROBRAS and is showing to be an effective tool to help integrate its petroleum supply chain as well as to do what-if analysis to look for alternative solutions never thought before.

[pt] No nosso quotidiano ouvimos com frequência falar da importância das Tecnologias de Informação e Comunicação (TIC) pelos diversos atores sociais. A influência das TIC atravessa as diversas áreas da sociedade como: agricultura, serviços, comércio, indústria, investigação, entre outros. Se fizermos um raciocínio inverso será difícil nomearmos campos sociais que não sejam influenciados direta ou indiretamente pelas TIC. Além disso a demanda de trabalhadores em Computer Science e áreas relacionadas a STEM (Science, Technology, Engineering and Mathematics) está em aumento. É por isso mesmo que é importante que as crianças desde tenra idade se interessem pela tecnologia (Programação de computadores) e participem dela de uma forma divertida e lúdica. O presente trabalho propõe a criação de uma ferramenta de Realidade Virtual que permite que os estudantes aprendem conceitos básicos da programação e pensamento computacional tendo como finalidade que eles desfrutem da tecnologia e se sintam motivados em aprender mais. A ferramenta é uma Linguagem Visual de Programação. Os algoritmos são formados mediante a montagem de blocos-, resolvendo com isso um dos principais problemas dos estudantes que são os erros de sintaxe. Além disso a ferramenta traz consigo um conjunto de desafios ordenados por níveis, que têm como finalidade ensinar aos estudantes princípios básicos da programação e a lógica (programação sequencial, estrutura de dados repetitiva e condicional), onde em cada nível o aluno aprenderá as diferentes conceitos e comportamentos do pensamento computacional. Para as avaliações com os usuários se contou com a participação de 18 alunos com idades entre 12 e 15 anos provenientes de duas instituições públicas do Rio de Janeiro. Nestas avaliações considerou-se também medir a sensação de imersão mediante a Telepresença, Presença Social e Usabilidade. / [en] Nowadays, we often hear about the importance of Information and Communication Technologies (ICT) by various social actors. The influence of ICT crosses the various areas of society as agriculture, services, trade, industry, research, among others. If we do an inverse reasoning, it will be difficult to name social fields that are not directly or indirectly influenced by ICTs. In addition, the demand for workers in Computer Science and areas related to the STEM (Science, Technology, Engineering, and Mathematics) is on the rise. That is why it is important to make the young person interested in technology (Computer programming) and participate in it in a fun and playful way. The present work proposes the creation of a Virtual Reality tool that allows students to learn basic concepts of programming and computational thinking with the purpose that they enjoy the technology and feel motivated to learn more. The tool is a Visual Programming Language; the algorithms are formed by block-assembly, thereby solving one of the students main problems, which are syntax errors. In addition, the tool brings with it a set of level-ordered challenges aimed at teaching students basic principles of programming and logic (sequential programming, repetitive and conditional data structure), where at each level the student will learn the different concepts and behaviors of computational thinking. For the evaluations with the users we counted on the participation of 18 students between 12 and 15 years old coming from two public institutions of Rio de Janeiro. In these evaluations it was also considered to measure the sensation of immersion through Telepresence, Social Presence and Usability.

[pt] Se diz que uma linguagem de programação tem funções de primeira classe quando ela fornece a capacidade de manipular funções da mesma maneira que outros valores, isto é, guardar em variáveis, passar como parâmetros, etc.. Programar com funções de primeira classe abre o programadora novas formas de abstração e é o padrão em linguagens de programação funcionais. Porém, se tratando de linguagens imperativas (incluindo linguagens orientadas a objeto), cada linguagem tem semântica, propriedades e terminologia diferentes para funções—em grande parte graças a seu foco em mutabilidade, que as linguagens funcionais não têm. Para esclarecer essas diferenças, nós fizemos um levantamento sobre a especificação de funções como valores em linguagens de programação imperativas de várias disciplinas diferentes. Para cada linguagem, nós ilustramos, nos baseando em exemplos, as propriedades dos valores de funções nela,destacando onde ela difere de outras linguagens—tudo isso usando uma terminologia consistente em todas as linguagens. Nós esperamos oferecer uma referência para desenvolvedores compararem e contrastarem as diferentes versões de funções num só lugar. / [en] A programming language is said to have first-class functions when it provides the capability of manipulating functions in the same way as other values, i.e., storing in variables, passing as parameters, etc.. Programming with first-class functions opens the programmer to new forms of abstractions and it s the default in functional programming languages. However, in the realm of imperative languages (including object-oriented languages), each language has different semantics, properties, and terminology for functions—in great part, thanks to their focus on mutability, which isn t present in functional languages. To help shed light on these differences, we made a survey of the specifi-cation of function values in imperative programming languages from many different disciplines. For each language, we illustrate, based on examples,the properties of function values in it, highlighting where it differs from other languages—all this with a consistent terminology in all languages. We provide a reference that compares and contrasts different renditions offunctions in one single place and conclude that the design of functions in a language depends on the interaction of its features and constraints with its functions.