Project description.

The efficient utilization of scarce resources is a major challenge within production planning and logistics. When modeled adequately, already deterministic settings lead to inherently hard computational problems. However, it becomes increasingly important to consider additionally incomplete information and random influences.

The goal in this project is to develop new efficient algorithms for optimization problems as they occur in logistics and planning. We will assess their performance by comparing their guaranteed performance relative to an unknown optimum. Our focus lies primarily on handling incomplete information and we consider therefore classic models as online optimization and stochastic input.

This project evolved from the previous Matheon Project C5 "Stochastic and nonlinear methods for solving resource constrained scheduling problems".

Research program.

The integration of online planning and stochastic information, as done in the stochastic online scheduling model (Megow, Uetz, and Vredeveld 2006), is not restricted to scheduling problems. In the next period, we will open our investigations in that field to a wider class of problems as they occur in logistics. While scheduling concerns solely the temporal assignment of tasks to scarce resources, many logistics problems have an additional aspect: the location; servers or resources are expected to move in a network, whereas the position of resources in classical scheduling problems is assumed to be fixed and, thus, does not play any role. With our results on handling incomplete information in scheduling from the first project period, we have established a promising basis for our extended research.

An immediate application of logistic problems under uncertainty is the assignment of transportation requests to automated guided vehicles (AGV) in the Hamburg Harbor. A new cooperation with the Hamburger Hafen und Logistik AG has already evolved. In the current stage, the actual routing of AGVs in the harbor area is investigated within Matheon Project B8 and a BMBF project on Online AGV Routing, whereas the exact transportation requests (which AGV serves which source-destination task) are determined only heuristically. Now, we shall improve the latter component; we are asked to find an efficient policy for assigning transportation requests to AGVs such that the throughput of containers in the harbor can be improved. We will address this problem in a two-stage process. First, we will ignore the actual routing process, i.e., we assume that the routes of AGVs are fixed, and concentrate on scheduling the requests. Thereby, our experience in solving online k-server problems (Gutierrez, Krumke, Megow, Vredeveld 2006) will serve as a basis for theoretical extensions to the more complex problem of planning transportation requests. In the second stage, we combine our results for the scheduling problem (assignment of requests to AGVs) with the actual routing process. This could be done in form of an online exchange of information such as fixing arrival time windows or prioritizing tasks for the routing process, or the router may provide the exact arrival times to the scheduler and thus reduces the uncertainty in the scheduling process.

Project Output.