Re: [Boost-users] graph theoretical problem

Subject: Re: [Boost-users] graph theoretical problem
From: Peter Foelsche (foelsche_at_[hidden])
Date: 2013-08-05 13:20:02

On Mon, 5 Aug 2013, Jeremiah Willcock wrote:


thanks!


> How important is a good solution compared to doing the scheduling 

> quickly? One option you may have is work stealing, which is designed


there will be many executions of the optimized graph -- of course the optimization must complete in a reasonable time

 
> for dynamic tasks being spread across threads; one implementation that 
> allows dependencies is PFunc (https://projects.coin-or.org/PFunc).  An 
> optimal solution will be hard to find, since the problem (with arbirary 
> dependencies) is NP-complete even for scheduling onto one thread.  Do 
> you have further restrictions on the dependencies (at most one 
> predecessor, at most one successor, etc.)?


no -- there might be zero or more (including more than one) predecessors or successors for every task

Peter