Controllable random permutations

Tuesday, February 13, 2007 - 4:30pm
Skiles 255
Yuri Nesterov
Yuri Nesterov

In this talk, we propose a new procedure for generating random permutations. We discuss applications of this technique to some scheduling problems. In particular, we show that by applying this procedure to a single machine, it is possible to ensure a desired average completion time for every job, or to prove that this is not feasible. The parameters of the procedure can be found in polynomial time by solving a simple nonlinear convex optimization problem.

Refreshments at 4:00PM in Skiles 236