No description available.

No description available.

No description available.

This work concerns new borders, heuristics, algoritms and mathematic models of pallet loading problem (PLP). We try to describe these computational methods and find out if we can use them in real. We maximalize number of boxes placed on rectangular pallets in a particular warehouse by using chosen heuristics. Every box has a rectangular form with the same lenght and width and is fully placed on the pallet. We can rotate with the box by 90% degree until it is fixed as we want and its side lies parallelly with side of the pallet. All instances are setted in model (X, Y, a, b), where X is lenght, Y width of the pallet, a lenght and b width of the box.

Made available in DSpace on 2017-07-21T14:19:39Z (GMT). No. of bitstreams: 1 Robson Fernando Duda.pdf: 3342961 bytes, checksum: 3f61d3a8f1dcfb461c6860c82d3f54db (MD5) Previous issue date: 2014-02-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This paper presents a solution to the routing problem of vehicles with homogeneous fleet. To do so, heuristic and metaheuristic based algorithms applied towards the development of a decision support system, with georeferenced interface were developed. The algorithms had as base heuristic methods built in two phases, besides a metaheuristic. The interface layer used as visualization component is based in cartographic data that indicates the location of the points to be assisted and the paths that connects them, forming a road system represented using the Google Maps® API. The algorithms were validated using instances from the literature, presenting satisfactory results regarding optimization based in the methods that were used, showing that it is possible the usage of the developed system in the distribution of agricultural products. / Este trabalho apresenta uma solução para o problema de roteamento de veículos com frotas homogêneas. Para tanto, foram desenvolvidos algoritmos baseados em heurísticas e meta-heurísticas aplicadas ao desenvolvimento de um sistema de apoio a decisão, com interface georreferenciada. Os algoritmos tiveram como base métodos heurísticos construtivos e em duas fases, além de uma meta-heurística. A camada de interface utilizada como componente de visualização é baseada em dados cartográficos que indicam a localização dos pontos a serem atendidos e as vias que os interligam, formando a malha viária que é representada utilizando a API do Google Maps®. Os algoritmos foram validados utilizando instâncias da literatura, apresentando resultados satisfatórios em relação a otimização baseada nos métodos utilizados, mostrando ser possível a utilização do sistema desenvolvido para a distribuição de produtos agrícolas.

The rate of data growth in many domains is straining our ability to manage and analyze it. Consequently, we see the emergence of computing systems that attempt to efficiently process data-intensive applications or I/O bound applications with large data. Cloud computing offers “infinite” resources on demand, and on a pay-as-you-go basis. As a result, it has gained interest for large-scale data processing. Given this supposedly infinite resource set, we need a provisioning process to determine appropriate resources for data processing or workload execution. We observe that the prevalent data processing architectures do not usually employ provisioning techniques available in a public cloud, and existing provisioning techniques have largely ignored data-intensive applications in public clouds. In this thesis, we take a step towards bridging the gap between existing data processing approaches and the provisioning techniques available in a public cloud, such that the monetary cost of executing data-intensive workloads is minimized. We formulate the problem of provisioning and include constructs to exploit a cloud’s elasticity to include any number of resources to host a multi-tenant database system prior to execution. The provisioning is modeled as a search problem, and we use standard search heuristics to solve it. We propose a novel framework for resource provisioning in a cloud environment. Our framework allows pluggable cost and performance models. We instantiate the framework by developing various search algorithms, cost and performance models to support the search for an effective resource configuration. We consider data-intensive workloads that consist of transactional, analytical or mixed workloads for evaluation, and access multiple database tenants. The workloads are based on standard TPC benchmarks. In addition, the user preferences on response time or throughput are expressed as constraints. Our propositions and their results are validated in a real public cloud, namely the Amazon cloud. The evaluation supports our claim that the framework is an effective tool for provisioning database workloads in a public cloud with minimal dollar cost. / Thesis (Ph.D, Computing) -- Queen's University, 2013-11-30 19:30:39.427

Tvarkaraščių sudarymo uždaviniai – viena iš sunkiau sprendžiamų problemų, kylančių įvairiose gamybinėse struktūrose, grupė. Darbo pradžioje supažindinama su bendrais tvarkaraščių sudarymo uždavinių bruožais ir jų sprendimo algoritmais. Detaliau nagrinėti šiame darbe parenkamas vienas sunkiausių gamybinių tvarkaraščių ir apskritai kombinatorinių optimizavimo uždavinių – darbo fabriko uždavinys (angl. job shop scheduling problem), kuris be abejo nėra tiksliai sprendžiamas per polinominį sprendimo laiką. Šio uždavinio pradiniai duomenys yra duotos darbų ir įrenginių aibės. Kiekvienas darbas apdorojamas specifine įrenginių tvarka. Uždavinio tikslas – minimizuoti visų darbų atlikimo laiką. Šiam uždaviniui spręsti pristatėme du apytikslius tabu – atkaitinimo modeliavimo bei paieškos kintamose aplinkose algoritmus, priklausančius metaeuristinių metodų šeimai. Iš tabu – atkaitinimo modeliavimo galima nesunkiai gauti paprastą tabu paiešką, tad prie dviejų minėtų algoritmų galima pridėti ir paprastąją tabu paiešką. Šiame darbe atlikta minėtų algoritmų programinė realizacija. Pristatytų algoritmų efektyvumui įvertinti ir algoritmų parametrų parinkimo rekomendacijoms pateikti, buvo pasirinkti gerai literatūroje žinomi bei sunkiau sprendžiami etaloniniai darbo fabriko uždavinių pavyzdžiai. Darbo pabaigoje pateikiamos minėtų algoritmų parametrų parinkimo rekomendacijos ir aptariamas algoritmų efektyvumas, kuris nagrinėtuose uždaviniuose nebuvo pastovus minėtų trijų algoritmų atvejais, t... [toliau žr. visą tekstą] / At the beginning of this work we introduce to the combinatorial optimization, scheduling problems and methods used to solve them. In computer science scheduling problems is considered strongly NP-complete. The combinatorial optimization problem considered in this paper is a static job shop problem scheduling arising in the manufacturing processes. In the static job shop scheduling problem, a finite number of jobs are to be processed by a finite number of machines. Each job consists of a prederminated sequence of task operations, each of which needs to be processed without preemption for a given period of time on a given machine. Tasks of the same job cannot be processed concurrently and each job must visit each machine exactly once. A schedule is an assignment of operation to time slots on a machine. The makespan is the maximum completion time of the jobs and the objective of the job shop scheduling problem is to find a schedule that minimizes the makespan. When the size of problem increases, the computational time of the exact methods grows exponentially. Therefore, the recent research on job shop and other scheduling problems is focused on heuristic algorithms. We also presented some meta-heuristic algorithms such as Tabu search – Simulated annealing (TS/SA), Tabu Search (TS), Variable Neighborhood Search (VNS) and showed their results on some job shop instances. At the end of this work we tell recommendations about choosing suitable parameters.

This work investigates new approaches to the container loading problem which address the issue of how to load three-dimensional, rectangular items (e.g. boxes) into the container in such a way that maximum utilisation is made of the container space. This problem occurs in several industry sectors where the loading approach places cargo effectively into aeroplanes, ships, trailers or trucks in order to save considerable cost. In carrying out this work, the investigation starts by developing a new heuristic approach to the two-dimensional bin packing problem, which has lower complexity than container loading in the aspects of constraints and geometry. A novel approach, including the heuristic strategies and handling method for remaining areas, is developed that can produce good results when testing with benchmark and real world data. Based on the research for two-dimensional bin packing, a novel heuristic approach is developed to deal with the container loading problem with some practical constraints. The heuristic approach to container loading also includes heuristic strategies and the handling of remaining spaces. The heuristic strategies construct effective loading arrangements where combinations of identical or different box types are loaded in blocks. The handling method for remaining spaces further improves the loading arrangements through the representation, partitioning and merging of remaining spaces. The heuristic approach obtains better volume utilisation and the highest stability compared with other published heuristic approaches. However, it does not achieve as high a volume utilisation as metaheuristic approaches, e.g. genetic algorithms and tabu search.To improve volume utilisation, a new hybrid heuristic approach to the container loading problem is further developed based on the tabu search technique which covers the encoding, evaluation criterion and configuration of neighbourhood and candidate solutions. The heuristic strategies as well as the handling method for remaining spaces developed in the heuristic approach are used in this new hybrid tabu search approach. It is shown that the hybrid approach has better volume utilisation than the published approaches under the condition that all loaded boxes with one hundred per cent support from below. In addition, the experimental results show that both the heuristic and hybrid tabu search approaches can also be applied to the multiple container loading problem.

High availability, cost effectiveness and ease of application deployment have accelerated the adoption rate of cloud computing. This fast proliferation of cloud computing promotes the rapid development of large-scale infrastructures. However, large cloud datacenters (DCs) require infrastructure, design, deployment, scalability and reliability and need better management techniques to achieve sustainable design benefits. Resources inside cloud infrastructures often operate at low utilization, rarely exceeding 20-30%, which increases the operational cost significantly, especially due to energy consumption. To reduce operational cost without affecting quality of service (QoS) requirements, cloud applications should be allocated just enough resources to minimize their completion time or to maximize utilization.  The focus of this thesis is to enable resource-efficient and performance-aware cloud infrastructures by addressing above mentioned cost and performance related challenges. In particular, we propose algorithms, techniques, and deployment strategies for improving the dynamic allocation of virtual machines (VMs) into physical machines (PMs).  For minimizing the operational cost, we mainly focus on optimizing energy consumption of PMs by applying dynamic VM consolidation methods. To make VM consolidation techniques more efficient, we propose to utilize multiple paths to spread traffic and deploy recent queue management schemes which can maximize network resource utilization and reduce both downtime and migration time for live migration techniques. In addition, a dynamic resource allocation scheme is presented to distribute workloads among geographically dispersed DCs considering their location based time varying costs due to e.g. carbon emission or bandwidth provision. For optimizing performance level objectives, we focus on interference among applications contending in shared resources and propose a novel VM consolidation scheme considering sensitivity of the VMs to their demanded resources. Further, to investigate the impact of uncertain parameters on cloud resource allocation and applications’ QoS such as unpredictable variations in demand, we develop an optimization model based on the theory of robust optimization. Furthermore, in order to handle the scalability issues in the context of large scale infrastructures, a robust and fast Tabu Search algorithm is designed and evaluated. / High availability, cost effectiveness and ease of application deployment have accelerated the adoption rate of cloud computing. This fast proliferation of cloud computing promotes the rapid development of large-scale infrastructures. However, large cloud datacenters (DCs) require infrastructure, design, deployment, scalability and reliability and need better management techniques to achieve sustainable design benefits. Resources inside cloud infrastructures often operate at low utilization, rarely exceeding 20-30%, which increases the operational cost significantly, especially due to energy consumption. To reduce operational cost without affecting quality of service (QoS) requirements, cloud applications should be allocated just enough resources to minimize their completion time or to maximize utilization.  The focus of this thesis is to enable resource-efficient and performance-aware cloud infrastructures by addressing above mentioned cost and performance related challenges. In particular, we propose algorithms, techniques, and deployment strategies for improving the dynamic allocation of virtual machines (VMs) into physical machines (PMs).

O presente trabalho tem por objetivo a proposição de uma abordagem para gestão integrada da operação do sistema elétrico em tempo real pelo diagnóstico da interrupção e determinação de planos de atenuação dos efeitos pela definição da topologia do sistema, com propostas de cortes seletivos da carga em condições de esgotamento da capacidade de transferência. A metodologia proposta abrange sistemas elétricos de grande porte e de diferentes níveis de tensão, tais como sistemas de sub-transmissão e distribuição, simultaneamente e com geração distribuída. Como técnica de solução é aplicada a Busca Tabu para minimização do total de seções desconectadas (desenergizadas) e o número de manobras realizadas para atendimento em casos contingenciais, com atendimento de clientes prioritários e alívio de carga e geração distribuída. A codificação e estrutura de dados aplicados propiciam uma melhor eficiência computacional, favorecendo a aplicação em sistemas operacionais de tempo real. A modelagem proposta é avaliada em sistemas de testes adaptados da literatura, demonstrando a qualidade, robustez e eficiência computacional nos resultados obtidos da abordagem proposta. / The present work aims at proposing an automatic computational methodology to electrical systems operational management in real time via the interruption diagnosis and effect attenuation plan definition by means of system topology determination with load curtailment in load transference capacity exhaustion conditions. The proposed methodology tackles large electrical systems with different voltage levels, such as sub-transmission and distribution systems simultaneously with distributed generators. The Tabu Search is applied to minimize the out-of-service area and the number of switching operations during contingencies with priority customer, load curtailment and distributed generators. The software codification and data structure applied provide computational efficiency, favoring the application to electrical systems operation in real time and the proposed model is validated with test systems from the literature, ensuring the computational efficiency and quality of results.