Skip to main content
main-content

Über dieses Buch

Within a project human and non-human resources are pulled together in a tempo­ raray organization in order to achieve a predefined goal (d. [20], p. 187). That is, in contrast to manufacturing management, project management is directed to an end. One major function of project management is the scheduling of the project. Project scheduling is the time-based arrangement of the activities comprising the project subject to precedence-, time-and resource-constraints (d. [4], p. 170). In the 1950's the standard methods MPM (Metra Potential Method) and CPM (Cri­ tical Path Method) were developed. Given deterministic durations and precedence­ constraints the minimum project length, time windows for the start times and critical paths can be calculated. At the same time another group of researchers developed the Program Evaluation and Review Technique (PERT) (d. [19], [73] and [90]). In contrast to MPM and CPM, random variables describe the activity durations. Based on the optimistic, most likely and pessimistic estimations of the activity durations an assumed Beta­ distribution is derived in order to calculate the distribution of the project duration, the critical events, the distribution of earliest and latest occurence of an event, the distribution of the slack of the events and the probability of exceeding a date. By the time the estimates of the distributions have been improved (d. e.g. [52] and [56]). Nevertheless, there are some points of critique concerning the estimation of the resulting distributions and probabilities (d. e.g. [48], [49] and [50]).

Inhaltsverzeichnis

Frontmatter

Chapter 1. The Model

Abstract
We consider a project which consists of a set of activities. Equivalently we refer to the activities with the term job or task, where the latter one is more closely related to the operation within the machine scheduling environment (cf. [5]).
Arno Sprecher

Chapter 2. Special Cases

Abstract
In this chapter we will discuss some wellknown scheduling problems which turn out to be special cases of the more general resource-constrained project scheduling problem. More precisely, we will point out how to transfer the commonly known flow-shop- (FSP), job-shop- (JSP) and open-shop-problem (OSP) to a resource-constrained project scheduling problem RCPSP. Furthermore, by the reformulation of the assembly line balancing problem as a resource-constrained project problem the versatility of the model is illustrated.
Arno Sprecher

Chapter 3. Variants and Extensions

Abstract
In this section we deal with some generalizations of the resource-constrained project scheduling problem presented in Chapter 1. A discussion of a more general framework of precedence relations is given in Section 3.1. In Section 3.2 the time varying request for renewable resources is outlined. A brief discussion of further regular measures of performance follows in Section 3.3.
Arno Sprecher

Chapter 4. Types of Schedules

Abstract
In this chapter we state the formal definitions of different types of schedules. The original work can be found in [111], where beside the points to be explained here a set of examples brings the necessity of more formal definitions into focus. The schedules we are considering are the semi-active, the active and the non-delay schedules, where the latter one are only dealt with for the sake of completeness.
Arno Sprecher

Chapter 5. A Branch and Bound Algorithm

Abstract
Whereas exact methods for solving the single-mode resource-constrained project scheduling problem are well documented in the literature (cf. e.g. [7], [18], [25], [27], [32], [33], [33], [95], [101], [112], [113]), the multi-mode extension has attracted less attention (cf. [88], [89], [109], [114], [115], [116]). In this chapter we present and analyze an algorithm for the multi-mode resource-const rained project scheduling problem. The stepping stone of the algorithm is a proposal from Patterson et al. (cf. [88]) who introduced an enumeration procedure of the Branch and Bound (B&B) type. The basic ideas were, of course, given by Talbot and Patterson (cf. [116]) and Talbot (cf. [115]). For getting deeper insight the algorithm is completely restructured, where main differences will be identified by remarks.
Arno Sprecher

Chapter 6. Generation of Instances by ProGen

Abstract
In this chapter we describe an algorithm for the generation of a general class of precedence- and resource-constrained scheduling problems. The generator has been developed by Kolisch, Sprecher and Drexl (cf. [68]). It has been coded in Turbo Pascal.
Arno Sprecher

Chapter 7. Computational Results

Abstract
In this chapter we present the results of our computational studies. One of the main results will be that, although the efficieny of the algorithm has been substantially increased by the proposed bounding rules, the multi-mode resource-const rained project scheduling problem is less tractable than reported in the literature. Patterson et al. (cf. [89]) have generated 91 instances. The number of jobs ranged from 10 to 500, where 75 instances have up to 30 jobs. The instances have been characterized by the mean number of modes, mean activity duration, minimum/maximum activity duration, standard deviation of the activity durations, critical path length (based on minimum activity durations), average fraction of resources used by an activity mode and network density. The procedure has been coded in Fortran and implemented on an IBM 4381 mainframe, which is, as has been stated, approximately seven times faster than a 386-based, 20 MHz PC with numeric coprocessor. For an imposed time limit of 1 (10) minutes 30 (33) of the problems with up to 50 activities have been solved to optimality. The preponderance of these problems ranged between ten and thirty jobs.
Arno Sprecher

Chapter 8. An Artificial Intelligence Approach

Abstract
In this chapter we will use a logic programming approach in order to attack the scheduling problems described. Preliminary studies can be found in [46].
Arno Sprecher

Chapter 9. Applications

Abstract
Beyond the applications mentioned in the preface concerning the management of projects, the models and algorithm proposed can be used in production planning. With production planning we refer to the preparation of decisions concerning the production.
Arno Sprecher

Chapter 10. Conclusions

Abstract
We have considered the multi-mode resource-constrained project scheduling problem. The problem has been stated as a mathematical programming formulation, the versatility of which has been illustrated by examples. This should encourage the reader to try his hand on embedding other models in the formulation outlined.
Arno Sprecher

Backmatter

Weitere Informationen