Step 0

  1. FCFS: jobs are processed following the order of their arrival. If a job’s deadline expires while it is being processed, the job is removed from the system. The server does not know the service times in advance.

Easiest to implement, the most natural scheduling. Requires no information about the job. However it might not prioritize jobs that need to be dealt with fast.

  1. EDF (Earliest Deadline First): jobs are processed according to the earliest deadline with preemption, i.e., the current job is interrupted if a new job with an earlier deadline arrives. The server does not know the service times in advance.

Easy to implement but it requires to know the deadlines. It is still rather limited and easy information to get.

  1. EDF-NP (Earliest Deadline First Non-preemptive): As EDF but jobs are not interrupted once their processing has started. The server does not know the service times in advance.

Just as easy as EDF to implement but it makes less job swirches. The disadvantage is that if a job enters and it’s deadline comes it is treated, the job will use processsor time for nothing (once the deadline has passed, it is useless).

  1. SRPT (Shortest Remaining Processing Time): the job with the shortest remaining processing time is served first. Here, the jobs whose remaining processing times overflow their corresponding deadlines are not considered, i.e., removed from the system.

Recquires to know both the service times and the deadlines as well as time already spent in the processor. It seems like it will provide great results but it si usually impossible to implement in practice.

  1. SRT2D (Shortest Remaining Time to Deadline): the job with the shortest remaining time to deadline is served first. Note that “the remaining time to deadline” is always non-negative because jobs that cannot be completed by the deadline are removed from the system.

Requires to know both the service times and the deadlines as well as time already spent in the processor. Has the same problem as SRPT. It improves by not starting the jobs that cannot be completed by the deadline. Not much harder to implement than SRPT but should yield better results.

  1. SERT2D (Shortest Expected Remaining Time to Deadline): as SRT2D but instead of the remaining time to deadline, we consider the expected remaining time to deadline. The server does not know the service times in advance (but it knows their distribution function).

Requires to know the deadlines and the distribution of the service times. It is a much easier information to get making it easier and more realistic to implement. It seems like a good way to get similar results to SRPT and SRT2D in a more realistic way.

Step 1 & 2

Simulation

knitr::opts_chunk$set(echo = TRUE)

# This function performs the required simulation.
# As input, it takes the job service times (Service), their expected value (ES), the job deadlines (relative to the absolute job arrival time), and the system load
run_simulation <- function(Service, ES, Deadline, rho,debug, scheduling_disciplines=c("EDF", "EDF-NP", "SRT2D", "SERT2D", "SRPT", "FCFS")){
    num_arrival_rates=1;
    lambda = rho/ES;
    
    # Matrix of average response times for all disciplines and arrival rates
    Results <- matrix(0, nrow = length(scheduling_disciplines), ncol = 3);
    rownames(Results) <- scheduling_disciplines;
    colnames(Results) <- c("RT", "MDR", "IDR"); # performance metrics
    
    # Let's assume a Poisson process coming in, otherwise change the next line
    Arrival= cumsum(rexp(n=N, rate = lambda)); # Arrival times
    AbsDeadline = Arrival+Deadline;
    
    for (scheduling_discipline in scheduling_disciplines)
    {
        t = 0; # simulation time
        Remaining = rep(N, x=NA);           # Remaining service times of each job
        ExpectedRemaining = rep(N, x=NA);  # Expected remaining service times of each job
        Completion = rep(N, x=NA);          # Completion time of each job
        
        CurrentTask = NA;
        NextArrival = 1;
        AvgJobs = 0;
        while (TRUE) {

if (debug==1){
    print("*********************");
    cat("Arrival:     ",Arrival,'\n');
    cat("AbsDeadline: ",AbsDeadline,'\n');
    cat("Service:     ",Service,'\n');
    cat("Remaining:   ",Remaining,'\n');
    cat("Sched discipline:",scheduling_discipline,'\n');
}
            dtA = NA; dtC = NA; dtE=NA;
            if(length(Arrival[Arrival>t])>0) { # if an arrival exists after t
                dtA = head(Arrival[Arrival>t],n=1)-t ; # time to next arrival
            }
            if(!is.na(CurrentTask)) { # if a task is running
                dtC = Remaining[CurrentTask]; # time to next completion
                dtE = AbsDeadline[CurrentTask] - t;
            }
            if(is.na(dtA) & is.na(dtC)) { # no more jobs to be serviced or to currently being serviced 
                break; # cut the simulation for this scheduling discipline
            }
        
            dt = min(dtA,dtC,dtE,na.rm=T);
            
if (debug==1){
    cat("dtA:     ",dtA,'\n');
    cat("dtC:     ",dtC,'\n');
    cat("dtE:     ",dtE,'\n');
    cat("dt:      ",dt,'\n');
}
        
            # update system variables
            t = t + dt;
            AvgJobs=AvgJobs+dt*sum(!is.na(Remaining));
            
            # Job arrival
            if((NextArrival <=N) & (Arrival[NextArrival] == t)) {
                Remaining[NextArrival] = Service[NextArrival];
                ExpectedRemaining[NextArrival] = ES;
                NextArrival = NextArrival + 1;
            }
        
            # Job departure
            if(!is.na(CurrentTask)) {
                Remaining[CurrentTask] = Remaining[CurrentTask] - dt;
                if(Remaining[CurrentTask] <= 0) {
                    # CurrentTask completed
                    Completion[CurrentTask] = t;
                    Remaining[CurrentTask] = NA;
                    ExpectedRemaining[CurrentTask] = NA;
                    CurrentTask = NA;
                }
            }
            
            # Job deadline reached
            if(!is.null(CurrentTask) && length(CurrentTask)==1 && !is.na(CurrentTask)){
              
                if(AbsDeadline[CurrentTask] == t){
                  Remaining[CurrentTask] = NA;
               #   ExpectedRemaining[CurrentTask] = NA;
                  CurrentTask = NA;
                }
            }
            
            
            # Scheduling discipline: Let's find the new task to process
            
            
if (debug==1){
    print(paste("Sim. time:", t));
    print(paste("# of jobs arrived: ", NextArrival));
}
              if (scheduling_discipline=="FCFS"){
                WaitingList=(1:NextArrival)[!is.na(Remaining) & AbsDeadline>t];
                if(length(WaitingList)>0) {
                  CurrentTask = head(WaitingList,n=1);
                }
              }
              
              if (scheduling_discipline=="EDF"){
                WaitingList=(1:NextArrival)[!is.na(Remaining) & AbsDeadline>t];
                if(length(WaitingList)>0) {
                  CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])];
                }
              }
        
              if (scheduling_discipline=="EDF-NP"){
                WaitingList=(1:NextArrival)[!is.na(Remaining) & AbsDeadline>t];
                if(length(WaitingList)>0) {
                  if (is.na(CurrentTask)) {
                    CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])];
                  } 
                }
              }

              if (scheduling_discipline=="SRPT"){
                WaitingList=(1:NextArrival)[!is.na(Remaining) & AbsDeadline > (t+Remaining)];
                if(length(WaitingList)>0) {
                    CurrentTask = WaitingList[which.min(Remaining[WaitingList])];
                }
              }
                
              if (scheduling_discipline=="SRT2D"){
                WaitingList=(1:NextArrival)[!is.na(Remaining) & AbsDeadline > (t+Remaining)];
                if(length(WaitingList)>0) {
                  CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList]-(t+Remaining[WaitingList]))];
                }
              }
                
              if (scheduling_discipline=="SERT2D"){
                WaitingList=(1:NextArrival)[!is.na(Remaining) & AbsDeadline > (t+ExpectedRemaining)];
                if(length(WaitingList)>0) {
                 CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList]-(t+ExpectedRemaining[WaitingList]))];
                }
              }
             
if (debug==1){
    cat("WaitingList:", WaitingList, "\n");
}
            
             if(is.null(CurrentTask)){
                CurrentTask = NA;
              }
    
if (debug==1){
    print(paste("Current Task = ", CurrentTask))
    #    readline(prompt="Press [enter] to proceed")
}
        
    } # while
        IDR=mean(Service>Deadline);
        MDR=mean(is.na(Completion));
        ResponseTime = mean(Completion-Arrival,na.rm=T); 
        AvgJobs=AvgJobs/(tail(Completion,n=1)-Arrival[1]);

if (debug>=0){
    cat(paste(" Little law verification: ", round(AvgJobs,digits = 4), "=N=lambda*R=", 
              round(lambda*ResponseTime,digits = 4),"\n"));
}        
        
        # Simulation completed.
        
        Results[scheduling_discipline,1]=ResponseTime;
        Results[scheduling_discipline,2]=MDR;
        Results[scheduling_discipline,3]=IDR;
        
        cat(scheduling_discipline," completed.\n");
    
    } # loop scheduling discipline
    
    cat("\nResults:\n")
    print(Results)
    
} # end function

Step 3

knitr::opts_chunk$set(echo = FALSE)

set.seed(9); # Set seed for reproducibility

N = 10; # number of jobs to simulate;

P=runif(N,0,1);
# Service times
Service=rep(N, x=NA);
for (i in 1:N) {
  if(P[i]<0.85){
    Service[i]=runif(1,0,10);
  }else{
    Service[i]=runif(1,90,110);
  }
}
x=5;
Deadline=Service*x; # Relative deadlines

rho=0.9; # load
run_simulation(Service, 5*0.85+100*0.15, Deadline, rho,1,scheduling_disciplines=c("SRT2D"));
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      0.3088366 
## dtC:      NA 
## dtE:      NA 
## dt:       0.3088366 
## [1] "Sim. time: 0.30883655100011"
## [1] "# of jobs arrived:  2"
## WaitingList: 1 
## [1] "Current Task =  1"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    1.17639 NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      52.30967 
## dtC:      1.17639 
## dtE:      5.881948 
## dt:       1.17639 
## [1] "Sim. time: 1.48522609061443"
## [1] "# of jobs arrived:  2"
## WaitingList:  
## [1] "Current Task =  NA"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      51.13328 
## dtC:      NA 
## dtE:      NA 
## dt:       51.13328 
## [1] "Sim. time: 52.618506269001"
## [1] "# of jobs arrived:  3"
## WaitingList: 2 
## [1] "Current Task =  2"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA 0.08471164 NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      27.24017 
## dtC:      0.08471164 
## dtE:      0.4235582 
## dt:       0.08471164 
## [1] "Sim. time: 52.7032179105399"
## [1] "# of jobs arrived:  3"
## WaitingList:  
## [1] "Current Task =  NA"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      27.15546 
## dtC:      NA 
## dtE:      NA 
## dt:       27.15546 
## [1] "Sim. time: 79.8586759261694"
## [1] "# of jobs arrived:  4"
## WaitingList: 3 
## [1] "Current Task =  3"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA 8.833668 NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      26.10692 
## dtC:      8.833668 
## dtE:      44.16834 
## dt:       8.833668 
## [1] "Sim. time: 88.6923440719862"
## [1] "# of jobs arrived:  4"
## WaitingList:  
## [1] "Current Task =  NA"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      17.27326 
## dtC:      NA 
## dtE:      NA 
## dt:       17.27326 
## [1] "Sim. time: 105.965600196068"
## [1] "# of jobs arrived:  5"
## WaitingList: 4 
## [1] "Current Task =  4"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA 3.010547 NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      2.974151 
## dtC:      3.010547 
## dtE:      15.05274 
## dt:       2.974151 
## [1] "Sim. time: 108.939751388811"
## [1] "# of jobs arrived:  6"
## WaitingList: 4 5 
## [1] "Current Task =  4"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA 0.03639589 4.927435 NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      14.89127 
## dtC:      0.03639589 
## dtE:      12.07858 
## dt:       0.03639589 
## [1] "Sim. time: 108.97614727568"
## [1] "# of jobs arrived:  6"
## WaitingList: 5 
## [1] "Current Task =  5"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA 4.927435 NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      14.85487 
## dtC:      4.927435 
## dtE:      24.60078 
## dt:       4.927435 
## [1] "Sim. time: 113.903582334314"
## [1] "# of jobs arrived:  6"
## WaitingList:  
## [1] "Current Task =  NA"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      9.927438 
## dtC:      NA 
## dtE:      NA 
## dt:       9.927438 
## [1] "Sim. time: 123.831020047508"
## [1] "# of jobs arrived:  7"
## WaitingList: 6 
## [1] "Current Task =  6"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA 5.006299 NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      12.04878 
## dtC:      5.006299 
## dtE:      25.0315 
## dt:       5.006299 
## [1] "Sim. time: 128.837319434241"
## [1] "# of jobs arrived:  7"
## WaitingList:  
## [1] "Current Task =  NA"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      7.042481 
## dtC:      NA 
## dtE:      NA 
## dt:       7.042481 
## [1] "Sim. time: 135.879800922875"
## [1] "# of jobs arrived:  8"
## WaitingList: 7 
## [1] "Current Task =  7"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA 4.020345 NA NA NA 
## Sched discipline: SRT2D 
## dtA:      40.84474 
## dtC:      4.020345 
## dtE:      20.10172 
## dt:       4.020345 
## [1] "Sim. time: 139.900145656601"
## [1] "# of jobs arrived:  8"
## WaitingList:  
## [1] "Current Task =  NA"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
## dtA:      36.8244 
## dtC:      NA 
## dtE:      NA 
## dt:       36.8244 
## [1] "Sim. time: 176.724542341702"
## [1] "# of jobs arrived:  9"
## WaitingList: 8 
## [1] "Current Task =  8"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA 9.770828 NA NA 
## Sched discipline: SRT2D 
## dtA:      9.46876 
## dtC:      9.770828 
## dtE:      48.85414 
## dt:       9.46876 
## [1] "Sim. time: 186.193302817503"
## [1] "# of jobs arrived:  10"
## WaitingList: 8 9 
## [1] "Current Task =  9"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA 0.3020677 3.58326 NA 
## Sched discipline: SRT2D 
## dtA:      3.093157 
## dtC:      3.58326 
## dtE:      17.9163 
## dt:       3.093157 
## [1] "Sim. time: 189.286460183758"
## [1] "# of jobs arrived:  11"
## WaitingList: 8 9 10 
## [1] "Current Task =  9"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA 0.3020677 0.4901027 99.83321 
## Sched discipline: SRT2D 
## dtA:      NA 
## dtC:      0.4901027 
## dtE:      14.82314 
## dt:       0.4901027 
## [1] "Sim. time: 189.77656292622"
## [1] "# of jobs arrived:  11"
## WaitingList: 8 10 
## [1] "Current Task =  8"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA 0.3020677 NA 99.83321 
## Sched discipline: SRT2D 
## dtA:      NA 
## dtC:      0.3020677 
## dtE:      35.80212 
## dt:       0.3020677 
## [1] "Sim. time: 190.078630663496"
## [1] "# of jobs arrived:  11"
## WaitingList: 10 
## [1] "Current Task =  10"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA 99.83321 
## Sched discipline: SRT2D 
## dtA:      NA 
## dtC:      99.83321 
## dtE:      498.3739 
## dt:       99.83321 
## [1] "Sim. time: 289.911841551815"
## [1] "# of jobs arrived:  11"
## WaitingList:  
## [1] "Current Task =  NA"
## [1] "*********************"
## Arrival:      0.3088366 52.61851 79.85868 105.9656 108.9398 123.831 135.8798 176.7245 186.1933 189.2865 
## AbsDeadline:  6.190784 53.04206 124.027 121.0183 133.5769 148.8625 155.9815 225.5787 204.1096 688.4525 
## Service:      1.17639 0.08471164 8.833668 3.010547 4.927435 5.006299 4.020345 9.770828 3.58326 99.83321 
## Remaining:    NA NA NA NA NA NA NA NA NA NA 
## Sched discipline: SRT2D 
##  Little law verification:  0.4995 =N=lambda*R= 0.6763 
## SRT2D  completed.
## 
## Results:
##             RT MDR IDR
## SRT2D 14.46585   0   0

Step 4

##  Little law verification:  2.7859 =N=lambda*R= 2.02 
## EDF  completed.
##  Little law verification:  NA =N=lambda*R= 3.6727 
## EDF-NP  completed.
##  Little law verification:  32.9874 =N=lambda*R= 2.528 
## SRT2D  completed.
##  Little law verification:  NA =N=lambda*R= 3.0938 
## SERT2D  completed.
##  Little law verification:  19.15 =N=lambda*R= 1.5064 
## SRPT  completed.
##  Little law verification:  NA =N=lambda*R= 4.2542 
## FCFS  completed.
## 
## Results:
##              RT   MDR IDR
## EDF    43.20560 0.038   0
## EDF-NP 78.55527 0.513   0
## SRT2D  54.07209 0.053   0
## SERT2D 66.17323 0.380   0
## SRPT   32.22012 0.029   0
## FCFS   90.99264 0.597   0

We achieved the best performance with SRPT. This makes it the best scheduling discipline in theory. However, as discussed in step 0, this is basically impossible to implement in practice. The second best is EDF. This ones requires very little informations and yields very close results.