-
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 and Statistics Table
- visualization.graph - Graph Visualisation
- visualization.gantt - Gantt Chart Visualisation
Solution and Schedule are used interchangeably throughout this documentation.
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
Represents a complete/partial solution.
- Provides functions to obtain properties of the solution:
- The cost function f(s) of the solution. (Refer to the A* 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 PriorityBlockingQueue.
Solves task scheduling problem using an A* branch & bound algorithm. (Refer to the A* page) for more details)
- Considers the information on the task graph and command line arguments before executing the AStar algorithm.
- PriorityBlockingQueue for the OPEN set. It's thread-safe for concurrent popping from when parallelised A* is run.
- HashSet for the CLOSED set.
- The data visualizers are constantly updated while the solution space is traversed.
AStarParallelised is responsible for parallelising AStar. It does this by 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. (Refer to the A* page's Parallelisation part) for more details)
Steps taken to parallelise A*
- Initialise the OPEN and CLOSED sets with an empty schedule in the OPEN set.
- Initialise AStarThreads with the same OPEN and CLOSED sets(same as the number of cores opted).
- Start the AStarThreads.
- Wait for all the AStarThreads to finish.
- Compare their optimal solutions and return the best one as the optimal solution.
Extends AStar to allow instantiation of the initial OPEN and CLOSED sets and to pass them to the AStarThreads.
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.
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 A* page) for more details)
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.
An exception that is used (thrown) in the Solution class to determine if a vertex's dependencies have been scheduled.
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 table 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
StatisticTable is updated in AStar as the algorithm progresses
Classes: Visualizer, NodeClickListener
Uses GraphStream library to visualize the input graph.
Displays task digraph on the screen. Tasks are coloured based on the processor it has been scheduled on. Unscheduled tasks are black.
- The graph is styled with a CSS stylesheet represented as a String.
Visualizer is updated in AStar as the algorithm progresses
Listener to handle click of graph nodes, so that task node specific information can be displayed to user on demand:
- Task name
- Which processor the task is scheduled on
- Start time on the processor
- End time on the processor
Classes: Gantt, GanttChartFactory, TaskNumeric, CustomGanttRenderer, CustomIntervalCategoryGanttToolTipGenerator
Contain the classes required to visualize a Gantt chart of the schedules (partial/optimal solution). The Gantt chart will look similar to the chart used by the client's technician to visualize the solution.
Uses JFreeChart library to make the Gantt Chart.
The documentation for the following package might not make much sense if you're referring to the code because of the terminologies of a Gantt chart. In this package, Task is used to represent a collection of tasks and SubTask is used to represent a task. This documentaion plans to simplify the understanding of the classes and so will stay consistent with the other packages.
Represents a single Gantt chart. It takes in a schedule, and generates a dataset. The dataset is then used to render a Gantt chart which will be put into a JPanel.
Gantt is updated in AStar as the algorithm progresses
This class represents a collection of tasks on the Gantt chart.
- Normally, in a gantt chart, Date is used for the start and end time, 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 renders the Gantt chart by extending the base GanttRenderer class to make the following additions:
- Changes the colour of the bars
- Adds borders to each task
- Displays and formats the item labels for tasks
- Displays tooltips for tasks
This class generates tooltips for tasks. It also changes the display format of the tooltips to correctly show integer start/end times instead of showing Dates.