Publications: 75 | Followers: 1

## 幻灯片 1 - Columbia University

Publish on Category: Birds 0

An Investment Planning
In a barber shop businessPaxton ZhouPaul Kim
Basic parameters
Customers arrives according to a Poisson distributionMale and female has thesame arrival rate of 3 customers per hourProcessing time for each customer is uniformly distributedMale: [15, 75] min per customerFemale: [21, 81] min per customer5 barbers; 2 only handle male hair, 2 only handle female hair, the fifth barber (the master) can handle both male and female hair and is 2x faster than the other barbers
The no-queue scenario
Master
Male Barber 2
MaleBaber 1
Female Barber 4
Female Barber 3
Customers arrive Poisson (λ=3) for both male and female
We assume that customers have no patience—if no barber is free they will just leave and go to another barber shop near byAs a result, we assumeimmediate blockingwhen all “machines” are busy
List scheduling (L-S) method:FCFSWhen a customer arrivesIf male, assigned to male only barbers (B1, B2) firstIf no male barber available, assign to master barber (B5)If master barber is busy, the customer leaves for another barber shopIf Female, assign to female only barbers first (B3, B4)If no female barber available, assign to master barberIf master barber is busy, the customer leaves for another barber shopThe barber shop opens for 8 hours. Any customer who arrives after 8 is not admitted. But barbers still need to work overtime to serve, for example, a customer who arrives at 7:50 and still need an hour to process
Run simulation 10,000 times and take average
Result of List-scheduling (L-S)The Average make span is (in hours): 8.666184804397565The Average # of Male customer served: 17.578The Average # Female Customer Served: 16.978The Average # of Total Customer Served: 34.556
Let’s think of how to improve the system to serve more customers, while minimizing themakespan
The list-scheduling method assign customers to gender constrained barbers (barbers who only handle male or female)Can we improve the system by prioritizing the master barber, who is 2x faster and can handle both male and female?
Fastest Barber First (FBF) method:FCFSWhen a customer arrivesIf male, assigned to B5If B5 is busy, assign to B1 or B2, whoever is availableIf B1 and B2 are busy, the customer leaves for another barber shopIf Female, assigned to B5If B5 is busy, assign to B3 or B4, whoever is availableIf B3 and B4 are busy, the customer leaves for another barber shopSame as above, the barber shop opens for 8 hours only
Run FBF 10,000 times and take average, compare with L-S method
There seems to be a very minor improvementWe introduce another master barber B6 and see whether prioritizing fastest machines would improve the system
Compare Fastest Barber First with 2 master barbers(FBF-2) to List Scheduling with 2 master barbers (L-S-2)FCFSFBF-2: Assign new arrivals to B5 or B6 first, then to genderconstraintbarbersB1~4L-S-2: Assign new arrivals to B1~4, if these gender constraint barbers are busy, assign to B5 or B6Same as above, the barber shop opens for 8 hours only
Run L-S-2, FBF-2 10,000 times and take average, compare with previous methods
There is no improvement in terms of # of customers served, actually, fewer (very little) customers are servedThere very limited reduction inmakespanHiring more barbers does not reducemakespan!
The queue scenario
Master
Male Barber 2
MaleBaber 1
Female Barber 2
Female Barber 1
Customers arrive Poisson (λ=3) for both male and female
We assume that customers are willing to wait for at most 30 minutes—if no barber is free then they will just leave and go to another barber shop near by
Waitingseats
Introducing a Queue/ waiting area
We compare the performance of L-S, FBF. L-S-2, FBF-2
Having the queue does not make FBF any better compared to L-SFBFresults in 2% less customers being served
Having a queue does not substantially increasesmakespan, but we can serve more customers keep the queue!Do not hire one more master barber: only to serve 3~4 more customers is not worth it as an average barber serves more than 8 under the 5 barber systemHaving a queue improves the system by serving more customers, while not dramatically increasing themakespan!.
Should we have a queue/ build a waiting area?
If thePoissionarrival rate is very low, then whether or not do we have a queue does not make a big differenceWhen a customer came in, one barber maybe idle and probably have been waiting for a long timeBut if the arrival rate is high (much higher thanλ=3 per hour,i.ea holiday),:Having a queue will allow the barber shop to serve more customers (more arrivals will be “stored “ in the queue for later processing)The only drawback is that themakespancould be higher (customers in the queue may force barbers to work longer)We run a simulation underλ=10, and see if having a queue will benefit us. We also compare L-S to FBF
Having a queue allows us to serve 5 more customers per day by increasing 30minsmakespan this is desirable as each customer has an average processing time of more than 30minL-S-2 is not desirableHiring an extra master barber allows us to serve 12 more customers. This may be desirable, as originally, a master barber processes more than 12 customers we now serve more customers without suffering form diminishing return
λ=10
A growing queue!
Under low arrival rate
This is intuitiveA queue is not requiredNo need to hire an extra master barber not many customers out there to serveFBF is optimal (example: the shop is quite empty and most of the barbers idle, a customer arrives at t=7:50 you want to assign him/her to the available fastest barber to reducemakespan)
Our conclusion:
Under normal arrival rate; we need to implement a queue; we do not hire an extra master barber; and either L-S or FBF is optimalUnder high arrival rate, we need a queue; we may hire an extra barber; FBF-2 is optimalUnder low arrival rate, a queue is not necessary; we do not need to hire an extra master barber; FBF is optimal

0

Embed

Share