A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Costs <s> We consider the problem of scheduling a set of activities satisfying precedence constraints in order to minimize the sum of the costs associated with the starting times of the activities. We consider the case in which the activity starting time cost functions are irregular functions. This problem can be solved in polynomial time either when the precedence graph has a special structure or when the starting time cost function of each activity is monotonic. A (0-1) integer programming formulation of this problem is presented and used to derive valid lower bounds to the optimal solution cost. An exact branch-and-bound algorithm is described. Computational results show the effectiveness of the proposed exact algorithm in solving problems up to 100 activities. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Costs <s> Maniezzo and Mingozzi (Oper. Res. Lett. 25 (1999) 175-182) study a project scheduling problem with irregular starting time costs. Starting from the assumption that its computational complexity status is open, they develop a branch-and-bound procedure and they identify special cases that are solvable in polynomial time. In this note, we present a collection of previously established results which show that the general problem is solvable in polynomial time. This collection may serve as a useful guide to the literature, since this polynomial-time solvability has been rediscovered in different contexts or using different methods. In addition, we briefly review some related results for specializations and generalizations of the problem. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Costs <s> In a given project network, execution of each activity in normal duration requires utilization of certain resources. If faster execution of an activity is desired then additional resources at extra cost would be required. Given a project network, the cost structure for each activity and a planning horizon, the project compression problem is concerned with the determination of optimal schedule (duration) of performing each activity while satisfying given restrictions and minimizing the total cost of project execution. This paper considers the project compression problem with time dependent cost structure for each activity. The planning horizon is divided into several regular time intervals over which the cost structure of an activity may vary. But the cost structure of the activities remains the same (constant) within a time interval. Key events of the project attract penalty for finishing earlier or later than the corresponding target times. The objective is to find an optimal project schedule minimizing the total project cost. We present a mathematical model for this problem, develop some heuristics and an exact branch and bound algorithm. Using simulated problems we provide an insight into the computational performances of heuristics and the branch and bound algorithm. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Costs <s> Integrating project scheduling and material ordering adds more realism to project scheduling and considers additional trade-offs that could lead to reductions in the overall project cost. In this paper we review the evolution of the integrated problem, and investigate the impact of treating the activity duration as a decision variable on the activities schedule and materials plan. The effects of introducing rewards (penalties) for early (late) completion as well as materials quantity discounts on the project schedule and cost are also considered- These additions provide scheduling flexibility that might lead to further reduction in the project's total cost or makespan. Considering the various project costs, we found that there exists an optimal schedule that either starts as early as possible (ai time zero) or completes as late as possible. We also show that if the project starts at time zero, then its duration cannot be longer than that for the case where the schedule ends as late as possible. Ft is also shown that the material ordering policy does not follow the Wagner and Whitin model when activity duration is variable or in the presence of quantity discounts. These results have led to modeling and solving the problem in a more efficient manner. Extensive computational work shows the validity of the model and the solution approach. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Costs <s> In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in manufacturing, production planning, project management, and elsewhere. It is one of the most intractable problems in operations research, and has therefore become a popular playground for the latest optimization techniques, including virtually all local search paradigms. We show that a somewhat more classical mathematical programming approach leads to both competitive feasible solutions and strong lower bounds, within reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integer programming formulation and relaxation-based list scheduling, enriched with a useful idea from recent approximation algorithms for machine scheduling problems. The efficiency of the algorithm results from the insight that the relaxed problem can be solved by computing a minimum cut in an appropriately defined directed graph. Our computational study covers different types of resource-constrained project scheduling problems, based on several notoriously hard test sets, including practical problem instances from chemical production planning. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Costs <s> We introduce a generalized model of the resource constrained project scheduling problem (RCPSP). It features that (i) the duration of an activity is not constant, but can vary in a specified range, and (ii) the objective is to minimize a convex function of time-lag costs, where a time-lag cost is charged according to the difference between the start/completion times of activities. These features achieve the flexibility of the model. It is known that, in the RCPSP, resource constraints can be replaced by some precedence constraints appropriately defined between the activities that require a common scarce resource. If we remove resource constraints by precedence constraints, our problem can be formulated as the dual problem of a minimum cost flow problem, and thus can be solved efficiently. Exploiting this property, we design a heuristic algorithm based on local search. We conducted computational experiments with benchmark instances to minimize the weighted earliness-tardiness costs, as well as instances in which activity-crashing or relaxation of temporal constraints are allowed. These results indicate the usefulness of our generalized RCPSP model and the proposed algorithm. <s> BIB006
Maniezzo and Mingozzi BIB001 and Möhring et al. BIB002 BIB005 consider costs c jt for each activity j that depend on the start time t of j. The objective is to minimize the sum of these costs (the underlying problem is an RCPSP without resources). As pointed out by Möhring et al. BIB005 , this objective includes various other well-known objectives as special cases, such as makespan minimization, earliness-tardiness-based objectives and maximization of the net present value (for the latter see Section 5.7). Achuthan and Hardjawidjaja BIB003 minimize total project costs which consist of earliness and tardiness costs with regard to due dates as well as costs related to the durations of the activities (the durations can be shortened at additional costs). The project must be finished not later than a given deadline, and renewable resources are not considered. Dodin and Elimam BIB004 aim at minimizing costs which includes costs for activity crashing (i.e., shortening the duration), material costs and inventory holding costs. Based on a given due date, a bonus for early project completion or a penalty for late completion is added. Nonobe and Ibaraki BIB006 consider activity durations which have to be between a lower and an upper limit. This leads to an objective that minimizes the costs related to the durations, where the cost function for each activity is convex. Rummel et al.  consider a cost-based objective that consists of two components. The project duration costs are proportional to the makespan. Activities can be combined (consolidated) in order to reduce the makespan, but this causes consolidation costs. The objective is used in a problem without resource constraints.