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.

Escalonamento de processos é um tipo de problema de otimização combinatória no qual devemos alocar máquinas à tarefas por períodos específicos de tempo. A literatura contém diversos estudos propondo técnicas para resolver modelos de escalonamento de processos como o job shop e o open shop. Esses modelos permitem que os passos no processo produtivo sejam ou completamente ordenados ou sem ordenação alguma. Com o aumento da complexidade das aplicações industriais no encontramos, mais recentemente, diversos trabalhos que propõe problemas de escalonamento de processos mais gerais para modelar mais precisamente os processos produtivos. O mixed shop, group shop e partial shop são exemplos de tais modelos. Nesse trabalho nós propomos uma busca tabu iterada para o partial shop, que é um modelo geral que inclui diversos modelos mais restritivos. Os componentes novos mais importantes da técnica são o gerador de solução inicial, a vizinhança e o limite inferior para a vizinhança. Em experimentos computacionais nós conseguimos demonstrar que a heurística genérica e única é capaz de competir, e as vezes superar, as técnicas de estado de arte desenvolvidas especificamente para partial, open, mixed e group shop. Algumas vezes uma máquina é o gargalo de um processo produtivo, e é replicada. Na literatura o caso das máquinas paralelas foi incluído em diversas extensões de problemas de escalonamento de processos. Nessa tese nós também propomos uma técnica para escalonar as máquinas paralelas, sem incluí-las explicitamente na representação do problema. Nós usamos técnicas gerais para os casos sem máquinas paralelas para produzir uma busca heurística tabu rápida, e estado da arte, para o caso do job shop com máquinas paralelas. / Shop scheduling is a combinatorial optimization type of problem in which we must allocate machines to jobs for specific periods time. A set of constraints defines which schedules are valid, and we must select one that minimizes or maximizes an objective function. In this work we use the makespan, which is the time the last job finishes. The literature contains several studies proposing techniques to solve shop problems such as the job shop and open shop. These problems allow the steps of the production processes to be either fully ordered or not ordered at all. With increasing complexity and size of industrial applications we find, more recently, several works which propose more general shop problems to model the production processes more accurately. The mixed shop, group shop and partial shop are examples of such problems In this work we propose an iterated tabu search for the partial shop, which is a general problem and includes several other more restrictive shop problems. The most important novel components of the solver are the initial solution generator, the neighbourhood, and the lower bound for the neighbourhood. In computational experiments we were able to show that the general partial shop solver is able to compete with, and sometimes surpass, the state-of-the-art solvers developed specifically for the partial, open, mixed and group shops. Sometimes a machine is a bottleneck in the production process, and is replicated. In the literature the parallel machines case has being included in several extensions of shop problems. In this thesis we also propose a technique to schedule the parallel machines heuristically, without including them explicitly in the representation of the problem. We use general techniques for the non-parallel machine cases to produce a fast tabu search heuristic results for the job shop with parallel machines.

Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

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.

Agricultural producers consider utilizing multiple machines to reduce field completion times for improving effective field capacity. Using a number of smaller machines rather than a single big machine also has benefits such as sustainability via less compaction risk, redundancy in the event of an equipment failure, and more flexibility in machinery management. However, machinery management is complicated due to logistics issues. In this work, the allocation and ordering of field paths among a number of available machines have been transformed into a solvable Vehicle Routing Problem (VRP). A basic heuristic algorithm (a modified form of the Clarke-Wright algorithm) and a meta-heuristic algorithm, Tabu Search, were employed to solve the VRP. The solution considered optimization of field completion time as well as improving the field efficiency. Both techniques were evaluated through computer simulations with 2, 3, 5, or 10 vehicles working simultaneously to complete the same operation. Furthermore, the parameters of the VRP were changed into a dynamic, multi-depot representation to enable the re-route of vehicles while the operation is ongoing. The results proved both the Clarke-Wright and Tabu Search algorithms always generated feasible solutions. The Tabu Search solutions outperformed the solutions provided by the Clarke-Wright algorithm. As the number of the vehicles increased, or the field shape became more complex, the Tabu Search generated better results in terms of reducing the field completion times. With 10 vehicles working together in a real-world field, the benefit provided by the Tabu Search over the Modified Clarke-Wright solution was 32% reduction in completion time. In addition, changes in the parameters of the VRP resulted in a Dynamic, Multi-Depot VRP (DMDVRP) to reset the routes allocated to each vehicle even as the operation was in progress. In all the scenarios tested, the DMDVRP was able to produce new optimized routes, but the impact of these routes varied for each scenario. The ability of this optimization procedure to reduce field work times were verified through real-world experiments using three tractors during a rotary mowing operation. The time to complete the field work was reduced by 17.3% and the total operating time for all tractors was reduced by 11.5%. The task of a single large machine was also simulated as a task for 2 or 3 smaller machines through computer simulations. Results revealed up to 11% reduction in completion time using three smaller machines. This time reduction improved the effective field capacity.

Cellular manufacturing, which is also referred to as group technology among researchers, has primarily been used as a means to increase productivity, efficiency and flexibility. Under group technology, similar jobs, which have similar shape, material, and processing operations are assigned to the same group. Moreover, dissimilar machines are assigned to the same cell to meet the processing requirements of jobs in a group or multiple groups. Group scheduling problems have been studied extensively in the past as implementation of group technology became more prevalent in industry. However, most of the work that has been done has focused on single-criterion optimization. A bi-criteria group scheduling problem in a flow shop with sequence-dependent setup time is investigated in this research. Cellular manufacturing and flow shop are two popular scenarios in industry. To mimic real industry practice, dynamic job releases and dynamic machine availabilities are assumed. The goal is to minimize the weighted sum of total weighted completion time and total weighted tardiness, which satisfy the producer and customer goals separately. Normalized weights are assigned to both criteria to describe the trade-off between the two goals. Two different initial solution finding mechanisms are proposed, and a tabu-search based two-level search algorithm is developed to find near optimal solutions for the problem. An example problem is used to demonstrate the applicability of the search algorithm. A mathematical model is developed and implemented to evaluate the quality of the solutions obtained from the heuristics in small problem instances. Further, to uncover the difference in performance of initial solution finding mechanisms and heuristics, a detailed experimental design is performed. The results show that different heuristics have different performance in solving problems generated with different parameters. / Graduation date: 2012