Load balancing in parallel and distributed processing of tree-based multiple-task jobs

The efficient processing of tree based multiple task jobs arriving in batches to parallel and distributed systems is presented. This type of processing can be found in such application fields as, for example, automatic diagnostics and document recognition. A key management issue in such systems is task allocation. Load balancing is often proposed as the task allocation approach. The load balancing algorithms are employed to improve the throughput of the system by distribution of the incoming workload evenly among the processors in the system. The problem-specific static algorithms as well as general dynamic load balancing algorithms have been developed for supporting batch processing of tree based multiple task jobs. The proposed algorithms have been studied through simulation. Prescheduling load balancing algorithms have been evaluated as superior to other algorithms investigated