The Lazy Cook Problem, or Scheduling Two Parallel Machines to Optimize Vehicle Utilization

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 awhile 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.