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

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

Full description

Saved in:
Bibliographic Details
Main Authors: Demeulemeester, E, Herroelen, W, Simpson, W.P, Baroum, S, Patterson, J. H., Yang, Kum Khiong
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 1994
Subjects:
Online Access:https://ink.library.smu.edu.sg/lkcsb_research/2226
https://doi.org/10.1016/0377-2217(94)90018-3
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.lkcsb_research-3225
record_format dspace
spelling sg-smu-ink.lkcsb_research-32252010-09-23T12:30:04Z On a Paper by Christofides Et Al. For Solving the Multiple-Resource Constrained, Single Project Scheduling Problem Demeulemeester, E Herroelen, W Simpson, W.P Baroum, S Patterson, J. H. Yang, Kum Khiong 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. 1994-01-01T08:00:00Z text https://ink.library.smu.edu.sg/lkcsb_research/2226 info:doi/10.1016/0377-2217(94)90018-3 https://doi.org/10.1016/0377-2217(94)90018-3 Research Collection Lee Kong Chian School Of Business eng Institutional Knowledge at Singapore Management University Business
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Business
spellingShingle Business
Demeulemeester, E
Herroelen, W
Simpson, W.P
Baroum, S
Patterson, J. H.
Yang, Kum Khiong
On a Paper by Christofides Et Al. For Solving the Multiple-Resource Constrained, Single Project Scheduling Problem
description 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.
format text
author Demeulemeester, E
Herroelen, W
Simpson, W.P
Baroum, S
Patterson, J. H.
Yang, Kum Khiong
author_facet Demeulemeester, E
Herroelen, W
Simpson, W.P
Baroum, S
Patterson, J. H.
Yang, Kum Khiong
author_sort Demeulemeester, E
title On a Paper by Christofides Et Al. For Solving the Multiple-Resource Constrained, Single Project Scheduling Problem
title_short On a Paper by Christofides Et Al. For Solving the Multiple-Resource Constrained, Single Project Scheduling Problem
title_full On a Paper by Christofides Et Al. For Solving the Multiple-Resource Constrained, Single Project Scheduling Problem
title_fullStr On a Paper by Christofides Et Al. For Solving the Multiple-Resource Constrained, Single Project Scheduling Problem
title_full_unstemmed On a Paper by Christofides Et Al. For Solving the Multiple-Resource Constrained, Single Project Scheduling Problem
title_sort on a paper by christofides et al. for solving the multiple-resource constrained, single project scheduling problem
publisher Institutional Knowledge at Singapore Management University
publishDate 1994
url https://ink.library.smu.edu.sg/lkcsb_research/2226
https://doi.org/10.1016/0377-2217(94)90018-3
_version_ 1770570169922355200