Linear Relaxation Techniques for Task Management in Uncertain Settings

Speaker: Pradeep Varakantham (http://www.cs.cmu.edu/~pradeepv/)Abstract:In this work, we consider the problem of assisting a busy user in managing his/her workload of pending tasks. We assume that our user is typically oversubscribed, and is invariably juggling multiple concurrent streams of tasks (or work flows) of varying importance and urgency. There is uncertainty with respect to the duration of a pending task as well as the amount of follow-on work that may be generated as a result of executing the task. The user's goal is to be as productive as possible; i.e., to execute tasks that realize the maximum cumulative payoff. This is achieved by enabling the assistant to provide advice about where and how to shed load when all tasks cannot be done. We present two techniques that are based on linear relaxation for solving this oversubscribed problem. Given an ordering of tasks, these algorithms identify which tasks to ignore, which to compress and by how much, to maximize quality. We show experimentally that our approaches perform significantly better than techniques adapted from prior research in oversubscribed scheduling.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia