Optimisation Methods in Sustainable Manufacturing

In a general multi-criteria linear optimisation problem, one is given a set of \( k \) cost vectors \( c_{1} , \ldots ,c_{k} \in {\mathbb{R}}^{n} \) and seeks to minimize all linear cost functions \( c_{i} \cdot x = \sum\nolimits_{j = 1}^{n} {c_{{i_{j} }} x_{j} } \), for \( i = 1, \ldots ,k, \) simultaneously over all \( n \)-dimensional vectors \( x = (x_{1} , \ldots ,x_{n} ) \) subject to a set of linear inequality and integer constraints. In particular, let \( M \) be some finite index set and suppose that for every \( i \in M \), we are given an \( n \)-dimensional vector \( a_{i} \) and a scalar \( b_{i} \). Let \( N_{1} \), \( N_{2} \) and \( N_{3} \) be subsets of \( \{ 1, \ldots ,n\} \) that indicate which variables \( x_{j} \) are constrained to be non-negative, binary or integer, respectively. We then consider the problem

The variables \( x_{1} , \ldots ,x_{n} \) are called decision variables and a vector \( x \) satisfying all of the constraints is called a feasible solution. The set of all feasible solutions is called feasible set and will be denoted by \( {\mathcal{X}} \). The image \( y = (c_{1} \cdot x, \ldots ,c_{k} \cdot x) \) of a feasible solution \( x \) is called a feasible point and the set of all feasible points is called objective set and will be denoted by \( {\mathcal{Y}} \). If \( N_{1} \) coincides with \( \{ 1, \ldots ,n\} \) (implying \( N_{2} = N_{3} = \emptyset \)), then (1) is considered a linear programming problem. If \( N_{2} = \{ 1, \ldots ,n\} \) or \( N_{3} = \{ 1, \ldots ,n\} \), then we refer to (1) as a binary or integer programming problem, respectively. In case of \( \emptyset { \subsetneq }N_{1} { \subsetneq }\{ 1, \ldots ,n\} \), (1) is considered a mixed-integer programming problem. The earliest investigations of multicriteria mathematical optimisation go back to the 1950s when the simplex method coined by Dantzig opened up a wide range of applications and prepared the ground for the huge success of linear programming (Dantzig 1963). If \( k = 1 \), then we refer to (1) as a single-objective problem and the notion of optimality is unambiguous. For a multi-criteria optimisation problem (with number of objectives \( k \ge 2 \)) we cannot expect to find a solution that optimizes all objectives simultaneously leading to several possible notions of optimality in the multi-criteria case (Ehrgott 2005). A widely accepted (and in the following considered) one is the notion of efficiency. A solution \( x^{*} \, \in \,{\mathcal{X}} \) is considered efficient if there is no other solution \( x \in {\mathcal{X}} \) that achieves objective values at least as good with a strictly better value in at least one objective, i.e., there is no \( x \in {\mathcal{X}} \) with \( c_{i} \cdot x \le c_{i} \cdot x^{*} \) for \( i = 1, \ldots ,n \) and \( c_{i} \cdot x < c_{i} \cdot x^{*} \) for at least one \( i \in \{ 1, \ldots ,n\} \). The image of an efficient solution is called non-dominated. The challenge for a multi-criteria optimisation problem is then to compute all different non-dominated points (Figs. 1 and 2).

Production problems, scheduling problems and similar decision problems are a fruitful domain for (mixed) integer programming. Binary variables might represent on-off decisions and linear or integer variables, respectively, might represent production quantities. In the following we will shortly present how multi-criteria integer programming could be used to model a scheduling problem that accounts for production costs, electricity consumption and worker satisfaction. Lets \( [M] = \{ 1, \ldots ,M\} \) be a finite set representing a set of different machines and let \( [J] = \{ 1, \ldots ,J\} \) be a finite set representing a set of jobs. We will consider a time horizon for the entire production process and let \( s \) and \( e \) be the start and end time of it. Introduce variables \( x_{jmt} \in \{ 0,1\} \) where \( j \in [J] \), \( m \in [M] \) and \( t \in \{ s, \ldots ,e\} \). We set \( x_{jmt} = 1 \) if and only if starting time of job \( j \) on machine \( m \) is set to \( t \). In order to model the constraint that every job needs to run on every machine before end time \( e \), let \( dur(m) \) the duration on machine \( m \), i.e., the time that a job spends on machine \( m \). Then,models the above fulfilment constraint. Furthermore, the constraint that job \( j \) is only allowed to run on machine \( m + 1 \) if it is finished on machine \( m \) can be modelled via

Furthermore, it is very reasonable to assume that a new job can only be started on machine \( m \) if the previous job on machine \( m \) was finished. This constraint could be modelled via

For the single-objective case there are several commercial solvers and software packages (CPLEX 2016; Xpress 2016; Gurobi 2016) and non-commercial ones (Achterberg 2009). One could have expected that the exponential growth in computing power and the even larger algorithmic speed-ups in mixed integer programming during the last decade (Bixby 2002) would automatically lead to multi-criteria extensions. But the situation is contrary: none of the available commercial solvers supports multi-criteria problems and there are only a few, recently developed non-commercial solvers available: BENSOLVE (Löhne and Weiing 2014) and inner (Csirmaz 2016) handle multi-criteria linear programming problems, SYMPHONY (Ladanyi et al. 2016) supports bi-criteria mixed integer problems and PolySCIP (Schenker et al. 2016) supports multi-criteria linear and integer problems.

PolySCIP reads problems of the above form (1) via its MOP file format which is based on the widely used MPS file format (MPS-Format 2016) and allows the user to model constraints like (2), (3), (4) easily via an algebraic modelling language (Koch 2004). It can handle an arbitrary number of objectives and thousands of variables and constraints (Fig. 3).

In this section, we will introduce system dynamics as a modelling methodology as well as the most important modelling rules and characteristics of system dynamics models.

System dynamics was introduced by Jay Forrester in the 1950s as a method of describing and simulating time-dependent effects of complex influence networks with feedback loops (Forrester 1961). Such networks are characterized by non-linear, often surprising behaviour. In fact, a forecast of their future development, and thus their control, represents a difficult mathematical problem.

One of the strengths of the system dynamics approach lies in its visual representation of complex systems. This visual approach is essential in the system dynamics modelling process, and simplifies access for beginners and users who lack experience with systems of differential equations.

The main objects of system dynamics models are stocks and flows. The stocks contain the state information of the system. By convention, each stock has two flows, one flowing into the stock, and one flowing out of the stock. Figures 4 and 5 show visual representations of a stock and a flow respectively. As a third component, auxiliary variables are often introduced to structure a diagram. Lastly, the existence of functional dependencies between stocks, flows and variables is indicated by arrows. Figure 6 shows an example.

Using this visual representation, a systematic modelling process could be structured as follows:

The result of this process is a complete system dynamics model. In the next section, we will discuss numerical methods for simulating a system dynamics model as it develops over time.

Although it is possible to find general solutions analytically for some models, this is generally neither possible nor required. A range of numerical simulation techniques exist that provide quickly accurate simulations. One class of such simulation techniques are the Runge-Kutta schemes (Runge 1895; Kutta 1901) which we will use in this chapter.

As we discussed in the previous sections, in its basic form, SD aims at describing and simulating influence networks. This is an important step in pursuit of understanding the mutual dependencies. In addition to obtaining a mere understanding however, what we would like to do is to intervene in the network, bring it to a desired stable state, or get as close as possible to that state.

Policies constitute a basic and important concept of system dynamics modelling. A policy is a function in some variables that describes the rates of flow in a system and hence the dynamic behaviour of the model (Richardson and Pugh 1981). Thus, a policy is a decision rule which specifies how a decision-maker processes available information from model variables (Sterman 2000). Questions regularly arise concerning whether a given policy can be improved, or even what a “good” policy “actually constitutes or entails. In this context, the need for efficient computational methods for policy analysis as well as policy improvement and design has been recognized in system dynamics, see, e.g., Yücel and Barlas (2011), Keloharju and Wolstenholme (1988), and is an active field of research.

When developing a simulation model, the modelling step of “policy formulation and evaluation” also compares the performance of two or more candidate policies (Sterman 2000). When two simulations with different policies lead to different system behaviors, one has to evaluate which of the two simulations is more suitable or “better” for a given model purpose. To answer this question, one needs to define an objective function so that the higher the value of the objective function for a given simulation, the more favorable or “better” the policy (Dangereld and Roberts 1996). Once an objective function is defined, several approaches to computer-aided policy improvement are at one’s disposal.

Direct parameter policy design starts with the definition of an analytic, parametrized, and usually nonlinear policy function (Keloharju and Wolstenholme 1989). The parameters of this function are set to starting values, and for each parameter, a range of valid values is defined. These parameters constitute then the free variables of the optimisation problem, i.e., the variables which can be varied freely in pursuit of an optimal solution. Consequently, the goal of the policy improvement is to find a set of parameter values within the given range that improves the value of the objective function. The solution space in this case is reduced by the a priori definition of the shape of the policy function. The solution found by the optimisation algorithm depends strongly on this definition and therefore on the expectations of the modeler. If a software package offers parameter optimisation capabilities, it is usually possible to attempt producing the solution of such direct parameter policy design problems.

Table function policy design is one possible way to generalizing direct parameter policy design, by defining a parametrized table function instead of an analytic function (Keloharju and Wolstenholme 1989). In this case, the modeler has to define the number of data points of the table function and two intervals that define the range of valid values of the data points on the \( x \)- and \( y \)-axis. This approach removes the modeler’s expectations of the shape of the policy from the optimisation process. However, the possible policies are reduced to the space of the piecewise linear functions with the selected number of points. If the data points are then required to have a pre-defined distance on the \( y \)-axis, the possible solutions are reduced further, but at the same time, the number of parameters and thus the number of free variables decreases. As in the previous case, the goal of the policy improvement is to find parameter values (i.e., data points of the table function), that improve the value of the objective function. A software package that supports table function policy design is found with the Powersim Studio plug-in SOPS (Moxnes and Krakenes 2005).

In both cases, the modeler has to define the functional dependencies of the policy function. This choice is closely related to the concept of bounded rationality (MoreCroft 1985; Simon 1984) models.

A policy function, i.e., a decision rule, is a model about what information cues an actor employs in order to make decisions in a given system. If this actor has only a limited view of the system, then the policy will only depend on the variables and information that are available to this particular actor (Sterman 2000). An improved policy will enable this actor to make better decisions based on the limited information available to him/her. Recent work has focused on improving policies for such actors, using, for instance, co-evolutionary analysis (Liu et al. 2012).

In this paper, we will consider a different kind of actor. Our actor has a global view of the model, i.e., he or she has information on all the state variables at all times within the simulation time horizon.

Modeling the policy of an actor with such a comprehensive level of awareness with the application of conventional approaches to policy analysis constitutes a difficult endeavor. One option would be to define a table function for each state, that depends only on that state. A mixed policy function that depends on all states, can then be defined as a sum of these functions (Keloharju and Wolstenholme 1989).

One conventional approach to System Dynamics optimisation is based on “optimisation by repeated simulation” (Liu et al. 2012). This has the advantage, that any model which can be simulated, can also be optimized, since there are no requirements on the properties of the model equations. However, approaches using repeated simulation suffer from the “curse of dimensionality” Bellman (2003) dynamic, where the significant dimension is that of the space of free variables. An additional free variable adds a dimension to the optimisation algorithm’s search space. Solving optimisation problems with a large number of free variables therefore quickly becomes impractical. As a consequence, the degrees of freedom in a mixed policy function situation, are limited from a practical perspective, in the case of an optimisation of the policy by repeated simulation being attempted.

The resulting optimisation problem based on a system dynamics model can be written as follows:

In order to solve such a problem, we differentiate between two approaches:

After the discretization of the system dynamics optimisation problem, it is possible to attempt to solve it with existing solvers. Since we are interested in global solutions, the algorithm used should be able to provide a certificate of global optimality. One group of solvers that can provide this certificate are the branch-and-cut solvers that were introduced in Sect. 2.3 This approach has been successfully applied in the solution of Mixed Integer Linear Programs as well as MINLPs from a range of applications [for example, see Defterli et al. (2011), Borndörfer et al. (2013), Humpola and Fügenschuh (2013)]. Solving a control problem derived from a discretised dynamical system with a standard branch-and-cut solver is, however, in many cases unsuccessful, since the solver does not take into account the special structure of the MINLP that arises from the discretization, and from the handling of non-smooth functions via integer variables. Without considering this structure, even finding a single feasible solution can exceed a reasonable time budget of several hours or even days.

In the remainder of this section, we will present the concept of a tailored solver for system dynamics optimisation problems. Like PolySCIP, this concept has been implemented in the framework of the modern MINLP solver SCIP and results can be found in Fügenschuh and Vierhaus (2013a, b), Vierhaus et al. (2014), Fügenschuh et al. (2013). A diagram describing the improved solution process is shown in Fig. 6.