Colóquio 

18/12/2007, 17:00 — 18:00 — Sala P12, Pavilhão de Matemática
Rhonda Righter, University of California, Berkeley

Scheduling in Highly Uncertain Environments

I consider scheduling problems that arise in web-based services, where uncertainty and variability are high, and ask the following questions. How do we deal with extreme uncertainty? How might variability increase the range of scheduling options? When does more variability help us? When is it worthwhile to do extra monitoring to collect more information (and when not)? How can we compensate for a lack of information? I address these questions for two particular Internet applications: router scheduling and computational grid scheduling. Policies specifically designed for high variability are required, and are made feasible by the nature and technology of the Internet. Such policies tend to do better when there is more variability, and they are robust in the sense that they work well for a wide range of conditions and parameters, and do not require much information.