Keywords

1 Introduction

The field of study of quantitative methods offers a solution to those problems that emerge in industrial organisation and supply chain management by designing efficient mathematical models and algorithms to deal with decision-making procedures.

Research into planning areas has exponentially evolved since the 1950s, which was when operations research gave the first results promoted by computational complexity improvement and algorithms development to solve large-sized problems [1].

In this context, mathematical models described the problem and provided a closed series of solutions to obtain an optimal or approximate solution by means of which an approximation that moved closer to the true solution was accomplished. However, mathematical models’ nature makes modelling realistic highly complex systems difficult [2]. The continuous improvement of computational mathematical programming capabilities has facilitated their solution. Nevertheless, the running times and computational costs to obtain the solutions of very large problems involving many thousands of decision variables and restrictive constraints are still inefficient, and only limited-sized models have been solved to date. In this context, defining and applying heuristics and metaheuristics have improved solving large-scale planning problems with limited computation capacity and extended capabilities beyond merely solving mathematical programming models. Nowadays, the operations management research area offers the proposal of matheuristic as an interoperation of metaheuristics and mathematical programming techniques [3]. The innovative traits of designing matheuristic require of modellers more expertise. Model designers also have to deal with highly complex modelling and must solve planning problems in supply chains, which are characterised by a vast amount of input data and variables, and also by conflicting constraints and objectives appearing among supply chain partners [4]. All in all, through their solution by algorithms, mathematical models help decision-making by generating optimal, or near-optimal, solutions according to an established objective.

In order to confer the design of mathematical models and algorithms a higher level of familiarity, this paper proposes a framework to guide: (i) the formulation and notation of the models used to solve supply chain planning problems, including source, make and delivery, by employing the plans defined by [5, 6]; (ii) the identification of algorithms so they are more properly used to solve the previously formulated planning model. In any case, if users are interested in building models and algorithms, they have to define the type of plan to be solved and the horizon. Having characterised the plan, the framework herein proposed allows the generation of a set of decision variables, input data and objectives to formulate the defined planning problem.

This paper is arranged as follows: Sect. 2 offers a literature review of the mathematical modelling approach and works formerly proposed to facilitate model designers’ task of formulating mathematical models to support decision-making in the planning context. Section 3 contains the main contribution: a conceptual framework to formulate planning models and to identify solver algorithms. Section 4 presents the case study by applying the proposed conceptual framework to formulate a mathematical model by employing a real planning problem from a second-tier automotive supplier. Finally, Sect. 5 includes the conclusions.

2 Literature Review

According to Christou [1], planning processes are a focal point of enterprises and SC operations, and one of the most significant activities in industrial organisation. The operations management research area provides techniques and methods to model planning processes. This makes operations research a discipline that can deal with the application of advanced analytical and mathematical methods, theories and techniques to support the decision-making process in supply chains. Some examples of such are business analytics, computer science, decision analysis, forecasting, game theory, graph theory, industrial engineering, logistics, mathematical modelling, mathematical optimisation, probability and statistics, simulation, stochastic processes and supply chain management.

In the supply chain and industrial management area, operations research deals with determining the extreme values of planning processes objectives, e.g. maximisation or minimisation. When a researcher or an industrial expert formulates planning models, (s)he cannot always be able to exactly depict the organisation’s reality. Instead the person in charge of modelling, the problem should have to simplify it to make it solvable after selecting the solver algorithm.

According to Pidd [7], “a model is an explicit and external representation of part of the reality as it is seen by people who want to use the model in order to understand, change, manage and control that part of reality”. Models represent part of reality. However, reality is always more complex than any model, regardless of how sophisticated it might be. The model designer has to determine which aspects are relevant, and which are not, depending on the objective intended to be fulfilled. Experience shows that the main benefit from generating a model is to understand what the modeller acquires from reality’s behaviour. Quite often when developing a model, the designer becomes aware of information that (s)he has never paid attention to. Moreover, it is quite usual that, when a modeller formulates the model, real and contradictory data appear between different elements of reality. In his book “Quantitative Methods in Supply Chain Management: Models and Algorithms”, Christou[1] provides an example of what would occur when modelling a job-shop scheduling planning problem: “… almost all of the hard constraints we shall encounter in job-shop scheduling and due-date management, in reality are not that “hard” but are soft constraints in that often, violating one of them by a small slack does not violate any physical laws nor does it hurt company profitability in the long run”.

Bearing all this in mind, the reviewed literature clearly shows the complexity of formulating a model from scratch. Some authors have proposed methodologies and tools that efficiently deal with modelling planning processes or have provided a realistic formulation with knowledge-based tools that help non-expert users to build mathematical models in different planning areas. For this purpose, different papers in the literature have been identified. Hackman and Leachman[8] introduce a general framework that guides the management scientist’s formulation of deterministic models of production processes. The work of Krishnan [9] proposes a knowledge-based tool for building the algebraic schema of appropriate linear programming (LP) models for production, distribution and inventory (PDI) planning problems. Krishnan [10] studies the application of knowledge-based techniques to support various modelling process phases by integrating artificial intelligence (AI) techniques into decision support systems (DSS).

Shapiro[11] classifies models according to the effect their result has at the normative or descriptive level. Mathematical models are normative (in turn they can be classified as optimisation models and resolution models by heuristics). Descriptive models cover all the modelling techniques that do not involve defining mathematical structures that, in turn, define a desirable solution to be implemented. Before going further into the use and formulation of mathematical models, it is worth clarifying that the literature addresses the task of modelling planning problems from a perspective that is not only normative, but is also descriptive and conceptual. Indeed Hernández et al., [12] state that the conceptual model is helpful for gaining a better understanding of the system and, consequently, of detecting irregularities and suggesting improvements. Accordingly, Hernandez et al. [13] propose a conceptual model for the production and transport planning process in the automobile sector.

Although the authors of the present paper are aware of the relevance of other modelling approaches, the work herein conducted focuses on planning process modelling from a normative perspective. In an attempt to facilitate the representation of planning problems, Hashimoto and Kubo [14] collect a set of fundamental mathematical optimisation models (mixed integer linear programming, MILP), such as logistics network design, inventory, scheduling, lot-sizing, and vehicle routing models, to provide modellers with knowledge about basic mathematical formulations in the enterprise planning context. Therefore, the work of Hashimoto and Kubo [14] gives modellers a clue about the indices, input data, objectives, variables and output data that are widely used to formulate planning problems.

According to Mula et al., [15] the most widespread approach to model planning problems is MILP. Yet some characteristics are identified as limitations when solving planning problems through MILP, especially when considering enterprises’ real resolution environments. The main weaknesses are related to: (i) the combinatorial nature of real-world problems, in which the amount of decision variables exponentially increases when the number of plants, products or time periods increases; (ii) the large volume of data. Both cases generate an extensive use of computer memory, which results in an increased need for solution time [16]. It is here when solver algorithms and heuristics come into play to employ them as complementary techniques to solve mathematical programming models, mainly integer linear programming (LP). In line with this, Prasad et al.[16] propose a collection of algorithms to support solving mathematical models, formulated to support planning decision-making.

The literature review clearly indicates that a lot of progress has been made in proposing algorithms to support solving mathematically modelled planning problems (MILP). Nevertheless, the papers analysed in this section focus only on proposing approaches that support LP model formulation, and do not consider the solver mechanisms that solve them. To the best of our knowledge, the works that develop mechanisms to help to formulate mathematical models do not address the identification of appropriate solver algorithms.

In light of this, the present paper proposes a theoretical framework to support: (i) the formulation of mathematical models in the replenishment, production and delivery planning contexts; (ii) the identification of best fitting algorithms that solve real-world planning problems, regardless of the vast amount of data required for the problem to be solved in a real enterprise or supply chain. These algorithms enable an efficient computationally solution process during which a vast amount of data is used.

3 Conceptual Framework to Formulate Planning Models and to Identify Solver Algorithms

When addressing planning processes, it is necessary to develop optimisation and decision support tools that help to explore and analyse alternatives that can optimise economic performance and service levels [17]. The quantitative methods area studies ways to improve the quality, understanding and consequences of the decision-making process. Mathematical programming plays a very important role in this research area.

Planning models imply high complexity levels, especially if models are applied to an enterprise’s full-sized planning or a supply chain network. The combinatorial nature of real-world problems makes models exponentially complex in terms of input data, objectives, constraints and decision variables. Consequently, modellers must possess sufficient knowledge and background about the plans to be represented and solved. They must also have enough expertise to mathematically formulate the planning process by considering the soft and hard constraints, as well as a set of input data, required to meet the proposed objective.

So despite making efforts to simplify the planning problem, computationally solving mathematical models is still complex and time-consuming. Although significant progress has been made in the general solving mathematical programming area, current optimisation algorithms are still unsatisfactory for efficiently solving all general medium-sized integer linear programmes in reasonable times. Both complexity and inefficiency increase when solving full-sized planning problems, and this involves large datasets. Although adequate computational techniques have been developed for special problems, it is still necessary to propose algorithms to effectively solve the large-scale planning problems that appear in real-world enterprises to ensure that the optimal or near-optimal solutions are robust when different variables interact.

In order to bridge the gaps in the literature, a framework is proposed for dealing with the formulation of replenishment, production and delivery plans, and for proposing solution algorithms to efficiently deal with such complexity. This framework is used to: (i) identify the type of planning problem to be represented by the modeller, and the associated objective function; (ii) generate a range of input data to be potentially used for modelling the desired plan by considering the defined objective function; (iii) provide a MILP skeleton that consists in an open mathematical modelling language. This skeleton is characterised by being versatile enough to be applied to any studied plan object based on modellers’ requirements; (iv) select the algorithm that is most likely to solve MILP; (v) build a standard structure and implement the previously selected algorithm.

3.1 Methodology to Formulate Mathematical Models

Mathematical programming models spend extremely long computing times and, therefore, it is in modellers’ interest to build quickly formulated models. The proposed methodology follows a set of steps (Table 1) to formulate mathematical programming models, which are to be potentially applied to develop any planning model regardless of its nature. The objectives, input data [21] and output data are classified per plan type S [22], M [19], D [23], SM [22], MD [23], SMD [19] (see Table 2).

Table 1 Methodology steps to formulate a mathematical model in the planning context
Full size table
Table 2 Objectives, input data [21] and output data classified per plan type S [22], M [19], D [23], SM [22], MD [23], SMD [19]
Full size table

3.2 Identifying Solver Algorithms

The computational cost for solving large-scale industrial problems is still excessive today. Some general solution procedures are available, can be purchased on the market and are capable of solving increasingly complicated problems in appropriate times. In practice, however, it may be more cost-effective to design the solution procedure. Therefore, methods for designing problem-solving procedures are already modelled and are addressed in this section of the paper.

Although modellers can programme algorithms to solve mathematical planning problems, it is worth noting that occasionally using commercial software is more efficient than any individual implementation, such as CPLEX and Gurobi. Apart from optimisation software, it is necessary to have interface software to not only access and collect data, and to also structure and introduce a problem into a model-shaped package. Indeed, different packages provide high-level languages for mathematical programming, e.g. MPL modelling language from the Maximal Software, JUMP (Julia) or Pyomo (Python).

An exact algorithm ensures obtaining the best possible solution, the optimal one, by exploring the entire solution space. Nevertheless, the methods commonly used to solve problems are of a heuristic or metaheuristic type. Heuristics, metaheuristic and matheuristic algorithms are capable of generating approximate solutions for the problem and come as close as possible to the optimum one but may fail while making attempts. Being able to design a good heuristic, metaheuristic or matheuristic algorithm requires knowledge of the problem, which can lead to other improvements. This section of the proposed framework helps modellers to identify the most appropriate solver algorithm according to the identified plan type and plan subtype (steps 1 and 2 in the methodology). The algorithms proposed by the framework consists in a procedure that allows a solution for the selected specific planning problem to be found (see Table 3).

Table 3 Solver algorithms used per plan type S [22], M [19], D [23], SM [22], MD [23], SMD [19]
Full size table

3.3 Identifying Appropriate Algorithms

Algorithms consist of a systematic procedure that moves from one decision point to another to solve a category of problems. The Simplex algorithm is, for example, used to solve LP problems. The algorithms proposed in this part of the framework always meet one of three conditions: (i) there is no feasible solution; (ii) there is an optimal solution; (iii) the objective function is not limited to the feasible region. Moreover, the algorithms need: (i) procedure initialisation; (ii) a stopping criterion to denote when a solution is reached; (iii) an improvement method to move from an area of solution where there is no solution (relative minimum or maximum) to a better area to achieve the optimal or near-optimal solution. Algorithms can be classified according to the proximity to the optimum and the calculation mechanism [20]: (i) optimiser (AO), an algorithm that follows a systematic procedure that ensures achieving the optimum solution. Nevertheless, for some classes of problems, the time required to find the optimal solution is unacceptable. Algorithms that enable good solutions to be found are needed, including: (ii) heuristic (AH), an algorithm that employs an ad hoc procedure, but does not guarantee reaching the optimal solution, rather a near-optimal or sufficient one for immediate objectives; (iii) metaheuristic (AM), which is a higher-level procedure followed to select a heuristic (partial search algorithm) to obtain a sufficiently good solution. AM includes random searches that facilitate achieving several solutions (without ensuring the optimum) and needs a termination rule; (iv) matheuristic (AMT), which is a procedure that consists in the interoperation of metaheuristic and optimisation techniques [3]. Matheuristic can find near-optimal solutions (or sufficiently good ones) more quickly than some optimisation procedures. The reviewed papers indicate the use of each algorithm according to the plan type (Table 3).

4 Case Study

The case study is generated for a particular planning problem at the operational decision-making level, namely the scheduling plan of the second-tier supplier in the automotive supply chain as part of the “Zero-Defect Manufacturing Platform” (ZDMP) H2020 Project. The framework herein proposed is applied by the authors using realistic data. The plan type is determined by the Make classification of SCOR. The scheduling plan deals with the start and due dates of individual products, and also with machine assignments. It involves allocating finite resources to meet demand requirements by contemplating constraints like capacity, precedence and start and due dates, and identifying the quantity of products to be produced during a certain period [19].

In order to obtain a representative amount of parameters and variables to create the scheduling plan’s skeleton, a literature review is done in the scheduling context [21, 24–28]. The review process allowed us to identify a set of objectives, input data and output data, which are classified according to their nature (see Table 4): (i) capacity: referring to the amount of resources the enterprise owns for planning, e.g. number of workers, time, space, machines, monetary units, etc.; (ii) inventory: concerning the properties of the products in the warehouse; (iii) product: applied to the features related to raw materials and finished products; (iv) production: characterises the processes and methods used to transform raw materials, semifinished goods and subassemblies; (v) resources: seen as the productive factor required to perform an activity to obtain final products; (vi) sequence: contemplates the dependence and precedence of materials, products or resources; (vii) time: related to the unit of measurement used to categorise length of time; (viii) transport: considers the aspects related to moving products from one place to another. The main indices applied in the reviewed works are: set of products (finished goods, raw materials); set of finished goods; set of periods.

Table 4 Scheduling plan: objectives, input data and output data
Full size table

The proposed framework also provides a set of common constrains that characterise the scheduling plan, including: (i) inventory balance equations for finished goods and raw materials; (ii) inventory capacity limitation; (iii) production capacity limits; (iv) production sequence determination; (v) the product for which the machine is setup; (vi) only one product can be setup at the end of each period; (vii) elimination of subtours when more than one product is produced during a single period. The same product cannot be produced as both first and last during a period; finally (viii) the binary and non-negativity properties for the decision variables are to be included.

The framework shows the model designer all the objectives, input data, output data and constraints to select the parameters, variables and restrictions that apply to the enterprise’s scheduling plan. According to the selected elements, the framework generates the mathematical model skeleton (MILP). Finally, the modeller reviews the proposed MILP and makes final adjustments.

The framework identifies the most appropriate solver algorithm to solve the end version of MILP. The application of a solver algorithm such as a heuristic algorithm allows large-sized problems to be solved, which involves a vast amount of data, and the complete enterprise scheduling problem is considered. This means scheduling all the products manufactured by the enterprise using each involved resource and a real time horizon.

5 Conclusions

This paper identifies the gap identified in the literature about the automatic formulation of mathematical models and solver algorithms to solve large-sized planning problems. As far as we know, the papers that propose guidelines and tools to mathematically formulate planning problems are limited to model formulation, and do not take into account enterprises’ real needs, e.g. formulating models applicable to solve large-sized enterprise plans. The main contribution of this paper led to the proposal of a complete framework, which allows planning processes to be modelled by considering not only an intra-enterprise perspective that involves replenishment, production and delivery plans, but also collaborative scenarios in which supply chain plans are jointly solved. The framework also focuses on identifying solver algorithms, which can manage large amounts of data and allow planning models to be solved in a computationally efficient manner.

The advantages of using mathematical models derive from the clear conceptualisation of the industrial planning process to be modelled. However, the modeller must know that there are times when the mathematical formulation is limited by having to generate artificial constraints to model restrictions that can be easily modelled with a heuristic algorithm. Moreover if the problem’s behaviour is nonlinear, applying a LP model can only model an approximation to reality, and more artificial restrictions should be created. The identified limitations enabled the authors to identify future research lines that lead to the framework being extended so as to not force users having to face developing a mathematical model. In this way, the modeller can directly generate a heuristic or metaheuristic to model the planning problem and solve it. A second future research line is about examining in more depth the part of the framework employed to identify and formulate solver algorithms. Here the first action is to focus on generating the solver algorithm. The second action goes further and permits the authors to propose general simple metaheuristic procedures to solve large-sized planning problems in short times with fewer computational resources.