The cafeteria line problem

[LB]

I thought of this problem randomly and have done no research or any thinking on it, I was just wondering if it sounded similar to any existing problem.

The dining hall at my college is an all you can eat buffet. Usually you can just walk up to anywhere with a plate and put food on it, then walk away. But, in times of high traffic, people have a natural tendency to both form lines and stand in existing lines, even if they don't know what the line is for. In this particular case, the line passes along the majority of the buffet area.

Each student knows in advance what they want to eat - they have 1 or more preferred foods, as well as 0 or more substitutions for each. Batched of food are produced on timed intervals, and there can be periods where a particular food is not available at a particular time. We'll say the unit of time is the line of students moving forward to the next food type.

The problem is sorting the students so that, when the line moves along the buffets, as many students as possible get all their preferred foods. Once students have all the foods they want they leave the line. If a student can't get their first choice for one of their foods they'll know to get their next choice for that food while in line - you must avoid the case where the student gets to their first preferred food but that food has run out and they already passed their second preferred food. It's implicitly ok, though, if that happens and their second preferred food is later in the line.

I probably have not mapped out enough details, but this problem is already so complex to me that I can't even think about how to begin solving it. All i can do is think of these basic ways to store the problem state (maybe this will clear up ambiguities):

enum struct Food
{
    //...
};

struct Buffet
{
    Food const food_type;
    unsigned remaining_food;
    unsigned time_until_refill;
    unsigned const refill_interval;
    unsigned const refill_amount;
};

using Buffets = std::vector<Buffet>;

struct Student
{
    using FoodPreferences = std::vector<Food>;
    using MissingFoods = std::set<FoodPreferences>;
    MissingFoods missing_foods;
};

using Students = std::vector<Student>;

void cafe_sort(Students &line, Buffets const &buffets)
{
    //magic
}

Again, I thought of all this completely randomly while sitting in the dining hall one day. It's probably too complex with not enough information and it might even have unsolvable scenarios with it's current way of time progression (I don't even know what should happen in the event of a holdup/line split, or if that can be avoided). So, really I'm just interested in if there are similar problems and/or how to fix/refine this problem definition.

[helios]

How about this:

First sort the list of food preferences in order of decreasing preference, and the list of food trays in order of appearance on the queue.
Sort the students in increasing order according to the following distance function: for every pair in the list of preferences, if the food items are in reversed order on the list of preferences as they are on the list of trays, add 1 to the distance.

The students whose distance(preferences) == 0 will always get some food as long as there's any food in any tray. As the distance increases, the chance that a student will need to restart the line increase. Hopefully the line will shorten fast enough to amortize the cost of requeuing. This will depend on the frequency distribution of distance().
I conjecture that there's no better scheduling algorithm, at least not with the minimal set of constraints given.

[LB]

Does that avoid several students in a row exhausting a buffet to the point where it cannot be refilled for the next students in line?

[helios]

No. There's no way to avoid that, since no constraints are given to the minimum amount of food in a buffet or the maximum number of students with a given preference. The odds can be evened out by shuffling the students whose distances are equal.

EDIT:

I conjecture that there's no better scheduling algorithm, at least not with the minimal set of constraints given.

Addendum: except for "try all permutations and find the one that finishes in the least number of steps".

[MiiNiPaa]

As I understand, student have several "food groups" each of which should be fulfilled for student to leave the queue. Each "food group" has one ore more meals. If student sees any food from unfullfilled group, he takes it and group that meal belongs are considered fulfilled. Am I right?

First what comes to mind is to reorder food in the buffet: place food that is least preferred to the beginning of the queue: we want it to have at least some demand; and place most common food in the back as a sort of "catch-all" so students which needs are still unfulfilled would have greater chance to meet them there (and to avoid exhaustion too quickly)

[LB]

@helios: the idea is that you group the students at various points in the line so the food they want is refilled before they get to it. There is a progression of time.

@MiiNiPaa: The buffet arrangement is immutable. Also, you have the right idea with the food groups, except that some options in each food group are more preferable than others. The goal is to have as many students as possible get their preferred foods.


I'm getting the impression I did a really poor job of explaining. Not to mention a poor job of mapping out the problem in the first place. I should mention that there is another element in play - you can 'waste time' to have a student hold up the line while they wait for a food, and the idea is to sort the students so that the total time of the simulation is as short as possible. This results in wanting to sort the 'picky' students toward the end so that they don't hold up very many students behind them.

[MiiNiPaa]

What happens if a "second-rate" food is encountered first? Will he grab it or will try to get his favorite? Can we fine-tune specific student behavior? Can we tell him to skip his favorite food which is too demanded and instead to move to another dish?

My idea is to serve most picky eaters (which have little to no substututions) first, hoping that initial meals would be enough and force them to empty least demanded trays first, letting more demanded trays to fill up and hopefully last till the end.

If you want to find shortest simulation time, you should not care about preferences.

[ResidentBiscuit]

Bump.

Interesting problem, I've had a few ideas I need to flesh out when I have time. I look forward to seeing what solutions people come up with.

[helios]

So, to summarize,

Assumption: A particular food appears a single time in a single food group.

When in front of a non-empty buffet, the student grabs a plate if that food has the highest preference index in the intersection of the preference list and the list of buffets with position posterior or equal to the current, and if that food group hasn't already been filled.

When in front of an empty buffet, the student waits until refill, holding up the line, if the size of the previously mentioned intersection is equal to 1 and that food group hasn't already been filled.

[LB]

I think I have made the problem far too complex and open-ended to explain or solve properly. I will do some thinking when I have time and reduce the complexity of the problem and try my hand at a solution, or at least make a program that gives the results of the simulation.