The central thesis of this dissertation is that insight from queueing analysis can effectively guide standard (combinatorial) scheduling algorithms in dynamic environments. Scheduling is generally concerned with complex combinatorial decisions for static problems, whereas queueing theory simplifies the combinatorics and focuses on dynamic systems. We examine a queueing network with flexible servers under queueing and scheduling techniques. Based on the strengths of queueing analysis and scheduling, we develop a hybrid model that guides scheduling with results from the queueing model. In order to include setup times, we create a logic-based Benders decomposition model for a static representation of the queueing network. Our model is able to find optimal schedules up to 5 orders of magnitude faster than the only other model in the literature. A hybrid model is then developed for the dynamic problem and shown to achieve the best mean flow time while also guaranteeing maximal capacity.

The Lovasz theta function and the associated convex sets known as theta bodies are fundamental objects in combinatorial and semidefinite optimization. They are accompanied by a rich duality theory and deep connections to the geometric concept of orthonormal representations of graphs. In this thesis, we investigate several ramifications of the theory underlying these objects, including those arising from the illuminating viewpoint of duality. We study some optimization problems over unit-distance representations of graphs, which are intimately related to the Lovasz theta function and orthonormal representations. We also strengthen some known results about dual descriptions of theta bodies and their variants. Our main goal throughout the thesis is to lay some of the foundations for using semidefinite optimization and convex analysis in a way analogous to how polyhedral combinatorics has been using linear optimization to prove min-max theorems. A unit-distance representation of a graph $G$ maps its nodes to some Euclidean space so that adjacent nodes are sent to pairs of points at distance one. The hypersphere number of $G$, denoted by $t(G)$, is the (square of the) minimum radius of a hypersphere that contains a unit-distance representation of $G$. Lovasz proved a min-max relation describing $t(G)$ as a function of $\vartheta(\overline{G})$, the theta number of the complement of $G$. This relation provides a dictionary between unit-distance representations in hyperspheres and orthonormal representations, which we exploit in a number of ways: we develop a weighted generalization of $t(G)$, parallel to the weighted version of $\vartheta$; we prove that $t(G)$ is equal to the (square of the) minimum radius of an Euclidean ball that contains a unit-distance representation of $G$; we abstract some properties of $\vartheta$ that yield the famous Sandwich Theorem and use them to define another weighted generalization of $t(G)$, called ellipsoidal number of $G$, where the unit-distance representation of $G$ is required to be in an ellipsoid of a given shape with minimum volume. We determine an analytic formula for the ellipsoidal number of the complete graph on $n$ nodes whenever there exists a Hadamard matrix of order $n$. We then study several duality aspects of the description of the theta body $\operatorname{TH}(G)$. For a graph $G$, the convex corner $\operatorname{TH}(G)$ is known to be the projection of a certain convex set, denoted by $\widehat{\operatorname{TH}}(G)$, which lies in a much higher-dimensional matrix space. We prove that the vertices of $\widehat{\operatorname{TH}}(G)$ are precisely the symmetric tensors of incidence vectors of stable sets in $G$, thus broadly generalizing previous results about vertices of the elliptope due to Laurent and Poljak from 1995. Along the way, we also identify all the vertices of several variants of $\widehat{\operatorname{TH}}(G)$ and of the elliptope. Next we introduce an axiomatic framework for studying generalized theta bodies, based on the concept of diagonally scaling invariant cones, which allows us to prove in a unified way several characterizations of $\vartheta$ and the variants $\vartheta'$ and $\vartheta^+$, introduced independently by Schrijver, and by McEliece, Rodemich, and Rumsey in the late 1970's, and by Szegedy in 1994. The beautiful duality equation which states that the antiblocker of $\operatorname{TH}(G)$ is $\operatorname{TH}(\overline{G})$ is extended to this setting. The framework allows us to treat the stable set polytope and its classical polyhedral relaxations as generalized theta bodies, using the completely positive cone and its dual, and it allows us to derive a (weighted generalization of a) copositive formulation for the fractional chromatic number due to Dukanovic and Rendl in 2010 from a completely positive formulation for the stability number due to de Klerk and Pasechnik in 2002. Finally, we study a non-convex constraint for semidefinite programs (SDPs) that may be regarded as analogous to the usual integrality constraint for linear programs. When applied to certain classical SDPs, it specializes to the standard rank-one constraint. More importantly, the non-convex constraint also applies to the dual SDP, and for a certain SDP formulation of $\vartheta$, the modified dual yields precisely the clique covering number. This opens the way to study some exactness properties of SDP relaxations for combinatorial optimization problems akin to the corresponding classical notions from polyhedral combinatorics, as well as approximation algorithms based on SDP relaxations.

Genetic algorithms are commonly used to solve combinatorial optimizationproblems. The implementation evolves using genetic operators (crossover, mutation,selection, etc.). Anyway, genetic algorithms like some other methods have parameters(population size, probabilities of crossover and mutation) which need to be tune orchosen.In this paper, our project is based on an existing hybrid genetic algorithmworking on the multiprocessor scheduling problem. We propose a hybrid Fuzzy-Genetic Algorithm (FLGA) approach to solve the multiprocessor scheduling problem.The algorithm consists in adding a fuzzy logic controller to control and tunedynamically different parameters (probabilities of crossover and mutation), in anattempt to improve the algorithm performance. For this purpose, we will design afuzzy logic controller based on fuzzy rules to control the probabilities of crossoverand mutation. Compared with the Standard Genetic Algorithm (SGA), the resultsclearly demonstrate that the FLGA method performs significantly better.

The aim of this work is to investigate Ant Colony Algorithm for the traveling salesman problem (TSP). Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of a pheromone trail deposited on the edges of the TSP graph. This paper is based on the ideas of ant colony algorithm and analysis the main parameters of the ant colony algorithm. Experimental results for solving TSP problems with ant colony algorithm show great effectiveness.

The transition fundions for the correlated random walk with two absorbing boundaries are derived by means of a combinatorial construction which is based on Krattenthaler's Theorem for counting lattice paths with turns. Results for walks with one boundary and for unrestricted walks are presented as special cases. Finally we give an asymptotic formula, which proves to be useful for computational purposes. (author's abstract) / Series: Forschungsberichte / Institut für Statistik

The mathematical modelling of a market, and the proof of existence of equilibria have been of central importance in mathematical economics. Since the existence proof is non-constructive in general, a natural question is if computation of equilibria can be done efficiently. Moreover, the emergence of Internet and e-commerce has given rise to new markets that have completely changed the traditional notions. Add to this the pervasiveness of computing resources, and an algorithmic theory of market equilibrium becomes highly desirable. The goal of this thesis is to provide polynomial time algorithms for various market models. Two basic market models are the Fisher model: one in which there is a demarcation between buyers and sellers, buyers are interested in the goods that the sellers possess, and sellers are only interested in the money that the buyers have; and the Arrow-Debreu model: everyone has an endowment of goods, and wants to exchange them for other goods. We give the first polynomial time algorithm for exactly computing an equilibrium in the Fisher model with linear utilities. We also show that the basic ideas in this algorithm can be extended to give a strongly polynomial time approximation scheme in the Arrow-Debreu model. We also give several existential, algorithmic and structural results for new market models: - the *spending constraint* utilities (defined by Vazirani) that captures the "diminishing returns" property while generalizing the algorithm for the linear case. - the capacity allocation market (defined by Kelly), motivated by the study of fairness and stability of the Transmission Control Protocol (TCP) for the Internet, and more generally the class of Eisenberg-Gale (EG) markets (defined by Jain and Vazirani). In addition, we consider the adwords market on search engines and show that some of these models are a natural fit in this setting. Finally, this line of research has given insights into the fundamental techniques in algorithm design. The primal-dual schema has been a great success in combinatorial optimization and approximation algorithms. Our algorithms use this paradigm in the enhanced setting of Karush-Kuhn-Tucker (KKT) conditions and convex programs.

Thesis (M. Phil.)--University of Hong Kong, 2001. / Includes bibliographical references (leaves 56-59).

Thesis (Ph.D)--Computing, Georgia Institute of Technology, 2009. / Committee Chair: Khot, Subhash; Committee Member: Tetali, Prasad; Committee Member: Thomas, Robin; Committee Member: Vempala, Santosh; Committee Member: Vigoda, Eric. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Thesis (Ph. D.)--Oregon State University, 2003. / Typescript (photocopy). Includes bibliographical references (leaves 59-60). Also available on the World Wide Web.

Not available / text