Balancing risk and reward in a market-based task service


Journal Article

This paper investigates the question of scheduling tasks according to a user-centric value metric - called yield or utility. User value is an attractive basis for allocating shared computing resources, and is fundamental to economic approaches to resource management in linked clusters or grids. Even so, commonly used batch schedulers do not yet support value-based scheduling, and there has been little study of its use in a market-based grid setting. In part this is because scheduling to maximize time-varying value is a difficult problem where even simple formulations are intractable. We present improved heuristics for value-based task scheduling using a simple but rich formulation of value, in which a task's yield decays linearly with its waiting time. We also show the role of value-based scheduling heuristics in a framework for market-based bidding and admission control, in which clients negotiate for task services from multiple grid sites. Our approach follows an investment metaphor: the heuristics balance the risk of future costs against the potential for gains in accepting and scheduling tasks. In particular, we show the importance of opportunity cost, and the impact of risk due to uncertainty in the future job mix.

Full Text

Duke Authors

Cited Authors

  • Irwin, DE; Grit, LE; Chase, JS

Published Date

  • October 18, 2004

Published In

Start / End Page

  • 160 - 169

International Standard Serial Number (ISSN)

  • 1082-8907

Digital Object Identifier (DOI)

  • 10.1109/HPDC.2004.1323519

Citation Source

  • Scopus