A discrete animal migration algorithm for dual-resource constrained energy-saving flexible job shop scheduling problem

Abstract

This paper presents a discrete animal migration optimization (DAMO) to solve the dual-resource constrained energy-saving flexible job shop scheduling problem (DRCESFJSP), with the aim of minimizing the total energy consumption in the workshop. A job-resource-based two-vector encoding method is designed to represent the scheduling solution, and an energy-saving decoding approach is given based on the left-shift rule. To ensure the quality and diversity of initial scheduling solutions, a heuristic approach is employed for the resource assignment, and some dispatching rules are applied to acquire the operation permutation. In the proposed DAMO, based on the characteristics of the DRCESFJSP problem, the search operators of the basic AMO are discretized to adapt to the problem under study. An animal migration operator is presented based on six problem-based neighborhood structures, which dynamically changes the search scale of each animal according to its solution quality. An individual updating operator based on crossover operation is designed to obtain new individuals through the crossover operation between the current individual and the best individual or a random individual. To evaluate the performance of the proposed algorithm, the Taguchi design of experiment method is first applied to obtain the best combination of parameters. Numerical experiments are carried out based on 32 instances in the existing literature. Computational data and statistical comparisons indicate that both the left-shift decoding rule and population initialization strategy are effective in enhancing the quality of the scheduling solutions. It also demonstrate that the proposed DAMO has advantages against other compared algorithms in terms of the solving accuracy for solving the DRCESFJSP.

Keywords

Dual-resource constraint energy-saving scheduling flexible job shop discrete animal migration optimization

1 Introduction

Flexible Job Shop Scheduling Problem (FJSP) has strong theoretical significance and application background, which has been widely paid attention by scholars [1]. Most of the previous work on FJSP only consider the scheduling problem with limited machine resource. However, in the actual production, there are more than one type of resources that affect the workshop production simultaneously, such as labor, gas, fund, fixture, transporter, and so on. Considering the increasing labor cost, it is very important to make a proper use of the limited workers in the workshop. In recent years, the FJSP with worker and machine resources, namely dual-resource constrained flexible job shop scheduling problem (DRCFJSP), has aroused the interest of scholars at home and abroad. Compared with the traditional FJSP, the DRCFJSP is a more complex NP-hard problem. However, to the best of our knowledge, small number of literature addressed the DRC scheduling problem in FJSP environment [2 –6]. There still exists much work to be done to make the problem closer to the practical production. With regard to most of the existing literature on the DRCFJSP, the economic indicators related to time, quality or cost are considered, and the environmental indicators are always ignored, such as CO₂ emission, carbon footprint, noise pollution, and energy consumption, and so on.

With the increasing of environmental deterioration and energy crisis, manufacturing industries are encouraged to draw up some measurements to reduce the energy consumption from different directions, such as machine level, product level and management level. Limited by some financial constraints, small-scale enterprises may not purchase energy-saving machines and design energy-efficient products. Therefore, the existing literature have mainly focused on the management level [7]. In recent years, the energy-saving FJSP has gradually become a research hotspot [8 –22]. A summary of research on energy-saving FJSP is presented in Table 1. Observed from Table 1, the current literature have seldom considered the dual-resource constrained energy-saving flexible job shop scheduling problem (DRCESFJSP), most of which only focus on the machine constraints, and ignore the influence of worker allocation on the reduction of the energy consumption in the workshop. However, energy-saving scheduling and dual-resource constraints often exist simultaneously in the actual flexible job shop. The consideration on energy-saving FJSP with dual-resource constraints can result in good schedule close to the practical production and should be an important topic in the manufacturing field. In addition, as shown in Table 1, a number of meta-heuristic algorithms have been applied to address the energy-saving FJSP because of the NP-hard nature. However, as the famous No Free Lunch (NFL) theorem [23] stated, no meta-heuristic is best suited for all optimization problems. That is to say, a particular meta-heuristic may obtain very promising solutions on a set of problems, but it may show poor performance on a different set of problems [24]. This encourages researchers to modify current algorithms or present new meta-heuristics for solving various optimization problems. Therefore, it is worthwhile to devise a fresh meta-heuristic algorithm for the energy-saving FJSP, especially for the considered DRCESFJSP.

Table 1
Summary of research on energy-saving FJSP

Literature Resources Objectives Algorithms

Lei et al. [8] Machine Workload balance and total energy consumption SFLA

Jiang and Deng [9] Machine Total energy consumption and earliness/tardiness cost DCSO

Wu et al. [10] Machine Makespan and total energy consumption Hybrid PIO and SA

Wu and Sun [11] Machine Makespan, energy consumption and numbers of turning-on/off machines MOGA

Jiang et al. [12] Machine Total energy consumption IABO

Ren et al. [13] Machine Production efficiency and energy consumption Hybird PSO and GA

Yin et al. [14] Machine Productivity, energy efficiency and noise reduction MOGA

Zhang et al. [15] Machine Total energy consumption and makespan NSGA-II

Li and Lei [16] Machine Makespan, total tardiness and total energy consumption FICA

Dai et al. [17] Machine Total energy consumption and makespan GA

Zhang et al. [18] Machine Total energy consumption and makespan NHM

Lu et al. [19] Machine Energy consumption cost and completion-time cost DWWO

Li et al. [20] Machine and worker Total energy consumption MMBO

Wu and Li [21] Machine and worker Makespan, energy consumption and ergonomic risk MOEA/D

Li et al. [22] Machine and worker Total energy consumption MJAYA

Literature	Resources	Objectives	Algorithms
Lei et al. [8]	Machine	Workload balance and total energy consumption	SFLA
Jiang and Deng [9]	Machine	Total energy consumption and earliness/tardiness cost	DCSO
Wu et al. [10]	Machine	Makespan and total energy consumption	Hybrid PIO and SA
Wu and Sun [11]	Machine	Makespan, energy consumption and numbers of turning-on/off machines	MOGA
Jiang et al. [12]	Machine	Total energy consumption	IABO
Ren et al. [13]	Machine	Production efficiency and energy consumption	Hybird PSO and GA
Yin et al. [14]	Machine	Productivity, energy efficiency and noise reduction	MOGA
Zhang et al. [15]	Machine	Total energy consumption and makespan	NSGA-II
Li and Lei [16]	Machine	Makespan, total tardiness and total energy consumption	FICA
Dai et al. [17]	Machine	Total energy consumption and makespan	GA
Zhang et al. [18]	Machine	Total energy consumption and makespan	NHM
Lu et al. [19]	Machine	Energy consumption cost and completion-time cost	DWWO
Li et al. [20]	Machine and worker	Total energy consumption	MMBO
Wu and Li [21]	Machine and worker	Makespan, energy consumption and ergonomic risk	MOEA/D
Li et al. [22]	Machine and worker	Total energy consumption	MJAYA

With the continuous development of natural science and computer science, a variety of meta-heuristic algorithms have been developed recently to solve various complicated optimization problems [25 –31]. Among these existing algorithms, Animal Migration Optimization (AMO) algorithm, as a novel intelligent algorithm, has attracted great research interests, which originates from the natural migration behavior of animals [32]. AMO has many advantages like few adjustable parameters, easy implementation, as well as strong global search ability. Due to its novelty and superiority, AMO has been successfully used to deal with various optimization problems [33 –36]. However, there are limited literature adopting AMO to solve energy-efficient flexible job shop scheduling problems, especially with dual-resource constraints. Furthermore, AMO was proposed for continuous optimization problems, which means that it can not be directly used for the discrete production scheduling problems. Therefore, a series of improvement strategies should be specially designed according to the characteristics of the considered problem. In this paper, a discrete animal migration optimization (DAMO) algorithm is proposed for solving the DRCESFJSP considering the total energy consumption to be minimized. In the DAMO, some improvement strategies are employed as follows: (1) A job-resource-based two-vector encoding method is adopted to represent the scheduling solutions, and an energy-saving decoding approach is developed based on the left-shifting rule by considering the dual resource constrains. (2) A population initialization approach is proposed to ensure initial scheduling solutions with a certain quality and diversity. (3) To make the AMO algorithm be suitable for the discrete scheduling problem, a discrete animal migration operator is designed based on six problem-specific neighborhood structures, which can dynamically adjust the search scale of each animal according to its solution quality, a discrete individual updating operator is designed to obtain new individuals through the crossover operation.

The remainder of this paper is organized as follows. In Section 2, the DRCESFJSP is described and modeled. In Section 3, the DAMO is developed, including the encoding/decoding approach, population initialization and discrete search operators. A comparison of experimental results is given in Section 4. Section 5 shows the conclusions.

2 Problem description and formulation

Assume that the processing task with n jobs needs to be completed by m machines M = {M₁, M₂, ⋯ , M_m} and w workers W = {W₁, W₂, ⋯ , W_w} in a workshop. For any job i, it contains J_i operations OP_i = {O_i1, O_i2, ⋯ , O_{iJ
_i}}. Each operation O_ij has an eligible machine set M (O_ij), and each machine k has an eligible worker set W (k). The processing time depends on the machine assigned to each operation and the workers selected for the processing machine. For the considered problem in this paper, there are mainly two sub-problems, namely resource allocation and operation permutation. The optimization objective is to minimize the total energy consumption of the workshop through effective resource allocation and operation sequencing. For this system, there are several assumptions to be considered:

Each worker and machine is available and each job is ready at time zero.

Only one job can be processed on a machine at a time.

One worker operates only one machine at a time.

The job is not allowed to be preempted during processing.

The assigned machines and workers can not be adjusted when any job is being processed.

Different jobs are independent of each other, and there is a sequence of processing between different operations in a job.

Once the machine is started, it is not allowed to be stopped until all jobs on it are completed.

The setup times of machines, the movement times of workers and the transportation times of jobs between machines are not taken into account.

Some necessary symbols and variables of the mathematical model are given as below.

TEC: the total energy consumption;

p_ijkl: the processing time of O_ij on machinek handled by worker l;

PE_ijkl: the processing energy coefficient of O_ij on machine k handled by worker l;

SE_k: the idle energy coefficient of machine k;

CE: the common energy coefficient;

C_k: the completion time of machine k;

S_k: the start time of machine k;

WL_k: the total workload of machine k;

C_max: the makespan of all jobs;

ST_ij: the start time of O_ij;

CT_ij: the completion time of O_ij;

Γ: a big position constant;

T_kl: the available time of worker l operating machine k;

x_ijkl: a 0-1 variable, if O_ij is processed on machine k handled by worker l, x_ijkl = 1, otherwise, x_ijkl = 0;

y_iji′j′k: a 0-1 variable, if O_ij is processed on machine k adjacently prior to O_i′j′, y_iji′j′k = 1, otherwise, y_iji′j′k = 0;

ξ_kk′l: a 0-1 variable, if machine k is handled by worker l adjacently prior to machine k′, ξ_kk′l = 1, otherwise ξ_kk′l = 0.

$\begin{matrix} min TEC = \sum_{i \in I} \sum_{j \in {OP}_{i}} \sum_{k \in M (O_{ij})} \sum_{l \in W (k)} {PE}_{ijkl} x_{ijkl} p_{ijkl} \\ + \sum_{k \in M} {SE}_{k} (C_{k} - S_{k} - {WL}_{k}) + CE \times C_{max} \end{matrix}$ (1)

$\begin{matrix} s . t . {CT}_{ij} - {ST}_{ij} = \sum_{k \in M (O_{ij})} \sum_{l \in W (k)} x_{ijkl} p_{ijkl}, \\ \forall i \in I; j \in {OP}_{i} \end{matrix}$ (2)

${ST}_{i (j + 1)} - {CT}_{ij} ⩾ 0, \forall i \in I; j \in {OP}_{i}$ (3)

$\begin{matrix} {ST}_{i^{'} j^{'}} + Γ (1 - y_{{iji}^{'} j^{'} k}) ⩾ {CT}_{ij}, \forall i, i^{'} \in I; \\ j \in {OP}_{i}; j^{'} \in {OP}_{i^{'}}; k \in (M (O_{ij}) \cap M (O_{i^{'} j^{'}})) \end{matrix}$ (4)

$\begin{matrix} {ST}_{ij} + Γ y_{{iji}^{'} j^{'} k} ⩾ {CT}_{i^{'} j^{'}}, \forall i, i^{'} \in I; j \in {OP}_{i}; \\ j^{'} \in {OP}_{i^{'}}; k \in (M (O_{ij}) \cap M (O_{i^{'} j^{'}})) \end{matrix}$ (5)

$\begin{matrix} T_{k^{'} l} + Γ (1 - ξ_{{kk}^{'} l}) ⩾ T_{kl}, \forall k, k^{'} \in M; \\ l \in (W (k) \cap W (k^{'})) \end{matrix}$ (6)

$T_{kl} + Γ ξ_{{kk}^{'} l} ⩾ T_{k^{'} l}, \forall k, k^{'} \in M; l \in (W (k) \cap W (k^{'}))$ (7)

$\begin{matrix} {ST}_{ij} ⩾ T_{kl} + Γ (1 - x_{ijkl}), \forall i \in I; j \in {OP}_{i}; \\ k \in M (O_{ij}); l \in W (k) \end{matrix}$ (8)

$T_{kl} ⩾ 0, \forall k \in M; l \in W$ (9)

$\sum_{k \in M (O_{ij})} \sum_{l \in W (k)} x_{ijkl} = 1, \forall i \in I; j \in {OP}_{i}$ (10)

${WL}_{k} = \sum_{i \in I} \sum_{j \in {OP}_{i}} \sum_{l \in W (O_{ij})} p_{ijkl} x_{ijkl}, \forall k \in M$ (11)

$\begin{matrix} C_{k} = max {{CT}_{ij} x_{ijkl}}, \forall i \in I; j \in {OP}_{i}; \\ k \in M (O_{ij}); l \in W (k) \end{matrix}$ (12)

$\begin{matrix} S_{k} = min {{ST}_{ij} x_{ijkl}}, \forall i \in I; j \in {OP}_{i}; \\ k \in M (O_{ij}); l \in W (k) \end{matrix}$ (13)

$\begin{matrix} x_{ijkl} \in {0, 1}, \forall i \in I; j \in {OP}_{i}; \\ k \in M (O_{ij}); l \in W (k) \end{matrix}$ (14)

$\begin{matrix} y_{{iji}^{'} j^{'} k} \in {0, 1}, \forall i, i^{'} \in I; j \in {OP}_{i}; j^{'} \in {OP}_{i^{'}}; \\ k \in (M (O_{ij}) \cap M (O_{i^{'} j^{'}})) \end{matrix}$ (15)

$ξ_{{kk}^{'} l} \in {0, 1}, \forall k, k^{'} \in M; l \in (W (k) \cap W (k^{'}))$ (16)

In Equation (1), the first item is the processing energy consumption which is consumed for processing operations, the second item is the idle energy consumption which occurs when the machines are waiting for jobs, and the third item is the common energy consumption which comes from the auxiliary equipment, such as lights and air conditioners. Constraint (2) means that the processing of an operation can not be disturbed. Constraint (3) ensures the precedence relationships between operations of the same job. Constraints (4) and (5) define that each machine can only process one operation at a time. Constraints (6) and (7) represent that each worker cannot handle more than one machine simultaneously. Constraint (8) indicates that each process can only start after the machine and worker are ready. Constraint (9) means that the ready time of machine and the worker can not be smaller than 0. Constraint (10) indicates that the worker and the machine for processing an operation can not be adjusted once they are determined. Constraint (11) represents the machine workload, which is equal to the total processing times of all operations on the machine. Constraints (12) and (13) define the completion time and the start time of each machine. Constraints (14)∼(16) are 0-1 variables.

3 Discrete animal migration optimization

3.1 Basic animal migration optimization

Animal migration optimization (AMO) algorithm is inspired by the natural migration behavior of animals [32]. The process of the algorithm can be divided into animal migration and individual updating. In the migration process, the algorithm updates each individual according to the positions of its neighbors, and simulates the group of animals moving from the current habitat to the new one. This process can be represents by Equation (17).

$X_{i}^{t + 1} = X_{i}^{t} + δ (X_{neighborhood}^{t} - X_{i}^{t})$ (17)

where t represents the iteration number; X_i represents the position of individual i; δ is a random number following the Gaussian distribution; X_neighborhood is the position of the neighbor of X_i. In the individual updating process, individual i will be replaced by the new individual according to probability Pa_i, ${Pa}_{i} = \frac{{rank}_{i}}{PS}$ , PS is the size of the population, rank_i is the sequence number of individual i after sorting all the individuals according to the fitness values in a descending order. For the best individual, Pa is 1, and Pa of the worst individual is 1/PS. During the updating process, a random number is generated for each individual following a uniform distribution in [0,1]. If rand > Pa_i, the updating process will be conducted by Equation (18).

$\begin{matrix} X_{i}^{t + 1} = X_{r_{1}}^{t} + rand \times (X_{best}^{t} - X_{i}^{t}) \\ + rand \times (X_{r_{2}}^{t} - X_{i}^{t}) \end{matrix}$ (18) where X_{r
₁}, X_{r
₂} are two different individuals randomly selected from the current population. X_best is the current best individual. In both the two processes, $X_{i}^{t + 1}$ will be compared with $X_{i}^{t}$ . If $X_{i}^{t + 1}$ is better than $X_{i}^{t}$ , $X_{i}^{t + 1}$ will be accepted as the current solution, otherwise, $X_{i}^{t}$ remains unchanged.

3.2 Encoding approach

The energy-saving scheduling problem in this paper can be divided into resource allocation problem and process sequencing problem. Therefore, a two-vector encoding method based on jobs and resources is adopted, and the length of each vector is the total number of operations in the workshop. Suppose that a workshop (two workers and three machines) need to complete the processing tasks of three jobs, and each job contains three operations. The encoding scheme is shown in Fig. 1. The first vector represents the operation permutation scheme, and its element value is the number of each job. The same value represents the different operations of the same job, and the appearance order of the operations represents the serial numbers of them in the job. For example, the first ’1’ is the first operation of job 1, and the second ’3’ is the second operation of job 3. The second vector represents the resource allocation scheme, whose element value is the codes of worker and machine assigned for the corresponding operation. For example, the first ’(1,2)’ indicates that the operation O₁₁ is processed on machine 2 handled by worker 1.

Fig.1

Encoding scheme.

3.3 Energy-saving decoding approach

In order to reduce the energy consumption, we adopt an energy-saving decoding method based on the left-shift mechanism to compress the idle interval time between adjacent operations on the machine and shorten the maximum completion time of the jobs, so as to achieve the purpose of reducing the idle energy consumption and common energy consumption. The steps of the decoding approach is as follows:

Step 1 Traverse the operation permutation vector from left to right. If O_ij is not scheduled, obtain the worker W_l and the machine M_k assigned for the operation from the resource allocation vector.

Step 2 Find all the idle time intervals of machine M_k, and the q th idle interval can be represented by MIV_kq. ${mt}_{kq}^{S}$ and ${mt}_{kq}^{E}$ denote the start time and the end time of MIV_kq, respectively.

Step 3 Find all the idle time intervals of worker W_l, and the bth idle interval can be represented by WIV_lb. ${wt}_{lb}^{S}$ and ${wt}_{lb}^{E}$ denote the start time and the end time of WIV_lb, respectively.

Step 4 Calculate the earliest start time of O_ij, i.e., ${ST}_{ij} = max ({CT}_{i (j - 1)}, {mt}_{kq}^{S}, {wt}_{lb}^{S})$ . If ${ST}_{ij} + p_{ijkl} ⩽ min ({mt}_{kq}^{E}, {wt}_{lb}^{E})$ is met, O_ij can be inserted into the idle time interval on M_k. If all the idle time intervals on M_k cannot be inserted, O_ij should be moved to the end of M_k. The start time of O_ij can be measured by ST_ij = max(CT_i(j-1), MET_k, WET_l), where MET_k and WET_l are the end time of the last operation on M_k and W_l, respectively.

Step 5 Determine whether all operations are scheduled. If yes, the decoding procedure is terminated; otherwise, go to Step 1.

3.4 Population initialization

3.4.1 Initial resource allocation

For the initialization of the resource allocation, Li et al. [20] proposed a heuristic method for the resource allocation based on machine workload. That is to find the minimum element value from the constructed processing time matrix, and find the corresponding operation and resources to the element, and then add the element value to the corresponding machine to update the machine workload, and repeat the above procedure until all the operations are allocated. However, the processing energy consumption of machines is not considered. Therefore, a modified resource allocation method is proposed based on the processing energy consumption matrix in this paper. The steps are listed as follows:

Step 1 Construct a processing energy consumption matrix MT with the size of h × g, where h is equal to the total number of operations to be processed in the workshop $\sum_{i = 1}^{n} J_{i}$ , g is equal to the number of combinations of machines and workers in a workshop m × w. Take the workshop in Section 3.2 as an example, the row elements correspond to [O₁₁, O₁₂, O₁₃, O₂₁, O₂₂, O₂₃, O₃₁, O₃₂, O₃₃], and the column elements correspond to [M₁W₁, M₁W₂, M₂W₁, M₂W₂, M₃W₁, M₃W₂].

Step 2 Initialize the matrix MT, and set each element value as the processing energy consumption of each operation under different resource combination PE_ijklp_ijkl. If the operation cannot be processed by a resource combination, the corresponding element value is set to a large number R to ensure that the resource combination will not be selected.

Step 3 Find the minimum element value sl in the matrix. If there is more than one sl values, choose one of them at random. Record the corresponding operation and resource combination of the selected element in row h₁ and column g₁. And fill the assigned worker and machine into the corresponding position of the operation in the resource allocation vector of the current initial solution.

Step 4 Set all the elements in row h₁ to be R to avoid the operation in this row being repeatedly selected.

Step 5 Adds sl to the elements in all columns corresponding to the selected machine.

Step 6 Determine whether all operations have been assigned. If yes, the resource allocation is completed; otherwise, repeat Steps 3–5.

In addition to the above allocation method, the random generation method is also used to obtain the initial resource allocation scheme. For each operation, one machine is randomly chosen from the eligible machine set, and then one worker is randomly chosen from the eligible worker set of the machine. The two methods generate the initial resource allocation scheme according to a certain proportion. In this paper, 80% of the individuals use the modified resource allocation method and the remaining 20% use the random generation method.

3.4.2 Initial operation permutation

For each generated resource allocation scheme, three dispatching rules proposed by Pezzella et al. [37] are selected with the same probability to generate several operation permutation schemes. Each combination of the resource allocation scheme and the operation permutation scheme is evaluated, and the group with the minimum objective value is determined as an initial scheduling solution. Here, the three dispatching rules are adopted as below.

Most Work Remaining (MWR): Select a job with the most amount of remaining processing times.

Most Operation Remaining (MOR): Select a job with the most number of remaining operations.

Random Rule (RR): Generate the operation permutation in a random manner.

3.5 Discrete search operators

It can be seen from Equations (17) and (18) that the basic AMO algorithm is suitable for the continuous optimization problems, while for the discrete shop scheduling problem, a series of discretization methods are needed for designing the two search operators: animal migration operator and individual update operator.

3.5.1 Animal migration operator

As mentioned before, AMO algorithm updates the position of each individual according to the information of its neighbors, so as to realize the population migration operation. Therefore, according to the feature of the problem, six neighborhood structures are employed in this section. For each individual i, a neighborhood structure is randomly selected and performed δ_i times of neighboring operations to obtain a new solution. The value of δ_i is calculated by Equation (19). If the new solution is superior to the original one, the new solution is accepted, otherwise, the original solution keeps unchanged.

$δ_{i} = ⌊ δ_{max} - (δ_{max} - δ_{min}) \frac{{TEC}_{max} - {TEC}_{i}}{{TEC}_{max} - {TEC}_{min}} ⌋$ (19)

where TEC_i is the objective value of individual i; TEC_max, TEC_min are the objective values of the worst individual and the best individual in the current population, respectively; δ_max, δ_min are the maximum value and the minimum value of δ_i, which are equal to 5 and 1 in this paper. It can be seen from Equation (4) that better individuals perform neighborhood operations for fewer times to prevent individuals from being destroyed, while poorer individuals perform neighborhood operations for more times to search for better solutions.

(1) Neighborhood structure NH₁: Randomly select two different elements in the operation permutation vector, and then swap the positions of the selected elements.

(2) Neighborhood structure NH₂: Select an element at random in the resource allocation vector, choose a different machine from the eligible machine set of the corresponding operation of the element, and then select a different worker from the eligible worker set of the machine.

(3) Neighborhood structure NH₃: Select an element at random in the resource allocation vector, and select a different worker from the eligible worker set of the machine corresponding to the operation of the element.

(4) Neighborhood structure NH₄: Execute the two neighborhood structures NH₁ and NH₂ simultaneously.

(5) Neighborhood structure NH₅: Execute the two neighborhood structures NH₁ and NH₃ simultaneously.

(6) Neighborhood structure NH₆: Execute the three neighborhood structures NH₁, NH₂ and NH₃ simultaneously.

3.5.2 Individual updating operator

It can be observed from Equation (18) that the basic AMO algorithm updates the individuals according to the information of the current best individual and random individuals. Here, we propose a discrete individual updating method based on crossover operation, as shown in Equation (20).

$X_{i}^{t + 1} = c_{1} \otimes CR (X_{best}^{t}, X_{i}^{t}) \oplus c_{2} \otimes CR (X_{r}^{t}, X_{i}^{t})$ (20) where $X_{i}^{t + 1}$ contains two parts, i.e., $X_{i}^{t + 1} = F_{1} \oplus F_{2}$ . ‘⊕’ denotes that the better one between F₁ and F₂ will be selected. F₁ and F₂ can be further addressed as below.

$\begin{matrix} F_{1} = & c_{1} \otimes CR (X_{best}^{t}, X_{i}^{t}) \\ = & {\begin{matrix} CR (X_{best}^{t}, X_{i}^{t}), if rand < c_{1} \\ X_{i}^{t}, if rand ⩾ c_{1} \end{matrix} \end{matrix}$ (21)

$\begin{matrix} F_{2} & = c_{2} \otimes CR (X_{r}^{t}, X_{i}^{t}) \\ = {\begin{matrix} CR (X_{r}^{t}, X_{i}^{t}), if rand < c_{2} \\ X_{r}^{t}, if rand ⩾ c_{2} \end{matrix} \end{matrix}$ (22)

c₁, c₂ represent the crossover rate; ‘⊗’ Indicates that a crossover operation is performed after the condition to the left of the symbol is satisfied; CR represents the crossover operation. In this paper, the POX crossover is used for the operation permutation vector, by which jobs are randomly divided into two subsets, the positions of the jobs in subset 1 are maintained in the parent individuals, and then the sequence of operations belonging to jobs in subset 2 is exchanged between the parent individuals. The two-point crossover is employed for the resource allocation vector, by which two positions are randomly selected in the parent individuals, and then the elements between the selected positions are exchanged. The two crossover operations are illustrated by Fig. 2. It is worth noting that the two individuals obtained after the crossover operation need to be further compared, and the better one will be selected as the new individual.

Fig.2

Crossover operation.

3.6 Steps of the proposed algorithm

The steps of DAMO algorithm are as follows:

Step 1 Set the parameters of the algorithm, such as the population size PS, the maximum number of iterations iter_max, the crossover rate c₁ and c₂.

Step 2 Create the initial population according to the method in Section 3.4.

Step 3 Perform the discrete animal migration operator for each individual.

Step 4 Evaluate each individual and find the current best solution.

Step 5 Calculate the value of Pa_i for each individual. If rand > Pa_i, carry out individual updating operator according to Equation (20).

Step 6 Calculate the objective value of each individual and find the current best solution.

Step 7 Set iter ← iter + 1. If iter < iter_max is met, go to Step 3; otherwise, go to Step 8.

Step 8 Terminate the algorithm.

4 Simulation experiment

4.1 Test instance

In this section, 32 instances designed by Li et al. [22] are used for simulation experiments. Each instance contains m machines, w workers and n jobs, and the problem size is expressed as m × n × w, where the number of machines is 10,15,20,25, the number of workers is ⌊0.6m ⌋ + 1, and the number of jobs is 10,20,30,40,50,60,70,80. Other data follow a discrete uniform distribution, i.e., J_i∈[1,5, 1,5], nop∈[2,m] (nopdenotes the number of eligible machines of each operation), nwk∈[2,w] (nwk denotes the number of eligible workers of each machine), p_ijkl∈[10,20, 10,20], E_ijkl∈[10,15, 10,15], SE_k∈[6,10, 6,10], CE∈[12,18, 12,18]. The algorithm is programmed in Fortran language and run on the virtual machine (VMware Workstation platform) with 2 G memory under the WinXP operating system. All the compared algorithms are run for 10 times independently in each instance to obtain the computational results.

4.2 Parameter settings

The DAMO algorithm mainly contains four parameters, namely population size PS, maximum number of iterations iter_max, crossover rate c₁ and c₂. Here, Taguchi design of experiment method is adopted to set the algorithm parameters. First, an orthogonal table with four factors and four levels L₁₆ (4⁴) needs to be constructed, as shown in Table 2 and Table 3. For the instance RM13, the algorithm under different parameter combinations is run independently for 10 times, and the average value Avg in ten runs is used to evaluated the computational results. Following the data in Table 3, the response values of each parameter were calculated, as shown in Table 4, and then the influence curve of the algorithm parameters on the computational results is obtained, as shown in Fig. 3. Observed from Table 4, the Dleta value of iter_max is the largest, indicating that the maximum iteration number has the greatest impact on the algorithm performance, and the second significant parameter is PS. For the DAMO algorithm, the population size PS is 40, the maximum number of iterations iter_max is 500, and the crossover rate c₁ and c₂ are both equal to 0.7.

Table 2
Parameter levels

Factor Level

1 2 3 4

PS 20 30 40 50

iter _max 200 300 400 500

c ₁ 0.6 0.7 0.8 0.9

c ₂ 0.6 0.7 0.8 0.9

Factor	Level
PS	20	30	40	50
iter _max	200	300	400	500
c ₁	0.6	0.7	0.8	0.9
c ₂	0.6	0.7	0.8	0.9

Table 3

Orthogonal array

Combination	Factor				Avg
number	PS	iter _max	c ₁	c ₂
1	1	1	1	1	35750.3
2	1	2	2	2	34818.3
3	1	3	3	3	34646.7
4	1	4	4	4	34380.4
5	2	1	2	3	35111.5
6	2	2	1	4	34637.5
7	2	3	4	1	34250.6
8	2	4	3	2	33861.4
9	3	1	3	4	34566.3
10	3	2	4	3	34624.6
11	3	3	1	2	33694.6
12	3	4	2	1	33210.3
13	4	1	4	2	34564.3
14	4	2	3	1	34405.6
15	4	3	2	4	33939.9
16	4	4	1	3	33583.8

Table 4

Response value and significance rank

Level	Factor
	PS	iter _max	c ₁	c ₂
1	34898.9	34998.1	34416.6	34404.2
2	34465.3	34621.5	34270.0	34234.7
3	34024.0	34133.0	34370.0	34491.7
4	34123.4	33759.0	34455.0	34381.0
Delta	874.9	1239.1	185.0	257.0
Rank	2	1	3	4

Fig.3

Factor level trend of parameters.

4.3 Comparison of different algorithms

In order to verify the effectiveness of the DAMO algorithm, it is compared with seven algorithms, such as AMONLD, AMORAN, VNS [2], MMBO [20], MJAYA [22], DWWO [19] and IWOA [7]. The main reasons to choose these compared algorithms are as follows: (1) The AMONLD and the AMORAN are the abbreviated versions of the proposed DAMO. The AMONLD denotes the algorithm where the left-shifting decoding is excluded, the processing time of each operation O_ij can be measured by ST_ij = max(CT_i(j-1), MET_k, WET_l). The AMORAN means that a completely random population initialization method is adopted to get initial solutions. (2) The VNS algorithm was designed for the DRCFJSP problem without considering the energy consumption. (3) The MMBO and the MJAYA was proposed for the same problem in this study. (4) The DWWO and the IWOA were respectively developed energy-saving FJSP and JSP, which can be easily modified to solve the problem under study.

The parameters of the above seven algorithms are as follows: For the AMONLD and the AMORAN algorithms, the parameters are the same with those in the DAMO algorithm; For the VNS, the maximum iteration is set to be 2.5×10⁵; For the MMBO algorithm, the population size of MMBO is 51, the maximum of iteration is 400, the number of neighboring solutions is 3, the number of the shared neighboring solutions is 1, and the number of tours is 10, the predefined lifespan of each individual is 50, and the maximum iteration of the embedded local search algorithm is 10; For the MJAYA, the population size is 50, the maximum iteration is 2000, and the maximum iteration of the embedded local search algorithm is 10; For the DWWO, the population size is 50, the maximum iteration is 2000, the maximum iteration of local search algorithm is 10, which are the same as those of the MJAYA algorithm. In addition, the maximum wave height is 10, and the number of copies generated for each solution in the propagation operator is 20; For the IWOA, the population size is 50, and the maximum iteration is 2000.

In Table 5, the first column is the instance name, the second column is the problem size, and the other columns are the computational results of different algorithms. BRPD and ARPD represent the relative percentage deviations, i.e., $BRPD = \frac{100 \times (A_{i}^{*} - A^{*})}{A^{*}}$ , $ARPD = \frac{100 \times ({\bar{A}}_{i} - A^{*})}{A^{*}}$ . $A_{i}^{*}$ represents the best value obtained by the ith algorithm in 10 runs. ${\bar{A}}_{i}$ represents the average value obtained by the ith algorithm in 10 runs. Table 6 shows the average time (in seconds) of each algorithm in 10 runs. According to the computational results in Tables 5 and 6, it can be observed that: (1) In the comparison between DAMO and AMONLD, DAMO consumes much more running time than AMONLD due to the introducing of the left-shift decoding method, but DAMO is significantly superior to AMONLD in terms of BRPD and ARPD metrics for most of the test instances, namely 28 out of 32 instance for the BRPD metric, and 29 out of 32 instances for the ARPD metric. The comparison results demonstrate that the proposed left-shift decoding method is effective for enhancing the solution quality of the algorithm. (2) In the comparison between DAMO and AMORAN, DAMO outperforms AMORAN in terms of BRPD and ARPD metrics for all test instances due to the good quality of the initial solutions. Regarding the Time metric, there is little difference between the two algorithms. It can be deduced that the population initialization method is beneficial to enhance the performance of the algorithm. (3) In the comparison with other five published algorithms, DAMO can also achieve the best values in terms of BRPD and ARPD metrics for most of the test instances, namely 27 out of 32 instance for the BRPD metric, and 26 out of 32 instances for the ARPD metric, which demonstrates the effectiveness of the proposed algorithm.

Table 5
Comparison results of BRPD and ARPD

Instance m × n × w DAMO AMONLD AMORAN VNS

BRPD ARPD BRPD ARPD BRPD ARPD BRPD ARPD

RM01 10×10×7 0.00 3.19 3.04 5.23 11.39 16.07 0.64 7.26

RM02 10×20×7 0.00 2.00 0.09 2.53 8.15 15.22 7.07 12.50

RM03 10×30×7 0.00 4.87 3.15 6.05 15.26 20.47 6.16 10.53

RM04 10×40×7 0.00 2.69 1.18 3.47 17.68 22.26 6.14 13.04

RM05 10×50×7 2.02 4.09 4.66 5.92 29.70 33.35 0.00 9.03

RM06 10×60×7 1.37 5.95 0.29 2.53 21.58 27.04 1.03 10.72

RM07 10×70×7 0.00 1.88 0.28 2.34 25.46 31.56 6.93 15.53

RM08 10×80×7 4.04 6.66 3.90 5.77 30.88 34.03 7.30 11.79

RM09 15×10×10 0.00 2.01 0.28 3.58 5.27 10.75 0.99 5.83

RM10 15×20×10 0.00 1.72 0.81 3.04 16.46 19.91 5.93 12.08

RM11 15×30×10 0.04 2.40 0.14 3.41 16.01 19.28 2.02 10.70

RM12 15×40×10 6.24 8.46 6.47 9.79 22.02 31.67 5.03 10.98

RM13 15×50×10 0.00 2.76 0.79 3.25 25.02 29.81 5.45 13.78

RM14 15×60×10 0.00 3.88 1.49 5.10 28.12 30.97 1.94 9.36

RM15 15×70×10 0.00 2.48 1.98 4.58 31.34 34.49 7.71 18.31

RM16 15×80×10 0.00 3.08 1.16 3.17 34.07 36.71 9.07 16.91

RM17 20×10×13 0.51 2.91 0.00 1.99 4.17 7.23 2.28 4.49

RM18 20×20×13 0.00 2.32 1.28 3.19 15.25 19.22 7.36 14.05

RM19 20×30×13 0.00 5.48 2.77 6.02 15.77 22.02 5.91 16.32

RM20 20×40×13 0.00 2.70 1.78 4.82 21.36 26.43 8.49 14.90

RM21 20×50×13 0.00 2.29 3.25 5.35 25.06 29.08 0.74 7.98

RM22 20×60×13 0.00 2.04 0.71 3.80 29.00 33.34 3.27 10.38

RM23 20×70×13 0.00 2.82 2.52 5.27 31.06 34.96 5.58 15.16

RM24 20×80×13 0.02 2.94 2.96 4.88 34.53 39.44 0.00 15.23

RM25 25×10×16 1.55 3.32 0.00 3.62 5.90 7.67 1.34 7.08

RM26 25×20×16 0.00 2.22 1.50 3.20 13.14 16.90 12.03 17.51

RM27 25×30×16 0.00 3.64 0.57 3.94 13.90 22.21 11.21 18.84

RM28 25×40×16 0.00 4.40 0.21 5.47 24.97 27.87 9.51 16.01

RM29 25×50×16 0.00 3.98 2.65 5.87 29.55 34.51 12.65 21.79

RM30 25×60×16 0.00 3.37 2.73 5.54 29.50 35.51 3.73 17.15

RM31 25×70×16 0.00 3.14 4.24 5.81 32.85 37.64 5.19 13.67

RM32 25×80×16 0.00 2.63 4.10 5.89 37.66 41.84 9.27 20.10

Instance m × n × w MMBO MJAYA DWWO IWOA

BRPD ARPD BRPD ARPD BRPD ARPD BRPD ARPD

RM01 10×10×7 1.46 4.36 9.82 14.40 4.83 7.20 17.25 23.27

RM02 10×20×7 5.56 6.91 11.02 15.82 20.78 22.25 24.55 34.90

RM03 10×30×7 3.84 7.28 12.57 16.65 26.30 27.59 33.75 41.74

RM04 10×40×7 1.98 6.15 3.25 9.90 31.78 33.91 44.06 51.22

RM05 10×50×7 2.27 3.84 8.64 10.44 32.72 33.59 41.19 46.91

RM06 10×60×7 0.00 1.50 5.72 8.40 30.86 32.65 43.76 52.39

RM07 10×70×7 2.56 5.13 8.72 13.18 36.53 37.78 51.53 58.57

RM08 10×80×7 0.00 1.71 0.50 4.01 34.08 35.86 56.25 64.61

RM09 15×10×10 0.50 2.57 3.06 6.51 3.86 6.11 14.55 19.01

RM10 15×20×10 1.39 5.13 11.35 13.73 21.67 22.80 28.40 35.18

RM11 15×30×10 0.00 2.93 5.48 8.62 23.62 26.32 34.97 40.54

RM12 15×40×10 0.00 4.21 1.11 6.62 33.29 34.62 43.59 49.68

RM13 15×50×10 1.49 3.81 3.81 8.87 35.46 37.57 43.28 55.48

RM14 15×60×10 3.57 4.83 4.46 6.43 29.82 32.44 56.48 64.39

RM15 15×70×10 3.59 7.52 9.33 11.86 44.03 44.87 58.75 69.92

RM16 15×80×10 2.89 4.37 0.51 7.35 40.27 40.72 63.28 69.81

RM17 20×10×13 1.14 1.86 0.43 4.25 2.26 5.16 12.05 17.94

RM18 20×20×13 3.03 7.07 9.38 12.62 24.25 25.69 36.41 41.65

RM19 20×30×13 4.76 6.61 11.68 13.78 32.85 34.34 44.98 50.27

RM20 20×40×13 2.87 5.47 3.72 8.27 37.65 39.20 53.49 57.70

RM21 20×50×13 0.53 3.69 2.25 5.71 36.97 38.74 52.22 63.00

RM22 20×60×13 3.12 4.74 1.78 6.42 39.93 42.00 52.89 61.37

RM23 20×70×13 4.49 6.21 3.35 7.21 34.34 37.66 60.76 73.37

RM24 20×80×13 5.02 6.32 2.43 4.22 40.91 42.39 63.42 72.12

RM25 25×10×16 0.42 2.72 4.01 5.93 1.45 3.13 12.42 16.86

RM26 25×20×16 4.98 6.47 8.12 12.38 24.86 26.29 35.01 41.46

RM27 25×30×16 5.01 7.36 8.82 12.28 34.95 35.74 44.16 50.28

RM28 25×40×16 3.95 6.77 4.39 6.76 37.52 39.18 44.45 57.22

RM29 25×50×16 6.41 8.31 8.08 9.61 45.03 46.15 59.45 67.48

RM30 25×60×16 5.65 7.42 3.01 6.49 42.85 44.33 62.29 73.13

RM31 25×70×16 4.21 7.49 3.20 6.20 42.81 44.82 56.76 69.57

RM32 25×80×16 6.92 8.80 2.85 6.07 45.25 48.20 63.75 80.29

Instance	m × n × w	DAMO	AMONLD	AMORAN	VNS
RM01	10×10×7	0.00	3.19	3.04	5.23	11.39	16.07	0.64	7.26
RM02	10×20×7	0.00	2.00	0.09	2.53	8.15	15.22	7.07	12.50
RM03	10×30×7	0.00	4.87	3.15	6.05	15.26	20.47	6.16	10.53
RM04	10×40×7	0.00	2.69	1.18	3.47	17.68	22.26	6.14	13.04
RM05	10×50×7	2.02	4.09	4.66	5.92	29.70	33.35	0.00	9.03
RM06	10×60×7	1.37	5.95	0.29	2.53	21.58	27.04	1.03	10.72
RM07	10×70×7	0.00	1.88	0.28	2.34	25.46	31.56	6.93	15.53
RM08	10×80×7	4.04	6.66	3.90	5.77	30.88	34.03	7.30	11.79
RM09	15×10×10	0.00	2.01	0.28	3.58	5.27	10.75	0.99	5.83
RM10	15×20×10	0.00	1.72	0.81	3.04	16.46	19.91	5.93	12.08
RM11	15×30×10	0.04	2.40	0.14	3.41	16.01	19.28	2.02	10.70
RM12	15×40×10	6.24	8.46	6.47	9.79	22.02	31.67	5.03	10.98
RM13	15×50×10	0.00	2.76	0.79	3.25	25.02	29.81	5.45	13.78
RM14	15×60×10	0.00	3.88	1.49	5.10	28.12	30.97	1.94	9.36
RM15	15×70×10	0.00	2.48	1.98	4.58	31.34	34.49	7.71	18.31
RM16	15×80×10	0.00	3.08	1.16	3.17	34.07	36.71	9.07	16.91
RM17	20×10×13	0.51	2.91	0.00	1.99	4.17	7.23	2.28	4.49
RM18	20×20×13	0.00	2.32	1.28	3.19	15.25	19.22	7.36	14.05
RM19	20×30×13	0.00	5.48	2.77	6.02	15.77	22.02	5.91	16.32
RM20	20×40×13	0.00	2.70	1.78	4.82	21.36	26.43	8.49	14.90
RM21	20×50×13	0.00	2.29	3.25	5.35	25.06	29.08	0.74	7.98
RM22	20×60×13	0.00	2.04	0.71	3.80	29.00	33.34	3.27	10.38
RM23	20×70×13	0.00	2.82	2.52	5.27	31.06	34.96	5.58	15.16
RM24	20×80×13	0.02	2.94	2.96	4.88	34.53	39.44	0.00	15.23
RM25	25×10×16	1.55	3.32	0.00	3.62	5.90	7.67	1.34	7.08
RM26	25×20×16	0.00	2.22	1.50	3.20	13.14	16.90	12.03	17.51
RM27	25×30×16	0.00	3.64	0.57	3.94	13.90	22.21	11.21	18.84
RM28	25×40×16	0.00	4.40	0.21	5.47	24.97	27.87	9.51	16.01
RM29	25×50×16	0.00	3.98	2.65	5.87	29.55	34.51	12.65	21.79
RM30	25×60×16	0.00	3.37	2.73	5.54	29.50	35.51	3.73	17.15
RM31	25×70×16	0.00	3.14	4.24	5.81	32.85	37.64	5.19	13.67
RM32	25×80×16	0.00	2.63	4.10	5.89	37.66	41.84	9.27	20.10

Instance	m × n × w	MMBO	MJAYA	DWWO	IWOA
RM01	10×10×7	1.46	4.36	9.82	14.40	4.83	7.20	17.25	23.27
RM02	10×20×7	5.56	6.91	11.02	15.82	20.78	22.25	24.55	34.90
RM03	10×30×7	3.84	7.28	12.57	16.65	26.30	27.59	33.75	41.74
RM04	10×40×7	1.98	6.15	3.25	9.90	31.78	33.91	44.06	51.22
RM05	10×50×7	2.27	3.84	8.64	10.44	32.72	33.59	41.19	46.91
RM06	10×60×7	0.00	1.50	5.72	8.40	30.86	32.65	43.76	52.39
RM07	10×70×7	2.56	5.13	8.72	13.18	36.53	37.78	51.53	58.57
RM08	10×80×7	0.00	1.71	0.50	4.01	34.08	35.86	56.25	64.61
RM09	15×10×10	0.50	2.57	3.06	6.51	3.86	6.11	14.55	19.01
RM10	15×20×10	1.39	5.13	11.35	13.73	21.67	22.80	28.40	35.18
RM11	15×30×10	0.00	2.93	5.48	8.62	23.62	26.32	34.97	40.54
RM12	15×40×10	0.00	4.21	1.11	6.62	33.29	34.62	43.59	49.68
RM13	15×50×10	1.49	3.81	3.81	8.87	35.46	37.57	43.28	55.48
RM14	15×60×10	3.57	4.83	4.46	6.43	29.82	32.44	56.48	64.39
RM15	15×70×10	3.59	7.52	9.33	11.86	44.03	44.87	58.75	69.92
RM16	15×80×10	2.89	4.37	0.51	7.35	40.27	40.72	63.28	69.81
RM17	20×10×13	1.14	1.86	0.43	4.25	2.26	5.16	12.05	17.94
RM18	20×20×13	3.03	7.07	9.38	12.62	24.25	25.69	36.41	41.65
RM19	20×30×13	4.76	6.61	11.68	13.78	32.85	34.34	44.98	50.27
RM20	20×40×13	2.87	5.47	3.72	8.27	37.65	39.20	53.49	57.70
RM21	20×50×13	0.53	3.69	2.25	5.71	36.97	38.74	52.22	63.00
RM22	20×60×13	3.12	4.74	1.78	6.42	39.93	42.00	52.89	61.37
RM23	20×70×13	4.49	6.21	3.35	7.21	34.34	37.66	60.76	73.37
RM24	20×80×13	5.02	6.32	2.43	4.22	40.91	42.39	63.42	72.12
RM25	25×10×16	0.42	2.72	4.01	5.93	1.45	3.13	12.42	16.86
RM26	25×20×16	4.98	6.47	8.12	12.38	24.86	26.29	35.01	41.46
RM27	25×30×16	5.01	7.36	8.82	12.28	34.95	35.74	44.16	50.28
RM28	25×40×16	3.95	6.77	4.39	6.76	37.52	39.18	44.45	57.22
RM29	25×50×16	6.41	8.31	8.08	9.61	45.03	46.15	59.45	67.48
RM30	25×60×16	5.65	7.42	3.01	6.49	42.85	44.33	62.29	73.13
RM31	25×70×16	4.21	7.49	3.20	6.20	42.81	44.82	56.76	69.57
RM32	25×80×16	6.92	8.80	2.85	6.07	45.25	48.20	63.75	80.29

Table 6

Comparison results of the running time

Instance	m × n × w	DAMO	AMONLD	AMORAN	VNS	MMBO	MJAYA	DWWO	IWOA
RM01	10×10×7	8.5	2.1	8.5	24.4	18.5	13.8	11.2	8.2
RM02	10×20×7	33.9	4.8	35.3	35.5	45.0	36.7	23.2	21.3
RM03	10×30×7	72.8	8.3	75.3	51.6	79.5	51.7	37.9	36.9
RM04	10×40×7	135.1	12.5	142.9	95.8	123.3	84.7	51.9	51.8
RM05	10×50×7	246.1	19.2	248.4	98.8	179.0	163.5	84.2	88.3
RM06	10×60×7	404.5	26.5	425.9	151.0	258.9	253.4	150.6	104.0
RM07	10×70×7	594.6	34.1	591.2	176.6	337.5	321.3	195.2	134.0
RM08	10×80×7	902.7	43.7	869.4	216.4	414.9	381.5	234.7	200.5
RM09	15×10×10	7.3	2.3	7.8	25.4	22.4	13.7	13.4	8.6
RM10	15×20×10	27.8	5.5	29.9	38.1	52.2	37.7	24.1	21.5
RM11	15×30×10	61.9	9.2	63.7	56.0	88.3	66.8	40.7	37.9
RM12	15×40×10	110.6	14.1	114.4	102.5	136	86.9	58.4	44.0
RM13	15×50×10	194.9	20.3	199.1	107.2	199.4	159.8	94.8	87.6
RM14	15×60×10	321.6	27.9	313.6	159.5	290.7	248.3	176.8	90.3
RM15	15×70×10	437.2	35.8	446.6	192.6	365	326.2	213.1	116.1
RM16	15×80×10	606.9	45.9	605.9	230.1	451.3	387.3	234.8	201.9
RM17	20×10×13	7.3	2.7	7.6	26.6	24.9	15.3	15.4	9.3
RM18	20×20×13	26.5	5.8	28.2	43.6	56.9	39.5	28.5	23.3
RM19	20×30×13	58.7	10.2	59.9	60.8	100.3	75.0	45.3	41.2
RM20	20×40×13	106.1	15.8	103.9	101.4	150.2	94.9	67.4	46.0
RM21	20×50×13	174.4	22.3	180.9	116.5	219.9	174.7	103.5	91.5
RM22	20×60×13	273.6	30.4	278.1	165.1	306.6	248.1	178.6	97.3
RM23	20×70×13	391.5	38.9	385.9	197.2	366.2	320.6	249.6	123.8
RM24	20×80×13	555.7	48.8	531.8	245.6	490.9	402.4	257.6	216.7
RM25	25×10×16	7.6	3.1	7.3	28.3	28.8	16.6	17.6	10.3
RM26	25×20×16	27.8	6.4	26.6	46.8	69.1	44.9	32.3	24.9
RM27	25×30×16	57.3	10.9	57.9	65.8	113.2	76.8	49.1	44.0
RM28	25×40×16	100.6	16.5	100.6	106.3	168.1	99.4	68.4	49.5
RM29	25×50×16	171.6	23.1	168.8	127.7	245.1	187.7	109.0	98.6
RM30	25×60×16	277.3	31.9	259.5	176.5	340.8	286.4	193.6	99.8
RM31	25×70×16	366.9	40.7	357.5	211.5	431.5	363.9	254.7	128.5
RM32	25×80×16	508.8	52.6	495.1	260.4	531.6	420.6	275.8	224.1

To ensure the comparison results statistically more convincing, Table 7 conducts the paired-sample t-test to test the performance of the eight algorithms, where the t-test (A,B) represents the paired t-test between algorithm A and algorithm B. If the p-value is less than 0.05, A performs better than B. As observed from Table 7, all the p-values are smaller than 0.05. This indicates that the performance of our DABO is superior to other algorithms, which is consistent with the previous analyses. Figures 4 and 5 respectively show the Gantt charts under the instances RM04 and RM14, which are obtained by the DAMO algorithm.

Table 7

T-test results of paired samples

t-test	p-value (BRPD)	p-value (ARPD)
t-test(DAMO, AMONLD)	6.18316E-06	2.63643E-05
t-test(DAMO, AMORAN)	5.60933E-14	3.56527E-15
t-test(DAMO, VNS)	1.00592E-07	3.3899E-13
t-test(DAMO, MMBO)	5.09932E-05	4.43167E-04
t-test(DAMO, MJAYA)	1.96831E-07	6.0749E-09
t-test(DAMO, DWWO)	1.68096E-14	2.05717E-14
t-test(DAMO, IWOA)	2.62206E-16	1.5248E-16

Fig.4

Gantt chart of the instance RM04.

Fig.5

Gantt chart of the instance RM14.

5 Conclusions

In this paper, the dual resource constrained energy-saving flexible job shop scheduling problem is studied, and a discrete animal migration algorithm is proposed for minimize the total energy consumption in the workshop. A encoding method based on job and resource is used to represent the scheduling solution, and an energy-saving decoding method is adopted to save energy based on the left-shifting mechanism. A population initialization method is proposed to obtain the scheduling solutions with a certain quality and diversity. In addition, a kind of animal migration operator based on neighborhood structures and individual updating operator based on crossover operation are developed according to the characteristics of the problem. A large number of simulation experiments show that the DAMO algorithm is effective in solving the considered problem.

The limitation of this paper is that static scheduling with single-objective is only considered, thereby restricting the implementation of DAMO for multi-objective scheduling problem in dynamic manufacturing environment. Moreover, it should be acknowledged that the left-shift decoding method concentrates more on the improvement of the solution quality, which leads to the increasing of the computational time. In the next work, more practical factors will be considered in the energy-saving scheduling problems to bridge the gap between the theoretical research and practical application, such as multiple optimization objectives, dynamic manufacturing environment, distributed workshop, transportation constraints, deterioration effect, time-of-use electricity policy, renewable resources, etc. Furthermore, we will further extract the knowledge contained in the problem, obtain more efficient search strategies, improve the computational efficiency of the algorithm, and study the effective combination of AMO algorithm with other intelligence optimization algorithms.

Footnotes

Acknowledgments

This research was funded by the Fundamental Research Funds for the Central Universities, JLU, the Shandong Provincial Natural Science Foundation under Grant ZR2020QG005, ZR2021MG008, the Youth Entrepreneurship and Technology of Colleges and Universities in Shandong Province (2019KJN002); the Yantai Science and Technology Planning Project (2021xdhz072); the Major Innovation Projects in Shandong Province (2020CXGC010701, 2020CXGC010702), the Doctoral Foundation of Shandong Technology and Business University under Grant BS201938.

References

Jiang

and Zhang

, Adaptive discrete cat swarm optimisation algorithm for the flexible job shop problem, International Journal of Bio-Inspired Computation 13(3) (2019), 199–208.

Lei

and Guo

, Variable neighbourhood search for dual-resource constrained flexible job shop scheduling, International Journal of Production Research 52(9) (2014), 2519–2529.

Zheng

and Wang

, A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem, International Journal of Production Research 54(18) (2016), 5554–5566.

Yazdani

, Zandieh

, Tavakkoli-Moghaddam

, et al., Two meta-heuristic algorithms for the dual-resource constrained flexible job-shop scheduling problem, Scientia Iranica. Transaction E, Industrial Engineering 22(3) (2015), 1242–1257.

Kress

, Müller

and Nossack

, A worker constrained flexible job shop scheduling problem with sequence-dependent setup times, OR Spectrum 41(1) (2019), 179–217.

, Li

, Guo

, et al., Solving the dual-resource constrainedflexible job shop scheduling problem with learning effect by ahybrid genetic algorithm, Advances in Mechanical Engineering 10(10) (2018), 1687814018804096.

Jiang

, Zhang

and Zhu

, et al., Energy-efficient scheduling fora job shop using an improved whale optimization algorithm, Mathematics 6(11) (2018), 220–239.

Lei

, Zheng

and Guo

, A shuffled frog-leaping algorithm for flexible job shop scheduling with the consideration of energy consumption, International Journal of Production Research 55(11) (2017), 3126–3140.

Jiang

and Deng

, Optimizing the low-carbon flexible job shop scheduling problem considering energy consumption, IEEE Access 6 (2018), 46346–46355.

10.

, Shen

and Li

, The flexible job-shop scheduling problem considering deterioration effect and energy consumption simultaneously, Computers & Industrial Engineering 135 (2019), 1004–1024.

11.

and Sun

, A green scheduling algorithm for flexible job shop with energy-saving measures, Journal of Cleaner Production 172 (2018), 3249–3264.

12.

Jiang

, Zhu

and Deng

, Improved African buffalo optimization algorithm for the green flexible job shop scheduling problem considering energy consumption, Journal of Intelligent & Fuzzy Systems 38(4) (2020), 4573–4589.

13.

Ren

, Wen

and Yan

, et al., Multi-objective optimisation for energy-aware flexible job-shop scheduling problem with assembly operations, International Journal of Production Research (2020), 1–16.

14.

Yin

, Li

, Gao

, et al., A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem, Sustainable Computing: Informatics and Systems 13 (2017), 15–30.

15.

Zhang

, Wu

, Peng

, et al., An improved scheduling approach for minimizing total energy consumption and make span in a flexible job shop environment, Sustainability 11(1) (2019), 179.

16.

and Lei

, An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times, Engineering Applications of Artificial Intelligence 103 (2021), 104307.

17.

Dai

, Tang

, Giret

, et al., Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints, Robotics and Computer-Integrated Manufacturing 59 (2019), 143–157.

18.

Zhang

, Xu

, Pan

, et al., A novel heuristic method for the energy-efficient flexible job-shop scheduling problem with sequence-dependent set-up and transportation time, Engineering Optimization (2021), 1–22.

19.

, Lu

and Jiang

, Energy-conscious scheduling problem in a flexible job shop using a discrete water wave optimization algorithm, IEEE Access 7 (2019), 101561–101574.

20.

, Zhu

and Jiang

, Modified migrating birds optimization for energy-aware flexible job shop scheduling problem, Algorithms 13(2) (2020), 44–56.

21.

and Li

, Sustainable flexible job shop scheduling problemconsidering dual resources, Computer Integrated Manufacturing Systems (2020), https://kns-cnki-net.web.bisu.edu.cn/kcms/detail/11.5946.tp.20201026.1047.024.html.

22.

, Zhu

and Jiang

, Modified JAYA algorithm for solving theflexible job shop scheduling problem considering worker flexibility and energy consumption, International Journal of Wirelessand Mobile Computing 20(3) (2021), 212–223.

23.

Wolpert

D.H.

and Macready

W.G.

, No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1(1) (1997), 67–82.

24.

Zhu

and Zhou

, An efficient evolutionary grey wolf optimizer for multi-objective flexible job shop scheduling problem with hierarchical job precedence constraints, Computers & Industrial Engineering 140 (2020), 106280.

25.

Wang

G.G.

and Tan

, Improving metaheuristic algorithms with information feedback models, IEEE Transactions on Cybernetics 49(2) (2017), 542–555.

26.

Wang

G.G.

, Guo

, Gandomi

A.H.

, et al., Chaotic krill herd algorithm, Information Sciences 274 (2014), 17–34.

27.

Wang

G.G.

, Deb

and Cui

, Monarch butterfly optimization, Neural Computing and Applications 31(7) (2019), 1995–2014.

28.

Wang

G.G.

, Moth search algorithm: a bio-inspired metaheuristic algorithm for global optimization problems, Memetic Computing 10(2) (2018), 151–164.

29.

Zhang

, Wang

G.G.

, Li

, et al., Enhancing MOEA/D with information feedback models for large-scale many-objective optimization, Information Sciences 522 (2020), 1–16.

30.

Ganguly

, Multi-objective distributed generation penetration planning with load model using particle swarm optimization, Decision Making: Applications in Management and Engineering 3(1) (2020), 30–42.

31.

Biswas

and Pal

B.B.

, A fuzzy goal programming method to solve congestion management problem using genetic algorithm, Decision Making: Applications in Management and Engineering 2(2) (2019), 36–53.

32.

, Zhang

and Yin

, Animal migration optimization: an optimization algorithm inspired by animal migration behavior, Neural Computing and Applications 24(7-8) (2014), 1867–1877.

33.

Zhou

, Luo

, Ma

et al., Animal migration optimization algorithm for constrained engineering optimization problems, Journal of Computational and Theoretical Nanoscience 13(1) (2016), 539–546.

34.

ÜLKER

, An elitist approach for solving the traveling salesman problem using an animal migration optimization algorithm, Turkish Journal of Electrical Engineering & Computer Sciences 26(1) (2018), 605–617.

35.

Farshi

T.R.

, A multilevel image thresholding using the animal migration optimization algorithm, Iran Journal of Computer Science 2(1) (2019), 9–22.

36.

Subhashini

K.R.

and Chinta

, An augmented animal migration optimization algorithm using worst solution elimination approach in the backdrop of differential evolution, Evolutionary Intelligence 12(2) (2019), 273–303.

37.

Pezzella

, Morganti

and Ciaschetti

, A genetic algorithm for the flexible job-shop scheduling problem, Computers & Operations Research 35(10) (2008), 3202–3212.

A discrete animal migration algorithm for dual-resource constrained energy-saving flexible job shop scheduling problem

Abstract

Keywords

1 Introduction

3.1 Basic animal migration optimization

3.4 Population initialization

3.4.1 Initial resource allocation

3.4.2 Initial operation permutation

3.5 Discrete search operators

3.5.1 Animal migration operator

4 Simulation experiment

4.1 Test instance

4.2 Parameter settings

Table 2 Parameter levels Factor Level 1 2 3 4 PS 20 30 40 50 iter max 200 300 400 500 c 1 0.6 0.7 0.8 0.9 c 2 0.6 0.7 0.8 0.9

Footnotes

Acknowledgments

References

Table 2
Parameter levels

Factor Level

1 2 3 4

PS 20 30 40 50

iter _max 200 300 400 500

c ₁ 0.6 0.7 0.8 0.9

c ₂ 0.6 0.7 0.8 0.9