TY - JOUR

T1 - Scheduling unit-time jobs on processors with different capabilities

AU - Chen, Y. L.

AU - Chin, Y. H.

PY - 1989

Y1 - 1989

N2 - 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}mn log2 n) algorithm is designed to find an assignment which minimizes the maximum of Tj for 1≤ j ≤ m.

AB - 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}mn log2 n) algorithm is designed to find an assignment which minimizes the maximum of Tj for 1≤ j ≤ m.

UR - http://www.scopus.com/inward/record.url?scp=0024940507&partnerID=8YFLogxK

U2 - 10.1016/0305-0548(89)90029-4

DO - 10.1016/0305-0548(89)90029-4

M3 - 期刊論文

AN - SCOPUS:0024940507

VL - 16

SP - 409

EP - 417

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 5

ER -