Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:36:28Z (GMT). No. of bitstreams: 1 Marini_BrunoConti_M.pdf: 1252984 bytes, checksum: 40439ec279501ea9ca594d950e42a229 (MD5) Previous issue date: 2011 / Resumo: Uma das formas mais econômicas e, em relação ao meio ambiente, mais seguras de se transportar combustíveis é bombeá-los através de redes de dutos. Contudo, as diversas restrições operacionais que precisam ser consideradas fazem com que o planejamento das atividades de bombeamento se transforme em um grande desafio. Dentre os diversos cenários em que o problema se apresenta, investiga-se nessa dissertação o caso de uma rede composta de um único duto onde diversos produtos são bombeados unidirecionalmente. Trata-se de uma situação real enfrentada pela Petrobras no gerenciamento da rede OSBRA. Na literatura existem propostas de vários modelos matemáticos para tratar esta instância particular do problema. Contudo, no melhor do nosso conhecimento, não existem comparações efetivas entre estes modelos e os algoritmos usados para computá-los. Nessa dissertação faz-se uma comparação aprofundada entre três desses modelos, a qual se baseia em uma metodologia sugerida pelos técnicos da Petrobras. Neste trabalho são destacadas não só as dificuldades envolvendo a implementação dos modelos, bem como as deficiências encontradas na aplicação da metodologia de comparação usada pela empresa. Propostas são feitas nessa dissertação no intuito de superar estes obstáculos / Abstract: One of the most economical and, with respect to the environment, safest ways to transport fuel is to pump them through pipeline networks. However, the several operational constraints that have to be considered turn the planning of these activities into a major challenge. Among the several cenarios in which the problem arises, in this dissertation we investigate the case of a network composed of a single pipeline through which several products are pumped unidirectionally. This is a real situation faced by Petrobras in the management of the OSBRA network. In the literature there are proposals of various mathematical models to tackle this particular instance of the problem. However, to the best of our knowledge, there are no effective comparisons of these models and of the algorithms used to compute them. In this dissertation an in-depth comparison is made between three of these models, which is based on a methodology suggested by the technical staff of Petrobras. In this work we highlight not only the difficulties involving the implementation of the models but also the deficiencies encountered in the application of the comparison methodology used by the company. Proposals are made in this dissertation in an attempt to overcome these obstacles / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

En réponse aux contraintes économiques, au problème du vieillissement de la population et aussi à la volonté des patients de se faire soigner dans le milieu familial, l’Hospitalisation À Domicile (HAD) prend de plus en plus d’ampleur. Dans ce travail de recherche, nous nous intéressons aux établissements d’hospitalisation à domicile, parmi les différentes problématiques qui existent dans ce domaine, nous étudions le problème de routage et de planification des personnels.Nous développons tout d’abord un modèle de programmation linéaire en nombres entiers qui permet de formuler clairement les contraintes du problème.Nous présentons par la suite, une matheuristique permettant de résoudre le problème défini sur une journée de planification. Nous développons également une variante de notre matheuristique sur un horizon de 14 jours. Cette dernière prend en considération plusieurs contraintes en plus de celles considérées pour la planification sur une journée. Enfin, nous introduisons un problème de réoptimisation de routage et de la planification des personnels pour l’hospitalisation à domicile et présentons quelques approches de résolutions. Ces différentes méthodes combinent des heuristiques, la programmation dynamique et la programmation mathématique. / Home health care (HHC), i.e., visiting and nursing patients athome, is a growing sector in the medical care system. There fore, the optimal scheduling of the health care staffs arises. The objective of this problem consists in constructing routes and rosters for the staffs while optimizing costs. We propose an integer linear programming formulation (ILP) that clearly formulate the constraints of the problem. We present a matheuristic to solve the daily routing and rostering problem. We also develop a variant of our matheuristic defined for a period of 14 days. It takes into account several constraints in addition to those considered in the daily planning. Finally, we introduce the problem of reoptimizing the routing and rostering staffs and we give some ideas to solve this problem. These methods combine heuristic algorithms, dynamic programming and mathematical programming.

This research aims to develop solutions to relieve system stress conditions in electric grids. The approach adopted in this research is based on a new concept in the Smart Grid, namely, demand response optimization. A number of demand response programs with energy storage systems are designed to enable a community to achieve optimal demand side energy management. The proposed models aim to improve the utilization of the demand side energy through load management programs including peak shaving, load shifting, and valley lling. First, a model is proposed to nd the optimal capacity of the battery energy storage system (BESS) to be installed in a power system. This model also aims to design optimal switchable loads programs for a community. The penetration of the switchable loads versus the size of the BESS is investigated. Another model is developed to design an optimal load operation scheduling of a residential heating ventilation and air-conditioning system (HVACs). This model investigates the ability of HVACs to provide optimal demand response. The model also proposes a comfort/cost trade-os formulation for end users. A third model is proposed to incorporate the uncertainty of the photovoltaic power in a residential model. The model would nd the optimal utilization of the PV-output to supply the residential loads. In the first part of this research, mixed integer programming (MIP) formulations are proposed to obtain the optimal capacity of the (BESS) in a power system. Two optimization problems are investigated: (i) When the BESS is owned by a utility, the operation cost of generators and cost of battery will be minimized. Generator on/o states, dispatch level and battery power dispatch level will be determined for a 24-hour period. (ii) When the BESS is owned by a community for peak shaving, the objective function will have a penalty component for the deviation of the importing power from the scheduled power. MIP problems are formulated and solved by CPLEX.The simulation results present the effect of switchable load penetration level on battery sizing parameters. In the second part, a mixed integer programming (MIP) based operation is proposed in this part for residential HVACs. The objective is to minimize the total cost of the HVAC energy consumption under varying electricity prices. A simplied model of a space cooling system considering thermal dynamics is adopted. The optimization problems consider 24-hour operation of HVAC. Comfort/cost trade-o is modeled by introducing a binary variable. The big-M technique is adopted to obtain linear constraints while considering this binary variable. The MIP problems are solved by CPLEX. Simulation results demonstrate the effectiveness of HVAC's ability to respond to varying electricity price. Then, in the final part of this research, two Benders Decomposition strategies are applied to solve a stochastic mixed integer programming (MIP) formulation to obtain the optimal sizing of a photovoltaic system (PV) and battery energy storage system (BESS) to power a residential HVACs. The uncertainty of PV output is modeled using stochastic scenarios with the probability of their occurrence. Total cost including HVAC energy consumption cost and PV/battery installation cost is to be minimized with the system at grid-connected mode over eight hours subject to a varying electricity price. The optimization problem will nd the optimal battery energy capacity, power limit, a number of PV to be installed, and expected HVAC on/o states and BESS charging/discharging states for the next eight hours. This optimization problem is a large-scale MIP problem with expensive computing cost.

Routing and designing are essential for transportation networks. With effective routing and designing policies, transportation networks can work safely and efficiently. There are two transportation problems: hazardous materials (hazmat) transportation and warehouse logistics. This dissertation addresses the routing of networks for both problems. For hazmat transportation, the routing can be regulated via network design. Due to catastrophic consequences of potential accidents in hazmat transportation, a risk-averse approach for routing is necessary. In this dissertation, we consider spectral risk measures, for risk-averse hazmat routing. In addition, we introduce a network design problem to select a set of closed road segments for hazmat traffic with conditional value-at-risk (CVaR) to regulate hazmat routing. In warehouses, the routing of electric forklifts with sufficient battery levels is for material handling. The optimization model of dynamic wireless charging lane location is proposed under the workflow congestion in parallel-aisle warehouses. Considering the uncertainty of demands, the wireless charging lane location problem is formulated as a two-stage stochastic programming model. We confirm the efficiency of the proposed algorithms in solving these problems and the key advantages of use the proposed routing and designing policies via case studies.

Inventories totaling 1.7 trillion U.S. dollars represent an opportunity for U.S. manufacturers. This exploratory case study researched supply chain strategies used to manage inventory in manufacturing operations of a U.S. manufacturing company. A mature value chain contained within a single organization using the value chain framework was the basis for this study. Individual interviews conducted with 16 managers responsible for defining and implementing inventory control strategies, and 4 internal users provided primary information for the study. Other sources of information included a value chain map created through the observation of operations, various inventory measurements, and policies and guidelines related to managing inventory levels. An inductive content analysis employing zero-level coding of the interview transcripts identified 4 themes that describe inventory control strategies as economic order quantity, kanban, vendor managed inventory, and process integration. Physical observation of the value chain, review of supporting documents, and analysis of inventory data ensured the trustworthiness of interpreted themes. Findings identified no single inventory control strategy that fit all applications. Findings also revealed that the financial governing bodies' measurements were not the best tools for operational managers' improvement activities related to inventory control. Included are measures providing alternative means to gauge inventory efficiency. With the results of this study, managers may develop effective strategies to optimize inventory and improve material flow. Manufacturing managers improving material flow may promote sustainability of raw materials and business efficiencies through reduced waste, improved environmental conditions, and increased employment opportunities in associated communities.

Construction management projects involve complex, dynamic environments resulting in uncertainty and risk, compounded by demanding time constraints. Research indicated project managers have struggled to identify best practices for scheduling construction projects via critical path methodologies while searching for tools to increase timely job completions and budget profits. The purpose of this single case study was to explore the strategies that construction project managers used to manage scheduled construction project delivery on time. The constructivist philosophical worldview was used as the framework for this study. Data were collected from semistructured interviews from 7 project managers from 5 different construction companies selected via purposive sampling throughout Florida. All project managers had at least 15 years of experience and multiple construction projects with managing scheduled project deliveries. Three themes emerged through thematic analysis: project, time delay, and cost. A construction project can have many variables that project managers cannot control such as the issue of on-time scheduling. Project managers identified that a project could be within the budget or cost set for the project and still be on time and go over budget or be within budget and not meet schedule. No broad support was found for agile project management, and no confirmation could be made that principles of philosophical theories were critical for project success. Implications for a positive social change result in creating new jobs during and after construction, bringing new individuals to neighborhoods, schools, and area businesses.

Reinforcement learning techniques offer a very powerful method of finding solutions in unpredictable problem environments where human supervision is not possible. However, in many real world situations, the state space needed to represent the solutions becomes so large that using these methods becomes infeasible. Often the vast majority of these states are not valuable in finding the optimal solution. This work introduces a novel method of using linear programming to identify and represent the small area of the state space that is most likely to lead to a near-optimal solution, significantly reducing the memory requirements and time needed to arrive at a solution. An empirical study is provided to show the validity of this method with respect to a specific problem in vehicle dispatching. This study demonstrates that, in problems that are too large for a traditional reinforcement learning agent, this new approach yields solutions that are a significant improvement over other nonlearning methods. In addition, this new method is shown to be robust to changing conditions both during training and execution. Finally, some areas of future work are outlined to introduce how this new approach might be applied to additional problems and environments.

Ce travail de thèse de doctorat est dédié à l'étude d'un problème de placement de tâches dans le domaine de la compilation d'applications pour des architectures massivement parallèles. Ce problème vient en réponse à certains besoins industriels tels que l'économie d'énergie, la demande de performances pour les applications de type flots de données synchrones. Ce problème de placement doit être résolu dans le respect de trois critères: les algorithmes doivent être capable de traiter des applications de tailles variables, ils doivent répondre aux contraintes de capacités des processeurs et prendre en compte la topologie des architectures cibles. Dans cette thèse, les tâches sont organisées en réseaux de communication, modélisés sous forme de graphes. Pour évaluer la qualité des solutions produites par les algorithmes, les placements obtenus sont comparés avec un placement aléatoire. Cette comparaison sert de métrique d'évaluation des placements des différentes méthodes proposées. Afin de résoudre à ce problème, deux algorithmes de placement de réseaux de tâches de grande taille sur des architectures clusterisées de processeurs de type many-coeurs ont été développés. Ils s'appliquent dans des cas où les poids des tâches et des arêtes sont unitaires. Le premier algorithme, nommé Task-wise Placement, place les tâches une par une en se servant d'une notion d'affinité entre les tâches. Le second, intitulé Subgraph-wise Placement, rassemble les tâches en groupes puis place les groupes de tâches sur les processeurs en se servant d'une relation d'affinité entre les groupes et les tâches déjà affectées. Ces algorithmes ont été testés sur des graphes, représentants des applications, possédant des topologies de types grilles ou de réseaux de portes logiques. Les résultats des placements sont comparés avec un algorithme de placement, présent dans la littérature qui place des graphes de tailles modérée et ce à l'aide de la métrique définie précédemment. Les cas d'application des algorithmes de placement sont ensuite orientés vers des graphes dans lesquels les poids des tâches et des arêtes sont variables similairement aux valeurs qu'on peut retrouver dans des cas industriels. Une heuristique de construction progressive basée sur la théorie des jeux a été développée. Cet algorithme, nommé Regret Based Approach, place les tâches une par une. Le coût de placement de chaque tâche en fonction des autres tâches déjà placées est calculée. La phase de sélection de la tâche se base sur une notion de regret présente dans la théorie des jeux. La tâche qu'on regrettera le plus de ne pas avoir placée est déterminée et placée en priorité. Afin de vérifier la robustesse de l'algorithme, différents types de graphes de tâches (grilles, logic gate networks, series-parallèles, aléatoires, matrices creuses) de tailles variables ont été générés. Les poids des tâches et des arêtes ont été générés aléatoirement en utilisant une loi bimodale paramétrée de manière à obtenir des valeurs similaires à celles des applications industrielles. Les résultats de l'algorithme ont également été comparés avec l'algorithme Task-Wise Placement, qui a été spécialement adapté pour les valeurs non unitaires. Les résultats sont également évalués en utilisant la métrique de placement aléatoire. / This Ph.D thesis is devoted to the study of the mapping problem related to massively parallel embedded architectures. This problem arises from industrial needs like energy savings, performance demands for synchronous dataflow applications. This problem has to be solved considering three criteria: heuristics should be able to deal with applications with various sizes, they must meet the constraints of capacities of processors and they have to take into account the target architecture topologies. In this thesis, tasks are organized in communication networks, modeled as graphs. In order to determine a way of evaluating the efficiency of the developed heuristics, mappings, obtained by the heuristics, are compared to a random mapping. This comparison is used as an evaluation metric throughout this thesis. The existence of this metric is motivated by the fact that no comparative heuristics can be found in the literature at the time of writing of this thesis. In order to address this problem, two heuristics are proposed. They are able to solve a dataflow process network mapping problem, where a network of communicating tasks is placed into a set of processors with limited resource capacities, while minimizing the overall communication bandwidth between processors. They are applied on task graphs where weights of tasks and edges are unitary set. The first heuristic, denoted as Task-wise Placement, places tasks one after another using a notion of task affinities. The second algorithm, named Subgraph-wise Placement, gathers tasks in small groups then place the different groups on processors using a notion of affinities between groups and processors. These algorithms are tested on tasks graphs with grid or logic gates network topologies. Obtained results are then compared to an algorithm present in the literature. This algorithm maps task graphs with moderated size on massively parallel architectures. In addition, the random based mapping metric is used in order to evaluate results of both heuristics. Then, in a will to address problems that can be found in industrial cases, application cases are widen to tasks graphs with tasks and edges weights values similar to those that can be found in the industry. A progressive construction heuristic named Regret Based Approach, based on game theory, is proposed. This heuristic maps tasks one after another. The costs of mapping tasks according to already mapped tasks are computed. The process of task selection is based on a notion of regret, present in game theory. The task with the highest value of regret for not placing it, is pointed out and is placed in priority. In order to check the strength of the algorithm, many types of task graphs (grids, logic gates networks, series-parallel, random, sparse matrices) with various size are generated. Tasks and edges weights are randomly chosen using a bimodal law parameterized in order to have similar values than industrial applications. Obtained results are compared to the Task Wise placement, especially adapted for non-unitary values. Moreover, results are evaluated using the metric defined above.

Natural and man-made disasters, such as earthquakes, floods, plane crashes, high-rise building collapses, or major nuclear facility malfunctions, pose an ever-present challenge to public emergency services. Disasters may result in a large volume of responders arriving on-scene to provide assistance to victims. Coordination of responding resources is a major problem in disasters. The main motivation for the work is that disaster response and recovery efforts require timely interaction and coordination of public emergency services in order to save lives and property. In the present research effort, we are primarily concerned with assisting the Emergency medical agencies that deal with emergency situations by developing a decision-support system that can help them respond quickly and efficiently to a given situation. The overall goal of this project develop a practical solution for the resource allocation problem which can be integrated with the DIORAMA system that we have developed in our lab. The DIORAMA system collects information like victim’s location and condition in disaster site. Based on the information collected by the DIORAMA system, we developed an algorithm that can find the nearest resources from the disaster site to mitigate the risk. This problem can be solved in two phases, allocation and dispatching. The Emergency manager will provide the system Priority ratings of the cluster with respect to the emergency response resources and also the demands at each cluster. In the first phase allocation, we determine the number of emergency resources that can be allocated at each cluster which minimizes the overall risk. We define risk as the fraction of the unsatisfied demand. The output of this phase is the optimal resource allocation table. In the second phase, we find the nearest resource warehouse that can cater the demands of the cluster and dispatch the resources accordingly to the disaster site. This is also an integer programming problem. The final output of this phase is the dispatch table from which we can determine from where should the resources has to be sent to the clusters for an efficient and timely response. This is also rendered on Google Maps.

Key performance measures for PC performance are timeliness and continuity. Whereas the first refers to the ability to obtain an appointment as soon as possible, the latter warrants a patient being able to see a familiar physician. In this context one has to consider the two types of appointments - same-day and prescheduled. The former is characterized by an urgent need of the patient to see a physician, the latter embodies non-urgent follow-up visits or regular appointments due to a chronic comorbidity. How should requests for appointments be assigned in order to deliver on the conflicting key metrics? What impact does the presence and the location of prescheduled appointments have in this context? How does the capacity allocation between prescheduled and same-day demand influence the decision making in the clinic? Using a stochastic dynamic program to model the dynamics of practice, we explore various ways of managing the inherent flexibility of physicians to see each others’ patients. Patients are calling in for same-day appointments. Thus, assignment decisions have to be made dynamically in real time under uncertainty of future demand and in presence of prescheduled appointment slots. The study consists of three parts: first, we examine the impact of the location of prescheduled appointments on the performance of the clinic. Second, we use our structural insights gained in the first part in order to derive implementable heuristic assignment policies. Third, we evaluate the performance of the heuristics in comparison to the optimal solution gained in the stochastic dynamic program and derive implications for the practice of primary care.