We consider several related problems arising in geometric graphs. In particular, we investigate the computational complexity and approximability properties of several optimization problems in unit ball graphs and develop algorithms to find exact and approximate solutions. In addition, we establish complexity-based theoretical justifications for several greedy heuristics. Unit ball graphs, which are defined in the three dimensional Euclidian space, have several application areas such as computational geometry, facility location and, particularly, wireless communication networks. Efficient operation of wireless networks involves several decision problems that can be reduced to well known optimization problems in graph theory. For instance, the notion of a \virtual backbone" in a wire- less network is strongly related to a minimum connected dominating set in its graph theoretic representation. Motivated by the vastness of application areas, we study several problems including maximum independent set, minimum vertex coloring, minimum clique partition, max-cut and min-bisection. Although these problems have been widely studied in the context of unit disk graphs, which are the two dimensional version of unit ball graphs, there is no established result on the complexity and approximation status for some of them in unit ball graphs. Furthermore, unit ball graphs can provide a better representation of real networks since the nodes are deployed in the three dimensional space. We prove complexity results and propose solution procedures for several problems using geometrical properties of these graphs. We outline a matching-based branch and bound solution procedure for the maximum k-clique problem in unit disk graphs and demonstrate its effectiveness through computational tests. We propose using minimum bottleneck connected dominating set problem in order to determine the optimal transmission range of a wireless network that will ensure a certain size of "virtual backbone". We prove that this problem is NP-hard in general graphs but solvable in polynomial time in unit disk and unit ball graphs. We also demonstrate work on theoretical foundations for simple greedy heuristics. Particularly, similar to the notion of "best" approximation algorithms with respect to their approximation ratios, we prove that several simple greedy heuristics are "best" in the sense that it is NP-hard to recognize the gap between the greedy solution and the optimal solution. We show results for several well known problems such as maximum clique, maximum independent set, minimum vertex coloring and discuss extensions of these results to a more general class of problems. In addition, we propose a "worst-out" heuristic based on edge contractions for the max-cut problem and provide analytical and experimental comparisons with a well known "best-in" approach and its modified versions.

For traditional wireless communication systems, static spectrum allocation is the major spectrum allocation methodology. However, according to the recent investigations by the FCC, this has led to more than 70 percent of the allocated spectrum in the United States being under-utilized. Cognitive radio (CR) technology, which supports opportunistic spectrum sharing, is one idea that is proposed to improve the overall utilization efficiency of the radio spectrum. In this thesis we consider a CR communication system based on spectrum sharing schemes, where we have a secondary user (SU) link with multiple transmitting antennas and a single receiving antenna, coexisting with a primary user (PU) link with a single receiving antenna. At the SU transmitter (SU-Tx), the channel state information (CSI) of the SU link is assumed to be perfectly known; while the interference channel from the SU-Tx to the PU receiver (PU-Rx) is not perfectly known due to less cooperation between the SU and the PU. As such, the SU-Tx is only assumed to know that the interference channel gain can take values from a finite set with certain probabilities. Considering a SU transmit power constraint, our design objective is to determine the transmit covariance matrix that maximizes the SU rate, while we protect the PU by enforcing both a PU average interference constraint and a PU outage probability constraint. This problem is first formulated as a non-convex optimization problem with a non-explicit probabilistic constraint, which is then approximated as a mixed binary integer programming (MBIP) problem and solved with the Branch and Bound (BB) algorithm. The complexity of the BB algorithm is analyzed and numerical results are presented to validate the eff ectiveness of the proposed algorithm. A key result proved in this thesis is that the rank of the optimal transmit covariance matrix is one, i.e., CR beamforming is optimal under PU outage constraints. Finally, a heuristic algorithm is proposed to provide a suboptimal solution to our MBIP problem by efficiently (in polynomial time) solving a particularly-constructed convex problem.

1 x N optical power splitters using hybrid sol-gel glasses based on buried waveguide structure on silicon substrate were fabricated. The advantage over conventional ridge structures is the fact that Y branch of the splitters can be easily obtained with the buried structure using standard photo lithography processes. Now we can successfully make the width of Y branch of less of 1um. Proximity printing was used to define the waveguide trench on sol-gel films. Then burying the sol-gel glass into the trench to define waveguide core. Finally the waveguide was packaged for measurement after coating a sol-gel top cladding layer onto the guiding layer. The propagation losses of this waveguide device are 0.69 dB/cm and 0.70 dB/cm for TE and TM polarized lights. The coupling losses are 1.57 dB and 1.89 dB for TE and TM lights with a index contrast of 0.66 %. The insertion loss and the branching loss of the 1¡Ñ2 splitter are 5.7 dB and 0.3 dB¡Arespectively.

In manufacturing environments, machines are usually subject to down periods due to various reasons such as preventive maintenance activities, pre-accepted jobs and pre-known material shortages. Among these reasons, preventive maintenance, which is defined as the pre-planned maintenance activities to keep the machine in its operating state, has gained much more importance in recent years. In this thesis, we consider the single machine total flow time problem where the jobs are non-resumable and the machine is subject to preventive maintenance activities of known starting times and durations. We propose a number of optimality properties together with the upper and lower bounding procedures. Using these mechanisms, we build a branch and bound algorithm to find the optimal solution of the problem. Our extensive computational study on randomly generated test instances shows that our algorithm can solve large-sized problem instances with up to 80 jobs in reasonable times. We also study a two-alternative maintenance planning problem with minor and major maintenances. We give an optimizing algorithm to find the timing of the maintenances, when the job sequence is fixed.

In project scheduling, the activity durations can often be reduced by dedicating additional resources. Time/Cost Trade-off Problem considers the compromise between the total cost and project duration. The discrete version of the problem assumes a number of time/cost pairs, so called modes, and selects a mode for each activity. In this thesis we consider the Discrete Time/Cost Trade-off Problem. We first study the Deadline Problem, i.e., the problem of minimizing total cost subject to a deadline on project duration. To solve the Deadline Problem, we propose several optimization and approximation algorithms that are based on optimal Linear Programming Relaxation solutions. We then analyze the problem of generating all efficient solutions, and propose an approach that uses the successive solutions of the Deadline Problem. Our computational results on large-sized problem instances have revealed the satisfactory behavior of our algorithms.

Rhizopus oryzae is a filamentous fungus, which can produce high amounts of L(+)-lactic acid and produces ethanol as the main by-product. In an effort to understand the pyruvate branch point of this organism, fermentations under different inoculum and glucose concentrations were carried out. At low inoculum size (1x103 spores ml-1), high amount of lactate (78 g l-1) was produced, whereas high ethanol concentration (37 g l-1) was obtained at high inoculum sizes (1x106 spores ml-1). Decreasing working volume increased lactate production significantly at high inoculum sizes (1x105 and 1x106 spores ml-1), but did not influenced the physiology at low inoculum sizes (1x103 and 1x104 spores ml-1). In shake flask cultures, at low initial glucose concentrations biomass yield was high and lactate and ethanol yields were low. Higher lactate and ethanol and lower biomass yields were obtained by increasing the initial glucose concentrations. In alginate immobilized, semi-continuous cultures with cell retention, glucose level in the medium was kept at low values. Like in shake flask cultures, as the glucose concentration decreased lactate and ethanol yields decreased and biomass yields increased. Increasing the glucose concentration by a pulse of glucose caused increases in branch point enzyme activities, as well as in concentrations of the metabolites. In fed batch cultures higher biomass yield (0.25 g DCW g glucose-1) could be obtained. Lactate dehydrogenase was influenced by the inoculum size and glucose concentration more than pyruvate decarboxylase and alcohol dehydrogenase. It showed higher activity at lactate producing fermentations. Unlike lactate dehydrogenase, pyruvate decarboxylase and alcohol dehydrogenase showed high activity even at low glucose concentrations.

The growing extent and variety of present military operations forces to use the resources in hand at its best. Especially, the optimum usage and assignment of limited number of the air force resources to missions will provide a considerable advantage in the battle field. The problem of finding the feasible and optimum assignment has been known to be studied / yet performing the process faster is still a topic that captures researchers&rsquo / attention because of the computational complexity that the assignment problem involves within. In this thesis, exploring the optimal assignment of fleets/aircrafts to targets/groups of targets is going to be performed via algorithms and heuristics. As the best choice for finding the exact solution, Branch-and-Bound algorithm, which is an intelligent way of searching for the solution on a solution tree where the nodes with potential of not leading to the solution are fathomed, has been investigated and applied according to the specific problem needs. The number of nodes on the search tree increases exponentially as the problem size increases. Moreover / as the size of the assignment problem increases, attaining the solution solely by Branch-and-Bound algorithm is definitely computationally expensive due to memory and time requirements. Therefore, Genetic algorithm which can provide good solutions in a relatively short time without having computational difficulties is considered as the second algorithm. Branch-and-Bound algorithm and Genetic algorithm are separately used for obtaining the solution. Hybrid algorithms which are combinations of Branch-and-Bound and Genetic algorithms are used with heuristics for improving the results.

ABSTRACT FLEXIBLE ASSEMBLY LINE DESIGN PROBLEM WITH FIXED NUMBER OF WORKSTATIONS Barut&ccedil / uoglu, Sirin M.S. Department of Industrial Engineering Supervisor: Prof. Dr. Meral Azizoglu July 2009, 70 pages In this thesis, we study a Flexible Assembly Line Design problem. We assume the task times and equipment costs are correlated in the sense that for all tasks the cheaper equipment gives no smaller task time. Given the cycle time and number of workstations we aim to find the assignment of tasks and equipments to the workstations that minimizes the total equipment cost. We study a special case of the problem with identical task times. For the general case, we develop a branch and bound algorithm that uses powerful lower bounds and reduction mechanisms. We test the performance of our branch and bound algorithm on randomly generated test problems. The results of our experiments have revealed that we are able to solve large-sized problem instances in reasonable times.

Web pages serve a huge number of internet users in nearly every area. An adequate testing is needed to address the problems of web domains for more efficient and accurate services. We present an automated tool to test web applications against execution errors and the errors occured when many users connect the same server concurrently. Our tool, called NaMoX, attains the clickables of the web pages, creates a model exerting depth first search algorithm. NaMoX simulates a number of users, parses the developed model, and tests the model by branch coverage analysis. We have performed experiments on five web sites. We have reported the response times when a click operation is eventuated. We have found 188 errors in total. Quality metrics are extracted and this is applied to the case studies.

No description available.