A Cost-Effective Critical Path Approach for Service Priority Selections in a Grid Computing Economy

Publication Type

Journal Article

Publication Date

2006

Abstract

The increasing demand for grid computing resources calls for an incentive-compatible pricing mechanism for differentiated service qualities. This paper examines the optimal service priority selection problem for a grid computing services user, who is submitting a multi-subtask job for the priced services in a grid computing network. We conceptualize the problem into a prioritized critical path method (CPM) network, identify it as a time–cost tradeoff problem, and differentiate it from the traditional problem by considering a delay cost associated to the total throughput time. We define the optimal solution for the prioritized CPM network as the globally cost-effective critical path (GCCP), the optimal critical path for the solution that minimizes the total cost. As the exponential time complexity of GCCP makes the problem practically unsolvable, we propose a locally cost-effective critical path (LCCP) based approach to the prioritized CPM problem with a heuristic solution. The locally optimized priority constituting the configuration for LCCP can provide a lower bound for the throughput time of GCCP with the same time complexity as that for a traditional CPM problem. To further improve the quality of the solution, we conceive a priority adjustment algorithm named Non-critical Path Relaxation (NPR) algorithm, to refine the priority selections of the nodes on the non-critical paths. A discussion of the effects of the users' priority selections on the grid network pricing is provided to elicit future research on the computing resource pricing problem on the service-side.

Keywords

Grid computing, Internet resources pricing, Critical path method (CPM), Time–cost tradeoff, Heuristic algorithm, Computational complexity

Discipline

Computer Sciences | Management Information Systems

Research Areas

Information Systems and Management

Publication

Decision Support Systems

Volume

42

Issue

3

First Page

1628

Last Page

1640

ISSN

0167-9236

Identifier

10.1016/j.dss.2006.02.010

Publisher

Elsevier

Additional URL

http://dx.doi.org/10.1016/j.dss.2006.02.010

Link to Full Text

Share

COinS