Facing energy-aware scheduling: a multi-objective extension of a scheduling support system for improving energy efficiency in a moulding industry

Abstract

Nowadays most industries do not integrate product, process and energy data. Costs due to energy consumption are often considered externalities and energy efficiency is not deemed a relevant performance criterion. In energy-intensive processes, as injection moulding, the specific energy consumption, embedded inside the same products, depends on the machine–product combinations. Multi-objective scheduling, including the energy data acquired from shop floor and allocation criteria, is a valuable approach to improve energy efficiency. This paper presents the extension of a commercial detailed scheduling support system developed within a regional Italian project aiming at providing tools to manufacturing industry for improving energy efficiency. The project designed a monitoring system developed by instrumenting injection moulding presses to acquire the energy consumption for each product–machine combination. The commercial scheduling system was extended by implementing a multi-objective metaheuristic scheduling approach. The experimental assessment of the proposed approach involved a major producer of plastic dispensers. The extended algorithm simultaneously optimizes the total weighted tardiness, the total setup and the energy consumption costs. The obtained results, produced for a real test case and a set of random generated instances, show the effectiveness of the proposed approach.

1 Introduction

Within the emerging industrial sustainability domain, production efficiency interventions are gaining practical interest (Tonelli et al. 2013), since manufacturing plants are facing increasing pressure to reduce their carbon footprint, driven by concerns related to energy costs and climate changes. Energy costs due to production have been traditionally considered as externalities that must be incurred and that cannot be reduced by production planning and scheduling. Nowadays, an holistic view, combining economic efficiency of manufacturing production with environmental issues and their consequent economic costs, is considered more and more essential (Despeisse et al. 2012). Therefore, industrial sustainability, in particular energy efficiency (EE), has recently grown as a complementary factor to productivity. Three key factors drive energy efficiency improvements: energy cost (Mukherjee 2008), consumer awareness on sustainability, turning into company competitive advantage (Jovane et al. 2008; Sutherland et al. 2008) and legal compliances (UN 1998). The possible policies (Thollander et al. 2013) and hurdles relevant to the implementation of EE in several countries have been recently analysed (Kostka et al. 2013). In practical terms, the possible reduction of energy costs can be pursued both by increasing EE of production processes and implementing new operational management approaches (Weinert et al. 2011). Possible strategies range from the reduction of non-production modes (Soroush 2010) to the optimization of the use of energy during time, taking into account both the reduction of peak of demand and the shift of load from peak periods to off-peak ones to take advantage from reduced energy prices (Michaloski et al. 2011).

In order to successfully implement EE policies, the integration between energy consumption monitoring and management of production flow is fundamental. This requires performance indicators able to combine energy consumption with traditional indicators, like production costs or delivery times (Taticchi et al. 2013), so as to measure and improve both dimensions in an integrated way. Nowadays most of the manufacturing industries miss energy related data, lacking the information flow from shop floor to top floor; consequently modelling and integrating EE as a relevant performance criterion in a comprehensive framework is prevented (Seow and Rahimifard 2011). Even when energy data capturing systems are available, significant difficulties occur in using and integrating raw data about power, energy and processing variables with the information handled by the other systems supporting production operations. Specifically the effective use of the acquired data requires a bottom-up integration of the energy data into the Manufacturing Execution Systems (MES), managing machines and processes, and the Enterprise Resource Planning (ERP), organizing the customer orders, articles, quantities to be produced and stocks of raw materials. A valuable example is provided in Langer et al. (2014), where model-based manufacturing control strategies are discussed, which provide energy-saving resource scheduling and order dispatch in automotive plants by levelling and temporal shifting power demands. Hence, energy efficiency becomes an organizational aim in all management levels of an enterprise and it needs to be included as an optimization objective in MES.

A very interesting industrial sector for introducing EE is Injection Moulding (IM), that, by processing 32 % by weight of plastic products, is one of the most widespread manufacturing industry. Although being one of the greater energy consumer, with $2.06 \times 10^8$ GJ per year only in USA, IM industry still considers energy as an externality, i.e., an overhead or a fixed cost. IM intrinsically provides high production rate while its energy efficiency is low [approximately 10–20 % (Mattis et al. 1996)]. This figure makes IM a primary candidate for implementing EE strategies since also a reduction of a very few per cent in energy consumption could provide important cost savings. Therefore, to improve energy efficiency in IM several approaches focusing on machine improvements and moulding technologies, on process parameters optimization, or on products design are reported (Lu et al. 2012).

This paper presents a research carried out within the framework of a project funded by the Liguria Region (Italy) that involved an Italian small medium enterprise, operating as an ICT solution provider for manufacturing, and researchers from the University of Genova (Italy). The project had two overall objectives. One was providing tools for improving the industry awareness about energy consumption due to production processes. To this end the project included the development of a system for monitoring, collecting and analysing data about energy consumptions, associating them with data relevant to machines and products. The project objective specifically considered in this paper was to extend the software company Detailed Scheduling Support System (DSSS) to account for energy consumption in addition to typical production key performance indicators. The project was developed with reference to a real industrial test case, since it involved as end user an IM industry leader in the production of plastic sprayers and dispensers with plants in several countries.

The remainder of this paper is organized as follows. In Sect. 2 the relevant literature is summarized. Section 3 introduces the faced problem and Sect. 4 provides a mathematical formulation. The developed approach to extend the software company DSSS is presented in Sect. 5 and the experimental tests performed both on real data provided by the end user industry and on random generated instances are shown and discussed in Sect. 6. Finally, some conclusions are drawn in Sect. 7.

2 Literature review

The problem of taking into account objectives relevant to the reduction of costs due to energy usage together with classic scheduling objectives, e.g., associated with the completion times of the activities or due dates, recently received an increasing interest. Therefore, the relevant scheduling problems require to be faced by multiple criteria optimization approaches (Hoogeveen 2005). Possible strategies for increasing EE try to reduce the energy waste in production processes and usually operate at the single machine level, allowing, whenever possible and convenient, to turn off the machines during idle times (Mouzon et al. 2007; Shrouf et al. 2014).

In multi-machine environments, both mathematical models and metaheuristics have been designed to deal with EE improvement in scheduling. Liu et al. (2013) face the problem of simultaneously minimize the total weighted tardiness and total energy consumption in job shops by a multi-objective genetic algorithm. A similar strategy is used by Yi et al. (2012) to minimize both carbon emissions and makespan, whereas Yan et al. (2005) propose a tabu search heuristics for minimizing energy consumption and makespan. Several works refer to EE trying to reduce the peaks of energy consumption in parallel multi-machine contexts. Fang et al. (2011) propose a multi-objective mixed integer programming formulation for minimizing makespan, the peak time total power consumption and the carbon footprint. In Bruzzone et al. (2012) a time-indexed formulation is used for optimizing the timing of a schedule produced by an Advanced Planning and Scheduling (APS) system in order to minimize the peak consumption, while accepting the trade-off of a possible increase in the total tardiness.

Another strategy tries to take advantage of the variable energy prices, aiming at reducing the energy consumption during the on-peak periods. In Shrouf et al. (2014) a genetic algorithm to minimize total energy consumption costs is proposed for a single machine scheduling problem, considering also the possibility of turning off idle machines. In continuous manufacturing a mixed integer programming model based on time discretization is adopted by Mitra et al. (2012) for production planning in power-intensive processes. Kuster et al. (2013) use an approach based on evolutionary algorithms to shift energy intense processes to times when renewable energies are abundant, also exploiting multi-agent technology for distributing the optimization. The optimal insertion of idle times in periods when energy cost is high is considered in Moon et al. (2013). Luo et al. (2013) face a hybrid flow shop scheduling considering not only production efficiency, but also electric power cost with the presence of time-of-use electricity prices.

In many manufacturing industries characterized by intense production process (e.g., as in the moulding industry considered in this work) and by fixed working time shifts, EE by moving the production activities in off-peak periods or inserting significant idle times for the machines may not be acceptable. In multi-machine workshop a different possibility, followed in this paper, is to take into account the different levels of energy consumption needed by the alternative machines eligible for executing the jobs. Following this approach, in Dai et al. (2013) an energy-efficient model for flexible flow shop scheduling in a metalworking workshop is reported, which uses a genetic-simulated annealing algorithm to make a significant trade-off between the makespan and the total energy consumption. Similarly to the approach developed in this paper, several works in literature integrate or complement existing scheduling solutions to extend their capabilities to take into account EE. Le and Pang (2011) face a dynamic scheduling problem for an industrial stamping system, which minimizes the sum of energy cost and tardiness penalty under power consumption uncertainties. Nilakantan et al. (2015) propose models focusing on time and energy to simultaneously minimize the cycle time and total energy consumption in a real robotic assembly line.

3 The problem

The complexity of manufacturing systems can be faced by a multiple-level structure, from the level of the individual devices, where unit processes take place, through to that of the enterprise, where all the activities of the manufacturing system, including supply chain externalities, are considered. EE measures for the IM industry are consequently possible at the levels of:

• Device/unit process;

• Line/cell/multi-machine systems;

• Facility.

Differently from previous contributions investigating energy-aware scheduling for flexible flow shops, the proposed research has been implemented at line/cell/multi-machine continuous/discrete manufacturing process. Specifically, the EE approach relies on the availability of actual energy consumption data, related to the product-injection machine combination, to define a performance index affecting the solution of scheduling problems.

The problem complexity is increased by the need to simultaneously consider different and conflicting objectives, such as energy consumption costs, penalty costs due to delayed demand satisfaction and machine tools setup costs.

Manufacturing process monitoring to track energy consumption and energy efficiency parameters has been implemented at a large plastic IM factory of the company involved as case study. The production process is done by IM presses capable to produce multiple pieces for each moulding cycle, according to a selected stamp tool, with electrical power between 46 and 69 kW.

The plastic producer company invested in substituting most of the presses from hydraulic/hybrid to all-electric machines whose specific energy consumption (SEC) is 1.46 MJ/kg of produced product, without accounting for the efficiency of the electric grid; besides SEC of all-electric presses is quite not dependent on the throughput (Thiriez et al. 2006).

The factory cumulates consumptions that can be considered belonging to the high yearly consumption class, as they exceed 10 GWh per year. Nevertheless, the factory is managed with medium-low consumption logic since products and processes are treated as being performed by single lines and working cells. Even though the introduction of all-electric presses already represents a valuable step towards EE, to further improve EE of the considered process, the presses have been instrumented through acquisition hardware (Schneider Electric PM3250 Model), allowing to get the required relevant data such as current, voltage, power, power factor, apparent, and reactive power. These data, linked to the production schedule of the orders released on the presses over time, provide the electrical consumption details.

The considered problem assumes a set of orders that must be processed on a set of machines; each order corresponds to a job. Each job is characterized by a release date (the earliest start date for processing) and a due date. A penalty cost is due if the order is completed after the due date. The jobs are carried out by the machines (presses) selected from a set of alternative ones. The processing time and electrical consumption of the jobs depend on the selected machine. In order to execute a job the machines must be prepared by changing the mould, cleaning the machinery, etc. Therefore, a setup time between two successive jobs producing different products on a machine must be considered; setup times may also depend on the kind and peculiarities of the machine, therefore the setup depends on machine and job sequence.

The solution $S^*$ of the considered multi-objective scheduling problem is obtained by minimizing a vectorial objective function:

$$\begin{aligned} S^* = \arg \min _{S}[\hbox {Dd}(S), \hbox {En}(S), \hbox {Sc}(S)]' \end{aligned}$$

(1)

where

• $\hbox {Dd}(S)$ is the penalty cost due to the late completion of the jobs with respect to the order due date,

• $\hbox {En}(S)$ is the energy consumption cost and

• $\hbox {Sc}(S)$ is the total setup cost.

The $\hbox {En}(S)$ cost is due to the fact that different presses may need different quantities of energy to carry out the same job (a new machine can be faster and can require less energy than an older).

4 The mathematical model

In this section, a mixed integer programming (MIP) model is introduced for the considered scheduling problem. The following notation is used for sets, constant parameters and variables.

Sets

• $J=\{1,\ldots ,n\}$ set of jobs; note that indexes 0 and $n+1$ denote two fictitious jobs corresponding to the first and last jobs on each machine;

• $M=\{1,\ldots ,m\}$ set of resources (the resources correspond to machines equipped with some tool, that is, machines in a certain state; note that tools are not explicitly considered);

• $M_j, \forall j \in J$ set of resources that can execute job j;

• $J_k, \forall k \in M$ set of jobs that can be executed in resource m;

Constant parameters

• B a sufficiently large constant (big-M);

• $D_j, \forall j \in J$ the due date of job j;

• $R_j, \forall j \in J$ the release date of job j;

• $W_j, \forall j \in J$ the tardiness penalty of job j;

• $T_{jk}, \forall j \in J, k \in M_j$ the processing time of job j on the eligible machine k;

• $E_{jk}, \forall j \in J, k \in M_j$ energy cost for processing job j on machine k;

• $S_{ijk}, \forall i,j \in J, k \in M_j, i \ne j$ the setup time on machine k between the completion of job i and the start of the subsequent job j;

• C setup cost for unit of time;

• $\Pi _g, g=1,2,3$ the weights of the objective function components, i.e., total weighted tardiness, total energy cost and total setup cost.

Variables

• $c_j, \forall j \in J$ completion time of job j;

• $t_j, \forall j \in J$ tardiness of job j with respect to its due date;

• $x_{ijk} \in \{0,1\}, \forall i,j \in J, k \in M_i \cap M_j, i \ne j$ binary assignment and sequencing variables; $x_{ijk}=1$ denotes that job i immediately precedes job j on machine k.

The multi-objective scheduling problem can be formulated as a mathematical model where the three objective function components in (1) are aggregated into a scalar function. Particular attention must be given to the way such an aggregation is performed since the objective components have different dimensions (time and energy) and their conversion to a common dimension (e.g., cost) may not always be practical. In addition, it may not be easy for the decision-maker to express a preference considering the original dimension for the objectives components. In these cases a suitable possibility is to adopt a minimum deviation method to find the best compromise solution, defining the following normalized scalar objective function F:

$$\begin{aligned} F(\theta ) = \sum _{g=1}^{3} \Pi _g \cdot \frac{f_{g}(\theta ) - f_g^{-}}{f_g^+ - f_g^{-}} \end{aligned}$$

(2)

where $\theta$ is the vector of the problem variables and $f_g(\theta )$, $g = 1,2,3$, represents the three objective function components, i.e., the total weighted tardiness $\hbox {Dd}(\theta )$, the total energy cost $\hbox {En}(\theta )$ and the total setup cost $\hbox {Sc}(\theta )$, expressed as a function of the variables in $\theta$ as follows

$$\begin{aligned} \hbox {Dd}(\theta )= & {} f_1(\theta ) = \sum _{j \in J} W_j \cdot t_j\end{aligned}$$

(3)

$$\begin{aligned} \hbox {En}(\theta )= & {} f_2(\theta ) = \sum _{j \in J} \sum _{k \in M_j} E_{jk} \sum _{\begin{array}{c} i \in J_k\\ i \ne j \end{array}} x_{ijk}\end{aligned}$$

(4)

$$\begin{aligned} \hbox {Sc}(\theta )= & {} f_3(\theta ) = C \sum _{k \in M} \sum _{i \in J_k} \sum _{\begin{array}{c} j \in J_k\\ j \ne i \end{array}} S_{ijk}\cdot x_{ijk} \end{aligned}$$

(5)

In (2) $f_g^-$ represents the best (i.e., minimum) value for the gth component when this is optimized individually, whereas $f_g^+$ is an suitable estimation of the worse value that can be assumed by the gth component. In particular, $f_g^+$ can be fixed equal to $\max _{h \ne g}f_g(\theta _h^*)$, where $\theta _h^*$ is the optimal solution found when the objective $f_h(\theta )$ is individually optimized, i.e., $f_g^+$ is the worst value obtained for the gth component corresponding to the solutions optimizing the other components $h\ne g$. The weights $\Pi _g$, $g = 1,2,3$, in (2) express the relative importance given by the decision maker to the different objective components and are selected such that $\sum _g \Pi _g = 1$. Note that the use of function (2) increases the computational burden, since the computation of $f_g^-$ and $f_g^+$ requires to solve a single objective optimization for each objective function component. Then, the resulting MIP formulation is

$$\begin{aligned}&\min F(\theta )\end{aligned}$$

(6)

$$\begin{aligned}&\text {s.t.} \nonumber \\&\sum _{k \in M}\sum _{i=0}^{n} x_{ijk}=1\quad \forall j\in J \end{aligned}$$

(7)

$$\begin{aligned}&\sum _{k \in M}\sum _{j=1}^{n+1} x_{ijk}=1\quad \forall i \in J \end{aligned}$$

(8)

$$\begin{aligned}&\sum _{i=0}^{n} x_{ijk}=\sum _{h=1}^{n+1} x_{jhk}\quad \forall j \in J, k \in M_j \end{aligned}$$

(9)

$$\begin{aligned}&\sum _{j=1}^{n} x_{0jk} \le 1\quad \forall k \in M \end{aligned}$$

(10)

$$\begin{aligned}&c_j \ge R_j + \sum _{k\in M}T_{jk} \sum _{i=0}^{n} x_{ijk}\quad \forall j \in J \end{aligned}$$

(11)

$$\begin{aligned}&t_j \ge c_j - D_j\quad \forall j \in J \end{aligned}$$

(12)

$$\begin{aligned}&c_j \ge c_i + T_{jk}+S_{ijk} -B \cdot (1- x_{ijk}) \nonumber \\&\quad \forall k \in M, \forall i,j \in J_k, i \ne j \end{aligned}$$

(13)

$$\begin{aligned}&c_0 = 0 \end{aligned}$$

(14)

$$\begin{aligned}&t_j \in \mathfrak {R}_+, c_j \in \mathfrak {R}_+ \qquad \forall j \in J \end{aligned}$$

(15)

$$\begin{aligned}&x_{ijk} \in \{0, 1\} \qquad \forall i,j \in J, i \ne j, k \in M_i \cap M_j \end{aligned}$$

(16)

Constraints (7) and (8) impose that each job must be assigned to one machine and it is preceded and followed by a single job (the job preceded by the fictitious job 0 is the first job on a machine, whereas the job followed by job $n+1$ is the last one). Constraints (9) guarantee the flow conservation, ensuring that if job j is scheduled on machine k, then j has a predecessor and a successor on k. Constraints (10) impose that, at most, a single job is the first scheduled on each machine. Constraints (11) define the lower bound for the job completion time, whereas (12) define the job tardiness. Constraints (13) control the job completion times ensuring that each machine processes one job at a time and that the setup time between two successive jobs is satisfied; such constraints establish that $c_j \ge c_i + T_{jk} + S_{ijk}$ if $x_{ijk} = 1$, otherwise they become redundant. Constraints (14) fix the completion time for the dummy job 0 and (15) and (16) define the problem variables.

5 The scheduling algorithm

The considered scheduling problem clearly generalizes well-known computationally intractable problems, as the single machine total weighted tardiness problem, and then belongs to the class of NP-hard problems (Lawler 1997).

5.1 The detailed scheduling support system

The software company DSSS has been devised as based on a heuristic scheduling approach, which essentially performs a discrete event simulation. This means that the schedule is defined progressively by simulating the time evolution in the shop floor, and scheduling decisions are taken at the occurrence of events. Specifically, two types of events are considered in DSSS:

• End events, corresponding to the instants at which a machine become available, usually when a job performed on a machine is completed;

• Release events, corresponding to the instants at which the processing of a job can start.

The heuristic exploited in the DSSS is basically a constructive one that, at the occurrence of each event, considers the machines in a given order and selects, among the ready jobs, the next to be sequenced on the current machine using a simple lexicographic priority rule (e.g., earliest due date, evaluating job priority in case of tie, and then shortest setup time).

The reason for such a simple approach comes from the company’s need of dealing, in a computational efficient way, with scheduling contexts possibly including many other complicating constraints, such as, precedence relationships with minimum and maximum time lags, material availability, human resource availability and shifts. Hence, the company conceived the DSSS as a decision support system that is able to quickly generate a solution, even if not feasible, in many different scheduling contexts, possibly warning the decision maker about the need of manually adjusting the solution.

5.2 The metaheuristic extension of the DSSS

The devised extension of the DSSS is based on three different kinds of improvements. First, the DSSS simulation-based constructive heuristics is exploited in a stochastic iterated local search algorithm. Second, a Greedy Randomized Adaptive Search Procedure (GRASP) like rule is used to take the local assignment decisions. Third, a multi-objective optimization method is adopted to allow the decision-makers to express trade-offs between the three considered objectives.

The proposed metaheuristic extension (ME) of the DSSS yielded an algorithm with four main steps:

• 1. Initialization, consisting in loading the problem data, and generating the initial events; the iteration index h is set $h = 0$;

• 2. Event simulation and generation of a candidate schedule;

• 3. Schedule evaluation, possibly updating the current best solution; $h = h+1$;

• 4. If $h \le H$, the maximum number of iterations (an algorithm parameter), go to step 2, otherwise the procedure terminates.

5.3 Step 1

In step 1 the algorithm loads from the company database all the data relevant to the given scheduling horizon, i.e., the jobs to be scheduled and the current state of the machines, and initializes the list of future events.

5.4 Step 2

Step 2 is the algorithm core, as it is responsible of the generation of candidate schedules. Step 2 consists in a discrete events simulation of the timetabling process that determines the start time of the jobs on the machines: basically, at the occurrence of an event a scheduling decision is taken, i.e., a job that has become ready can be sequenced on a compatible available machine, or a job waiting for processing can be sequenced on a machine that has become idle.

At the occurrence of an event the decisions about which is the next job to be sequenced and on which machine it is assigned, must be taken. Hence, the role of simulation is to progressively define the timetable, setting the correct start and end times for the jobs, considering the time constraints. Such a behaviour is similar to that of scheduling approaches based on rather simple dispatching rules (Pinedo 2012), where decisions are taken by sorting the executable jobs and the available machines according to some index (e.g., the due date) and assigning the first job to the first compatible machine. Differently, the proposed algorithm iterates the construction of a sequence of alternative solutions, performing in this way a local exploration of different scheduling decisions. In particular, in order to favour the identification of a global optimum, the alternative solutions are determined by means of stochastic rules as they usually reduce the risk of being trapped in local optima.

Formally, let t be the current simulation time at which the next event to be processed occurs, $\hbox {SB}$ the current best solution and $\hbox {SR}$ the current reference solution. In step 2, at time t the algorithm performs the following event processing procedure:

• 1. All the events that simultaneously occur at time t are processed, and consequently the list of jobs ready to start and the list M of the available machines at time t are updated; machines in M are randomly ordered;

• 2. The machines in M are considered one at a time according to the order determined in 1. Let k be the current machine; the list $E_k$ of jobs ready to be executed on k is computed. The next job $\tau$ to be assigned to k is determined according to the following procedure based on a modified GRASP:

  • 2.1 $E_k$ is sorted according to the start times of the jobs in the reference solution $\hbox {SR}$ (possible ties are randomly broken); at the first iteration, when $\hbox {SR}$ is not yet defined, the jobs are sorted according to the original DSSS lexicographic order rule;

  • 2.2 An ordered candidate job list $C_k = (\tau _1,\ldots , \tau _r)$, composed by the first r (an algorithm parameter) jobs in $E_k$, is build and the following selection probability is assigned to the jobs in $C_k$

    $$\begin{aligned}&P_i=\frac{\pi _i}{\sum _{h=1}^{r} \pi _h}\nonumber \\&\quad \text {with}\ \pi _i = \frac{r-i}{r-1}+\pi _{\min } \quad i=1,\ldots , r \end{aligned}$$

    (17)

    being $\pi _{\min }$ a small positive value a priori fixed;

  • 2.3 A candidate job $\tau _C \in C_k$ is randomly determined according to the probabilities in (17);

  • 2.4 The next job $\tau$ to be assigned to machine k is determined by an exploration versus exploitation rule: a random number q is extracted from the uniform distribution U[0, 1] and if $q < q_0$, where $q_0$ is a fixed exploitation threshold (an algorithm parameter), then $\tau = \tau _1$ otherwise $\tau = \tau _C$.

  After the assignment of $\tau$ to k the future event list is updated, k is removed from the machine set, $M = M {\setminus } \{k\}$ and step 2 is iterated until the machine set is empty, $M =\emptyset$.

The above event processing procedure is performed at each event until the simulation ends and a complete candidate schedule $\hbox {SC}$ is generated.

5.5 Step 3

In step 3, the candidate schedule $\hbox {SC}$ is evaluated taking into account the three objectives function components in (1). In particular, the percentage deviation $\Delta Z(\hbox {SC})$ of $\hbox {SC}$ with respect to $\hbox {SB}$ is computed as detailed in the next Sect. 5.6. If $\Delta Z(\hbox {SC}) >0$ then the best schedule ($\hbox {SB}$) and the reference schedule ($\hbox {SR}$) are updated ($\hbox {SB} = \hbox {SC}$ and $\hbox {SR} = \hbox {SC}$); otherwise a Simulated Annealing like acceptance rule is used to update $\hbox {SR}$ to a solution worse than $\hbox {SB}$: $\hbox {SR} = \hbox {SC}$ according to the probability $P=\exp (\Delta Z(\hbox {SC})/T_h)$, where $T_h$ is a control parameter (the so-called temperature), initialized with a value $T_0$ and exponentially reduced at each iteration as $T_h=\alpha \cdot T_{h-1}$ where $\alpha$ is the cooling factor.

5.6 The multi-objective evaluation method

As discussed in Sect. 4, the minimum deviation method can be used to convert the multi-objective function in (1) into a scalar one. However such a strategy relies on the possibility of identifying suitable estimates for the $f_g^-$ and $f_g^+$ values; this cannot always be true when using a stochastic algorithm, unless a sufficient number of runs of the algorithm are performed; in addition, as noted, this method increases the computational burden. A better strategy is to adopt a sort of online minimum deviation method that determines the overall weighted percentage deviation of a solution S from the current best solution $\hbox {SB}$ as follows

$$\begin{aligned} \Delta Z(S) = \min \sum _{g=1}^{3} \Pi _g \cdot \frac{f_g^B - f_g(S)}{f_g^B} \end{aligned}$$

(18)

where $f_g^B$ denotes the value of the gth objective component for $\hbox {SB}$.

Another issue regards the typical difficulty of decision-makers in directly expressing the value of the weights $\Pi _g$. In order to identify a suitable set of weights $\Pi _g$ for the scalar function (18), the following procedure that aims at eliciting the local trade-offs between the objective components is used. Considering a pair of objectives g and $g'$, a base solution $S_0$ (e.g., the initial one) is proposed to the decision-maker, as well as a hypothetical solution $\hat{S}_{(g)}$ obtained from $S_0$ by improving g of $\Delta f_g$. Figure 1 provides and example of such a construction in the space of the objective functions $f_g$ and $f_{g'}$, where $S_0$ corresponds to the point $(f_g^\circ ,f_{g'}^\circ )$ and $\hat{S}_{(g)}$ to the point $(\hat{f}_g,f_{g'}^\circ )$. The decision-maker is then requested to express a local trade-off between g and $g'$ by specifying a third possible solution $\hat{S}_{(g')}$ (e.g., the point $(f_g^\circ ,\hat{f}_{g'})$ in Fig. 1) that improves $S_0$ as regards objective $g'$ and that the decision-maker judges equivalent to $\hat{S}_{(g)}$.

Fig. 1

Elicitation of trade-offs from the decision-maker

For the considered problem, the decision-maker is asked to evaluate, with respect to the base solution $S_0$, a percentage improvement in the total tardiness $\Delta \hbox {Dd}$ against a percentage improvement, respectively, in the energy consumption $\Delta \hbox {En}$ and in the total setup time $\Delta \hbox {Sc}$. Specifically, the resulting weights for the total tardiness, total setup and energy consumption objective components, are computed from the following three equations

$$\begin{aligned} \frac{\Pi _2}{\Pi _1}=\frac{\Delta \hbox {Dd}}{\Delta \hbox {En}} \quad \frac{\Pi _3}{\Pi _1}=\frac{\Delta \hbox {Dd}}{\Delta \hbox {Sc}} \quad \sum _{g=1}^{3}\Pi _g = 1 \end{aligned}$$

(19)

where $\Delta \hbox {Dd}$, $\Delta \hbox {En}$ and $\Delta \hbox {Sc}$ correspond to the following ratio $\Delta _g$, respectively, for $g=1, 2$, and 3

$$\begin{aligned} \Delta _g = \frac{f_{g}^{0}-\hat{f}_{g}}{\hat{f}_{g}} \end{aligned}$$

(20)

The aggregate objective function (18) hence represents the sum of the individual fractional deviations of the objectives, which are dimensionless numbers.

6 Experimental analysis

To validate the proposed approach, two sets of tests were performed. The first set considers a real case study consisting in a quite severe scheduling instance provided by the IM company involved in the project; whereas, in the second one, two sets of random instances are used. Both the tests compare the existing detailed scheduling support system (DSSS) with the one including the proposed metaheuristic extension (ME); in addition, ME is compared to a commercial MIP solver implementing the formulation of Sect. 4 on a set of random instances.

6.1 Tests on a real scenario

The IM company provided a test instance coming from a real scheduling scenario with 488 jobs, corresponding to single production orders, to be scheduled on a set of 88 IM machines. The average job processing times on the machines have the distribution pattern shown in Fig. 2, where the job durations range between 30 min and 6 months, with an average duration of 3.5 days. About 30.5 % of the jobs can be executed by only one machine; in addition, the energy consumption for alternative machines varies on the average ${\pm }3~\%$ around the mean value. It was observed that most of the jobs (373 over 488) have a due date preceding the start date of the scheduling horizon. This fact highlights a tardiness offset for the instance of about 18.9 days on the average for each job.

Fig. 2

Average job processing times distribution

Preliminary tuning tests permitted to set the ME algorithm’s parameters: the length of the job candidate list was fixed $r = 4$, the exploitation threshold $q_0 = 0.9$, and the cooling factor $\alpha = 0.95$. The initial control parameter $T_0$ was set so that a $10~\%$ worsening in the objective is accepted with a $90~\%$ probability. The maximum number of iterations was fixed $H = 500$, where each iteration consists in the generation of a solution by the simulation performed in step 2 of the algorithm. With this termination condition the computation time required was about 240 s on a 2.4 GHz Intel Core 2 Duo E6600 notebook. Since the implemented approach has a random nature, the considered results correspond to averages over 5 independent runs.

The first test compared the total tardiness, total setup time and energy consumption obtained by the original DSSS with the ones generated by ME, in particular focusing only on the minimization of the total tardiness. Thus, for this test the weights $\Pi _1 = 1$ and $\Pi _2 = \Pi _3 = 0$, were used for ME, so neglecting setup and energy optimization. The obtained results are reported in Table 1 in the DSSS and ME(1) rows. Note that Table 1 shows the tardiness results both including (offset) and excluding (no offset) the tardiness contribution for the jobs whose due date precedes the start of the scheduling horizon.

Table 1 Results comparison for the first and second test

Table 1 shows that ME is able to improve the total tardiness of 1.21 % (9.22 % excluding the offset); a remarkable result is the great improvement (36.36 %) of the total setup. Clearly, setup time reduction allows the earlier completion of a subset of jobs and produces a benefit for the overall tardiness. The improvements in the tardiness and setup obtained by ME are paid by an increase (1.72 %) in the energy consumption objective.

Fig. 3

Percentage variations of the total tardiness and energy consumption objectives as function of iterations for the first test

Figure 3 shows the percentage variations of the total tardiness and energy consumption objectives referred to their best values as a function of iterations: the monotonic behaviour of the total tardiness is justified by the fact that tardiness was the only objective optimized by the proposed algorithm.

The second test consisted in the multi-objective optimization of the three considered objectives. The method described in Sect. 5.6 was applied to determine the values for the weights from the company decision-makers, obtaining $\Pi _1 = 0.6$, $\Pi _2 = 0.35$ and $\Pi _3 = 0.05$. The average results yielded by the multi-objective optimization of second test are also shown in Table 1 in correspondence with the ME(2) row. It can be observed that ME was able to improve all the three objectives when compared to the original commercial scheduler. In particular, ME produced a better compromise solution than the one provided for the first test: the worsening of 0.53 % in total tardiness (4.42 % neglecting the offset) and of 8 % in total setup, combined with the improvement of 3.62 % in the energy consumption, generate, according to the selected objective weights, an improvement in the overall objective of 0.55 % with respect to the solution obtained by ME in the first test.

Fig. 4

Percentage variations of total tardiness and energy consumption for the second tests

Figure 4, similarly to Fig. 3, reports the percentage variations from their best values, of the total tardiness, total energy consumption, and the overall objective, as a function of the algorithms iterations. Even for the second test the overall objective presents a monotonic decreasing behaviour that is in general obtained with different combinations of the three components, tardiness, setup time and energy.

6.2 Tests on random instances

The second set of tests was performed to evaluate ME compared to DSSS for a large number of instances which share some similarities with the real case study considered in the first set of tests. In each instances 500 jobs have to be scheduled on 90 unrelated machines. Since in the real case study the average number of eligible machines for job was about 10, the machine eligibility was randomly determined according to the probability $P_e(k, j) = {1}/{m}+0.1$. The processing times and setup times were randomly generated according to the distributions that best fit the relevant data in the instance provided by the IM company. In particular, for the processing times a generalized extreme value distribution characterized by shape $\xi =1.09$, scale $\sigma =8.76$ and location $\mu =7.03$ was used, whereas for the setup times a generalized Pareto distribution with shape $\xi =0.12$, location $\mu =0.5$ and scale fixed to three alternative values $\sigma \in \{5.27, 10.27, 15.27\}$ in order to model three different classes of setup times, respectively, denoted as short (Sh), medium (Me) and large (Lg). In this way, the medium setup times resulted on the average about 2.8 greater than the shorter ones and the large setup times 2.6 greater than the medium ones. The generation of the release dates and due dates followed a procedure as suggested in Hall and Posner (2001). In particular, the release dates were generated from the uniform distribution $U[0, \bar{C}\cdot r_\mathrm{R}]$, where $\bar{C}$ is the estimation of average maximum completion time (i.e., makespan) on the machines computed as

$$\begin{aligned} \bar{C}=\frac{1}{m} \sum _{k \in M}\left( \sum _{j \in J_k} P_{jk} + \frac{1}{n-1}\sum _{i \in J_k}\sum _{\begin{array}{c} j \in J_k\\ j \ne i \end{array}} S_{ijk}\right) \end{aligned}$$

(21)

and $r_\mathrm{R}$ is the ready date range factor selected as $r_\mathrm{R} \in \{0.2, 0.6, 1, 1.4, 1.8 \}$. The due dates were generated from the uniform distribution $U[D_{\min }, D_{\max }]$ where $D_{\min } = \max (0, \bar{C}(1-\tau -r_\mathrm{D}/2))$ and $D_{\max }=\bar{C}(1-\tau +r_\mathrm{D}/2)$, being $\tau$ the tardiness tightness and $r_\mathrm{D}$ the due date range, both fixed in $\{0.2, 0.4, 0.6, 0.8, 1\}$. Note that the tardiness tightness is associated with the proportion of the jobs that are expected to be late and it influences the average due date, whereas the due date range represents the range of the due dates as a proportion of the expected makespan. Finally, the energy consumption for each admissible job-machine assignment were generated as $E_{jk} \sim U[50, 100]$ kWh. For each combination of the parameters characterizing the setup time, due dates and release dates, 5 instances were generated, producing a set of 1875 instances. The tests considered two versions of ME: the extended algorithm as described in Sect. 5, which use the reference solution $\hbox {SR}$ to provide a sort of memory to the GRASP rule in step 2, denoted as ${{\text {ME}}}_{\text {S}}$; the ME algorithm that in step 2 does not use the reference solution but, as in the first iteration, always sorts the jobs according to the original DSSS lexicographic rule, denoted as ${{\text {ME}}}_{\text {W}}$.

Table 2 Overall comparisons for the second set of tests

Table 2 reports the overall comparison of the results obtained by DSSS, ${\text {ME}}_{\text {W}}$ and ${\text {ME}}_{\text {S}}$ averaged on the whole set of instances. In particular, the first three columns in Table 2 show the average percentage deviations from the best objective value for the three objective function components in (1), computed as $(f_{g} - f_{g}^{\mathrm{best}})/f_{g}^{\mathrm{best}}$, whereas the last column reports the average percentage deviations for the aggregated objective function according to the weights $\Pi _g$. Table 2 clearly highlights the quality of the extended algorithm compared to the original one. In addition, the algorithm ${\text {ME}}_{\text {S}}$, which exploits the reference solution, outperforms ${\text {ME}}_{\text {W}}$ as regards the most relevant total tardiness objective (Dd), so that the overall objective turns out to be significantly the best even from a statistical point of view.

Table 3 The percentage deviation results for the different classes of setup times

Fig. 5

Percentage worsening of the solutions as a function of the classes of setup times

The comparison of the results obtained for the three different classes of setup times is provided by Table 3, whose structure is similar to Table 2. As it can be noted, there is a generalized worsening in the solutions moving from short to large setup times. However, the overall results of ME clearly outperforms for each classes of setup times the ones of DSSS, and ${\text {ME}}_{\text {S}}$ always appears the best algorithm, confirming the effectiveness of using the reference solution in the GRASP rule for local decisions. In addition, Fig. 5 provides a graphic representation of the relative percentage worsening of the quality of the results for the three compared algorithms as a function of the increase of the setup times; again, from Fig. 5, ${\text {ME}}_{\text {S}}$ results the approach with the lowest relative decrease of performance due to the increase of setup times.

Table 4 reports the average percentage deviations as a function of the different values for the tardiness tightness and the due dates and release dates ranges. Even in this case, observing the results in the first five columns, the superiority of ${\text {ME}}_{\text {S}}$ algorithm emerges. However, it appears that the difference between the performance of the three algorithms decreases when the difficulty in optimizing the main objective increases (i.e., when also the values of the three parameters increase). The last column of Table 4 shows the coefficient of variation ($C_\mathrm{v}$), computed as the ratio of the standard deviation to the mean of the data in the rows, that is used describe the dispersion of the row data independently from their magnitude. Then, column $C_\mathrm{v}$ point out the greater stability of ${\text {ME}}_{\text {S}}$ algorithm in providing the best results for considered set of test.

Table 4 The percentage deviation results for the different value of $\tau$, $r_\mathrm{D}$ and $r_\mathrm{R}$

The final test aimed at comparing ${\text {ME}}_{\text {S}}$ with a commercial MIP solver, specifically IBM ILOG CPLEX 12.6. This test, however, raised some issues, highlighting the difficulty in using the MIP formulation for the considered industrial context. First of all, it was not possible to base the comparison neither on the real test instance nor on the set of large random instances with 500 jobs and 90 machines, since the MIP solver always run out of memory on the available hardware when generating the model for the formulation of Sect. 4. Thus, after several trials, a different set of 375 random instances of smaller dimension, i.e., 50 jobs and 5 machines, was finally generated. A second issue is the different kind of normalization used in (2) (that also need three additional runs of the solver to determine the $f_g^-$ and $f_g^+$ parameters) with respect to the online minimum deviation normalization adopted in the metaheuristics. To make the comparison possible, the objective minimized by the ${\text {ME}}_{\text {S}}$ was changed to the scalar function $F(\theta )$ with the same parameter values used for the MIP solver.

Having fixed a 3600 s time limit, the MIP solver was able to optimally solve 63 % of the instances in an overall average time of 1378 seconds, with an average optimality gap for the instances not optimally solved of 16.3 %. On the other hand, the average time needed by ${\text {ME}}_{\text {S}}$ to complete $H = 500$ iterations was about 30 s; within such a time the ${\text {ME}}_{\text {S}}$ found 52 % of the optimal solutions determined by the MIP solver and its overall average percentage deviation from the MIP solver results was 1.1 %, with an average optimality gap for the instances not solved optimally of 8.4 % and a −97.8 % of computation time deviation. These results confirm the effectiveness of the proposed algorithm even on this smaller dimension instance set.

7 Conclusions

Despite its low energy efficiency, plastic injection moulding process, characterized by high production rate, provides 32 % by weight of plastic products. Generally, in this context, energy consumption costs are considered as externalities and efforts to improve EE usually focused only on technology and process parameters.

In this paper, an alternative approach for EE, experimented in a real IM industry, is proposed. This approach is based on the availability of data regarding the actual energy consumption of each product–machine combination, provided by a monitoring system set up in the considered industry. Such data permitted to extend an existing detailed scheduling support system, provided by an Italian software company, by devising a new multi-objective scheduling optimization algorithm able to take into account due date constraints, setup times and energy consumptions. The validation of the overall algorithm, performed both on an actual scenario provided by test case company and on a set of random generated instances, showed the algorithm capability of simultaneously improving the total tardiness, the total setup time and the energy efficiency. In particular, the latter improvement observed in the real test case, although limited to 1.83 %, represents a very valuable result if one considers the total amount of energy spent by the IM industry.