A stochastic model of statically assigning tasks to homogeneous processors that exploits the theory of majorization is considered.
Each task consists of a tree of subtasks: upon completion of the root subtask, a random number of next-generation subtasks is generated. Each of these may generate new tasks in the same manner. The number of subtasks and the execution time of each subtask are random. All tasks and subtasks behave identically with respect to execution time and the number of new subtasks generated.
Execution may be synchronized: either a subtask is not executed before all subtasks of the previous generation are finished, or only the completion of all subtasks is awaited. Either each tree of subtasks is assigned statically to one of the processors, or a large number of processors is shared, allowing for parallel processing.
The results are theorems with statements of the following type. With respect to a class of objective functions, two assignments are compared, stating that one of them is not worse than the other. Optimal assignments are obtained. The objective functions are Schur-convex [1] or symmetric in all arguments. The theory is applied to finishing time, functions of queue length, reliability, and parallel processing using many processors.
The limitations of the developed theory are as follows. The assignment is static, the tasks and subtasks must behave identically, only special kinds of synchronization are considered, and the processors are homogeneous. The strength of the theory is the generality of the covered objective functions and the fact that optimal assignments can be identified even when constraints must be taken into account that may be different for different processors.