AREA OF SCIENCE……………………………………………………...4

CONCLUSIONS ………………..……………………………………….11

C++ program code……………………………………………………………… 16

Actors…………………………………………………………………………… 19

Class Diagram.………………………………………………………………… 22

Entity Relationship Diagram.……….…………………………………………. 23

Sequence Diagram.…………………………………………………………….. 24

State Diagrams………………………………………………………………….. 25

Activity Diagram……………………………………………………………….. 27

Queueing analysis is a mathematical technique for analyzing waiting lines. In a simple waiting line, a customer arrives, joins a queue, is serviced, and leaves. Queueing theory assumes exponential arrival and service rates. Generally, this exponential distribution is Poisson. Thus, for a queueing system with low traffic intensity, the expected number of customers in the queue is small. However, with a bursty input process, long queues may build up in a short time. We studied various length traffic queueing systems, some with bursty input processes. We examined the distributions of queue lengths, waiting times, busy and active periods, and their corresponding expansions. If time permitted, we would give special attention to some conditional distributions of queue lengths, waiting times, and system-active periods. The expansions would provide a potential asymptotic approach to the computation of various descriptors of queueing systems. The coefficients of those expansions would reflect some important features of episodic queues and prioritization methods, which were not included, in depth, in this project. We also studied graphical representations of the numerical results of approximations and of the effect of the burstiness of the input and service processes on the queues. As a result, the program generated a practical output of potential scheduling matrices.

The science area for this project is Math. The program will analyze numbers for scheduling and not the behavioral aspects of humans. Originally, the behavioral area was considered due to the use of human beings as subjects, but the motivation behind their activity is not relevant to the problem of scheduling.

Standing in a line, a queue, is a simple fact of life. Whether at the bank, department store, motor vehicle department, or even waiting for a job to print, we spend a significant part of our lives affected by a queue. From a manager’s point of view, we know that brief periods of activity alternate with longer periods during which there is no arrival of customers. We wanted to know what was happening during the peak periods of transactions rather than overall averages, and how many employees would have to be scheduled to minimize waiting time. Therefore, our program was designed to study the various alternatives in scheduling and would be used to optimize employees and their work schedules, alleviating the problem of waiting.

This project used the queueing theory to determine an optimal number of employees to schedule in any service industry and "to provide the fundamental concepts and computations required for the analysis of any system that features a waiting line (queue)." (Marks) For this project, it was assumed that customers are inanimate objects. These ideas were traditionally applied to service industries, such as grocery stores, airline ticket counters, fast food restaurants, retail stores, auto license agencies, and banks. Other applications of this project would be production processes or printer queues. In the context of information system, queueing theory was used to help plan, design and reconfigure communication networks. In the context of efficiency, the queueing theory will make a difference.

The code for this problem will involve performing a summation using a loop until the numbers either diverge or converge. The program will compute such statistics as the time a customer spends in the queue and in the system, the expected line length, and the expected number of customers in the system.

We wrote the code using C++. The arrival process of the customers is assumed to be Poisson, that is, the service is assumed to be deterministic and provided to customers on a first come, first served basis (FIFO). Markovian equations and Poissons arrival equations are applicable to a queue scenario. In the scenario, the customer enters the system, collects the goods, waits to be served, is served, and leaves the system. The management uses the program to analyze and prepare work schedules for the employees accordingly. The expected outcome, shorter wait times, facilitates the scheduling of enough employees during the peak periods of customers into the system and is a useful tool for any manager, of either humans or inanimate objects.

The code begins with comments that are descriptions of variables used in the program and that will give results of several different situations. When we study this problem, the steady state probability is what we are seeking. This is same number of customers entering the system as are being served. This can be attained. Once this is found, by choosing a certain number of customers entering the system, we can decide the service rate. This will determine how many customers we are able to service.

Next, once you decide how many customers to prepare for, then the steady state formula tells us the expected time in the queue, the expected time in system, the expected length of the line, and the expected number of customers in line. The decision is made on how long it takes to get 90% of customers through the queue and through the system.

The variable indicating arrival rate in hours is lambda; mu indicates the service rate (how many customers are serviced in one hour); psi indicates traffic intensity and the number of customers divided by the time it takes to be serviced. If lambda is bigger than mu, the length of the line will approach infinity, which would render our model useless. We use n to represent the number of customers used in the for loop that will find the steady state probability using the M/M/1 model and creates a table of numbers that could be graphed.

We can only expect 90% of the customers to fall within our formulae and get through the queue in timely fashion. We have no control over some situations. A manager can analyze this output and would realize that you must have more people servicing customers than customers entering the system.

It was definitely a challenge to complete this project in two weeks, and technically, it can be done and then easily expanded. The experience of actually preparing an interim report, the code, and a final report and presentation will be helpful in understanding the steps, and anxieties, that our students will have to experience when they compete in the High School Supercomputing Challenges. The advanced research skills we already had accumulated were augmented by the excellent work done previously by the authors we found. However, the research we discovered is just the tip of the iceberg. We realize that the enormity and vastness of the research itself may overwhelm students.

In choosing this practical project, we feel that its solution would be useful in so many scenarios. Application of the output would lessen the waiting time anyone would have to undergo, significantly improving the productive time of humans everywhere and reducing their stress levels. This would ultimately improve the quality of life. Originally, we hadn’t realized that a C++ program would have this application, and so we are content with the results.

The weakness in our program includes the fact that this entire project, from start to finish, was constructed within two weeks, and therefore, was limited in its scope. An expanded program, given the time span of the normal school year, could have included episodic queues and prioritized queues and could have been much more comprehensive. The limitations invoked by time and performance measurements were considered by the team to be a starting point for an expanded project. "Since this project assumes exponential arrival and service rates, queueing theory should not be used if it clear that either rate is not exponential. Other inhibiting are prioritization of customers, a service rate that varies by the size of the waiting line, a restriction on queue length, and complexity of system design." (Marks, 642)

Our strengths include the team-building skills that were primarily a result of the closeness of the team. We enjoyed a cooperative learning environment where everyone worked for the completion of the project and its excellence. Two of the participants had no previous C++ coding experience; thus, we enhanced our research and coding skills and learned new multimedia avenues, such as PowerPoint and graphic manipulation. Additionally, our time-management skills were tested, and the result delivered achievement.

Among the various queueing theory models, we chose to look at the M/M/1 steady state model because of its relative simplicity. The steady state probabilities are calculated as follows:

n = number of customers in the system (queue plus service)

p_o = 1 – p _t

p _n = (1-p) p ⁿ

whereas n can be equal to 1, 2, 3, …

The expressions associated W_q , W, L _q, L are used to calculate time in a queue, time in system, line length and number in the system respectively.

If we examine the expressions where p₀ has the value of 0.20 and p₁ is 0.16, p₂ is 0.128, and p₃ =0.124; these numbers are from the general equation p _n = (1-p) p ^{n .}

This can be interpreted for the probabilities that 0, 1, 2, and 3 people are in the system. Thus, an employee is idle if there are zero people in the queue 20% of the day.

An arriving customer has a 0.8 probability of having to wait before he or she can be

serviced.

The following qualities suggest a congested condition of this system. This condition occurs when:

W = 1 hour, W_q = 0.8 hr or 48 minutes, L = 4 customers, and Lq = 3.2 customers.

The ratio mean time in queue to mean service is 4, that is, 48/ 12, which is lambda/mu.

Organizations are ubiquitous. They are necessary to accomplish complex tasks. To be serviced by almost any organization, one must stand in a queue. We discovered what was happening during the peak periods of transactions, and how many employees would have to be scheduled to minimize waiting time. Therefore, this program gives a manager a way to study the various alternatives in scheduling, which could be used to optimize employees and their work schedules, alleviating waiting.

This project used the queueing theory to analyze customer time in a queue in order to determine an optimal number of employees to schedule in any service industry and provided the computations required for the analysis of any system that features a waiting line (queue).

We would like to express our sincere gratitude to the following:

The instructors of the Supercomputing Challenge Teacher Training Session of June 1999: David Kratzer, Gina Fisk, Chris Karr, Karin Wiburg Ph.D., and Sharon Benson, who have made this report possible.

Nolan Gray, Mike Fisk, and Shaun Cooper for their support in not only judging these presentations, but also being available to answer our questions.

New Mexico State University and Los Alamos National Laboratories for providing the venue, the computer labs, and funding to increase our knowledge of the Supercomputing Challenge.

Lastly, all the little people (students) who will have to be subjected to this intense situation in the years to come. Without their creation of coding to find the solutions to the problems of the next generation, all of us would have more difficult lives.

Bolch, Gunter, Greiner, Stefan, de Meer, Hermann, and Kishor S. Trivedi. (1998).

Evaluation with Computer Science Applications. New York: John Wiley &

Sons, Inc.

Davis, William S. and Yen, David C. (1999). Systems Analysis and Design: Information

System Consultant’s Handbook. Boca Raton, Florida: CRC Press.

Dshalalow, Jewgeni H. (1997). Frontiers in Queueing: Models and Applications in

Science in Engineering. Boca Raton, Florida: CRC Press.

Enns, S. T. (1999). A simple spreadsheet approach to understanding work flow in

production facilities. Total Quality Management, Abingdon.

Glass, Victor and Cahn, Ellen S. (1997). "A queueing model of organization structure."

Journal of Business and Economic Studies 3 , 13-28.

He, Qu-Ming & Marcel F. Neuts. (1997). "On Episodic Queues." Society for Industrial

Robertazzi, Thomas G. (1994). Computer Networks and Systems: Queueing Theory and

Performance Evaluation. New York: Springer-Verlag.

Standard Template Library. (1999). http://www.la.unm.edu 8001/cs259/stl_doc/

Clement Hudson Bachelor of Arts in Physical Education with a minor in Mathematics – Western New Mexico University; Masters of Arts in Mathematics and Composite Studies - Western New Mexico University; High School Teacher of Physics, Supercomputing Challenge, and Math at Tularosa High School – 28 years. Endorsements in Math, Science, Physical Education, and Coaching. Who’s Who Among American High School Teachers. Excellent and extensive programming ability. Ten years experience in Supercomputing Challenge with a finalist project in 1997.

Albert Simon Bachelor of Science Business Administration - University of Maryland; Master of Business Administration – Southern Illinois University at Edwardsville; Master of Science in Education - Secondary Education. Teach Computer Science – AP , Adventures in Supercomputing , American Government, Economics, and World History. High School teacher for seven years at Alamogordo High School and College Instructor for six years at NMSU–Alamogordo in Education, having taught computer literacy and personal finance. Who’s Who Among American High School Teachers. Seven years experience in Supercomputing Challenge with a finalist project in 1999.

Margaret Suzukida Bachelor of Science in Food Science – University of Illinois Champaign-Urbana; Master of Science in Biochemistry – NMSU. Teaching certificate for secondary science. Thirteen years teaching experience at high school, junior high school, and community college level in Chemistry and as a gifted education facilitator. Two published scientific papers. NMSU–A associate faculty teaching excellence award and Who’s Who Among American High School Teachers.

Clare Riker Tinguely Bachelor of Arts in Accounting – Ohio Dominican College; Masters of Education in Educational Administration – Eastern New Mexico University; High School teacher of Computer Applications, English, and Yearbook – five years teaching experience at Alamogordo High School. Endorsements in Business, English, and Coaching. Who’s Who Among American High School Teachers. NSTA member. Excellent verbal and writing skills.

C++ program code

Actors Class Diagram

Entity Relationship Diagram

Sequence Diagram

State Diagrams

Activity Diagram

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// que.cc Study of the Queuing theory

// by 'THE' Tularosa Basin Team

//

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#include

#include

//***** notes *****

// lamda ---> arrival rate

// mu ---> service rate

// psi ---> traffic intensity or lambda / mu

// Note: psi must be < 1 or infinite lenth queue.

// n ---> number of customers in system (queue + service)

// p ---> steady state probabilities

// ==>

// p(0) = 1 - psi

// ==>

// p(n) = (1 - psi)(psi^n), n = 1, 2, 3,....

//

// W(q) ---> expected time in queue

// ==> E[time in queue]

// W(q) = lambda / [mu (mu - 1)]

//

// W ---> time in system

// ==> E[time in system]

// W = 1/(mu - lambda)

//

// L(q) ---> line length

// ==> E[line length]

// L(q) = lamda^2 / [mu(mu - lamda)]

//

// L ---> number of customers

// ==> E[number in system]

// L = lamda / (mu - lamda)

//

// pi ---> percentil

// pi(q) ---> high percentiles for time in queue

// pi(w) ---> high percentiles for time in system

//

// ln ---> the natural logarithm

// pi(q)[90] = W * ln(10 * psi)

// pi(q)[95] = W * ln(20 * psi)

// pi(w)[90] = W * ln(10)

// pi(w)[95] = W * ln(20)

void main()

{

float lam = 0; // lamda --> arrival rate ( people per hour);

float mu = 0; // mu --> service rate ( people per hour);

cout << "\n Input customers arrived per hour " ;

cin >> lam ;

cout << "\n Input customers serviced per hour ";

cout << "\n NOTE: if customers arrivel is more than can be "

<< "\n servied the will grow very long very quickly. ";

cin >> mu;

float si = lam / mu;

cout << "\n Traffic intensity rate is " << si ;

int n = 0; // number of customers in system ( queue + service)

float p[22];

p[n] = 1 - si;

cout << "\n p[" << n << "] = " << p[n] ;

for ( n = 1; n < 20; n++)

{

p[n] = (1 - si) * ( pow(si, n));

cout << "\n p[" << n << "] = " << p[n] ;

}

float Wq; // expected time in line

Wq = lam / (mu * (mu - 1));

cout << "\n Expected time in line is " << Wq << " hours ";

cout << " or " << Wq * 60 << " minutes ";

float W ; // time in the system

W = 1 / (mu - lam) ;

cout << "\n Time in the system is " << W << " hours. "

<< " or " << W * 60 << " minutes. ";

float Lq; // line length

Lq = (lam * lam) / (mu * (mu - 1));

cout << "\nLength of the line is " << Lq;

float L; // number of customers

L = lam / (mu - lam);

cout << "\nNumber of customers in line are : " << L;

// pi --> percentil

// piq --> high percentiles (90 to 95%) for time in queue

float piq90, piq95 ;

piq90 = W * log(10 * si); // 10 is used to get 90%

piq95 = W * log(20 * si); // 20 is used to get 95%

cout << "\n 90% of customers will be through queue in ";

cout << piq90 << " hours or " << piq90 * 60 << " minutes ";

cout << "\n 95% of customers will be through queue in ";

cout << piq95 << " hours or " << piq95 * 60 << " minutes ";

// piw --> high percentiles for time in system

float piw90, piw95;

piw90 = W * log(10);

piw95 = W * log(20);

cout << "\n 90% of customers will be through system in ";

cout << piw90 << " hours or " << piw90 * 60 << " minutes ";

cout << "\n 95% of customers will be thorugh system in ";

cout << piw95 << " hours or " << piw95 * 60 << " minutes ";

cout << "\n\n";

}