I’m more of a practical programmer than a computer scientist, so I need your help to find a solution (or at least point me into the right direction) to an extremely practical problem related to cooking food in the oven.
I have N ovens and I have multiple various ingredients to cook in them. Each ingredient has certain preparation (e.g. peel the potato, cut the meat, etc.) time and oven cooking time. At time 0 we start preparing ingredients and putting them into the oven to cook. I need an algorithm to find the most optimal arrangement for the queues of these N ovens, so that it takes minimum time to finish cooking all of the ingredients.
Additional note: each ingredient is cooked at specific temperature, so no 2 ingredients can be cooked simultaneously.
2 ovens: O1, O2
A (PT 200, CT 400)
B (PT 180, CT 380)
C (PT 80, CT 240)
D (PT 60, CT 180)
E (PT 40, CT 120)
F (PT 20, CT 60)
G (PT 0, CT 20)
Where: PT – preparation time, minutes; CT – cooking time, minutes.
I solved it simply visually and found that optimal solution looks like this:
Time: action 0: put G in O1 20: take G from O1, put F in O1 40: put E in O2 80: take F from O1, put C in O1 160: put take E from O2, put D in O2 320: take C from O1, put A in O1 340: take D from O2, put B in O2 720, take A from O1, take B from O2 -- finished in 720 min!
Visually it looks like this:
In a search for an answer I found that problem cannot be solved by simply sorting ingredients in some order, as changing the timing on one of the ingredients can dramatically change the cooking order: sometimes ingredients need to wait for certain time, even though they are prepared and ready to be cooked — the priority queue can change completely!
Whoever sees any similarities with certain mathematical or CS problems (Knapsack? Packing?), please point me in the right direction. Or, preferably, point me to the solution, which surely must exist for such an obvious problem.