Algorithm - SeanSpires/Project1-306-Team-Stonks GitHub Wiki

As decided on in the planning phase, we needed to do research on both the viable algorithms, A* and Branch-and-Bound. What we have found was that although A* can be faster if, given the correct heuristics, it can be very easy for the algorithm to go off-course. Additionally, we decided that attempting to parallelise the A* algorithm would be too time-consuming compared to parallelising Branch-and-Bound.

We initially started off by implementing a fairly simple branch and bound algorithm which develops the search and tree and does relatively simple pruning. The Branch-and-Bound algorithm which considers all possible solutions to an optimisation problem. This is done in a tree structure, where every node of the tree represents a partial solution to the problem i.e. a partial schedule. A partial solution node is expanded by adding one more stage, thereby creating the children of the node. There is one child for each possible choice. We then further expanded upon this by adding in further pruning techniques using a greedy algorithm for lower and upper bounds of partial schedules to determine potential-optimal paths. This section was heavily based on the work of M.M. Rahman (see below for link). However, the upper bound greedy algorithm encountered many issues with always finding an optimal solution.

To further our algorithm in terms of speed and validity, then we developed a new method for traversing the search space of our algorithm. Instead of using the upper and lower bound method described by Rahman, we opted to use the computational bottom level weight of a schedule (idea heavily inspired from the works of O. Sinnen, see below) in order to determine which paths are worth exploring. This increased execution time significantly as the search space was pruned efficiently and effectively. With this move, we have essentially developed a Branch and Bound A* algorithm. That is, creating the search space like a normal branch and bound algorithm, but transversing the space using heuristics(upper bound in our case) akin to A*.

Pseduo Code

 Use a Priority queue of schedules(partial or complete) ordered by lowest cost
 node = Poll lowest cost item from the queue
 IF a complete schedule, RETURN node
 ELSE
     Add item to CLOSED (nodes already seen) list
     For all unscheduled tasks t
         For all processors p
             Schedule task t on processor p
             Calculate cost of new partial schedule using COMPUTATIONAL BOTTOM LEVEL
             If partial schedule is contained in CLOSED list
                 DELETE new partial schedule
             If cost > best cost 
                 DELETE new partial schedule
             If cost < best FINISHED SCHEDULE COST && schedule is finished
                 Best cost = cost
     Add new partial schedule to the priority queue(unless deleted)
 REPEAT

Parallelisation

The parallelisation of the algorithm is done by splitting the exploration of different paths into different threads. Each thread will take a partial schedule from a shared priority queue which sorts the schedules starting from the lowest end time. If the thread decides that this partial schedule is no longer worth exploring, it will discard it and select another one from the queue. With this move, we have more threads exploring the large search space in order to find the optimal solution quicker.

Resources Used