Let’s compare several heuristics for the problem (Pm1,…,PmK)||Cmax with divisible tasks. Each task is initially on its best processor. Tasks are then moved one by one on another proc until it is not possible to decrease the makespan anymore. The LP solution is optimal.

functions <- c(alloc_most2any, alloc_any2least, alloc_most2least, alloc_any2any, alloc_LP)
replicate(100, {
  costs <- replicate(3, { rgamma(n = 30, shape = 1, scale = 1) })
  map_dbl(functions, ~.(costs)$mks)
}) %>% t() %>%
  list() %>% map(~. / apply(., 1, min)) %>% data.frame() %>%
  gather(method, ratio) %>%
  ggplot(aes(x = method, y = ratio)) +
  geom_boxplot()

None of these approaches is optimal, but the most efficient seems to allow task migration from any machine to any machine.

## R version 3.3.3 (2017-03-06)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 16.04.2 LTS
## 
## 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] Rsymphony_0.1-23 ggplot2_2.1.0    dplyr_0.5.0      tidyr_0.2.0     
## [5] purrr_0.2.0      stringr_1.0.0   
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_0.12.9      knitr_1.14       magrittr_1.5     munsell_0.4     
##  [5] colorspace_1.2-2 R6_2.1.2         plyr_1.8.1       tools_3.3.3     
##  [9] grid_3.3.3       gtable_0.1.2     pacman_0.4.1     DBI_0.6         
## [13] htmltools_0.3.5  yaml_2.1.13      lazyeval_0.1.10  assertthat_0.1  
## [17] digest_0.6.9     tibble_1.2       reshape2_1.2.2   formatR_1.4     
## [21] evaluate_0.10    rmarkdown_1.1    labeling_0.1     stringi_0.5-5   
## [25] scales_0.4.0