1 Introduction
-
Propose a set of metrics to compare two fuzzy models of total energy for the flexible job shop. To do so we motivate some measures that compare the models based both on their fuzzy values and on the use of crisp samples to simulate the behaviour in a real setting.
-
Compare the proposed energy model for the flexible job shop with the more straightforward alternative that directly translates the crisp model.
-
Propose a new neighbourhood function that ensures feasibility and connectivity. We formally demonstrate that the neighbourhood allows to obtain an optimal solution starting from any other solution. This is a desirable property when the neighbourhood is used in a wide variety of local search algorithms.
-
Integrate the proposed neighbourhood in a memetic algorithm and compare its performance with the state of the art. The results show that it is competitive and especially relevant in CPU-constrained applications.
2 Problem formulation
Symbol | Description |
---|---|
\(\textbf{O}\) | The set of operations |
\(\textbf{R}\) | The set of resources |
m | The number of resources |
\(\textbf{J}\) | The set of jobs |
n | The number of jobs |
\(\textbf{R}(o)\) | The subset of resources in which operation o can be executed |
\(\chi (o)\) | The job to which operation o belongs to |
\(\eta (o)\) | The position in which operation o has to be executed relative to its job |
\(\widehat{p}(o,r)\) | The processing time of operation o in the resource r |
\(P_p(r)\) | The passive power consumption of resource r |
\(P_a(o,r)\) | The active power consumption of executing operation o in resource r |
\(\varvec{\tau }_{\phi }\) | The resource assignments for solution \(\phi\) |
\(\textbf{s}_{\phi }\) | The starting time assignments for solution \(\phi\) |
\(\varvec{\sigma }_{\phi }\) | The operation processing order for solution \(\phi\) |
\(\tau _{\phi }(o)\) | The resource assigned to operation o in solution \(\phi\) |
\(\widehat{s_{\phi }}(o)\) | The starting time assigned to operation o in solution \(\phi\) |
\(\sigma _{\phi }(o)\) | The position of operation o in \(\varvec{\sigma }_{\phi }\) |
\(\widehat{c_{\phi }}(o)\) | The completion time of operation o in solution \(\phi\) |
\(\widehat{p_{\phi }}(o)\) | The processing time of operation o in solution \(\phi\). Equivalent to \(\widehat{p}(o,\tau _{\phi }(o))\) |
\(\widehat{h_{\phi }}(o)\) | The head of operation o in solution \(\phi\) |
\(\widehat{q_{\phi }}(o)\) | The tail of operation o in solution \(\phi\) |
\(JP (o)\) | The job predecessor of operation o |
\(JS (o)\) | The job successor of operation o |
\(RP _\phi (o)\) | The resource predecessor of operation o in solution \(\phi\) |
\(RS _\phi (o)\) | The resource successor of operation o in solution \(\phi\) |
\(\widehat{C_{max}}(\phi )\) | The makespan of solution \(\phi\) |
\(\widehat{E_p}(\phi )\) | The passive energy consumption in solution \(\phi\) |
\(\widehat{E_a}(\phi )\) | The active energy consumption in solution \(\phi\) |
\(\widehat{E}(\phi )\) | The total energy consumption in solution \(\phi\) |
\(\textbf{T}_{C_{max}}(\phi )\) | The set of all makespan-critical operations in solution \(\phi\) |
\(\textbf{B}_{C_{max}}(\phi )\) | The set of all makespan-critical blocks in solution \(\phi\) |
\(\mathbb {E}(\widehat{a})\) | The expected value of TFN \(\widehat{a}\) |
\(S(\widehat{a})\) | The spread of TFN \(\widehat{a}\) |
\(MVP (\widehat{a})\) | The modal value position of TFN \(\widehat{a}\) |
\(RDEV (\phi ,\varvec{\rho })\) | The relative distance of a possible scenario \(\varvec{\rho }\) to the expected value of a solution \(\phi\) |
\(UU (\phi ,\textbf{S})\) | The used uncertainty of a set of possible scenarios \(\textbf{S}\) for a solution \(\phi\) |
2.1 Fuzzy processing times
2.2 Fuzzy schedules
2.3 Total energy consumption
2.3.1 Alternative energy models in the fuzzy context
2.4 Measures for comparing fuzzy schedules
2.4.1 Measures based on fuzzy values
-
Expected Value (\(\mathbb {E}\)). As explained in Sect. 2.1, the expected value can be used to rank TFNs, so the smaller the expected value of the total energy, the better the solution.
-
Spread (S). For a TFN \(\widehat{a}\) its spread (Ghrayeb 2003) is defined as:The spread is a measure of the uncertainty of the TFN. Although uncertainty is present in the problem, between two solutions, that with an energy value having a smaller spread (uncertainty) should be preferred.$$\begin{aligned} S(\widehat{a}) = a^3-a^1 \end{aligned}$$(16)
-
Modal value position (\(MVP\)). Given a TFN \(\widehat{a}\) its modal value position is defined as:This is a number in \([-1,1]\), negative when the TFN’s modal value is on the left of the support’s midpoint, positive when the modal value is on the right of the midpoint, and zero when the TFN is symmetric. It could somehow be seen as a measure of the skewness of the TFN. Obviously, the \(MVP\) of the schedule’s energy depends on the processing times. However, if two schedules for the same problem have total energy values with different modal value position, the one with a \(MVP\) closer to 0 seems preferable in the sense that it is less biased, compared to the other schedule, which could be seen as accumulating uncertainty to the left (which could be seen as over-optimistic) or to the right (which could be seen as over-pessimistic). This measure is inspired by the ranking defined in Chen (1985), although the authors use it for a different objective.$$\begin{aligned} MVP (\widehat{a}) = \frac{(a^2-a^1)-(a^3-a^2)}{a^3-a^1} \end{aligned}$$(17)
2.4.2 Measures based on crisp realisations
-
Relative distance to the expected value (\(RDEV\)). Let \(a_{\varvec{\rho }}\) denote the value of the crisp objective function when the solution is evaluated on a possible scenario \(\varvec{\rho }\); then:If this value is negative, that is, the total energy consumption in the executed schedule is smaller than expected, it means that the a-priori schedule objective function is pessimistic. On the contrary, if \(RDEV\) is positive, the a-priori schedule could be seen as optimistic. Overall, the smaller the absolute value of \(RDEV\), the closer the predicted energy consumption of the solution is to real scenarios.$$\begin{aligned} RDEV (\phi ,\varvec{\rho }) = \frac{a_{\varvec{\rho }} - \mathbb {E}[\widehat{a}]}{\mathbb {E}[\widehat{a}]} \end{aligned}$$(18)
-
Used uncertainty (\(UU\)). Let \(\textbf{S}\) be a set of possible scenarios and let \(a_{\varvec{\rho }}\) denote the value of the objective function in a scenario \(\varvec{\rho } \in \textbf{S}\). Then:This gives a value in [0, 1] measuring the proportion of the support of the predicted fuzzy objective function that is covered with the possible scenarios in \(\textbf{S}\). When \(\textbf{S}\) is representative enough of all the possible scenarios, a value of \(UU\) close to 1 means that the range of values considered as obtainable by the TFN is actually achievable in real situations. Small values of \(UU\) would on the other hand mean that the fuzzy schedule incorporates artificial uncertainty and, hence, is less informative.$$\begin{aligned} UU (\phi ,\textbf{S}) = \frac{\max _{\varvec{\rho } \in \textbf{S}}a_{\varvec{\rho }}-\min _{\varvec{\rho } \in \textbf{S}}a_{\varvec{\rho }}}{a^3-a^1} \end{aligned}$$(19)
3 Neighbourhood for energy minimisation
3.1 Neighbourhoods aimed at reducing passive energy
3.2 Neighbourhood aimed at reducing active energy
3.3 Neighbourhood aimed at reducing total energy consumption
-
If \(\widehat{E_p}(\phi _k) >_E \widehat{E_p}(\phi _{opt})\) and \(\forall o \in \textbf{T}_{C_{max}}(\phi _k) \; \tau _{\phi _{opt}}(o) \ne \tau _{\phi _k}(o)\), then, by Lemma 1 there exists \(\phi ' \in \mathbf {N_{MCORR}}(\phi _k)\) which is closer to \(\phi _{opt}\); take \(\phi _{k+1}=\phi '\).
-
Else if \(\widehat{E_p}(\phi _k) >_E \widehat{E_p}(\phi _{opt})\), then, by Lemma 4 there exists \(\phi ' \in \mathbf {N_{MCOI_r}}(\phi _k)\) which is closer to \(\phi _{opt}\); take \(\phi _{k+1}=\phi '\).
-
Else if \(\widehat{E_a}(\phi _k) >_E \widehat{E_a}(\phi _{opt})\), then by Lemma 5 there exists \(\phi ' \in \mathbf {N_{OPERR}}(\phi _k)\) which is closer to \(\phi _{opt}\); take \(\phi _{k+1}=\phi '\).
3.4 The memetic algorithm
4 Experimental results
ev_pop_sz
is the size of the population; ev_st_it
represents the number of iterations without improvement after which the search will be halted; tb_lst_lbr
and tb_lst_ubr
correspond to the range of lower and upper bound values for the size of the tabu list; ls_st_it
represents the number of iterations after which a run of the tabu search will be stoppedev_pop_sz | ev_st_it | tb_lst_lbr | tb_lst_ubr | ls_st_it |
---|---|---|---|---|
mn | mn/2 | [mn/2, mn] | [2mn, 3mn] | mn |
4.1 Models comparison
4.1.1 Comparisons based on fuzzy values
4.1.2 Comparisons based on crisp scenarios
4.1.3 Comparisons based on CPU times
4.2 Comparison with the state of the art
Instance | rma | Imp. w.r.t. sma(%) | Imp. w.r.t. ema(%) | ||||||
---|---|---|---|---|---|---|---|---|---|
Mean | Best | Time | Mean | Best | Time | Mean | Best | Time | |
07a | 5406215.23 | 5342610.25 | 234.55 | \(-\)1.82 | \(-\)1.13 | 71.11 | \(-\)0.66 | \(-\)0.42 | 66.10 |
08a | 4448751.69 | 4411737.00 | 436.93 | \(-\)0.03 | 0.24 | 63.40 | \(-\)0.12 | \(-\)0.09 | 25.21 |
09a | 4728223.43 | 4693336.75 | 1034.42 | 0.61 | 0.49 | 61.53 | \(-\)0.25 | \(-\)0.34 | 28.72 |
10a | 5200786.87 | 5153733.75 | 251.85 | \(-\)1.69 | \(-\)1.33 | 62.46 | \(-\)0.61 | \(-\)1.03 | 66.26 |
11a | 4816362.64 | 4764942.75 | 440.91 | \(-\)0.05 | 0.33 | 64.07 | \(-\)0.25 | \(-\)0.22 | 43.75 |
12a | 4367695.83 | 4328756.75 | 912.57 | 0.64 | 0.71 | 58.71 | \(-\)0.24 | 0.02 | 5.79 |
13a | 7032932.70 | 6976623.75 | 943.23 | \(-\)0.73 | \(-\)0.37 | 28.78 | \(-\)0.25 | \(-\)0.14 | 46.38 |
14a | 6681278.33 | 6614463.50 | 1713.58 | 0.52 | 0.83 | 35.10 | \(-\)0.19 | \(-\)0.04 | 19.07 |
15a | 5940752.25 | 5887899.00 | 3855.72 | 1.54 | 1.52 | 27.97 | \(-\)0.13 | \(-\)0.01 | \(-\)13.82 |
16a | 6625853.63 | 6581874.50 | 1064.52 | \(-\)0.77 | \(-\)0.44 | 21.93 | \(-\)0.34 | \(-\)0.31 | 47.23 |
17a | 5989073.42 | 5931685.50 | 1480.84 | 0.27 | 0.55 | 40.17 | \(-\)0.29 | \(-\)0.34 | 31.47 |
18a | 5975974.31 | 5917202.25 | 3433.81 | 1.51 | 1.60 | 25.74 | \(-\)0.14 | 0.12 | \(-\)10.90 |
average values | 0.00 | 0.25 | 46.75 | \(-\)0.29 | \(-\)0.23 | 29.60 |