To build an efficient metacomputer, one must assign jobs to the various networked machines intelligently. A poor job assignment strategy can result in heavily unbalanced loads and thrashing machines. A strong job assignment strategy helps a metacomputer complete all of its jobs swiftly. Resource heterogeneity makes job assignment more complex. Placing a job on one machine might risk depleting its small memory.
Bin packing on memory protects the system against thrashing.
Load balancing protects the system against high CPU loads. Combining the two approaches, however, gives an ad hoc heuristic algorithm with no clear theoretical merit. The Cost-Benefit Framework, developed in this work, offers a new approach to job assignment on metacomputers. It smoothly handles heterogeneous resources by converting them into a unitless cost. This approach gives us an online strategy provably competitive with the optimal offline algorithm in the maximum usage of each resource.