Question 1 : Simulation of a G/G/k queue with different scheduling disciplines.

First, let’s define the function that will simulate each simulation.

do_one_simulation <- function(Service, Arrival, k, scheduling_discipline, debug) {
  CurrentTasks = rep(k, x=NA);
  AvgJobs = 0;
  t = 0;
  NextArrival = 1;
  Remaining = rep(N, x=NA);    # Remaining service times of each job
  Completion = rep(N, x=NA);   # Completion time of each job

  while (TRUE) {
        
        if (debug==1){
            print("*********BEFORE NEXT TASK************");
            print(Arrival);
            print(Service);
            print(Remaining);
        }
      
            dtA = 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
            }
            
            dtC = rep(NA, k);  # Time to completion for each server
            
            if (!all(is.na(CurrentTasks))) {  # If at least one task is running
                dtC[!is.na(CurrentTasks)] = Remaining[CurrentTasks[!is.na(CurrentTasks)]];  # Time to completion for each server
            }
            
            if (is.na(dtA) & all(is.na(dtC))) {  # If no arrival and no completion
                break;  # Exit
            }
            
            dt = min(c(dtA, dtC), na.rm = TRUE);  # Calculation of the next event time

            # update system variables
            t = t + dt;
            AvgJobs = AvgJobs+dt*sum(!is.na(Remaining));
      
        if (debug==1){
            print(paste("Sim. time:", t));
            print(paste("# of jobs arrived: ", NextArrival));
        }
            # Job arrival
            if((NextArrival <=N) & (Arrival[NextArrival] == t)) {
                Remaining[NextArrival] = Service[NextArrival];
                NextArrival = NextArrival + 1;
            }
      
            # Job departure
        
            for (i in 1:k) { # Foreach servers (k)
              if (!is.na(CurrentTasks[i])) {  # If a task is not in progress
                Remaining[CurrentTasks[i]] = Remaining[CurrentTasks[i]] - dt;  # Update remaining service time
                if (Remaining[CurrentTasks[i]] <= 0) {  # If task finished
                  Completion[CurrentTasks[i]] = t;  # Update completion time
                  Remaining[CurrentTasks[i]] = NA;  # Free server
                  CurrentTasks[i] = NA; # Free server
                }
              }
            }

            # Scheduling discipline
            
            # Changes made to avoid the same job being selected by many servers
            WaitingList = which(!is.na(Remaining));
            for (i in 1:k) {
              if (!is.na(CurrentTasks[i])) {
                WaitingList = WaitingList[WaitingList != CurrentTasks[i]];
              }
            }
            

            for (i in 1:k) {
              # For this part, I will make the assumption that each "server" can't release a job before it is done with it.
              # This is why if the server is busy, we will skip the iteration.
              if (!is.na(CurrentTasks[i])) {
                # Skip iteration
                next;
              }

              # The waiting queue will now evolves depending on the scheduling discipline
              # If the waiting list is empty, we will break the loop
              if (length(WaitingList) == 0) {
                break;
              }
              
              
              # FCFS
              if (scheduling_discipline == 1) {
                SelectedTask = head(WaitingList,n=1);
              }
              
              # LCFS
              if (scheduling_discipline == 2) {
                SelectedTask = tail(WaitingList,n=1);
              }
              
              # ROS: Random Order of Service
              if (scheduling_discipline == 3) {
                if (length(WaitingList)>1) {
                  SelectedTask = sample(WaitingList,size=1);
                } else {
                  # To avoid the error when we have only one task in the waiting list that implies the wrong sample behavior
                  SelectedTask = WaitingList;
                }
              }
              
              # SRPT: Shortest Remaining Processing Time
              if (scheduling_discipline == 4) {
                if (length(WaitingList)>1) {
                  SelectedTask = WaitingList[which.min(Remaining[WaitingList])];
                } else {
                  # Possible unwanted behavior too
                  SelectedTask = WaitingList;
                }
              }
              
              # Generics steps :
              if (debug==1){
                print(paste("Server ", i, " selected task ", SelectedTask));
              }
              
              # Removing the selected task from the waiting list
              # to avoid having two servers working on the same task
              WaitingList = WaitingList[WaitingList!=SelectedTask];
              
              # Assign the task to the server
              CurrentTasks[i] = SelectedTask;
            }
      
            if (debug==1){
                for (i in 1:k) {
                  
                    print(paste("Server ",i," --task-> ",CurrentTasks[i]));
                }
                # If line = stop we will stop the simulation
                line = readline(prompt="Press [enter] to proceed")
                if (line == "stop") {
                  break;
                }
                
            }
            
        } # while
    
  # Result with Meann Response Time + Average Jobs
    ResponseTime = mean(Completion-Arrival); #average response time
    AvgJobs=AvgJobs/(tail(Completion,n=1)-Arrival[1]);
    return(c(ResponseTime, AvgJobs));
}

Comparison of scheduling disciplines for a G/G/k queue.

# This function plot the average response time of a G/G/1 queue for various scheduling disciplines.
# As input, it takes the job service times (Service) and their mean value (ES)
plot_response_times_debug <- function(Service, ES, k, debug){

    scheduling_disciplines = c(1:4); # 'FCFS'=1,'LCFS'=2,'RO-S'=3,'SRPT'=4
    num_arrival_rates=5;
    lambdas = (1/ES) * c(1:num_arrival_rates)/(num_arrival_rates+1) ;
    
    # Matrix of average response times for all disciplines and arrival rates
    R_time <- matrix(0, nrow = length(scheduling_disciplines), ncol = length(lambdas));
    rownames(R_time) <- c("FCFS","LCFS","RO-S","SRPT");
    colnames(R_time) <- paste("rho=", round(lambdas*ES, digits = 3), sep = "");
    
    cnt=0;
    for (lambda in lambdas)
    {
      cnt=cnt+1;
      # Let's assume a Poisson process coming in, otherwise change the next line
      Arrival= cumsum(rexp(n=N, rate = lambda)); # Arrival times
  
      for (scheduling_discipline in scheduling_disciplines)
      {
        # Simulation
        res = do_one_simulation(Service, Arrival, k, scheduling_discipline, debug);
        
        ResponseTime = res[1];
        AvgJobs = res[2];
  
        # Simulation completed. Let's verify Little law: N=lambda*R
        r_names=rownames(R_time)
        cat(paste("Sim. ",r_names[scheduling_discipline],"(rho=",round(lambda*ES,digits = 2),") completed."));
        cat(paste(" Little law verification: ", round(AvgJobs,digits = 4), "=N=lambda*R=", round(lambda*ResponseTime,digits = 4),"\n"));
        
        R_time[scheduling_discipline,cnt]=ResponseTime;
  
      } # loop scheduling discipline
    
    } # loop lambda
    
    cat("\nResponse time matrix:\n")
    print(R_time)
    
    matplot(t(R_time), type = "l", xlab="Load (lambda*E[S])", ylab="Avg Response Time", xaxt = "n", lwd = 3);
    title(paste("Avg Response Time for a G/G/", k, " queue"));
    legend("topleft", legend = rownames(R_time), col=1:4, pch=1);
    axis(side=1,at=1:ncol(R_time),labels=round(lambdas*ES, digits=3));


} # end function

plot_response_times <- function(Service, ES, k) {
  plot_response_times_debug(Service, ES, k, debug=0);
}

Now let’s run this code to compare G/G/k with k from 1 to 4 while considering exponentially distributed service times.

Question 2 : Simulation and numerical evidence of the dynamics induced by 10 arrivals with k = 3.

To validate our simulation method, we will go through two steps.

Step 1 : Analysis of the dynamics of the system manually

Just by enabling the debug mode, we can see that the system seems to be working as expected in code below.

# Set seed for reproducibility
set.seed(11)

# Defining the parameters
N = 10
mu = 1
lambda = mu*0.9

# Generate service times and arrival times
Service = rexp(N, rate = mu)
Arrival = cumsum(rexp(N, rate = lambda))

# Simulate with k = 3
res = do_one_simulation(Service, Arrival, k = 3, scheduling_discipline = 1, debug = 1)
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1] NA NA NA NA NA NA NA NA NA NA
## [1] "Sim. time: 0.891587708429707"
## [1] "# of jobs arrived:  1"
## [1] "Server  1  selected task  1"
## [1] "Server  1  --task->  1"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1] 0.8021464        NA        NA        NA        NA        NA        NA
##  [8]        NA        NA        NA
## [1] "Sim. time: 1.69373406587186"
## [1] "# of jobs arrived:  2"
## [1] "Server  1  --task->  NA"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1] NA NA NA NA NA NA NA NA NA NA
## [1] "Sim. time: 1.81864325422705"
## [1] "# of jobs arrived:  2"
## [1] "Server  1  selected task  2"
## [1] "Server  1  --task->  2"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]       NA 6.992977       NA       NA       NA       NA       NA       NA
##  [9]       NA       NA
## [1] "Sim. time: 3.09453135713731"
## [1] "# of jobs arrived:  3"
## [1] "Server  2  selected task  3"
## [1] "Server  1  --task->  2"
## [1] "Server  2  --task->  3"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]         NA 5.71708854 0.02121675         NA         NA         NA
##  [7]         NA         NA         NA         NA
## [1] "Sim. time: 3.11574810309132"
## [1] "# of jobs arrived:  4"
## [1] "Server  1  --task->  2"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]       NA 5.695872       NA       NA       NA       NA       NA       NA
##  [9]       NA       NA
## [1] "Sim. time: 4.3106877062976"
## [1] "# of jobs arrived:  4"
## [1] "Server  2  selected task  4"
## [1] "Server  1  --task->  2"
## [1] "Server  2  --task->  4"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]       NA 4.500932       NA 4.203723       NA       NA       NA       NA
##  [9]       NA       NA
## [1] "Sim. time: 7.40382971877269"
## [1] "# of jobs arrived:  5"
## [1] "Server  3  selected task  5"
## [1] "Server  1  --task->  2"
## [1] "Server  2  --task->  4"
## [1] "Server  3  --task->  5"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]       NA 1.407790       NA 1.110581 2.463376       NA       NA       NA
##  [9]       NA       NA
## [1] "Sim. time: 8.51441032593757"
## [1] "# of jobs arrived:  6"
## [1] "Server  1  --task->  2"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  5"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]        NA 0.2972096        NA        NA 1.3527952        NA        NA
##  [8]        NA        NA        NA
## [1] "Sim. time: 8.81161990067733"
## [1] "# of jobs arrived:  6"
## [1] "Server  1  --task->  NA"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  5"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]       NA       NA       NA       NA 1.055586       NA       NA       NA
##  [9]       NA       NA
## [1] "Sim. time: 8.94489683422792"
## [1] "# of jobs arrived:  6"
## [1] "Server  1  selected task  6"
## [1] "Server  1  --task->  6"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  5"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]        NA        NA        NA        NA 0.9223087 0.8530472        NA
##  [8]        NA        NA        NA
## [1] "Sim. time: 9.79794405142833"
## [1] "# of jobs arrived:  7"
## [1] "Server  1  --task->  NA"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  5"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]         NA         NA         NA         NA 0.06926147         NA
##  [7]         NA         NA         NA         NA
## [1] "Sim. time: 9.8672055198672"
## [1] "# of jobs arrived:  7"
## [1] "Server  1  --task->  NA"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1] NA NA NA NA NA NA NA NA NA NA
## [1] "Sim. time: 10.373502334376"
## [1] "# of jobs arrived:  7"
## [1] "Server  1  selected task  7"
## [1] "Server  1  --task->  7"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]         NA         NA         NA         NA         NA         NA
##  [7] 0.08540696         NA         NA         NA
## [1] "Sim. time: 10.3844303932693"
## [1] "# of jobs arrived:  8"
## [1] "Server  2  selected task  8"
## [1] "Server  1  --task->  7"
## [1] "Server  2  --task->  8"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]        NA        NA        NA        NA        NA        NA 0.0744789
##  [8] 1.2830445        NA        NA
## [1] "Sim. time: 10.4589092969192"
## [1] "# of jobs arrived:  9"
## [1] "Server  1  --task->  NA"
## [1] "Server  2  --task->  8"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]       NA       NA       NA       NA       NA       NA       NA 1.208566
##  [9]       NA       NA
## [1] "Sim. time: 11.4998355202148"
## [1] "# of jobs arrived:  9"
## [1] "Server  1  selected task  9"
## [1] "Server  1  --task->  9"
## [1] "Server  2  --task->  8"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]        NA        NA        NA        NA        NA        NA        NA
##  [8] 0.1676393 0.4679750        NA
## [1] "Sim. time: 11.6674748444317"
## [1] "# of jobs arrived:  10"
## [1] "Server  1  --task->  9"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]        NA        NA        NA        NA        NA        NA        NA
##  [8]        NA 0.3003357        NA
## [1] "Sim. time: 11.9678105056989"
## [1] "# of jobs arrived:  10"
## [1] "Server  1  --task->  NA"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1] NA NA NA NA NA NA NA NA NA NA
## [1] "Sim. time: 12.9890195222497"
## [1] "# of jobs arrived:  10"
## [1] "Server  1  selected task  10"
## [1] "Server  1  --task->  10"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1]        NA        NA        NA        NA        NA        NA        NA
##  [8]        NA        NA 0.1473714
## [1] "Sim. time: 13.1363909652382"
## [1] "# of jobs arrived:  11"
## [1] "Server  1  --task->  NA"
## [1] "Server  2  --task->  NA"
## [1] "Server  3  --task->  NA"
## Press [enter] to proceed
## [1] "*********BEFORE NEXT TASK************"
##  [1]  0.8915877  1.8186433  3.0945314  4.3106877  7.4038297  8.9448968
##  [7] 10.3735023 10.3844304 11.4998355 12.9890195
##  [1] 0.80214636 6.99297665 0.02121675 4.20372262 2.46337580 0.85304722
##  [7] 0.08540696 1.28304445 0.46797499 0.14737144
##  [1] NA NA NA NA NA NA NA NA NA NA

Step 2: Simulation vs Numerical evidence

We will now compare the simulation results with the theoretical results for the average response time of an M/M/c queue.

But before let’s define some useful functions :

We can now run the simulation and compare the results for an example.

# Set seed for reproducibility
set.seed(11)

# Defining the parameters
N =  1e4
mu = 1
lambda = mu * 0.9
k = 3

results = simulate_and_calculate_response_time(N, mu, lambda, k)

# Print the results
cat("Simulated Avg Response Time:", results[1], "\n")
## Simulated Avg Response Time: 1.027974
cat("Theoretical Avg Response Time:", results[2], "\n")
## Theoretical Avg Response Time: 1.023844

The out coming results are promising because the simulated average response time is really close to the theoretical average response time.

Our simulation seems to be working as expected.

Question 3 : 5 times faster G/G/1 queue vs G/G/k queue with k = 5

Plotting a G/G/1 queue with 5 times faster service times than a G/G/5 queue.

set.seed(11); # Set seed for reproducibility
N = 8e3; # number of jobs to simulate;

mu=5;

Service1=rexp(N,rate=mu); # Service times of G/G/1
Service2=rexp(N, rate=mu/5); # Service times of G/G/5

#print (Service1)
#print (Service2)


num_arrival_rates=7;
lambdas = (mu) * c(c(1:num_arrival_rates)/(num_arrival_rates+0.4)) ;

# Matrix of average response times for all disciplines and arrival rates
R_time = matrix(0, nrow = 2, ncol = length(lambdas));
rownames(R_time) = c("G/G/1","G/G/5");
colnames(R_time) = paste("rho=", round(lambdas*(1/mu), digits = 3), sep = "");
ratios = numeric(length(lambdas))
cnt=0;
for (lambda in lambdas) {
  # do_one_simulation <- function(Service, Arrival, k, scheduling_discipline, debug)
  cnt=cnt+1;
  Arrival= cumsum(rexp(n=N, rate = lambda)); # Arrival times
  res1 = do_one_simulation(Service1, Arrival, 1, 1, 0);
  res2 = do_one_simulation(Service2, Arrival, 5, 1, 0);
  R_time[1,cnt]=res1[1];
  R_time[2,cnt]=res2[1];
  ratios[cnt] = res1[1]/res2[1];
}

cat("\nResponse time matrix:\n")
print(R_time)

matplot(t(R_time), type = "l", xlab="Load (lambda*(1/mu))", ylab="Avg Response Time", xaxt = "n", lwd = 3);
legend("topleft", legend = rownames(R_time), col=1:2, pch=1);
axis(side=1,at=1:ncol(R_time),labels=round(lambdas*(1/mu), digits=3));
title("G/G/1 vs G/G/5: Avg Response Time");

# Ratio plot
matplot(lambdas*(1/mu), ratios, type = "l", xlab="Load (lambda*(1/mu))", ylab="Avg Response Time Ratio (G/G/1)/(G/G/5)", lwd=3);
title("G/G/1 vs G/G/5: Avg Response Time Ratio");

The result is consistent with the intuition that the G/G/1 queue is faster by far than the G/G/5 queue when the load is low. This is due to the fact that the minimum time of treatment of a job is 5 time lower in the G/G/1 queue, which leads to a much lower response time for the G/G/1 queue when the load is low (low stress level). However, We can see that the more we approach the load of 1, the more G/G/5 queue closes the gap with the G/G/1 queue.

Question 4 : Find the value of the ratio defined in the previous point in a limiting regime where the load approaches one from below. Provide some intuition for the obtained value.

For this question, let’s take a closer look at our expectation and the obtained value from the previous question.

As said at the end of the previous question, the more we approach the load of 1, the more G/G/5 queue should closes the gap with the G/G/1 queue. This is why we expect a ratio close to 1 when the load approaches 1 from below.

By analyzing the ratio plot, we can see that it is indeed the case :

It is clear that the closer we get to the load of 1, the more the ratio approaches 1. This seems to confirm our intuition.