Machine Reassignment is a problem posed by Google (for ROADEF Challenge 2012) in which a better configuration of processes to machines in terms of resource loading and resource balancing is pursued.
Solution Approach
Our approach consists of two main components: the Integer Programming Module and the Metaheuristic Module. These modules are activated in turn until time limit (300 sec) expires. Decisions about the processes and the machines that should be included in move relocation attempts are dictated by a taboo scheme. The IP Module address partitions of the full problem where iteratively a subset of the processes are allowed to move to a subset of the machines. The Metaheuristic Module expoits swap moves so as to find better allocations. These moves are incorporated in a metaheuristic that implements an adaptive version of a Late Acceptance scheme.
Implementation
The program was implemented in Java and uses ORTools developed by Google as a wrapper around a third party linear solver which in our case is CBC 2.7.5.
Results (on 8/12/2011)
| Dataset | LP Lower Bound | Senior - Open Source Category | |
|---|---|---|---|
| Cost | Time (seconds) | ||
| model_a1_1 | 44,306,480.4 | 44,306,501 | 47 |
| model_a1_2 | 777,530,747.5 | 778,206,505 | 300 |
| model_a1_3 | 583,005,700.2 | 583,038,554 | 300 |
| model_a1_4 | 242,392,996.1 | 282,009,209 | 297 |
| model_a1_5 | 727,578,295.8 | 727,582,988 | 294 |
| model_a2_1 | 65.1 | 1,030,119 | 291 |
| model_a2_2 | 29,349,215.6 | 1,078,453,898 | 297 |
| model_a2_3 | 573,167,429.5 | 1,496,353,090 | 298 |
| model_a2_4 | 1,680,231,435.7 | 1,761,975,869 | 268 |
| model_a2_5 | 307,040,586.5 | 417,543,422 | 298 |
New Results (31/01/2012)
| Dataset | Initial Cost | Cost |
|---|---|---|
| model_a1_1 | 49,528,750 | 44,306,501 |
| model_a1_2 | 1,061,649,570 | 777,534,031 |
| model_a1_3 | 583,662,270 | 583,009,491 |
| model_a1_4 | 632,499,600 | 260,654,544 |
| model_a1_5 | 782,189,690 | 727,582,435 |
| model_a2_1 | 391,189,190 | 200 |
| model_a2_2 | 1,876,768,120 | 1,033,837,163 |
| model_a2_3 | 2,272,487,840 | 1,399,161,091 |
| model_a2_4 | 3,223,516,130 | 1,680,969,151 |
| model_a2_5 | 787,355,300 | 364,919,534 |