An efficient parallel algorithm for scheduling interval ordered tasks

DOI10.1016/S0885-064X(03)00028-1zbMATH Open1244.68014OpenAlexW2076406733MaRDI QIDQ652455FDOQ652455

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

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

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)

Cites Work

• Optimal scheduling for two-processor systems
• Scheduling Interval-Ordered Tasks
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Optimal Sequencing of Two Equivalent Processors
• Parallel Merge Sort
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• 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
• The Two-Processor Scheduling Problem is in Random NC
• Two Processor Scheduling is in $\mathcal{NC}$
• The edge inducibility of graphs
• Title not available (Why is that?)
• Scheduling Interval Ordered Tasks in Parallel
• SCHEDULING INTERVAL ORDERS IN PARALLEL
• Parallel maximum matching algorithms in interval graphs

Cited In (7)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)