Improving productivity at the expense of heavy energy consumption is often no longer possible in modern manufacturing industries. Through efficient scheduling technologies, however, we are able to still maintain high productivity while reducing energy costs. This article addresses a flexible job shop scheduling problem under time-of-use electricity tariffs with the objective of minimizing total energy consumption while considering a predefined makespan constraint. We propose a novel two-individual-based evolutionary (TIE) algorithm, which incorporates several distinguishing features, such as a tabu search procedure, a topological order-based recombination operator, a new neighborhood structure for this specific problem, and an approximate neighborhood evaluation method. Extensive experiments are conducted on widely used benchmark instances, which show that the proposed TIE outperforms traditional trajectory-based and population-based methods. We also analyze the key features of TIE to identify its critical success factors, and discuss the impact of varying key parameters of the problem to derive practical insights.

Population-based evolutionary algorithms usually manage a large number of individuals to maintain the diversity of the search, which is complex and time-consuming. In this paper, we propose an evolutionary algorithm using only two individuals, called master-apprentice evolutionary algorithm (MAE), for solving the flexible job shop scheduling problem (FJSP). To ensure the diversity and the quality of the evolution, MAE integrates a tabu search procedure, a recombination operator based on path relinking using a novel distance definition, and an effective individual updating strategy, taking into account the multiple complex constraints of FJSP. Experiments on 313 widely-used public instances show that MAE improves the previous best known results for 47 instances and matches the best known results on all except 3 of the remaining instances while consuming the same computational time as current state-of-the-art metaheuristics. MAE additionally establishes solution quality records for 10 hard instances whose previous best values were established by a well-known industrial solver and a state-of-the-art exact method.