On a Paper by Christofides Et Al. For Solving the Multiple-Resource Constrained, Single Project Scheduling Problem

Publication Type

Journal Article

Publication Date

1994

Abstract

In a recently published article in EJOR, Christofides et al. (CAT) present a depth-first search, branch-and-bound solution procedure for the multiple-resource constrained, single project scheduling problem. While there are many important contributions in this paper, we show by counterexample that if the branching strategy described by the authors is used, the optimal solution might not result. Computational experience on a set of test problems appearing in the open literature is reported both with the original branching strategy suggested by the authors and a modified branching strategy that we propose. The modified strategy guarantees the determination of the optimal solution in all instances of the problem at the expense of an increase in node evaluations and average CPU time. Computational results using the revised procedure and a hybrid, breadth-first search procedure also investigated by CAT are reported.

Discipline

Business

Research Areas

Operations Management

Publication

European Journal of Operational Research

Volume

76

Issue

1

First Page

218

Last Page

228

ISSN

0377-2217

Identifier

10.1016/0377-2217(94)90018-3

Publisher

Elsevier

Link to Full Text

Share

COinS