skip to Main Content

AbstractWhen an organization has multiple projects to be initiated the challenge it faces is the lack of a methodology that would select and prioritize projects that compete for limited resources. This research applies the Data Envelopment Analysis (DEA) approach to the selection and prioritization of projects. drafted research will be used to identify factors used in the selection of projects, classify these factors into inputs and outputs, then develop and solve a DEA model for each project. Results from the solved DEA models will be analyzed to identify highly efficient projects and make recommendations on how to improve inefficient projects.Keywords: DEA, DEA inputs, DEA outputs, project selectionI. INTRODUCTIONDecision making is at the core of all management functions. Managers are constantly called upon to make decisions in order to solve problems and/or to select one course of action from several possible alternative actions in order to obtain the goals and objectives of the organization. Since decisions direct actions, decisions regarding an organization’s, resources, strengths, weaknesses, and future growth are all important factors that will have a considerable impact on the performance of a firm and which will determine the success or failure of the firm. For the past two decades, a factor that has had a significant impact on decision making in many firms is globalization. During the 1990’s the forces of globalization (i.e., new demands of international competition and dramatic advances in technology) substantially changed the nature and operation of markets and organization of the production function in many industries throughout the world. As a result, today’s highly competitive and demand driven market has put increased pressure on management to allocate and utilize resources appropriately in an effort to achieve optimal performance efficiently. Since decisions may be related to the allocation of scarce organizational resources, some of which involve substantial resources, may be difficult to reverse and can affect a company’s business into the future, it is important that decisions are made that allow a firm to operate as efficiently and effectively as possible with the given resources.One of the results of globalization is that it has had a huge impact on the way that organizations perform activities. In order for firms to keep pace with the fast changing environment there is a greater emphasis on project management. Project management was primarily driven by firms that realized the benefits not only of organizing work around projects, but also the need to communicate and coordinate tasks across departments and professions. It is an effective way of dealing with international projects. For project managers and their teams the decision making process often involves selecting one alternative project from several alternative projects. The decision making may be complicated since one or more projects selected from competing projects may be evaluated according to different criteria. Some projects require multiple decision makers and difficulties may arise due to different goals involved. For example, an important part of decision making for competing projects is to verify and validate alternatives. This may require input not only from the project manager but also from engineers or analysts. Even if decision makers share the same selection criteria, the importance level that is attached to each criterion is not necessarily the same, due to different budgets, time factors, alternative projects under consideration etc. At times several competing projects may be considered at the same time, with no interest a priori to one or more of the projects. The decision making may be further complicated because of a large number of attributes that must be considered. As a result, in order to arrive at a viable decision, managers at times must cope with an enormous amount of data relating to competing projects. Consequently, selecting the ‘best’ project from a potentially large number of different projects with varying levels of capability and potential is a complicated and time-consuming task. In summary, at any time a typical organization has multiple projects to be initiated and the challenge organizations face is the lack of a methodology that would help them select and prioritize projects that simultaneously compete for limited organizational resources. This paper presents an example of how Data Envelopment Analysis (DEA) may be used as a tool for selection and prioritization of projects. A review of the last 25 years of research involving applications of DEA methodology is summarized in Table 1. This table is not meant to be a comprehensive review but rather an overview of the different applications, inputs and outputs that have been utilized with DEA.The next section summarizes the basics of DEA and its application in managerial decision-making. This is followed by a section that summarizes a DEA approach for selection and prioritization of projects. Next, a DEA model for project selection decision is developed and solved. Finally, model results are analyzed and interpreted to identify managerial implications of the DEA approach to project selection.II. DATA ENVELOPMENT ANALYSIS (DEA)Data Development Analysis (DEA) is an application of the linear programming technique and was developed by Charnes et al. (1978) to measure the relative efficiencies of options which involve multiple, incommensurate inputs and outputs. These options are referred to as decision-making units (DMUs). DEA has found a variety of applications in several areas and has been used to measure the performance of physician practices, component suppliers, school districts, banks hospitals, robots, courts etc. Several of these applications were summarized in Table 1 under section I. Lall and Teyarachakul (2006), Thanassoulis et al. (1978), Boussofiane et al. (1991) and several other papers addressed the fact that information obtained from DEA assessment can be used to discover which DMUs can be classified as efficient or inefficient, identify possible good operational practices and explore the possibility of setting targets for inefficient units. Banker and Morey (1986) presented the DEA formulation to evaluate the efficiency of DMUs when some of the inputs and outputs are exogenously fixed and beyond the control of the DMUs. Recently, DEA has been integrated with the multiple-objective linear programming (MOLP) as an interactive approach to a resource-allocation problem in organizations with a centralized decision-making environment. Golany (1988) proposed the use of preference information when setting the performance targets in the context of DEA. Sutton and Green (2002) used the DEA notion to evaluate decision choices. They suggested the modified DEA to find weights which show the performance of options and to provide a framework to elicit and use information exogenous to the decision alternatives. The efficiency score of each DMU is determined by the weighted sum of outputs divided by the weighted sum of inputs. Charnes et al. (1978) recognized the difficulty in seeking common weights because each DMU may value inputs and output differently; they proposed to use a set of weights that give the highest possible relative efficiency scores.The fractional form of DEA, which maximize the efficiency h0 of the j0 DMU is defined as follows:[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (Model M1)where[y.sub.rj] = the amount of the [] output from unit j,[u.sub.r] = the weight given to the [] output,[x.sub.ij] = the amount of the [] input to the unit j,[v.sub.i] = the weight given to the [] input, and[epsilon] = a very small positive numberCharnes and Cooper (1962) provide approaches to convert Model M1 into a linear programming model by setting the denominator in the objective function to some arbitrary constant and moving the denominator in the first constraints to the right-hand side of the constraint. For computational convenience, the DEA linear programming model is converted into a dual model as follows:[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (Model M2)where [[lambda].sub.j], [[bar.s].sub.i] [s.sup.+.sub.r] are the dual variables.There are alternatives to measure the efficiency of a DMU. One may use either the input- reducing efficiency or an output-increasing efficiency measure. Both model M1 and M2 measure output-increasing efficiency. In measuring the input-reducing efficiency, the relative efficiency of a DMU (for example DMU j0) is evaluated by finding the best practice DMU’s minimum effort required to produce the same amount of outputs as DMU j0 does. In other words, how much effort it takes for the best practice DMU (reference DMU) to produce as much outputs as DMU j0. We consider the application of DEA to project selection; the choices of DMU become project alternatives. For simplicity, we apply model M1 to select the best project candidate.III. A DEA APPROACH FOR SELECTION AND PRIORITIZATION OF PROJECTSDEA assesses the relative efficiency of DMUs by obtaining the maximum of a ratio of weighted outputs to weighted inputs. The selection criteria for competing projects will be the inputs and outputs in our study. Several selection criteria have been identified in the literature. Examples of these criteria include: Return on Investment, implementation time, clerical time, training time, net benefit, cost, efficiency, alignment with corporate strategy/goals, to name a few. Note that the units of measure of these criteria varies from $ to hours to percentages to subjective ratings. The DEA approach allows for the simultaneous use of data as it comes regardless of how different the units of measure of the output and input criteria under consideration are.IV. DEA RESULTSRelevant results from a DEA application are dependent upon the ratio of the number of input and output variables to the number of Decision Making Units. A rule of thumb for this ratio is given by Banker et al. (1984) as: s + m < n/3, where s is the number of inputs, m is the number of outputs and n is the number of DMUs. For illustration purposes and consistent with this rule of thumb, we will be considering 10 DMUs or projects and 4 project features. Return on investment and alignment with corporate strategy will be assumed to be outputs and implementation time and project cost will be assumed to be inputs. The data set used is included in Table 2. The original data set was obtained from McCain (2011) who applied the prioritization matrix technique to rank three alternative projects. To demonstrate the applicability of DEA to project selection and evaluation, seven additional projects with randomly assigned values of inputs and outputs were added to the original dataset. Alignment with corporate strategy is measured subjectively using a 1-5 score where 5 indicates perfect alignment. Implementation time is given in hours and cost in thousands of dollars.Results from applying the DEA model are reported in Table 3. An examination of Table 3 indicates that projects 5, 6 and 10 exhibit a relative efficiency value of 1, meaning that for their individual return on investment percentage and alignment to corporate strategy score, no better implementation time and cost features could be offered by any of the competing projects under consideration.The other seven projects under consideration exhibit a relative efficiency value of below 1, indicating that at least one other project in the sample offers better ROI and alignment to corporate strategy features for comparable levels (hours and $) of implementation time and cost features. As an illustration consider project 8. The DEA model suggests that project 8 is 42.4% less efficient than its reference set, namely, projects 6 and 10. An examination of the data associated with projects 8 and 6 reveals that a higher alignment score (5,4) and at least as high ROI (10,10) is attained with project 6 than with project 8 even when implementation time and cost features are higher for project 8 (6000, 1700) than for Project 6 (4000, 900). This indicates that one could expect at least as good of a return and better alignment with corporate strategy from project 6 even though it costs less and takes less time to implement than project 8. A consequence of this finding would be that in order for project 8 to be as attractive as project 6, the input variable cost would need to change, i.e. the cost of the project will have to be less and/or the implementation time feature will have to improve. As it can be seen then, the DEA results allow for an easier examination of why some projects are in fact better than others and thus provide an opportunity to determine what it would take for a given project to improve its standing relative to others in the sample. In addition, as indicated previously, the DEA approach allows for the use of various units of measure to be included simultaneously and in 'raw' form.V. CONCLUSIONS, LIMITATIONS AND OPPORTUNITIESIn this paper, a DEA approach is proposed as an alternative procedure to assist decision-makers select the best project from several being considered. An actual data set available in the literature was modified by adding additional projects with corresponding inputs and outputs. This modified data set was used to illustrate how the DEA model works and to compare its features with those of an existing and fairly common procedure (use of informed weights and scores). In the data set used, subjective scores were assigned to the various features offered by the competing projects. Given that the DEA approach allows for the simultaneous consideration of inputs/outputs with different measurement units, a possible area of opportunity would be to replace the scores assigned to various inputs and outputs with actual raw data. For example, the output alignment to strategy could be replaced with another feature that used numerical data and not a rating. Sensitivity analysis may be performed on the results to determine what specific changes must occur in the input and output values of a project showing a relative efficiency of less than 1 in order for the package to attain a relative efficiency of 1.ReferencesAhuja, G. and S. Majumdar (1998), "An Assessment of the Performance of Indian State Owned Enterprises", Journal of Productivity Analysis, Vol. 9, No. 2, 113-132.Al-Shammari, M. (1999), "Optimization Modeling for Estimating and Enhancing Relative Efficiency with Application to Industrial Companies", European Journal of Operational Research, Vol. 115, No. 3,488-496.Athanassopoulos, A. and J. Ballantine (1995), "Ratio and Frontier Analysis for Assessing Corporate Performance: Evidence From the Grocery Industry in the UK", Journal of Operational Research Society, Vol. 46, No.4, 427-440.Athanassopoulos, A., N. Lambroukos, and L. Seiford (1999), "Data Envelopment Scenario Analysis for Setting Targets to Electricity Generating Plants", European Journal of Operational Research, Vol. 115, No. 3, 413-428.Baker, R. and S. Talluri (1997), "A Closer Look at the Use of Data Envelopment Analysis for Technology Selection", Computers and Industrial Engineering, Vol. 32, No. 1, 101-108.Banker, R. D. and R. C. Morey (1986), "Efficiency Analysis for Exogenously Fixed Inputs and Outputs", Operations Research, Vol. 34, No. 4, 513-521.Banker, R. D., A. C. Charnes and W. W. Cooper (1984), "Some Models for Estimating Technical and Scale Inefficiencies in Data Analysis", Management Science, Vol. 39, 1078-1092.Boussofiane, A., R. G., Dyson and Thanassoulis (1991), "Applied Data Envelopment Analysis", European Journal of Operational Research, Vol. 2, 429-444.Bowlin, W (1987), "Evaluating the Efficiency of US Air Force Real-Property Maintenance Activities", Journal of Operational Research Society, Vol. 38, No. 2, 127-135.Burgess, J. and P. Wilson (1993), "Technical Efficiency in Veterans Administration Hospitals", In The Measurement of Productive Efficiency: Techniques and Applications, H. Fried, C. Lovell, and S. Schmidt, eds, Oxford University Press, Inc., 335-351.Chandra, P., W. Cooper., S. Li. and A. Rahman (1998), "Using DEA to Evaluate 29 Canadian Textile Companies--Considering Returns to Scale", Journal of Production Economics, Vol. 54, No. 2, 129-141.Charnes, A., W. Cooper and S. Li (1988), "Using Data Envelopment Analysis to Evaluate Efficiency in the Economic Performance of Chinese Cities", Socio-Economic Planning Sciences, Vol. 23, No. 6, 325-344.Charnes, A., W. W. Cooper and E. Rhodes (1978), "Measuring the Efficiency of the Decision Making Units", European Journal of Operational Research, Vol. 2, 429-444.Charnes, A. and W.W. Cooper (1962), "Programming With Linear Fractional Functionals", Naval Research Logistics, Vol. 9, 181-185.Cheng, E., Y. Chaing, and B. Tang (2007), "Alternative Approach to Credit Scoring by DEA: Evaluating Borrowers with Respect to PFI Projects", Building and Environment, Vol. 42, No. 4, 1752-1760.Chu, S. and G. Lim (1998), "Share Performance and Profit Efficiency of Banks in an Oligopolistic Market: Evidence from Singapore", Journal of Multinational Financial Management, Vol. 8, No. 2-3, 155-168.El-Maghary, S. and R. Lahdelma (1995), "Data Envelopment Analysis--Visualizing the Results", European Journal of Operational Research, Vol. 83, No. 3, 700-710.El-Mashaleh, M., R. Minchin, and W. O'Brien (2007), "Management of Construction Firm Performance Using Benchmarking" Journal of Management Engineering, Vol. 23, No. 1, 10-17.Farrell, M. (1957), "The Measurement of Productive Efficiency", Journal of the Royal Statistical Society (A, general), Vol. 120, part 3, 253-281.Golany, B. (1988), "An Interactive MOLP Procedure for the Extension of DEA to Effectiveness Analysis", The Journal of the Operational Research Society, Vol. 39 No. 8.Goto, M. and M. Tsutsui (1998), "Comparison of Productive and Cost Efficiencies Among Japanese and US Electric Utilities", Omega-International Journal of Management Science, Vol. 26, No. 2, 177-194.Grosskopf, S. and V. Valdmanis (1987), "Measuring Hospital Performance: a Nonparametric Approach", Journal of Health Economics, Vol. 6, 89-107.Hjalmarsson, L. and J. Odeck (1996), "Efficiency of Trucks in Road Construction and Maintenance: an Evaluation With Data Envelopment Analysis", Computers and Operations Research, Vol. 23, No. 4, 393-404.Kirjavainen, T. and H. Loikkanen (1998), "Efficiency Differences of Finnish Senior Secondary Schools: an Application of DEA and Analysis", Economics of Education Review, Vol. 17, No. 4, 377-394.Kozmetsky, G. (1998), "Comparative Performance of Global Semiconductor Companies," Omega-International Journal of Management Science, Vol. 26, No. 2, 153-175.Lall, V., and S. Teyarachakul (2006), "Enterprise Resource Planning (ERP) Selection: A Data Envelopment Analysis (DEA) Approach", Journal of Computer Information Systems, Vol. 47, No. 1, 123-127.Lee, H. and A. Somwaru (1993), "Share Tenancy and Efficiency in U.S. Agriculture", In The Measurement of Productive Efficiency: Techniques and Applications, H. Fried, C. Lovell, and S. Schmidt, eds., Oxford University Press, Inc., 288-299.Lovell, P. and J. Turner (1995), "Measuring Macroeconomic Performance in the OECD a Comparison of European and non-European Countries", European Journal of Operational Research, Vol. 87, No. 3, 507-518.McCabe, B., V. Tran and J. Ramani (2005), "Construction Prequalification Using Data Envelopment Analysis", Canadian Journal of Civil Engineering, Vol. 32, No. 1, 183-193.McCain, C. (2011), "Use a Selection Matrix to Pick Projects, Evaluate Solutions", Quality Progress, 72.McCarty, T. and S. Yaisawarng (1993), 'Technical Efficiency in New Jersey School Districts", In The measurement of Productive Efficiency: Techniques and Applications, H. Fried, C. Lovell, and S. Schmidt, eds., Oxford University Press, New York, 271-287.Odeck, J. (1996), "Evaluating Efficiency of Rock Blasting Using Data Envelopment Analysis", Journal of Transportation Engineering, Vol. 122, No. 1, 41-49.Ott, R. and M. Longnecker (2001), Statistical Methods and Data Analysis, Pacific Grove, CA.Peck, M., C. Scheraga and R. Boisjoly (1998), "Assessing the Relative Efficiency of Aircraft Maintenance Technologies: an Application of Data Envelopment Analysis", Transportation Research Part A-Policy and Practice, Vol. 32, No. 4, 261-269.Ray, S. and H. Kim (1995), "Cost Efficiency in the U. S. Steel Industry: a Nonparametric Analysis Using Data Envelopment Analysis", European Journal of Operational Research, Vol. 80, No. 3, 654-671.Rouse, P., M. Putterill and D. Ryan (1997), "Towards a General Managerial Framework for Performance Measurement: A Comprehensive Highway Maintenance Application", Journal of Productivity Analysis, Vol. 8, No. 2, 127-149.Russel, T., P. Dharmapala, L. Rothenberg and R. Thrall (1996), "DEA/AR Efficiency and Profitability of 14 Major Oil Companies in the U.S. Exploration and Production", Computers and Operation Research, Vol. 23, No. 4, 357-373.Sutton, P. P. and R. H. Green (2002), "A Data Envelopment Approach to Decision Analysis", The Journal of the Operational Research Society, Vol. 53, 1215-1224.Thanassoulis, E. (1995), "Assessing Police Forces in England and Wales Using Data Envelopment Analysis", European Journal of Operational Research, Vol. 87, No. 3, 641-657.Thore, S., F. Phillips, T. Ruefli and P. Yue (1996), "DEA and The Management of The Product Cycle: the US Computer Industry, Computers and Operations Research, Vol. 23, No. 4, 341-356.Vinter, G., S. Roznes and S. Spraggett (2006), "Using Data Envelope Analysis to Compare Project Efficiency in a Multi-Project Environment", International Journal of Project Management, Vol. 24, No. 4, 323-329.VINOD LALL *, RUTH LUMB * AND ABEL MORENO *** Minnesota State University-Moorhead, 1104 7th Avenue S, Moorhead, MN 56563, E-mails: , ** School of Business, Metropolitan State College of Denver, Campus Box 45, P. O. Box 173362, Denver, CO, 80217, E-mail: INTRODUCTIONProject selection is to assign the limited resources to the most needed or valuable project so as to maximize the overall profit of an organization. This is especially true for the public projects, because they are capital intensive. In addition, many factors and interest groups can influence the selection of the public projects; thus, a systematic procedure should be developed to objectively prioritize the project proposals.Suppose that the net discounted cost and revenue of each project can be evaluated in advance, then the problem can be formulated as finding an optimal set of projects that yield the maximum profit within the budget constraint. A 0/1 linear programming known as the knapsack problem can be used to describe the selection of the projects. Nevertheless, the 0/1-knapsack problem is NP-complete [11] or "hard" combinatorial optimization for which, to date, no technically sound algorithms are available [2]. Realizing the difficulty of the problems, several researchers have proposed different heuristic approaches for solving the problems [3-5, 8]. Consider the project selection formulation in Problem (1), if we try all possible combinations of the item selections to decide the optimal solution, we may need O([2.sup.n]) computational time in the worst case. Because obtaining the optimal solution is so expensive and intractable, developing a heuristic algorithm that provides a near-optimal solution and takes non-exponential time becomes necessary. For an overview of several knapsack problems and their applications, see Matello and Toth [6].Several algorithms to solve the knapsack problem apply Lagrangean-based reduction schemes to fix on or off a portion of the variables [1, 5, 7, 8]. The procedure starts off by solving the linear programming relaxation and follows by performing a sequence of pivoting phases to improve the 0-1 solution. However, these heuristic algorithms generally work well only on the problems with easy data instances [6]. It is then interesting to analyze why some of the problems are so hard as to deteriorate the effectiveness of the algorithms. The variation of the data set and the size of the budget might be the two most sensitive parameters affecting the performance of the heuristic algorithms. This is because the decision variables of the binary knapsack problem are "all-or-nothing" (zero-one) type discrete variables, and the budget never be exhausted in reaching the optimal solution. As a result, the complementary slackness characteristic is nonexistent in the binary knapsack problem. Thus, it is seemingly unreasonable and unsuitable to solve the knapsack problem by using the "continues" relaxation techniques.Before searching the optimal solution set, if the solution space can be tightened to a certain feasible range, the computing time can be significantly reduced. Fortunately, two major improvements, which have been ignored by most researchers, can be made from the data set. First, using the available budget and the given cost of each project, we can constrain the feasible range (CR), alternatively, the number of projects to be selected, instead of conducting all possible searches on the range of {0, n}. Second, after the feasible range is determined, we can reduce the candidate set (RCS) through a linear search algorithm [10] or the variable dominant matrix [11]. Nevertheless, both algorithms [10, 11] rely on the tightness of the number of projects to determine which project should be retained or discarded in the reduced candidate set. When the lower and upper bounds of the feasible range are widely spread, such as when the costs of the projects vary from zero to the total budget (the worst case), then the optimal solution cannot be easily obtained via the techniques of searching the feasible range and the reduced candidate set. This will be shown later in Examples 5 and 6.Moreover, consider problem (1) again, if the decision variable [x.sub.k] is selected ([x.sub.k] = 1), then it will cost [c.sub.k] from the budget and add the performance contribution [p.sub.k] to the objective function. Obviously, it would be more meaningful to use the "net profit" ([p.sub.k] - [c.sub.k]) as the decision criterion, rather than the revenue-to-cost ratio ([p.sub.k]/[c.sub.k]). The purpose of this paper is to revise the CR - RCS algorithm by replacing the profit [p.sub.k] by the net profit [p.sub.k] - [c.sub.k] as the performance contribution to the objective function, and then use the dominant matrix to reduce the candidate set. The proposed algorithm is more robust than the techniques used in [10, 11].The revised CR - RCS algorithm is presented next, followed by the comparisons of the results obtained from [10, 11] and the proposed algorithm.THE NEW HEURISTIC ALGORITHMThe project selection problem, when formulated using the binary knapsack algorithm, would be a simple discrete programming model. Given the net discounted revenue [p.sub.k] and cost [c.sub.k] of each project, k = 1, n, then the project selection can be described as the following 0/1-knapsack problem:Maximize [summation of] [x.sub.k] [p.sub.k] where k = 1 to nPROBLEM (1)Subject to:[summation of] [x.sub.k][c.sub.k] [less than or equal to] B where k = 1 to n[x.sub.k] = 0 or 1where k is the project number, [p.sub.k] and [c.sub.k] indicate the net discounted revenue and cost of each project, and B is the budget constraint.The 0/1-knapsack problem takes O([2.sup.n]) computational time to decide the optimal solution in the worst case. Many researchers investigated heuristic algorithms that yield near-optimal solutions but consume non-exponential time. For example, several researchers have explored using multiple criteria to produce a candidate set, supplemented by a technique to further squeeze the feasible range [10, 11].Various criteria have been used to prioritize the candidates. Generally, the criterion that can precisely relate the cost and revenue is believed to be able to produce a better heuristic solution. One commonly used criterion based on the concepts of linear programming is the ratio between revenue and cost, i.e. [r.sub.k] = [p.sub.k]/[c.sub.k]. However, even divisibility is allowed, sorting by [r.sub.k] does not give optimal solution in the 0/1-knapsack problem [11]. This can be easily realized from the fact that two [r.sub.k] of the same value will be viewed as two equally acceptable candidates, while the difference between the profit resulted from each project can be significant. In addition, 0/1-knapsack problems are to make decisions of selecting either all or nothing. Using [r.sub.k] to measure the fraction of the contribution does not capture the intrinsic nature of the problems. Another linear search algorithm based on the nondecreasing order of [c.sub.k] or the nonincreasing order of [p.sub.k] also cannot give the optimal solution. Exceptional examples can always be constructed. Instead of the one-way linear search, observing two criteria jointly, such as [r.sub.k] and [c.sub.k], [r.sub.k] and [p.sub.k], or [p.sub.k] and [c.sub.k], one can conduct the two-way linear search. Unfortunately, the optimal solution is still not guaranteed. Practically, from the perspective of maximizing the surplus, the maximized net profit, which is the cost subtracted by the revenue, i.e. ([p.sub.k] - [c.sub.k]), may frequently be the decision makers' actual goal. Thus, it will be used as the criterion in this study to improve the heuristic solution and to minimize the computational efforts.To reduce the problem, the candidate set can be divided into three parts: selected set (SS), excluded set (ES), and remaining candidate set (RCS). The n - SS + ES + RCS, where SS and ES contains projects that will be certainly selected and excluded respectively, and RCS is composed of the remaining projects that cannot be surely decided. Instead of searching the complete enumeration, the method that maximizes the selected set and excluded set can significantly reduce the computational time. Thus, the feasible range {L, U} indicating the number of projects that can be possibly selected must be first determined, where L is the expected minimum number of projects decided by the nonincreasing order of [c.sub.k]. U is the expected maximum number of projects obtained from the set of ([p.sub.k] - [c.sub.k]) sorted by the nondecreasing order. Using the feasible range and the dominant matrix, the selected set and excluded set can be easily determined. The problem is therefore dramatically reduced. Summarily, the following algorithm can be derived:ALGORITHM1. Determine the value of ([p.sub.k] - [c.sub.k]) of each project.2. Sort ([p.sub.k] - [c.sub.k]) by the nonincreasing order to obtain L when[summation of] [c.sub.k] [less than or equal to] B. where k = 1 to L3. Sort [c.sub.k] by nondecreasing order to obtain U when[summation of] [c.sub.k] [less than or equal to] B where k = 1 to U.4. Construct the dominant matrix in such a way that project k is said to dominate project j if and only if ([p.sub.k] - [c.sub.k]) [greater than] ([p.sub.j] - [c.sub.j]) and [c.sub.k] [less than] [c.sub.j]. Let WIN(k) and LOSS(k) denote the number of projects that project k dominates and has been dominated respectively.5. Obtain the selected set and excluded set using results of steps 2, 3, and 4. Project k is in the selected set if WIN(k) [greater than or equal to] (n - L), and in the excluded set if LOSS(k) [greater than or equal to] U.6. Construct another dominant matrix to compare the remaining candidate set. The optimal solution is then reduced to the enumeration of C([absolute value of RCS], m - [absolute value of SS]), where [absolute value of [center dot]] is the number of projects in [center dot].Unlike previous methods, the proposed algorithm produces a small feasible range {L, U} and large selected set and excluded set. This indicates that a tremendous amount of searching time can be saved. Besides, the algorithm can also solve the hard problems with significant revenue and cost variation, while those problems are frequently unsolvable by other methods. The information in the next section will show that the proposed method is a better heuristic approach.PERFORMANCE OF THE ALGORITHMTo verify the performance of the algorithm, six examples adopted from [7, 11] are tested. The following materials demonstrate the detailed and complete discussions. Comparisons of the results from other methods are also included.EXAMPLE 1: n - 15, B - 1500 [9]Example 1 deals with 15 projects within 1500 budget constraint. The cost and revenue are listed in TABLE 1. The feasible range is between {1,2}; in other words, only one or


Do you need help working on this assignment? We will write a custom essay on this or any other topic specifically for you.

Back To Top