Monday, July 2, 2012
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Uncertainty is prevalent in real-world scheduling problems. Jobs may take more or less time than originally estimated, resources may be unreliable and slow down or become completely unavailable, material may arrive late, new jobs may have to be incorporated or others may be dropped, etc. In this talk I will give an overview on different models, algorithms, and performance measures for scheduling under uncertainty. The methods for obtaining provably good solutions involve linear programming, priority indices borrowed from probability theory, the doubling technique, and some geometry. I will also discuss recent approaches on obtaining robust schedules, in particular, universal solutions for unreliable machine behaviors.
Colloquium - 16:00
Abstract:
We consider the problem of scheduling the maintenance of the links of a network in such a way that the total disruption of the connections in the network are minimized.
This problem is motivated by an application in telecommunications: Given an optical network consisting of fiber links and switching nodes, a set of established communication paths in the network, and a discretized planning horizon, the task is to decide when to upgrade the WDM transmission technology of each link. Upgrading a link requires several technicians, and the number of technicians available per period is limited. Since the old and the new technology are incompatible, a communication path will be disrupted from the period when its first link is replaced until the period when all its links are replaced. The objective is to minimize the total time that the given communication paths are disrupted.
We present two integer linear programming formulations for this problem, discuss its relation to the linear arrangement problem and the complexity of some special cases, and finally report on computational results for some real world instances.
Joint work with Daniel Karch.