Repository: TheAlgorithms/Java
Pull request #3843 (2023-01-12 13:41:07)

Shortest Job First  schedule algorithm implementation
<!-- For completed items, change [ ] to [x] -->

- [ ] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [ ] This pull request is all my own work -- I have not plagiarized it.
- [ ] All filenames are in PascalCase.
- [ ] All functions and variable names follow Java naming conventions.
- [ ] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
issue : #3810 


Patch:
diff --git a/src/main/java/com/thealgorithms/others/SJF.java b/src/main/java/com/thealgorithms/others/SJF.java
deleted file mode 100644
index 17147412..00000000
--- a/src/main/java/com/thealgorithms/others/SJF.java
+++ /dev/null
@@ -1,199 +0,0 @@
-package com.thealgorithms.others;
-
-/**
- *
- *
- * <h2>Shortest job first.</h2>
- *
- * <p>
- * Shortest job first (SJF) or shortest job next, is a scheduling policy that
- * selects the waiting process with the smallest execution time to execute next
- * Shortest Job first has the advantage of having minimum average waiting time
- * among all scheduling algorithms. It is a Greedy Algorithm. It may cause
- * starvation if shorter processes keep coming. This problem has been solved
- * using the concept of aging.
- *
- * @author shivg7706
- * @since 2018/10/27
- */
-import java.util.*;
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.Scanner;
-
-class Process {
-
-    public int pid;
-    public int arrivalTime;
-    public int burstTime;
-    public int priority;
-    public int turnAroundTime;
-    public int waitTime;
-    public int remainingTime;
-}
-
-class Schedule {
-
-    private int noOfProcess;
-    private int timer = 0;
-    private ArrayList<Process> processes;
-    private ArrayList<Process> remainingProcess;
-    private ArrayList<Integer> gantChart;
-    private float burstAll;
-    private Map<Integer, ArrayList<Process>> arrivals;
-
-    Schedule() {
-        Scanner in = new Scanner(System.in);
-
-        processes = new ArrayList<Process>();
-        remainingProcess = new ArrayList<Process>();
-
-        gantChart = new ArrayList<>();
-        arrivals = new HashMap<>();
-
-        System.out.print("Enter the no. of processes: ");
-        noOfProcess = in.nextInt();
-        System.out.println(
-            "Enter the arrival, burst and priority of processes"
-        );
-        for (int i = 0; i < noOfProcess; i++) {
-            Process p = new Process();
-            p.pid = i;
-            p.arrivalTime = in.nextInt();
-            p.burstTime = in.nextInt();
-            p.priority = in.nextInt();
-            p.turnAroundTime = 0;
-            p.waitTime = 0;
-            p.remainingTime = p.burstTime;
-
-            if (arrivals.get(p.arrivalTime) == null) {
-                arrivals.put(p.arrivalTime, new ArrayList<Process>());
-            }
-            arrivals.get(p.arrivalTime).add(p);
-            processes.add(p);
-            burstAll += p.burstTime;
-        }
-        in.close();
-    }
-
-    void startScheduling() {
-        processes.sort(
-            new Comparator<Process>() {
-                @Override
-                public int compare(Process a, Process b) {
-                    return a.arrivalTime - b.arrivalTime;
-                }
-            }
-        );
-
-        while (!(arrivals.size() == 0 && remainingProcess.size() == 0)) {
-            removeFinishedProcess();
-            if (arrivals.get(timer) != null) {
-                remainingProcess.addAll(arrivals.get(timer));
-                arrivals.remove(timer);
-            }
-
-            remainingProcess.sort(
-                new Comparator<Process>() {
-                    private int alpha = 6;
-                    private int beta = 1;
-
-                    @Override
-                    public int compare(Process a, Process b) {
-                        int aRem = a.remainingTime;
-                        int bRem = b.remainingTime;
-                        int aprior = a.priority;
-                        int bprior = b.priority;
-                        return (
-                            (alpha * aRem + beta * aprior) -
-                            (alpha * bRem + beta * bprior)
-                        );
-                    }
-                }
-            );
-
-            int k = timeElapsed(timer);
-            ageing(k);
-            timer++;
-        }
-
-        System.out.println("Total time required: " + (timer - 1));
-    }
-
-    void removeFinishedProcess() {
-        ArrayList<Integer> completed = new ArrayList<Integer>();
-        for (int i = 0; i < remainingProcess.size(); i++) {
-            if (remainingProcess.get(i).remainingTime == 0) {
-                completed.add(i);
-            }
-        }
-
-        for (int i = 0; i < completed.size(); i++) {
-            int pid = remainingProcess.get(completed.get(i)).pid;
-            processes.get(pid).waitTime =
-                remainingProcess.get(completed.get(i)).waitTime;
-            remainingProcess.remove(remainingProcess.get(completed.get(i)));
-        }
-    }
-
-    public int timeElapsed(int i) {
-        if (!remainingProcess.isEmpty()) {
-            gantChart.add(i, remainingProcess.get(0).pid);
-            remainingProcess.get(0).remainingTime--;
-            return 1;
-        }
-        return 0;
-    }
-
-    public void ageing(int k) {
-        for (int i = k; i < remainingProcess.size(); i++) {
-            remainingProcess.get(i).waitTime++;
-            if (remainingProcess.get(i).waitTime % 7 == 0) {
-                remainingProcess.get(i).priority--;
-            }
-        }
-    }
-
-    public void solve() {
-        System.out.println("Gant chart ");
-        for (int i = 0; i < gantChart.size(); i++) {
-            System.out.print(gantChart.get(i) + " ");
-        }
-        System.out.println();
-
-        float waitTimeTot = 0;
-        float tatTime = 0;
-
-        for (int i = 0; i < noOfProcess; i++) {
-            processes.get(i).turnAroundTime =
-                processes.get(i).waitTime + processes.get(i).burstTime;
-
-            waitTimeTot += processes.get(i).waitTime;
-            tatTime += processes.get(i).turnAroundTime;
-
-            System.out.println(
-                "Process no.: " +
-                i +
-                " Wait time: " +
-                processes.get(i).waitTime +
-                " Turn Around Time: " +
-                processes.get(i).turnAroundTime
-            );
-        }
-
-        System.out.println(
-            "Average Waiting Time: " + waitTimeTot / noOfProcess
-        );
-        System.out.println("Average TAT Time: " + tatTime / noOfProcess);
-        System.out.println("Throughput: " + (float) noOfProcess / (timer - 1));
-    }
-}
-
-public class SJF {
-
-    public static void main(String[] args) {
-        Schedule s = new Schedule();
-        s.startScheduling();
-        s.solve();
-    }
-}
diff --git a/src/main/java/com/thealgorithms/scheduling/SJFScheduling.java b/src/main/java/com/thealgorithms/scheduling/SJFScheduling.java
new file mode 100644
index 00000000..bf3a9f00
--- /dev/null
+++ b/src/main/java/com/thealgorithms/scheduling/SJFScheduling.java
@@ -0,0 +1,115 @@
+package com.thealgorithms.scheduling;
+
+import com.thealgorithms.devutils.entities.ProcessDetails;
+
+import java.util.ArrayList;
+
+/**
+ * Implementation of Shortest Job First Algorithm: The algorithm allows the waiting process with the minimal burst time to be executed first.
+ * see more here: https://www.guru99.com/shortest-job-first-sjf-scheduling.html
+ */
+
+public class SJFScheduling {
+    protected ArrayList<ProcessDetails> processes;
+    protected ArrayList<String>schedule ;
+
+    /**
+     * a simple constructor
+     * @param processes a list of processes the user wants to schedule
+     *  it also sorts the processes based on the time of their arrival
+     */
+    SJFScheduling(final ArrayList<ProcessDetails> processes) {
+        this.processes = processes;
+        schedule=new ArrayList<>();
+        sortByArrivalTime();
+    }
+protected void sortByArrivalTime() {
+        int size=processes.size(),i,j;
+        ProcessDetails temp;
+        for(i=0;i<size;i++)
+        {
+            for(j=i+1;j<size-1;j++)
+            {
+                if(processes.get(j).getArrivalTime()>processes.get(j+1).getArrivalTime())
+                {
+                    temp=processes.get(j);
+                    processes.set(j,processes.get(j+1));
+                    processes.set(j+1,temp);
+                }
+            }
+        }
+
+}
+
+    /**
+     * this functions returns the order of the executions
+     */
+
+    public void scheduleProcesses() {
+        ArrayList<ProcessDetails> ready=new ArrayList<>();
+
+        int size = processes.size(),runtime,time=0;
+        int executed=0,j,k=0;
+        ProcessDetails running;
+
+        if (size == 0) {
+            return;
+        }
+
+
+        while(executed<size)
+        {
+            while(k<size && processes.get(k).getArrivalTime()<=time)//here we find the processes that have arrived.
+            {
+                ready.add(processes.get(k));
+                k++;
+            }
+
+            running=findShortestJob(ready);
+            if(running==null)
+            {
+                  time++;
+            }
+            else {
+                  runtime = running.getBurstTime();
+                  for (j = 0; j < runtime; j++) {
+                      time++;}
+                  schedule.add(running.getProcessId());
+                  ready.remove(running);
+                  executed++;
+                  }
+        }
+
+
+    }
+
+    /**
+     * this function evaluates the shortest job of all the ready processes (based on  a process burst time)
+     * @param ReadyProcesses an array list of ready processes
+     * @return returns the process' with the shortest burst time OR NULL if there are no ready processes
+     */
+    private ProcessDetails findShortestJob(ArrayList<ProcessDetails> ReadyProcesses) {
+        if (ReadyProcesses.isEmpty()){
+            return null;
+        }
+        int i,size = ReadyProcesses.size();
+        int minBurstTime = ReadyProcesses.get(0).getBurstTime(), temp, positionOfShortestJob = 0;
+
+
+        for (i = 1; i < size; i++) {
+            temp = ReadyProcesses.get(i).getBurstTime();
+            if (minBurstTime > temp  ) {
+                minBurstTime = temp;
+                positionOfShortestJob = i;
+            }
+        }
+
+        return ReadyProcesses.get(positionOfShortestJob);
+    }
+
+
+
+
+
+    }
+


Test patch:
diff --git a/src/test/java/com/thealgorithms/scheduling/SJFSchedulingTest.java b/src/test/java/com/thealgorithms/scheduling/SJFSchedulingTest.java
new file mode 100644
index 00000000..8ba3b679
--- /dev/null
+++ b/src/test/java/com/thealgorithms/scheduling/SJFSchedulingTest.java
@@ -0,0 +1,120 @@
+package com.thealgorithms.scheduling;
+
+import com.thealgorithms.devutils.entities.ProcessDetails;
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SJFSchedulingTest {
+    private  ArrayList<ProcessDetails> process;
+    void initialisation0()
+    {
+
+        process=new ArrayList<>();
+        process.add(new ProcessDetails("1",0 ,6));
+        process.add(new ProcessDetails("2",1,2));
+    }
+    void initialisation1()
+    {
+
+        process=new ArrayList<>();
+        process.add(new ProcessDetails("1",0 ,6));
+        process.add(new ProcessDetails("2",1,2));
+        process.add(new ProcessDetails("3",4 ,3));
+        process.add(new ProcessDetails("4",3,1));
+        process.add(new ProcessDetails("5",6 ,4));
+        process.add(new ProcessDetails("6",5,5));
+    }
+
+    void initialisation2()
+    {
+
+        process=new ArrayList<>();
+        process.add(new ProcessDetails("1",0 ,3));
+        process.add(new ProcessDetails("2",1,2));
+        process.add(new ProcessDetails("3",2 ,1));
+
+    }
+    void initialisation3(){
+        process=new ArrayList<>();
+        process.add(new ProcessDetails("1",0 ,3));
+        process.add(new ProcessDetails("2",5,2));
+        process.add(new ProcessDetails("3",9 ,1));
+    }
+    @Test
+    void constructor()
+    {
+        initialisation0();
+        SJFScheduling a=new SJFScheduling(process);
+         assertEquals( 6,a.processes.get(0).getBurstTime());
+        assertEquals( 2,a.processes.get(1).getBurstTime());
+    }
+
+     @Test
+    void sort()
+    {
+        initialisation1();
+        SJFScheduling a=new SJFScheduling(process);
+        a.sortByArrivalTime();
+        assertEquals("1",a.processes.get(0).getProcessId());
+        assertEquals("2",a.processes.get(1).getProcessId());
+        assertEquals("3",a.processes.get(3).getProcessId());
+        assertEquals("4",a.processes.get(2).getProcessId());
+        assertEquals("5",a.processes.get(5).getProcessId());
+        assertEquals("6",a.processes.get(4).getProcessId());
+
+    }
+
+    @Test
+    void scheduling(){
+        initialisation1();
+        SJFScheduling a=new SJFScheduling(process);
+        a.scheduleProcesses();
+        assertEquals( "1"  , a.schedule.get(0));
+        assertEquals( "4"  , a.schedule.get(1));
+        assertEquals(  "2" , a.schedule.get(2));
+        assertEquals(  "3" , a.schedule.get(3));
+        assertEquals("5"   , a.schedule.get(4));
+        assertEquals(   "6", a.schedule.get(5));
+
+
+    }
+
+    @Test
+    void schedulingOf_TwoProcesses(){
+        initialisation0();
+        SJFScheduling a=new SJFScheduling(process);
+        a.scheduleProcesses();
+        assertEquals( "1"  , a.schedule.get(0));
+        assertEquals( "2"  , a.schedule.get(1));
+    }
+
+    @Test
+    void schedulingOfA_ShortestJobArrivingLast(){
+        initialisation2();
+        SJFScheduling a=new SJFScheduling(process);
+        a.scheduleProcesses();
+        assertEquals( "1"  , a.schedule.get(0));
+        assertEquals( "3"  , a.schedule.get(1));
+        assertEquals( "2"  , a.schedule.get(2));
+    }
+    @Test
+    void scheduling_WithProcessesNotComingBackToBack(){
+        initialisation3();
+        SJFScheduling a=new SJFScheduling(process);
+        a.scheduleProcesses();
+        assertEquals( "1"  , a.schedule.get(0));
+        assertEquals( "2"  , a.schedule.get(1));
+        assertEquals( "3"  , a.schedule.get(2));
+    }
+    @Test
+    void schedulingOf_nothing(){
+        process=new ArrayList<>();
+        SJFScheduling a=new SJFScheduling(process);
+        a.scheduleProcesses();
+        assertTrue( a.schedule.isEmpty());
+
+    }
+}
\ No newline at end of file