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

• Main Authors: LIN, Mei, Lin, Z.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2006
• Subjects: Grid computing; Internet resources pricing; Critical path method (CPM); Time–cost tradeoff; Heuristic algorithm; Computational complexity; Computer Sciences; Management Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/1718; http://dx.doi.org/10.1016/j.dss.2006.02.010
• Institution: Singapore Management University

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.