This thesis presents a thorough introduction to flow shop problems with synchronous movement which are a variant of a non-preemptive permutation flow shop. Jobs have to be moved from one machine to the next by an unpaced synchronous transportation system, which implies that the processing is organized in synchronized cycles. This means that in each cycle the current jobs start at the same time on the corresponding machines and after processing have to wait until the last job is finished. Afterwards, all jobs are moved to the next machine simultaneously. In this thesis flow shops with synchronous movement are systematically embedded into the flow shop scheduling framework. The problem is defined for the most common objective functions as well as for many extensions and additional constraints that can be observed in real world applications. The thesis offers an extensive study of complexity of the discussed problems. Several exact and heuristic solution algorithms are proposed and evaluated. Further, a project in cooperation with a practitioner where flow shops with synchronous movement and resource constraints appear in a real world application is discussed. The results of the implemented heuristic approach are compared to the actual production of the industrial partner.

Let $A \subseteq \Z_n$ with $|A| = k$ for some $k \in \Z^+$. We consider the metric space $(\Z_n,\delta)$ in which $\delta$ is the distance metric on $\Z_n$ defined as follows: for every $x,y \in \Z_n$, $\delta(x,y) = |x-y|_n$ where $|z|_n = \min(z,n-z)$ for $z \in \{0,\ldots,n-1\}$. We say that $A$ is \emph{Erd\H{o}s-deep} if, for every $i \in \{1,2,\dots,k-1\}$, there is a positive number $d_i$ satisfying $$|\{\{x,y\} \subseteq A: \delta(x,y)=d_i\}|=i.$$ Erd\H{o}s-deep sets in $\Z_n$ have been previously classified as translates of: $\{0,1,2,4\}$ when $n = 6$; and, modular arithmetic progressions $\{0,g,2g,\cdots,(k-1)g\} \subseteq \Z_n$ for some generator $g$ and size $k$. Erd\H{o}s-deep sets have primarily been considered in metric spaces $(\Z_n,\delta)$ and $(\R^d,\norm{\cdot})$ for $d = 2$, but some exploration for $d > 2$ has been done as well. We introduce the notion of an \emph{Erd\H{o}s-deep family}. Let $\mathcal{F}=\{A_1,A_2,\dots,A_s\}$, where $A_1,\ldots, A_s \subseteq \Z_n$. Then we say $\mathcal{F}$ is Erd\H{o}s-deep if for some $k \in \Z^+$, for every $i \in \{1,2,\dots,k-1\}$ there is exactly one positive number $d_i$ satisfying $$\sum_{j=1}^s |\{\{x,y\} \subseteq A_j: \delta(x,y)=d_i\}|=i,$$ and no such $d_i$ for any $i \ge k$. We provide a complete existence theorem for Erd\H{o}s-deep pairs of arithmetic progressions $A_1,A_2 \subseteq \Z_n$ and also give a conjectured classification for Erd\H{o}s-deep families of three arithmetic progressions. Using an identity on triangular numbers, we show a general construction for larger families whose size $s$ is the square of an integer. This construction suggests the existence of Erd\H{o}s-deep families often relies on such number-theoretic identities. We define an extremal case of the Erd\H{o}s-deep family in $(\Z_n,\delta)$ in which both the distances and multiplicities are in $\{1,\ldots,k-1\}$; such families are called Winograd families. We conjecture that Winograd families of arithmetic progressions do not exist in the metric space $(\Z,|\cdot|)$. Erd\H{o}s-deep sets in $(\Z_n,\delta)$ correspond to a class of interesting musical rhythms. We conclude this work with a variety of musical demonstrations and original compositions using Erd\H{o}s-deep rhythm families as a creative constraint in composing multi-voiced rhythms. / Graduate

In this dissertation, we consider extensions of dynamic programming for combinatorial optimization. We introduce two exact multi-objective optimization algorithms: the multi-stage optimization algorithm that optimizes the problem relative to the ordered sequence of objectives (lexicographic optimization) and the bi-criteria optimization algorithm that simultaneously optimizes the problem relative to two objectives (Pareto optimization). We also introduce a counting algorithm to count optimal solution before and after every optimization stage of multi-stage optimization. We propose a fairly universal approach based on so-called circuits without repetitions in which each element is generated exactly one time. Such circuits represent the sets of elements under consideration (the sets of feasible solutions) and are used by counting, multi-stage, and bi-criteria optimization algorithms. For a given optimization problem, we should describe an appropriate circuit and cost functions. Then, we can use the designed algorithms for which we already have proofs of their correctness and ways to evaluate the required number of operations and the time. We construct conventional (which work directly with elements) circuits without repetitions for matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, convex polygon triangulation, line breaking (text justification), one-dimensional clustering, optimal bitonic tour, and segmented least squares. For these problems, we evaluate the number of operations and the time required by the optimization and counting algorithms, and consider the results of computational experiments. If we cannot find a conventional circuit without repetitions for a problem, we can either create custom algorithms for optimization and counting from scratch or can transform a circuit with repetitions into a so-called syntactical circuit, which is a circuit without repetitions that works not with elements but with formulas representing these elements. We apply both approaches to the optimization of matchings in trees and apply the second approach to the 0/1 knapsack problem. We also briefly introduce our work in operation research with applications to health care. This work extends our interest in the optimization field from developing new methods included in this dissertation towards the practical application.

So Long Sucker is a strategy board game requiring 4 players, each with c chips of their designated color, and a board made of k empty piles. With a clear set-up come intricate rules, such as: players taking turns but not in a fixed order, agreements between some players being made and broken at any time, and a player winning the game even without any chips in hand. One of the main points of interest in studying this game, is finding when a player has a winning strategy. The game begins with four players that get eliminated successively until the winner is left. To study winning strategies, it is of interest to look at endgame situations. We present the following game set-up: there are two players left in the game, Blue and Red, and only their respective chip colors. In this thesis, we characterize Blue's winning situations and strategies through inductive reasoning.

No description available.

No description available.

No description available.

No description available.

No description available.

The electrical double layer (EDL) is formed due to the accumulation of charge at the interface of a metal surface in contact with an electrolyte. The total charge in the EDL compensates the charge on the metal surface. As EDL is the layer that "connects" the electrode to the "bulk", all electrode mediated transport and redox reaction depends on the structure and dynamics of the ions in the EDL. Thus the ion dynamics in the EDL are critical to a wide range of physical and biological phenomena such as electrochemical reaction, flow in channels of nanofluidic devices, wetting of fluids; to biology, for example, folding and function of proteins, conformation change of DNA and ionic flow through cell membranes. EDL polarization is the ion accumulation or depletion in the EDL due to the potential of the metal surface. The conventional method of measuring the EDL polarization is by monitoring the current flowing through the electrochemical system. Thus, the electrical characteristics of the EDL are inferred indirectly from the total current that is implicitly related to effects such as the impedance of the bulk solution. We have developed a sensitive optical interferometric technique to directly measure the polarization of the metal-electrolyte interface. The key advantage of our method is high sensitivity, and the measurement is specific only to the changes at the metal-electrolyte interface. The ion accumulation in the EDL of a simple salt like NaCl is studied as a function of the frequency and the amplitude of the applied potential on the metal electrode. The amplitude of modulation of the ions is linearly proportional to the amplitude of the applied AC potential. The linearity is observed up to high amplitude (up to 2V) and salt concentration as high as 0.5M. Furthermore, the local segmental dynamics of polyelectrolytes such as polystyrene sulfonate have been measured. Next we extend this novel technique to study electrochemical redox reactions. The oxidation of the widely used redox ion [Fe(CN)6]4- is followed by measuring the response to an AC potential (amplitude ~100mV) as a function of a superimposed saw-tooth potential ramp, at a time period 106 fold slower and amplitude 5-10 fold larger than the AC potential. The sensitivity of the optical method is significantly better than the measurement of the AC current. For a redox process on the electrode, the change in the optical signal is over two orders of magnitude larger than the electrical signal. Using the optical technique, we can separate the kinetic events in redox processes: transport of charged species to the electrode surface and charge transfer across the electrode-electrolyte interface. Because we measure the local electrochemical process, the method can be used to probe redox reaction at multiple spots on the same electrode (i.e., combinatorial electrochemistry). / Ph. D.