fj_dag_makespan.h File Reference

Makespan of a task system with precedence constraints. More...

#include <cstddef>
#include <vector>
#include "line/api/fj/fj_types.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for fj_dag_makespan.h:

Go to the source code of this file.

Classes
struct	line::fj::FJDagMakespanResult< T >
	[C, I, Cend, E] of fj_dag_makespan. More...

Namespaces
namespace	line
namespace	line::fj

Functions
template<class T>
FJDagMakespanResult< T >	line::fj::fj_dag_makespan (const Matrix< T > &pred, const Matrix< T > &rate)
	Makespan of a task system with precedence constraints.

Detailed Description

Makespan of a task system with precedence constraints.

Templated port of matlab/src/api/fj/fj_dag_makespan.m.

Because the precedence relation is acyclic, so is the chain whose state is the SET of completed tasks, and the makespan is swept level by level instead of solved as a linear system. In a state with completed set S the eligible tasks are those all of whose predecessors lie in S; task i among the k of them completes at rate rate(i,k), so the state is held for M(S) = 1/T(S) and moves to S + {i} with probability b(S,i) = rate(i,k)/T(S). Making the rate depend on the concurrency is what couples the task system to the queueing network underneath it.

p(R) = sum_{S -> R} p(S) b(S,R), D(R) = M(R) p(R) + sum_{S -> R} b(S,R) D(S),

started at p(empty) = 1; the makespan is D at the fully completed state, and the per-task initiation and completion times accumulate over the transitions that start and that finish each task.

Definition in file fj_dag_makespan.h.