key: cord-0166861-golpxd9z
authors: Araujo, K. A. G.; Birgin, E. G.; Kawamura, M. S.; Ronconi, D. P.
title: Relax-and-fix heuristics applied to a real-world lot-sizing and scheduling problem in the personal care consumer goods industry
date: 2021-07-22
journal: nan
DOI: nan
sha: 7da9a5cc44c1eca2e686f7f80245551cfc3f5623
doc_id: 166861
cord_uid: golpxd9z

This paper addresses an integrated lot-sizing and scheduling problem in the industry of consumer goods for personal care, a very competitive market in which the good customer service level and the cost management show up in the competition for the clients. In this research, a complex operational environment composed of unrelated parallel machines with limited production capacity and sequence-dependent setup times and costs is studied. There is also a limited finished-goods storage capacity, a characteristic not found in the literature. Backordering is allowed but it is extremely undesirable. The problem is described through a mixed integer linear programming formulation. Since the problem is NP-hard, relax-and-fix heuristics with hybrid partitioning strategies are investigated. Computational experiments with randomly generated and also with real-world instances are presented. The results show the efficacy and efficiency of the proposed approaches. Compared to current solutions used by the company, the best proposed strategies yield results with substantially lower costs, primarily from the reduction in inventory levels and better allocation of production batches on the machines.

According to the Brazilian Toiletry, Perfumery and Cosmetic Association (ABIHPEC), the Brazilian market for personal care, perfumery, and cosmetics showed a growth of 2.2% in 2020 above the −4.5% of the overall industry and −4.1% of the GDP (Gross Domestic Product) (both heavily affected by the COVID-19 pandemic); and a CAGR (Compound Annual Growth Rate) of 1.7% over the last 10 years compared to a CAGR of −2.1% for industry overall and −0.3% for GDP over the same period (ABIHPEC, 2021) . Among the factors that have contributed to this accelerated growth are the growing participation of women in the labor market, the frequent releases of new products, the higher productivity by using cutting-edge technology, and, more recently, the essentiality of the segment's products in the combat of COVID-19 pandemic. This segment is comprised of a large number of small manufacturers and some large companies. In 2020, Brazil held the fourth biggest consumer market of this sector in the world with US$ 23.7 billions. Inside this market, the segment studied in this work is the disposable personal care one, composed of diapers, sanitary pads, toilet paper, towels, and tissues. These products are characterized by (i) frequent consumption by the population, (ii) relatively low cost, and (iii) very similar quality among different brands. Therefore the process of production planning, scheduling and control performs an important role in the companies to guarantee productivity, cost control, and adequate customer service level. In most companies, the main responsibility of this activity is to simultaneously analyze several relevant information such as the seasonality of the demand, the seasonality of the supply of raw materials, perishability of the finished products and the raw material, and the manufacturing capacity to develop a production plan that optimizes the use of productive resources while meets the demand for manufactured products.

Typical production planning decisions as lot sizing and scheduling significantly influence the results of a company by maximizing the fulfillment of sales orders, adjusting correctly the inventory levels, and incurring in proper operating costs. The process of lot sizing consists of determining how much to produce of each product in each period in order to meet a projected demand under the existing conditions and operational capabilities. On the other hand, scheduling means determining when and in which sequence these lots have to be produced in order to maximize the productive resources efficiency and to meet the deadlines. Inefficiencies in these processes can cause overstocking of finished products, unfulfilled sales orders, loss of perishable material, not accomplished due dates, significant reduction in the productive capacity of the production line, stocks of finished products accumulated in advance, higher preparation machine costs, among others.

In this work, a case study of a large company in the market of disposable personal care products is performed. The company has factories in the south and southeast of Brazil and its market is also geographically concentrated in these regions. Its main product categories are diapers, feminine sanitary pads, and toilet paper. These products are manufactured by the company itself; and their demands are predominantly affected by the own company marketing activities and by the competition. Some other manufactured products have a strongly seasonal demand as tissue paper, which are widely used in the winter due to higher incidence of respiratory diseases, and disposable napkins and paper towels, sold mostly on holiday periods like Christmas, Easter, and New Year, among others. The production configuration of the company consists of machines of different models that have been acquired over time, as demand was increasing. These machines have performance profiles distinct from each other with regard to efficiency, speed, and cost. Moreover, by technical constraints, not all products can be manufactured in all machines. Between the production of batches of different products on the same line, machine preparation (setup) is required, which may be simple and fast as changing the consuming packing or complex and slow if it involves change of raw material or reconfiguration of the parameters of the product, among others. Thus, these setups depend on the product to be produced and also on the product which was being produced in line in the previous batch. The products manufactured are shipped to a limited capacity distribution center located close to the factories. Figure 1 schematically represents the process. In the literature, the integrated lot sizing and scheduling problem with dependent setup times and costs on a single machine (or a singe line) is called GLSPST (General Lot Sizing and Scheduling Problem with sequence-dependent Setup Time); while the same problem involving parallel machines is called GLSPPL (General Lot Sizing and Scheduling Problem with Parallel Machines). The GLSP with non-zero minimum lotsizes and without setup times has been proved to be NP-complete by Fleischmann and Meyr (1997) . Consequently, the GLSP and the GLSPPL with sequence setup times are also NP-hard (Meyr, 2000 (Meyr, , 2002 . The focused problem can be seen as the GLSPPL with sequence-dependent setup times and costs, non-identical parallel machines, in addition to specific characteristics of the environment addressed, such as limited warehousing capacity for finished products, machine eligibility constraints, backorder costs, and setup state conservation among adjacent periods. Up to the authors acknowledge, few studies addressed the GLSPPL with all the characteristics of the focused real-word problem.

In this research, a heuristic procedure able to tackle real-world instances of a large company in the market of hygiene products is presented. The proposed solution method is a customized relax-and-fix heuristic that decompose the original mixed integer linear programming (MILP) model of the problem into less complex subproblems that are successively solved. This strategy was selected due to the fact that this heuristic method had been successfully applied to similar problems (see for example Clark and Clark (2000) ; Beraldi et al. (2008) ; Lang and Shen (2011); Soler et al. (2019) ). Furthermore, this MILP-based approach is mentioned by Copil et al. (2017) as the next generation of solution methods for the MILP models of the lot sizing and scheduling problems. Eleven different solving approaches are presented. Nine of them are problemdependent strategies that divide the main problem considering several metrics associated with machines, products, and periods; and two of them are problem-independent strategies. The aim of the study is not only to solve a complex real-world problem but also to assess in which way the form of partitioning the problem into simpler subproblems and the sequence in which subproblems are solved affect the performance of the relax-and-fix heuristic.

The rest of this paper is organized as follows. A literature review is presented in Section 2. In Section 3, a MILP formulation of the problem is given. In Section 4 the considered relax-and-fix heuristics are described. In Section 5 numerical experiments with randomly generated instances and real-world instances of the company are conducted. The proposed heuristic methods are compared against a commercial solver applied to the MILP model presented in Section 3; while, for the real-world instances, a comparison with the solutions adopted by the company is also presented. Conclusions are given in the last section.

Due to the relevance of the production planning for the industry and its complexity, many authors have addressed the lot sizing and scheduling problem with different characteristics. See classical reviews about the theme in Drexl and Kimms (1997) , Karimi et al. (2003) , Zhu and Wilhelm (2006) , Quadt and Kuhn (2008) , Robinson et al. (2009) , and for a recent review see Copil et al. (2017) . A brief description of the works that address that GLSPPL with specific characteristics is presented below. Differences with the problem considered in this work are highlighted. Kang et al. (1999) treat the GLSPPL considering the minimization of setup and inventory costs using column generation techniques. In this work the cost of sequence-dependent setups is considered, but setup times are ignored. Clark and Clark (2000) studies the GLSPPL whose objective is the minimization of storage and backordering costs, but without considering setup costs. The proposed mathematical model is based on the premise that the maximum number of setups per period is predetermined. A rolling-horizon method and relax-and-fix heuristics are applied. However, the presented computational results shows that only small problems could be solved in reasonable time. Aiming to minimize production, inventory and setup costs without allowing delivery delays, Meyr (2002) considers the metaheuristics Threshold Accepting and Simulated Annealing in small real instances with identical machines. Beraldi et al. (2008) develop rolling-horizon and relax-and-fix heuristics to solve the GLSPPL in the textile and fiberglass industry environment. Unlike the mathematical model developed by Meyr (2002) , the authors introduce a compact formulation for the case of identical machines considering the setup costs, but neglecting the setup times. Józefowska and Zimniak (2008) develop a decision support system applied to a Polish company that manufacture plastic pipes, whose production environment is composed of unrelated parallel machines. This system is based on a multi-objective model which includes, among its criteria, the maximization of the machine utilization and the minimization of the deviation between the production schedule and the S&OP (Sales and Operations Plan) and the amount of products below the required level of safety stock. The model is solved using a genetic algorithm after having its solution space reduced by adding restrictions suggested by experienced planners. Mateus et al. (2010) approach the lot sizing and scheduling problem considering a factory of refractory bricks with different machines in parallel. Unlike the problem addressed in this work, the authors do not consider setup carry-over, i.e. the preparation of the machines is not maintained from one period to the next. The proposed iterative solution method is composed by two modules: the first solves exactly the problem of lot sizing considering aggregate capacity and estimated setup times; while the second searches a feasible sequencing for pre-sized lots through a GRASP meta-heuristic. Meyr and Mann (2013) deal with the GLSPPL composed by heterogeneous parallel machines with the objective of minimizing inventory and sequence-dependent setup and production costs, without backlogging. The authors propose an heuristic which iteratively decomposes the multi-line problem into a series of single-line subproblems, which can be easily solved by the heuristic TADR proposed by Meyr (2000) . Two strategies of decomposing the problem into subproblems are proposed: (i) a strategy based on priority rules and (ii) another based on aggregating the original problem, solving the aggregate problem, and disaggregating the results to define the demand and initial inventory for each line. Xiao et al. (2015) also examine the parallel-machine lot-sizing and scheduling problem with sequence-dependent setup times. In addition, release times of the items and machine eligibility and preference constraints are considered. However, the setup cost is sequence-independent and the production costs are not considered. The authors initially propose a MILP model; next the original problem is decomposed into a lot-sizing subproblem and a set of single-machine scheduling subproblems by Lagrangian decomposition. A Lagrangian-based heuristic algorithm, which incorporates the simulated annealing algorithm to improve the solution of the scheduling problem, is proposed.

Considering the GLSPPL with secondary resources, Dastidar and Nagi (2005) approach a problem on the health-related injection molding industry where a number of resources, available in limited quantities (e.g. grinders and driers), are installed on machines to perform certain tasks. The authors tackle the problem through a two-stage decomposition. In the first phase, the machines are grouped according to their criticality (machines that produce products with fewer machine options to be processed are more critical). In the second phase, the sub-problems represented by a MILP model, are solved using an open-source solver. Almeder and Almada-Lobo (2011) present MILP models to tackle the synchronization of a secondary resource in lot-sizing and scheduling problems with parallel unrelated machines. The machines have to be equipped with a special kind of resource (e.g. a tool) with limited capacity and multiple products can be produced with the same tool, therefore the tool changeovers costs and times are considered instead of product changeovers. A GLSPPL inspired by a real-world production environment in the food industry is addressed by Soler et al. (2019) . In the problem at hand, due to the scarcity of resources, only a subset of production lines can operate simultaneously and these lines need to be assembled at each production period. Due to this feature, no setup carryover between adjacent periods exist, only a subset of products can be produced in a given period, and for each product, only one production line is capable of producing it. The authors define a branching rule to accelerate the performance of the branch-and-bound algorithm of the CPLEX solver and a relax-and-fix procedure is also implemented. More recently, Ríos-Solís et al. (2020) tackle a GLSPPL to maximize the profit of assembled products where pieces are produced using auxiliary equipment (molds) to form finished products. Each piece may be processed in a set of molds with different production rates on various machines. An iterative heuristic which decouples the lot-sizing and scheduling decisions is proposed. First, the lot-size of the products is determined through the solution of a MILP model where a mold can be used in more than one machine at a time. Next, another MILP model is presented that, based on the lot-size and mold-machine assignment previously obtained, allows to determine the molds schedule in the machines in each planning period. de Armas and Laguna (2020) address the GLSPPL in a context of pipe insulation manufacturing in which a limited number of resources must be shared by parallel machines and sets of make-to-stock (MTS) and make-to-order (MTO) units must be considered simultaneously. The stock level of each MTS stock keeping unit (SKU) must be within specified limits at the end of each period, while each MTO SKU must be produced within its specified time frame. The objective is to maximize the total amount of production in a given planning horizon considering sequence-dependent setup times; the setup costs are not considered. The authors propose a two-phase procedure. First, a MIP model in which the setup times are considered independent of the sequence is formulated and solved. Next, a onepass heuristic is applied to search for setup-time savings by reordering the products assigned by the MIP model to each machine in each period. An overview on simultaneous lot sizing and scheduling involving secondary resources can be found in Wörbelauer et al. (2019) .

In the GLSPPL, n types of products are manufactured in a shop floor composed of m different machines over a horizon divided into T time periods. In a period t (the time interval that goes from instant t − 1 to instant t), a machine can produce more than one type of product, provided its time availability is not exceed. Machines have different production rates and efficiency levels. Some machines, due to their manufacturer, model, or preservation status can achieve a higher production speed with lower scrap rates than others. Consequently, the production time p iℓ and the production cost c P iℓ to produce product i on machine ℓ depend on the product and the machine. Furthermore, by technical constraints, not all products can be manufactured in all machines. Between production batches of different types of products, it is necessary a time to prepare the machine and to set the correct product parameters, which generally generates loss of material. These setup times e ijℓ and, consequently, their respective costs c S ijℓ , are sequence dependent. Preemption is not permitted. The demand d it of each product i at the end of period t is dynamic and deterministic, i.e. it is known and it varies along the time. Backordering is allowed but each backordered unit of product i is penalized by g i per period of delay. Finished goods are transferred from the factory to a centralized distribution center with limited warehousing capacity C W . Each stored unit of product i costs an inventory cost h i per period. In the considered problem, besides defining the quantities of each product to be produced and the production sequence, the solution determines in which machine each batch is manufactured in order to minimize the sum of the costs of inventory, setup, production, and backordering.

The MILP formulation presented in the current section is based on the MILP formulation introduced in Meyr (2002), that does not consider the allowance of backorders, machine eligibility constraints, and the limited capacity of warehousing. In the formulation, many products can be produced in a machine in a certain period of time. The machine availability is consumed by the time necessary to setup the machine and to produce the lot. The setup time and cost depend on the sequence of products that are produced in the machine. The planning horizon is divided in T periods. Within each period t, each machine ℓ has w ℓt variable-length subperiods. A machine can produce a single type of product within each subperiod; and the duration of the subperiod is given by the duration of the production of the lot that is being produced. There may be subperiods with zero length, even though the machine is set up to produce some product. The division into subperiods determines the sequence of the jobs on each machine and also defines the associated setup times and costs.

In order to present the proposed model we introduce the following notation: Main constants: m: number of machines, n: number of products, 

where w ℓt is the number of subperiods of machine ℓ within period t (ℓ ∈ L, t ∈ T ) and W ℓ = t∈T w ℓt (ℓ ∈ L), S ℓt = {s ∈ S ℓ |w ℓt + 1 ≤ s ≤w ℓt + w ℓt }: subperiods of machine ℓ within period t (ℓ ∈ L, t ∈ T ), wherew ℓt = 0 for t = 1 andw ℓt =w ℓ,t−1 + w ℓ,t−1 for t = 2, . . . , T . Parameters: C W : capacity of warehousing, C P ℓt : amount of time machine ℓ is available (for production and setup) within period t (ℓ ∈ L, t ∈ T ),

h i : inventory cost per period of a unit of product i (i ∈ I), g i : backordering cost per period of a unit of product i (i ∈ I), p iℓ : time required to produce a unit of product i in machine ℓ (ℓ ∈ L, i ∈ I ℓ ), c P iℓ : cost of producing a unit of product i in machine ℓ (ℓ ∈ L, i ∈ I ℓ ), q lb iℓ : minimum lot of product i that can be produced in machine ℓ (ℓ ∈ L, i ∈ I ℓ ), e ijℓ : setup time required to produce product j immediately after i in machine ℓ (ℓ ∈ L, i, j ∈ I ℓ ), c S ijℓ : cost of the setup required to produce product j immediately after i in machine ℓ (ℓ ∈ L, i, j ∈ I ℓ ),

x iℓ0 : 1, if machine ℓ is prepared to produce product i at instant t = 0; 0, otherwise (ℓ ∈ L, i ∈ I ℓ ). Variables:

q iℓs : quantity of product i produced in machine ℓ within subperiod s (ℓ ∈ L, s ∈ S ℓ , i ∈ I ℓ ),

x iℓs : 1, if machine ℓ is prepared to produce product i at the beginning of subperiod s (i.e. at instant s − 1); 0, otherwise (ℓ ∈ L, s ∈ S ℓ , i ∈ I ℓ ), y ijℓs : 1, if the setup required to produce product j immediately after i in machine ℓ occurs within subperiod s, i.e. between instants s − 1 and s; 0, otherwise (ℓ ∈ L, s ∈ S ℓ , i, j ∈ I ℓ ),

The proposed mathematical formulation is presented below:

Minimize i∈I t∈T

subject to

Objective function (1) corresponds to the sum of the costs of inventory, backordering, setup, and production. Constraints (2) define inventory and backordering conservation flow, i.e. the relation between inventory, backordering, demand, and produced quantities. Constraints (3) determine that the total amount of inventory cannot exceed the warehousing capacity of the distribution center. In the problem under consideration, existing storage capacity cannot be increased nor violated. (If desired, it would be possible to consider, in the objective function, an additional cost associated with exceeding the current capacity.) Constraints (4) guarantee that the sum of production time and setup time of each machine within each period is not larger than the corresponding machine's availability. Constraints (5) ensure that machine ℓ produces product i within subperiod s only if the machine has been previously configured for this purpose. Constraints (6) impose a minimum lot size restriction. Constraints (7) determine that, for every machine, within every machine's subperiod, a single product can be produced. Constraints (8) indicate that, if the machine ℓ switch from producing product i to producing product j occurs within subperiod s, then the corresponding setup must be made over the course of subperiod s. Constraints (9,10,11,12) determine the variables' domain. Note that it is not necessary to impose variables y ijℓs to be binary, because they naturally assume values in {0, 1} at an optimal solution. This is due to the fact that constraints (8) restrict them to be larger than or equal to −1, 0, or 1; while constraints (11) inhibit the possibility of being negative. Then, the minimization of the objective function forces them to assume binary values at the optimal solution.

The main idea of the relax-and-fix (RF) heuristic (Pochet and Wolsey, 2006) for solving a MILP problem is to partition the set X of integer variables into K subsets X 1 , . . . , X K and to solve a sequence of K smaller MILP problems. In the kth subproblem, the variables in X k are restricted to be integers; while the integrality of the variables in X k+1 ∪· · ·∪X K is relaxed and the variables in X 1 ∪ · · · ∪ X k−1 are already fixed; see Figure 2 .

. .

Constraints of first subproblem Constraints of second subproblem Figure 2 : Relax-and-fix algorithm working structure. In the second subproblem,x 1 i , i ∈ X 1 , correspond to the optimal values found when solving the first subproblem.

Model (1-12), that will be named "Model M" from now on, needs to be modified in order to be used within the context of an RF-based heuristic. Let X = {(i, ℓ, s) | ℓ ∈ L, s ∈ S ℓ , i ∈ I ℓ } be the set of all valid indices' 3-uples of variables x iℓs . The RF-based heuristic relies on the partition of the set X into K subsets X k (k = 1, . . . , K) that verify ∪ K k=1 X k = X and X k 1 ∩ X k 2 = ∅ for all k 1 = k 2 . Let Model M 1 be defined as Model M in which constraint (9) is substituted with

We can now define Model M k , for k = 2, . . . , K, as Model M in which constraint (9) is substituted with

x

where, in (14),x w iℓs for (i, ℓ, s) ∈ X w correspond to the optimal values obtained when solving Models M w for w = 1, . . . , k − 1. This expresses the fact that, in Model M k , variables x iℓs with (i, ℓ, s) ∈ ∪ k−1 w=1 X w are fixed, variables x iℓs with (i, ℓ, s) ∈ X k preserve their integrality constraint, and variables x iℓs with (i, ℓ, s) ∈ ∪ K w=k+1 X w are variables whose integrality constraint is relaxed. Note that, in Model M, constraint (9), which says that x iℓs ∈ {0, 1} for all (i, ℓ, s) ∈ X, implies that all variables y ijℓs , for all ℓ ∈ L, ∈ S ℓ , i, j ∈ I ℓ , assume binary values at an optimal solution. On the other hand, a different relation holds in Model M k (k = 1, . . . , K). Due to (8), a variable y ijℓs is guaranteed to assume binary values in an optimal solution of Model M k only if (i, ℓ, s−1) and (j, ℓ, s) ∈ X k .

The key feature of an RF-based heuristic is the determination of the number of subproblems K and the sets X 1 , . . . , X K . Problem-dependent and problem-independent strategies will be considered. The problem-dependent strategies divide variables x iℓs considering the dimensions related to machine, product, and period; and they are based on several metrics associated with machines, products, and periods that we now describe. We define the demand d i of a product i as

and the flexibility f i of a product i as the number of machines that can produce it, i.e.

for all i ∈ I. In addition, inspired by Vogel's approximation method for the transportation problem (Reinfeld and Vogel, 1958 , §4) (see also Glover et al. (1974) ), we define the discrepancy a i of a product i as the difference between its two smallest processing times, given by

Following Dastidar and Nagi (2005) , we say a machine is critical if it is able, and thus it potentially will need to, process products with low flexibility. Therefore, we define the criticality ω ℓ of a machine ℓ as

for all ℓ ∈ L. We also associate with a machine ℓ a metric of efficiency ε ℓ , given by the sum of the machine's average processing times and costs, i.e.

for all ℓ ∈ L. Finally, for a period t ∈ T , we define its overall demand δ t as

As a whole, nine different problem-dependent and two problem-independent partition strategies are considered. Each strategy consists of a way of sorting the 3-uples of indices (i, ℓ, s) ∈ X, where X is the set of valid 3-uples of the variables x iℓs . After sorting, the first ⌊|X|/K⌋ variables constitute the set X 1 , the next ⌊|X|/K⌋ variables constitute the set X 2 , and so on. In fact, if |X| is not a multiple of K, then we have that K⌊|X|/K⌋ < |X|. So, in the first r = |X| − K⌊|X|/K⌋ subsets, we consider ⌈·⌉ instead of ⌊·⌋ for the cardinality of X 1 , . . . , X r . In most strategies, the suggested order does not imply a total order of the 3-uples. Therefore, tie-breaking criteria play an important role in the strategies. In the suggested strategies, the tie-breaking criterion will always consist in applying a second strategy. Thus, the strategies are intrinsically hybrid. As a second tie-breaking rule, the lexicographic order of the index 3-uples is used. The description of each strategy follows:

• Time-dimension-based strategies:

(S1) Chronological time: Given (i, ℓ, s) ∈ X, we have that s ∈ S ℓt for some t ∈ T . 3-uples are sorted in increasing lexicographical order of (t, s), where t is the period t to which the subperiod s corresponds.

(S2) Periods with larger demand first: The same as (S1), but 3-uples (i, ℓ, s) ∈ X are sorted in decreasing order of δ t (instead of increasing order of t), where δ t is the demand of period t given by (22).

• The product-dimension-based strategies:

(S3) Most demanded products first: 3-uples (i, ℓ, s) ∈ X are sorted in decreasing order of the items demands d i given by (17).

(S4) Less demanded products first: The same as (S3) but in increasing order.

(S5) Less flexible products first: 3-uples (i, ℓ, s) ∈ X are sorted in increasing order of the items flexibility f i given by (18).

(S6) Products with more discrepant two smallest production times first: 3-uples (i, ℓ, s) ∈ X are sorted in decreasing order of the items discrepancy a i given by (19).

• The machine-dimension-based strategies:

(S7) Less efficient machines first: 3-uples (i, ℓ, s) ∈ X are sorted in increasing order of the machines efficiency ε ℓ given by (21).

(S8) More efficient machines first: The same as (S7) but in decreasing order.

(S9) More critical machines first: 3-uples (i, ℓ, s) ∈ X are sorted in decreasing order of the machines criticality ω ℓ given by (20).

• Problem-independent strategies:

(S10) More fractional variables first: In this strategy, we first solve a linear programming (LP) problem that corresponds to Model M in which the constraint x iℓs ∈ {0, 1} is relaxed to 0 ≤ x iℓs ≤ 1 for all (i, ℓ, s) ∈ X. Letx 0 iℓs , for (i, ℓ, s) ∈ X, be the optimal solution of the LP problem. For each variable x iℓs for (i, ℓ, s) ∈ X, we compute the "distance to integrality" given by

3-uples (i, ℓ, s) ∈ X are sorted in decreasing order of their distance to integrality d 0 iℓs . In fact, there is no need to sort all 3-uples since, to construct X 1 , only the ⌊|X|/K⌋ or ⌈|X|/K⌉ 3-uples with largest d 0 iℓs are required. In general, after having solved the kth subproblem (k < K), distances d k iℓs = min{x k iℓs , 1−x k iℓs } for (i, ℓ, s) ∈ X \∪ k w=1 X w are computed, wherex k iℓs is the optimal solution of the kth subproblem, and the ⌊|X|/K⌋ or ⌈|X|/K⌉ 3-uples with largest d k iℓs are selected to constitute X k+1 . (S11) More influential variables first: In this strategy, variables with more "influence" in the objective function are considered first. This "influence" could be directly related to the cost associated with the variable in the objective function; and this is the most direct interpretation of this rule. However, in the problem at hand, variables x iℓs with (i, ℓ, s) ∈ X do not appear in the objective function. However, their value influences the value of variables q iℓs and y ijℓs . Thus, the influence α iℓs of variable x iℓs is defined as

Note that, in fact, α iℓs does not depend on s and, therefore, variables x iℓs 1 and x iℓs 2 with s 1 = s 2 have the same influence measure. Therefore, in the particular problem at hand, this problem-independent strategy depends on the products and the machines. More specifically, products with large processing times and/or that, after being produced, require a time consuming preparation of the machine, are considered more influential.

Note that strategy (S10) is a dynamic strategy that differs of all other strategies because set X k is determined after having solved subproblems from 1 to k − 1; while other strategies determine all subsets X 1 , . . . , X K a priori. Moreover, strategy (S10) requires to solve an LP problem first. In the present work, we consider hybrid strategies that consists in applying a problem-dependent strategy between (S1) and (S9), using (S10) or (S11) as first tie-breaking rule, and the lexicographic order in the 3-uples (i, ℓ, s) ∈ X as second tie-breaking rule. (Hybrid strategies that combined two problem-dependent strategies were also evaluated numerically, but they showed marginal benefits in relation to those presented in this paper.)

In this section, we evaluate the performance of the partition strategies described in the previous section. In a first set of experiments, strategies are evaluated on a set of randomly generated instances. In a second experiment, selected strategies are applied to a set of ten real-world instances of the industry of personal care products. The experiments were carried out in a Intel Xeon X5690 3.47 GHz machine with 64 Gb of RAM. The RF algorithms and the formulations were solved using CPLEX 12.10.0 using default parameters with concert library and C++ programming language. The code was compiled using gcc 6.3.0 compiler with the Codeblocks 16.01 IDE. Benchmark instances and code are available at https://github.com/kennedy94/GLSPPL-RF.

The benchmark test suite is composed of 25 randomly generated instances inspired by the production environment of the target industry. All instances have a planning horizon composed of 16 time periods divided into 7 subperiods each. As each period corresponds to one week, the planning horizon comprises approximately four months. (This does not mean that each subperiod corresponds to one day. This means that a machine can produce at most seven different products in a period of one week. The subperiods correspond to the production of different products on the machine and are of varying duration.)

Five groups of instances were considered (A, B, C, D and E) and five different random instances were generated within each of the groups, with a total of 25 instances. The random generation used either discrete or continuous uniform distributions, depending on the nature of each parameter. The number of machines m for groups A, B, C, D, and E is 2, 3, 4, 5 and 7, respectively; while the number of products n for groups A, B, C, D, and E is 8, 12, 16, 20 and 28, respectively. It is considered that the machines are not ready for the production of any item at the beginning of the planning horizon, i.e. x iℓ0 = 0 for all i ∈ I and ℓ ∈ L i . Table 1 shows details of the random generation of all instances parameters. It should be noted that the random instances were generated from real-world data. In the table,ē is the average of the setup times e ijℓ for ℓ ∈ L and i, j ∈ I ℓ ; and d t (for t ∈ T ) corresponds to an aggregated period demand. For each item i ∈ I, a proportion d p i ∈ [0.05, 0.9] is randomly generated (independently of t); and d it is defined as d it = d t d p i /( i∈I d p i ). The production and setup time intervals for each group were obtained from the average times and standard deviations provided by the company. The range for the minimum lot q lb iℓ of product i on machine ℓ relative to each group was built based on the average and the standard deviation, informed by the industrial area of the company, of the minimum feasible quantity to be produced with productivity and material loss within the required standards. In fact, average and standard deviation were informed for each group in working shiftsq lb and transformed in units of products q lb iℓ considering the processing times p iℓ and the fact that each working shift corresponds to 8 hours of labor. The ranges for the amount of products in stock and backordered products at the beginning of the time horizon were calculated using averages and standard deviations, based on historical data, provided by the company. Table 2 shows detailed information about the generated instances. In the table, columns IV, CV, and CO, correspond to the numbers of integer variables, continuous variables, and constraints of Model M, respectively. The last line of each group displays average values. Initially, to decide which of the problem-independent strategies would be used as the tiebreaking rule, we ran strategies S10 and S11 varying K ∈ 1, 2, . . . , 10. The two rows at the bottom of Table 3 show the results. In the table, the results obtained with K ≥ 2 are compared with the result obtained with K = 1, which simply corresponds to solving Model M using CPLEX. The results appear separated by group and refer to the 5 instances of the group solved with 9 values of K ∈ {2, . . . , 10} . Under the heading (W, G(%)) it appears how many, out of the 45 cases, the relax-and-fix strategy found a better result (W stands for "win") than CPLEX and what the average gap was in these cases (G(%) stands for "average gap in percentage"). Under the heading (L, G(%)) appears how many of the 45 cases did the relax-and-fix strategy perform worse (L stands for "lost") than CPLEX and what was the average gap in these cases. Since there were no ties, if the number of wins and losses does not add up to 45, it is because for some instances and values of K, relax-and-fix could not find a feasible solution. The last column of the table shows the average gap considering the 25 instances and the 9 tested values of K. The results show that the strategy S11 obtained better results than the strategy S10 and, for this reason, it will be used as a tie-breaker for all the other strategies that depends on the problem. The performance of strategies S1 to S9, using S11 as the tiebreaker strategy is shown at the top of Table 3 . At this point it is important to mention that for both CPLEX and the relax-and-fix strategy a time limit of 1 hour was used. (The influence of this time limit on the comparison will be analyzed later in this section.) Furthermore, in the relax-and-fix strategy, the time was divided linearly between the subproblems such that the first subproblem has twice as much time as the last. Preliminary tests giving three times as much time to the first subproblem and dividing the time evenly among the subproblems showed similar results. The last column of the table shows that, in aggregate, that is, without evaluating the different values of K and the groups of instances individually, all strategies improved the results obtained with CPLEX with a gap ranging from −36% to −47%. The numbers also show that strategies S1 and S9 presented the best results. It is also worth noting that these two strategies found feasible solutions for all instances and all tested values of K. Table 4 shows the results for strategies S1 and S9 disaggregated, that is, for each value of K separately. Figures 3 and 4 show graphically the same that is being shown by Table 4 . The numbers in the table show that, except for the case K = 2, the results vary little depending on the value of K chosen, which can be seen as a positive feature of the methods. The numbers also show that the relax-and-fix strategies almost always beat CPLEX, except for some instances of groups A and B that concentrate the smallest instances.

Group A Group B Group C Group D Group E G(%) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) S1

39 - Table 3 : General performance of hybrid strategies S1 to S9 with S11 as a tie-breaking rule plus standalone strategies S10 and S11 on random instances.

The comparison with CPLEX depends very much on the 1 hour time limit being used; since if the instance is small and CPLEX is able to find an optimal solution (regardless of whether it can prove that the solution is optimal or not), then there is nothing that relax-and-fix can do. So we decided to test the influence of the time limit on the comparison. To this end, we re-run CPLEX and strategies S1 and S9 with time limits of 600, 1200, 1800, 2400, 3000 and 3600 seconds. We considered S1 with K = 6 and S9 with K = 4 because Table 4 shows that these were the best values of K for these two strategies. But this does not mean that we intend to use these values of K in the next experiments, since as already mentioned before, the method is robust and shows small variations with respect to the value of K. Figures 5 and 6 show the results for strategies S1 (with K = 6) and S9 (with K = 4), respectively. Figures 5(a) and 6(a) show that when the time limit is reduced the advantage of the relax-and-fix strategy increases. In the case of strategy S1, the average gap with CPLEX, which is −49.88% for the one-hour time limit, goes to −76.00%. In the case of strategy S9, the gap goes from −49.20% to −70.21%. This experiment shows that if you have less time, using the relax-and-fix strategy is even more advantageous. But the question that remains is: With less time, how much do the solutions found by relax-and-fix deteriorate? Figures 5(b) and 6(b) compare the solution obtained by relax-and-fix with a reduced budget against the solution found with the one hour budget. The figures show that the maximum deterioration is, in average, approximately 30%. Strategy S1

K Group A Group B Group C Group D Group E G(%) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) 2 5 -16. K Group A Group B Group C Group D Group E G(%) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) (W,G(%)) / (L,G(%)) 2 4 -25. Table 4 : Detailed performance of strategies S1 and S9 with S11 as a tie-breaking rule varying K ∈ {2, 3, . . . , 10} on random instances.

The deterioration of the solutions found by CPLEX with reduced time is much greater, which is why the advantage of the relax-and-fix strategy increases.

In this section we apply the presented methods to eight real instances provided by the company. All instances, as well as the randomly generated ones, have 16 periods divided into 7 subperiods. The number of machines varies between 2 and 7 and the number of products varies between 8 and 26. Table 5 shows some details of the instances and their respective models.

Recall that in the table, IV, CV and CO stands for "integer variables", "continuous variables", and "constraints". The table also shows, for each instance, the solution found by the company, which was calculated by an expert with an undisclosed empirical method.

The results with the random instances showed that there is no clear advantage of a certain value of K over others (excluding small values of K) and that small variations in the values of K generate small variations in the results. Because of this and also because we do not know how the solutions given by the company were calculated, we solved the eight instances with strategies S1 and S9 varying the time limit and varying K, as we did with the random instances. Figure 7 shows the results. On the one hand, the figure shows that, for fixed K, the longer the time limit, the better the solution found. On the other hand, the figure also shows that the two strategies find very similar values for any K ≥ 6. Because of this, we arbitrarily fixed, for both strategies, K = 8. Table 5 : Detailed information of the real-world instances. Table 6 shows the results obtained by strategies S1 and S9, both with K = 8, varying the time limit. The table also shows the results obtained by CPLEX, varying the time limit as well. For each method and time limit, the table shows the solution obtained and also shows the gap where F method and F company correspond to the objective function values of the solutions found by the method and the company, respectively. The numbers in the table show that the two proposed strategies always improve the company's solution by an amount that roughly varies, on average, between 41% and 47%, depending on the time limit given to the strategy. The solutions found by CPLEX are, on average, worse than the solutions reported by the company when the timeout is 600 or 1200 seconds; while CPLEX improves the company's solutions on average between 24% and 35% for longer times limits. Figure 8 shows the data from Table 6 in a different way. In the figure, for each instance, the solution reported by the company corresponds to 100% and the solutions found by the other methods (CPLEX and strategies S1 and S9) appear as percentages of the solution reported by the company. In the figure, CPLEX appears in light blue, strategy S1 appears in violet and Boxplot of the gaps between S1 (K = 6) applied to the 25 random instances varying its time limit in {600, 1200, . . . , 3000} and S1 (K = 6) with a one-hour time limit. have a decreasing height from left to right, which shows that, with more time, the methods are able to find better solutions. Overall, as already stated by looking at Table 6 , both CPLEX and strategies S1 and S9 improve the solutions reported by the company, except for instances P6 and P8 where CPLEX found worse solutions for threshold times below 1800 seconds. Regardless, the performance of CPLEX and strategies S1 and S9 are similar in instances P1, P2, P3 and P4. In these 4 instances, the 3 methods improve the solution presented by the company and return very similar solutions. It is worth noting that these 4 instances are the smallest instances, with dimensions similar to the random instances of groups A and B. In these instances, using CPLEX would be a reasonable alternative. The situation is different in instances P5, P6, P7 and P8, which are the largest within the set considered, both S1 and S9 substantially improve the solutions found by the company, in a way that is not being matched by CPLEX. Note even that in instances P5, P6 and P8, the solution found by strategies S1 and S9 with the shortest time limit is better than the solution found by CPLEX with the longest time limit considered.

This paper addressed an integrated real-world lot sizing and scheduling problem in a complex operating environment that occurs in a large company in the personal care consumer goods industry. This problem is composed of distinct parallel machines with limited production capacity and sequence-dependent setup times and costs. There is also limited storage capacity for finished goods. In order to solve this problem, a MILP model was presented and several problem-dependent and problem-independent strategies based on the relax-and-fix heuristic were developed. The performance of the heuristics was evaluated by solving randomly generated instances and real-world cases. Exhaustive details about the parameters of the real instances are given (see Table 1 ) in such a way that new random instances can be generated that preserve the characteristics of the real instances. This allows the generation of new test sets to evaluate and compare methods that apply to the problem under consideration. The relax-and-fix strategies introduced showed the best results overall. Strategies S1 and S9 that prioritize chronological time and critical machines, respectively, showed robustly superior Table 6 : Gap between solutions found by CPLEX and strategies S1 and S9 (with K = 8) and the company's solutions, with varying CPU time limits in {600, 1200, 1800, 2400, 3000, 3600}.

performance compared to the other strategies. In addition, the performance of the relax-and-fix strategies was compared with actual results performed by the company and the results obtained by solving the MILP model using CPLEX. Compared to the actual solutions used by the company, the strategies produced results with lower costs and a reduction between 41% and 47%, mainly from the reduction of inventory levels and better allocation of production lots on the machines. The relax-and-fix heuristics also outperformed CPLEX applied to the MILP model. Due to the successful application of the proposed methods, the ideas presented in this work are now being extended to more complex production and logistics environments with multiple distribution centers and factories that are also presented in the target company.

Conflict of interest statement: On behalf of all authors, the corresponding author states that there is no conflict of interest.

Data availability: The datasets generated during and/or analysed during the current study are available in the GitHub repository, https://github.com/kennedy94/GLSPPL-RF.

Industry Overview of the Brazilian Personal Care, Perfumery and Cosmetics Industry (In Portuguese

Synchronisation of scarce resources for a parallel machine lotsizing problem

Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs

Rolling-horizon lot-sizing when set-up times are sequencedependent

Simultaneous lotsizing and scheduling problems: a classification and review of models

Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs

Parallel machine, capacitated lot-sizing and scheduling for the pipe-insulation industry

Lot sizing and scheduling-survey and extensions

The general lotsizing and scheduling problem

A computation study on start procedures, basis change criteria, and solution algorithms for transportation problems

Optimization tool for short-term production planning and scheduling

Lotsizing and scheduling on parallel machines with sequence-dependent setup costs

The capacitated lot sizing problem: A review of models and algorithms

Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions

Capacitated lot sizing and sequence dependent setup scheduling: an iterative approach for integration

Simultaneous lotsizing and scheduling by combining local search with dual reoptimization

Simultaneous lotsizing and scheduling on parallel machines

A decomposition approach for the general lotsizing and scheduling problem for parallel production lines

Production Planning by Mixed Integer Programming. Series in Operations Research and Financial

Capacitated lot-sizing with extensions: A review

Mathematical Programming

A heuristic based on mathematical programming for a lot-sizing and scheduling problem in mold-injection production

Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms

MIP approaches for a lot sizing and scheduling problem on multiple production lines with scarce resources, temporary workstations, and perishable products

Simultaneous lotsizing and scheduling considering secondary resources: a general model, literature review and classification

A hybrid lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times

Scheduling and lot sizing with sequence-dependent setup: A literature review