The track "Scheduling under Uncertainty" centers on scheduling problems arising in the context of complex networks where uncertainty plays a critical role. The program features a keynote presentation by a world-renowned expert, Kirk Pruhs (Pittsburgh), along with three invited presentations by prominent researchers in The Netherlands, Marc Uetz (UTwente), Rene Sitters (VU/CWI) and Bert Zwart (CWI/Eindhoven) an on eclectic range of subjects within the overarching theme mentioned above.
A central goal of the workshop is to foster the dialogue and promote interaction between researchers in two different mathematically-oriented communities, the stochastic modeling and networking community, and the algorithms and complexity community, around scheduling as a topic of strong common interest. This ties in with the broader thrust of the NETWORKS project to forge connections at the interface of algorithmic and stochastics.
University of Pittsburgh
Energy Efficient Circuit Routing
I will discuss energy efficient circuit routing protocols for a network of components that are speed scalable, and that may be shutdown when idle. I will initially concentrate on the case that the power management componentsare links. I will give a polynomial-time offline algorithm that has apoly-log approximation ratio.
This algorithm is a combination of three natural combinatorial algorithms. The key step of the algorithm design is a random sampling technique that we call hallucination. The algorithm extends rather naturally to an online algorithm.
The analysis of the online algorithm introduces a natural "priority"multicommodity flow problem, and bounds the priority multicommodity flow-cut gap.
I will then briefly explain the additional difficulty faced if the powermanagement components are vertices, and explain how to how to surmount thisdifficulty in the offline case.
Several models have been proposed to handle uncertainty in the area of scheduling. In this lecture, we focus on stochastic scheduling, where processing times are modelled as random variables. This leads to intriguing combinatorial optimization problems with sometimes counterintuitive phenomena. For example, optimal scheduling policies might require to deliberately leave machine capacity idle. The lecture gives a mild introduction into the stochastic scheduling model. We then focus on the efficient computation of scheduling policies with provable guarantees on the expected performance. It turns out that much of the work that has been done for non-stochastic problems can -with some extra work- be carried over to the more general stochastic setting. The lecture will give one example of such a policy: We show how to derive a performance bound for a very simple greedy algorithm using a primal-dual framework. Both algorithm and analysis even even hold in the setting where an unknown stream of jobs arrives online. Some open problems in this area will be highlighted, too.
CWI Amsterdam /Vrije Universiteit Amsterdam
Scheduling over scenarios
The problem of scheduling over scenarios appears in settings where scenarios change frequently while frequent changes in the schedule are not desired or even impossible. Examples are found in vehicle routing and manufacturing.
In this model, the goal is to compute a single, a-priori schedule that performs well over a set of possible scenarios. A (first-stage) schedule needs to be constructed before it is known which scenario will take place. Once the scenario is known, the final (second-stage) schedule should be similar to and easy to derive from the first-stage schedule. For example, each scenario may be a set of jobs and the first-stage schedule is an assignment of the jobs to machines while the final schedule is just the first-stage assignment restricted to the jobs in the scenario. The objective may be to minimize the worst-case cost or the expected cost of the final schedule. Another example is the a-priori traveling salesman problem. Each job is a point to be visited and scenarios are subsets of points. A first-stage solution is a tour on all points and the solution for a scenario is obtained by shortcutting the first-stage tour on the points in the scenario.
CWI Amsterdam/Eindhoven University of Technology
Scheduling queues in heavy traffic
We are interested in scheduling policies for the GI/GI/1 queue where we wish to minimize the average sojourn time. It is well-known that this objective is minimized by the Shortest Remaining Processing Time (SRPT) policy; however, this policy needs to know all job sizes upon arrival in the system. If this information is not available then the server needs to resort to so-called blind policies.
Naturally, we now wonder which blind policy to choose in order to perform as good as possible, and how big the performance gap is when compared to the SRPT policy. This talk addresses these two questions and presents a known blind policy that is (in some sense) optimal. The proof of this result displays a promising hybrid of competitive analysis and applied probability techniques.
In the last part of this talk we examine the scheduling discipline FB in more detail. While traditional heavy traffic behaviour is governed by central limit theorems, we illustrate that ideas from extreme value theory play a key role in the analysis of size-biased disciplines.
(joint work with Nikhil Bansal and Bart Kamphorst)