The DOI matches its Crossref record.
An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Resource-constrained project scheduling: Notation, classification, models, and methods
Brucker, P., Drexl, A., Möhring, R., Neumann, K., & Pesch, E. (1999) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00204-5 · Cited by 1,500
Chapter 9 Sequencing and scheduling: Algorithms and complexity
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80189-6 · Cited by 761
Resource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case
Talbot, F. B. (1982) · Management Science · doi:10.1287/mnsc.28.10.1197 · Cited by 456
Self-citationA Robust Genetic Algorithm for Resource Allocation in Project Scheduling
Alcaraz, J., & Maroto, C. (2001) · Annals of Operations Research · doi:10.1023/a:1010949931021 · Cited by 275
Scheduling of deconstruction projects under resource constraints
Schultmann, F., & Rentz, O. (2002) · Construction Management and Economics · doi:10.1080/01446190210135913 · Cited by 24
Metadata
- Authors
- Talbot, F. B., & Patterson, J. H.
- Venue
- Management Science
- Published
- 1978-07
- Volume
- 24
- Issue
- 11
- Pages
- 1163-1174
- ISSN
- 0025-1909 (ISSN-L)
- 1526-5501
- OpenAlex
- W2066190993
- Cited by
- 209
- References
- 0
- FWCI
- 2.11
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems. https://app.cochat.ai/papers/10.1287/mnsc.24.11.1163
- The paper
- Talbot, F. B., & Patterson, J. H. (1978). An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems. Management Science. https://doi.org/10.1287/mnsc.24.11.1163
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.