•A scheduling framework is presented to improve carbon efficiency in flow shops.•We extend NEH-Insertion Procedure to incorporate energy criterion.•Two multi-objective optimization algorithms (MONEH and MMOIG) are proposed.•Numerical computations show that the proposed algorithms outperform NSGA-II. Recently, there has been an increasing concern on the carbon efficiency of the manufacturing industry. Since the carbon emissions in the manufacturing sector are directly related to the energy consumption, an effective way to improve carbon efficiency in an industrial plant is to design scheduling strategies aiming at reducing the energy cost of production processes. In this paper, we consider a permutation flow shop (PFS) scheduling problem with the objectives of minimizing the total carbon emissions and the makespan. To solve this multi-objective optimization problem, we first investigate the structural properties of non-dominated solutions. Inspired by these properties, we develop an extended NEH-Insertion Procedure with an energy-saving capability. The accelerating technique in Taillard’s method, which is commonly used for the ordinary flowshop problem, is incorporated into the procedure to improve the computational efficiency. Based on the extended NEH-Insertion Procedure, a multi-objective NEH algorithm (MONEH) and a modified multi-objective iterated greedy (MMOIG) algorithm are designed for solving the problem. Numerical computations show that the energy-saving module of the extended NEH-Insertion Procedure in MONEH and MMOIG significantly helps to improve the discovered front. In addition, systematic comparisons show that the proposed algorithms perform more effectively than other tested high-performing meta-heurisitics in searching for non-dominated solutions.