Sage Journals: Discover world-class research

Abstract

Nowadays, manufacturing enterprises, as larger energy consumers, face the severe environmental challenge and the mission of reducing energy consumption. Therefore, how to reduce energy consumption becomes a burning issue for manufacturing. Production scheduling provides a feasible scheme for energy saving on the system level. However, the existing researches of energy-saving scheduling rarely focus on the permutation flow line scheduling problem. This article proposes an energy-saving method for permutation flow line scheduling problem. First, a mathematical model for the permutation flow line scheduling problem is developed based on the principle of multiple energy source system of the computer numerical control machine tool. The optimization objective of this model is to simultaneously minimize the total flowtime and the fixed energy consumption. Since permutation flow line scheduling problem is a well-known NP-hard problem, the non-dominated sorting genetic algorithm II is adopted to solve the multi-objective permutation flow line scheduling problem. Finally, the effectiveness of this method is verified by numerical illustration. The computation results show that a significant trade-off between total flowtime and fixed energy consumption for the permutation flow line scheduling problem, and there would be potential for saving energy consumption by using the proposed method.

Keywords

Permutation flow line scheduling energy saving multi-objective optimization fixed energy consumption non-dominated sorting genetic algorithm II

Introduction

Nowadays, manufacturing enterprises not only face shorter product life-cycle, complex and diverse economic trends, rapidly changing science and technology, increasedly diverse demand of customer, and the globalization of production activities but also face enormous environmental challenges. These challenges include the global climate change (e.g. greenhouse effect), the exhaustion trends of various non-renewable resources (e.g. gas, oil, coal), and decreasing biodiversity. In the United States, statistical data show that the industrial sector is responsible for approximately 33% of total national electricity consumption.^1,2 The corresponding amount of carbon dioxide emissions, which is generated by the electricity consumption, was 18%–20%. In most cases, the electricity is mainly produced by using fossil fuels. So, the costs of manufacturing enterprises are increased along with the fossil fuels’ price soaring. Meanwhile, manufacturers encounter pressure from the relevant environment laws and regulations. For these reasons, it is a burning issue to reduce energy consumption during production process in manufacturing enterprises.

Fang et al.³ indicate that more than 85% of the energy is used for functions which are not directly related to the actual production of parts in a mass production environment. Therefore, this implies that rather than focusing on updating individual machines or processes to be more energy-efficient, attention should be directed at system-level changes which could realize significant energy benefits. In recent years, energy saving during production process becomes a research hotspot for scholars at home and aboard. And production scheduling has provided an effective method to realize energy saving. Mouzon et al.⁴ have studied single-machine scheduling. They present that there is a big space of energy saving when non-bottleneck (i.e. underutilized) machines/equipments are turned off when they will be idle for a certain amount of time. Dispatching rules and artificial neural network (ANN) are used to solve the multi-objective mathematical programming model, the optimization objectives of which are simultaneously minimizing energy consumption and maximum completion time. In the further study of Mouzon and Yildirim,⁵ a framework for solving multi-objective optimization scheduling problem with minimizing energy consumption and total tardiness is proposed. They use a new greedy randomized multi-objective adaptive search meta-heuristic to obtain an approximate pareto front. Shrouf et al.⁶ provide a mathematical model to minimize energy consumption costs for single-machine production scheduling during production processes. By making decisions at machine level to determine the launch times for job processing, idle time, when the machine must be shut down, “turning on” time, and “turning off” time, this model enables the operations manager to implement the least expensive production scheduling during a production shift. He et al.⁷ propose a bi-objective model for the job shop scheduling problem. The objective function value of the model represents synthesized optimization of energy consumption and makespan. Also, a heuristic algorithm is developed to locate the optimal or near-optimal solutions of the model based on the Tabu search mechanism. They use scheduling method to decrease unloaded energy consumption of the machine tools, that is, reducing the energy consumption during idle state of machine. Hence, the total energy consumption is reduced, and the goal of energy saving is achieved. In order to integrating process planning and scheduling, Dai et al.⁸ present an energy-aware mathematical model for job shops. They adopt a modified genetic algorithm to solve the energy-aware model, the optimization objectives of which are minimizing energy consumption and makespan. Considering both production factors (i.e. makespan and machine workload) and environmental influence (i.e. carbon emission), Zhang et al.⁹ provide a low-carbon scheduling model for the flexible job shop. They combine the original non-dominated sorting genetic algorithm II (NSGA-II) with a local search algorithm based on neighborhood search and propose a hybrid NSGA-II to solve the low-carbon scheduling model. Focusing on the energy-saving problem of flexible manufacturing system, Zhang et al.¹⁰ put forward an energy-saving approach based on energy evaluation model for integration of process planning and scheduling problem and use a mutation-combined ant colony optimization algorithm to solve this problem. Moon et al.¹¹ discuss the unrelated parallel machine scheduling problem with minimization of the makespan of production and minimization of time-dependent electricity costs. He and Liu¹² explore the systematic methodology for incorporating energy consumption and environmental impact consideration into the production operation of machining process. They use this methodology to solve the parallel machine scheduling problem. Fang et al.³ consider double-machine scheduling problem and present a new mathematical programming model of the flow shop scheduling problem that considers peak power load, energy consumption, and associated carbon footprint in addition to cycle time. In the further research of Fang et al.,¹³ they investigate both mathematical programming and combinatorial approaches to this scheduling problem and test their approaches with instances arising from the manufacturing of cast iron plates. Salido et al.¹⁴ study and analyze three important objectives: energy efficiency, robustness and makespan, and the relationship among them. It can be observed that there exists a clear relationship between robustness and energy efficiency and a clear trade-off between robustness/energy efficiency and makespan. Aiming to production efficiency and electric power cost, Luo et al.¹⁵ propose a new ant colony optimization meta-heuristic for solving hybrid flow shop scheduling problem. Dai et al.¹⁶ present an energy-efficient model for flexible flow shop scheduling. This model can determine whether the machine tools should be on or off when they are idle for a certain amount of time. So, energy consumption can be reduced by turning off the correspondingly idle machine tool. Mashaei and Lennartson¹⁷ address the design of a control strategy for a closed-loop flow shop plant based on a one-loop pallet system. The objective is optimal running of the machines and track of pallet to obtain the minimal energy consumption in idle machines, as well as to gain the desired throughput for the plant. Chen et al.¹⁸ investigate energy consumption decrease in production systems through efficient scheduling of machine turning on and off. Their study focuses on serial production lines with finite buffers and machines having Bernoulli reliability model. The trade-off between productivity and energy efficiency in production systems is discussed. To explore the energy-saving opportunities, Brundage et al.¹⁹ combine the two largest energy consumers in a manufacturing plant: the production line and the heating, ventilation, and air conditioning (HVAC) system. They utilize the concept of the energy opportunity window (OW) to optimize the energy cost saving. Zanoni et al.²⁰ analyze a system where a single product is manufactured on a machine and delivered to the subsequent production stage in batch shipments. The aim of their work is to propose an analytical model of this system and to minimize the total costs of producing and storing the product, including energy cost. Zhang et al.²¹ develop a time-indexed integer programming formulation and use it to identify manufacturing schedules that minimize electricity cost and the carbon footprint under time-of-use tariffs without compromising production throughput. Liu and Huang²² examine carbon footprint within the context of production scheduling. Two multiple-objective scheduling problems involving economic- and environmental-related criteria are researched. According to the manufacturing model, the above-mentioned researches can be classified into six types as shown in Table 1.

Table 1.

Relevant researches for the energy-saving scheduling.

Manufacturing model	System of objective	Solving algorithm	Reference
Single machine	Energy consumption, total completion time	Dispatching rules, artificial neural network	Mouzon et al.⁴
	Energy consumption, total tardiness	Greedy algorithm	Mouzon and Yildirim⁵
	Energy consumption costs	Genetic algorithm	Shrouf et al.⁶
Parallel machine	Makespan, electricity costs	Genetic algorithm	Moon et al.¹¹
Parallel machine	Energy consumption, makespan	–	He and Liu¹²
Job shop	Energy consumption, makespan	Tabu search	He et al.⁷
	Energy efficiency, robustness, makespan	–	Salido et al.¹⁴
	Energy consumption, makespan	Genetic algorithm	Dai et al.⁸
Flexible job shop	Makespan, machine workload, carbon emission	Meta-heuristic algorithm	Zhang et al.⁹
Flexible job shop	Energy efficiency	Ant colony optimization	Zhang et al.¹⁰
Flow line	Makespan, carbon footprint	–	Fang et al.³
	Makespan with a restriction on peak power consumption	Heuristic	Fang et al.¹³
	Electricity cost, carbon footprint	–	Zhang et al.²¹
	Energy consumption, throughput	Heuristic	Mashaei and Lennartson¹⁷
	Energy efficiency, productivity	–	Chen et al.¹⁸
	Energy cost	Heuristic	Brundage et al.¹⁹
	Energy cost	–	Zanoni et al.²⁰
Hybrid flow line	Electric power cost, makespan	Ant colony optimization	Luo et al.¹⁵
	Total weighted tardiness, carbon footprint, peak power	The non-dominated sorting-based genetic algorithm II (NSGA-II)	Liu and Huang²²
	Makespan, total energy consumption	Meta-heuristic	Dai et al.¹⁶

Looking at the existing researches for flow line scheduling, the academic’s measures rarely focus on the energy-saving scheduling problem about permutation flow line. In this article, we focus on the energy saving of the permutation flow line scheduling problem (PFLSP) with two optimization objectives which are simultaneous minimizing total flowtime and energy consumption. Based on the principle of the fixed energy,²³ which is the energy demand of all activated machine components ensuring the operational readiness and the basic of normal operation of the machine tool, it is very significative to reduce the fixed energy consumption (FEC) of the machine tool in order to decrease the total energy consumption of PFLSP during the whole machining process.

The rest of the article is organized as follows. First, a general multi-objective PFLSP is described. Then, a novel energy-saving model for PFLSP is illustrated. After that, the well-known NSGA-II algorithm is introduced for solving the multi-objective optimization problem. Two numerical experiments on production scheduling problem are simulated. Finally, conclusions are given.

Description of multi-objective PFLSP

The PFLSP is described as follows: the set of $J = {1, 2, \dots, n}$ denotes n jobs, and the set of $M = {1, 2, \dots, m}$ denotes m machines. Each job follows the same order of the machines and passes through each machine only once. The constraints of the PFLSP are the following:

One machine can process at most one operation at a time.

For the first machine, all jobs are available at time $t = 0$ .

There are no precedence relationships between different jobs

There are precedence relationships between different operations of one job. That is, one job can start on machine j only when it is completed on machine $j - 1$ .

Preemption is not permitted; that is, once an operation is started, it must be completed without interruption.

The operating sequences of the jobs are the same on every machine. That is to say, if one job is at the ith operation on machine 1, then this job will be at the ith position on all the machines.

The objective of PFLSP is to seek a schedule that minimizes the total flowtime and the total energy consumption.

A model of energy-saving scheduling for the PFLSP

FEC of machine tools

Hu²⁴ regards the energy system of the computer numerical control (CNC) machine tool as a multiple energy source system. The energy consumption subsystems of the machine tool mainly include main driving system, feed shaft system, hydraulic system, cooling and lubrication system, and auxiliary system and periphery system. The electrical components of the energy consumption subsystems are shown in Table 2.

Table 2.

Electrical components in machine tools.

Energy consumption subsystems	Electrical components
Main driving system	Components of variable velocity variable frequency of main spindle
	Main spindle motor
	Main spindle mechanical system
Feed shaft system	Servo drives
	Servo motor
	Feed shaft mechanical system
Cooling and lubrication system	Cooler pump motor
Cooling and lubrication system	Lubricant pump motor
Auxiliary system	Computer and display
	Fan
	Lightning
Periphery system	Chip conveyer motor
Periphery system	Tool change arm motor
Hydraulic system	Hydraulic unit motor

At systems’ level, the energy consumption of each component (or subsystem) of CNC machine tool has some characteristics as follows: (1) because the energy consumption of cooling and lubrication system, auxiliary system, periphery system, and hydraulic system depends on whether these subsystems are running or not, it is relatively independent of the cutting load of the machine tool and can be approximated to a constant and (2) the energy consumption of the main driving system and feed shaft system is decided by the cutting load. Therefore, the above-mentioned systems can be divided into load-related energy consumption systems (LRECS) and load-unrelated energy consumption systems (LUECS).²⁴ The energy balance equation is constructed as follows

\begin{array}{l} E_{i n} (t) = \sum_{i = 1}^{n} \int_{t_{0}}^{t} g_{i} (t) \cdot C_{i} d t + \int_{t_{0}}^{t} P_{s p} (t, n, M_{s p}, B_{s p}, v, a_{p}, f) d t \\ + \sum_{j = 1}^{m} \int_{t_{0}}^{t_{j}} P_{a x_{j}} (t, ω, M_{j}, B_{j}, f, T) d t (i = 1, 2, \dots, n; j = 1, 2, \dots, m) \end{array}

(1)

where $\sum_{i = 1}^{n} g_{i} (t) \cdot C_{i}$ represents the power of LUECS, n represents the number of LUECS, $g_{i} (t) = {\begin{matrix} 1 the i th subsystem is running \\ 0 the i th subsystem is not running \end{matrix}$ represents the used state of LUECS, and $C_{i}$ represents the power of the ith LUECS and is unrelated to time t. $P_{sp} (n, M_{sp}, B_{sp}, v, a_{p}, f)$ , which is the power of main spindle system, is a function of the rotating speed n, friction M, damping coefficient B, cutting speed v, cutting depth $a_{p}$ , and feed speed f. $P_{a x_{j}} (ω, M_{j}, B_{j}, f, T)$ , which is the power of the jth feed shaft, is a function of motor speed $ω$ , friction torque $M_{j}$ , damping coefficient $B_{j}$ , feed speed f, and cutting torque T.

Equation (1) reveals that the energy consumption of the machine tool is produced by LUECS when the machine is in a state of processing preparation. That is, $E_{in} (t) = \sum_{i = 1}^{n} \int_{t_{0}}^{t} g_{i} (t) \cdot C_{i} dt$ . Due to defining the demand of all activated machine components ensuring the operational readiness of the machine tool as fixed power by Li et al.,²³ $P_{F} = \sum_{i = 1}^{n} g_{i} (t) \cdot C_{i}$ can be treated as the fixed power of the machine tool according to equation (1). Hence, the FEC is the integral of fixed power at the time interval $(t_{0}, t)$ .

In addition, Zhou et al.²⁵ point out that there are five states of machine tool use including standby, starting, idling, air-cutting, and cutting:

Standby state represents activating machine components and ensuring the operational readiness of the machine tool.

Starting state represents the starting and accelerating of the spindle motor.

Idling state represents the spindle’s steady rotation at a certain speed.

Air-cutting state represents starting the feed motor and feeding or retracting the cutting tool.

Cutting state represents cutting workpiece.

Therefore, this article focuses on energy saving by reducing the FEC during the standby state of the machine tools of permutation flow line.

Energy-saving scheduling based on FEC

As mentioned before, FEC is closely related to decreasing the energy consumption of the machine during production process in manufacturing industry. At the existing manufacturing plant, the standby mode of the machine is inevitable in most situations. Especially for flow line production, there are some standby machines because of different production rhythm of each machine and adjusting of job order. Figure 1(a) and (b) shows two schedule of PFLSP. Each one of job set ( $J_{1}$ , $J_{2}$ , $J_{3}$ ) follows the same operating sequences on each machine of set ( $M_{1}$ , $M_{2}$ , $M_{3}$ ) and passes through every machine on the flow line. $J_{ij}$ represents that the ith job is machined on the jth machine, and the value of $J_{ij}$ is shown in Table 3.

Figure 1.

Different scheduling on the same flow line with identical jobs: J_ij represents that the ith job is machined on the jth machine.

Table 3.

Jobs processing time on each machine (min).

Jobs	Machines
Jobs	$M_{1}$	$M_{2}$	$M_{3}$
$J_{1}$	3	2	1
$J_{2}$	3	1	2
$J_{3}$	2	1	3

According to Figure 1, the makespan of each job for schedule (a) is ${6 (J_{1}), 11 (J_{2}), 9 (J_{3})}$ , and the makespan of each job for schedule (b) is ${11 (J_{1}), 6 (J_{2}), 9 (J_{3})}$ , where $S_{a} = {J_{1}, J_{3}, J_{2}}$ represents schedule (a) and $S_{b} = {J_{2}, J_{3}, J_{1}}$ represents schedule (b). Because the sum of all makespans for schedule equals the total flowtime, both total flowtime of schedules are 26 min. If optimization objective of scheduling is minimizing total flowtime, both schedules can be chosen as the best solution. However, schedule (a) should be chosen as the best solution on the condition that optimization objective of scheduling is minimizing energy consumption. The reasons of the above chosen solution are as follows. In schedule (a), the time of standby ① and ② is total 5 min for $M_{2}$ , and the time of standby ③ is 5 min for $M_{3}$ . But in schedule (b), the time of standby ④, ⑤, and ⑥ is total 6 min for $M_{2}$ , and the time of standby ⑦ and ⑧ is total 5 min for $M_{3}$ . The standby time and FEC of $M_{1}$ and $M_{3}$ are equal in schedules (a) and (b), but standby time and FEC of $M_{2}$ in schedule (a) are less than themselves in schedule (b). In addition, for the production mode of permutation flow line, once the process procedure of jobs is confirmed, the processing time and the energy consumption for job machining are also confirmed. And then, the variation in the total energy consumption of permutation flow line mainly depends on the FEC derived from standby state of each machine tool. Therefore, total energy consumption in schedule (a) is less than that in schedule (b).

Energy-saving model for multi-objective PFLSP

Sections “FEC of machine tools” and “Energy-saving scheduling based on FEC” illustrate that the energy consumption of LRECS is related to the specific processing technology and the energy consumption of LUECS is related to the working state of specific machine components. Once a process is determined, the energy consumption, which is produced by LRECS and LUECS, is inevitable for the machine during machining process. However, in flow line production, the standby time of the machine can be reduced by scheduling methods in order to decrease the energy consumption of LUECS, which means decreasing FEC. In this section, an energy-saving model for multi-objective PFLSP is proposed, the optimization objectives of which are minimizing total flowtime and minimizing FEC. The parameters are given below:

n is the number of jobs.

m is the number of machines in flow line.

${π_{1}, π_{2}, \dots, π_{n}}$ is a schedule.

$t (i, j)$ is the processing time when job i is processed on machine j, where $i = 1, 2, \dots, n$ , $j = 1, 2, \dots, m$ .

$C (π_{i}, j)$ is the completion time when job $π_{i}$ is processed on machine j.

$F_{total}$ is the total flowtime of a schedule.

$T (π_{i}, j)$ is the standby time after machine j has finished job $π_{i - 1}$ and before job $π_{i}$ started.

$P_{j}^{F}$ is the fixed power of machine j.

$E_{F}$ is the total FEC of standby state of machines in flow line during the whole machining process.

The objective function of scheduling model is as follows

{\begin{matrix} min F_{total} \\ min E_{F} \end{matrix}

(2)

The total flowtime $F_{total}$ and the total FEC $E_{F}$ are calculated by the following formulas:

Completion time $C (π_{i}, j)$

\begin{array}{l} C (π_{1}, 1) = t (π_{1}, 1) \\ C (π_{i}, 1) = C (π_{i - 1}, 1) + t (π_{i}, 1) i = 2, \dots, n \\ C (π_{1}, j) = C (π_{1}, j - 1) + t (π_{1}, j) j = 2, \dots, m \\ C (π_{i}, j) = \max {C (π_{i - 1}, j), C (π_{i}, j - 1)} + t (π_{i}, j) i = 2, \dots, n; j = 2, \dots, m \end{array}

Total flowtime $F_{total}$

F_{total} = \sum_{i = 1}^{n} C (π_{i}, m)

Standby time of machine tools $T (π_{i}, j)$

\begin{array}{l} T (π_{i}, 1) = 0 i = 1, \dots, n \\ T (π_{1}, j) = C (π_{1}, j - 1) j = 2, \dots, m \\ T (π_{i}, j) = \max {C (π_{i}, j - 1) - C (π_{i - 1}, j), 0} i = 2, \dots, n; j = 2, \dots, m \end{array}

Total FEC $E_{F}$

E_{F} = \sum_{j = 1}^{m} \sum_{i = 1}^{n} P_{j}^{F} \cdot T (π_{i}, j) i = 1, \dots, n; j = 1, \dots, m

In conclusion, the energy-saving model for multi-objective PFLSP is as follows

\begin{array}{l} Z = {\begin{cases} \min F_{t o t a l} \\ \min E_{F} \end{cases} \\ S . T . {\begin{cases} C (π_{1}, 1) = t (π_{1}, 1) \\ C (π_{i}, 1) = C (π_{i - 1}, 1) + t (π_{i}, 1) i = 2, \dots, n \\ C (π_{1}, j) = C (π_{1}, j - 1) + t (π_{1}, j) j = 2, \dots, m \\ C (π_{i}, j) = \max {C (π_{i - 1}, j), C (π_{i}, j - 1)} + t (π_{i}, j) i = 2, \dots, n; j = 2, \dots, m \\ F_{t o t a l} = \sum_{i = 1}^{n} C (π_{i}, m) \\ T (π_{i}, 1) = 0 i = 1, \dots, n \\ T (π_{1}, j) = C (π_{1}, j - 1) j = 2, \dots, m \\ T (π_{i}, j) = \max {C (π_{i}, j - 1) - C (π_{i - 1}, j), 0} i = 2, \dots, n; j = 2, \dots, m \\ E_{F} = \sum_{j = 1}^{m} \sum_{i = 1}^{n} P_{j}^{F} \cdot T (π_{i}, j) i = 1, \dots, n; j = 1, \dots, m \end{cases} \end{array}

(3)

Multi-objective evolutionary algorithm for PFLSP

Since there are two objectives included in formula (3) and the flow line scheduling problem is well known as NP-hard problem,²⁶ the application of multiple-objective meta-heuristic algorithm is necessary. NSGA-II is a well-known and high-efficiency multiple-objective evolutionary algorithm offered by Deb et al.²⁷ This algorithm adopts a population of individuals and acquires an approximation of Pareto optimal front. Two primary operations of NSGA-II which have been generally used by the scholars are non-dominated sorting and crowding distance calculating. The non-dominated sorting ranks the solutions in different Pareto fronts. The crowding distance calculating disperses distribution of the solutions in each Pareto front and keeps the diversification of the solutions. Hence, these two functions form the Pareto fronts in each generation of this algorithm.

The flow chart of NSGA-II is shown in Figure 2:

Step 1. Randomly generate initial population $P_{t}$ , the size of which is N. Set $t = 0$ .

Step 2. According to formula (3), calculate objective function of each individual in $P_{t}$ . Then, use non-dominated sorting algorithm for the initial population $P_{t}$ .

Step 3. Use genetic evolution operations (selection, crossover, mutation) for $P_{t}$ to obtain the offspring population $Q_{t}$ .

Step 4. Obtain new population $R_{t}$ by merging $P_{t}$ and $Q_{t}$ and removing the same individuals (reserve one same individuals). The size of $R_{t}$ less than or equal to $2 N$ .

Step 5. According to formula (3), calculate objective function of each individual in $R_{t}$ . Then, use non-dominated sorting algorithm and crowding distance calculating for the objective values of individuals to achieve Pareto fronts. Based on these Pareto fronts and the crowding distance of each Pareto front, the next population $P_{t + 1}$ , the size of which is N, is obtained. Then, set $t = t + 1$ .

Step 6. If the terminate condition (reaching the maximum generation) of this algorithm is satisfy, output the first level of Pareto front of $P_{t}$ and stop the algorithm; Or else, turn to Step 3.

Figure 2.

The flow chart of NSGA-II.

The pseudo code of NSGA-II algorithm is as follows:

Randomly generate initial population $P_{t}$ with size N, set $t = 0$ , set maximum generation;

Use non-dominated sorting for $P_{t}$ ;

while ( $t \leq$ maximum generation)

$P^{temp} \leftarrow P_{t}$ ; $% P_{t}$ is assigned to $P^{t e m p} . %$

Execute selection operation for $P^{temp}$ ;

Execute crossover operation for $P^{temp}$ ;

Execute mutation operation for $P^{temp}$ ;

$Q_{t} \leftarrow P^{temp}$ ; $% P^{t e m p}$ is assigned to $Q_{t} . %$

$R_{t} \leftarrow P_{t} \cup Q_{t}$ ; % The result, obtained by merging $P_{t}$ and $Q_{t}$ , is assigned to $R_{t} . %$

Use non-dominated sorting and crowding distance calculating for $R_{t}$ ; %This step is for obtaining Pareto fronts of $R_{t} . %$

$P_{t + 1}$ ← the top N optimal Pareto solution of $R_{t}$ ; %This step is for constituting new population $P_{t + 1} . %$

$t = t + 1$ ;

end

$Non - dominated__Set$ ← the first level of Pareto fronts of $P_{t}$ ; %This step is for extracting the results of NSGA-II algorithm. %

Output $Non - dominated__Set$ ;

Selection, crossover, and mutation are the three basic genetic evolution operations for searching new solutions beginning from the current population. Tournament selection strategy,²⁸ partially matched crossover (PMX),²⁹ and a single-point mutation policy are adopted in this article.

Numerical illustration

In order to verify the feasibility and effectiveness of the proposed method, the NSGA-II algorithm has been used to solve the energy-saving scheduling for multi-objective PFLSP with two numerical experiments. The first numerical experiment illustrates the trade-off relationship between total flowtime and FEC by demonstrating the distribution of Pareto front. And the numerical instances in the second numerical experiment are increased to further verify the proposed method. The simulation is carried out by utilizing the MATLAB programming language. The experiment tests are carried out on a personal computer with Intel(R) Core(TM)2 Duo E7500 with 2 GB Ram and 2.93 GHz frequency, and Windows 7.

Implementation of proposed method with numerical example

Assuming the following permutation flow line scheduling, there are 15 jobs waiting to be scheduled and processed on the same flow line. There are five machines on the flow line, and each job must successively pass through these machines. The fixed power of the machines and the processing time of each job on each machine are shown in Table 4. The optimal parameter combinations for NSGA-II are determined by performing a series of experiments with various parameter settings before conducting actual runs to gather the results. The candidate values of NSGA-II parameters are as follows: population size $\in {20, 50, 100}$ , maximum generation $\in {50, 100, 200}$ , crossover probability $\in {0.7, 0.8, 0.9}$ , and mutation probability $\in {0.01, 0.05, 0.1}$ . In the parameter test, only one parameter is changed and the others are constant. The results show that the best parameter combination of NSGA-II includes the population size 50, the maximum generation 100, the crossover probability 0.8, and the mutation probability 0.05. The NSGA-II algorithm was run 10 times to obtain the total flowtime and the FEC.

Table 4.

Relative data of fixed power of machine and relative data of jobs processing time (min).

Job number	Machines
	Machine label	M1	M2	M3	M4	M5
	Fixed power (W)	769	802	1290	967	1166
1		3	4	6	10	3
2		4	5	2	8	8
3		7	10	8	4	7
4		9	10	2	2	6
5		2	2	5	9	9
6		2	1	1	8	3
7		5	7	8	2	5
8		2	9	2	9	8
9		9	7	3	8	1
10		8	5	7	2	2
11		9	6	9	4	7
12		7	9	3	2	4
13		8	8	2	2	9
14		1	2	6	5	9
15		8	2	10	1	4

The calculating results and the Pareto optimal front distribution are, respectively, shown in Table 5 and Figure 3. The Pareto optimal front is constituted by the points’ set which include (932, 1145.8), (919, 1207.8), (915, 1290.4), (912, 1348.7). It obviously reflects a significant trade-off between total flowtime and FEC for the PFLSP. The decision-makers can choose the scheduling scheme according to their preference for saving energy or saving flowtime. Energy-saving scheduling scheme consumes less energy than other time saving–based scheduling scheme. The energy-saving percent is indeed improved with time-saving percent deteriorating. The comparison principle is based on the percent variation which is caused by choosing energy-saving scheduling scheme instead of choosing the time-saving one. Specifically, contrasting to the best time-saving scheduling (total flowtime is 912 min, FEC is 1348.7 W h), the scheduling scheme of the most energy-saving (total flowtime is 932 min, FEC is 1145.8 W h) can decrease 15.0% energy consumption with merely increasing 2.2% total flowtime.

Table 5.

The optimal solutions set of total flowtime and FEC.

No.	Total flowtime (min)	Fixed energy consumption (W h)	Corresponding scheduling scheme
1	912	1348.7	6, 14, 8, 15, 2, 1, 7, 12, 5, 3, 9, 10, 13, 11, 4
2	915	1290.4	6, 14, 5, 1, 7, 3, 10, 12, 2, 15, 8, 11, 9, 13, 4
3	919	1207.8	6, 14, 8, 15, 2, 1, 7, 12, 5, 3, 9, 11, 4, 10, 13
4	919	1207.8	6, 14, 8, 15, 2, 1, 7, 12, 5, 3, 11, 9, 4, 10, 13
5	919	1207.8	6, 14, 5, 1, 7, 12, 2, 15, 8, 11, 3, 9, 4, 10, 13
6	932	1145.8	6, 14, 5, 8, 7, 1, 12, 15, 2, 3, 11, 4, 9, 13, 10

Figure 3.

The Pareto optimal front distribution of total flowtime versus FEC.

Implementation of proposed method with benchmark problems

To further prove the effectiveness of the proposed method, in this numerical experiment, we consider nine sets of benchmark data from Taillard,³⁰ which include 20 jobs machined on 5 machines (Ta 20 × 5), 20 jobs machined on 10 machines (Ta 20 × 10), 20 jobs machined on 20 machines (Ta 20 × 20), 50 jobs machined on 5 machines (Ta 50 × 5), 50 jobs machined on 10 machines (Ta 50 × 10), 50 jobs machined on 20 machines (Ta 50 × 20), 100 jobs machined on 5 machines (Ta 100 × 5), 100 jobs machined on 10 machines (Ta 100 × 10), and 100 jobs machined on 20 machines (Ta 100 × 20). The fixed power of these machines satisfies uniform distribution of $U [700, 1500]$ , and the processing time of these jobs satisfies uniform distribution of $U [1, 99]$ . In this numerical experiment, the parameters of algorithm are the same as the parameters in the first numerical experiment: the population size 50, the maximum generation 100, the crossover probability 0.8, and the mutation probability 0.05. The NSGA-II algorithm was run 10 times to, respectively, obtain the best total flowtime and the best FEC. The results of benchmark related to PFLSP are shown in Table 6, where T1 represents the minimum total flowtime, E1 represents the corresponding FEC related to minimum total flowtime, E2 represents the minimum FEC, and T2 represents the corresponding total flowtime related to the minimum FEC. According to the results of benchmark instances, we know that the values of FEC and total flowtime are increased with scheduling scale enlarging. Furthermore, contrasting to the minimum total flowtime scheduling, the scheduling scheme of the most energy-saving can achieve the reducing rate of energy consumption (the calculating formula is (E1 − E2)/E1) with a small total flowtime increasing (the calculating formula is (T2 − T1)/T1). In other words, the energy-saving percent improvement is greater than time-saving percent degeneration. Therefore, the energy-efficient scheduling for permutation flow line can decrease energy consumption with less total flowtime increasing.

Table 6.

The results of benchmark instances.

Scheduling scale	Total flowtime		FEC		Percent variation caused by choosing energy-saving scheduling instead of time-saving scheduling (%)
Scheduling scale	Min (T1)	Corresponding FEC (E1)	Min (E2)	Corresponding total flowtime (T2)	Total flowtime increasing (T2 − T1)/T1	Fixed energy consumption decreasing (E1 − E2)/E1
Ta 20 × 5	14,864	26,760	23,232	15,071	1.4	13.2
Ta 20 × 10	17,023	76407	61,471	18,141	6.6	19.5
Ta 20 × 20	34,210	283,905	261,738	36,353	6.3	7.8
Ta 50 × 5	70,270	34,584	31,802	72,183	2.7	8.0
Ta 50 × 10	94,902	96,899	76,867	97,713	3.0	20.7
Ta 50 × 20	128,941	344,124	317,807	132,146	2.5	7.6
Ta 100 × 5	291,605	72,864	65,529	300,722	3.1	10.1
Ta 100 × 10	320,450	107,196	94,876	335,096	4.6	11.5
Ta 100 × 20	409,328	412,800	363,762	423,554	3.5	11.9

FEC: fixed energy consumption.

Managerial insights and conclusion

This article has studied the energy-saving scheduling problem for permutation flow line and presents a method of multi-objective scheduling for energy-saving. First of all, a multiple energy source system in CNC machine tool is expounded. On this basis, we proposed that the total energy consumption of flow line will be decreased by reducing the FEC of the machine tools with energy-saving scheduling. Then, for solving this scheduling problem, a mathematical model which is on basis of reducing the FEC of machine tools is proposed. The optimization objective of this model is to simultaneously minimize the total flowtime and the FEC. Furthermore, in order to solve the multi-objective PFLSP, which is a well-known NP-hard problem, the NSGA-II is adopted. Finally, numerical experiments are executed for verifying the proposed method.

The results of two numerical experiments show a significant trade-off between total flowtime and FEC for the PFLSP. Therefore, the decision-makers can choose the energy-saving scheduling scheme or time-saving scheduling scheme according to their preference for guiding production. Moreover, if the energy-saving scheduling scheme is selected instead of time-saving scheduling scheme, the energy-saving percent improvement is greater than time-saving percent degeneration.

Certainly, many directions of energy-saving scheduling for flow line are worth of further study. For optimization objectives, production cost, quality, and customer satisfaction may be considered to be combined with energy-saving target to form different multi-objective scheduling problem. Furthermore, limited buffer, sequence-dependent setup times, precedence constraints, reentrant, preemption, and so on can also be considered into this problem and worthy of further discussion.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the State Key Program of National Natural Science Foundation of China (project no. 51375513) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20120191110001).

References

Evans

. Saving energy in manufacturing with smart technology. World Energy 2003; 6(2): 112–118.

National Association of Manufacturers. Efficiency and innovation in U.S. manufacturing energy use. National Association of Manufacturers, 2005, http://www.osti.gov/scitech/biblio/1216346/

Fang

Uhan

Zhao

. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. J Manuf Syst 2011; 30(4): 234–240.

Mouzon

Yildirim

Twomey

. Operational methods for minimization of energy consumption of manufacturing equipment. Int J Prod Res 2007; 45(18–19): 4247–4271.

Mouzon

Yildirim

. A framework to minimise total energy consumption and total tardiness on a single machine. Int J Sustain Eng 2008; 1(2): 105–116.

Shrouf

Ordieres-Meré

García-Sánchez

. Optimizing the production scheduling of a single machine to minimize total energy consumption costs. J Clean Prod 2014; 67: 197–207.

Liu

Cao

. A bi-objective model for job-shop scheduling problem to minimize both energy consumption and makespan. J Cent South Univ T 2005; 12(2): 167–171.

Dai

Tang

. Energy-aware integrated process planning and scheduling for job shops. Proc IMechE, Part B: J Engineering Manufacture 2015; 229(Suppl. 1): 13–26.

Zhang

Jiang

. Low-carbon scheduling and estimating for a flexible job shop based on carbon footprint and carbon efficiency of multi-job processing. Proc IMechE, Part B: J Engineering Manufacture 2015; 229(2): 328–342.

10.

Zhang

Jiang

Zhang

. Energy-aware integration of process planning and scheduling of advanced machining workshop. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(11): 2040–2055.

11.

Moon

Shin

Park

. Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency. Int J Adv Manuf Tech 2013; 68(1–4): 523–535.

12.

Liu

. Methods for integrating energy consumption and environmental impact considerations into the production operation of machining processes. Chin J Mech Eng 2010; 23(4): 428.

13.

Fang

Uhan

Zhao

. Flow shop scheduling with peak power consumption constraints. Ann Oper Res 2013; 206(1): 115–145.

14.

Salido

Escamilla

Barber

. Energy efficiency, robustness, and makespan optimality in job-shop scheduling problems. Artificial Intelligence for Engineering Design Analysis & Manufacturing 2015. DOI: 10.1017/S0890060415000335.

15.

Luo

Huang

. Hybrid flow shop scheduling considering machine electricity consumption cost. Int J Prod Econ 2013; 146(2): 423–439.

16.

Dai

Tang

Giret

. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robot CIM: Int Manuf 2013; 29(5): 418–429.

17.

Mashaei

Lennartson

. Energy reduction in a pallet-constrained flow shop through on–off control of idle machines. IEEE T Autom Sci Eng 2013; 10(1): 45–56.

18.

Chen

Zhang

Arinez

. Energy-efficient production systems through schedule-based operations. IEEE T Autom Sci Eng 2013; 10(1): 27–37.

19.

Brundage

Chang

. Energy efficiency management of an integrated serial production line and HVAC system. IEEE T Autom Sci Eng 2014; 11(3): 789–797.

20.

Zanoni

Bettoni

Glock

. Energy implications in a two-stage production system with controllable production rates. Int J Prod Econ 2014; 149: 164–171.

21.

Zhang

Zhao

Fang

. Energy-conscious flow shop scheduling under time-of-use electricity tariffs. CIRP Ann: Manuf Techn 2014; 63(1): 37–40.

22.

Liu

Huang

. Reduction of power consumption and carbon footprints by applying multi-objective optimisation via genetic algorithms. Int J Prod Res 2014; 52(2): 337–352.

23.

Zein

Kara

. An investigation into fixed energy consumption of machine tools. In: Hesselbach

Herrmann

(eds) Glocalized solutions for sustainability in manufacturing. Berlin, Heidelberg: Springer, 2011, pp.268–273.

24.

. Energy consumption characteristics of multiple-component of modern CNC machine tools. PhD Thesis, Chongqing University, Chongqing, China, 2012.

25.

Zhou

Liu

Cai

. An energy-consumption model for establishing energy-consumption allowance of a workpiece in a machining system. J Clean Prod 2015, http://dx.doi.org/10.1016/j.jclepro.2015.10.090

26.

Sun

Zhang

Gao

. Multi-objective optimization algorithms for flow shop scheduling problem: a review and prospects. Int J Adv Manuf Tech 2011; 55(5–8): 723–739.

27.

Deb

Pratap

Agarwal

. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE T Evolut Comput 2002; 6(2): 182–197.

28.

Yang

Soh

. Structural optimization by genetic algorithms with tournament selection. J Comput Civil Eng 1997; 11(3): 195–200.

29.

Goldberg

Lingle

. Alleles, loci, and the traveling salesman problem. In: Proceedings of the first international conference on genetic algorithms and their applications, Pittsburgh, PA, 24–26 July 1985, pp.154–159. Hillsdale, NJ: Lawrence Erlbaum Associates, Inc.

30.

Taillard

. Benchmarks for basic scheduling problems. Eur J Oper Res 1993; 64(2): 278–285.

Multi-objective energy-saving scheduling for a permutation flow line

Abstract

Keywords

Introduction

Description of multi-objective PFLSP

A model of energy-saving scheduling for the PFLSP

FEC of machine tools

Energy-saving scheduling based on FEC

Energy-saving model for multi-objective PFLSP

Multi-objective evolutionary algorithm for PFLSP

Numerical illustration

Implementation of proposed method with numerical example

Implementation of proposed method with benchmark problems

Managerial insights and conclusion

Footnotes

Declaration of conflicting interests

Funding

References