An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems

F. Brian Talbot and James H. Patterson
Additional contact information
F. Brian Talbot: University of Michigan
James H. Patterson: University of Missouri-Columbia

Management Science, 1978, vol. 24, issue 11, 1163-1174

Abstract: In this paper we describe 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. Also included in this class of problems for which our procedure is applicable is the assignment of jobs to machines such that the elapsed time for completing all jobs (makespan) is a minimum over all possible job-machine assignments. 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. Many of the mini-computers available today are capable of implementing our approach without extensive programming being required for writing to auxiliary storage, making the technique available to the project manager in those environments in which extensive computer resources for scheduling are not readily available.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (52)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.24.11.1163 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:24:y:1978:i:11:p:1163-1174

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().