Scheduling unit-time jobs on processors with different capabilities

Let J = {J₁, J₂, ..., J_n} be a set of unit execution-time jobs and P = {P₁, P₂, ..., P_m} be a set of parallel processors. Each job J_i 1 ≤ i ≤ n, can only be run on a nonempty subset S_i ⊂- P of processors. An assignment is said to be feasible if every job is assigned to a processor that can execute it. Let T_j denote the completion time of P_j. A feasible assignment is called balanced if and only if |T_i - T_j|≤ 1 for any i and j, where 1 ≤ i, j ≤ m. In this paper, an O(min{n^0.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{n^0.5, m}mn log₂ n) algorithm is designed to find an assignment which minimizes the maximum of T_j for 1≤ j ≤ m.