International Journal of Industrial

Engineering & Technology (IJIET)

ISSN 2277-4769
Vol. 3, Issue 2, Jun 2013, 1-10
© TJPRC Pvt. Ltd.

FLEXIBILITY IN ASSIGNMENT PROBLEM USING FUZZY NUMBERS WITH

NONLINEAR MEMBERSHIP FUNCTIONS

ATUL KUMAR TIWARI1, ANUNAY TIWARI2, CHERIAN SAMUEL3 & SATISH KUMAR PANDEY4
1,3
Department of Mechanical Engineering, Indian Institute of Technology, Banaras Hindu University, Varanasi, India
2
School of Management Sciences, Indira Gandhi National Open University, New Delhi, India
4
Computational Laboratory, Tapasthali Vidyashram Society, Varanasi, India

ABSTRACT

Assignment Problem (AP), as extensively discussed in operations research, industrial engineering and
computational mathematics has been addressed under different headings and using different approaches. One of the
approaches to solve an AP under uncertainty and in real world scenarios is using fuzzy theory. Fuzzy multi-objective linear
programming usually deals with flexible aspiration levels that are indicative of optimality when considering all objectives
or goals simultaneously with possible deviation in objectives or constraints in vague, imprecise and uncertain environment.
Therefore in this study we propose an algorithm for solving multi-objective assignment problem (MOAP) with linear and
nonlinear membership functions. The proposed model will give a compromised solution for best optimality and higher
satisfaction level for parameters being considered in uncertain environment. The result obtained by using a linear
membership function has been compared with the solution obtained by using some non-linear membership functions. A
Numerical example is taken to illustrate the solution procedure.

KEYWORDS: Multi Objective Assignment Problem (MOAP), Vague Parameters, Fuzzy Multi Objective Linear
Programming, Non Linear Fuzzy Numbers

INTRODUCTION

The Assignment Problem (AP) is among the most-studied, well-known problem in operations research, industrial
engineering and mathematical programming in which objective is to assign a number of jobs (tasks) to an equal number of
machines (workers) so as to minimize the total cost incurred or to minimize the total time consumed for execution of all
the jobs (tasks).It was first introduced by Votaw (1952) in military operation contexts. Assignment Problem can be
categorized into three groups, Assignment Problem model with at most one task per agent, Assignment Problem model
with multiple tasks per agent and Assignment Problem model for multidimensional assignment problem. The general
solution techniques can be found in the literature survey of Pentico (2007) on assignment problems. Gilbert and Hofstra
(1988),Kennington and Wang Z. (1992), Geetha and Nair (1993), Volgenant (1996), Amico and Martello (1997), Aora and
Puri(1998) and Caron et al. (1999) give good of examples of these techniques applied to many situation. Hansen (2000)
proposed some heuristics to solve very large and complex assignment problems. Tiwari et al. (2012) used fuzzy logic with
non- linear membership functions to solve a multi-objective problem with three different ctiteria in a realistic situation.
Tsai et al (1999) provided a solution for balanced multi-objective decision making problem associated with cost,time and
quality by fuzzy concept. Zadeh(1965) first introduced the concept of fuzzy set theory. Then, Zimmermann (1978) first
applied a suitable linear membership functions to solve linear programming problem with several objective functions. He
showed that solutions obtained by fuzzy linear programming are always efficient. Tsai et.al. (1999) used fuzzy multi
objective program for deployment of manpower.
2 Atul Kumar Tiwari, Anunay Tiwari, Cherian Samuel & Satish Kumar Pandey

Leberling (1981) first used a nonlinear membership functions in fuzzy theory, namely a min-operator for the
vector maximum LP problem. He showed that solutions obtained by fuzzy linear programming with this type of non-linear
membership functions are always efficient. Verma et al. (1997) applied the fuzzy programming method with non-linear
namely, hyperbolic and exponential membership functions to investigate a multi-objective transportation problem and
inferred that non linear fuzzy membership function are always efficient. Dhingra et al (1992) defined few other types of the
non-linear membership functions and applied them to an optimal design problem. In this paper we apply fuzzy multi
objective programming approach using linear and two non linear functions. Linear membership function corresponds to a
simple and rational ideal scenario which is very difficult to be seen in the complex situations of today’s business. The two
non linear membership functions are exponential and parabolic type. Exponential membership function corresponds to a
realistic scenario in which conditions are not favourable are more conservative type in nature whereas a parabolic
membership function is designed to catch a scenario which is very favourable to the firms and which can increase firm
expectation of achievement of higher satisfaction levels. However it is advisable that in order to have a better membership
function, one needs to get a real data from the industry, fit the data for some mathematical curve, get the membership curve
and then use this technique.

FUZZY MULTI -OBJECTIVE LINEAR PROGRAMMING

The concept of decision making in Fuzzy environment involving several objectives was proposed by Jadeh(1965).
It was applied to vector maximum problem by transforming Fuzzy Multi-Objective Linear Programming (FMOLP)
Problem to single objective linear program by Zimmerman (1978). For the following Multi-Objective Linear Programming
model being considered,

Max Z= CX

Subject to AX b

The adopted Fuzzy model can be given by,

Max Z0 CX

Subject to AX b

A Linear Fuzzy Membership function is,

The graphical presentation for a linear fuzzy membership function is as shown in figure 1.

Figure 1: Graphical Presentation of a Linear Membership Function

Flexibility in Assignment Problem Using Fuzzy Numbers with Nonlinear Membership Functions 3

A similar set of equations can be written for maximizing objective functions. Some nonlinear membership
functions are as follows

An exponential membership function for a conservative scenario and for the kth objective function can be
formulated as below.

Where, S is a non-zero parameter prescribed by the decision maker. It denotes the risk perceived by the decision
maker in an environment. As this parameter decreases, the overall aspiration or the satisfaction level of the objective
functions increases. tk is the tolerance or the amount of admissible flexibility in the parameters. Graphically it is as shown
in figure 2.

Figure 2: Graphical Representation for Exponential Membership Function

A Parabolic membership function for more favorable conditions and for the kth objective function can be
formulated as below. Corresponding graphical presentation is as in figure 3.

Figure 3: Graphical Representation for Parabolic Membership Function

4 Atul Kumar Tiwari, Anunay Tiwari, Cherian Samuel & Satish Kumar Pandey

FUZZY MULTI-OBJECTIVE LINEAR PROGRAMMING FOR ASSIGNMENT PROBLEM

The most commonly considered objective for Assignment Problem is to minimize the cost of operation and
minimize the time of production. Therefore the individual objective functions for each objective can be formed. Let

denote the binary variable which equals one when job ith is assigned to jth machine and is zero otherwise i.e.

Let Cijdenote the cost incurred when ith job is assigned to jth machine. We have to minimize total expenses in
doing so. The goal is set for total estimated cost for entire flow of jobs to designated machines and it is denoted by .

For situations when estimated cost doesn’t meet, we set tolerancet1 for estimated cost. Therefore the objective
function for minimization of estimated cost is given as follows:

(1)

Let tij denote the time taken for ith job to be processed on jth machine and be its corresponding aspiration level.
Then the objectives function for minimization of the total time with tolerance t2 is written as follows:

(2)

The membership functions for these objectives are set using a nonlinear function to check their level of
acceptance in real world like framework.

The constraints are as follows. Equation (1) and (2) ensures that every job should be assigned to exactly one
machine and vice versa that is,

(3)

(4)

And non-negativity constraints:

(5)

SOLUTION METHOD AND ILLUSTRATED EXAMPLE

Algorithm Steps

• Solve individual objective function under the constraints D; Calculate each objective function (Z1, ,…, Zk); To
determine membership function for each of the objective functions (µ1(Z1), µ2(Z2),…, µk(Zk)).
• Determine the weights [w1,w2,w3,…,wk]of each objective according to priorities assigned using AHP.
• Assign the tolerancest1, t2, t3,…, tk for each objective within the minimum and maximum values of that objective
• Establish an Aggregated objective function: U = w1µ1(Z1)+…+wkµk(Zk)
• Solve a linear programming U under given constraints D, find a best alternative X*.
• If DM is not satisfied alternative X* then return to step (iii).
• If DM is satisfied alternative X* then choose X*.
A Framework in the form of Flowchart for obtaining optimal satisfaction is given in figure 4. Table 1 contains the
data assumed to illustrate an example using this technique.
Flexibility in Assignment Problem Using Fuzzy Numbers with Nonlinear Membership Functions 5

Table 1: The Input Matrix in Time and Cost for Each Pair of Job and Machine (Adapted from Kagade 2009)

Job
Machine
1 2 3
(Cost, Time)
1 (10,13) (8,15) (15,8)
2 (13,10) (12,20) (13,12)
3 (8,15) (10,10) (9,12)

MinZ1=10X11+8X12+15X13+13X21+12X22+13X23+8X31+10X32+9X33
MinZ2=13X11+15X12+8X13+10X21+20X22+12X23+15X31+10X32+12X33

Figure 4: Framework in Form of Flowchart for Obtaining Optimal Satisfaction Considering all the
Criteria of the Assignment Problem

The results are tabulated in table 2. Solution obtained using proposed fuzzy muzzy objective linear programme
gives optimally best compromised solution for this case.

Table 2: Individual Best Solutions and Compromised Optimal FMOLP Solution

Objective Minimum Value Maximum Value Proposed

Function (Individually) (Individually) FMOLP
Z1 Z10= 29 38 30
Z2 Z20= 28 45 37
For Z1
X12 = 1, For Z1
X13 = 1, X12 = 1,
Optimal X23 = 1, X31 =1 X21 = 1, X32 =1 X21 = 1,
Solution For Z2
X13 = 1, For Z2
X11 = 1,
X33 =1
X21 = 1, X32 =1 X22 = 1, X33 =1

Figure 5 shows a diagrammatic representation of compromised optimal solution and individual best solutions for
the two objective functions. This helps us to create the fuzzy linear and nonlinear membership function.
6 Atul Kumar Tiwari, Anunay Tiwari, Cherian Samuel & Satish Kumar Pandey

Figure 5: A Diagrammatic Representation of Compromised Optimal Solution and Individual

Best Solutions for the Two Objective Functions

(6)

(7)

Now we formulate a crisp single objective linear programming with above fuzzy numbers and least satisfaction
level of each of the objectives

Maximize

Subjected to:

and Constraints (3) – (5)

are parameters to assign weights to various objectives. It should be application oriented and can be
different for different set ups. Some multi criteria decision making techniques like Analytic Hierarchical Program (AHP)
by Saaty (1980), can be used to determine these weights. However without loss of generality we assume each objective to
be equally important and assign equal weight i.e. 1/2 to each of these parameters for this model.
Lingo 11.0 computer software is used to run this ordinary LP model on an Intel® 1.60GHz Processor with 1 GB
RAM to obtain results as in table 2. Figure 5 is a diagrammatic representation of the results and it is a comparative study of
the best individual and worst individual solutions against the most compromised optimal solution for two different criteria
for aforementioned assignment problem in table1.
Flexibility in Assignment Problem Using Fuzzy Numbers with Nonlinear Membership Functions 7

Table 3: Solutions Obtained Using Different Linear and Non-Linear Membership Functions
for the Assignment Problem

Scen Tolerance α α (Expo α (Expo α

Route
-ario (t1,t2) (Linear) S=1) S=0.1) (Parabolic)
1 (2,8) - - - - No feasible solution
2 (2,10) 0.300000 0.219374 0.291531 0.470000 X12 = 1, X21 = 1, X33 =1
3 (3,10) 0.383333 0.306383 0.375528 0.539444 X12 = 1, X21 = 1, X33 =1
4 (4,10) 0.425000 0.355638 0.418054 0.563750 X12 = 1, X21 = 1, X33 =1
5 (3,12) 0.458333 0.358428 0.448100 0.663194 X12 = 1, X21 = 1, X33 =1
6 (4,12) 0.500000 0.407682 0.490626 0.687500 X12 = 1, X21 = 1, X33 =1
7 (5,12) 0.525000 0.439266 0.516313 0.698750 X12 = 1, X21 = 1, X33 =1
8 (6,12) 0.541667 0.461217 0.533509 0.704861 X12 = 1, X21 = 1, X33 =1
9 (5,14) 0.578571 0.481522 0.568821 0.773367 X12 = 1, X21 = 1, X33 =1
10 (6,14) 0.595238 0.503473 0.586016 0.779478 X12 = 1, X21 = 1, X33 =1
11 (7,14) 0.607143 0.519606 0.598334 0.783163 X12 = 1, X21 = 1, X33 =1
12 (8,14) 0.616071 0.531960 0.607592 0.785555 X12 = 1, X21 = 1, X33 =1
13 (9,14) 0.623016 0.541723 0.614804 0.787195 X12 = 1, X21 = 1, X33 =1

It is obvious from the results in table 3 that the first job is to be assigned to the second machine, the second job to
the first machine and third job to the third machine. Though the flow of jobs to machines remains same; by varying the
tolerances on the two parameters being considered in this problem, a different degree of expectation or satisfaction levels
are obtained.

Results obtained from linear membership functions are very similar to that obtained by the exponential
membership function when the risk perceived by the decision maker is less.

The satisfaction level obtained by using a parabolic function is better than all other. It is due to the inherent
property of parabola which is visible from the curve in figure 2 i.e. it is concave upward. It means membership is nearer to
one for small tolerances. It is nearer to one even for relatively larger tolerances in the parameters Satisfaction levels against
tolerances in the parameters for different nonlinear functions are shown in figure 6.

Figure 6: Measure of Satisfaction Levels against Tolerances in the Cost and Time Parameters
8 Atul Kumar Tiwari, Anunay Tiwari, Cherian Samuel & Satish Kumar Pandey

CONCLUSIONS

In the present paper, an assignment problem is investigated as Fuzzy multi objective problem with vague and
imprecise decision parameters in cost and time using linear and nonlinear membership function. The tolerances or the
flexibility are introduced on these two parameters by decision maker to accommodate this ambiguity. By adjusting these
tolerances or flexibility, a range of solutions with diverse satisfaction level are attained from which decision maker chooses
one that best meets her requirements within given flexibility in parameters. There is a tremendous potential for further
work on development of methods to solve Assignment Problem with vague description of resources using other techniques
like Rough Sets. For efficient results, some heuristics may further be exploited such as swarm optimization, ant colony
optimization though some researchers have tried larger problems on assignment using these techniques. There are many
other nonlinear membership functions that are capable of representing real life scenario to some extent. An interesting
follow up would be to match real life scenarios with these functions based on real life data and curve fitting or statistical
techniques and then better results can be produced in a real world environment. Further a problem with relative
dependencies among objective functions can be analyzed for further research where one objective may enjoy some priority
over other as decided by management of corporate firms. Multi criteria decision making approaches can be exploited for
such study.

REFERENCES

1. Amico M. D., Martello S,. (1997)The k-cardinality assignment problem. Discrete Applied Mathematics 76 (1–3)
:103–121

2. Angel E, Bampis E, Gourvès L (2004) Approximating the Pareto curve with Local Search for BiCriteria TSP (1,2)
Problem.Theor.Comp. Sci. 310(1-3): 135-146

3. Aora S., Puri M. C. (1998) A variant of time minimizing assignment problem. European Journal of Operational
Research 110 (2): 314–325

4. Bit A. K.,Biswal M. P.,Alam S. S. (1992) Fuzzy programming approach to multi criteria decision making
transportation problem. Fuzzy Sets and Systems North-Holland 50: 135-141

5. Caron G., Hansen P., Jaumard B. (1999)The assignment problem with seniority and job priority constraints.
Operations Research 47 (3): 449–454

6. Chaudhuri A, De K (2011) Fuzzy multi objective linear programming for traveling salesman problem. Afr. J.
Math. Comp. Sci. Res. 4(2): 64-70

7. Dhingra, A.K., Rao, S.S. and Kumar, V.(1992) Nonlinear Membership Function in Multiobjective Fuzzy
Optimization to Mechanical and Structural Systems. AIAA J30: 251-260

8. Ehrgott, M. (2000) Approximation Algorithms for Combinatorial Multi-CriteriaProblems. International

Transactions in OperationsResearch 7: 5-31

9. Fischer R, Richter K (1982) Solving Multi-Objective Traveling Salesman Problem by Dynamic Programming.
Mathematicsche operations forschung und Statistic Series Optimization 13(2): 247-252

10. Geetha S., Nair K.P.K. (1993) A variation of the assignment problem. European Journal of Operations Research
68:422-426.
Flexibility in Assignment Problem Using Fuzzy Numbers with Nonlinear Membership Functions 9

11. Gilbert K. C., Hofstra R. B. (1988) Multidimensional assignment problems. Decision Sciences19 (2): 306–321

12. Hansen, M. P.(2000) Use of Substitute Scalarizing Functions to Guide a Local Search Based Heuristics.The Case
of MOTSP. Journal of Heuristics 6: 419-431

13. Kagade K.L, Bajaj B.H (2009) Fuzzy approach with linear and some non-linear membership functionsfor solving
multi-objective assignment problems. Advances in Computational Research 1(2): 14-17

14. Kennington J., Wang Z. (1992) A shortest augmenting path algorithm for the semi-assignment problem.
Operations Research 40 (1):178–187

15. Leberling H. (1981)On finding compromise solutions in multi-criteria problems using the fuzzy min-
operator.Fuzzy sets and Systems 6:105-118

16. Melamed, I. I., Sigal, I. K.(1997) The Linear Convolution of Criteria in the Bi-Criteria Traveling Salesman
Problem. Computational Mathematics and Mathematical Physics 37: (8): 902-905

17. Paquete L, Chiarandini M, Stützle T (2004) Pareto Local Optimum Sets in Bi-Objective Traveling Salesman
Problem: An Experimental Study,Metaheuristics for Multi-objective Optimization.Lect. Notes.Econ.Math.Syst
Springer Verlag, Berlin 535: 177-199

18. Pentico D. W. (2007)Assignment problems: A golden anniversary Survey. European Journal of Operational
Research 176: 774–793

19. RehmatA, Saeed H, Cheema MS (2007) Fuzzy Multi-objective Linear Programming Approach for Traveling
Salesman Problem. Pak. J. Stat. Oper. Res. 3(2): 87-98

20. Saaty T, (1980)The analytical hierarchy process. Ed. USA McGraw Hill

21. Schrage L.(1984) Linear, integer and quadratic programming with LINDO The Scientific Press. Palo Alto, CA

22. Sigal, I. K.(1994) Algorithm for Solving the Two-Criterion Large-scale Traveling Salesman Problem.
Computational Mathematics and Mathematical Physics 34(1) : 33-43

23. Taha H.A.( 1992) Operations Research, An Introduction ,5th ed. Macmillan, NewYork

24. Tiwari A. K., Cherian S., Singh V., Saraswati V.(2012) Fuzzy number with nonlinear membership functions to
provide flexibility in a multi objective Travelling Salesman Problem. Proceedings of ICAdC, AISC springerlink
174:1011-1019

25. Tsai C.H., Wei C.C. and Cheng C.L. (1999) Multi objective fuzzy deployment of manpower. International Journal
of the Computer, the Internet and Management 7(2)

26. Tung, C. T.(1994) A Multi criteria Pareto-optimal Algorithm for the Traveling Salesman Problem. Asia-Pacific
Journal of Operational Research 11: 103-115

27. Verma R., Biswal M. P,,Biswas A. (1997) Fuzzy programming technique to solve multiobjective transportation
problem with some non-linear membership functions. Fuzzy Sets and Systems 91:37-43

28. Volgenant A. (1996) Linear and semi-assignment problems: A core oriented approach. Computers & Operations
Research 23 (10) :917–932
10 Atul Kumar Tiwari, Anunay Tiwari, Cherian Samuel & Satish Kumar Pandey

29. Votaw D. F., Orden A., (1952)The personnel assignment problem, Symposium on Linear Inequalities and
Programming. SCOOP 10 US Air Force: 155–163.

30. Yan Z, Zhang L, Kang L, Lin G (2003) A new MOEA for multi-objective TSP and its convergence property
analysis.Proceedings of Second International Conference, Springer Verlag Berlin 342-354.

31. Zadeh, L., (1965) Fuzzy Logic and its Applications. Academic Press, New York

32. Zimmerman, H.J. (1978) Fuzzy programming and linear programming with several objective functions. Fuzzy
sets and systems 1: 45-55.