A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Multi-Project Scheduling <s> Application of heuristic solution procedures to the practical problem of project scheduling has previously been studied by numerous researchers. However, there is little consensus about their findings, and the practicing manager is currently at a loss as to which scheduling rule to use. Furthermore, since no categorization process was developed, it is assumed that once a rule is selected it must be used throughout the whole project. This research breaks away from this tradition by providing a categorization process based on two powerful project summary measures. The first measure identifies the location of the peak of total resource requirements and the second measure identifies the rate of utilization of each resource type. The performance of the rules are classified according to values of these two measures, and it is shown that a rule introduced by this research performs significantly better on most categories of projects. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Multi-Project Scheduling <s> Abstract The multiproject scheduling problem is investigated under the assumption that delays corresponding to different projects carry different penalties. Five penalty functions are introduced that simulate typical business behavior. These are: 1) assigning the highest penalty to the project requiring the greatest amount of resources; 2) assigning the highest priority to the longest project; 3) assigning the highest priority to the project requiring the least amount of resources; 4) assigning the highest priority to the shortest project; and 5) random assignment. Justification for each case is provided. Two powerful project summary measures were used to generate the test problems. The first measure, average resource load factor (ARLF), identifies whether the location of the peak requirement of all (i.e., combined) resources is in the first or second half of the project's critical path. If each resource is expressed in terms of dollars, then ARLF identifies the location of the peak cash requirement. Since in practice the choice of the scheduling strategy is influenced by the location of the peak cash requirement, performance of the scheduling strategies is analyzed with respect to values of this measure. The second measure, average utilization factor (AUF), calculates the ratio of resource requirements to availabilities. It is shown that problems tested must have different AUF values in order to be classified different for purposes of experimental design. Thus a factorial model of the form, y = Strategy + Penalty + ARLF + AUF + ϵ was used to generate 385 problems, each requiring 2 to 4 resources, containing 3 to 5 projects and 34 to 63 activities. The computer program used in the study is based on a parallel method of scheduling in which priorities of the activities are determined when the activity is considered for scheduling. Ten scheduling strategies are tested. Some important ones are: 1) to schedule the shortest activity first; 2) to schedule the activity with minimum slack first; 3) to schedule the activity with maximum work content first (i.e., from the project with highest work content); 4) to schedule the shortest activity from the shortest project first; and 5) to schedule the activity with maximum penalty first. Shortest activity first and minimum slack first are popular strategies introduced by other researchers. Using number of times ranked first as our criterion, scheduling the activity with maximum penalty first provides the best results followed by the strategy of scheduling the activity with maximum work content. But when these results are analyzed with respect to existence of a very expensive project (i.e., dominance) in the problem, performance of the maximum penalty strategy improves. When the overall results are analyzed with respect to values of ARLF, a different picture emerges. Then the strategy of scheduling the activity with the highest penalty first provides the best results if the peak requirement is early. When the peak requirement is toward the middle of a project's unconstrained critical path, scheduling the activity with the highest work content provides the best results. When the peak requirement is late in a project's life, scheduling the shortest activity from the shortest project is the best strategy to adopt. These findings were tested for statistical significance by using nonparametric testing procedures and were found to be significant. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Multi-Project Scheduling <s> Abstract This paper addresses the problem of scheduling multiple resource-constrained projects with the objective of minimizing weighted tardiness costs. Extending our earlier heuristic scheduling work for production shops, we develop an efficient and effective means of generating low cost schedules for multiple projects requiring multiple resources. A ‘cost-benefit’ scheduling policy with resource pricing is developed which balances the marginal cost of delaying the start of an eligible activity with the marginal benefit of such a delay. A central part of this policy is the heuristic estimation of implicit resource prices, which form the basis for calculating marginal delay costs. The resulting policies are tested against a number of dispatch scheduling rules taken from the project scheduling literature, and against several new scheduling rules, with encouraging results for both the weighted tardiness problem and for the special case of weighted project delay. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Multi-Project Scheduling <s> Abstract This paper describes the application of 0–1 goal programming (GP) in multi-project resource-constrained scheduling for the maintenance of mineral-processing equipment at a copper mine in China. This involves four projects, 40 jobs and nine types of resources. We first develop a generalized 0–1 GP model. Because of the limited computing capacity at the mine, an effective two-phase hybrid solution approach is then proposed. In Phase I, under resource constraints, a feasible schedule is obtained by a heuristic. Based on this feasible schedule and a model-simplification procedure, many decision variables in the generalized model are eliminated and redundant constraints are removed. (Although this procedure is particularly designed for this mine, we also discuss its extension to general problems.) In Phase II, the streamlined model is solved by implicit enumeration. This approach eliminates 90% of the variables and 96% of the constraints in the problem we studied. We are thus able to solve a multi-project scheduling problem of medium size on a PC. In comparison with the heuristic method that the mine was using, our hybrid approach reduced project duration by 13%, total project cost by 30%, cost for the critical project by 15%, and overall workload by 59%. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Multi-Project Scheduling <s> Abstract Many works published in the area of project management make reference to the scheduling of single projects and time objectives like minimising project duration. Nevertheless, frequently companies manage various projects which share a pool of constrained resources, taking into account other objectives in addition to time. In order to add flexibility in using project scheduling tools, we have developed a multicriteria heuristic that improves lexicographicly two criteria: one time type – mean project delay or multiproject duration increase – and one no time type – project splitting, in-process inventory, resource levelling or idle resources – that can be chosen by the user. The multicriteria heuristic algorithm consists of several algorithms based on the improvement of multiproject feasible schedules. Through an extensive computational study, we have shown that this method improves the feasible multiproject schedule obtained from heuristic methods based on the priority rules coded Maximum Total Work Content (MAXTWK) and Minimum Latest Finish Time (MINLFT) as well as project management software – Microsoft Project, CA-SuperProject, Time Line and Project Scheduler. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Multi-Project Scheduling <s> The main purposes of this study are to incorporate both the project delay penalty and early completion bonus into the objective function of the resource-constrained multi-project scheduling problem with discounted cash flows (RCMPSP-DCF) and to develop an efficient heuristic search scheduling rule. The effectiveness of the proposed heuristic rule is evaluated by comparing it with the optimal solution obtained by the optimal model for 42 small-scale problems. The result indicates that the solution obtained using the proposed heuristic rule is very close to the optimal solution, and that the proposed heuristic rule provides significant savings in computation time. Moreover, the proposed heuristic rule is also compared with four existing heuristic rules based on an experiment involving the single-project and multi-project scheduling problems. The results indicate that the proposed heuristic rule is superior to the four existing rules under the performance criteria of the average total project net present value and the average total project delay. In addition, the number of times that the proposed heuristic rule can obtain the best solution is also far more than that of any other rule considered in this paper under the two aforementioned performance criteria. Furthermore, this study has found that the performance of a heuristic scheduling rule is significantly affected by the number of projects. A rule that can lower the total project delay to the minimum is also able to maxi5 mize the total project net present value. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Multi-Project Scheduling <s> A restart evolution strategy (RES) for the resource-constrained project scheduling problem (RCPSP), as well as its integration in a multi-agent system (MAS) for solving the decentralized resource-constrained multi-project scheduling problem (DRCMPSP) will be presented. To evaluate the developed approach, problem instances of the RCPSP taken from the literature with up to 300 activities are used, as well as 80 generated instances of the DRCMPSP, with up to 20 projects and with up to 120 activities each. For 73 instances of the RCPSP, the RES found better solutions than the best ones found so far. In addition, the MAS is suitable for solving large multi-project instances decentrally. The results for the DRCMPSP instances show that the presented decentralized MAS is competitive with a central solution approach. <s> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Multi-Project Scheduling <s> Managers of multiple projects with overly constrained resources face difficult decisions in how to allocate resources to minimize the average delay per project or the time to complete the whole set of projects. We address the static resource-constrained multi-project scheduling problem (RCMPSP) with two lateness objectives, project lateness and portfolio lateness. In this context, past research has reported conflicting results on the performance of activity priority rule heuristics and does not provide managers with clear guidance on which rule to use in various situations. Using recently improved measures for RCMPSP characteristics, we conducted a comprehensive analysis of 20 priority rules on 12,320 test problems generated to the specifications of project-, activity-, and resource-related characteristics--including network complexity and resource distribution and contention. We found several situations in which widely advocated priority rules perform poorly. We also confirmed that portfolio managers and project managers will prefer different priority rules depending on their local or global objectives. We summarize our results in two decision tables, the practical use of which requires managers to do only a rough, qualitative characterization of their projects in terms of complexity, degree of resource contention, and resource distribution. <s> BIB008
Several different objectives for scheduling multiple projects have been discussed. In many multiproject problems, each project is associated with a due date, and the tardiness appears to be among the most widely used performance measures for multi-project scheduling. Chen BIB004 employs the minimization of weighted tardiness as well as the minimization of costs that exceed the budget of each individual project as well as the total budget. Chiu and Tsai BIB006 deal with an NPV objective that includes earliness and tardiness payments with regard to the project due dates. Franck et al.  consider resource leveling as well as resource investment objectives. Goncalves et al.  aim at minimizing the weighted sum of earliness and tardiness as well as the flow time of each project. Homberger BIB007 discusses the minimization of the average makespan of the projects, where the makespan of each individual project is defined as its completion time minus its release date. Lawrence and Morton BIB003 deal with the minimization of weighted tardiness. Lova et al. BIB005 consider various objectives such as mean tardiness, makespan of the "superproject," resource leveling and project splitting. The latter is defined as the number of periods a project is interrupted, i.e., no activity of this project is carried out after the project has been started and before it is finished (but probably activities related to other projects). Kurtulus and Davis BIB001 consider the total delay, where the delay of each project is measured as the difference between completion time in the actual schedule and completion time in the resource-unconstrained case. Kurtulus BIB002 extend this approach by defining several functions that assign different delay penalties to the projects. Browning and Yassine BIB008 follow this definition of delays and discuss objectives including average delay per project, average percentage delay per project (measured as percentage of the critical path length) as well as percentage delay of the "super-network."