Project Scheduling under Limited Resources

A project consists of activities which must be carried out to achieve a predefined goal. One of the main tasks in project management is the scheduling of the project, that is, the temporal arrangement of the activities. Within a project schedule, certain requirements must be observed, especially limited availabilities of resources that are needed to perform the activities.

Until today, many different project scheduling models have been proposed, covering a broad variety of real-world requirements. This chapter introduces the basic components of these models such as activities, precedence relations, and resources. The models discussed here provide the basis for developing project scheduling algorithms and analyzing applications in the remainder of this work.

Having discussed several models for resource-constrained project scheduling in the previous chapter, we now deal with scheduling algorithms which compute optimal schedules for given projects. Due to the NP-hardness of the RCPSP and its extensions, however, we cannot expect the exact algorithms to determine optimal solutions for problems of larger size in reasonable computation times. Consequently, heuristic procedures are needed for application to real-world projects. Nevertheless, there are two important reasons for dealing with exact approaches: First, they allow to determine optimal solutions for (smaller) test problems which provide a basis for the evaluation of heuristics. Second, the knowledge gained from designing efficient exact procedures is useful when developing heuristics, as will be demonstrated in the remainder of this work.

The computational results reported in the previous chapter demonstrated that exact solution algorithms are of no use when scheduling projects of real-world size. From a theoretical point of view, this outcome is no surprise due to the NP-hardness of the RCPSP and its extensions. But, considering the data uncertainty often occuring in practice such as unpredictable delays, perfectly accurate planning would not be needed anyway. For that reason, schedules which are close to the optimum are sufficient in most cases. Such good but not necessarily optimal schedules are constructed by heuristics. Since 1963 when Kelley [111] introduced a schedule generation scheme, a large number of different heuristic algorithms have been suggested in the project scheduling literature.

In this chapter, we discuss genetic algorithm (GA) heuristics for the RCPSP. The GAs make use of many of the concepts that were discussed in the previous chapter, such as schedule generation schemes, problem representations, and priority rule methods. We will also introduce some new approaches such as new operators, generalized representations, and a local search extension. In particular, we will introduce a representation which allows the GA to adapt itself by learning which algorithmic component should be used.

In the last chapter, we have only briefly reported on computational results concerning the impact of the representation within a genetic algorithm. However, we have not yet given any test results for the extended GA, and we do not yet know how our GAs perform compared to heuristics from the literature. This chapter closes these gaps. We present a computational study which gives a performance analysis of the four GAs introduced in Chapter 5 and many of the state-of-the-art heuristics which have been described in the literature survey of Chapter 4. As in the previous two chapters, the focus is again on the single-mode RCPSP. The experimental investigation is accompanied by explanations for the performance results. The goal is to point out the most promising heuristic for the RCPSP.

The previous chapter has shown that our extended genetic algorithm is currently the best heuristic for the single-mode RCPSP. The goal of this chapter is to generalize and adapt the concepts used in the single-mode GA to obtain a good heuristic for multi-mode project scheduling. Therefore, we will consider those general aspects that contributed to the success of the best single-mode GA. We extend the activity list representation and associated crossover and mutation in order to make it suitable for dealing with multiple modes. Moreover, we will discuss local search extensions that further improve the behavior of the GA. The local search components for the multi-mode case are completely different from that of the single-mode RCPSP and will lead us to an analysis of different inheritance mechanisms within GAs in general.

In this chapter, we study two real-world applications of resource-constrained project scheduling. First, we deal with scheduling the experiments of a medical research project. Here, various constraints have to be observed, especially scarce laboratory equipment and the arrangement of different experiment types. Then we consider the task of scheduling the interviews of a market research study which can be viewed as a project. This includes the selection of interviewers with respect to several constraints such as regional distribution of the interviews, qualification, and available working time of the interviewers.

In this work, we have considered models, solution methods, and applications for project scheduling under scarce resources. We finish with a summary of the main results and some comments on opportunities in future research.