A simulated annealing algorithm for the allocation of production resources in the food catering industry Open Access

Students at school, employees at work, and patients in hospitals demand ready-to-eat meals. Food service companies are indeed responsible for supplying meals to schools, hospitals and private companies which are not capable of producing and providing food on their own (Mahalik and Nambiar, 2010). This industry counts about 60.000 companies employing one million people in Europe (Sjögren et al., 2015). This sector has continuously grown in the last decade, up to a turnover of €24 billion in Europe, because a third of the European companies signed a catering contract for the supply of food services (e.g. canteens or cafeteria services) (Europe Food Service, 2017).

To fulfil cultural, diet and nutritional purposes and tastes the consumers pretend to choose among an extensive portfolio of courses every day (Benvenuti et al., 2016; Khan et al., 2013). As a consequence, the broad production mix is the primary challenge a food service company has to face. The second is to comply with strict rules and controls of the state of conservation (i.e. Hazard Analysis and Critical Control Points HACCP), safety and quality of meals before consumption and along with production, storage, packaging and delivery processes (European Parliament, 2004). To provide cost-effective, safe and tasty meals, these two issues have to be carefully managed through advanced decision-support systems and infrastructure/operations design approaches and planning techniques (Adler-Nissen et al., 2013; Tufano et al., 2019).

In food safety, practitioners of the food industry typically adopt the rule of thumb of avoiding the ‘temperature danger zones’, i.e. a food product is safely conserved below and above 4 °C and 65 °C, respectively (Evans et al., 1996; Marzano and Balzaretti, 2011). The range [4 °C–65 °C] is a thermal region that allows pathogens and bacteria to proliferate (Rahman, 2002). This rule is reasonably easy to respect in a cook-serve service, i.e. when the point of production and consumption are close to each other (e.g. from the kitchen to tables in a canteen). The case of deferred service is more complicated, since, a single centralised kitchen (CEKI) organised as a job-shop production system, cooks, stores, packs and ships meals to many points of consumption located within a medium-short distance range (e.g. within 100 km) (Ciappellano, 2009). Such service guarantees to exploit economies of scale in the production (e.g. aggregating orders into production batches), but causes critical logistics and safety issues.

In a deferred service, three main alternative production processes result in the following food thermal profiles:

1. Cook-warm: the product is cooked in the facility and maintained warm (above 65 °C) along the delivery process.

2. Cook-and-chill: the product is cooked, blasted (below 4 °C), and delivered to the customer within refrigerated shipments. The customer re-warms it before serving.

3. Cook-chill-and-warm: a cook-and-chill product is re-warmed in the CEKI and delivered according to a cook-warm profile.

The cook-warm profile is the most critical as it needs some hot-holding machines (i.e. devoted to storing products above 65 °C) both in the CEKI and at the canteens. This leads to higher energy costs and consumptions, and higher risk for quality and safety decay (Tufano et al., 2018a, b). Despite these factors, the cook-warm profile remains extremely popular among customers (in particular schools) since the quality perceived by the consumers does not necessarily couple with safety concerns (Fallis, 2004; Galić et al., 2011; Sun et al., 2010).

The number of processing resources affects both the lead time and the quality of finished products. Figure 1 showcases this impact by illustrating product temperature samples measured along with the processing tasks performed within a CEKI according to two scenarios. The real situation is tracked by considering per each process the number of resources established and available at the CEKI. Conversely, the ideal scenario simulates the effect of an infinite number of resources (i.e. upper bound) per each stage. Figure 1 clearly shows that such upper bound avoids that the average temperature of a product goes below 65 °C during production and delivery processes, while in the real scenario, mainly due to queues at the temporary storage, the product experiences temperature within the danger range. When the number of resources is limited, indeed, a batch could wait outside the hot-holding machine (e.g. in case these are occupied by other batches or products). Furthermore, the concentration of most of the production batches before lunchtime exacerbates this issue as most of the workload is concentrated in a few hours (Tufano et al., 2018a, b).

This paper aims at illustrating a decision-support method for the allocation of the proper number of processing resources in a food service facility, thereby answering the following unmet research questions:

In order to address these RQs, this paper proposes a bi-objective optimisation problem to explore how the number of processing resources affects production costs (1) and the safety of meals (2). Moreover, it introduces a metaheuristic simulated annealing (SA) algorithm to solve this problem. The proposed methodology is applied to a real-world application and provides general guidelines for production managers and food catering practitioners a to deal with the design of a new food catering production facility.

The remainder of the manuscript is organized as follows. Section 2 presents a literature review of the methodologies for food production systems design and planning. Section 3 introduces the bi-objective formulation and illustrates the SA algorithm. Section 4 illustrates the case study and the numerical application of the algorithm. Section 5 discusses the results of the case study and the practical implications of the methodology, while Section 6 concludes the paper with suggestions for future developments.

This paper focuses both on infrastructural costs (i.e. associated with the installation of processing resources) and food safety management in a food service production system. For this reason, the proposed literature review collects new methodologies addressing one or both these goals.

Dealing with the allocation of processing resources several contributions are intended to the minimisation of the workload peaks. The minimisation of peaks has a long tradition in job scheduling and resource allocation problems, both in production systems and in power grids management (Ranjan et al., 2014; Yaw and Mumey, 2017). As for power grids which need for the balance of power load among the users, the workload in production systems needs to be balanced between several processing resources (e.g. manufacturing plants and machines, assembly systems, storage and material handling equipment) (Germs and Riezebos, 2010). Conversely, a production workload, generated by a sequence of production batches, behaves according to two possibilities (Sivasankaran and Shahabudeen, 2014):

1. In the presence of a scarce number of processing resources (i.e. a number of resources lower than the workload peak), a batch may wait in a queue (see Figure 1)

2. When the number of processing resources is higher than the workload peak, these will remain under-utilised for most of the time.

These are the main reasons why job/task-resource allocation and job/task scheduling approaches are widely used to balance production flows and peaks among the resources (Pinedo, 2009). In particular, scholars define the so-called min-max problem, used to minimise the maximum workload peak for the processing resources. This is widely adopted for job/task-resource allocation in the balancing of assembly systems (Jayaswal and Agarwal, 2014; Pereira, 2018).

Since the task-resource optimal allocation problem is generally non-polynomial in time solvable, many heuristics and meta-heuristics are developed to address real-world instances (Baykasoǧlu, 2006; Jiao et al., 2006; Roshani et al., 2012; Seyed-Alagheband et al., 2011). The min-max formulation is used in the job/task scheduling problem as well, to minimise the maximum tardiness of tasks (Federgruen and Mosheiov, 1996). To solve this problem in a reasonable time, metaheuristic methods have been developed so far (Chaudhry and Khan, 2016).

Moreover, the exponential number of discrete time periods (i = 1,…,m∈ T) (e.g. one i per minute or even second), necessary to control the job/task-resource allocation and the job/task scheduling (which both vary continuously over the daily production time), motivates the adoption of metaheuristics techniques. Among these, SA is mostly used for industrial applications (Fattahi et al., 2009; Khalife et al., 2010; Loukil et al., 2007; Yazdani et al., 2009).

Despite its importance, the management and control of food safety throughout production systems are less treated in the traditional resource allocation and task scheduling literature. Other perspectives and disciplines typically address these issues. Food technologists are focused on determining the thermal treatments and cooking technologies able to prevent rapid shelf-life and quality decay (Devlieghere et al., 2004). Management scientists aim at addressing food safety and waste reduction through integrated planning of logistics operations along the supply chain (Jedermann et al., 2014; De Steur et al., 2016).

Only a few studies consider the impact of production task scheduling on the quality of food products. Decision support systems (DSS) aid production scheduling and reduce food losses (Akkerman and van Donk, 2008), provide support in scheduling deliveries and distribution operations (Accorsi et al., 2018a, b) and organising warehousing activities (Accorsi et al., 2018a, b; Fikar, 2018).

Even in the food service industry, some studies provide support to scheduling by taking into consideration the shelf life and safety decay. Early, (Guley and Stinson, 1984) proposes a scheduling model to minimise the time between production and delivery. (Pires et al., 2015) provides a production planning model for perishable products using mixed integer and linear programming (MILP), while (Akkerman and Van Donk, 2007) focus on the role on intermediate and temporary storage/buffers between processing resources/stations. Although these models involve the perishability of food, none of them investigates how the number of processing resources and their allocation to tasks and the tasks scheduling affects food safety.

Combining the minimization of investment costs of the production system (i.e. number of processing resources) with the maximization of food safety, this study proposes a bi-objective formulation of resource allocation and task scheduling problem and illustrates a SA algorithm to solve it in real- world applications. Two metrics are identified to quantify the two objective functions: the balancing of workload peaks (1) and the minimisation of food losses (2). As the preference among these goals is unknown, an a-posteriori solving strategy is chosen (Chiandussi et al., 2012).

Given the computational complexity of this decisional problem, a metaheuristics SA algorithm is proposed to generate the solutions and the Pareto Frontier as well (see for reference of a similar approach (Fang et al., 2011)). To the best of authors' knowledge, this study provides a novel contribution to the literature on food service industry.

This section describes the original proposed method illustrating the model notation and formulation (1), the descriptive mathematical model and the objective functions (2), the metaheuristics SA algorithm (3).

We introduce the usual processing activities of a food catering facility (see Figure 1). In the food industry, the production cycle of a product is set from its recipe (Accorsi et al., 2019; Akkerman and van Donk, 2009), which is a list of processing operations, named tasks, characterised by the following main parameters:

1. the type of task (e.g. boiling, braising, frying);

2. the associated product;

3. the quantity for a production batch;

4. the processing time;

5. the processing temperature.

During the operations, each task is allocated to a resource for a certain amount of time contributing to the determination of the total processing time of the batch of a given product. Since different recipes occupy different resources of the system at different time instances, a synchronisation of the batches is needed. In particular, batches belonging to the same delivery tour, are to be ready to shipping together According to an ideal scenario, the end of processing of different batches belonging to the same delivery tour should coincide. Consequently, two main categories of tasks exist:

1. Processing tasks, which are the processes transforming products (e.g. cooking)

2. Buffering tasks, which consist of temporary storage performed within hot-holding machines aiming at balancing and synchronising operations for the reasons above.

Figure 2 exemplifies how the production tasks are modelled according to these assumptions and which inputs and outputs are expected from the production planning.

This model addresses the task allocation problem, by identifying which physical resource is adequate the most to perform a specific class of tasks.This decision problem is described as follows.

For each task, some parameters can be tracked and collected as exemplified in Figure 2. In particular, q_rj represents the percentage of utilisation of the capacity of task j on resource r and is defined as the ratio between the volume of the processed batch and capacity of r. Whether the processing time c_j is known for the processing tasks, the duration of buffering tasks is influenced by the concurrent production of many batches and by the job scheduling, as well as by priorities, queues and delays, so that it is hard to predict ex-ante.

Thus, in order to determine the proper number of resources for each type, two critical goals (i.e. objective functions) have to be simultaneously addressed:

1. Minimising the utilisation of resources at each time period (⁠$ϑ$ or O.F. 1). This determines the number of resources and the investment cost of the production system;

2. Maximising the conservation temperature of products, at least above 65 °C (i.e. the food safety metric) (⁠$φ$ or O.F. 2).

O.F. 1 evaluates the maximum number of resources required by a given workload (i.e. a list of tasks) in each time instant. O.F. 2 evaluates the number of products entering the temperature danger zone (i.e. 4–6 °C) at any production task.

These goals are described by Eqns (1) and (2). The feasible region (i.e. all feasible task-allocation solutions) is defined by the set of Constraints (3) to (15).

Constraints (3) ensure all tasks are processed. Constraints (4) control that production of lot p is completed within the due date d_p. Constraints (5) control that each task duration is at least equal to its processing time (longer duration is, then, allowed for buffering tasks). Constraints (6) state that each task must start exactly when the previous is finished. Constraints (7) links the decision variables of assignment (i.e.) and time (i.e. t_j). Constraints (8) assign the value of the temperature at the end of each processing task. Please note that, in this formulation, temperature decay law is approximated to a linear function to preserve the linearity of the model. Such limitation does not affect the SA algorithm illustrated in the following. Constraint (9) and (10) verify whether or not a lot enters into the temperature danger zone during one of its tasks. Constraints (11), (12), (13), (14), (15) control the value (i.e. binary or continuous) of the decision variables.

The aforementioned descriptive model presents many criticalities. First of all the complexity in the number of variables defined for every single task and a min-max objective function lead to uncertainty in the computational time to get an optimal solution (e.g. using branch-and-bound algorithms applied to the model presented in Section 3.2.). Besides, constraints (8) approximate the temperature drop to a linear function which is, in practice, too optimistic since this relation is better explained by an exponential curve (Tufano et al., 2018a, b). For these reasons, a metaheuristic SA algorithm is developed and proposed to allocate tasks to resources accounting for O.F. 1 and 2 simultaneously. Metaheuristics techniques start from an initial feasible solution and apply perturbations, called ‘moves’, on the value of the variables. After each move, the incumbent solution value (i.e. the value of the objective function at the current iteration) is assessed and accepted under some ‘acceptance rules’ whose thresholds vary with the type of the algorithm chosen.

SA metaheuristic is inspired to the physical process of annealing where a piece of metal, after heat treatment, acquires a more stable molecular state while its temperature decreases. The same approach is used for the value of the objective function (i.e. the solution value) after each move. Given a minimisation problem, at each iteration the associated SA algorithm:

1. will always maintain the new solution if this is lower than the previous (i.e. the ‘incumbent solution’);

2. will maintain the new solution if this is greater than the previous under a certain probability, which decreases iteration by iteration (i.e. dropping the annealing temperature) such that the final solution converges on a local minimum.

In the proposed SA algorithm, each move modifies the duration of a generic hot-holding task (i.e. buffering task). Given a production batch p and the related sequence of tasks, a move shifts the execution of these tasks forward or backwards and the impact on both objective functions $(ϑandφ)$ is quantified accordingly.

Given the sub-optimal nature of the proposed metaheuristic, the accurate tuning of the algorithm parameters is crucial to prevent from bad solutions. Table 2 reports all the tuning parameters used to run the algorithm.

The algorithm performs moves until the time limit TL is reached, starting from an initial feasible solution s^* which is progressively perturbated. The initial annealing temperature T₀, and the cooling rate factor cr control the probability to select better or worse solution values (i.e. the solution acceptance rate). The value of the initial annealing temperature T₀ is defined such that, at the first iteration, a solution t% worse (i.e. greater) than the initial one s^* is accepted with a probability equal to 50%. The value of t is set to 5% to avoid the acceptance of solution values farther from the incumbent one. By incorporating the initial solution value s^* in the definition of T₀, the acceptance rule is coherent with the size of the instance of the decision problem (Reinhardt et al., 2013). The cooling rate factor is set to cr = 0.001 to obtain a slow decay of the acceptance rate. This implies that the probability to accept a worse solution t% slowly decays from 50% (at the first iteration) to 0 (at TL).

Besides, a tailored threshold th is introduced in the choice of the moves (i.e. the production task j to perturb). The value of th is randomly generated at each iteration of the algorithm. The probability that a task j is selected for perturbation is proportional to p_j i.e., the duration c_j of task j itself over the total processing time of the associated lot. This results in a low probability of choosing the shortest tasks, whose impact on the objective functions would be limited. The procedure to evaluate the value of p_j is presented in Figure 3 together with the definition of the O.F. 1.

The problem parameters (Table 1) and the tuning parameters (Table 2) feed the SA algorithm presented in Figure 4. The algorithm iteratively selects a buffering task j whose p_j exceeds the threshold th. It randomly perturbs its duration from 50% less to 50% more than the as-is value. It consequently reschedules all j∈F_p i.e., the tasks of production lot p. The algorithm checks if the produced solution is feasible i.e., production of lot p ends before its deadline d_p. When this condition is true, the algorithm analyses the value of the solution and, according to the current annealing temperature, the incumbent solution value is accepted or rejected.

The SA algorithm is able to run minimising O.F. 1 rather than O.F. 2. In both cases, the value of the other objective function is evaluated to investigate how a reduction in one objective function affects the value of the other. The following section shows an application of the proposed SA algorithm to a real-world case study and explores the trade-off between the two objective functions.

This section introduces a case study, to validate the methodology by presenting its implementation in a real context involving the redesigning of the plant layout of the production system. The decision problem regarded the determination of the adequate number of processing and buffering stations/machines able to satisfy safety and infrastructural cost reduction purposes. Thus, the proposed SA algorithm was applied to decide on the number of production resources to address the economic sustainability of the plant re- layout and the reduction of the risk of dangerous food conservation throughout the production system.

As the meals demand from schools typically drives the catering industry, the menu of a generic weekly production (from Monday to Friday) represented the validation dataset for the proposed methodology. The dataset involved five working days with two shifts per day as a collection of orders. For each order the batch quantity (1), the working cycle (i.e. the recipe) (2), and the due time (3) were available (as in the conceptual model of Figure 2).

Also, a monitoring campaign has beenwas set to estimate how production bottlenecks contribute to the decay of product and WIPs temperature, thereby affecting the safety of processed meals (Tufano et al., 2018a, b). Table 3 summarises the number of entities involved in the input dataset.

During the day, the production workload is not uniformly distributed. Figure 5 reveals the complexity of each instance. The x- and y-axes define the working time (in min) and the number of processing tasks to process each batch. The size and the colour of the dots both indicate the processing quantities of each batch. As one can see, large batches might require a significant working time or a considerable number of tasks (i.e. Monday and Wednesday), producing congestions and bottlenecks. Due to the market demand, the recipe portfolio wais ample and count more than 150 different products each day, where the first 20% covers about 70% of the total meals, resulting in high complexity of the production balancing and scheduling with many bottlenecks and queues to manage.

The proposed metaheuristic starts with an initial feasible solution, obtained through the at-the-lastest scheduling of the production batches on the delivery time. In such a case, the number of processing resources is assumed as infinite so that queues are avoided. Then, the algorithm run to minimise the number of processing resources while reducing the queues that mostly affect the conservation temperature of WIPs.

The SA algorithm run two times per each daily instance, minimising O.F. 1 and O.F. 2 respectively. For each run, the value of both the objective functions is quantified. The run time is two hours on 3.5 GHz Intel Core i7 work station equipped with 32 Gb RAM. Figure 6 shows how the values of both the functions evolve iteration by iteration. Although the workload wais similar between instances, differences exist in the recipes processed and the gradient of the temperature drop of each product (e.g. sliced roasted chicken vs pasta with tomato sauce vs broth).

Figure 7 combines the values of the two objective functions, identifies the non-dominated solutions, and highlights the Pareto frontier for each working day. The initial solution (i.e. the as-last-as-possible scheduling), in blue in Figure 7, is always improved by the algorithm for both objective functions with any of the solutions belonging to Pareto frontier.

Every Pareto frontier identifies two anchor points $xθ,xϕ$ (i.e. the minimum solution values for $θandϕ$⁠). Anchor points coincide in three instances, identifying a local optimum for both $θandϕ$⁠. The distance $ψ=‖xθ−xϕ‖$ measures the tradeoff between the two objective functions. The larger $ψ$⁠, the more difficult to choose between investment cost and quality cost.

This result moved the decision-makers to focus only on critical tasks and critical resources from a food safety perspective (i.e. all the tasks following the cooking phase) since the determination of the number of resources responsible for critical tasks can prevent products from entering the danger zone.

Table 4 measures $ψr$⁠, i.e. the maximum difference (among the five instances) between the obtained minimum number of a specific resource r minimizing $θ$ and $ϕ$⁠. The columns AS-IS describes the initial feasible solution value. The analysis suggests that increasing the number of hot-holding machines can significantly reduce the temperature drops of the processed lots, even though they do not directly contribute to improving the production throughput. It is, then possible, to significantly increase food quality with a minor investment in hot-holding machines.

The decision-makers, then, decided to increase the number of hot-holding machines from one to three machines to reduce the risk connected to food safety (see Figure 8).

The following section discusses how these implications can be generalised for the design of a food catering production plant.

This section discusses how the results obtained from the proposed algorithm can be generalised and used as guidelines in the design of the production system of a food service facility. A preliminary consideration involves the assumptions undertaken to assess which tasks are critical according to the workload or the safety levers. O.F. 1 evaluates the sum of the peak demand for all the resources of the CEKI As shown in Figure 7 this value is extremely high (even higher than a thousand of resources). This value describes a sum of the worst case scenarios (i.e. the workload peak) for each resource preventing from queues. This is obviously a too high number of resources unfeasible in practice.

The methodology needs to consider all the tasks j ∈ F_p scheduled for each lot p ∈ p, and all the resources r ∈ R. Nevertheless, a small subset of tasks affecting food safety (e.g. cooking, hot-holding, packing) identifies the subset R^x of critical resources. For this reason, the interpretation of the results focuses on a subset of critical tasks processed by R^x (see Table 4).

The allocation of critical tasks to resources is crucial. The difference between the number of resources obtained minimising $ϕ,andθ$ (i.e. the quality gap in Table 4) answers RQ1 by identifying the sensitivity between quality and number of resources. Decision-makers should focus their attention on this subset of critical resources.

The cost of the quality has to be considered to address the tradeoff between the cost of food safety risk and the investment cost for a critical resource (RQ2). A packing task is chosen as an example (see Figure 9), but the procedure is generalisable to any task and resource. The values on the plot are the average from the five working days of the amount of degree lost in that task. They are represented as a cumulative distribution function (each processed batch is an observation) for each objective function. For example, the probability of losing more than 30 °C from the product temperature after cooking (i.e. 95–100 °C) ranges from about 8% in the scenario minimising O.F. 1 to about 2% in the scenario based on O.F. 2. As a consequence, a new packing line could be added to the production system whether the economic benefit in term of food safety improvement (and associated food waste reduction) would cover the initial investment. Given the cost of a new packing line (i.e. 200.000 €) it is convenient to add a resource when the cost of 6% (i.e. 8–2 %) of the finished products is higher than the cost of a new resource. In the case of the packing task, the high cost of an additional package line prevents economic convenience.

Feasibility studies like this, are valid for any processing resource. When applied to the hot-holding machines (see Table 4), also this procedure suggests enhancing the number of stations in the light of a low initial investment compared to the high benefit on the food product conservation throughout the production system.

This paper aims at investigating the trade-off between the infrastructural investment in production resources and the increase of safety of food products throughout the production system in the food service industry. The production issues in the food service industry are illustrated with particular emphasis on the critical tasks performed within a CEKI facility.

The methodology proposes a model to describe the scheduling of production processes of a food catering production facility and an original simulated annealing algorithm to solve it. The paper analyses the solution to explore the tradeoff between resources investment cost and food safety. Two objective functions are used to identify the mentioned trade-off, by evaluating the workload peak (i.e. the ideal number of resources required to avoid queues) and the level of food safety (i.e. the number of processed lots whose temperature falls within the temperature danger zone).

This methodology has been applied to aid the re-design of an existing food service facility, with particular focus on the cooking and packing tasks. It comes out that additional hot-holding machines are an appropriate investment to prevent quality decay, from food losses and missing revenues in the long term. Besides, it is demonstrated that a task allocation policy which minimises the workload peak has often positive impacts on food quality.

This research contribution links the design aspects (i.e. the determination of the number of the resources) with control issues (i.e. the quality of the finished products) of the food catering industry. Future researches may elaborate on this link by investigating other design and control issues in the food industry.

The authors would like to heartily thank the company Camst – La Ristorazione Italiana Soc. Coop. a r.l. involved in this study.Particularly, in the name of Dr. Andrea Lenzi and Eng. Federica Garbellini, for their valuable inputs, their priceless support and their willingness to cooperate in this research project