In this dissertation, we study the single machine scheduling problem with an objective of minimizing the total completion time subject to release dates. The problem, denoted 1|rj £UCj ,was known to be strongly NP-hard and both theoretically and practically important. The focus of the research in this dissertation is to develop the efficient algorithms for solving the 1|rj|£UCj problem. This thesis contains two parts. In the first part, the theme concerns the approximation approach. We derive a necessary and sufficient condition for local optimality, which can be implemented as a priority rule and be used to construct three heuristic algorithms with running times of O(n log n). By ¡¨local optimality¡¨, we mean the optimality of all candidates whenever a job is selected in a schedule, without considering the other jobs preceding or following. This is the most broadly considered concepts of locally optimal rule. We also identify a dominant subset which is strictly contained in each of all known dominant subsets, where a dominant subset is a set of solutions containing all optimal schedules. In the second part, we develop our optimality algorithms for the 1|rj |£UCj problem. First, we present a lemma for estimating the sum of delay times of the rest jobs, if the starting time is delayed a period of time in a schedule. Then, using the lemma, partially, we proceed to develop a new partition property and three dominance theorems, that will be used and have improved the branch-and-bound algorithms for our optimization approach. By exploiting the insights gained from our heuristics as a branching scheme and by exploiting our heuristics as an upper bounding procedure, we propose three branch-and-bound algorithms. Our algorithms can optimally solve the problem up to 120 jobs, which is known to be the best till now.

We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

The study in this thesis focuses on the DTV antennas for mobile applications. By using the novel techniques in the proposed antenna, the narrow-band problem and the radiation pattern of the conventional DTV antenna can be improved. In the first design, the antenna comprises two radiating arms. By adjusting the open gap between the ends of the two radiating arms, large impedance bandwidth can be obtained for DTV signal reception. In the second design, by integrating a coupling portion into the dipole antenna, the full-wavelength resonant mode can be excited successfully and combined with the half-wavelength mode to form a wide operating band. Finally, in the third design, a U-shaped feeding gap is embedded within the V-shaped antenna to excite the full-wavelength resonant mode. Additionally, the dipole antenna can radiate comparable E£X and E£c components, resulting in no nulls in the total-power radiation patterns in the horizontal and vertical planes.

Während der Flutkatastrophe im August 2002 wurde auch das Tharandter Badetal durch das Hochwasser der Wilden Weißeritz geflutet. Die dort im so genannten Altbau des Campusgeländes befindliche Zweigbibliothek (ZWB) Forstwesen der Sächsischen Landesbibliothek - Staats- und Universitätsbibliothek Dresden (SLUB) wurde von den Wassermassen, die sich mit 170 Kubikmeter Wasser pro Sekunde den Weg talabwärts suchten, umschlossen und schwer geschädigt.

Ziel der vorliegenden Arbeit ist es, die Auswirkungen exogener Schocks auf das Handeln der Unternehmer und die daraus resultierende Entwicklung des Unternehmenserfolges unter Rückgriff auf Modelle der Sozialökonomischen Verhaltensforschung sowie der Industrieökonomik branchenspezifisch zu analysieren. Unter einem exogenen Schock ist dabei eine aus dem System bzw. Modell heraus nicht erklärbare Veränderung der handlungsexogenen Einflußfaktoren der Unternehmen zu verstehen. Aufgrund der Betrachtung von Zeitreiheninnovationen lassen sich diese exogenen Schocks auch als stochastische Prognosefehler der Wirtschaftssubjekte interpretieren. Die Kenntnis der Intensität der Abhängigkeit des Unternehmenserfolges einzelner Branchen von exogenen Schocks ist insbesondere für die Durchführung von Branchenratings von großer Bedeutung. Auf der Basis der gewonnenen Untersuchungsergebnisse können u.a. empirisch fundierte Aussagen über die branchenspezifische Ausprägung zentraler Ratingkriterien getroffen werden, wie beispielsweise über die Konjunkturempfindlichkeit, Fixkostenbelastung, Verhandlungsmacht der Lieferanten, aktuelle Profitabilität, Preisempfindlichkeit sowie das Marktwachstum bestimmter Branchen.

<p>This thesis consists of an introduction and sevenindependent, but closely related, papers which all deal withproblems in structural optimization. In particular, we considermodels and methods for global optimization of problems intopology design of discrete and continuum structures.</p><p>In the first four papers of the thesis the nonconvex problemof minimizing the weight of a truss structure subject to stressconstraints is considered. First itis shown that a certainsubclass of these problems can equivalently be cast as linearprograms and thus efficiently solved to global optimality.Thereafter, the behavior of a certain well-known perturbationtechnique is studied. It is concluded that, in practice, thistechnique can not guarantee that a global minimizer is found.Finally, a convergent continuous branch-and-bound method forglobal optimization of minimum weight problems with stress,displacement, and local buckling constraints is developed.Using this method, several problems taken from the literatureare solved with a proof of global optimality for the firsttime.</p><p>The last three papers of the thesis deal with topologyoptimization of discretized continuum structures. Theseproblems are usually modeled as mixed or pure nonlinear 0-1programs. First, the behavior of certain often usedpenalization methods for minimum compliance problems isstudied. It is concluded that these methods may fail to producea zero-one solution to the considered problem. To remedy this,a material interpolation scheme based on a rational functionsuch that compli- ance becomes a concave function is proposed.Finally, it is shown that a broad range of nonlinear 0-1topology optimization problems, including stress- anddisplacement-constrained minimum weight problems, canequivalently be modeled as linear mixed 0-1 programs. Thisresult implies that any of the standard methods available forgeneral linear integer programming can now be used on topologyoptimization problems.</p><p><b>Keywords:</b>topology optimization, global optimization,stress constraints, linear programming, mixed integerprogramming, branch-and-bound.</p>

Real-time aspects are becoming more important in standard desktop PC environments and x86 based processors are being utilized in embedded systems more often. While these processors were not created for use in hard real time systems, they are fast and inexpensive and can be used if it is possible to determine the worst case execution time. Information on CPU caches (L1, L2) and branch prediction architecture is necessary to simulate best and worst cases in execution timing, but is often not detailed enough and sometimes not published at all. This document describes how the underlying hardware can be analysed to obtain this information.

This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.

Thesis (doctoral)--Universität Karlsruhe, 1999.

Project Thesis (D. Min.)--Denver Conservative Baptist Seminary, 1989. / Includes bibliographical references (leaves 97-105).