piz

An Intellectual Exercise

34 posts in this topic

I have a real-world problem to solve. The following is an analogy that captures the essence of the problem. I've been struggling with this for months and cannot come up with an answer that seems reasonable, i.e. that doesn't unduly inconvenience "old customers" (see below):

For a single day, you are selling widgets. They are very popular. Customers form a line to wait to buy them, because the nature of the product allows only one to be sold at a time. However there is no limit to the number of widgets a customer may buy on any given day, so they may re-enter the line at any time to buy another widget. Also, two or more customers may buy a single widget as a group.

Your goal is to sell to as many customers as possible (this has an effect on how you treat groups). You want to encourage customers who are buying their first widget, so you'd like to let them skip to the front of the line. However, you also don't want to anger those customers who already bought a widget by putting them off for too long if there are many new customers. You open for business at 9:00 AM, and your agreement with the owner of the space you are using mandates that at 5:00 PM you must close, regardless of how many are waiting in line.

What rules would you establish to most effectively arrange and rearrange the order of the line as customers enter and re-enter, to satisfy these requirements? The more algorithmic the rules, the better.

Share this post


Link to post
Share on other sites
I have a real-world problem to solve. The following is an analogy that captures the essence of the problem. I've been struggling with this for months and cannot come up with an answer that seems reasonable, i.e. that doesn't unduly inconvenience "old customers" (see below):

For a single day, you are selling widgets. They are very popular. Customers form a line to wait to buy them, because the nature of the product allows only one to be sold at a time. However there is no limit to the number of widgets a customer may buy on any given day, so they may re-enter the line at any time to buy another widget. Also, two or more customers may buy a single widget as a group.

Your goal is to sell to as many customers as possible (this has an effect on how you treat groups). You want to encourage customers who are buying their first widget, so you'd like to let them skip to the front of the line. However, you also don't want to anger those customers who already bought a widget by putting them off for too long if there are many new customers. You open for business at 9:00 AM, and your agreement with the owner of the space you are using mandates that at 5:00 PM you must close, regardless of how many are waiting in line.

What rules would you establish to most effectively arrange and rearrange the order of the line as customers enter and re-enter, to satisfy these requirements? The more algorithmic the rules, the better.

One more note on groups: members of a group may re-enter the line either in the same group, in different combinations of groups, or as individuals.

Share this post


Link to post
Share on other sites

I am assuming there is more than one type of widget available, and more than one widget may be purchased between 9 to 5. If customers can be grouped by transaction efficiency regardless of the particular widget they came for on that day sometime between 9 to 5, and if customers can use other customers' widgets (meaning customers must check their inventory of widgets and the widgets used by those around them to see if they can use any held or existing widgets, given that a widget purchase log is explicitly created and classified after each transaction. Those unable to express what widget type they need or who did not realize a widget type did not apply to their needs are also identified.), I refer you to Heppner and Grenander's stochastic model of individuals interacting in beneficial competition in The Ubiquity of Chaos.

Share this post


Link to post
Share on other sites
Why not just have two lines: one for new customers and one for repeaters?

That's the "alternate old/new" strategy, which I've tried and found to cause unacceptably long waits. Depending on exactly how it's implemented, either old customers wait longer and longer each time they reenter the line or new customers wait much longer between their first and second widget than the average wait time between any other successive widgets (2nd/3rd, 7th/8th, whatever) for any customer.

What I'm aiming for is something like: if you waited an hour for your first widget, the wait for each of your succeeding widgets should be as close to an hour as possible (less than an hour is, of course, acceptable).

Share this post


Link to post
Share on other sites

I don't understand why giving line preference to new customers is anticipated to increase the number of customers served. Won't you naturally have more customers as word of your widgets spreads? And if you already have so many customers that you limit the number of widgets per customer to 1, then the problem isn't customers but serving them faster. Doesn't that mean you need to increase production?

Share this post


Link to post
Share on other sites

Let me suggest that you are attempting to solve the wrong problem. Instead of attempting to prioritize customers within the constraints, spend the time eliminating the worst constraint which appears to be that each orders must be no more than one unit.

For example, if each widget order is actually a page request, can the page experience for existing customers be personalized so that they receive multiple items of content relevant to them in a single page request instead of re-queuing.

Share this post


Link to post
Share on other sites
I don't understand why giving line preference to new customers is anticipated to increase the number of customers served. Won't you naturally have more customers as word of your widgets spreads? And if you already have so many customers that you limit the number of widgets per customer to 1, then the problem isn't customers but serving them faster. Doesn't that mean you need to increase production?

It's not about increasing the number of customers, but serving as many different customers as possible in the time allowed while not driving off those who have already been served, when they want more, by making them wait overly long. It may seem strange, but if I accomplish this goal then word of the "widgets" will spread and I will do more business.

Also keep in mind that this is a one-day exercise. In the real world this occurs over and over again, but each given day is a self-contained "event," so I cannot, for example, give out vouchers to those who don't get served today to be used tomorrow. Tomorrow I have to begin over again as if today never happened. That's why I stipulated that this is a one-day-only event.

Let me suggest that you are attempting to solve the wrong problem. Instead of attempting to prioritize customers within the constraints, spend the time eliminating the worst constraint which appears to be that each orders must be no more than one unit.

For example, if each widget order is actually a page request, can the page experience for existing customers be personalized so that they receive multiple items of content relevant to them in a single page request instead of re-queuing.

Unfortunately, for purposes of this exercise you must take the conditions as "metaphysical givens." They cannot be changed. Production can't be increased: the analogous element in the real world problem absolutely limits "acquisition" of the item in question to one at a time, and it is not possible to produce more of the item. Also, the nature of the item cannot be changed: it is as if I were doling out hydrogen atoms - they cannot be customized, made larger, or in any other way altered.

In fact, forget about the widgets: what matters is the handling of the customer queue.

Share this post


Link to post
Share on other sites
It's not about increasing the number of customers, but serving as many different customers as possible in the time allowed while not driving off those who have already been served, when they want more, by making them wait overly long. It may seem strange, but if I accomplish this goal then word of the "widgets" will spread and I will do more business.

Well, good luck then.

Share this post


Link to post
Share on other sites

Instead of FIFO, index the wait queue by an adjusted wait time, which would simply add a priority factor based upon the customer relationship to the actual wait time. The customer relationship classification could be reset on every customer each day or retained to account for prior activity.

For the new customers, the factor would effectively give them a relatively lower average wait time. Frequent customers would be penalized with a factor that would increase their average wait time, but only when they are in resource competition with others who have been prioritized.

Several ranges for relationship categories could be set: new, low, moderate, and high frequencies.

The adjustment factor should be set so that the variance from average wait time is within an acceptable service level for the repeat customers.

Essentially, allowing some customers to cut in line but not so far as to interfere with those that have already been waiting a significant amount of time.

Share this post


Link to post
Share on other sites

Piz, I really do not understand how this can be called a "real-world problem" as in the real world you would just open another distribution site. But, I am willing to try according to your stated guidelines which I am not sure I fully understood.

I would not penalize the repeat buyer by making him wait as it is their repeat business that will develop the most referrals long-term and hence exapand your sales/profit. As a business owner you cannot know what the first time buyer is thinking about the product until they come back for another purchase. It is also the referrer that will do the talking and explaining away the problem of waiting for the product. It is their validity with the possible client that will get your product sold without you having to do much explaining. For example, "Jim, this product is great, but there is only one place to get them and the wait is long the first time but worth it."

The business owner generally has three different types of customers of which two are similar. The two clients that are similar are the referred and the non-referred. The third client is your returning customer who is bringing you the new referrals. I would attempt to set up a ticketing system that would be in accordance to which type of client they are. You could either have a person or machine give out purchasing tickets in accordance to the type of customer. Once again an example might be helpful. If it is the middle of the day and one of your returning customers comes in and a ticket would be handed out that would allow him to basically skip 3 non-returning cusotmers. This could be done without the new customers knowing by giving them tickets that gave numbers something like, RC1. For the non-referred clients (which have not been told about the product as in my qoute from Jim above) you could also set up seperate tickets which allowed the non-referred customer to skip over 2 referred customers. The referred customer most likely already knows that there will be a line and that the product is worth it and does not need to cut, but must still be given a ticket. I would also recommend not having a line and just allowing the customers to wait in chairs around the edge of the waiting area. This will keep them from noticing that someone who came in later got to skip in front of them.

Aagin, I do not know if this is exactly what you are asking for nor what I would call a "real-world" solution, but I hope it is helpful.

Share this post


Link to post
Share on other sites
Piz, I really do not understand how this can be called a "real-world problem" as in the real world you would just open another distribution site. But, I am willing to try according to your stated guidelines which I am not sure I fully understood.

It's analogous to my real-world problem. However, the nature of that problem is that it's not possible to open more distribution sites. These are self-contained events where people queue up to use something that can only be used by one at a time. That "something" is what I called a "widget" in my example. Maybe I should have said that there's only one widget and that people queue up to use it, but there's little difference between having only one widget and having only one "window" for the passing out of widgets.

I would not penalize the repeat buyer by making him wait as it is their repeat business that will develop the most referrals long-term and hence exapand your sales/profit. As a business owner you cannot know what the first time buyer is thinking about the product until they come back for another purchase. It is also the referrer that will do the talking and explaining away the problem of waiting for the product. It is their validity with the possible client that will get your product sold without you having to do much explaining. For example, "Jim, this product is great, but there is only one place to get them and the wait is long the first time but worth it."

Yes, that's exactly the problem. I have to satisfy both new and returning customers by not making either of them wait "too long." As for "first-time buyers," this is a common, well-known product (i.e. everybody in the real world knows exactly what a "widget" is); it's the process of doling it out it that I'm trying to optimize.

The business owner generally has three different types of customers of which two are similar. The two clients that are similar are the referred and the non-referred. The third client is your returning customer who is bringing you the new referrals. I would attempt to set up a ticketing system that would be in accordance to which type of client they are. You could either have a person or machine give out purchasing tickets in accordance to the type of customer. Once again an example might be helpful. If it is the middle of the day and one of your returning customers comes in and a ticket would be handed out that would allow him to basically skip 3 non-returning cusotmers. This could be done without the new customers knowing by giving them tickets that gave numbers something like, RC1. For the non-referred clients (which have not been told about the product as in my qoute from Jim above) you could also set up seperate tickets which allowed the non-referred customer to skip over 2 referred customers. The referred customer most likely already knows that there will be a line and that the product is worth it and does not need to cut, but must still be given a ticket. I would also recommend not having a line and just allowing the customers to wait in chairs around the edge of the waiting area. This will keep them from noticing that someone who came in later got to skip in front of them.

Interestingly, your description is quite close to the real-world situation. Waiting customers don't really stand in line, but wait in a "seating area" until they are called up. They use the "widget" one at a time (or, as I said in the original post, two or more may use the widget at once, but there's only one widget. Or, more in keeping with my original description, there is only one "window" at which they can acquire a widget, though two or more may do so at the same time). The person (or machine - I hope to write a program to manage this for me) handing out "tickets" is me. More accurately, customers come up to me and put in a request for a widget, and I have to manage the timing of the requests so as to make wait time as equitable as possible, both not to discourage new customers and not to upset repeat customers. It's the wait time that I must optimize. The means of dealing with skipping over other waiting customers is precisely the problem I'm trying to solve.

Also, it's policy to announce the rules for how waiting is to be managed, so everyone knows exactly how it will work. Making the process transparent means customer A can understand exactly why customer B gets called up before him, so if A's wait time increases, he at least knows why. Customer A also knows why he got preference over customer C earlier, which makes him more likely to accept B getting preference now.

By the way, to head off anyone who might suggest this, as much as I might want to I cannot allow the "price" of the widget to be subject to bidding or "bribes" (more accurately, tips). Doing so would damage my reputation and that of the company I work for, with a long-term result of losing business.

Aagin, I do not know if this is exactly what you are asking for nor what I would call a "real-world" solution, but I hope it is helpful.

Sorry for not divulging more of the nature of the actual situation, but I was hoping to distill it down to essentials, to eliminate going off on tangents or addresssing non-essential aspects. You've touched on exactly some of the things that make up the solution. It's the precise algorithm for managing (to use your term) the redeeming of the "tickets" that I'm trying to develop.

Share this post


Link to post
Share on other sites
Yes, that's exactly the problem. I have to satisfy both new and returning customers by not making either of them wait "too long." As for "first-time buyers," this is a common, well-known product (i.e. everybody in the real world knows exactly what a "widget" is); it's the process of doling it out it that I'm trying to optimize.

[...]

Waiting customers don't really stand in line, but wait in a "seating area" until they are called up. They use the "widget" one at a time (or, as I said in the original post, two or more may use the widget at once, but there's only one widget. Or, more in keeping with my original description, there is only one "window" at which they can acquire a widget, though two or more may do so at the same time). The person (or machine - I hope to write a program to manage this for me) handing out "tickets" is me. More accurately, customers come up to me and put in a request for a widget, and I have to manage the timing of the requests so as to make wait time as equitable as possible, both not to discourage new customers and not to upset repeat customers. It's the wait time that I must optimize. The means of dealing with skipping over other waiting customers is precisely the problem I'm trying to solve.

This sounds, in principle, like the problem faced by doctors, dentists, lawyers, hair stylists, and others providing personal services. The way they optimize their sales is to sell by appointment with, perhaps, serving those without an appointment if and when there is an opening in their schedule.

Share this post


Link to post
Share on other sites

Piz, my statement about the customer "not noticing" being skipped was not an attempt to be deceitful. It was an attempt to instead save you the time of explaining to everyone the reason for being skipped.

If you intend on writing a program to hand out the tickets why not have first time customers fill out a questionaire on a computer that when finished will give them the appropriate ticket. The return customers could use the same computers, but they would already be in the system and be given the appropriate ticket after they sign in. Of course until you have the program complete you could just have the new customers fill out paperwork that you file for later use.

If there are some parts of the day that are slower than others maybe you could recommend the return customers to come at those slower times. Of course knowing what your return customers do for a living might help when recommending the above action. You could find out some simple information through the original questionaire.

Share this post


Link to post
Share on other sites

Perhaps I missed it but I don't see any mention of the actual wait time for any given customer to get his widget and whether this wait time is dependent on the type of customer or not. (I think this is related to what Cometmaker dubbed transaction efficiency.)

Share this post


Link to post
Share on other sites

You can't solve it until it is mathematically well-defined. That is the root source of the current flailing. You need to precisely define and specify how you measure the preferences you describe, the quantitative nature of the waiting and how many customers there can be, and the constraints. Since you are looking for a way to order the customer requests based on such rankings and constraints the notion of "lines" is irrelevant. Once you do that you can formulate it as a discrete combinatoric optimization problem. Depending on how much you know in advance about what the customers want or are likely to want, it also depends on probabilities. Try very simple versions of the problem to start with and generalize from there to see how far you can go with it.

Share this post


Link to post
Share on other sites
You can't solve it until it is mathematically well-defined. That is the root source of the current flailing. You need to precisely define and specify how you measure the preferences you describe, the quantitative nature of the waiting and how many customers there can be, and the constraints. Since you are looking for a way to order the customer requests based on such rankings and constraints the notion of "lines" is irrelevant. Once you do that you can formulate it as a discrete combinatoric optimization problem. Depending on how much you know in advance about what the customers want or are likely to want, it also depends on probabilities. Try very simple versions of the problem to start with and generalize from there to see how far you can go with it.

Would good would this do in the real world? Even though we can ask a customer many questions in advance, their everyday situation can change dramatically and hence their willingness to wait. All the mathematically defined preferences will go to hell once the customer decides that they are unwilling to wait, get skipped, or the ability to use just one widget sends them looking for another widget company.

Share this post


Link to post
Share on other sites
You can't solve it until it is mathematically well-defined. That is the root source of the current flailing. You need to precisely define and specify how you measure the preferences you describe, the quantitative nature of the waiting and how many customers there can be, and the constraints. Since you are looking for a way to order the customer requests based on such rankings and constraints the notion of "lines" is irrelevant. Once you do that you can formulate it as a discrete combinatoric optimization problem. Depending on how much you know in advance about what the customers want or are likely to want, it also depends on probabilities. Try very simple versions of the problem to start with and generalize from there to see how far you can go with it.

Would good would this do in the real world? Even though we can ask a customer many questions in advance, their everyday situation can change dramatically and hence their willingness to wait. All the mathematically defined preferences will go to hell once the customer decides that they are unwilling to wait, get skipped, or the ability to use just one widget sends them looking for another widget company.

You can't solve the optimization problem without putting it into mathematical terms, and you can't solve the right problem without realistically basing that on the relevant facts reflecting at least what happens on average. You have to frame the problem mathematically before seeking a mathematical algorithm to solve it, but you had better make sure of your "assumptions" and look at what happens if they are violated.

This is done all the time in the field called "Operations Research" in which production and other kinds of processes are optimized. There will always be special cases of customers who are unique, but you can't satisfy all of them on a one at a time basis in a large scale operation; you can only optimize the expected outcome based on what you do know.

Share this post


Link to post
Share on other sites
You can't solve it until it is mathematically well-defined. That is the root source of the current flailing. You need to precisely define and specify how you measure the preferences you describe, the quantitative nature of the waiting and how many customers there can be, and the constraints. Since you are looking for a way to order the customer requests based on such rankings and constraints the notion of "lines" is irrelevant. Once you do that you can formulate it as a discrete combinatoric optimization problem. Depending on how much you know in advance about what the customers want or are likely to want, it also depends on probabilities. Try very simple versions of the problem to start with and generalize from there to see how far you can go with it.

Would good would this do in the real world? Even though we can ask a customer many questions in advance, their everyday situation can change dramatically and hence their willingness to wait. All the mathematically defined preferences will go to hell once the customer decides that they are unwilling to wait, get skipped, or the ability to use just one widget sends them looking for another widget company.

You can't solve the optimization problem without putting it into mathematical terms, and you can't solve the right problem without realistically basing that on the relevant facts reflecting at least what happens on average. You have to frame the problem mathematically before seeking a mathematical algorithm to solve it, but you had better make sure of your "assumptions" and look at what happens if they are violated.

This is done all the time in the field called "Operations Research" in which production and other kinds of processes are optimized. There will always be special cases of customers who are unique, but you can't satisfy all of them on a one at a time basis in a large scale operation; you can only optimize the expected outcome based on what you do know.

ewv is right, why don't you specify the value ratio of new to old customers' getting served within specific time parameters? Is this actually a narrative treatment of a data structures problem?

Share this post


Link to post
Share on other sites

If you have to close at a certain time no matter what I'd at least put that (and when you open) on a sign with a clock next to it.

That way people would stop queuing when they estimate that they'll not get another turn.

I think that would give better feedback.

I don't know about a certain queuing order but there could be a discount to someone who bought a new customer.

And maybe also a discount for those willing to use or buy (I'm a bit confused about that now) as a group so more could be served.

That is if ''widgeting'' in groups is faster.

Share this post


Link to post
Share on other sites

At this point I think I'm just confusing everyone, most likely because I did a poor job creating the analogy between the real-world situation and what I wrote. Naturally anyone should feel free to drop the exercise at any time.

For those willing to keep at it, I'll try a new and, I hope, better and simpler analogy:

There is one widget. People can only use it one at a time. In the course of a day customers can request to use the widget one or more times (most want more than one). Not everyone arrives at the same time. When closing time comes, the customer using the widget gets to finish, then everybody must leave, whether or not they've had a chance to use the widget. Each day, all customers are treated as if they've never used the widget before (i.e. initially they're all "new" customers*). The goal is to manage the queue of customers waiting to use the widget so that, to the greatest extent possible, those waiting to use the widget for the first time today always get to use the widget (i.e. everybody gets a turn), but those using it for their second and subsequent times do not wait "too long."** (For the time being, forget about more than one person using the widget at the same time. That actually adds an important twist, but it can wait.)

_____

* This also means that today's activity has no bearing on tomorrow, except that if I manage this well then word will spread and I'll get more customers over time.

** "Too long" here means "long enough to make them angry, or make them not want to come back tomorrow." Since I think it's impossible to prevent ever-lengthening wait times as more and more new customers arrive, accomplishing this goal probably means that on average nobody waits longer than anybody else even as wait times increase. Note, however, that in the real world the number of customers present always levels off about half way through the day, i.e. at that point almost no more new customers arrive, which means wait times will also level off (though I don't think that has any effect on what the best procedure is).

Share this post


Link to post
Share on other sites
There is one widget. People can only use it one at a time. In the course of a day customers can request to use the widget one or more times (most want more than one). Not everyone arrives at the same time. When closing time comes, the customer using the widget gets to finish, then everybody must leave, whether or not they've had a chance to use the widget. Each day, all customers are treated as if they've never used the widget before (i.e. initially they're all "new" customers*). The goal is to manage the queue of customers waiting to use the widget so that, to the greatest extent possible, those waiting to use the widget for the first time today always get to use the widget (i.e. everybody gets a turn), but those using it for their second and subsequent times do not wait "too long."**

Then my analysis still holds. Make appointments for the use of the widget and then its use is optimized and nobody has to wait.

Share this post


Link to post
Share on other sites

Piz, your example sounds more like a government run medical facility than a business problem in the real world.

Share this post


Link to post
Share on other sites

Piz, is there a time limit to how long each customer can use the widget? Do the newer customers spend more time using the widget than the repeat customers? I have more questions but I will await your answers on these.

Share this post


Link to post
Share on other sites
Piz, your example sounds more like a government run medical facility than a business problem in the real world.

LOL

OK, I guess I'll break down and reveal what it really is. As I mentioned some months ago, I got a job as a karaoke DJ. My problem is scheduling singers. Only one song (widget) can happen at a time. Our company motto is "Everybody Sings" (which, BTW, MySpace Karaoke stole from us, if unknowingly :rolleyes:), so I want to make sure everybody gets a turn; hence bumping new singers toward the front of the queue. But I don't want the people who've already had a turn to get upset over waiting too long for their next song. The events are self-contained - from the perspective of scheduling singers, each new gig begins as if there's never been a previous one, so everybody starts "new." Sometimes I get two or more singers at once ("Bohemian Rhapsody" often draws six or seven at a time B)), so there's a problem with deciding if that counts as a turn for just one of them or all.

Some people (like me) submit all their songs at once, others turn them in one at a time. Some want to sing right away every time, some want to jump in and "help" everybody who comes up, some want to sing along with the filler music between singers, and, being in bars, the drunker they are the more obnoxious they can become. So I have to have a definite set of rules that I stick to like glue, so everyone knows exactly what's what, and I can fall back on the rules when dealing with the obnoxious ones. But the primary issue is balancing new vs. old singers.

There are a lot of web sites that describe how to deal with the singer "rotation," but I've set up a number of test programs using different techniques and none have proven satisfactory. So I'm trying to develop something optimal. It's possible that it's impossible to improve on what's out there, but I'm a stubborn S.O.B. when it comes to things like that - I think I can do better, but it's been proving to be a nasty problem.

Share this post


Link to post
Share on other sites