# Matheuristic Algorithms for Production Planning in Manufacturing Enterprises

Eduardo Guzman, Beatriz Andrés, Raúl Poler

► To cite this version:

Eduardo Guzman, Beatriz Andrés, Raúl Poler. Matheuristic Algorithms for Production Planning in Manufacturing Enterprises. 12th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Jul 2021, Costa de Caparica, Portugal. pp.115-122, 10.1007/978-3-030-78288-7_11. hal-03685950

HAL Id: hal-03685950

https://inria.hal.science/hal-03685950

Submitted on 2 Jun 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Matheuristic Algorithms for Production Planning in Manufacturing Enterprises

Eduardo Guzman, Beatriz Andres and Raul Poler

Research Centre on Production Management and Engineering (CIGIP) Universitat Politècnica de València (UPV), Calle Alarcón, 03801 Alcoy, Alicante, Spain

**Abstract.** Production systems are moving towards new levels of smart manufacturing, which means that production processes become more autonomous, sustainable, and agile. Additionally, the increasing complexity and variety of individualized products makes manufacturing a challenge, since it must be produced by consuming the least number of resources, generating profitability. In mathematical perspective, most production planning problems, such as real-world scheduling and sequencing problems, are classified as NP-Hard problems, and there is most likely no polynomial-time algorithm for these kinds of problems. In addition, advances in information and communication technologies (ICT) are increasing, leading to an already existing trend towards real-time scheduling. In this context, the aim of this research is to develop matheuristic algorithms for the optimization of production planning in the supply chain. The development of matheuristic algorithms allows finding efficient solutions, achieving shorter computational times, providing companies with smart manufacturing skills to quickly respond to the market needs.

**Keywords:** scheduling, matheuristics, supply chain, production planning

## 1 Introduction

Nowadays, the rapid economic growth of markets, the competitive pressure and the increasingly turbulent business environments are increasingly forcing companies, particularly small and medium-sized enterprises (SMEs), to innovate in their industrial manufacturing systems. SMEs currently represent 99.8% of companies in the non-financial business sector of the European Union (EU-28) [1]. The market in which these companies operate today is intensely dynamic, which makes effective supply chain (SC) management central to improving organizational performance.

Today, there is great interest from researchers to improve the performance of companies and SCs in general. An example of the improvement in performance and innovation is what is present in the automotive industry. However, this and other industries have had to respond and adapt to the continuous changes of the organizational environment, with the aim of providing high quality and personalized products and services. Consequently, SCs are not static since they must respond to continuous changes, adapting their techniques of control, and coordinating and managing the change in the way operation and configuration of companies. Moreover,
enterprises have to manage their evolution towards participating in collaborative networks [2].

In order to deal with these dynamic environments, advanced tools and techniques have to be designed to provide SMEs affordable tools, in terms of cost, usability, and computationally efficiency, enhancing enterprises’ competitiveness in current global changing markets. The techniques to be provided can be based on different approaches, for example, mathematical programming and analytical techniques. However, most real-world planning problems are too complex to be mathematically modelled. At the same time, its resolution, with commercial solvers, is not computationally efficient when the planning problems to be solved consider many variables and a large amount of data.

Combinatorial optimization problems are present in a large number of services related to life improvement, such as public transport, delivery services, shift scheduling in hospital centers [3], etc. and in manufacturing, such as production scheduling, operations sequencing [4], etc. These problems are usually presented as NP-Hard, which means that exact techniques and some algorithms cannot solve them in an effective calculation time, when the problem has become too large.

Therefore, it is necessary to focus research efforts on the study and generation of techniques and tools that improve the way in which available resources are used, both in the SC and in the services used in the society, in general. In accordance with this reality, the search for solutions to this type of planning problems continues to be a relevant research topic. Finding better solutions in quality and time has a significant value since intractable production planning problems with a large amount of data and variables would have a solution in an effective computational time. Therefore, the following research question is addressed, in this paper, are:

**RQ1.** In which kind of scenarios are matheuristic algorithms faster or more efficient than linear programming models or metaheuristic algorithms?

**RQ2.** How matheuristic algorithms contribute to applied artificial intelligence systems?

**RQ3.** How matheuristic algorithms solve complex production scheduling problems?

To provide a response to the research questions posed, the original contribution proposed in this research focuses on the development of matheuristic algorithms to solve manufacturing planning problems both individually (enterprise level) and globally (SC level). Accordingly, the document is structured as follows. Section 2 examines the utility of matheuristic in applied artificial intelligence systems. Section 3 proposes brief state of the art of the matheuristic algorithms. Section 4 describes the contribution and innovation of this research. Finally, section 5 covers the conclusions of the developed work and future lines of research.

## 2 Matheuristics for Applied Artificial Intelligence Systems

Manufacturing systems are becoming increasingly dynamic [5], due to the new requirements demanded by the industry. Over time, classical approaches of decision-making assistance, such as Enterprise Resource Planning (ERP) and Decision Support System (DSS), have been changing or adapting to new technologies, such as machine
learning, data mining and big data [6]. Currently, manufacturing processes seek to adapt to novel approaches, such as industry 4.0 or the internet of things.

Regarding classic production scheduling approaches that analyze the operation time of the production sequences, the configuration times and even the maintenance activities [7], evolve towards intelligent scheduling approaches that seek to respond dynamically to the environment. In this regard, smart scheduling uses intelligent algorithms to process and analyze information from sensors and wireless communication devices of the machines. The collection of real-time information, not only allows to compute scheduling plans using optimization techniques but also to recompute the production scheduling, attending to the changes that could occur in the production environment [8]. This means that the initial production schedule configuration is modified due to events that may unexpectedly appear in the production process, such as machine malfunctions, the reception of new orders or modifications in the execution priorities of the work to be carried out. [9]. Production scheduling problems are characterized by the large amount of data associated with the problem and in a collaborative context, the problem becomes even more difficult when a production plan has to be rescheduled since in collaborative planning, both customers and suppliers must continuously share information to plan their activities and this data exchange must be relevant and timely for all members of the supply chain involved [10]. Currently, Artificial Intelligence (AI) systems support companies in performing efficient data analysis through predictive analytics which is becoming an important part of companies as they seek to predict future events that may affect the production process.

In this context, the effectiveness of the different types of metaheuristic algorithms to solve these types of problems is determined by the ability to adapt them to the problem and its unique characteristics while avoiding falling into the local optimum. Currently, the approaches to artificial intelligence and machine learning, which is a subfield of AI, have gained popularity in recent years, and techniques such as Learnheuristics [11] (combination of metaheuristics and machine learning) are showing their efficiency in this field [12]. In order to reschedule a plan and find optimal or near-optimal solutions, the processing time required by mathematical models or some metaheuristics to solve this type of problems may be inefficient and require many hours or possibly days. In this sense, combining machine learning with matheuristic algorithms can be helpful since mathematical algorithms present better performance and computationally more efficient solutions by taking advantage of the experience of commercial or free solvers and the advantages of heuristic or metaheuristic algorithms [13] [14].

## 3 Literature Review

There is a wide variety of papers describing different models and algorithms to solve procurement, production, distribution problems. Nevertheless, many of these techniques correspond to mathematical models, heuristic and metaheuristic algorithms [15]. The application of these techniques depends on the application area, i.e. SC planning under uncertainty [16], closed loop SC [17], SC sustainable management [18], or green SC management [19]. These studies reviewed the models and algorithms employed to solve optimization problems in their specific field.
In these reviews, very few mention the use of combined or hybrid algorithms, such as matheuristic algorithms. These algorithms are performed by "*the interoperation of metaheuristics and mathematical programming techniques*" [20]. According to Ball [21] and Talbi [22], combinations or hybridizations of matheuristics can be classified into three approaches 1) decomposition approaches, the problem is decomposed into subproblems to be solved optimally; 2) improvement heuristics or metaheuristics, the mathematical programming model will be used to enhance an initial solution obtained by some heuristic or metaheuristic method; and 3) approaches employing the mathematical programming model to provide approximate solutions, in that a relaxation of the problem towards optimality is solved. The method presented in our study, consists of a combination of a genetic algorithm and linear programming models, fall into categories 2) and 3) of this classification.

Cabrera-Guerrero et al. [23] demonstrate that the combination of techniques, or hybridization, can be advantageous to solve complex problems. Verbiest et al. [24] uses a combination of an iterated local search algorithm (metaheuristic) with a Mixed Integer Linear Programming (MILP) model, to optimize production lines, design of installed line and allocation of products. This study compares the matheuristic approach with an exact method (MILP), verifying that the matheuristic offers efficient solutions, in a shorter calculation time. Worth to highlight is the work of Ta et al. [25], in which the solution given by a genetic algorithm is compared with the solution obtained through the implementation of a matheuristic algorithm, in the context of scheduling problem, concluding that the matheuristic algorithm behaves more efficiently than the genetic algorithm. According to the results of the works analyzed, it can be concluded that matheuristic techniques are suitable for solving problems in realistic instances and allow obtaining good results in acceptable computing times.

# 4 Research Contribution and Innovation

In general, both in the literature and in industry, mathematical programming models are generally one of the standard approaches to solve scheduling problems. In this study, we present the resolution of the job shop scheduling problem (JSP) with a matheuristic algorithm that hybridizes a Mixed Integer Linear Programming (MILP) model and a Genetic Algorithm (GA). MILP formulations for JSP exist since the 1960s, since the significant improvement of MILP solvers in the last years, it is relevant to perform a comparison of standard JSP models using modern optimization software such as GUROBI and a matheuristic algorithm, with this comparison we will answer the research questions RQ1 and RQ3.

The selected MILP is a disjunctive model based on Ku and Beck [26]. The job shop scheduling problem is given by a *J* finite set of *n* jobs or parts and a finite set *M* of *m* machines. For each job *j* ∈ *J*, the list (*σ*<sub>1</sub><sup>j</sup>, ..., *σ*<sub>*h*</sub><sup>j</sup>, ..., *σ*<sub>*m*</sub><sup>j</sup>) of machines with the processing order of job *j* is provided. *σ*<sub>*h*</sub><sup>j</sup> is the *h*-th operation of job *j*. *p*<sub>*ij*</sub> represents the processing time of job *j* on machine *i*. Only one job at a time can be processed by each machine, and a job, once it starts on a given machine, must finish processing on such machine without interruption.
$$ \min C_{max} \tag{1} $$

$$ \text{s.t.} \quad x_{ij} \ge 0, \tag{2} $$

$$ x_{\sigma_{h,j}^i} \ge x_{\sigma_{h-1,j}^i} + p_{\sigma_{h-1,j}^i}, \quad \forall j \in J, i \in M \tag{3} $$

$$ x_{ij} \ge x_{ik} + p_{ik} - V \cdot z_{ijk}, \quad \forall j, k \in J, j < k, i \in M \tag{4} $$

$$ x_{ik} \ge x_{ij} + p_{ij} - V \cdot (1 - z_{ijk}), \quad \forall j, k \in J, j < k, i \in M \tag{5} $$

$$ C_{max} \ge x_{\sigma_{m,j}^i} + p_{\sigma_{m-1,j}^i}, \quad \forall j \in J \tag{6} $$

$$ z_{ijk} \in \{0,1\}, \quad \forall j, k \in J, i \in M \tag{7} $$

$$ z_{ij} \in \mathbb{Z}, \quad \forall j, k \in J \tag{8} $$

The aim to find a schedule of jobs on machines that minimizes the makespan [26]. Constraint (2) guarantees that each job's start time is equal to or greater than 0. Constraint (3) assures that each operation of a job is carried out in the required order. Disjunctive constraints (4) and (5) establish there cannot be two jobs scheduled on one machine at the same time. It is necessary to assign $V$ a value large enough to guarantee the correctness of (4) and (5), $V = \sum_{j \in J} \sum_{i \in M} p_{ij}$ considering that the completion time of any operation must not be greater than the sum of the processing times of all operations. Constraint (6) guarantees that the makespan is the longest completion time of the last operation of all jobs as a minimum [26].

The aim of this section is to provide a matheuristic approach to solve the job shop scheduling problem quickly and efficiently, in particular for large-size problems. To this extent, we design a matheuristic approach applying a linear programming model within the metaheuristic procedure (Genetic algorithm). The quality of the solutions is improved by integrating dispatch rules with the GA to generate an efficient initial population, including: First In First Out- FIFO; Last In First Out - LIFO; Shortest Remaining Operation Time – SROT; Longest Remaining Operation Time – LRPT; Shortest Operation Time- SOT; Less Remaining Operations – LRO; Most Remaining Operations – MRO; Least Set-Up – LSU; Longest Operation Time – LOT; Work In Next Queue – WINQ; Due Date – DD; Static Slack -SS; Dynamic Slack -DS; Relative Dynamic Slack -RDS; SS/ Remaining Operation Time – SS/TPR; DS/ Remaining Operation Time – DS/TPR; SS / Remaining Operations – SS/RO; DS / Remaining Operations – DS/RO.

GA generates an initial population (set of chromosomes) at 50% randomly and the rest of the population is generated through dispatching rules, due to the randomness of chromosomes it is difficult to obtain an appropriate fitness value, so dispatching rules are used to improve GA speed.

All chromosomes in the population are evaluated in each generation (fitness) using the relaxed disjunctive mathematical model. A repair strategy is used to avoid infeasible chromosomes. This strategy corrects the sequence of an individual in the population if it is non-viable (non-viability arises from non-compliance with precedence constraints, that is, when a job's predecessor is processed after its successor job) then calculates a new sequence [27]. Fitness values are considered in mating to form new offspring. Therefore, selecting chromosomes according to the most suitable fitness values allows the matheuristic to obtain better solutions. The roulette wheel method is used as a selection operator to select an individual from the population. The mating is produced by two parent chromosomes to obtain a child chromosome using the Partially Mapped
Crossover Operator, then mutating the daughter chromosome using Swap Mutation Operator. The flow chart of matheuristic algorithm is illustrated in Fig. 1.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Flow chart of matheuristic algorithm.</figcaption></figure>

For the assessment of the performance of the proposed matheuristic, we first evaluate
the behavior of the MILP for job shop scheduling problem, for this, we use a Taillard
instance (ta02) [28] consisting of 15 jobs and 15 machines, the JSP is NP-hard for n ≥
3 and m ≥ 2 [26]. To solve this instance, we use the GUROBI solver, the MILP obtains
an optimal solution at 7057.71 seconds and a makespan of 1244. Computational tests
performed were run on an Intel (R) Core (TM) I5-8500 CPU with 3.00 GHz and 8 GB
RAM.

To compare matheuristic efficiency to the MILP, we establish a stopping parameter
in the matheuristic of 60 seconds. The proposed matheuristic obtains a makespan of
1399.0, this means that the matheuristic obtains a GAP of 12.45%, for this reason we
can conclude that the matheuristic is efficient, for this type of problems obtaining good
solutions in relatively shorter calculation time. Therefore, the future lines of research
are to improve the genetic algorithm since the genetic operators used are the standard
ones and operators designed for the concrete problem would obtain better performance,
as well as to try other metaheuristics and new instances with different characteristics of
processing times.

# 5 Conclusions and Further Work

This study analyzes the evolution suffered in the manufacturing research area, due to
the new requirements associated to the changing and global markets. New production
paradigms offer great opportunities and challenges, as they support the transformation
of technology and market conditions. The optimization of manufacturing processes of
a company will be determined by the appropriateness of tools and the size of the data
needed to model and solve a planning problem. This research focuses on the
development of tools to generate matheuristic algorithms applicable to solve
manufacturing planning problems, both at the enterprise and SC levels, achieving the
integral optimization of manufacturing assets.

The proposed tools will be based on a methodology that describes the best
combination of metaheuristic algorithms and exact methods, depending on (i) the type
of optimization problem; (ii) the type of input and output data; and (iii) the amount of
data that the company or the supply chain handles.
Future lines of research include the design of efficient matheuristics, to reduce the calculation time when solving real-sized enterprise and SC problems, generating near-optimal or good solutions. The matheuristics should be as general as possible to be applied in different industries and sectors, without losing the accurateness of the planning problem modelled and the efficiency on the computation time.

**Acknowledgments.** Funding for this work has been provided by the Conselleria de Educación, Investigación, Cultura y Deporte - Generalitat Valenciana for hiring predoctoral research staff with Grant (ACIF/2018/170) and European Social Fund with Grant Operational Program of FSE 2014-2020, the Valencian Community.

## References

1. European Commission, "Annual Report on European SMEs 2016/2017: Focus on self employment," 2017. doi: 10.2873/742338.

2. B. L. MacCarthy, C. Blome, J. Olhager, J. S. Srai, and X. Zhao, "Supply chain evolution – theory, concepts and science," *Int. J. Oper. Prod. Manag.*, vol. 36, no. 12, pp. 1696–1718, 2016, doi: 10.1108/IJOPM-02-2016-0080.

3. E. Guzmán Ortiz, B. Andres, F. Fraile, R. Poler, and Á. Ortiz Bas, "Fleet management system for mobile robots in healthcare environments," *J. Ind. Eng. Manag.*, vol. 14, no. 1, p. 55, 2021, doi: 10.3926/jiem.3284.

4. B. Andres, E. Guzman, and R. Poler, "A Novel MILP Model for the Production, Lot Sizing, and Scheduling of Automotive Plastic Components on Parallel Flexible Injection Machines with Setup Common Operators," *Complexity*, vol. 2021, p. 16, 2021, doi: https://doi.org/10.1155/2021/6667516.

5. A. Dolgui, D. Ivanov, S. P. Sethi, and B. Sokolov, "Scheduling in production, supply chain and Industry 4.0 systems by optimal control: fundamentals, state-of-the-art and applications," *Int. J. Prod. Res.*, vol. 57, no. 2, pp. 411–432, 2019, doi: 10.1080/00207543.2018.1442948.

6. J. Koźlak, B. Sniezynski, D. Wilk-Kołodziejczyk, A. Leśniak, and K. Jaśkowiec, "Multi-agent Environment for Decision-Support in Production Systems Using Machine Learning Methods," in *Computational Science -- ICCS 2019*, 2019, pp. 517–529.

7. D. Alemão, A. D. Rocha, and J. Barata, "Production Scheduling Requirements to Smart Manufacturing BT - Technological Innovation for Industry and Service Systems," 2019, pp. 227–237.

8. D. A. Rossit, F. Tohmé, and M. Frutos, "Industry 4.0: Smart Scheduling," *Int. J. Prod. Res.*, vol. 57, no. 12, pp. 3802–3813, 2019, doi: 10.1080/00207543.2018.1504248.

9. D. Rossit and F. Tohmé, "Scheduling research contributions to Smart manufacturing," *Manuf. Lett.*, vol. 15, pp. 111–114, 2018, doi: 10.1016/j.mfglet.2017.12.005.

10. B. Andres and R. Poler, "Models, guidelines and tools for the integration of collaborative processes in non-hierarchical manufacturing networks: a review," *Int. J. Comput. Integr. Manuf.*, vol. 2, no. 29, pp. 166–201, 2016, doi: 10.1080/0951192X.2014.1003148.

11. L. Calvet, J. De Armas, D. Masip, and A. A. Juan, "Learnheuristics: Hybridizing metaheuristics with machine learning for optimization with dynamic inputs," *Open Math.*, vol. 15, no. 1, pp. 261–280, 2017, doi: 10.1515/math-2017-0029.

12. W. T. de Sousa Junior, J. A. B. Montevechi, R. de C. Miranda, M. L. M. de Oliveira, and A. T. Campos, "Shop floor simulation optimization using machine learning to improve parallel metaheuristics," *Expert Syst. Appl.*, vol. 150, 2020, doi: 10.1016/j.eswa.2020.113272.

13. C. F. Motta Toledo, L. De Oliveira, R. De Freitas Pereira, P. M. França, and R. Morabito, "A genetic algorithm/mathematical programming approach to solve a two-level soft drink
production problem,” *Comput. Oper. Res.*, vol. 48, pp. 40–52, 2014, doi: 10.1016/j.cor.2014.02.012.

14. Y. Bin Woo and B. S. Kim, “Matheuristic approaches for parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities,” *Comput. Oper. Res.*, vol. 95, pp. 97–112, 2018, doi: 10.1016/j.cor.2018.02.017.

15. J. Mula, D. Peidro, M. Díaz-Madroñero, and E. Vicens, “Mathematical programming models for supply chain production and transport planning,” *Eur. J. Oper. Res.*, vol. 204, no. 3, pp. 377–390, 2010, doi: 10.1016/j.ejor.2009.09.008.

16. D. Peidro, J. Mula, R. Poler, and F. C. Lario, “Quantitative models for supply chain planning under uncertainty,” *Int. J. Adv. Manuf. Technol.*, vol. 43, no. 3–4, pp. 400–420, 2009, doi: 10.1007/s00170-008-1715-y.

17. D. Stindt and R. Sahamie, “Review of research on closed loop supply chain management in the process industry,” *Flex. Serv. Manuf. J.*, vol. 26, no. 1–2, pp. 268–293, 2014, doi: 10.1007/s10696-012-9137-4.

18. M. Brandenburg, K. Govindan, J. Sarkis, and S. Seuring, “Quantitative models for sustainable supply chain management: Developments and directions,” *Eur. J. Oper. Res.*, vol. 233, no. 2, pp. 299–312, 2014, doi: 10.1016/j.ejor.2013.09.032.

19. R. K. Malviya and R. Kant, “Green supply chain management (GSCM): a structured literature review and research implications,” *Benchmarking An Int. J.*, vol. 22, no. 7, pp. 1360–1394, Oct. 2015, doi: 10.1108/BIJ-01-2014-0001.

20. M. A. Boschetti, V. Maniezzo, M. Roffilli, and A. Bolufé Röhler, “Matheuristics: Optimization, simulation and control,” *Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics)*, vol. 5818 LNCS, pp. 171–177, 2009, doi: 10.1007/978-3-642-04918-7 13.

21. M. O. Ball, “Heuristics based on mathematical programming,” *Surv. Oper. Res. Manag. Sci.*, vol. 16, no. 1, pp. 21–38, 2011, doi: 10.1016/j.sorms.2010.07.001.

22. E.-G. Talbi, “A Unified Taxonomy of Hybrid Metaheuristics with Mathematical Programming, Constraint Programming and Machine Learning,” in *Hybrid Metaheuristics*, E.-G. Talbi, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 3–76.

23. G. Cabrera-Guerrero, C. Lagos, C. Castañeda, F. Johnson, F. Paredes, and E. Cabrera, “Parameter tuning for local-search-based matheuristic methods,” *Complexity*, vol. 2017, 2017, doi: 10.1155/2017/1702506.

24. F. Verbiest, T. Cornelissens, and J. Springael, “A matheuristic approach for the design of multiproduct batch plants with parallel production lines,” *Eur. J. Oper. Res.*, vol. 273, pp. 933–947, 2018, doi: 10.1016/j.ejor.2018.09.012.

25. Q. C. Ta, J. C. Billaut, and J. L. Bouquard, “Matheuristic algorithms for minimizing total tardiness in the m-machine flow-shop scheduling problem,” *J. Intell. Manuf.*, vol. 29, no. 3, pp. 617–628, 2018, doi: 10.1007/s10845-015-1046-4.

26. W. Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis,” *Comput. Oper. Res.*, vol. 73, pp. 165–173, 2016, doi: 10.1016/j.cor.2016.04.006.

27. N. Kundakci and O. Kulak, “Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem,” *Comput. Ind. Eng.*, vol. 96, pp. 31–51, 2016, doi: 10.1016/j.cie.2016.03.011.

28. E. Taillard, “Benchmarks for basic scheduling problems,” *Eur. J. Oper. Res.*, vol. 64, no. 2, pp. 278–285, 1993, doi: https://doi.org/10.1016/0377-2217(93)90182-M.