The Connected Assignment of Multiple Tasks on Homogeneous Multiprocessor Systems

A new approach to task scheduling, connected assignment, is proposed for parallel processing of multiple tasks on homogeneous multiprocessor systems. The fault-tolerant capability of a system can be increased via connected assignment without any particular hardware or software. Certain criteria for connected assignability are presented while the decision of arbitary connected assignability is shown to fall into the class of NP-complete problems. Polynomial time algorithms are given for some special types of connected assignment.