-
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
Classes: Main
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.
- 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.
Usage:
new InputParser(command line arguments).parse()
Use the get/set methods to obtain the arguments
Reads the input file and populate fields to hold task digraph information.
Usage:
DataReader dataReader = new DataReader(input graph file name)
Read graph(s) from the input file.
dataReader.readNextGraph()
Read the next graph in the input file and store the tasks' properties in fields that can be accessed with get/set methods.
Fields:
DefaultDirectedWeightedGraph _digraph
Store the currently read digraph.
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 used to identidy the edges from _verticesAndEdgesInfo, so that the information can be printed out without adding extra attributes.
Outputs the optimal schedule to a file. It considers the initially recorded information for ordering of the node and edges in the output file.
Usage:
OutputWriter outputWriter = new OutputWriter(output file name)
Initialise the OutputWriter and also to indicate the output file name.
outputWriter.initialise()
Create the file for output if it doesn't exist or clear it if it does
outputWriter.createSchedule(...)
Output the optimal schedule to a file. Uses the _verticesAndEdgesInfo and _verticesAndEdges from dataReader for order of output.
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)
Report the error message and exit the program.
Corrects input digraph files found on Oliver's website.
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()
Check if the scheduling is to be done sequentially. Will only return true in this class. It will return a different value in child class AStarParallelised.
aStar.execute()
Executes A* branch & bound.
- Initialise empty Solution containing the root task vertices as schedulables and total weight of tasks as upper bound.
- Pass the information on task bottom levels to the Solution.
- While the current best schedule is not a complete schedule, pop the OPEN priority queue and add all promising partial schedules that start from the current best schedule to OPEN. Add the current best schedule to CLOSED closed solutions. Then repeat step 3. Partial Expansion and Processor Normalisation are used to skip certain partial schedules.
- Update displayed graph with current best solution if visualization is opted for
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. Used during Processor Normalisation of A* bounding.
Represent partial/complete solution. Implements Comparable so for ordering in PriorityQueue using maxCostFunction().
Usage:
Solution solution = Solution(...)
Create a Solution with list of scheduled, schedulable, non-schedulable tasks, upper bound and the task digraph. Empty Processors are created to store tasks.
solution.getTime()
Get the last finishing time among all the Processors.
solution.earliestDataReadyTime(task vertex, processor number)
Get the earliest time that a task can start on a processor. Does this by looping through all the Processors and then getting the latest start time depending on the location of the parent task and also the communication time. Then returns the larger one of the latest start time depending on parents and the latest finishing time on the current Processor.
solution.addProcess(task vertex, processor number)
Adds a task to a Processor at its earliest allowable start time.
maxCostFunction()
Return the max of maximumEndTimeOfPartialSchedule() maximum of start time and bottom level of
any task in partial schedule, idleTimePlusComputationLoad() idle time plus computation load and maximumEndTimeOfFreeVertices() maximum of earliest start time and bottom level of any free tasks.
Side note: idleTimePlusComputationLoad() currently uses _upperBound which currently is the total of task weights, need to change is list scheduling is used to compute upper bound
solution.updateSchedulable(task that just got scheduled)
Add the scheduled task to the list of scheduled and updates list of schedulables and non-schedulables with children tasks that met all dependencies.
solution.isCompleteSchedule()
Checks to see if schedule is complete
isBelowUpperBound() (under development)
checks if the current Solution can still become the optimal solution by comparing the maxCostFunction() and the upper bound which is current the total of task weights.
might need to change if the definition of _upperBound changes as well
solution.createChildren()
Returns a set of Solutions (made from adding every schedulable node to every Processor to a hard copy of the current Solution) that are deemed to be below upper bound by isBelowUpperBound() and still have chance of becoming the optimal solution. method is under maintenance
createDuplicateSolution()
Create a hard copy of the current solution and to be used by createChildren when adding children tasks to the current schedule.
solution.getVertexString(task vertex)
Used by OutputWriter.createSchedule(...) to print out the additional information for each task.
@Override compareTo(solution)
For PriorityQueue to compare the cost of different Solutions for ordering.
@Override equals(object)
Overridden for proper comparison between Solutions.
@Override hashcode() (under development)
Usage:
AStarParallelised aStarP = new AStarParallelised(...)
Call constructor to AStar and stores the number of threads.
runSequentially()
Returns false is multi-threading is necessary which is when the solution space is very large.
astarP.execute()
Calls AStar's execute() if it was determined to run sequentially, else call AStarParallelised's executeInParallel()
executeInParallel()
Executes the A* algorithm using multithreading.
- First create an array to store PriorityQueues, each representing a different thread.
- (in development)
Used in executeInParallel() to store solutions to be passed into a thread in a PriorityQueue.
(in development)
Extends AStar and implements Runnable to allow the A* branch & bound to be executed in different threads for multi-threading purposes.
Usage:
AStarThread aStarThread = new AStarThread(...)
Calls constructor to AStar and stores the thread label number.
Fields:
_numberOfThreads
number of threads
AStarThread[] AStarThreads = new AStarThread[_numberOfThreads]
array of AStar threads with data structures to perform A* algorithm
Thread[] threads = new Thread[_numberOfThreads]
array of threads from the java Thread class
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, NodeClickListener
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. Add ViewerListener to listen to mouse actions on displayed graph.
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
(in development)
Usage:
NodeClickListener listener = NodeClickListener(...)
Takes in view and graph. Then registers itself as the mouse input listener of the view which is connected to the graph.
buttonPushed(id)
Prints out the id of the node clicked, to the terminal.
mouseReleased(event)
Check if some events are pending and dispatch them to the registered outputs.
(in development)
Classes: Gantt, GanttChartFactory, TaskNumeric
Displays a gantt chart for a solution.
(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.