Energy-Efficient Scheduling Problem Using an Effective Hybrid Multi-Objective Evolutionary Algorithm

Lvjiang Yin, Xinyu Li, Chao Lu, Liang GaoSustainability 2016 · DOI

TL;DR

This paper tackles the complex challenge of optimizing manufacturing schedules to simultaneously minimize production costs (earliness/tardiness and operational expenses) and energy consumption. They introduce a novel hybrid multi-objective evolutionary algorithm (LMOEA) that uses a unique solution representation and a self-adaptive local search mechanism to effectively navigate this multi-faceted problem, outperforming existing state-of-the-art algorithms.

What Problem Does This Paper Address?

Modern manufacturing faces a dual pressure: achieving "just-in-time" (JIT) production to reduce inventory costs and meet deadlines, while also drastically cutting energy consumption to address rising costs and environmental concerns. These goals often conflict. For instance, speeding up production to meet JIT might increase energy usage, while shutting down machines to save energy could lead to delays.

Existing research often simplifies this by focusing on single objectives or single machines. However, real-world scenarios involve multiple conflicting objectives (earliness/tardiness, cost, and energy) and complex dependencies like sequence-dependent setup times. This paper addresses this gap by developing a comprehensive model for a single-machine environment that accounts for controllable processing times, sequence-dependent setup times, and the three key objectives: total earliness/tardiness (E/T), total cost (including compression/expansion of processing times), and total energy consumption.

Methods

The core of this work is a novel Local Multi-Objective Evolutionary Algorithm (LMOEA). Key innovations include:

  • New Solution Representation: Instead of traditional discrete representations, they propose a real-valued encoding that cleverly combines job processing time adjustments (compression/expansion) and job sequencing. This allows them to convert a discrete combinatorial problem into a continuous one, simplifying constraint handling.
  • Hybrid Local Search with Self-Adaptation: The LMOEA incorporates a sophisticated local search mechanism. It doesn't rely on a single strategy but uses three distinct local search operators (focused on energy reduction, tardiness/earliness minimization, and cost reduction). Crucially, these operators are selected adaptively based on their performance, allowing the algorithm to dynamically choose the most effective strategy during the search.
  • Hybridization: The LMOEA integrates elements from Harmony Search (HS), Genetic Algorithms (GA), and Differential Evolution (DE) to leverage their diverse search capabilities and improve population diversity and algorithm stability.

Datasets

The authors evaluated their LMOEA on a set of generated test instances. These instances were categorized into three sizes (small, medium, large) based on the number of jobs (10, 50, 100). For each size, they generated instances with varying "tightness" of due dates (k=1 to 5), creating a total of 15 distinct problem configurations. They also conducted a case study using real-world data from a welding workshop, involving 12 jobs with specific processing times, setup times, and machine power characteristics.

Key Insights and Ideas

  • The Trade-off is Real: The paper clearly demonstrates that optimizing for earliness/tardiness, cost, and energy consumption simultaneously is a complex balancing act. Improving one objective often leads to a worsening of another, highlighting the necessity of multi-objective optimization.
  • Encoding Matters: The novel real-valued encoding scheme significantly simplifies the problem by transforming it into a continuous domain, making it easier for evolutionary algorithms to handle.
  • Local Search is Powerful, but Diversity is Key: While individual local search strategies showed promise, their integration with a self-adaptive mechanism proved crucial. This combination not only improved the algorithm's ability to find good solutions but also enhanced its robustness and diversity.
  • Energy Saving is Achievable Beyond Machine Design: The study emphasizes that significant energy savings can be realized through operational strategies like intelligently turning machines on/off during idle periods, rather than solely relying on more energy-efficient hardware.

Key Results

The LMOEA consistently outperformed several well-established multi-objective evolutionary algorithms (NSGA-II, SPEA2, OMOPSO, MOEA/D) across various metrics (IGD, GD, Spread).

  • Superior Performance: The LMOEA achieved the best IGD values on 11 out of 15 test instances and the best GD values on 13 out of 15 instances, indicating superior convergence and overall performance.
  • Robustness: The proposed algorithm showed good diversity, covering a wider range of Pareto fronts compared to some competitors.
  • Efficiency: While not the absolute fastest, the LMOEA's CPU time increased more slowly than other algorithms, especially OMOPSO, suggesting good scalability.
  • Case Study Success: The LMOEA successfully generated high-quality and diverse Pareto front solutions for the real-world welding workshop problem.

Limitations and Future Work

  • Heuristic Information: The authors acknowledge that their LMOEA doesn't currently incorporate problem-specific heuristic information, which could potentially further enhance search efficiency.
  • Parameter Sensitivity: The algorithm's performance is influenced by certain parameters, and further tuning might be beneficial.
  • Future Directions:
    • Broader Applicability: Evaluate the LMOEA on different scheduling environments (e.g., job shop, open shop) to assess its generalizability.
  • Advanced Techniques: Explore incorporating newer techniques like deep learning to improve search efficiency.
  • Operational Speed: Consider the impact of processing speeds on energy consumption in future research.

Summary updated

Abstract

Nowadays, manufacturing enterprises face the challenge of just-in-time (JIT) production and energy saving. Therefore, study of JIT production and energy consumption is necessary and important in manufacturing sectors. Moreover, energy saving can be attained by the operational method and turn off/on idle machine method, which also increases the complexity of problem solving. Thus, most researchers still focus on small scale problems with one objective: a single machine environment. However, the scheduling problem is a multi-objective optimization problem in real applications. In this paper, a single machine scheduling model with controllable processing and sequence dependence setup times is developed for minimizing the total earliness/tardiness (E/T), cost, and energy consumption simultaneously. An effective multi-objective evolutionary algorithm called local multi-objective evolutionary algorithm (LMOEA) is presented to tackle this multi-objective scheduling problem. To accommodate the characteristic of the problem, a new solution representation is proposed, which can convert discrete combinational problems into continuous problems. Additionally, a multiple local search strategy with self-adaptive mechanism is introduced into the proposed algorithm to enhance the exploitation ability. The performance of the proposed algorithm is evaluated by instances with comparison to other multi-objective meta-heuristics such as Nondominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2), Multiobjective Particle Swarm Optimization (OMOPSO), and Multiobjective Evolutionary Algorithm Based on Decomposition (MOEA/D). Experimental results demonstrate that the proposed LMOEA algorithm outperforms its counterparts for this kind of scheduling problems.
BibTeX
@inproceedings{yin2016energy,
  author = {Lvjiang Yin and Xinyu Li and Chao Lu and Liang Gao},
  title = {{Energy-Efficient Scheduling Problem Using an Effective Hybrid Multi-Objective Evolutionary Algorithm}},
  booktitle = {Sustainability},
  year = {2016},
  doi = {10.3390/su8121268},
}
Figure