Scheduling with deadline. Suppose that you have N tasks to schedule. Each task t

ID: 3691274 • Letter: S

Question

Scheduling with deadline. Suppose that you have N tasks to schedule. Each task takes 1 unit of time and has a deadline by which time it is expected to finish. If a task is not completed by its deadline, you pay a $1,000 fine. Find a schedule that minimizes the penalty. Hint: schedule the tasks in order of their deadline, but don't bother with any task that won't finish by its deadline , using piority queue in java Scheduling with deadline. Suppose that you have N tasks to schedule. Each task takes 1 unit of time and has a deadline by which time it is expected to finish. If a task is not completed by its deadline, you pay a $1,000 fine. Find a schedule that minimizes the penalty. Hint: schedule the tasks in order of their deadline, but don't bother with any task that won't finish by its deadline , using piority queue in java

Explanation / Answer

import java.util.ArrayList;
import java.util.Scanner;

public class PriorityQueueProject {

   private static ArrayList<Entry> input = new ArrayList<Entry>();
   private static ArrayList<Entry> completedJobs = new ArrayList<Entry>();
   private static HeapPriorityQueue pq = new HeapPriorityQueue();
   public static int time = 0;

   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);

       while(scan.hasNext()){
           int value = scan.nextInt();
           int size = scan.nextInt();
           int deadline = scan.nextInt();

           Job j = new Job(size, deadline);
           Entry e = new Entry(value, j);
           input.add(e);
       }
       // assigns all jobs their job number
       for(int i = 0; i < input.size(); i++){
           Entry e = input.get(i);
           e.getJob().setJobNumber(i);
       }
       scan.close();

       // adds the first Entry that can complete to the priority queue to get started
       add(0);

       while(!pq.isEmpty()){
           completeJob(pq.max());
       }

       for(Entry e : completedJobs){
           System.out.print(e.getJob());
       }
   }

   // adds the correct number of Entry instances to the priority queue
   // depending on the amount of time it took the last job to complete
   public static void add(int changeInTime){
       if(input.isEmpty()) return;
       // first Entry that can complete
       if(changeInTime == 0){
           Entry first = input.remove(0);

           if(isCompletable(first)){
               pq.insert(first.getValue(), first.getJob());
               int timeRequired = pq.max().getJob().getSize();
               time += timeRequired;
               completedJobs.add(pq.removeMax());
               // imports the jobs that came in during the time it took to complete the first one
               add(timeRequired);
           }
           else {
               time += 10;           // adds 10s wait until next job arrives
               add(0);            // adds the new head of input to the priority queue (recursively until it can complete)
           }
       }
       // adds Entry instances to the priority queue when it is NOT the first Entry
       else {
           int numToAdd = (changeInTime / 10);

           while(numToAdd > 0 && !input.isEmpty()){
               Entry newest = input.remove(0);
               pq.insert(newest.getValue(), newest.getJob());
               numToAdd--;
           }

           // if the time is multiple of 5, but not a multiple of 10
           if(time % 5 == 0 && (double)time % 10 != 0){
               time += 5;
               add(10);   // adds one Entry to the priority queue, since 1 Entry comes in every 10 seconds
           }
       }
   }

   public static void completeJob(Entry e){
       if(isCompletable(e)){
           int timeRequired = e.getJob().getSize();
           time += timeRequired;
           Entry completedEntry = pq.removeMax();
           completedJobs.add(completedEntry);
           add(timeRequired);    // imports jobs that came in during the time it took to complete this one
       }
       else{
           pq.removeMax();       // removes top job since it cannot be completed in time

           if(pq.isEmpty()){
               time+=10;
               add(10);
           }
       }
   }

   public static boolean isCompletable(Entry e){
       if(e.getJob().getSize() + time > e.getJob().getDeadline())
           return false;
       return true;
   }
}

now we have the second class:-

import java.util.ArrayList;

public class HeapPriorityQueue {
   private ArrayList<Entry> heap = new ArrayList<Entry>();

   public int parent(int j){
       return (j-1)/2;
   }
   public int left(int j){
       return 2*j + 1;
   }
   public int right(int j){
       return 2*j + 2;
   }
   public boolean hasLeft(int j){
       return left(j) < heap.size();
   }
   public boolean hasRight(int j){
       return right(j) < heap.size();
   }

   public void swap(int i, int j){
       Entry temp = heap.get(i);
       heap.set(i, heap.get(j));
       heap.set(j, temp);
   }

   public void upheap(int j){
       while(j > 0){
           int p = parent(j);
           if(heap.get(p).getValue() >= heap.get(j).getValue())
               break;
           swap(j, p);
           j = p;
       }
   }

   public void down_heap(int j){
       while(hasLeft(j)){
           int leftIndex = left(j);
           int bigChildIndex = leftIndex;
           if(hasRight(j)){
               int rightIndex = right(j);
               if(heap.get(rightIndex).getValue() > heap.get(leftIndex).getValue())
                   bigChildIndex = rightIndex;
           }
           if(heap.get(j).getValue() > heap.get(bigChildIndex).getValue())
               break;
           swap(j, bigChildIndex);
           j = bigChildIndex;
       }
   }

   public Entry insert(int key, Job j){
       Entry newest = new Entry(key, j);
       heap.add(newest);
       upheap(heap.size()-1);
       return newest;
   }

   public Entry removeMax(){
       if(heap.isEmpty())
           return null;
       Entry answer = heap.get(0);
       swap(0, heap.size()-1);
       heap.remove(heap.size()-1);
       down_heap(0);
       return answer;
   }

   public Entry max(){
       return heap.get(0);
   }

   public boolean isEmpty() {
       if(heap.isEmpty())
           return true;
       return false;
   }

   public String toString(){
       return heap.toString();
   }
}

We define the job and deadline in this class.

public class Job {
   private int size;
   private int deadline;
   private int jobNumber;

   public Job(int s, int d){
       setSize(s);
       setDeadline(d);
   }

   public void setJobNumber(int j) {
       jobNumber = j;
   }

   public int getSize() {
       return size;
   }
   public void setSize(int s) {
       size = s;
   }

   public int getDeadline() {
       return deadline;
   }
   public void setDeadline(int d) {
       deadline = d;
   }

   public String toString(){
       return jobNumber + " ";
   }

}

As priority queue is maintained using heap, the implementation is as follows:-

import java.util.ArrayList;
import java.util.Scanner;

public class PriorityQueueProject {

Navigate

Scheduling to minimize average completion time. Suppose you are given a set S =

Scheduling with deadline. Suppose that you have N tasks to schedule. Each task t

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Scheduling with deadline. Suppose that you have N tasks to schedule. Each task t

Question

Explanation / Answer

Related Questions

Navigate