Consider a finite network of workstations of varying speeds. Consider also a finite set of tasks and a normalized execution time associated with each task. The task interaction graph has one node for each task, and has an edge between two nodes if the corresponding tasks communicate during execution. If two tasks do communicate, then the time spent on interprocessor (or intraprocessor) communication is also specified and labels the corresponding edge. This paper considers the problem of allocating the tasks to the workstations so that the total medium access time is minimized; this total is a sum of interprocessor communication times scaled by a waiting time to access the network. The allocation is successful if the overall elapsed time (the maximum of the job completion time and the medium access time), the number of workstations allocated, and the accumulated load (the sum of elapsed time in all the workstations) are all minimized.

Since the problem is NP-complete, and in fact is equivalent to bin-packing, even when all the workstations are assumed to have the same speed (homogeneity), all communication times are zero, and waiting time is zero, there is no polynomial-time allocation algorithm. The authors provide and prove an algorithm under the assumptions of zero waiting time, homogeneity, and an unbounded number of workstations. They then construct a heuristic algorithm based on this algorithm and report on its experimental success on a large sample of task interaction graphs.