A Cost-Effective Critical Path Approach for Service Priority Selections in a Grid Computing Economy
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.
Grid computing, Internet resources pricing, Critical path method (CPM), Time–cost tradeoff, Heuristic algorithm, Computational complexity
Computer Sciences | Management Information Systems
Information Systems and Management
Decision Support Systems
LIN, Mei and Lin, Z..
A Cost-Effective Critical Path Approach for Service Priority Selections in a Grid Computing Economy. (2006). Decision Support Systems. 42, (3), 1628-1640. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1718