|
COPYRIGHT 2006 Institute for Operations Research and the Management Sciences
1. Introduction
The task allocation problem (TAP) is to assign a set of tasks or modules to a set of processors or machines so that the overall cost is minimized. The overall cost may include the task assignment cost and the interprocessor communication cost, among others. Sometimes processors may have a limited capacity or memory, which is shared by its assigned tasks. If some processors have capacity limits, then this version of the TAP is called the capacitated TAP (CTAP), otherwise it is called the uncapacitated TAP (UTAP).
The TAP is an important problem that arises in distributed computing systems (see Stone 1977) and has also been applied in the automobile manufacturing industry in Rao (1992). Many heuristic and exact algorithms have been designed for solving various versions of the TAP. Heuristic algorithms are developed in Dutta et al. (1982), Kopidakis et al. (1997), Lo (1988), Ma et al. (1982), Milis (1995), and Sarje and Sagar (1991); metaheuristic algorithms such as simulated annealing, tabu search, and genetic algorithms are proposed in Chen and Lin (2000), Hadj-Alouane et al. (1999), and Hamam and Hindi (2000); and exact mathematical programming and/or branch-and-bound approaches are used in Billionnet et al. (1992), Magirou and Milis (1989), Sinclair (1987), and Stone (1977).
Because of the complexity of the TAP, none of the above-mentioned algorithms, with the exception of Billionnet et al. (1992), are capable of solving some real-world applications optimally. Most versions of the TAP can be formulated as integer quadratic programs (see Hadj-Alouane et al. 1999, Hamam and Hindi 2000). The potential of mathematical programming approaches has not been fully explored for solving the TAP. In the last decade, great progress has been made both in computational power and computational technology of mathematical programming. In this paper, we show that exact mathematical programming approaches are viable alternatives to the heuristics as well as the exact methods mentioned above for obtaining solutions to the TAP. Our emphasis will be on the UTAP. We shall also discuss how the techniques to be introduced for the UTAP can be extended to the CTAP.
We define the TAP and its two special versions, UTAP and CTAP, in the next section. In [section]3, the UTAP is reformulated as integer linear programs using different variables. We explore the column generation approach for the UTAP in [section]4. Several integer linear programming (LP) formulations as well as a column generation formulation for the CTAP are summarized in [section]5. Computational results are reported in [section]6. We make some concluding remarks in [section]7.
2. Problem Definition
We consider the TAP arising from a distributed computing system. (1) The processors in the system are heterogeneous. In other words, a task may require different amounts of running time (or incur different execution costs) if assigned to different processors. (2) Identical links are used by the processors for message transmission. This means that identical messages, even if transmitted through different communication links, will have identical transmission times. That is, the communication cost between two tasks assigned to different processors is uniform (see Sinclair 1987).
N processors are used to perform M tasks, each of which is assigned to exactly one processor. Let [d.sub.ik] be the execution cost of task i if it is assigned to processor k. Let [b.sub.k] and [s.sub.k] be the capacity and the fixed cost for processor k, respectively. Let [a.sub.i] be the amount of the resource required from its assigned processor for task i. If two tasks i and j are assigned to two different processors, then the cost of communication between i and j is [c.sub.ij] (we assume that [c.sub.ij] = [c.sub.ji] and [c.sub.ii] = 0).
Define the binary decision variables. [x.sub.ik] = 1 if and only if task i is allocated to processor k. Define [y.sub.k] to be a binary variable so that [y.sub.k] = 1 if and only if processor k is assigned at least one task. The TAP can be cast as an integer quadratic program:
TAP min [M-1.summation over (i=1)][M.summation over (j=i+1)][c.sub.ij](1 - [N.summation over (k=1)][x.sub.ik][x.sub.jk]) + [M.summation over (i=1)][N.summation over (k=1)][d.sub.ik][x.sub.ik] + [N.summation over (k=1)][s.sub.k][y.sub.k] (1)
s.t. [N.summation over (k=1)][x.sub.ik] = 1, i = 1,..., M, (2)
[M.summation over (i=1)][a.sub.i][x.sub.ik] [less than or equal to] [b.sub.k][y.sub.k], k = 1,..., N, (3)
[x.sub.ik] [less than or equal to] [y.sub.k], i = 1,..., M, k = 1,..., N, (4)
[x.sub.ik] [member of] {0, 1}, [y.sub.k] [member of] {0, 1} [for all]i, k. (5)
The objective is to minimize the sum of the total communication cost between tasks, the overall execution cost of performing all tasks, and the overall fixed cost of using processors, which are assigned at least one task. The first term of the objective states that the communication cost between two tasks is incurred only if these two tasks are assigned to two different processors. Constraint (2) indicates that each task needs to be assigned to exactly one processor. Constraint (3) states that the total resource usage from the tasks assigned to a processor cannot exceed its capacity. Constraint (4) specifies that any task cannot be assigned to a processor that is not used. Constraint (5) ensures that both x and y are binary variables.
Constraint (4) is redundant if [a.sub.i] > for all i because it can be deduced from constraints (2), (3), and (5). We include constraint (4) in the TAP for two reasons. First, it is for mathematical correctness to allow for the trivial case, where [a.sub.i] = for some i. Second, this constraint can be used as a cut to improve computational efficiency. In fact, this constraint can be replaced by a weaker constraint: [[summation].sub.i=1.sup.M][x.sub.ik] [less than or equal to] My[.sub.k] for all k.
In the literature, several special versions of the TAP are considered. In particular, the following condition is assumed in Billionnet et al. (1992) and Kopidakis et al. (1997): (3) The capacities of processors and communication links are assumed to be unlimited.
The following version of the TAP is mostly studied in the literature, in which the fixed cost associated with processors is not included in the objective because it is assumed to be the sunk cost:
UTAP min [M-1.summation over (i=1)][M.summation over (j=i+1)][c.sub.ij](1 - [N.summation over (k=1)][x.sub.ik][x.sub.jk]) + [M.summation over (i=1)][N.summation over (k=1)][d.sub.ik][x.sub.ik] (6)
s.t. (2), [x.sub.ik] [member of] {0, 1}, i = 1,..., M, k = 1,..., N. (7)
The following problem is another important version of the TAP considered in the literature (see Chen and Lin 2000, Hadj-Alouane et al. 1999, Hamam and Hindi 2000):
CTAP min [M-1.summation over (i=1)][M.summation over (j=i+1)][c.sub.ij](1 - [N.summation over (k=1)][x.sub.ik][x.sub.jk]) + [N.summation over (k=1)][s.sub.k][y.sub.k] (8)
s.t. (2), (3), (4), (5).
The major difference between the UTAP and the CTAP is the resource capacity constraint. In addition, the two objectives are different although both include the communication cost.
3. Integer Linear Programming Formulations for the UTAP
The UTAP formulated in the previous section is an integer program with a quadratic objective and linear constraints. It is generally computationally expensive to find optimal solutions of integer quadratic programs. In this section, we provide various integer LP formulations for the UTAP.
Let [r.sub.ijkl] be a binary variable. [r.sub.ijkl] = 1 if and only if task i is assigned to processor k and j to l. Our four index integer LP-formulation, the UTAP4, is based on [r.sub.ijkl]:
UTAP4 min [M-1.summation over (i=1)][M.summation over (j=i+1)][N.summation over (k=1)][summation over (l[not equal to]k)][c.sub.ij][r.sub.ijkl] + [M.summation over (i=1)][N.summation over (k=1)][d.sub.ik][x.sub.ik] (9)
s.t. [N.summation over (k=1)][N.summation over (l=1)][r.sub.ijkl] = 1, i, j = 1,..., M, (10)
[N.summation over (k=1)][r.sub.ijkl] = [x.sub.jl], i, j = 1,..., M, l = 1,..., N, (11)
[N.summation over (l=1)][r.sub.ijkl] = [x.sub.ik], i, j = 1,..., M, k = 1,..., N, (12)
[x.sub.ik], [r.sub.ijkl] [member of] {0, 1}, i, j, k, l. (13)
Through introduction of the variable r, the quadratic term in the objective of the UTAP has been replaced by the linear term in the UTAP4. Constraint (2) is not included in the UTAP4. However, it is straightforward to deduce that from (10), (11), and (12).
Note that the integrality property of the variable r may be relaxed to be [r.sub.ijkl] [member of] [0, 1] and integrality will be automatically achieved in optimal solutions to the UTAP4. This can be easily proved as follows. Assume that there exist i*, j*, k*, and l* such that and [x.sub.j*[l.sup.+]] > 0, and hence, [x.sub.j*l*] = 1 and [x.sub.j*[l.sup.+]] = 1 by the integrality condition. This implies that
1 = [N.summation over (k=1)][N.summation over (l=1)][r.sub.i*j*kl] [greater than or equal to] [x.sub.j*l*] + [x.sub.j*[l.sup.+]] = 2,
which cannot hold. Therefore, [r.sub.i*j*k*l*] must be either zero or one.
Define a three-index binary variable [z.sub.ijk] such that [z.sub.ijk] = 1 if and only if both tasks i and j are assigned to processor k. Based on [z.sub.ijk], a three-index formulation, the UTAP3 reads
UTAP3
min [M-1.summation over (i=1)][M.summation over (j=i+1)][c.sub.ij](1 - [N.summation over (k=1)][z.sub.ijk]) + [M.summation over (i=1)][N.summation over (k=1)][d.sub.ik][x.sub.ik] (14)
s.t. (2), [z.sub.ijk]...
Read the full article for free courtesy of your local library.
|
Bookmark this article
Print this article
Link to this article
Email this article
Digg It!
Add to del.icio.us
RSS
