Let’s study Kasahara instances. We start by downloading them.

cd 18_using_kasahara_instances
mkdir -p instances/stg
for size in 50 #100 300 500
do
  wget http://www.kasahara.elec.waseda.ac.jp/schedule/ver2/rnc$size.tgz
  tar -xzf rnc$size.tgz
  if [ -d "$size" ]; then
    cd $size
    for file in $(ls)
    do
      mv "$file" "$(basename $file .stg)_$size.stg"
    done
    cd ..
    mv $size/* instances/stg
    rm -r $size
  fi
done
mkdir -p instances/kasahara
mkdir -p instances/params

Then, we complete the instance generation with costs on the GPU.

k_s <- c(1, 2, 4, 8)
mk_s <- c(1, 2, 3, 5)
files <- list.files(paste(prefix_path, "instances/stg", sep = "/"),
                    full.names = TRUE)
for (filename in files) {
  size <- type.convert(str_match(filename, "_([0-9]+)")[2])
  for (k in k_s)
    for (mk in mk_s) {
      m <- k * mk
      instance <- read_instance_stg(filename, tau = sqrt(m / k), CV_CPU = 0.3)
      g <- instance$g
      name_dot <- str_replace(filename, "/stg/", "/kasahara/") %>%
        str_replace(".stg", paste("_", m, "_", k, ".dot", sep = ""))
      write_graph_str(g, name_dot, "dot")
      schedule <- HEFT(m, k, g)
      LB <- LB_europar(cbind(get.vertex.attribute(g, "CPU"),
                             get.vertex.attribute(g, "GPU")), m, k)
      params <- data.frame(n = size, tau = sqrt(m / k), CV_CPU = 0.3,
                           m = m, k = k, CP = CP(g),
                           LB_europar = LB, HEFT = schedule$mks,
                           instance$params[c("Precedenceconstraintsgenerator",
                                             "Taskprocessingtimegenerator")])
      name_params <- str_replace(name_dot, "/kasahara/", "/params/") %>%
        str_replace("\\.dot", ".params")
      write.table(params, name_params, row.names = FALSE, sep = ",")
      name_HEFT <- str_replace(name_params, "\\.params", ".HEFT")
      capture.output(schedule, file = name_HEFT)
    }
}

We start now the algorithms.

# Generating results
PARAM=kasahara
RESULT=result_$PARAM.csv
> $RESULT
for k in 1 2 4 8
do
  for mk in 1 2 3 5
  do
    m=$((k * mk))
    rm -rf src/input/$PARAM
    mkdir -p src/input/$PARAM
    cp instances/$PARAM/*_$m\_$k.dot src/input/$PARAM
    ./src/test -m $m -k $k -i src/input/$PARAM
    sed "s/_\([0-9]*\).dot/_\1/" -i output_$m-$k.dat
    tail -n +2 output_$m-$k.dat >> $RESULT
  done
done
sed -i "1i\\$(head -n 1 output_$m-$k.dat)" $RESULT

# Mixing results with lower bounds
sed -i "s/\t/,/g" $RESULT
sed -i "s/ //g" $RESULT
for file in $(awk -F',' 'NR>1 { print "instances/params/" $1 ".params" }' $RESULT)
do
    tail -n 1 $file
done > $RESULT.tmp1
paste $RESULT <(echo $(head -n 1 $file); cat $RESULT.tmp1) > $RESULT.tmp2
rm $RESULT.tmp1
mv $RESULT.tmp2 $RESULT

And the results.

data <- read.csv(paste(prefix_path, "result_kasahara.csv", sep = "/"))
table(data$MxQE - data$EFiT)
## 
##    0 
## 2880
data %>%
  mutate(LB = pmax(CP, LB_europar)) %>%
  gather(algo, mks, QALS, ERLS, EFiT, Quik, Rati, HEFT) %>%
  mutate(algo = factor(algo, levels = c("Rati", "Quik", "QALS", "ERLS", "EFiT",
                                        "HEFT"),
                       labels = c("Ratio", "Quick", "QALS", "ERLS", "EFT/Mix",
                                  "HEFT"))) %>%
  ggplot(aes(x = Precedenceconstraintsgenerator, y = mks / LB, col = algo)) +
  geom_boxplot() +
  # scale_color_hue(name = "Algorithm", l = c(100, 80, 60, 40, 20, 0)) +
  scale_color_brewer(name = "Algorithm", palette = "Set1") +
  facet_grid(m / k ~ k)

This needs some additional analysis.

## R version 3.4.3 (2017-11-30)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 16.04.3 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] bindrcpp_0.2  igraph_1.0.1  ggplot2_2.2.1 dplyr_0.7.4   tidyr_0.2.0  
## [6] purrr_0.2.0   stringr_1.2.0
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_0.12.10       knitr_1.15.1       bindr_0.1         
##  [4] magrittr_1.5       munsell_0.4        colorspace_1.2-2  
##  [7] R6_2.1.0           rlang_0.1.6        plyr_1.8.1        
## [10] tools_3.4.3        grid_3.4.3         gtable_0.1.2      
## [13] pacman_0.4.6       htmltools_0.3.6    lazyeval_0.2.0    
## [16] yaml_2.1.13        rprojroot_1.2      digest_0.6.3      
## [19] assertthat_0.1     tibble_1.3.1       RColorBrewer_1.0-5
## [22] reshape2_1.2.2     glue_1.2.0         evaluate_0.10     
## [25] rmarkdown_1.8      labeling_0.1       stringi_0.5-5     
## [28] compiler_3.4.3     scales_0.4.1       backports_1.0.5   
## [31] pkgconfig_2.0.1