3.1 Extended assignment problem
As indicated in the previous section, in the traditional assignment problem, it is assumed that each assignment \(i \to j\)incurs \({c_{ij}}\)cost. However, in practice, costs and expenditure can have numerous origins and need to be accurately captured. This scenario can be described by considering n tasks that should be performed by n assignees, whereby p inputs \(x_{{ij}}^{r},\,\,\,1 \leqslant r \leqslant p,\,\,1 \leqslant i,j \leqslant n\) are at the disposal to generate q outputs \(y_{{ij}}^{s},\,\,\,1 \leqslant s \leqslant q,\,\,1 \leqslant i,j \leqslant n\) for each assignment \(i \to j\). It is evident that there are \({n^2}\) possible assignments (and associated inputs and outputs), which can be computationally expensive to evaluate (Bazaraa et al., 2011). As number of assignments (\({n^2}\)) is usually greater than the sum of inputs and outputs (p+q), in this work, we propose the envelopment form DEA model of the expression given by Equation (3) for making this process more efficient:
\(\begin{gathered} {\theta _{ij}}=Min\,\,\theta \, \hfill \\ \,s.t \hfill \\ \,\sum\limits_{{k=1}}^{n} {\sum\limits_{{l=1}}^{n} {{\lambda _{kl}}x_{{kl}}^{r}} } \leqslant \theta x_{{ij}}^{r}\,\,\,\,\,\,\,\,\,1 \leqslant r \leqslant p\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(6) \hfill \\ \,\sum\limits_{{k=1}}^{n} {\sum\limits_{{l=1}}^{n} {{\lambda _{kl}}y_{{kl}}^{r}} } \geqslant y_{{ij}}^{s}\,\,\,\,\,\,\,\,\,\,\,1 \leqslant s \leqslant q & \hfill \\ \,{\lambda _{kl}} \geqslant 0,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant k,l \leqslant n \hfill \\ \, \hfill \\ \end{gathered}\)
As a result, our approach requires only \({n^2}+1\) computations, rather than \(2{n^2}+1\) needed for Chen and Lu's (2007) approach. In addition, as allocating an assignee to a task is not independent of allocation of other assignees, we evaluate all possible assignments. Therefore, our model evaluates an assignment in comparison with all potential assignment not just assignment associated with a specific assignee or a specific task. Consider assignment \(1 \to 1\), for instance. The first index set of (Chen & Lu, 2007) measure the relative efficiency of \(1 \to 1\) compared with other assignments of \(1 \to j,\,\,\,\,2 \leqslant j \leqslant n\), namely horizontally (see figure 1, yellow path). But it is important to note that other assignees also compete over all tasks and should be considered when evaluating assignment\(1 \to 1\).The second index set of (Chen & Lu, 2007) measure the relative efficiency of \(1 \to 1\) compared with other assignments \(j \to 1,\,\,\,\,2 \leqslant j \leqslant n\), namely vertically (red path in figure 1). But we should note that other tasks are competed by all assignees. We propose one set on indices that are found for a specific assignment while all other assignments, namely, vertical and horizontal assignment.
Our model consists of considered assignment model of (Chen & Lu, 2007). Therefore, our model has more discrimination power contrasted with assignment model of (Chen & Lu, 2007). In other words, the efficiency of an assignment in our model is not higher than its efficiency measured by model of (Chen & Lu, 2007). In order to fulfill the assignment problem we use the result of above model to find an efficient assignment based on observed data.
\(\begin{gathered} Min\,\,\,\sum\limits_{{i=1}}^{n} {\sum\limits_{{j=1}}^{n} { - {\theta _{ij}}{x_{ij}}} } \hfill \\ s.t., \hfill \\ \sum\limits_{{j=1}}^{n} {{x_{ij}}=1\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant i \leqslant n} \,\,\,\,\,\,\,\,\,\,\,(7) \hfill \\ \sum\limits_{{i=1}}^{n} {{x_{ij}}=1\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant j \leqslant n} \,\,\,\,\,\,\, \hfill \\ {x_{ij}} \in \{ 0,1\} \,\,\,\,\,\,\,\,\,\,\,1 \leqslant i,j \leqslant n \hfill \\ \end{gathered}\)
Note that we use the efficiency of each assignment for the coefficient of objective function, that is, higher is better. That is why a minus is multiplied to the coefficient in contrast with cost coefficient of generic assignment problem of (4). One may multiply all coefficients by a minus and find the following model:
\(\begin{gathered} Max\,\,\,\sum\limits_{{i=1}}^{n} {\sum\limits_{{j=1}}^{n} {{\theta _{ij}}{x_{ij}}} } \hfill \\ s.t., \hfill \\ \sum\limits_{{j=1}}^{n} {{x_{ij}}=1\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant i \leqslant n} \,\,\,\,\,\,\,\,\,\,\,(8) \hfill \\ \sum\limits_{{i=1}}^{n} {{x_{ij}}=1\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant j \leqslant n} \,\,\,\,\,\,\, \hfill \\ {x_{ij}} \in \{ 0,1\} \,\,\,\,\,\,\,\,\,\,\,1 \leqslant i,j \leqslant n \hfill \\ \end{gathered}\)
It is a well-known fact in DEA literature that \(0<{\theta _{ij}} \leqslant 1\). Although extended logarithmic model of (Chen & Lu, 2007) helps to reduce some complexity, but that fact may causes some obstacles for their model (model (M8)). First, efficient distribution loses their coefficient in the objective function (note that \(\log ({\theta _{ij}})=\log (1)=0\)). Second, other distribution have a negative coefficient in the objective function (note that \(\log ({\theta _{ij}})<0\)for \(0<{\theta _{ij}}<1\). In fact, model of (Chen & Lu, 2007) minimizes sum of efficiencies multiplied by associated distribution that may be crucial. Our extended model of (8) overcome to all aforementioned obstacles by choosing proper coefficient for objective function.
3.2 Extended transportation problem
The classical transportation problem consider a cost of \({c_{ij}}\) for distribution of commodity from source \(1 \leqslant i \leqslant m\) to destination \(1 \leqslant j \leqslant n\). In many real world applications a distribution consist of multiple inputs and multiple outputs. Thus, consider m sources that supply commodities for n destination and assume p inputs \(x_{{ij}}^{r},\,\,\,1 \leqslant r \leqslant p,\,\,1 \leqslant i \leqslant m,\,\,1 \leqslant j \leqslant n\)and q outputs \(y_{{ij}}^{s},\,\,\,1 \leqslant s \leqslant q,\,\,1 \leqslant i \leqslant m,\,\,1 \leqslant j \leqslant n\)for a distribution of \(i \to j,\,\,1 \leqslant i \leqslant m,\,\,1 \leqslant j \leqslant n\). We may use the following model for evaluating this distribution in comparison with all other possible distributions:
\(\begin{gathered} {\theta _{ij}}=Min\,\,\theta \, \hfill \\ \,s.t \hfill \\ \,\sum\limits_{{k=1}}^{m} {\sum\limits_{{l=1}}^{n} {{\lambda _{kl}}x_{{kl}}^{r}} } \leqslant \theta x_{{ij}}^{r}\,\,\,\,\,\,\,\,\,1 \leqslant r \leqslant p\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(9) \hfill \\ \,\sum\limits_{{k=1}}^{m} {\sum\limits_{{l=1}}^{n} {{\lambda _{kl}}y_{{kl}}^{r}} } \geqslant y_{{ij}}^{s}\,\,\,\,\,\,\,\,\,\,\,1 \leqslant s \leqslant q & \hfill \\ \,{\lambda _{kl}} \geqslant 0,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant k \leqslant m,\,\,1 \leqslant l \leqslant n \hfill \\ \, \hfill \\ \end{gathered}\)
In contrast with model of (Amirteimoori, 2011) our model has higher discrimination power, that is, measured efficiency of a distribution by our model is not higher than its measured efficiency by model of (Amirteimoori, 2011). With a same argument as previous subsection on assignment problem, here our model evaluate a distribution \(k \to j\)for a fixed k and j in comparison with all possible distributions contrasted with (Amirteimoori, 2011)’s model that compare that distribution within specific group of distributions, namely, \(k \to j,\,\,\,\,1 \leqslant j \leqslant n\)and fixed k. In fact, (Amirteimoori, 2011)’s model only consider destination in his first extended model and no comparison is assumed between sources. In order to overcome to this obstacle, (Amirteimoori, 2011) used second extended model that consider only sources and then he defined the average optimal value of these two extended models for efficiency a distribution. It is important to point out that choosing destination for a source is not only depend on the potential destinations and associated costs but also it is depend on the associated cost of other sources and associated cost of those destinations. Therefore, our model evaluate a distribution in comparison with all potential distributions not potential destinations. The extended transportation problem using the information of efficiency evaluation process can be found as follows:
\(\begin{gathered} Max\,\,\,\sum\limits_{{i=1}}^{n} {\sum\limits_{{j=1}}^{n} {{\theta _{ij}}{x_{ij}}} } \hfill \\ s.t., \hfill \\ \sum\limits_{{j=1}}^{n} {{x_{ij}}={s_i}\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant i \leqslant m} \,\,\,\,\,\,\,\,\,\,(10) \hfill \\ \sum\limits_{{i=1}}^{n} {{x_{ij}}={d_j}\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant j \leqslant n} \,\,\,\,\,\,\, \hfill \\ {x_{ij}} \geqslant 0\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,1 \leqslant i \leqslant m,\,\,\,1 \leqslant j \leqslant n \hfill \\ \end{gathered}\)
Another difference between our extended transportation model and model of (Amirteimoori, 2011) is that we use \({\theta _{ij}}\)as coefficient of objective function instead of \(1 - {\theta _{ij}}\). But it is a well-known fact that \(0<{\theta _{ij}} \leqslant 1\), so some distribution may be found efficient (see example of (Amirteimoori, 2011)), that is, \({\theta _{ij}}=1\) and it is problematic since associated distribution vanishes in the objective function. But by the fact that \({\theta _{ij}}>0\), thus we do not have this problem in extended model of (10).