EFFICIENT INTEGER PROGRAMMING ALGORITHM WITH NETWORK CUTS FOR SOLVING RESOURCE-CONSTRAINED SCHEDULING PROBLEMS.

Description of an integer programming algorithm for allocating limited resources to competing activities (jobs, tasks, etc. ) of a project such that the completion time of the project is minimal among all possible completion times. Typical of such problems is the minimization of the completion time of projects of the PERT/CPM variety where limits on resource availability force the postponement of selected activities during project performance. The procedure developed consists of a systematic evaluation (enumeration) of all possible job finish times for each task in the project. To limit the number of task assignments which have to be explicitly evaluated, an artifice called a network cut is developed which removes from consideration the evaluation of job finish times which cannot lead to a reduced project completion time. Results reported demonstrate that the procedure developed is a reliable optimization technique for projects consisting of up to 30-50 jobs and three different resource types. The procedure is particularly applicable in those instances in which computer primary storage is limited.