×

zbMATH — the first resource for mathematics

Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer. (English) Zbl 0614.90056
Eur. J. Oper. Res. 29, 262-273 (1987); note ibid. 125, No. 1, 216-217 (2000).
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.}

MSC:
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balas, E., Machine sequencing via disjunctive graphs: an implicit enumeration algorithm, Operations research, 17, 941-957, (1969) · Zbl 0183.49404
[2] Balas, E., Project scheduling with resource constraints, ()
[3] Bennington, G.E.; McGinnis, L.F., An improved feasibility test for Gorenstein’s algorithm, Operations research, 22, 1117-1119, (1974) · Zbl 0294.90087
[4] Davis, E.W.; Heidorn, G.E., An algorithm for optimal project scheduling under multiple constraints, Management science, 17, B803-B816, (1971) · Zbl 0224.90030
[5] Davis, E.W.; Patterson, J.H., A comparison of heuristics and optimum solution in resource-constrained project scheduling, Management science, 21, 944-955, (1975)
[6] Fisher, M.L.; Fisher, M.L., Optimal solution of scheduling problems using Lagrange multipliers, (), 294-318, Part II
[7] Functional Mathematical Programming System (FMPS), Programmer Reference UP 8198 Rep. 1, Sperry Univac.
[8] Gorenstein, S., An algorithm for project (job) scheduling with resource constraints, Operations research, 20, 835-850, (1972) · Zbl 0241.90030
[9] Gutjhar, A.L.; Nemhauser, G.L., An algorithm for the line-balancing problem, Management science, (1964) · Zbl 0137.39303
[10] Held, M.; Wolfe, P.; Crowder, H.P., Validation of the subgradient optimization, Mathematical programming, 6, 62-88, (1974) · Zbl 0284.90057
[11] Patterson, J.H.; Roth, G.W., Scheduling a project under multiple resource constraints: A 0-1 programming approach, AIEE transactions, 8, 449-455, (1976)
[12] Pritsker, A.A.; Waters, L.J.; Wolfe, P.M., Multi-project scheduling with limited resources: A 0-1 approach, Management science, 16, 93-108, (1969)
[13] Stinson, J.P.; Davis, E.W.; Khumawala, B.H., Multiple resource-constrained scheduling using branch and bound, AIEE transactions, 10, 252-259, (1978)
[14] Talbot, F.B.; Patterson, J.H., An efficient integer programming algorithm for solving resource constrained scheduling problems, Management science, 24, 1163-1174, (1978) · Zbl 0395.90036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.