The container loading problem considered in this thesis is to determine placements of a set of packages within one or multiple shipping containers. Smaller packages are consolidated on pallets prior to being loaded in the shipping containers together with larger packages. There are multiple objectives which may be summarized as fitting all the packages while achieving good stability of the cargo as well as the shipping containers themselves. According to recent literature reviews, previous research in the field have to large extent been neglecting issues relevant in practice. Our real-world application was developed for the industrial company Atlas Copco to be used for sea container shipments at their Distribution Center (DC) in Texas, USA. Hence all applicable practical constraints faced by the DC operators had to be treated properly. A high variety in sizes, weights and other attributes such as stackability among packages added complexity to an already challenging combinatorial problem. Inspired by how the DC operators plan and perform loading manually, the batch concept was developed, which refers to grouping of boxes based on their characteristics and solving subproblems in terms of partial load plans. In each batch, an extensive placement heuristic and a load plan evaluation run iteratively, guided by a Genetic Algorithm (GA). In the placement heuristic, potential placements are evaluated using a scoring function considering aspects of the current situation, such as space utilization, horizontal support and heavier boxes closer to the floor. The scoring function is weighted by coefficients corresponding to the chromosomes of an individual in the GA population. Consequently, the fitness value of an individual in the GA population is the rating of a load plan. The loading optimization software has been tested and successfully implemented at the DC in Texas. The software has been proven capable of generating satisfactory load plans within acceptable computation times, which has resulted in reduced uncertainty and labor usage in the loading process. Analysis using real sea container shipments shows that the GA is able to tune the scoring coefficients to suit the particular problem instance being solved.

A case study for the tool LBTest illustrating benets and limitations of the tool along the terms of usability, results and costs. The study shows the use of learning based testing on a safety critical application in the avionics industry. While requiring the user to have the oretical knowledge of the tools inner workings, the process of using the tool has benefits in terms of requirement analysis and the possibility of finding design and implementation errors in both the early and late stages of development

Spatial layout design must consider not only ease of movement for pedestrians under normal conditions, but also their safety in panic situations, such as an emergency evacuation in a theatre, stadium or hospital. Using pedestrian simulation statistics, the movement of crowds can be used to study the consequences of different spatial layouts. Previous works either create an optimal spatial arrangement or an optimal pedestrian circulation. They do not automatically optimise both problems simultaneously. Thus, the idea behind the research in this thesis is to achieve a vital architectural design goal by automatically producing an optimal spatial layout that will enable smooth pedestrian flow. The automated process developed here allows the rapid identification of layouts for large, complex, spatial layout problems. This is achieved by using Cellular Automata (CA) to model pedestrian simulation so that pedestrian flow can be explored at a microscopic level and designing a fitness function for heuristic search that maximises these pedestrian flow statistics in the CA simulation. An analysis of pedestrian flow statistics generated from feasible novel design solutions generated using the heuristic search techniques (hill climbing, simulated annealing and genetic algorithm style operators) is conducted. The statistics that are obtained from the pedestrian simulation is used to measure and analyse pedestrian flow behaviour. The analysis from the statistical results also provides the indication of the quality of the spatial layout design generated. The technique has shown promising results in finding acceptable solutions to this problem when incorporated with the pedestrian simulator when demonstrated on simulated and real-world layouts with real pedestrian data.

Over the last few years, the GRAPE algorithm has become of central importance in the development of general purpose control sequences for several branches of Nuclear Magnetic Resonance. In this thesis, the application of the GRAPE algorithm to quantum information processing tasks is considered. First the theory underlying the algorithm is reviewed in detail, then a number of extensions and improvements to the core technique are developed. An implementation of the GRAPE algorithm using GPUs is presented and compared with a standard CPU based implementation. A variety of experimental results are presented covering many different aspects of the practical use of GRAPE. This includes an evaluation of some of the errors that can affect the performance of GRAPE sequences in real experiments, and their relative importance. The strengths and weaknesses of GRAPE compared to the other possible techniques are assessed, and some suggestions made regarding potential developments in this direction. Pseudo-pure states are a crucial component of any NMR based quantum computer, but many current methods for preparing them sacrifice purity in exchange for simplicity in the preparation sequence. This thesis also presents a new method for robustly generating pseudo-pure states with the maximum possible purity.

Parameter estimation is a long-lasting topic in queueing systems and has attracted considerable attention from both academia and industry. In this thesis, we design a parameter estimation framework for a tandem queueing system that collects end-to-end measurement data and utilizes the finite mixture model for the maximum likelihood (ML) estimation. The likelihood equations produced by ML are then solved by the iterative expectation-maximization (EM) algorithm, a powerful algorithm for parameter estimation in scenarios involving complicated distributions. We carry out a set of experiments with different parameter settings to test the performance of the proposed framework. Experimental results show that our method performs well for tandem queueing systems, in which the constituent nodes' service time follow distributions governed by exponential family. Under this framework, both the Newton-Raphson (NR) algorithm and the EM algorithm could be applied. The EM algorithm, however, is recommended due to its ease of implementation and lower computational overhead. / Graduate / hangli@uvic.ca

This thesis focuses on the Binary Integer Modulo-Division Algorithm that is essential for the permutation process in Sunar-Koc ONB Type II Multiplier and also for other general purposes. This thesis explains the new algorithm developed based on the systolic array architecture which gives a systematic approach to the iterative process for the Modulo-Division. The scheduling and projection timing functions are proposed for the processor array allocation and the matlab code has been implemented to verify the efficiency of the algorithm. The thesis also explores the possibility of word based algorithm for design optimisation. / Graduate / 0544 / 0984 / m.shubha8@gmail.com

The goal of a parallel algorithm is to solve a single problem using multiple processors working together and to do so in an efficient manner. In this regard, there is a need to categorize strategies in order to solve broad classes of problems with similar structures and requirements. In this dissertation, two parallel algorithm design strategies are considered: linked list ranking and parentheses matching.

In this thesis, we describe Schensted's algorithm for finding the length of a longest increasing subsequence of a finite sequence. Schensted's algorithm also constructs a bijection between permutations of the first N natural numbers and standard bitableaux of size N. We also describe the Hillman-Grassl algorithm which constructs a bijection between reverse plane partitions and the solutions in natural numbers of a linear equation involving hook lengths. Pascal programs and sample output for both algorithms appear in the appendix. In addition, we describe the operations on standard bitableaux corresponding to the operations of inverting and reversing permutations. Finally, we show that these operations generate the dihedral group D_4

Modern society relies heavily on communication networks that in turn rely on both wired and wireless infrastructure. This work pertains to scenarios where a group of people or robots need to communicate in an environment where there is no preexisting communications infrastructure. These include sites of emergencies and disasters (e.g., inside burning buildings, search and rescue operations) and unexplored areas on Earth and other planets. Wireless ad hoc or mesh networks offer the ability to keep such entities connected, but they falter when any single entity wishes to leave the developed coverage area. Utilizing mobile repeater nodes can help, but is costly and complicated. By eliminating the need for repeater nodes to traverse the environment, their size and cost can be vastly reduced. This work explores the use of static "breadcrumb" repeater nodes to increase the reach of such a network. Determining when and where to place a static repeater node can be difficult in an environment where radio propagation characteristics are unknown. In this work, several algorithms for node placement are compared under the constraint that placement of a static repeater node should not dictate the entity's movement. The algorithms investigated range from calculating rolling averages to modeling channel parameters on-the-fly. The placement algorithms were configured to run in real-time on TP-Link MR-3040 portable WiFi routers and the approach is demonstrated in an outdoor uncharacterized environment.

The discovery of transcription factor binding site (TFBS) motifs remains an important and challenging problem in computational biology. This thesis presents MITSU, a novel algorithm for TFBS motif discovery which exploits stochastic methods as a means of both overcoming optimality limitations in current algorithms and as a framework for incorporating relevant prior knowledge in order to improve results. The current state of the TFBS motif discovery field is surveyed, with a focus on probabilistic algorithms that typically take the promoter regions of coregulated genes as input. A case is made for an approach based on the stochastic Expectation-Maximisation (sEM) algorithm; its position amongst existing probabilistic algorithms for motif discovery is shown. The algorithm developed in this thesis is unique amongst existing motif discovery algorithms in that it combines the sEM algorithm with a derived data set which leads to an improved approximation to the likelihood function. This likelihood function is unconstrained with regard to the distribution of motif occurrences within the input dataset. MITSU also incorporates a novel heuristic to automatically determine TFBS motif width. This heuristic, known as MCOIN, is shown to outperform current methods for determining motif width. MITSU is implemented in Java and an executable is available for download. MITSU is evaluated quantitatively using realistic synthetic data and several collections of previously characterised prokaryotic TFBS motifs. The evaluation demonstrates that MITSU improves on a deterministic EM-based motif discovery algorithm and an alternative sEM-based algorithm, in terms of previously established metrics. The ability of the sEM algorithm to escape stable fixed points of the EM algorithm, which trap deterministic motif discovery algorithms and the ability of MITSU to discover multiple motif occurrences within a single input sequence are also demonstrated. MITSU is validated using previously characterised Alphaproteobacterial motifs, before being applied to motif discovery in uncharacterised Alphaproteobacterial data. A number of novel results from this analysis are presented and motivate two extensions of MITSU: a strategy for the discovery of multiple different motifs within a single dataset and a higher order Markov background model. The effects of incorporating these extensions within MITSU are evaluated quantitatively using previously characterised prokaryotic TFBS motifs and demonstrated using Alphaproteobacterial motifs. Finally, an information-theoretic measure of motif palindromicity is presented and its advantages over existing approaches for discovering palindromic motifs discussed.