Abstract
A multimode resource-constrained project scheduling problem (MRCPSP) may have multifeasible solutions, due to its nature of targeting multiobjectives. Given the NP-hard MRCPSP and intricate multiobjective algorithms, finding the optimized result among those solutions seems impossible. This paper adopts data envelopment analysis (DEA) to evaluate a series of solutions of an MRCPSP and to find an appropriate choice in an objective way. Our approach is applied to a typical MRCPSP in practice, and the results validate that DEA is an effective and objective method for MRCPSP solution selection.
1. Introduction
Resource-constrained project scheduling problem (RCPSP) has been intensively studied since the 1960s and a standard model for RCPSP has been widely accepted to fulfill scheduling tasks. Despite its preeminence, standard RCPSP can hardly cover all practical situations and many effective extensions have been proposed. Multimode RCPSP (MRCPSP) is one of them. It was first developed by Elmaghraby [1], and it allows multialternative modes that an activity can choose, providing different combinations of resources and durations.
Most of the previous studies focused on solutions to MRCPSP. As Brucker [2] summarized, those algorithms fell into three categories: exact algorithms, heuristics algorithms, and metaheuristic algorithms. Kolisch and Drexl [3], however, proved that whether MRCPSP has a feasible solution is an NP-hard problem when two or more renewable resources and infinite unrenewable ones coexist.
Schnell and Hartl [4] proposed new exact approaches to the MRCPSP with generalized precedence relations. They implemented the optimization framework SCIP which contained two constraint handlers “cumulativemm” and “gprecedencemm” and formulated SCIP models for the MRCPSP. Their solution obtained the outperform results especially on 50 activities when imposing time limits of 27s. Some new metaheuristics have also emerged recently including hybridization of genetic algorithm and fully informed particle swarm [5]; a column generation based distributed scheduling algorithm [6]; a hybrid optimization method which consists of a novel heuristic and unique genetic optimization algorithm for large-scale projects [7]; and an effective mirror-based genetic algorithm [8]. In terms of MRCPSP model extension, some scholars have considered renewable resource vacation and activity splitting [9]. Nemati-Lafmejani et al. [10] proposed an integrated biobjective optimization model to deal with MRCPSP and contractor selection (CS) problem, simultaneously. Hill et al. [11] proposed a reformulation of the waterway ship scheduling problem as a variant of the MRCPSP, which incorporates time-dependent resource capacities besides the earliest and latest start times for the tasks. This problem was solved through integer programming, using a compact mathematical formulation.
Typically, project scheduling achieves ultimate goals in three perspectives: duration, cost, and quality. These multiobjectives make the already complex MRCPSP even harder [12]. Researchers have sought different ways to solve it. Some scholars considered two targets: cost and duration [13]; some tried to maximize net present value and minimize duration [14]; others took all the three (duration, cost, and quality) as objectives to optimize [15].
In practice, duration is usually the most predominant goal of a project, and the priorities of resource, cost, and quality vary with different project executors. Multisolutions to an MRCPSP with different optimized goals may be available and how to evaluate each of them in a subjective way becomes a problem.
Here is a typical scenario. A project manager proposed a number of solutions to a project scheduling, and all their durations met the company’s strategic requirements. Other managers, however, imposed their respective emphases and filed different proposals. For example, CFO focused on capital investment, CHO considered resources, and CMO predicted the quality that would impact the company’s profile. Since all of the solutions were reasonable and feasible, the dilemma that CEO faced then was to evaluate them in an objective and convincible way and make decisions thereafter.
As a matter of fact, the project selection is critical and intricate due to availability of numerous projects, as well as existence of various qualitative and quantitative criteria. The decision-making can involve the enterprise in a long-term commitment. While various methods of project selection have been proposed in the literature, Naldi et al. [16] focus on the profit-fairness trade-off, they adopt a knapsack-type integer linear programming formulation to optimize both quality indicators of budget allocation, employing a fairly wide selection of fairness measures. Liu et al. [17] proposed a novel multiattribute decision-making method based on spherical fuzzy sets for selecting Yunnan Baiyao’s R&D project of toothpastes. However, although the methods mentioned above are effective, they are all targeted at specific types of project selection, which are also complicated and require a lot of information processing in advance.
Furthermore, the most notable among these methods is data envelopment analysis (DEA). DEA is a nonparametric method to measure productive efficiency of decision-making units (DMUs) that involve multi-inputs and multioutputs. This method was first proposed by Charnes et al. [18] in 1978 but rooted in the studies by Debreu [19], Koopmans [20], and Farrell [21] on the measurement of productive efficiency. Thanks to its expertise at performance evaluation, this method has taken great leaps both in theory and in practice. Researchers have applied DEA models to address transportation systems, health care, resource allocation, energy and environmental economics, and regional and national sustainability issues as well as those related to supply chain. Recent overviews of DEA can be found in Mahmoudi et al. [22], Kohl et al. [23], Yang et al. [24], Mardani et al. [25], Zhou et al. [26], Soheilirad et al. [27], Cook and Seiford [28], and Liu et al. [29].
Hitherto, DEA has been applied to solution selections for construction projects [30], and Research and Development (R&D) proposals [31], information project [32, 33], and Six Sigma project [34]. Although, it objectively selected the most efficient projects even under the influences of the executor’s subjective instincts and opinions, there has been little discussion on how to evaluate and select solutions from MRCPSP. There are two major differences. Firstly, the project selection problem deals with opting a set of best feasible proposals from a large pool of projects with making the best use of available resources, while the MRCPSP solution selection is to evaluate different solutions from the same project. Secondly, each project uses different resources and produces various outputs while the latter utilizes the same set of available but limited resources and focuses on the time, cost, quality involved in project management. Our attempt of applying DEA to MRCPSP is to evaluate advantages and disadvantages between multifeasible solutions, providing a solid reference to the decision-maker.
This paper is to investigate the selection of MRCPSP solutions. We adopt data envelopment analysis (DEA) to evaluate available solutions. The contribution of this paper is mainly reflected in two aspects. One is to deepen the application research of MRCPSP and discuss the solution selection from the perspective of relative efficiency. Second, it extends the application field of DEA and the proposed DEA approach could be applied to MRCPSP. Moreover, it provides a new perspective and useful tool for project managers to objectively evaluate a set of similar solutions in an MRCPSP.
The remainder of the paper is organized as follows. Section 2 presents a description of MRCPSP using a virtual case and the solutions of MRCPSP are presented. Section 3 introduces the solution methodology, DEA, designed to solve the problem and computational results are presented and discussed. Finally, conclusions are shown in Section 4.
2. Problem Description and Its Solutions
Suppose there is a project composed of 20 activities, including two dummy ones: the “beginning” and the “termination.” Its activity-on-node (AON) network is depicted in Figure 1. Each activity could run in one of the two modes, the normal and the speedy; the two modes cost differently and lead to different qualities. All the activities could allocate three renewable resources, and their respective totals are 12, 13, and 12. The parameters of the project are listed in Table 1.
This is a typical MRCPSP. A project consists of J activities. And two dummy activities are added: the beginning activity 0 and the termination activity J + 1, both of which need zero recourse and zero processing time. Thus, the activities can be defined as a set . Each activity holds M alternative modes. The renewable resources are encapsulated into a set , and the number of resources of type that can be used in each period is described by ; similarly, there is a set of consumable resources and it contains resources of type . , is the set of direct predecessors of activity j, which means activity j cannot begin until every activity is completed. If an activity j processes in mode m, , defines its processing time, the quantity of the renewable resource of type , and the quantity of consumable resource of type .
The ultimate goal is to minimize the total duration of the project, called makespan. Thus, this problem can be described as follows:subject towhere equation (1) defines the objective function to obtain the minimum processing time; the constraint in equation (2) defines that one activity only processes once in one mode; equation (3) qualifies the timing constraints between activities; equation (4) keeps the number of usable renewable resources in each period less than the total number of the renewable resources; and equation (5) ensures that all the used unrenewable resources cannot exceed the total nonrenewable resources. in these constraints represent the earliest and the latest time windows of an activity, respectively. Table 2lists all the parameters used in the model.
Many scholars proposed novel solutions to MRCPSP, like Van Peteghem and Vanhoucke [35], Wang and Fang [36], Ballestin et al. [37], Liu et al. [38], and Gutjahr [13]. The author of this paper adopted a genetic algorithm, developed by Liu et al., to achieve the ultimate goals. The algorithm was coded by JAVA and run in a PC with double CPUs (Pentium 2.7 GHZ) and a 2.0 GB RAM. And 32 options were selected from the results that provided nondominated solutions within 1000 days, as listed in Table 3.
Figure 2 demonstrates that the increase of the project duration can elevate the quality, but the marginal utility of the former is diminishing. Project cost, as exhibited in Figure 3, is nonlinearly related to the duration: a speedy working mode can dramatically increase the cost, but prolonging duration can hardly reduce the cost reversely. Figure 4 further explains the consequences of Figure 3: the growing cost leads to a lower quality, instead of a higher one, due to the shortened duration.
Those solutions put processing time first without any preference suggestions and leave decision-makers struggling to choose the most appropriate ones. Therefore, we adopted data envelopment analysis (DEA) to further evaluate those solutions.
3. Results of DEA Models and Discussions
3.1. Results
In our DEA model, processing time is a reverse output. The smaller it is, the better. So for the sake of simplicity, we regarded the processing time, together with the cost, as the inputs, while the quality as the output. Given the inability of traditional DEA models, like CCR and BCC, to rank efficient units and thus to choose the best one, we utilized superefficiency DEA models to complete those works. Table 4 compares four efficiencies of the 32 options, including CCR, BCC, CRS superefficiency, and VRS superefficiency.
3.2. Discussions
Table 4 indicates that the CCR model results in 13 efficient units; the highest of the 32 efficiencies is 1 and the lowest is 0.8972. However, the BCC model obtains 22 efficient units; the highest is 1 and the lowest is 0.9908. These results imply that BCC holds a weaker ability than CCR of determining efficiency, although their minimum efficiencies are close. Among the results of the superefficiency CRS model, the highest is 1.0015 in decision-making unit (DMU) 28, and the lowest is similar to that of CCR, while for VRS model, the highest is 1.0057 in DMU 7, and the lowest equals that of BCC. CRS presents both lower maximum and lower minimum than VRS.
Notably, the maximums and the minimums of the four models are pretty close, which implies that finding the best from the 32 options is a tough task. But through comparing the four columns, one can notice that when a result of a traditional model is inefficient, it equals that of the corresponding superefficient model; otherwise, it is less than that of the corresponding superefficient model. This indicates that superefficient models can be used to further rank efficient units and find the best one. In addition, it should be noted that DMU 28 has no solution in the VRS superefficiency model, which is because we adopt an input-oriented super efficiency model, and the output value of DMU 28 (i.e., engineering quality value) is the largest among all DMU. Traditional models can help decision-makers find the worst inefficient DMU but tend to provide multiefficient DMUs with the same efficiency, due to the upper limit. Superefficiency models remove this limit and present efficient DMUs with various values; thus the best one can be easily spotted. In our study, CRS chose DMU 28 as the best while VRS chose DMU 7.
Superefficiency models can find the best among solutions to an MRCPSP in an effective and speedy way. Applying superefficiency DEA models to MRCPSP is validated to be a convincible and better approach.
MRCPSP occurs in many real-world applications, such as construction engineering, subway line selection, medical diagnosis, supplier location, cargo transportation, and software development. A very common difficulty of many real MRCPSPs is how to evaluate each of the solutions in a subjective way. The DEA approach proposed in this paper should be a good choice.
4. Conclusions
As project scheduling usually targets multigoals, solutions to multimode resource-constrained project scheduling problems can be multiple. How to select an appropriate one according to objective principles has become a problem in practice. We adopt data envelopment analysis to a typical MRCPSP and effectively propose a series of objective benchmarks that can help to evaluate those solutions to the MRCPSP and determine an appropriate one. Our approach provides an innovative perspective and an effective approach for decision-makers when selecting a proper solution to an MRCPSP.
Data Availability
The data used to support the findings of this study are included within the article.
Conflicts of Interest
The author has no conflicts of interest to declare.
Acknowledgments
This work was supported by the Xuzhou Medical University excellent talents scientific research start-up fund (53591420); initial funding for postdoctoral research of XZMU (53470321); and the Priority Academic Program Development of Jiangsu Higher Education Institutions (PAPD).