Project Planning and Scheduling

This chapter focuses on the planning and scheduling of jobs that are subject to precedence constraints. The setting may be regarded as a parallel machine environment with an unlimited number of machines. The fact that the jobs are subject to precedence constraints implies that a job can start with its processing only when all its predecessors have been completed. The objective is to minimize the makespan while adhering to the precedence constraints. This type of problem is referred to as a project planning and scheduling problem. A more general version of the project planning and scheduling problem assumes that the processing times of the jobs are not entirely fixed in advance. A project manager has some control on the durations of the processing times of the different jobs through the allocation of additional funds from a budget that he has at his disposal. Since a project may have a deadline and a completion after its deadline may entail a penalty, the project manager has to analyze the trade-off between the costs of completing the project late and the costs of shortening the durations of the individual jobs. These types of planning and scheduling problems often occur in practice when large projects have to be undertaken. Examples of such projects are real estate developments,construction of power generation centers,sof tware developments, and launchings of spacecraft. Other applications include projects in the defense industry,suc h as the design,dev elopment and construction of aircraft carriers and nuclear submarines.