It was observed that our implementation of HeteroPrio is buggy. It does not perform all possible spoliations (each machine steals at most once whereas it should be that each machine interrupts an execution at most one). This impacts the results.

Let’s reimplement the algorithm and rerun the simulation.

n <- 300
m <- 20
k <- 4
cases <- data.frame(rbind(cv1 = c(0.2, 1, 0.2, 1), cv2 = c(0.2, 0.2, 1, 1)))
ratios <- map_df(cases, function(case) {
  replicate(100, {
    costs_CPU <- 15 * rgamma_cost(n, mean = 1, sd = case[1])
    costs_GPU <- rgamma_cost(n, mean = 1, sd = case[2])
    costs <- matrix(c(costs_CPU, costs_GPU), ncol = 2, byrow = FALSE)
    RR <- list(schedule_LPT_balance_greedy(costs, m, k),
               schedule_greedy_balance_proved(costs, m, k),
               schedule_DADA(costs, m, k),
               schedule_DualHP(costs, m, k),
               schedule_CLB2C(costs, m, k),
               schedule_HeteroPrio(costs, m, k))
    names(RR) <- c("LPT_bal", "greedy_bal", "DADA", "DualHP", "CLB2C",
                   "HeteroPrio")
    c(list(case = paste(map(case, ~ ifelse(. == 0.2, "low", "high")),
                        collapse = "/"),
           LB = LB_simple(costs, m, k)), map_dbl(RR, ~.$mks))
  }) %>% t() %>% data.frame() %>% map(unlist) %>% data.frame()
})
## Warning in rbind_all(x, .id): Unequal factor levels: coercing to character
balanceMakespan <- "\\textsc{BalancedMakespan}"
balanceEstimate <- "\\textsc{BalancedEstimate}"
dualHP <- "\\textsc{DualHP}"
heteroPrio <- "\\textsc{HeteroPrio}"
names(ratios)[3:ncol(ratios)] <- c(balanceMakespan, balanceEstimate, "DADA",
                                   dualHP, "CLB2C", heteroPrio)
ratios[,c("case", "LB", balanceMakespan, balanceEstimate, dualHP,
          "DADA", heteroPrio, "CLB2C")] %>%
  gather(key = "algo", value = "ratio", -case, -LB) %>%
  ggplot(aes(x = case, y = ratio / LB, color = algo)) +
  geom_boxplot(aes(group = interaction(algo, case)), outlier.size = 1) +
  coord_cartesian(ylim = extendrange(c(1, 1.2))) +
  scale_color_brewer("Algorithm", palette = "Set1") +
  scale_x_discrete("Coefficient of variation (CPU/GPU)") +
  scale_y_continuous("Makespan / LB")

map_dbl(ratios[,3:8], ~quantile(. / ratios$LB, probs = 0.025))
## \\textsc{BalancedMakespan} \\textsc{BalancedEstimate} 
##                   1.002756                   1.002756 
##                       DADA           \\textsc{DualHP} 
##                   1.009324                   1.002756 
##                      CLB2C       \\textsc{HeteroPrio} 
##                   1.036050                   1.033589
map_dbl(ratios[,3:8], ~quantile(. / ratios$LB, probs = 0.975))
## \\textsc{BalancedMakespan} \\textsc{BalancedEstimate} 
##                   1.074752                   1.145258 
##                       DADA           \\textsc{DualHP} 
##                   1.136329                   1.144228 
##                      CLB2C       \\textsc{HeteroPrio} 
##                   1.367646                   1.168800
map_dbl(3:8, ~ max(ratios[,.] / apply(ratios[,setdiff(3:8,.)], 1, min)))
## [1] 1.005036 1.158837 1.154255 1.140383 1.495513 1.206498
map_dbl(3:8, ~ length(which(ratios[,.] < apply(ratios[,setdiff(3:8,.)], 1, min) + 1e-5))) / nrow(ratios)
## [1] 0.9625 0.3600 0.0375 0.3825 0.0000 0.0000
## R version 3.4.0 (2017-04-21)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 16.04.2 LTS
## 
## Matrix products: default
## BLAS: /usr/lib/openblas-base/libblas.so.3
## LAPACK: /usr/lib/libopenblasp-r0.2.18.so
## 
## locale:
##  [1] LC_CTYPE=fr_FR.UTF-8       LC_NUMERIC=C              
##  [3] LC_TIME=fr_FR.UTF-8        LC_COLLATE=fr_FR.UTF-8    
##  [5] LC_MONETARY=fr_FR.UTF-8    LC_MESSAGES=fr_FR.UTF-8   
##  [7] LC_PAPER=fr_FR.UTF-8       LC_NAME=C                 
##  [9] LC_ADDRESS=C               LC_TELEPHONE=C            
## [11] LC_MEASUREMENT=fr_FR.UTF-8 LC_IDENTIFICATION=C       
## 
## attached base packages:
## [1] stats     graphics  grDevices utils     datasets  methods   base     
## 
## other attached packages:
## [1] ggplot2_0.9.3.1 dplyr_0.4.3     tidyr_0.2.0     purrr_0.2.0    
## [5] stringr_1.0.0  
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_0.12.10       knitr_1.15.1       magrittr_1.5      
##  [4] MASS_7.3-47        munsell_0.4        colorspace_1.2-2  
##  [7] R6_2.1.0           filehash_2.4-1     plyr_1.8.1        
## [10] tools_3.4.0        dichromat_2.0-0    parallel_3.4.0    
## [13] grid_3.4.0         tikzDevice_0.10-1  gtable_0.1.2      
## [16] pacman_0.4.6       DBI_0.3.1          htmltools_0.3.6   
## [19] lazyeval_0.1.10    yaml_2.1.13        rprojroot_1.2     
## [22] digest_0.6.3       assertthat_0.1     RColorBrewer_1.0-5
## [25] reshape2_1.2.2     evaluate_0.10      rmarkdown_1.5     
## [28] labeling_0.1       stringi_0.5-5      compiler_3.4.0    
## [31] scales_0.2.3       backports_1.0.5    proto_0.3-10