An alternative formulation for the fuzzy assignment problem

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit measured as crisp. However, in many real applications, costs are not deterministic numbers. This paper develops a procedure based on Data Envelopment Analysis method to solve the assignment problems with fuzzy costs or fuzzy profits for each possible assignment. It aims to obtain the points with maximum membership values for the fuzzy parameters while maximizing the profit or minimizing the assignment cost. In this method, a discrete approach is presented to rank the fuzzy numbers first. Then, corresponding to each fuzzy number, we introduce a crisp number using the efficiency concept. A numerical example is used to illustrate the usefulness of this new method.     

An extended transportation problem: a DEA-based approach

The transportation problem is an important network structured linear programming problem that arises in several contexts and that has received a great deal of attention in the literature. The existing transportation problems are limited to consideration unit of shipping cost or profit along an arc. However, in many real applications, various attributes are usually considered in a transportation problem. The current paper, proposes an extension to this problem in the presence of multiple in-commensurate inputs and outputs for each arc. The concept of relative efficiency is defined for each possible transportation plan. Two linear programming models are proposed to determine the transportation plan with the maximum efficiency. A numerical example is used to illustrate the applicability of the approach.     

Multiobjective data envelopment analysis

Data envelopment analysis (DEA) is popularly used to evaluate relative efficiency among public or private firms. Most DEA models are established by individually maximizing each firm's efficiency according to its advantageous expectation by a ratio. Some scholars have pointed out the interesting relationship between the multiobjective linear programming (MOLP) problem and the DEA problem. They also introduced the common weight approach to DEA based on MOLP. This paper proposes a new linear programming problem for computing the efficiency of a decision-making unit (DMU). The proposed model differs from traditional and existing multiobjective DEA models in that its objective function is the difference between inputs and outputs instead of the outputs/inputs ratio. Then an MOLP problem, based on the introduced linear programming problem, is formulated for the computation of common weights for all DMUs. To be precise, the modified Chebychev distance and the ideal point of MOLP are used to generate common weights. The dual problem of this model is also investigated. Finally, this study presents an actual case study analysing R&D efficiency of 10 TFT-LCD companies in Taiwan to illustrate this new approach. Our model demonstrates better performance than the traditional DEA model as well as some of the most important existing multiobjective DEA models.     

Common set of weights in data envelopment analysis: a linear programming problem

Data Envelopment Analysis is used to determine the relative efficiency of Decision Making Units as the ratio of weighted sum of outputs by weighted sum of inputs. To accomplish the purpose, a DEA model calculates the weights of inputs and outputs of each DMU individually so that the highest efficiency can be estimated. Thus, the present study suggests an innovative method using a common set of weights leading to solving a linear programming problem. The method determines the efficiency score of all DMUs and rank them too.     

An extended shortest path problem: A data envelopment analysis approach

A special and important network structured linear programming problem is the shortest path problem. Classical shortest path problems assume that there are unit of shipping cost or profit along an arc. In many real occasions, various attributes (various costs and profits) are usually considered in a shortest path problem. Because of the frequent occurrence of such network structured problems, there is a need to develop an efficient procedure for handling these problems. This paper studies the shortest path problem in the case that multiple attributes are considered along the arcs. The concept of relative efficiency is defined for each path from initial node to final node. Then, an efficient path with the maximum efficiency is determined.     

Uncertain programming model for uncertain optimal assignment problem

This paper employs uncertain programming to deal with uncertain optimal assignment problem in which profit is uncertain. Within the framework of uncertain programming, it gives the uncertainty distribution of the optimal assignment profit, and the concept of α-optimal assignment for uncertain optimal assignment problem is proposed. Then α-optimal model is also constructed. Taking advantage of properties of uncertainty theory, α-optimal model can be transformed into a corresponding deterministic form, which can be solved by Kuhn–Munkres algorithm.     

Maximally productive input–output units

Technical or Pareto–Koopmans efficiency models can be based on ratios of weighted sums of outputs to weighted sums of inputs. Differing meanings have been considered for such factor weights. In this paper, we use value or cost rate meanings depending on model orientation. These meanings permit considering the simultaneous assignment of input and output factor weights along with optimal intensity values for a virtual composite unit constructed from the observed units. An optimization principle we call the winners-take-all criterion is proposed for determining the maximally productive unit(s). No assumptions are required on the internal transformation processes of the units. The model simultaneously determines the intensities and factor weights and results in indefinite quadratic programming problems that simplify to linear programming in certain cases. For the general case, genetic search is applied. Numerical illustrations are provided for faculty merit scoring and for the 15 hospital dataset of Sherman.     

Equivalence in two-stage DEA approaches

Data envelopment analysis (DEA) is a linear programming problem approach for evaluating the relative efficiency of peer decision making units (DMUs) that have multiple inputs and outputs. DMUs can have a two-stage structure where all the outputs from the first stage are the only inputs to the second stage, in addition to the inputs to the first stage and the outputs from the second stage. The outputs from the first stage to the second stage are called intermediate measures. This paper examines relations and equivalence between two existing DEA approaches that address measuring the performance of two-stage processes.     

Measuring the efficiency of decision making units

A nonlinear (nonconvex) programming model provides a new definition of efficiency for use in evaluating activities of not-for-profit entities participating in public programs. A scalar measure of the efficiency of each participating unit is thereby provided, along with methods for objectively determining weights by reference to the observational data for the multiple outputs and multiple inputs that characterize such programs. Equivalences are established to ordinary linear programming models for effecting computations. The duals to these linear programming models provide a new way for estimating extremal relations from observational data. Connections between engineering and economic approaches to efficiency are delineated along with new interpretations and ways of using them in evaluating and controlling managerial behavior in public programs.     

A compromise solution approach for finding common weights in DEA: an improvement to Kao and Hung's approach

Data envelopment analysis (DEA) is the leading technique for measuring the relative efficiency of decision-making units (DMUs) on the basis of multiple inputs and multiple outputs. In this technique, the weights for inputs and outputs are estimated in the best advantage for each unit so as to maximize its relative efficiency. But, this flexibility in selecting the weights deters the comparison among DMUs on a common base. For dealing with this difficulty, Kao and Hung (2005) proposed a compromise solution approach for generating common weights under the DEA framework. The proposed multiple criteria decision-making (MCDM) model was derived from the original non-linear DEA model. This paper presents an improvement to Kao and Hung's approach by means of introducing an MCDM model which is derived from a new linear DEA model.     

Dynamic Capacity Acquisition and Assignment under Uncertainty

Given a set of m resources and n tasks, the dynamic capacity acquisition and assignment problem seeks a minimum cost schedule of capacity acquisitions for the resources and the assignment of resources to tasks, over a given planning horizon of T periods. This problem arises, for example, in the integrated planning of locations and capacities of distribution centers (DCs), and the assignment of customers to the DCs, in supply chain applications. We consider the dynamic capacity acquisition and assignment problem in an environment where the assignment costs and the processing requirements for the tasks are uncertain. Using a scenario based approach, we develop a stochastic integer programming model for this problem. The highly non-convex nature of this model prevents the application of standard stochastic programming decomposition algorithms. We use a recently developed decomposition based branch-and-bound strategy for the problem. Encouraging preliminary computational results are provided.     

Multi-objective integer programming: A general approach for generating all non-dominated solutions

In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical ε-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical ε-constraint method on the bi-objective integer programming problem for the sake of completeness and comment on its efficiency. Then present our method on tri-objective integer programming problem and then extend it to the general MOIP problem with k objectives. A numerical example considering tri-objective assignment problem is also provided.     

A new framework for the solution of DEA models

We provide an alternative framework for solving data envelopment analysis (DEA) models which, in comparison with the standard linear programming (LP) based approach that solves one LP for each decision making unit (DMU), delivers much more information. By projecting out all the variables which are common to all LP runs, we obtain a formula into which we can substitute the inputs and outputs of each DMU in turn in order to obtain its efficiency number and all possible primal and dual optimal solutions. The method of projection, which we use, is Fourier–Motzkin (F–M) elimination. This provides us with the finite number of extreme rays of the elimination cone. These rays give the dual multipliers which can be interpreted as weights which will apply to the inputs and outputs for particular DMUs. As the approach provides all the extreme rays of the cone, multiple sets of weights, when they exist, are explicitly provided. Several applications are presented. It is shown that the output from the F–M method improves on existing methods of (i) establishing the returns to scale status of each DMU, (ii) calculating cross-efficiencies and (iii) dealing with weight flexibility. The method also demonstrates that the same weightings will apply to all DMUs having the same comparators. In addition it is possible to construct the skeleton of the efficient frontier of efficient DMUs. Finally, our experiments clearly indicate that the extra computational burden is not excessive for most practical problems.     

A multi-objective joint replenishment inventory model of deteriorated items in a fuzzy environment

In this study, a fuzzy multi-objective joint replenishment inventory model of deteriorating items is developed. The model maximizes the profit and return on inventory investment (ROII) under fuzzy demand and shortage cost constraint. We propose a novel inverse weight fuzzy non-linear programming (IWFNLP) to formulate the fuzzy model. A soft computing, differential evolution (DE) with/without migration operation, is proposed to solve the problem. The performances of the proposed fuzzy method and the conventional fuzzy additive goal programming (FAGP) are compared. We show that the solution derived from the IWFNLP method satisfies the decision maker’s desirable achievement level of the profit objective, ROII objective and shortage cost constraint goal under the desirable possible level of fuzzy demand. It is an effective decision tool since it can really reflect the relative importance of each fuzzy component.     

A generalized model for weight restrictions in data envelopment analysis

Data envelopment analysis (DEA) is designed to maximize the efficiency of a given decision-making unit (DMU) relative to all other DMUs by the choice of a set of input and output weights. One strength of the original models is the absence of any need of a priori information about the process of transforming inputs into outputs. However, in the practical application of DEA models, this strength has also become a weakness. Incorporation of process knowledge is more a norm than an exception in practice, and typically involves placing constraints on the input and/or output weights. New DEA formulations have evolved to address this issue. However, existing formulations for weight restrictions may underestimate relative efficiency or even render a problem infeasible. A new model formulation is introduced to address this issue. This formulation represents a significant improvement over existing DEA models by providing a generalized, comprehensive treatment for weight restrictions.     

Resolving a strange case of efficiency

In a recent paper in the Journal of the Operational Research Society, Tone proposes an alternative to the Farrell cost efficiency index to avoid the ‘strange case’ problem in which firms with identical inputs and outputs but with input prices differing by some factor (eg, one has input prices twice another) will have the same Farrell cost efficiency. We provide an alternative cost efficiency indicator that avoids this problem, allows for decomposition into technical and allocative efficiency, and is easily estimated using DEA type models.     

A new approach for achievement of the equilibrium efficient frontier with fixed-sum outputs

In a recent paper, Yang et al developed an algorithm based on the extended minimal adjustment strategy and the equilibrium competition strategy to achieve a common equilibrium efficient frontier. However, the computational burden of their algorithm is challenging when a sample contains many inefficient decision-making units (DMUs). In this paper, we propose a linear programming model that can achieve a common equilibrium efficient frontier in a single step, regardless of the number of inefficient DMUs. Furthermore, we demonstrate the existence and the non-uniqueness of the equilibrium efficient frontier and identify its shortcomings through an example. Next, we extend our approach to incorporate weight restrictions to indicate the relative importance of the different inputs and outputs and introduce the secondary goal of minimizing the maximal relative deviation for each fixed-sum output, which can result in a unique equilibrium efficient frontier.     

Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling

We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i’s cost parameter by a cost function of agent j. The cost function of agent j is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is NP-hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations.     

Measuring the Efficiency of Prescribing by General Practitioners

Data envelopment analysis (a mathematical programming technique) has often been applied to measuring the efficiency with which outputs are produced. The technique derives efficient combinations of outputs for given inputs: constant returns to size may be assumed or one may choose to examine whether decreasing or increasing returns hold true. An analysis of the cost of prescribing drugs for 106 general practices in the Lincolnshire Health Authority for the year 1993/1994 reveals the statistical problems that are encountered in applying this technique.     

Congestion analysis in DEA inputs under weight restrictions

Data envelopment analysis (DEA), which is used to determine the efficiency of a decision-making unit (DMU), is able to recognize the amount of input congestion. Moreover, the relative importance of inputs and outputs can be incorporated into DEA models by weight restrictions. These restrictions or a priori weights are introduced by the decision maker and lead to changes in models and efficiency interpretation. In this paper, we present an approach to determine the value of congestion in inputs under the weight restrictions. Some discussions show how weight restrictions can affect the congestion amount.