Scheduling Tree-Structured Tasks on Two Processors to Minimize Schedule Length | Zendy

Jianzhong Du | Zendy; Joseph Y.T. Leung | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Scheduling Tree-Structured Tasks on Two Processors to Minimize Schedule Length

Author(s) -

Jianzhong Du,

Joseph Y.T. Leung

Publication year - 1989

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/0402016

Subject(s) - scheduling (production processes) , schedule , generalization , computer science , mathematics , combinatorics , tree (set theory) , parallel computing , discrete mathematics , algorithm , mathematical optimization , operating system , mathematical analysis

Consider a set of n tasks with a tree-structured precedence relation and execution time of 1 or 3 units. We give an $O(n^2 \log n)$-time algorithm to find a minimum length schedule for these tasks on two identical processors. Possible generalization to the case of 1 or k units is also given.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research