No description available.

No description available.

<p> Identifying motifs that are "close" to one or more substrings in each sequence in a given set of sequences and hence characterize that set is an important problem in computational biology. The target motif identification problem requires motifs that characterize one given set of sequences but are far from every substring in another given set of sequences. This problem is N P-hard and hence is unlikely to have efficient optimal solution algorithms. In this thesis, we propose a set of modifications to one of the most popular stochastic heuristics for finding motifs, Gibbs Sampling [LAB+93], which allow this heuristic to detect target motifs. We also present the results of four simulation studies and tests on real protein datasets which suggest that these modified heuristics are very good at (and are even, in some cases, necessary for) detecting target motifs.</p> / Thesis / Master of Science (MSc)

No / The effective maintenance scheduling of power system generators is very important for the economical and reliable operation of a power system. This represents a tough scheduling problem which continues to present a challenge for efficient optimization solution techniques. This paper presents the application of metaheuristic approaches, such as a genetic algorithm (GA), simulated annealing (SA) and their hybrid for generator maintenance scheduling (GMS) in power systems using an integer representation. This paper mainly focuses on the application of GA/SA and GA/SA/heuristic hybrid approaches. GA/SA hybrid uses the probabilistic acceptance criterion of SA within the GA framework. GA/SA/heuristic hybrid combines heuristic approaches within the GA/SA hybrid to seed the initial population. A case study is formulated in this paper as an integer programming problem using a reliability-based objective function and typical problem constraints. The implementation and performance of the metaheuristic approaches and their hybrid for the test case study are discussed. The results obtained are promising and show that the hybrid approaches are less sensitive to the variations of technique parameters and offer an effective alternative for solving the generator maintenance scheduling problem.

Rail and truck freight transportation systems provide vital logistics services today. Rail systems are generally used to transport heavy and bulky commodities over long distances, while trucks tend to provide fast and flexible service for small and high-value products. In this dissertation, we study two different distribution planning problems that arise in rail and truck transportation systems. In the railroad industry, shipments are often grouped together to form a block to reduce the impact of reclassification at train yards. We consider the time and capacity constrained routing (TCCR) problem, which assigns shipments to blocks and train-runs to minimize overall transportation costs, while considering the train capacities and shipment due dates. Two mathematical formulations are developed, including an arc-based formulation and a path-based formulation. To solve the problem efficiently, two solution approaches are proposed. The sequential algorithm assigns shipments in order of priority while considering the remaining train capacities and due dates. The bump-shipment algorithm initially schedules shipments simultaneously and then reschedules the shipments that exceed the train capacity. The algorithms are evaluated using a data set from a major U.S. railroad with approximately 500,000 shipments. Industry-sized problems are solved within a few minutes of computational time by both the sequential and bump-shipment algorithms, and transportation costs are reduced by 6% compared to the currently used trip plans. For truck transportation systems, trailer fleet planning (TFP) is an important issue to improve services and reduce costs. In this problem, we consider the quantities and types of trailers to purchase, rent, or relocate among depots to meet time varying demands. Mixed-integer programming models are developed for both homogeneous and heterogeneous TFP problems. The objective is to minimize the total fleet investment costs and the distribution costs across multiple depots and multiple time periods. For homogeneous TFP problem, a two-phase solution approach is proposed. Phase I concentrates on distribution costs and determines the suggested fleet size. A sweep-based routing heuristic is applied to generate candidate routes of good quality. Then a reduced mathematical model selects routes for meeting customer demands and determines the preferred fleet size. Phase II provides trailer purchase, relocation, and rental decisions based on the results of Phase I and relevant cost information. This decomposition approach removes the interactions between depots and periods, which greatly reduces the complexity of the integrated optimization model. For the heterogeneous TFP problem, trailers with different capacities, costs, and features are considered. The two-phase approach, developed for the homogeneous TFP, is modified. A rolling horizon scheme is applied in Phase I to consider the trailer allocations in previous periods when determining the fleet composition for the current period. Additionally, the sweep-based routing heuristic is also extended to capture the characteristics of continuous delivery practice where trailers are allowed to refill products at satellite facilities. This heuristic generates routes for each trailer type so that the customer-trailer restrictions are accommodated. The numerical studies, conducted using a data set with three depots and more than 400 customers, demonstrate the effectiveness of the two-phase approaches. Compared to the integrated optimization models, the two-phase approaches obtain quality solutions within a reasonable computational time and demonstrate robust performance as the problem sizes increase. Based on these results, a leading industrial gas provider is currently integrating the proposed solution approaches as part of their worldwide distribution planning software. / Ph. D.

The representation of information in modern database systems is complicated by the need to represent relationships among pieces of information. A natural representation for such databases is the information graph that associates the pieces of information with vertices in the graph and the relationships with edges. Five characteristics of this representation are noteworthy. First, each vertex has a size (in bytes) sufficient to store its corresponding piece of information. Second, retrieval in an information graph may follow a number of patterns; in particular, retrieval of adjacent vertices via edge traversals must be efficient. Third, in many applications such as a dictionary or bibliographic archive, the information graph may be considered static. Fourth, the ultimate home for an information graph is likely to be a roughly linear medium such as a magnetic disk or CD-ROM. Finally, information graphs are quite large-hundreds of thousands of vertices and tens of megabytes in size. / Master of Science

This thesis is concerned with the development of heuristic algorithms for the popular Quadratic Assignment Problem (QAP) which finds a wide variety of applications in various fields. This discrete optimization problem, which seeks the placement of m facilities on m locations in order to minimize a quadratic interactive cost, is well known to be NP-hard and turns out to be computationally intractable for even moderately sized problems. Hence, problems involving more than 12-15 facilities usually need to be analysed by approximate solution procedures. The more successful heuristic procedures which exist for problem QAP are computationally intensive, some of these resulting from a premature termination of exact solution procedures. The motivation here is to develop a polynomial time heuristic which is effective with respect to the quality of solutions obtained, while at the same time not being computationally very expensive. The method proposed herein is flexible in that one can operate it to suitably trade solution quality against effort as desired, and is portable in that the modules used as building blocks can be employed in conjunction with other heuristics as well. Computational experience on test problems found in the literature is provided to evaluate the worth of this method. / M.S.

Developing economical yet effective methods of incorporating usability engineering as an integral part of software engineering is a primary focus of human-computer interaction (HCI) research. However, much HCI research has focused primarily on inspecting and evaluating applications supporting command-line or graphical user interface (GUI) interaction styles. With the dramatic increase in virtual environment (VE) research in recent years, the HCI community is beginning to place an added emphasis on creating methodologies to ensure usability in VE development. While the demand for VE-specific usability engineering methods and criteria is dire as the amount of money invested by military, government, commercial, and industrial organizations continues to grow, widely accepted methodologies for assessing VE usability are, at this point in time, minimal. There has been a recent increase in research discussing the need of VE-specific usability engineering methodologies, but few research projects have concentrated their efforts on providing such methodologies. Therefore, application developers attempting to apply a user-centered design approach in constructing VEs must often perform largely ad-hoc assessments or in-house evaluations using existing non-VE-specific usability engineering methodologies. The primary focus of this research was to develop a method to guide usability engineering of VEs. The strategy used to develop this usability evaluation method was to modify existing usability evaluation methodologies to support VE development by leveraging the results of previous VE usability research performed at Virginia Tech and elsewhere. The result was a VE-specific usability evaluation methodology that encompasses two existing usability assessment techniques: usability inspections and formative evaluations. We applied this methodology to Crumbs, an immersive visualization VE developed at the National Center for Supercomputing Applications (NCSA). A multi-dimensional framework of VE usability characteristics was a topic of research at Virginia Tech. This framework provided the backbone for VE-specific modifications to the existing usability evaluation techniques proposed in this research. Framework design guidelines permitted usability specialists to perform guidelines-based usability inspections of Crumbs. Results gathered from the guidelines-based usability inspections were used not only to redesign the Crumbs user interface but also drive creation of a formative evaluation plan. Application of the methodology not only uncovered usability issues with Crumbs, but also provided invaluable information regarding the effectiveness of the methodology itself. We conclude this thesis by describing a usability evaluation methodology, called the Modified Concept Book Usability Evaluation Methodology, proposed to improve the usability evaluation methodology performed on Crumbs and other VEs. Our methodology was adapted from an established methodology for performing content analysis on a large volume of qualitative data. Because the realm of VEs is so vast and diverse in application domains and devices, we do not claim that our methodology supports an exhaustive usability evaluation of all VEs. However, the proposed technique is a first attempt at modifying existing usability evaluation methods, and therefore can be used as a launching pad for methodologies to evaluate other aspects of specific VE applications. / Master of Science

The author of this thesis uses her own personal experience of the Old Fire that took place in the fall of 2003 in San Bernardino County to teach children ecological concepts, especially fire ecology using an art oriented methodology. Thus, heArts for the Forest was born incorporating ash from the burned forest into pottery and other art pieces to sell and raise money for reforestation efforts in the San Bernardino mountains.

The aim of my thesis is to find the shortest total route to export trash at the bus stops for several variants and also determine the suitability of approximate algorithms. The tasks are solved by insertion heuristic, closest neighbor heuristic and optimization. The optimal solution is gained by using the system LINGO and by using optimization solver CPLEX. In my thesis I first describe the problem of maintenance of bus stops. Following chapter is devoted to the role of routing problems, its classifications, problems to solve, possibilities of solution. The used methods are Traveling Salesman Problem with one or multiple vehicles available in a unique depot and Vehicle Routing Problem with one or multiple vehicles available in a unique depot or multiple depots. The last chapter describes and compare the results of the solution of insertion heuristic, closest neighbor heuristic and optimization for problem of replacement of bus schedules and of maintenance of bus stops.