New Approach to Teaching Discrete Event System Simulation

A. M. Zikic¹ and B. Lj. Radenkovic^2
1 Department of Electronics Engineering and Physics, Electronics Division, University of Paisley, Paisley, PA1 2BE, Scotland
Tel. 44 141 848 3414,
Fax 44 141 848 3404,
Email ziki-ee0@wpmail.paisley.ac.uk
² Faculty of Organisational Sciences, University of Belgrade, 11000 Belgrade, Jove Ilica 154, Yugoslavia

The paper presents a different way of teaching discrete event system simulation. A completely new language, ISDS, based on GPSS concepts but with interactive user interface and Pascal like syntax with many other new features was developed as the teaching tool. The main purpose of this simulation system is to enable a cheap and easy learning and practising environment, particularly suited for students of engineering. In addition to the language definition, it's implementation and the user interface description, we also present a comparison of ISDS to GPSS and PASSIM and performance comparison between ISDS and GPSS/FON in teaching simulation. Finally, our experience in teaching simulation using ISDS is illustrated with an example of students’ exercise that compares favourably with a previously published work.

KEY WORDS : Discrete event simulation, simulation languages, interactive environment.

1. INTRODUCTION

The discrete event system theory, simulation and practice are covered in many books and articles in scientific journals and started appearing even in IEEE publications on control systems. The reader of this paper can find a brief summary of discrete event system theory in [1]. After many years of teaching the discrete event system simulation we monitored students progress in learning the concepts of GPSS and GPSS/FON [1,2,3] as well as the average time needed to accept an entirely new approach to programming. Our findings can be summarised as:

a) Students learn programming based on Pascal and C concepts that employ very strict and explicit typing of variables and objects.

b) On the other hand, GPSS does not have either the explicit declaration or strict typing of variables but uses a mixture of implicit and explicit of both.

c) A structured approach to programming developed by using Pascal as the main programming language becomes the second nature to students long before we attempt to teach them the discrete event simulation.

d) GPSS syntax is of assembler type with many labels and transfer block statements. At the time of its creation, the structured approach to programming was non existent and its structure is very similar to that of the contemporary languages.

It is obvious from above that our findings summarised in a) and c) are in an irreconcilable conflict with those in b) and d). There was, therefore, no doubt in our mind that the GPSS syntax and structure posed a great impediment in learning discrete event system simulation to all those who had any pre-knowledge of modern programming techniques and concepts. In order to improve the students response to our teaching efforts, we decided to write an entirely new language that would satisfy the following requirements:

1. Cheap and affordable for an average student's home practising
2. Language syntax with strictly divided specification of the model database, model structure and control of the simulation process
3. Interactive environment with resident editor, processor and result analyser
4. Fast and easy model debugging

Before an attempt was made to write a rather pretentious package that would meet the above requirements, we decided to investigate simulation systems other than GPSS, available at the time. One of affordable solutions was Passim, [4,5]. It imbeds GPSS statements in a standard Pascal program and uses the pre-processor to generate the Pascal source. However, the main disadvantage of this solution is a necessity of the Pascal compiler. Second disadvantage is a fairly complicated debugging process for an inexperienced user. As even the most affordable package did not satisfy all our criteria we adventured into development of an Interactive System for Discrete-event System simulation (ISDS) as a joint research project of the Department of Organisational Sciences, University of Belgrade and the Department of Electronic Engineering and Physics, University of Paisley. The main requirement was to develop a simulation language with concepts similar to those of GPSS but with a small and concise kernel of syntax rules that would satisfy the following requirements:

1. Strict label, constants and entity declarations
2. model definitions with block statements, assign statements, wait-until and logical branch statements
3. input-output statements for interactive simulation and graphical result presentation
4. a set of control statement that supports interactive environment.

2. ISDS LANGUAGE SYNTAX and SEMANTICS

When we started writing the syntax rules of the new language, it occurred to us that our graduates will have to use GPSS or some other commercially available system, rather then our ISDS. Thus whenever possible, we tried to retain the GPSS instruction names. Those instructions that are different in ISDS are either non existent in GPSS or cause confusion in a novice's mind while using the latter. Modern concepts of compiler design 'demand' a single pass compilation which, on the other hand, means that the left recursion and backtracking must be strictly avoided. Thus, we adopted the recursive descent method for our syntax analyser which in return defined the global syntax structure of ISDS. The complete language definition in EBNF is given in [6]. We present here only a short description of the language syntax, given in Figure 1. In addition, a number of pre-defined functions that define usual statistical distributions is readily available to the user. The Semantics of typical ISDS statements is shown in Table 1.

3. COMPARISON of ISDS to GPSS, PASSIM and SIMAN/CINEMA

Our knowledge of and the experience in using SIMAN/CINEMA is fairly limited compared to that of PASSIM and various GPSS dialects, including our own [1], as neither of our institutions runs a copy of that language. Thus, our comparison of ISDS to SIMAN/CINEMA will be equally limited and is based on our experience through occasional access that we were granted by the licensed institutions.

Unlike GPSS, ISDS possesses a strictly formal syntax definition and checking if operands are of permissible type for a given function. Also, a very useful feature is introduced through the conditional branching instruction set IF-THEN-ELSE-CASE that allow the nesting of program segments in a clear and easy-to-follow manner. Like GPSS and SIMAN/CINEMA, ISDS possesses the block oriented syntax structure in its processing of process interactions, but unlike the two it also has a facility of abstracting many instructions into a compound statement that makes the branching instructions much easier to use, follow and debug.

Unlike in GPSS, all static entities like FACILITY, LOGIC SWITCH, SAVE VALUE, etc. must be explicitly defined in a separate program segment and cannot be used unless previously defined. Thus, those errors due to a wrong implicit specification that may (as well as no) become obvious at the GPSS program execution are fully eliminated in ISDS and are reported at the compilation stage as non-defines. The ability of ISDS to compound statements and accept only explicitly defined static entities enables a trainee to make fewer mistakes in modelling a system than in either GPSS or SIMAN/CINEMA.

Although the PASSIM enables both Pascal and GPSS structures to appear in the same program, thus ‘marrying the best of the two worlds’, it still lacks several properties of ISDS:

1. Firstly, a PASSIM user should be reasonably fluent in both GPSS and Pascal which is not necessary in the case of ISDS; indeed, many of our re-training course attendants are not fluent in either and do not normally require any knowledge of Pascal for their present and/or future work.
2. Secondly, not all of the GPSS shortcomings are eliminated by the availability of Pascal code whereas practically all of them are in ISDS.
3. The user of PASSIM must have a Pascal compiler whereas an ISDS user does not require any additional piece of software other than the operating system.
4. An ISDS user has to debug only one language structure and not possibly two entirely different ones as a PASSIM user may.

4. ISDS PROCESSOR

The syntax analyser is designed by using a recursive descent method which translates the model into an internal representation, in a single phase. The internal representation of the model consists of two main parts:

1. Handling of transactions as dynamic entities. It includes

a) Transactions
b) transaction chains

2. Static entities- blocks, storages, queues etc.

a) Tables of permanent entities
b) Tables of statements
c) Other global variables

Transaction handling mechanism consist of two linked lists: Current Event Chain (CEC) and Future Event Chain (FEC) and procedures for transaction manipulation. In the execution phase, the processor prepares the simulation process as the 'next event strategy', by using a data base consisting of the model structure and its parameters [7]. The implementation was realised by using Turbo Pascal language and its object oriented libraries.

5. STATISTICAL DATA ACQUISITION

The user must build his/her own set of control statements that depend on model structure. ISDS has facilities for collecting statistical data during run time, similar to those of GPSS. The standard numerical attributes, assign statements, input/output and control statements permit custom designed data collection. The computation of the statistical parameters is performed by using standard recursive techniques. The main advantage in using the recursive technique is that only a simple database, consisting of two values, has to be updated in each pass. The statistical data related to permanent entities such as Storage, Facility, Queue and User Chain are obtained by using the well known statistical formulae.

The determination of the statistical values is performed when either a transaction and the entity meet or when a transaction leaves the entity. The actual evaluation is done by the appropriate block procedures as specified above. Some block procedures (Generate, Advance and Transfer) use three internal random number generators for computing their operand values. In this implementation of ISDS we use a linear multiplicative congruent pseudo random number generator, [8].

 6. USER INTERFACE

The user interface is built in accordance with prepositions given in [9], using object oriented approach. The communications among parts of the environment are realised through an event driven mechanism. The latter, named 'dialogue acceptor', detects every change in the state of environment and performs a task chosen by the user, such as the screen editor, operating system interface, simulator and the simulation result analyser.

ISDS interactive environment can be formally described by using the discrete event formalism

IE = < IES, IM, OM,s, o>

where:

IE - Integrated environmentd

IES - Integrated environment states comprising the finite set

{Idle,
edit =<file-1, file-2,...,file-n>,
compile <file-1, file-2,...,file-n>,
simulate,
analyse =<statistical, graphical>,
utility =<Chdir, Dos_shell> }

IM - Input messages consisting of either keyboard or mouse motion sequences.

OM - Output messages consisting of various comments, warnings and error messages.

s - State functions s : IES x IM => IES

The event scheduler suspends the currently executed task several times per second and checks for input messages; if no input message is detected, the execution of the suspended task is resumed. 

o - Output functions o : IES x IM => OM

The Output messages scheduler is triggered by either an input message or the currently executed task.

 

The number of files that can be edited or compiled simultaneously is limited by the available memory. The system operates as a quasi multitasking system; each state can be temporarily frozen in favour of some other one and reassumed latter. There is, however, no background execution of any suspended tasks.

The integrated environment provides a quick and comfortable means of system modelling, simulation and data analysis. In addition, the utility option enables a quick access to the operating system utilities. A typical control screen of the IE is shown in Fig 2.

 7. EXAMPLE

A similar model to the one published in [1] is used, for comparison reasons, to illustrate the language:

Write the simulation model by using the following experimental data: Maximum number of customers in the shop is 40 at any time; currently, the manager runs the shop with 20 baskets only and virtually no queuing at the tills. There are two standard tills for any number of items and one express till for up to 5 items. Shoppers arrive at average time intervals of one minute with exponential distribution. A shopper buys 20 items in average. If baskets are not available, a shopper leaves the shop (a lost customer). The shop opens at 9.00h and closes at 18.00h.

Figure 3 presents one of the solutions submitted by students. Figure 4 shows the queue length at standard tills. Additional analysis identical to the one in [1], including 3D plots, can be also performed and is not included in this paper for obvious reasons.

 8. ISDS PERFORMANCE METRICS

As soon as the 'zeroth' version of ISDS was finished and debugged back in 1991, as reported in [10], it was introduced in our teaching program. During the following academic year, we monitored the students progress in accepting the new language and the merits of ISDS; both results were compared to those based on and accumulated over many years of GPSS practice. Encouraged by our preliminary findings we spent the following two years in accumulating relevant statistical data regarding the ISDS merits. The experiment was conducted by using two groups of students having similar learning and programming skills; the criterion used to form the groups was based on the past performance obtained from the Students’ Record Department and a personal view of the relevant lecturers. The most ‘talented’ representatives from either group were used to form the "Pascal control" group. Each of the main groups consisted of at least forty students and the Pascal control group consisted of ten students irrespective of the main group sizes. One of the main groups was taught discrete event simulation by using ISDS and the other, the control group, covered the identical syllabus in GPSS/FON. GPSS/FON rather than the standard form was used in this assessment so as to eliminate the clear advantage that the ISDS’s interactive environment would have over the standard implementation of GPSS. The Pascal control group was taught, in addition to its respective language, the event presentation, event chain management and other simulation concepts in Pascal.

We measured the following parameters:

- Time needed to understand basic concepts
- Time needed to develop a simulation model
- Duration of the simulation process
- Ease of the simulation results analysis

8.1 Evaluation Criteria

A weighting factor, based on the following criteria was assigned to each student, irrespective of the group

1. Average mark a_t taken over all previous subjects (6 £ n £ 10)
2. Average mark a_r taken separately over relevant subject like mathematics and programming (6 £ n £ 10)
3. Relevant subject lecturers’ ranking a_l from 1 to 10

A set of individual weights are assigned to each of the contributing factors; the assigned values are based on the principle of importance and objectivity; for this purpose, the highest weight is assigned to relevant subjects and the lowest to the least objective, but still very important, lecturers’ ranking. The weighting factor, w, is then calculated as

w = 0.35 a_t + 0.45 a_r + 0.2 a_l

It is assumed that a higher scoring individual needs less time to complete the same task then the lower scoring one. The time, in hours, needed to complete each of the 10 stages of the syllabus was multiplied by the weighting factor and the average time was then evaluated over the group size. The Pascal control group performance, based on the same criteria, was compared to the respective students’ performance in their main groups. Our analysis shows that there is no significant difference in understanding the basic concepts of ISDS and GPSS. This result showed us that our criteria in the statistical analysis are very likely to be correct; as GPSS and ISDS share the same basic concepts, any other result would indicate a serious fault in our assessment strategy. As we hoped for, our further analysis showed that translation of the basic concepts into the respective codes took between 45-60% less time to the ISDS group than to the GPSS/FON group when writing models for identical exercises. Finally, the Pascal control group needed 300-400% more time to understand basic event scheduling concepts in Pascal.

The analysis shows that ISDS, compared to GPSS/FON, is

30% - 60% simpler at the model-specification stage
40% - 60% faster at the compilation/debug stage
10% - 20% faster at the execution stage
3 - 5 times easier to use at the model testing stage

The limiting values of the model-specification and compilation performance intervals (say 40% - 60%) are determined so that 95% of all students’ weighted performances fall below the average performance of the control group and that the mode and average values are both within the stated limits referenced to the control average. The actual statistical distribution of performances, shown in Figure 5, is of Log-normal type and is fitted to the experimental data by using the strategy described in [11]. The ISDS performance distribution is described by the standard deviation of s =0.3 and the geometric mean of b=22. The GPSS performance distribution is described by the standard deviation of 0.44 and the geometric mean of 36.44. By using these parameters, the average values are easily obtained, using E[X]=b×exp(s ²/2) [11], and are 23 and 39.66 for ISDS and GPSS distributions, respectively. The location parameters of both distributions are negative and negligibly different than zero. It is easily verifiable from Figure 5 that more than 95% of all students in ISDS group fall below the 40 hour average of the control group and that the mode of 20 and average of 23 also fall between 40% (16) and 60% (24) of the same control average.

9. CONCLUSION

This paper has a goal to demonstrate the capabilities of ISDS language in teaching simulation of discrete event systems. ISDS has a number of features which help novices in descrete event system ‘environment’ to start modelling very quickly. Our experience shows that once the new programming concepts are accepted it is a matter of days rather than weeks that takes an ISDS trainee to become GPSS, or in that matter any similar language, programmer. A typical example of the mini-market model, superficially different from the one published in [1], illustrated the usage of ISDS language and if compared to the almost equivalent GPSS/FON one in [1] shows the strength and simplicity of the proposed system. Finally, the comparison results between ISDS and GPSS/FON performances and the comparison of the former to GPSS, SIMAN/CINEMA and PASSIM show the superiority of ISDS in teaching discrete event system simulation. Based on these positive results we adopt ISDS from this academic year as the only teaching tool.

Our professional application, on the other hand, proved that ISDS is not only more powerful than GPSS in teaching simulation but that it also proves to be a more comfortable and faster environment for serious applications. For future improvements of ISDS, we plan to include a graphical tool for the model specification phase. The current version of the ISDS, 3.15 at present, is available on request for teaching and research purposes only.

REFERENCES

1. A. M. Zikic and B. Lj. Radenkovic, Applications of GPSS/FON in teaching simulation, Int. J. Engng. Ed., 8,5,355-366 (1992)
   
2. B. Lj. Radenkovic and A. Markovic, An Application of GPSS/FON Language in Teaching Simulation at the University of Belgrade, Proc. of SCS Western Simulation Multiconference, Newport Beach, California (1992)
   
3. A. M. Zikic and B. Lj. Radenkovic, A fully portable implementation of GPSS language on 8 and 16 bits microprocessors, Proc. of the 7th System engineering conference, Las Vegas, Nevada, pp. 773-779 (1990)
   
4. D. H. Ueno and W. Vaessen, PASSIM: A Discrete-Event Simulation Package for Pascal, Simulation, 35, 6 (1980)
   
5. C. C. Barnett, Micro Passim: A Discrete-Event Simulation Package for a Microcomputers Using UCSD Pascal, in L.A.Leventhal(ed.), Modelling and Simulation on Microcomputers, The Society of Computer Simulation, La Jolla, California (1982)
   
6. B. Lj. Radenkovic, Interactive Simulation System for Discrete-stochastic Simulation and it's Implementation on Mini and Micro computers, Ph.D. Thesis, University of Belgrade, Yugoslavia (1989)
   
7. T. J. Schriber, Simulation Using GPSS, John Wiley and Sons, New York (1974)
   
8. G. S. Fishman, Principles of discrete event simulation, Wiley Interscience, New York (1978)
   
9. J. O. Hernriksen, The Integrated Simulation Environment, Operations Research, 31, 6 (1983)
   
10. A. M. Zikic and B. Lj. Radenkovic, Interactive Simulation System ISDS - Definition of a new Language, Proc 8^th Int. Conf. on Sys. Engr., Coventry, pp.260-266 (1991)
    
11. A. M. Zikic, R. I. Ristic and J. N. Sherwood, Three Parameter Distribution Function fit to Growth Rate Dispersion Among Small Crystals, Journal of Crystal Growth, 158, pp. 560-567 (1996)

CAPTIONS to FIGURES

Figure 1 Brief format of the ISDS language syntax

Figure 2 A typical Interactive Environment screen of the ISDS system

Figure 3 A sample of ISDS program simulating a mini market (see text for details)

Figure 4 A histogram produced by the ISDS graphical result-analysis tool

Figure 5 Performance statistics of ISDS and GPSS groups at the compilation/debug stage

Table 1 Semantics of the most important ISDS instructions