CIS 307: Solution to Homework 1

We are required to do a discrete event simulation of a system representing a pediatrician's office. The system consists of two SERVERS or service providers - a nurse and a pediatrician, and a set of CLIENTS representing patients waiting for or receiving treatment from the pediatrician and the nurse. Patients are classified into three categories - those who see the nurse alone, those who see only the pediatrician, and those who receive treatment from both the nurse and the pediatrician.
The STATUS of a server at an instant is "busy" if there is a patient receiving treatment from the server at that instant, and "free" otherwise. A patient arriving at a server starts receiving treatment immediately if the server is free, and enters a FIFO queue for the server if the server is busy. A STATE of the system is a snapshot of the system that captures information relevant to the activities of the system at an instant in time. The state includes the status of each server and the contents of their queues. An EVENT in a system is an action that causes the system to undergo a change of state. For example, the arrival of a patient at the nurse is an event in the system as it changes either the status of the nurse or the contents of his queue. Such an event may be referred to as an "arrival event". Clearly the arrival of any patient at the nurse is an arrival event. An EVENT TYPE represents a set of events of the same kind. Individual events from the same event type are referred to as INSTANCES of that type. Thus every event instance has two attributes - a type that it belongs to, and a time of occurrence. In what follows we shall use the term event to denote an instance of a type whenever the type is implicit, or while referring to an arbitrary instance of an arbitrary type.

The following are the types of events that occur in the system representing a pediatrician's office :

1. Arrival of a patient into the system. This represents arrivals at the nurse, and arrivals of patients who see ONLY the pediatrician.

2. Completion of treatment of a patient by the nurse.

3. Completion of treatment of a patient by the pediatrician.

Whenever an event occurs the system undergoes a state transition and enters a state determined completely by the TYPE of the event and the state of the system at the time of occurrence of the event. The simulation process consists in tracing the state transitions the system undergoes in chronological order from a given initial state at the start of the simulation and terminating at the end of the simulation period. We construct the sequence of state transitions or the equivalent sequence of events from our knowledge of the initial condition and behaviour of the system, and the pattern of arrival of patients into the system.

The chronological sequence of events can be generated if

1. The type and time of occurrence of the first event are known, and
2. Immediately following the occurrence of each event, the type and time of occurrence of its successor event in the sequence can be determined.

Arrival events are fundamental to the system as they give rise to subsequent completion events. Since the time between successive arrivals is uniformly distributed in the interval AMIN .. AMAX, we may use a random number generator to approximate the distribution and determine the temporal separation of successive arrival events. When a patient arrives at a server the time at which the patient would leave the server can be computed if the server is not busy since the service times are also uniformly distributed random variables. Thus the completion event corresponding to an arrival can be completely determined at the time of the arrival if the server is free and there are no patients waiting for the server at that time. Otherwise the arriving patient enters the queue for the server. The patient leaves the queue to receive treatment when the patient ahead of him leaves the server, at which time we may compute the time of completion of treatment for the patient as described above. Thus the completion event corresponding to an arrival can be determined either at the time of the arival or when some completion event of the same type occurs at a later point in time. From the above observations it follows that the sequence of events can be constructed if the time of occurrence of the first arrival is known.

We assume that the servers are free and their queues are empty at the start of the simulation. For the sake of simplicity we also assume that the first arrival coincides with the start of the simulation.

Data Structures for the algorithm

We use the following data types and structures to facilitate the description of the simulation algorithm. The definition of the data types and the algorithm are presented in a Pascal-like language.

type

 EventType   = (Arrival,Completion_N,Completion_P,Termination)
 PatientType = (N_Patient,P_Patient,NP_Patient)

 PatientInfoType = record 
                      PatientId : integer
 		      PatientKind : PatientType
		      ArrivalSystem : Real
		      ArrivalPediatrician : Real
		   end 

 EventNode = record 
		EventKind : EventType
		EventTime : Real
		PatientInfo : PatientInfoType
		Next : Pointer to EventNode
	     end

 EventQueueType = record 
		     First, Last : Pointer to EventNode
		  end

 ServerQueueType = record
		      First, Last : Pointer to EventNode
		      SIze : Integer
		      LastUpdate : Real
		   end

 VAR 
   EventQ : EventQueueType
   QUEUE1, QUEUE2 : ServerQueueType

We assume that the operations CreateqFQ, InsertqFQ, DeleteqFQ, and IsemptyqFQ for the abstract data type FIFO queue, and their counterparts CreateqPQ, InsertqPQ, DeleteqPQ, and IsemptyqPQ for the abstract data type priority queue are already defined.

The algorithm also invokes the function PickRandom

     FUNCTION PickRandom(Low, High : Real):Real;

that returns a random number between Low and High. PickRandom uses one of the built-in random number generators like random() or rand().

Now we state the algorithm in toto.

Algorithm Doctor'sOfficeSimulation
BEGIN
 Read and validate input;
 Initialize EventQ with the first Arrival and Termination events;
 Initialize QUEUE1 and QUEUE2 to be empty;
 NurseBusy := False;
 PediatricianBusy := False;
 REPEAT
   CurrentEvent := DeleteqPQ(EventQ);
   CurrentTime := CurrentEvent.EventTime;
   CASE CurrentEvent.EventKind OF 
   
     Arrival : Log event in the log file;
               Call CreateNextArrival(EventQ,CurrentTime,AMIN,AMAX,R1,R2);
               IF this is a P_Patient THEN 
               BEGIN
		 IF PediatricianBusy Then 
		 BEGIN 
		   InsertqFQ(QUEUE2,CurrentEvent);
                   Update QUEUE2 size stats
		 end
                 else { pediatrician is not busy }
                 begin
		   Transform CurrentEvent into a Completion_P event 
		     occurring at CurrentTime + PickRandom(S2MIN,S2MAX);
		   PediatricianBusy := true;
		   PediatricianBusyFrom := CurrentTime;
		   InsertqPQ(EventQ,CurrentEvent);
		 end
	       end
	       else { N_Patient or NP_Patient }
	       begin
		 if NurseBusy then 
		 begin 
		   InsertqFQ(QUEUE1,CurrentEvent);
                   Update QUEUE1 size stats
		 end
                 else { nurse is not busy }
                 begin
		   Transform CurrentEvent into a Completion_N event 
		     occurring at CurrentTime + PickRandom(S1MIN,S1MAX);
		   NurseBusy := true;
		   NurseBusyFrom := CurrentTime;
		   InsertqPQ(EventQ,CurrentEvent);
		 end
	       end

     Completion_N : Log event in the log file;
		    Compute response time for nurse, update stats;
		    IF this is an N_Patient THEN 
		    BEGIN
		      Update response stats for N_Patients;
		      IF IsemptyqFQ(QUEUE1) THEN 
			NurseBusy := FALSE
		      ELSE
		      BEGIN 
			CurrentEvent := DeleteqFQ(QUEUE1);
			Update QUEUE1 size stats;
		        Transform CurrentEvent into a Completion_N event 
		          occurring at CurrentTime + PickRandom(S1MIN,S1MAX);
		        NurseBusy := true;
		        NurseBusyFrom := CurrentTime;
		        InsertqPQ(EventQ,CurrentEvent);
		      END
		    END
		    ELSE { NP_Patient }
		    BEGIN
                      CurrentEvent.PatientInfo.ArrivalPediatrician 
                                                          := CurrentTime; 
		      IF PediatricianBusy Then 
		      begin
		        InsertqFQ(QUEUE2,CurrentEvent);
                        Update QUEUE2 size stats
		      end
                      else { pediatrician is not busy }
                      begin
		        Transform CurrentEvent into a Completion_P event 
		          occurring at CurrentTime + PickRandom(S2MIN,S2MAX);
		        PediatricianBusy := true;
		        PediatricianBusyFrom := CurrentTime;
		        InsertqPQ(EventQ,CurrentEvent);
		      end
		    END

     Completion_P : Log event in the log file;
                    Compute response time for pediatrician, update stats;
		    IF this is a P_Patient then
		      Update response stats for P_Patients
		    ELSE { NP_Patient }
		      Update response stats for NP_Patients;
		    IF IsemptyqFQ(QUEUE2) THEN
		      PediatricianBusy := FALSE
		    ELSE
		    BEGIN
		      CurrentEvent := DeleteqFQ(QUEUE2);
		      Update QUEUE2 size stats;
		      Transform CurrentEvent into a Completion_P event 
		        occurring at CurrentTime + PickRandom(S2MIN,S2MAX);
		      PediatricianBusy := true;
		      PediatricianBusyFrom := CurrentTime;
		      InsertqPQ(EventQ,CurrentEvent);
		    END

     Termination : Log event in the log file;
		   Check if Nurse(Pediatrician) is busy and if so 
		     update busy time for Nurse(Pediatrician);
		   IF QUEUE1(QUEUE2) is not empty THEN
		     update QUEUE1(QUEUE2) size stats;
   END; { CASE }
 UNTIL (CurrentEvent.EventKind = Termination);
 Compute Results;
END. { Doctor'sOfficeSimulation }

PROCEDURE CreateNextArrival (var EventQ : EventQueueType;
                             CurrentTime, AMIN, AMAX, R1, R2 : Real);
{ Creates a node corresponding to an Arrival event that would occur at 
  CurrentTime + PickRandom(AMIN,AMAX) and places it in EventQ.  EventQ is a 
  priority queue in which events are stored in nondecreasing order of the 
  event occurrence times.
} 
VAR
  NewEvent : EventNode;
  PatientChoice : Real;
BEGIN
  Create a node of type EventNode in NewEvent;
  Make assignments to the components of NewEvent so that it represents an
    Arrival event occurring at CurrentTime + PickRandom(AMIN,AMAX);
  PatientChoice := PickRandom(0,1);
  IF PatientChoice > R1 THEN 
    NewEvent.PatientInfo.PatientKind := P_Patient
  ELSE IF PatientChoice <= R1 * R2 THEN 
    NewEvent.PatientInfo.PatientKind := N_Patient
  ELSE
    NewEvent.PatientInfo.PatientKind := NP_Patient;
  InsertqPQ(EventQ,NewEvent);
END; { CreateNextArrival }

amandala@astro.ocis.temple.edu