Business Commons^™

On The Use Of The Complexity Index As A Measure Of Complexity In Activity Networks, Bert De Reyck, Willy Herroelen

Research Collection Lee Kong Chian School Of Business

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 …