Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer
type: Item
instance of: scholarly article
title: Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer
zbMATH Open document ID: 0614.90056
DOI: 10.1016/0377-2217(87)90240-2
author: Nicos Christofides
author: Ramón Alvarez-Valdes
author: José Manuel Tamarit
published in: European Journal of Operational Research
publication date: 1987-01-01T00:00:00Z
review text: This paper describes a branch and bound algorithm for project scheduling with resource constraints. The algorithm is based on the idea of using disjunctive arcs for resolving conflicts that are created whenever sets of activities have to be scheduled whose total resource requirements exceed the resource availabilities in some periods. Four lower bounds are examined. The first is a simple lower bound based on longest path computations. The second and third bounds are derived from a relaxed integer programming formulation of the problem. The second bound is based on the linear programming relaxation with the addition of cutting planes, and the third bound is based on a Lagrangean relaxation of the formulation. This last relaxation involves a problem which is a generalization of the longest path computation and for which an efficient, though not polynomial, algorithm is given. The fourth bound is based on the disjunctive arcs used to model the problem as a graph. We report computational results on the performance of each bound on randomly generated problems involving up to 25 activities and 3 resources. \{F. Kaefer points out that the Lagrangean relaxation is used incorrectly.\}
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 3995434
zbMATH Keywords: Lagrange multipliers
zbMATH Keywords: branch and bound algorithm
zbMATH Keywords: project scheduling
zbMATH Keywords: resource constraints
zbMATH Keywords: relaxation
zbMATH Keywords: cutting planes
zbMATH Keywords: longest path
zbMATH Keywords: computational results
MaRDI profile type: Publication
full work available at URL: 0377-2217(87)90240-2
OpenAlex ID: W2024237395
cites work: Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm
cites work: Technical Note—An Improved Feasibility Test for Gorenstein's Algorithm
cites work: An Algorithm for Optimal Project Scheduling under Multiple Resource Constraints
cites work: Q5183254
cites work: An Algorithm for Project (Job) Sequencing with Resource Constraints
cites work: An Algorithm for the Line Balancing Problem
cites work: Validation of subgradient optimization
cites work: An Efficient Integer Programming Algorithm with Network Cuts for Solving Resource-Constrained Scheduling Problems
description: scientific article; zbMATH DE number 3995434