'Trace the algorithm : Graph theory problem
Graph theory Algorithm problem
Consider a set of, say p single-core processors which have been assigned q programs is given along with: – start times for the programs – end times for the programs – Total processing time to complete a program Programs can be stopped, restarted, and moved between processors without any penalty. i. Device an algorithm to schedule the running of programs on processors such that the deadlines are met. ii. Trace the algorithm for a set of values of your choice
I don't know which algorithm to use bellman-ford or floyd warshall or ford-fulkerson or dijksta's or kruskal's or prim's algorithm.
What algorithms could be used here, and what would be the correct way to formulate this problem using graph theory language?
Solution 1:[1]
You can use Dijkstra to find the critical path, if you set the edge costs to the reciprocal of the task duration. Then always choose to run a ready task if it is on the critical path, otherwise choose a non critical task at random.
This is the bare bones of the algorithm. Lots of details to sort out. You can see all the details at https://github.com/JamesBremner/TaskGraphScheduler
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | ravenspoint |