A* Algorithm

The A* algorithm is designed to look at the best current schedule first. By this, we need to be looking at the most promising current schedule which is determined by the cost of the schedule plus a heuristic to order the queue of current schedules so that in our average case we can limit our search space. This would in the ideal case result in a search in our search space where we would be looking at the minimal number of possible solutions.

public ISchedule AStar(IGraph graph){
    // new priority queue with a the heuristic as the comparator
    // add the empty state to the queue
    // while true
        // take the top of the queue
        // if the number of nodes scheduled in the queue is the same as the number of nodes in the graph
            //return the scheudle as the optimal solution
        // for all nodes which can be scheduled
            // for all the processes which we have available
                //add to the priority queue a new schedule with node added as soon as possible on the same processes
}

We will implement custom heuristics to better track future costs which will allow us to reduce the search space even further than the base hueristic of the current cost. This will result in faster output of the schedule.