An efficient parallel algorithm for scheduling interval ordered tasks

DOI10.1016/S0885-064X(03)00028-1MaRDI QIDQ652455zbMATH OpenOpenAlexFDO

Authors Yoojin Chung, Kunsoo Park

Publication date 14 December 2011

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0885-064x(03)00028-1

zbMATH Keywords

parallel algorithmCREW PRAM\(m\)-processor scheduling problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 1759465
• scientific article; zbMATH DE number 512819
• Optimal scheduling on parallel machines for a new order class
• Scheduling Interval Ordered Tasks in Parallel
• Scheduling interval orders with communication delays in parallel

Cites work

• scientific article; zbMATH DE number 176752 (Why is no real title available?)
• An Almost-Linear Algorithm for Two-Processor Scheduling
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Optimal Sequencing of Two Equivalent Processors
• Optimal scheduling for two-processor systems
• Parallel Merge Sort
• Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency
• Parallel maximum matching algorithms in interval graphs
• SCHEDULING INTERVAL ORDERS IN PARALLEL
• Scheduling Interval Ordered Tasks in Parallel
• Scheduling Interval-Ordered Tasks
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• The Two-Processor Scheduling Problem is in Random NC
• The edge inducibility of graphs
• Two Processor Scheduling is in $\mathcal{NC}$

Cited in

(7)

• scientific article; zbMATH DE number 1759465 (Why is no real title available?)
• Non-preemptive profile scheduling and quasi-interval orders
• Scheduling interval orders with communication delays in parallel
• An optimal algorithm for scheduling interval ordered tasks with communication on \(N\) processors
• Scheduling with constrained processor allocation for interval orders
• scientific article; zbMATH DE number 6006722 (Why is no real title available?)
• Scheduling Interval Ordered Tasks in Parallel

This page was built for publication: An efficient parallel algorithm for scheduling interval ordered tasks

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