Scheduling tree-structured tasks with restricted execution times

DOI10.1016/0020-0190(88)90206-2MaRDI QIDQ1111371zbMATH OpenOpenAlexFDO

Authors Joseph Y.-T. Leung, Jian-Zhong Du

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90206-2

zbMATH Keywords

multiprocessor schedulingNP-completenessNP-hardnessschedule lengthtree-structured task system

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25)

Review text

We show that scheduling a tree-structured task system with two execution times in order to minimize the schedule length is strongly NP-hard for an arbitrary number of processors. If the execution times are powers of some integer \(r>1\), then the problem is NP-hard even for two processors.

Recommendations

• Scheduling Tree-Structured Tasks on Two Processors to Minimize Schedule Length
• Scheduling trees with large communication delays on two identical processors
• Tree scheduling with communication delays
• The Complexity of Scheduling Trees with Communication Delays
• Complexity of master-slave tasking on heterogeneous trees

Cites work

• Bin packing with divisible item sizes
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3795353 (Why is no real title available?)
• NP-complete scheduling problems
• On Scheduling Independent Tasks with Restricted Execution Times
• Optimal scheduling for two-processor systems

Cited in

(8)

• Minimizing the overhead for some tree-scheduling problems
• Complexity of master-slave tasking on heterogeneous trees
• Scheduling of resource tasks
• A note on minimum makespan assembly plans
• Scheduling Tree-Structured Tasks on Two Processors to Minimize Schedule Length
• CHAIN STRUCTURES IN SCHEDULES TASKS
• Experimental and Efficient Algorithms
• Scheduling task-tree with additive scales on parallel/distributed machines

This page was built for publication: Scheduling tree-structured tasks with restricted execution times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111371)