A survey of variants and extensions of the resource-constrained project scheduling problem <s> Further Specific Multi-Project Problems <s> Abstract We address the problem of scheduling in programs involving the production of multiple units of the same product. Our study was motivated by a construction program for fast naval patrol boats. Other applications of this problem include procurement of multiple copies of aircraft, spacecraft, and weapon systems. In this problem we must decide how many units of the product to assign to each of a number of available crews (individuals, teams, subcontractors, etc.). These types of problems are characterized by two potentially conflicting considerations: 1) the need to complete each unit by its contractual due date, and 2) learning effects. Because of the first consideration, there is a tendency to use multiple crews for simultaneous production, so that meeting due dates is assured. However, the second consideration encourages assigning many units to a single crew so that learning effects are maximized. We study this scheduling problem with two different penalty cost structures and develop models for both versions. The models trade-off the penalty associated with late deliveries and the savings due to learning (and possibly incentive payments for early completion). We discuss different heuristic algorithms — simulated annealing, a genetic algorithm, and a pair-wise swap heuristic — as well as an exhaustive search to determine a baseline for comparisons. Our computational results show that the pair-wise swap algorithm is the most efficient solution procedure for these models. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Further Specific Multi-Project Problems <s> Abstract The problem of scheduling multiple, large-scale, make-to-order assemblies is considered. Beside `classical’ precedence and resource constraints as known from resource-constrained project scheduling we take spatial resource and part availability constraints into account. The objective is to minimize the sum of the weighted tardiness. We propose a MIP-model of the problem which is a generalization of three allocation problems. Since the problem is NP -hard, a list-scheduling heuristic is proposed and evaluated on a set of benchmark instances. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Further Specific Multi-Project Problems <s> Abstract Many studies in the product development literature discuss the benefits of partnering with suppliers. In these partnership relations buyers and suppliers establish long term, co-operative relationships during Product Development Projects (PDP) in order to reduce product development time and improve project performance. Traditional contractual approaches, on the other hand, where buyers work independently of suppliers and lack control over suppliers' resources, are commonly blamed for delays in the development time. This study constitutes of an initial effort to model and investigate these relationships analytically. The impact of scheduling strategies, the number of suppliers, and resource availability on PDP completion time is evaluated under contractual or partnership arrangement. Contractual relationships seem to provide a good or even better development times than the ones provided by the partnership approach. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Further Specific Multi-Project Problems <s> Repetitive projects involve the repetition of activities along the stages of the project. Since the resources required to perform these activities move from one stage to the other, a main objective of scheduling these projects is to maintain the continuity of work of these resources so as to minimize the idle time of resources. This requirement, often referred to as work continuity constraints, involves a tradeoff between total project duration and the resource idle time. The contribution of this paper is threefold. First, we provide an extensive literature summary of the topic under study. Although most research papers deal with the scheduling of construction projects, we show that this can be extended to many other environments. Second, we propose an exact search procedure for scheduling repetitive projects with work continuity constraints. This algorithm iteratively shifts repeating activities further in time in order to decrease the resource idle time. We have embedded this recursive search procedure in a horizon-varying algorithm in order to detect the complete tradeoff profile between resource idle time and project duration. The procedure has been coded in Visual C++ and has been validated on a randomly generated problem set. Finally, we illustrate the concepts on three examples. First, the use of our new algorithm is illustrated on a small fictive problem example from literature. In a second example, we show that work continuity constraints involve a tradeoff between total project duration and the resource idle time. A last example describes the scheduling of a well-known real-life project that aims at the construction of a tunnel at the Westerschelde in The Netherlands. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Further Specific Multi-Project Problems <s> We consider the problem of simultaneously scheduling IT-projects and assigning multi-skilled internal and external human resources with resource-specific efficiencies to the project work. The objective is to minimize labor costs. The problem is modeled as a mixed-integer linear program (MIP) with a tight LP-bound. The performance of the model w.r.t. solution gap and computation time is assessed and managerial insight is given concerning different problem parameters such as the time window size of projects, the number of skills of human resources, and the workload. Furthermore, we show the benefit of applying the MIP compared to simple heuristics used in practice in terms of obtaining feasible and low-cost solutions. Finally, we provide insight into the benefit of applying the MIP in case of central compared to decentral planning. <s> BIB005
Heimerl and Kolisch BIB005 propose a multi-project problem where the schedule of each project is fixed. Consequently, each project can be viewed as an activity with time-dependent resource requirements. The resources are the internal and external workforce where different skills and efficiencies are taken into account. The objective is to minimize costs for regular and overtime work as well as for external resources. Kolisch BIB002 presents a problem for scheduling multiple assembly projects. It includes due dates for the individual projects and tardiness minimization. Only a limited number of individual projects can be in progress at the same time because space in the assembly area is limited. Moreover, an activity can only start when all parts required for the assembly are available (note that this is similar to the concept of cumulative resources, see Section 4.3). Shtub et al. BIB001 develop multi-project problems which assume that a project is repeated several times, as it may occur in small batch production. Their problem settings consider learning effects that can be exploited if a (human) resource performs several identical projects, that is, the time needed for one project may decrease. Tukel and Wasti BIB003 discuss problems for product development projects which include outsourcing of sub-projects to suppliers. The "contractual approach" assumes that the suppliers schedule their sub-projects in the first step. The second step is the scheduling of the main project, where each sub-project of a supplier is treated as a single activity with the duration corresponding to the sub-project's makespan. The "partnership approach" is a multi-project problem setting that integrates the sub-project's activities into the overall project network. Vanhoucke BIB004 considers a project which is repeated several times. The resulting projects are represented in a super-network as described above, and the super-sink is associated with a deadline. An activity requires the same resource in each project (which is referred to as work continuity), and the objective is to minimize the resource idle time.