The solution is based on approaches suggested within the paper: Scheduling Workflows with Budget Constraints. First a HEFT algorithm is implemented and then the LOSS approach is used to validate if the current solution is not only the fastest concerning execution time, but also is within a given budget.
Phillip Häusle & Dennis Sommer
For this implementation the wikipedia article: https://en.wikipedia.org/wiki/Heterogeneous_Earliest_Finish_Time is used to structure the development.
-
As described the first step is to prioritize the tasks. Therefore the average computation and communication time is calculated. The prioritization of a task is not independent from other tasks, since some depend on conclusion of other tasks.
-
Afterwards the tasks are assigned to workers.
The Heft algorithm is done at this point and the LOSS algorithm is implemented to redistribute the tasks on the servers to obtain a solution, which stays inside the defined budget.
start index.js
function, which gets a TaskID and determines which other task it depends on. In example task 7 needs task 0 to be finished to start.
function, which gets a TaskID and determines, on which other function it is dependent on.
In example task 0 is not dependent on and task. Function will return empty array.
function, determining how much it would cost(time vise) to transfer a task from on server(worker) to another.
function, returning how long a task takes on a server (worker)
function, returns all tasks
Uses the ID of one task, to calculate its average computation cost, meaning: Gets computation time of task on each server/worker and divides it by the number of servers.
Uses the ID of one server and one task and returns the average time to transfer this task to one of the other servers.
Returns the priority of a task, therefore the averageComputationCostAmongAllNodes of the task is computed, then all tasks are took in consideration, which the task dependsOn. Now for each of these tasks the computAverageComunicationCostsAmongAllNodes is used for the task on each of the tasks it depends on. The final result consists of the max wait time on the servers since even when able to execute the task earlier it still has to wait for all other tasks it dependsOn to finish, and the servers to be free.
is the first function to be called, it prioritizes all tasks using the computePriority function.
returns if a task is completed.
Returns the true if the task can be completed successfully. Saves the server/worker, start and finish Time on Server, taskID in the result array. In consideration of dependencies of all tasks related and if they are completed.
after the tasks are prioritized the next step is to assign them to workers, for this the function assignToBestWorker is used.
returns the execution costs of a task meaning: time multiplied by cost per hour on the server.
implementation of the LossWeight algorithm from paper.
returns the server with the biggest result in concern of finished time on the server, since this is the end of the overall workflow.
implemented like described in paper page 7. Done till the part of re assigning the task to another machine.
The next step in the solution must be to: "Re-assign Task i to Machine j in S and calculate new cost of S". Seems pretty straight forward, to realize this in code is actually quite complex, since when a task is shifted to another machine, all tasks running on the machine must be rescheduled in addition to the tasks on the machine were it was shifted to.
This is were the algorithm has to be continued from, as described above.