Can anybody provide me references on theorems and proofs on makespan bounds of optimally scheduled DAG for following this basic problem: assume DAG with deterministic execution time and zero communication costs have optimum (minimum) makespan Cmax,opt for unlimited number of resources (processors). Now replace any task T (execution time t) by multiple serially connected tasks T(i) with same sum execution time as the original task i.e. sum{t(i)}=t resulting in DAG' and optimum makespan C'max,opt for an unlimited number of processors. What parts of the following relation are valid: a) C'max,opt
Thank you Nguyen. Yes, correct is b). Minimum makespan for unlimited number of resources is equal to critical path (longest path) of DAG and the length of this path does not change by applying any kind of task partitioning (mentioned above) while preserving precedence constraints. I know that this is very trivial problem, however, I'm interesting on mathematical proof of this problem i.e. mathematical reasoning. In addition, I'm looking for publication where i could find collection of such trivial problems incl. proofs (e.g. the same as above but for limited number of resources, etc.)
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Publication