Programming assignment: A few classes ago, we looked at getting a legal ordering
ID: 3705452 • Letter: P
Question
Programming assignment: A few classes ago, we looked at getting a legal ordering of classes with prerequisites. For those that got to it, we also looked at trying to minimize the number of semesters left if you can schedule as many courses as you like for any term in particular. For this assignment, we generalize that: find the "minimum completion time" for a set of jobs, where jobs may happen in parallel, and also, each job may take different amounts of time. This is also discussed in Section 24.2, the PERT section.
You will create a "JobSchedule" data structure (with a constructor), which will hopefully use an underlying directed, acyclic (more on that later) graph. You will also have an inner class, JobSchedule.Job.
For JobSchedule, you will have a public constructor (no parameters). Additionally, you will have three public methods:
public Job addJob(int time) adds a new job to the schedule, where the time needed to complete the job is time. (time will be positive.) Jobs will be numbered, by the order in which they are added to your structure: the first job added is (implicitly) job 0, the next 1, even though they won't be labeled.
public Job getJob(int index) method, which returns the job by its number. (Use the implicit number, as described in addJob. That number has nothing to do with the time for completion.) (I will only call this method with valid indices. I want you to correctly code the algorithm, rather than worrying about bullet-proofing your code against bad inputs.)
public int minCompletionTime() should return the minimum possible completion time for the entire JobSchedule, or -1 if it is not possible to complete it. (It is not possible to complete if there is a prerequisite cycle within the underlying graph).
Your Job class should have exactly two public methods. It should not have a public constructor. (Its constructor should only be called from within the JobSchedule class.)
public void requires(Job j) sets up the requirement that this job requires job j to be completed before it begins.
public int getStartTime() will return the earliest possible start time for the job. (The very first first start time, for jobs with no pre-requisites, is 0.) If there IS a cycle, and thus the given job can never be started (because it is on the cycle, or something on the cycle must be completed before this job starts), return -1. However, if the job can be started, even if other jobs within the overall schedule cannot be, return a valid time.
Example: for the following calls, I show the return values expected:
JobSchedule schedule = new JobSchedule();
schedule.addJob(8); //adds job 0 with time 8
JobSchedule.Job j1 = schedule.addJob(3); //adds job 1 with time 3
schedule.addJob(5); //adds job 2 with time 5
schedule.minCompletionTime(); //should return 8, since job 0 takes time 8 to complete.
/* Note it is not the min completion time of any job, but the earliest the entire set can complete. */
schedule.getJob(0).requires(schedule.getJob(2)); //job 2 must precede job 0
schedule.minCompletionTime(); //should return 13 (job 0 cannot start until time 5)
schedule.getJob(0).requires(j1); //job 1 must precede job 0
schedule.minCompletionTime(); //should return 13
schedule.getJob(0).getStartTime(); //should return 5
j1.getStartTime(); //should return 0
schedule.getJob(2).getStartTime(); //should return 0
j1.requires(schedule.getJob(2)); //job 2 must precede job 1
schedule.minCompletionTime(); //should return 16
schedule.getJob(0).getStartTime(); //should return 8
schedule.getJob(1).getStartTime(); //should return 5
schedule.getJob(2).getStartTime(); //should return 0
schedule.getJob(1).requires(schedule.getJob(0)); //job 0 must precede job 1 (creates loop)
schedule.minCompletionTime(); //should return -1
schedule.getJob(0).getStartTime(); //should return -1
schedule.getJob(1).getStartTime(); //should return -1
schedule.getJob(2).getStartTime(); //should return 0 (no loops in prerequisites)
Your algorithm should look pretty similar to the acyclic single source shortest path one. The primary difference is that, for every node, the initial (default) start time, before any constraints are added, is 0. Instead of relaxing edges to give shorter paths, you are actually "relaxing" constraints to give higher start times. That is, in the example above, the first constraint raises 0's start time because, if 2 starts at its start time 0, and takes 5 to complete, then the start time for 0 is now max(0,5), the previous start time and the new constraint from job 2.
Your code should be efficient. This includes two aspects: your graph should have an efficient enough implementation for basic functions, and also, you can try to figure out how, algorithmically, you can make your code more efficient specifically for this problem. That being said, there will be some tests that should pass if your code is correct but not efficient (but it can't be absurdly inefficient), and others that should pass only if you have efficient code. This is the "interesting" part of the assignment: rather than just translating from high-level pseudocode to a program (a programming problem), you are being asked to think a bit about what the algorithm does, and how to improve it.
Also remember that we discussed two different algorithms to topologically order data. For this problem, the non-DFS topological sort solution is probably preferred, as I will create at least one test on a large graph, where DFS might hit stack-overflow errors. (Alternatively, you can make a DFS based solution that explicitly uses a stack of your own, rather than using the program stack.)
You should submit your own JUnit tests as well, in a file with a name ending in Test.java or Tests.java. WebCAT gives feedback based on (a) how well your tests cover your own code, (b) how well your code does on your tests, and (c) how well your code does on MY tests. Just to let you know, excluding the efficiency tests (and perhaps one other test), if you fail even one of my tests, they are set up to make it likely that you fail many of them. (If you know that your code has an error, it is hard to consider your code as "working", but if you see that you are passing 90% of tests, you might feel like it works.)
zip (or tar, or jar) your java code for both your classes and your tests cases into one file to submit, or use the submitter with your IDE. You should have more tests than the one I give above.
No package. JobSchedule.java should be your main java file, along with your JUnit java tests.
Explanation / Answer
Tests.java
import static org.junit.Assert.*;
import org.junit.Test;
public class Tests {
@Test
public void givenTest() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(8); //adds job 0 with time 8
JobSchedule.Job j1 = schedule.addJob(3); //adds job 1 with time 3
schedule.addJob(5); //adds job 2 with time 5
System.out.println(schedule.minCompletionTime());
assertEquals(8, schedule.minCompletionTime()); //should return 8, since job 0 takes time 8 to complete.
/* Note it is not the min completion time of any job, but the earliest the entire set can complete. */
schedule.getJob(0).requires(schedule.getJob(2)); //job 2 must precede job 0
assertEquals(13, schedule.minCompletionTime()); //should return 13 (job 0 cannot start until time 5)
schedule.getJob(0).requires(j1); //job 1 must precede job 0
assertEquals(13, schedule.minCompletionTime()); //should return 13
assertEquals(5, schedule.getJob(0).getStartTime()); //should return 5
assertEquals(0, j1.getStartTime()); //should return 0
assertEquals(0, schedule.getJob(2).getStartTime()); //should return 0
j1.requires(schedule.getJob(2)); //job 2 must precede job 1
assertEquals(16, schedule.minCompletionTime()); //should return 16
assertEquals(8, schedule.getJob(0).getStartTime()); //should return 8
assertEquals(5, schedule.getJob(1).getStartTime()); //should return 5
assertEquals(0, schedule.getJob(2).getStartTime()); //should return 0
schedule.getJob(1).requires(schedule.getJob(0)); //job 0 must precede job 1 (creates loop)
assertEquals(-1, schedule.minCompletionTime()); //should return -1
assertEquals(-1, schedule.getJob(0).getStartTime()); //should return -1
assertEquals(-1, schedule.getJob(1).getStartTime()); //should return -1
assertEquals(0, schedule.getJob(2).getStartTime()); //should return 0 (no loops in prerequisites)
}
@Test
public void testParallel1() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // job 0 -- 1
schedule.addJob(2); // job 1 -- 2
schedule.addJob(3); // job 2 -- 3
schedule.addJob(4); // job 3 -- 4
schedule.addJob(5); // job 4 -- 5
//System.out.println(schedule.minCompletionTime());
assertEquals(5, schedule.minCompletionTime());
assertEquals(0, schedule.getJob(0).getStartTime());
assertEquals(0, schedule.getJob(1).getStartTime());
assertEquals(0, schedule.getJob(2).getStartTime());
assertEquals(0, schedule.getJob(3).getStartTime());
assertEquals(0, schedule.getJob(4).getStartTime());
}
@Test
public void testCycle1() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // job 0 -- 1
schedule.addJob(2); // job 1 -- 1
schedule.addJob(3); // job 2 -- 1
schedule.addJob(4); // job 3 -- 1
schedule.addJob(5); // job 4 -- 1
schedule.getJob(1).requires(schedule.getJob(0));
schedule.getJob(2).requires(schedule.getJob(1));
schedule.getJob(3).requires(schedule.getJob(2));
schedule.getJob(4).requires(schedule.getJob(3));
schedule.getJob(1).requires(schedule.getJob(3));
assertEquals(-1, schedule.minCompletionTime());
assertEquals(0, schedule.getJob(0).getStartTime());
assertEquals(-1, schedule.getJob(1).getStartTime());
assertEquals(-1, schedule.getJob(2).getStartTime());
assertEquals(-1, schedule.getJob(3).getStartTime());
assertEquals(-1, schedule.getJob(4).getStartTime());
}
@Test
public void testCycleAndParallel() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // job 0 -- 1
schedule.addJob(2); // job 1 -- 1
schedule.addJob(3); // job 2 -- 1
schedule.addJob(4); // job 3 -- 1
schedule.addJob(5); // job 4 -- 1
schedule.getJob(1).requires(schedule.getJob(0));
schedule.getJob(2).requires(schedule.getJob(1));
schedule.getJob(3).requires(schedule.getJob(2));
schedule.getJob(4).requires(schedule.getJob(3));
schedule.getJob(1).requires(schedule.getJob(3));
schedule.addJob(1); // job 5 -- 1
schedule.addJob(2); // job 6 -- 2
schedule.addJob(3); // job 7 -- 3
schedule.addJob(4); // job 8 -- 4
schedule.addJob(5); // job 9 -- 5
schedule.getJob(6).requires(schedule.getJob(5));
schedule.getJob(7).requires(schedule.getJob(6));
schedule.getJob(8).requires(schedule.getJob(7));
schedule.getJob(9).requires(schedule.getJob(8));
assertEquals(-1, schedule.minCompletionTime());
assertEquals(0, schedule.getJob(0).getStartTime());
assertEquals(-1, schedule.getJob(1).getStartTime());
assertEquals(-1, schedule.getJob(2).getStartTime());
assertEquals(-1, schedule.getJob(3).getStartTime());
assertEquals(-1, schedule.getJob(4).getStartTime());
//System.out.println(schedule.getJob(9).getStartTime());
assertEquals(3, schedule.getJob(7).getStartTime());
assertEquals(10, schedule.getJob(9).getStartTime());
}
@Test
public void testCycleLinkParallel() {
for (int i = 0; i < 1000; i++) {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // job 0 -- 1
schedule.addJob(2); // job 1 -- 1
schedule.addJob(3); // job 2 -- 1
schedule.addJob(4); // job 3 -- 1
schedule.addJob(5); // job 4 -- 1
schedule.getJob(1).requires(schedule.getJob(0));
schedule.getJob(2).requires(schedule.getJob(1));
schedule.getJob(3).requires(schedule.getJob(2));
schedule.getJob(4).requires(schedule.getJob(3));
schedule.getJob(1).requires(schedule.getJob(3));
schedule.addJob(1); // job 5 -- 1
schedule.addJob(2); // job 6 -- 2
schedule.addJob(3); // job 7 -- 3
schedule.addJob(4); // job 8 -- 4
schedule.addJob(5); // job 9 -- 5
schedule.getJob(6).requires(schedule.getJob(5));
schedule.getJob(7).requires(schedule.getJob(6));
schedule.getJob(8).requires(schedule.getJob(7));
schedule.getJob(9).requires(schedule.getJob(8));
schedule.getJob(0).requires(schedule.getJob(9));
//System.out.println(schedule.minCompletionTime());
assertEquals(-1, schedule.minCompletionTime());
assertEquals(15, schedule.getJob(0).getStartTime());
assertEquals(-1, schedule.getJob(1).getStartTime());
assertEquals(-1, schedule.getJob(2).getStartTime());
assertEquals(-1, schedule.getJob(3).getStartTime());
assertEquals(-1, schedule.getJob(4).getStartTime());
//System.out.println(schedule.getJob(9).getStartTime());
assertEquals(3, schedule.getJob(7).getStartTime());
assertEquals(10, schedule.getJob(9).getStartTime());
}
}
@Test
public void test2() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // job 0 -- 1
schedule.addJob(2); // job 1 -- 2
schedule.addJob(3); // job 2 -- 3
schedule.addJob(4); // job 3 -- 4
schedule.addJob(5); // job 4 -- 5
schedule.getJob(1).requires(schedule.getJob(0));
schedule.getJob(2).requires(schedule.getJob(1));
schedule.getJob(3).requires(schedule.getJob(2));
schedule.getJob(4).requires(schedule.getJob(3));
assertEquals(15, schedule.minCompletionTime());
schedule.addJob(1); // job 5 - 1
schedule.getJob(1).requires(schedule.getJob(5));
schedule.getJob(2).requires(schedule.getJob(5));
assertEquals(15, schedule.minCompletionTime());
//System.out.println(schedule.getJob(5).getStartTime());
assertEquals(0, schedule.getJob(0).getStartTime());
assertEquals(0, schedule.getJob(5).getStartTime());
//System.out.println(schedule.minCompletionTime());
}
@Test
public void test3() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // job 0 -- 1
schedule.addJob(2); // job 1 -- 2
schedule.addJob(3); // job 2 -- 3
schedule.addJob(4); // job 3 -- 4
schedule.addJob(5); // job 4 -- 5
schedule.getJob(1).requires(schedule.getJob(0));
assertEquals(5, schedule.minCompletionTime());
schedule.getJob(2).requires(schedule.getJob(1));
assertEquals(6, schedule.minCompletionTime());
schedule.getJob(3).requires(schedule.getJob(2));
assertEquals(10, schedule.minCompletionTime());
schedule.getJob(4).requires(schedule.getJob(3));
assertEquals(15, schedule.minCompletionTime());
schedule.addJob(1); // job 5 - 1
schedule.getJob(1).requires(schedule.getJob(5));
schedule.getJob(2).requires(schedule.getJob(5));
assertEquals(15, schedule.minCompletionTime());
//System.out.println(schedule.getJob(5).getStartTime());
assertEquals(0, schedule.getJob(0).getStartTime());
assertEquals(0, schedule.getJob(5).getStartTime());
//System.out.println(schedule.minCompletionTime());
}
@Test
public void test4() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // job 0 -- 1
schedule.addJob(2); // job 1 -- 2
schedule.addJob(3); // job 2 -- 3
schedule.addJob(4); // job 3 -- 4
schedule.addJob(5); // job 4 -- 5
//schedule.addJob(1); // job 5 -- 1
schedule.getJob(1).requires(schedule.getJob(0));
schedule.getJob(2).requires(schedule.getJob(1));
schedule.getJob(3).requires(schedule.getJob(1));
schedule.getJob(4).requires(schedule.getJob(3));
schedule.addJob(1); // job 5 -- 1
schedule.addJob(2); // job 6 -- 2
schedule.addJob(3); // job 7 -- 3
schedule.addJob(4); // job 8 -- 4
schedule.addJob(5); // job 9 -- 5
schedule.getJob(1).requires(schedule.getJob(6));
schedule.getJob(6).requires(schedule.getJob(5));
schedule.getJob(7).requires(schedule.getJob(6));
schedule.getJob(8).requires(schedule.getJob(6));
schedule.getJob(9).requires(schedule.getJob(7));
schedule.getJob(6).requires(schedule.getJob(9));
//System.out.println(schedule.minCompletionTime());
//System.out.println(schedule.getJob(5).getStartTime());
//System.out.println(schedule.getJob(6).getStartTime());
//System.out.println(schedule.getJob(1).getStartTime());
//System.out.println(schedule.getJob(3).getStartTime());
//System.out.println(schedule.getJob(4).getStartTime());
assertEquals(-1, schedule.minCompletionTime());
}
@Test
public void test5() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // job 0 -- 1
schedule.addJob(2); // job 1 -- 2
schedule.addJob(3); // job 2 -- 3
schedule.getJob(1).requires(schedule.getJob(0));
schedule.getJob(2).requires(schedule.getJob(1));
schedule.getJob(0).requires(schedule.getJob(2));
assertEquals(-1, schedule.minCompletionTime());
}
@Test
public void testPiazza() {
JobSchedule schedule = new JobSchedule();
schedule.addJob(1); // A 0
schedule.addJob(1); // B 1
schedule.addJob(2); // C 2
schedule.addJob(1); // D 3
schedule.addJob(1); // E 4
schedule.addJob(1); // F 5
schedule.addJob(1); // G 6
schedule.addJob(1); // H 7
schedule.getJob(0).requires(schedule.getJob(5));
schedule.getJob(5).requires(schedule.getJob(3));
schedule.getJob(3).requires(schedule.getJob(0));
schedule.getJob(4).requires(schedule.getJob(3));
schedule.getJob(2).requires(schedule.getJob(1));
schedule.getJob(7).requires(schedule.getJob(2));
assertEquals(-1, schedule.minCompletionTime());
assertEquals(0, schedule.getJob(1).getStartTime());
assertEquals(1, schedule.getJob(2).getStartTime());
assertEquals(0, schedule.getJob(6).getStartTime());
assertEquals(3, schedule.getJob(7).getStartTime());
}
}
JobSchedule.java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
public class JobSchedule {
private ArrayList<Job> jobs;
private boolean onStack[];
private boolean marked[];
private boolean hasCycle;
private Stack<Job> topologicalOrder;
private boolean[] cantFinish;
private int min;
class Job{
private int time;
private ArrayList<Job> adj;
private int start;
private int index;
private Job(int time){
this.time = time;
adj = new ArrayList<>();
start = 0;
}
public void requires(Job j) {
j.adj.add(this);
update();
}
public int getStartTime() {
return start;
}
}
public JobSchedule() {
jobs = new ArrayList<>();
}
public Job addJob(int time) {
Job j = new Job(time);
j.index = jobs.size();
jobs.add(j);
min = Math.max(time, min);
return j;
}
public Job getJob(int index) {
return jobs.get(index);
}
private void update() {
hasCycle = false;
boolean[jobs.size()];
marked = new boolean[jobs.size()];
cantFinish = new boolean[jobs.size()];
topologicalOrder = new Stack<>();
int maxPathTime = 0; // the time of one path
for (int i = 0; i < jobs.size(); i++) {
if (!marked[i] && !cantFinish[i]) {
//System.out.println("***");
nonrecursiveDFS(i, true, marked);
}
}
// now it is guarantee the a DAG
while (!topologicalOrder.empty()) {
Job j = topologicalOrder.pop();
if (cantFinish[j.index]) {
j.start = -1;
continue;
}
if (j.adj.size() == 0) { // means j is the tail
maxPathTime = Math.max(maxPathTime, j.start + j.time);
} else {
for (Job jw : j.adj) {
jw.start = Math.max(jw.start, j.start + j.time);
}
}
}
if (hasCycle()) min = -1;
else min = maxPathTime;
}
public int minCompletionTime() {
return min;
}
public boolean hasCycle() {
return hasCycle;
}
/*
* no use this dfs
private void dfs(int v, boolean checkCycle, boolean[] flag) {
if (checkCycle) onStack[v] = true;
flag[v] = true;
if (!checkCycle) cantFinish[v] = true; // when checkArrive == false, just check which vertex can't arrive
Job jv = jobs.get(v);
for (Job jw : jv.adj) {
int w = jw.index;
//if (hasCycle && checkCycle) return; // when checkArrive == false, do not return because it has cycle, but
if (!flag[w]) { // need to know which vertex
dfs(w, checkCycle, flag);
} else if (onStack[w] && checkCycle){
hasCycle = true;
dfs(w, false, cantFinish);
}
}
if (checkCycle) {
topologicalOrder.push(jv);
onStack[v] = false;
}
}
*/
private void nonrecursiveDFS(int s, boolean checkCycle, boolean[] flag) {
Stack<Integer> stack = new Stack<>();
Iterator<?>[] iters = new Iterator[jobs.size()];
for (int i = 0; i < jobs.size(); i++) {
iters[i] = jobs.get(i).adj.iterator();
}
stack.push(s);
flag[s] = true;
if (checkCycle) onStack[s] = true;
while (!stack.empty()) {
int v = stack.peek();
if (checkCycle) onStack[v] = true;
flag[v] = true;
if (iters[v].hasNext()) {
Job jw = (Job) iters[v].next();
int w = jw.index;
if (!flag[w]) {
onStack[w] = true;
stack.push(w);
} else if (onStack[w] && checkCycle) {
hasCycle = true;
nonrecursiveDFS(w, false, cantFinish);
}
} else {
int i = stack.pop();
if (checkCycle) {
Job ji = jobs.get(i);
topologicalOrder.push(ji);
}
onStack[i] = false;
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.