Track: Operations Research

Abstract

This study formulates a cooking scheduling optimization problem as a combinatorial optimization problem. This study seeks schedules for mass cooking of more than 100 servings. Steam convection ovens which can cook multiple dishes in large quantities are used in high-volume cooking facilities. Previous studies have proposed a formulation that applies a flexible job shop scheduling problem. They have not been able to determine the processing machinery for each process. In addition, there is no constraint to prevent contamination. Therefore, realistic schedules were not obtained.

In many developed countries, sanitation control based on HACCP is mandatory. A cooking facility consists of two main areas. They are contaminated areas and uncontaminated areas. The former is an area where meat and fish are processed prior to heating. The latter is an area where heat treatment and food cutting are performed. Bacteria can spread throughout cooking facilities when they adhere to the floor and cooks' shoes. Therefore, cooks should take an air shower and change shoes when moving between the two areas.

 Three constraints must be considered when cooking in large quantities with cooks and machines. First, all cooks must move in only one direction between contaminated work areas and non-contaminated work areas. Cross contamination can be prevented by moving these areas in only one direction. Second, works on steam convection ovens must be started after preheating is complete. It takes more time to lower the temperature in steam convection ovens than to raise it. Preheating time can be reduced by working in a sequence of gradually increasing heating temperatures. Cook's workload can be reduced by working as many jobs as possible on a steam convection oven at the same time. Unit time is a discrete value of one minute. Third, when several cooks work on the same task, they must start at the same time.

We seek optimal cooking schedules given the number of cooks and machines, the type of machine, and recipes for multiple dishes. A directed acyclic graph called a DAG is created by using arcs to connect processes that have priority relationships within a recipe. Within a DAG, a job is defined as a set of the nodes with a fixed antecedent relationship. There are pairs of precedence relationships between the processes of two different jobs. This information is used to create a constraint equation that adhere to the preceding relationship. The purpose of the formulation is to minimize the start time difference between processes working on steam convection in addition to the makespan. There are two things to decide in this problem. The first is the order in which jobs are worked on each machine. The second is the assignment of processing machines to each process.

Numerical experiments were conducted on several example problems. As a result, we succeeded in obtaining exact solutions for small-scale problems. In the future, we will receive evaluations from workers at cooking facilities. In addition, we will make improvements based on them.