Redundancy in model specifications for discrete event simulation

ABSTRACT

Although redundancy in model specification generally has negative connotations, we offer arguments for revising those convictions. Defining “representational redundancy” as the inclusion of any symbols not required to fulfill the study objectives, we cite several sources of redundancy, classified as accidental or intentional, that contribute positively to the model development tasks. Comparative benefits and detriments are discussed briefly. Focusing on the most interesting source of redundancy‐that which is intentionally induced by a modeling methodology—we demonstrate that automated elimination of redundancy can actually improve model execution time. Using four models drawn from the literature that are easily understood, but which represent some differences in size and complexity, the direct graphical representations shows improvements over a base case ranging from 27.3 percent to 68.1 percent in execution time. Further, increasing improvement is realized with increasing model size and complexity. These results are encouraging because they suggest that modeling methodologies with automated model diagnosis can significantly reduce both execution and developments time and cost.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Osman Balci, The implementation of four conceptual frameworks for simulation modeling in high-level languages, Proceedings of the 20th conference on Winter simulation, p.287-295, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318204]
• 3: BARGER, L. F. 1986. The model generator: A tool for simulation model definition, specification, and documentation. Master's Thesis. Department of Computer Science, Virginia Tech, Blacksburg, VA.
• 4: BUXTON, g. N. AND LASKI, g. G. 1963. Control and simulation language. Comput. J. 5, 194-199.
• 5: Bruce A. Cota , Robert G. Sargent, Simultaneous events and distributed simulation, Proceedings of the 22nd conference on Winter simulation, p.436-440, December 09-12, 1990, New Orleans, Louisiana, United States
• 6: Cox, D. R. AND SMITH, W. L. 1961. Queues. Methuen and Co., Ltd., London, England.
• 7: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 8: FISHMAN, G. S. 1973. Concepts and Methods in Discrete Event Digital Simulation. John Wiley and Sons, Inc., New York, NY.
• 9: GURALNIK, D. B., Ed. 1980. Webster's New World Dictionary. William Collins Publishers, Inc., Cleveland, Ohio.
• 10: HANSEN, R. H. 1984. The model generator: A crucial element of the model development environment. Technical Report CS84008-R. Department of Computer Science, Virginia Tech, Blacksburg, VA.
• 11: Charles Antony Richard Hoare, The emperor's old clothes, Communications of the ACM, v.24 n.2, p.75-83, Feb. 1981 [doi>10.1145/358549.358561]
• 12: LACKNER, M. R. 1964. Digital simulation and system theory. Technical Report SDC SP-12. System Development Corporation, Santa Monica, CA.
• 13: NANCE, R. E. 1971. On time flow mechanisms for discrete system simulation. Manage. Sci. 18, 1 (Sept.), 59-73.
• 14: Richard E. Nance, The time and state relationships in simulation modeling, Communications of the ACM, v.24 n.4, p.173-179, April 1981 [doi>10.1145/358598.358601]
• 15: Richard E. Nance, A tutorial view of simulation model development, Proceedings of the 15th conference on Winter simulation, p.325-332, December 12-14, 1983, Arlington, Virginia, United States
• 16: NANCE, R. E. 1994. The conical methodology and the evolution of simulation model development. Ann. Oper. Res., 1-45.
• 17: Richard E. Nance , James D. Arthur, The methodology roles in the realization of a model development environment, Proceedings of the 20th conference on Winter simulation, p.220-225, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318192]
• 18: NANCE, R. E. AND OVERSTREET, C. M. 1987a. Diagnostic assistance using digraph representations of discrete event simulation model specifications. Trans. Soc. Comput. Simul. 4, 1 (Jan.), 33-57.
• 19: Richard E. Nance , C. Michael Overstreet, Exploring the forms of model diagnosis in a simulation support environment, Proceedings of the 19th conference on Winter simulation, p.590-596, December 14-16, 1987, Atlanta, Georgia, United States [doi>10.1145/318371.318669]
• 20: Charles Michael Overstreet, Model specification and analysis for discrete event simulation, 1982
• 21: C Michael Overstreet , Richard E. Nance, A specification language to assist in analysis of discrete event simulation models, Communications of the ACM, v.28 n.2, p.190-201, Feb. 1985 [doi>10.1145/2786.2792]
• 22: OVERSTREET, C. M. AND NANCE, R. E. 1986. World view based discrete event model simplification. In Modelling and Simulation Methodology in the Artificial Intelligence Era Elsevier Sci. Pub. B. V., Amsterdam, The Netherlands, 165-179.
• 23: C. Michael Overstreet , Ernest H. Page , Richard E. Nance, Model diagnosis using the condition specification: from conceptualization to implementation, Proceedings of the 26th conference on Winter simulation, p.566-573, December 11-14, 1994, Orlando, Florida, United States
• 24: PAGE, E. H. 1990. Model generators: Prototyping simulation model definition, specification, and documentation under the conical methodology. Master's Thesis. Department of Computer Science, Virginia Tech, Blacksburg, VA.
• 25: Ernest H. Page, The condition specification: revisiting its role within a hierarchy of simulation model specifications, ACM SIGSIM Simulation Digest, v.22 n.3, p.11-33, March, 1993 [doi>10.1145/165347.165351]
• 26: Ernest H. Page, Jr. , Richard E. Nance, Simulation modeling methodology: principles and etiology of decision support, 1995
• 27: Ernest H. Page , Richard E. Nance, Incorporating support for model execution within the condition specification, Transactions of the Society for Computer Simulation International, v.16 n.2, p.47-62, June 1999
• 28: PUTHOFF, F.A. 1990. The automatic simplification of the action cluster incidence graph: An expert system approach. Tech. Rep.. Department of Computer Science, Virginia Tech, Blacksburg, VA.
• 29: PUTHOFF, F.A. 1991. The model analyzer: Prototyping the diagnosis of discrete-event simulation model specification. Master's Thesis. Department of Computer Science, Virginia Tech, Blacksburg, VA.
• 30: Thomas J. Schriber, An introduction to simulation using GPSS/H, John Wiley & Sons, Inc., New York, NY, 1991
• 31: Lee Schruben, Simulation modeling with event graphs, Communications of the ACM, v.26 n.11, p.957-963, Nov. 1983 [doi>10.1145/182.358460]
• 32: SOM, T. K. AND SARGENT, R. G. 1989. A formal development of event graphs as an aid to structured and efficient simulation programs. ORSA J. Comput. 1, 2, 107-125.
• 33: K. D Tocher, The art of simulation, English Universities Press, 1967
• 34: Jack C. Wallace, The control and transformation metric: toward the measurement of simulation model complexity, Proceedings of the 19th conference on Winter simulation, p.597-603, December 14-16, 1987, Atlanta, Georgia, United States [doi>10.1145/318371.318670]
• 35: Enver Yücesan , Lee Schruben, Structural and behavioral equivalence of simulation models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.2 n.1, p.82-103, Jan. 1992 [doi>10.1145/132277.132281]
• 36: Bernard P. Zeigler, Theory of Modelling and Simulation, Krieger Publishing Co., Inc., Melbourne, FL, 1984
• 37: Bernard P. Zeigler, Multifacetted modelling and discrete event simulation, Academic Press Professional, Inc., San Diego, CA, 1984

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures; Complexity measures

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
  I.6 SIMULATION AND MODELING
      I.6.7 Simulation Support Systems
          Subjects: Environments
      I.6.8 Types of Simulation
          Subjects: Discrete event

General Terms:
Design, Measurement, Performance

Keywords:
discrete event simulation, model analysis, model development environment, uses of redundancy