-
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: Gui, CustomButton, GraphPage, Legend, StatisticTable
Contains classes that form the GUI to hold the graph, gannt chart and statistics visualisation
Instantiates the GUI containing the representations of the schedule in the forms of a graph and Gantt chart. It also contains a statistics table which shows relevant information about the current progress of the AStar algorithm.
- Allows the users to switch between panels which minimise a number of contents shown on the screen.
- Updates the contents regularly to keep the users informed visually.
Generates a button with the custom settings to fit the overall look an feel of the GUI.
- CustomButton extends JButton to allow customisations that cannot be set with the default JButton class.
Generates a panel to contain the graph produced by the Visualizer class.
Generates a panel containing the legend for the graph produced by the Visualizer class.
- The legend labels colours based on the processors that will be carrying out the tasks. The colour of the nodes on the graph indicates which processor a certain task is ran on.
Generates a panel containing a table with relevant information about the current AStar process:
- Number of processors being used by the computer to produce the optimal schedule
- Number of solutions created
- Number of solutions popped
- Number of solution pruned
- Amount of memory being used in megabytes (MB)
- Time since the program has started in seconds (s)
- Finish time of the current optimal solution
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
Represents a single Gantt chart. It takes in a schedule, and looks at all tasks within each processor of the schedule to generate a IntervalCatergoryDataset. Each subtask within a task-series represents a single task on a processor. It then uses the dataset to render a Gantt chart and puts in chart in a JPanel.
This class represents a Task on the Gantt chart. Since a (regular) task in a gantt chart uses java.util.Date for the start and end times, TaskNumeric instead uses integers to represent start and end time.
Creates a Gantt Chart, but the X-axis is in Integer format instead of Date format
This class extends the base GanttRenderer class but makes the following additions:
- Changes the colour of the bars
- Adds borders to each task
- Displays and formats the item labels for subtasks
- Displays tooltips for subtasks
This class extends IntervalCategoryGanttToolTipGenerator to generate tooltips for subtasks. It also changes the display format of the tooltips to correctly show integer start/end times instead of showing Dates.