On the use of the complexity index as a measure of complexity in activity networks

On the use of the complexity index as a measure of complexity in activity networks

0.00 Avg rating0 Votes
Article ID: iaor1999122
Country: Netherlands
Volume: 91
Issue: 2
Start Page Number: 347
End Page Number: 366
Publication Date: Jun 1996
Journal: European Journal of Operational Research
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.