A cost-effective critical path approach for service priority optimization in the grid computing economy

The advancement in the utilization and technologies of the Internet has led to the rapid growth of grid computing; and the perpetuating demand for grid computing resources calls for an incentive-compatible solution to the imminent QoS problem. This paper examines the optimal service priority selection problem that a grid computing network user will confront. We model grid services for a multi-subtask request as a prioritized PERT graph and prove that the localized conditional critical path, which is based on the cost-minimizing priority selection for each node, sets the lower bound for the length of cost-effective critical path that commits the optimal solution. We also propose a heuristic algorithm for relaxing the nodes on the non-critical paths with respect to a given critical path.