Leveraging constraint-based approaches for multi-objective flexible flow-shop scheduling with energy costs

1 Introduction

Over the last years, due to the increasing importance of the energy and environmental factors in society, the need to include such factors among the optimisation requirements of industrial processes has become more and more compelling. As a result, the scheduling problems typically built on top of the production processes (i.e., Job Shops problems, Flow Shops problems, etc.) and historically revolving around time-based objective functions (e.g., completion time, tardiness, workload, changeover time), have been progressively extended to the multi-objective case, including both energy and environment-related costs (e.g., peak-power load, energy consumption, associated carbon footprint) [3, 5, 17].

This work considers a flexible flow-shop environment where a set of M machines partitioned over q production stages are employed to execute n jobs. Each activity in a job has a set of possible execution modes with different trade-off between energy consumed and processing time. Moreover, global energy consumption may also depend on the possibility to switch-off the machines during the idle periods. The goal of this work is to widen the knowledge about constraint-based stochastic local search (SLS) [9] performance capabilities in the multi-objective realm.

According to literature [10, 19] the methods for solving multi-objective optimisation problems can be classified into three groups, given the phase in which the user involved in the decision making process expresses his/her preferences: the a priori, the interactive, and the a posteriori methods.

In the a priori methods the user expresses his/her preferences before starting the solution process (e.g., the weights to the objective functions). The drawback of this approach is that it is very difficult for a decision maker to accurately quantify his/her preferences, because he/she never sees the whole set of efficient solutions (the Pareto front) or an approximation of it. In the interactive methods, computation phases are interleaved with user-interaction phases on behalf of the decision maker. The user progressively drives the search with her/his answers towards the most preferred solution. While in this approach the drawback related to the lack of knowledge about the Pareto front is less severe, yet the most preferred solution clearly depends on what the user progressively discovers during the computation. Finally, in the a posteriori method the Pareto front (or its approximate representation) is generated first, and then the decision maker selects the most preferred solution. Despite the a posteriori methods are generally the least popular due to their heavy computational burden, the fact that none of the potential solutions is left undiscovered strengthens the confidence of the decision makers on the final decision [18, 19].

In this work we will focus on the a posteriori methods, leveraging in particular their ability of efficiently finding high quality approximations of the solution Pareto front. To this aim, we focus on two different meta-heuristic approaches for solving the proposed multi-objective scheduling problem based on SLS algorithms: (i) an ɛ-constraint based approach [10, 14], and (ii) a multi-objective Large Neighbourhood Search LNS optimisation approach [22]. Meta-heuristic procedures are typically composed of a number of different components, each of which should contribute to the final solving capabilities of the algorithm. In particular, in this work we compare the performances of both approaches, empirically analysing the effects of the algorithmic components on the proposed problem. Such analysis is done both using some benchmarks and case studies taken from the literature [3], and proposing new benchmarks representing increasingly difficult multi-objective scheduling instances with makespan and energy consumption as objective functions.

The paper is organized as follows. Section 2 defines the class of scheduling problems with energy costs tackled in this work, while Section 3 provides an overview of the constraint-based reasoning paradigm used to implement the solving procedures. Such procedures will be described in details in Sections 4 and 5, respectively. Subsequently, an experimental analysis that assesses the performance of the proposed algorithms against the benchmark of reference and summarises some important observations, is provided in Section 6. Finally, a concluding section ends the paper.

2 The energy-FFS scheduling problem

The Energy-FFS (ENFFS) entails synchronising the use of a set M of r machines to perform a set of n _J jobs J = { J 1 , … , J n J }, according to a multi-stage production process. In order to complete the production process, each job has to pass all the q productions stages (see Fig. 1) in the same order which cannot be modified. Job reentry is not allowed, hence each job is composed of exactly q operations. Let M _k  = {m_k1, m_k2, …, m _{kr k} } the set of machines in each production stage k = 1 … q; each machine belongs to just one production stage, such that ∪ k = 1 q M k = M and M _i ∩ M _j  = ∅ with i ≠ j (∑ k = 1 q r k = r ).

One job can be processed by only one machine at each production stage; each machine can process at most one job at a time. Each machine is available at time t = 0 and all the jobs are released at time t = 0. No preemption is allowed. Let O the set of all the job operations a _jk , such that a _jk is the k-th operation of job j: a _jk requires the exclusive use of a single machinem ∈ M _k for its entire duration. The machines M _k that can be assigned to a _jk are generally characterised by different working speeds and different energy consumption. More concretely, the processing time d jk m of each activity a _jk depends on the assigned machine m ∈ M _k , such that e jk - s jk = d jk m (constant value), where the variables s _jk and e _jk represent the start and end time of a _jk . Similarly, the execution of each operation a _jk is associated with a determined power consumption P jk m, which depends on m ∈ M _k . According to [3], the value E jk m = P jk m d jk m represents the basic energy consumption of the operation a _jk to maintain the machine m ∈ M _k in the on-state, and the value P jk m is called unload power. It should be underscored at this point that the execution of the operation a _jk should also include the consumption of an additional amount of energy, the so-called cutting energy component (i.e., the energy consumed by the machine when a job is processed with a certain speed). However, following the approach used in [3], such component of the energy is not taken into account for the optimisation purposes because its value is considered constant and independent of the machine m ∈ M _k and hence, it can be ignored.

Figure 2 depicts an example of ENFFS scheduling problem with n _J  = 3 jobs and q = 3 production stages, where the first stage contains one machine (m₁₁), the second stage contains two machines (m₂₁ and m₂₂), and the third stage contains one machine (m₃₁). As the reader can observe, each operation of each job is characterised by as many duration and power value pairs as are the machines contained in the stage of interest. For example, operation a₂₂ is characterised by a duration of 4 minutes on machine m₂₁ and 9 minutes on machine m₂₂, whereas the power consumption is 2.8 kW on machine m₂₁ and 3.7 kW on machine m₂₂.

A solutionSol = { ( s 11 ¯ , m 11 ¯ ) , ( s 12 ¯ , m 12 ¯ ) , … ,( s n J q ¯ , m n J q ¯ ) } of the ENFFS problem is a set of pairs ( s jk ¯ , m jk ¯ ), where s jk ¯ is the assigned start-time of operation a _jk , m jk ¯ is the selected machine for a _jk , and all the constraints previously described are satisfied.

Let C _k be the completion time for the job J _k , the makespan of the solution is the value C max = max 1 ≤ k ≤ n J { C k }. Given a solution Sol, let us define the overall energy consumption E as E = E basic + E unload(1) The first component E _basic represents the sum of all basic energy consumptions of the operations a _jk . E basic = ∑ j = 1 n J ∑ k = 1 q P jk m jk ¯ d jk m jk ¯(2) The second term E _unload represents the sum of all idle energy consumptions in Sol, which is computed as follows. For each machine m and for each pair of consecutive operations (u, v) executing on that machine and separated by a temporal distance T_u,v = s _v  - e _u , the idle energy consumption E unload m ( u , v ), used in between the pair of operations, is bounded by the so-called turn-off-on energy E off - on m, i.e., the energy required to switch off and again on the machine m. Hence, E unload m ( u , v ) = min { E off - on m , P u m T uv }, where P u m is the unload power of machine m when the operation u is executed (see Fig. 3). Hence, we have E u n l o a d = ∑ m ∈ M ∑ u ∈ O m , v = succ m ( u ) , v ≠ n i l E u n l o a d m ( u , v )(3)

Where O _m is the set of operations a _jk assigned to machine m in Sol, and succ _m  () is a successor function representing the total order imposed on the set of operations O _m .

We observe that the value T s m = E on - off m / P u m is the break-even temporal distance between any two consecutive activities (operating on the same machine m) beyond which it is convenient to turn off the machine m and within which it is convenient to leave it on.

The objective of the present analysis is the minimisation of both the total energy consumption E and the overall completion time C _max . However, the possibly conflicting nature of these two objectives may prevent the existence of a unique solution Sol^* that is optimal w.r.t. both the objectives. Therefore, in this work we are interested in the set of all optimal “tradeoffs”, which are known as the Pareto optimal solutions. A Pareto optimal solution is a solution such that the improvement of one objective necessarily implies the worsening of the other objective. More formally, given two solutions Sol (C _max , E) and Sol ′ ( C max ′ , E ′ ) characterised by the given objective functions, SoldominatesSol′, represented in the following as Sol ≺ Sol′, if ( C max < C max ′ ∧ E ≤ E ′ ) ∨ ( C max ≤ C max ′ ∧ E < E ′ ). The Pareto set PS^* is the set of solutions Sol, such that for each Sol ∈ PS^* there is no solution Sol′ which dominates Sol (Sol′ ≺ Sol). A Pareto Set for a bi-dimensional optimisation problem such as the ENFFS can be graphically represented as in Fig. 4.

The ENFFS is a computationally hard problem since it is an extension of the single objective Flexible Flow Shop Scheduling problem which is NP-hard [7].

Figure 5 shows a solution of the problem represented in Fig. 2. In the solution, all machines start in the off state, and they are turned on as soon as they have to process one job); moreover, the sequencing order pertaining to the activities of the three jobs is maintained, and no machine is busy processing more than one job at a time. It should be noted that, depending on the length of the idle interval between two different activities processed by the same machines, the latter can either remain on or be turned off. Particularly in the figure, the machine m₂₂ remains turned on between the processing of jobs J₁ and J₂, while the machine m₃₁ is turned off between the processing of jobs J₂ and J₃, while it remains on between the processing of jobs J₁ and J₂. The reader can easily verify that it is convenient to turn offm₃₁ between J₂ and J₃, as the temporal distance between the two jobs (9 minutes, i.e., 0.15 hours) is longer than m₃₁’s break-even temporal distance (computed as T s m 31 = E on - off m 31 / P unload m 31 ≃ 0.12).

Constraint Programming (CP) is a well-known declarative programming paradigm [1] suitable for solving constraint satisfaction and optimisation problems. A constraint program is defined as a set of decision variables, each ranging on a discrete domain of values, and a set of constraints that limit the possible combination of variable-value assignments. After a model of the problem is created, the solver interleaves two main steps: 1) constraint propagation, and 2) search. In the constraint propagation step, inconsistent values are progressively removed from variables domains. The search strategy step explores alternative assignments of variable-values until either a solution is found or a failure is detected. We represent the given ENFFS problem as a Constraint Satisfaction Problem (CSP) [20]. A CSP is defined by a set of variables, X₁, X₂, . . . , X _n , and a set of constraints, C₁, C₂, . . . , C _m . Each variable X _i has a nonempty domain D _i of possible values. Each constraint C _i involves some subset of the variables and specifies the allowable combinations of values for that subset. A solution of a CSP is defined as a consistent assignment of values to all of the variables X₁, X₂, . . . , X _n , i.e., an assignment that satisfies all the constraints. Constraint Programming is particularly suited for solving scheduling problems [16] where the decision variables correspond to the problem operations. In particular, each operation variable a is characterised at least by two features: s _a representing its start time, and d _a representing its duration. For scheduling problems, a number of different global constraints have been developed, the most important being the unary-resource constraint [27] for modelling simple machines, the cumulative resource constraint [16] for modelling, cumulative resources (e.g., a pool of workers), and the reservoir [13] for modelling consumable resources (e.g., a fuel tank). In particular, given unary-resource(Ops), the constraint holds if and only if all the operations in the set Ops never overlap each other at any point in time. A number of propagation algorithms are embedded in the unary-resource constraint for removing probably inconsistent assignments of operation start-time variables.

To tackle the ENFFS, in this work we compare two different CP-based approaches known in literature. In the first approach (called ɛ-constraint-based approach, and described in Section 4) the decision variables are the starting times s _jk of the operations a _jk  ∈ O and the variables x _jk  ∈ M _k , representing the set of machines which can be assigned to the operation a _jk . This approach is implemented on the IBM-ILOG CPLEX Optimization Studio CP Optimizer (v12.6.0), a known and efficient state-of-the-art CP development toolkit, and will be presented in Section 4. In the second approach (called Multi-objective Large Neighborhood Search, based on that used in [23] for single-objective makespan minimization, and described in Section 5), we focus on assigning resources to operations and on establishing precedence constraints between pairs of operations that require the same resource (machine), so as to eliminate all possible conflicts in the resource usage. Hence, in CSP terms, we identify two sets of decision variables: (i) a variable x _i , defined for each operation a _i to select one resource for its execution (the domain of x _i is the set of available machines M _k corresponding to the production stage k of a _i ), and (ii) a variable o _ijm , defined for each pair of operations a _i and a _j requiring the same machine m (i.e., where x _i  = x _j  = m) which can take one of the two values a _i  ⪯ a _j or a _j  ⪯ a _i , and representing the so-called disjunctive constraints. The main contribution of the this paper is the analysis of the performances of a Multi-objective Large Neighborhood Search procedure w.r.t. two versions of ɛ-constraint-based procedures (a basic and a state-of-the-art version) described in Section 4, against both a EnFFS benchmark recently proposed in the literature [3], and a set of new challenging instances of increasing size.

4 A ɛ-constraint based approach

A well-studied multi-objective optimisation method to generate the whole Pareto front is the ɛ-constraint method [18, 19]. The ɛ-constraint method works by choosing one objective function as the only objective and properly constraining the remaining objective functions during the optimization process. Through a systematic variation of the constraint bounds, different elements of the Pareto front can be obtained. In the following Section 4.1 we describe the ɛ-constraint method in two different forms, a basic form and a more advanced one; both versions can be used as a reference baseline for the empirical evaluation of the multi-objective LNS strategy proposed in Section 5. Both the ɛ-constraint methods take as an input parameter an optimisation procedure based on a Constraint Programming (CP) model, which will be described in Section 4.2.

In this section we propose a state-of-the-art meta-heuristic algorithm for solving the proposed multi-objective scheduling ENFFS problem. In particular, we propose a stochastic local search (SLS) algorithm [9] in line with the Large Neighbourhood Search (LNS) approaches proposed in [23, 26]. Such procedures are typically composed of a number of different components, each of which should contribute to the final solving capabilities of the algorithm.

Figure 8 describe the proposed algorithm named MO-LNS and Fig. 9 gives an intuition about how the optimisation proceeds. The algorithm takes in input an instance of the ENFFS problem prb, and a termination criteria tc (e.g., a max number of solving attempts). The idea is to generate and use a set of elite-solutions ES [8] where each solution S ∈ ES can be selected as a starting point for the generation of the final approximation of the Pareto set PS^* during the optimization process. The ES is composed of two subsets, a “non-dominated” component of solutions ES^*, corresponding to the best approximation of the Pareto set, and a “dominated” component ES^-, obtained as the subset of ES \ ES^* composed of all solutions that neither dominate nor are dominated by one another. Note that ES = ES^* ∪ ES^- and ES^*∩ ES^- = ∅. The core steps of the MO-LNS algorithm (i.e., the lines 3-6) implement a so-called Wave Strategy, which moves the elite set solutions towards the Pareto set PS^*. In particular, MO-LNS iteratively applies the Wave Strategy until the termination criteria tc is satisfied. At line 3 a solution S is selected from ES’s dominated component ES^-. Many selection strategies can be devised; the current strategy is based on a simple random selection of the elements in ES^-. Next, an optimisation strategy is selected (line 4); there are two different strategies: one focused on the minimisation of the completion time C _max and another one focused on the minimisation of the overall consumed energy E. In the currently implemented Wave Strategy selection policy, we choose the two strategies at random. Subsequently, an optimisation strategy is applied at line 5 via a LNS algorithm which is an extension of the algorithm proposed in [23]. A brief description of this algorithm is given in the next subsection (Section 5.1).

Finally, the algorithm updates the elite set ES (line 6). In order to control the degree of diversification in the search, we define a threshold Tr representing the max allowed distance (distance in the Cartesian plane C _max E) between the non-dominated and the dominated components of ES, called ESacceptance threshold (see also Fig. 10). The idea behind the threshold Tr separating the two sets ES^* and ES^- is inspired by well-known works such as  [4, 12]; in heuristic-based iterative optimization procedures it is often more effective to perform each iteration of the optimization cycle starting from a solution selected from a set of “sufficiently good” solutions, rather than directly selecting the best solution found so far (see, for example, [21]). In the multi-objective context of this work, the dominated subset ES^- simply represents the container of all such “sufficiently good” solutions, and the threshold Tr is the parameter that controls the maximum allowed quality difference between the ES^* and the ES^- subsets. Operationally, the Tr parameter is used to perform the update of the set ES, according to the following rationale: if the new solution S′ found at line 6 of the algorithm deserves to enter the ES^* set, it is saved there. Every possible solution S ∈ ES^* dominated by S′ is expunged from ES^* and possibly inserted in S ∈ ES^- (and again, all ES^- solutions possibly dominated by this last insertion are eliminated from ES^-). Please note that if the Pareto acceptance threshold Tr = 0, then ES^* ≡ ES^-.

The algorithm terminates at line 8, where the best approximation of the Pareto Set PS^* is extracted as the non-dominated component of the Elite Set ES obtained at the end of the optimization loop.

6 Experimental analysis

This section has the twofold objective of (i) comparing the performances of the constraint-based MO-LNS procedure presented in Section 5 with the performances of the CPɛ and CPɛ ^ad algorithms presented in Section 4 (see Figs. 6 and 7, respectively) against an ENFFS instance previously tackled in literature, and (ii) extending the same analysis against a novel ENFFS benchmark created with the purpose of progressively stressing the solver’s capabilities, thus providing the community with a wider set of increasingly difficult instances to foster future comparisons. The ENFFS instance against which we are going to compare the MO-LNS, CPɛ and CPɛ ^ad procedures is composed of 12 jobs and 3 production stages (i.e., each job has to undergo 3 production operations on 3 different machines, selected at each stage). In particular, stage S₁ has 3 available machines, stage S₂ has 2 available machines, and stage S₃ has 4 available machines. For each operation, the processing time and the energy consumption depend on the selected machine. Moreover, the idle energy consumption (E _unload ), used by each pair of operations on the same machine separated by a temporal distance T, is computed according to the formula E _unload  = min {E_on-off, (T * P _unload )/1.2} 1 , where P _unload defines the unload power. Please note that the E_on-off quantity is not a fixed value, and generally depends on the spindle speed at which the machine is working. For the full details about the particular ENFFS instance described above, the reader is referred to [3].

Figure 12 depicts the obtained results in the shape of four Pareto sets, comparing the results obtained in [3] (RCIM) with the results obtained with the MO-LNS, the CPɛ and the CPɛ ^ad procedures). Both the CPɛ and CPɛ ^ad Pareto sets shown in the plot have been built leveraging the ɛ-constraint based approaches (see [18] and [15], respectively), minimising the Energy (E) objective function while using the makespan (C _max ) objective function as a further constraint, and incorporating it in the constraint part of the model as shown in Section 4. In particular, for each test we have run the CPɛ and the CPɛ ^ad procedures 10 times, using as many progressively decreasing values of C _ɛ (see Section 4), and allowing maximum 1 minute per run (hence constraining to 10 minutes the maximum time to build the whole Pareto set, for each procedure). Relatively to the CPɛ procedure, the variability range of the C _max objective function has been selected to be equal to [ C min molns , C max molns ], where C min molns and C max molns are the minimum and maximum makespans found by the MO-LNS procedure, respectively. Both the CPɛ and CPɛ ^ad procedures have been implemented on the IBM-ILOG CPLEX Optimization Studio, a state-of-the-art commercial CP development toolkit. The test has been executed on a AMD Phenom II X4 Quad 3.5 Ghz under Linux Ubuntu 14.04.

Focusing on the MO-LNS algorithm presented in Fig. 8, the Wave Strategy employed for this test was based on a Random solution selection from the Elite Set (line 3), a random relaxation with γ = 0.2 during the LNS step (line 4), and on an Elite Set acceptance threshold equal to 0, i.e., considering only the non-dominated component of the Elite Set (line 6). As the plot in Fig. 12 shows, we have obtained significantly better results (the exact figures can be found in Table 1); as can be proved by simple visual inspection, the MOLNS Pareto Set is definitely well below the RCIM.

As clearly shown in the figure, both the CPɛ and the CPɛ ^ad procedures obtain even better results. This outcome was indeed expected, mainly due to the fact that, as opposed to the precedence constraint posting procedure at the core of the MO-LNS approach, the CPɛ’s and CPɛ ^ad ’s search space is not limited to that of the early start time solutions. In other words, both the ɛ-based procedures are free to explore a larger solution space where, given the non-regularity of the objectives of the flow shop problem tackled here (energy may decrease as the operation start-times increase, see [2] for more details) better energy-saving solutions can be found by properly right-shifting the operation chains on every machine. Interestingly, the CPɛ ^ad procedure provides slightly better results than CPɛ. However, this is not surprising result; as explained in Section 4, the CPɛ ^ad procedure leverages the advantage of the adaptive scheme to generate appropriate constraint values during the solving run, rather than determining such constraint values a priori.

Of course, while having access to a larger solution space increases the possibility to explore promising regions, it also increases the search burden. One interesting issue of the analysis that follows will be the investigation of whether (and to what extent) this “right-shift advantage” will depend on the size of the problem. It is in fact perfectly reasonable to expect that as the size of the problem increases, such advantage will be counteracted by the increased computational burden of exploring much larger search spaces.

In order to provide further results in line with the previous objective, we have generated four new ENFFS instances of increasing size EnFFSxN (N = 1, 2, 3, 4) starting from the original instance tackled above, where the operations exhibit a more pronounced inverse correlation between the processing time and the energy consumption, namely:

EnFFSx1 (12 jobs × 3 stages = 36 operations)

Figure 13 presents four plots (a), (b), (c) and (d) relatively pertaining to the four ENFFS novel instances outlined above. Each plot presents three Pareto sets (Best, Worst, and Best CPɛ) which were built according to the following rationale: Best and Worst respectively represent the best and worst Pareto sets obtained through the MO-LNS search, varying a number of search parameters as explained below, Best CPɛ represents the best Pareto set obtained by CPɛ, while Best CPɛ adaptive represents the best Pareto set obtained by CPɛ ^ad (the exact values for the Best Pareto sets only can be found in Table 2).

In particular, the MO-LNS parameters we have varied during the analysis are: (i) the relaxing factor γ ∈ {0.1, 0.2, 0.3, 0.4}, (ii) the MaxFail parameter which specifies the maximum number of non-improving moves that the algorithm will tolerate before terminating, with MaxFail ∈ {0, 10, 100, 1000}, and the Elite Set Threshold Tr ∈ {0,  min,  medium,  max} (all values are proportional to the instance size). In order to assess the influence on performance of the Threshold parameters within our Wave Strategy, Worst Pareto set is obtained varying the Elite Set Threshold Tr and keeping the other parameters fixed w.r.t. the best Pareto. The Solution selection strategy for all tests has been set to Random. Again, all tests have been executed by allotting a maximum CPU time of 10 minutes.

On the MO-LNS’s side, the results show that as the problem’s size increases (i.e., moving from the EnFFSx1 instance to the EnFFSx4 instance) the most promising policy consists in reducing the relaxing factor γ and concurrently increasing the Elite Set Threshold Tr. As for the MaxFail parameter, what can be learned in general is that lower MaxFail values tend to work better with bigger instances (i.e., with bigger instances it is more convenient to bet on exploration than on intensification). But this aspect requires further investigation. Special attention is required on the (d) plot (biggest instance); as the reader can observe, there is no clear difference between the best and the worst Pareto set. One possible explanation for this behaviour is that the 10 minutes CPU time limit was not long enough to allow for a significant exploration of the search space for problems of large size.

Comparing the MO-LNS results with those obtained with CPɛ, we can observe the following. The (a) plot describes a similar behaviour as in Fig. 12, i.e., the MO-LNS is clearly outperformed by the CPɛ; the latter succeeds in further minimising the energy levels, partly due to the right-shift mechanism mentioned above. As previously supposed however, different effects come into play as the problem size increases. In fact, while the (b) plot confirms the lowest energy levels obtained by CPɛ at large makespans, as the makespan decreases the CPɛ procedure seems to loose its performance; not only the obtained solutions are characterised by high energy levels, but the procedure does not seem to be very effective in finding solutions below a certain makespan (as the MO-LNS does). The previous characteristics are confirmed in plots (c) and (d); in particular, plot (d) exhibits a clear superiority of MO-LNS over CPɛ in terms of both energy and makespan minimization capabilities, thus fully confirming the expectations.

The comparison between the CPɛ and the CPɛ ^ad performances seems to confirm the the results obtained in Fig. 12, basically for all the four plots (a), (b), (c), and (d). Again, the advantage of the constraint generation adaptive scheme of the CPɛ ^ad procedure is clear; interestingly enough, the drawbacks exhibited by the CPɛ procedure w.r.t. the MO-LNS as the problem’s size increases are confirmed also in the CPɛ ^ad case. The conclusion we can draw from the experimentation is that the “anytime” behavior guaranteed by the MO-LNS approach allows to explore the Pareto set more efficiently than the CPɛɛ-constraint based approach, especially when the size of the problem increases. The reasons for this result mainly lie in the fact that, under the condition of equal allotted time for both procedures, the ɛ-constraint based approach is forced to equally divide the available time to be assigned for each solution’s optimisation attempt, while an anytime approach – such as the one implemented by MO-LNS – is free to allot the time available for optimisation among the solutions selected from the most promising Pareto set regions, according to the heuristics employed.

7 Conclusions and future work

In this work we have compared an “anytime” Multi-Objective (MO) Large Neighborhood Search (LNS) approach with an ɛ-constraint based approach (CPɛ), against FSSP problems with energy costs. Relatively to the MO-LNS procedure, two contributions have been presented: (i) an algorithmic template for solving multi-objective optimisation problems based on the LNS strategy, and (ii) an heuristic approach for solving ENFFS instances. Both ɛ-based procedures have been implemented on the IBM-ILOG CPLEX Optimization Studio, a known and efficient state-of-the-art CP development toolkit.

We have tested both previous approaches on: (i) a relevant case study taken from [3], and (ii) an extended set of ENFFS instances of increasing size, highlighting the pros and cons of both approaches as the size of the scheduling problem increases.

For future work, we are currently studying post-optimization search procedures to apply to the solutions obtained with MO-LNS, in order to overcome the early start time limitation of the core precedence constraint posting solver, and improve solution quality on problems characterised by non-regular objective functions such as the one tackled in this work. Moreover, we are collecting a large benchmark set from the instances available in the literature, relatively to scheduling problems with energy costs. The idea is to introduce new propagation procedures for the energy constraints, in order to foster comparison among different strategies for approximating the Pareto set.

To summarise, our analysis is following the direction of studying innovative meta-heuristic strategies (or hybridizations of these meta-heuristics such as Large Neighborhood Search, Scatter Search with Path Relinking, etc.) for solving scheduling problems with energy costs. Moreover, a further source of innovation may be represented by studying the energy constraints imposed on the above problems, in order to improve the search efficiency of a generic search strategy.