School Seminars and Colloquia

A combined model for online scheduling with stochastic information (Speaker Two)

Joint ORSUM/Complex Systems Seminar

by Ms Nicole Megow

Institution: Technische Universitaet Berlin, Institut fuer Mathematik
Date: Fri 16th September 2005
Time: 1:05 PM
Location: Room 213, Richard Berry Building, The University of Melbourne

Abstract: This seminar is presented in conjunction with ORSUM, and will comprise two 1/2-hour talks:

Sequencing and scheduling is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. 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.

We introduce a general model for scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are
assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future.

The particular setting we analyze is non-preemptive parallel machine scheduling, with the objective to minimize the total weighted completion times of jobs. We propose combinatorial online scheduling policies, and derive performance guarantees that match the currently best known performance guarantees for stochastic and online parallel machine scheduling.

For More Information: Emma Lockwood tel. 8344-1617 email: