Greedy Algorithms

Breadth First Search

The breadth first search algorithm will explore the entire graph and when there are no dependencies it will schedule to the first process resulting in a valid process however it wont very effecient since we arent utilizing the available processes.

public void bfs(GraphNode node){
    Queue<GraphNode> queue = new LinkedList();
    if(node != null){
        return;
    }
    queue.add(node);
    while(!queue.empty()){
        GraphNode node = queue.peek();
        queue.remove();
        // for all the outgoing edges on the current node
            // remove the depenedency from the child nodes
            // if the child node after removing has no dependencies add it to the queue
        // end for
        //schedule the current node to the first process
    }
}

Greedy Non Optimal Scheduler

Yet to be implemented this will be used however in conjunction with a possible Branch and Bound solution as an optimization to hopefully provide a better starting point for the algorithm then what could be achieved just using the left side of the schedule. This should provide us with the ability to prune solutions earlier as our greedy solution should be closer to the optimal solution then the first branch in most cases.

To come up with this greedy algorithm we decided to take the approach of looking at all given free nodes within our free set and then picking the graph which causes the schedule to cost the least after picking it. We try scheduling each node on all the possible processes which should result in a schedule that is close to the optimal.

We were able to follow a similar idea to our A* algorithm however instead of adding all the schedules that we expanded we only add the most promising schedule. This leads us to do DFS on the search tree finding the non-optimal result in a very fast period of time.

Having the greedy non-optimal scheduler allows for tighter bounds on the upper bound of our algorithm which will result in faster run time due to better pruning for our branch and bound approaches. For our A* algorithms it will result in a decreased memory usage since we will be adding less partial states to our queue.