Optimization Problem

GIVEN:

An arbitrary workflow, i$.$e$.$ directed acyclic graph $($DAG$)G=(V,E),$ where each node $v$ is a job

and each directed edge $(u,v)$ shows that the output data of job $u$ is transferred as the input data of

job $v,K$ homogeneous machines, the execution time $t(v)$ of each job running individually on a

single machine, and the communication time $t(u,v)$ of each data transfer between jobs $u$ and $v$

running in different machines.

QUESTION:

Find the minimum execution time of the entire workflow along with a feasible schedule mapping

all the jobs onto no more than $K$ machines.

Submission

Project report $($in a PDF$)$

$(10$ points$)$ a$.$ Prove the problem's computational complexity of the assigned problem;

$(20$ points$)$ b$.$ Design and describe an efficient $($exact$/$approximation$/$heuristic$)$ algorithm;

$(10$ points$)$ c$.$ Analyze your algorithm's time complexity;

$(10$ points$)$ d$.$ Show the execution results $($including the input instance and the output of the job

schedule and its workflow execution time$)$ of your source code on two different cases, one with

no less than $9$ jobs and $3$ machines and the other with no less than $16$ jobs and $4$ machines

$(10$ points$)$ e$.$ Plot the average execution time of $20$ randomly generated workflow instances for

each triple over different numbers of jobs $\{100,200,300,400\},$ different numbers of data

dependencies $\{400,500,600\},$ and different numbers of machines $\{2,4,8\}.$

Source code $($compressed in a ZIP file$)$

$(40$ points$)$ Implement the designed algorithm $(\frac{C}{C}++$ in Linux with Makefile is required$).$

$(25$ points$)$ Bonus: Design $(1.$b$)$ and implement $(2)$ the second algorithm, analyze $(1.$c$)$ its

efficiency, and compare the optimality of these two algorithms according to the simulation

results for the same workflow instances $(1.$e$).$

Evaluation

The correctness of the problem's computational complexity analysis

The optimality and efficiency of the designed algorithm and clearness of algorithm description

to solve the optimization problem.

The correctness of your algorithm's time complexity analysis

The correctness of your implementation corresponding to your algorithm

Your code readability $($such as code format and necessary comments$)$