## Abstract

Let J = {J_{1}, J_{2}, ..., J_{n}} be a set of unit execution-time jobs and P = {P_{1}, P_{2}, ..., 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_{2} n) algorithm is designed to find an assignment which minimizes the maximum of T_{j} for 1≤ j ≤ m.

Original language | English |
---|---|

Pages (from-to) | 409-417 |

Number of pages | 9 |

Journal | Computers and Operations Research |

Volume | 16 |

Issue number | 5 |

DOIs | |

State | Published - 1989 |