The project is to develop a branch-and-bound, or A* type algorithm that solves the NP Hard Scheduling problem with the highest possible performance. The scheduling problem is depicted as a weighted directed acyclic graph where the nodes are tasks and its weight is the cost of computation, and the edges are the communication costs between tasks. Now with the commonality of multi-processing, to be able to achieve the highest possible performance, the algorithm will need to be parallelized, so that the algorithm itself is able to use multiple processes to speed up the search.
Maven 4.0.0 is required to compile the project.
please refer to Maven Install Instruction for direct download.
apt install maven
brew install maven
git clone git@github.com:SoftEng306-2021/project-1-raspberry-spirits-15.git
mvn clean package -DskipTests
The compiled jar will be located in target/scheduler.jar
The compiled Jar file can be run using the following command.
Java -jar target/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
Notice users must have java version of at least Java 1.8
.
−o
OUTPUT output file is named OUTPUT (default is INPUT−output.dot )
−p N
use N cores for execution in parallel (default is sequential)
-v
visualise the serach