-
Notifications
You must be signed in to change notification settings - Fork 1
Home
- io - Input and Ouput
- scheduler - Main
- scheduler.astar - A* Branch and Bound
- scheduler.topologicalsort - Topological Sort
- scheduler.dfsbranchandbound - DFS Branch and Bound
- scheduler.graphstructures - Graph Data Classes
- visualization - Graph Visualisation
- visualization.gantt - Optimal Solution Visualisation
- Packages - names should be lower case only, subsequent words are just appended to the end, e.g. helloworld
- Classes - use CamelCasing for names, starting with UPPER case
- Methods - use camelCasing for names, starting with lower case
- Variables - use camelCasing for names, starting with lower case
- Fields - put underscore ( _ ) before variable names
- Getters and setters are not covered
- Only fields and functions requiring explanations are covered
The main class for Task Scheduler.
What it does to produce the optimal schedule
- Instantiate InputParser to parse the command line arguments.
- Instantiate OutputWriter to write to the output file, with an output file name.
- Instantiate DataReader to read the input file, with a file name.
- Find optimal solution for all the task graphs in the input file.
while there are more graphs in the file read
if visualization is opted for
instantiate a Visualizer to display the graph
start timing
solve the graph and find optimal solution using A* algorithm, taking into account input arguments
stop timing and print out time taken
if visualization is opted for
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.
Usage:
new InputParser(command line arguments).parse()
and then use the get/set methods
Reads the input file and populate fields to contain task information. A DefaultDirectedWeightedGraph is created in the process.
Usage:
DataReader dataReader = new DataReader(input graph file name)
to read graph(s) from the input file
dataReader.readNextGraph()
to read the next graph in the input file and store the tasks' properties in fields that can be accessed with get/set methods
Fields:
ArrayList<String> _verticesAndEdgesInfo
Record vertices and edges in the order of reading, so that the output solution can have the same ordering.
ArrayList<String> _verticesAndEdgesRead
Same as _verticesAndEdgesInfo except that edges are recorded as ">". It is used alongside _verticesAndEdgesInfo. The edges, identified by ">" can be printed out by OutputWriter from _verticesAndEdgesInfo, without adding extra attributes.
Outputs the optimal schedule to a file. It considers the initially recorded information for ordering of the node and edges and also the the optimal Solution.
Usage:
OutputWriter outputWriter = new OutputWriter(output file name)
To initialise the OutputWriter
outputWriter.initialise()
To create the file for output
outputWriter.createSchedule(...)
To output the optimal schedule to a file. Uses the _verticesAndEdgesInfo and _verticesAndEdges from dataReader.
Has a single static method which takes in an error message. The message is then printed out and the task scheduler exits.
Usage: ErrorMessenger.reportError(errorMessage)
Corrects input digraph files found on Oliver's website. might wanna confirm input file format from client since graph 10 provided by technician is not in a valid format
Usage:
- Run the class in Eclipse.
- Set the values at the top of the main method,
-
int fromFileandint toFileindicate the range of files requiring correction, assuming files have numbers as names. -
int fromLineandint toLineindicate the range of the code lines that needs to be deleted to achieve correct input format.
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 CLOSEDUsage:
AStar aStar = AStar(task digraph, no. of processors, visualizer)
Take in the task digraph to solve along with the number of processors it will run on and a Visualizer to update
runSequentially()
Checks if the scheduling is to be done sequentially. To be further implemented
aStar.execute()
Executes A* branch & bound.
getBottomLevel(task vertex)
Uses recursion to return a task's bottom level.
Fields:
PriorityQueue<Solution> _solutionSpace
To store partial schedules, prioritised based on a cost function.
Set<Solution> _closedSolutions
To store closed partial schedules. Useful for bounding.
Stores a list of ProcessInfo, which is a list of tasks ran on the processor.
Usage:
Processor processor = new Processor()
initialise a processor with no tasks ran on it
processor.createDeepCopy()
create a deep copy of processor and return it, as in the new copy contains entirely new ProcessInfo references and not just pointers to the original ones
processor.getTime() and processor.earlistNextProcess()
return the earliest possible start time for the next process
processor.getProcess(task vertex)
return ProcessInfo corresponding to the task, so that further information of task on the processor can be obtained
processor.idleTime()
checks to see how long the processor has been idle states for
Store a task's start/end time. ProcessInfo is to be stored on a Processor for tasks represented as vertices.
Usage:
new ProcessInfo(task vertex, start time)
Stores start and end time for a vertex. End time is computed by adding task weight to start time.
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.
Usage:
DefaultDirectedWeightedGraph dag = new DefaultDirectedWeightedGraph()
to create the empty digraph, get/set methods are then used to populate it
dag.addEdge(source vertex, destination vertex, edge weight)
to add an edge by specifying its properties
Edge with information on source/destination vertices and weight.
Usage:
DefaultWeightedEdge edge = new DefaultWeightedEdge(source vertex, destination vertex, edge weight)
to return a weighted directed edge
edge.contains(vertex)
to check if a vertex is part of an edge
Contains get/set methods to set name, weight, bottom level and touch count. the last 2 fields mentioned might not be used at all
Usage:
new Vertex(task name)
and use get/set methods to set fields
Classes: Visualizer
Displays task digraph on the screen. Tasks are coloured based on the processor it has been scheduled on.
Usage:
Visualizer visualiser = new Visualizer
Internally creates a graph for display and also set various properties of the graph such as the stylesheet
visualizer.add(task digraph)
Set the digraph for display by adding the nodes and edges from the digraph to the internal graph which is the one that is displayed. Additional CSS properties are added to the nodes to distinguish roots, leaves and the intermediate nodes.
visualizer.displayGraph()
Display the internal graph onto the screen. Action listerners to mouse actions are to be implemented. fromViewer.addSink(_graph) in the end is for listening to _graph events
visualizer.updateGraph(current best solution)
Change the colour of nodes displayed based on the processor they are on for the current best solution. Different processors' scheduled tasks' nodes will have different colours. Unscheduled tasks will be black.
visualizer.getColor(processor number)
Gets a color value based on the processor. might wanna consider possibility of exceeding 13 processors, like adding a random colour generator
Fields:
String stylesheet
stylesheet for the graph, CSS information on the graph, its edges and its nodes
Classes: Gantt, GanttChartFactory, TaskNumeric
Displays a gantt chart for a solution.
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.
Classes: Schedule, ScheduleGenerator, Sorter, VertexInfo
Performs topological sort of the task digraph.