1 Introduction

Product manufacturing typically improves competitiveness by increasing quality and reducing cost. Interactive simulation techniques contribute to this improvement by helping identify potential optimisations without incurring in heavy physical testing processes [2, 3, 16]. There are many different approaches in the literature that are based in physical simulations and deterministic models that optimise industrial processes in terms of quality, time, raw material, etc. From a design perspective, Cherifi et al. [11] propose the use of methodologies such as TRIZ [8] to introduce new factors in the design process.

On the other hand, the machine tool industry is currently creating devices fully equipped with sensors that provide massive and heterogeneous data on the production process that is available in real-time. This data can contain highly valuable information that, if properly characterised and modelled, could dramatically improve optimisation processes.

As a specific realization of this approach, we propose the use of linear and non-linear optimization methods to generate optimal schedules for reducing energy and time consumption, increasing in this way the competitiveness of aluminium injection processes. The main limitation of scheduling processes for manufacturing is the computational cost in terms of processing time for the creation of optimal schedules, especially in non-linear optimization methods: for real world applications, it is crucial to be able to provide a low time response for the scheduling task.

The formal understanding of industrial production processes and their optimization have represented valuable objectives for the effective management of manufacturing plants at least since the work of Frederick Taylor [28]. The possibility for innovation is brought forward by massive real time collection of sensor data which represent a valuable asset to these ends. Methodologies to exploit this data are typically based on on-line analytical procedures that can be set up to summarize the state of the production plant and to identify and suggest possibilities for improvement in the overall efficiency.

Energy consumption optimization is growing in societal significance [13] and as a consequence energy-efficient manufacturing [25] is one of the top priorities for future years [22]. To this end, energy-optimal production scheduling methodologies are gaining growing importance in manufacturing [14].

Process scheduling is based on optimization procedures that need to consider large numbers of input variables (the types of parts that are to be produced, the different steps and components in the production process) and of operational constraints (for instance, not all the machines are capable to produce every kind of part) across multiple manufacturing lines. In principle, multiple locally optimal production schedules exists, while global maxima need if at all possible to be identified.

The present contribution introduces the results of a specific study carried out on real data resulting in the definition, implementation and validation of procedures for the time- and energy-optimal on-line scheduling of production across a manufacturing plant operating by metal injection molding. The on-line capabilities of the proposed methodology imply that unforeseen contingency situations related e.g. to the interruption of manufacturing processes in one or more lines can be accounted for by rapidly rescheduling the production of the required output on available facilities.

The structure of the present contribution can be described as follows: Sect. 2 describes the state of the art and related work, Sect. 3 introduces the proposed methodology in detail, Sect. 4 describes the data acquisition process and characteristics and in Sects. 5 and 6 the employed techniques to optimize energy and time consumption are analyzed. In Sect. 7 computational results are evaluated and in Sect. 8 the quality of the final optimization results is evaluated. The interactive scheduling visualization component is introduced in Sect. 9, which is followed by the Conclusions.

2 Related work

The present work builds on contributions put forward in the state of the art by a number of authors proposing related methodologies [1, 5, 24, 27]. All these contribution focus on process scheduling optimization given the constraints imposed by manufacturing process planning. The relation between the two can be described as follows. Manufacturing process planning defines how a product will be manufactured. It entails the minimization of objective functions describing for instance the cost of the produced good or its makespan. It therefore is a prerequisite to scheduling and implicitly defines its context. In contrast to this, process scheduling has the objective of producing a timetable describing the utilization of the manufacturing resources defined by the planning for the optimal production of the intended items [26]. In the remainder of this contribution, we focus solely on scheduling, treating the results of planning as a given that is not subject to further optimization.

A number of classes of Parallel Machine Scheduling Problems (PMSPs) are investigated in the literature [15]. The problem is given by a set \(N = \{1,2,3,\ldots ,n\}\) of n jobs to be scheduled in m unrelated parallel machines \(M = \{1,2,3,\ldots ,m\}\). Any job \(j \in N\) can be carried out on any machine \(k \in M\) that is able to process it, with an associated time cost \(t_{j,k}\) and an energy cost \(e_{j,k}\) which depends on the characteristics of the machine and on those of the specific job. Each job is released at the beginning of the scheduling period.

Contributions in the literature distinguish among three PMSP categories: identical, uniform and unrelated PSMPs [10]. The problem presented in this paper concerns the optimization of the scheduling of N jobs in M parallel unrelated PMSP. The jobs’ processing times and consumptions are machine-dependent and without any relationship among machines.

In further detail, in the frame of this contribution, we focus on PSMPs with machine-independent setup times [17], assuming setup time variations negligible with respect to actual production times and therefore disregarding them. This assumption represents a simplification with respect to the full framework considered by contributions in which set-up times are explicitly considered as dependent for instance on the specific manufacturing line to be employed and on the manufactured item type [4, 18].

In order to find optimal solutions to the scheduling, most contribution reduce the optimization problem to one of the standard NP-hard combinatorial problems [20]. Multiple constraints related to available production times and possibly materials need to be taken into account.

A further constraint refers to the fact that that each job needs to be allocated to a machine or manufacturing line that is known to be able to process it. This machine–product compatibility constraint stems from the fact that in general machines/production lines are non-identical, and need therefore to be considered incapable of producing a product of a specific type, unless evidence is available of the contrary—for example given by the fact that they have been observed producing products of that class according for instance to historical log records. More complex variations of this constraint are of course possible, and can be described in terms of criteria taking into account multiple characteristics of product types and machines. We consider this simplified approach a good approximation of reality for the purposes of this contribution.

Resulting processing schedules are typically represented as tables reporting sequences of the numbers of pieces of a specific type to be produced by each specific processing line or manufacturing machine.

A final issue refers to the visualization of the obtained optimal schedules. For time oriented schemes of this type, conventional diagrams in the form of Gantt charts [29] are widely used and understood in applications as diverse as project management, the representation of patient histories [12] or manufacturing planning/scheduling visualizations [19]. Their integration into interactive interfaces allows their exploration and interpretation even when highly detailed plans are output by the planning system [23].

3 General optimization methodologies

Operations research methods can be used to optimize production task schedules taking into account energy consumption and time limitations. Their general objective is the definition of methodologies for science based decision making taking into account on the best utilization of available resources.

The general format of operations research models includes or objective function which can in general be considered as representing the cost of a given solution to the problem. A second component of the standard problem definition is a set of constraints which are represented by additional inequalities. These inequalities bound the the feasible set, the sub-space of valid solutions.

As a specific example, in the case of linear problems, the cost function can be represented as

$$\begin{aligned} minimize: f(x) = c^T x . \end{aligned}$$
(1)

Linear constraint inequalities can be written as

$$\begin{aligned} \begin{aligned} subject\, to: Ax = b \\ x<=0 . \end{aligned} \end{aligned}$$
(2)

In this case, a polygonal feasible set results (Fig. 1).

Fig. 1
figure 1

Geometric interpretation of an Linear Programming [6]

Full size image

In the case in which both the inequalities and the objective are linear, the level curves of the objective functions can be understood as hyperplanes orthogonal to c, while an optimal \(x*\) point can be found in P that goes as far as possible in the direction c [6].

In the case that the objective function has non-linear components, more complicated methodologies need to be taken into account. A possible way to address the problem is to reduce the optimization problem to a known combinational optimization problem of the kind of the Bagged Binary Knapsack [7]. In this standard problem, we are given a set of n items and m sacks to save them in. Each item i has a well-defined associated profit or value p(i) and a size s(i), and each sack j has a known capacity c(j). Solving the problem amounts to finding a subset of items with maximum profit such that they have a feasible packing in the available bins [9]. Finding an optimal solution is in general hard: the Knapsack problem is known to be NP-hard and, as a consequence, methods for efficiently finding approximated or locally-optimal yet good-enough solutions are often employed.

4 Specific problem setup

Optimal schedules need to be defined for a metal injection molding plant equipped with 31 injector machines. Every injector is provided with components for the real-time collection of sensor data designed to allow the monitoring of the energy consumed by the elements of the plant.

The collected sensor data is aggregated locally by control systems and immediately transmitted to a central server for secure storage. The central server ingests the acquired measures in a relational database that keeps track of energy and time consumption with a sampling period of around one second. As additional information, the number of correct and invalid output pieces produced is inserted in the database at the end of every shift.

According to the available historical records, the machines are collectively capable of producing 57 different kinds of output parts, yet as mentioned above not all the parts can be produced by any machine. Again, for extended schedules we assume we can neglect mold changing time variations and machine-dependent setup time variations with respect to the actual production times.

Operators read the proposed production schedules from graphical terminals installed next to the production machines, and are able to monitor the progress of the production on the same terminals. A consequence of this configuration is that keeping computational costs controlled across the different schedule optimization algorithms is essential to allow the final user who is in front of the interface to keep working efficiently.

5 Energy optimization methodology

For M given machines, an energy-optimal production task schedule can be defined based on linear programming methods based on operations research.

An objective function \(E_i\) specific to the production of part i can be defined based on the total number of parts produced. If i is the part index \((1\ldots I)\) and m is the machine index \((1\ldots M)\), \(n_i^m\) is the number of parts per hour that a specific machine m is capable of producing, \(t_i^m\) is the time that the machine needs to produce each part and \(e_i^m\) is power consumption in W for the given injector for each part per hour, then obviously:

$$\begin{aligned}&E_i\left( t_1^1,\ldots ,t_1^M,t_2^1,\ldots ,t_2^M,t_I^1,\ldots ,t_I^M\right) \nonumber \\&\quad = \sum _{m=1}^M \sum _{i=1}^I \left( n_i^m \cdot t_i^m\right) \cdot e_i^m \end{aligned}$$
(3)

Equations 4 and 5 show the optimization constraints, where \(O_i\) is the total number of parts of type i that must be produced and T is the maximum amount of time that can be used to produce all parts:

$$\begin{aligned}&\sum _{m=1}^M \left( n_i^m \cdot t_i^m\right) = O_i \end{aligned}$$
(4)
$$\begin{aligned}&\sum _{m=1}^M \sum _{i=1}^I \left( n_i^m \cdot t_i^m\right) \le T \end{aligned}$$
(5)

The structure of the energy optimization objective function and of its constraints has the linear structure described in Sect. 3. As a consequence, while a large variety of optimization techniques can be employed depending on the structure of the objective function and on the constraints, simple Linear Programming techniques can be used for energy optimization.

An example optimized schedule is represented in Figs. 6 and 8.

6 Time optimization methodology

If i is the part index \((1\ldots I)\) and m is the machine index \((1\ldots M)\), \(n_i^m\) is the number of parts per hour that a specific machine m is capable of producing, \(t_i^m\) is the time that the machine needs to produce each part.

$$\begin{aligned} T\left( t_1^1,\ldots ,t_1^M,t_2^1,\ldots ,t_2^M,t_I^1,\ldots ,t_I^M\right) = \max _m \sum _{i=1}^I t_i^m \end{aligned}$$
(6)

While energy optimization can easily be carried out by linear methods, the objective function used in time optimization (Eq. 6) evidently includes a non-linear expression that represents the minimum time taken by the slowest machine.

Given the non-linear nature of the objective function considered for the time optimization, we map it to a well-known Bagged Binary Knapsack problem in order to more easily define solution methodologies for it.

To this end, we map the processing times in the scheduling problem to the item weights in the standard formulation of the problem, and the available machine time to the space left in the sack representing the machine. A measure of urgency for a given piece (a ratio between the number of items to be produced for a given product class and the available time left on the machines capable of producing that kind of piece) is taken as a measure of profit or value for a given piece.

Approximate solution methods capable of efficiently identifying locally-optimal solutions to the Bagged Binary Knapsack can therefore be exploited. We employ an approximation based on the Dantzig method [21] to greedily solve the problem, sorting the items to be produced in decreasing order of value per unit of weight and inserting them in order into the current proposed scheduling solution set.

The obtained methodology represents a heuristic converging to a local minimum. If \(S^m\) represents the slack for given machine m then \( (\sum _m n_p^m \cdot S^m)_{p \in P} \) is the maximum number of of parts that can be produced considering all machines concurrently. A valid scheduling solution must verify the condition that the scheduling order it represents does not exceed production capacity:

$$\begin{aligned} \left( \sum _m n_p^m \cdot S_p^m\right) _{p \in P} \; \forall p \in P = O_p. \end{aligned}$$
(7)

The mapping of the quantities from the scheduling to the Bagged Binary Knapsack problem can be described as follows:

  • the available machine time \(S_p^m\) corresponds to the slack for machine m, and is mapped to the available space in the Knapsack to be filled

  • a measure of the urgency of each piece to be produced, \(O_p/\sum _m n_p^m S_p^m\), is mapped to the value of the item to be added to the Knapsack

  • the number of maximum parts that can be produced in the available time, \(n_p^m S_p^m\), is mapped to the number of available items for the Knapsack

  • the weight of the element in the Knapsack is mapped to the number of minutes to produce the required product \(1/n^m_p\).

The most urgent product \(\hat{p}\) can therefore be identified by

$$\begin{aligned} \hat{p} = \arg \max _p \left( \frac{O_p}{\sum _m n_p^m \cdot S_p^m}\right) _p \end{aligned}$$
(8)

The machine \(\hat{m}_{\hat{p}}\) that is most available for it

$$\begin{aligned} \hat{m}_{\hat{p}} = \arg \max _m \left( n_{p=\hat{p}}^m \cdot S_p^m \right) _m \end{aligned}$$
(9)

can be assigned to it to progressively allocate the available time to parts to be produced.

Equivalent rescaled and quantized weights for the machine that is fastest at the most urgent product can be described as

$$\begin{aligned} \left( w_p^{m={\hat{m}_{\hat{p}}}} \right) _{p \in P} = \left( 1 / n_p^{m={\hat{m}_{\hat{p}}}} \right) _{p \in P} \; \end{aligned}$$
(10)

Iteratively updating the order matrix

$$\begin{aligned} \sum _p \hat{S}_p^{m=\hat{m}} = \sum _p n_p^{\hat{m}}/\hat{O}_p^{\hat{m}} \end{aligned}$$
(11)

and the computed slack by \(S_p^m - \sum _p \hat{S}_p^m\) results in an effective optimization of the production schedule across production lines that is attainable in a limited number of iterations and is therefore usable for on-line scheduling of manufacturing orders.

If the constant quantity C denotes the maximum available time to produce all parts, then:

$$\begin{aligned} C \ge \sum _{m=1}^M \sum _{i=1}^I \left( n_i^m \cdot t_i^m\right) \end{aligned}$$
(12)

Examples of locally time-optimal schedules are represented in Figs. 6 and 8.

7 Experimental results

The proposed optimization algorithms were implemented in the Python interpreted language and exposed through a web service from a network server equipped with an Intel Core i7-4790 3.60 GHz CPU and 4GB of RAM.

Three sets of experiments were designed and ran in the server comparing the results between 2 algorithms. In the first test, an iterative production of a variable number n of jobs for 200 parts were simulated in m machines. In the second one, the same iterative jobs and machines were used for 1000 parts. In the third set, 5000 parts were considered.

The experimental parameters and the obtained results are summarized in Table 1. The nomenclature for iterations is m / n / p where the m index denotes the number of machines, n indicates the number of jobs to be inserted in the schedule, and p is the number of parts to be produced.

Figures 2, 3 and 4 presents the results in graphical format. The format of the index used in the diagrams deserves a detailed explanation. The index is composed of two integers separated by a slash, with a format \(kj\) according to the notation in Sect. 2. Again, the first integer \(k \in M ={1\ldots m}\) represents the number of concurrent machines, while the second one \(j \in N ={1\ldots n}\) represents the number of jobs.

The maximum number of jobs that we can consider, given the historical event logs made available by the real plant, is until the writing of this contribution of 10: this is the current number of different pieces ever produced in the two most prolific machines of the plant since the installation of the metrics logging system.

The maximum number of machines that we consider is again of 10: a significant set of existing machines whose work is recorded in the event logs have been necessarily left out of the present analysis because they had been essentially used isolation, processing jobs that had not been assigned to almost any other one. The jobs meant for them would have been “stuck” in this work centres without the possibility for the scheduler to re-allocate them to a different one.

Table 1 consumption times for optimization without time constraint in seconds
Full size table

Experimental energy optimization results In the case of energy-optimal scheduling without any maximum time constraint, computational costs in time for the three different tests have measures between 4.07 seconds for the fastest and 18.30 seconds for the slowest one. The consumed time grows linearly between 4 and 10 second for scheduling the production of 200 parts (Fig. 2), it stays between 10 and 12 for the experiment in which the production of 1000 parts is considered (Fig. 3), and it grows exponentially from 4 to 18 seconds for the 5000 parts scheduling experiment (Fig. 4). When a constraint specifying the maximum available production time is added to the problem formulation, experimental time consumption results are not affected by the addition.

Experimental time optimization results In the case of time-optimal scheduling, the computational cost grows linearly in the 200 parts and in the 1000 parts experiments (Figs. 2, 3) from 5.51 to 22.03 s. For the 5000 parts scheduling experiment, with two or more machines CPU time consumption rises until 139.74 in the best case. This represents a problem, since as we described in a previous Section, a practical requirement for the exploitation of the scheduler in the operational environment is that the response is produced in less than one minute. Again, adding a maximum total available time constraint does not affect computation times.

Fig. 2
figure 2

Comparison between energy optimization and time optimization CPU work time for 200 parts

Full size image
Fig. 3
figure 3

Comparison between energy optimization and time optimization CPU work time for 1000 parts

Full size image

Comparison between experimental results Figures 2 and 3 confirm that time consumption is larger for time-optimal than for energy-optimal scheduling, as expected from the different performance of linear optimization and non-linear optimization algorithms. The comparison between Figs. 4 and 5 shows that the time cost of non-linear algorithms grows rapidly, bringing them out of the range of practical applicability.

Fig. 4
figure 4

Energy optimization CPU work time for 5000 parts

Full size image
Fig. 5
figure 5

Time optimization CPU work time for 5000 parts

Full size image

8 Optimization results

Figure 6 shows an energy-optimal schedule for the parts to be produced with no maximum production time constraint. Figure 8 shows how the introduction of a constraint imposing a maximum production time of 27 h forces the energy-optimal scheduling to result in a balanced workload among three energetically efficient injectors.

In the procedure for time-optimal scheduling, the constraint imposing a maximum production time can be made inactive by specifying a number of hours ample enough for all pieces to be produced in any possible order. In this case, the scheduler converges as expected to a locally optimal schedule, as can be seen for example in Fig. 7.

When, on the other hand, the maximum production time constraint is imposed by specifying a number of total hours generated for instance by the fast energy-optimal schedule generator, then the production gets distributed in a more balanced way to all available machines, resulting in a better minimum to be reached for the makespan, as shown in Fig. 9. In the specific case of parts 10033 and 10052, the scheduler is not able to distribute the work because of the machine-part compatibility constraint according to the historical logs available.

Fig. 6
figure 6

Cumulative time in hours for the production of a specific parts in different injectors—energy optimal scheduling without any time constraint

Full size image
Fig. 7
figure 7

Cumulative time in hours for the production of a specific parts in different injectors—time locally optimal scheduling without any time constraint

Full size image

Each optimization algorithm is adapted to the specific purpose for which it was designed. The energy-optimal scheduling algorithm is fast and converges to a global optimum for its objective function. The time-optimal scheduling algorithm by itself only converges to a local minimum. Introducing in its formulation a maximum production time constraint based on the results from the fast energy optimizer makes it converge to a lower minimum. This composition of the two methods makes it possible to rapidly obtain schedules that combine low energy footprint with low makespans for the production.

Fig. 8
figure 8

Cumulative time in hours for the production of specific parts in different injectors—energy-optimal scheduling with a 27 h maximum time constraint

Full size image
Fig. 9
figure 9

Cumulative time in hours for the production of specific parts in different injectors—time-optimal scheduling with a 27 h maximum time constraint. In the specific case of parts 10,033 and 10,052, the scheduler is not able to distribute the work because of the machine-part compatibility constraint, based on the historical production logs available

Full size image

9 Interactive schedule visualization

The design and implementation of a Graphical User Interface front-end to the scheduling system makes its interactive usage possible. Planners can introduce the parts that they need produced, and any maximum production time constraints that are deemed relevant. The tool reads this input and the historical production logs, then calculates an optimal schedule that is then presented in a Gantt chart. Figure 10 shows a screenshot of the interface, which includes an interactive schedule visualization which is created based on the planning results.

Fig. 10
figure 10

Schedule representation in a Gantt chart

Full size image

10 Conclusions

The sensorization of manufacturing in Industry 4.0 can be leveraged for automated energy- and time-optimal production scheduling across multiple production lines.

We present an methodology aimed at this objective that focuses methodologically on optimization by linear programming and Bagged Binary Knapsack. Combining the results from an efficient energy-optimizing scheduler with a secondary time-optimizing method yields the best results.

The methodology is demonstrated and evaluated on real data from a sensorized manufacturing plant operating by metal injection molding procedures.