Soft Comput DOI 10.1007/s00500-017-2605-8
FOCUS
A hybrid genetic algorithm and DEA approach for multi-criteria fixed cost allocation Parag C. Pendharkar1
© Springer-Verlag Berlin Heidelberg 2017
Abstract This paper proposes a hybrid genetic algorithm and data envelopment analysis framework for solving the fixed cost allocation (FCA) problem. The proposed framework allows managers to incorporate different FCA subobjectives for efficient and inefficient decision-making units (DMUs) and solves the FCA problem so that the total entropy of resource allocation for efficient DMUs is maximized, and correlation between resource allocation and efficiency scores of inefficient DMUs is minimized. The FCA sub-objectives and solutions are kept consistent with the overall management objective of rewarding efficient DMUs by allocating to them fewer fixed cost resources. We illustrate the application of our approach using an example from the literature. The results of our study indicate that the solution values obtained in our study are superior to those obtained in other studies under various criteria. Additionally, the relative gap between the solution obtained using our procedure, and the upper bound on the optimal value is approximately 1%, which indicates that our solution is very close to the optimal solution. Keywords Multi-criteria decision making · Data envelopment analysis · Genetic algorithms · Fixed cost allocation
Communicated by A. Genovese, G. Bruno.
B 1
Parag C. Pendharkar
[email protected] http://www.personal.psu.edu/pxp19/ School of Business Administration, Pennsylvania State University at Harrisburg, 777 West Harrisburg Pike, Middletown, PA 17057, USA
1 Introduction Recently, there is a surge in interest for applying data envelopment analysis (DEA) for cost efficiency analysis (Ray 2016) and cost allocation (Tsionas and Mamatzakis 2017). The problem of allocating common fixed costs to several business units is called the fixed cost allocation (FCA) problem. The FCA problem was first proposed by Cook and Kress (Cook and Kress 1999) and a number of studies followed to solve this problem (Beasley 2003; Cook and Zhu 2005; Du et al. 2014). In the FCA literature, there are two primary objectives used to solve the FCA problem. In both cases, the new fixed cost is allocated as an additional input for a decision-making unit (DMU). The first objective highlighted in the literature is the efficiency invariance objective, where the FCA problem with additional input was solved so that the new efficiency of the DMU remains unchanged after adding new input (Cook and Kress 1999). The second objective is that of maximizing average efficiency, where fixed cost is distributed by adding additional input and distributing fixed cost in a way that maximizes average efficiency across all DMUs (Beasley 2003). The literature highlights that both approaches have their merits (Cook and Zhu 2005), but solution procedures for solving the FCA problem with either objective are very different. Notably, there are a few studies that investigate a variant of the FCA problem called fixed cost and target setting problem where the objective is an allocation of fixed costs where certain predetermined output targets are achieved (Amirteimoori and Kordrostami 2005; Hosseinzadeh Lotfi et al. 2013; Lin 2011a). A recent study proposed another variant where minimum efficiency constraints for centralized resource allocation were used (Hakim et al. 2016). Solving the FCA problem is not a trivial matter. Even for an agreed-upon objective of efficiency invariance, numerous
123
P. C. Pendharkar
solution procedures exist (Cook and Zhu 2005; Jahanshahloo et al. 2004; Lin 2011b). For multi-input and multi-output FCA problem, multiple optimal solutions exist for the FCA problem with the efficiency invariance objective (Jahanshahloo et al. 2004; Li et al. 2013). Both the solution procedures and the solutions to the FCA problem are limited in their usefulness. For example, some solutions to the FCA arbitrarily assign zero fixed cost to some efficient DMUs and nonzero cost to other efficient DMUs (Cook and Zhu 2005). On one extreme, one study proposes a procedure that assigns high nonzero cost allocations to efficient DMUs and zero values to some of the inefficient units (Hosseinzadeh Lotfi et al. 2013). Many studies assign higher fixed costs to some efficient DMUs and lower costs to inefficient DMUs (Lin 2011b; Jahanshahloo et al. 2004; Li et al. 2013). If the objective of fixed cost allocation is to penalize inefficient DMUs, then none of these solutions will be acceptable in the real world. A few researchers have mentioned the need to consider equity and fairness in FCA (Yang and Zhang 2015; Si et al. 2013; Amirteimoori and Kordrostami 2005). Although we believe that these proposed measures are limited in the sense that the definition of equity and fairness was more related to equal allocation of fixed cost to all DMUs regardless of their efficiency scores, we call this equal resource distribution approach an equitable approach (EA) to distribution of resources for the FCA problem. In this paper, we argue that managerial objectives must be considered for solving the FCA problem. Only after considering managerial objectives, appropriate solution procedures can be designed and evaluated. For example, data envelopment analysis (DEA) is used in software engineering literature for over two decades (Banker and Slaughter 1997; Banker and Kemerer 1999). There are two scenarios where fixed cost of either employee training or performance bonus may be allocated to software-development projects. In case of employee training, the managerial objective may be to assign as little cost to efficient software projects as possible because employees of efficient software projects are less likely to receive any benefits of additional employee training. However, for assigning performance bonus, the managerial objective would be exactly opposite where efficient projects must be assigned a cost that is as high as possible. The EA or traditional approaches for solving FCA problem may not yield satisfactory results. Thus, it is necessary to tailor and solve the FCA problem based on managerial objectives. For the rest of the paper, we assume that managerial objective is to assign as little cost to efficient projects as possible in an equitable way. Our approach may be suitable for most consulting organizations that have billable and overhead costs. Billable costs such as employee salaries are directly charged to projects, whereas overhead costs (e.g., recruiting costs) are
123
distributed among projects. Fair and equitable distribution of these overhead costs is an important managerial problem. By assigning low overhead costs to high-performing projects, managers free resources from these projects so that the projects have enough resources to provide performance incentives (e.g., bonus), and vice versa. Given managerial objective, we adopt a definition of equity that is more performance oriented in that the maximum cost allocation for any of efficient DMUs must be less than the minimum cost allocated to any of the inefficient DMUs thereby encouraging higher performance for each inefficient DMU. Only when such criterion is satisfied, management is ensuring that efficient projects are not penalized. Second, as far as possible, all efficient projects must be assigned a cost that is as equal as possible (i.e., EA-based resource distribution only for efficient DMUs). Since DEA does not discriminate among efficient projects neither should the FCA solution procedure when allocating costs among efficient units. Third, an inverse correlation is desirable between cost allocation and efficiency of inefficient DMUs. This inverse correlation ensures that extremely inefficient DMUs are assigned higher costs than DMUs that are borderline inefficient. Fourth, efficiency invariance objective must be satisfied. Finally, all DMUs must be assigned a cost, and no DMU should be assigned a zero cost. Resource allocation via solving the FCA satisfying aforementioned criteria will find easy acceptance within an organization, but will make solving the FCA problem much more difficult. Fortunately, these criteria can be incorporated into a hybrid heuristic genetic algorithm (GA) and DEA model. When several of these criteria are incorporated into the traditional FCA problem, we call it multi-criteria FCA (MCFCA) problem. This paper proposes and solves the MCFCA. The rest of the paper is organized as follows: Sect. 2 describes the MCFCA problem. Section 3 describes the GA– DEA procedure for solving the MCFCA problem. Section 4 describes the results of our experiments using the Cook and Kress (Cook and Kress 1999) example. Section 5 concludes the paper with a summary and provides directions for future research.
2 A multi-criteria fixed cost allocation problem We assume a homogenous production process consisting of n DMUs where each DMU j with j = 1, . . ., n consumes m inputs and produces s outputs. Let x j = [x1 j , . . ., xm j ]T and y j = [y1 j , . . ., ys j ]T represent input and output vectors for DMU j , respectively. The dual of output oriented DEA CCR model (Charnes et al. 1978), solved for each decision making p = 1, . . ., n appearing in objective function, can be represented as follows:
A hybrid genetic algorithm and DEA approach for multi-criteria fixed cost allocation
Maximizeλ j ϕ p , Subject to : n j=1 n
(2.1)
λ j xi j ≤ xi p
i = 1, . . . , m,
(2.2)
λ j yr j ≥ ϕ p yr p
r = 1, . . . , s,
(2.3)
j = 1, . . . , n.
(2.4)
λj ≥ 0
The efficiency of DMU p , ξ p = ϕ1∗ , takes a value of 1 and p considered efficient when ϕ ∗p = 1, otherwise ξ p < 1 and DMU p is considered inefficient. If common cost R is distributed among n DMUs so that each DMU is assigned a cost r j such that nj=1 r j = R then the new FCA DEA model with additional input r j can be written as follows: Maximizeλ j ϕ pF , Subject to :
j=1 n j=1 n
(2.5)
λ j xi j ≤ xi p
i = 1, . . . , m,
(2.6)
r = 1, . . . , s,
(2.7)
j = 1, . . . , n.
(2.8)
λjr j ≤ rp λ j yr j ≥ ϕ p yr p
j=1
λj ≥ 0 We define ξ pF =
n
j
j=1
n
Minimizeξ F
2 n j=1 ξ jF − ξ j
1 ϕ pF∗
obtained by solving the FCA problem (2.5)–(2.8). The con straint nj=1 λ j r j ≤ r p is essentially part of (2.6) to account for new additional input in the augmented DEA model with m + 1 inputs. Thus, we do not give it a separate equation number. To describe our multi-criteria, we assume that the overall managerial objective is to reward efficient DMUs from (2.1) to (2.4) by assigning to them as little r j > 0 as possible. For all DMUs j = 1, . . ., n, we define an efficient set E where DMU j ∈ E if and only if its corresponding ξ j = 1. Other/ E. Our first criterion is that of efficiency wise, DMU j ∈ invariance. Efficiency invariance is obtained when ξ j = ξ Fj ∀ j = 1, . . ., n. Since in multi-criteria decision-making problems, there are tradeoffs between different criteria and a possibility exists that not all criteria are fully satisfied leading to Pareto optimal solutions, we incorporate an efficiency invariance criterion as that of minimizing root mean square (RMS) error between ξ j and ξ Fj . Mathematically, this criterion can be represented as:
(2.9)
Since the managerial objective is to reward efficient DMUs by assigning to them as little fixed cost as possible, we highlight a fairness objective where the maximum resource (i.e., cost) assigned to any efficient DMU must be less than the minimum resource assigned to any of inefficient DMUs. This fairness criterion can be represented as follows:
rj . max j∈E r j < min j ∈E /
(2.10)
The DEA assigns efficiency score values of 1 to several DMUs due to the weighted flexibility problem where each DMU is allowed to set weights to maximize its own efficiency (Dyson and Thannassoulis 1988), additional fairness criterion requires that resource assignments to DMUs belonging to efficient set be as identical as possible. This identical distribution of resources can be measured using the principle of maximum entropy (Jaynes 1957). We define additional variables ω j s, where each ω j represents a fraction of resource R assigned to DMU j . Mathematically, n rj = ω , ω > 0 and ω j j j=1 j = 1. If ω E = j∈E ω j , R then fairness criterion for equal resource distribution for efficient DMUs can be achieved by maximizing following expression: ⎛ Maximizeω j
as the optimal efficiency of DMU p
.
⎞ ωj ωj ⎝− ⎠. ln ωE ωE
(2.11)
j∈E
Continuing with fairness criteria, for inefficient DMUs, higher resources are assigned to DMUs that have lower efficiency scores. If ρξr represents Pearson’s correlation coefficient between original efficiency scores ξ j and resource assignments r j for inefficient DMUs, then following expression should be minimized: ρξr min j ∈E /
(2.12)
Equations (2.9)–(2.12) constitute four different criteria that need to be optimized in an FCA problem to ensure that the overall managerial objective of panelizing inefficient DMUs by assigning to them higher fixed cost is achieved in a fair way. It is well known that the traditional FCA problem has multiple optimal solutions (Jahanshahloo et al. 2004). The MCFCA would also have multiple Pareto optimum solutions. Thus, solving the MCFCA requires a hybrid GA and DEA approach to search through possible Pareto optimal solutions search space and identify the best solution that satisfies all criteria.
123
P. C. Pendharkar
3 A genetic algorithm and DEA procedure for solving the MCFCA problem There are a few heuristics approaches available for solving continuous and combinatorial optimization problems. Among the popular heuristics to solve continuous optimization are genetic algorithms (GA) and particle swarm optimization (PSO). Tabu search (Glover and Laguna 1997) and simulated annealing (Kirkpatrick et al. 1983) heuristics are primarily used for combinatorial optimization problems. Since our problem is that of continuous optimization, only GA and PSO are suitable to solve the MCFCA. Among these two heuristics, GA has a slight advantage in our case because our problem is that of constrained optimization. In the PSO (Kennedy and Eberhart 2001), imposing constraints can be challenging because birds in the PSO optimization are allowed to fly unconstrained. Adding constraints in GA is slightly easier, and therefore we use this heuristics in our research. GAs are population-based search procedures that use the principle of survival of the fittest to evolve solutions to optimization problems (Goldberg 1989). A GA starts with random set of population members and uses selection, crossover and mutation operators to evolve populations that achieve higher fitness over successive generations. Traditionally, GA population members are represented as binary variables, but non-binary representations are often used due to their ease of implementation (Pendharkar 2008). We use a non-binary GA procedure to evolve and obtain values of ω j as possible solutions of the MCFCA problem. Let’s assume n = 5 and R = 100 then a population member may be represented as a list of five numbers each between (0,1) as: < 0.2, 0.15, 0.1, 0.3, 0.25 >. In this list, ω1 = 0.2, . . ., ω5 = 0.25. The respective resource allocations (r j ) for population member would be ω j R and can be written as: < 20, 15, 10, 30, 42 >. Our GA needs two special constraints that must be satisfied. First, genes in a population members (i.e., values of individual ω j s) must take n a value between zero and one, and second, we must have j=1 ω j = 1. Recently, Pendharkar (Pendharkar 2013) proposed a GA and its operators that ensures both of these constraints are satisfied. We now describe the hybrid GA– DEA procedure. Before our GA procedure starts, we obtain the efficiency values ξ j s by solving formulation (2.1)–(2.4) for each j. Next, for each population member in the GA, we randomly generate j values, β j ∈ (L , U ), where L = 0 and U > 0 may be any positive number. In our study, we use a value of U = 20. The assignment for individual genes in a populaβ tion member is computed from β j s as ω j = n j β , which j=1
j
satisfies the two special constraints mentioned in the previous paragraph. The fitness for a given population member
123
is computed in several steps. First, using genes of population member, we compute resource allocations r j s (shown in previous paragraph) and then solve formulation (2.5)–(2.8) to compute values of ξ Fj because of the interdependence of resource allocations and efficiency values. The score on our first criterion, c1 , is then computed from Eq. (2.9). For our second criterion, we compute its score, c2 , by looking at original efficiency values and r j s; and then applying following rule:
r j THEN c2 = 1 IF max j∈E r j < min j ∈E / ELSE c2 = 0. The criterion scores for third (c3 ) and fourth (c4 ) criteria can be computed directly from Eqs. and (2.12). More (2.11) ωj ωj 3 specifically, c = − j∈E ω E ln ω E and c4 = ρξr . The c3 objective, when maximized, ensures that resource allocation for all efficient units is as equal as possible; and the c4 objective, when minimized, ensures that resource allocation for inefficient units is as high as possible. Since GA uses survival of the fittest strategy, where higher fitness values mean better solutions and given that some of our criteria are maximized (c2 and c3 ) and other minimized (c1 and c4 ), our overall fitness value assuming additive decisionmaker utility function, F, is computed using following formula: F = n − c1 + c2 + c3 − c4 .
(3.1)
After initial random population generation and its fitness calculation, future population generations are evolved using GA operators of selection, crossover and mutation. We use ranking selection operator (Goldberg and Deb 1991) that selects two parents for mating. Mating of parents occurs using the crossover operator. Assuming n = 5, if P1 =< ω1 , ω2 , ω3 , ω4 , ω5 > and P2 =< ω1! , ω2! , ω3! , ω4! , ω5! > are two parents selected using the selection operator, the crossover operations require randomly generating a crossover point between 1 and ( j − 1). Let’s say that this crossover point is 3 then two children C1 and C2 are produced using following crossover operation: ⎛
C1 = ω1 , ω2 , ω3 , ⎝1 − ⎛ ⎝1 −
3 j=1
⎞
3
⎞
ω! ω j ⎠ 5 4
j=1
ω5!
ω j ⎠ 5
! j=4 ω j
,
! j=4 ω j
,
A hybrid genetic algorithm and DEA approach for multi-criteria fixed cost allocation
and ⎛
C2 = ω1! , ω2! , ω3! , ⎝1 −
3
⎞ ω!j ⎠
j=1
⎛ ⎝1 −
3 j=1
⎞ ω!j ⎠
ω4 , 5 ωj j=4
ω5 . 5 ωj j=4
Assume P1 = 0.2, 0.2, 0.2, 0.2, 0.2, P2 = 0.1, 0.15, 0.2, 0.25, 0.3 and crossover point after the third gene as before. We get two children C1 and C2 as follows: 0.25 C1 = 0.2, 0.2, 0.2, (1 − 0.6) , (1 − 0.6) 0.25 + 0.3 0.3 =< 0.2, 0.2, 0.2, 0.182, 0.218 >; 0.25 + 0.3 and 0.2 C2 = 0.1, 0.15, 0.2, (1 − 0.45) , (1 − 0.45) 0.2 + 0.2 0.2 =< 0.1, 0.15, 0.2, 0.275, 0.275 > . 0.2 + 0.2 nIt is easy to see that the crossover operator always satisfies j = 1 constraint. j=1 ω The nj=1 ω j = 1 constraint eliminates the possibility of single gene mutation unless the mutated gene is an exact replica of itself in which case mutation operation becomes redundant. The next best possibility is to consider two gene mutation. In our mutation approach, we consider a swap mechanism with two possibilities applied with equal probability. In the first possibility, we randomly pick two genes and swap their values. In the second possibility, we randomly pick two genes and replace the value of one gene with sum of original values of both genes and the other gene with a value of zero. In our five gene simple example, we mutate C1 using first possibility and C2 using the second possibility. We assume that genes 2 and 5 will be swapped in each case. The result of C1 and C2 after mutation is as follows. C1 = 0.2, 0.218, 0.2, 0.182, 0.2 , and C2 = 0.1, 0.425, 0.2, 0.275, 0 . Our mutation operator causes minimal disruption to majority of genes of the children and introduces a zero value into the genes. For problems where zero resource allocation is undesirable, second approach to mutation that
introduces zero value can be dropped from consideration. In our research, we drop the second approach and only use the first approach to mutate the population members. We note additional implementation consideration that is necessary to ensure that nj=1 ω j = 1 is always satisfied. Due to numerical accuracy errors introduced by computer compilers, over time crossover and mutation operations will lead to violation of nj=1 ω j = 1 constraint. One way to ensure that this violation does not occur is to renormalize all the genes of population members before computing their fitness values. Renormalization divides original values of genes of a population member by their sum. We apply renormalization procedure to each population member before computing its fitness value. Figure 1 illustrates the overall GA–DEA procedure for solving the MCFCA problem.
4 Experiments and results For our experiments, we use the Cook and Kress (Cook and Kress 1999) dataset because it has been used in various studies, and it allows us to compare our approach to the solutions found in different studies reported in literature. Table 1 illustrates this dataset along with original efficiency values for each DMU using the CCR model. We use a value of R = 100 for the problem and apply the managerial objectives highlighted in Sect. 2. After initial experimentation, we set the values of GA operators crossover rate (χ ) to 30%, mutation rate (μ) to 10%, population size (Ω) to 100 and maximum number of learning generations to 500. Table 2 provides the resource allocations using our approach, and the allocations reported in other studies in the literature. Before we compare the results of our study with other studies, we first provide detailed results of our study and the values of four managerial objectives. Table 3 summarizes these results. The results indicate that all four criteria highlighted in Sect. 2 were satisfied. The maximum resource allocation for an efficient unit #4 was 6.62, which was lower than minimum resource allocated for inefficient unit # 10 (7.84). The correlation between efficiency scores and resource allocated for inefficient units was negative at −0.859 giving an indication that generally higher efficiency values for inefficient units were inversely related to actual resource allocations thereby penalizing inefficient units by allocating more resources. The last two columns of Table 3 show that efficiency invariance objective was satisfied as well. Since there are 5 efficient DMUs, the maximum possible entropy score for efficient DMUs in Eq. (2.11) would be: 5 × − 15 ln 15 = 1.609. The best population member entropy value is 1.593, which is very close to 1.609. Figure 2 illustrates the evolution of best population member fitness
123
P. C. Pendharkar
Solve DEA model (2.1)-(2.4) And obtain scores ξj*
Read GA Parameters χ, μ, Ω, ψ
Iteraon =1
Compute fitness for populaon Members using eq. (3.1)
No
Iteraon < ψ
Print best populaon member
Yes Apply roulee selecon
Iteraon=iteraon+1
Apply crossover operator
Apply mutaon operator
Fig. 1 The hybrid GA–DEA procedure to solve MCGCA problem Table 1 The cook and kress Input–Output dataset and CCR efficiency scores
Input 1
Input 2
1
350
39
9
67
751
2
298
26
8
73
611
0.923002
3
422
31
7
75
584
0.747018
4
281
16
9
70
665
1
5
301
16
6
75
445
1
6
360
29
17
83
1070
7
540
18
10
72
457
0.860406
8
276
33
5
78
590
1
9
323
25
5
75
1074
1
10
444
64
6
74
1072
0.831782
11
323
25
5
25
350
0.333333
12
444
64
6
104
1199
and average population fitness in our GA population evolution. The best possible fitness value for a population member (i.e., upper bound on the optimal solution) can be computed from Eq. (3.1) and is 15.609 (where n = 12, c1 = 0, c2 = 1, c3 = 1.609, c4 = −1). The final fitness for best population member was 15.451, which was very close to the best possible fitness value. The relative gap between the fitness of the best population member and upper bound on the optimum solution is about 1% illustrating that the hybrid GA–DEA procedure did well to solve the MCFCA problem.
123
Input 3
Output 1
Output 2
ξDMU
DMU
0.756701
0.961226
1
In our experiments, we also kept track of best found individual criterion values for three different criteria during the GA run. It is important to note that best found criteria values may not necessarily belong to the best fitness population member which represents best found solution on all criteria. Figure 3 illustrates the best found fitness value for our first criterion of RMS defined in Eq. (2.9). The figure illustrates how easy it was to satisfy efficiency invariance assumption in Cook and Kress example (Cook and Kress 1999). It appears that initial random population has a population member with
A hybrid genetic algorithm and DEA approach for multi-criteria fixed cost allocation Table 2 Resource allocations in our study and other related studies DMU
Current study
Cook and Kress (1999)
Beasley (2003)
Cook and Zhu (2005)
Hosseinzadeh Lotfi et al. (2013)
Li et al. (2013)
Lin (2011a)
Jahanshahloo et al. (2004)
1
8.412
14.52
6.78
11.22
8.199
6.3839
6.86678396
8.22144185
2
10.441
6.74
7.21
0
7.462
7.4219
6.189440845
6.85808717
3
11.912
9.32
6.83
16.95
4.284
6.6827
7.287544514
9.50216897
4
6.623
5.6
8.47
0
9.301
8.8327
6.098745945
6.32100806
5
4.160
5.79
7.08
0
4.807
7.6335
4.368493091
6.67217517
6
8.119
8.15
10.06
15.43
15.37
9.6989
7
10.175
8.86
5.09
0
0
4.2765
7.204662758
11.73311299
8
5.939
6.26
7.74
0
7.339
8.3526
5.615905542
6.48626317
9
4.257
7.31
15.11
17.62
16.33
15.871
10
7.838
10.08
10.08
21.15
11.598
9.751
11
16.391
7.31
1.58
17.62
0
12
5.733
10.08
13.97
0
15.31
Table 3 Results of our study along with efficiency scores Allocation
ξDMU
1
8.4122
0.756701
0.756701
2
10.4407
0.923002
0.923002
3
11.912
0.747018
0.747018
1
1
4
6.62308
5
4.15962
1
1
6
8.11901
0.961226
0.961226
0.860406
0.860406
7
10.1748
8
5.93932
1
1
9
4.25661
1
1
10 11 12
7.83839 16.3908 5.73341
5.802228536 13.62795957
0.455
5.802228512
14.6404
18.61793572
8.38669696
7.29188184 10.61764098 7.29188184 10.61764098
RMS value very close to zero (satisfying efficiency invariance criterion). The nonzero infinitesimal values of RMS are primarily due to numerical accuracy considerations of computers. For the most part, efficiency invariance criterion 2.50E-13 2.00E-13
0.831782
0.831782
0.333333
0.333333
1
1
RMS Value
DMU
F ξDMU
12.518071
Best RMS. 1.50E-13 1.00E-13 5.00E-14 0.00E+00 0
Best population member Eq. (2.11) entropy = 1.593 and Eq. (2.12) correlation = −0.859
100
200
300
400
500
Generaon Number
Fig. 3 Best value of RMS found in our experiments Fig. 2 GA average population fitness and best member fitness evolution
16
Relave gap approx. 1%
Fitness Value
15.5 15
Average Fit. of Pop.
14.5
Best Pop. Member Fit. 14
Max Fitness Possible 13.5 13 0
100
200
300
400
500
Generaon Number
123
P. C. Pendharkar 1.61
Entropy Value
1.608 1.606 Best Ent. 1.604 1.602 1.6 1.598
0
100
200
300
Generaon Number
400
500
Fig. 4 Best value of entropy found in our experiments 0 0
100
200
300
400
500
Correlaon Value
-0.2 -0.4 Best Corr. -0.6 -0.8 -1 -1.2
Generaon Number
Fig. 5 Best value of correlation found in our experiments
was satisfied by at least one population member of the initial random GA population. After about 200th generation, best found RMS value did not improve in its value.
Table 4 Allocations for best found individual criterion values
DMU
1
123
Figure 4 illustrates the best entropy value for a population member during the GA run (value of Eq. 2.11). The best value of entropy was found before the 100th generation. The best value of entropy ever found in our GA experiments was 1.6085 against the best possible value of 1.609 and the best fitness population member that had final entropy value of 1.593. Figure 5 illustrates evolution of the best value of correlation coefficient found in our experiments (value of Eq. 2.12). The best value of the correlation coefficient that was found in our experiments was −0.984. The correlation coefficient for genes in the best fitness population member was −0.859. Thus, it appears that first criterion was easy to satisfy, and other three criteria required rigorous search during the GA population evolution. Table 4 lists the best RMS, best entropy and best correlation allocations and corresponding allocation efficiency scores (i.e., ξ Fj values) for best population member values found in Figs. 3, 4 and 5. The best RMS allocations do not satisfy second criterion (Eq. 2.10), and the best correlation and the best entropy allocations do not satisfy both the efficiency invariance criterion and the second criterion. We now revisit Table 2 and compare the results of our experiments with the results of other studies. We recognize that other studies used different criteria for solving the FCA problem, but we believe that our study uses realistic criteria, and solutions satisfying our criteria would be more acceptable in the real world. We reiterate our criteria before comparing different resource allocation results. We consider the fairness of resource allocation in “performance oriented” sense described by five criteria: four described by Eqs. (2.9)– (2.12) and fifth of nonzero resource allocation for all DMUs
Best RMS allocation
Best entropy allocation
Allocation
F ξDMU
Allocation
F ξDMU
22.4522
Best correlation allocation Allocation
F ξDMU
0.756701
12.4202
0.756701
7.88679
0.756701
2
8.01207
0.923002
12.6547
0.923002
5.57528
0.97504
3
6.42899
0.747018
3.91622
1
7.90913
0.758712
4
6.97066
1
7.16849
1
6.43447
1
5
3.91012
1
7.98988
1
6
12.8913
0.961226
7
11.7194
0.860406
10.7708
16.5984
1
0.961226
4.15071
1
9.59699
0.860406
5.58369
1
8
7.44615
1
7.2503
1
7.02293
1
9
3.82479
1
7.48924
1
4.29397
1
10
7.81694
0.831782
0.831782
7.34828
0.831782
11
5.79706
0.333333
3.55709
0.617548
12
2.73032
1
7.15342
1
10.0327
21.9668 5.22957
0.333333 1
A hybrid genetic algorithm and DEA approach for multi-criteria fixed cost allocation Table 5 Comparison of our results with the results of related studies Criterion
Current study
Cook and Kress (1999)
Beasley (2003)
Cook and Zhu (2005)
Hosseinzadeh Lotfi et al. (2013)
Li et al. (2013)
Lin (2011a) Jahanshahloo et al. (2004)
RMS (Eq. 2.9)
0.0
0.0
0.23a
0.0
0.23a
0.23a
0.0
0.0
Fairness (Eq. 2.10)
Yes
No
No
No
No
No
No
No
Entropy (Eq. 2.11)
1.59262
1.58362
1.55887
N/A
1.51745
1.56161
1.43485
1.58822
Correlation (Eq. 2.12) −0.8586
0.0606
0.8165
−0.3951
0.6145
0.8324
0.46017
0.29124
NonZero
Yes
Yes
No
No
Yes
Yes
Yes
a
Yes
Efficiency invariance was not the primary objective of resource allocations in these studies
(which is automatically satisfied by our GA operators). We report these comparisons in Table 5. The results indicated that our results are the best. On numeric criteria of entropy and correlation coefficient, when compared to other studies, our results provide the highest entropy value and the lowest correlation value. Efficiency invariance was an easy criterion to satisfy and all studies that used this criterion satisfied it. Only our study results satisfy the fairness criterion (Eq. 2.10). Based on results from Figs. 3, 4 and 5, it appears that fairness criterion was the most difficult to satisfy and there were tradeoffs on satisfying this criterion and other numeric criteria of maximizing entropy and minimizing correlation coefficient. When compared to the upper bound on the fitness function, our best population member has a value that was approximately 1% lower than the upper bound. This low relative gap indicates that the solution found by our procedure is very high-quality solution.
The hybrid GA–DEA approach proposed and used in this study is flexible, easy to understand and use. Our approach also allows a decision-maker to add additional constraints, such as lower bound on minimum resource allocation. These constraints can be implemented into the GA fitness function using the method using IF-THEN rules used to implement fairness criterion from Eq. (2.10). The GA operators of crossover and mutation used in our study served us well. However, it may be possible to improve upon these operators. Future research may focus on either adding additional criteria to the MCFCA problem or improving GA operators for solving the MCFCA problem. Compliance with ethical standards
Conflict of interest Author Parag Pendharkar declares that he has no conflict of interest. Human and animal rights This article does not contain any studies with human participants performed by any of the authors.
5 Summary, conclusions and directions to future work Most studies in the FCA considered either overall efficiency maximization or satisfying efficiency invariance as the primary objectives of the FCA problem. In our study, we illustrate that solving the FCA using these objectives may provide solutions that managers may not find very useful in the real world. In the real world, allocation of resources may be made with objectives of either assigning higher resources to efficient DMUs or assigning lower resources to efficient DMUs . In our study, assuming resource allocation to encourage higher performance by assigning lower resources (as a new input) to high-performing DMUs, we propose a set of fairness and equity criteria to propose an MCFCA problem. After proposing the MCFCA problem, we proposed a hybrid GA–DEA method to solve the MCFCA problem. Next, we solved the MCFCA problem using the Cook and Kress (Cook and Kress 1999) example. The results of our experiments indicate that the best solution found in our study is superior to other solutions available in the literature.
Informed consent No human subjects were involved so informed consent was not applicable.
References Amirteimoori A, Kordrostami S (2005) Allocating fixed costs and target setting: a DEA-based approach. Appl Math Comput 171:136–151. doi:10.1016/j.amc.2005.01.064 Banker RD, Kemerer CF (1999) Scale economies in new software development. IEEE Trans Softw Eng 15:1199–1205 Banker RD, Slaughter S (1997) A field study of scale economies in software maintenance. Manag Sci 43:1709–1725 Beasley J (2003) Allocating fixed costs and resources via data envelopment analysis. Eur J Oper Res 147:198–216. doi:10.1016/ S0377-2217(02)00244-8 Charnes A, Cooper WW, Rhodes E (1978) Measuring the efficiency of decision making units. Eur J Oper Res 2:429–444 Cook WD, Kress M (1999) Characterizing an equitable allocation of shared costs: a DEA approach. Eur J Oper Res 119:652–661. doi:10.1016/S0377-2217(98)00337-3 Cook WD, Zhu J (2005) Allocation of shared costs among decision making units: a DEA approach. Comput Oper Res 32:2171–2178. doi:10.1016/j.cor.2004.02.007
123
P. C. Pendharkar Du J, Cook WD, Liang L, Zhu J (2014) Fixed cost and resource allocation based on DEA cross-efficiency. Eur J Oper Res 235:206–214 Dyson RG, Thannassoulis E (1988) Reducing weight flexibility in data envelopment analysis. J Oper Res Soc 39:563–576 Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Norwell Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading Goldberg DE, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms, G. Rawlins. Morgan Kaufmann Publishers, Inc., San Mateo Hakim S, Seifi A, Ghaemi A (2016) A bi-level formulation for DEAbased centralized resource allocation under efficiency constraints. Comput Ind Eng 93:28–35 Hosseinzadeh Lotfi F, Hatami-Marbini A, Agrell PJ et al (2013) Allocating fixed resources and setting targets using a common-weights DEA approach. Comput Ind Eng 64:631–640. doi:10.1016/j.cie. 2012.12.006 Jahanshahloo G, Hosseinzadeh Lotfi F, Shoja N, Sanei M (2004) An alternative approach for equitable allocation of shared costs by using DEA. Appl Math Comput 153:267–274. doi:10.1016/ S0096-3003(03)00631-3 Jaynes ET (1957) Information theory and statistical mechanics. Phys Rev 106:620–630 Kennedy J, Eberhart R (2001) Swarm intelligence. Morgan Kaufmann Publishers, Inc., San Francisco Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–679
123
Li Y, Yang M, Chen Y et al (2013) Allocating a fixed cost based on data envelopment analysis and satisfaction degree. Omega 41:55–60. doi:10.1016/j.omega.2011.02.008 Lin R (2011) Allocating fixed costs or resources and setting targets via data envelopment analysis. Appl Math Comput 217:6349–6358. doi:10.1016/j.amc.2011.01.008 Lin R (2011) Allocating fixed costs and common revenue via data envelopment analysis. Appl Math Comput 218:3680–3688. doi:10. 1016/j.amc.2011.09.011 Pendharkar PC (2008) Maximum entropy and least square error minimizing procedures for estimating missing conditional probabilities in Bayesian networks. Comput Stat Data Anal 52:3583–3602. doi:10.1016/j.csda.2007.11.013 Pendharkar PC (2013) Genetic learning of virtual team member preferences. Comput Hum Behav 29:1787–1798 Ray S (2016) Cost efficiency in an Indian bank branch network: a centralized resource allocation model. Omega Int J Manag Sci 65:69–81 Si X, Liang L, Jia G et al (2013) Proportional sharing and DEA in allocating the fixed cost. Appl Math Comput 219:6580–6590. doi:10. 1016/j.amc.2012.12.085 Tsionas EG, Mamatzakis EC (2017) Adjustment costs in the technical efficiency: an application to global banking. Eur J Oper Res 256:640–649 Yang Z, Zhang Q (2015) Resource allocation based on DEA and modified Shapley value. Appl Math Comput 263:280–286
