Article ID: | iaor2008736 |
Country: | Netherlands |
Volume: | 42 |
Issue: | 3 |
Start Page Number: | 1628 |
End Page Number: | 1640 |
Publication Date: | Dec 2006 |
Journal: | Decision Support Systems |
Authors: | Lin Zhangxi, Lin Mei |
Keywords: | computers: information, project management, artificial intelligence: decision support |
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 C PM 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.