Integrated Production Planning and Scheduling Optimization

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Integrated production planning and scheduling optimization Daniel Carvalho Mestrado Integrado em Engenharia Electrotécnica e de Computadores Supervisor: Pedro Amorim Co-Supervisor: Eduardo Curcio August 14, 2019 c Daniel Carvalho, 2019 Resumo Este trabalho propõe um método de solução iterativa para abordar a integração do planeamento táctico (dimensionamento de lotes) e operacional (sequenciamento) numa produção industrial com setups dependentes da sequência. Este método decompõe o problema da integração em dois. No primeiro sub-problema, planeamento táctico, o plano de produção é optimizado sem ter em conta setups necessários, usando um modelo matemático. O sequenciamento dos produtos é depois definido usando estratégias de pesquisa local. O resultado final será usado como feedback na formulação de regras adicionais para complementarem o modelo do primeiro sub-problema. De seguida, o planeamento táctico é repetido, considerando as novas regras definidas anteriormente. O algoritmo continua iterativamente até que as funções objectivo dos dois níveis convirjam. Os principais ganhos deste método são o seu procedimento intuitivo e fácil de implementar, e o pouco tempo computacional necessário. De modo a analisar resultados obtidos, dois experimentos computacionais são propostos. O primeiro para comparar o método iterativo com outros métodos de solução encontrados na literatura para problemas similares, nomeadamente meta-heuristicas e modelos de programação inteira. Por fim, a investigação foi focada num caso de uma indústria de nutrição animal, onde o setup de produção é dependente da sequência e não-triangular. O propósito do segundo experimento é avaliar os eventuais ganhos desta abordagem no planeamento de produção nesta indústria, usando os dados de uma empresa real. Os respectivos resultados demonstraram que o método iterativo é uma boa solução para problemas de produção extensivos, nos quais um modelo MIP necessita de tempos computacionais impraticáveis, derivado ao elevado número de variáveis binárias. i ii Abstract This work proposes an iterative solution method to address the integration of the tactical (lotsizing) and operational (scheduling) levels in production planning with sequence dependent setups. This method breaks the integrated lot-sizing and scheduling problem into two. In the first subproblem, at the tactical level, the production plan is optimized with production setups disregarded using a mathematical model. The production scheduling solution is then defined using local search strategies. The final solution will serve as feedback to formulate additional rules to complement the first sub-problem model. After that, the tactical level is again optimized, considering the rules defined from the operational level. The algorithm continues iteratively until the objective functions from both levels converge. The main advantages of this method are it’s intuitive and easy to implement procedure, and the low computational time required. In order to analyze results, two computational experiments are proposed. The first is performed to compare the solution method proposed with mixed-integer programming models and meta-heuristics from the literature. Then the research will focus on an animal feed industry case, in which production setup is sequence dependent and non-triangular. The purpose of the second experiment is to evaluate the potential gains to the production planning in this industry, using a real company dataset. The respective results showed that the iterative method is a good solution to extensive production problems, in which the MIP models require intractable computational times, resulting from the high number of binary variables. iii iv Acknowledgements Firstly I want to thank both of my supervisors. Eduardo Curcio, for the constant support throughout all the development of this work. I’m grateful for always being willing to help me to keep this thesis on track, without which this work would not exist. His professionalism and kindness in my guiding process will always inspire me in my professional career. I would also like to thank professor Pedro Amorim, for helping me with important insights in the writing process and key advice in the structure of this work. Moreover, I express my gratitude to the all the co-authors that contributed to this work, particularly, professor Luis Guimarães, that helped me in the early stage of this work, defining the problem addressed and the possible solution methods. I also want to thank the institution INESC TEC, for providing me with a place for the development of this thesis, where I always found an excellent working and friendly environment. Additionally I have to mention FEUP, where everyday I learned to be a better person and for making the last 5 years, the best of my life. Lastly, I have to thank my family, especially my parents, for all the continuous patience and support that always kept me focus in this work. I want to also thank my close friends for always being there when I needed, in particular my college friends from FEUP, that everyday helped keeping me in a good mood, not only during the months of this work, but throughout all my college journey, and which friendships will continue for the last of my life. Daniel Carvalho v vi “The people who are crazy enough to think they can change the world are the ones who do” Steve Jobs vii xiv LIST OF TABLES Abbreviations and symbols ATSP Asymetric travelling salesman problem BRKGA Biased random-key genetic algorithms CLPS Capacitated lot-sizing problem CSLP Continuous setup lot-sizing problem DLSP Discrete lot-sizing and scheduling problem FO Fix-and-Optimize GA Genetic Algorithm GLSP General Lot-sing and Scheduling problem HIER Hierarchical planning strategy ILSP Iterative Lot-Sizing and Scheduling Planning ILSPnR Iterative Lot-Sizing and Scheduling Planning without resolution ILSPRIterative Lot-Sizing and Scheduling Planning with resolution LS Local Search MA Memetic Algorithm MIP Mixed integer programming PLSP Proportional lot-sizing and scheduling problem RF Relax-and-Fix SA Simulated Annealing SC Supply chain TS Tabu Search xv Chapter 1 Introduction 1.1 Context Production planning is one of the most challenging subjects in operations management, with great importance in the company’s reduction of cost. In a production planning problem, the timing and sizes of production orders must be determined in order to fulfill the market demand and minimize the associated costs [4]. The two main production planning problems addressed in this work are lot-sizing and scheduling. •Lot-sizing - determines the quantities of production necessary to satisfy deterministic product demand over a finite planning horizon. •Scheduling - establishes the order in which lots are produced within a time period, accounting for the sequence-dependent setup time and costs. 1.1.1 Lot-Sizing and Scheduling in the Supply Chain The supply chain (SC) of a manufacturing company is a network of organizations with the following main functions: acquisition of raw materials, transformation of raw material into finished products, and distribution of the products to costumers, having the goal to achieve high service level at low costs. The planning problems that have to be solved to achieve this purposes cover a wide range of time scales as described by [1]: Long-term - Determines the structure of the supply chain (e.g., facility location). Medium-term - Makes decisions such as the assignment of production targets to facilities and the transportation from them to warehouses or distribution centers. In the production stage, the lot-sizing problem is placed here. Short-term - Carried out on a daily or weekly basis to determine the assignment of tasks and their sequence. In the production level, short-term planning is referred to as scheduling. 1 2Introduction The production planning (medium-term) and scheduling (short-term) problems positions in the supply chain, previously described, are represented in Figure 1.1. Figure 1.1: Production planning and scheduling positions in the supply chain [1]. 1.1.1.1 Tactical planning The medium-term planning in production is also called tactical planning, where it is decided the products to be produced in each macro-period (e.g., days) and the amounts necessary to fulfill the demand. Figure 1.2: Tactical planning framework. Decision: What products and how much should be produced in each one of the days? Main objectives: 1. Minimize inventory costs. 2. Minimize backlog costs. 3. Minimize overtime costs. 1.1 Context 3 1.1.1.2 Operational planning The operational planning (short-term) has the goal to find the best sequence of production for the products defined previously in the tactical planning. This problem is called scheduling, defined as the act of determine priorities and arranging activities with the purpose of minimizing the production time and costs [5]. Figure 1.3 represents this operational phase, the previous macro-periods (days) are divided into micro-periods (e.g., hours) to plan the production sequence. Figure 1.3: Operational planning framework. Decision: What is the best the production sequence in each one of the days? Main objectives: 1. Minimize the setup costs. In sequence-based manufacturing, a changeover from one product to another usually causes setup costs as well as setup times which are sequence-dependent. If those those setups are not well managed it may result in significant losses in production capacity, which may lead to unmet demands and costumer dissatisfaction. This problem is frequently found in distinct industries like animal feed, automobile, chemical and electronics. This work will later focus on a case of an animal feed company, in which it is frequent to have the possibility of contamination in the production of two consecutive products from different families, requiring a cleaning batch in between those products. 1.1.2 Integrated planning Primarily most commercial production planning and control systems tried to construct feasible production plans in a step-wise manner, so the manufacturing resource planning (MRP II) logic was implemented. It can be divided in 3 main phases, as described by [6]. 4Introduction ∗Phase I: Starting with the final products, lot sizes are computed level by level, ignoring capacity constraints. ∗Phase II: The results of the first phase usually exceeds the capacity in some periods. In this phase some lots are shifted to find a plan that meets the capacity limits. ∗Phase III: The plan sequence decisions are made and the orders sent to the shop floor. The MRP II concept, by having Phase I, II and III disconnected, may present some problems: long lead times, high work-in-progress, and unfulfilled orders. So sophisticated approaches are necessary to solve production planning and scheduling problems. Strategies to solve this problem can be classified in 3 categories, illustrated in the Figure 1.4. Having one master and one slave, the communication can be unidirectional from the master to the slave (Hierarchical), or with feedback (Iterative). In the case that this division does not exist, and the problem formulation refers to all working periods, the solution will have all the necessary information to both the lot-sizing and scheduling problem (Full-space). Figure 1.4: Solution strategies for production planning [1]. This study reviews these three approaches for the integration of medium-term production planning and short-term scheduling that enable the creation of better production plans than those obtained when solving the two problems independently by introducing the solution of the lot-sizing problem in the scheduling planning level. The goal of this integration is to construct the production plan for all the planning horizon. Production plans are created with the objective of minimizing the overall costs consisting mainly of inventory holding, setup, overtime and backlog, while satisfying the available capacity and meeting the demand in each time period. In the Figure 1.5 we can see a representation of an integrated planning solution that will be explored in this work. 1.2 Motivation 5 Figure 1.5: Integrated planning. 1.2 Motivation Several companies face the problem of integrating lot-sizing and scheduling in their production planning over a given planning horizon, and the constant complexity growth in the industry’s productions has urged a research from the scientific community to create new methods, more sophisticated, to attend the needs of the companies and keep competitiveness. In many of these production environments, switching between production lots triggers operations with costs for the company, such as machine adjustments and cleansing procedures. The decisions of lot-sizing and scheduling are often made separately, which can cause operational costs and compromise the response to the demand deadlines their quality taking into account the operational costs and demand deadlines. So there is an urge in companies to integrate these phases. Therefore the two main motivations of this study are the following: Scientific: Development of efficient solution methods to the lot-sizing and scheduling integration problems, found in the literature. Practical: Obtain good solutions to the production planning that consider tactical and operational planning, that are aligned with the corporate objectives of the company. 6Introduction 1.3 Objectives This work conducts a series of studies on mathematical models and other solution methods for integrated lot-sizing and scheduling problem and apply them in a real case of a company of animal feed. The ultimate goal is to optimize the production planning in order to reduce the company costs. Summarily our objectives are the following: •Mathematically modeling a real optimization problem of production planning and scheduling. •Developing and comparing different solution methods in terms of solution quality and computational complexity. •Assessing the value of integration and the solution quality obtained over the current planning performed by an animal feed company. 1.4 Thesis structure This thesis is organized as following. Chapter 2presents a literature review on the subject that studies the current state of the art. The study initially focuses on the mathematical models used to represent this problem and then explores other solution methods based on heuristics and metaheuristics. In Chapter 3, the problem addressed and its mathematical model are defined. The proposed iterative solution method is presented and detailed in Chapter 4. Chapter 5firstly describes other solution methods commonly used for this planning problem that are used to benchmark the iterative method proposed. All methods are then assessed with the instances found in the literature and their results are compared, both in quality and computing power. Still in Chapter 5, a real case of an animal feed company in Brazil is studied, having a dataset and their planning results, the solutions and gains from the various method proposed are analyzed. In the last chapter, the conclusion of the work is presented as well as proposals for future work. Chapter 2 Literature review This chapter is divided in 3 sections. Firstly, a literature review on lot-sizing and scheduling problems is made, comparing the various mathematical models used to represent it, particularly the large and small bucket models, focusing then on the hybrid models that will be used on this study. Secondly, it presents a study on other solution methods using heuristics and meta-heuristics. The chapter concludes with an investigation on these solutions methods applied in the case of animal feed industry. 2.1 Mixed integer programming models Linear programming is a mathematical optimization used to maximize (or minimize) a linear objective function subject to one or more constraints. An MIP model adds one additional condition that at least one of the decision variables can only take on integer values. The use of integer variables greatly expands the scope of useful optimization problems that you can define and solve. An important special case is a decision variable that must be either 0 or 1 at the optimal solution. Such variables are called binary integer variables and can be used to model yes/no decisions. However, integer variables make an optimization problem non-convex, and therefore far more difficult to solve. Memory and solution time may rise exponentially as more integer variables are added. This literature review specifies the main lot-sizing and scheduling MIP models and their variants. It was based on [6] that summarizes the work in the field and details the differences of the lot-sizing and scheduling problems. They can be classified into 2 major categories [7], some based on micro-periods for short-term planning (small-bucket problems), and models which use macro-periods for medium-term planning (large-bucket problems). 2.1.1 Large-bucket problems To represent the tactical planning level, [6] present the capacitated lot-sizing problem (CLSP) which determines the lot sizes of production but not the sequence of the lots. Several items may be produced per period, that represents a big time slot, typically one week in the real world. The planning horizon is usually less than six months. Next we present the MIP model for this problem: 7 14 Literature review It is also necessary to have another decision variable to decide if sequence sis selected for production: Ws∈ {0,1}= 1 if sequence sis selected for production. The subproblem relative to the formulation of the predefined sequences can be solved with a metaheuristic method using local search strategies. Another solution method is proposed by [11], solving the subproblem as a price collecting traveling salesman [15]. A network is created that consist of a set of nodes, each representing a product, and arc sets representing the production sequence of this products. This method is described with more detail by [11] in Appendix B. The model proposed by [14] is then represented as the following: min J ∑ j=1 T ∑ t=1 hjIjt +∑ s∈St c scsWs(2.24) Subject to: (2.13) J ∑ j=1 pjxjt +∑ s∈St b stsWs≤Capt∀t(2.25) ∑ s∈St Ws=1∀t(2.26) ∑ s∈St fjsWs=∑ s∈St ljsWs∀j,t(2.27) xjt ≤Mj∑ s∈St gjsWs∀j,t(2.28) Objective function (2.24) minimizes the total expenditure in holding costs and setup costs incurred from sequence selection. Constraints (2.13) represent the classical inventory balances. Capacity constraints are expressed in (2.25). The use of one sequence in each macro-period is ensured by (2.26). Constraints (2.27) guarantee setup carry-over by linking the first and last products of consecutive time periods. Lastly, Constraints (2.28) only allows production for products in the sequence selected in period t. 2.2 Heuristics and metaheuristics In this section, solution methods based on heuristics and metaheuristics are reviewed. This methods can be applied in the integrated lot-sizing and scheduling problem. We present their functionality and how they can be applied. 2.2 Heuristics and metaheuristics 15 2.2.1 Heuristics Here firstly we describe two heuristics, Relax-and-fix (RF) with Fix-and-Optimize(FO), and how they can be employed to solve MIP models. Then it is presented the local search heuristic that works as base to some metaheuristics that will be shown next. 2.2.1.1 Relax-and-fix (RF) The Relax-and-fix method is a construction heuristic used in the resolution of mixed-integer problems, which defines an initial solution by solving several small MIP models. Initially, all binary variables in the RF solution are relaxed which means they can take any value between 0 and 1. Then a set of variables X, according to a window size Ws defined, are forced to be integer, while the others are kept relaxed, and the resulting MIP is then solved. Next, the Xvariables are fixed with the results and another set of integer variables are optimized. This process is repeated until all variables are fixed [16]. This method was applied in a animal feed industry by [17], mentioned before, where the results are discussed and compared with the classic MIP solvers and with the current company’s planning strategy. 2.2.1.2 Fix-and-optimize (FO) The fix-and-optimize heuristic uses another approach to resolve MIP models. It also operates in an iterative fashion to solve a series of sub-problems that are derived from the main MIP model. In each iteration, most binary variables are set to a fix value and the resulting sub-problem is then solved by a MIP solver. A different set of binary variables are left "free" to optimize in every iteration until all the variables are optimized [18]. 2.2.1.3 Local search Local Search (LS) is one of the oldest and simplest heuristics method. It starts at a given initial solution and at each iteration the algorithm replaces the current solution by a neighbor solution. A neighbor is generated by the application of an operator that performs a small perturbation to the current solution. Three methods can be used to choose the next solution: •Best improvement (Steepest ascent): All the neighbors are calculated and the best solution is chosen to replace the current one. •First improvement: Neighbors solutions are generated until one is better than the current solution that then replaces it. •Random Selection: A random neighbor is selected from those improving the current selection. 16 Literature review This search stops when all candidate neighbors are worse than the current solution, so a local optimum is reached. In the case that the objective function is a minimizing one, LS may be seen as a descent walk in the graph representing the search space. Next it is presented the pseudo-code for the steepest ascent LS variant. Algorithm 1: LS (steepest ascent) pseudo-code. Data: s=s0;/∗InitialSolution ∗/ 1while (Termination Criteria no satisfied) do 2Generate (N(s)); /*Generation of candidate neighbors*/ 3if (No better neighbor) then 4Stop; 5else 6s = s’; /* Best neighbor s’ */ 7end 8end 9Output: Final solution, local optima In general, LS is an easy method to design and implement, but one of its main disadvantages is that it normally converges toward local optimal solutions. Therefore more complex methods, presented below, are needed to avoid that the algorithm gets trapped in local optima. 2.2.2 Metaheuristics Metaheuristics are a higher-level procedure designed as strategies to guide a search process that may provide a sufficiently good solution to an optimization problem. Metaheuristics work with a set of solutions which is usually too large to be completely sampled. An analysis on the various methods was made by [19], among the metaheuristics discussed are Tabu Search; Simulated Annealing; Genetic Algorithms; Memetic Algorithms that will be described below in more detail. The review of the metaheuristics in this section is based on [9]. 2.2.2.1 Tabu search Tabu search (TS) is a method to solve optimization problems, firstly proposed by [20]. It works as a steepest ascent LS algorithm but it uses a list to store past solutions, it also accepts nonimproving solutions to escape from local optima when all the neighbors are worse than the current solution. To avoid cycles, TS discards the neighbors that have been previously visited, managing a memory of the solutions recently applied, which is called tabu list. The tabu list may be too restrictive so an aspiration criteria is created in a way that tabu solutions can eventually be accepted. 2.2 Heuristics and metaheuristics 17 Then the admissible solutions are the non-tabu ones or that hold the aspiration criteria. The TS pseudo-code is presented next: Algorithm 2: TS pseudo-code. Data: s=s0;/∗InitialSolution ∗/ 1Initialize the tabu list; 2while (Stopping criteria not satisfied) do 3Find best admissible neighbor s’; 4s = s’; 5Update tabu list, aspiration conditions; 6end 7Output: Best solution found 2.2.2.2 Simulated annealing The simulated annealing (SA) concept, applied to optimization problems, was first introduced by [21]. SA is based on the principles of statistical mechanics, where the annealing process requires heating and then slowly cooling to obtain a strong crystalline structure. This analogy is represented in the Table 2.1. Table 2.1: Analogy between the physical system and the optimization problem. Physical System Optimization Problem System state Solution Molecular positions Decision variables Energy Objective function Ground state Global optimal solution Metastable state Local optimum Rapid quenching Local search Temperature Control parameter Careful annealing Simulated annealing The algorithms works using an random LS strategy. At each iteration a random neighbor is generated, and moves that improve the actual solution are always accepted. However in SA, if the neighbor is not better it can be selected with a given probability (2.29) that depends on the current temperature (T) and the difference to the actual solution (∆E). If the starting temperature (T0) is very high the search will be like a random LS. Otherwise, if it is very low, it will behave like a first improvement variant LS. Hence, a balance is needed between these two extreme procedures. P(∆E,T) = e−∆E T(2.29) Acceptance probability function: Main element of SA that enables non-improving neighbors to be selected. 18 Literature review The cooling schedule: Defines the temperature at each step of the algorithm. Essential to the efficiency and effectiveness of the algorithm. The following algorithm describes the SA search process: Algorithm 3: SA pseudo-code. Data: s=s0/* Initial Solution*/ T=Tmax /* Start temperature*/ 1while (stopping criteria not satisfied ( T < Tmin)) do 2while (Equilibrium condition not satisfied (fixed temperature)) do 3Generate random neighbor s’; 4∆E = f(s’) - f(s); 5if (∆E < 0) then 6s = s’ /*accept the neighbor solution*/ 7else 8Accept s’ with probability (e−∆E T); 9end 10 end 11 T = g(T); /*Temperature update*/ 12 end 13 Output: Best solution found 2.2.2.3 Genetic algorithms (GA) methods Genetic algorithms are a family of computational methods inspired by the evolution theory. These algorithms encode a potential solution to a specific problem on a simple chromosome-like data structure, and apply recombination operators to these structures in order to optimize the solution. Five main phases are considered in a standard genetic algorithm [22]: Initial Population: The process begins with a set of individuals which is called a population. Each individual represents a solution to the problem and it is generated randomly. Fitness score: The fitness function determines how good a solution is. It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score. Selection: The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for the crossover. Crossover: Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes. The individual is created by exchanging the genes of the parents among themselves using a crossover point. That new solution is then added to the population. 2.2 Heuristics and metaheuristics 19 Mutation: In certain new individuals formed, some of their genes can be subjected to a mutation with a low probability. Mutation occurs to maintain diversity within the population and prevent premature convergence. The pseudo-code algorithm with all this phases is presented below: Algorithm 4: GA pseudo-code [23]. Data: Set pop-size, max-gen, gen = 0, cross-rate, mutate-rate 1initialize population; 2while maxgen ≥gen do 3evaluate fitness; 4for i←1to pop-size by 1do 5select(parent1, parent2); 6if (random(0,1) ≤cross-rate) then 7child = crossover(parent1, parent2); 8end 9if (random(0,1) ≤mutate-rate) then 10 child = mutation(); 11 end 12 end 13 end 14 Output: Best solution found. A variant of the GA are biased random-key genetic algorithms (BRKGA), introduced by [2], where one of the parents used for mating is biased to be of higher fitness, called the elite individuals, a pefraction of the population with the best solutions. The transition process from the previous generation to next in the BRKGA method is represented in the Figure 2.1. BRKGA also uses an parameterized uniform crossover, in which for each gene has the probability (1 - pe) of inheriting the value from the elite parent instead of the non-elite one. In this way, the offspring is more likely to inherit characteristics of the best parent. A BRKGA heuristic was presented by [24] for the production scheduling problem. The methods shown good results getting the best-known solution for 73 % of the instances. The BRKGA’s flowchart is represented in the Figure 2.2, which is very similar to the standard GA. 20 Literature review Figure 2.1: Transition between generations in BRKGA [2]. Figure 2.2: BRKGA’s flowchart [2]. 2.2.2.4 Memetic algorithm The term ‘memetic algorithms’(MAs) was introduced in the late 80s to define a family of metaheuristics that have as central theme the hybridization of different algorithmic approaches for a given problem. The memetic algorithms can be viewed as a merge between a population-based global algorithm and a local search made by each of the individuals. They are a special kind of genetic algorithms with a local hill climbing. In a memetic algorithm the population is initialized at random or using a constructive heuristic. Then, each individual makes a local search to improve its fitness. Like generic GA’s, individuals with higher fitness are more likely to be selected to pass their genes to the next generation. The 2.3 Lot-sizing and scheduling in the animal feed industry 21 role of the local search in memetic algorithms is to locate the local optimum more efficiently then genetic algorithms, using less randomness. Algorithm 5: Memetic algorithm pseudo-code [23]. Data: Set pop-size, max-gen, gen = 0, cross-rate, mutate-rate 1initialize population; while max-gen > gen do 2apply GA; 3apply local search; 4gen = gen + 1; 5end 6apply final local search to best chromosome; 2.3 Lot-sizing and scheduling in the animal feed industry This work also addresses the production planning of an animal feed company, in the studied case, the optimization problem occurs in planning the schedule for a mixer’s use. Product changes are frequent in this industry, typically about 30–40 per week, and can be grouped into several families. Products within the same family do not contaminate each other and have negligible changeover times and identical processing times. A complicating feature of the animal feed industry is that some product families can contaminate others if produced in successive batches so the production line must be cleaned, resulting in substantial setup time. Thus, the production scheduling in this industry, has the objective of minimizing the amount of cleanings necessary in the production plan. 2.3.1 Non-triangular setup times Triangular sequence-dependent setup times occurs when it is always faster to perform the sequence from product p to r directly than via a third product q. However, in the animal feed and other industries, typically such cleanings can sometimes be avoided by introducing a single lot of an intermediate product from other family, between the two problematic products, since the triangular inequality does not hold. which is called non-triangular setup times [3]. This concept is represented in the Figure 2.3. Figure 2.3: Triangular and non-triangular setup [3]. 22 Literature review 2.3.2 Integration problem in animal feed industries [17] conducted a research on the production planning of a Brazilian animal feed compound company, that works with one mixer. To decide lot sizes and sequences in each period, two MIP models were designed based on the GLSP. The first for independent sequences, where a cleaning is made during non-productive time between periods, therefore not requiring initial setup in the beginning of the period. The second for depedent sequences where the production is active 24h a day, eliminating the non-productive time between periods. This last one being more complex since the sequence has to be optimized over multiple periods rather than over a single period. Another approach was made by [25], where the production system studied was constituted by one mixer in the first stage, a pelletizer, an extruder and a bulk machine, with each one having one or more silos. The production planning sequences the batches on the mixer and also assigns each product to a silo. Here a MIP model is formulated as an extension of the GLSP. A more extensive study on the integrated lot sizing and scheduling problem in the animal feed compound industry is presented by [26]. Using a case study in a company of the sector, two approaches are proposed to model and solve the problem. The first is based on GLSP with sequence dependent setup times. The other consists of modeling the lot sequencing problem as an asymetric travelling salesman problem (ATSP). For each method is proposed two company strategies related to the cleaning of the production line already mentioned before, the first for Independent Sequences, and the second with Dependent Sequences (setup carryover). The instances presented in the appendix of [26] will be used in a computational experiment later and their respective results compared to the method proposed. Chapter 3 Problem Definition The objective of this chapter is to provide a clear definition on the problem that is addressed by this thesis. First, all the parameters needed for the lot-sizing and scheduling integration problem are presented, focusing then on the specific case of an animal feed industry. 3.1 Integrated production planning The integrated production planning considered in this work consists of a set of N products, and a planning horizon of T macro-periods, each one containing N micro-periods. Every product has a production time that, alongside the setup times calculated, have to respect the capacity(time) of each macro-period. The main decision of the planning is to decide the production quantities Xjs for each micro-period s, in order to answer the demand that is represented with a matrix N×T that has the needs djt for every product jin macro-period t. The setup costs and time values, between each product, are represented by a matrix N×N. Table 3.1 presents an example of a production plan solution for a timespan of 5 days, considering 5 distinct families (Fam) of products and showing the quantity (Quant) to be produced for each product. Table 3.1: Example of a Production Plan. Order Period 1 Period 2 Period 3 Period 4 Period 5 Fam Quant Fam Quant Fam Quant Fam Quant Fam Quant 1 2 10 4 8 1 4 4 5 5 6 2 5 3 2 4 3 12 2 8 4 1 3 3 8 5 6 2 5 1 5 2 1 4 1 5 3 2 5 1 3 1 3 10 5 4 7 1 9 4 2 5 8 1 7 23 30 Iterative method 4.3 Tactical level Firstly, the ILSP uses a simple linear programming model, represented below, to solve the tactical planning sub-problem. This tactical model (ILSP-Tactical) is based on the CLSP model previously mentioned in section 4.3. In the model it is considered the possibility of having backlog and overtime. Data: j=1,.....,JNumber of products t=1,.....,TNumber of periods CtCapacity (time) available in period t. OtOvertime (time) available in period t. pjCapacity consumption (time) needed to produce one unit of product j. hjNon-negative holding costs of product j. octOvertime costs for product family j. bcjBacklog costs for product family j. djt Demand of product jin period t. Ij0Initial inventory of product jat the beginning of the planning horizon. Decision variables (Model’s output): Ijt ≥0 Inventory of product jat the end of period t. Bjt ≥0 Backlog of product jat the end of period t. Ott≥0 Overtime used in period t. qjt ≥0 Production quantity of item jproduced in period t. 4.4 Operational level 31 min J ∑ j=1 T ∑ t=1 (Ijthj+Bjt bcj)+ T ∑ t=1 Ottoct(4.1) Subject to: Ijt−1+Bjt +qjs =Ijt +Bjt−1+djt ∀j,t(4.2) J ∑ j=1 pjqjt ≤Ct+Ott∀t(4.3) Ott≤Ot∀t(4.4) For the ILSP-Tactical, the objective function (4.1) takes into account the three possible costs in the production studied: holding Inventory, backlog and overtime. Constraints (4.2) represent the typical inventory balances combined with the backlog possibility. Capacity of each macro-period is controlled by constraints (4.3) and the maximum overtime is limited in Constraints (4.4). For a simple production planning of 5 families of products and 3 macro-periods, a tactical level solution can be represented as: Table 4.1: Example of tactical level solution. Period 1 Period 2 Period 3 Fam Quant Fam Quant Fam Quant 1 10 1 8 1 4 2 3 2 4 2 12 3 8 3 6 3 5 4 5 4 2 4 1 5 7 5 9 5 2 4.4 Operational level After obtaining an tactical solution, the next step of the ILSP is to optimize the production sequence. First, a good initial solution is generated and then local search techniques are used to improve the solution. This process is represented in Figure 4.3. 32 Iterative method Figure 4.3: Operational level algorithm. 4.4.1 Generate initial solution Firstly, the algorithm 6generates initial solutions for each macro period, considering a new parameter, setups2j, that represents the sum of the setup costs of a product when it is the second in every setup pair. This parameter will be important to choose the products in the making of an initial good sequence solution. The concept of the algorithm is that the product from the first period in the tactical level solution that requires the most setups, setups2j, is chosen as the initial one, then the next product to be placed in the sequence is always the one that creates the less setup costs. This is repeated until the total production sequence is defined. Since in the cases addressed it is possible that two products can not ever be produced consecutively, a new restriction is necessary where, in the case that the last products in a period have this condition, the sequence creation is stopped. Then a different product from the tactical solution is chosen as the initial one to again start the algorithm. This strategy was chosen in order to reduce the running time in the local search phase since it represents an already good starting solution to it and requires low running time. 4.4 Operational level 33 Algorithm 6: Generate an operational solution pseudo-code. Data: 1sci j; /*Matrix of setup costs from product ito j*/ 2setups2j= sum(sci j); /* Sum of setup cost for product j*/ 3plant; /*Tactical plan with products for each period t*/ 4opt,s; /*Operational plan with the sequence of the products for each period t*/ 5ptried ; /*list of products already tried as the initial product*/ 6while (size(ptried) < total number of products do 7op0,0=j∈plantwith max(setups2j) if jnot in ptried; /* Choose the product that needs the more setups for the initial one in the first macro-period, that has not been tried yet*/ 8for t←0to Tby 1do 9for s←0to length(plant)by 1do 10 if (Every product left can’t be produced after ops−1)then 11 ptried .add(op0,0); 12 break; /* Go the next iteration of the while cycle*/ 13 else 14 opt,s=jin min(scps−1j) if j∈plantwith plantand not in the solution yet; /* the next product to be chosen is the one that creates the less amount of setup costs for the previous product*/ 15 end 16 end 17 end 18 break; /* The whole plan has been defined*/ 19 end 20 Output: op /* Sequence of production*/ For the special case of an animal feed industry addressed in this work, one part of the algorithm is modified. As mentioned before, in this production sector the setup costs represent cleanings, that are needed in the mixer if a product is produced after another specific type that contaminates it. Therefore in line 14, instead of choosing the minimum setup cost, we choose one product that doesn’t require cleaning if possible. However there may be various situations where there are several products still to place in the sequence that does not force a cleaning in the mixer. In order to better optimize the sequence, a strategy around the setup costs was chosen to decide which one of the products is to be placed. This is done using another parameter, setups1j, that now represents the sum of the setup costs of a product when it is the first in every setup pair. The product chosen is the one that creates the necessity of cleaning in the less amount of products still to produce, min(setups1j). The goal is that more problematic types of products are placed at the 34 Iterative method end of the sequence, so less cleanings are needed and those products become easier to identify later to create the feedback information. Also being dependent sequences with setup carryover for the next period, the last mixer state, for a problematic product, can be passed by to the next period and avoid a cleaning, if that same product is to be produced in that period. So line 14, used to decide the next product after a product i, is changed to: opt,s=j∈plant,with min(setups1j)∀j that scopt,s−1,j=0 4.4.2 Local search heuristic After that, to optimize the initial solution, a local search (LS) heuristic is used for each macroperiod with the following characteristics: •Neighborhood: For each iteration the neighbors of the current solution are evaluated. To create each one of the neighbors, two products positions in the sequence are swapped, demonstrated in Figure 4.4. •First improvement: In each iteration the first neighbor that improves the best solution is chose as the new solution. This first improving technique was chosen, instead of the steepest descent one, since for extensive production problems, creating all the neighborhood for each iteration quickly becomes intractable. •Stopping criteria: The local search ends when all the neighborhood solutions are worst than the current one so a local optimum was reached. In Figure 4.4, it is demonstrated how the neighbours are defined. Each arrow represents a switch between the two products that originates a different scheduling solution. Using a simple example of a sequence with four products, the first one is swapped with every subsequent product after it, then the second is placed in every position ahead of it and so on consecutively. Therefore there is no duplicated position swaps in the neighborhood. 4.4 Operational level 35 Figure 4.4: Neighborhood creation strategy in Local Search. 4.4.2.1 Non-triangular instances In the case of non-triangular instances, an additional type of neighbor solutions are formulated in the local search heuristic. For each product, a single lot with the minimum production quantity allowed is placed in a different position in order to test if it is able to reduce the setup costs. This is possible in the case of non-triangular production setups, since high setup costs can be avoided by producing an intermediate product. This process is represented in Figure 4.5. Figure 4.5: Additional neighbor creation strategy for non-triangular instances. 36 Iterative method Having the example in Table 4.1 as input for operational level, the output of the algorithm is represented in Table 4.2. Table 4.2: Example of operational level result. Order Period 1 Period 2 Period 3 Fam Quant Fam Quant Fam Quant 1 2 10 4 8 1 4 2 5 3 2 4 3 12 3 3 8 5 6 2 5 4 1 5 3 2 5 1 5 4 7 1 9 4 2 4.5 Feedback from operational level to tactical As mentioned before, the integration of both levels of the ILSP comes with a feedback given from the operational phase to the next iteration of the tactical phase. After the optimization of the sequence it is registered the capacity used and where in the plan still are found significant setup costs. This information are incorporated in the tactical level of the next iteration. The operational level, at the end of the scheduling optimization, sends two type of feedback back: •Capacity: Adding the setup times in the operational level, the amount of capacity time used above the limit or free time in each period is sent to the next tactical level iteration. •Setup costs: The products that created significant setup costs, unavoidable during the operational level, have an additional cost in the next tactical level iteration. The formulation of this tactical level inputs are described in detail in the next subsections. 4.5.1 Capacity feedback Although the ILSP-tactical model presented in section 4.3 takes into account the capacity limits presented in constraints 4.3, it does not acknowledge the setup times needed since the sequence is not being defined. Therefore it is common that the model estimates that the capacity is respected but after the sequence is optimized, adding the setup times, that can no longer be true. The capacity feedback is accomplished by changing the captand ottlimits in the ILSP-tactical model. Having the optimized sequence, initially the capacity time used for each period is calculated with the following formulation: usedt=∑ j pjqjt +∑ i ∑ j sti jzi jt ∀t(4.5) 4.5 Feedback from operational level to tactical 37 Then it is registered where usedtis in the capacity limits. There are 2 possible situations that could take place in each macro-period t: •usedt<capt: If the capacity used is less than the limit in macro-period t, the new capacity in the next iteration of the tactical level is increased and the overtime boundary is decreased by the same amount. new capt=capt+ (capt-usedt) new ott=ott- (capt-usedt) •usedt>capt: If the capacity used exceeds the limit and requires overtime, the inverse of the previous case happens, with the new capacity and overtime being adjusted. new capt=capt- (usedt-capt) new ott=ott+ (usedt-capt) The goal of this approach is to adjust the capacity and overtime limits according to the results of the scheduling phase. The total time available in the tactical level doesn’t change but as the portions of the standard capacity and the overtime vary, the model tends to put more products in periods with less overtime in order to avoid overtime costs. 4.5.2 Setup costs feedback For the setup costs feedback two different approaches were developed. The first, ILSPnR, allows the tactical phase to choose when to produce the products that were resulting in high setup costs. The second, ILSPRdetermines the macro-periods for the problematic products that reduce the setup costs and forces them to be produced at these periods in the tactical level. 4.5.2.1 ILSPnR - Feedback from setup costs without resolution As mentioned before, at the end of the sequence optimization in the operational level it is possible setup costs could not be avoided. The Table 4.3 shows an example of an optimized sequence that still presents a cleaning between product 8 and 1. Table 4.3: Example of a production sequence with a cleaning. Day Order 2 4 7 1 9 4 2 5 8 cleaning 1 7 For this first proposed method, ILSPnR, it is only analyzed in which periods tan inevitable expensive setup costs will occur for a product j. In productions where all changeovers require a 38 Iterative method setup cost, to determine this expensive setup costs after the scheduling optimization, all the setup costs are sorted and the biggest hsc are considered, where hsc is a small portion of the total number of setup costs. In productions with constant setup costs, as it is in the animal feed case analyzed with the cleanings process, all the setups costs after the operational level are considered. To incorporate this information in the tactical level, a new production cost pcjt is added to the ILSP-Tactical model for products jthat present the considered hsc setups or cleaning in period t. This new parameter is updated at the end of every iteration if this big setup costs are found: pcjt =sci j (4.6) An additional variable yjt is created that determines if product jis being produced in period t and the objective function is also updated to add this new costs: yjt ∈ {0,1}1, if product jis produced in period t( = 0 otherwise). min∑ j ∑ t (Ijthj+Bjt bcj)+∑ t Ottoct+∑ t ∑ j yjt pcjt (4.7) Therefore the ILSP-Tactical model can still place the problematic product in the same period if putting it in any one of the others creates more costs than the setup ones. But this strategy enables the model to acknowledge inevitable setup costs. 4.5.2.2 ILSPRFeedback from setup costs with resolution The previous method only determines where the inevitable hsc setups are and gets that information to the Tactical Level in order for the model to have that costs into consideration. One step forward for this strategy is the second method proposed, ILSPR. It locates in which different macro-period the problematic product can be placed that will create the less costs and then forces the tactical level to follow that solution. This is accomplished by using the local search based algorithm 7. The idea is that for every hsc setup or cleaning considered, the products that are causing the setup cost are moved to every possible position in other macro-periods sequences, creating new solutions. The evaluation of the solution also takes into account the capacity, holding inventory and backlog costs, since the products are being moved to new macro-periods and the ones that improve the initial sequence is stored in a list. Then a steepest ascent approach is employed, in which the best solution of the list replaces the initial solution, and the parameters of the setup avoided: product type, old macroperiod and new macro-period are stored. This process is repeated for all the remaining hsc setup costs, considering the new best solution as reference, until all of them are resolved or no better solution is found. 4.5 Feedback from operational level to tactical 39 Algorithm 7: Find solutions for high setup costs pseudo-code. Data: 1Nhsc ←number of hsc setup costs found from ito jin macro-period t; 2sc setup cost with the parameters: tperiod, ifirst product and jsecond product; 3osolutiont,s; /*optimized sequence solution for each macro-period t*/ 4nsolutiont,s; /*new solution for each macro-period t*/ 5Lsolutions ←empty list of new solutions, with the product and position changed; 6StProduction sequence for macro-period t; 7while Nhsc > 0 do 8for sc ←0to Nhsc by 1do 9for t←06=sctto Tby 1do 10 for s←0to Stby 1do 11 nsolution =osolution 12 delete nsolutionsct,scs/* Take out product jfrom the period sctwhere he is creating a hsc setup cost */ 13 nsolutiont,s=scj; /* Put product jfrom period sctin period tand position s */ 14 if (nsolution.f itness < osolution.fitness) then 15 Add [nsolution,j,sct,t] to Lsolutions; 16 end 17 end 18 end 19 if lenght(Lsolutions) = 0 then 20 break; /*None of the products position movements improved the solution */ 21 Store j,sctand tfor the best solution in Lsolutions; 22 osolution = best solution in Lsolutions; /* the new solution where the remaining hsc setup costs are going to be analysed is the best from the previous iteration*/ 23 end 24 Output: Setup costs resolved. In the end of the algorithm, the information stored for each product position moved is passed on to the tactical level. For this it is introduced two new variables in the ILSP-Tactical model: maxqjt maximum quantity of product jthat can be produced in period t. minqjt minimum quantity of product jthat needs to be produced in period t. And an additional constraint that controls the production quantities: 46 Computational Experiment Figure 5.5: ILSP-Tactical production planning after first iteration. The production quantities obtained by solving the tactical level are used in the operational level to obtain the best production sequence. Figure 5.6 presents the solution structure for the operational level considering cleaning setups, production capacity and its fitness. The next table represent its output for this first iteration. It is also possible to see where cleanings are necessary, the capacity limit and the one used in each period. Lastly it is also presented the fitness of the solution, the total costs produced by the represented production plan. 5.2 Illustrative example of ILSP 47 Figure 5.6: Solution structure after the first iteration. 5.2.2 Feedback results At the end of each iteration, feedback from the final solution of operational level is used in the next iteration. As described in Chapter 4, this feedback has two type of information. The first is related to capacity, so in the example shown in Figure 5.6, the feedback will have information that both periods 3 and 4 after the scheduling optimization exceeded the capacity limit and required overtime, and, on the other hand, period 1 had a lot of free time. The second feedback are on the products that caused high setup costs in the previous iteration. The first method proposed, ILSPnR, gives freedom to the tactical level to decide where to move those products and ILSPRforces these problematic products to be produced in the best period found in the operational level. The results of each method are shown next, for the sequence in Figure 5.6. The solution of ILSPnR in Figure 5.7 shows that the capacity used in the periods have changed from the previous iteration, and also that product 19 and 20 were moved from periods 3 and 4, where they were causing cleanings, to period 2 since the production in these periods now had an associated setup cost. 48 Computational Experiment Figure 5.7: Solution structure after the second iteration of the ILSPnR. For the ILSPR, a new strategy is employed to address problematic products in a sequence. This strategy applies local search to find the best period to place a problematic product. For instance, Figure 5.8 shows that product 20 was creating setup cleanings in both periods 3 and 4 and the search algorithm concluded that the plan could be improved if that product is placed in period 1. Figure 5.8: Solution structure after the second iteration of the ILSPR. 5.2 Illustrative example of ILSP 49 5.2.3 Solution convergence Considering that the tactical level does not account for setup costs and times, its first solution can be considered as a lower bound for the integrated problem. With the feedbacks from the operational phase, new information related to production scheduling (capacity and setup costs) are added to the tactical level at the end of each iteration. The new information aim at evaluating the real costs of the "relaxed" tactical production planning and it is expected that at one point both tactical and operations solutions converge. The solution convergence of both ILSPnR and ILSPRfor the instance "month A" is depicted in Figures 5.9 and 5.10. Figure 5.9: ILSPnR convergence. Figure 5.10: ILSPRconvergence. Both models reach similar solutions, but the ILSPnR converges slower than the ILSPRsince it evaluates more possible solutions to avoid setup costs. 50 Computational Experiment 5.2.4 Final solution For the instance presented, the best solution found by the ILSPRmethod is depicted in Figure 5.11 Figure 5.11: Final solution obtained by the ILSPRfor instance Month A. 5.3 Classical instances For the first computational experiment, the instances presented in [11] were used. For all the instances, the parameters values are generated randomly using an uniform distribution. The parameters presented next are created in the same way for each instance, using this limits: •Demand: U[40-59] units •Holding costs: U[2-9] units •Setup times: U[5-10] units •Processing time: 1 time unit The setup costs are made proportional to setup times by using a cost factor θ. To define the machine capacity, two parameters Cut and CutVar were created. Cut establishes the target utilization over the entire planning horizon and CutVar the maximum deviation from the target capacity utilization in each period, this last one was defined as 0.5. It is ensured that the cumulative capacity utilization in any period does not exceed Cut to unsure problem feasibility. The instances are generated considering the following values for each parameter: •N=15 5.3 Classical instances 51 •T∈ {5,10,15} •Cut ∈ {0.6,0.8} •θ∈ {50,100} Combining this parameters, 12 different problem types were formulated with the following designation: N−T−Cut −θ. The solutions methods compared in this computational experiment are: •Full-space models: GLSP •Hierarchical method: HIER •Metaheuristic: GA •Iterative Methods: ILSPnR and ILSPR Table 5.3 presents the results of the computational experiment for each one of the methods, the production costs for the best solution found and the respective running time(s). The GLSP model used is a variant of the one presented in Section 3.2, where neither backlog or overtime is considered. For the capacity limit in the HIER method, the capacity reduction is calculated considering the average setup time AVG and the number of products N, so the new capacity is calculated as follows: capt−AV G −stime ×N. For all the methods, the running time was limited to 1 hour. 52 Computational Experiment Table 5.3: Results for the classic instances Instances ILSP-nR ILSP-R HIER GA GLSP Literature solutionCost Time Cost Time Cost Time Cost Time Cost Time Gap 15-5-0.6-50 15874 8 15687 16 15874 8 15399 83 14.605 3600 21% 17839 15-5-0.6-100 28192 77 28052 34 31872 13 27511 80 24586 3600 29% 29517 15-5-0.8-50 16024 28 15347 30 15926 11 17012 82 15.318 3600 19% 17814 15-5-0.8-100 27477 34 26734 54 29521 18 28823 80 24.210 3600 31% 30635 15-10-0.6-50 30534 199 31758 203 32625 53 33844 167 32.545 3600 41% 35270 15-10-0.6-100 60036 156 60739 156 63479 34 61993 148 52229 3600 52% 58268 15-10-0.8-50 30103 164 29968 244 30808 51 33510 143 32.002 3600 52% 35475 15-10-0.8-100 60856 97 54121 237 62657 21 61224 143 54.107 3600 63% 59197 15-15-0.6-50 48245 433 47420 670 48419 57 55427 202 53525 3600 60% 53061 15-15-0.6-100 83954 1096 86579 1604 93405 72 96774 210 76564 3600 58% 87509 15-15-0.8-50 46358 175 45299 559 46331 66 54881 217 47.946 3600 48% 53393 15-15-0.8-100 83644 703 79904 2275 91871 64 100486,1 212 79.625 3600 60% 88468 For the smaller instances, with less periods, the GLSP model reaches better solutions but requires higher computational times. However, once the instances get more extensive, with more products and periods, the solutions of the GLSP models get worst for the limited time, as demonstrated by the gap evolution throughout the instances presented in Figure 5.12. Figure 5.12: Gap evolution for the GLSP model. Comparing the solutions of ILSPRand ILSPnR, the predicted results are confirmed, with the first reaching better solutions but taking more computational time. This comparison is represented in Figure 5.13. 5.3 Classical instances 53 Figure 5.13: Performance comparison between ILSPRand ILSPnR. Figure 5.14 depicts the performance evolution across all instances for the ILSPR, GLSP, and the GA, using the deviation to the best solution found in all the methods for each one. The respective trend line is then shown in Figure 5.15. The results show that the iterative method solutions get better for the instances with more products and periods. Figure 5.14: Performance comparison for the GLSP, ILSPRand GA. 54 Computational Experiment Figure 5.15: Trendline comparison for comparison for the GLSP, ILSPRand GA. Figure 5.16 presents the average deviation to the best solution found for all the methods tested, and the average running time. Figure 5.16: Average results for all methods in the variable setup costs case 5.4 Animal feed instances For the second experimental test, instances from [26] and from a real company case were used. The instances represent problems of an animal feed company. In these problems, setup times are calculated based on cleaning necessity, which consists of two values: cleaning required (setup time = 1.67) and no cleaning required (setup time = 0). 5.4 Animal feed instances 55 5.4.1 Literature instances The instances considered in this section, consist of 26 product types, and a planning horizon of 4 weeks. with a less filled demand, where some products do not have requests in various macroperiods. The same methods were used in this experiment, apart from the full space MIP model GLSP. Instead, the results from the GLSP model proposed by [26] are presented. For this case, the capacity reduction for the HIER method is calculated as follows: the capacity time limit is decreased by 2 cleanings, capt −2×stime, in the Tactical Level. Table 5.4: Results of each method for the animal feed instances. Instances ILSP-nR ILSP-R HIER GA GLSP Result Time Result Time Result Time Result Time Result Time Month A 3521 10 3707 7 6276 25255 89 3519 360 Month B 17288 6 16870 17 18669 116875 79 16616 157 Figure 5.17 presents the average results and running time of each solution method for the animal feed instances. Figure 5.17: Average results for all methods considering the animal feed instances. The GLSP model is able to converge and find better solutions than the iterative method but it is exponentially slower. For these instances, both ILSPRand ILSPnR produced similar solutions, with an significant improvement to the HIER and GA methods. 5.4.2 Real animal feed company instance A real animal feed company was contacted in order to understand how this production planning problems are solved in the industry. The company is based in Brazil, and has a extensive variety 62 Literature animal-feed instance Table A.2: Processing time and holding inventory cost for each product Product Holding cost Processing time fam1 0,4 660 fam2 0,4 170 fam3 0,4 85,1 fam4 0,4 151,2 fam5 0,2 103,4 fam6 0,4 110 fam7 0,2 42,1 fam8 0,2 44,3 fam9 0,2 39,2 fam10 0,2 48,8 fam11 0,2 77,5 fam12 0,2 59,1 fam13 0,3 84,9 fam14 0,3 92,2 fam15 0,2 31,2 fam16 0,2 43,2 fam17 0,2 62,1 fam18 0,4 59,2 fam19 0,6 137,1 fam20 0,6 102,6 fam21 0,3 44,6 fam22 0,2 44,3 fam23 0,2 50,1 fam24 0,2 52,5 fam25 0,3 98,6 fam26 0,2 69,2 Literature animal-feed instance 63 Table A.3: Demand for each product Product Month A Month B t=1 t=2 t=3 t=4 t=1 t=2 t=3 t=4 fam1 0 0 0 0 0 0 0 0 fam2 2 3 9 1 1 6 7 5 fam3 9 16 9 25 12 41 20 16 fam4 0 0 1 0 0 0 0 0 fam5 25 15 2 5 6 6 12 10 fam6 0 0 0 0 0 0 0 0 fam7 15 16 12 11 43 44 52 51 fam8 29 29 32 52 32 32 48 32 fam9 40 32 32 52 32 40 48 32 fam10 58 57 65 79 56 31 57 58 fam11 2 6 6 5 0 0 0 0 fam12 2 1 1 0 4 4 0 0 fam13 0 1 1 1 0 0 0 0 fam14 12 15 20 19 8 8 9 6 fam15 1 1 0 0 0 0 0 0 fam16 1 0 0 0 0 0 0 0 fam17 10 3 3 3 11 11 4 0 fam18 0 0 0 0 0 0 0 0 fam19 0 1 1 4 0 0 0 0 fam20 4 0 4 1 1 1 2 1 fam21 35 38 46 47 56 38 73 36 fam22 0 0 0 0 0 0 0 0 fam23 0 0 0 0 0 0 0 0 fam24 0 0 0 0 0 0 0 0 fam25 0 0 0 0 0 0 0 0 fam26 0 0 0 0 0 0 0 0 64 Literature animal-feed instance Appendix B Real animal feed company instance 65 66 Real animal feed company instance Table B.1: Groups and attributes for each product Product Group Atributes 123456789 82289 11 0 0 3 0 0 0 0 0 9 82286 11 0 0 3 0 0 0 0 0 0 82266 11 0 0 3 0 0 0 0 0 9 75356 11 0 0 3 0 0 0 0 0 0 82163 11 0 0 3 0 0 0 0 0 0 71443 12 0 0 3 0 0 0 0 0 0 71447 12 0 0 3 0 0 0 0 0 0 71473 12 0 0 3 0 0 0 0 0 0 82263 12 0 0 3 0 0 0 0 0 0 81811MD 15 1 0 3 0 0 6 0 0 0 81812ME 15 1 0 3 0 0 6 0 0 0 81811ME 15 1 0 3 0 0 6 0 0 0 81561MD 15 1 0 3 0 0 6 0 0 0 82174 10 0 0 0 0 0 0 0 0 0 82175 10 0 0 0 0 0 0 0 0 0 81812LN 15 0 0 3 0 0 0 0 0 9 71449 10 0 0 3 0 0 0 0 0 9 71479 10 0 0 3 0 0 0 0 0 9 82275-35 10 0 0 3 0 0 0 0 0 0 82275-17.5 10 0 0 3 0 0 0 0 0 0 82286PN 10 0 0 3 0 0 0 0 0 0 82981 14 0 0 3 0 0 6 0 0 0 82243 11 0 0 3 0 0 0 0 0 0 81811NR 15 0 0 3 0 0 6 0 0 0 81611CA 15 0 0 3 0 0 0 0 0 0 81861CA 15 0 0 3 0 0 6 0 0 0 82115 10 0 0 3 0 0 0 0 0 0 75356VG 10 0 0 0 0 0 0 0 0 0 82243MD 11 1 0 3 0 0 0 0 0 0 82051 14 0 0 0 0 0 6 0 0 0 82163PR 11 0 0 3 0 0 0 0 0 0 82326 11 0 0 3 0 0 0 0 0 0 82329-15 11 0 0 3 0 0 0 0 0 9 82329-30 11 0 0 3 0 0 0 0 0 9 71457DZ 12 0 0 0 0 0 0 0 0 0 82391 8 0 0 0 0 0 0 0 0 0 81812 15 0 0 3 0 0 6 0 0 0 81561CA 15 0 0 3 0 0 6 0 0 0 81711CA 15 0 0 3 0 0 6 0 0 0 82135 10 0 0 3 0 0 0 0 0 0 82138 10 0 0 3 0 0 0 0 0 0 82147PL 10 0 0 0 0 0 0 0 0 0 82176 10 0 0 0 0 0 0 0 0 0 82326AL 11 0 0 3 0 0 0 0 0 0 82263MD 12 1 0 3 0 0 0 0 0 0 81711ME 15 1 0 3 0 0 6 0 0 0 82021SL 14 0 0 0 0 0 0 0 0 0 82263AL 11 0 0 3 0 0 0 0 0 0 81531CA 15 0 0 3 0 0 6 0 0 0 81861ME 15 1 0 3 0 0 6 0 0 0 81611ME 15 1 0 3 0 0 6 0 0 0 Real animal feed company instance 67 Table B.2: Demand for each product Product Day 1 Day 2 Day 3 Day 4 Day 5 82289 0 0 500 0 475 82286 0 0 1500 1500 800 82266 2700 1800 0 0 33025 75356 240 0 0 200 1700 82163 0 0 660 0 0 71443 0 600 300 0 150 71447 0 2250 0 150 0 71473 0 650 0 0 0 82263 0 0 600 0 6450 81811MD 0 0 600 0 1100 81812ME 0 0 600 0 2725 81811ME 0 0 0 0 14150 81561MD 0 0 300 0 3300 82174 0 0 0 0 1300 82175 0 0 0 0 700 81812LN 950 0 0 0 0 71449 0 1840 0 0 0 71479 0 0 0 0 1220 82275-35 0 0 0 0 3255 82275-17.5 0 612 875 0 808 82286PN 0 0 0 0 1950 82981 0 0 0 0 450 82243 0 0 0 0 200 81811NR 0 0 0 0 8150 81611CA 0 0 0 0 600 81861CA 0 0 0 0 3900 82115 0 0 0 0 2360 75356VG 0 0 0 0 1180 82243MD 0 0 0 0 880 82051 0 0 0 0 7340 82163PR 0 0 0 0 300 82326 0 0 0 0 760 82329-15 0 0 0 0 2010 82329-30 0 0 0 0 1260 71457DZ 0 0 0 0 1200 82391 0 0 0 0 750 81812 0 0 0 0 500 81561CA 0 0 0 0 600 81711CA 0 0 0 0 5275 82135 0 0 0 0 600 82138 0 0 0 0 900 82147PL 0 0 0 1540 0 82176 0 0 0 0 280 82289 0 0 0 0 15380 82326AL 0 0 0 0 3500 82263MD 0 0 0 0 4150 81711ME 0 0 0 0 925 82021SL 0 0 0 0 150 82263AL 0 0 0 0 1675 81531CA 0 0 0 0 600 68 Real animal feed company instance Figure B.1: Company’s production plan Real animal feed company instance 69 Figure B.2: ILSPnR solution 70 Real animal feed company instance References [1] Christos T Maravelias and Charles Sung. Integration of production planning and scheduling: Overview, challenges and opportunities. Computers & Chemical Engineering, 33(12):1919– 1930, 2009. [2] José Fernando Gonçalves and Mauricio GC Resende. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525, 2011. [3] Alistair Clark, Masoumeh Mahdieh, and Socorro Rangel. Production lot sizing and scheduling with non-triangular sequence-dependent setup times. International Journal of Production Research, 52(8):2490–2503, 2014. [4] António Aroso Menezes, Alistair Clark, and Bernardo Almada-Lobo. Capacitated lotsizing and scheduling with sequence-dependent, period-overlapping and non-triangular setups. Journal of Scheduling, 14(2):209–219, 2011. [5] Dileep R Sule. Production planning and industrial scheduling: examples, case studies and applications. CRC press, 2007. [6] Andreas Drexl and Alf Kimms. Lot sizing and scheduling—survey and extensions. European Journal of operational research, 99(2):221–235, 1997. [7] Karina Copil, Martin Wörbelauer, Herbert Meyr, and Horst Tempelmeier. Simultaneous lotsizing and scheduling problems: a classification and review of models. OR spectrum, 39(1):1–64, 2017. [8] Bernhard Fleischmann. The vehicle routing problem with multiple use of vehicles. Forschungsbericht Fachbereich Wirtschaftswissenschaften, Universität Hamburg, 1990. [9] Uday S Karmarkar and Linus Schrage. The deterministic dynamic product cycling problem. Operations Research, 33(2):326–345, 1985. [10] Andreas Drexl and Knut Haase. Proportional lotsizing and scheduling. International Journal of Production Economics, 40(1):73–87, 1995. [11] Luis Guimarães, Diego Klabjan, and Bernardo Almada-Lobo. Modeling lotsizing and scheduling problems with sequence dependent setups. European Journal of Operational Research, 239(3):644–662, 2014. [12] Bernhard Fleischmann and Herbert Meyr. The general lotsizing and scheduling problem. Operations-Research-Spektrum, 19(1):11–21, 1997. [13] Alistair R Clark and Simon J Clark. Rolling-horizon lot-sizing when set-up times are sequence-dependent. International Journal of Production Research, 38(10):2287–2307, 2000. 71