The first implementation of the new greedy algorithm for \((Pm,Pk)||C_{\max}\) was not sastisfactory. Let’s test the new one and compare it to the previous one. We also include the new LPT balanced method to check that the new LB is always below.

m <- 3
k <- 3
n <- 15
tests <- replicate(1000, {
  costs <- matrix(c(runif(n, min = 0, max = 2),
                    runif(n, min = 0, max = 2)),
                  nrow = n, byrow = FALSE)
  alloc_init <- allocation_greedy_balance(costs, m, k)
  mks_new <- schedule_greedy_balance(costs, m, k)$mks
  LB_new <- LB_greedy_balance(costs, m, k)
  LPT_balance <- schedule_LPT_balance(costs, m, k, strategy = "abssuff")$mks
  unlist(list(mks_init = alloc_init$mks, mks_new = mks_new,
              LB_init = alloc_init$LB, LB_new = LB_new,
              LPT_balance = LPT_balance))
})

Let’s first test that the bound is always smaller than any makespan with a particularly good heuristic:

which(tests["LPT_balance",] < tests["LB_new"])
## integer(0)

All good. Now, let’s see if the bound is equal to or better than the previous one.

summary(tests["LB_new",] - tests["LB_init",])
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
## 0.00000 0.00000 0.00000 0.01191 0.00000 0.33290

It is better than the previous one. This is due to the previous implementation being incomplete. Now the makespan of the new implementation should be equal to or better than the previous one.

plot.ecdf(tests["mks_init",] - tests["mks_new",])

This is actually not zero because the optimization may result in a worse allocation for the input of the final LPT. However, data show it is preferable.

The new implementation seems solid and this study confirms the previous one as well.

## R version 3.3.2 (2016-10-31)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 16.04.1 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] ggplot2_2.1.0 dplyr_0.4.3   tidyr_0.2.0   purrr_0.2.0   stringr_1.0.0
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_0.12.7      digest_0.6.9     assertthat_0.1   plyr_1.8.1      
##  [5] grid_3.3.2       R6_2.1.2         gtable_0.1.2     DBI_0.3.1       
##  [9] pacman_0.4.1     formatR_1.4      magrittr_1.5     scales_0.4.0    
## [13] evaluate_0.10    stringi_0.5-5    rmarkdown_1.1    tools_3.3.2     
## [17] munsell_0.4      parallel_3.3.2   yaml_2.1.13      colorspace_1.2-2
## [21] htmltools_0.3.5  knitr_1.14       tibble_1.2