Multi-objective optimization of energy-efficient production schedules using genetic algorithms

The model can be subdivided into two sides: Entities, i.e. the installed machinery, and activities, i.e. the tasks that are to be performed. Also, those are subdivided into multiple levels: Production cells and products on a high level, and individual machines within a cell and tasks that make up those products on a low level. Each task has one or more task modes that describe different ways how the task can be executed and can require or produce different resources (Fig. 1).

One key distinguishing feature of this model is that each task can be implemented in different task modes, which could simply represent performing the same task on different machines, or different ways to manufacture the task that could, e.g., take more time while consuming less energy or vice versa, or consume the energy at a different point in time within the task.

Also, the model features resources that can be used to represent different intermediate products that are produced by one task and consumed by the next, or they can stand for environmental factors, such as one task (or task mode) producing waste heat that must not exceed a certain level, or the state-of-charge of a buffer battery. All resources must always remain within their respective minimum and maximum capacity during the entire production. While resources can be useful for modeling concepts and circumstances that could not be represented otherwise, in other settings they may not be needed and are thus optional. We will come back to resources later when discussing constraints.

This way, the same model can be used for socket power that has a (possibly variable) price and is (for all practical purposes) available in infinite quantities, as well as for limited locally installed “free” renewable energy. Further, negative availability can be used for energy sinks (parts of the production system that consume energy and can not be changed or shifted).

The model can also be used for capped energy tariffs, i.e. tariffs that offer a certain price but allow only a maximum of x Wh to be consumed, and will charge a higher price if that consumption is exceeded. Those can be modeled as two energy sources: The first with the lower price and an availability of x Wh, and another with the higher price and unlimited availability.

The production system is subject to two types of constraints: General constraints and user-specified constraints. The first group includes, among others:These constraints constitute the general “laws” of the system that always have to be respected.

Finally, resource constraints can be used to specify more complex dependencies between tasks by having one task (or task mode) produce a resource that is then consumed by another task (or task mode). Among others, resources and resource constraints can be used for representing:The aforementioned task-dependencies could also be represented using only resource-constraints, but dedicated task-dependencies make those both easier to describe in the model and more efficient to enforce or check.

The result is a schedule for each production cell, describing for each of the tasks that make up the products (a) when the task is to be executed, (b) which task mode to use, and (c) on which machine to execute the task, as well as some statistics, like the total duration, energy consumption in each step, and total energy costs (see Fig. 2).

The request and result as well as the several features comprised in them have been modeled in an object-oriented way, allowing a straightforward implementation in Java and a transformation to readable JSON, as shown in Sect. 4. This request can then be passed to the optimization system, which will be described in more detail in the following section.

Each candidate solution is represented as a genetic code, i.e. an array of integer numbers, subdivided into different “chromosomes” for different aspects of the schedule, which can then be mutated and recombined with a number of primitive and mostly domain-agnostic functions. Table 1 shows an overview of the terms used in the GA and the concepts they represent.

Given the information that makes up the schedule (not considering the derived information like total duration or total energy cost), a first naive representation would be to encode each task with three numbers on three different chromosomes: The starting time, the selected task mode, and the machine to execute the task.

The problem with this representation is that it is very easy to create invalid schedules. For instance, it is not easily possible to swap the order of two tasks to be executed on the same machine. First, one task would have to be moved “out of the way” before the other task can take its place and finally the first task can take the place of the second, otherwise there would be an immediate constraint violation. But even with this three-way-swap, each of the intermediate steps will likely have a lower quality than the original setup. Thus, the candidate schedules containing the partial swap will have a very high chance of being discarded before the swap is complete. Implementing this swap as an atomic operation is not trivial either, as the tasks might have different length and there might be other tasks in between.

An alternative representation, which was adopted in this work, is to replace the starting-time chromosome with two chromosomes for task ordering and pause times, where the former is a valid permutation of the tasks and the latter encodes the time for the task to wait after the last task occupying the same machine has been completed (or after the start of the corresponding product, if there is no prior task on the same machine). While this representation is slightly more complex and more computationally intensive to encode and decode, the benefit is that there can, by definition, be no two tasks occupying the same machine at the same time, and hence fewer candidate schedules will violate constraints. A swap operation as described above can be completed in a single mutation, even if the swap affects more than two tasks. Figure 3 shows a simple example comparing the two representations.

Similarly, on a higher level, the assignment of products to cells is encoded in another chromosome, as are the product ordering and product pause times, i.e. the times to wait before starting the next product (Fig. 4). Consequently, the tasks’ start/pause times are always relative to the start/pause times of their product, and the machine used for a task is always taken from the machine pool of the corresponding product’s cell.

The fitness function is subdivided into two parts: The hard score and the soft score. The hard score includes all the constraints that were defined in Sect. 2 (those that are not prevented by construction), while the soft score includes the makespan, total costs and energy usage, and the maximum power peak. The different aspects of both the hard and the soft score are combined as two weighted products, and then both are combined to the total score. The weighted products are calculated as (1), where rating(s, c) is the rating of schedule s w.r.t. criterion c, and \(w_c\) is the weight given to that criterion.For both hard and soft scores, a lower score is considered better, i.e. if a schedule has a hard score of zero it has no constraint violations. A schedule with a lower hard score will always be preferred to a schedule with a higher hard score, independently of their soft scores. All individual ratings are \(\ge 0\), and, by adding a small \(\varepsilon >0\) to each, effectively \(>0\) so the product does not degrade to zero. The weights are normalized to have a sum of 1, such that, after subtracting the same \(\varepsilon\) from the final product, the score is 0 for a schedule without any defects.

In each generation g, the individuals of the population \(P_g\) are derived from the previous population \(P_{g-1}\) by selecting a random sample of n individuals to be kept without change, i.e. survivors, and a random sample of m individuals to be kept with random alterations, i.e. offspring. (2)The following altering methods have been implemented:Recombination/crossover was tried in the form of partially matched crossover for permutations and single-point crossover for assignment chromosomes, but did not result in a significant improvement of quality.

For security reasons, automated production cells are commonly enclosed by a safety fence preventing human-machine collisions. The use case analyzed here makes use of a turn table that can safely bring a part in- and outside the enclosed cell by rotating \(\pm\)180\(^\circ\). The turn table is driven by a bevel gear (SEW KTF57/R) and an asynchronous motor (SEW DRL100L4BE45) with six pneumatic grippers (Festo ADVU-12-50). The electrical power for the machine is provided by a photo voltaic plant (PVP) with a limited availability but assumed as free of charge (installation, amortization and running costs are neglected) and from an electrical grid with unlimited availability but energy costs. The process consists of several tasks, which are exemplary shown in Fig. 5 and are described in the following:

The components were modeled in the object-oriented and equation-based language Modelica⁷ (Mattsson et al. 1998; Fritzson and Engelson 1998; Fritzson 2010) making use of the Modelica Standard Library. The models were validated against measured energy curves taken from the cell provided by FFT Produktionssysteme GmbH & Co. KG⁸ as part of the SPEAR project. To extend the modularity, these digital twins have been exported as functional mock-up units (FMUs) (Blochwitz et al. 2011, 2012; Modelica 2019). A large set of consumption profiles (task modes) have been computed by varying relevant parameters in the digital twins using the PyFMI⁹ simulation environment. In this use case, the task modes for each of the components differ on their execution velocity, as will be explained later. The resulting consumption profiles are expressed as time series of power.

The resulting power curves for the non-optimized process are plotted in Fig. 6a. In red the consumed power for the manufacturing stages are depicted. For the actual manufacturing process inside the cell a generic constant power consumption of 10 kW is assumed as no real values can be given due to intellectual property protection considerations. In green the power from the photo voltaic plant is plotted. If the power consumption is higher than the energy from the PVP (negative sign), additional power is taken from the electrical grid, whereas unused photo voltaic power is fed back in the power system (positive sign). This power, which is a balance of the green and red curve, is plotted in blue. The resulting energy curve is plotted as blue dashed line. The whole non-optimized manufacturing process takes approximately 46.5 s per part and a total energy of 5.9 kJ is taken from the electrical grid.

For the optimization process different production modes were considered, corresponding to different production speeds, i.e. 25%, 50%, 75% and 100% of the maximum production speed. For validation, the process was optimized for makespan, costs and energy usage with different relative optimization weights. In Fig. 6 the original process without optimization (Fig. 6a), the process purely optimized for makespan (Fig. 6b), a mixed optimization for makespan and energy consumption of energy from the electrical grid with equal weights (Fig. 6c), and purely optimized for minimizing the power consumption from the electrical grid (Fig. 6d) are depicted beside each other for comparison. Additionally, the curves for the energy taken from or fed into the electrical grid are depicted as blue dashed lines. The manufacturing process optimized for makespan takes only 33.5 s, but the power consumption from the electrical grid is increased to 60.0 kJ. When optimizing for minimum costs and energy usage, the process takes 107.5 s and a total energy of 369.3 kJ is fed into the energy grid due to the PVP. Mixed optimizations lies in between these extreme cases. As a compromise the process takes 51.5 s and a total energy of 55.7 kJ is fed into the energy grid. This means for less than 10% longer makespan 61.6 kJ can be saved, which is approximately 30% of the overall power consumption. The results show that the presented algorithm is capable of optimizing the process in the machine for different optimization goals.

As a second use case, the driving path for an automated guided vehicle (AGV) is optimized. The AGV, which was designed and developed by Reeb-Engineering GmbH¹⁰, is depicted in Fig. 7a. It serves as an alternative for the turn table, described in Sect. 5.1, supplying the manufacturing cell with new parts and transporting the processed parts away automatically. For this example, the velocity and drive modes for the path shown as red dotted line in Fig. 7b were optimized.

The AGV considered here moves on four Mecanum wheels that allow holonomic, omnidirectional movement in the plane. Thus, an infinite number of displacement combinations (directions, orientations and velocities of the movement) exist for a given target position. To limit the number of possible combinations, only longitudinal and transverse movement as well as rotation is considered. In position 1 an unmanufactured part is loaded onto the AGV. Afterwards the AGV drives to position 2, where the part is taken from it automatically and further processed. During the manufacturing, the AGV battery is charged by induction marked by the blue rectangle in Fig. 7b. Then the AGV drives to position 3 where the processed part is taken from the AGV for further processing. In total the pathway consists of six different positions (two of which are visited twice, hence seven segments) with two driving modes (longitudinal and transverse) and ten different maximum velocities for each driving mode as well as five charging speeds. The rotation is automatically included where it is needed to achieve the target orientation. This leads to \((2 \cdot 10)^7 \cdot 5 = 6.4 \cdot 10^9\) different possibilities in total.

Similar to the first use case, the modeling of the AGV has been performed in the Modelica Language. The system is divided into four main components: a) a target coordinate system, b) a movement controller, c) the motion prediction describing the transients of the different movements, and d) a simplified battery model. The vehicle motion has been modeled based on velocity, position and energy consumption measurements on the real device provided by Reeb-Engineering GmbH as part of the SPEAR project. From these measurement, it can be seen, for example, that longitudinal movements are energetically more efficient than transverse movements. For visualization and validation the possibility to simulate FMUs in Siemens NX MCD™¹¹ was used and a video of the resulting process is provided by Reeb-Engineering GmbH (2020).

The results of the optimizer are plotted in Fig. 8. The solid lines are the power curves and the dashed lines are the corresponding energies. While the part is processed, which takes 28 s, the AGV battery is charged, which can be seen by the negative sign of the power curves as well as the negative slope of the energy curves. In Fig. 8a the path optimized for minimum makespan is shown, which takes about 66 s to complete a round. To get a minimum makespan the segments 2, 4, 5 and 7 are driven transversely, because no rotation is needed. Also, as expected, the optimizer proposes to use the maximum velocity for each segment. This combination of modes consumes an energy of 10.4 kJ in total. In Fig. 8b the result of a mixed optimization is plotted, where the energy consumption and minimum makespan are equally weighted. This process takes approximately 71 s and an energy of 8.9 kJ is used. To reduce the power consumption, between segments 4 and 5 as well as 7 and 1 rotations occur, and the path is driven with lower velocities than the path presented in Fig. 8a. Because of the rotation between segments 4 and 5, the available charging time is reduced (rotation time plus charging time equals 28 s). Finally, in Fig. 8c the path for minimum costs and energy usage is plotted. For all way points, except the one between 4 and 5, the AGV rotates, allowing to only drive longitudinally. This leads to a longer makespan of 86.7 s in total and energy consumption of 7.2 kJ. Contrary to initial expectations, the optimum driving mode for minimum energy usage does not employ minimum driving velocities due to the fact that lower velocities use temporarily lower energy, but for longer time, leading to a higher energy consumption in total. This observation underlines the necessity of sophisticated optimization approaches, like the one presented in this work. The results also demonstrate that, comparing the paths for minimum makespan and the mixed optimization, only 6% longer makespan can save approximately 14% of the energy consumption.

For validation, also all possible combinations were evaluated to make sure to get the global minimum of makespan and power energy usage and not just a local minimum. This kind of “brute-force” optimization took seven days on a single-core 2.4 GHz CPU, compared to approximately one hour with the presented framework based on genetic algorithms. It was shown that both approaches (brute-force and genetic algorithms) give the same results and hence that the presented results are global minima and not just local minima, but the presented approach took just about 1% of the time of the brute-force approach. Thus, this example can be solved efficiently by genetic algorithms.

Other approaches use Jacobian matrices to avoid evaluating all permutations of possibilities (Braun et al. 2011; Åkesson et al. 2012). However, not all permutations are valid and the numerical effort would be tremendous. On the other side, sequential optimization of intermediate segments or single movements might not lead to a global optimum.