Let J={J1,J2,...,Jn} be a set of unit execution-time jobs and P={P1,P2,...,Pm} be a set of parallel processors. Each job Ji,1•i•n, can only be run on a nonempty subset Si⊆P of processors. An assignment is said to be feasible if every job is assigned to a processor that can execute it. Let Tj denote the completion time of Pj. A feasible assignment is called balanced if and only if ℝTi-Tjℝ•1 for any i and j, where 1•i, j•m. In this paper, an O(min{n0’.5,m}mn) algorithm is first developed to determine whether a balanced assignment exists. If it exists, it can be found. If it does not, O(min{n0’.5,m}mnlog2n) algorithm is designed to find an assignment which minimizes the maximum of Tj for 1•j•m.
