Scheduling unit-time jobs on processors with different capabilities

Y. L. Chen, Y. H. Chin

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)409-417
Number of pages9
JournalComputers and Operations Research
Volume16
Issue number5
DOIs
StatePublished - 1989

Fingerprint

Dive into the research topics of 'Scheduling unit-time jobs on processors with different capabilities'. Together they form a unique fingerprint.

Cite this