[9] | 1 | /* GAP, Generalized Assignment Problem */ |
---|
| 2 | |
---|
| 3 | /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
---|
| 4 | |
---|
| 5 | /* The Generalized Assignment Problem (GAP) is to assign a set of jobs |
---|
| 6 | to a set of agents subject to the constraints that each job must be |
---|
| 7 | assigned exactly to one agent and the total resources consumed by all |
---|
| 8 | jobs assigned to an agent must not exceed the agent's capacity. */ |
---|
| 9 | |
---|
| 10 | param m, integer, > 0; |
---|
| 11 | /* number of agents */ |
---|
| 12 | |
---|
| 13 | param n, integer, > 0; |
---|
| 14 | /* number of jobs */ |
---|
| 15 | |
---|
| 16 | set I := 1..m; |
---|
| 17 | /* set of agents */ |
---|
| 18 | |
---|
| 19 | set J := 1..n; |
---|
| 20 | /* set of jobs */ |
---|
| 21 | |
---|
| 22 | param a{i in I, j in J}, >= 0; |
---|
| 23 | /* resource consumed in allocating job j to agent i */ |
---|
| 24 | |
---|
| 25 | param b{i in I}, >= 0; |
---|
| 26 | /* resource capacity of agent i */ |
---|
| 27 | |
---|
| 28 | param c{i in I, j in J}, >= 0; |
---|
| 29 | /* cost of allocating job j to agent i */ |
---|
| 30 | |
---|
| 31 | var x{i in I, j in J}, binary; |
---|
| 32 | /* x[i,j] = 1 means job j is assigned to agent i */ |
---|
| 33 | |
---|
| 34 | s.t. one{j in J}: sum{i in I} x[i,j] = 1; |
---|
| 35 | /* job j must be assigned exactly to one agent */ |
---|
| 36 | |
---|
| 37 | s.t. lim{i in I}: sum{j in J} a[i,j] * x[i,j] <= b[i]; |
---|
| 38 | /* total amount of resources consumed by all jobs assigned to agent i |
---|
| 39 | must not exceed the agent's capacity */ |
---|
| 40 | |
---|
| 41 | minimize obj: sum{i in I, j in J} c[i,j] * x[i,j]; |
---|
| 42 | /* the objective is to find cheapest assignment (note that gap can also |
---|
| 43 | be formulated as maximization problem) */ |
---|
| 44 | |
---|
| 45 | data; |
---|
| 46 | |
---|
| 47 | /* These data correspond to the instance c515-1 (gap1) from: |
---|
| 48 | |
---|
| 49 | I.H. Osman, "Heuristics for the Generalised Assignment Problem: |
---|
| 50 | Simulated Annealing and Tabu Search Approaches", OR Spektrum, Volume |
---|
| 51 | 17, 211-225, 1995 |
---|
| 52 | |
---|
| 53 | D. Cattrysse, M. Salomon and L.N. Van Wassenhove, "A set partitioning |
---|
| 54 | heuristic for the generalized assignment problem", European Journal |
---|
| 55 | of Operational Research, Volume 72, 167-174, 1994 */ |
---|
| 56 | |
---|
| 57 | /* The optimal solution is 261 (minimization) or 336 (maximization) */ |
---|
| 58 | |
---|
| 59 | param m := 5; |
---|
| 60 | |
---|
| 61 | param n := 15; |
---|
| 62 | |
---|
| 63 | param a : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 := |
---|
| 64 | 1 8 15 14 23 8 16 8 25 9 17 25 15 10 8 24 |
---|
| 65 | 2 15 7 23 22 11 11 12 10 17 16 7 16 10 18 22 |
---|
| 66 | 3 21 20 6 22 24 10 24 9 21 14 11 14 11 19 16 |
---|
| 67 | 4 20 11 8 14 9 5 6 19 19 7 6 6 13 9 18 |
---|
| 68 | 5 8 13 13 13 10 20 25 16 16 17 10 10 5 12 23 ; |
---|
| 69 | |
---|
| 70 | param b := 1 36, 2 34, 3 38, 4 27, 5 33; |
---|
| 71 | |
---|
| 72 | param c : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 := |
---|
| 73 | 1 17 21 22 18 24 15 20 18 19 18 16 22 24 24 16 |
---|
| 74 | 2 23 16 21 16 17 16 19 25 18 21 17 15 25 17 24 |
---|
| 75 | 3 16 20 16 25 24 16 17 19 19 18 20 16 17 21 24 |
---|
| 76 | 4 19 19 22 22 20 16 19 17 21 19 25 23 25 25 25 |
---|
| 77 | 5 18 19 15 15 21 25 16 16 23 15 22 17 19 22 24 ; |
---|
| 78 | |
---|
| 79 | end; |
---|