A* Implementation Algorithm

A* Algorithm

A* algorithm together with Pruning was used to find the optimal schedule in the NP-Hard problem. This algorithm used Heuristics to exhaust the search space until an optimal schedule was found. Each new partial schedule created by the algorithm was iteratively extended and then ordered according to the heuristic. A fully optimal schedule is found when the head of the queue contains a schedule that includes all tasks. see pseudocode for details

PsuedoCode

OPEN is a priority queue where ordered by Heuristic

OPEN ← initialise -> Put first node in partial schedule and add to OPEN 
while OPEN not empty
  s - > Take the first element in OPEN 
  if s complete schedule then
    return s (optimal) 
  else 
    Extend s to new states NEW 
  for all schedules s in NEW
    Calculate Heuristic for each schedule s
    Check for duplicates and then insert into OPEN
Insert s into CLOSED and remove s from OPEN