Consider optimizing a periodic schedule for an automated production plant as a last step of a more comprehensive design process. In our scenario, each robot’s cyclic sequence of operations and trajectories between potential waiting points have already been fully specified. Further given are those precedences that fix sequence requirements on operations between different robots. It remains to determine the starting time for each operation or movement of each robot within a common cyclic time period so as to avoid collisions of robots that operate in the same space simultaneously. So the task is to find a conflict-resolving schedule that minimizes this common periodic cycle time while observing all precedence relations and collision avoidance constraints. The proposed cycle time minimization problem for robot coordination has, to the best of our knowledge, not been studied before. We develop an approach for solving it by employing binary search for determining the smallest feasible period time of an iso-periodic event scheduling problem (IPESP). This is a variant of the periodic event scheduling problem in which the objects that have to be scheduled need to obey exactly the same period time. The possibility to wait arbitrarily long at waiting points turns out to be essential to justify the use of binary search for identifying the minimum cycle time, thereby avoiding bilinear mixed integer formulations. Special properties of the given scenario admit bounds on the periodic tension variables of an integer programming formulation. Although the IPESP subproblems remain NP-complete in general, these bounds allow solving real-world instances sufficiently fast for the approach to be applicable in practice. Numerical experiments on real-world and randomly generated data are supplied to illustrate the potential and limitations of this approach. Summary of Contribution: When designing automated production plants, a crucial step is to identify the smallest possible per unit period time for the production processes. Based on periodic event scheduling ideas, we develop and analyze mathematical methods for this purpose. We show that the algorithmic implementation of our approach provides an answer to current real-world designs in reasonable time.

We provide strongly polynomial time combinatorial algorithms to minimize the largest eigenvalue of the weighted Laplacian of a bipartite graph and the weighted signless Laplacian of an arbitrary graph by redistributing weights among the edges. This is accomplished by solving graph embedding problems which arise as dual programs of a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.

The aim of the train timetabling problem is to find a conflict free timetable for a set of passenger and freight trains along their routes in an infrastructure network. Several constraints like station capacities and train dependent running and headway times have to be satisfied. In this work we deal with large scale instances of the aperiodic train timetabling problem for the German railway network. The problem is modelled in a classical way via time discretised networks, its Lagrange-dual is solved by a bundle method. In order to handle the enormous number of variables and constraints dynamic graph generation and dynamic rolling horizon techniques are employed.

Given a graph $G=(V,E)$ with node weights $\varphi_v \in \mathbb{N}\cup\{0\}$, $v\in V$, and some number $F\in \mathbb{N}\cup\{0\}$, the convex hull of the incidence vectors of all cuts $\delta(S)$, $S\subseteq V$, with $\varphi(S)\le F$ and $\varphi(V\setminus S)\le F$ is called the bisection cut polytope. We study the facial structure of this polytope which shows up in many graph partitioning problems with applications in VLSI design or frequency assignment. We give necessary and in some cases sufficient conditions for the knapsack tree inequalities introduced in [C. E. Ferreira et al., Math. Programming, 74 (1996), pp. 247–267] to be facet-defining. We extend these inequalities to a richer class by exploiting the fact that each cut intersects each cycle in an even number of edges. Finally, we present a new class of inequalities that are based on nonconnected substructures yielding nonlinear right-hand sides. We show that the supporting hyperplanes of the convex envelope of this nonlinear function correspond to the faces of the so-called cluster weight polytope, for which we give a complete description under certain conditions.

Based on the method of Maxwell and Baker [7], an all-integer algorithm is developed for the rendering of elliptical curves.It is immune to problems of degeneracy and best suited for hardware implementation.At each point the algorithm provides the tangent vector and an estimate of the quantization error, all the data needed for rendering high precision elliptical arcs and generating antialiased curves, (categories and

Even though GKS did not include circles and, in a more general form, ellipses and elliptical arcs in the list of elementary graphics primitives, CGM settled this omission with its standardization in 1987. According to CGM as well as to CGI, ellipses and elliptical arcs are defined in a very general way via endpoints of conjugate diameter pairs (CDP). Based on the algorithm of Maxwell & Baker [5] this paper presents a new algorithm for the rendering of general ellipses (i.e. not aligned to the coordinate axes) and elliptical arcs which is not only fast and very well suited for implementation in hardware but also deals with all degenerate cases of ellipses at no extra cost. Furthermore, the algorithm provides all the information which is necessary for the generation of anti-aliased elliptical curves.