A random generator of resource-constrained multi-project network problems
Tóm tắt
Many scheduling problems in project management, manufacturing, and elsewhere require the generation of activity networks to test proposed solution methods. Single-network generators have been used for the resource-constrained project scheduling problem (RCPSP). Since the first single-network generator was proposed in 1993, several advances have been reported in the literature. However, these generators create only one network or project at a time; they cannot generate multi-project problems to desired specifications. This paper presents the first multi-network problem generator. It is especially useful for investigating the resource-constrained multi-project scheduling problem (RCMPSP), where a controlled set of multi-project test problems is crucial for analyzing the performance of solution methods. In addition to the single-project characteristics handled by existing network generators—such as activity duration, resource types and usage, and network size, shape, and complexity—the proposed generator produces multi-project portfolios with controlled resource distributions and amounts of resource contention. To enable the generation of projects with desired levels of network complexity, we also develop several theoretical insights on the effects of network topology on the probability of successful network generation. Finally, we generate 12,320 test problems for a full-factorial experiment and use analysis of means to conclude that the generator produces “near-strongly random” problems. Fully “strongly random” problems require much greater computational expense.
Tài liệu tham khảo
Agrawal, M. K., Elmaghraby, S. E., & Herroelen, W. S. (1996). DAGEN: a generator of testsets for project activity nets. European Journal of Operational Research, 90(2), 376–382.
Alvarez-Valdés, R., & Tamarit, J. M. (1989). Heuristic algorithms for resource-constrained project scheduling: a review and an empirical analysis. In R. Slowinski & J. Weglarz (Eds.), Advances in project scheduling (pp. 113–134). New York: Elsevier.
Bein, W. W., Kamburowski, J., & Stallmann, M. F. M. (1992). Optimal reduction of two-terminal directed acyclic graphs. SIAM Journal on Computing, 21(6), 1112–1129.
Browning, T. R., & Yassine, A. A. (2009). Resource-constrained multi-project scheduling: priority rule performance revisited. TCU Neeley School of Business, Working Paper.
Dar-El, E. M. (1973). MALB—a heuristic technique for balancing large single-model assembly lines. AIIE Transactions, 5(4), 343–356.
Davis, E. W. (1975). Project network summary measures and constrained resource scheduling. IIE Transactions, 7(2), 132–142.
Davis, E. W., & Patterson, J. H. (1975). A comparison of heuristic and optimum solutions in resource-constrained project scheduling. Management Science, 21(8), 944–955.
De Reyck, B., & Herroelen, W. (1996). On the use of the complexity index as a measure of complexity in activity networks. European Journal of Operational Research, 91(2), 347–366.
Demeulemeester, E., Dodin, B., & Herroelen, W. (1993). A random activity network generator. Operations Research, 41(5), 972–980.
Demeulemeester, E., & Herroelen, W. (1992). A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Management Science, 38(12), 1803–1818.
Demeulemeester, E., Vanhoucke, M., & Herroelen, W. (2003). A random network generator for activity-on-the-node networks. Journal of Scheduling, 6(1), 13–34.
Elmaghraby, S. E. (1977). Activity networks: project planning and control by network models. New York: Wiley.
Elmaghraby, S. E., & Herroelen, W. S. (1980). On the measurement of complexity in activity networks. European Journal of Operational Research, 5(4), 223–234.
Gutiérrez, M., Durán, A., Alegre, D., & Sastrón, F. (2004). Hiergen: a computer tool for the generation of activity-on-the-node hierarchical project networks. In Proceedings of the computational science and its applications—ICCSA, Part III, Assisi, Italy (pp. 857–866).
Haberle, K., Burke, R., & Graves, R. (2000). A note on measuring parallelism in concurrent engineering. International Journal of Production Research, 38(8), 1947–1952.
Hartmann, S., & Kolisch, R. (2000). Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 127(2), 394–407.
Johnson, T. J. R. (1967). An algorithm for the resource-constrained project scheduling problem. PhD thesis, MIT.
Kaimann, R. A. (1974). Coefficient of network complexity. Management Science, 21(2), 172–177.
Kaimann, R. A. (1975). Coefficient of network complexity: erratum. Management Science, 21(10), 1211–1212.
Kao, E. P. C., & Queranne, M. (1982). On dynamic programming methods for assembly line balancing. Operations Research, 30(22), 375–390.
Kolisch, R., Sprecher, A., & Drexl, A. (1992). Characterization and generation of a general class of resource-constrained project scheduling problems. Kiel, Germany.
Kolisch, R., Sprecher, A., & Drexl, A. (1995). Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science, 41(10), 1693–1703.
Kurtulus, I., & Davis, E. W. (1982). Multi-project scheduling: categorization of heuristic rules performance. Management Science, 28(2), 161–172.
Kurtulus, I. S., & Narula, S. C. (1985). Multi-project scheduling: analysis of project performance. IIE Transactions, 17(1), 58–65.
Liberatore, M. J., & Pollack-Johnson, B. (2003). Factors influencing the usage and selection of project management software. IEEE Transactions on Engineering Management, 50(2), 164–174.
Lova, A., & Tormos, P. (2001). Analysis of scheduling schemes and heuristic rules performance in resource-constrained multi-project scheduling. Annals of Operations Research, 102(1–4), 263–286.
Maroto, C., Tormos, P., & Lova, A. (1999). The evolution of software quality in project scheduling. In J. Weglarz (Ed.), Project scheduling: recent models, algorithms and applications (pp. 239–259). Boston: Kluwer Academic.
Mastor, A. A. (1970). An experimental and comparative evaluation of production line balancing techniques. Management Science, 16(22), 728–746.
Pascoe, T. L. (1966). Allocation of resources—CPM. Revue Française de Recherche Opérationelle, 38, 31–38.
Patterson, J. H. (1976). Project scheduling: the effects of problem structure on heuristic performance. Naval Research Logistics, 23(1), 95–123.
Patterson, J. H. (1984). A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem. Management Science, 30(7), 854–867.
Payne, J. H. (1995). Management of multiple simultaneous projects: a state-of-the-art review. International Journal of Project Management, 13(3), 163–168.
Schwindt, C. (1995). A new problem generator for different resource-constrained project scheduling problems with minimal and maximal time lags. Institut für Wirtschaftstheorie und Operations Research, Universität Karlsruhe, WIOR-Report-449.
Schwindt, C. (1996). Generation of resource-constrained project scheduling problems with minimal and maximal time lags. Institut für Wirtschaftstheorie und Operations Research, Universität Karlsruhe, Report WIOR-Report-489.
Schwindt, C. (1998). Generation of resource-constrained project scheduling problems subject to temporal constraints. Institut für Wirtschaftstheorie und Operations Research, Universität Karlsruhe, Report WIOR-543.
Tavares, L. V. (1998). Advanced models for project management. Boston: Kluwer Academic.
Tavares, L. V., Ferreira, J. A., & Coelho, J. S. (1999). The risk of delay of a project in terms of the morphology of its network. European Journal of Operational Research, 119(2), 510–537.
Temperley, H. M. (1976). Graph theory and applications. Chichester: Ellis Horwood.
Thesen, A. (1977). Measures of the restrictiveness of project networks. Networks, 7, 193–208.
Vanhoucke, M., Coelho, J., Debels, D., & Tavares, L. V. (2004). On the morphological structure of a network. Vlerick Leuven Gent Management School, Working Paper no. 2004/9.