Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

7-2008

Abstract

In this paper, we consider the problem of assisting a busy user in managing 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. A simple temporal problem with uncertainty and preferences (called an STPPU) provides a natural framework for representing the user’s current set of tasks. However, current STPPU solution techniques are inadequate as a basis for generating advice in this context, since they are applicable only in the restrictive case where all pending tasks can be accomplished within time constraints and our principal concern is support in oversubscribed circumstances. We present two techniques that are based on linear relaxation for solving the 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.

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 18th International Conference on Automated Planning and Scheduling, ICAPS 2008, Sydney, September 14-18

First Page

363

Last Page

371

Publisher

AAAI Press

City or Country

Palo Alto, CA

Additional URL

http://www.aaai.org/Library/ICAPS/2008/icaps08-045.php

Download

Share

COinS