Repository navigation
Algorithm Design Decisions
While researching the different options of algorithms to implement, such as A*, DFS and BFS algorithms, a number of issues were recognized. These algorithms all require an increasingly large amount of memory space on large inputs. Furthermore, they all visited repeated states and did not provide any easy solutions for the homogeneous processor problem (all processors are equivalent so scheduling the same task partitions onto different processors is not required to be explored). As a result, this increases the amount of time required for these algorithms to solve the task scheduling problem.
More complex algorithms were researched; these were depth-first branch and bound, IDA* and AO
The depth first branch and bound algorithm was the first researched. This algorithm involved running a depth first search, adding tasks to the solution space with the inclusion of bounding techniques to remove the need to search through states which are already determined to be non-optimal.
As the algorithm progresses through the states in a depth first manner, it offers a significant reduction in memory from an A* implementation. Furthermore, the bounding techniques applied significantly increased the performance time.
However, it still has the homogeneous states issues which was addressed earlier; due to the depth-first nature, this is difficult to deal with in this algorithm.
The AO algorithm, which involves completing an allocation of tasks onto processors step, followed by ordering the tasks on each allocation, was a unique and complex algorithm. The main benefit the algorithm provided was the speed of operation on larger inputs.
This increased speed was caused by the algorithm eliminating the homogeneous processors problem, as well as reducing the number of repeated states which were looked over. AO proved to be more effective in these areas than the other algorithms in these areas. However, this required a large amount of overhead, meaning it would be inefficient for a small number of states. As the initial requirements suggested that only a small input this options was perhaps an inefficient algorithm for this particular problem.
Furthermore, there was not very much documentation for this type of algorithm on the internet, making it difficult to research further, and also making it difficult to debug and improve further.