Title: On the use of the complexity index as a measure of complexity in activity networks
Authors: DeReyck, B ×
Herroelen, Willy #
Issue Date: Jun-1996
Publisher: Elsevier science bv
Series Title: European journal of operational research vol:91 issue:2 pages:347-366
Abstract: A large number of optimal and suboptimal procedures have been developed for solving combinatorial problems modeled as activity networks. The need to differentiate between easy and hard problem instances and the interest in isolating the fundamental factors that determine the computing effort required by these procedures, inspired a number of researchers to develop various complexity measures. In this paper we investigate the relation between the hardness of a problem instance and the topological structure of its underlying network, as measured by the complexity index. We demonstrate through a series of experiments that the complexity index, defined as the minimum number of node reductions necessary to transform a general activity network to a series-parallel network, plays an important role in predicting the computing effort needed to solve easy and hard instances of the multiple resource-constrained project scheduling problem and the discrete time/cost trade-off problem.
ISSN: 0377-2217
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Management, Leuven
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science