Abstract The tremendous progress in all aspects of signal processing technology has naturally been accompanied by a corresponding development of arithmetic techniques to provide high-speed operations at reasonable complexity. In the past, many architectural design efforts have focused on maximizing performance for frequently executed simple arithmetic operations such as addition and multiplication while left other rarely used operations ignored. In this dissertation, we firstly propose two design approaches for 64-b carry-lookahead adders (CLA) using a two-phase clocking dynamic CMOS logic since fast adders are the key elements in many digital circuits. Secondly, we place emphasis on the inner product operation since it is one of the most frequently used mathematical operations in the computation of digital neural networks. A ratioed 3-2 compressor is also presented to resolve several physical design problems that are not fully considered or implemented in previous research works. Finally we propose several fast 64b/32b integer dividers because the integer division is unavoidable in many important signal-processing applications.

Thesis (Ph. D.)--University of Washington, 2002. / Vita. Includes bibliographical references (leaves 71-75).

Integer multicommodity network flow (MCNF) models have applications in various areas like logistics, freight transportation, telecommunication and manufacturing. In this thesis we study an extension of the integer MCNF problem (MCNF-FIFO) where commodities are handled (processed) in a first-in-first-out (FIFO) order at each transshipment location and resource capacities are shared across arcs in the network. The objective of the MCNF-FIFO model is to find feasible routes for all commodities from their origins to destinations while minimizing the total transportation and holding cost or the sum of delivery times. We formulate the MCNF-FIFO problem on a time-space network and develop three different integer-programming (IP) formulations for the FIFO constraints, and two IP formulations for the flow conservations requirements. Since these formulations have a very large number of variables and constraints, we develop various algorithmic strategies to obtain good quality solutions quickly. The first strategy is to reduce the problem size by using properties of the optimal solution. We develop novel problem reduction and decomposition techniques that eliminate variables and constraints, and decompose the problem into smaller components. To further reduce the problem size, we classify the FIFO constraints into different categories by utilizing the relationships between different commodities, and provide specialized formulations for each of these categories so as to reduce the number of FIFO constraints significantly. The second strategy is to develop heuristic algorithms that provide near-optimal solutions to the MCNF-FIFO problem. Our first algorithm is an optimization-based heuristic that solves a relaxed MCNF-FIFO model with a limited number of FIFO constraints. Then, it removes the remaining infeasibilities in the solution of the relaxed MCNF-FIFO model using a repair heuristic to obtain a feasible solution. We develop two other heuristic algorithms that are stand-alone construction heuristics that build a feasible solution from scratch. To assess the effectiveness of the modeling and algorithmic enhancements, we implement the methods and apply them to three real life test instances. Our tests show that the problem reduction techniques are very effective in reducing the solution times. Among the heuristic algorithms, the optimization-based heuristic performs the best to find near-optimal solutions quickly. / text

Not available / text

We consider a scheduling problem where each job requires multiple classes of resources, which we refer to as the multiple resource constrained scheduling problem(MRCSP). Potential applications include team scheduling problems that arise in service industries such as consulting and operating room scheduling. We focus on two general cases of the problem. The first case considers uncertainty of processing times, due dates, and resource availabilities consumption, which we denote as the stochastic MRCSP with uncertain parameters (SMRCSP-U). The second case considers uncertainty in the number of jobs to schedule, which arises in consulting and defense contracting when companies bid on future contracts but may or may not win the bid. We call this problem the stochastic MRCSP with job bidding (SMRCSP-JB).We first provide formulations of each problem under the framework of two-stage stochastic programming with recourse. We then develop solution methodologies for both problems. For the SMRCSP-U, we develop an exact solution method based on the L-shaped method for problems with a moderate number of scenarios. Several algorithmic enhancements are added to improve efficiency. Then, we embed the L-shaped method within a sampling-based solution method for problems with a large number of scenarios. We modify a sequential sampling procedure to allowfor approximate solution of integer programs and prove desired properties. The sampling-based method is applicable to two-stage stochastic integer programs with integer first-stage variables. Finally, we compare the solution methodologies on a set of test problems.For SMRCSP-JB, we utilize the disjunctive decomposition (D2 ) algorithm for stochastic integer programs with mixed-binary subproblems. We develop several enhancements to the D2 algorithm. First, we explore the use of a cut generation problem restricted to a subspace of the variables, which yields significant computational savings. Then, we examine generating alternative disjunctive cuts based on the generalized upper bound (GUB) constraints that appear in the second-stage of the SMRCSP-JB. We establish convergence of all D2 variants and present computational results on a set of instances of SMRCSP-JB.

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved.The primary contributions of this dissertation are as follows. We formulate and discuss the modeling of this filter placement problem as a mixed-integer program. We then show the sensitivity of the optimal number of deployed filters as the required level of security changes, and demonstrate that current vertex cover-based heuristics are ineffective for problems with relaxed security levels. We identify a set of special network topologies on which the filter placement problem is solvable in polynomial time, focusing our attention on the development of a dynamic programming algorithm for solving this problem on tree networks. These results can then in turn be used to derive valid inequalities for an integer programming model of the filter placement problem. Finally, we present heuristic algorithms based on the insights gained from our overall study for solving the problem, and evaluate their performance against the optimal solution provided by our integer programming model.

No description available.

We propose a resource allocation model for the management of the fund for the screening and treatment of women infected by Chlamydia trachomatis and Neisseria gonorrhoeae. The goal is to maximize the number of infected women cured of Chlamydia trachomatis and Neisseria gonorrhoeae infections. The population going for screening is divided into groups by ages and races. The group number is dynamic. Dierent groups have dierent infection rates. There are four possible test assays and four possible treatments. We employed a two-phase algorithm to solve the problem. The first phase is small so an exhaustive method is applied, while the second phase is transformed to a knapsack problem and a dynamic programming method is applied.

In this thesis, we develop integer programming models which find the optimal part-machine family solutions, that disaggregate a factory process at the lowest cost. The groupings created using the methods presented in this thesis can then act as the basis for the application of Group Technology, which include machine placement, job scheduling, and part routing. Four exact 0−1 Linear Programming techniques are developed and presented. The first 0 − 1 Linear Programming technique only focuses on part subcontracting as a means to disaggregate, and the second only focuses on machine duplication to disaggregate. The final two methods both yield part-machine family disaggregation through simultaneous part subcontracting and machine duplication. Once these methods are applied to example problems, the results provide the exact solutions, which have not been found in previous work. / NSERC Discovery Grant

No description available.