An efficient parallel algorithm for scheduling interval ordered tasks

DOI10.1016/S0885-064X(03)00028-1zbMath1244.68014OpenAlexW2076406733MaRDI QIDQ652455

Yoojin Chung, Kun Soo 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) Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency
• Optimal scheduling for two-processor systems
• The Two-Processor Scheduling Problem is in Random NC
• Two Processor Scheduling is in $\mathcal{NC}$
• Parallel Merge Sort
• Scheduling Interval-Ordered Tasks
• The edge inducibility of graphs
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Scheduling Interval Ordered Tasks in Parallel
• SCHEDULING INTERVAL ORDERS IN PARALLEL
• PARALLEL MAXIMUM MATCHING ALGORITHMS IN INTERVAL GRAPHS
• Optimal Sequencing of Two Equivalent Processors

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