Scheduling unit-time jobs on processors with different capabilities

Y. L. Chen, Y. H. Chin

研究成果: 雜誌貢獻期刊論文同行評審

8 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)409-417
期刊Computers and Operations Research
出版狀態已出版 - 1989


深入研究「Scheduling unit-time jobs on processors with different capabilities」主題。共同形成了獨特的指紋。