PRODUCTION SYSTEMS AND OPERATIONS MANAGEMENT

©1998 Joseph Martinich. All rights reserved. None of these materials can be stored, transmitted or reproduced by any means (electronic, mechanical, photocopying or otherwise) without the written permission of Joseph Martinich. These materials may be used by students in classes taught by Professor Martinich at University of Missouri - St. Louis.

WAITING LINE CONSIDERATIONS IN PRODUCTION SYSTEMS

Queueing Theory

• The study of how queues (waiting lines) develop and behave as a function of the system characteristics.
• Queueing systems are made up of two entities:
• Customers: entities that require service
• Servers: entities that provide service to customers
• Queueing systems are an essential aspect of almost all production systems; both service and manufacturing

• The key element of queueing systems is randomness
• Typically average capacity > average demand; but queues develop because of randomness
• Example: Customers arrive at a bank at an average rate of 5 per hour. Average time to serve them is 10 minutes (i.e, the bank can serve 6 per hour on average)

Customer #	Time of arrival	time in queue	service time	departure time
1	8	0	12	20
2	10	10	11	31
3	13	18	6	37
4	29	8	5	42
5	45	0	7	52
6	63		14

• Note: the actual average service time was 8.2 minutes (faster than average)
• Even though the average arrival rate (demand) is substantially less than the average service rate (capacity), waiting occurs.

• Queueing systems occur everywhere

• Note: Customers and servers do not have to be humans

• Purpose of Queueing Theory
• To assist in the design and operation of queueing systems
• General Approach
• Specify the conditions or characteristics of the queueing system

• Use Mathematical models to estimate or predict how the queueing system would behave under these conditions
• The outputs from the queueing analysis are usually numerical measures of customer waiting times, average queue lengths, or fraction of customers desiring service that are served
• Note: The models used are Descriptive models, not Optimization Models
• These models estimate what will happen under the specified assumptions; they will not tell us what we should do.

• Two types of models and analysis
• Steady-state formulas (closed-form equations)
• When system characteristics are simple and steady
• Equations describe system performance as a function of the system characteristics
• Simulation
• When the design or operational characteristics of the queueing system are more complex
• We attempt to mimic how the actual system would behave in practice (on computer)

• Main Characteristics that Must be Specified
• Customer Characteristics

1. Size of the Customer Population

• Infinite
• Finite

2. Composition of the Customer Population

• Homogeneous
• Heterogeneous

3. The Customer Arrival Process

• Probability distribution for the interarrival times

• Usually a poisson arrival process (exponentially distributed interarrival times)
• l is the average arrival rate of customer

1/l is the average time between arrivals

• How do customers behave when all servers are busy?
• Well-behaved
• Balk
• Renege
• Service Characteristics

1. Service Mechanism or Process

• Probability distribution for service times
• m is the average service rate possible (capacity) per server

1/m is the average service time per customer

2. Queue Discipline

• Rules for selecting the next waiting customer for service
• FCFS; SPT

• System Configuration Characteristics
• Number and Type of Servers
• Configuration of Servers
• Queue Capacity
• Number of Waiting Lines

• Notation
• l = average rate of arrivals in customers/unit time
• m = average rate at which a server can serve customers in customers/unit time
• s = number of servers (sometimes called service channels) in the system
• Measures of System Performance
• W_q = average time customers spend waiting in the queue
• W_s = average time customers spend in the system

Note: W_s = W_q + 1/m

• L_q = average number of customers waiting in the queue

Note: W_q = L_q / l

• L_s = average number of customers in the system.

Note: L_s = L_q + l/m

• Note: These are usually assumed to be steady-state averages.

• Additional notation
• r = the utilization factor
• Fraction of the time the servers are busy
• Fraction of service capacity utilized
• Typically r = l / s m
• P_n = the probability or fraction of time that exactly n customers are in the system
• P_>n = the probability or fraction of time at least n customers are in the system
• P_{W =} P_>s = probability a customer will have to wait in a queue

• Capacity Utilization and a Queueing System Property
• As the utilization factor increases above approximately 0.70-0.80 and approaches 1.00, the average waiting times and queue lengths increase exponentially
• Called the "exploding queue" phenomenon
• Trying to utilize servers at 90+% (real-time) utilization will create poor customer service

• The Kendall-Lee Notation for Queueing Systems
• a/b/s
• "a" specifies the arrival process
• If a = M => poisson arrivals (interarrival times are exponentially distributed)
• If a = G => general distribution
• If a = D => deterministic
• "b" specifies the service process
• If b = M => exponential service times
• If b = G => general distribution
• If b = D => deterministic
• s = number of parallel servers

• M/M/1 Systems
• Assumptions

1. Arrivals are generated by a poisson process

2. Service times are exponentially distributed

3. There is one server

4. Any queue discipline can be used

5. Queue capacity is infinite

6. The customer population is homogeneous and infinite in size

7. Customers are well-behaved; no balking or reneging occurs

• Steady-state formulae.

r = l/m

L_q = l²/[m(m-l)]

L_s = l/(m-l)

W_q = l/[m(m-l)]

W_s = 1/(m-l)

P_n = (1-l/m)(l/m)ⁿ for n = 0,1,2,...

P_>n = (l/m)ⁿ for n = 0,1,2,...

Notice: P₀ = 1-l/m = 1-r = 1 - fraction of time the server is busy.

• Example
• American Chemicals International (ACI) makes thousands of custom chemicals. The products are made in small batches at over a hundred mixing stations. Because of the variation in chemical types and batch sizes, batches are completed throughout the plant at totally random times that approximate a poisson arrival process (i.e., the time between batches being completed is exponentially distributed). On average six batches are finished per hour.
• For safety and environmental reasons all mixing tanks must be cleaned at a special cleaning station. When a batch is completed the tank is transported to the cleaning station and cleaned by the cleaning crew. Only one tank can be cleaned at a time.
• The current cleaning crew is made up of two workers, who use special cleaning and containment equipment. The time to clean a tank is exponentially distributed with an average cleaning time of 7.5 minutes.
• While a tank is being cleaned or awaiting cleaning, the company estimates that it costs the company $80 per hour in wasted labor (the two-person production crew that usually performs the production is idle while it waits for the cleaning), and the cost of the idle tank and other production equipment and facilities.

• Occasionally mixing tanks (and production crews) must wait more than 30 minutes in line before the cleaning crew can start cleaning the tank. Consequently the company is considering ways to speed up the cleaning. The company estimates that if it were to add a third worker to the cleaning crew the average cleaning time would decrease to 6 minutes per tank. The manager of the support services department, which includes the cleaning station, opposes the addition of a worker because the current cleaners are only busy approximately 75% of the time, and an additional cleaner would cost $24 per hour to keep on staff.
• Should the company add an additional cleaner? Why or why not.

• The cleaning station is an M/M/1 queueing system, where the tanks are the customers, and the cleaning station is the single server. (Note that the number of cleaners affects the speed of service, but not the number of servers - only one tank can be cleaned at a time).

l = 6 tanks/hour arriving at the cleaning station

For the current two-person cleaning crew:

1/m = 7.5 min./customer => m = (1/7.5) customer/min.

=> m = 8.0 customers/hr

Then:

r = l/m = 6/8 = 0.75.

L_s = l/(m-l) = 6/(8-6) = 3.0 customers (tanks)

So on average there are three tanks and production crews idle at a time. At $80 per hour the lost production time is costing the company 3.0 x $80 = $240 per hour.

[An alternative approach is to notice that 6 tanks require service per hour on average. On average, each one spends W_s = l/(m-l) = 1/(8 per hr. - 6 per hr.) = 1/2 hour waiting in the queueing system (in the queue plus being cleaned). So each tank cleaning costs 0.5 hr x $80 per hr = $40 in lost production time. The cost per hour for lost production is 6 cleanings per hr. x $40 per cleaning = $240 per hour.)

• If the company adds an extra worker to the cleaning crew this will cost $24 per hour. We can compute the average lost production cost as follows.

1/m = 6 min/customer => m = 1/6 cust/min = 10 cust/hr

L_s = l/(m-l) = 6/(10-6) = 1.5 customers (tanks)

So on average there will be 1.5 tanks and production crews idle at a time. At $80 per hour the lost production cost is 1.5 x $80 = $120 per hour.

So the company would save ($120 - $24) = $96 per hour by hiring an extra cleaner, even though the three cleaners would now be busy only l/m = 6/10 = 60% of the time.

• Suppose the manager of support services is evaluated on person-hours of direct labor per tank cleaned. Should (would) she support adding another cleaner?

• M/M/s Systems
• Same assumptions as M/M/1 except there are s servers, with one waiting line.
• Formulas

r = l/sm

s-1

P₀ = 1/{ S [(l/m)ⁿ/n!] + [(l/m)^s/s!][1-(l/ sm)]^-1 }

n=0

P_n = [(l/m)ⁿ]P₀/ n! for 0 < n < s

[(l/m)ⁿ]P₀/ [s! (n-s)!] for n > s

L_q = [(l/m)^s r P₀]/[s! (1-r)²]

L_s = L_q + l/m

W_q = L_q/ l

W_s = W_q + 1/m

• Example:
• The MIS and Marketing Departments have each decided that they are going to buy their own photocopiers, rather than using a central campus facility, which requires a 5 minute walk to reach. The departments are approximately the same size and each has estimated that department members use the photocopier approximately 8 times per hour. Visits to the photocopier approximate a poisson process.
• The time to perform the photocopying is exponentially distributed with an average time of 5 minutes per use.
• The MIS department is located on the second floor, and the Marketing department is located on the third floor of the Business Building, so each department wants to purchase its own photocopier.
• On average, how long will a person wait to photocopy a document?
• Suppose the University put both photocopiers on the same floor, and it took 45 seconds extra each way to go between floors. Would this be better?

• Each Department Has Its Own Copier (and each department has exclusive use of its copier unless the other department's copying is broken)
• Each department copier is an M/M/1 system with
• l = 8 customers per hour
• 1/m = 5 min per cust. =>

m = 1/(5 min per cust.) = 12 cust. per hr.

• W_q = l/[m(m-l)] = 8[12(12-8)] = 1/6 hour

= 10 minutes per customer

• L_q = l²/[m(m-l)] = 8²/[12(12-8)]

= 1.5 customers at each photocopier

• Two Copiers on One Floor Are Shared by the Two Departments
• The "copy area" is an M/M/2 system with
• l = 16 customers per hour
• 1/m = 5 min per cust. =>

m = 1/(5 min per cust.) = 12 cust. per hr.

• r = 16/[2(12)] = 0.67
• From the formula for P₀ or from the Tables we find that P₀ = 0.2
• So L_q = [(l/m)^s r P₀]/[s! (1-r)²]

= [(16/12)² (2/3)(0.2)]/[2!(1-2/3)²]

= 16/15 = 1.067 customers

• W_q = L_q/ l = (16/15)/ 16 cust. per hr.

= 1/15 hr. per cust. = 4 minutes

• So even with a 45 second walk between floors, the users would be better off with two copiers together rather than exclusive use of their own copier.

• Benefits of Pooling Servers

The result from this example hold in general:

• If customers are homogeneous (with respect to their service time distributions), then better service can be provided by pooling the servers and having one queueing system, rather than having s separate queueing systems.
• The main reason is that with several single-server systems, you can have customers waiting for service in one system while the servers in another system are idle. This won't happen with a multi-server system. Note: that the servers do not work any harder in the pooled system; they just operate more efficiently.

• M/G/1 Systems
• Same assumptions as M/M/1 except the service times can have any probability distribution, and we assume we know the standard deviation of the service distribution, s.
• r = l/m

L_q = [l² s^{2 +} r² ] / 2[1-r]

L_s = L_q + l/m

W_q = L_q/l

W_s = W_q + 1/m

• Note: All other things being equal, the larger the variation in service times, the longer the queues and the longer the waiting time

• M/D/1 System
• Deterministic service times; that is, s = 0.
• Then L_q = r² / 2[1-r]

• Example:
• A company uses a batch flow production process. Jobs (customer orders) arrive at the company according to a poisson process at the rate of 5 per day.
• At the first production stage the processing times are randomly distributed with an average time of 4 hours and a standard deviation of 4 hours.
• The company works 24 hours a day.
• Compute the average number of orders awaiting processing at the first stage, and the average time it takes a job to make it through the first stage.
• l = 5 cust. per day; 1/m = 4 hours = 1/6 day, so m = 6 customers per day; s = 4 hours = 1/6 day; r = 5/6.
• L_q = [l² s^{2 +} r² ] / 2[1-r]

= [5²(1/6)² + (5/6)²] / 2[1-(5/6)] = 4.167

• W_q = L_q/ l = 4.167 / 5 cust per day

= 0.833 day

• W_s = W_q + 1/m = 0.833 + 0.167 = 1.0 day

• Now suppose we revised the production process so that the average processing time was still 4 hours, but the standard deviation is reduced to 1 hour.
• L_q = [l² s^{2 +} r² ] / 2[1-r]

= [5²(1/24)² + (5/6)²] / 2[1-(5/6)] = 2.21

• W_q = L_q/ l = 2.21/ 5 cust per day

= 0.443 day

• W_s = W_q + 1/m = 0.443 + 0.167 = 0.610 day
• So reducing service time variation, dramatically reduces waiting time and average queue length

• Variation and Queueing Systems

1. The less variation there is in the arrival pattern and the service times, the less waiting that occurs

• Pace customer arrivals
• Use appointments in human systems
• Assign different customer groups to different times of the day

2. Slower servers can produce less customer waiting if they have less variable service times

• Less variation in service times
• Servers can be faster, on average, with more homogeneous customers
• Differential levels of service can be provided to different customer groups
• Separate queues make it possible to use delay avoidance tactics, such as cash only lines. Customers offered access to a faster server in exchange for better behavior on their part.
• Note that there is a loss of pooling efficiencies by having separate servers for different customer groups, but as long as idle servers can serve waiting customers of another type, there is little loss of pooling effects

• Serial Queues and Queueing Networks
• Made up of a series of queueing subsystems
• A multi-stage production process
• Operating at high utilization with high variation can create very large queues and waiting (large in-process inventories and long throughput times)
• Variance reduction actions at one stage can often reduce waiting at successive stages as well
• Example:
• A company uses a 5-stage, batch flow production process. Jobs (customer orders) arrive at the company according to a poisson process at the rate of 5 per day.
• At each production stage the processing times are exponentially distributed with an average time of 4 hours. (Note: this implies that the standard deviation is the service times is also 4 hours.)
• The company works 24 hours a day.
• Compute the average number of orders awaiting processing each stage, and the average throughput time (from time an order is received until it is completed).

• It is a mathematical fact that customers exiting an M/M/1 queueing system form a poisson process, with a departure rate of l. So the arrival of jobs at the next stage is a poisson process. Therefore each production stage is an identical M/M/1 queueing system, with

• l = 5 cust. per day; 1/m = 4 hours = 1/6 day, so m = 6 customers per day; s = 4 hours = 1/6 day; r = 5/6 = 0.83.
• Using either the M/M/1 formulas, or the M/G/1 with s = 1/6 day, we get

L_q = [l² s^{2 +} r² ] / 2[1-r]

= [5²(1/6)² + (5/6)²] / 2[1-(5/6)]

= 4.167 jobs

L_{s =} L_q + l/m = 4.167 + 0.833 = 5.0 jobs

W_q = L_q/ l = 4.167 / 5 cust per day

= 0.833 day

W_s = W_q + 1/m = 0.833 + 0.167 = 1.0 day

• So on average, at each stage there are 4.167 jobs waiting for processing; 0.833 jobs actually being processed; and the average job spends 0.833 day waiting in queue at the stage and 0.167 day being processed. For the system as a whole, there are 25 jobs in the system (waiting or being processed), and it takes a job an average of 5 days to get through the system, even though it only requires 0.833 day of actual processing.
• Suppose demand increased by 14% to 5.7 jobs per day. Then r = 5.7/6 = 0.95, and if we recompute these values we get

L_q = [l² s^{2 +} r² ] / 2[1-r]

= [(5.7)²(1/6)² + (5.7/6)²] / 2[1-(5.7/6)]

= 18.05 jobs

Ls = L_q + l/m = 18.05 + 0.95 = 19.0 jobs

W_q = L_q/ l = 18.05 / 5.7 cust per day

= 3.167 days

W_s = W_q + 1/m = 3.167 + 0.167 = 3.33 days

• At each stage there are an average of 18.05 jobs waiting and 0.95 jobs being processed, and the average job takes 3.33 days to get through each stage. So a 14% increase in demand causes the in-process inventory of jobs to increase 280% from 25 to 95 jobs, and throughput time to increase 233% from 5 days to 16.67 days.
• Now suppose we revised the production process so that the average processing time at each stage is still 4 hours, but the standard deviation is reduced to 1 hour. The first stage is an M/G/1 queue with

L_q = [l² s^{2 +} r² ] / 2[1-r]

= [(5.7)²(1/24)² + (5.7/6)²] / 2[1-(5.7/6)]

= 9.59 jobs

L_s = L_q + l/m = 9.59 + 0.95 = 10.54 jobs

W_q = L_q/ l = 9.59/ 5.7 cust per day

= 1.682 days

W_s = W_q + 1/m = 1.682 + 0.167 = 1.849 days

• So at the first stage the variance reduction cuts the number of waiting jobs and the average waiting time almost in half.

• Each of the successive stages is a G/G/1 queue with much less variation in arrival times than at stage 1, so the average queue length and waiting time is even less than at stage 1. In fact L_q decreases to less than 5 at stage 2 and continues to decrease at successive stages; a similar thing occurs for W_q.. Thus, for the entire system, the overall inventory and throughput time decrease by over 75%.
• Suppose all variation in processing time could be eliminated so s = 0.
• Then the first stage is an M/D/1 queue with

L_q = r² / 2[1-r]

= (5.7/6)² / 2[1-(5.7/6)]

= 9.025 jobs

L_s = L_q + l/m = 9.025 + 0.95 = 9.975 jobs

W_q = L_q/ l = 9.025/ 5.7 cust per day

= 1.583 days

W_s = W_q + 1/m = 1.583 + 0.167 = 1.75 days

• More importantly, jobs leave stage 1 almost evenly spaced. Each succeeding stage is approximately a D/D/1 system, so L_q = 0 and

W_q = 0 for stages 2-5. Thus, the total system inventory is less than 14 jobs (compared to 95 with the original variance), and throughput time is less than 2.5 days (compared to 16.67 days with the original variance.)

• Reducing processing time variance automatically reduces inventories and throughput time, with increasing benefits at each succeeeding stage of production.

• Psychological and Other Factors in Queueing

1. Nonlinear Disutility

• Convex curve with threshold or S-Shaped Curve
• If Threshold is five minutes, then a system where everyone waits 4 minutes may be better than one where 80% wait one minute and 20% wait 10 minutes.
• Fire losses and health emergencies are nonlinear

2. Social Justice

• People hate to be jumped over by later-arriving customers
• Injustice can be inefficient: Race of the barges

3. Waiting is unpleasant and costly because environment is often not enjoyable, and there is no opportunity for customers to utilize waiting time

• Make waiting environment pleasant and productive (e.g., TV, magazines, art show, entertainment, stock quotes, work tables)

• Involve customers in the service process to speed up their own service (e.g., automated phone systems, internet)
• Create intentional delays to distract customers form the wait (a last resort)

4. Provide Accurate Feedback and Information on Waiting Times

• Phone systems that inform caller of the waiting time
• Walt Disney World

URL: http://www.umsl.edu/~jmartini/pomnotes/webqueueing.htm
Page Owner: Joseph Martinich (Joseph.Martinich@umsl.edu)
Last Modified: October 27, 1998