On the use of the complexity index as a measure of complexity in activity networks. (English) Zbl 0924.90092
Summary: 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.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C35 | Programming involving graphs or networks |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1975), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0307.68053 |
| [2] | Alvarez-Valdes, R.; Tamarit, J. M., Heuristic algorithms for resource-constrained project scheduling: A review and empirical analysis, (Slowinski, R.; Weglarz, J., Advances in Project Scheduling (1989), Elsevier: Elsevier Amsterdam) · Zbl 0614.90056 |
| [3] | Baroum, S. M.; Patterson, J., A comparative evaluation of cash flow weight heuristics for maximizing the net present value of a project (1993), Indiana University: Indiana University Bloomington, IN, Research paper |
| [4] | Bein, W. W.; Kamburowski, J.; Stallmann, M. F.M., Optimal reduction of two-terminal directed acyclic graphs, SIAM Journal on Computing, 21, 1112-1129 (1992) · Zbl 0768.68119 |
| [5] | Caestecker, G.; Herroelen, W., The generation of random activity networks, (Research Report No. 7906 (1979), Department of Applied Economics, Katholieke Universiteit Leuven: Department of Applied Economics, Katholieke Universiteit Leuven Belgium) |
| [6] | Cooper, D. F., Heuristics for scheduling resource-constrained projects: An experimental comparison, Management Science, 22, 1186-1194 (1976) · Zbl 0326.90029 |
| [7] | Davis, E. W., Project network summary measures and constrained resource scheduling, IIE Transactions, 7, 132-142 (1975) |
| [8] | Davies, E. M., An experimental investigation of resource allocation in multiactivity projects, Operational Research Quarterly, 24, 587-591 (1974) |
| [9] | Demeulemeester, E.; Herroelen, W., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management Science, 38, 1803-1818 (1992) · Zbl 0761.90059 |
| [10] | Demeulemeester, E.; Dodin, B.; Herroelen, W., A random activity network generator, Operations Research, 41, 972-980 (1993) · Zbl 0804.90049 |
| [11] | Demeulemeester, E.; Elmaghraby, S. E.; Herroelen, W., Optimal procedures for the discrete time/cost trade-off problem in project networks, (Research report No. 9337 (1993), Department of Applied Economics, Katholieke Universiteit Leuven: Department of Applied Economics, Katholieke Universiteit Leuven Belgium) · Zbl 0913.90168 |
| [12] | Demeulemeester, E.; Herroelen, W.; Simpson, W. P.; Baroum, S.; Patterson, J.; Yang, K., On a paper by Christofides et al. for solving the multiple-resource constrained, single project scheduling problem, European Journal of Operational Research, 76, 218-228 (1994) · Zbl 0811.90045 |
| [13] | Elmaghraby, S. E.; Herroelen, W., On the measurement of complexity in activity networks, European Journal of Operational Research, 5, 223-234 (1980) · Zbl 0444.90049 |
| [14] | Ford, L. R.; Fulkerson, D. R., Flows in Networks (1962), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0139.13701 |
| [15] | Harel, D., A linear time algorithm for finding dominators in flow graphs and related problems (extended abstract), (Proceedings 17th Annual ACM Symposium on Theory of Computing. Proceedings 17th Annual ACM Symposium on Theory of Computing, Providence, RI (1985)), 185-194 |
| [16] | Herroelen, W. S.; Demeulemeester, E. L., Recent advances in branch-and-bound procedures for resource-constrained project scheduling problems, (Chrétienne, P.; etal., Scheduling Theory and Its Applications (1995), Wiley: Wiley New York) · Zbl 0905.00086 |
| [17] | Hopcroft, J. E.; Karp, M., An \(n^{52}\) algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing, 2, 225-231 (1973) · Zbl 0266.05114 |
| [18] | Kaimann, R. A., Coefficient of network complexity, Management Science, 21, 172-177 (1974) · Zbl 0291.90032 |
| [19] | Kaimann, R. A., Coefficient of network complexity: Erratum, Management Science, 21, 1211-1212 (1975) · Zbl 0305.90020 |
| [20] | Kamburowski, J.; Michael, D. J.; Stallmann, M., Optimal construction of project activity networks, (Proceedings of the 1992 Annual Meeting of the Decision Sciences Institute. Proceedings of the 1992 Annual Meeting of the Decision Sciences Institute, San Francisco, CA (1992)), 1424-1426 |
| [21] | Kamburowski, J.; Michael, D. J.; Stallmann, M., On the minimum dummy-arc problem, Revue Française de Recherche Opérationelle, 27, 153-168 (1993) · Zbl 0774.90047 |
| [22] | Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems: Easy and hard instances, (Research report No. 301 (1992), Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel: Institut für Betriebswirtschaftslehre, Christian-Albrechts-Universität zu Kiel Germany) · Zbl 0870.90070 |
| [23] | Kurtulus, I. S.; Narula, S. C., Multi-project scheduling: Analysis of project performance, IIE Transactions, 17, 58-66 (1985) |
| [24] | Pascoe, T. L., Allocation of resources — CPM, Revue Française de Recherche Opérationelle, 38, 31-38 (1966) |
| [25] | Patterson, J. H., Project scheduling: The effects of problem structure on heuristic performance, Naval Research Logistics, 23, 95-123 (1976) · Zbl 0325.90027 |
| [26] | Patterson, J. H., A comparison of exact procedures for solving the multiple constrained resource project scheduling problem, Management Science, 30, 854-867 (1984) |
| [27] | Talbot, F. B., Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case, Management Science, 28, 1197-1210 (1982) · Zbl 0493.90042 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
