Article ID: | iaor19941727 |
Country: | United States |
Volume: | 41 |
Issue: | 5 |
Start Page Number: | 972 |
End Page Number: | 980 |
Publication Date: | Sep 1993 |
Journal: | Operations Research |
Authors: | Dodin B., Demeulemeester E., Herroelen W. |
Keywords: | networks: scheduling, heuristics |
Exact and heuristic procedures are often developed to obtain optimal and near-optimal solutions to decision problems modeled as activity networks. Testing the accuracy and efficiency of these procedures requires the use of activity networks with various sizes, structures, and parameters. The size of the network is determined by its number of nodes and arcs, where the structure is chosen from the set of all structures for the specified network size. The network parameters depend on the nature of the decision problem. Often, it is desirable for test problems to be generated at random from the space of all feasible networks. This paper deals with the problem of generating the size and structure of the network at random from the space of all feasible networks. It develops a theory which guarantees the randomness of the network structure. The theory is the basis for two methods. One can be used to generate dense networks, where the other is used to generate nondense networks. The methods, which are practical and easy to use, have been programmed for use on mainframe or personal computers. CPU time requirements are negligible. Copies of the computer program can be obtained from the authors.