# An Improved Immune Genetic Algorithm for Solving the Flexible Job Shop Scheduling Problem with Batch Processing

Authors: Libo Song; Chang Liu; Haibo Shi; Jun Zhu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

This paper presents a mathematical model for the flexible job shop scheduling problem (FJSP) with batch processing for manufacturing enterprises with both the flexible job shop scheduling problem and a batch process (BP) problem in actual production. An improved immune genetic algorithm (IGA) based on greedy thought combined with local scheduling rules is used to solve this scheduling problem. In the flexible job shop part, the greedy optimal solution is obtained through the greedy thought. The concept of cross-entropy is then introduced to improve the standard IGA. Calculating the cross-entropy of the individual and greedy optimal solutions for optimization considerably accelerates the optimization speed of the algorithm and enhances the ability of the algorithm to escape the local optimum. In the batching process, effective batching rules are designed to reduce blockage and improve batching efficiency; thus, the job can quickly and effectively pass the batching process and complete the entire production process. In the algorithm verification stage, standard FJSP datasets are used to simulate and verify the proposed algorithm. Considering the specific FJFP with BP problem, we perform simulation experiments with actual production data of a transformer manufacturer. The results show that the proposed method can effectively solve such problems.


---

## Body

## 1. Introduction

The flexible job shop scheduling problem (FJSP) is an extension of the traditional job shop scheduling problem (JSP) and was first proposed by Brucker and Schlie [1] in 1990. In FJSP, each job operation can be assigned to multiple machines, which may have different processing times; thus, FJSP is a more complicated nondeterministic polynomial-hard problem than JSP. Recently, more methods have been applied to solving the FJSP and its expansion problem. For example, Zhao [2] proposed an improved neighborhood structure hybrid algorithm and achieved good results. Lin et al. [3] proposed a hybrid multiverse optimization to address the fuzzy FJSP. An et al. [4] proposed an improved nondominated sorting biogeography-based optimization to solve the (hybrid) multiobjective FJSP. Li et al. [5] examined the FJSP with transportation resource constraints, which increased the problem complexity and practicability. Cao et al. [6] studied the FJSP with sequencing flexibility. Lei et al. [7] proposed a two-phase metaheuristic for multiobjective FJSP with a total energy consumption threshold. Gao et al. [8] focused on a flexible job shop rescheduling problem (FJRP) for new job insertion and solved the problem using a discrete Jaya algorithm. Gong et al. [9] developed energy- and labor-aware multiobjective flexible job shop scheduling under dynamic electricity pricing. Yang et al. [10] proposed mining dispatching rules from dispatching-related historical data with the characteristics of industrial big data to solve the FJSP. Other extended research issues of the FJSP include distributed FJSP [11], FJSP considering automated guided vehicle planning [12], and FJSP considering machine breakdowns [13–15]. Meanwhile, certain new methods have been applied to solving the FJSP, and examples are distributed particle swarm optimization algorithm [16], two-stage genetic algorithm [17], and state transition algorithm based on the normal cloud model [18–22].Batch scheduling is an optimization problem with a strong application background. Its basic assumption is that the machine can process multiple jobs simultaneously. Jia et al. [23] proposed a two-objective collaborative optimization algorithm based on the ant colony to solve the parallel batch machine scheduling problem. Chi et al. [24] constructed a class of forward-looking batching algorithms for uncertain environments. Wang et al. [25] studied a new type of rolling batch scheduling problem arising in continuous casting and rolling processes. Li et al. [26] investigated the problem of scheduling jobs with unit processing time and nonidentical sizes on single or parallel identical batch machines. Tan et al. [27] addressed the green batch scheduling problem on nonidentical parallel machines with time-of-use electricity prices. Wang et al. [28] studied a new, mixed batch scheduling problem that arises in vacuum heat treatment. Shahvari and Logendran [29] discussed the batch scheduling problem in a hybrid flow shop with a learning effect.In the research of the combination of the FJSP and batch process (BP), Huang et al. [30] studied the batch scheduling algorithm of the flexible flow shop for incompatible job families in a flexible flow shop for mold heat treatment comprising quenching and tempering processes. Zhou [31] studied the scheduling problem of two batch processing machines with different jobs. Zhu et al. [32] used a hybrid algorithm that combines the particle swarm algorithm and Nawaz–Enscore–Ham heuristic algorithm to study the batch scheduling problem of a differential job shop. Yin et al. [33] studied the scheduling problem of a large-scale flexible job shop, adopted the batch scheduling method based on job group to degrade the problem scale, and used the adaptive genetic algorithm to optimize the solution. Currently, only a few studies have investigated the scheduling problem comprising flexible job shop and BP scheduling, which are combined in different ways. Therefore, it is crucial to investigate flexible job shop scheduling and batch scheduling thoroughly.The rest of this paper is organized as follows. Section2 describes the problem and mathematical model of the FJSP with the BP. Section 3 introduces the method to solve the FJSP–BP problem: Section 3.1 describes a proposed improved immune genetic algorithm (IIGA) to solve the FJSP part of the problem, including designing an effective coding method, genetic operators, cross-entropy thought, and greedy optimal solution; Section 3.2 describes the design of effective batching methods and batching rules for the batching process. Section 4 describes the experimental analysis: using the standard FJSP benchmark example to verify the effectiveness of the algorithm and using the actual data of a transformer manufacturing enterprise that conforms to the FJSP–BP problem to verify the effectiveness and feasibility of the algorithm. Section 5 summarizes the study and highlights the scope of future work.


## 2. Problem Description

In this study, we developed the FJSP–BP, which is an extension of the FJSP. The FJSP–BP is widely used in manufacturing enterprises, such as transformer manufacturing, semiconductor production, engine parts manufacturing, and steel production line. In this type of problem, most job operations are flexibly distributed on multiple machines. At the same time, specific operations must be unified in batches through batch processing machines, such as drying ovens and dryers, which is a combination of batch scheduling and FJSP.Figure1 shows the production process of a transformer, which illustrates the FJSP–BP problem. The entire production process is divided into two parts. The first part is the FJSP, where n jobs are assigned to M machines as an FJSP. The operations consist of several sections, such as the core process, coil process, and lead process setting. The second part is batch processing. Here, the jobs pass through the drying oven in batches, which is equivalent to batch scheduling problems with different arrival times. Figure 2 illustrates a simplification of the production process 2.Figure 1
Transformer production flow chart.Figure 2
Schematic of flexible job shop scheduling problem with batch processing.The FJSP–BP can be described as follows:n jobs J1,J2,⋯,Jn must be processed on M+1 machines (M1,M2,⋯,Mm,MB). When the jobs are processed on (M1,M2,⋯,Mm,MB), it is an FJSP, which meets the following conditions: each job contains one or more operations; the sequence of operations is predetermined; each operation can be processed on multiple processing machines; the processing time of the operation varies with the processing machine. All the jobs must pass through the batch machine MB in a batch mode; the batch machine MB has volume or quality constraints; the batch processing times for different jobs are different; the time for the entire batch to pass through the batch machine is the maximum of all the single-batch processing times in the batch. To optimize a certain performance index of the entire system, scheduling was aimed at selecting the appropriate machine for each operation, determining the best processing sequence and start time of each operation on each machine, and determining the batching method when all jobs pass through the batch machine. Therefore, the FJSP–BP includes three subproblems: determining the processing machine of each job (machine selection sub-problem), determining the sequencing of the operations on each machine (operations sequencing sub-problem), and determining the way each job passes through the batch machine (batching problem).In addition, the following constraints must be met during processing.Flexible job shop part:(1)
A machine can only process one job per time(2)
An operation of the job can only be processed by one machine per time(3)
Once each operation of each job starts, the processing cannot be interrupted(4)
Different jobs have the same priority(5)
No sequential constraints exist between the operations of different jobs, and sequential constraints exist between the processes of the same job(6)
All jobs can be processed at zero timeBatch processing part:(1)
The batch machine can only process one batch at a certain time, and the batch cannot be interrupted once it starts processing(2)
The sum of the volume or mass of all jobs in each batch is less than or equal to the volume or mass threshold of the batch machineFor the convenience of subsequent description, the following mathematical symbols are defined, as presented in Table1.Table 1
Mathematical symbols and their definitions.
Mathematics symbolSymbol definition and interpretationnTotal number of jobsmTotal number of machinesΩTotal machine seti,eMachine serial number,i,e=1,2,3,⋯,mj,kJob serial number,j,k=1,2,3,⋯,n。hjTotal number of operations of the jobjlOperation sequence,l=1,2,3,⋯,hjΩjhOptional processing machine set for the operation h of the job jmjhNumber of optional processing machines for the operation h of the jobjOjhOperations h of the jobjMijhOperationsh of the job j is processed on machine ipijhProcessing time of the operations h of the jobj on machine isjhProcessing start time of the operationsh of the job jcjhCompletion time of the operationsh of the job jIA positive number large enoughdjDue date of the jobjCjCompletion time of each jobpjBatch processing time of the jobjsjSize of the jobjrjArrival time of the jobj to the buffer of the batch processing machineCBatch processing machine capacityJbSet of jobs in batchbBSets of all batchesRTbAvailable time of batchb, the maximum arrival time of all jobs in batch bSTbStart time of batchbPTbProcessing time of batchb, the maximum processing time of all jobs in batch bCTbCompletion time of batchbThe mathematical model of the FJSP–BP is expressed as(1)minCmax(2)s.t.sjh+xijh×pijh≤cjh,wherei=1,2,⋯,m,j=1,2,⋯,n,andh=1,2,⋯,hj.(3)cjh≤sjh+1,j=1,2,⋯,n,h=1,2,⋯,hj−1,(4)cjhj≤Cmax,j=1,2,⋯,n,(5)sjh+pijh≤skl+I1−yijhkl,j=0,1,⋯,n,k=1,2,⋯,n,h=1,2,⋯,hj,l=1,2,⋯,hk,i=1,2,⋯,m,(6)cjh≤sjh+1+I1−yikljh+1,j=1,2,⋯,n,k=1,2,⋯,n,h=1,2,⋯,hj−1,l=1,2,⋯,hk,i=1,2,⋯,m,(7)∑i=1mjhxijh=1,h=1,2,⋯,hj,j=1,2,⋯,n,(8)∑j=1n∑h=1hjyijhkl=xikl,i=1,2,⋯,m,k=1,2,⋯,n,l=1,2,⋯,hk,(9)∑k=1n∑l=1hkyijhkl=xijh,i=1,2,⋯,m,j=1,2,⋯,n,h=1,2,⋯,hk,(10)sjh≥0,cjh≥0,j=1,2,⋯,n,h=1,2,⋯,hj,xijh=1,ifoperationOjhselectmachinei0,else,(11)yijhkl=1,ifoperationOijhprecedesOikl0,else,(12)∑b∈Bxjb=1,j=1,2,⋯,n,(13)∑s=1Bybs=1,(14)∑j=1nsjxjb≤C,(15)RTb≥rjxjb,(16)PTb≥pjxjb,(17)STb≥RTb,(18)STb′≥CTb∀b,b′∈B∩∀s≤B,∑i=1sybi≥∑i=1syb′i,(19)CTb=STb+PTb,(20)xjb,ybs∈0,1.Equation (1) is the optimization goal, which is to maximize completion time. Equations (2) and (3) express the sequence constraints of each job. Equation (4) expresses the constraint of the job completion time, where the completion time of each job cannot exceed the total completion time. Equations (5) and (6) indicate that a machine can only process one process per time. Equation (7) represents machine constraints, and an operation can only be processed by one machine per time. Equations (8) and (9) indicate that the operation of each machine can be cyclic. Equation (10) indicates that each parameter must be positive. Equation (12) ensures that each job j can only be arranged in one batch b. Equation (13) ensures that each batch is processed only once on the machine, where s=1,2,⋯,B represents the processing sequence of the batch on the machine. If the processing order of batch b on the machine is s, then ybs=1; otherwise, ybs=0. Equation (14) ensures that the sum of the sizes of the jobs in each batch does not exceed the machine capacity C. Equations (15) and (16) indicate that the available time and processing time of the batch are determined by the maximum arrival and processing times of the jobs in the batch, respectively. Equation (17) indicates that the start time of a batch cannot be earlier than its available time. Equation (18) indicates that batch processing cannot be interrupted, and processing can only begin when a previous batch has been processed. Equation (19) is the expression for calculating batch completion time. Equation (20) indicates that the decision variables xjb and ybs are all 0 or 1 variables [34].Table2 illustrates an example of a 4×5 FJSP problem, which is an example of an FJSP with four jobs, five machines, and 12 total operations. The numbers presented in the table are the processing times of the corresponding machine operation, and “—” indicates that the process cannot be processed on the corresponding machine.Table 2
A4×5 FJSP problem.
JobOperationOptional processing machineM1M2M3M4M5J1O1126535O12—824—J2O2137——6O2246510—O23—711—8J3O31—386—O327829—J4O41—8644O42312—79O43—5610—


## 3. FJSP–BP Solution

To obtain the solution to the FJSP–BP, we solve the flexible job shop part and the batch processing part separately. The IIGA is used to solve the flexible job shop part, and the concepts of greedy thought and cross-entropy thought are introduced. The introduced concepts accelerate the optimization speed and search ability of the algorithm. The batch processing part is equivalent to solving the batch scheduling problem of a single-batch processing machine with different arrival times; the rule-based method is used for batch processing and batch sorting.


### 3.1. Solving the FJSP Part Using an Improved Immune Genetic Algorithm

To obtain the solution to the FJSP part, we propose the IIGA. The performance of the algorithm is improved by the concepts of greedy thought and cross-entropy thought. We design effective encoding and decoding methods and optimize the selection, crossover, mutation, and other operations in the algorithm framework.


#### 3.1.1. Chromosome Coding

The FJSP part includes two subproblems: machine selection and operation sequencing, which are independent of each other. Therefore, we code machine selection and operation sequencing separately. The chromosome is divided into two parts, A/B, representing the machine selection and operation sequencing subproblems, respectively. The length of both parts of the chromosome is equal toT0, which represents the total number of operations.Machine selection subproblem: the length of the machine selection part of the chromosome isT0. Each gene locus is represented by an integer, and the integers are arranged sequentially according to the job and its order. Each integer represents the serial number of the processing machine selected in the current operation. The FJSP example presented in Table 2 illustrates the machine coding method. The encoding result is presented in Table 3.Table 3
FJSP chromosome coding.
(a)Machine selection coding(MS)1324232542J1J2J3J4O11O12O21O22O23O31O32O41O42O43M1M3M2M4M2M3M2M5M4M2(b)Operation sequencing coding(OS)2134421234JO21O11O31O41O42O22O12O23O32O43Operation sequencing subproblem: the chromosome length of the process sequencing part is equal to the total number of processesT0. Each gene is directly coded with a process number, and the order in which the part number appears indicates the process sequence among the job operations; thus, the chromosomes are compiled from left to right. For example, the h-th operation number indicates the h-th operation of job j, and the number of occurrences of the job number is equal to the total number of operations hj of the job.


#### 3.1.2. Chromosome Decoding

The decoding part also comprises the machine selection and operation sequencing decoding.Machine selection decoding: the machine selection part is decoded from left to right and converted into a machine sequence matrixJM and time sequence matrix T. JMj,h represents the machine number of operation Oh of job Jj; JMj,∙ represents the arrangement of the machine numbers processed by all operations of the job Jj in order of priority; and Tj,h represents the processing time of operation Oh of job Jj. JMj,h and Tj,h have a corresponding relationship.
(21)JM=1324232542,T=22710788475.Operation sequencing decoding: the chromosomes of the operation sequencing part are read from left to right, and the processing machine and processing times corresponding to each job process are obtained according to the machine and time sequence matrices corresponding to the machine selection part. Finally, the operation is sorted to obtain the scheduling result.


#### 3.1.3. Chromosome Crossover

Machine selection part: the machine selection part must ensure that the sequence of each gene remains the same, using the uniform crossover.Step 1.
Randomly generate an integerr in the interval [1,T0] to represent the number of gene positions that remain unchanged.Step 2.
Generater unequal integers, which correspond to the specific positions of the r invariant gene positions.Step 3.
According to ther integers generated in Step 2, copy the genes at the corresponding positions in the parent chromosomes P1 and P2 to the offspring chromosomes C1 and C2, maintaining their position and order.Step 4.
Genetically copy the remaining genes ofP1 and P2 to C1 and C2, maintaining their position and order.As Figure3 illustrates and taking Table 2 as an example, P1 and P2 are the two parent chromosomes. Assuming r=3 and the three random numbers of Step 2 are 2, 5, and 7, then the offspring chromosomes C1 and C2 are obtained by the uniform crossover.Figure 3
FJSP chromosome crossover. (a) Machine selection uniform crossing. (b) Operation sequencing precedence preserving order-based crossover crossing.
(a)(b)Operation sequencing part: the operation sequencing part adopts the precedence preserving order-based crossover method, and the operation of multiple jobs in each chromosome can better inherit the excellent characteristics of the parent individual.Step 1.
Randomly divide the job setJ1,J2,⋯,Jn into two job sets, Jobset1 and Jobset2.Step 2.
Copy the processes of the jobs contained in Jobset1/Jobset2 in the parent chromosomesP1 and P2 to C1/C2, maintaining their positions and sequences.Step 3.
Copy the processes of the jobs excluded from Jobset1/Jobset2 inP1 and P2 to C2/C1, and maintain only their order.In Figure3, Jobset1=1,4.


#### 3.1.4. Chromosome Variation

Both the machine selection and operation sequencing parts use the random variation method, and the steps are outlined as follows.Machine selection part:Step 1.
Randomly selectr positions in the variant chromosome.Step 2.
Select each position in turn and randomly replace the machine in each position with one of the machines in the set of optional machines.Operation sequencing part:Randomly selectr genes in the mutant chromosome, maintain the position and order of genes in other positions, and randomly order the selected r genes to replace their original positions and orders.


#### 3.1.5. Greedy Optimal Solution Thought

We improve the IGA and introduce the greedy thought. Before each iteration of the algorithm, a “greedy optimal solution” is obtained through the greedy thought.This greedy optimal solution is not necessarily the global optimal solution, but it is highly similar to the global optimal solution with a high probability. Therefore, the optimization can be accelerated by selecting highly similar individuals to the greedy optimal solution in the IIGA.The greedy optimal solution selection thought is as follows:(1)
When selecting the machine for each job operation, choose the machine with the shortest process time in the optional machine collection(2)
During machine selection, distribute the process evenly to each machine as much as possible(3)
Considering the constraints of the operation sequence, start processing the earlier processes as soon as possibleGreedy optimal solution selection: the steps for selecting the greedy optimal solution forn jobs and m machines are as follows.Step 1.
Set up an integer array with a length equal to the total number of machinesm, followed by the machine serial number M1,M2,⋯,Mm; the array corresponds to the processing time, and each element in the array is initialized to zero.Step 2.
Among the initializedn jobs, randomly select a job Jj1 and set its first operation as Oj11. Select the machine Mm1 with the shortest processing time in the collection of processing machines where the operation Oj11 is located.Assign operationOj11 to machine Mm1 and define the processing time of the corresponding machine. Mm1=Tj11m1.Tj11m1 is the processing time of the job Jj1 on machine Mm1.Step 3.
Randomly selectJj2 from the remaining n–1 jobs and set its first operation as Oj21. Select the machine Mm2 with the shortest processing time in the collection of processing machines where the operation Oj21 is located. (At this time, the processing time of the first operation Oj21 of job Jj2 on machine Mm1 should be Tj21m1=Tj21m1+Mm1.) Update Mm1=Tj21m1. If the time is unchanged, the machine with a small number of assigned operations is preferred.Step 4.
By analogy, complete the machine allocation problem of the first operation of all jobs.Step 5.
Repeat Steps 2–4 to complete the machine allocation problem of all operations of all jobs.Step 6.
Get the greedy optimal solutionXbest of the final machine allocation result.The solution process is illustrated in Figure4.Figure 4
Flow chart description of solving the greedy optimal solution, converted to machine selection coding.


#### 3.1.6. Information Entropy and Cross-Entropy

In the IGA, concepts such as antibody information entropy, antibody similarity, and antibody concentration are introduced. The immune optimization method calculates the affinity between the antibody and antigen as well as the similarity between antibodies. The adoption of a concentration-based selection mechanism not only encourages antibodies with high adaptability but also inhibits antibodies with high concentrations, which reflects the regulatory function of the immune system and can prevent falling into a local optimal solution.We introduce the concept of cross-entropy into the IGA. Cross-entropy is an important concept in Shannon’s information theory, mainly used to measure the difference in information between two probability distributions. Ifpx is the true probability distribution of the data and qx is the probability distribution calculated from the data, then the cross-entropy is defined as
(22)Hp,q=−∑xpxlnqx.Cross-entropy is often used in machine learning. It is hoped that the data distributionqx obtained by the algorithm is as close as possible to the true distribution px of the data. In machine learning, cross-entropy is generally defined as a loss function.In the initial stage of the population, we obtain the greedy optimal solutionXbest through greedy thought. Xbest corresponds to the true distribution px according to the cross-entropy thought, and other ordinary individuals in the population correspond to qx. We expect individuals to be as similar to Xbest as possible. By calculating the cross-entropy, similarity, and other indicators of each individual xi and Xbest, the better individual is selected in the selection process, which speeds up the optimization process of the entire algorithm. The calculation method of cross-entropy is illustrated in Table 4 and by Equations (23) and (24).
(23)qkx=ThenumberofXbest_kinthek‐thgeneThenumberofthek‐thgene,(24)pkx=ThenumberofXbest_kinthek‐thgeneNumberofoptionalmachinesforthek‐thgene.Table 4
Cross-entropy calculation explanation.
Xbest3412523413X14412523413X23212523413HXbest,X1=−∑k=110pkxlnqkx=−15•ln12+0+⋯_0HXbest,X2=−∑k=110pkxlnqkx=−0+13•ln12+0+⋯_0Cross-entropy similarity definition:(25)AXbest,Xi=11+HXbest,Xi.The greater the value of the cross-entropy similarity is, the higher the similarity between this individual and the greedy optimal solution.


#### 3.1.7. Algorithm Steps of the IIGA to Solve the FJSP Part

The IIGA framework is outlined as follows.Algorithm 1: IIGA framework.
1: Randomly generate initial populationsP0 and Q0; the population size is N; set t=0.2: Combine the parent and offspring populations, namely,Rt=Pt∪Qt.3: ObtainXbest through the greedy thought and then calculate the fitness value of the 2N individuals in Rt and the cross-entropy value and similarity with Xbest, respectively.4: ArrangeF2N and H2N according to their values and take the largest of the first N phases as FN and HN.5: LetTE=FN∩HN6: DefinePt+1=TE+Xbest+FN−TEτ∙N−1−E+HN−TE1−τ∙N−1−E; update population Pt+17: Perform a crossover operation on the populationPt+1.8: Perform a mutation operation on the populationPt+1 to generate a new population Qt+1.9: Ift<maxgen, then t=t+1; return to Step 2; otherwise, the algorithm terminates.The flow chart of the IIGA is shown in Figure5.Figure 5
Flow chart of IIGA for solving the FJSP part.


### 3.2. Batch Process Part

For each solution in the flexible job shop part, all the jobs will arrive sequentially in the buffer in front of the batch machine with different arrival times. For the batch machine, this is equivalent to the batch processing of problems with different arrival times [35].Batch rules: BF (best fit) rules:(1)
Given a sequence of jobs, a solution for the flexible job shop part is calculated by calculating the arrival time of all the jobs in the front buffer of the batch machine. Sort the jobs according to the arrival time from smallest to largest(2)
Select the first jobJ1 in the sequence as the first job of batch b1. Then, check whether the second job can be added to the batch b1; if it can be added, add job J2 to batch b1; otherwise, create a batch b2 with job J2 as the first job(3)
Then check whether the jobJ3 can be added to batches b1 and b2 in sequence. If it is possible, add the job to the batch; if not, create a new batch b3(4)
When the capacity of a certain batch reaches the maximum value, no other job can be added. For jobJi, find the batch bk that can accommodate the modified job and the earliest arrival time among all unfinished batches; then, add job Ji to the batch. Otherwise, create a new batch bl and add the job to the new batch(5)
By analogy, repeat the above steps until all the jobs are finished in batchesWhen multiple formed batches wait in the buffer, the batch sorting problem is involved.Batch sorting rules: ERT–LPT (earliest release time–longest processing time):(1)
Calculate the arrival and processing times of all batches. The arrival time of the batch is the arrival time of the latest job in the batch, and the processing time of the batch is the maximum processing time of the job in the batch(2)
Arrange the batches in the order of arrival time. If there are multiple batches with the same arrival time, they are further arranged in the order of the batch processing time(3)
Select the machine that is currently idle and arrange the first batch in the batch sequence for processing on this machine(4)
Repeat Step (3) until every batch scheduling is completed; finally, calculate the makespan


## 3.1. Solving the FJSP Part Using an Improved Immune Genetic Algorithm

To obtain the solution to the FJSP part, we propose the IIGA. The performance of the algorithm is improved by the concepts of greedy thought and cross-entropy thought. We design effective encoding and decoding methods and optimize the selection, crossover, mutation, and other operations in the algorithm framework.


### 3.1.1. Chromosome Coding

The FJSP part includes two subproblems: machine selection and operation sequencing, which are independent of each other. Therefore, we code machine selection and operation sequencing separately. The chromosome is divided into two parts, A/B, representing the machine selection and operation sequencing subproblems, respectively. The length of both parts of the chromosome is equal toT0, which represents the total number of operations.Machine selection subproblem: the length of the machine selection part of the chromosome isT0. Each gene locus is represented by an integer, and the integers are arranged sequentially according to the job and its order. Each integer represents the serial number of the processing machine selected in the current operation. The FJSP example presented in Table 2 illustrates the machine coding method. The encoding result is presented in Table 3.Table 3
FJSP chromosome coding.
(a)Machine selection coding(MS)1324232542J1J2J3J4O11O12O21O22O23O31O32O41O42O43M1M3M2M4M2M3M2M5M4M2(b)Operation sequencing coding(OS)2134421234JO21O11O31O41O42O22O12O23O32O43Operation sequencing subproblem: the chromosome length of the process sequencing part is equal to the total number of processesT0. Each gene is directly coded with a process number, and the order in which the part number appears indicates the process sequence among the job operations; thus, the chromosomes are compiled from left to right. For example, the h-th operation number indicates the h-th operation of job j, and the number of occurrences of the job number is equal to the total number of operations hj of the job.


### 3.1.2. Chromosome Decoding

The decoding part also comprises the machine selection and operation sequencing decoding.Machine selection decoding: the machine selection part is decoded from left to right and converted into a machine sequence matrixJM and time sequence matrix T. JMj,h represents the machine number of operation Oh of job Jj; JMj,∙ represents the arrangement of the machine numbers processed by all operations of the job Jj in order of priority; and Tj,h represents the processing time of operation Oh of job Jj. JMj,h and Tj,h have a corresponding relationship.
(21)JM=1324232542,T=22710788475.Operation sequencing decoding: the chromosomes of the operation sequencing part are read from left to right, and the processing machine and processing times corresponding to each job process are obtained according to the machine and time sequence matrices corresponding to the machine selection part. Finally, the operation is sorted to obtain the scheduling result.


### 3.1.3. Chromosome Crossover

Machine selection part: the machine selection part must ensure that the sequence of each gene remains the same, using the uniform crossover.Step 1.
Randomly generate an integerr in the interval [1,T0] to represent the number of gene positions that remain unchanged.Step 2.
Generater unequal integers, which correspond to the specific positions of the r invariant gene positions.Step 3.
According to ther integers generated in Step 2, copy the genes at the corresponding positions in the parent chromosomes P1 and P2 to the offspring chromosomes C1 and C2, maintaining their position and order.Step 4.
Genetically copy the remaining genes ofP1 and P2 to C1 and C2, maintaining their position and order.As Figure3 illustrates and taking Table 2 as an example, P1 and P2 are the two parent chromosomes. Assuming r=3 and the three random numbers of Step 2 are 2, 5, and 7, then the offspring chromosomes C1 and C2 are obtained by the uniform crossover.Figure 3
FJSP chromosome crossover. (a) Machine selection uniform crossing. (b) Operation sequencing precedence preserving order-based crossover crossing.
(a)(b)Operation sequencing part: the operation sequencing part adopts the precedence preserving order-based crossover method, and the operation of multiple jobs in each chromosome can better inherit the excellent characteristics of the parent individual.Step 1.
Randomly divide the job setJ1,J2,⋯,Jn into two job sets, Jobset1 and Jobset2.Step 2.
Copy the processes of the jobs contained in Jobset1/Jobset2 in the parent chromosomesP1 and P2 to C1/C2, maintaining their positions and sequences.Step 3.
Copy the processes of the jobs excluded from Jobset1/Jobset2 inP1 and P2 to C2/C1, and maintain only their order.In Figure3, Jobset1=1,4.


### 3.1.4. Chromosome Variation

Both the machine selection and operation sequencing parts use the random variation method, and the steps are outlined as follows.Machine selection part:Step 1.
Randomly selectr positions in the variant chromosome.Step 2.
Select each position in turn and randomly replace the machine in each position with one of the machines in the set of optional machines.Operation sequencing part:Randomly selectr genes in the mutant chromosome, maintain the position and order of genes in other positions, and randomly order the selected r genes to replace their original positions and orders.


### 3.1.5. Greedy Optimal Solution Thought

We improve the IGA and introduce the greedy thought. Before each iteration of the algorithm, a “greedy optimal solution” is obtained through the greedy thought.This greedy optimal solution is not necessarily the global optimal solution, but it is highly similar to the global optimal solution with a high probability. Therefore, the optimization can be accelerated by selecting highly similar individuals to the greedy optimal solution in the IIGA.The greedy optimal solution selection thought is as follows:(1)
When selecting the machine for each job operation, choose the machine with the shortest process time in the optional machine collection(2)
During machine selection, distribute the process evenly to each machine as much as possible(3)
Considering the constraints of the operation sequence, start processing the earlier processes as soon as possibleGreedy optimal solution selection: the steps for selecting the greedy optimal solution forn jobs and m machines are as follows.Step 1.
Set up an integer array with a length equal to the total number of machinesm, followed by the machine serial number M1,M2,⋯,Mm; the array corresponds to the processing time, and each element in the array is initialized to zero.Step 2.
Among the initializedn jobs, randomly select a job Jj1 and set its first operation as Oj11. Select the machine Mm1 with the shortest processing time in the collection of processing machines where the operation Oj11 is located.Assign operationOj11 to machine Mm1 and define the processing time of the corresponding machine. Mm1=Tj11m1.Tj11m1 is the processing time of the job Jj1 on machine Mm1.Step 3.
Randomly selectJj2 from the remaining n–1 jobs and set its first operation as Oj21. Select the machine Mm2 with the shortest processing time in the collection of processing machines where the operation Oj21 is located. (At this time, the processing time of the first operation Oj21 of job Jj2 on machine Mm1 should be Tj21m1=Tj21m1+Mm1.) Update Mm1=Tj21m1. If the time is unchanged, the machine with a small number of assigned operations is preferred.Step 4.
By analogy, complete the machine allocation problem of the first operation of all jobs.Step 5.
Repeat Steps 2–4 to complete the machine allocation problem of all operations of all jobs.Step 6.
Get the greedy optimal solutionXbest of the final machine allocation result.The solution process is illustrated in Figure4.Figure 4
Flow chart description of solving the greedy optimal solution, converted to machine selection coding.


### 3.1.6. Information Entropy and Cross-Entropy

In the IGA, concepts such as antibody information entropy, antibody similarity, and antibody concentration are introduced. The immune optimization method calculates the affinity between the antibody and antigen as well as the similarity between antibodies. The adoption of a concentration-based selection mechanism not only encourages antibodies with high adaptability but also inhibits antibodies with high concentrations, which reflects the regulatory function of the immune system and can prevent falling into a local optimal solution.We introduce the concept of cross-entropy into the IGA. Cross-entropy is an important concept in Shannon’s information theory, mainly used to measure the difference in information between two probability distributions. Ifpx is the true probability distribution of the data and qx is the probability distribution calculated from the data, then the cross-entropy is defined as
(22)Hp,q=−∑xpxlnqx.Cross-entropy is often used in machine learning. It is hoped that the data distributionqx obtained by the algorithm is as close as possible to the true distribution px of the data. In machine learning, cross-entropy is generally defined as a loss function.In the initial stage of the population, we obtain the greedy optimal solutionXbest through greedy thought. Xbest corresponds to the true distribution px according to the cross-entropy thought, and other ordinary individuals in the population correspond to qx. We expect individuals to be as similar to Xbest as possible. By calculating the cross-entropy, similarity, and other indicators of each individual xi and Xbest, the better individual is selected in the selection process, which speeds up the optimization process of the entire algorithm. The calculation method of cross-entropy is illustrated in Table 4 and by Equations (23) and (24).
(23)qkx=ThenumberofXbest_kinthek‐thgeneThenumberofthek‐thgene,(24)pkx=ThenumberofXbest_kinthek‐thgeneNumberofoptionalmachinesforthek‐thgene.Table 4
Cross-entropy calculation explanation.
Xbest3412523413X14412523413X23212523413HXbest,X1=−∑k=110pkxlnqkx=−15•ln12+0+⋯_0HXbest,X2=−∑k=110pkxlnqkx=−0+13•ln12+0+⋯_0Cross-entropy similarity definition:(25)AXbest,Xi=11+HXbest,Xi.The greater the value of the cross-entropy similarity is, the higher the similarity between this individual and the greedy optimal solution.


### 3.1.7. Algorithm Steps of the IIGA to Solve the FJSP Part

The IIGA framework is outlined as follows.Algorithm 1: IIGA framework.
1: Randomly generate initial populationsP0 and Q0; the population size is N; set t=0.2: Combine the parent and offspring populations, namely,Rt=Pt∪Qt.3: ObtainXbest through the greedy thought and then calculate the fitness value of the 2N individuals in Rt and the cross-entropy value and similarity with Xbest, respectively.4: ArrangeF2N and H2N according to their values and take the largest of the first N phases as FN and HN.5: LetTE=FN∩HN6: DefinePt+1=TE+Xbest+FN−TEτ∙N−1−E+HN−TE1−τ∙N−1−E; update population Pt+17: Perform a crossover operation on the populationPt+1.8: Perform a mutation operation on the populationPt+1 to generate a new population Qt+1.9: Ift<maxgen, then t=t+1; return to Step 2; otherwise, the algorithm terminates.The flow chart of the IIGA is shown in Figure5.Figure 5
Flow chart of IIGA for solving the FJSP part.


## 3.1.1. Chromosome Coding

The FJSP part includes two subproblems: machine selection and operation sequencing, which are independent of each other. Therefore, we code machine selection and operation sequencing separately. The chromosome is divided into two parts, A/B, representing the machine selection and operation sequencing subproblems, respectively. The length of both parts of the chromosome is equal toT0, which represents the total number of operations.Machine selection subproblem: the length of the machine selection part of the chromosome isT0. Each gene locus is represented by an integer, and the integers are arranged sequentially according to the job and its order. Each integer represents the serial number of the processing machine selected in the current operation. The FJSP example presented in Table 2 illustrates the machine coding method. The encoding result is presented in Table 3.Table 3
FJSP chromosome coding.
(a)Machine selection coding(MS)1324232542J1J2J3J4O11O12O21O22O23O31O32O41O42O43M1M3M2M4M2M3M2M5M4M2(b)Operation sequencing coding(OS)2134421234JO21O11O31O41O42O22O12O23O32O43Operation sequencing subproblem: the chromosome length of the process sequencing part is equal to the total number of processesT0. Each gene is directly coded with a process number, and the order in which the part number appears indicates the process sequence among the job operations; thus, the chromosomes are compiled from left to right. For example, the h-th operation number indicates the h-th operation of job j, and the number of occurrences of the job number is equal to the total number of operations hj of the job.


## 3.1.2. Chromosome Decoding

The decoding part also comprises the machine selection and operation sequencing decoding.Machine selection decoding: the machine selection part is decoded from left to right and converted into a machine sequence matrixJM and time sequence matrix T. JMj,h represents the machine number of operation Oh of job Jj; JMj,∙ represents the arrangement of the machine numbers processed by all operations of the job Jj in order of priority; and Tj,h represents the processing time of operation Oh of job Jj. JMj,h and Tj,h have a corresponding relationship.
(21)JM=1324232542,T=22710788475.Operation sequencing decoding: the chromosomes of the operation sequencing part are read from left to right, and the processing machine and processing times corresponding to each job process are obtained according to the machine and time sequence matrices corresponding to the machine selection part. Finally, the operation is sorted to obtain the scheduling result.


## 3.1.3. Chromosome Crossover

Machine selection part: the machine selection part must ensure that the sequence of each gene remains the same, using the uniform crossover.Step 1.
Randomly generate an integerr in the interval [1,T0] to represent the number of gene positions that remain unchanged.Step 2.
Generater unequal integers, which correspond to the specific positions of the r invariant gene positions.Step 3.
According to ther integers generated in Step 2, copy the genes at the corresponding positions in the parent chromosomes P1 and P2 to the offspring chromosomes C1 and C2, maintaining their position and order.Step 4.
Genetically copy the remaining genes ofP1 and P2 to C1 and C2, maintaining their position and order.As Figure3 illustrates and taking Table 2 as an example, P1 and P2 are the two parent chromosomes. Assuming r=3 and the three random numbers of Step 2 are 2, 5, and 7, then the offspring chromosomes C1 and C2 are obtained by the uniform crossover.Figure 3
FJSP chromosome crossover. (a) Machine selection uniform crossing. (b) Operation sequencing precedence preserving order-based crossover crossing.
(a)(b)Operation sequencing part: the operation sequencing part adopts the precedence preserving order-based crossover method, and the operation of multiple jobs in each chromosome can better inherit the excellent characteristics of the parent individual.Step 1.
Randomly divide the job setJ1,J2,⋯,Jn into two job sets, Jobset1 and Jobset2.Step 2.
Copy the processes of the jobs contained in Jobset1/Jobset2 in the parent chromosomesP1 and P2 to C1/C2, maintaining their positions and sequences.Step 3.
Copy the processes of the jobs excluded from Jobset1/Jobset2 inP1 and P2 to C2/C1, and maintain only their order.In Figure3, Jobset1=1,4.


## 3.1.4. Chromosome Variation

Both the machine selection and operation sequencing parts use the random variation method, and the steps are outlined as follows.Machine selection part:Step 1.
Randomly selectr positions in the variant chromosome.Step 2.
Select each position in turn and randomly replace the machine in each position with one of the machines in the set of optional machines.Operation sequencing part:Randomly selectr genes in the mutant chromosome, maintain the position and order of genes in other positions, and randomly order the selected r genes to replace their original positions and orders.


## 3.1.5. Greedy Optimal Solution Thought

We improve the IGA and introduce the greedy thought. Before each iteration of the algorithm, a “greedy optimal solution” is obtained through the greedy thought.This greedy optimal solution is not necessarily the global optimal solution, but it is highly similar to the global optimal solution with a high probability. Therefore, the optimization can be accelerated by selecting highly similar individuals to the greedy optimal solution in the IIGA.The greedy optimal solution selection thought is as follows:(1)
When selecting the machine for each job operation, choose the machine with the shortest process time in the optional machine collection(2)
During machine selection, distribute the process evenly to each machine as much as possible(3)
Considering the constraints of the operation sequence, start processing the earlier processes as soon as possibleGreedy optimal solution selection: the steps for selecting the greedy optimal solution forn jobs and m machines are as follows.Step 1.
Set up an integer array with a length equal to the total number of machinesm, followed by the machine serial number M1,M2,⋯,Mm; the array corresponds to the processing time, and each element in the array is initialized to zero.Step 2.
Among the initializedn jobs, randomly select a job Jj1 and set its first operation as Oj11. Select the machine Mm1 with the shortest processing time in the collection of processing machines where the operation Oj11 is located.Assign operationOj11 to machine Mm1 and define the processing time of the corresponding machine. Mm1=Tj11m1.Tj11m1 is the processing time of the job Jj1 on machine Mm1.Step 3.
Randomly selectJj2 from the remaining n–1 jobs and set its first operation as Oj21. Select the machine Mm2 with the shortest processing time in the collection of processing machines where the operation Oj21 is located. (At this time, the processing time of the first operation Oj21 of job Jj2 on machine Mm1 should be Tj21m1=Tj21m1+Mm1.) Update Mm1=Tj21m1. If the time is unchanged, the machine with a small number of assigned operations is preferred.Step 4.
By analogy, complete the machine allocation problem of the first operation of all jobs.Step 5.
Repeat Steps 2–4 to complete the machine allocation problem of all operations of all jobs.Step 6.
Get the greedy optimal solutionXbest of the final machine allocation result.The solution process is illustrated in Figure4.Figure 4
Flow chart description of solving the greedy optimal solution, converted to machine selection coding.


## 3.1.6. Information Entropy and Cross-Entropy

In the IGA, concepts such as antibody information entropy, antibody similarity, and antibody concentration are introduced. The immune optimization method calculates the affinity between the antibody and antigen as well as the similarity between antibodies. The adoption of a concentration-based selection mechanism not only encourages antibodies with high adaptability but also inhibits antibodies with high concentrations, which reflects the regulatory function of the immune system and can prevent falling into a local optimal solution.We introduce the concept of cross-entropy into the IGA. Cross-entropy is an important concept in Shannon’s information theory, mainly used to measure the difference in information between two probability distributions. Ifpx is the true probability distribution of the data and qx is the probability distribution calculated from the data, then the cross-entropy is defined as
(22)Hp,q=−∑xpxlnqx.Cross-entropy is often used in machine learning. It is hoped that the data distributionqx obtained by the algorithm is as close as possible to the true distribution px of the data. In machine learning, cross-entropy is generally defined as a loss function.In the initial stage of the population, we obtain the greedy optimal solutionXbest through greedy thought. Xbest corresponds to the true distribution px according to the cross-entropy thought, and other ordinary individuals in the population correspond to qx. We expect individuals to be as similar to Xbest as possible. By calculating the cross-entropy, similarity, and other indicators of each individual xi and Xbest, the better individual is selected in the selection process, which speeds up the optimization process of the entire algorithm. The calculation method of cross-entropy is illustrated in Table 4 and by Equations (23) and (24).
(23)qkx=ThenumberofXbest_kinthek‐thgeneThenumberofthek‐thgene,(24)pkx=ThenumberofXbest_kinthek‐thgeneNumberofoptionalmachinesforthek‐thgene.Table 4
Cross-entropy calculation explanation.
Xbest3412523413X14412523413X23212523413HXbest,X1=−∑k=110pkxlnqkx=−15•ln12+0+⋯_0HXbest,X2=−∑k=110pkxlnqkx=−0+13•ln12+0+⋯_0Cross-entropy similarity definition:(25)AXbest,Xi=11+HXbest,Xi.The greater the value of the cross-entropy similarity is, the higher the similarity between this individual and the greedy optimal solution.


## 3.1.7. Algorithm Steps of the IIGA to Solve the FJSP Part

The IIGA framework is outlined as follows.Algorithm 1: IIGA framework.
1: Randomly generate initial populationsP0 and Q0; the population size is N; set t=0.2: Combine the parent and offspring populations, namely,Rt=Pt∪Qt.3: ObtainXbest through the greedy thought and then calculate the fitness value of the 2N individuals in Rt and the cross-entropy value and similarity with Xbest, respectively.4: ArrangeF2N and H2N according to their values and take the largest of the first N phases as FN and HN.5: LetTE=FN∩HN6: DefinePt+1=TE+Xbest+FN−TEτ∙N−1−E+HN−TE1−τ∙N−1−E; update population Pt+17: Perform a crossover operation on the populationPt+1.8: Perform a mutation operation on the populationPt+1 to generate a new population Qt+1.9: Ift<maxgen, then t=t+1; return to Step 2; otherwise, the algorithm terminates.The flow chart of the IIGA is shown in Figure5.Figure 5
Flow chart of IIGA for solving the FJSP part.


## 3.2. Batch Process Part

For each solution in the flexible job shop part, all the jobs will arrive sequentially in the buffer in front of the batch machine with different arrival times. For the batch machine, this is equivalent to the batch processing of problems with different arrival times [35].Batch rules: BF (best fit) rules:(1)
Given a sequence of jobs, a solution for the flexible job shop part is calculated by calculating the arrival time of all the jobs in the front buffer of the batch machine. Sort the jobs according to the arrival time from smallest to largest(2)
Select the first jobJ1 in the sequence as the first job of batch b1. Then, check whether the second job can be added to the batch b1; if it can be added, add job J2 to batch b1; otherwise, create a batch b2 with job J2 as the first job(3)
Then check whether the jobJ3 can be added to batches b1 and b2 in sequence. If it is possible, add the job to the batch; if not, create a new batch b3(4)
When the capacity of a certain batch reaches the maximum value, no other job can be added. For jobJi, find the batch bk that can accommodate the modified job and the earliest arrival time among all unfinished batches; then, add job Ji to the batch. Otherwise, create a new batch bl and add the job to the new batch(5)
By analogy, repeat the above steps until all the jobs are finished in batchesWhen multiple formed batches wait in the buffer, the batch sorting problem is involved.Batch sorting rules: ERT–LPT (earliest release time–longest processing time):(1)
Calculate the arrival and processing times of all batches. The arrival time of the batch is the arrival time of the latest job in the batch, and the processing time of the batch is the maximum processing time of the job in the batch(2)
Arrange the batches in the order of arrival time. If there are multiple batches with the same arrival time, they are further arranged in the order of the batch processing time(3)
Select the machine that is currently idle and arrange the first batch in the batch sequence for processing on this machine(4)
Repeat Step (3) until every batch scheduling is completed; finally, calculate the makespan


## 4. Experimental Results and Analysis

For the IIGA verification in this study, we used MATLAB 2014 run on an environment with an Intel Core I5 fourth-generation CPU (3.20 GHz main frequency), 8 GB memory, and Windows 7 operating system (64-bit, professional edition). The experiments were divided into two parts. In the first part, to verify the effectiveness of the IIGA, we used a standard FJSP example to compare the performance of different algorithms. In the second part, we focused on the FJSP–BP. Taking the actual data of a transformer manufacturing enterprise as an example, we solved the FJSP–BP by the IIGA and used batching rules to verify the feasibility and effectiveness of the algorithm.


### 4.1. Algorithm Parameter Setting

The IIGA used in this study had three parameters at the algorithmic level: crossover probabilityPc, mutation probability Pm, and selection parameter τ in the selection process.Determining and optimizing parameters is extremely complicated, thereby requiring continuous simulation experiments. For the crossover probabilityPc and mutation probability Pm under the genetic algorithm framework, the crossover probability Pc was set to (0.6, 0.9), while the mutation probability Pm ranged between (0.005, 0.02). These values were based on previous experiments. In the following examples, the operating parameters of the crossover probability Pc and mutation probability Pm were set to 0.75 and 0.01, respectively. For the selection parameter τ introduced by the improved algorithm in this study, we used the MK01 example to test the selection of τ.The MK01 example is one of the ten classic FJSP test problems designed by Brandimarte. The problem contains ten jobs, six machines, and 55 operations. We considered different settings ofτ to determine the influence of the parameter on the performance of the algorithm. The population size and the maximum number of iterations were both 100, and the algorithm ran 20 times continuously. The experimental results are illustrated in Figure 6.Figure 6
Optimization ofτ. (a) Relationship between the optimal solution times and τ. (b) Relationship between the average optimal solution and τ. (c) Relationship between the average iterations when converging to the optimal solution and τ.
(a)(b)(c)Figure6 shows that when τ is relatively small, the part selected by cross-entropy in the selection process is larger, the average number of iterations when the algorithm converges is small, and the algorithm converges quickly, but the number of optimal solutions and the average optimal solution are inferior. When τ is relatively large, the selection process based on fitness is larger, the average number of iterations when the algorithm converges is large, the algorithm convergence speed is low, and the number of optimal solutions and the average optimal solution effect are moderate. When the value of τ is in the range of (0.4, 0.6), the algorithm considers both the convergence speed and optimal solution quality. Although the convergence speed is moderate, the number of optimal solutions and the average optimal solution effect are both good. Therefore, in the following experiment, the value of τ was set to 0.5.


### 4.2. Standard FJSP Example to Verify the Effectiveness of the IIGA

To verify the improvement effect of the improved algorithm, we used 27 sets of FJSP standard case data to test and analyze the IIGA. The genetic algorithm, IGA, and the emerging group intelligence algorithm JAYA were used for comparison. The 27 sets of data used include the following:(1)
Five groups of Kacem calculation examples. The Kacem calculation example is the earliest standard FJSP calculation example. The five questions are combined from the number of jobs from 4 to 15 and the number of machines from 5 to 15(2)
Ten sets of BRdata calculation examples. The BRdata calculation example is one of the classic standard FJSP calculation examples proposed by Brandimarte. The ten questions are combined from the number of jobs from 10 to 20 and the number of machines from 4 to 15. The process of each group of questions ranges from 5 to 15, and the average number of processing machines for each process in each group of questions ranges from 1.43 to 4.10(3)
Twelve groups of BCdata calculation examples. The BCdata example is a 21-example problem proposed by Barnes and Chambers. The 21 calculation examples are mainly constructed from the three most challenging problems in the classic JSP (mt10, la24, and la40) according to certain principles. The average number of processing machines in each process of the BCdata calculation example is relatively small, and its data type and flexibility are similar to those in the flexible job shop part of the transformer production line. Therefore, 12 of 21 groups of BCdata calculation examples were selected for algorithm verificationEach algorithm ran 30 times on each group of data, the initial population of the four algorithms was 100, and the maximum evolutionary number was 200 generations.n×m represents the problem scale; LB and UB represent the lower and upper bounds of the optimal solution, respectively; CM is the minimum value of the maximum completion time; and AVCM represents the average optimal value obtained by running the algorithm 30 times continuously. The test results are presented in Tables 5 and 6.Table 5
Kacem and BR problem test results.
Problemn×mLB,UBGAIGAJAYAIIGACMAVCMCMAVCMCMAVCMCMAVCMKacem14×511,∗1111.5111111111111Kacem28×814,∗2324.61516.21414.61414.3Kacem310×711,∗1921.61414.811121111.6Kacem410×107,∗1316.488.377.877.5Kacem515×1511,∗2731.51718.41414.71112.1Mk0110×636,424041.5404040404040Mk0210×624,322929.1262626262626Mk0315×8204,211204204204204204204204204Mk0415×848,816747.34606060606060Mk0515×4168,186176178.1173176.8173174.4172175.2Mk0610×1533,866768.825860.55860.55758Mk0720×5133,157147152.9144146.3144148.5139140.2Mk0820×10523523523.34523523523523523523Mk0920×10299,369320327.74311311307309307310.8Mk1020×15165,296229235.72201203.6197200.2196198.6Table 6
Twelve BCdata problem test results.
Problemn×mLB,UBGAIGAJAYAIIGACMAVCMCMAVCMCMAVCMCMAVCMmt10c110×11655,927928928.2927927.2927927.4927927mt10cc10×12655,914910912.4910911.7908908.8908908mt10x10×11655,929918919.6918918918918918918mt10xx10×12655,936918918.6918918918918918918setb4c915×11857,924919920.4919919.2914914.6914914.2setb4cc15×12857,909909915.0909911.6907910.0907908.5setb4x15×11846,937925934.3925926.8925925925925setb4xx15×12847,930925933.7925925.4925925925925seti5c1215×161027,118511741184.711741176.011741174.211701171seti5cc15×17955,113611361146.511361137.211361136.411351135.8seti5x15×16955,121812091213.212001209.012011203.611981199.4seti5xx15×17955,120412041205.911991200.611981202.411971198.3Table5 shows that for the Kacem and BR examples, IGA has a similar optimization effect to that of JAYA, but JAYA is slightly better. The average completion time of the two algorithms is relatively small, while their optimization effect is rather better. Compared with IGA and JAYA, both CM and AVCM of the GA are larger, and the optimization effect is relatively poor. In terms of AVCM, IIGA is slightly worse than JAYA in the MK05 and MK09 instances but better than JAYA in the seven instances of kacem2-kacem5, MK06, MK07, and MK10; the AVCM of the two algorithms is the same in the other six instances. Therefore, the performance of the two algorithms is similar in terms of AVCM. IIGA is slightly better than JAYA but far better than the other two algorithms. In terms of CM, IIGA has the best value on five instances of kacem5, MK05, MK06, MK07, and MK10; in the remaining ten instances, the best value of CM is parallel to other three algorithms. Thus, IIGA is significantly better than the other three algorithms in terms of CM.For BCdata, in terms of the optimization effect, IIGA has a significant improvement compared with the other three algorithms. In terms of the average optimization effect, the optimization effect of IIGA is also significantly better than that of GA, IGA, and JAYA.During testing, we found that when four algorithms used data for 30 simulation experiments, theCM obtained each time had obvious volatility. Because the algorithm easily falls into local extreme values, its CM may even have large abnormal values. To better compare and evaluate the optimization effects of the four algorithms, we selected the MK06 group of data as an example and drew the CM obtained by running the four algorithms 30 times into a box plot, as shown in Figure 7.Figure 7
Box plot of the four algorithms.The box plot is a statistical graph used to show the degree of dispersion in a set of data. The stability of the optimization effect can be reflected through the box plot. The interquartile range (IQR) is used in the box plot to measure the degree of dispersion in the data.Figure7 shows that in the 30 runs of the algorithm, IGA had the widest solution range fluctuation, indicating that it is easier for the algorithm to fall into the local extreme value because of the immune mechanism. The position of the box plot generated by IIGA is the lowest, indicating that the overall quality of the solution generated by the algorithm is better than that of the other three algorithms. Moreover, the IQR of the box plot generated by IIGA is smaller than that of the other three algorithms, showing that the degree of dispersion of the solution produced by the algorithm is smaller than that of the other three algorithms. Its stability is also the best among the four algorithms.We plotted the relationship between the maximum completion time and the number of iterations of the four algorithms under the MK06 data, as shown in Figure8.Figure 8
Iteration graph of the four algorithms.Figure8 shows that IIGA has the fastest convergence speed and the smallest optimal solution, and it converges to the optimal solution in the shortest time: Cmax of 57 after about 60 iterations. The final convergence value of GA is 67, and the performance is the worst. The optimal values of IGA and JAYA are both 58, but the optimization speed of IGA is faster. Analyzing the search mechanism of the two algorithms shows that JAYA uses the optimal individual Xbest and worst individual Xworst in the search process for optimization according to the iterative formula, and it only selects individuals according to the fitness function value, making the algorithm easy to fall into a local optimum. Meanwhile, IGA calculates the similarity between antibodies and antibodies in addition to the affinity between antibodies and antigens in the optimization process, and the algorithm adopts a concentration-based selection mechanism, which encourages the adaptation of antibodies with a high degree of concentration to inhibit antibodies with a high concentration. The algorithm reflects the regulation function of the immune system, which can escape the local optimal solution and accelerate the convergence speed. The selection mechanism and results of the convergence speed of both algorithms are different.Figure9 shows the Gantt chart of IIGA under the MK06 example.Figure 9
MK06 optimal solution Gantt chart.


### 4.3. Transformer Manufacturer Data

We considered the data from an actual transformer manufacturing enterprise as an example. The production workshop of the transformer manufacturer includes several sections, including the coil process, iron core, and lead process setting sections, as the FJSP part; the transformer body drying process section is the BP part.The FJSP part contains multiple machines and equipment, and the drying oven is batched with job volume as a constraint. We simplified the FJSP part into a total of 20 machines. In the BP part, the selected jobs are divided into two categories. Similar jobs have the same volume, and the FJSP part has different processing times; the job volume differs by category, and the batch processing times differ. The batch processing part normalizes the volume, and the batch machine has a capacity of 12; the volumes of the two job types are three and four, respectively.Among the two job types, the job of class A is a laminated core transformer, while the job of class B is an amorphous alloy transformer. Table7 presents basic information about the two job types.Table 7
Basic information on two job types.
Job categoryNumber of operationsNumber of machinesJob volumeBatch machine volumeBatch processing timeCategory A11+120+131210Category B11+1412Both types of jobs in the FJSP part have 11 operations. Compared with class A jobs, class B jobs require two press-fitting and drying operations, and class B jobs have no insertion operation. In the actual production process, the iron core and coil operations of class A products are produced in parallel, and the iron core of class B products is purchased out. In this study, we investigated the coil process, body equipment, and drying process sections. The iron core part was set as a prefabricated part, and unified installation was performed in the coil assembly operation. The detailed processing information of the two job types is shown in Table8.Table 8
Detailed processing information on two job types.
Category ACategory BOperation numberOperation nameOptional machine setsProcessing timeOperation numberOperation nameOptional machine setsProcessing time1Low voltage winding1-35-71Low voltage winding1-36-82High voltage winding4-76-92Pressing and drying8-93-53Pressing and drying8-94-53High voltage winding4-77-104Remove the mold10-112-34Pressing and drying8-93-45Turn measurement and brush glue10-117-85Remove the mold10-112-36Inspection12-133-46Turn measurement and brush glue10-118-107Coil assembly14-208-107Inspection12-133-48Insert silicon steel sheet14-206-88Coil assembly14-207-99Body assembly14-204-69Body assembly14-204-610Lead assembly14-203-510Lead assembly14-202-511Inspection12-133-411Inspection12-133-412Drying211012Drying2112According to the actual production situation of the transformer manufacturer, we use half a month’s production data to verify the effectiveness of the algorithm. The total number of jobs isJ=25, where A =15 and B=10. The Gantt chart of scheduling results is shown in Figure 10.Figure 10
Gantt chart of the transformer production process (J=25).Figure10 shows that the jobs are evenly distributed to each machine, and the completion time is 225. In the actual production process, the completion time is 282. Thus, the completion time is increased by 25.3%, reflecting the effectiveness of the algorithm in this paper.


## 4.1. Algorithm Parameter Setting

The IIGA used in this study had three parameters at the algorithmic level: crossover probabilityPc, mutation probability Pm, and selection parameter τ in the selection process.Determining and optimizing parameters is extremely complicated, thereby requiring continuous simulation experiments. For the crossover probabilityPc and mutation probability Pm under the genetic algorithm framework, the crossover probability Pc was set to (0.6, 0.9), while the mutation probability Pm ranged between (0.005, 0.02). These values were based on previous experiments. In the following examples, the operating parameters of the crossover probability Pc and mutation probability Pm were set to 0.75 and 0.01, respectively. For the selection parameter τ introduced by the improved algorithm in this study, we used the MK01 example to test the selection of τ.The MK01 example is one of the ten classic FJSP test problems designed by Brandimarte. The problem contains ten jobs, six machines, and 55 operations. We considered different settings ofτ to determine the influence of the parameter on the performance of the algorithm. The population size and the maximum number of iterations were both 100, and the algorithm ran 20 times continuously. The experimental results are illustrated in Figure 6.Figure 6
Optimization ofτ. (a) Relationship between the optimal solution times and τ. (b) Relationship between the average optimal solution and τ. (c) Relationship between the average iterations when converging to the optimal solution and τ.
(a)(b)(c)Figure6 shows that when τ is relatively small, the part selected by cross-entropy in the selection process is larger, the average number of iterations when the algorithm converges is small, and the algorithm converges quickly, but the number of optimal solutions and the average optimal solution are inferior. When τ is relatively large, the selection process based on fitness is larger, the average number of iterations when the algorithm converges is large, the algorithm convergence speed is low, and the number of optimal solutions and the average optimal solution effect are moderate. When the value of τ is in the range of (0.4, 0.6), the algorithm considers both the convergence speed and optimal solution quality. Although the convergence speed is moderate, the number of optimal solutions and the average optimal solution effect are both good. Therefore, in the following experiment, the value of τ was set to 0.5.


## 4.2. Standard FJSP Example to Verify the Effectiveness of the IIGA

To verify the improvement effect of the improved algorithm, we used 27 sets of FJSP standard case data to test and analyze the IIGA. The genetic algorithm, IGA, and the emerging group intelligence algorithm JAYA were used for comparison. The 27 sets of data used include the following:(1)
Five groups of Kacem calculation examples. The Kacem calculation example is the earliest standard FJSP calculation example. The five questions are combined from the number of jobs from 4 to 15 and the number of machines from 5 to 15(2)
Ten sets of BRdata calculation examples. The BRdata calculation example is one of the classic standard FJSP calculation examples proposed by Brandimarte. The ten questions are combined from the number of jobs from 10 to 20 and the number of machines from 4 to 15. The process of each group of questions ranges from 5 to 15, and the average number of processing machines for each process in each group of questions ranges from 1.43 to 4.10(3)
Twelve groups of BCdata calculation examples. The BCdata example is a 21-example problem proposed by Barnes and Chambers. The 21 calculation examples are mainly constructed from the three most challenging problems in the classic JSP (mt10, la24, and la40) according to certain principles. The average number of processing machines in each process of the BCdata calculation example is relatively small, and its data type and flexibility are similar to those in the flexible job shop part of the transformer production line. Therefore, 12 of 21 groups of BCdata calculation examples were selected for algorithm verificationEach algorithm ran 30 times on each group of data, the initial population of the four algorithms was 100, and the maximum evolutionary number was 200 generations.n×m represents the problem scale; LB and UB represent the lower and upper bounds of the optimal solution, respectively; CM is the minimum value of the maximum completion time; and AVCM represents the average optimal value obtained by running the algorithm 30 times continuously. The test results are presented in Tables 5 and 6.Table 5
Kacem and BR problem test results.
Problemn×mLB,UBGAIGAJAYAIIGACMAVCMCMAVCMCMAVCMCMAVCMKacem14×511,∗1111.5111111111111Kacem28×814,∗2324.61516.21414.61414.3Kacem310×711,∗1921.61414.811121111.6Kacem410×107,∗1316.488.377.877.5Kacem515×1511,∗2731.51718.41414.71112.1Mk0110×636,424041.5404040404040Mk0210×624,322929.1262626262626Mk0315×8204,211204204204204204204204204Mk0415×848,816747.34606060606060Mk0515×4168,186176178.1173176.8173174.4172175.2Mk0610×1533,866768.825860.55860.55758Mk0720×5133,157147152.9144146.3144148.5139140.2Mk0820×10523523523.34523523523523523523Mk0920×10299,369320327.74311311307309307310.8Mk1020×15165,296229235.72201203.6197200.2196198.6Table 6
Twelve BCdata problem test results.
Problemn×mLB,UBGAIGAJAYAIIGACMAVCMCMAVCMCMAVCMCMAVCMmt10c110×11655,927928928.2927927.2927927.4927927mt10cc10×12655,914910912.4910911.7908908.8908908mt10x10×11655,929918919.6918918918918918918mt10xx10×12655,936918918.6918918918918918918setb4c915×11857,924919920.4919919.2914914.6914914.2setb4cc15×12857,909909915.0909911.6907910.0907908.5setb4x15×11846,937925934.3925926.8925925925925setb4xx15×12847,930925933.7925925.4925925925925seti5c1215×161027,118511741184.711741176.011741174.211701171seti5cc15×17955,113611361146.511361137.211361136.411351135.8seti5x15×16955,121812091213.212001209.012011203.611981199.4seti5xx15×17955,120412041205.911991200.611981202.411971198.3Table5 shows that for the Kacem and BR examples, IGA has a similar optimization effect to that of JAYA, but JAYA is slightly better. The average completion time of the two algorithms is relatively small, while their optimization effect is rather better. Compared with IGA and JAYA, both CM and AVCM of the GA are larger, and the optimization effect is relatively poor. In terms of AVCM, IIGA is slightly worse than JAYA in the MK05 and MK09 instances but better than JAYA in the seven instances of kacem2-kacem5, MK06, MK07, and MK10; the AVCM of the two algorithms is the same in the other six instances. Therefore, the performance of the two algorithms is similar in terms of AVCM. IIGA is slightly better than JAYA but far better than the other two algorithms. In terms of CM, IIGA has the best value on five instances of kacem5, MK05, MK06, MK07, and MK10; in the remaining ten instances, the best value of CM is parallel to other three algorithms. Thus, IIGA is significantly better than the other three algorithms in terms of CM.For BCdata, in terms of the optimization effect, IIGA has a significant improvement compared with the other three algorithms. In terms of the average optimization effect, the optimization effect of IIGA is also significantly better than that of GA, IGA, and JAYA.During testing, we found that when four algorithms used data for 30 simulation experiments, theCM obtained each time had obvious volatility. Because the algorithm easily falls into local extreme values, its CM may even have large abnormal values. To better compare and evaluate the optimization effects of the four algorithms, we selected the MK06 group of data as an example and drew the CM obtained by running the four algorithms 30 times into a box plot, as shown in Figure 7.Figure 7
Box plot of the four algorithms.The box plot is a statistical graph used to show the degree of dispersion in a set of data. The stability of the optimization effect can be reflected through the box plot. The interquartile range (IQR) is used in the box plot to measure the degree of dispersion in the data.Figure7 shows that in the 30 runs of the algorithm, IGA had the widest solution range fluctuation, indicating that it is easier for the algorithm to fall into the local extreme value because of the immune mechanism. The position of the box plot generated by IIGA is the lowest, indicating that the overall quality of the solution generated by the algorithm is better than that of the other three algorithms. Moreover, the IQR of the box plot generated by IIGA is smaller than that of the other three algorithms, showing that the degree of dispersion of the solution produced by the algorithm is smaller than that of the other three algorithms. Its stability is also the best among the four algorithms.We plotted the relationship between the maximum completion time and the number of iterations of the four algorithms under the MK06 data, as shown in Figure8.Figure 8
Iteration graph of the four algorithms.Figure8 shows that IIGA has the fastest convergence speed and the smallest optimal solution, and it converges to the optimal solution in the shortest time: Cmax of 57 after about 60 iterations. The final convergence value of GA is 67, and the performance is the worst. The optimal values of IGA and JAYA are both 58, but the optimization speed of IGA is faster. Analyzing the search mechanism of the two algorithms shows that JAYA uses the optimal individual Xbest and worst individual Xworst in the search process for optimization according to the iterative formula, and it only selects individuals according to the fitness function value, making the algorithm easy to fall into a local optimum. Meanwhile, IGA calculates the similarity between antibodies and antibodies in addition to the affinity between antibodies and antigens in the optimization process, and the algorithm adopts a concentration-based selection mechanism, which encourages the adaptation of antibodies with a high degree of concentration to inhibit antibodies with a high concentration. The algorithm reflects the regulation function of the immune system, which can escape the local optimal solution and accelerate the convergence speed. The selection mechanism and results of the convergence speed of both algorithms are different.Figure9 shows the Gantt chart of IIGA under the MK06 example.Figure 9
MK06 optimal solution Gantt chart.


## 4.3. Transformer Manufacturer Data

We considered the data from an actual transformer manufacturing enterprise as an example. The production workshop of the transformer manufacturer includes several sections, including the coil process, iron core, and lead process setting sections, as the FJSP part; the transformer body drying process section is the BP part.The FJSP part contains multiple machines and equipment, and the drying oven is batched with job volume as a constraint. We simplified the FJSP part into a total of 20 machines. In the BP part, the selected jobs are divided into two categories. Similar jobs have the same volume, and the FJSP part has different processing times; the job volume differs by category, and the batch processing times differ. The batch processing part normalizes the volume, and the batch machine has a capacity of 12; the volumes of the two job types are three and four, respectively.Among the two job types, the job of class A is a laminated core transformer, while the job of class B is an amorphous alloy transformer. Table7 presents basic information about the two job types.Table 7
Basic information on two job types.
Job categoryNumber of operationsNumber of machinesJob volumeBatch machine volumeBatch processing timeCategory A11+120+131210Category B11+1412Both types of jobs in the FJSP part have 11 operations. Compared with class A jobs, class B jobs require two press-fitting and drying operations, and class B jobs have no insertion operation. In the actual production process, the iron core and coil operations of class A products are produced in parallel, and the iron core of class B products is purchased out. In this study, we investigated the coil process, body equipment, and drying process sections. The iron core part was set as a prefabricated part, and unified installation was performed in the coil assembly operation. The detailed processing information of the two job types is shown in Table8.Table 8
Detailed processing information on two job types.
Category ACategory BOperation numberOperation nameOptional machine setsProcessing timeOperation numberOperation nameOptional machine setsProcessing time1Low voltage winding1-35-71Low voltage winding1-36-82High voltage winding4-76-92Pressing and drying8-93-53Pressing and drying8-94-53High voltage winding4-77-104Remove the mold10-112-34Pressing and drying8-93-45Turn measurement and brush glue10-117-85Remove the mold10-112-36Inspection12-133-46Turn measurement and brush glue10-118-107Coil assembly14-208-107Inspection12-133-48Insert silicon steel sheet14-206-88Coil assembly14-207-99Body assembly14-204-69Body assembly14-204-610Lead assembly14-203-510Lead assembly14-202-511Inspection12-133-411Inspection12-133-412Drying211012Drying2112According to the actual production situation of the transformer manufacturer, we use half a month’s production data to verify the effectiveness of the algorithm. The total number of jobs isJ=25, where A =15 and B=10. The Gantt chart of scheduling results is shown in Figure 10.Figure 10
Gantt chart of the transformer production process (J=25).Figure10 shows that the jobs are evenly distributed to each machine, and the completion time is 225. In the actual production process, the completion time is 282. Thus, the completion time is increased by 25.3%, reflecting the effectiveness of the algorithm in this paper.


## 5. Conclusion

In this study, a combination of intelligent methods and scheduling rules is used to solve the FJSP–BP problem. An improved IGA based on the concept of greed and cross-entropy is proposed, and an effective batching method and batching rules are designed. The standard FJSP benchmark example and data conforming to the FJSP-PB problem from a transformer manufacturing enterprise were used to verify the effectiveness and practicability of the proposed algorithm. This work provides a significant reference for solving the FJSP–BP problem.From a scheduling problem perspective, we only investigated the single-batch machine problem under small-scale data. In future research, we will thoroughly study the FJSP with parallel batch machines under medium- and large-scale data. As the problem is more complicated, the selection of batch machines must be considered based on MS and OS. Meanwhile, analysis and research will be conducted for different optimization objectives, including machine load, equipment energy consumption, and early/delay penalty. In addition, in terms of research methods, it is necessary to determine a global optimization algorithm that considers both the FJSP and BP parts as well as a multiobjective optimization algorithm that includes multiple optimization objectives.



---

*Source: 2856056-2022-06-26.xml*