In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.

In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.

Thesis (Ph.D.) -- La Trobe University, 2005. / Submitted in total fulfilment of the requirements for the degree of Doctor of Philosophy to the Zoology Dept., School of Life Sciences, Faculty of Science, Technology and Engineering. Research. Includes bibliographical references (leaves 133-152). Also available via the World Wide Web.

Thesis (M.S.)--Western Washington University, 2008. / Includes bibliographical references (p. 116-128). Also available online.

Thesis (Ph. D.)--University of Washington, 1998. / Vita. Includes bibliographical references (leaves [235]-251).

Thesis (Ph. D.)--Ohio State University, 2009. / Title from first page of PDF file. Includes vita. Includes bibliographical references (p. 82-92).

Data orientation is a common design principle in distributed data management systems. In contrast to process-oriented or transaction-oriented system designs, data-oriented architectures are based on data locality and function shipping. The tight coupling of data and processing thereon is implemented in different systems in a variety of application scenarios such as data analysis, database-as-a-service, and data management on multiprocessor systems. Data-oriented systems, i.e., systems that implement a data-oriented architecture, bundle data and operations together in tasks which are processed locally on the nodes of the distributed system. Allocation strategies, i.e., methods that decide the mapping from tasks to nodes, are core components in data-oriented systems. Good allocation strategies can lead to balanced systems while bad allocation strategies cause skew in the load and therefore suboptimal application performance and infrastructure utilization. Optimal allocation strategies are hard to find given the complexity of the systems, the complicated interactions of tasks, and the huge solution space. To ensure the scalability of data-oriented systems and to keep them manageable with hundreds of thousands of tasks, thousands of nodes, and dynamic workloads, fast and reliable allocation strategies are mandatory. In this thesis, we develop novel allocation strategies for data-oriented systems based on graph partitioning algorithms. Therefore, we show that systems from different application scenarios with different abstraction levels can be generalized to generic infrastructure and workload descriptions. We use weighted graph representations to model infrastructures with bounded and unbounded, i.e., overcommited, resources and possibly non-linear performance characteristics. Based on our generalized infrastructure and workload model, we formalize the allocation problem, which seeks valid and balanced allocations that minimize communication. Our allocation strategies partition the workload graph using solution heuristics that work with single and multiple vertex weights. Novel extensions to these solution heuristics can be used to balance penalized and secondary graph partition weights. These extensions enable the allocation strategies to handle infrastructures with non-linear performance behavior. On top of the basic algorithms, we propose methods to incorporate heterogeneous infrastructures and to react to changing workloads and infrastructures by incrementally updating the partitioning. We evaluate all components of our allocation strategy algorithms and show their applicability and scalability with synthetic workload graphs. In end-to-end--performance experiments in two actual data-oriented systems, a database-as-a-service system and a database management system for multiprocessor systems, we prove that our allocation strategies outperform alternative state-of-the-art methods.

The additive partition diversity has been a promising method to analyze patterns of diversity in hierarchical studies. Streams are recognized for having a spatial structure hierarchically organized in increasing scales, ranging from places such as habitat, stretch, streams and the entire drainage system. The diversity and spatial distribution of mayfly nymphs communities were studied over four hierarchical spatial scales in Planalto Sul-rio-grandense (sampling units, substrates, streams and basin). Additionally, the influence of local environmental descriptors on the structure of the nymphs communities was tested. Samples were collected in 13 streams of two independent parts of the Planalto Sul-rio-grandense, in each stream were obtained 10 samples in falls five in stone substrate and five in leaves. The spatial distribution of mayfly nymphs showed structuring according to types of substrates sampled. The partitioning of diversity among the analyzed scales revealed that the major portion of beta diversity occurred between the sampling units and between the streams of the same dimension and a very small amount in the range of substrate. Thus, we assume that the fauna of aggregation in the smaller spatial scale was not due to substrate differences associated with rapid but the variation between rapids, reflecting the predominance of specific processes related to the availability of resources. We assume also that the nymphs of ephemeral not have barriers to the use at these substrate, which could actively move between the rapids of streams. In addition, the diversity that occurs between streams of the same part, can be attributed to local characteristics of each stream, such as slope, conductivity and current velocity. Finally, three environmental descriptors (altitude, slope, and dissolved oxygen) were important to structure the mayfly community at the streams of Planalto Sulriograndense. We conclude that the scales from rapids (sampling units) and between streams are scales that have the largest portion of the variability of the taxonomic composition showing to be more effective in assessing the spatial variation of mayfly nymphs communities. / A partição aditiva da diversidade vem sendo um método promissor para analisar padrões de diversidade em estudos hierárquicos. Riachos são reconhecidos por apresentarem uma estrutura espacial organizada hierarquicamente, em escalas crescentes, variando desde locais, como habitat, trecho, riachos e toda a rede de drenagem. A diversidade e distribuição espacial das comunidades de ninfas de Ephemeroptera foram estudadas ao longo de quatro escalas espaciais hierárquicas no Planalto Sul-rio-grandense (unidades amostrais, substratos, riachos e bacias). Adicionalmente, a influência de descritores ambientais locais sobre a estrutura das comunidades das ninfas foi testada. As coletas foram realizadas em 13 riachos de duas bacias independentes do Planalto Sul-rio-grandense, em cada riacho foram obtidas 10 amostras em corredeiras, cinco em substrato de pedras e cinco em folhas. A distribuição espacial das ninfas de Ephemeroptera não mostrou estruturação segundo os tipos de substratos amostrados em corredeiras de riachos. A partição da diversidade entre as escalas analisadas revelou que a maior porção da diversidade beta ocorreu entre as unidades amostrais e entre os riachos da mesma bacia e uma porção muito pequena na escala de substrato e de bacia. Dessa forma, supomos que a agregação da fauna na menor escala espacial não foi devido à diferença de substrato, mas a variação entre corredeiras, refletindo a predominância de processos pontuais relacionados à disponibilidade de recursos. Supomos ainda, que as ninfas de efêmeros não encontram barreiras para a utilização desses substratos, as quais poderiam se deslocar ativamente entre as corredeiras de riachos. Adicionalmente, a diversidade que ocorre entre os riachos de uma mesma vertente, pode ser atribuída as características locais de cada riacho, tais como declividade, condutividade e velocidade da correnteza. Por fim, três descritores ambientais (altitude, declividade e oxigênio dissolvido) foram importantes para estrutura da comunidade de Ephemeroptera em riachos do Planalto Sul-riograndense. Concluímos que as escalas entre corredeiras (unidades amostrais) e entre riachos são escalas que detêm a maior porção da variabilidade da composição taxonômica evidenciando-se mais efetivas na avaliação da variação espacial das comunidades de ninfas de Ephemeroptera.

[pt] As principais estratégias de sintonia fina utilizadas por administradores de bancos de dados relacionais são a construção de estruturas de acesso, como índices, índices parciais e visões materializadas, e técnicas como desnormalização e reescrita de consultas. Estas técnicas e estruturas de acesso, juntas ou separadas, podem melhorar o desempenho das consultas submetidas ao banco de dados. O particionamento de tabelas do banco de dados, técnica tradicionalmente utilizada para distribuição de dados, também possui potencial para sintonia fina, pois permite que a varredura das tabelas seja realizada somente nas partições que satisfazem os predicados das consultas. Mesmo em consultas com predicados de seletividade alta, cujos planos de execução frequentemente utilizam índices, o particionamento pode oferecer um benefício ainda maior. Esta dissertação de mestrado propõe avaliar o particionamento como ação de sintonia fina de bancos de dados relacionais e, para tanto, desenvolve heurísticas para seleção de estratégias de particionamento e avaliação do seu benefício. Uma avaliação da qualidade dos resultados obtidos é realizada através de experimentos com um benchmark padrão para este tipo de pesquisa e mostramos que, em certos casos, é vantajoso particionar dados. / [en] The main fine tuning strategies used by relational database administrators are the construction of access structures, such as indexes, partial indexes and materialized views, and techniques such as denormalization and query rewriting. These techniques and access structures, together or separately, can improve the performance of queries submitted to the database. Database partitioning, a technique traditionally used for data distribution, has also the potential for fine tuning, since it allows the scanning of tables to be performed only on partitions that satisfy query predicates. Even in queries with high selectivity predicates, whose execution plans often use indexes, partitioning can offer even greater benefit. This dissertation proposes to evaluate the partitioning as a fine tuning action of relational databases and, for that, develops heuristics for selection of partitioning strategies and evaluation of its benefit. An evaluation of the quality of the results obtained is carried out through experiments with a standard benchmark for this type of research and we have shown that, in certain cases, it is advantageous to partition data.

No description available.