-
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 - Graph Visualisation
- visualization.gantt - Optimal Solution Visualisation
Classes: Main
The main entry point for the Task Scheduler program.
What it does 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.
- Find optimal solution for all the input task graphs.
while there are more graphs to read from the input file
if visualization is opted for
instantiate a Visualizer to display the graph
find optimal schedule using A* algorithm
write the optimal schedule to the output file
if visualization is opted for // under development
instatntiate a Chart to display the optimal solutionClasses: InputParser, DataReader, OutputWriter, ErrorMessenger, InputFileCorrector
Deals with file input/output.
- Input arguments parsing and checking
- Reading in the input graph
- Outputting the optimal solution
Parses the command line arguments and provide get/set methods to obtain argument values. Also checks the validity of the input arguments.
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 populate fields to hold task digraph information.
Outputs the optimal schedule to a file. It considers the initially recorded information for ordering of the node and edges in the output file.
Has a single static method which takes in an error message. The message is then printed out and the task scheduler exits.
Classes: AStar, AStarParallelised, AStarThread, Processor, ProcessInfo, Solution
Solves task scheduling problem using A* branch & bound.
Based off the following pseudocode;
OPEN : priority list of unexamined states
CLOSED : set of already examined states
Init
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 CLOSEDExtends AStar and implements Runnable to allow the A* branch & bound to be executed in different threads for multi-threading purposes.
Stores a list of ProcessInfo, which is a list of tasks ran on the processor.
Store a task's start/end time. ProcessInfo is to be stored on a Processor for tasks represented as vertices.
Classes: DefaultDirectedWeightedGraph, DefaultWeightedEdge, Vertex
Represent the input task graph. It contains data structures for weighted DAG and a weighted edge to be used by the DAG.
The class names and methods resemble the JGraphT classes as the classes are created to replace JGraphT classes.
Stores the list of tasks as vertices and the dependencies as edges. Functions are implemented to support getting in/out degree, in/out going edges and source/destination vertices of an edge.
Edge with information on source/destination vertices and weight.
Contains get/set methods to set name, weight, bottom level and touch count. the last 2 fields mentioned might not be used at all
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
(under consideration) Classes: SolutionGenerator
Creates an optimal solution using Depth First Search Branch Branch & Bound.
Based off the following pseudocode:
B <- upperBound
DFS on state space (depth until f(s) >= B):
if complete solution sc found & f(sc) < B then
B <- f(sc)Uses recursion to carry out state space search and also takes into account of bottom levels when bounding.
(in development)
Classes: Schedule, ScheduleGenerator, Sorter, VertexInfo
Performs topological sort of the task digraph.