2.7.1. Queues with an unbounded number of elements (class queue)

Learning objectives

The class queue

At the Saarbrücken Central Station, from which the author often travels far away when he is fed up of writing boring tutorials, the author is often fed up with the long processing times at the ticket offices and wants to be far away.

There are 8 desks there. In the past, a queue formed in front of each of the 8 desks. When a new traveller came into the hall, he lined up in the shortest queue. Of course, he always had the feeling to have lined up in the queue in which the processing of his wishes lasted longest, in full harmony with Murphy's law. Figure 2.22 shows this situation.

Figure 2.22. Old system at the Saarbrücken Central Station

Old system at the Saarbrücken Central Station

There are 8 desks with 8 queues. A traveller arriving newly in the hall lines up in one of the currently shortest queues.


The system is so unfair”, many travellers grumbled. And: “The one who came first also should always be the first one to be served. Who comes first, pays first!” Deutsche Bahn, always being on the side of its customers, recognized this defect and introduced a new queuing system. Instead of 8 single queues there is a central queue now in which every traveller lines up first. When a desk becomes free, then the one who is right ahead in the central queue goes to this desk, which has just become free. The new system is depicted in Figure 2.23.

Figure 2.23. New system at the Saarbrücken Central Station

New system at the Saarbrücken Central Station

New travellers joining the system line up in the central queue first. In front of every desk, only one traveller stands. When a desk becomes free, the first traveller of the central queue walks to this desk.


With this system every traveller has at least the impression that the whole waiting procedure is going on more fairly. It remains the question whether this system really shortens the mean time for processing. Is this really so? Or does the new system rather increase the mean processing times even further? Or does it at least reduce the standard deviation of the processing time, by which the grumbling about individual waiting times differing too much should get softer?

To settle these questions, we want to compare both systems in a simulation. Of course, the main attention shall lie on the LEDA class queue, which models the queues.

Our simulation proceeds discretely in minutes. In every minute between 0 and 4 travellers arrive.[27] As probability distribution we take a binomial distribution with mean value 2. So on the average 2 travellers per minute come into the system. Every traveller takes 2, 3, 5, or 6 minutes personal processing time; 3 minutes of processing time are twice as probable as the other times. This distribution has a mean value of 3.8 minutes. So per one minute of the simulation, we need 2 · 3.8 = 7.2 minutes of work to be done on the average. This is just managed by the 8 desk clerks so that the queues do not get infinitely long and the system does not become chaotic.

We put travellers into the queues. We model these by means of a class Traveller. Every traveller knows his time of arrival and can give information about it. He knows the number of minutes that he still needs as personal processing time. He can decrement this number (if he is processed by the clerk) and give information about the time remaining. For the distribution of the original processing time, which is defined in the constructor of a Traveller, we still need a (static) random source and a (static) array of individual processing times.[28] With that the header file Traveller.h looks as follows:

Filename: Traveller.h
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include <LEDA/random_source.h>

using leda::random_source;

class Traveller {
private:
  int time_to_serve;
  int arrival_time;
  static const int service_times[];
  static random_source S;
public:
  Traveller(int);
  ~Traveller();
  
  int dec_time_to_serve();
  int get_arrival_time();
};

The implementation Traveller.C defines the array of the processing times and the random source. A Traveller records his time of arrival in the constructor; thereby, the time spent in the system by this traveller can be calculated later by subtraction from the current system time. In addition, the constructor creates a random processing time by means of the random source.

Filename: Traveller.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include "Traveller.h"

random_source Traveller::S;

const int Traveller::service_times[] = {2,3,3,5,6}; 
// total of 19 means 3.8 minutes per traveller on the average

Traveller::Traveller(int t) {
  arrival_time = t;
  time_to_serve = service_times[S(0,4)];
} 

Traveller::~Traveller() {} 

int Traveller::dec_time_to_serve() { return --time_to_serve;}
int Traveller::get_arrival_time() { return arrival_time;}

We now come to the actual simulation, which is based on the LEDA type queue. First we simulate the old queuing system for a whole year of uninterrupted runtime. In every minute of the simulation the following happens: At first a random number of travellers freshly coming into the system is created. Every new traveller lines up in the currently shortest queue. After this, all 8 clerks carry out 1 minute of work each, that is, they serve the first traveller standing in the queue right in front of them. This traveller decrements his remaining processing time. If it has become 0, he exits the queue and the system. We accumulate the time that he altogether spent in the system in a sum variable and store it additionally in a list in order to be able to calculate statistical indicators, like the standard deviation, later.

Filename: QueueExperiment1.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include <LEDA/queue.h>
#include <LEDA/list.h>
#include <LEDA/array.h>
#include <LEDA/random_variate.h>
#include "Traveller.h"

using leda::queue;
using leda::array;
using leda::random_variate;
using leda::list;
using std::cout;

array< queue<Traveller*> > Queues(1,8);
int min_queue = 1; // number of a shortest queue

list<int> Service_times; // needed for computation of variance

const int mins_to_simulate = 60*24*7*52; // 1 full year

int total_travellers = 0;
int travellers_served = 0;
int total_service_time = 0;

void compute_shortest_queue();
void output_statistics();

int main()
{

  // random variate of 'travellers per minute'
  array<int> weight(0,4);

  weight[0] = 1; 
  weight[1] = 4; 
  weight[2] = 6;
  weight[3] = 4; 
  weight[4] = 1;
  // this gives 2 travellers per minute on the average
  random_variate R(weight); 


  // for every minute of the time interval do the following

  for(int time = 0; time < mins_to_simulate; time++) {

    // some new travellers arrive
    int num_new_travellers = R.generate();

    total_travellers += num_new_travellers;

    // Queing the new travellers
    for(int i = 0; i < num_new_travellers; i++ ) {
      Traveller* T = new Traveller(time);
      // Traveller t goes to the queue with minimal length
      Queues[min_queue].append(T);
      compute_shortest_queue();
    }

    
    // Travellers at the front of the queues get served
    for(int i = 1; i <= 8; i++)
      if(!Queues[i].empty()) {
        Traveller* T = Queues[i].top();
        if(T->dec_time_to_serve() == 0) {
          // T leaves the system
          Queues[i].pop();
          travellers_served++;
          compute_shortest_queue();
          int time_used = time - T->get_arrival_time();
          total_service_time += time_used;
          Service_times.append(time_used);
          delete T;
        }
      }
  }

  output_statistics();
}


// Update min_queue
// Hint: Priority Queues and Sorted Sequences are 
// better data structures for this task!

void compute_shortest_queue() {
  for(int j = 1; j <= 8; j++)
    if(Queues[j].size() < Queues[min_queue].size())
      min_queue = j;
}


void output_statistics() {

  double mean = total_service_time/(double)travellers_served;
  
  // compute standard deviation
  int time;
  double sum;
  forall(time,Service_times) 
    sum += (time - mean) * (time - mean);
  double variance = sum / (Service_times.size()-1);
  double stddev = sqrt(variance);


  cout << "Total number of travellers arrived = " << total_travellers << "\n";
  cout << "Total number of travellers served = " << travellers_served << "\n";
  cout << "Total service time = " << total_service_time << "\n";
  cout << "Service time per traveller = " << mean << "\n";
  cout << "Standard deviation = " << stddev << "\n";
}

The output of a sample run is:

Total number of travellers arrived = 1048773
Total number of travellers served = 1048769
Total service time = 6018465
Service time per traveller = 5.7386
Standard deviation = 3.86143

So almost all travellers were served; the queues did not fill excessively. On the average, every traveller was served within 5.73 minutes. The standard deviation was 3.86 minutes. We will compare these results with those of the second simulation at once.

The method for inserting elements into a queue is called

Q.append();

The method

Q.top();

returns a copy of the first element in the queue.

A call

Q.pop();

does the same; however, it additionally removes the first element from the queue.

Q.size();

returns the number of elements in a queue.

Q.empty();

checks whether a queue is empty, and by

Q.clear();

a queue can be emptied completely.

[Note]Note

It is remarkable here that we put pointers to Traveller into the queues, not the Travellers themselves. This is due to the fact that the method top() returns a copy of the first element in the queue, not a reference to it!

Since we want to change the internal time information of the first traveller (by dec_time_to_serve()), a copy of the accompanying object, returned by the queue, would not be of use for us.

With regard to their interface, the types queue and stack follow the classic textbook approach, according to which the structure physically contains the individual elements. Furthermore, it is not possible to iterate over the elements of a queue or a stack! This is in harmony with what we said in Section 2.4. Simple interfaces often allow simple implementations.

[Tip]Tip

The lengths of the individual queues change from minute to minute. The simulation must, however, know the currently shortest queue. Here, we calculate this queue by a complete comparison of all lengths. For exactly this problem definition, though, LEDA keeps ready especially efficient data types, which we will come to know yet: sortseq and p_queue.

We come to the new system now: There are only one central queue and 8 desks, at which at most one traveller is standing. We implement the desks by an array of pointers to travellers. Again, new travellers are created in every minute of the simulation, according to the same distributions. However, these travellers first line up in the central queue. If a desk is empty, the first traveller of the central queue walks to this desk. After this, all 8 clerks carry out 1 minute of work again, that is, they serve the traveller standing right in front of them (if one stands there at all).

Filename: QueueExperiment2.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include <LEDA/queue.h>
#include <LEDA/list.h>
#include <LEDA/array.h>
#include <LEDA/random_variate.h>
#include "Traveller.h"

using leda::queue;
using leda::array;
using leda::random_variate;
using leda::list;
using std::cout;

queue<Traveller*> BigQueue;
array<Traveller*> TicketOffice(1,8);

list<int> Service_times; // needed for computation of variance

const int mins_to_simulate = 60*24*7*52; // 1 full year

int total_travellers = 0;
int travellers_served = 0;
int total_service_time = 0;

void output_statistics();

int main()
{

  // random variate of travellers per minute
  array<int> weight(0,4);

  weight[0] = 1; 
  weight[1] = 4; 
  weight[2] = 6;
  weight[3] = 4; 
  weight[4] = 1;
  // this gives 2 travellers per minute on the average
  random_variate R(weight);


  // intialize offices
  for(int i = 1; i <= 8; i++) TicketOffice[i] = nil;

  // for every minute of the time interval do the following

  for(int time = 0; time < mins_to_simulate; time++) {

    // some new travellers arrive
    int num_new_travellers = R.generate();

    total_travellers += num_new_travellers;

    // Queing the new travellers into the one big queue
    for(int i = 0; i < num_new_travellers; i++ ) {
      Traveller* T = new Traveller(time);
      BigQueue.append(T);
    }

    // Empty offices get travellers from the big queue
    for(int i = 1; i <= 8; i++)
      if(!TicketOffice[i] && !BigQueue.empty()) 
        TicketOffice[i] = BigQueue.pop();
                
    // Travellers at the 8 offices get served
    for(int i = 1; i <= 8; i++)
      if(Traveller* T = TicketOffice[i]) {
        if(T->dec_time_to_serve() == 0) {
          // T leaves the system
          TicketOffice[i] = nil;
          travellers_served++;
          int time_used = time - T->get_arrival_time();
          total_service_time += time_used;
          Service_times.append(time_used);
          delete T;
        }
      }

  }

  output_statistics();
}


void output_statistics() {

  double mean = total_service_time/(double)travellers_served;
  
  // compute standard deviation
  int time;
  double sum;
  forall(time,Service_times) 
    sum += (time - mean) * (time - mean);
  double variance = sum / (Service_times.size()-1);
  double stddev = sqrt(variance);


  cout << "Total number of travellers arrived = " << total_travellers << "\n";
  cout << "Total number of travellers served = " << travellers_served << "\n";
  cout << "Total service time = " << total_service_time << "\n";
  cout << "Service time per traveller = " << mean << "\n";
  cout << "Standard deviation = " << stddev << "\n";
}

The output of an example run is here:

Total number of travellers arrived = 1047306
Total number of travellers served = 1047303
Total service time = 5491971
Service time per traveller = 5.24392
Standard deviation = 3.26802

There you are! A cheer for Deutsche Bahn! By the new system, we save half a minute at the desks on the average. Moreover, the oscillation around the mean processing time is smaller, making the system appear fairer and therefore our fellow passengers less grumbly. (However, this all is recompensated by sufficient train delay and a very, very strange pricing policy well enough.)

Implementation and further information

The class queue is implemented by linearly linked lists. All operations take time O(1) apart from clear(), which takes time O(n) if a queue contains n elements.

More about queues can be found on the corresponding manual page.



[27] These distributions are arbitrary. However, they could be based on a measuring. Here we could, of course, think up and implement more complex distribution models also, but this would turn away the main attention from the class queue, which it is all about here, actually.

[28] One should expect after reading Section 2.6 that the individual processing times, which are not all equally likely, are implemented by a random variate. Unfortunately, it is not possible with the present implementation of random_variate to make an object of this class a static member that can be initialized suitably. We therefore manage here with a static random_source and a static array in which the number 3 occurs twice.

Another possibility is to use a static pointer to a random_variate that is initialized to NULL. If a random processing time is needed for time_to_serve in the constructor, it is checked first whether the pointer is still NULL; if it is, a new random_variate, to which the pointer then points, is created with new. Random processing times are created via this pointer from then on. With this handle technique the problem of not being able to create any static random_variate is bypassed elegantly.




Imprint-Dataprotection