Some hints for Homework 1

You are required to do a discrete event simulation of a system representing a pediatrician's ofice. The system consists of two servers - the nurse and the pediatrician. Patients are classified into five categories :

1. Patients that see first the nurse then the pediatrician.
2. Patients that only see the nurse.
3. Patients that only see the pediatrician.
4. Patients that first see the pediatrician then the nurse.
5. Patients that see first the nurse, then the pediatrician, then again the nurse.

The status of a server is busy if there is a patient receiving treatment from the server and free otherwise. A patient arriving at the 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. The following are the types of events that occur in the system:

1. Arrival of a patient either at the nurse or the pediatrician.
2. Completion of treatment by the nurse.
3. Completion of treatment by the pediatrician.
4. Termination of the simulation.

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 occurence of the event. The simulation process consists of tracing the state transitions that 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.

Arrival events are fundamental to the system as they give rise to subsequent departture 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 departure event corresponding to an arrival can be determined at the time of arrival if the server is free and there are no patients waiting for the server at that time. Otherwise the patient enters the queue for that server. The patient leaves the queue to receive treatment when the patient ahead of him leaves the server, at which time we can compute the time at which this patient will deaprt from the server as described above.

It is assumed that the servers are free at the start of the simulation. It is also assumed that the first arrival coincides with the start of the simulation.

Priority Queue

A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key.
A priority queue supports the following operations.
InsertPQ(S,x) : Inserts the element x into the set S.
DeletePQ(S): Removes and returns the element of S with the largest/smallest key as required.

For this simulation the key field in each event of the priority queue is the time of occurence of that event. The events will be stored in the priority queue in ascending order of the value of the key field i.e., in ascending order of their times of occurence. When it is time to remove an event from the the event with the smallest key field value is removed. The priority queue may be implemented as a doubly linked list or a MIN heap.

Computing the Average size of a Queue

Avg. queue size = w1l1 + w2l2 + ... + wnln
where wi = Period of time for which length of the queue was li/Total time of simulation

In the above formula the summation is over the number of sucessive periods with distinct queue lengths in adjacent periods till the end of the simulation.

I suggest that you read the input parameters for the simulation from a file so that as you modify your program and test it you don't have to enter all the input parameters every time you run your program.

For additional hints and the format of the log file look at the instructions provided by Dr.Ingargiola in the home page.

Data Structures for the program

// Type definitions //
EventType = (Arrival, Departure_N, Departure_P, Termination)
PatientType = (NP_Patient, N_Patient, P_Patient, PN_Patient, NPN_Patient)

structure Patient
    PatientId : Integer
    PatientKind : PatientType
    ArrivalTime : Real
    Arrival@Pediatrician : Real
    ServiceNumber : Integer //Initialized to zero//
end Patient

A note about ServiceNumber : After service received at each server (nurse or pediatrician) this number is incremented. This is important for the following reason: Suppose we have an NPN_Patient. If he has just been served at the nurse must he go to the pediatrician or must he leave the office? If ServiceNumber is 1 then he goes to the pediatrician and if service number is 3 he leaves the office.

structure Event
    EventKind : EventType
    EventTime : Real
    PatientInfo : Pointer to Patient
    Next : Pointer to Event
end Event


structure PriorityQueueInfo
    First : Event
    Last : Event
end PriorityQueueInfo


structure ServerQueueInfo
    First : Event
    Last : Event
    LastUpdate : Real
end ServerQueueInfo

structure InputParameters 
    SEED : Integer
    INITTIME : Integer
    FINTIME : Integer
    AMIN : Integr
    AMAX : Integer
    S1MIN : Integer
    S1MAX : Integer
    S2MIN : Integer
    S2MAX : Integer
    LOG_FILENAME : Pointer to String
end InputParameters

Var Agenda : PriorityQueueInfo
    QUEUE1, QUEUE2 : ServerQueueInfo

Assume that the operations CreateFQ, InsertFQ, DeleteFQ, and IsemptyFQ for the abstract data type FIFO queue, and their counterparts CreatePQ, InsertPQ, DeletePQ and IsemptyPQ for the abstract data type priority queue are already defined.

The algorithm also invokes the function Random

Function Random(Low, High : Real):Real

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

Algorithm

procedure DiscreteEventSimulation
var NewEvent : Event
//Read SEED, INITTIME, FINTIME, AMIN, AMAX// 
//Read S1MIN, S1MAX, S2MIN, S2MAX, LOGFILE_NAME//

//Initialize Agenda with Arrival and Termination events //
//Initialize QUEUE1 and QUEUE2 to be empty //

NurseBusy = FALSE
PediatricianBusy = FALSE

repeat
  CurrentEvent = DeletePQ(Agenda)
  CurrentTime = CurrentEvent.EventTime

  case //Events//
      Currentevent.EventKind = Arrival:  
      
      //Log event in the Log file//
      call CreateNextArrival(Agenda, CurrentTime, AMIN, AMAX)

      case 
	  CurrentEvent.PatientInfo.PatientKind 
	  = P_Patient OR PN_Patient:
	  
	  if PediatricianBusy then
	      [InsertFQ(QUEUE2, CurrentEvent)
	      //Update QUEUE2 stats//]
	  else
	      [PediatricianBusy = TRUE
	       //Create a Departure_P event occuring 
	       @CurrentTime + Random(S2MIN, S2MAX)
	       Let NewEvent be this event//
	       InsertPQ(Agenda, NewEvent)
	       PediatricianBusyFrom = CurrentTime] 

	  CurrentEvent.PatientInfo.PatientKind 
	   = N_Patient OR NP_Patient OR NPN_Patient:
	  
	  if NurseBusy then
	     [InsertFQ(QUEUE1, CurrentEvent)
	     //Update QUEUE1 stats//]
	  else
	     [NurseBusy = TRUE
	     //Create a Departure_N event occuring 
	       @CurrentTime + Random(S1MIN, S1MAX)
	       Let NewEvent be this event//
	     InsertPQ(Agenda, NewEvent)
	     NurseBusyFrom = CurrentTime]
      end    
      
      Currentevent.EventKind = Departure_N: 
      
      //Log event in the Log file//
      //Compute response time for nurse, update stats//

      case
	  CurrentEvent.PatientInfo.PatientKind 
	  = N_Patient OR PN_Patient OR (NPN_Patient AND 
	  CurrentEvent.PatientInfo.ServiceNumber == 3)(leaving the office):
	  
	  //Update response stats for N_Patients// 
	  if IsEmptyFQ(QUEUE1) then                
	      NurseBusy = FALSE
	  else 
	      [NurseBusy = TRUE
	      CurrentEvent = DeleteFQ(QUEUE1)
	     //Create a Departure_N event occuring 
	       @CurrentTime + Random(S1MIN, S1MAX)
	       Let NewEvent be this event//
	       InsertPQ(Agenda, NewEvent)
	       NurseBusyFrom = currentTime]

	  CurrentEvent.PatientInfo.PatientKind 
	  = NP_Patient OR 
	  (NPN_Patient AND CurrentEvent.PatientInfo.ServiceNumber == 1)
              (going to the Pediatrician):
	  
	  //Record arrival time @Pediatrician//
	  if PediatricianBusy then
	     [InsertFQ(QUEUE2, CurrentEvent)
	     //Update QUEUE2 size stats//]
	  else 
	     [PediatricianBusy = TRUE
	     //Create a Departure_P event occuring 
	       @CurrentTime + Random(S2MIN, S2MAX)
	       Let NewEvent be this event//
	     InsertPQ(Agenda, NewEvent)
	     PediatricianBusyFrom = CurrentTime]
      end

      Currentevent.EventKind = Departure_P: 
      
      //Log event in the Log file//
      //Compute response time for Pediatrician, update stats//

      case
	  CurrentEvent.PatientInfo.PatientKind 
	  = P_Patient OR NP_Patient:
	  
	  //Update response stats for P_Patients// 
	  if IsEmptyFQ(QUEUE2) then                
	     PediatricianBusy = FALSE
	  else 
	    [PediatrcianBusy = TRUE
	     CurrentEvent = DeleteFQ(QUEUE2)
	     //Create a Departure_P event occuring 
	       @CurrentTime + Random(S2MIN, S2MAX)
	       Let NewEvent be this event//
	     InsertPQ(Agenda, NewEvent)
	     PediatricianBusyFrom = currentTime]

	  CurrentEvent.PatientInfo.PatientKind 
	  = PN_Patient OR NPN_Patient (going to the Nurse):
	  
	  //Record arrival time @Nurse//
	  if NurseBusy then
	    [InsertFQ(QUEUE1, CurrentEvent)
	    //Update QUEUE1 size stats//]
	  else 
	      [NurseBusy = TRUE
	      //Create a Departure_N event occuring 
	       @CurrentTime + Random(S1MIN, S1MAX)
	       Let NewEvent be this event//
	     InsertPQ(Agenda, NewEvent)
	     NurseBusyFrom = CurrentTime]
      end

      Currentevent.EventKind = Termination:
      
      //Log Event in the Log file//
      //check if Nurse and/or Pediatrician are busy
      if so, update busy time for Nurse and/or Pediatrician//
      //If QUEUE1 and/or QUEUE2 are not empty then
      update QUEUE1 and/or QUEUE2 size stats //
  end //Events//

  until CurrentEvent.EventType = Termination
  //Compute Results//
end DiscreteEventSimulation


procedure CreateNextArrival(Var Agenda : AgendaInfo; CurrentTime, 
		    AMIN, AMAX : Real)
Var NewEvent : Event
  //Create a new event and assign it to Newevent
  The type of NewEvent is Arrival and 
  EventTime = CurrentTime + Random(AMIN, AMAX)//
  //Assign a type to the Patient//
  InsertPQ(Agenda, NewEvent)
end CreateNextArrival

Mail queries to :

ppappach@thunder.ocis.temple.edu