-
Notifications
You must be signed in to change notification settings - Fork 1
Class Documentation
- io - Input and Ouput
- scheduler - Main
- scheduler.astar - A* Branch and Bound
- scheduler.graphstructures - Graph Data Structures
- visualization.gui - GUI to hold Graph, Gannt Chart and statistics visualisation
- visualization - Graph Visualisation
- visualization.gantt - Gantt Chart Visualisation
Classes: Main
Contains a single Main class
The main entry point for the task scheduling program.
Steps taken to produce the optimal schedule
- Instantiate InputParser to parse the command line arguments.
- Instantiate OutputWriter to write to the output file.
- Instantiate DataReader to read the input file.
- If visualisation is opted for, instantiate data visualizers to display the progress and results.
- Find optimal solution for the input task graph using A* algorithm with the number of cores specified by the user (1 core if none specified).
- Use the instantiated OutputWriter to write the optimal solution to the output file.
Classes: InputParser, DataReader, OutputWriter, InputParserException
Deals with file input/output.
- Input arguments parsing and checking
- Reading in the input graph
- Outputting the optimal solution
Parses the task scheduler's command line input from the user to determine the output file name, number of processors to schedule for, number of cores to useand whether or not to provide a visual representation of the scheduling process.
- Getters are provided to obtain argument values.
- The validity of the input arguments are checked. InputParserException is thrown when an invalid argument is detected.
- Responds to the input argument
--helpand prints out the available command line options:
java -jar scheduler.jar INPUT.dot P [OPTION]
INPUT.dot a task graph with integer weights in dot format
P number of processors to schedule the INPUT graph on
Optional:
-p N use N cores for execution in parallel (default is sequential)
-v visualise the search
-o OUTPUT output file is named OUTPUT (default is INPUT-output.dot)Uses Apache Commons Cli library to parse the optional commands that starts with a dash "-" and followed by the option's alphabet.
Reads the input file and populates data structures to hold the task graph's information.
- DefaultDirectedWeightedGraph is used to represent the task graph.
Outputs the optimal schedule to a file, in the correct format.
- The initially recorded input file's information is considered when ordering of the node and edges' information in the output file.
Exception class that can be instantiated to print an error message and quit the program.
Classes: AStar, AStarParallelised, AStarThread, Processor, ProcessInfo, Solution, ListScheduler, PriorityAStarQueue
Represents a complete/partial solution.
- Provides functions to obtain properties of the solution:
- The cost function f(s) of the solution. (Refer to the AStar page for more details)
- Last finishing time among the processors represented within the solution
- Earliest possible time for a task to be scheduled on a certain processor.
-
Allows generation of new solutions based on the current solution, using free tasks, hence expanding the state space.
-
Implements the Comparable interface to allow ordering of solutions based on cost function f(s) in PriorityAStarQueue.
Solves task scheduling problem using an A* branch & bound algorithm. Refer to the AStar page for more information.
The AStar alogrithm is based off the following pseudocode:
OPEN : priority list of unexamined states
CLOSED : set of already examined states
Initialise the solution space
OPEN <= initial state
CLOSED <= Ø
Loop
Pop best state s from OPEN (with lowest f(s))
Test if s is goal state
If yes, finished
Expand s => create new states
Calculate f for states
Insert in OPEN
Insert s in CLOSED- Considers the information on the task graph and command line arguments before executing the AStar algorithm.
- Thread-safe collection classes are used to represent the OPEN and CLOSED set for concurrent accesses during parallelisation.
- PriorityAStarQueue for the OPEN set.
- CopyOnWriteArraySet for the CLOSED set.
- The data visualizers are constantly updated while the solution space is traversed.
AStarParallelised is responsible in executing instances of AStarThreads (same as the number of cores opted) which share the same OPEN set and CLOSED set. Executing multiple AStar threads allows the state space to be searched through more quickly, hence the optimal solution can be reached in a shorter time.
- Extends AStar to allow instantiation of the initial OPEN and CLOSED sets and to pass them to the AStarThreads.
- Solutions of different AStarThreads are compared when an optimal solution is reached and the best is returned.
Extends AStar and implements Runnable to allow the A* branch & bound to be executed as a thread for parallelisation purposes.
- To be instantiated and ran by AStarParallelised.
- Different from AStar in the way that the initial OPEN and CLOSED sets are obtained from the the constructor call.
- Signals other AStarThreads when an optimal solution is found to prepare for comparison of solutions.
Stores a list of ProcessInfo, which is a list of tasks ran on the processor.
- Methods are provided to query the information of the processor and the different tasks ran on the processor.
Stores information on a task's start/end time.
- ProcessInfo is used by Processor to represent the tasks ran on the processor.
Finds a possible finish time using task scheduling. The time returned is valid and can be used to set an upper bound for the A* algorithm. Refer to the AStar page for more information.
This is done by:
- Topologically sort the input graph and return a stack.
- Create a new empty solution to assign tasks to.
- Assign tasks popped from the top of the stack to a partial solution at its earliest possible start time. Since the stack is a a topologically sorted stack of tasks, the tasks being added to the solution will always have their dependencies ran.
- Return the latest finishing time among all the processors represented in the final solution.
A priority queue class that extends PriorityBlockingQueue so that the operations on the queue are thread safe.
-
add(T t)method is overriden to make sure that no duplicate states are added to the queue.
Classes: DefaultDirectedWeightedGraph, DefaultWeightedEdge, Vertex
Represent the input task graph. It contains data structures for a weighted directed acyclic graph, a directed weighted edge and a graph vertex.
The class names and methods resemble the JGraphT classes as the classes are created to replace JGraphT classes.
Represents a directed graph with weighted edges.
- Getters for many properties of the graph are provided:
- vertex and edge set
- in/out degreee of vertices
- in/out edges of vertices
- direct parents/children
- root vertices
- The graph caches the incoming and outgoing edges of all the vertices after the graph's vertices and edges are finalised, when the method to obtain them are called. This is to improve performance as the query for incoming and outgoing edges is carried out frequently.
Represents a directed weighted edge with information on source/destination vertices and weight.
Represents a task as a vertex with the following properties:
- name - Name of the task vertex as seen in the input file.
- weight - Weight of the task vertex.
- bottom level - Bottom level of the task vertex in the task graph.
- visited - Used by ListScheduler to mark vertices as visited as the digraph traversal in topological sort is carried out.
Classes: CustomBorder, CustomButton, GraphPage, Gui, Legend, StatisticTable
Classes: Visualizer, NodeClickListener
Displays task digraph on the screen. Tasks are coloured based on the processor it has been scheduled on.
Classes: Gantt, GanttChartFactory, TaskNumeric, CustomGanttRenderer, CustomIntervalCategoryGanttToolTipGenerator