Green Multi-Objective Scheduling - A memetic NSGA-III for flexible production with real-time energy cost and emissions (2024)

Sascha C Burmeister
Management Information Systems
Paderborn University
Paderborn, Germany
sascha.burmeister@upb.de

Abstract

The use of renewable energies strengthens decarbonization strategies.To integrate volatile renewable sources, energy systems require grid expansion, storage capabilities, or flexible consumption.This study focuses on industries adjusting production to real-time energy markets, offering flexible consumption to the grid.Flexible production considers not only traditional goals like minimizing production time but also minimizing energy costs and emissions, thereby enhancing the sustainability of businesses.However, existing research focuses on single goals, neglects the combination of makespan, energy costs and emissions, or assumes constant or periodic tariffs instead of a dynamic energy market.We present a novel memetic NSGA-III to minimize makespan, energy cost, and emissions, integrating real energy market data, and allowing manufacturers to adapt consumption to current grid conditions.Evaluating it with benchmark instances from literature and real energy market data, we explore the trade-offs between objectives, showcasing potential savings in energy costs and emissions on estimated Pareto fronts.

Keywords OR in Energy $\cdot$ Sustainable Production $\cdot$ Green Flexible Job Shop Scheduling $\cdot$ Memetic NSGA-III

1 Introduction

Renewable energy is a key solution to the challenge of climate change.However, traditional energy systems face high penetration of volatile renewable energy sources and face new challenges in terms of power quality, reliability, or power system reliability (Basit etal., 2020).To support the integration of renewable energy sources, energy systems need grid expansion, storage capabilities, or flexible loads.This work focus on flexible loads, where consumers are encouraged to shift energy demand away from peak times to relieve grid load and toward periods of high renewable generation, promoting sustainable energy consumption.For manufacturing industries as large energy consumers, flexible loads offer a high potential for cost savings (Keller etal., 2017), but also present the challenge of maintaining production flexibility in alignment with energy market fluctuations without compromising economic targets such as total production time (makespan).

There are three classic types of energy tariffs: (1) energy tariffs with constant energy prices, (2) time-of-use (TOU) tariffs, where energy prices are divided into several time periods (e.g. on-peak and off-peak prices), and (3) real-time pricing (RTP) tariffs, where the cost of electricity consumption is based on the electricity exchange and changes at least every hour.The latter offers the ability to respond to price signals, react flexibly to the needs of the power system, and thus save cost and emissions (Finn &Fitzpatrick, 2014).Using a dynamic energy tariff, production planners as decision-makers can shape their production in terms of energy costs and emissions.

In the field of operations research, classical scheduling problems prioritize economic factors such as the schedule’s makespan.Green Job Shop Scheduling Problems are an extension of classical scheduling problems, incorporating resource and environmental aspects (Li &Wang, 2022).As we show in Section2, recent research places different focuses on economic goals such as the makespan or energy costs and ecological goals such as the emissions emitted.To the best of our knowledge, no research has combined the minimization of makespan, energy cost, and emissions while considering RTP tariffs.However, integrating these factors is essential for practitioners to accurately compute the potential reductions in energy costs and emissions achievable through improved production flexibility.

In this work, we investigate the research question:How do preferences regarding makespan, energy costs, and emissions influence each other in scheduling choices?Our contributions include (1) the expansion of a Flexible Job Shop Scheduling Problem (FJSP) with dynamic energy costs to a Green FJSP with dynamic energy costs and emissions, (2) developing a memetic algorithm based on the Non-Dominated Sorting Algorithm III (NSGA-III), and (3) conducting computational experiments to evaluate the trade-offs among makespan, energy costs, and emissions.As a solution approach, we use an NSGA-III because it has already been used by Sun etal. (2021) to optimize schedules with respect to energy-related goals.NSGA-III also leads to favorable results in similar problems of the FJSP (e.g., Wu etal. (2021); Sang &Tan (2022)).Our memetic NSGA-III is based on the development of a memetic NSGA-II from Burmeister etal. (2023) and represents a further development to enable the calculation of multi-objective schedules aimed at minimizing makespan, energy cost, and emissions.We opt for this algorithm due to its ability to represent schedules in a three-dimensional Pareto front, allowing decision-makers to balance trade-offs and select solutions based on their preferences.A notable aspect of our study is the evaluation of the scheduling problem using real energy costs and emissions data from the German energy market.

The remainder of this paper is organized as follows.Sect.2, presents recent research in the area of green scheduling.Sect.3, introduces the mathematical model, for which we present a memetic NSGA-III in Sect.4.Sect.5 shows our computational experiments and discusses our results.Sect.6, summarizes our results and presents an outlook for future research.

2 Recent research

In this section, we present research related to energy cost- and emission-aware scheduling.We discuss the respective objectives and solution approaches from the literature.

A schedule can be designed to minimize makespan, emissions, energy cost, or a combination of these.In order to take ecological and economic goals into account, one approach is to minimize makespan while limiting energy consumption (Carlucci etal., 2021).Energy consumption can also be minimized as an objective, but is still independent of the underlying energy mix and its costs and emissions (Lu etal., 2021; Sun etal., 2021).Wang etal. (2020) incorporate an economic view of energy consumption and minimize the makespan and energy costs.They divide a day into several periods with different energy prices based on a TOU tariff.A more detailed consideration of dynamic prices with RTP tariffs can be found in FazliKhalaf &Wang (2018) and Abikarram etal. (2019).They consider hourly-changing prices but neglect a minimization of the emissions and the makespan of the production schedule.Burmeister etal. (2023) present a model for bicriteria optimization of makespan and energy cost, considering RTP tariffs with 15-minute intervals for price changes.

As solution methods, Carlucci etal. (2021), Fang etal. (2011), and FazliKhalaf &Wang (2018) choose an exact solver.Due to the computational complexity of scheduling problems, metaheuristic approaches have the advantage of responding quickly to changing energy prices and emissions.Wang etal. (2020) and Lu etal. (2021) use a multi-objective Genetic Algorithm, while Sun etal. (2021) and Burmeister etal. (2023) use multi-objective evolutionary metaheuristics for fast computation.

Recent research has focused on several areas of green scheduling.However, the reviewed works that include energy costs and emissions neglect the real-time energy market, while studies related to real-time energy markets do not include emissions.We aim to fill this research gap by combining economic and environmental perspectives, taking a dynamic energy market into account.

3 Mathematical model

In this section, we present the mathematical optimization model for the multi-objective FJSP with objectives of minimizing makespan, energy cost, and emissions.The model builds upon the research conducted by Burmeister etal. (2023), which we extend to take emissions into account.Tab. 1 presents the notation for the mathematical model.The set $J=\{1,...,\mu\}$ contains $\mu$ jobs to be processed, each of which is divided into $v_{i}$ operations $O_{i}=\{(i,1),...,(i,v_{i})\}$ .The operations of a job must be processed in sequence.The set $O=\bigcup_{i\in J}O_{i}$ contains all operations.For each operation, $\tau_{ijk}$ specifies the duration with which an operation $(i,j)$ can be processed on machine $k\in M$ .Supplementary, $\eta_{ijkt}$ and $\zeta_{ijkt}$ contain the energy cost and emissions for processing operation $(i,j)$ on machine $k\in M$ beginning at time $t\in T$ .

Notation	Description	Notation	Description
Sets		Variables
$J$	Jobs, $i,i^{\prime}\in J$	$c^{max}$	Maximum makespan
$O$	Operations, $O=\bigcup\limits_{i\in J}O_{i}$ ,	$p^{sum}$	Sum of all energy cost
	$O_{i}=\{(i,1),...,(i,\nu_{i})\}$	$e^{sum}$	Sum of all emissions
$M$	Machines, $k\in M$	$s_{ijk}$	Start time of operation $(i,j)$
$T$	Time steps, $t\in T$		on machine $k$
Parameters		$c_{ijk}$	End time of operation $(i,j)$
$L$	A large number		on machine $k$
$\tau_{ijk}$	Processing time of operation $(i,j)$ on machine $k$	$x_{ijk}$	Binary indicator, 1 iff operation $(i,j)$ is allocated on machine $k$
$\eta_{ijkt}$	Energy cost for processing operation $(i,j)$ on machine $k$ when starting at time $t$	$y_{iji^{\prime}j^{\prime}k}$	Binary indicator, 1 iff operation $(i,j)$ is predecessor of operation $(i^{\prime},j^{\prime})$ on machine $k$
$\zeta_{ijkt}$	Energy emissions for processing operation $(i,j)$ on machine $k$ when starting at time $t$	$p_{ijkt}$	Binary indicator, 1 iff operation $(i,j)$ starts on machine $k$ at time $t$

Eq. 1 defines the objective functions of the model and minimizes the variables $c^{max}$ , $p^{sum}$ , and $e^{sum}$ , which represent the maximum makespan, the sum of all energy cost, and the sum of all emissions, respectively.Eq. 2 reflects the final completion time across all operations $(i,j)\in O$ and machines $k\in M$ .Eq. 3 and 4 sum the energy cost $\eta_{ijkt}$ and emissions $\zeta_{ijkt}$ , respectively, for all operations $(i,j)\in O$ on all machines machines $k\in M$ at all time steps $t\in T$ .

4 The memetic NSGA-III

In this section, we present the memetic NSGA-III for solving the green multi-objective FJSP.We divide the section into two parts, first introducing the representation of solutions in genotypes and phenotypes in Subsection4.1, before explaining the algorithm of the memetic NSGA-III in Subsection4.2.

4.1 Representation of solutions

The NSGA-III is an evolutionary algorithm and describes solutions as individuals of a population that evolve over multiple generations.To represent solutions as individuals, we follow a decoder-based approach that encodes solutions as genotypes and uses phenotypes for decoding.We base our genotype on the work of Dai etal. (2019), who choose a bipartite gene string for the sequence of operations and their machine assignment, and Burmeister etal. (2023), who choose a tripartite gene string for the additional representation of the maximum allowable energy cost per operation.To account for emissions, we extend latter approach and add a fourth gene string to this representation to indicate the maximum allowable emissions per operation.Fig.1 shows an example genotype for three jobs to be assigned to two machines.

Green Multi-Objective Scheduling - A memetic NSGA-III for flexible production with real-time energy cost and emissions (1)

Fig.2 illustrates the representation of the genotype on Fig.1.The allocation of operations to the machines is plotted as a Gantt chart, with time steps noted on the x-axis and machines on the left y-axis.On the right y-axis are the energy cost values, shown as a dashed line, and the emissions values, shown as a dotted line.Energy cost are given in €/MWh and emissions are given in grams of carbon dioxide equivalent (gCO₂eq) per kWh.The sequence gene string specifies the order in which the jobs are placed, while the machine gene string reflects the machine to be selected.Thus, operation (1,1) is first assigned to machine 2.The operation is scheduled at the first possible time that satisfies both the associated maximum allowable energy cost of the energy cost gene string and the emissions of the emissions gene string.This means that operation (1,1) is scheduled at the first time that costs less than or equal to 1€ and less than or equal to 4gCO₂eq, which is time step 4.

Green Multi-Objective Scheduling - A memetic NSGA-III for flexible production with real-time energy cost and emissions (2)

All jobs are scheduled in the order specified by the sequence gene string.If the time horizon considered is not sufficient to place an operation, e.g., because the allowed energy cost or emissions are too high, either the time horizon can be extended or the energy cost and emissions can be reduced.While the former tends to produce long schedules with favorable energy cost and emissions, the latter tends to produce fast and expensive schedules.To avoid bias and promote population diversification, we alternate the approach in each generation.Overall, the genotype and phenotype can represent any sequence of operations on any combination of machines, energy cost, and emissions, resulting in a complete representation of the solution space.

4.2 Algorithm

In this section, we explain our memetic NSGA-III.We base the memetic NSGA-III on the algorithm developed by Deb &Jain (2014), which uses a similar framework to its predecessor Deb etal. (2002) while providing better diversity.We extend the NSGA-III to a memetic NSGA-III by adding a local refinement method.The memetic NSGA-III is outlined in Alg.1.

Population $P_{t}$ , Population size $N$

$S_{t}=\emptyset,i=1$

$R_{t}\leftarrow P_{t}\cup\Call{Recombination+Mutation}{P_{t}}$

$R_{t}\leftarrow\Call{LocalRefinement}{R_{t}}$

$(F_{1},F_{2},...)=\Call{Non-dominated-sort}{R_{t}}$ \Repeat

$S_{t}=S_{t}\cup F_{i}$ and $i\leftarrow i+1$ \Until $|S_{t}|\geq N$ \If $|S_{t}|=N$

$P_{t+1}\leftarrow S_{t}$ \Else

$P_{t+1}\leftarrow\bigcup^{i-1}_{j=1}F_{j}$

$k\leftarrow N-|P_{t+1}|$ $\triangleright$ Remaining space in $P_{t+1}$

$Z^{r}\leftarrow\Call{Normalization}{S_{t}}$

$\Call{Association}{Z^{r},S_{t}}$

$P_{t+1}\leftarrow P_{t+1}\cup\Call{Niching}{F_{i},k}$ \EndIf

\Require

For a population $P_{t}$ of size $N$ , the NSGA-III generates an equally sized next generation $P_{t+1}$ using recombination and mutation operators:Recombination operators intensify the search in the solution space, finding better individuals based on existing ones by crossing their genotypes.For recombination, we use a two-point crossover.From two parents, the genes of the gene strings are swapped between two different randomly chosen positions.The same positions are chosen for swapping for all gene strings.By swapping, the gene strings remain feasible for machine assignment, energy cost, and emissions.In the case of the sequence gene string, swapping may cause an infeasibility, e.g., if a job is no longer listed in the number of its operations.In this case, the defective children are repaired by replacing excess jobs with missing ones.Mutation operators diversify the search in the solution space by randomly changing parts of each individual’s genotype to explore new regions of the solution space.

Green Multi-Objective Scheduling - A memetic NSGA-III for flexible production with real-time energy cost and emissions (3)

For the extension to a memetic NSGA-III, we adopt the local refinement from Burmeister etal. (2023) and extend it to include the consideration of emissions.Our local refinement shown in Fig.3 is a greedy procedure that adjusts the values of a parent’s energy cost and emissions gene string to create two new children with lower energy cost and emissions, respectively, without worsening the makespan.(1)First, it sorts all operations of the parent based on their energy consumption in descending order into a queue $L$ .(2)Second, it calculates the earliest and latest possible start times $l_{cij}$ and $i_{cij}$ for each operation $(i,j)\in O$ based on the duration of the previous and subsequent operations of the job for both children $c\in\{1,2\}$ .(3)Third, the greedy procedure selects the operation with the highest energy consumption, and (4)fourth, it schedules it at the time of the cheapest energy cost (4a) and emissions (4b), respectively.(5)Fifth, it adjusts the earliest possible start and end times of the operations that are still to be sorted, and (6) dequeues the current operation from $L$ .The procedure repeats steps (3) and (4) successively for the next operation until all operations in $L$ have been scheduled.

After recombination, mutation, and local refinement, the resulting set $R_{t}$ is sorted into several non-dominated fronts as described in Deb &Jain (2014).Alg.1 successively adds the individuals of the fronts to the set $S_{1}$ until their cardinality is greater than or equal to the desired population size $N$ .If $|S_{t}|=N$ , the next generation $P_{t+1}$ inherits all individuals from $S_{t}$ .Otherwise, all previous fronts except the last front $F_{i}$ are added to the new generation.To decide which $k$ individuals remaining in $F_{i}$ are included in $P_{t+1}$ , the algorithm performs a (1) normalization, (2) association, and (3) niching.The three procedures are explained in detail in Deb &Jain (2014) and are briefly outlined below:(1) First, the three objective function values of all individuals in $S_{t}$ are first normalized.(2) Then, the algorithm then creates reference points $Z^{f}$ and associates each individual from $S_{t}$ with its nearest reference point.(3) Finally, the niching procedure successively adds the individuals from $F_{i}$ to $P_{t+1}$ with which the fewest individuals are associated.Niching ends when $k$ individuals have been added to the new generation $P_{t+1}$ , so that $|P_{t+1}|=N$ holds.The memetic NSGA-III iterates until a termination criterion (e.g., generation or runtime limit) is satisfied.The first front $F_{1}$ of the last generation is then the estimate of the Pareto front.

5 Computational experiments

In this section, we present the computational experiments.Sect.5.1 describes the experimental setup of scheduling problems in presence of real-world energy market data.Sect.5.2 to 5.4 present the results and discuss the pairwise relationship of the objective function values, i.e., the relationship between makespan and energy cost, makespan and emissions, and energy cost and emissions.Sect.5.5 formulates summarizing implications.

5.1 Instances and experimental setting

For the computational experiments, we use the benchmark set of Brandimarte (1993), which contains 15 instances for the FJSP with jobs and their respective operations as well as machines, making it suitable for emulating a production schedule.For consideration of the energy market, we enrich the instances with real data from the German energy market published by the Federal Network Agency Germany (2024).Fig.4 shows both electricity prices from the German wholesale market and emission values in hourly resolution from February 1^st to June 30^th, 2022.Emissions calculations rely on the lifecycle emissions per generation technology as outlined in Schlömer etal. (2014).

Green Multi-Objective Scheduling - A memetic NSGA-III for flexible production with real-time energy cost and emissions (4)

For parameterization, we follow the settings of Burmeister etal. (2023) and refer to this work for further information.We limit the runtime of 45 minutes to reflect the flexibility to respond to hourly price changes in the energy market.The memetic NSGA-III is implemented in C# 10 within the .NET 6 software framework.The problem is solved on a Red Hat Enterprise Linux 8.5 (Oopta) operating system with an Intel Xeon Gold 6148 CPU, 20x2.4GHz, and 190 GByte main memory.

5.2 Relation of makespan to energy cost

In this section, we focus on the relationship between makespan and energy cost without considering changing emissions levels.The first three columns of Tab.2 show the instance, the best makespan found by the memetic NSGA-III, and the associated energy cost.The remaining columns show the percentage of energy cost that can be saved by increasing the makespan.

	min		Increase of ms¹ (%)					min		Increase of ms¹ (%)
Inst.	ms¹	ec²	5	20	50	75	Inst.	ms¹	ec²	5	20	50	75
mk01	42	3965	2.0	6.5	17.0	22.3	mk09	341	45041	5.5	16.7	32.5	38.6
mk02	29	3204	0.1	2.2	2.3	3.1	mk10	263	40158	7.0	10.2	16.1	26.3
mk03	204	13954	1.7	2.5	2.5	2.5	mk11	621	41038	8.6	10.1	10.1	10.1
mk04	66	6943	0.7	7.7	26.5	51.7	mk12	524	49137	7.7	18.6	18.6	18.6
mk05	174	11791	5.0	6.9	6.9	6.9	mk13	457	71059	11.8	30.4	36.7	36.7
mk06	77	7988	3.7	15.9	45.0	49.3	mk14	694	63382	2.2	2.2	2.2	2.2
mk07	144	10658	14.6	15.9	15.9	15.9	mk15	429	89821	8.4	24.3	36.6	36.6
mk08	523	37481	8.9	14.5	14.5	14.5
¹ Makespan, ² Energy cost

A 5% makespan increase saves between 0.1% (mk02) to 14.6% (mk07) of energy cost across all instances.For a 20% makespan increase, the savings range from 2.2% (mk02 and mk14) to 30.4% (mk13).For makespan increases of 50% and 75%, the energy cost remain stagnant for instances mk03, mk05, mk08, mk11, mk12, and mk14, showing no further improvements.For other instances, energy cost continue to decrease, achieving savings of up to 45.0% (mk06).At a 75% makespan increase, instances mk06 and mk04 show the highest energy cost savings with 49.3% and 51.7%, while instances mk03 and mk14 show the lowest savings (2.5% and 2.2%).

The average energy cost savings are 5.86%, 12.31%, 18.89%, and 22.35% for relative makespan increases of 5%, 20%, 50%, and 75%, respectively.The results indicate that small makespan increases are most efficient for energy cost savings, as the relative increase in savings surpasses the increase in makespan for 9 out of 15 instances.However, the efficiency diminishes with larger instances, as observed in 2 out of 15 instances with 20% makespan increases and none instances with 50% or 75% increases.

5.3 Relation of makespan to emissions

Tab.3 shows the results of emissions reduction with increasing makespan and follows the structure of Tab.2.A 5% makespan increase saves between 0.4% (mk02) and 10.5% (mk13) of the emissions.With a 20% makespan increase, the savings range from 1.0% (mk14) to 19.1% (mk13).For makespan increases of 50% and 75%, the emissions remain constant for the instances mk03, mk05, mk07, mk08, mk11, and mk14.Other instances show emissions savings of up to 23.7% (mk15) and 24.1% (mk09) with makespan increases of 50% and 75%, respectively.

	min		Increase of ms¹ (%)					min		Increase of ms¹ (%)
Inst.	ms¹	em²	5	20	50	75	Inst.	ms¹	em²	5	20	50	75
mk01	42	5215	1.3	5.4	12.7	17.7	mk09	341	68240	3.4	11.8	20.4	24.1
mk02	29	4627	0.4	2.2	3.7	5.3	mk10	263	61328	5.0	7.6	13.4	21.2
mk03	204	24257	2.9	2.9	2.9	2.9	mk11	621	73575	4.7	5.6	5.6	5.6
mk04	66	9370	1.0	7.9	14.9	17.0	mk12	524	83272	5.7	10.4	10.7	10.7
mk05	174	18303	3.5	3.6	3.6	3.6	mk13	457	109633	10.5	19.1	23.1	23.1
mk06	77	10436	3.2	11.2	14.7	17.6	mk14	694	118605	1.0	1.0	1.0	1.0
mk07	144	17517	6.3	7.1	7.1	7.1	mk15	429	139310	6.9	17.6	23.7	23.7
mk08	523	64146	5.4	8.3	8.3	8.3
¹ Makespan, ² Emissions

The average emission savings are 4.08%, 8.11%, 11.05%, and 12.59% for relative makespan increases of 5%, 20%, 50%, and 75%, respectively.Again, the most efficient savings are observed for smaller instances.For a 5% makespan increase, the relative increase in savings exceeds the increase in makespan for 6 of 15 instances.

The emissions savings are lower than the energy cost savings in Tab.2.This can be attributed to the fact that market values of emissions are often higher than energy costs and have a positive value range.As a result, the algorithm has fewer opportunities to schedule jobs with high energy demands at favorable times.

5.4 Relation of energy cost to emissions

Tab.4 shows the results of the emissions savings potential as energy cost increase without considering the makespan.It is structured similarly to Tab.2 and 3.For instance mk02, the absolute value of the energy cost was used because the instance has few jobs, that are processed for negative energy cost.

	min		Increase of ec¹ (%)					min		Increase of ec¹ (%)
Inst.	ec¹	em²	5	20	50	75	Inst.	ec¹	em²	5	20	50	75
mk01	5	3249	0.3	1.7	5.4	6.2	mk09	10170	45452	2.0	5.7	6.1	6.1
mk02³	-2	3098	2.1	6.6	9.4	14.2	mk10	7182	40082	1.8	5.0	6.7	7.3
mk03	1282	17464	1.3	6.6	8.1	9.7	mk11	18933	60929	1.4	2.5	2.5	2.5
mk04	71	6343	1.6	5.7	8.0	8.9	mk12	16571	62976	1.0	2.7	2.8	2.8
mk05	838	13940	2.2	4.0	5.2	6.6	mk13	22309	74076	3.4	3.6	3.6	3.6
mk06	132	7506	0.2	8.6	12.1	13.5	mk14	32770	100836	1.4	2.2	2.2	2.2
mk07	668	13517	5.6	6.9	10.7	11.5	mk15	29438	93441	3.3	4.6	4.6	4.6
mk08	13019	48015	0.7	1.4	1.4	1.4
¹ Energy cost, ² Emissions, ³ Since the value is negative, we use the absolute value for
the percentage increase.

A 5% energy cost increase saves between 1.4% (mk08) and 5.6% (mk06) of emissions.For energy cost increases of 20, 50, and 75%, the maximum savings are 8.6 (mk06), 12.1 (mk06), and 14.2% (mk02), respectively, and the minimum savings are 1.4% (mk08).Except for the 5.6% reduction in emissions for a 5% deterioration in energy cost for instance mk07, the relative savings are less than the relative deterioration in all other cases.The average emission savings are 1.89%, 4.52%, 5.92%, and 6.74% for relative energy cost increases of 5%, 20%, 50%, and 75%, respectively.

5.5 Implications

In this section, we draw implications from the results.Fig.5 summarizes the previous Tab.2 through 4 and shows the medians of the percentage savings in energy costs when increasing the makespan (solid line), emissions when increasing the makespan (dashed line) and emissions when increasing the makespan (dotted line).The error bars show the minima and maxima.

Green Multi-Objective Scheduling - A memetic NSGA-III for flexible production with real-time energy cost and emissions (5)

First, extending makespan can lead to savings in energy costs and emissions.Energy costs show a higher savings potential than emissions due to the fact that the energy market has lower and sometimes negative prices, while emissions cannot be negative.While a percentage increase in makespan yields a disproportionately low rise in the percentage of savings in energy costs and emissions, the absolute savings are still considerable.We advise decision-makers, to contemplate the benefits of enhancing production flexibility for potential savings.

Second, opting for increased energy costs can result in decreased emissions.The results do show higher savings in emissions if a schedule with a longer makespan is considered and can thus react better to the dynamic energy market.If decision-makers are unable to consider an increase in makespan (e.g. due to deadlines), it may also be attractive for manufacturers to balance higher energy costs against emissions savings.Conversely, our approach can leverage the additional costs associated with emission reductions to set prices for low-emission or emission-free production, fostering the creation of new customer offerings within innovative business models.

6 Conclusion

Our study addresses the challenge of managing flexible loads in manufacturing industries, aiming to optimize schedules for minimum makespan, energy cost, and emissions.Drawing from existing literature, we introduce a novel linear optimization model for a Green Flexible Job Shop Problem (FJSP) and develop a memetic NSGA-III approach as a three-objective solution method.Evaluating our method on benchmark instances enriched with real energy market data from Germany, we find that the memetic NSGA-III effectively estimates Pareto fronts.This aids production planners in making load flexibility decisions to reduce energy cost and emissions.We find that increasing makespan can efficiently save energy cost and emissions, while reducing emissions may be less effective due to increased energy costs.Our findings underscore the importance of considering the interplay between the three target objectives to strengthen sustainable production planning in manufacturing companies.

Based on the limitations and findings of this study, we advise avenues for further research.First, we recommend to analyze our approach on real data.We recommend using real data from manufacturers and augmenting the decision model with additional details on production costs, including factors such as labor costs.In this way, we aim to achieve a better understanding of the trade-off between makespan, energy costs and emissions.Second, we recommend to extend our approach to address uncertainty of data.Currently, we assume deterministic knowledge regarding energy costs and emissions.In future work, schedules could be generated based on day-ahead energy market data and forecasts with daily updates through a rolling horizon approach.This approach enables deeper understanding of how decision-makers can adapt to the fluctuations in the dynamic energy market.Third, we recommend to study the proposed algorithm in more detail.While this work primarily guides manufacturers in exploring trade-offs between objectives and highlighting potential savings, it is important to note that the results are not subjected to statistical analysis.Consequently, we suggest future work to include metrics showing the quality of results and to further compare these results with those obtained from other state-of-the-art methods.

Acknowledgments

The authors gratefully acknowledge the financial support provided by the state of North Rhine-Westphalia, Germany, as part of the progres.nrw program area, in the framework of Re²Pli (project number EFO 0127A) and the funding of this project by computing time provided by the Paderborn Center for Parallel Computing (PC²).

References

(1)
Abikarram etal. (2019)Abikarram, J.B., McConky, K. &Proano, R. (2019), ‘Energy cost minimization for unrelated parallel machine scheduling under real time and demand charge pricing’, Journal of cleaner production 208,232–242.
Basit etal. (2020)Basit, M.A., Dilshad, S., Badar, R. &Samiur Rehman, S.M. (2020), ‘Limitations, challenges, and solution approaches in grid-connected renewable energy systems’, International Journal of Energy Research 44(6),4132–4162.
Brandimarte (1993)Brandimarte, P. (1993), ‘Routing and scheduling in a flexible job shop by tabu search’, Annals of Operations research 41(3),157–183.
Burmeister etal. (2023)Burmeister, S.C., Guericke, D. &Schryen, G. (2023), ‘A memetic nsga-ii for the multi-objective flexible job shop scheduling problem with real-time energy tariffs’, Flex Serv Manuf J .
Carlucci etal. (2021)Carlucci, D., Renna, P. &Materi, S. (2021), ‘A job-shop scheduling decision-making model for sustainable production planning with power constraint’, IEEE Transactions on Engineering Management .
Dai etal. (2019)Dai, M., Tang, D., Giret, A. &Salido, M.A. (2019), ‘Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints’, Robotics and Computer-Integrated Manufacturing 59,143–157.
Deb &Jain (2014)Deb, K. &Jain, H. (2014), ‘An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints’, IEEE Transactions on Evolutionary Computation 18(4),577–601.
Deb etal. (2002)Deb, K., Pratap, A., Agarwal, S. &Meyarivan, T. (2002), ‘A fast and elitist multiobjective genetic algorithm: Nsga-ii’, IEEE Transactions on Evolutionary Computation 6(2),182–197.
Fang etal. (2011)Fang, K., Uhan, N., Zhao, F. &Sutherland, J.W. (2011), ‘A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction’, Journal of Manufacturing Systems 30(4),234–240.
FazliKhalaf &Wang (2018)FazliKhalaf, A. &Wang, Y. (2018), ‘Energy-cost-aware flow shop scheduling considering intermittent renewables, energy storage, and real-time electricity pricing’, International Journal of Energy Research 42(12),3928–3942.
Federal Network Agency Germany (2024)Federal Network Agency Germany (2024), ‘SMARD market data’, online.
https://www.smard.de/en/downloadcenter/download-market-data
Finn &Fitzpatrick (2014)Finn, P. &Fitzpatrick, C. (2014), ‘Demand side management of industrial electricity consumption: Promoting the use of renewable energy through real-time pricing’, Applied Energy 113,11–21.
Keller etal. (2017)Keller, F., Schultz, C., Simon, P., Braunreuther, S., Glasschröder, J. &Reinhart, G. (2017), ‘Integration and interaction of energy flexible manufacturing systems within a smart grid’, Procedia CIRP 61,416–421.
Li &Wang (2022)Li, M. &Wang, G.-G. (2022), ‘A review of green shop scheduling problem’, Information Sciences 589,478–496.
Lu etal. (2021)Lu, C., Zhang, B., Gao, L., Yi, J. &Mou, J. (2021), ‘A knowledge-based multiobjective memetic algorithm for green job shop scheduling with variable machining speeds’, IEEE Systems Journal 16(1),844–855.
Özgüven etal. (2010)Özgüven, C., Özbakır, L. &Yavuz, Y. (2010), ‘Mathematical models for job-shop scheduling problems with routing and process plan flexibility’, Applied Mathematical Modelling 34(6),1539–1548.
Sang &Tan (2022)Sang, Y. &Tan, J. (2022), ‘Intelligent factory many-objective distributed flexible job shop collaborative scheduling method’, Computers & Industrial Engineering 164,107884.
Schlömer etal. (2014)Schlömer, S., Bruckner, T., Fulton, L., Hertwich, E., McKinnon, A., Perczyk, D., Roy, J., Schaeffer, R., Sims, R., Smith, P. etal. (2014), Annex iii: Technology-specific cost and performance parameters, in ‘Climate change 2014: Mitigation of climate change: Contribution of working group III to the fifth assessment report of the Intergovernmental Panel on Climate Change’, Cambridge University Press, pp.1329–1356.
Sun etal. (2021)Sun, X., Wang, Y., Kang, H., Shen, Y., Chen, Q. &Wang, D. (2021), ‘Modified multi-crossover operator nsga-iii for solving low carbon flexible job shop scheduling problem’, Processes 9(1).
Wang etal. (2020)Wang, L. etal. (2020), ‘Multi-objective optimization based on decomposition for flexible job shop scheduling under time-of-use electricity prices’, Knowledge-Based Systems 204,106177.
Wu etal. (2021)Wu, M., Yang, D., Zhou, B., Yang, Z., Liu, T., Li, L., Wang, Z. &Hu, K. (2021), ‘Adaptive population nsga-iii with dual control strategy for flexible job shop scheduling problem with the consideration of energy consumption and weight’, Machines 9(12),344.

min	$\textstyle(c^{max},p^{sum},e^{sum})$		(1)
s.t.	$\textstyle c^{max}\geq c_{ijk}$	$\textstyle\forall i,j,k$	(2)
	$\textstyle p^{sum}\geq\sum_{i,j,k,t}\eta_{ijkt}p_{ijkt}$		(3)
	$\textstyle e^{sum}\geq\sum_{i,j,k,t}\zeta_{ijkt}p_{ijkt}$		(4)
	$\textstyle\sum_{k}x_{ijk}=1$	$\textstyle\forall i,j$	(5)
	$\textstyle s_{ijk}+c_{ijk}\leq x_{ijk}L$	$\textstyle\forall i,j,k$	(6)
	$\textstyle c_{ijk}\geq s_{ijk}+\tau_{ijk}-(1-x_{ijk})L$	$\textstyle\forall i,j,k$	(7)
	$\textstyle\sum_{k}s_{ijk}\geq\sum_{k}c_{i,j-1,k}$	$\textstyle\forall i,j$	(8)
	$\textstyle s_{ijk}\geq c_{i^{\prime}j^{\prime}k}-y_{iji^{\prime}j^{\prime}k}L$	$\textstyle\forall i,j,i^{\prime},j^{\prime},k$	(9)
	$\textstyle s_{i^{\prime}j^{\prime}k}\geq c_{ijk}-(1-y_{iji^{\prime}j^{\prime}k%})L$	$\textstyle\forall i,j,i^{\prime},j^{\prime},k$	(10)
	$\textstyle x_{ijk}=\sum_{t}p_{ijkt}$	$\textstyle\forall i,j,k$	(11)
	$\textstyle s_{ijk}-t\geq-(1-p_{ijkt})L$	$\textstyle\forall i,j,k,t$	(12)
	$\textstyle s_{ijk}-t\leq(1-p_{ijkt})L$	$\textstyle\forall i,j,k,t$	(13)
	$\textstyle c^{max},p^{sum},e^{sum},s_{ijk},c_{ijk}\in\mathbb{R}_{+},$
	$\textstyle x_{ijk},y_{iji^{\prime}j^{\prime}k},p_{ijkt}\in\{0,1\}\hskip 16.000%08pt\forall i,j,i^{\prime},j^{\prime},k,t$		(14)