Homework I Solution


Category: Tag:


Problem A

This problem will involve the SimPy discrete-event simulation library, which relies heavily on the Python generator construct. Here are the details:

  • The new version of SimPy is quite complex. We’ll use the earlier one.

  • Your main source on SimPy will be the example in our Python textbook. However, if you want more examples, go here. You might start with the file DESimintro.pdf and possibly AdvancedSimPy.pdf, but really, the example in our textbook should be enough (except for passivate/reactivate).

  • Your code will be simulating the operation of an elevator. We’ll only model a single one now, but you should think of how it would be useful to model multiple elevators. E.g. how much would mean wait time decrease if we add a second elevator — worth the expense? Or, say, we have two of them. We might save money by shutting one down; how much would mean wait increase? Or what about more involved policies, e.g. elevator waits until a specified time at Floor 1 then leaves? What about modeling the traffic on the other floors?

  • There is a single elevator in a building. Our simulation is done from the point of view of Floor 1.

  • When the elevator arrives at Floor 1, it will pick up whatever passengers are waiting, up to its capacity, and leave immediately. Those unable to board will continue to wait. If no one is waiting when the elevator arrives, it will wait until a passenger arrives; he/she will board and the elevator will leave immediately.

  • Your code will be run as

% python Elevator.py passenger_arrival_rate elevator_capacity mean_elevator_return_time max_simtime 

Those command-line arguments are:

    • Reciprocal of the mean interarrival time, the latter being taken to be exponentially distributed.

    • Maximum number of passengers allowed into the elevator.

    • Mean time elapsed from an elevator departure to next time it arrives at Floor 1. Again, assume an exponential distribution.

    • Amount of simulated time to run the simulation.

  • Required output:

    • Proportion of visits of the elevator to Floor 1 in which there are more passengers waiting than can be accommodated.

    • Mean waiting time to board the elevator, measured from passenger arrival time. (Includes 0s.)

Important note regarding credit:

This is a difficult assignment. For that reason, I’ve made some changes from the original version:

  • Extended the due date.

  • Will provide hints below.

  • Will allow submission of a narrower version, for most of the credit.

Hints for the full version:

Normally I frown on the practice by some instructors of providing students with code outlines in the problem specs. I make plenty of help available to those who need it, but only after they’ve spent a goodly amount of time trying to devise a code strategy.

In this case, though, due to the difficulty of the problem, I will give extensive hints here:

  • You MUST (for full credit) have two SimPy Processes, one for the elevator and one for the passenger arrivals.

  • Here is my class for globals:

class G:  # globals
   Rnd = Random(12345)
   elevProc = None  # elevator process
   passProc = None  # passenger process
  • Here is part of my passenger class:

class passClass(Process):
   def __init__(self):
      self.passArrvRate = float(sys.argv[1])
      # self.arrvs will be arrivals waiting for pickup
      self.arrvs = [0.0]
      self.nextArrv = None  # for debugging/code verifying
   def Run(self):
      while True:
         # sim next arrival
  • At simulated time 0.0, the elevator has just arrived at Floor 1, and there is a passenger waiting there, having also just arrived. The latter condition is hardwired into the code, in the line seen above

self.arrvs = [0.0]
  • The arrivals Process will repeatedly loop, generating the time of next arrival, updating arrvs after the arrival, etc. It will “wake” the elevator process if needed,

  • The elevator Process will repeatedly loop. Each iteration covers one visit to Floor 1. Upon arrival, it will check for waiting passengers. If it finds any, they board up to capacity of the elevator, and the elevator leaves. On the other hand, if no passengers are waiting, the elevator Process will “go to sleep,”

yield passivate,self
  • Timing is key! Remember, executing yield means the Process is relinquishing control of your machine’s CPU. So, e.g. it makes a difference whether you update before or after a yield.

  • Use a debugging tool! As you know, I feel quite strongly about this, the key to good software engineering in the real world. It’s especially important in parallel programming, which is what SimPy is.

When I was debugging my code for this problem, I used Python’s built-in debugger, pdb. It’s pretty primitive, but I configured it to give me important information at each pause. Specifically, I set these at the beginning of my debugging session:

b 43                                                                                
b 55                                                                                
b 59                                                                                
b 74                                                                                
b 76                                                                                
alias c c;;now();;l;;G.elevProc;G.passProc         

The last redefines the “continue” command to print out things at each pause of the debugger.

For partial credit:

If you are willing to have a maximum grade of B+ on this assignment, you may do a scaled-down version:

  • Have only one Process, for the elevator, none for the arrivals.

  • Generate all the arrival times at the outset.

Why is this considered “scaled-down”? First, of course, it’s easier. But second, it is much less general. For example, it obviates our ability to model more sophisticated arrival schemes, such as balking, in which an arriving passenger sees a long line for the elevator and thus opts to take the stairs instead.

Problem B