|| In the below algorithm set S consists of jobs which are on time. The optimal
ID: 3936432 • Letter: #
Question
|| In the below algorithm set S consists of jobs which are on time. The optimal schedule then consists of the sequence of jobs in S ordered according to nondecreasing dj-values followed by the late jobs in any order. The algorithm adds jobs to S in order of nondecreasing due dates. If the addition of job j results in this job being completed after dj , then a job in S with the largest processing time is marked to be late and removed from S. t denotes the current schedule time. Algorithm 1. Enumerate jobs such that d1 d2 ... dn; 2. S := ; t := 0; 3. FOR i := 1 to n DO BEGIN 4. S := S {i}; 5. t := t + pi; 6. IF t > di THEN BEGIN 7. Find job j in S with a largest pj-value; 8. S := S {j}; 9. t := tpj END END
solve with moors algorithm in netbeans
Explanation / Answer
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
public class MooresAlgorithm {
private TreeMap<Integer, Integer> map=new TreeMap<>();
public MooresAlgorithm(int[] duedates, int[] processingtimes){
int n=duedates.length;
for(int i=0; i<n;i++) {
map.put(duedates[i], processingtimes[i]);
}
}
private void printMap() {
Set s = map.entrySet();
Iterator it = s.iterator();
while ( it.hasNext() ) {
Map.Entry entry = (Map.Entry) it.next();
int key = (int) entry.getKey();
int value = (int) entry.getValue();
System.out.println("{" + key + "," + value + "}");
}//while
}//p
private HashMap MooresAlgorithm() {
// Initialize an empty final set S
int jobid=0;
HashMap<Integer, Integer> S = new HashMap<>();
int numTasks=map.size();
Iterator it=map.entrySet().iterator();
while(it.hasNext()) {
Map.Entry entry=(Map.Entry) it.next();
// Get the processing time
int processingtime=(int) entry.getValue();
int duedate=(int) entry.getKey();
int tmp=sumProcessingTimesIn(S);
if(tmp+processingtime <= duedate){
S.put((Integer) entry.getKey(), (Integer) entry.getValue());
}
else {
S.put((Integer) entry.getKey(), (Integer) entry.getValue());
Entry longestTask=longestTask(S);
// Remove the longest task
S.remove(longestTask.getKey(), longestTask.getValue());
}
jobid++;
}
return S;
}
private Entry longestTask(Map<Integer, Integer> S) {
Iterator it=S.entrySet().iterator();
Map.Entry longestTask = null;
int max=0;
while(it.hasNext()) {
Map.Entry entry=(Map.Entry) it.next();
// Get the processing time
int processingtime=(int) entry.getValue();
int duedate=(int) entry.getKey();
if(processingtime>max) {
max=processingtime;
longestTask=entry;
}
}
return longestTask;
}
private int sumProcessingTimesIn(Map<Integer, Integer> S) {
if(S.isEmpty())
return 0;
int sum=0;
Iterator it=S.entrySet().iterator();
while(it.hasNext()) {
Map.Entry entry=(Map.Entry) it.next();
// Get the processing time
int processingtime=(int) entry.getValue();
int duedate=(int) entry.getKey();
sum+=processingtime;
}
return sum;
}
public static void main(String[] args) {
// {11,6}, {9,5}, {8,2}, {7,3}, {6,4} are the {duedate_of_task_i, processing_time_of_task_i}
int[] duedates = {11,9,8,7,6};
int[] processingtimes= {6,5,2,3,4};
// We use a treemap to hold the above pairs according in ascending order of due date
MooresAlgorithm alg=new MooresAlgorithm(duedates, processingtimes);
HashMap optimalSetOfTasks=alg.MooresAlgorithm();
System.out.println("The {due_date,processing_time} of a task are as below (in ascending order of due dates): ");
alg.printMap();
// Print the set of tasks
System.out.println("The optimal set of tasks that will minimize the number of late jobs: ");
Iterator it=optimalSetOfTasks.entrySet().iterator();
while(it.hasNext()) {
Entry entry=(Entry) it.next();
System.out.println("{" + entry.getKey() + "," + entry.getValue()+ "}");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.