This paper analyzes the stochastic runtime of the cross-entropy (CE) algorithm for the well-studied standard problems ONEMAX and LEADINGONES. We prove that the total number of solutions the algorithm needs to evaluate before reaching the optimal solution (i.e., its runtime) is bounded by a polynomial Q(n) in the problem size n with a probability growing exponentially to 1 with n if the parameters of the algorithm are adapted to n in a reasonable way. Our polynomial bound Q(n) for ONEMAX outperforms the well-known runtime bound of the 1-ANT algorithm, a particular ant colony optimization algorithm. Our adaptation of the parameters of the CE algorithm balances the number of iterations needed and the size of the samples drawn in each iteration, resulting in an increased efficiency. For the LEADINGONES problem, we improve the runtime of the algorithm by bounding the sampling probabilities away from 0 and 1. The resulting runtime outperforms the known stochastic runtime for a univariate marginal distribution algorithm, and is very close to the known expected runtime of variants of max-min ant systems. Bounding the sampling probabilities allows the CE algorithm to explore the search space even for test functions with a very rugged landscape as the LEADINGONES function.

Reducing traffic congestion via toll pricing has been a central topic in the operations research and transportation literature and, recently, it has been implemented in several cities all over the world. Since, in practice, it is not feasible to impose tolls on every edge of a given traffic network, we study the resulting mathematical problem of computing tolls on a predefined subset of edges of the network so as to minimize the total travel time of the induced equilibrium flow. We first present an analytical study for the special case of parallel edge networks highlighting the intrinsic complexity and nonconvexity of the resulting optimization problem. We then present algorithms for general networks for which we systematically test the solution quality for large‐scale network instances. Finally, we discuss the related optimization problem of computing tolls subject to a cardinality constraint on the number of edges that have tolls. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(3), 262–285 2015

Large-scale maintenance in industrial plants requires the entire shutdown of production units for disassembly, comprehensive inspection, and renewal. We derive models and algorithms for this so-called turnaround scheduling that include different features such as time-cost trade-off, precedence constraints, external resource units, resource leveling, different working shifts, and risk analysis. We propose a framework for decision support that consists of two phases. The first phase supports the manager in finding a good makespan for the turnaround. It computes an approximate project time-cost trade-off curve together with a stochastic evaluation. Our risk measures are the expected tardiness at time t and the probability of completing the turnaround within time t. In the second phase, we solve the actual scheduling optimization problem for the makespan chosen in the first phase heuristically and compute a detailed schedule that respects all side constraints. Again, we complement this by computing upper bounds for the same two risk measures. Our experimental results show that our methods solve large real-world instances from chemical manufacturing plants quickly and yield an excellent resource utilization. A comparison with solutions of a mixed-integer program on smaller instances proves the high quality of the schedules that our algorithms produce within a few minutes.

Material flow problems are complex logistic optimization problems. We want to utilize the available logistic network in such a way that the load is minimized or the throughput is maximized. This lecture deals with these optimization problems from the viewpoint of network flow theory and reports on two industrial applications: (1) contolling material flow with automated guided vehicles in a container terminal (cooperation with HHLA), and (2) timetabling in public transport (cooperation with Deutsche Bahn and Berlin Public Transport). The key ingredient for (1) is a very fast real-time algorithm which avoids collisions, deadlocks, and other conflicts already at route computation, while for (2) it is the use of integer programs based on special bases of the cycle space of the routing graph.

In many scheduling applications it is required that the processing of some job be postponed until some other job, which can be chosen from a pregiven set of alternatives, has been completed. The traditional concept of precedence constraints fails to model such restrictions. Therefore, the concept has been generalized to so-called AND/OR precedence constraints which can cope with this kind of requirement. In the context of traditional precedence constraints, feasibility, transitivity, and the computation of earliest start times for jobs are fundamental, well-studied problems. The purpose of this paper is to provide efficient algorithms for these tasks for the more general model of AND/OR precedence constraints. We show that feasibility as well as many questions related to transitivity can be solved by applying essentially the same linear-time algorithm. In order to compute earliest start times we propose two polynomial-time algorithms to cope with different classes of time distances between jobs.

We consider the problem to minimize the total weighted completion time of a set of jobs with individual release dates which have to be scheduled on identical parallel machines.Job processing times are not known in advance, they are realized on-line according to given probability distributions.The aim is to find a scheduling policy that minimizes the objective in expectation.Motivated by the success of LP-based approaches to deterministic scheduling, we present a polyhedral relaxation of the performance space of stochastic parallel machine scheduling.This relaxation extends earlier relaxations that have been used, among others, by Hall et al. [1997] in the deterministic setting.We then derive constant performance guarantees for priority policies which are guided by optimum LP solutions, and thereby generalize previous results from deterministic scheduling.In the absence of release dates, the LP-based analysis also yields an additive performance guarantee for the WSEPT rule which implies both a worst-case performance ratio and a result on its asymptotic optimality, thus complementing previous work by Weiss [1990].The corresponding LP lower bound generalizes a previous lower bound from deterministic scheduling due to Eastman et al. [1964], and exhibits a relation between parallel machine problems and corresponding problems with only one fast single machine.Finally, we show that all employed LPs can be solved in polynomial time by purely combinatorial algorithms.

We investigate a problem arising in the computer-aided design of cars, planes, ships, trains, and other motor vehicles and machines: refine a mesh of curved polygons, which approximates the surface of a workpiece, into quadrilaterals so that the resulting mesh is suitable for a numerical analysis. This mesh refinement problem turns out to be strongly NP -hard In commercial CAD systems, this problem is usually solved using a gree dy approach. However, these algorithms leave the user a lot of patchwork to do afterwards. We introduce a new global approach, which is based on network flow techniques. Abstracting from all geometric and numerical aspects, we obtain an undirected graph with upper and lower capacities on the edges and some additional node constraints. We reduce this problem to a sequence of bidirected flwo problems (or, equivalently, to b -matching problems). For the first time, network flow techniques are applied to a mesh refinement problem. This approach avoids the local traps of greedy approaches and yields solutions that require significantly less additional patchwork.

This paper investigates a transformation $P \to Q$ between partial orders $P,Q$ that transforms the interval dimension of P to the dimension of Q, i.e., $\text{idim} ( P ) = \dim ( Q )$. Such a construction has been shown before in the context of Ferrer’s dimension by Cogis [Discrete Math., 38 (1982), pp. 47–52]. The construction in this paper can be shown to be equivalent to his, but it has the advantage of (1) being purely order-theoretic, (2) providing a geometric interpretation of interval dimension similar to that of Ore [Amer. Math. Soc. Colloq. Publ., Vol. 38, 1962] for dimension, and (3) revealing several somewhat surprising connections to other order-theoretic results. For instance, the transformation $P \to Q$ can be seen as almost an inverse of the well-known split operation; it provides a theoretical background for the influence of edge subdivision on dimension (e.g., the results of Spinrad [Order, 5 (1989), pp. 143–147]) and interval dimension, and it turns out to be invariant with respect to changes of P that do not alter its comparability graph, thus also providing a simple new proof for the comparability invariance of interval dimension.

It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.

The fastest-known algorithm for recognizing interval graphs [S. Booth and S. Lucker, J. Comput. System Sci., 13 (1976), pp. 335–379] iteratively manipulates the system of all maximal cliques of the given graph in a rather complicated way in order to construct a consecutive arrangement (more precisely, a tree representation of all possible consecutive arrangements). This paper presents a much simpler algorithm using a related, but much more informative tree representation of interval graphs. This tree is constructed in an incremental fashion by adding vertices to the graph in a predefined order such that adding a vertex u takes $O(|{\operatorname{Adj}}(u)| + 1)$ amortized time.