A Decomposition-based Constraint Optimization Approach for Statically Scheduling Task Graphs with Communication Delays to Multiprocessors

Provided by: edaa
Topic: Hardware
Format: PDF
The authors present a decomposition strategy to speed up constraint optimization for a representative multiprocessor scheduling problem. In the manner of benders decomposition, their technique solves relaxed versions of the problem and iteratively learns constraints to prune the solution space. Typical formulations suffer prohibitive run times even on medium-sized problems with less than 30 tasks. Their decomposition strategy enhances constraint optimization to robustly handle instances with over 100 tasks. Moreover, the extensibility of constraint formulations permits realistic application and resource constraints, which is a limitation of common heuristic methods for scheduling.

Find By Topic