A project is a unique undertaking or endeavor to be accomplished that can be divided into individual subtasks or activities each of which requires time and scarce resources for its completion. Also there is a desired objective to be attained (for example, minimization of project duration or of variation of resource utilization, or maximization of net present value of the project). Moreover, there are given precedence relationships among activities prescrib­ ing the order in which activities must be carried out. Project scheduling, in its basic form, consists of finding start times for all activities such that pre­ scribed resource and precedence constraints are satisfied and an objective function is optimized. Since the concept of a project can be interpreted quite broadly, project scheduling problems arise in a great variety of practical situations. These in­ clude construction work, the development and introduction of new products, service systems, or software packages, strategic long-term planning in manu­ facturing and the service sector, emergency planning, and even the conduct­ ing of political campaigns. Recently, project scheduling has been successfully applied to production and operations management, e.g. make-to-order pro­ duction in manufacturing and batch production in process industries. Since the late 1950's, network-based planning methods for project sched­ uling problems have been developed, cf. Elmaghraby (1977) and Moder et al.