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.}

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.}

##### Keywords:

Lagrange multipliers; branch and bound algorithm; project scheduling; resource constraints; relaxation; cutting planes; longest path; computational results
PDF
BibTeX
XML
Cite

\textit{N. Christofides} et al., Eur. J. Oper. Res. 29, 262--273 (1987; Zbl 0614.90056)

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.