Scheduling under uncertainty

(Leen Stougie, Dept. of Operations Research, Vrije Universiteit Amsterdam & CWI Amsterdam)

Waaier 4, 12:15 – 13:00

Scheduling problems belong to the classical problems in combinatorial optimisation. Traditionally, especially by combinatorial optimisation researchers, deterministic variations of scheduling problems have been studied. Over the past half century this has led to an overwhelming body of research results, even if we concentrate on the scheduling results related to computational complexity theory, as we do in this lecture.

From a practical point of view however, scheduling problems do usually not appear with all input data known. Usually there is uncertainty about the processing times of jobs, machine availability, etc. We will present various ways for modelling uncertainty in scheduling, which can be viewed as a guide to modelling uncertainty in any combinatorial optimisation problem.

We will treat stochastic scheduling, a stochastic programming approach to scheduling (which is quite different from stochastic scheduling), on-line scheduling, robust scheduling, and universal scheduling, everything in the context of computational complexity. Of all models mathematical results on specific scheduling examples will be given. Time permitted, I will present a resent result on a universal scheduling problem.

In universal scheduling we take into account that machines might not be available for preventive maintenance, they may slow down due to simultaneous utilization by other users, they may break down completely for some time, etc.; i.e., unavailability is unpredictable. Thus the quest for a schedule that is robust against machine calamities emerges: the only influence the scheduler has is on the order in which he offers his jobs to be processed. We analyze the worst case performance of algorithms on this problem by comparing the solution value provided by an algorithm with that of an optimal clairvoyant algorithm that knows the machine behavior in advance, and that is even allowed to preempt jobs at any time.

Leen Stougie (PhD 1985 at Erasmus Universiteit Rotterdam) is full professor in Operations Research at the Vrije Universiteit Amsterdam and researcher at CWI in Amsterdam. Leen has previously worked at the TU Eindhoven and at the University of Amsterdam. His research area is in Discrete Optimization, with applications among others in Computational Biology.