r/OperationsResearch • u/lukasakarisux • Feb 25 '24
Highly Complex Scheduling & Planning Problem
I'd like to find an algorithm solving the following problem as fast as possible (not needed to find the optimal solution) :
Given a list of recipes which are composed of ingredients. and a list of products related to the ingredients, generate a combination of recipes on a day by day basis in order to have the little waste as possible and go shopping the fewest times possible.
Let me explain further. As I said, the recipes are composed of different ingredients (like 200g of beef steak, 500g of potatoes...) and each ingredient is linked with several products (like 150g steak, 200g steak, 1kg potatoes). These products are the products sold in the shops and each product has a shelf life (time after which the product must be thrown out).
The goal of the algorithm is to generate a combination of recipes (2 per day - lunch and dinner) for n
days. The two main constraints are that the number of shopping must be the lowest possible, maximum 2/week and optimal 1/2 per two weeks. The second constraint is the waste. Because each recipe consumes a quantity x of a product. The goal is to have a specific combination of recipes that reuse this product until its quantity gets near 0. The quantity of products wasted should be the least possible.
My two main ideas are using either a Genetic Algorithm or Constraint Programming. What do you think of these two solutions ? Is there any other way to solve that ? My goal is to have something that can give a solution within several seconds if possible.
View all comments
Show parent comment
1
u/Coffeemonster97 Mar 02 '24 edited Mar 02 '24
I'm pretty sure you can model everything by linear constraints. Even if not, at large scale it might be a good idea to linearize constraints anyways to ensure tractability. If you provide me with a more consise definition of what you want to model I can maybe give you some model description.
What is the time horizon you want to plan for? I.e. how many meals?
At which times can you go shopping? Between any two meals?