Cooperation in Multi-Organization Scheduling

Abstract. The distributed nature of the grid results in the problem of scheduling parallel jobs produced by several independent organizations that have partial control over the system. We consider systems composed ofÒidentical clusters ofÑ processors. We show that it is always possible to produce a collaborative solution that respects participant’s selfish goals, at the same time improving the global performance of the system. We propose algorithms with a guaranteed worst-case performance ratio on the global makespan: a 3-approximation algorithm if the last completed job requires at mostÑ�processors, and a 4-approximation algorithm in the general case.