Sage Journals: Discover world-class research

Abstract

Most traditional scheduling problems prioritize optimizing production efficiency, cost, and quality. However, with gradually increasing energy consumption and environmental pollution, the novel “energy-efficient scheduling” model has received increasing attention from scholars and engineers. This scheduling model focuses on reducing workshop energy consumption and environmental pollution and has become a hot topic in the scheduling area. This article proposes a new energy-efficient scheduling mathematical model considering productivity, energy efficiency, and noise reduction with flexible spindle speed for the job shop environment. This model considers the machining spindle speed that impacts the production time, power, and noise to be flexible and an independent decision-making variable. In addition, the evaluation methods of productivity, energy consumption, and noise are presented in this model. To cleanly solve this mixed integer programming model, an effective multi-objective genetic algorithm based on simplex lattice design is proposed. The corresponding encoding/decoding method, fitness function, and crossover/mutation operators are designed based on the features of this problem. To evaluate the performance of this method, three instances with different scales have been designed. The results demonstrate the effectiveness of the proposed model for the energy-efficient job shop scheduling problem.

Keywords

Energy-efficient scheduling job shop scheduling multi-objective optimization energy consumption noise emission

Introduction

Currently, environmental and energy problems have become worldwide concerns that receive increasing attention from most countries. In the future, energy consumption will continue to increase with worldwide development. For example, in 2040, China and India will consume twice as much energy as they did in 2013, as shown in Figure 1 (Energy Information Administration (EIA), 2013).¹ Along with increasing energy consumption, environmental problems are becoming increasingly severe. Therefore, how to effectively reduce carbon emissions and energy consumption has become a hot topic for research. Since the beginning of the industrial revolution, industry has consumed significant energy for production. Manufacturing enterprises are responsible for approximately one-half of the total global energy consumption, 38% of CO₂ emissions, and significant pollution.^2,3 Therefore, manufacturing enterprises urgently need sustainable development to achieve economic, ecological, and social goals.^4,5

Figure 1.

Energy consumption in China, USA, and India for 1990–2040 (EIA, 2013).

A manufacturing system is an input–output system that converts energy and material resources into final products, and scheduling is one of the most important sub-systems in a manufacturing system. Taking the process plans of jobs as inputs, the scheduling task schedules the operations of all the jobs on machines while satisfying precedence relationships in the process plans. Scheduling is the link between the two production steps, which are the preparation processes and implementation processes. Traditional studies focus more on productivity and cost and rarely address other aspects, particularly environmental issues. However, Gutowski et al.^6,7 noted that more than 85% of the energy consumed was not directly used for actual processing. This finding implies that efforts to improve energy efficiency that focus solely on the machines or processes may overlook a significant energy saving opportunity.⁸ In fact, scheduling can significantly impact the energy consumption of the entire manufacturing system. Therefore, reasonable scheduling plans are not only able to improve productivity but also can reduce energy consumption and emissions.^2,9,10 In addition, compared to other methods including redesigning machines or processes, shop floor scheduling and plant operation strategies require very little capital investment and can easily be applied to the existing systems.^11,12 Currently, with increasing energy consumption and environmental pollution, a novel “low-carbon scheduling” model has become a hot topic for scheduling.^13,14

Recently, there has been an upswing in studies on low-carbon scheduling.² For the single-machine scheduling environment, Mouzon et al.³ proposed a multi-objective mathematical programming model and several algorithms for a single computer numeric control (CNC) machine scheduling problem considering the goals of reducing energy consumption and total completion time. Mouzon and Yildirim¹³ applied a greedy randomized adaptive search algorithm to a single-machine multi-objective optimization scheduling problem with the objective of minimizing both the total energy consumption and total tardiness. Rager et al.¹⁵ proposed an evolutionary algorithm for energy-oriented parallel machine scheduling. For the flow shop scheduling environment, Fang et al.^16,17 presented several new mathematical programming models of the flow shop scheduling problem that consider peak power load, energy consumption, and the associated carbon footprint in addition to cycle time. Bruzzone et al.¹⁸ proposed an approach that relied on a mixed integer programming model in which the reference schedule was modified to account for energy consumption without changing the jobs’ assignment and sequencing provided by the reference schedule generated by an advanced planning and scheduling (APS) system. Dai et al.¹⁹ proposed an energy-efficient model for flexible flow shop scheduling and developed a genetic-simulated annealing algorithm to solve this problem. Luo et al.²⁰ proposed a new ant colony optimization meta-heuristic considering production efficiency as well as electric power cost for a hybrid flow shop scheduling problem. Keller et al.²¹ developed a heuristic method for the hybrid flow shop scheduling problem considering energy flexibility. For the job shop scheduling environment, Liu et al.⁸ developed a multi-objective scheduling method for the classical job shop scheduling problem (JSP) considering total energy consumption and total weighted tardiness as objectives. Wang et al.,²² Lu et al.,²³ and Yin et al.²⁴ proposed scheduling model focused on reducing energy consumption and environmental pollution at the workshop level, and they developed some new algorithms to solve these problems.

Based on the above review, current studies on the energy-efficient JSP are lacking. Most of the current energy-efficient scheduling studies focus on single machine or flow shop.⁸ However, job shop scheduling is a very important workshop type in the discrete manufacturing industry. All these manufacturing workshops urgently need new methods for sustainable development on the system level. Studies on the low-carbon JSP have only recently begun, and many research topics thus remain unexplored. The motivation of this article has two aspects: from the academic perspective, the models and methods of the energy-efficient JSP have not yet been studied well, and from the application perspective, most workshops in the discrete manufacturing industry use the job shop model. In this article, a new energy-efficient scheduling mathematical model considering productivity, energy efficiency, and noise reduction with flexible spindle speed is proposed for the job shop environment. This model considers the machining spindle speed that impacts production time, power, and noise to be flexible and an independent decision-making variable. This model presents the evaluation methods of productivity, energy consumption, and noise. To effectively solve this mixed integer programming model, an effective multi-objective genetic algorithm (MOGA) based on simplex lattice design is proposed. The corresponding encoding/decoding method, fitness function, and crossover/mutation operators are designed according to the features of this problem. Thus, this article can be used in the job shop environment and may significantly reduce energy consumption and noise emission while increasing productivity.

The reminder of this article is organized as follows. Problem formulation is discussed in section “Problem formulation.” A novel multi-objective algorithm for the energy-efficient JSP is proposed in section “MOGA based on a simplex lattice design for low-carbon JSP.” Experimental studies and discussions are reported in section “Experimental studies and discussion.” Section “Conclusion and future studies” offers the conclusion and proposes future studies.

Problem formulation

This article selects productivity, energy consumption, and noise emission as the three low-carbon scheduling optimization objectives. First, the evaluation models for these three objectives are proposed. Then, the mixed integer programming model of the low-carbon JSP is presented based on the above evaluation models.

This article mainly concentrates on the energy-efficient JSP, which considers three objectives. The main aim of this work is to search an optimal schedule from all feasible schedules. The existing research denoted that spindle speed can be viewed as a main factor that can evaluate energy consumption and noise sound. It can reflect relative difference between different schedules on objectives including energy consumption and noise sound. Therefore, objectives are simplified when constructing mathematical model for this energy-efficient JSP. Meanwhile, recent research also shows that energy consumption and noise sound are related to machine process. However, the most existing methods are based on experience or experiments, which is unsuitable for most practical environment and it is not key point of this article.

Evaluation models of productivity, energy consumption, and noise emission

The normal indicators relative to productivity in the workshop scheduling problem include makespan, total flow time, and average/maximum tardiness. The makespan is the most popular indicator and is used to evaluate productivity in this article.^25,26 The following sections describe the evaluation models of energy consumption and noise emission in detail.

Evaluation model of energy consumption

A machine uses its total output power for idling when it does not work for machining: p^l = p^u; when a machine is used to process some parts, some of the output power is used to maintain idling, some is used to process, and some of the power is lost to the loading condition of the machine. This lost power is called the loss of loading power

p^{l} = p^{u} + p^{c} + p^{a}

(1)

where p^l is the input power of the machine; p^µ is the idling power of the machine; p^c is the output power of the machine, also called machining power; and p^α is the loading power loss.

Assuming that the time of processing job j on machine k is t_kj, then, according to equation (1), the energy consumption can be expressed as e_kj

e_{k j} = \int_{0}^{t_{k j}} p_{k j}^{l} (t) d t = \int_{0}^{t_{k j}} p_{k j}^{u} (t) d t + \int_{0}^{t_{k j}} p_{k j}^{c} (t) d t + \int_{0}^{t_{k j}} p_{k j}^{a} (t) d t

(2)

In practical applications, to facilitate the calculation and the actual operation, the idling power of a machine is often used in place of the output power of machining, and establishing an energy consumption matrix is feasible after practice.

The loading loss of power is caused by the loading condition of a machine, which is proportional to the output power p^c in the allowable range. The power balance equation of machining can be expressed as

p^{l} = p^{u} + (1 + α) p^{c}

(3)

where α represents the loading power loss factor of the machine.

Therefore, equation (2) can be converted to the following equation

e_{k j} = \int_{0}^{t_{k j}} p_{k j}^{l} (t) d t = \int_{0}^{t_{k j}} p_{k j}^{u} (t) d t + \int_{0}^{t_{k j}} (1 + α) p_{k j}^{c} (t) d t

(4)

When the process parameters are the same, the energy consumption for machining the same parts is approximately the same, and the machining energy is not much greater than the idling energy consumption. Moreover, the impact of changing α is negligible compared to the energy consumed in the machining process. Therefore, the difference of the energy consumed in the machining process mainly loads from its idling consumption, so equation (4) can be simplified as follows

e_{k j} \approx 0 \int_{0}^{t_{k j}} p_{k j}^{u} (t) d t

(5)

In variable machine parameters, the spindle revolution has a critical role in the idling power of machines; therefore, equation (5) could be further simplified as follows

e_{k j} \approx p_{k j}^{u} (r) \times t_{k j}

(6)

In equation (6), p^u(r) is relative to the spindle speed of machining. In other words, the total power can be replaced by the idle power p^u(r) under different machine rotational speeds for the JSP.

Evaluation model of noise emission

Before evaluating the workshop noise, we must determine the evaluation index. Many physical indicators can be used to measure sound strength, such as sound pressure, sound pressure class, sound intensity, and sound intensity class. The most common indicator is sound pressure class, measured using the well-known unit of decibels (dB). For a machining shop, the noise radiation is wide band and stationary when all machines work at the same processing speed. A weighted method is used to correct such noise. Therefore, this article uses Class A sound pressure to evaluate the radiation of machining noise.

The noise of machining usually comprises structure noise and cutting noise; structure noise is typically evaluated by measuring the noise of idling machines, while cutting noise is due to the dynamic force of cutting. Cao and Yin reported that the cutting power consumption, dynamic cutting force, and cutting noise in the machining system could be regarded as approximately equal if using the same conditions of the process parameters, the fixture, and so on. The machining noise is mostly from the structure noise, which is determined by the machine frame.²⁷

Based on the reported studies, this article established a noise coefficient matrix of the scheduling model based on the spindle idling noise corresponding to the machine.²⁸ In the matrix l_vw = l_v(r), the machine idling noise parameter is associated with the spindle speed and irrelevant to parts.

After establishing the noise coefficient matrix in the scheduling model, we can obtain the noise figure of each machined workpiece. A schedule consists of a number of machining stages of the workpieces. This article uses an equivalent sound Class A to evaluate the noise performance merits in different scheduling environments.^29,30

In equivalent sound Class A, actual noises rarely remain stable and fixed but rather fluctuate up and down over time. In general, acoustic energy within the averaging time of the cycle is used to obtain the average energy in each sound Class A of the fluctuated change happening in a certain period. Then a continuous and stable sound Class A in an equivalent period is selected to represent the loudness. This continuous and stable sound Class A is called an equivalent continuous sound class of the unstable noise, marked by l_eq, which approximates that l_eq works consistently in the period, and is also called equivalent continuous sound Class A or equivalent sound Class A. The definition of the equivalent continuous sound class is the formula

l_{e q} = 10 \lg \frac{1}{T} \int_{0}^{T} 10^{0.1 l_{v}} d t

(7)

where l_v is the instantaneous value of sound Class A in the exposure time and T is the exposure time of the noise.

In the workshop studied in this article, the radiated noise value in each period is stable when the machine processes at the spindle speed. Therefore, equation (7) can be rewritten as

l_{e q} = 10 \lg \frac{\sum_{v} 10^{0.1 l_{v}} t_{v}}{\sum_{v} t_{v}}

(8)

where l_v is the sound Class A measured in v paragraphed time and t_v is the v paragraphed time.

Based on the above evaluation modes of productivity, energy consumption, and noise emission, a mixed integer programming model of the low-carbon JSP is proposed.

Mixed integer programming model of low-carbon JSP

The definition of the low-carbon JSP is as follows: a set of jobs J = {1, 2,…, n} are to be processed by a set of machines M = {1, 2,…, m}. The process of each job on each machine is pre-determined, and each job could be processed by a different machining speed according to the machine. The spindle speeds of a set of machines are represented by S = {s₁, s₂,…, s_s}, corresponding to the machining time of each spindle speed. The idling power and noise are known. Two sub-problems exist in this model: one is to determine which machine will process the operation of each job, and the other one is to schedule all operations according to the three objectives.

To solve this problem, the following assumptions are made:

Jobs are independent. Job preemption is not allowed and each machine can handle only one job at a time.

The different operations of one job cannot be processed simultaneously.

All jobs and machines are simultaneously available at time 0.

After a job is processed on a machine, the job is immediately transported to the next machine on its process, and the transmission time is assumed to be negligible.

The setup time for the operations on the machines is independent of the operation sequence and is included in the processing times.

A turn off/on strategy is used to save energy when the machine is idle.

Based on these assumptions and the classical JSP model, the mixed integer programming model of the low-carbon JSP is proposed as follows:

The notations used to explain the model are described below:

n total number of jobs

m total number of machines

r spindle speed of machine, $r \in R$ , R is the set of spindle speed

i, j index of job, i, j = 1,2,…,n

h, k index of machine, h, k = 1,2,…,m

c_ik completion time of job i on machine k

p_ikr processing time of job i on machine k with spindle speed r

q_ikr total power that job i on machine k with spindle speed r (note that q_ikr is equal to the total power, while the total power is associated with idle power p^u(r) according to equations (1)–(6). Therefore, q_ikr is equal to p^u(r) in this article)

v_ikr machining noise of job i on machine k with spindle speed r

M sufficiently large positive number

a_{i h k} = {\begin{matrix} 1, & if machine h processes job i prior to machine k \\ 0, & else \end{matrix}

x_{i j k} = {\begin{matrix} 1, & if job i precedes job j on the same machine k \\ 0, & else \end{matrix}

y_{i k r} = {\begin{matrix} 1, & if job i is processed on machine k with the speed r \\ 0, & else \end{matrix}

Objectives:

Minimizing the makespan

\min \max_{1 \leq i \leq n} {\max_{1 \leq k \leq m} c_{i k}}

(9)

Minimizing the total energy consumption

\min \sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{r \in R} q_{i k r} p_{i k r} y_{i k r}

(10)

Minimizing the noise emission

\min 10 \lg \frac{\sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{r \in R} 10^{0.1 v_{i k r}} p_{i k r} y_{i k r}}{\sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{r \in R} p_{i k r} y_{i k r}}

(11)

Subject to:

The different operations of one job cannot be processed simultaneously

\begin{array}{l} c_{i k} - \sum_{r \in R} p_{i k r} \cdot y_{i k r} + M \cdot (1 - a_{i h k}) \geq c_{i h} \\ i \in {1, 2, …, n}; h, k \in {1, 2, …, m} \end{array}

(12)

Each machine can handle only one job at a time

\begin{array}{l} c_{j k} - \sum_{r \in R} p_{i k r} y_{i k r} + M (1 - x_{i j k}) \geq c_{i k} \\ i, j \in {1, 2, …, n}; k \in {1, 2, …, m} \end{array}

(13)

The job cannot be preempted

\begin{array}{l} c_{i k} = s_{i k} + \sum_{r \in R} p_{i k r} y_{i k r} \\ i \in {1, 2, …, n}; k \in {1, 2, …, m} \end{array}

(14)

Only one spindle speed for each operation should be selected

\sum_{r \in R} y_{i k r} = 1 i \in {1, 2, …, n}; k \in {1, 2, …, m}

(15)

The objective functions are equations (9)–(11). Constraint (12) ensures that the different operations of one job cannot be processed simultaneously. Constraint (13) ensures that each machine can handle only one job at a time. Constraint (14) ensures that the job cannot be preempted. Constraint (15) ensures that only one spindle speed is selected for each operation.

The mixed integer programming model of the energy-efficient JSP developed above can be solved using the mixed integer programming methods. JSP has been proven to be one of the most difficult NP-complete problems.³¹ The energy-efficient JSP is also an NP-complete problem. Finding perfect solutions for large problems in reasonable time is difficult. The model proposed in this article is a multi-objective optimization problem, so the problem considered in this article is very hard. To solve this problem effectively, this article proposes a MOGA based on a simplex lattice design to solve the model and obtains a set of solutions distributed evenly on the Pareto boundary.

MOGA based on a simplex lattice design for low-carbon JSP

Simplex lattice design

Simplex lattice design was used early in the design of mixing formulas. The goal of simplex lattice design is to reasonably distribute the weight of the individual components and to evenly distribute each mixing formula weight in the design space. Then the design is tested separately by each distribution weight to find the best production formulation.³²

If each side of an equilateral triangle in Figure 2(a) is bisected, as shown in Figure 2(b), the three vertices and three midpoints on each side of this triangle are called the second-order lattice point set, marked as {3, 2}, where “3” represents the number of vertices of the regular simplex, with fraction m = 3, and “2” represents the equivalent divided number on each side, so that the order d = 2.

Figure 2.

Simplex lattice design.

If each side of the equilateral triangle is divided into three equal portions, as shown in Figure 2(c), the points are connected by a straight line that is parallel to one side, forming smaller equilateral triangle lattices within the original equilateral triangle. These vertices of the smaller equilateral triangles are called the third-order lattice point set, marked as {3, 3} in the simplex lattice design.

The other lattice point sets can be obtained by this approximate method. Selecting the above regular simplex as the design space of the test, if the points on the regular simplex lattice were chosen as the test points with response to the order, this test design would be called a simplex lattice point design. As known from the regular distribution of the simplex points in design space, this design can ensure that the test points distribute uniformly. In addition, the calculation becomes simpler and more precise.

The algorithm designed in this article applied the simplex lattice point design to various objective weight evaluations, obtained a set of evenly distributed weights using the design of simplex lattice points, guided the potential solution into various solution space directions, and finally obtained the uniform distribution Pareto set.

Simplex lattice design has 6 total points in the {3, 2} point set and 10 total points in the {3, 3} point set. As proven, there are $(m + d - 1)! / d! (m - 1)!$ points in the {m, d} point set, with m groups of d-order lattice points. The question solution in this article has three total objective functions, so m = 3. The order d is a variable in the algorithm. The larger the value of d, the more points there are in the {m, d} lattice point set and the more precise the solution. However, as d increases, the number of points in the {m, d} lattice point set will greatly increase, so the solution should depend on the actual issues with a reasonably designed d value to balance the calculation efficiency and precision.

Encoding and decoding methods

Encoding and decoding methods significantly impact the algorithm performance. Effective encoding and decoding methods can make the algorithm operation easier and improve the calculation performance.

Each chromosome in a scheduling population consists of two parts with the same length, as shown in Figure 3. The first part of a chromosome is the scheduling string. In this article, the scheduling encoding consisting of the job numbers is the operation-based representation. This representation uses an unpartitioned permutation with S_i repetitions of job numbers (where S_i is the total number of operations for job i). In this representation, each job number appears S_i times in the chromosome. By scanning the chromosome from left to right, the fth appearance of a job number refers to the fth operation of this job. The important feature of this representation is that any permutation of the chromosome can be decoded to a feasible solution. This article assumes that there are n jobs. Then the length of the scheduling plan string is equal to $\sum S_{i}$ .

Figure 3.

The chromosome of the problem.

The second part of a chromosome is the speed string. The length of this string is equal to the length of the scheduling string and denotes the selected spindle set of the corresponding operations of all jobs in the scheduling string.

Figure 3 shows an example chromosome. In this example, n is equal to 3, and S₁ = S₂ = S₃ = 3. Therefore, the scheduling string and speed string are made up of nine elements each. For job 1, there are three operations, so three elements of the scheduling string are one. The other elements in the chromosome can be deciphered accordingly.

The permutations can be decoded into semi-active, active, non-delay, and hybrid schedules. The active schedule is adopted in this article. The decoding procedure is as follows: first, scan the scheduling string from left to right, reading the speed information of each operation corresponding to the gene located in the speed string (the speed information can obtain the processing time, energy consumption and noise emission); then insert all the operations sequence and order of the scanned chromosome into the earliest idle time corresponding to the machine that will process this operation. This procedure is followed until all the operations are arranged in the best available station. Meanwhile, the energy consumption of all the process sequences is summed, and noises are equivalently converted to sound Class A.

Initial population and fitness evaluation

The encoding principle of the scheduling string in the chromosome in this article is an operation-based representation. The important feature of this representation is that any permutation of the chromosome can be decoded to a feasible schedule. Permutations cannot break the constraints on the precedence relations of operations. The initial population is randomly generated based on the encoding principle.

Because this is a multi-objective optimization problem, the fitness function should be combined with the makespan, energy consumption, and noise emission. For a scheduling plan, the maximum makespan is T(x), the total energy consumption is E(x), the equivalent sound Class A is N(x), and the fitness function could then be expressed as follows

F (x) = w_{1} \cdot T (x) + w_{2} \cdot E (x) + w_{3} \cdot N (x)

(16)

where w₁, w₂, and w₃ are the weight coefficients of each target and w₁ + w₂ + w₃ = 1.

However, because the dimension of each objective function is not consistent, it cannot be summed directly. Moreover, the differences among the objective values are large, which easily allows the fitness function to be dominated by a single objective. Therefore, each objective should be distributed with dimensionless and normalized uniformity. After the fitness function is made dimensionless and normalized, equation (16) is rewritten as follows

\begin{array}{l} F (x) = w_{1} \cdot \frac{T (x) - T_{\min}}{T_{\max} - T_{\min}} + w_{2} \cdot \frac{E (x) - E_{\min}}{E_{\max} - E_{\min}} \\ + w_{3} \cdot \frac{N (x) - N_{\min}}{N_{\max} - N_{\min}} \end{array}

(17)

where T_max and T_min denote the maximum and the minimum of objective T that can be achieved, respectively. The other parameters denote its significance similarly. After the disposal of equation (17), the range of each objective will be between 0 and 1. The fitness function also stays between 0 and 1, and the value of the fitness function approaches 0 for the same weight of a group, indicating that the scheduling plan performance improves.

To obtain a plurality of scheduling plans, the weight coefficients of the fitness function w₁, w₂, and w₃ are not unique. Their values are generated by the simplex lattice point design described in section “Simplex lattice design.”

Genetic operations

Selection operation

The proportional selection method is used as the selection operation. Using the probability of the proportion to individual fitness levels to select appropriate individuals, the method generates the random, $rand \in [0, 1]$ , if $\sum_{j = 1}^{i - 1} f_{j} / \sum_{j = 1}^{Pop_size} f_{j} < rand \leq \sum_{j = 1}^{i} f_{j} / \sum_{j = 1}^{Pop_size} f_{j}$ , and then selects individual i, where f_i is the fitness level of individual i.

Crossover operation

The single-point crossover method is used for the crossover operations, with the following steps (an example is shown in Figure 4):

Step 1: randomly select two individuals in the population as parents A and B and generate a random integer x following the length l of the front portion of chromosome string, where 1 < x < l.

Step 2: exchange the gene locus of the front portion and the rear portion of parents A and B before gene X and generate the children A and B, respectively.

Step 3: scan the excess and the missing genes in the front portion of the children chromosomes A and B, use the missing genes to modify the excess genes, and adjust the modified genes according to the revolution of the front individual of the crossover to ensure the legitimacy of the chromosome.

Figure 4.

Crossover operation.

Mutation operation

The mutation operation is divided into two parts. The detailed steps are as follows (an example is shown in Figure 5):

Step 1: for the first part of the parent chromosomes, randomly select two positions and mutually exchange the sequences in the two positions. Meanwhile, exchange the genes in the rear part of the chromosomes that represent the revolution information mutually as well.

Step 2: for the rear parts of the parent chromosome, randomly select a gene representing the revolution information if it has various revolution selections and randomly select the rest.

Figure 5.

Mutation operation.

A basic schematic of the mutation process is described as follows.

Elite strategy

To maintain the number of outstanding individuals in the population or species and ensure that the algorithm quickly converges to the optimal solution, the quality protection strategy is normally used in the algorithm. The best individual of the fitness is selected from the parent generation G of proportions during the evolution of each generation of the population and, directly entering the next generation of the population, the individuals of the remaining proportion (I-G) are generated by the mutation operation of crossover. This process ensures that the individuals of the offspring population and the parent population are consistent.

Framework of the proposed MOGA for the low-carbon JSP

Based on the key operations described above, the working steps of the algorithm procedure are as follows (the flowchart is shown in Figure 6):

Step 1: randomly generate an initial population and set parameters, including the simplex lattice design order d, the number of individuals of population NIND, the maximum iteration number MAXGEN, the quality protection ratio G, the crossover probability XOVR, and the mutation probability MUTR.

Step 2: calculate the fitness value of each individual in the population to determine whether the algorithm termination condition is satisfied or not. If the condition is satisfied, output the optimal results. Otherwise, perform the following steps.

Step 3: compare the pros and cons of the fitness value for each individual in the population and perform the operation of quality protection to select a better individual for the proportion G of fitness. Directly enter the next generation of the population.

Step 4: perform the selection operation on the population; select two parent individuals by a certain probability according to the fitness value of the individuals.

Step 5: perform the crossover operation on the selected parent individuals using the crossover probability XOVR to generate two interim individuals.

Step 6: MUTR performs the mutation operation on the interim individuals using the mutation probability. Generate two children individuals and put them into the next-generation population.

Step 7: check the number of individuals in the new generation population m. If m < NIND, return to Step 4; if m = NIND, replace the old population with the new generation population, add one to the generation number, and return to Step 2.

Figure 6.

The flowchart of the MOGA.

Experimental studies and discussion

The proposed algorithm was coded in MATLAB programming and implemented on a computer with a 2.0 GHz Core (TM) 2 Duo CPU. The algorithm designed in section “MOGA based on a simplex lattice design for low-carbon JSP” applied the simplex lattice point design to various objective weight evaluations, obtained a set of evenly distributed weights using the design of simplex lattice points, guided the potential solution into various solution space directions, and finally obtained the uniform distribution Pareto set. To evaluate the performance of this method, three instances with different scales are designed.

Experiment 1 (4 × 5)

Table 1 illustrates the data of instance 1.

Table 1.

Data of instance 1 (4 jobs and 5 machines).

Job	Process	Machine	Spindle speed (r/min)	Processing time (min)	Unload power (kW)	Energy consumption (kW h)	Unload noise (dB)
1	1-1	1	200	14	2	0.47	75.30
			400	7	5	0.58	83.80
			600	6	8	0.80	88.60
	1-2	2	100	7	2	0.23	74.20
			200	6	4	0.40	78.60
	1-3	3	300	8	4	0.53	77.30
			500	7	7	0.82	80.60
2	2-1	5	400	7	5	0.58	80.00
			500	6	8	0.80	82.60
			600	5	10	0.83	86.30
	2-2	2	100	4	2	0.13	74.20
			200	3	4	0.20	78.60
	2-3	4	200	7	3	0.35	79.00
			400	4	5	0.33	80.20
3	3-1	1	200	6	2	0.20	75.30
			400	5	5	0.42	83.80
			600	4	8	0.53	88.60
	3-2	4	200	5	3	0.25	79.00
			400	4	5	0.33	80.20
	3-3	5	400	13	5	1.08	80.00
			500	12	8	1.60	82.60
			600	8	10	1.33	86.30
4	4-1	3	300	9	4	0.60	77.30
			500	6	7	0.70	80.60
	4-2	4	200	6	3	0.30	79.00
			400	3	5	0.25	80.20
	4-3	1	200	5	2	0.17	75.30
			400	3	5	0.25	83.80
			600	2	8	0.27	88.60

In the solution, first take the maximum makespan, total processing energy consumption, and equivalent sound Class A of an individual objective and optimize them to obtain T_min = 22, T_max = 35; E_min = 4.82, E_max = 6.79; and N_min = 77.80, N_max = 84.80. Thus, the fitness function of the algorithm changes to the following

\begin{array}{l} F (x) = w_{1} \cdot \frac{T (x) - 22}{13} + w_{2} \cdot \frac{E (x) - 4.82}{1.97} \\ + w_{3} \cdot \frac{N (x) - 77.80}{7} \end{array}

(18)

During the algorithm operation, set the relevant parameters to the following: the simplex lattice point design order d = 5, the number of population individuals NIND = 100, the evolution algebra order MAXGEN = 200, the quality protection ration G = 10%, the crossover probability XOVR = 0.8, and the mutation probability MUTR = 0.6. After operating the algorithm through many iterations, obtain the problem solution set, as shown in Table 2. Figure 7 shows the space distribution of the solution set, and Figure 8 shows the Gantt chart of scheduling scheme 13.

Table 2.

Scheduling schemes of case 1.

No.	Weights			T (min)	E (kW h)	N (dB)
No.	T	E	N	T (min)	E (kW h)	N (dB)
1	0	0	1	35	4.89	77.80
2	0	0.2	0.8	35	4.84	77.81
3	0	0.4	0.6	35	4.82	77.85
4	0	0.6	0.4	35	4.82	77.85
5	0	0.8	0.2	35	4.82	77.85
6	0	1	0	35	4.82	77.85
7	0.2	0	0.8	35	4.89	77.80
8	0.2	0.2	0.6	35	4.84	77.81
9	0.2	0.4	0.4	28	4.95	79.06
10	0.2	0.6	0.2	28	4.93	79.13
11	0.2	0.8	0	28	4.93	79.13
12	0.4	0	0.6	26	5.46	79.50
13	0.4	0.2	0.4	27	5.12	79.28
14	0.4	0.4	0.2	28	4.93	79.13
15	0.4	0.6	0	28	4.93	79.13
16	0.6	0	0.4	25	5.68	80.11
17	0.6	0.2	0.2	23	5.59	82.05
18	0.6	0.4	0	22	5.81	83.04
19	0.8	0	0.2	22	5.81	83.04
20	0.8	0.2	0	22	5.81	83.04
21	1	0	0	22	5.81	83.04

Figure 7.

Scatter plot of scheduling schemes of instance 1.

Figure 8.

The Gantt chart of the 13th scheduling scheme of instance 1.

The proposed MOGA is compared with the exact algorithm provided by IBM ILOG CPLEX CP Optimizer tool 12.5 (CP optimizer) for this instance, and the results obtained by the exact method are presented in Figure 9. When only the makespan criteria are considered, the makespan obtained by the MOGA is 22 min, while that obtained by the exact algorithm is 27. Therefore, the proposed MOGA is superior to the exact algorithm.

Figure 9.

The Gantt chart obtained by the exact algorithm.

Experiment 2 (10 × 6)

Table 3 illustrates the data of instance 2.

Table 3.

Data of instance 2 (10 jobs and 6 machines).

Job	Process	Machine	Spindle speed (r/min)	Processing time (min)	Unload power (kW)	Energy consumption (kW h)	Unload noise (dB)
1	1-1	1	100	10	1	0.17	74.10
			200	8	2	0.27	76.50
			300	5	3	0.25	77.80
	1-2	2	300	3	5	0.25	82.30
			500	2	7	0.23	84.40
	1-3	3	200	8	4	0.53	79.70
			400	5	6	0.50	81.40
	1-4	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
2	2-1	2	300	6	5	0.50	82.30
			500	4	7	0.47	84.40
	2-2	3	200	8	4	0.53	79.70
			400	6	6	0.60	81.40
	2-3	5	400	12	6	1.20	83.80
			600	11	7	1.28	85.00
	2-4	6	800	10	8	1.33	87.60
			50	7	2	0.23	72.60
3	3-1	3	200	4	4	0.27	79.70
			400	3	6	0.30	81.40
	3-2	4	1000	4	10	0.67	89.00
			1500	3	14	0.70	89.90
	3-3	6	50	6	2	0.20	72.60
			100	4	5	0.33	75.30
	3-4	2	300	7	5	0.58	82.30
			500	5	7	0.58	84.40
4	4-1	1	100	8	1	0.13	74.10
			200	7	2	0.23	76.50
			300	6	3	0.30	77.80
	4-2	4	1000	5	10	0.83	89.00
			1500	3	14	0.70	89.90
	4-3	5	400	13	6	1.30	83.80
			600	10	7	1.17	85.00
			800	8	8	1.07	87.60
	4-4	6	50	7	2	0.23	72.60
			100	4	5	0.33	75.30
5	5-1	4	1000	6	10	1.00	89.00
			1500	4	14	0.93	89.90
	5-2	1	100	3	1	0.05	74.10
			200	2	2	0.07	76.50
			300	1	3	0.05	77.80
	5-3	3	200	8	4	0.53	79.70
			400	6	6	0.60	81.40
	5-4	2	300	6	5	0.50	82.30
			500	4	7	0.47	84.40
6	6-1	6	50	10	2	0.33	72.60
			100	6	5	0.50	75.30
	6-2	1	100	9	1	0.15	74.10
			200	7	2	0.23	76.50
			300	5	3	0.25	77.80
	6-3	2	300	10	5	0.83	82.30
			500	7	7	0.82	84.40
	6-4	4	1000	5	10	0.83	89.00
			1500	4	14	0.93	89.90
7	7-1	5	400	6	6	0.60	83.80
			600	4	7	0.47	85.00
			800	3	8	0.40	87.60
	7-2	6	50	7	2	0.23	72.60
			100	3	5	0.25	75.30
	7-3	2	300	9	5	0.75	82.30
			500	7	7	0.82	84.40
	7-4	1	100	8	1	0.13	74.10
			200	6	2	0.20	76.50
			300	4	3	0.20	77.80
8	8-1	2	300	8	5	0.67	82.30
			500	6	7	0.70	84.40
	8-2	5	400	12	6	1.20	83.80
			600	9	7	1.05	85.00
			800	7	8	0.93	87.60
	8-3	1	100	9	1	0.15	74.10
			200	7	2	0.23	76.50
			300	4	3	0.20	77.80
	8-4	3	200	6	4	0.40	79.70
			400	4	6	0.40	81.40
9	9-1	5	400	8	6	0.80	83.80
			600	7	7	0.82	85.00
			800	6	8	0.80	87.60
	9-2	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
	9-3	3	200	4	4	0.27	79.70
			400	3	6	0.30	81.40
	9-4	6	50	9	2	0.30	72.60
			100	4	5	0.33	75.30
10	10-1	6	50	5	2	0.17	72.60
			100	3	5	0.25	75.30
	10-2	5	400	3	6	0.30	83.80
			600	2	7	0.23	85.00
			800	1	8	0.13	87.60
	10-3	1	100	11	1	0.18	74.10
			200	8	2	0.27	76.50
			300	6	3	0.30	77.80
	10-4	3	200	7	4	0.47	79.70
			400	5	6	0.50	81.40

In the solution, first take the maximum makespan, total processing energy consumption, and equivalent sound Class A for an individual target and optimize them to obtain T_min = 40, T_max = 61; E_min = 18.13, E_max = 20.81; and N_min = 82.23, N_max = 84.58. Thus, the fitness function of the algorithm is as follows

\begin{array}{l} F (x) = w_{1} \cdot \frac{T (x) - 40}{21} + w_{2} \cdot \frac{E (x) - 18.13}{2.68} \\ + w_{3} \cdot \frac{N (x) - 82.23}{2.35} \end{array}

(19)

During the algorithm operation, set the relevant parameters to the following: the simplex lattice point design order d = 5, the number of population individuals NIND = 300, the evolution algebra order MAXGEN = 200, the quality protection ration G = 10%, the crossover probability XOVR = 0.9, and the mutation probability MUTR = 0.8. After operating the algorithm through many iterations, the problem solution set is shown in Table 4. Figure 10 shows the space distribution of the solution set, and Figure 11 shows the Gantt chart of scheduling scheme 15.

Table 4.

Scheduling schemes of instance 2.

No.	Weight			T (min)	E (kW h)	N (dB)
No.	T	E	N	T (min)	E (kW h)	N (dB)
1	0	0	1	61	19.21	82.23
2	0	0.2	0.8	58	19.02	82.41
3	0	0.4	0.6	58	18.51	82.57
4	0	0.6	0.4	59	18.48	82.82
5	0	0.8	0.2	59	18.20	83.03
6	0	1	0	60	18.13	83.12
7	0.2	0	0.8	56	19.05	82.44
8	0.2	0.2	0.6	55	18.80	82.57
9	0.2	0.4	0.4	53	18.33	82.78
10	0.2	0.6	0.2	52	18.31	82.96
11	0.2	0.8	0	48	18.29	83.45
12	0.4	0	0.6	50	18.53	82.67
13	0.4	0.2	0.4	47	18.45	82.98
14	0.4	0.4	0.2	44	18.48	83.57
15	0.4	0.6	0	45	18.43	83.75
16	0.6	0	0.4	44	18.91	83.20
17	0.6	0.2	0.2	42	18.86	83.65
18	0.6	0.4	0	42	18.55	83.89
19	0.8	0	0.2	40	19.49	84.10
20	0.8	0.2	0	41	19.21	84.07
21	1	0	0	40	19.48	84.23

Figure 10.

Scatter plot of scheduling schemes of instance 2.

Figure 11.

The Gantt chart of the 15th scheduling scheme of instance 2.

Experiment 3 (20 × 5)

Table 5 illustrates the data of instance 3.

Table 5.

Data of instance 3 (20 jobs and 5 machines).

Job	Process	Machine	Spindle speed (r/min)	Processing time (min)	Unload power (kW)	Energy consumption (kW h)	Unload noise (dB)
1	1-1	2	300	6	5	0.50	82.30
			500	4	7	0.47	84.40
	1-2	3	200	8	4	0.53	79.70
			400	6	6	0.60	81.40
	1-3	5	50	7	2	0.23	72.60
			100	5	5	0.42	75.30
2	2-1	1	100	10	1	0.17	74.10
			200	8	2	0.27	76.50
			300	5	3	0.25	77.80
	2-2	2	300	3	5	0.25	82.30
			500	2	7	0.23	84.40
	2-3	3	200	8	4	0.53	79.70
			400	5	6	0.50	81.40
3	3-1	1	100	8	1	0.13	74.10
			200	7	2	0.23	76.50
			300	6	3	0.30	77.80
	3-2	4	1000	5	10	0.83	89.00
			1500	3	14	0.70	89.90
	3-3	5	50	7	2	0.23	72.60
			100	4	5	0.33	75.30
4	4-1	4	1000	6	10	1.00	89.00
			1500	4	14	0.93	89.90
	4-2	3	200	8	4	0.53	79.70
			400	6	6	0.60	81.40
	4-3	2	300	6	5	0.50	82.30
			500	4	7	0.47	84.40
5	5-1	5	50	10	2	0.33	72.60
			100	6	5	0.50	75.30
	5-2	1	100	9	1	0.15	74.10
			200	7	2	0.23	76.50
			300	5	3	0.25	77.80
	5-3	2	300	10	5	0.83	82.30
			500	7	7	0.82	84.40
6	6-1	3	200	4	4	0.27	79.70
			400	3	6	0.30	81.40
	6-2	4	1000	4	10	0.67	89.00
			1500	3	14	0.70	89.90
	6-3	5	50	6	2	0.20	72.60
			100	4	5	0.33	75.30
7	7-1	1	100	11	1	0.18	74.10
			200	8	2	0.27	76.50
			300	6	3	0.30	77.80
	7-2	3	200	7	4	0.47	79.70
			400	5	6	0.50	81.40
	7-3	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
8	8-1	2	300	8	5	0.67	82.30
			500	6	7	0.70	84.40
	8-2	1	100	9	1	0.15	74.10
			200	7	2	0.23	76.50
			300	4	3	0.20	77.80
	8-3	3	200	6	4	0.40	79.70
			400	4	6	0.40	81.40
9	9-1	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
	9-2	3	200	4	4	0.27	79.70
			400	3	6	0.30	81.40
	9-3	5	50	9	2	0.30	72.60
			100	4	5	0.33	75.30
10	10-1	1	100	10	1	0.17	74.10
			200	8	2	0.27	76.50
			300	5	3	0.25	77.80
	10-2	2	300	3	5	0.25	82.30
			500	2	7	0.23	84.40
	10-3	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
11	11-1	5	50	7	2	0.23	72.60
			100	5	5	0.42	75.30
	11-2	4	1000	4	10	0.67	89.00
			1500	3	14	0.70	89.90
	11-3	2	300	7	5	0.58	82.30
			500	5	7	0.58	84.40
12	12-1	1	100	8	1	0.13	74.10
			200	7	2	0.23	76.50
			300	6	3	0.30	77.80
	12-2	3	200	8	4	0.53	79.70
			400	6	6	0.60	81.40
	12-3	2	300	7	5	0.58	82.30
			500	5	7	0.58	84.40
13	13-1	1	100	9	1	0.15	74.10
			200	7	2	0.23	76.50
			300	4	3	0.20	77.80
	13-2	5	50	9	2	0.30	72.60
			100	4	5	0.33	75.30
	13-3	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
14	14-1	4	1000	6	10	1.00	89.00
			1500	4	14	0.93	89.90
	14-2	3	200	4	4	0.27	79.70
			400	3	6	0.30	81.40
	14-3	1	100	10	1	0.17	74.10
			200	8	2	0.27	76.50
			300	5	3	0.25	77.80
15	15-1	2	300	3	5	0.25	82.30
			500	2	7	0.23	84.40
	15-2	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
	15-3	5	50	7	2	0.23	72.60
			100	4	5	0.33	75.30
16	16-1	5	50	5	2	0.17	72.60
			100	3	5	0.25	75.30
	16-2	3	200	7	4	0.47	79.70
			400	5	6	0.50	81.40
	16-3	2	300	8	5	0.67	82.30
			500	6	7	0.70	84.40
17	17-1	1	100	8	1	0.13	74.10
			200	6	2	0.20	76.50
			300	4	3	0.20	77.80
	17-2	5	50	7	2	0.23	72.60
			100	4	5	0.33	75.30
	17-3	3	200	6	4	0.40	79.70
			400	4	6	0.40	81.40
18	18-1	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
	18-2	1	100	11	1	0.18	74.10
			200	8	2	0.27	76.50
			300	6	3	0.30	77.80
	18-3	5	50	5	2	0.17	72.60
			100	3	5	0.25	75.30
19	19-1	2	300	3	5	0.25	82.30
			500	2	7	0.23	84.40
	19-2	3	200	8	4	0.53	79.70
			400	5	6	0.50	81.40
	19-3	4	1000	2	10	0.33	89.00
			1500	1	14	0.23	89.90
20	20-1	2	300	6	5	0.50	82.30
			500	4	7	0.47	84.40
	20-2	5	50	6	2	0.20	72.60
			100	4	5	0.33	75.30
	20-3	1	100	8	1	0.13	74.10
			200	7	2	0.23	76.50
			300	6	3	0.30	77.80

In the solution, first take the maximum makespan, total processing energy consumption, and equivalent sound Class A for an individual target and optimize them to obtain T_min = 64, T_max = 110; E_min = 21.73, E_max = 24.81; and N_min = 81.57, N_max = 83.14. Thus, the fitness function of the algorithm is as follows

\begin{array}{l} F (x) = w_{1} \cdot \frac{T (x) - 64}{46} + w_{2} \cdot \frac{E (x) - 21.73}{3.08} \\ + w_{3} \cdot \frac{N (x) - 81.57}{1.57} \end{array}

(20)

During the algorithm operation, set the relevant parameters to the following: the simplex lattice point design order d = 5, the number of population individuals NIND = 500, the evolution algebra order MAXGEN = 200, the quality protection ration G = 10%, the crossover probability XOVR = 0.9, and the mutation probability MUTR = 0.8. After operating the algorithm through many iterations, the problem solution set is shown in Table 6. Figure 12 shows the space distribution of the solution set, and Figure 13 shows the Gantt chart of scheduling scheme 15.

Table 6.

Scheduling schemes of instance 3.

No.	Weight			T (min)	E (kW h)	N (dB)
No.	T	E	N	T (min)	E (kW h)	N (dB)
1	0	0	1	110	22.19	81.57
2	0	0.2	0.8	108	22.17	81.64
3	0	0.4	0.6	106	22.14	81.70
4	0	0.6	0.4	101	22.03	81.72
5	0	0.8	0.2	100	21.98	81.74
6	0	1	0	105	21.73	81.80
7	0.2	0	0.8	93	22.51	81.67
8	0.2	0.2	0.6	90	22.25	81.75
9	0.2	0.4	0.4	90	22.04	81.85
10	0.2	0.6	0.2	87	22.12	81.93
11	0.2	0.8	0	92	21.82	81.93
12	0.4	0	0.6	84	22.58	81.77
13	0.4	0.2	0.4	83	22.47	81.86
14	0.4	0.4	0.2	76	22.37	82.13
15	0.4	0.6	0	80	22.24	82.14
16	0.6	0	0.4	68	23.14	82.42
17	0.6	0.2	0.2	72	23.05	82.12
18	0.6	0.4	0	69	22.88	82.76
19	0.8	0	0.2	65	23.33	82.71
20	0.8	0.2	0	66	22.96	82.60
21	1	0	0	64	23.68	82.79

Figure 12.

Scatter plot of scheduling schemes of instance 3.

Figure 13.

The Gantt chart of the 15th scheduling scheme of instance 3.

Performance comparison

In this section, three indexes are used to test the effectiveness of the MOGA. Three indexes are used in this article, which are described as follows:

1. Generational distance (GD) indicates how far away the Pareto front (PF) found is from the PF*.³³ This metric is formulated as follows

G D = \frac{\sqrt{\sum_{i = 1}^{n} D_{i}^{2}}}{n}

(21)

where n is the number of PF points found so far, and $D_{i}$ is the Euclidean distance between the ith member of the PF obtained and the nearest member of the optimal PF (PF*). A low value of GD is desirable, which denotes a good convergence to PF*.

2. Inverse generation convergence (IGD) is the inverse convergence method of the GD method. IGD calculates the mean of the minimum distance between the Pareto surface with points spread uniformly and the non-dominated solution sets.³⁴ The formulation of IGD is as follows

I G D = \frac{1}{N_{t u r e}} \sqrt{\sum_{i = 1}^{N_{t u r e}} d_{i}^{2}}

(22)

where $d_{i}$ is the minimum distance between the vector in the real PF and the vector in the target space. The smaller the IGD, the better the convergence. Moreover, IGD is also used to test uniformity and universality.

3. Spread (Δ) is applied to evaluate the distribution of the PF solution set and can be defined as follows³³

Δ = \frac{d_{f} + d_{l} + \sum_{i = 1}^{n - 1} | d_{i} - \bar{d} |}{d_{f} + d_{l} + (n - 1) \times \bar{d}}

(23)

where $d_{i}$ is the Euclidean distance between all two consecutive solutions in the PF solution set; $\bar{d}$ is the mean of $d_{i}$ ; $d_{f}$ and $d_{l}$ are the Euclidean distances between the boundary points of the PF and the best boundary points, respectively; and n is the number of the PF. The distribution factor is zero for a uniformly distributed solution. Therefore, the smaller the distribution factor, the better the distribution.

To test the efficiency of the proposed algorithm, it is compared with a well-known multi-objective evolutionary algorithm (MOEA) such as non-dominated sorting genetic algorithm II (NSGA-II) for the aforementioned cases. Tables 7 –9 show the mean and standard deviation metrics for these algorithms more than 30 independent runs. Tables 7 –9 reveal that the MOGA outperforms NSGA-II with regard to all metrics. Therefore, the MOGA is very suitable for solving this type of scheduling problem.

Table 7.

GD indicator.

	MOGA, mean (SD)	NSGA-II, mean (SD)
Case 1	0.0049 (0.0022)	0.0115 (0.0110)
Case 2	0.0026 (0.0011)	0.0032 (0.0012)
Case 3	0.0027 (0.0010)	0.0038 (0.0012)

MOGA: multi-objective genetic algorithm; NSGA-II: non-dominated sorting genetic algorithm II.

Table 8.

IGD indicator.

	MOGA, mean (SD)	NSGA-II, mean (SD)
Case 1	0.0215 (0.0068)	0.0283 (0.0094)
Case 2	0.0116 (0.0053)	0.0193 (0.0045)
Case 3	0.0134 (0.0028)	0.0139 (0.0024)

MOGA: multi-objective genetic algorithm; NSGA-II: non-dominated sorting genetic algorithm II.

Table 9.

Spread indicator.

	MOGA, mean (SD)	NSGA-II, mean (SD)
Case 1	1.1854 (0.1393)	1.3276 (0.3722)
Case 2	0.7695 (0.1920)	0.7075 (0.2564)
Case 3	0.7496 (0.2741)	0.9286 (0.2997)

MOGA: multi-objective genetic algorithm; NSGA-II: non-dominated sorting genetic algorithm II.

Parameters and operator analysis

In the MOGA, the algorithm performance is sensitive to the value of the parameters such as the crossover and mutation probability. However, the two parameters are not constant. In general, the crossover rate is set to the larger value, within a range of 0.7–0.9, while the mutation rate is usually set to the smaller value between 0.4 and 0.8. To test how the parameter settings affect the algorithm performance, we set different parameter values of crossover and mutation probability while the other parameter settings are kept constant, where crossover probability XOVR = {0.7, 0.8, 0.9} and mutation probability MUTR = {0.4, 0.6, 0.8}. Figure 14 shows the changes in the objective (i.e. F(x)) with different crossover and mutation probabilities for case 2. The figure clearly shows that the gap between the best and the worst value is not significant. Therefore, although different parameter settings affect the behavior of the algorithm in this case, the effect is not significant. In addition, XOVR (single-point crossover rate) or MUTR (the proposed swap mutation rate) with larger values will positively affect the algorithm performance.

Figure 14.

Parameter analysis for case 2.

Analysis of variance (ANOVA) can be used to calibrate the parameters. To test the efficiency of the proposed algorithm, it is used to find out the factors which have a significant impact on the algorithm through the data analysis. When the p-value of ANOVA is less than 0.05, the effect is significant. Table 10 show the F(x) and p metrics for the algorithm more than 30 independent runs. The results showed that MUTR and XOVR had no significant effect on the objective function. This is consistent with the above analysis.

Table 10.

MOGA parameters analysis of variances for case 2.

Parameters		XOVR
		0.7		0.8		0.9
		F(x)	p	F(x)	p	F(x)	p
MUTR	0.4	2.421	0.133	2.391	0.089	2.395	0.743
	0.6	2.437	0.956	2.416	0.362	2.441	0.067
	0.8	2.373	0.241	2.404	0.542	2.362	0.592

In addition, crossover has an important role in solving the scheduling problem. Different crossover operators are generally accepted to show different performance. To test the performance of the proposed algorithm, an algorithm with different crossover operators is measured. In this experiment, the MOGA is compared with an algorithm with partial mapping crossover (PMX). Each experiment conducted 10 independent runs for each case, and a boxplot is used to analyze the problem objective (i.e. F(x)).

Figure 15 shows that the MOGA with single-point crossover is more stable than that with PMX. Figure 16 shows that the average result obtained by the MOGA with one-point crossover is smaller than that of the result with PMX. Therefore, with increasing problem scale, one-point crossover is not sensitive to problem scale, but problem scale affects PMX.

Figure 15.

Boxplot for different crossovers on MOGA for case 1.

Figure 16.

Boxplot for different crossovers on MOGA for case 2.

Result analysis and discussion

An energy-efficient JSP issue comprises n jobs (each job contains n_i operations, where n_i is the total number of operations of job i) and m machines (each machine contains r spindle speeds for selection). The scale of the solution space is $Π_{i = 1}^{n} Π_{g = 1}^{n_{i}} r_{ig} \cdot Π_{k = 1}^{m} (N_{k}!)$ , where r_ij is the number of alternative spindle speeds of operation o_ig (the gth operation of job i) and N_k is the number of operations on machine k. The solution space is very large, as shown above. Moreover, the JSP is a multi-objective optimization problem, and the frontier problem Pareto cannot be solved precisely.

In this article, a MOGA based on the simplex lattice point design is used to solve the proposed energy-efficient JSP model. The aim of the algorithm is to find a group uniform distribution scheduling scheme set. The results of the above three instances with different scales demonstrate the effectiveness of the proposed model and method for the low-carbon JSP. The energy-efficient scheduling method described in this article could provide more selective scheduling schemes for decision-makers. In addition, the scheduling scheme can be reasonably adjusted according to actual production requirements and changes in production targets to better guide production.

Conclusion and future studies

For the urgent demand of sustainable development in the modern manufacturing industry, this article proposed a new energy-efficient scheduling mathematical model considering productivity, energy efficiency, and noise reduction with variable spindle speed for the job shop environment. This model considers the machining spindle speed that impacts the production time, power, and noise to be flexible and an independent decision-making variable. This model presents the evaluation methods of productivity, energy consumption, and noise. To effectively solve this mixed integer programming model, an effective MOGA based on simplex lattice design is proposed. The corresponding encoding/decoding method, fitness function, and crossover/mutation operators are designed according to the features of this problem. To evaluate the performance of this method, three instances with different scales have been designed. The results demonstrate the effectiveness of the proposed model and method for the low-carbon JSP.

Based on the above study, the authors believe that further study of energy-efficient scheduling problems can be performed in the following three directions: (1) energy-efficient scheduling involves many indicators. Other low-carbon indicators could be considered in future studies, such as peak power and exhaust emissions. (2) For various manufacturing plants, more types of manufacturing plants (such as open workshops) can be considered in the future. (3) Adding dynamic factors to energy-efficient scheduling will bring the model closer to reality because the actual plant accompanies factors during processing such as job delay, precedence of urgent jobs, and machine breakdowns.

Footnotes

Academic Editor: Murat Uzam

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 work was supported by the National Natural Science Foundation of China (NSFC) under grant no. 51375004, National Key Technology Support Program under grant no. 2015BAF01B04, Youth Science & Technology Chenguang Program of Wuhan under grant no. 2015070404010187, and the Fundamental Research Funds for the Central Universities, HUST: grant no. 2015TS061, the Humanities and Social Sciences Foundation of Ministry of Education of China (grant no. 15YJC630162).

References

Energy Information Administration (EIA). International energy outlook 2013 (DOE/EIA-0484). Washington, DC: U.S. Energy Information Administration, 2013.

Dai

Tang

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

Mouzon

Yildirim

Twomey

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

Herrmann

Methodology for the design of sustainable production systems. Int J Sustain Manuf 2009; 1: 376–395.

Tridech

Cheng

Low carbon manufacturing: characterisation, theoretical models and implementation. Int J Manuf Res 2011; 6: 110–121.

Gutowski

Murphy

Allen

. Environmentally benign manufacturing: observations from Japan, Europe and the United States. J Clean Prod 2005; 13: 1–17.

Gutowski

Branham

Dahmus

. Thermodynamic analysis of resources used in manufacturing processes. Environ Sci Technol 2009; 43: 1584–1590.

Liu

Dong

Lohse

. An investigation into minimising total energy consumption and total weighted tardiness in job shops. J Clean Prod 2014; 65: 87–96.

Pach

Berger

Sallez

. Reactive and energy-aware scheduling of flexible manufacturing systems using potential fields. Comput Ind 2014; 65: 434–448.

10.

Park

Kwon

Kim

. Energy consumption reduction technology in manufacturing—a selective review of policies, standards, and research. Int J Precis Eng Man 2009; 10: 151–173.

11.

Fang

Uhan

Zhao

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

12.

Wang

. A systematic approach of process planning and scheduling optimization for sustainable machining. J Clean Prod 2015; 87: 914–929.

13.

Mouzon

Yildirim

MB.

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

14.

Zhang

Jiang

PY.

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: 328–342.

15.

Rager

Gahm

Denz

Energy-oriented scheduling based on evolutionary algorithms. Comput Oper Res 2015; 54: 218–231.

16.

Fang

Uhan

Zhao

. A new shop scheduling approach in support of sustainable manufacturing. Berlin, Heidelberg: Springer, 2011, pp.305–310.

17.

Fang

Uhan

Zhao

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

18.

Bruzzone

AAG

Anghinolfi

Paolucci

. Energy-aware scheduling for improving manufacturing process sustainability: a mathematical model for flexible flow shops. CIRP Ann: Manuf Techn 2012; 61: 459–462.

19.

Dai

Tang

Giret

. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robot Comput Integrated Manuf 2013; 29: 418–429.

20.

Luo

Huang

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

21.

Keller

Schönborn

Reinhart

Energy-orientated machine scheduling for hybrid flow shops. Proced CIRP 2015; 29: 156–161.

22.

Wang

Rao

Zhang

. Estimation of distribution algorithm for energy-efficient scheduling in turning processes. Sustainability 2016; 8: 762.

23.

Gao

. An effective multi-objective discrete virus optimization algorithm for flexible job-shop scheduling problem with controllable processing times. Comput Ind Eng 2017; 156–174.

24.

Yin

. Energy-efficient scheduling problem using an effective hybrid multi-objective evolutionary algorithm. Sustainability 2016; 8: 1268.

25.

Low

Hsu

. Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. Appl Math Model 2010; 34: 334–342.

26.

Pinedo

ML.

Scheduling. Theory, algorithms, and systems. With CD-ROM. 3rd ed. New York: Prentice Hall, 2008, p.15.

27.

Yin

Gao

. A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem. Sustain Comput: Informat Syst. Epub ahead of print 24 November 2016. DOI: 10.1016/j.suscom.2016.11.002.

28.

Tandon

Noise-reducing designs of machines and structures. Sadhana: Acad Proc Eng Sci 2000; 25: 331–339.

29.

Yang

Zeng

. Noise exposure assessment with task-based measurement in complex noise environment. Chinese Med J 2011; 124: 1346–1351.

30.

Olayinka

Abdullahi

SA.

An overview of industrial employees’ exposure to noise in sundry processing and manufacturing industries in Ilorin metropolis, Nigeria. Ind Health 2009; 47: 123–133.

31.

Garey

Johnson

Sethi

The complexity of flowshop and jobshop scheduling. Math Oper Res 1976; 1: 117–129.

32.

Azevedo

Cunha

Mahajan

. Application of simplex lattice design for development of moisture absorber for oyster mushrooms. In: Saravacos

Taoukis

Krokida

. (eds) Procedia food science (11th international congress on engineering and food). Amsterdam: Elsevier Science B.V., 2011, pp.184–189.

33.

Deb

Pratap

Agarwal

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

34.

Zitzler

Thiele

Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE T Evolut Comput 1999; 3: 257–271.

Energy-efficient job shop scheduling problem with variable spindle speed using a novel multi-objective algorithm

Abstract

Keywords

Introduction

Problem formulation

Evaluation models of productivity, energy consumption, and noise emission

Evaluation model of energy consumption

Evaluation model of noise emission

Mixed integer programming model of low-carbon JSP

MOGA based on a simplex lattice design for low-carbon JSP

Simplex lattice design

Encoding and decoding methods

Initial population and fitness evaluation

Genetic operations

Selection operation

Crossover operation

Mutation operation

Elite strategy

Framework of the proposed MOGA for the low-carbon JSP

Experimental studies and discussion

Experiment 1 (4 × 5)

Experiment 2 (10 × 6)

Experiment 3 (20 × 5)

Performance comparison

Parameters and operator analysis

Result analysis and discussion

Conclusion and future studies

Footnotes

Declaration of conflicting interests

Funding

References