Publication Type

Journal Article

Version

publishedVersion

Publication Date

6-1996

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.

Keywords

Project planning, Network complexity measure, Complexity index, Network reduction

Discipline

Business Administration, Management, and Operations | Management Information Systems | OS and Networks

Research Areas

Operations Management

Publication

European Journal of Operational Research

Volume

91

Issue

2

First Page

347

Last Page

366

ISSN

0377-2217

Identifier

10.1016/0377-2217(94)00344-0

Publisher

Elsevier: 24 months

Embargo Period

8-31-2021

Download

Share

COinS