Minimizing Weighted Mean Completion Time for Malleable Tasks Scheduling

This applet considers malleable tasks of bounded amount of processing resources. The goal is to compute scheduling that minimize the weighted completion time of tasks. The applet generates all possible greedy schedulings for a given instance and displays only the best ones (that are conjectured to be optimal).

All the details can be found in this paper (accepted at IPDPS 2012).

You can also download the source and check that best greedy solutions are optimal. This code needs the Java interface for glpk library to be installed.

- Install Java interface for glpk 
> wget
> jar -xf malleable.jar
> java -classpath <glpk library>  TestGreedyOptimality 5 50 w 
The last command line generates 50 random instances composed of 5 tasks and check that the best greedy solutions are optimal.

Last remark: this sage worksheet contains some functions that are useful when considering the MWCT of instances that have homogeneous volume and weight and such that delta_i >= P/2.