Some hints for Homework 1

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

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:

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 departure 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 depart from the server as described above.

It is assumed that the servers are free and the queues are empty 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 priority queue 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 = w1*l1 + w2*l2 + ... + wn*ln
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     //Each paient has an id, one of: 1, 2, 3, ..
    PatientKind : PatientType
    ArrivalTime : Real
    ServiceNumber : Integer //Initialized to zero//
end Patient

A note about ServiceNumber : After service received at each server (nurse or Dentist) 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 dentist or must he leave the office? If ServiceNumber is 1 then he goes to the dentist 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;
    NurseBusyFrom, DentistBusyFrom: Real; 
//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
DentistBusy = FALSE

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

  switch(Currentevent.EventKind) //Events//

      case Arrival:  
      //Log event in the Log file//
      call CreateNextArrival(Agenda, CurrentTime, AMIN, AMAX)

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

          case 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]
          break
      end    
      break

      case Departure_N: 
      //Log event in the Log file//
      //Compute response time for nurse, update stats//

      switch(CurrentEvent.PatientInfo.PatientKind) 
          
          case 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]
          break
 
          case NP_Patient OR 
          (NPN_Patient AND CurrentEvent.PatientInfo.ServiceNumber == 1)
              (going to the Dentist):
          //Record arrival time @Dentist//
          if DentistBusy then
             [InsertFQ(QUEUE2, CurrentEvent)
             //Update QUEUE2 size stats//]
          else 
             [DentistBusy = TRUE
             //Create a Departure_P event occuring 
               @CurrentTime + Random(S2MIN, S2MAX)
               Let NewEvent be this event//
             InsertPQ(Agenda, NewEvent)
             DentistBusyFrom = CurrentTime]

	  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]
          break
      end
      break
     
      case Departure_P: 
      //Log event in the Log file//
      //Compute response time for Dentist, update stats//

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

          case 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]
          
	  if IsEmptyFQ(QUEUE2) then
  	     [DentistBusy = FALSE]
  	  else
             [DentistBusy = TRUE
             CurrentEvent = DeleteFQ(QUEUE2)
	     //Create a Departure_P event occuring
               @CurrentTime + Random(S2MIN, S2MAX)
               Let NewEvent be this event// 
             InsertPQ(Agenda, NewEvent)
             DentistBusyFrom = CurrentTime]
          break
      end
      break

      case Termination:
      //Log Event in the Log file//
      //check if Nurse and/or Dentist are busy
      if so, update busy time for Nurse and/or dentist//
      //If QUEUE1 and/or QUEUE2 are not empty then
      update QUEUE1 and/or QUEUE2 size stats //
      break

  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

In writing this homework be sure to partition your program into a number of files. For example, it would be appropriate to put the code for the FIFO queue in files fifo.h and fifo.c. For example, code for the priority queue could go in files agenda.h and agenda.c. If you are accustomed to writing C++ code, you can in C create an .h and .c file for each class.