Sage Journals: Discover world-class research

Abstract

In this article, we investigate a novel dual-resource constrained flexible job shop scheduling problem with consideration of worker’s learning ability and develop an efficient hybrid genetic algorithm to solve the problem. To begin with, a comprehensive mathematical model with the objective of minimizing the makespan is formulated. Then, a hybrid algorithm which hybridizes genetic algorithm and variable neighborhood search is developed. In the proposed algorithm, a three-dimensional chromosome coding scheme is employed to represent the individuals, a mixed population initialization method is designed for yielding the initial population, and advanced crossover and mutation operators are proposed according to the problem characteristic. Moreover, variable neighborhood search is integrated to improve the local search ability. Finally, to evaluate the effectiveness of the proposed algorithm, computational experiments are performed. The results demonstrate that the proposed algorithm can solve the problem effectively and efficiently.

Keywords

Flexible job shop scheduling problem dual-resource constrained learning ability genetic algorithm variable neighborhood search

Introduction

The flexible job shop scheduling problem (FJSP)¹ is a classic abstraction of actual production process and has been well known as one of the most important NP-hard combinatorial optimization problems. The FJSP consists of two sub-problems, that is, routing and scheduling. The routing sub-problem is to assign each operation to a machine among a set of given machines, whereas the scheduling sub-problem is to sequence the assigned operations on all machines to obtain a feasible schedule with a satisfactory objective value. It has been a research hotspot for decades and many research works have been carried out.^2–10

In FJSP, operation-sequence-constraint and machine-resources-constraint are considered, but the constraints imposed by the workers are ignored. However, in reality, operations cannot be processed if workers are not available or if workers lack requisite skills. Aiming at overcome this drawback, it is necessary to take the worker-resources-constraint into account. Thus, the extended FJSP which considers the worker-resources-constraint is proposed, it is called the dual-resource constrained flexible job shop scheduling problem (DRCFJSP).¹¹ Research on this problem can be applied to many production fields, such as automobile manufacturing, equipment manufacturing, and electronic products manufacturing. To solve the DRCFJSP, determination of operation sequence and allocation of the resources, including machines and workers, are required.

Because of the high complexity, it is quite difficult to achieve an optimal solution for the DRCFJSP with traditional optimization approaches in a reasonable computational time. Hence, many approaches, especially meta-heuristic algorithms, have been widely developed for solving the DRCFJSP. Cao and Yang¹² put forward a new immune genetic algorithm (GA) through combining immune algorithm with GA for solving the DRCFJSP. Operation-based encoding and an active schedule decoding method were employed, and several kinds of crossover operations were adopted to keep individual diversity. Liu et al.¹³ built a bi-objective DRCFJSP optimization model with the makespan and the production cost was concerned, and they applied a hybrid GA based on Pareto to solve the problem. The proposed algorithm embedded Pareto ranking strategy into Pareto competition method, the niche technology, and four kinds of crossover operations were used to promote solution diversity. Zhang et al.¹⁴ proposed a novel multi-objective hybrid particle swarm algorithm to solve the dual-resource constrained job shop scheduling problem with minimizing production period and production cost. In the proposed algorithm, simulated annealing (SA) with variable neighborhoods structure was introduced to improve the local search ability, and an external archive based on Pareto-dominance was applied to store the nondominated solutions. Lei and Guo¹⁵ proposed an effective variable neighborhood search (VNS) to minimize makespan of DRCFJSP, in which the solution of the problem was indicated as a quadruple string of the ordered operations and their resources. VNS was composed of two neighborhood search procedures and a restarting mechanism. Yazdani et al.¹⁶ addressed the DRCFJSP with the objective of minimizing the makespan. The authors presented two efficient meta-heuristic algorithms, SA and vibration damping optimization (VDO), to solve the DRCFJSP. The search procedure of both algorithms used four efficient neighborhood structures to search the solution space. Zheng and Wang¹⁷ aimed to solve the DRCFJSP with a makespan minimization criterion. A knowledge-guided fruit fly optimization algorithm with a new encoding method was proposed. In the proposed algorithm, two types of permutation-based search operators were designed to perform the smell-based search for operation sequence and resource assignment. Gao and Pan¹⁸ studied the FJSP under multi-resource constraints with the objective of minimizing the makespan. A dynamic shuffled multi-swarm micro-migrating birds optimization algorithm was presented for solving the problem. In Paksi and Ma’Ruf,¹⁹ a meta-heuristic approach, based on GA, was presented to solve the DRCFJSP. In the proposed algorithm, indirect chromosome representative that consists of two layers was used, and selection, elitism, crossover, and mutation operators are developed to search the best fitness value until steady-state condition was achieved. Zhang et al.²⁰ proposed a novel hybrid discrete particle swarm optimization (HDPSO) algorithm to solve the dual-resource constrained job shop scheduling problem with resource flexibility.

In most of the previous studies on DRCFJSP, all workers are supposed to be the same and have same efficiency. Only a very few studies have considered the heterogeneous workers. However, the efficiencies of workers are fixed throughout the entire processing period in these studies. Obviously, it is not accord with the actual situations, because workers have the ability to learn and remember. In reality, the efficiencies of workers will increase with the accumulation of experience and knowledge. Therefore, the DRCFJSP with consideration of worker’s learning ability is a more conformable abstraction of reality production environment, and it is an interesting topic to be investigated and has not been studied before. Thus, this article puts forward a novel DRCFJSP with learning effect (DRCFJSP-LE) and studies the method to solve the problem.

GA^21,22 is a kind of algorithm based on principles of natural selection and genetics; it simulates the biological evolution. Because GA has rapid random search ability, strong robustness, simple process, strong extensibility, and the other characteristics, it has been widely applied in various fields^23–26 and also has been proven to be one of the most effective evolutionary techniques for solving job shop scheduling problems.^27–31 Therefore, in this article, we use GA to solve the DRCFJSP. In addition, because local search is a promising approach for improving the convergence speed of GA,³² and VNS is an effective meta-heuristics based on local search methods, we adopt VNS to improve the convergence speed of GA and balance exploration and exploitation.

In this study, a new mathematical model considering worker’s learning ability in DRCFJSP is established. This model considers operation-sequence-constraint as well as machine and worker resources constraints and also considers the improvement of worker’s efficiency. To effectively solve this mixed integer programming model, an effective hybrid genetic algorithm (GA-VNS) is proposed. The corresponding encoding/decoding method, population initialization strategy, and crossover/mutation operators are designed according to the features of this problem. Moreover, under the framework of GA, an improved VNS with three neighborhood structures is introduced to enhance the local search ability. Finally, experimental results show that the proposed algorithm is feasible and effective.

The remainder of this article is organized as follows. Problem description and model formulation are presented in section “Problem description and formulation.” GA-VNS for solving the studied problem is elaborated in section “Proposed GA-VNS for DRCFJSP-LE.” Computational experiments and comparison summary are stated in section “Experimental studies and discussion.” Finally, conclusions and lines for further research are drawn in section “Conclusion.”

Problem description and formulation

In DRCFJSP-LE, operations can be processed only if the selected machine and worker are both available and eligible. The actual processing time of each operation depends on the given basic processing time and the worker’s processing efficiency. Workers may have different abilities and processing efficiencies when they operate the same machine. Because of the learning ability, worker’s processing efficiency will increase with the accumulation of processing time, but it cannot be improved indefinitely, it will stop at a given highest level. Workers have different learning efficiencies, and it is an inherent property of the worker. To describe the problem more formally, a mathematical model is established to minimize the makespan.

The assumptions are conducted for this studied problem as follows:

All machines and workers are available at time 0.

There are no precedence constraints among the jobs and all jobs are released at time 0.

Each machine can process only one operation at a time.

Each worker can be set on only one machine at a time.

The promotion of operating efficiency is only related to the accumulation of processing time.

Transportation times, setup times, and release times are negligible.

Each operation cannot be interrupted during its performance.

The indices, sets, parameters, and decision variables used throughout the article are defined as follows:

Indices and sets

$i, i'$ : index of jobs

$k, k'$ : index of machines

r: index of workers

$j, j'$ : index of operations

$O_{i, j}$ : jth operation in job i

J: set of jobs

M: set of machines

W: set of workers

$M_{i, j}$ : set of alternative machines for operation $O_{i, j}$

$W_{k}$ : set of alternative workers for machine k

Parameters

$n$ : total number of jobs

$m$ : total number of machines

$w$ : total number of workers

$p_{i}$ : total number of operations in job i

$t_{i, j, k}$ : basic processing time of operation $O_{i, j}$ on machine k

$e_{r, k}$ : basic efficiency of worker r operating machine k

$a_{r}$ : learning coefficient of worker r, $a_{r} < 0$

$d_{k}$ : limiting efficiency of machine k, $0 < k < 1$

$L$ : a large enough number

Decision variables

$S_{i, j}$ : starting time of operation $O_{i, j}$

$C_{i, j}$ : completion time of operation $O_{i, j}$

$C_{i}$ : completion time of job i

$C_{\max}$ : maximum completion time over all jobs (makespan)

$T_{k, r}$ : ready time for machine k operated by worker r

$A_{i, j, k, r}$ : cumulative time of worker r operating machine k before starting $O_{i, j}$

$h_{i, j}$ : actual processing time of operation $O_{i, j}$

$X_{i, j, k, r}$ : 1, if operation $O_{i, j}$ is processed on machine k operated by worker r; 0, otherwise

$ς_{i', j', k - i, j, k}$ : 1, if operation $O_{i', j'}$ is processed before operation $O_{i, j}$ adjacently on machine k; 0, otherwise

$ξ_{k', r - k, r}$ 1, if machine $k'$ is operated before machine k adjacently by worker r; 0, otherwise

$Y_{i', j' - i, j}$ : 1, if operation $O_{i', j'}$ is completed prior to the start of operation $O_{i, j}$

Based on the assumptions and notations above, the mathematical model with makespan minimization can be established as follows

\min C_{\max}

(1)

Equation (1) is the objective function that minimizes the makespan

C_{\max} = \max_{i = 1}^{n} {C_{i}}

(2)

Equation (2) defines the makespan $C_{\max}$ , which equals the maximum completion time over all jobs

C_{i} = C_{i, p_{i}}, i \in J

(3)

Equation (3) defines the completion time of each job, which equals the completion time of its last operation

C_{i, j} = S_{i, j} + h_{i, j}, i \in J, j = 1, 2, \dots, p_{i}

(4)

Equation (4) expresses the mathematical relationship between starting time, actual processing time, and completion time of each operation

S_{i, (j + 1)} \geq S_{i, j} + h_{i, j}, i \in J, j = 1, 2, \dots, p_{i} - 1

(5)

Equation (5) ensures that the precedence constraints between operations of a job are not violated

\begin{array}{l} A_{i, j, k, r} = \sum_{i^{'} = 1}^{n} \sum_{j^{'} = 1}^{p_{i}} h_{i^{'}, j^{'}} \times Y_{i^{'}, j^{'} - i, j} \times X_{i^{'}, j^{'}, k, r}, \\ i \in J, j = 1, 2, \dots, p_{i}, k \in M_{i, j}, r \in W_{k} \end{array}

(6)

\begin{array}{l} h_{i, j} = \sum_{k \in M_{i, j}} \sum_{r \in W_{k}} t_{i, j, k} \times x_{i, j, k, r} \\ \times (\max {e_{r, k} \times {(1 + A_{i, j, k, r})}^{a_{r}}, d_{k}}), i \in J, j = 1, 2, \dots, p_{i} \end{array}

(7)

Equation (6) calculates $A_{i, j, k, r}$ by summarizing the actual processing times of all previous operations of operation $O_{i, j}$ , which are handled by the same machine k and worker r; the actual processing time of an operation is determined by equation (7)

\begin{array}{l} S_{i, j} + (1 - ζ_{i^{'}, j^{'}, k - i, j, k}) \times L \geq S_{i^{'}, j^{'}} + h_{i^{'}, j^{'}}, i, i^{'} \in J, \\ j = 1, 2, \dots, p_{i}, j^{'} = 1, 2, \dots, p_{i^{'}}, k \in M \end{array}

(8)

T_{k, r} + (1 - ξ_{k^{'}, r - k, r}) \times L \geq T_{k^{'}, r}, k, k^{'} \in M, r \in (W_{k} \cap W_{k^{'}})

(9)

\begin{array}{l} T_{k, r} + (1 - X_{i, j, k, r}) \times L \leq S_{i, j}, i \in J, j = 1, 2, \dots, p_{i}, \\ k \in M_{i, j}, r \in W_{k} \end{array}

(10)

Equations (8) and (9) ensure that each machine can process at most one operation and each worker can operate at most one machine at a time, respectively; equation (10) guarantees that each operation cannot start until the assigned machine and worker are ready

\begin{array}{l} S_{i, j} + (1 - ζ_{i^{'}, j^{'}, k - i, j, k}) \times L \geq C_{i^{'}, j^{'}}, i, i^{'} \in J, \\ j = 1, 2, \dots, p_{i}, j^{'} = 1, 2, \dots, p_{i^{'}}, k \in M \end{array}

(11)

\sum_{k \in M_{i, j}} \sum_{r \in W_{k}} X_{i, j, k, r} = 1, i \in J, j = 1, 2, \dots, p_{i}

(12)

S_{i, j}, A_{i, j, k, r} \geq 0, h_{i, j} > 0, i \in J, j = 1, 2, \dots, p_{i}, k \in M_{i, j}, r \in W_{k}

(13)

T_{k, r} \geq 0, k \in M, r \in W_{k}

(14)

Equation (11) ensures that each operation cannot start until the immediate precedence operation on the same machine is completed; equation (12) ensures that each operation is assigned to one and only one compatible machine which is operated by one and only one eligible worker; at last, equations (13) and (14) state the range of decision variables.

Proposed GA-VNS for DRCFJSP-LE

In this section, we investigate how to solve the DRCFJSP-LE with GA-VNS for obtaining the minimal makespan. An encoding/decoding scheme and a mixed population initialization method are given first. Then adaptive selection, crossover, and mutation operators are presented for global search. Finally, an effective VNS with three neighborhood structures is introduced to improve the local search ability.

To describe the proposed algorithm clearly, an example with three jobs, three machines, and two workers is presented in Tables 1 and 2. The basic processing times are organized in Table 1, and Table 2 shows the basic operating efficiencies. “–” indicates that the machine cannot handle the operation or the worker cannot operator the machine.

Table 1.

Processing times.

	M ₁	M ₂	M ₃
$O_{1, 1}$	3	7	6
$O_{1, 2}$	–	5	4
$O_{1, 3}$	4	3	–
$O_{2, 1}$	9	–	7
$O_{2, 2}$	–	4	–
$O_{3, 1}$	7	7	8
$O_{3, 2}$	9	6	8
$O_{3, 3}$	7	–	6

Table 2.

Efficiencies.

	W ₁	W ₂
M ₁	0.8	–
M ₂	0.9	0.85
M ₃	–	0.9

Encoding and decoding

In this subsection, we propose an encoding mechanism in which each individual consists of three chromosomes: operation sequence chromosome (OSC) represents the processing sequence of operations; machine assignment chromosome (MAC) represents the allocation of machines; worker assignment chromosome (WAC) represents the assignment of workers. Each individual composed by the three chromosomes represents a feasible solution for the DRCFJSP-LE.

The number of genes in the OSC equals the total number of operations in all jobs. All operations are represented by its index of job, the gth occurrence of index i represents the gth operation in job i, and the repetition number of the index i equals the total number of operations in the job i. Figure 1(a) shows one possible OSC for the example. MAC is as long as the OSC, the gth gene in MAC represents a selected machine for the gth operation in the OSC, it is important to note that the selected machine must be an alternative machine. A feasible MAC based on the OSC in Figure 1(a) is shown in Figure 1(b). The encoding method of WAC is similar to that of MAC, the gth gene in WAC represents a selected worker for the gth machine in the WAC, and the selected worker also should be an alternative worker. A feasible WAC based on the WAC in Figure 1(b) is shown in Figure 1(c). Figure 1 shows a complete feasible individual for the given example in Tables 1 and 2.

Figure 1.

Individual coding example: (a) operation sequence chromosome, (b) machine assignment chromosome, and (c) worker assignment chromosome.

For the above representation, decoding can be divided into three steps: first, pick out the operations from the OSC one by one from left to right and obtain the corresponding machine and worker; then calculate the actual processing time of the operations using equation (7); and finally, arrange the operations at their earliest feasible time. The flowchart of decoding is presented in Figure 2. The variable $E T_{i}$ is the completion time of the latest completed operation in job i, $Ω_{k}$ is the set of occupation periods of machine k, and $θ_{r}$ is the set of occupation periods of worker r. For simplicity, set $a_{r} = - 0.2, \forall r \in W$ and $d_{k} = 0.3, \forall k \in M$ , and then, following the above decoding procedure, a schedule corresponding to the individual in Figure 1 can be obtained and the Gantt chart is illustrated in Figure 3.

Figure 2.

Flowchart of decoding.

Figure 3.

Gantt chart of coding example.

Population initialization

Since population initialization has an important influence on the algorithm’s performance, we put forward some adaptive strategies to improve the quality of initial population. Random generation is a commonly used strategy, initial population generated by this strategy has good diversity, but it does not guarantee a stable quality. Therefore, to balance the diversity and quality, we adopt a combination of random generation and strategic choice to generate the initial population. Three initialization strategies are proposed for OSCs, MACs, and WACs, respectively. First, the OSCs are generated using the mixed strategy,³³ which is composed of the following three rules:

Choose a job randomly;

Give preference to the job with the longest processing time of the remaining operations;

Choose the job with the largest number of rest operations.

The above three rules are used to generate OSCs accounted for 30%, 30%, and 40% of the initial population, respectively. Then for the MACs, 50% are selected in the constraint set randomly. The other 50% are generated by the method proposed in Kacem et al.,³⁴ and the procedures of this method are as follows:

Step 1. Pick out the gth (g = 1 at first, from left to right) operation $O_{i, j}$ from the OSC, which is in the same individual with the MAC.

Step 2. Select the machine k with the shortest basic processing time for operation $O_{i, j}$ .

Step 3. Add the basic processing time $t_{i, j, k}$ to the basic processing times of all the rest operations which can be processed by the selected machine k, and the machine assignment of the rest operations is based on the updated basic processing times.

Step 4. If g equals the total number of all operations in all jobs, stop; otherwise, set $g = g + 1$ and go to step 1.

The initialization method of the WACs is similar to that of MACs, the only difference is that one updates the basic processing times and the other updates the basic operating efficiencies.

Selection

In this article, elitist preservation and tournament selection are both adopted for the selection operation.

In elitist preservation, $⌈ α * popsize ⌉$ ( $α$ is the elite reserve ratio, 0.05 in this article, and $popsize$ is the population size) individuals with good fitness are selected into the next generation directly without genetic operations such as crossover and mutation. When using this strategy, an appropriate proportion is needed because a high proportion will reduce the diversity of the population.

The tournament selection can retain good individuals with a greater probability and eliminate the worse individuals. The implementation steps for the tournament selection strategy are described as follows:

Step 1. Select a certain number (approximately 3–5 in general) of individuals from the parent population.

Step 2. Select an individual with the highest fitness from the temporary set produced by the previous step and put the selected individual into the offspring population. The selected individual should be put back into the parent population and can be selected again.

Step 3. If the total number of individuals in the offspring population reaches the given population size, stop; otherwise, repeat the above two steps.

Crossover

Crossover is the main evolutionary operation in GA and has a significant impact on the efficiency and effectiveness of GA. In this subsection, a three-part crossover operator is proposed based on the characteristics of DRCFJSP-LE. The procedures are described in the following subsections.

Crossover for OSCs

Crossover process of OSCs is shown in Figure 4 and described below:

Step 1. Divide all operations in parent 1 into two nonempty sets randomly, marked as $j_{11}$ , $j_{12}$ ; in this example, $j_{11} = {3, 1, 2, 3, 1}$ , $j_{12} = {2, 3, 1}$ ; same as parent 2, marked as $j_{21}$ , $j_{22}$ , $j_{21} = {1, 2, 1, 2}$ , $j_{22} = {3, 3, 1, 3}$ .

Step 2. Let offspring 1 inherit all genes in $j_{11}$ and offspring 2 inherit all genes in $j_{21}$ , Keep the original position unchanged.

Step 3. Remove the genes that exist in both offspring 1 and parent 2 $({1, 3, 2, 3, 1})$ from parents 2, and then fill offspring 1 with genes left in parent 2 $({2, 1, 3})$ , keep the original order. For offspring 2, do the same with parent 1.

Step 4. For MACs and WACs in offspring 1, copy from parent 1 and adjust MACs and WACs correspondingly to keep the allocations of machine and worker unchanged. Same as offspring 2. In this way, we made a crossover operation for OSCs and kept the solution legal.

Figure 4.

Crossover for OSC.

Crossover for MACs

In this part, a new multi-point crossover method is adopted. An example is shown in Figure 5 and the execution procedure is as follows:

Step 1. Copy parent 1 to offspring 1 and parent 2 to offspring 2 (including OSCs and WACs).

Step 2. Randomly generate a vector $rand$ consisting of 0 or 1, whose length equals the chromosome.

Step 3. Select all positions in $rand$ with a value of 0 and exchange genes at the selected positions in MACs and WACs between offspring 1 and offspring 2.

Step 4. Check all genes in the MACs, if the machine is illegal (this is possible because the OSC is unchanged and a different operation may have a different alternative machine set), select a new one from the available machine set with the shortest basic processing time, and select a new worker if the current worker is also illegal.

Figure 5.

Crossover for MAC.

Crossover for WACs

For WACs, we use the simple two-point crossover. First, generate two intersection points randomly, then exchange genes between the intersection points, and finally fix the illegal values. An example is given in Figure 6.

Figure 6.

Crossover for WAC.

Mutation

The mutation operator is mainly used for maintaining the diversity of the population and improving the local search performance. In this article, the mutation operator is also divided into three parts for OSC, MAC, and WAC, respectively. The first part deals with the mutation of OSCs and the implementation detail is as follows: select two genes at different positions randomly in the parent OSC and exchange the selected genes as shown in Figure 7(a), and then adjust the MAC and WAC correspondingly to keep the allocations of machine and worker unchanged. It is proved that a new chromosome generated by this method is feasible based on the characteristics of encoding. The second part is the mutation of MACs: choose a gene randomly as the current machine in the parent MAC, then select a new machine from the available machine set (if the size of available machine set equals 1, select the gene again) that is not equal to the current machine, and finally replace the current machine by the selected new machine, as shown in Figure 7(b). If worker at the same position is illegal, then choose a new worker from alternative worker set randomly. An individual generated by this method is also feasible. The third part is the mutation of WACs, which is basically the same as the second part above, as shown in Figure 7(c).

Figure 7.

Mutation operation: (a) operation-assignment chromosome, (c) machine-assignment chromosome, and (c) worker-assignment chromosome.

Local search by VNS

VNS³⁵ is a meta-heuristic algorithm which has been successfully applied in various combinatorial optimization problems, including several scheduling problems,^36–39 and VNS has been proved to be one of the most efficient local search strategies for scheduling problems. Lei and Guo¹⁵ developed an effective VNS with variable neighborhood structures for solving the DRCFJSP, we adopt and modify it as the local search strategy in the GA-VNS. The workflow of the improved VNS is described in Algorithm 1, where $iter$ denotes the maximum iterations of VNS.

Algorithm 1. VNS
1: Get the individual x to be searched, set a = 0, b = 0, c = 0, d = 0; 2: for t = 1 → $iter$ do 3: If a = 0 or (a = 1 and b = 1 and c = 1), produce a new individual $y$ by Exchange operation; evaluate the individual y; if y is better than x, let x = y, a = 0, d = 0; else, a = 1 − a, d = d + 1; 4: If b = 0, produce a new individual y by Replace operation; evaluate the individual y; if y is better than x, let x = y, b = 0,d = 0; else, b = 1 − b, d = d + 1; 5: If c = 0, produce a new individual y by Change operation; evaluate the individual y; if y is better than x, let x = y, c = 0,d = 0; else, c = 1 − c, d = d + 1; 6: If $d > iter / 5$ , terminate and return the individual x 7: end for 8: Return the individual x.

Algorithm 1. VNS

1: Get the individual x to be searched, set a = 0, b = 0, c = 0, d = 0;
2: for t = 1 →

iter

do
3: If a = 0 or (a = 1 and b = 1 and c = 1), produce a new individual

y

by Exchange operation; evaluate the individual y; if y is better than x, let x = y, a = 0, d = 0; else, a = 1 − a, d = d + 1;
4: If b = 0, produce a new individual y by Replace operation; evaluate the individual y; if y is better than x, let x = y, b = 0,d = 0; else, b = 1 − b, d = d + 1;
5: If c = 0, produce a new individual y by Change operation; evaluate the individual y; if y is better than x, let x = y, c = 0,d = 0; else, c = 1 − c, d = d + 1;
6: If

d > iter / 5

, terminate and return the individual x
7: end for
8: Return the individual x.

Three neighborhood structures, Exchange, Replace, and Change are used in VNS:

Exchange is to make an exchange on the OSC: Select two genes with different values randomly in the OSC and exchange them, and then reallocate the machines and workers to guarantee that the new solution is feasible.

Replace is to replace the resources for an operation: Select a gene in the OSC randomly, then select a new machine with the shortest basic processing time from the operation’s alternative machine set, and finally, select a worker from the alternative worker set randomly for the new machine.

Change is to change the worker for a machine: Select a machine with more than one alternative worker in the WAC randomly, and then select a different worker with the best operating efficiency for this machine.

Workflow of the proposed GA-VNS

Based on the details introduced above, the overall procedure of the GA-VNS is depicted in Algorithm 2.

Algorithm 2. GA-VNS
1: Set parameters of the proposed GA-VNS; 2: Use the proposed initialization method to generate the initial population; 3: Evaluate all individuals by the objective function; 4: repeat 5: Use the proposed selection operator, crossover operator, and mutation operator to generate a new population; 6: Evaluate all individuals in the new population, select 50% of the individuals with higher objective function value from the population, apply the proposed local search strategy VNS to improve the quality of these individuals; 7: until Termination criteria are satisfied; 8: Output the best solution; 9: Stop.

Algorithm 2. GA-VNS

1: Set parameters of the proposed GA-VNS;
2: Use the proposed initialization method to generate the initial population;
3: Evaluate all individuals by the objective function;
4: repeat
5: Use the proposed selection operator, crossover operator, and mutation operator to generate a new population;
6: Evaluate all individuals in the new population, select 50% of the individuals with higher objective function value from the population, apply the proposed local search strategy VNS to improve the quality of these individuals;
7: until Termination criteria are satisfied;
8: Output the best solution;
9: Stop.

Experimental studies and discussion

Several experiments are carried out to verify the effectiveness of the proposed algorithm in this section. First, some necessary preparations for the experiments are introduced. Then, we test the validity of VNS by comparing GA-VNS with a simplified GA which has removed the VNS from GA-VNS and verify the performance of GA-VNS by comparing GA-VNS with a HDPSO.⁴⁰ Finally, the results and some statistical analysis are presented. All algorithms are coded in Java and run on a personal computer with 8 GB RAM and Intel Core i7 2.70 GHz CPU.

Testing instances

In this article, benchmarks for the FJSP are extended for testing the DRCFJSP-LE, because there is no common benchmarks for the DRCFJSP-LE. We choose 33 commonly used test instances 01a-18a⁴¹ and mk01-15⁴² for expansion. The supplementary data used for expansion are presented in Table 3. The total number of workers w can be calculated by $⌈ m \times 0.6 ⌉$ , where m is the total number of machines. When generating the basic efficiency $e_{r, k}$ , select 20% to set its value equal to $\infty$ , which means the worker r cannot operate the machine k, and the other 80% are generated randomly in $[0.8, 1.2]$ . A special situation that may arise is, for a given machine k, $e_{r, k} = \infty, \forall r \in W$ , it means that machine k cannot be operated by any worker. To fix this extreme case, select a worker $r'$ and $e_{r', k} \in [0.8, 1.2]$ randomly. Other parameters, such as $d_{k}$ and $a_{r}$ , are uniformly distributed in the given intervals. Instances for testing the DRCFJSP-LE can be generated using the method described above, the extended instances are still called 01a-18a and mk01-15 for simplicity.

Table 3.

Parameters for expansion.

Parameter	Description
Total number of workers (w)	$⌈ m \times 0.6 ⌉$
Basic efficiency (e_rk)	U[0.8, 1.2]
Limiting efficiency (d_k)	U[0.5,0.6]
Learning coefficient (a_r)	U[-0.2,-0.3]

Parameter setting

The selection of parameters has a noticeable influence on algorithm’s performance. In this article, we adopt the orthogonal experimental method to obtain appropriate parameters. In GA-VNS, there are four key parameters, that is, population size (popsize), crossover probability (pro_c), mutation probability (pro_m), and the iterative number of VNS (iter). We select five different levels for each parameter and list them in Table 4. The orthogonal design table $L_{25} (5^{6})$ is used and the front four columns are taken. The test combinations are shown in Table 5. For each test combination, set maximum iterations equal to 100 as the termination condition and run the GA-VNS 20 times independently on instance mk09. The average of 20 runs is used as the result for each test combination, and the results are listed in Table 5. According to the results, the best parameter setting is recommended as $popsize = 160$ , $pr o_{c} = 0.5$ , $pr o_{m} = 0.05$ , and $iter = 60$ .

Table 4.

Parameter level.

Level	$popsize$	$pr o_{c}$	$pr o_{m}$	$iter$
1	80	0.5	0.01	20
2	100	0.6	0.05	30
3	120	0.7	0.1	40
4	140	0.8	0.2	50
5	160	0.9	0.3	60

Table 5.

Orthogonal design table and results.

Index	$popsize$	$pr o_{c}$	$pr o_{m}$	$iter$	Result
1	1	1	1	1	349.93
2	1	2	5	3	339.06
3	1	3	4	5	331.39
4	1	4	3	2	340.80
5	1	5	2	4	329.99
6	2	1	5	2	336.16
7	2	2	4	4	328.21
8	2	3	3	1	341.74
9	2	4	2	3	329.58
10	2	5	1	5	326.67
11	3	1	4	3	327.28
12	3	2	3	5	324.28
13	3	3	2	2	333.84
14	3	4	1	4	322.71
15	3	5	5	1	338.33
16	4	1	3	4	322.80
17	4	2	2	1	336.47
18	4	3	1	3	326.45
19	4	4	5	5	328.29
20	4	5	4	2	328.84
21	5	1	2	5	321.61
22	5	2	1	2	325.27
23	5	3	5	4	326.28
24	5	4	4	1	335.78
25	5	5	3	3	328.85

The bold value means the best result.

For parameter setting in the GA and HDPSO, we use the same method. Parameters in the GA are adopted as $popsize = 140$ , $pr o_{c} = 0.9$ , and $pr o_{m} = 0.3$ . In the HDPSO, there are 10 parameters, that is, swarm size (pop), inertia weight (ω), learning factor (c), initial temperature (T₀), final temperature (T_end), annealing rate (B), maximal and minimal self-adaption probabilities $p f_{\max}$ and $p f_{\min}$ , and probability parameters $p l_{1}$ and $p l_{2}$ . The best parameter setting is recommended as $pop = 140$ , $ω = 0.2$ , $c = 0.8$ , $T_{0} = 2$ , $T_{end} = 0.2$ , $B = 0.7$ , $p f_{\max} = 0.7$ , $p f_{m i n} = 0.1, p l_{1} = 0.4$ and $p l_{2} = 0.5$ .

Performance evaluation metric

The performance of each algorithm is measured by the relative percentage deviation (RPD),⁴³ which is calculated by the formula

RPD (%) = \frac{A_{sol} - Best}{Best} \times 100

(15)

where $A_{sol}$ is the objective function value (in this article, it refers to the makespan) obtained by the given algorithm, and $Best$ represents the best value among the objective function values obtained by all algorithms involved in the contrast experiment.

Main results and discussion

In this subsection, we present a comparative evaluation of the GA-VNS, GA, and HDPSO. For a fair comparison, encoding mechanism, population initialization, and genetic operators in the GA are completely the same as that in GA-VNS, the only difference is no VNS in the GA. The HDPSO in Zhang et al.⁴⁰ is originally developed for solving the dual-resource constrained job shop scheduling problem, most of its operations are able to be used in solving the DRCFJSP-LE. Because they did not consider the flexibility of machines, some improvements are needed to upgrade the HDPSO so that the HDPSO will not produce illegal solutions. In order to obtain reliable results and avoid the randomness, each algorithm is run 30 times for each instance. Set maximum iterations $Gen = 100$ as the termination condition; the comparative results are shown in Table 6, $RP D_{B}$ , $RP D_{A}$ , and $RP D_{W}$ denote the best, average, and worst variance of $RPD$ in 30 runs, respectively. Furthermore, to verify whether there is a significant difference between the algorithms, the non-parametric Kruskal–Wallis test (K-W test) is adopted. In addition, the average runtime is also included in the table.

Table 6.

Comparisons with same iterations (Gen = 100).

Instance	Best	GA-VNS				GA				HDPSO				K-W test
		$RP D_{B}$	$RP D_{A}$	$RP D_{W}$	Time (s)	$RP D_{B}$	$RP D_{A}$	$RP D_{W}$	Time (s)	$RP D_{B}$	$RP D_{A}$	$RP D_{W}$	Time (s)	GA-VNS versus GA	GA-VNS versus HDPSO
01a	2298.58	0.00	2.94	5.00	8.8	4.43	8.10	12.55	2.1	3.94	7.57	9.53	12.1	Y	Y
02a	2095.1	0.00	3.79	6.87	7.1	7.86	12.45	16.73	1.7	6.11	8.95	11.50	10.0	Y	Y
03a	2113.53	0.00	2.64	6.68	9.1	2.41	6.58	10.79	2.1	7.65	9.53	12.05	12.4	Y	Y
04a	1913.9	0.00	3.49	6.47	7.7	3.76	6.12	8.96	1.8	3.12	5.67	7.67	10.6	Y	Y
05a	2455.86	0.00	3.06	5.89	9.3	6.82	12.19	21.87	2.1	3.96	8.35	10.50	12.5	Y	Y
06a	2250.05	0.00	5.15	8.95	9.1	7.80	12.74	17.09	2.1	8.00	10.87	13.43	12.5	Y	Y
07a	2430	0.00	3.49	8.73	15.4	8.16	13.68	20.21	3.5	7.74	10.06	12.12	19.5	Y	Y
08a	2550.54	0.00	3.15	6.47	15.9	1.93	7.64	11.39	3.7	2.89	5.85	7.73	19.8	Y	Y
09a	2270.03	0.00	8.70	14.79	13.9	8.86	14.32	20.29	3.3	9.87	12.34	15.13	18.4	Y	Y
10a	2377.46	0.00	2.36	4.90	15.9	2.87	6.59	11.60	3.9	2.07	5.28	9.82	20.4	Y	Y
11a	2201.71	0.00	5.74	9.04	13.9	5.95	9.25	11.53	3.5	4.62	7.64	10.18	19.1	Y	Y
12a	2097.98	0.00	4.73	9.83	13.6	12.50	17.97	23.56	3.4	8.13	10.54	13.47	18.6	Y	Y
13a	3258.04	0.00	13.72	21.65	28.6	15.86	18.02	22.62	7.1	6.82	11.58	13.86	34.3	Y	N
14a	3032.04	0.00	4.60	14.59	27.6	10.97	15.45	21.20	6.9	5.61	9.97	11.82	33.9	Y	Y
15a	3016.27	0.00	3.11	8.44	26.4	10.98	17.55	28.44	6.5	6.75	10.72	13.79	33.3	Y	Y
16a	3113.58	0.00	2.53	6.74	27.6	4.38	10.43	14.54	6.7	7.91	10.94	13.12	33.5	Y	Y
17a	3042.39	0.00	4.90	9.14	29.3	4.51	10.91	16.28	7.1	3.06	6.31	9.21	33.9	Y	Y
18a	2937.43	0.00	2.02	5.21	27.5	7.51	14.38	20.32	6.7	9.33	12.08	14.59	33.1	Y	Y
mk01	33.96	0.00	5.37	9.95	1.7	0.27	9.78	22.82	0.4	0.94	9.78	16.61	2.9	Y	Y
mk02	28.48	0.00	8.01	16.40	1.8	5.79	13.24	25.28	0.4	1.40	10.00	14.61	3.0	Y	Y
mk03	130.92	0.00	10.50	17.38	5.3	2.32	10.61	25.82	1.3	4.68	9.80	14.18	7.8	Y	N
mk04	77.79	0.00	6.49	13.11	3.7	4.61	11.29	18.20	0.9	4.50	7.48	11.81	5.3	Y	Y
mk05	159.6	1.02	2.90	5.96	3.9	7.70	11.28	15.00	0.9	0.00	8.92	13.85	5.9	Y	Y
mk06	67.38	0.01	4.48	10.26	5.3	2.63	8.22	14.92	1.3	0.00	4.43	8.12	7.9	Y	N
mk07	150.02	0.00	5.38	11.77	3.3	6.23	13.83	20.96	0.7	3.31	6.57	9.55	4.8	Y	Y
mk08	347.85	0.00	2.54	6.13	10.9	2.41	5.68	8.92	2.7	3.79	6.07	8.79	14.8	Y	Y
mk09	308.99	0.00	4.01	7.31	11.4	8.85	15.59	21.12	2.8	6.84	9.07	11.36	15.3	Y	Y
mk10	212.76	0.19	3.60	6.75	11.3	1.43	5.41	11.62	2.7	0.00	3.46	6.11	15.0	Y	N
mk11	645.99	0.00	3.31	5.89	7.7	7.60	12.70	17.87	1.8	10.10	12.78	15.34	10.6	Y	Y
mk12	525.67	0.00	6.70	9.83	9.1	8.26	13.80	17.50	2.2	4.39	8.38	17.00	12.7	Y	Y
mk13	463.73	0.00	4.08	8.09	11.0	10.05	15.73	20.76	2.6	13.68	16.92	20.15	15.2	Y	Y
mk14	424.09	0.00	3.76	7.03	13.1	1.33	3.88	8.80	3.3	0.92	4.94	6.78	18.6	Y	Y
mk15	433.64	0.00	4.32	10.13	12.4	5.75	12.82	20.60	3.0	0.00	6.06	9.62	17.1	Y	Y
Average		0.04	4.71	9.25	12.68	6.15	11.46	17.58	3.07	4.91	8.75	11.92	16.51

GA-VNS: genetic algorithm variable neighborhood search; HDPSO: hybrid discrete particle swarm optimization; K-W test: Kruskal–Wallis test; RPD: relative percentage deviation.

“Y” means that the first algorithm is significantly better than the second one.

From Table 6, it is easy to see that GA-VNS achieves better $RP D_{B}$ , $RP D_{A}$ , and $RP D_{W}$ on most of the instances, which means that GA-VNS has a stronger ability to obtain the better solutions compared to the GA and HDPSO. However, the defect of GA-VNS is that its runtime is longer than GA; this is reasonable because the GA-VNS performs more search operations than GA in same iterations.

To make a fairer comparison, we also test the performance of three algorithms with the same runtime. We set the runtime that used by HDPSO in Table 6 as the termination condition for each instance, the comparative results are presented in Table 7. In Table 7, GA-VNS obtains the smallest $RP D_{B}$ and $RP D_{A}$ on all instances and obtains the smallest $RP D_{W}$ on most of the instances; it shows that GA-VNS outperforms GA and HDPSO on all instances. GA-VNS performs better than GA, which implies that the improved VNS is useful to enhance the local search ability. To determine whether the differences are indeed statistically significant from a global point of view, the one-way analysis of variance (ANOVA) is adopted. The results are given in Table 8, and they indicate statistically significant differences in all metrics.

Table 7.

Comparisons with same runtime.

Instance	Best	GA-VNS			GA			HDPSO			K-W test
		$RP D_{B}$	$RP D_{A}$	$RP D_{W}$	$RP D_{B}$	$RP D_{A}$	$RP D_{W}$	$RP D_{B}$	$RP D_{A}$	$RP D_{W}$	GA-VNS versus GA	GA-VNS versus HDPSO
01a	2273.06	0.00	1.41	3.66	3.38	6.03	10.62	5.11	8.78	10.76	Y	Y
02a	2076.21	0.00	2.28	6.64	6.01	8.96	14.73	7.08	9.94	12.52	Y	Y
03a	2086.1	0.00	1.51	3.48	2.12	5.27	9.42	9.07	10.97	13.52	Y	Y
04a	1863.46	0.00	2.28	6.88	4.18	6.20	9.25	5.91	8.53	10.58	Y	Y
05a	2325.2	0.00	3.12	7.56	8.37	12.20	24.79	9.81	14.43	16.71	Y	Y
06a	2174.68	0.00	2.76	5.88	6.55	10.33	16.03	11.74	14.71	17.36	Y	Y
07a	2288.41	0.00	4.14	7.77	10.03	14.14	23.78	14.40	16.87	19.05	Y	Y
08a	2350.15	0.00	2.30	5.38	8.61	11.24	17.13	11.67	14.87	16.92	Y	Y
09a	2147.09	0.00	4.33	10.76	11.24	15.23	23.40	16.16	18.77	21.72	Y	Y
10a	2091.66	0.00	3.54	7.63	11.43	13.80	20.02	13.66	16.35	19.24	Y	Y
11a	2133.72	0.00	3.43	5.76	5.95	8.45	11.78	7.95	11.07	13.69	Y	Y
12a	2002.62	0.00	4.82	8.82	10.32	15.40	22.32	13.28	15.80	18.88	Y	Y
13a	3089.94	0.00	3.15	6.35	14.91	16.41	20.62	12.63	17.65	20.05	Y	Y
14a	2827.27	0.00	3.74	9.02	11.57	15.70	22.67	13.26	17.93	19.92	Y	Y
15a	2896.95	0.00	2.90	6.74	9.02	14.11	19.85	11.15	15.28	18.48	Y	Y
16a	2913.19	0.00	4.63	8.36	8.12	12.39	17.98	15.33	18.57	20.90	Y	Y
17a	2862.48	0.00	4.29	10.20	7.50	11.67	18.64	9.54	12.99	16.08	Y	Y
18a	2881.53	0.00	2.28	7.49	7.03	10.70	15.55	11.45	14.25	16.81	Y	Y
mk01	31.99	0.00	8.31	23.94	2.30	11.51	23.61	7.16	11.86	16.72	Y	Y
mk02	26.91	0.00	9.32	21.00	4.97	13.91	24.91	7.32	16.42	21.29	Y	Y
mk03	120.02	0.00	7.56	19.37	6.14	13.82	27.54	14.19	19.77	24.55	Y	Y
mk04	72.15	0.00	3.49	8.34	8.65	13.01	20.56	12.67	15.88	20.55	Y	Y
mk05	155.09	0.00	8.67	13.64	3.63	8.79	14.24	2.91	5.90	9.05	Y	Y
mk06	58.14	0.00	6.64	12.81	12.40	16.72	24.48	15.89	21.02	25.30	Y	Y
mk07	145.29	0.00	6.53	15.08	4.63	11.79	19.59	6.68	10.04	13.11	Y	Y
mk08	315.96	0.00	2.80	5.80	7.55	11.17	15.89	14.27	16.78	19.77	Y	Y
mk09	282.62	0.00	3.97	10.46	14.64	17.74	24.21	16.81	19.24	21.75	Y	Y
mk10	188.18	0.00	4.30	8.55	10.36	13.44	20.72	13.06	16.97	19.97	Y	Y
mk11	660.52	0.00	2.51	6.60	3.16	6.44	10.78	7.68	10.30	12.80	Y	Y
mk12	454.25	0.00	4.95	12.78	16.99	20.49	29.48	20.80	23.47	27.09	Y	Y
mk13	460.63	0.00	3.98	7.66	7.32	10.98	17.49	14.45	17.70	20.96	Y	Y
mk14	388.34	0.00	3.27	6.50	5.66	9.06	13.97	10.22	14.60	16.61	Y	Y
mk15	381.25	0.00	7.39	17.22	14.75	19.87	30.05	13.74	20.63	24.68	Y	Y
Average		0.00	4.26	9.64	8.17	12.33	19.28	11.42	15.10	18.10

GA-VNS: genetic algorithm–variable neighborhood search; HDPSO: hybrid discrete particle swarm optimization; K-W test: Kruskal–Wallis test; RPD: relative percentage deviation.

“Y” means that the first algorithm is significantly better than the second one.

Table 8.

ANOVA analysis results.

	$RP D_{B}$	$RP D_{A}$	$RP D_{W}$
GA-VNS versus GA (p value)	$3.97 \times 10^{- 19}$	$1.10 \times 10^{- 16}$	$1.09 \times 10^{- 10}$
GA-VNS versus HDPSO (p value)	$3.31 \times 10^{- 26}$	$1.67 \times 10^{- 21}$	$1.41 \times 10^{- 10}$

ANOVA: analysis of variance; GA-VNS: genetic algorithm–variable neighborhood search; HDPSO: hybrid discrete particle swarm optimization; RPD: relative percentage deviation.

Conclusion

In this article, DRCFJSP-LE is discussed and an efficient hybrid genetic algorithm is developed to solve this problem. In the proposed algorithm, effective encoding/decoding mechanism and population initial method are designed, special crossover and mutation operators are proposed. In addition, VNS is introduced to overcome GA’s weakness in local search. The experimental results demonstrate that the proposed algorithm has good performance in solving this problem.

As a direction of future study, other objective functions can be considered, such as cost, quality, machine load, and earliness/tardiness. Investigating the studied problem with a combination of learning and forgetting effect could be an interesting research topic. Finally, other types of production environments, such as flow shop scheduling, can be considered.

Footnotes

Handling Editor: Tatsushi Nishi

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 Science and Technology Support Program of Hubei Province in China under Grant no. 2015BAA063 and the Fundamental Research Funds for the Central Universities under Grant no. 2016-YB-020 and 2016III024.

ORCID iD

Rui Wu

References

Brucker

Schlie

. Job-shop scheduling with multi-purpose machines. Computing 1990; 45: 369–375.

Wang

Zhou

et al . An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Tech 2012; 60: 303–315.

Lei

Guo

. Scheduling job shop with lot streaming and transportation through a modified artificial bee colony. Int J Prod Res 2013; 51: 4930–4941.

Pan

Wang

et al . A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation. Omega 2014; 45: 42–56.

Lei

Guo

. An effective neighborhood search for scheduling in dual-resource constrained interval job shop with environmental objective. Int J Prod Econ 2015; 159: 296–303.

Gao

Suganthan

Pan

et al . An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time. Expert Syst Appl 2016; 65: 52–67.

Peng

et al . Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems. Comput Ind Eng 2017; 113: 10–26.

Devassia

Salazar-Aguilar

Boyer

. Flexible job-shop scheduling problem with resource recovery constraints. Int J Prod Res 2018; 56: 3326–3343.

Sun

. A green scheduling algorithm for flexible job shop with energy-saving measures. J Clean Prod 2018; 172: 3249–3264.

10.

Nouiri

Bekrar

Jemai

et al . An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem. J Intell Manuf 2018; 29: 603–615.

11.

Xie

. Recent developments in dual resource constrained (DRC) system research. Eur J Oper Res 2011; 215: 309–318.

12.

Cao

Yang

. An improved genetic algorithm for dual-resource constrained flexible job shop scheduling. In: Proceedings of the international conference on intelligent computation technology & automation, Shenzhen, China, 28–29 March 2011, pp.42–45. New York: IEEE.

13.

Liu

Tao

. Research on bi-objective scheduling of dual-resource constrained flexible job shop. Adv Mater Res 2011; 211–212: 1091–1095.

14.

Zhang

Wang

et al . A multi-objective particle swarm optimization for dual-resource constrained shop scheduling with resource flexibility. In: Proceedings of the 2013 IEEE symposium on computational intelligence for engineering solutions (CIES), Singapore, 16–19 April, pp.29–34. New York: IEEE.

15.

Lei

Guo

. Variable neighbourhood search for dual-resource constrained flexible job shop scheduling. Int J Prod Res 2014; 52: 2519–2529.

16.

Yazdani

Zandieh

Tavakkoli

et al . Two meta-heuristic algorithms for the dual-resource constrained flexible job-shop scheduling problem. Sci Iran 2015; 22–3: 1242–1257.

17.

Zheng

Wang

. A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem. Int J Prod Res 2016; 18: 1–13.

18.

Gao

Pan

. A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem. Inform Sci 2016; 372: 655–676.

19.

Paksi

ABN

Ma’Ruf

. Flexible job-shop scheduling with dual-resource constraints to minimize tardiness using genetic algorithm. Mater Sci Eng 2016; 114: 1–9.

20.

Zhang

Wang

. A hybrid discrete particle swarm optimization for dual-resource constrained job shop scheduling with resource flexibility. J Intell Manuf 2017; 28: 1961–1972.

21.

Holland

. Adaptation in natural and artificial systems. Ann Arbor 1992; 6: 126137.

22.

Goldberg

. Genetic algorithms in search, optimization and machine learning. 1st ed. Boston, MA: Addison-Wesley, 1989.

23.

Cellura

Longo

Marsala

et al . The use of genetic algorithms to solve the allocation problems in the life cycle inventory. In: Cavallaro

(ed.) Assessment and simulation tools for sustainable energy systems, vol. 129. London: Springer, 2013, pp.267–284.

24.

Mohammed

Khanapi

Ghani

et al . A review of genetic algorithm application in examination timetabling problem. J Eng Appl Sci 2017; 12: 5166–5181.

25.

Alshujeary

. A review of genetic algorithm applications in solving vehicle routing problem. J Eng Appl Sci 2017; 12: 4267–4283.

26.

Sabor

Abo-Zahhad

Ahmed

et al . A new energy-efficient adaptive clustering protocol based on genetic algorithm for improving the lifetime and the stable period of wireless sensor networks. Int J Energ Inform Commun 2014; 5: 47–72.

27.

Moon

Lee

Bae

. Genetic algorithms for job shop scheduling problems with alternative routings. Int J Prod Res 2008; 46: 2695–2705.

28.

Liu

Peng

. Improved adaptive genetic algorithms for job shop scheduling problems. Adv Mater Res 2010; 97–101: 2473–2476.

29.

Kacem

. Genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 2008; 35: 3202–3212.

30.

Lei

. A genetic algorithm for flexible job shop scheduling with fuzzy processing time. Int J Prod Res 2010; 48: 2995–3013.

31.

Demir

İşleyen

. An effective genetic algorithm for flexible job-shop scheduling with overlapping in operations. Int J Prod Res 2014; 52: 3905–3921.

32.

Gao

Sun

Gen

. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Oper Res 2008; 35: 2892–2907.

33.

Wang

Ding

. A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 2008; 35: 3202–3212.

34.

Kacem

Hammadi

Borne

. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE T Syst Man Cyb: Part C Appl Rev 2002; 32: 1–13.

35.

Hansen

Mladenovi

Prez

JAM

. Variable neighbourhood search: methods and applications. Annal Oper Res 2010; 175: 367–407.

36.

Wang

Zhang

. Hybrid VNS and memetic algorithm for solving the job shop scheduling problem. In: Proceedings of the IEEE international conference on industrial engineering and engineering management, Changchun, China, 3–5 September, pp.924–927. New York: IEEE.

37.

Sevkli

Aydin

. Variable neighbourhood search for job shop scheduling problems. J Software 2006; 1: 34–39.

38.

Adibi

Zandieh

Amiri

. Multi-objective scheduling of dynamic job shop using variable neighborhood search. Expert Syst Appl 2010; 37: 282–287.

39.

Zandieh

Adibi

. Dynamic job shop scheduling using variable neighbourhood search. Int J Prod Res 2010; 48: 2449–2458.

40.

Zhang

Wang

. A hybrid discrete particle swarm optimization for dual-resource constrained job shop scheduling with resource flexibility. J Intell Manuf 2015; 28: 1–12.

41.

Dauzre-Prs

Paulli

. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annal Oper Res 1997; 70: 281–306.

42.

Brandimarte

. Routing and scheduling in a flexible job shop by tabu search. Annal Oper Res 1993; 41: 157–183.

43.

Naderi

Ruiz

. A scatter search algorithm for the distributed permutation flowshop scheduling problem. Eur J Oper Res 2014; 239: 323–334.

Solving the dual-resource constrained flexible job shop scheduling problem with learning effect by a hybrid genetic algorithm

Abstract

Keywords

Introduction

Problem description and formulation

Proposed GA-VNS for DRCFJSP-LE

Encoding and decoding

Population initialization

Selection

Crossover

Crossover for OSCs

Crossover for MACs

Crossover for WACs

Mutation

Local search by VNS

Workflow of the proposed GA-VNS

Experimental studies and discussion

Testing instances

Parameter setting

Performance evaluation metric

Main results and discussion

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References