A flexible workforce or a versatile machine is employed to perform various types of operations. Often these resources are associated with setups. Whenever a worker or machine switches from processing one type of operation to another a setup time may be required although several operations of a same type can be processed in succession after a single setup. The presence of setups gives rise to the problem of choosing batch sizes that are neither too large nor too small. In the last one and a half decade, many researchers have addressed the problem of scheduling with batching. A majority of articles assumes that there is only one type of scarce resource, which is typically machine. Often there can be two scarce resources such as a worker and a machine or a machine and a tool. We propose a resource constrained scheduling model with a single operator and two or more machines. Whenever the operator changes machine, a setup time is required that may be sequence dependent or sequence independent. We consider the two cases of an open shop and a flow shop. In the open shop case, the order in which a job visits the machines is unrestricted. In the flow shop case, every job must visit the machines in the same order. We consider various scheduling objectives. For variable number of machines, many cases are intractable. We discuss some dominance properties that narrow down the search for an optimal schedule. We present a dynamic programming approach which solves a large number of cases. The running time of the dynamic program is polynomial for a fixed number of machines. For the case of two machines, we show that the dominance properties have a nice interpretation. We develop some algorithms and justify their use by establishing running times, comparing the running times with those of the existing algorithms, and testing the performance of the algorithms.

This dissertation explores approaches to the satisfiability problem, focusing on local search methods. The research endeavours to better understand how and why some local search methods are effective. At the root of this understanding are a set of metrics that characterize the behaviour of local search methods. Based on this understanding, two new local search methods are proposed and tested, the first, SDF, demonstrating the value of the insights drawn from the metrics, and the second, ESG, achieving state-of-the-art performance and generalizing the approach to arbitrary 0-1 integer linear programming problems. This generality is demonstrated by applying ESG to combinatorial auction winner determination. Further augmentations to local search are proposed and examined, exploring hybrids that incorporate aspects of backtrack search methods.

Channel sharing is known as a unique solution to satisfy the increasing demand for the spectral-efficient communication. In the channel sharing technique, several users concurrently communicate through a shared wireless medium. In such a scheme, the interference of users over each other is the main source of impairment. The task of performance evaluation and signaling design in the presence of such interference is known as a challenging problem. In this thesis, a system including $n$ parallel interfering AWGN transmission paths is considered, where the power of the transmitters are subject to some upper-bounds. For such a system, we obtain a closed form for the boundaries of the rate region based on the Perron-Frobenius eigenvalue of some non-negative matrices. While the boundary of the rate region for the case of unconstrained power is a well-established result, this is the first result for the case of constrained power. This result is utilized to develop an efficient user removal algorithm for congested networks. In these networks, it may not be possible for all users to attain a required Quality of Service (QoS). In this case, the solution is to remove some of the users from the set of active ones. The problem of finding the set of removed users with the minimum cardinality is claimed to be an NP-complete problem. In this thesis, a novel sub-optimal removal algorithm is proposed, which relies on the derived boundary of the rate region in the first part of the thesis. Simulation results show that the proposed algorithm outperforms other known schemes.

In drug discovery, thousands of compounds are assayed to detect activity against a biological target. The goal of drug discovery is to identify compounds that are active against the target (e.g. inhibit a virus). Statistical learning in drug discovery seeks to build a model that uses descriptors characterizing molecular structure to predict biological activity. However, the characteristics of drug discovery data can make it difficult to model the relationship between molecular descriptors and biological activity. Among these characteristics are the rarity of active compounds, the large volume of compounds tested by high-throughput screening, and the complexity of molecular structure and its relationship to activity. This thesis focuses on the design of statistical learning algorithms/models and their applications to drug discovery. The two main parts of the thesis are: an algorithm-based statistical method and a more formal model-based approach. Both approaches can facilitate and accelerate the process of developing new drugs. A unifying theme is the use of unsupervised methods as components of supervised learning algorithms/models. In the first part of the thesis, we explore a sequential screening approach, Cluster Structure-Activity Relationship Analysis (CSARA). Sequential screening integrates High Throughput Screening with mathematical modeling to sequentially select the best compounds. CSARA is a cluster-based and algorithm driven method. To gain further insight into this method, we use three carefully designed experiments to compare predictive accuracy with Recursive Partitioning, a popular structureactivity relationship analysis method. The experiments show that CSARA outperforms Recursive Partitioning. Comparisons include problems with many descriptor sets and situations in which many descriptors are not important for activity. In the second part of the thesis, we propose and develop constrained mixture discriminant analysis (CMDA), a model-based method. The main idea of CMDA is to model the distribution of the observations given the class label (e.g. active or inactive class) as a constrained mixture distribution, and then use Bayes’ rule to predict the probability of being active for each observation in the testing set. Constraints are used to deal with the otherwise explosive growth of the number of parameters with increasing dimensionality. CMDA is designed to solve several challenges in modeling drug data sets, such as multiple mechanisms, the rare target problem (i.e. imbalanced classes), and the identification of relevant subspaces of descriptors (i.e. variable selection). We focus on the CMDA1 model, in which univariate densities form the building blocks of the mixture components. Due to the unboundedness of the CMDA1 log likelihood function, it is easy for the EM algorithm to converge to degenerate solutions. A special Multi-Step EM algorithm is therefore developed and explored via several experimental comparisons. Using the multi-step EM algorithm, the CMDA1 model is compared to model-based clustering discriminant analysis (MclustDA). The CMDA1 model is either superior to or competitive with the MclustDA model, depending on which model generates the data. The CMDA1 model has better performance than the MclustDA model when the data are high-dimensional and unbalanced, an essential feature of the drug discovery problem! An alternate approach to the problem of degeneracy is penalized estimation. By introducing a group of simple penalty functions, we consider penalized maximum likelihood estimation of the CMDA1 and CMDA2 models. This strategy improves the convergence of the conventional EM algorithm, and helps avoid degenerate solutions. Extending techniques from Chen et al. (2007), we prove that the PMLE’s of the two-dimensional CMDA1 model can be asymptotically consistent.

As the next evolutionary step in digital communication systems, mobile ad hoc networks (MANETs) and their specialization like wireless sensor networks (WSNs) have been attracting much interest in both research and industry communities. In MANETs, network nodes can come together and form a network without depending on any pre-existing infrastructure and human intervention. Unfortunately, the salient characteristics of MANETs, in particular the absence of infrastructure and the constrained resources of mobile devices, present enormous challenges when designing security mechanisms in this environment. Without necessary measures, wireless communications are easy to be intercepted and activities of users can be easily traced. This thesis presents our solutions for two important aspects of securing MANETs, namely efficient key management protocols and fast implementations of cryptographic primitives on constrained devices. Due to the tight cost and constrained resources of high-volume mobile devices used in MANETs, it is desirable to employ lightweight and specialized cryptographic primitives for many security applications. Motivated by the design of the well-known Enigma machine, we present a novel ultra-lightweight cryptographic algorithm, referred to as Hummingbird, for resource-constrained devices. Hummingbird can provide the designed security with small block size and is resistant to the most common attacks such as linear and differential cryptanalysis. Furthermore, we also present efficient software implementations of Hummingbird on 4-, 8- and 16-bit microcontrollers from Atmel and Texas Instruments as well as efficient hardware implementations on the low-cost field programmable gate arrays (FPGAs) from Xilinx, respectively. Our experimental results show that after a system initialization phase Hummingbird can achieve up to 147 and 4.7 times faster throughput for a size-optimized and a speed-optimized software implementation, respectively, when compared to the state-of-the-art ultra-lightweight block cipher PRESENT on the similar platforms. In addition, the speed optimized Hummingbird encryption core can achieve a throughput of 160.4 Mbps and the area optimized encryption core only occupies 253 slices on a Spartan-3 XC3S200 FPGA device. Bilinear pairings on the Jacobians of (hyper-)elliptic curves have received considerable attention as a building block for constructing cryptographic schemes in MANETs with new and novel properties. Motivated by the work of Scott, we investigate how to use efficiently computable automorphisms to speed up pairing computations on two families of non-supersingular genus 2 hyperelliptic curves over prime fields. Our findings lead to new variants of Miller's algorithm in which the length of the main loop can be up to 4 times shorter than that of the original Miller's algorithm in the best case. We also generalize Chatterjee et al.'s idea of encapsulating the computation of the line function with the group operations to genus 2 hyperelliptic curves, and derive new explicit formulae for the group operations in projective and new coordinates in the context of pairing computations. Efficient software implementation of computing the Tate pairing on both a supersingular and a non-supersingular genus 2 curve with the same embedding degree of k = 4 is investigated. Combining the new algorithm with known optimization techniques, we show that pairing computations on non-supersingular genus 2 curves over prime fields use up to 55.8% fewer field operations and run about 10% faster than supersingular genus 2 curves for the same security level. As an important part of a key management mechanism, efficient key revocation protocol, which revokes the cryptographic keys of malicious nodes and isolates them from the network, is crucial for the security and robustness of MANETs. We propose a novel self-organized key revocation scheme for MANETs based on the Dirichlet multinomial model and identity-based cryptography. Firmly rooted in statistics, our key revocation scheme provides a theoretically sound basis for nodes analyzing and predicting peers' behavior based on their own observations and other nodes' reports. Considering the difference of malicious behaviors, we proposed to classify the nodes' behavior into three categories, namely good behavior, suspicious behavior and malicious behavior. Each node in the network keeps track of three categories of behavior and updates its knowledge about other nodes' behavior with 3-dimension Dirichlet distribution. Based on its own analysis, each node is able to protect itself from malicious attacks by either revoking the keys of the nodes with malicious behavior or ceasing the communication with the nodes showing suspicious behavior for some time. The attack-resistant properties of the resulting scheme against false accusation attacks launched by independent and collusive adversaries are also analyzed through extensive simulations. In WSNs, broadcast authentication is a crucial security mechanism that allows a multitude of legitimate users to join in and disseminate messages into the networks in a dynamic and authenticated way. During the past few years, several public-key based multi-user broadcast authentication schemes have been proposed in the literature to achieve immediate authentication and to address the security vulnerability intrinsic to μTESLA-like schemes. Unfortunately, the relatively slow signature verification in signature-based broadcast authentication has also incurred a series of problems such as high energy consumption and long verification delay. We propose an efficient technique to accelerate the signature verification in WSNs through the cooperation among sensor nodes. By allowing some sensor nodes to release the intermediate computation results to their neighbors during the signature verification, a large number of sensor nodes can accelerate their signature verification process significantly. When applying our faster signature verification technique to the broadcast authentication in a 4×4 grid-based WSN, a quantitative performance analysis shows that our scheme needs 17.7%~34.5% less energy and runs about 50% faster than the traditional signature verification method.

The major goals of this work were to: develop a new methodology for the preparation of site-isolated catalytic sites on a silica surface, prepare the first truly single-site supported metallocene/CGC polymerization catalyst, and develop structure-reactivity relationships for these new systems. To synthesize these novel catalysts, the approach taken was to develop a protocol which allows for the synthesis of an aminosilica material with isolated, uniform amine sites. This patterned aminosilica was then used as a scaffold to support a constrained geometry catalyst. These functionalizations occurred at essentially a quantitative level, in stark contrast to previous literature reports. The patterned catalysts were evaluated in the polymerization of ethylene and compared to densely loaded literature materials. Overall, it was found the patterned materials were 5-10 times more active than traditional immobilized CGC catalysts. The patterned catalysts were also found to be effective catalysts for the copolymerization of norbornenes (including functionalized norbornenes) and ethylene, the first reported use of a tethered CGC for the production of ethylene-norbornene copolymers. The control materials were inactive in these polymerizations, providing further evidence that the patterning protocol allows for the synthesis of unique highly active, isolated catalytic sites. Various structural components of the immobilized CGC developed in this work were tested for their impact on catalyst synthesis and reactivity in ethylene polymerizations. The results showed the patterned materials in general behaved according to the trends seen in homogeneous CGC polymerizations. These results, while congruent with similar homogeneous CGC studies, are in direct conflict with previous work on supported CGCs reported in the literature. This discrepancy is likely the result of the difference between the isolated, possibly single-site patterned catalysts developed in the course of this work and the multi-sited catalysts prepared by traditional supporting protocols. This also further illustrates the difficulty in developing structure-reactivity relationships when ill-defined solid catalysts are used.

In the thesis, we propose a dual-mode message delivery system with mechanisms of time constrained paging and multi-class message. The pairing decision depends on the effective pairing time defined by the system when a bluetooth device comes into service range. Within the constrained pairing time, central server can deliver a message to the bluetooth device directly without re-pairing. Otherwise, the bluetooth device has to be paired with an intermediate node before it can receive a message. In addition, we store the number of times that bluetooth devices can move into the service range into a data base in order to send multi-class messages to these bluetooth devices. To demonstrate the proposed schemes, we implement a central server on Linux system and intermediate nodes on Window Mobile platform. We also design control packets associated with their message formats. Control messages can be exchanged between the central server and the intermediate node by the control packets, and data messages can be transmitted in a heterogeneous network, consisting of bluetooth and Wi-Fi. Finally, we measured the time saved without using pairing procedure and also verified that the system can dynamically adjust the classes of messages according to the number of times that bluetooth devices enter to the service range.

Unmanned aerial vehicles (UAVs) are becoming increasingly popular for surveillance in civil and military applications. Vehicles built for this purpose vary in their sensing capabilities, speed and maneuverability. It is therefore natural to assume that a team of UAVs given the mission of visiting a set of targets would include vehicles with differing capabilities. This paper addresses the problem of assigning each vehicle a sequence of targets to visit such that the mission is completed with the least "cost" possible given that the team of vehicles is heterogeneous. In order to simplify the problem the capabilities of each vehicle are modeled as cost to travel from one target to another. In other words, if a vehicle is particularly suited to visit a certain target, the cost for that vehicle to visit that target is low compared to the other vehicles in the team. After applying this simplification, the problem can be posed as an instance of the combinatorial problem called the Heterogeneous Travelling Salesman Problem (HTSP). This paper presents a transformation of a Heterogenous, Multiple Depot, Multiple Traveling Salesman Problem (HMDMTSP) into a single, Asymmetric, Traveling Salesman Problem (ATSP). As a result, algorithms available for the single salesman problem can be used to solve the HMDMTSP. To show the effectiveness of the transformation, the well known Lin-Kernighan-Helsgaun heuristic was applied to the transformed ATSP. Computational results show that good quality solutions can be obtained for the HMDMTSP relatively fast. Additional complications to the sequencing problem come in the form of precedence constraints which prescribe a partial order in which nodes must be visited. In this context the sequencing problem was studied seperately using the Linear Program (LP) relaxation of a Mixed Integer Linear Program (MILP) formulation of the combinatorial problem known as the "Precedence Constrained Asymmetric Travelling Salesman Problem" (PCATSP).

Utilization of methylaluminoxane (MAO) activated metallocene and constrained geometry (CGC) olefin polymerization catalysts containing fluorenyl or octamethyloctahydrodibenzofluorenyl (Oct) moieties has yielded three series of syndiotactic copolymers of propylene with higher a-olefins. The melting temperatures of these polymers were analyzed, and found to correspond directly with the mole percent incorporation of comonomer, as well as with the frequency of stereoerrors in the polymers. Further analysis indicated that rmrr stereoerrors, a result of site epimerization, occur in close proximity to the incorporated comonomers. The MAO-activated fluorenyl/Oct-containing metallocene and CGC catalysts were further utilized to produce syndiotactic samples of poly(1-butene) (s-PB) and poly(1- pentene) (s-PPe). The syndiotacticity of the samples was quantified by 13C NMR and the melting temperatures determined by DSC. The samples of s-PB and s-PPe produced by Me2Si( h1-C29H36)( h1-N-tBu)ZrCl2·OEt2 (Oct-CGC) were found to melt at higher temperatures (55.9 and 43.1 °C, respectively) than any previously reported samples. The MAO-activated Oct-CGC was also used to produce polyethylene samples at a variety of polymerization temperatures and pressures. All of the samples were found to contain an unprecedented degree of branching (13-65 total branches per 1000 carbon atoms) for an early transition metal single-site catalyst. The branches were found to be almost exclusively of two or greater than five carbon atoms in length, and the levels of the longer branches could be controlled by varying the polymerization conditions. The number of ethyl branches was roughly 5 per 1000 carbon atoms for all samples. Finally, a binary catalyst system comprising the Oct-CGC and a chromium-based ethylene trimerization catalyst, ((tBuSCH2CH2)2NH)CrCl3, was developed. This MAOactivated catalyst system could be tuned to produce polyethylene samples with 17-49 total branches per 1000 carbon atoms. Between 4 and 16 of these branches were found to arise from incorporation of 1-hexene produced by the chromium oligomerization catalyst. Adjusting the ratios of oligomerization catalyst, polymerization catalyst, and activator was found to allow rational control over the branch content of the polymers. The branching levels could also be varied by altering the time between injection of the oligomerization and polymerization catalysts into the system.

The cytoskeleton is a diverse, multi-protein framework that plays a fundamental role in many cellular activities including mitosis, cell division, intracellular transport, cell motility, muscle contraction, and the regulation of cell polarity and organization. Furthermore, cytoskeletal filaments have been implicated in the pathogenesis of a wide variety of diseases including cancer, blood disease, cardiovascular disease, inflammatory disease, neurodegenerative disease, and problems with skin, nail, cornea, hair, liver and colon. Increasing evidence suggests that the distribution and organization of the cytoskeleton in living cells are affected by mechanical stresses and the cytoskeleton determines cell stiffness. We developed a fully nonlinear, constrained mixture model for adherent cells that allows one to account separately for the contributions of the primary structural constituents of the cytoskeleton and extended a prior solution from the finite elasticity literature for use in a sub-class of atomic force microscopy (AFM) studies of cell mechanics. The model showed that the degree of substrate stretch and the geometry of the AFM tip dramatically affect the measured cell stiffness. Consistent with previous studies, the model showed that disruption of the actin filaments can reduce the stiffness substantially, whereas there can be little contribution to the overall cell stiffness by the microtubules or intermediate filaments. To investigate the effect of mechanical stretching on cytoskeletal remodeling and cell stiffness, we developed a simple cell-stretching device that can be combined with an AFM and confocal microscopy. Results demonstrate that cyclic stretching significantly and rapidly alters both cell stiffness and focal adhesion associated vinculin and paxillin, suggesting that focal adhesion remodeling plays a critical role in cell stiffness by recruiting and anchoring F-actin. Finally, we estimated cytoskeletal remodeling by synthesizing data on stretch-induced dynamic changes in cell stiffness and focal adhesion area using constrained mixture approach. Results suggest that the acute increase in stiffness in response to an increased cyclic stretch was probably due to an increased stretch of the original filaments whereas the subsequent decrease back towards normalcy was consistent with a replacement of the highly stretched original filaments with less stretched new filaments.