Repository navigation
Parallelisation
Upon implementing IDA Star for our task scheduling algorithm, we were quick to realise that only one thread was being used at a given instance to compute the optimal algorithm. The idea of parallelisation couldn't be applied well to IDA* so we stiched to BBA*.
On task e3.dot, a best solution would not be set sometimes by the successful thread which resulted in a NullPointer Exception in some cases. This setback led to the team figuring out alternate solutions such as the one discussed below
BBA* parallelisation works by having a parent algorithm that creates a child BBA* algorithm instance per processor for parallelisation. Each instance runs on its own thread and takes 1 lower bound value which is calculated by taking a free task and calculating its Max upper bound and its minimum lower bound. The range is then divided across the number of processors available and each thread gets allocated a 'faux' lower bound. The parent algorithm instance is like a controller which gets updated with the best cost solutions found in all children. When it gets the best cost solution, all threads terminate and the optimal solution is found.