Repository navigation
Algorithms
Algorithms are methods of searching the state space. They are given a graph and a number of processes, and produce a valid schedule containing all nodes of the graph. Multi-threading of algorithms revolves around running new algorithms in different threads.
A BoundableAlgorithm is one that can be run on a subsection of a graph. It is mainly defined by the new run method of:
public abstract void run(Graph graph, Schedule schedule, HashSet<Node> nextNodes);
which means the algorithm may start on an already partially filled schedule, and the MultiAlgorithmCommunicator (TODO: Link) that the algorithm is given in it's constructor. The communicator is used to notify for when a boundable algorithm has created as much of a schedule as it wants to, and also handles shared information between all separately running boundable algorithms.
An implementation of the basic depth first search, which will recursively visit partial solutions. Partial schedules are only "valid" to explore if they are not pruned by a heuristic, or if their lower bound is higher than the time of our current best estimate.
As an optimising technique, all partial schedules are visited in ascending order of lower bounds. At each step of the recursion the partial schedule with the lowest lower bound will be explored, as myopically this is our best guess at which partial schedule will produce an optimal schedule. This greedy logic helps to speed up the discovery of an optimal schedule. The use of our custom heuristics greatly improved our implementation of DFS. The ability to cull partial schedules if they were more inefficient than or equivalent to those we had already visited meant we were able to greatly decrease the size of our search space.
DFS on average runs slightly more slowly than our implementation of A* which is why we do not preferentially use a pure implementation of DFS as our default algorithm. Though slower, DFS is still useful in our overall scheduling algorithm as it is able to determine optimal solutions from partial schedules without running into the memory problems associated to A*.
An implementation of the breadth-first search based algorithm. Starting from a given schedule, the algorithm will analyze all the possible tasks that can immediately be added to that schedule. If our heuristic and lower bound functions suggest a schedule should be further explored, it will be added to the queue of partial schedules to explore. Partial schedules are explored based on their lower bound estimates, those with the lowest estimates are explored first. The algorithm will return when it generates a schedule with all nodes added. It will only reach such a schedule when the said schedule is optimal.
Due to our algorithm design, the elements we wanted stored in our queue included a partial schedule, it's associated lower bound estimate and a list of the nodes that could next be added to the schedule. The most pivotal part of this was ensuring elements were sorted by ascending order of lower bound estimates, ie we wanted the schedule with the lowest lower bound estimate at the head of the queue at all times. Built-in Java structures could not provide us with this desired functionality so our own PriorityQueue - PackedScheduleQueue, was implemented. In this queue we maintained three lists, one for schedules, lower bounds and the next available nodes. Elements were sorted by ascending lower bounds. The method of adding an element to our custom priority queue implementation is as follows:
public void add(int lowerBound, SimpleSchedule schedule, HashSet<Node> visitableNodes)
All entries were related by their index position. Returning data at the head of the queue required accessing the elements at the front of all three lists, then removing this data - this is equivalent to the alternative poll() method from the Java.util.PriorityQueue class. The sorting of the three lists depends on the sorting of the list of lower bounds, elements were inserted into the queue structure using a binary search implementation.
As the multiprocessing task scheduling problem space scales as a factorial, the queue of potential schedules to explore in A* can grow significantly in size and can quickly cause memory problems for large input graphs. To take this into account we have implemented custom exit statements in the A* which are triggered if it is running low on memory. If the algorithm has less than 512Mb of available space, it will pass functionality to DFS. DFS will analyze the schedule currently at the front of A*'s priority queue and return the end time of the best schedule it could generate from the input partial schedule. At this point, control will only return to A* if it is no longer out of memory, otherwise, DFS will continue to take elements from the priority queue until an optimal schedule is found.
Our profiling suggests our A* implementation runs on average about 25% faster than our DFS for most graph types. For this reason, we have chosen to use A* as our core algorithm.