A Fuzzy Approach to solve a Team Allocation Problem using FDP technique
T. Nagalakshmi*
*Veltech Rangarajan Dr. Sagunthala R&D Institute of Science and Technology, Avadi, Chennai, Tamil Nadu, India.
*[email protected] , [email protected]
ABSTRACT
The purpose of this paper is to solve a team allocation problem by using FDP technique. Dynamic Programming is a mathematical process that is concerned with the optimization of multistage decision-making process. Real world data is available as indeterministic data where fuzzy concepts come to existence. FDP techniques play a vital role in solving many complicating problems by breaking them into simple sub-problems.
The significant method applied here is fuzzy recursive optimization. In this paper, a team allocation problem is considered with fuzzy constraints. It is solved by applying fuzzy recursive optimization technique. A numerical example is solved with the above approach and optimized results are obtained. The essence of this method will create interest in the researchers for their further studies in other DPpatterns with fuzziness.
Keywords
Fuzzy Dynamic Programming(FDP), Team Allocation Problem, Fuzzy Recursive Optimization
1. Introduction
Dynamic Programming is a mathematical processthat is concerned with the optimization of multistage decision-making process. The word ‘programming’ has been used in the mathematical sense of selecting an optimum allocation of resources, and it is ‘dynamic’ as it is particularly useful for problems where decisions are taken at several distinct stages, such as everyday or every week. Richard Bellman[1][2] developed this technique in early 1950. Dynamic programming can be given a more significant name as recursive optimization. In DP, a large complicated problem is split into small sub-problems each of them involving only a few variables. This technique converts every n-variable problem to n-sub-problems considered as stages comprising of a single variable. The optimum solution is obtained in an orderly manner.
That is, it is proceeded from one stage to the next, and is winded upif the extreme stage is attained. The concept of fuzziness is introduced to the dynamic programming which resulted in Fuzzy Dynamic Programming.
To convert a fuzzy verbal problem into a multistage structure is not always simple, and sometimes it become very difficult and even looks easy to apply. Fuzzy Recursive equations are of standard nature and its computer program runs in a standard routine. This uses a principle of
‘Bellman’s Principle of Optimality’. Thus, FDP method is very useful for solving various problems, such as inventory, replacement, allocation, linear programming etc with a fuzzy approach. While solving the problem, we use the concepts of stage and state. Moreover, the problem is solved stage by stage and to ensure that suboptimal solution does not result, we cumulated the objective function value in a particular way. Working backwards, for every stage, we found the decisions in that stage that will allow us to reach the final destination optimally, starting from each of the states of the stage. These decisions could be taken optimally, without the knowledge of how we actually reach the different states. State variable is the variable that links up two stages. At any stage, the status of the problem can be described by the values the state variable can take. These variables are referred to as states. The points at which decisions
called for are referred to as stages. Each stage can be thought of having a beginning and an end.
Different stages come in a sequence, with the ending of a stage marking the beginning of the immediately succeeding stage.
In this proposed approach, a team allocation problem is considered with fuzzy parameters. It is solved by fuzzy recursive optimization method in both forward and backward manner. This proposed approach is justified with the help of an example. This approach is proposed in order to give an idea for the researchers for their further studies in other DP models in a fuzzy environment. This paper is planned as follows: In section-2, Literature review is discussed briefly. In section-3,basic definitions and arithmetic operations are discussed. In section-4, a team allocation problem with fuzzy parameters is considered and forward and backward recursive equations are formulated in fuzzy manner. A demonstrative example is solved and its solution is obtained with the proposed approach.
2. Literature Review
Dynamic Programming Method is first introduced by Richard Bellman[1][2] in the year 1950. In the existing world multi stage decision making problems arises in all our day-to-day activities.
Now-a-days fuzziness exists in the observation of such problems. After Zadeh[3] introduced the concept of fuzzy theory, many researchers applied the concept of fuzzy theory in many fields.
Bellman and Zadeh[4] combined the fields of decision making and fuzzy theory and introduced many new concepts of fuzzy decision making. Gluss[5] proceeded their research work on fuzzy sets. Fuzzy was introduced in the field of Dynamic programming. Kacprzyk and Esogbue [6][7]
discussed about the basic problem classes and further developments of FDP in their work.
Terano et. al.[8] reviewed the concepts of planning in management by FDP. Hussein et. al. [9]
developed a method for decomposition of MOP(Multi Objective Programming) problems by hybrid FDP. Uthra and Nagalakshmi [10] solved a capital budgeting problem optimally with fuzzy constraints. They also developed a model to solve a fuzzy LPP [11]by theFDPtechique.
Kaliyaperumal et. al. [12] solved FDPP for single additive constraint with additively separable return with Trapezoidal membership functions. Rajkumar et. al.[13] obtained a shortest path using DP through fuzzy numbers. It is observed many researches are done in this FDP field. It is shown that FDP was anprominent technique for handling MSDM problems under fuzzy constraints.
3. Definition and preliminaries 3.1 Fuzzy set
A fuzzy set of a base set V is specified by its membership function 𝜌 : V → [0,1] assigning to each v in V, the degree or grade to which v belongs to 𝜌.
3.2 Trapezoidal-Fuzzy-Number
Let𝑃 = (𝑝1, 𝑝2, 𝑝3, 𝑝4) be a trapezoidal-fuzzy-number having a membership function which
satisfies
𝜌𝑃 𝑥 =
0 , 𝑥 ≤ 𝑝1 𝑥 − 𝑝1
𝑝2− 𝑝1 . 𝑝1 ≤ 𝑥 ≤ 𝑝2 1 . 𝑝2 ≤ 𝑥 ≤ 𝑝3 𝑝4− 𝑥
𝑝4− 𝑝3 , 𝑝3 ≤ 𝑥 ≤ 𝑝4 0 , 𝑥 ≥ 𝑝4 3.3 Generalized-Trapezoidal-Fuzzy-Number
Let 𝑃 = (𝑝1, 𝑝2, 𝑝3, 𝑝4: 𝑣) be a generalized-trapezoidal-fuzzy-number having a membership function which satisfies
𝜌𝑃 𝑥 =
0 , 𝑥 ≤ 𝑝1 𝑣 𝑥 − 𝑝1
𝑝2− 𝑝1 . 𝑝1 ≤ 𝑥 ≤ 𝑝2 1 . 𝑝2 ≤ 𝑥 ≤ 𝑝3 𝑣 𝑝4− 𝑥
𝑝4− 𝑝3 , 𝑝3 ≤ 𝑥 ≤ 𝑝4 0 , 𝑥 ≥ 𝑝4 3.4 Properties of GTrFNs:
Let 𝑃 = (𝑝1, 𝑝2, 𝑝3, 𝑝4: 𝑣1) and 𝑄 = (𝑞1, 𝑞2, 𝑞3, 𝑞4: 𝑣2) be two generalized trapezoidal fuzzy numbers. Its basic properties on arithmetic operations are given below:
1. 𝑃 + 𝑄 = (𝑝1+ 𝑞1, 𝑝2+ 𝑏𝑞2, 𝑝3+ 𝑞3, 𝑝4+ 𝑞4 ; 𝑣) , 𝑣 = min(𝑣1, 𝑣2) 2. 𝑃 − 𝑄 = (𝑝1− 𝑞4, 𝑝2 − 𝑞3, 𝑝3− 𝑞2, 𝑝4− 𝑞1 ; 𝑣) , 𝑣 = min(𝑣1, 𝑣2) 3. 𝑃 ∗ 𝑄 = (𝑝1𝑞1, 𝑝2𝑞2, 𝑝3𝑞3, 𝑝4𝑞4 ; 𝑣) , 𝑣 = min(𝑣1, 𝑣2)
4. 𝑃 ÷ 𝑄 = 𝑝1
𝑞4,𝑝2
𝑞3,𝑝3
𝑞2,𝑝4
𝑞1; 𝑣 , 𝑣 = mi n 𝑣1, 𝑣2 5. 𝑐𝑃 = 𝑐𝑝1, 𝑐𝑝2, 𝑐𝑝3, 𝑐𝑝4; 𝑣1 if 𝑐 ≥ 0
𝑐𝑃 = (𝑐𝑝4, 𝑐𝑝3, 𝑐𝑝2, 𝑐𝑝1 ; 𝑣1) if 𝑐 < 0 3.5 Method of Ranking GTrFN:
The ranking method proposed byKumar et. al.[14] is applied to defuzzify GTrFNs to obtain its crisp value for calculation and for making decisions. The
crisp value of the GTrFN𝑃 = (𝑝1, 𝑝2, 𝑝3, 𝑝4: 𝑣1) is given by 𝑅(𝑃 ) = 𝑣1(𝑝1+ 𝑝2+ 𝑝3 + 𝑝4)/4.
4. Fuzzy Team Allocation Problem
After Covid-19 pandemic people of the world has faced many problems such as isolation, fear, loss of income, bereavement which triggered their mental health conditions. It led to neurological and mental complications such as agitation, delirium, stroke etc., Hence, the World Health Council devoted to improve health-care in the under-developed countries of the world. It now has five medical teams available to allocate among three such countries to improve their medical care health education and training programmes. Therefore, the council need to determine how many teams to allocate to each of these countries to maximize the total effectiveness of the five(s=5)teams. The measure of effectiveness being used is additional man-years of life. For a particular country, this measure equals the country’s increased life expectancy in years times its population. The following table gives the estimated additional man-years of life (in multiples of thousands) which is expressed in generalized trapezoidal fuzzy numbers for each country for each possible allocation of medical items. The proposed approach determines the number of teams to be allocated to each country for maximum effectiveness. The following numerical example is considered and solved using fuzzy recursive optimization.
No. of Medical Teams
Thousands of Additional Man-years of life
Country - 1 Country - 2 Country - 3
0 (0,0,0,0:0.1) (0,0,0,0:0.1) (0,0,0,0:0.1)
1 (30,40,50,60:0.1) (5,15,25,35:0.1) (35,45,55,65:0.1) 2 (55,65,75,85:0.1) (30,40,50,60:0.1) (55,65,75,85:0.1) 3 (75,85,95,105:0.1) (60,70,80,90:0.1) (65,75,85,95:0.1) 4 (90,100,110,120:0.1) (95,105,115,125:0.1) (85,95,105,115:0.1) 5 (105,115,125,135:0.1) (135,145,155,165:0.1) (115,125,135,145:0.1) The above fuzzy team allocation problem is mathematically formulated as a fuzzy dynamic programming problem as follows:
Maximize 𝑍 = 𝑉 1(𝑢1) + 𝑉 2(𝑢2) + 𝑉 3(𝑢3)+. . . +𝑉 𝑛(𝑢𝑛) subject to
𝑢1+ 𝑢2+ 𝑢3+. . . +𝑢𝑛 ≤ 𝑠 Fuzzy Recursive Relationships:
Since there are three countries, the problem is considered to be three stage problem.
Let 𝑢𝑖 defines the number of medical teams allocated to the stages 1,2,3, . . . 𝑖.
Let 𝑑𝑖 be the number of teams still available for allocation.
Let 𝑉 𝑖(𝑢𝑖) be the thousands of additional man-years of life when 𝑥𝑖 teams are assigned.
Let the state variables be obtained from 𝑑𝑖−1 = 𝑑𝑖 − 𝑢𝑖
Let 𝑓 𝑖(𝑑𝑖, 𝑢𝑖) be the fuzzy optimal return function.
Fuzzy-Forward Recursive Method:
Fuzzy forward recursion is formulated as:
𝑓 1(𝑑1, 𝑢1) = max
𝑢1≤𝑑1
𝑉 1(𝑢1)
𝑓 𝑖(𝑑𝑖, 𝑢𝑖) = max𝑢𝑖≤𝑑𝑖{𝑉 𝑖(𝑢𝑖) + 𝑓 𝑖−1(𝑑𝑖 − 𝑢𝑖)} where 𝑖 = 2,3, . . . , 𝑛.
The above illustrative example is solved by fuzzy forward recursive method starting from first stage to third stage.
First Stage:𝑓 1(𝑑1, 𝑢1) = max𝑢1≤𝑑1𝑉 1(𝑢1)
𝑑1 𝑓 1(𝑢1) 𝑢1∗
0 (0,0,0,0:0.1) 0
1 (30,40,50,60:0.1) 1
2 (55,65,75,85:0.1) 2
3 (75,85,95,105:0.1) 3
4 (90,100,110,120:0.1) 4
5 (105,115,125,135:0.1) 5
Second Stage:𝑓 2(𝑑2, 𝑢2) = max𝑢2≤𝑑2{𝑉 2(𝑢2) + 𝑓 1(𝑑2 − 𝑢2)}
𝑑2 𝑢2 = 0 𝑢2 = 1 𝑢2 = 2 𝑢2 = 3 𝑢2 = 4 𝑢2 = 5 𝑓 2(𝑢2) 𝑢2∗ 0 (0,0,0,
0:0.1)
- - - (0,0,0,
0:0.1) 0 1 (30,40,
50, 60:0.1)
(5,15, 25, 35:0.1)
- - - - (30,40,
50, 60:0.1)
0
2 (55.65.
75, 85:0.1)
(35,55, 75, 95:0.1)
(30,40, 50, 60:0.1)
- - - (55.65.
75.
85:0.1) 0
3 (75.85.
95, 105:0.1)
(60,80, 100,
120 :0.1)
(60,80, 100, 120:0.1)
(60,70, 80, 90:0.1)
- - (60,80,
100, 120:0.1)
0, 1, 2 4 (90.100.
110, 120:0.1)
(80,100, 120, 140:0.1)
(85,105, 125, 145:0.1)
(90,110, 130, 150:0.1)
(95,105, 115, 125:0.1)
- (90,110, 130, 150:0.1)
3
5 (105,115 ,125, 135:0.1)
(95,115, 135, 155:0.1)
(105,125, 145, 165:0.1)
(115,135 ,155, 175:0.1)
(125,145, 165, 185:0.1)
(135,145, 155, 165:0.1)
(125,145, 165, 185:0.1)
4
Third Stage:𝑓 3(𝑑3, 𝑢3) = max𝑢3≤𝑑3{𝑉 3(𝑢3) + 𝑓 2(𝑑3 − 𝑢3)}
𝑑3 𝑢3 = 0 𝑢3 = 1 𝑢3 = 2 𝑢3 = 3 𝑢3 = 4 𝑢3 = 5 𝑓 3(𝑢3) 𝑢3∗ 5 (125,145
,165, 185:0.1)
(125,155 ,185, 215:0.1)
(115,145, 175, 205:0.1)
(120,140, 160, 180:0.1)
(115,135 ,155, 175:0.1)
(115,125, 135, 145:0.1)
(125,155, 185, 215:0.1)
1
Fuzzy-forward optimal Solution:
The fuzzy optimal total return value is (125,155,185,215:0.1) in terms of thousands of additional man-years of life. The following table gives its optimal solution.
𝑢3∗ 𝑑3 d2 = 𝑑3 – 𝑢3∗ 𝑢2∗ d1 = 𝑑2 – 𝑢2∗ 𝑢1∗
1 5 5 – 1 = 4 3 4 – 3 = 1 1
The optimal solution is (1,3,1) which implies that one team is allocated to country-1, three teams are allocated to country-2 and one team is allocated to country-3. The same solution is verified through fuzzy backward recursive method also.
Fuzzy-Backward Recursive Method:
Fuzzy backward recursion is formulated as:
𝑓 𝑛(𝑑𝑛, 𝑢𝑛) = max
𝑢𝑛≤𝑑𝑛
𝑉 𝑛(𝑢𝑛)
𝑓 𝑖(𝑑𝑖, 𝑢𝑖) = max𝑢𝑖≤𝑑𝑖{𝑉 𝑖(𝑢𝑖) + 𝑓 𝑖+1(𝑑𝑖 − 𝑢𝑖)} where 𝑖 = 1,2,3, . . . , 𝑛 − 1.
The above illustrative example is solved by fuzzy forward recursive method starting from first stage to third stage.
Third Stage:𝑓 3(𝑑3, 𝑢3) = max𝑢3≤𝑑3𝑉 3(𝑢3)
𝑑3 𝑓 3(𝑢3) 𝑢3∗
0 (0,0,0,0:0.1) 0
1 (35,45,55,65:0.1) 1
2 (55,65,75,85:0.1) 2
3 (65,75,85,95:0.1) 3
4 (85,95,105,115:0.1) 4
5 (115,125,135,145:0.1) 5
Second Stage:𝑓 2(𝑑2, 𝑢2) = max𝑢2≤𝑑2{𝑉 2(𝑢2) + 𝑓 3(𝑑2 − 𝑢2)}
𝑑2 𝑢2 = 0 𝑢2 = 1 𝑢2 = 2 𝑢2 = 3 𝑢2 = 4 𝑢2 = 5 𝑓 2(𝑢2) 𝑢2∗
0 (0,0,0, 0:0.1)
- - - (0,0,0,
0:0.1) 0 1 (35,45,
55, 65:0.1)
(5,15, 25, 35:0.1)
- - - - (35,45,
55, 65:0.1)
0
2 (55,65, 75, 85:0.1)
(40,60, 80, 100:0.1)
(30,40, 50, 60:0.1)
- - - (55,65,
75, 85:0.1)
0
3 (65,75, 85, 95:0.1)
(60,80, 100, 120:0.1)
(65,85, 105, 125:0.1)
(60,70, 80, 90:0.1)
- - (65,85,
105, 125:0.1)
2
4 (85,95, 105, 115:0.1)
(70,90, 110, 130:0.1)
(85,105, 125, 145:0.1)
(95,115, 135, 155:0.1)
(95,105, 115, 125:0.1)
- (95,115, 135, 155:0.1)
3
5 (115,125 ,135, 145:0.1)
(90,110, 130, 150:0.1)
(95,115, 135, 155:0.1)
(115,135 ,155, 175:0.1)
(130,150, 170, 190:0.1)
(135,145, 155, 165:0.1)
(130,150, 170, 190:0.1)
4
First Stage:𝑓 1(𝑑1, 𝑢1) = max𝑢1≤𝑑1{𝑉 1(𝑢1) + 𝑓 2(𝑑1 − 𝑢1)}
𝑑1 𝑢1 = 0 𝑢1 = 1 𝑢1 = 2 𝑢1 = 3 𝑢1 = 4 𝑢1 = 5 𝑓 1(𝑢1) 𝑢1∗ 5 (130,150
,170, 190:0.1)
(125,155 ,185, 215:0.1)
(120,150, 180, 210:0.1)
(130,150, 170, 190:0.1)
(125,145 ,165, 185:0.1)
(105,115, 125, 135:0.1)
(125,155,1 85, 215:0.1)
1
Fuzzy-backward optimal Solution:
The fuzzy optimal total return value is (125,155,185,215:0.1) in terms of thousands of additional man-years of life. The following table gives its optimal solution.
𝑢1∗ 𝑑1 d2 = 𝑑1 – 𝑢1∗ 𝑢2∗ d3 = 𝑑2 – 𝑢2∗ 𝑢3∗
1 5 5 – 1 = 4 3 4 – 3 = 1 1
The optimal solution is (1,3,1) which implies that one team is allocated to country-1, three teams are allocated to country-2 and one team is allocated to country-3. It is observed that the solution obtained by both fuzzy forward and backward recursive method are one and the same.
Conclusion
The new proposed approach is applied to solve a fuzzy team allocation problem whose
parameters are generalized trapezoidal fuzzy numbers. In this proposed approach, fuzzy-forward and fuzzy-backward recursive optimization techniques are framed by fuzzy dynamic programming method. Many times, real-world situations are indeterministic and imprecise parameters. So, fuzziness may prevail in every field. In this approach, FDP technique gives an optimal solution to the team allocation problem with fuzzy constraints. That is out of five teams, one team is allocated to country-1, three teams are allocated to country-2 and one team is allocated to country-3 for maximizing the additional man-years of life of all the three countries.
Limitations and Future Studies
In the real world, multi stage decision making problems arise in all the fields. A problem is considered as a dynamic one, if some of its characteristics are illustrated by its output which is produced with respect to time as a result of their present values and decisions made. The decisions taken at a certain stage and state will bring about aextremevariation in the output of the process considered. This will surely have an impact on the happenings in the future. Dynamic Programming is a powerful apparatus to solve those problems. If the parameters are unknown due to some uncontrollable factors, fuzziness prevails there. Hence, Fuzzy Dynamic Programming provides a systematic procedure to handle those situations. This study eliminates the vagueness and ambiguity in the Dynamic Programming models. It paves way for the researchers to apply these concepts to solve other DP models that prevails in the field of optimization.
References
[1] Bellman, R., ‘Dynamic Programming’, Dover Publications Inc., New York, 2003.
[2] Bellman, R. E., ‘Dynamic Programming’, Princeton University Press, New Jersey, 1957.
[3] Zadeh, L. A, ‘Fuzzy Sets’, Information and Control, 8, (1965), pp.338-353.
[4] Bellman, R. E. and Zadeh, L. A., Decision-making in a fuzzy environment, Management Science, 17(4) (1970), B141–B164.
[5] Gluss, B., Fuzzy multi-stage decision-making, fuzzy state and terminal regulators and their relationship to non-fuzzy quadratic state and terminal regulators, International Journal of Control, 17(1) (1973), 177–192.
[6] Kacprzyk, J. and Esogbue, A. O., Fuzzy dynamic programming: Main developments and applications, Fuzzy Sets and Systems, 81(1) (1996), 31–45.
[7] Kacprzyk, J. and Esogbue, A. O., Fuzzy dynamic programming: Basic issues and problem classes, Dynamical Aspects in Fuzzy Decision Making, 73 (2001), 1–25.
[8] Terano, T., Sugeno, M., and Tsukamoto, Y., Planning in management by fuzzy dynamic programming, IFAC Fuzzy Information, Marseille, France, 1983.
[9] M.L. Hussein, M.A. Abo-Sinna, Decomposition of multi objective programming problems by hybrid fuzzy dynamic programming, Fuzzy Sets and Systems 60 25–32, (1993).
https://doi.org/10.1016/0165-0114(93)90286-Q
[10] Uthra, G. and Nagalakshmi, T., An application of Generalized Trapezoidal fuzzy numbers in the optimal solution of a fuzzy capital budgeting problem, International Journal of Pure and Applied Mathematics, 109(9) (2016), 63-71.
[11] Nagalakshmi, T. and Uthra, G., ‘A New Approach to Find an Optimal Solution of a Fuzzy Linear Programming Problem by Fuzzy Dynamic Programming’, International Journal of Engineering & Technology, 7(4.10) (2018), 360-363.
[12] Kaliyaperumal, P., ‘Fuzzy Dynamic Programming Problem for Single Additive Constraint with Additively Separable Return by Means of Trapezoidal Membership Functions’, Handbook of Research on Fuzzy and Rough Set Theory in Organizational Decision Making, (2017), 168-187.
[13] Rajkumar, A., Ghousia Begum. S., and Jose Parvin Praveena. N., ‘Shortest path using dynamic programming through fuzzy numbers’, AIP Conference Proceedings, 2261, 030114 (2020); https://doi.org/10.1063/5.0017631
[14] Kumar, A., Singh, P., Kaur, A., and Kaur, P., RM approach for ranking of generalized trapezoidal fuzzy numbers, Fuzzy Information and Engineering, 1 (2010), 37–47.
