Simulating with a Queue

I l @ ve RuBoard

Simulating with a Queue

Well, the queue works! Now let's do something more interesting with it. Many real-life situations involve queues. For instance, customers queue in banks and in supermarkets, airplanes queue at airports, and tasks queue in multitasking computer systems. You can use the queue package to simulate such situations.

Suppose, for example, that Sigmund Landers has set up an advice booth in a mall. Customers can purchase one, two, or three minutes of advice. To ensure a free flow of foot traffic, mall regulations limit the number of customers waiting in line to ten (conveniently equal to the program's maximum queue size .) Suppose people show up randomly and that the time they want to spend in consultation is spread randomly over the three choices (one, two, or three minutes). How many customers, on average, will Sigmund handle an hour ? How long, on average, will customers have to wait? How long, on average, will the line be? These are the sort of questions a queue simulation can answer.

First, let's decide what to put in the queue. You can describe each customer in terms of the time when he or she joins the queue and in terms of how many minutes of consultation he or she wants. This suggests the following definition for the Item type:

 typedef struct item {    long arrive;      /* the time when a customer joins the queue   */    int processtime;  /* the number of consultation minutes desired */ } Item; 

To convert the queue package to handle this structure, instead of the int type the last example used, all you have to do is replace the former typedef for Item with the one shown here. After that's done, you don't have to worry about the detailed mechanics of a queue. Instead, you can proceed to the real problem ”simulating Sigmund's waiting line.

Here's one approach. Let time move in one-minute increments . Each minute, check to see whether a new customer has arrived. If a customer arrives and the queue isn't full, add the customer to the queue. This involves recording in an Item structure the customer's arrival time and the amount of consultation time the customer wants, and then adding the item to the queue. If the queue is full, however, turn the customer away. For bookkeeping, keep track of the total number of customers and the total number of turnaways (people who can't get in line because it is full).

Next, process the front of the queue. That is, if the queue isn't empty and if Sigmund isn't occupied with a previous customer, remove the item at the front of the queue. The item, recall, contains the time when the customer joined the queue. By comparing this time with the current time, you get the number of minutes the customer has been in the queue. The item also contains the number of consultation minutes the customer wants, which determines how long Sigmund will be occupied with the new customer. Use a variable to keep track of this waiting time. If Sigmund is busy, no one is "dequeued." However, the variable keeping track of the waiting time should be decremented.

The core code can look like this, with each cycle corresponding to one minute of activity:

 0; cycle < cyclelimit; cycle++) {    if (newcustomer(min_per_cust))    {       if (FullQueue(&line))          turnaways++;       else       {          customers++;          temp = customertime(cycle);          EnQueue(temp, &line);       }    }    if (wait_time <= 0 && !EmptyQueue(&line))    {       DeQueue (&temp, &line);       wait_time = temp.processtime;       line_wait += cycle - temp.arrive;       served++;    }    if (wait_time > 0)       wait_time--;    sum_line += QueueItems(&line); } 

Here are the meanings of some of the variables and functions:

• min_per_customer is the average number of minutes between customer arrivals.

• newcustomer() uses the C rand() function to determine whether a customer shows up during this particular minute.

• turnaways is the number of arrivals turned away.

• customers is the number of arrivals who join the queue.

• temp is an Item variable describing the new customer.

• customertime() sets the arrive and processtime members of the temp structure.

• wait_time is the number of minutes remaining until Sigmund finishes with the current client.

• line_wait is the cumulative time spent in line by all customers to date.

• served is the number of clients actually served.

• sum_line is the cumulative length of the line to date.

Think of how much messier and more obscure this code would look if it were sprinkled with malloc() and free() functions and pointers to nodes. Having the queue package enables you to concentrate on the simulation problem, not on programming details.

Listing 17.9 shows the complete code for the mall advice booth simulation. It uses the standard rand() , srand () , and time() functions to generate random values, following the method suggested in Chapter 13, "Storage Classes and Program Development." To use the program, remember to update the Item definition in queue.h with the following:

 typedef struct item {    long arrive;      /* the time when a customer joins the queue   */    int processtime;  /* the number of consultation minutes desired */ } Item; 

Also remember to link the code for mall.c with queue.c .

Listing 17.9 The mall.c program.

 /* mall.c -- use the Queue interface */ /* compile with queue.c              */ #include <stdio.h> #include <stdlib.h>    /* for rand() and srand() */ #include <time.h>      /* for time()             */ #include "queue.h" #define MIN_PER_HR 60.0 BOOLEAN newcustomer(double x);   /* is there a new customer? */ Item customertime(long when);    /* set customer parameters  */ int main(void) {    Queue line;    Item temp;               /* new customer data             */    int hours;               /* hours of simulation           */    int perhour;             /* average # of arrivals per hour */    long cycle, cyclelimit;  /* loop counter, limit           */    long turnaways = 0;      /* turned away by full queue     */    long customers = 0;      /* joined the queue              */    long served = 0;         /* served during the simulation  */    long sum_line = 0;       /* cumulative line length        */    int wait_time = 0;       /* time until Sigmund is free    */    double min_per_cust;     /* average time between arrivals */    long line_wait = 0;      /* cumulative time in line       */    InitializeQueue(&line);    srand(time(0));         /* random initializing of rand() */    puts("Case Study: Sigmund Lander's Advice Booth");    puts("Enter the number of simulation hours:");    scanf("%d", &hours);    cyclelimit = MIN_PER_HR * hours;    puts("Enter the average number of customers per hour:");    scanf("%d", &perhour);    min_per_cust = MIN_PER_HR / perhour;    for (cycle = 0; cycle < cyclelimit; cycle++)    {       if (newcustomer(min_per_cust))       {          if (FullQueue(&line))             turnaways++;          else          {             customers++;             temp = customertime(cycle);             EnQueue(temp, &line);          }       }       if (wait_time <= 0 && !EmptyQueue(&line))       {          DeQueue (&temp, &line);          wait_time = temp.processtime;          line_wait += cycle - temp.arrive;          served++;       }       if (wait_time > 0)          wait_time--;       sum_line += QueueItems(&line);    }    if (customers > 0)    {       printf("customers accepted: %ld\n", customers);       printf("  customers served: %ld\n", served);       printf("       turnaways: %ld\n", turnaways);       printf("average queue size: %.2f\n",          (double) sum_line / cyclelimit);       printf(" average wait time: %.2f minutes\n",          (double) line_wait / served);    }    else       puts("No customers!");    return 0; } /* x = average time, in minutes, between customers       */ /* return value is true if customer shows up this minute */ BOOLEAN newcustomer(double x) {    if (rand() * x / RAND_MAX < 1)       return True;    else       return False; } /* when is the time at which the customer arrives            */ /* function returns an Item structure with the arrival time  */ /* set to when and the processing time set to a random value */ /* in the range 1 - 3                                        */ Item customertime(long when) {    Item cust;    cust.processtime = rand() % 3 + 1;    cust.arrive = when;    return cust; } 

The program enables you to specify the number of hours to simulate and the average number of customers per hour. Choosing a large number of hours gives you good average values, and choosing a small number of hours shows the sort of random variation you can get from hour to hour. The following runs illustrate these points. Note that the average queue sizes and wait times for 80 hours are about the same as for 800 hours, but that the two one-hour samples differ quite a bit from each other and from the long- term averages. That's because smaller statistical samples tend to have larger relative variations.

 Case Study: Sigmund Lander's Advice Booth Enter the number of simulation hours: 80 Enter the average number of customers per hour: 20 customers accepted: 1633   customers served: 1633        turnaways: 0 average queue size: 0.46 average wait time: 1.35 minutes Case Study: Sigmund Lander's Advice Booth Enter the number of simulation hours: 800 Enter the average number of customers per hour: 20 customers accepted: 16020   customers served: 16019        turnaways: 0 average queue size: 0.44 average wait time: 1.32 minutes Case Study: Sigmund Lander's Advice Booth Enter the number of simulation hours: 1 Enter the average number of customers per hour: 20 customers accepted: 20   customers served: 20        turnaways: 0 average queue size: 0.23 average wait time: 0.70 minutes Case Study: Sigmund Lander's Advice Booth Enter the number of simulation hours: 1 Enter the average number of customers per hour: 20 customers accepted: 22   customers served: 22        turnaways: 0 average queue size: 0.75 average wait time: 2.05 minutes 

Another way to use the program is to keep the numbers of hours constant, but try different average numbers of customers per hour. Here are a few sample runs exploring this variation:

 Case Study: Sigmund Lander's Advice Booth Enter the number of simulation hours: 80 Enter the average number of customers per hour: 25 customers accepted: 1960   customers served: 1959        turnaways: 3 average queue size: 1.43 average wait time: 3.50 minutes Case Study: Sigmund Lander's Advice Booth Enter the number of simulation hours: 80 Enter the average number of customers per hour: 30 customers accepted: 2376   customers served: 2373        turnaways: 94 average queue size: 5.85 average wait time: 11.83 minutes 

Note how the average wait time takes a sharp upturn as the frequency of customers increases . The average wait for 20 customers per hour (80-hour simulation) was 1.35 minutes. It climbs to 3.50 minutes at 25 customers per hour and soars to 11.83 minutes at 30 customers an hour. Also, the number of turnaways climbs from 0 to 3 to 94. Sigmund could use this sort of analysis to decide whether he needs a second booth.

I l @ ve RuBoard