We study a so-called static approach for the problem of routing vehicles conflict-free through a given street network. In fact, we assume that routes are computed without taking time-dependences into account
and collisions are avoided via a particular reservation procedure. In this context, the task is to cope with two arising problems: the appearance of congestion and detours on the one hand and the risk of deadlocks on the other.
We provide a two-stage routing approach for that problem. In the first phase we focus on balancing the load on the edges of the
given graph that models the underlying street network. Therefore, we consider the Online Load Balancing Problem with Bounded Stretch
Factor and give an optimal algorithm with respect to a specific performance ratio, the stretch factor restricted competitive ratio. Furthermore, in a second phase, we investigate the detection and avoidance of deadlock situations.
For the evaluation of the entire algorithm we consider the routing of Automated Guided Vehicles (AGVs) at HHLA Container Terminal
Altenwerder (CTA).
We consider quickest flows within a new model that is based on transportation applications. In contrast to other models, it is forbidden to store flow in nodes and to cross nodes with more than one flow unit simultaneously. We work on undirected graphs. Grid graphs are of special interest because they typically arise in practice. Our model allows to close edges temporarily by time windows, and considers waiting on edges.
We solve several quickest s,t–flow problems without time windows polynomially. We prove that time windows make these problems NP–hard and even not approximable. In a multicommodity environment, all quickest flow variants are shown to be NP–hard even in grid graphs with uniform edge transit times. An alternative proof shows NP-hardness already for a small number of commodities in the case that waiting is not allowed and transit times are edge–specific. Finally, we propose two approximation algorithms in the case that time windows do not occur.
In the planning process of railway companies, we propose to integrate important
decisions of network planning, line planning, and vehicle scheduling into the task of periodic
timetabling. From such an integration, we expect to achieve an additional potential for
optimization.
Models for periodic timetabling are commonly based on the Periodic Event Scheduling
Problem (PESP). We show that, for our purpose of this integration, the PESP has to be extended
by only two features, namely a linear objective function and a symmetry requirement.
These extensions of the PESP do not really impose new types of constraints, because practitioners
have already required them even when only planning timetables autonomously without
interaction with other planning steps.
Large-scale maintenance in industrial plants requires the entire shutdown of production
units for disassembly, comprehensive inspection and renewal. It is an important process but causes high out-of-service cost. Therefore a good schedule for a shutdown and and an analysis of possible associated risks are crucial for the manufacturer.
We derive models and algorithms for shutdown scheduling that include different features
such as time-cost tradeoff, precedence constraints, hiring external resources, resource leveling, different working shifts, and risk analysis. Our experimental results show that our methods solve large real-world instances very fast 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.
Our algorithms work in two phases. The first phase supports the manager in finding a
good makespan for the shutdown. It computes an approximate project time cost tradeoff
curve together with a stochastic evaluation of the risk for meeting a particular makespan t. Our risk measures are the expected tardiness at time t and the probability of completing the shutdown within time t. In the second, detailed planning 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, but now for the detailed schedule. The shutdown problem has many relationships with well established areas of scheduling, and we also give an overview on the large variety of scheduling problems involved.
We propose a hybrid approach for solving the resource-constrained project scheduling problem which is an extremely hard to solve combinatorial optimization problem of practical relevance. Jobs have to be scheduled on (renewable) resources subject to precedence constraints such that the resource capacities are never exceeded and the latest completion time of all jobs is minimized. The problem has challenged researchers from different communities, such as integer programming (IP), constraint programming (CP), and satisfiability testing (SAT). Still, there are instances with 60 jobs which have not been solved for many years. The currently best known approach, lazyFD, is a hybrid between CP and SAT techniques. In this paper we propose an even stronger hybridization by integrating all the three areas, IP, CP, and SAT, into a single branch-and-bound scheme. We show that lower bounds from the linear relaxation of the IP formulation and conflict analysis are key ingredients for pruning the search tree. First computational experiments show very promising results. For five instances of the well-known PSPLIB we report an improvement of lower bounds. Our implementation is generic, thus it can be potentially applied to similar problems as well.