Journal of Applied Sciences and Environmental Management World Bank assisted National Agricultural Research Project (NARP) - University of Port Harcourt ISSN: 1119-8362 Vol. 14, Num. 1, 2010, pp. 35-38

Journal of Applied Sciences and Environmental Management, Vol. 14, No. 1, March, 2010, pp. 35-38

Determining Feasible Solutions of a Multicriteria Assignment Problem

¹ Odior, A.O., ² Charles-Owaba, O.E. ² Oyawale, F. A.

¹ Department of Production Engineering, University of Benin, NIGERIA. Email: waddnis@yahoo.com.
² Department of Industrial and Production Engineering, University of Ibadan, Nigeria.

ABSTRACT

This paper presents an important research tool in operations research as it applies to a particular structure of the multicriteria assignment problem. The paper addresses the problem of effectiveness of feasible solutions of a multicriteria assignment problem and this was done in two steps. In the first step, we determine whether or not a given feasible solution of a multicriteria assignment problem is a real efficient one. In the second step, if the feasible solution is not real efficient, we provide a real efficient solution that dominates that not real efficient solution, using our proposed method which consists of transforming the original problem into an assignment problem. @ JASEM

The basic problem in operations research is to assign tasks to facilities on a one-to-one basis in an optimal way. The problem may be to find the best assignment of workers to jobs, football players to field positions, equipment to construction site and so forth. The main objective of assignment problem is to minimize the total time to complete a set of tasks, or to maximize skill ratings, or to minimize the cost of the assignments. The assignment problem requires that there be as many facilities as tasks, say n of each. In this case, there are exactly n! different ways to assign the tasks to the facilities on a one-to-one basis. This follows because there are n ways to assign the first task, n-1 ways to assign the second, n - 2 ways to assign the third, and so on, with a total of n · (n - 1) · (n -2) ···· 3 · 2 · 1 = n! possible assignments. Among these n! possible assignments, we are to find the optimal assignment.

Let c_ij be the cost of assigning the i-th facility to the jth task for i, j = 1, 2, &, n. The units of cij may be naira, miles, hours or what ever is appropriate to the problem. We define the cost matrix to be the n x n matrix as presented below, (Taha, 2002).

Matrix

The standard assignment problem consists of assigning a number of tasks to an equal number of agents. Each agent is assigned to exactly one task and each task has exactly one agent assigned to perform it in such a way to minimize the overall cost of assigning agents to tasks. The mathematical formulation of the standard assignment problem (SAP) is as follows, (Taha, 2002; Bufardi, 2008; Lee, et al., 1995).

where for all i, j = 1, &, n, c_ij is the cost of assigning agent i to task j, x_ij = 1 means that agent i is assigned to task j and x_ij = 0 means that agent i is not assigned to task j.

The first set of constraints implies that each agent is assigned to one and only one task and the second set of constraints implies that to each task is assigned one and only one agent. It should be noted that in addition to the minimization of assignment cost, an assignment problem may also consider other objective functions such as the minimization of completion time. When the assignment problem is considered with the minimization of assignment cost as the objective function, it is called the cost minimizing assignment problem.

Assignment problem has been used in a variety of application contexts such as personnel scheduling, manpower planning and resource allocation.

Sonia, (2008) reported that various methodologies including primal-dual algorithms, simplex-like methods, cost operation algorithms, forest algorithms and relaxation techniques have been proposed to solve the cost minimizing assignment problem. According to Pentico, (2007) and Kuhn, (2005), Hungarian method developed by Kuhn is recognized to be the first practical method for solving the SAP. The standard assignment problem can be seen as a relaxation of more complex combinatorial optimization problems such as travelling salesman problem, quadratic assignment problem, etc. It can also be considered as a particular transportation problem with all supplies and demands equal to 1, (Malhotra, et. al., 1982). Many optimization problems in real- life applications are multi objective in nature; indeed a single objective is rarely sufficient to embrace all facets of the problem which should be considered for the evaluation and comparison of the alternatives. In that, the assignment problems are not an exception; they can also involve multiple objectives. Indeed, in the problem of assigning jobs to machines, the minimization of completion time can also be an important objective in addition to the conventional objective which is the inimization of assignment cost, (Bufardi, 2008; Mazzola, et al., 1986). Numerous solution techniques have been proposed for solving multicriteria (multiple objective) mathematical programming decision problems with preemptive priorities. In such problems, lower priority objectives are used only to break ties among alternate optima for higher level. It is important to note that in multiobjective optimization problems, there often exist conflicts or contradictions between the different objectives to be optimized simultaneously. Two objective functions are said to be in conflict if the full satisfaction of one, results in only partial satisfaction of the other. In other words, the optimal solutions for the two objective functions are not the same, (Charnes, et al., 1969). The objective of the study is to determine whether or not a multiobjective optimization problem has a real efficient feasible solution by transforming the original problem into an assignment problem with side constraints for which solution techniques already exist.    THEORY. We consider a multiobjective assignment problem with t objective functions denoted as R (t) and formulated as follows:

Let x° be a feasible solution of  (t) i.e., x° satisfies constraints (2), (3) and (4). In the first step, we want to determining whether or not x° is a real effective solution of R (t) and in the case where x° is not a real solution, we determine in the second step a solution x* that is a real effective solution of R (t) and which dominates x°. The idea is that the efficiency of x° is investigated because it is assumed to be an interesting solution for the decision maker and its efficiency is checked before its selection as a final solution. In the case where it is not real efficient, x* is not only real efficient but it also dominates x° which makes it even a better candidate for selection.

Now, recall that x° is a real solution of R(t) if and only if there does not exist any solution x satisfying constraints (2), (3) and (4) such that:

(i ) z^k(x)≤ z^k(x°), for all k = 1, ..., t, and (ii) there is at least one index m, such that 1 d m d t, for which z^m(x) < z^m(x°). It is worth to note that z^k(x)≤ z^k(x°), for all k = 1, ..., t, with at least one strict inequality is equivalent to z^k(x)≤ z^k(x°), for all k = 1, ..., t and

The feasible solution x° is real efficient if the system (t) defined as follows is not feasible.

We now define C_ij,A_ijk and B_k,fori,j=1,...,nandk = 1, ..., t as follows:

Let us define as follows:

With these transformations, we obtain an assignment problem with t side constraints which is denoted as È (x°). Its formulation is as follows

:

It should be noted that the number of side constraints in ψ(x°) is equal to the number of objective functions in R(t). For the kth side constraint, k = 1... t, the left member is simply the kth objective function in R(t) and the right member is the value of kth objective function for the feasible solution x°. The objective function of R (x°) is the sum of the t objective functions z^k(x), k = 1... t of the problem R(t).

Given that x° is a feasible solution of R(t), it means that x°satisfies constraints (2), (3) and (4). It should however be noted that the set of feasible solutions of (t) and the set of feasible solutions of standard assignment problem (SAP) are the same. Therefore, the set of feasible solutions of R(t) can be obtained through the use of any solution technique of standard assignment problem. In this case we wish to address two problems: (i) to investigate whether or not x° is a real effective solution of (t) and (ii) in case x°is found not to be a real solution, we will determine a real effective solution that dominates x^O .

Let x* be an optimal solution of R (x°) obtained. Depending on the value of the objective function of R (x°) for the optimal solution x*, two cases can be
distinguished:

In the first case (14), the feasible solution x° is real because any feasible solution of R(t) which is at least as good as x° with respect to all criteria, fulfils
the constraints of R (x°) and cannot be strictly better than x°on one of the t criteria. Indeed, if there exist a solution x that is feasible for R (x°) and an index m, 1≤ m≤ t, such that

and this contradicts the fact that x* is an optimal 0 i=1 nn solution to R (x ).

In the second case (15), the feasible solution x° is not real efficient and x* is a real efficient solution that dominates x°. Indeed, since z^k(x*) d z^k(x°) for all k = 1, ..., t because x* satisfies constraints (13) and (15), then there necessarily exists  m, 1d m d t,such that z^m(x*)k(x⁰). Consequently, x* dominates x°, it implies that x* is a real efficient solution for  (t). Indeed, if x* is real efficient, then there will exist x which satisfies (2), (3), and (4) such that z^k(x) d z^k(x*), for all k = 1, ..., t and

since for all k = 1, ..., t, z^k(x) d z^k(x*), and z^k(x*) d z^k(x°), then z^k(x) d z^k(x°), for all k = 1, ..., t. Hence, x satisfies (13). Since x satisfies also (2), (3), and (4), then x is a feasible solution of R (x°). The fact that x* is an optimal solution of R (x°) implies that

which contradicts condition (17).

We have therefore shown that solving R (x°) to optimality is sufficient to answer the question which is" is x° a real efficient solution?", and to determine a real efficient solution that dominates x°    in the case where x° is not efficient.

CONCLUSION

Assignment problem is a special case of transportation problem which occurs when each supply is 1 and each demand is 1 and is a real life linear programming problem. A real-life assignment problems may involve more than one objective function to optimize and this is why multiobjective assignment models suit better to real-life assignment applications than single objective assignment models. An important concept in multiobjective optimization is that related to efficient solutions. We investigated the problem of knowing whether or not a given feasible solution of a multiobjective assignment problem is a real efficient one and in the case where it is not efficient we provided a technique to determine an efficient solution that dominates the earlier one. We have been able to provide a technique that can determine all real efficient solutions of a general multiobjective assignment problem. We also provided answers to two basic questions raised in this paper through the transformation of the original problem into an assignment problem with side constraints. The main application of the work developed in this paper is mainly the case where an interesting feasible solution of a multiobjective assignment problem is given and where its selection as a final solution is conditioned by the fact whether or not it is a real efficient solution. The work also provides an additional potential application of the solution techniques of the assignment problem with side constraints leading to optimality.

REFERENCES

• Bufardi, A (2008). On the efficiency of feasible solutions of a multicriteria assignment problem. J. Operational Research. 2 (27): 25- 28.
• Charnes, A; Cooper, W W; Neihaus, R J; Stedry, A (1969). Static and dynamic assignment models with multiples objectives and some remarks on organization design. J. Management Science. 15 (8): 365- 375.
• Kuhn, H W (2005). The Hungarian method for the assignment problem. Naval Research Logistic Quarterly. 52 (1): 7-21.
• Lee, S M; Schniederjans, M J (1995). A multicriteria assignment problem: a goal programming approach. J. Socio-Economic Planning Sciences. 29 (3): 245-256.
• Malhotra, R; Bhatia, M L; Puri, M C (1982). Bi- criteria assignment problem. J. Opsearch. 19 (2): 84-96.
• Mazzola, J B; Neebe, A W (1986). Resource- constrained    assignment    scheduling.    J. Operations Research. 34 (4): 560-572.
• Pentico, D W (2007). Assignment problems: A golden anniversary survey. European J. Operations Research. 176 (2): 774-793.
• Sonia, P M C (2008). Two-Stage Time Minimizing Assignment Problem. Omega articles on Manufacturing magazines. 36 (5): 730-740.
• Taha, H A (2002). Operations Research: An Introduction, Seventh Edition, Thomson Press (1) Ltd, India. pp: 196 -203.

Copyright 2010- Journal of Applied Sciences and Environmental Management

The following images related to this document are available:

Photo images