Let’s use maxima to determine how to deal with cycles of length 3:

I1 : m1*c12-m2*c22;
I2 : m2*c23-m3*c33;
I3 : m3*c31-m1*c11;
solve([I - I1, I - I2, I - I3], [m1, m2, m3]);
solve([I1 - I2, I2 - I3], [m2, m3]);

Now, for cycle of length 4 (from 1 to 2 to 3 to 2 and to 1 again):

I1 : m4*c41-m1*c11;
I2 : m1*c12+m3*c32-m2*c22-m4*c42;
I3 : m2*c23-m3*c33;
solve([I - I1, I - I2, I - I3], [m2, m3, m4]);

There are several ways for fixing the moving fractions. Let’s fix one of those quantity:

m4: 0;
solve([I1 - I2, I1 - I3], [m2, m3]);

This way, we can deduce the amount to move. Let’s focus on transitions from 1 to 2 to 3 and back only to 2.

I1 : -m1*c11;
I2 : m1*c12+m3*c32-m2*c22;
I3 : m2*c23-m3*c33;
solve([I1 - I2, I1 - I3], [m2, m3]);

OK, let’s try the method with some random input and compare it to the optimal LP.

n <- 5
# Test for triggered assertions with 5 tasks
for (i in 1:1000) {
  costs <- replicate(3, { rgamma(n = n, shape = 1, scale = 1) })
  alloc_max_cycle(costs)
}
# Compare with the optimal LP with 5 tasks
replicate(1000, {
  costs <- replicate(3, { rgamma(n = n, shape = 1, scale = 1) })
  alloc_LP(costs)$mks - alloc_max_cycle(costs)$mks
}) %>% plot.ecdf()

This seems correct. Let’s use larger instances.

n <- 20
# Test for triggered assertions with 20 tasks
for (i in 1:100) {
  costs <- replicate(3, { rgamma(n = n, shape = 1, scale = 1) })
  alloc_max_cycle(costs)
}
# Compare with the optimal LP with 20 tasks
replicate(100, {
  costs <- replicate(3, { rgamma(n = n, shape = 1, scale = 1) })
  alloc_LP(costs)$mks - alloc_max_cycle(costs)$mks
}) %>% plot.ecdf()

This also seems correct. Let’s try all combinations with specific costs.

# Test all instances with 2 tasks and 3 costs
replicate(2 * 3, { c(0.1, 0.5, 0.9) }) %>%
  apply(2, list) %>% flatten() %>%
  expand.grid() %>%
  apply(1, function(x) { list(matrix(x, ncol = 3)) }) %>% flatten() %>%
  map_dbl(~ alloc_LP(.)$mks - alloc_max_cycle(.)$mks) %>%
  plot.ecdf()

# Test all instances with 4 tasks and 2 costs
replicate(4 * 3, { c(0.1, 1) }) %>%
  apply(2, list) %>% flatten() %>%
  expand.grid() %>%
  apply(1, function(x) { list(matrix(x, ncol = 3)) }) %>% flatten() %>%
  map_dbl(~ alloc_LP(.)$mks - alloc_max_cycle(.)$mks) %>%
  plot.ecdf()

OK, the method is always similar to the optimal one. Let’s study the number of iterations:

replicate(300, {
  n <- sample(3:20, 1)
  costs <- replicate(3, { rgamma(n = n, shape = 1, scale = 1) })
  c(alloc_max_cycle(costs), list(costs))
}) -> res
plot(map_int(res[4,], nrow), unlist(res[3,]))

table(unlist(res[3,]) - 2 * map_int(res[4,], nrow) + 2)
## 
##   0   1   2   3 
## 260  35   4   1

This is not perfect. There are sometimes one or two more iterations than necessary even if we favor transitions that do not augment any depleted task on a given processor, and then cycle with three processors, and then cycle with the best improvements in terms of density.

replicate(100, {
  costs <- replicate(3, { rgamma(n = 10, shape = 1, scale = 1) })
  c(alloc_max_cycle(costs), list(costs))
}) -> res
table(unlist(res[3,]))
## 
## 18 19 20 
## 94  4  2

It is also possible to favor the transitions that decreases the makespan the most but it does not help. It remains to identify a strategy to make sure the number of iterations is in O(n).

## 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      digest_0.6.9     assertthat_0.1   plyr_1.8.1      
##  [5] grid_3.3.3       R6_2.1.2         gtable_0.1.2     DBI_0.6         
##  [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.3     
## [17] munsell_0.4      yaml_2.1.13      colorspace_1.2-2 htmltools_0.3.5 
## [21] knitr_1.14       tibble_1.2