The lazy cook problem, or scheduling two parallel machines to optimize vehicle utilization

The lazy cook problem, or scheduling two parallel machines to optimize vehicle utilization

0.00 Avg rating0 Votes
Article ID: iaor2005512
Country: United States
Volume: 15
Issue: 4
Start Page Number: 333
End Page Number: 354
Publication Date: Oct 2003
Journal: International Journal of Flexible Manufacturing Systems
Authors: ,
Abstract:

A cook has to prepare n cakes using an oven with two racks. According to the recipe, the i-th cake has to be baked for exactly ai minutes. Cakes to be cooked are taken from a table and carried to the oven, and once cooked are carried back to the table by means of a trolley that can carry two cakes at a time. What is the minimum number q* of round trips required of the cook? This problem has application to the operation scheduling of transportation systems and to material cutting. A different problem arises according to whether the cook accepts or not to stay near the oven for a while with the trolley. If the trolley cannot be idle at the oven, an optimum schedule with no oven idle-time always exists: consequently, the trolley schedule is trivial, and the problem is transformed into a set packing. For this case, we propose and test a heuristic method which generates all of the promising columns of the set packing, and solves the resulting problem by branch-and-bound. Instead, if the trolley can be idle at the oven for a limited amount of time, a problem arises to find an optimal schedule of the trolley: in this case we show how to use a scaling technique in order to obtain a very good feasible solution by the method above.

Reviews

Required fields are marked *. Your email address will not be published.