Heuristics for Negotiation Schedules in Multi-plan Optimization

In cooperating systems such as grids [4] and collaborative streaming analysis [2], autonomous sites can establish “agreements” to arrange access to remote resources for a period of time [1]. The determination of which resources to reserve to accomplish a task need not be known a priori, because there exist multiple plans for accomplishing the same task and they may require access to different resources [3]. While these plans can be functionally equivalent, they may have different performance/cost tradeoffs and may use a variety of resources, both local and belonging to other sites. The negotiation schedule, i. e. , the order in which remote resources are negotiated, determines how quickly one plan can be selected and deployed; it also decides the utility for running the plan. This paper studies the problem of optimizing negotiation schedules in cooperative systems with multiple plans. We first provide a votingbased heuristic that reduces the complexity O(n!) of the exhaustive search to O(mnq ). We also present a weight-based heuristic that further reduces the complexity to O(mn). Experimental results show that, on average, 1) the voting-based approach achieved 6% higher utility than the weight-based approach but the voting-based approach has a much higher computation cost than the weightbased approach, 2) the two proposed approaches achieved almost 50% higher utility than a randomized approach; and 3) the average utility produced by the two proposed approaches are within almost 90% of that of the optimal results with reasonable plan sizes.

Authors

• Bo An Nanyang Technological University
• Fred Douglis
• Fan Ye

Keywords

• Optimization
• heuristics
• collaborative systems