Resource-constrained project scheduling with preemption of jobs.

We examine the problem of obtaining a minimum duration schedule for projects with constrained resources, where preemption of jobs in progress is allowed. This problem is NP-complete, as are many scheduling problems. Traditional enumerative solution procedures, such as branch- and -bound, have had limited success in the area of resource-constrained project scheduling. In this dissertation, we approach the problem from a dynamic programming point of view. When activities are preemptible, an optimal schedule can be found in a recursive fashion. We exploit this property to derive two solution procedures which obtain an optimal solution for the situation where there are no setup times or preemption limits for any jobs in the project. Analogues to popular priority-dispatch scheduling heuristics are derived, which enable us to obtain a feasible schedule with little computational effort. In addition, we develop an iterative procedure to obtain tight lower bounds on the minimum project duration. These upper and lower bounds serve to further enhance the optimal solution procedures. The algorithms developed in this dissertation are then tested on a set of well-known test problems. We report the computational results of this testing, which indicate that the dynamic programming procedures can efficiently obtain optimal schedules. Finally, we extend the dynamic programming formulation of the project scheduling problem to incorporate more general restrictions on activity preemption. We show that setup times and direct limits on job preemption can be included within the dynamic programming framework.PhDOperations researchUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/161931/1/8821594.pd