# Hybrid Algorithm Based on Genetic Simulated Annealing Algorithm for Complex Multiproduct Scheduling Problem with Zero-Wait Constraint

Authors: Zhongyuan Liang; Mei Liu; Peisi Zhong; Chao Zhang; Xiao Wang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Aiming at the complex multiproduct scheduling problem with 0-wait constraint, a hybrid algorithm based on genetic algorithm (GA) and simulated annealing (SA) algorithm was studied. Based on the results of pruning and grading to the operation tree of complex multiproduct, the design structure matrix (DSM) with precedence constraints was established. Then, an initial population coding method based on DSM was proposed and three strategies to optimize the initial population were proposed to improve the quality of the initial population for the situation of multiple operations in the same grade which need to be processed on the same machine. The specific process flow and the setting method of related parameters for the hybrid algorithm were given out. For the infeasible solution produced in the crossover operation, the repair method was proposed. In the decoding process with makespan as the optimization objective, the chromosome genes were classified and the decoding for complex multiproduct scheduling problem with 0-wait constraint was realized through the analysis of its characteristics. The effectiveness of the proposed algorithm for complex multiproduct scheduling problem with 0-wait constraint is verified by the test of related examples in the existing literature.


---

## Body

## 1. Introduction

Shop scheduling is the core of production management system and one of the most difficult problems in theoretical research. It is committed to providing a profit-maximizing production planning scheme with a series of production constraints and resource constraints to guide the production work in the workshop. The quality of the scheduling plan directly affects the enterprise whether on-time delivery, equipment utilization, inventory control, and other economic indicators. Therefore, manufacturing enterprises need excellent workshop scheduling technology and methods in order to better manage production and win benefits for enterprises. The traditional workshop scheduling problem is mainly to schedule the products which are independent of each other and do not have the sequential constraint relation in the processing stage. Such as flow shop, job shop, and flexible job shop. Johnson [1] was the first to study the flow-shop scheduling problem for sequential processing of two machines. Researchers from all over the world have conducted in-depth research on this issue, and most of them adopted general optimization methods such as mathematics and operations research. Bansal [2] used a modified branch and bound technique to solve the scheduling of n jobs over m machines when the objective is to minimize the sum of completion times of all jobs on the last machine. Ying [3] developed a new mixed integer linear programming (MILP) model and a two-phase enumeration algorithm to improve the best so far exact methods for solving this problem with the objective of minimizing the makespan. Ozolins [4] proposed a new exact algorithm based on the dynamic programming (DP) to solve the no-wait job-shop scheduling problem (NWJSP) with a makespan objective.But it becomes infeasible due to the time consuming as the scale of scheduling problem becomes larger and it was proved to be an NP-hard problem by Bansal [2]. All kinds of intelligent algorithms have been developed and applied to shop scheduling problem, and the great potential of these algorithms has been shown gradually. For various scales’ scheduling problems, the metaheuristic algorithm attracted extensive attention from scholars at home and abroad. Wu [5] proposed the hybrid ant colony algorithm based on the 3D disjunctive graph model by combining the elitist ant system, max–min ant system, and the staged parameter control mechanism and optimized the flexible job-shop scheduling problem (FJSP) to minimize the longest completion time. Wei [6] proposed a hybrid genetic simulated annealing (SA) algorithm for flow-shop scheduling problems. Shi [7] proposed a hybrid solving method that combines improved extended shifting bottleneck procedure and genetic algorithm (GA) for the assembly job-shop scheduling problem (JSP). Nagano [8] addressed the m-machine no-wait flow-shop scheduling problem with the objective of minimizing makespan subject to an upper bound on total completion time and proposed an iterated greedy with local search algorithm. Mudjihartono [9] proposed a GA-PSO algorithm, which implements it in both parallel and nonparallel modes, and compared to original GA, the GA-PSO gives a 4.58% better solution on average. Liu [10] proposed a multiobjective optimization model aimed at minimizing carbon footprints of all products and makespan and designed a hybrid fruit fly optimization algorithm to solve the proposed model. Ali [11] proposed a new SA algorithm utilizing block insertion and block exchange operators and established a dominance rule to the no-wait flow-shop scheduling problem on m machines with separate setup times. Zhang [12] integrated three metaheuristics algorithms, Shuffled Frog Leaping Algorithm (SFLA), Intelligent Water Drops (IWD) algorithm, and Path Relinking (PR) algorithm, which were put together to solve JSP. Nouiri [13] proposed a two-stage particle swarm optimization (2S-PSO) to solve the FJSP under machine breakdowns with the lowest makespan obtained and also robust and stable schedules. Wu [14] proposed a similarity-based scheduling algorithm for setup time reduction (SSA4STR) and then an improved nondominated sorting GA II (NSGA-II) to optimize the dual-resource-constrained FJSP when loading and unloading time (DRFJSP-LU) of the fixtures are considered. Huang [15] proposed a new and concise Four-Tuple Scheme (FTS) for modelling a job with operation and processing flexibility and an enhanced GA through a more efficient encoding strategy. Yüksel [16] proposed a novel multiobjective discrete artificial bee colony algorithm (MO-DABC), a traditional multiobjective genetic algorithm (MO-GA), and a variant of multiobjective GA with a local search (MO-GALS) for the biobjective no-wait permutation flow-shop scheduling problem. Wu [17] considered an energy-efficient biobjective no-wait permutation flow-shop scheduling problem in the presence of dynamic speed-scaling technique to minimize makespan and total energy consumption through the proposed AM-VNS works by operating some local search on the solutions in WS and updating the corresponding AS iteratively. Wang [18] proposed a particle swarm optimization (PSO) algorithm with improvements to solve the issue of how to reschedule the randomly arrived new jobs to pursue both performance and stability in a job shop.However, the researchers mainly focus on traditional shop scheduling, flow-shop scheduling, flexible job-shop scheduling, and shop scheduling with some added environment variables. The no-wait constraint is common in flow-shop scheduling problems. Dong [19] introduced the no-wait two-stage flow-shop scheduling problem with the first stage machine having multitask flexibility motivated by a real-world scenario in hospitals. Xu [20] proposed a metaheuristic, self-adaptive memetic algorithm (SAMA for short) for no-wait flow shop with variable processing times and used the evolutionary operators to adaptively control the balance between intensification and diversification of the algorithm. Ying [21] presented a multistart SA with bidirectional shift timetabling (MSA-BST) algorithm for solving the NWJSP. Deng [22] proposed the population-based iterated greedy (PBIG) algorithm for the sequencing subproblem by adopting favourable features of the iterated greedy algorithm and formulated the no-wait job-shop problem with a total flow time criterion based on time difference and decomposes the problem into timetabling and sequencing subproblems.Although some research work has been done on NWJSP in theory and practice and some useful research results have been obtained, the research work and results mainly focus on the single mass production, and rarely involve the mixed form of multiple variety scheduling, while the multiproduct scheduling problem mainly solves the production scheduling of small batch products, as well as the cooperation between the parts of the relationship between fabrication and assembly. Shi [7] proposed a hybrid solving method that combines improved extended shifting bottleneck procedure and GA for the assembly JSP. Lei [23] proposed a novel encoding method based on the dynamic operation relationship matrix table and solved the integrated scheduling problem with processing and assembly by GA. And he [24] also used the method mentioned above to solve the no-wait problem proposed by Xie [25–28]. Zhao [29] proposed a novel division coding strategy that ensured all initial feasible solutions were designed based on the rank of virtual components, which reflected the sequence constraints of parts processing and assembly.We summarized the research of the existing papers in Table1 (the interpretation of acronyms was shown in Table 2). To sum up, the solution method of JSP is a continuous development process. The general direction is to develop from enumeration method to metaheuristic method with the enlargement of problem scale. The application of metaheuristic algorithm not only is shown in solving the workshop scheduling problem but also shows obvious advantages in the path planning problems such as UAV and robot [31, 32]. The workshop scheduling problem also develops from the flow shop at the beginning to the flexible workshop and the workshop scheduling under the constraint conditions. The maximum completion time is still the first optimization objective; of course, there are carbon emissions, machine load, and another multiobjective optimization. The scheduling problem of single small-batch products, as well as the coordination and cooperation relationship between parts and components with high constraint requirements, is a common scheduling problem in small- and medium-sized enterprises. For this kind of problem, the standard metaheuristic algorithm only provides a solution framework, and its specific implementation scheme needs to be greatly adapted. This paper addressed the problem of minimizing makespan on complex multiproduct scheduling problem with 0-wait constraint. To minimize the makespan, a hybrid algorithm based on GA and SA algorithm was adopted. In order to adapt to the complex multiproduct scheduling problem, a coding method based on design structure matrix (DSM) was proposed, which solved the sequence constraints and 0-wait constraints between products. According to the different operations types represented by chromosome, the decoding scheme was given. Through three initialization strategies, the initial population quality was improved effectively. Finally, two complex multiproduct scheduling problems with 0-wait constraints were solved by using a global search of GA and a local search of SA algorithm.Table 1
Classification and summarizing of algorithms solving the product scheduling problem.
DevelopmentPublicationsBackgroundObjectivesAlgorithmsEnumeration methodsJohnson [1]Flow shopMakespanMPBansal [2]Flow shopMakespanBBOzolins [4]No-wait job shopMakespanDPXie [25–28]No-wait integrated scheduling problemMakespanMPMetaheuristic algorithmWu [5]Flexible job shopMakespanACOWei [6]Flow shopMakespanGA-SAMudjihartono [9]Job shopMakespanGA-PSOLiu [10]Flexible job shopCarbon footprint and makespanFOANouiri [13]Flexible job shopMakespanTwo-stage PSOWu [14]Flexible job shopMakespan and total setup timeNSGAIIHuang [15]Flexible job shopMakespanGAWang [18]Dynamic job shopMakespanPSONagano [8]No-wait flow shopMakespanIterated greedy algorithmAli [11]No-wait flow shopTotal tardinessSAYüksel [16]No-wait permutation flow shopTotal tardiness and energy consumptionABC and NSGAIIWu [17]No-wait permutation flow shopMakespan and energy consumptionMultiobjective VNSDong [19]No-wait two-stage flow shopMakespanLinear-time combinatorial algorithmXu [20]No-wait permutation flow shopMakespanSelf-adaptive memetic algorithmYing [3, 21, 30]No-wait job shopMakespanMultistart SADeng [22]No-wait job shopTotal flow timeIterated greedy algorithmShi [7]Assembly job shopMakespanGALei [23]Integrated scheduling problemMakespanGAZhao [29]Integrated scheduling problemMakespanGATable 2AcronymsFull termMPMathematical programmingBBBranch and bound techniqueDPDynamic programmingACOAnt colony optimizationGAGenetic algorithmSASimulated annealingPSOParticle swarm optimizationFOAFruit fly optimization algorithmNSGAIIFast nondominated sorting genetic algorithmABCArtificial bee colonyVNSVariable neighborhood searchEDAEstimation of distribution algorithmThe remaining organisational structure of this paper is as follows. InSection 2, the problem description for complex multiproduct scheduling problem with 0-wait constraint is given. In Section 3, the implementation of the HGSA is described, including the initial population coding based on DSM and optimization strategies to improve initial population quality, selection, crossover, mutation operator, and decoding algorithm. In Section 4, the specific examples given in the relevant literature are tested and relevant comparative analyses are reported. Finally, the conclusions of this paper and future research work are given.


## 2. Problem Description

The research on the traditional JSP solves the scheduling problem of pure processing after decomposing the product into unconstrained jobs, which is more suitable for large quantities of the same product. Complex product problem deals with the process scheduling problem of complex products with constraints among the workpiece, which processes the processing and assembly of complex products together. Generally speaking, in order to simplify the complex product scheduling problem, the processing and assembly procedures are unified into operations, and the processing and assembly equipment or stations are unified into machines. Complex multiproduct scheduling problem referred to the simultaneous scheduling of multiple varieties of complex products. Given the product setP=P1,P2,…,Pl, the product PiPi∈P,1≤i≤l has operations Oi1,Oi2,…,Oin, and all the operations are processed on machine set M=M1,M2,…,Mm with the following constraints:(1)
Each operationOij can only be processed by one machine Mk at a time and each machine Mk can only process one operation Oij at a time, 1≤j≤n,1≤k≤m.(2)
Once a machine processes an operation, it cannot process other operations until the operation is completed.(3)
Sequence constraints exist among operations and follow the relationship given in the product operation tree, and any operation cannot be interrupted until it is completed, while the processing time of each operation is known in the product operation tree.(4)
All machines are idle at time 0.On the basis of the above description, the complex multiproduct scheduling problem is to reasonably arrange the operation processing sequence on each machine with the completion time of all the products being as small as possible. IfCij indicates the completion time of the operation Oij, so the objective function is(1)minCmax=minmaxilmaxjnCij,subject to(2)Sij≥0,where 1≤i≤l and 1≤j≤n. Sij is the start time of operation Oij.(3)Sij+Pij=Cij,where 1≤i≤l and 1≤j≤n. Pij is the process time of operation Oij and Cij is the completion time of operation Oij.(4)Cij≤Spq,where 1≤i≤l, 1≤j≤n, 1≤p≤l, 1≤q≤n, and Oij is prior to Opq.(5)Pijk+Ppqk≤Cpqk−Sijk,where 1≤i≤l, 1≤j≤n, 1≤p≤l, 1≤q≤n, and 1≤k≤m. Pijk is the process time of operation Oij on machine Mk.Constraints (2)–(4) describe sequential constraints between operations and operations cannot be interrupted. Meanwhile, all time nodes are unique; that is, the same operation can only be processed once by a machine. Constraint (5) is the constraint to machine that each machine can only process one operation at a time.However, there are some other constraints in the production of complex products, such as zero-wait constraint between operations. Zero-wait constraint between operations means that after a certain operation is finished, it must immediately enter the next operation to process; that is, there should be no time gap between operations. The 0-wait constraint can be described in constraint(6)∑j=1hPij=Cih−Sij,where 1≤i≤l, 1≤j≤n, 1≤h≤n, and Oij,...,Oih∈NWt. NWt is a set of operations with the same 0-wait constraints.Figure1 shows the operation tree of products A and B. Each rectangular box represents an operation. The data in the rectangular box represent the product name, operation number, machine number, and processing time in turn, and arrows represent sequential constraints. The dotted box represents the 0-wait constraint, which refers to the completion of the previous operation that must be seamless into the next operation, such as injection molding, steelmaking, and hot assembly.Figure 1
Operation tree of productsA and B.


## 3. Methods

As a typical iterative algorithm, GA and SA algorithm can be used to solve the JSP. GA is based on the mechanism of biological evolution. It starts from the string set of problem solution and has a strong global searching ability. SA algorithm originates from the principle of solid annealing and is a probabilistic-based algorithm. It starts from the current solution that produces a new solution in the solution space and has a strong local searching ability. If the single-threaded search of SA algorithm is changed into multithreaded search, that is to say, add the population iteration idea of GA, then the hybrid algorithm will have the ability of global search and local search. The hybrid genetic SA algorithm uses a large number of samples as a possible solution to the problem rather than a single sample as a possible solution to the problem, which will greatly increase the convergence rate. At the same time, probabilistic acceptance of new solutions can also solve the population diversity and prevent entering local optimal. To sum up, the hybrid algorithm complements the GA and SA algorithm and has more advantages in solution than the single algorithm. For the above analysis of the characteristics of the complex multiproduct 0-wait constraint problem, in this paper, we adopted the hybrid algorithm based on GA and SA algorithm (HGSA) to solve the problem.According to the research of the operation tree, first, we simplify each operation into a virtual workpiece satisfying the sequential constraint relationship, and on this basis, we use DSM to generate the initial population. At the same time, we adopt the proposed three optimization strategies and reverse coding to improve the initial population quality and then enter the solution searching process using HGSA. The flowchart of the algorithm is shown in Figure2.Figure 2
Algorithm flowchart of HGSA.


### 3.1. Initial Population Coding Based on DSM

#### 3.1.1. Pruning Method and Grading

Directed graph is one of the simplest methods to express the process. It mainly consists of the nodes representing tasks or features and the directed edges indicating the transmission of requirement information between the nodes. The operation tree is also representation of a directed graph. Pruning the product operation tree can simplify the model and improve the coding efficiency. Simply put, pruning is the process of integrating the single line operations or 0-wait operations into a virtual workpiece.The steps of pruning method are as follows:Step 1. Calculate the node in-degree in the directed graph corresponding to the product operation tree and mark the nodes with in-degree being 0.Step 2. Starting from a node with in-degree being 0, find the next node along the directed edge until reaching another node with in-degree being bigger than 1 or another node belonging to 0-wait operations. However, the above method is applicable; the starting node does not belong to the 0-wait operations. On the contrary, if the starting node belongs to 0-wait operations, end the searching process after the last 0-wait operations. Then, get a new operation tree.Step 3. Repeat Step 2 to the new operation tree until reaching the last operation in the operation tree.Virtual workpieces are graded based on the completion of pruning, using the method of calculating the task height value in a directed acyclic graph [33]. The grade of a virtual workpiece is defined as(7)gradeJi=0,predJi=ϕ,maxgradepredJi+1,otherwise.gradeJi is the grade of virtual workpiece Ji. predJi is the immediate predecessor virtual workpiece of Ji.The serial numberi of virtual workpiece Ji is defined as follow:Step 1. Calculate the number of virtual workpieces less than each grade.Step 2. In the same grade, number the virtual workpiece as 1 on the far left, then +1 on the second far left, and so on till reaching virtual workpiece on the far right.Step 3. In the same grade, add the number obtained from Step 1 and Step 2, and get the serial number i of current virtual workpiece Ji.Based on the definition above, if the grade number of one virtual workpiece is bigger than another, that means its serial number is bigger.As shown in Figure3, the shadow represents the operation with in-degree of 0, that is, the starting operation. The dotted box represents the 0-wait constraint. We can get the mapping relation such as J1 = {A1, A3}, J4 = {A2, A6}, and J7 = {A8}.Figure 3
Pruning process and grading result.


#### 3.1.2. Coding Based on DSM

The solution of JSP is the sequence of jobs, and the sequence can get the start time and end time of each job on each machine. Based on this, the virtual workpieces can be sorted and solved according to the constraint relationship. Donald Steward [34] introduced structural design matrices (DSM) to analyse information flows in 1981. In this paper, we proposed an initialization population coding method for operations based on DSM, which contains the sequence constraints between virtual workpieces.Figure4 shows the specific principle of DSM. Building the DSM, firstly, the virtual workpieces are arranged in ascending order according to the grade from top to bottom and left to right. In principle, there is no sequence requirement for virtual workpieces in the same grade, but they are generally in ascending order according to the serial number of jobs. In DSM, the row number of the element represents the serial number of the virtual workpiece, and the column number of the element represents the serial number of the virtual workpiece corresponding to the immediate predecessor of the current virtual workpiece. For diagonal elements, if it is a virtual workpiece with 0-wait constraint, put 1 in; else, put the number of operations in this virtual workpiece in. For nondiagonal elements, if it is a virtual workpiece with 0-wait constraint, which means that there will be at least 2 operations in the virtual workpiece, find the serial number of its immediate predecessor, and in this column, put the serial number of the operation in current virtual workpiece in. On the contrary, if it is a virtual workpiece without 0 wait constraint, then the pruning rules determine that only the 1st operation in it has immediate predecessor, and put 1 in. For other elements, put 0 in. To sum up, it can be summarized as(8)DSMi,i=1,Jiis 0−wait virtual workpiece,nJi,Jiis non−0−wait virtual workpiece,(9)DSMi,j=k,Jjis immediate predecessor ofOkinJi,0,otherwise.Figure 4
The DSM of virtual workpieces.Then, get the DSM of the above problem as(10)DSM=aijn×n=2000000000001000000000001000000002001000000002001000000002001000000001001000000001001000000002001000000001101000000000101.The steps of the chromosome encoding method based on DSM are as follows:Step 1. Get set S of optional jobs. According to the characteristics of DSM, if all elements are 0 in row i except aii, then put Jiinto S.Step 2. Select one job Jk randomly in the set S as the current coding job and put gene k at the latest station of the chromosome. Meanwhile, update akk=akk−1. If the new akk=1, perform Step 3. If the new akk=0, update 0 to all elements in column k of DSM, and then perform Step 3.Step 3. Update DSM. Repeat Step 1 until DSM=0.Step 4. Insert 0-wait genes into the chromosome. If there are m operations in one 0-wait virtual workpiece, then repeat m−1 times insert gen m after gen m. End Step 4 till all 0-wait jobs complete gene insertion.After Step 3, the resulting chromosome contains all operations’ genes of non-0-wait virtual workpieces and 1 gene of each 0-wait virtual workpiece, for instance, 3-6-2-1-5-1-4-8-7-10-9-11, in which, there are two genes “1” and only one “4,” “5,” “6,” and “9.” After Step 4, the final coding chromosome is 3-6-6-2-1-5-5-1-4-4-8-7-10-9-9-11. If a numberi appears twice, it means that the virtual workpiece has 2 operations, the 1st number i represents the 1st operation in Ji, and the 2nd number i represents the 2nd operation in Ji.


### 3.2. Optimization Strategies to Improve Initial Population Quality

The quality of initial population has a great influence on the speed and quality of GA. At present, most of the literature generally adopts the random initialization method, which makes the quality of the initial solution unstable, especially when multiple operations need to be processed on the same machine. To solve this problem, combined with the characteristics of complex multiproduct scheduling problem, we proposed optimization strategies for the initial population. With the population produced by optimization strategies liberated into the initial population, we expect to improve the convergence speed of the algorithm.When multiple operations in setS of optional jobs need to be processed on the same machine, obviously, these operations are in the same grade, and the optimization strategies are as follows.For operationsOi and Ok, where Oi and Ok are both belong to leaf node operations, define Li as the number of the operations from Oi to root node operation. Define Ti as the time of the operation Oi. Define STi as the sum time of the operation from Oi to root node operation (Figure 5).(1)
More-task operation first (Figure5(a)). If Li≥Lk, then priority process Oi. If the priority is Ok then the number of operations that can be processed in parallel will be less, and the time of parallel processing will be increased.(2)
Long-path operation first (Figure5(b)). If Li=Lk, STi≥STk, then priority process Oi. In oriented graph, the path with the maximum path length from the start point to the end point is the critical path. Of cause, the path where Oi located is the critical path, and in the scheduling problem, it determines the value of makespan.(3)
Short-time operation first (Figure5(c)). If Li=Lk, STi=STk, STi≥STk, then priority process Oi. As the explanation in (2), either the path where Ji located or the path where Ok located can be selected to be the critical path. Therefore, when the operation with short processing time (Oi) is given priority, the operation with long processing time (Ok) enters the parallel processing state, which is more conducive to shorten the total processing time.Figure 5
The optimization strategies.
(a)(b)(c)


### 3.3. Select, Cross, and Mutate

#### 3.3.1. Selection Operator

In GA, the commonly used selection operators are rotating selection operator, rotating selection operator with ranking, random consistent selection operator, tournament selection operator, and so on. This paper adopts tournament selection operator. During the selection of the tournament selection operator,k individuals are randomly selected from the population, and the one with the best fitness among the k individuals is identified as the optimal individual. This optimal individual is an individual in the next generation population, and the process repeats n times to produce a new population.


#### 3.3.2. Crossover Operator

The purpose of crossover is to make use of the parent individuals to generate new individuals after a certain combination of operations and to search the solution space efficiently on the basis of minimizing the probability that the effective mode is destroyed. Zhang [35] adopted POX (multiparent precedence operation crossover) to for FJSP. Zhao [29] applied POX and IPOX to GA with virtual component level division coding. However, it is easy to produce infeasible solutions when POX is directly applied to the assembly JSP, so it is necessary to repair the chromosome with infeasible solution.The steps with repair to infeasible solution based on POX are shown in Figure6 and are as follows:Step 1. Randomly select a virtual workpiece as the intersection point. Let us say J8 is selected.Step 2. Divide the set of virtual workpieces into two sets according to the node workpiece: one is the set (Set_A) of virtual workpieces in front of the node and the other set (Set_B) is the rest virtual workpieces. Set_A=2,5,8, and Set_B=1,3,4,6,7,9,10.Step 3. The genes in Set_A of parent chromosome are passed on to offspring in situ and the genes in Set_B of the other parent chromosome are passed on to offspring supplementally.Step 4. The offspring chromosome with the greater serial number of the selected node in parent chromosome needs to be repaired. The offspring chromosome C2 needs to be repaired because J10 is earlier than J8.(a)
Get set (Set_C) of virtual workpieces which must be processed after the selected node workpiece.(b)
Extract the genes in Set_C of the offspring chromosome and insert them after the gene of selected node workpiece, and the follow-up gene complements the blank gene.Figure 6
The POX crossover.


#### 3.3.3. Mutation Operator

In terms of the ability to generate new individuals in the process of GA, crossover operation is the main method to generate new individuals, while mutation operation is the auxiliary method to generate new individuals. Combined with the characteristics of 0-wait complex multiproduct scheduling problem, this paper presents a new insertion mutation operator. The steps are as follows (Figure7):Step 1. Randomly select a virtual workpiece as the intersection point. Let us say J8 is selected.Step 2. Divide the set of virtual workpieces into two sets according to the node workpiece: one is the set (Set_A) of virtual workpieces in front of the node and the other set (Set_B) is the rest virtual workpieces. Set_A=2,5,8, and Set_B=1,3,4,6,7,9,10.Step 3. Insert the elements in Set_A into the offspring chromosome in turn according to the original procedure. The principle of Step 3 is shown in Figure 7.(a)
Get the number (Num_A) of workpieces in Set_A, and get the serial number (SN_P) of the tight after operation of the point workpiece in parent chromosome. Count_A = 0.(b)
Select the elements in Set_A in order. Count_A = Count_A + 1. If the current workpiece is the first element in Set_A, then insert it at [1, SN_P − Num_A]. Otherwise, get the serial number (SN_pre) of the immediate predecessor workpiece of it in offspring chromosome and insert it at [SN_pre + 1, SN_P − (Num_A − Count_A) − 1].(c)
Repeat (b) until Count_A = Num_A.(d)
Supplement the elements in Set_B to the blank of offspring chromosome.Figure 7
Step 3 of mutation.


### 3.4. Decoding

Decoding is the process of calculating the start and end time of each operation according to chromosome and determining the maximum completion time (makespan). In this paper, based on the initial operation of leaf node, the genes are divided into two categories, according to the machine counter and workpiece counter to decode.The notations are defined as follows:Oi, the current decoding operation represented by the ith gene.Oi_pre, the immediate predecessor operation of the current decoding operation Oi.O_leaf, leaf node initial workpiece set; that is, there is no precedence operations, which only refers to the first operation in the virtual workpieceM_counter, record the number of operations processed by the machine where the current decoding operation is located, including the current operation.O_counter, record the number of operations in the virtual workpiece where the current decoding operation is located, that is, the serial number in the virtual workpiece.No_wait, 0-wait operations set. For uniline no-wait constraint, that means all the operations in the same virtual workpiece have only one immediate predecessor operation, and in DSM, that is there is only one “1” element except the diagonal element in a row. For multiline no-wait constraint, that means allowing an operation in the virtual workpiece to have more than one immediate predecessor operation, and in DSM, there are non-0 and non-1 elements in a row.Si, start time of the ith gene.Pi, process time of the ith gene.Ei, end time of the ith gene.E_mb, end time of the last operation on the machine where the current decoding process is located.E_ob, end time of the last operation in the virtual workpiece where the current decoding operation is located.E_opre, end time of the immediate predecessor operation of the current decoding operation.The process of decoding, to put it simply, is to determine the operation type of current gene in the chromosome and determine when and which machine can start the operation. TheM_counter and O_counter can help us to understand the end time of E_mb, E_ob, and E_opre, and by comparing their values, the start time of current operation can be obtained. It is worth noting that active decoding is used here so that when it is found that there is enough free time in front of the machine and the operations sequence requirements are met, the process can be inserted forward and the gene sequence can be corrected. For the process with 0-wait constraint, the scheduled preoperation is updated according to the situation to make sure that there is no time gap between them. The specific decoding algorithm is in Algorithm 1 and the schematic diagram of decoding is in Figure 8.Algorithm 1:Decoding.
Input: Operation chromosome, Process time chromosome, Machine chromosome;Output: Makespan;(1)
for (i ← 1; i ≤ length of operation chromosome; i++)(2)
Case 1 (Oi belongs to O_leaf)(3)
if (O_counter = 1)(4)
if (M_counter = 1)//Figure 8-①(5)
Si = 0;(6)
else//Figure 8-②(7)
Si = E_mb;(8)
end if(9)
else(10)
if (M_counter = 1)//Figure 8-③(11)
Si = E_ob;(12)
else//Figure 8-④(13)
Si = max (E_mb, E_ob)(14)
end if(15)
end if(16)
Ei = Si + Pi;(17)
Case 2 (Oi does not belong to O_leaf)(18)
if (O_counter = 1)(19)
if (M_counter = 1)(20)
if (Oi does not has immediate predecessor operation)//Figure 8-⑤-1(21)
Si = 0;(22)
else//Figure 8-⑤-2(23)
Si = E_opre;(24)
end if(25)
else(26)
if (Oi does not has immediate predecessor operation)(27)
if (Oi cannot be inserted forward)//Figure 8-⑥-1, Figure 8-⑥-2(28)
Si = E_mb;(29)
else//Figure 8-⑥-3(30)
Si = the starting point of the idle time that can be inserted;(31)
end if(32)
else//Figure 8-⑥-4(33)
Si = max (E_mb, E_opre);(34)
end if(35)
end if(36)
else(37)
if (Oi does not belong to No-wait)(38)
if (M_counter = 1)//Figure 8-⑦(39)
Si = E_ob (or E_opre);(40)
else//Figure 8-⑧(41)
Si = max (E_mb, E_ob (or E_opre));(42)
end if(43)
else(44)
if (Oi belongs to uniline No-wait)(45)
if (M_counter = 1)//Figure 8-⑨-1(46)
Si = E_ob (or E_opre);(47)
else//Figure 8-⑨-2(48)
Si = max (E_mb, E_ob (or E_opre));(49)
Ei−1 = Si;(50)
Si−1 = Ei−1 − Pi−1;(51)
end if(52)
else(53)
if (M_counter = 1)//Figure 8-⑩-1(54)
Si = max (E_ob, E_opre);(55)
if (E_ob < E_opre)(56)
Ei−1 = Si;(57)
Si−1 = Ei−1 − Pi−1;(58)
end if(59)
else//Figure 8-⑩-2(60)
Si = max (E_mb, E_ob, E_opre);(61)
if (E_ob < E_opre ||E_ob < E_opre)(62)
Ei−1 = Si;(63)
Si−1 = Ei−1 − Pi−1;(64)
end if(65)
end if(66)
end if(67)
end if(68)
end if(69)
Ei = Si + Pi;(70)
end for(71)
Makespan=maxio_numEiFigure 8
Schematic diagram of decoding.After decoding the chromosome, the start time and completion time of each operation per machine can be obtained, and the corresponding scheduling Gantt chart can be drawn. The maximum completion time of the last operation of each machine is the value of the objective function.


### 3.5. Metropolis in Hybrid Algorithm

The setting of the initial value of temperatureT0 is one of the important factors affecting the global search performance of the SA algorithm. If T0 is high, it is possible to find the global optimal solution, but it takes a lot of computation time. Otherwise, the computation time can be saved, but the global search performance may be affected. This paper used the following formula to set the initial temperature:(11)T0=Umax−Umin,where Umax is the maximum solution in the contemporary population. Umin is the minimum solution in the contemporary population.Based on the above description, the acceptance probability of the solution in the nonoptimal direction is(12)p=exp−ΔfT0,Δf=Cmaxk+1−Cmaxk,where k represents the number of iterations.


## 3.1. Initial Population Coding Based on DSM

### 3.1.1. Pruning Method and Grading

Directed graph is one of the simplest methods to express the process. It mainly consists of the nodes representing tasks or features and the directed edges indicating the transmission of requirement information between the nodes. The operation tree is also representation of a directed graph. Pruning the product operation tree can simplify the model and improve the coding efficiency. Simply put, pruning is the process of integrating the single line operations or 0-wait operations into a virtual workpiece.The steps of pruning method are as follows:Step 1. Calculate the node in-degree in the directed graph corresponding to the product operation tree and mark the nodes with in-degree being 0.Step 2. Starting from a node with in-degree being 0, find the next node along the directed edge until reaching another node with in-degree being bigger than 1 or another node belonging to 0-wait operations. However, the above method is applicable; the starting node does not belong to the 0-wait operations. On the contrary, if the starting node belongs to 0-wait operations, end the searching process after the last 0-wait operations. Then, get a new operation tree.Step 3. Repeat Step 2 to the new operation tree until reaching the last operation in the operation tree.Virtual workpieces are graded based on the completion of pruning, using the method of calculating the task height value in a directed acyclic graph [33]. The grade of a virtual workpiece is defined as(7)gradeJi=0,predJi=ϕ,maxgradepredJi+1,otherwise.gradeJi is the grade of virtual workpiece Ji. predJi is the immediate predecessor virtual workpiece of Ji.The serial numberi of virtual workpiece Ji is defined as follow:Step 1. Calculate the number of virtual workpieces less than each grade.Step 2. In the same grade, number the virtual workpiece as 1 on the far left, then +1 on the second far left, and so on till reaching virtual workpiece on the far right.Step 3. In the same grade, add the number obtained from Step 1 and Step 2, and get the serial number i of current virtual workpiece Ji.Based on the definition above, if the grade number of one virtual workpiece is bigger than another, that means its serial number is bigger.As shown in Figure3, the shadow represents the operation with in-degree of 0, that is, the starting operation. The dotted box represents the 0-wait constraint. We can get the mapping relation such as J1 = {A1, A3}, J4 = {A2, A6}, and J7 = {A8}.Figure 3
Pruning process and grading result.


### 3.1.2. Coding Based on DSM

The solution of JSP is the sequence of jobs, and the sequence can get the start time and end time of each job on each machine. Based on this, the virtual workpieces can be sorted and solved according to the constraint relationship. Donald Steward [34] introduced structural design matrices (DSM) to analyse information flows in 1981. In this paper, we proposed an initialization population coding method for operations based on DSM, which contains the sequence constraints between virtual workpieces.Figure4 shows the specific principle of DSM. Building the DSM, firstly, the virtual workpieces are arranged in ascending order according to the grade from top to bottom and left to right. In principle, there is no sequence requirement for virtual workpieces in the same grade, but they are generally in ascending order according to the serial number of jobs. In DSM, the row number of the element represents the serial number of the virtual workpiece, and the column number of the element represents the serial number of the virtual workpiece corresponding to the immediate predecessor of the current virtual workpiece. For diagonal elements, if it is a virtual workpiece with 0-wait constraint, put 1 in; else, put the number of operations in this virtual workpiece in. For nondiagonal elements, if it is a virtual workpiece with 0-wait constraint, which means that there will be at least 2 operations in the virtual workpiece, find the serial number of its immediate predecessor, and in this column, put the serial number of the operation in current virtual workpiece in. On the contrary, if it is a virtual workpiece without 0 wait constraint, then the pruning rules determine that only the 1st operation in it has immediate predecessor, and put 1 in. For other elements, put 0 in. To sum up, it can be summarized as(8)DSMi,i=1,Jiis 0−wait virtual workpiece,nJi,Jiis non−0−wait virtual workpiece,(9)DSMi,j=k,Jjis immediate predecessor ofOkinJi,0,otherwise.Figure 4
The DSM of virtual workpieces.Then, get the DSM of the above problem as(10)DSM=aijn×n=2000000000001000000000001000000002001000000002001000000002001000000001001000000001001000000002001000000001101000000000101.The steps of the chromosome encoding method based on DSM are as follows:Step 1. Get set S of optional jobs. According to the characteristics of DSM, if all elements are 0 in row i except aii, then put Jiinto S.Step 2. Select one job Jk randomly in the set S as the current coding job and put gene k at the latest station of the chromosome. Meanwhile, update akk=akk−1. If the new akk=1, perform Step 3. If the new akk=0, update 0 to all elements in column k of DSM, and then perform Step 3.Step 3. Update DSM. Repeat Step 1 until DSM=0.Step 4. Insert 0-wait genes into the chromosome. If there are m operations in one 0-wait virtual workpiece, then repeat m−1 times insert gen m after gen m. End Step 4 till all 0-wait jobs complete gene insertion.After Step 3, the resulting chromosome contains all operations’ genes of non-0-wait virtual workpieces and 1 gene of each 0-wait virtual workpiece, for instance, 3-6-2-1-5-1-4-8-7-10-9-11, in which, there are two genes “1” and only one “4,” “5,” “6,” and “9.” After Step 4, the final coding chromosome is 3-6-6-2-1-5-5-1-4-4-8-7-10-9-9-11. If a numberi appears twice, it means that the virtual workpiece has 2 operations, the 1st number i represents the 1st operation in Ji, and the 2nd number i represents the 2nd operation in Ji.


## 3.1.1. Pruning Method and Grading

Directed graph is one of the simplest methods to express the process. It mainly consists of the nodes representing tasks or features and the directed edges indicating the transmission of requirement information between the nodes. The operation tree is also representation of a directed graph. Pruning the product operation tree can simplify the model and improve the coding efficiency. Simply put, pruning is the process of integrating the single line operations or 0-wait operations into a virtual workpiece.The steps of pruning method are as follows:Step 1. Calculate the node in-degree in the directed graph corresponding to the product operation tree and mark the nodes with in-degree being 0.Step 2. Starting from a node with in-degree being 0, find the next node along the directed edge until reaching another node with in-degree being bigger than 1 or another node belonging to 0-wait operations. However, the above method is applicable; the starting node does not belong to the 0-wait operations. On the contrary, if the starting node belongs to 0-wait operations, end the searching process after the last 0-wait operations. Then, get a new operation tree.Step 3. Repeat Step 2 to the new operation tree until reaching the last operation in the operation tree.Virtual workpieces are graded based on the completion of pruning, using the method of calculating the task height value in a directed acyclic graph [33]. The grade of a virtual workpiece is defined as(7)gradeJi=0,predJi=ϕ,maxgradepredJi+1,otherwise.gradeJi is the grade of virtual workpiece Ji. predJi is the immediate predecessor virtual workpiece of Ji.The serial numberi of virtual workpiece Ji is defined as follow:Step 1. Calculate the number of virtual workpieces less than each grade.Step 2. In the same grade, number the virtual workpiece as 1 on the far left, then +1 on the second far left, and so on till reaching virtual workpiece on the far right.Step 3. In the same grade, add the number obtained from Step 1 and Step 2, and get the serial number i of current virtual workpiece Ji.Based on the definition above, if the grade number of one virtual workpiece is bigger than another, that means its serial number is bigger.As shown in Figure3, the shadow represents the operation with in-degree of 0, that is, the starting operation. The dotted box represents the 0-wait constraint. We can get the mapping relation such as J1 = {A1, A3}, J4 = {A2, A6}, and J7 = {A8}.Figure 3
Pruning process and grading result.


## 3.1.2. Coding Based on DSM

The solution of JSP is the sequence of jobs, and the sequence can get the start time and end time of each job on each machine. Based on this, the virtual workpieces can be sorted and solved according to the constraint relationship. Donald Steward [34] introduced structural design matrices (DSM) to analyse information flows in 1981. In this paper, we proposed an initialization population coding method for operations based on DSM, which contains the sequence constraints between virtual workpieces.Figure4 shows the specific principle of DSM. Building the DSM, firstly, the virtual workpieces are arranged in ascending order according to the grade from top to bottom and left to right. In principle, there is no sequence requirement for virtual workpieces in the same grade, but they are generally in ascending order according to the serial number of jobs. In DSM, the row number of the element represents the serial number of the virtual workpiece, and the column number of the element represents the serial number of the virtual workpiece corresponding to the immediate predecessor of the current virtual workpiece. For diagonal elements, if it is a virtual workpiece with 0-wait constraint, put 1 in; else, put the number of operations in this virtual workpiece in. For nondiagonal elements, if it is a virtual workpiece with 0-wait constraint, which means that there will be at least 2 operations in the virtual workpiece, find the serial number of its immediate predecessor, and in this column, put the serial number of the operation in current virtual workpiece in. On the contrary, if it is a virtual workpiece without 0 wait constraint, then the pruning rules determine that only the 1st operation in it has immediate predecessor, and put 1 in. For other elements, put 0 in. To sum up, it can be summarized as(8)DSMi,i=1,Jiis 0−wait virtual workpiece,nJi,Jiis non−0−wait virtual workpiece,(9)DSMi,j=k,Jjis immediate predecessor ofOkinJi,0,otherwise.Figure 4
The DSM of virtual workpieces.Then, get the DSM of the above problem as(10)DSM=aijn×n=2000000000001000000000001000000002001000000002001000000002001000000001001000000001001000000002001000000001101000000000101.The steps of the chromosome encoding method based on DSM are as follows:Step 1. Get set S of optional jobs. According to the characteristics of DSM, if all elements are 0 in row i except aii, then put Jiinto S.Step 2. Select one job Jk randomly in the set S as the current coding job and put gene k at the latest station of the chromosome. Meanwhile, update akk=akk−1. If the new akk=1, perform Step 3. If the new akk=0, update 0 to all elements in column k of DSM, and then perform Step 3.Step 3. Update DSM. Repeat Step 1 until DSM=0.Step 4. Insert 0-wait genes into the chromosome. If there are m operations in one 0-wait virtual workpiece, then repeat m−1 times insert gen m after gen m. End Step 4 till all 0-wait jobs complete gene insertion.After Step 3, the resulting chromosome contains all operations’ genes of non-0-wait virtual workpieces and 1 gene of each 0-wait virtual workpiece, for instance, 3-6-2-1-5-1-4-8-7-10-9-11, in which, there are two genes “1” and only one “4,” “5,” “6,” and “9.” After Step 4, the final coding chromosome is 3-6-6-2-1-5-5-1-4-4-8-7-10-9-9-11. If a numberi appears twice, it means that the virtual workpiece has 2 operations, the 1st number i represents the 1st operation in Ji, and the 2nd number i represents the 2nd operation in Ji.


## 3.2. Optimization Strategies to Improve Initial Population Quality

The quality of initial population has a great influence on the speed and quality of GA. At present, most of the literature generally adopts the random initialization method, which makes the quality of the initial solution unstable, especially when multiple operations need to be processed on the same machine. To solve this problem, combined with the characteristics of complex multiproduct scheduling problem, we proposed optimization strategies for the initial population. With the population produced by optimization strategies liberated into the initial population, we expect to improve the convergence speed of the algorithm.When multiple operations in setS of optional jobs need to be processed on the same machine, obviously, these operations are in the same grade, and the optimization strategies are as follows.For operationsOi and Ok, where Oi and Ok are both belong to leaf node operations, define Li as the number of the operations from Oi to root node operation. Define Ti as the time of the operation Oi. Define STi as the sum time of the operation from Oi to root node operation (Figure 5).(1)
More-task operation first (Figure5(a)). If Li≥Lk, then priority process Oi. If the priority is Ok then the number of operations that can be processed in parallel will be less, and the time of parallel processing will be increased.(2)
Long-path operation first (Figure5(b)). If Li=Lk, STi≥STk, then priority process Oi. In oriented graph, the path with the maximum path length from the start point to the end point is the critical path. Of cause, the path where Oi located is the critical path, and in the scheduling problem, it determines the value of makespan.(3)
Short-time operation first (Figure5(c)). If Li=Lk, STi=STk, STi≥STk, then priority process Oi. As the explanation in (2), either the path where Ji located or the path where Ok located can be selected to be the critical path. Therefore, when the operation with short processing time (Oi) is given priority, the operation with long processing time (Ok) enters the parallel processing state, which is more conducive to shorten the total processing time.Figure 5
The optimization strategies.
(a)(b)(c)


## 3.3. Select, Cross, and Mutate

### 3.3.1. Selection Operator

In GA, the commonly used selection operators are rotating selection operator, rotating selection operator with ranking, random consistent selection operator, tournament selection operator, and so on. This paper adopts tournament selection operator. During the selection of the tournament selection operator,k individuals are randomly selected from the population, and the one with the best fitness among the k individuals is identified as the optimal individual. This optimal individual is an individual in the next generation population, and the process repeats n times to produce a new population.


### 3.3.2. Crossover Operator

The purpose of crossover is to make use of the parent individuals to generate new individuals after a certain combination of operations and to search the solution space efficiently on the basis of minimizing the probability that the effective mode is destroyed. Zhang [35] adopted POX (multiparent precedence operation crossover) to for FJSP. Zhao [29] applied POX and IPOX to GA with virtual component level division coding. However, it is easy to produce infeasible solutions when POX is directly applied to the assembly JSP, so it is necessary to repair the chromosome with infeasible solution.The steps with repair to infeasible solution based on POX are shown in Figure6 and are as follows:Step 1. Randomly select a virtual workpiece as the intersection point. Let us say J8 is selected.Step 2. Divide the set of virtual workpieces into two sets according to the node workpiece: one is the set (Set_A) of virtual workpieces in front of the node and the other set (Set_B) is the rest virtual workpieces. Set_A=2,5,8, and Set_B=1,3,4,6,7,9,10.Step 3. The genes in Set_A of parent chromosome are passed on to offspring in situ and the genes in Set_B of the other parent chromosome are passed on to offspring supplementally.Step 4. The offspring chromosome with the greater serial number of the selected node in parent chromosome needs to be repaired. The offspring chromosome C2 needs to be repaired because J10 is earlier than J8.(a)
Get set (Set_C) of virtual workpieces which must be processed after the selected node workpiece.(b)
Extract the genes in Set_C of the offspring chromosome and insert them after the gene of selected node workpiece, and the follow-up gene complements the blank gene.Figure 6
The POX crossover.


### 3.3.3. Mutation Operator

In terms of the ability to generate new individuals in the process of GA, crossover operation is the main method to generate new individuals, while mutation operation is the auxiliary method to generate new individuals. Combined with the characteristics of 0-wait complex multiproduct scheduling problem, this paper presents a new insertion mutation operator. The steps are as follows (Figure7):Step 1. Randomly select a virtual workpiece as the intersection point. Let us say J8 is selected.Step 2. Divide the set of virtual workpieces into two sets according to the node workpiece: one is the set (Set_A) of virtual workpieces in front of the node and the other set (Set_B) is the rest virtual workpieces. Set_A=2,5,8, and Set_B=1,3,4,6,7,9,10.Step 3. Insert the elements in Set_A into the offspring chromosome in turn according to the original procedure. The principle of Step 3 is shown in Figure 7.(a)
Get the number (Num_A) of workpieces in Set_A, and get the serial number (SN_P) of the tight after operation of the point workpiece in parent chromosome. Count_A = 0.(b)
Select the elements in Set_A in order. Count_A = Count_A + 1. If the current workpiece is the first element in Set_A, then insert it at [1, SN_P − Num_A]. Otherwise, get the serial number (SN_pre) of the immediate predecessor workpiece of it in offspring chromosome and insert it at [SN_pre + 1, SN_P − (Num_A − Count_A) − 1].(c)
Repeat (b) until Count_A = Num_A.(d)
Supplement the elements in Set_B to the blank of offspring chromosome.Figure 7
Step 3 of mutation.


## 3.3.1. Selection Operator

In GA, the commonly used selection operators are rotating selection operator, rotating selection operator with ranking, random consistent selection operator, tournament selection operator, and so on. This paper adopts tournament selection operator. During the selection of the tournament selection operator,k individuals are randomly selected from the population, and the one with the best fitness among the k individuals is identified as the optimal individual. This optimal individual is an individual in the next generation population, and the process repeats n times to produce a new population.


## 3.3.2. Crossover Operator

The purpose of crossover is to make use of the parent individuals to generate new individuals after a certain combination of operations and to search the solution space efficiently on the basis of minimizing the probability that the effective mode is destroyed. Zhang [35] adopted POX (multiparent precedence operation crossover) to for FJSP. Zhao [29] applied POX and IPOX to GA with virtual component level division coding. However, it is easy to produce infeasible solutions when POX is directly applied to the assembly JSP, so it is necessary to repair the chromosome with infeasible solution.The steps with repair to infeasible solution based on POX are shown in Figure6 and are as follows:Step 1. Randomly select a virtual workpiece as the intersection point. Let us say J8 is selected.Step 2. Divide the set of virtual workpieces into two sets according to the node workpiece: one is the set (Set_A) of virtual workpieces in front of the node and the other set (Set_B) is the rest virtual workpieces. Set_A=2,5,8, and Set_B=1,3,4,6,7,9,10.Step 3. The genes in Set_A of parent chromosome are passed on to offspring in situ and the genes in Set_B of the other parent chromosome are passed on to offspring supplementally.Step 4. The offspring chromosome with the greater serial number of the selected node in parent chromosome needs to be repaired. The offspring chromosome C2 needs to be repaired because J10 is earlier than J8.(a)
Get set (Set_C) of virtual workpieces which must be processed after the selected node workpiece.(b)
Extract the genes in Set_C of the offspring chromosome and insert them after the gene of selected node workpiece, and the follow-up gene complements the blank gene.Figure 6
The POX crossover.


## 3.3.3. Mutation Operator

In terms of the ability to generate new individuals in the process of GA, crossover operation is the main method to generate new individuals, while mutation operation is the auxiliary method to generate new individuals. Combined with the characteristics of 0-wait complex multiproduct scheduling problem, this paper presents a new insertion mutation operator. The steps are as follows (Figure7):Step 1. Randomly select a virtual workpiece as the intersection point. Let us say J8 is selected.Step 2. Divide the set of virtual workpieces into two sets according to the node workpiece: one is the set (Set_A) of virtual workpieces in front of the node and the other set (Set_B) is the rest virtual workpieces. Set_A=2,5,8, and Set_B=1,3,4,6,7,9,10.Step 3. Insert the elements in Set_A into the offspring chromosome in turn according to the original procedure. The principle of Step 3 is shown in Figure 7.(a)
Get the number (Num_A) of workpieces in Set_A, and get the serial number (SN_P) of the tight after operation of the point workpiece in parent chromosome. Count_A = 0.(b)
Select the elements in Set_A in order. Count_A = Count_A + 1. If the current workpiece is the first element in Set_A, then insert it at [1, SN_P − Num_A]. Otherwise, get the serial number (SN_pre) of the immediate predecessor workpiece of it in offspring chromosome and insert it at [SN_pre + 1, SN_P − (Num_A − Count_A) − 1].(c)
Repeat (b) until Count_A = Num_A.(d)
Supplement the elements in Set_B to the blank of offspring chromosome.Figure 7
Step 3 of mutation.


## 3.4. Decoding

Decoding is the process of calculating the start and end time of each operation according to chromosome and determining the maximum completion time (makespan). In this paper, based on the initial operation of leaf node, the genes are divided into two categories, according to the machine counter and workpiece counter to decode.The notations are defined as follows:Oi, the current decoding operation represented by the ith gene.Oi_pre, the immediate predecessor operation of the current decoding operation Oi.O_leaf, leaf node initial workpiece set; that is, there is no precedence operations, which only refers to the first operation in the virtual workpieceM_counter, record the number of operations processed by the machine where the current decoding operation is located, including the current operation.O_counter, record the number of operations in the virtual workpiece where the current decoding operation is located, that is, the serial number in the virtual workpiece.No_wait, 0-wait operations set. For uniline no-wait constraint, that means all the operations in the same virtual workpiece have only one immediate predecessor operation, and in DSM, that is there is only one “1” element except the diagonal element in a row. For multiline no-wait constraint, that means allowing an operation in the virtual workpiece to have more than one immediate predecessor operation, and in DSM, there are non-0 and non-1 elements in a row.Si, start time of the ith gene.Pi, process time of the ith gene.Ei, end time of the ith gene.E_mb, end time of the last operation on the machine where the current decoding process is located.E_ob, end time of the last operation in the virtual workpiece where the current decoding operation is located.E_opre, end time of the immediate predecessor operation of the current decoding operation.The process of decoding, to put it simply, is to determine the operation type of current gene in the chromosome and determine when and which machine can start the operation. TheM_counter and O_counter can help us to understand the end time of E_mb, E_ob, and E_opre, and by comparing their values, the start time of current operation can be obtained. It is worth noting that active decoding is used here so that when it is found that there is enough free time in front of the machine and the operations sequence requirements are met, the process can be inserted forward and the gene sequence can be corrected. For the process with 0-wait constraint, the scheduled preoperation is updated according to the situation to make sure that there is no time gap between them. The specific decoding algorithm is in Algorithm 1 and the schematic diagram of decoding is in Figure 8.Algorithm 1:Decoding.
Input: Operation chromosome, Process time chromosome, Machine chromosome;Output: Makespan;(1)
for (i ← 1; i ≤ length of operation chromosome; i++)(2)
Case 1 (Oi belongs to O_leaf)(3)
if (O_counter = 1)(4)
if (M_counter = 1)//Figure 8-①(5)
Si = 0;(6)
else//Figure 8-②(7)
Si = E_mb;(8)
end if(9)
else(10)
if (M_counter = 1)//Figure 8-③(11)
Si = E_ob;(12)
else//Figure 8-④(13)
Si = max (E_mb, E_ob)(14)
end if(15)
end if(16)
Ei = Si + Pi;(17)
Case 2 (Oi does not belong to O_leaf)(18)
if (O_counter = 1)(19)
if (M_counter = 1)(20)
if (Oi does not has immediate predecessor operation)//Figure 8-⑤-1(21)
Si = 0;(22)
else//Figure 8-⑤-2(23)
Si = E_opre;(24)
end if(25)
else(26)
if (Oi does not has immediate predecessor operation)(27)
if (Oi cannot be inserted forward)//Figure 8-⑥-1, Figure 8-⑥-2(28)
Si = E_mb;(29)
else//Figure 8-⑥-3(30)
Si = the starting point of the idle time that can be inserted;(31)
end if(32)
else//Figure 8-⑥-4(33)
Si = max (E_mb, E_opre);(34)
end if(35)
end if(36)
else(37)
if (Oi does not belong to No-wait)(38)
if (M_counter = 1)//Figure 8-⑦(39)
Si = E_ob (or E_opre);(40)
else//Figure 8-⑧(41)
Si = max (E_mb, E_ob (or E_opre));(42)
end if(43)
else(44)
if (Oi belongs to uniline No-wait)(45)
if (M_counter = 1)//Figure 8-⑨-1(46)
Si = E_ob (or E_opre);(47)
else//Figure 8-⑨-2(48)
Si = max (E_mb, E_ob (or E_opre));(49)
Ei−1 = Si;(50)
Si−1 = Ei−1 − Pi−1;(51)
end if(52)
else(53)
if (M_counter = 1)//Figure 8-⑩-1(54)
Si = max (E_ob, E_opre);(55)
if (E_ob < E_opre)(56)
Ei−1 = Si;(57)
Si−1 = Ei−1 − Pi−1;(58)
end if(59)
else//Figure 8-⑩-2(60)
Si = max (E_mb, E_ob, E_opre);(61)
if (E_ob < E_opre ||E_ob < E_opre)(62)
Ei−1 = Si;(63)
Si−1 = Ei−1 − Pi−1;(64)
end if(65)
end if(66)
end if(67)
end if(68)
end if(69)
Ei = Si + Pi;(70)
end for(71)
Makespan=maxio_numEiFigure 8
Schematic diagram of decoding.After decoding the chromosome, the start time and completion time of each operation per machine can be obtained, and the corresponding scheduling Gantt chart can be drawn. The maximum completion time of the last operation of each machine is the value of the objective function.


## 3.5. Metropolis in Hybrid Algorithm

The setting of the initial value of temperatureT0 is one of the important factors affecting the global search performance of the SA algorithm. If T0 is high, it is possible to find the global optimal solution, but it takes a lot of computation time. Otherwise, the computation time can be saved, but the global search performance may be affected. This paper used the following formula to set the initial temperature:(11)T0=Umax−Umin,where Umax is the maximum solution in the contemporary population. Umin is the minimum solution in the contemporary population.Based on the above description, the acceptance probability of the solution in the nonoptimal direction is(12)p=exp−ΔfT0,Δf=Cmaxk+1−Cmaxk,where k represents the number of iterations.


## 4. Experiments Results and Analysis

The existing international benchmark test examples can be directly used for JSP. However, the standard test case library for complex product scheduling problem has not been established, especially the complex multiproduct scheduling problem with 0-wait constraint. In order to verify the performance of the algorithm proposed in this paper, examples found in relevant literature are selected for testing.The algorithm was coded in MATLAB language. The computer CPU (Intel Core i5-4460) locks at 3.2 GHz and the RAM is 8 GB.


### 4.1. Case 1

Case 1.
is an example of the problem in reference of Xie [25]. Figure 1 is its operation tree of product. Figure 3 is its pruning process and grading result. The DSM representing the sequential constraint relationship between operations is shown in equation (10). For this case, the algorithm parameters were set as follows: the initial population size was 20, the maximum genetic algebra was 50, the crossover probability was 0.9, and the mutation probability was 0.05.
In the process of solving 10 times, the average makespan was 41, and the average solution time was 2.175 s. Figure9 is the population distribution map of Case 1. In order to better represent the population density in the same generation, individuals were moved to the neighborhoods in the mapping, so that individuals with the same fitness are not concentrated in one point. It shows that the individual diversity of the primary population was relatively large, and there was no most solvable one. With the increase in the number of iterations, individuals gradually moved to the optimal solution. However, in a certain generation of population, the existence of mutation individuals can prevent the population from falling into the local optimal solution.
Figure10 is the population evolutionary process of Case 1. In the whole evolutionary process, the individuals of the population moved evidently to the optimal solution twice in the 4th and 11th generations, respectively. Finally, the optimal solution was obtained in the 12th generation. With the change of population iteration times, the mean and variance of individual fitness also showed good convergence. The fluctuation of variance can reflect the existence of population richness, so as to avoid falling into the local optimal solution.
Figure11(a) is the Gantt chart of the optimal scheduling result obtained by this algorithm and the optimal solution result is 41. At the same time, this result was also obtained in reference of Guo [24]. Figure 11(b) is the Gantt chart of the optimal scheduling result obtained by the reference of Xie [28] and the optimal solution result was 45. Figure 11(c) is the Gantt chart of the optimal scheduling result obtained by the reference of Xie [25] and the optimal solution result was 46. Figure 12 is the population evolutionary process of diffident algorithm. Here, the algorithm parameters were all set as follows: the initial population size was 50, the maximum genetic algebra was 50, the crossover probability was 0.9, and the mutation probability was 0.05. As shown in the picture, the algorithm proposed in this paper has high initial population quality and the fastest convergence speed. The reference of Guo [24] has the second fastest convergence rate. The convergence speed of the standard GA is the slowest. To sum up, this is because the algorithm proposed in this paper adds optimized high-quality individuals to the initial population and combines with the greedy mechanism of SA algorithm, which makes this algorithm better than other algorithms.Figure 9
The population distribution map of Case 1.Figure 10
The population evolutionary process of Case 1.Figure 11
The Gantt chart of Case 1. (a) The minimum makespan is 41, (b) the minimum makespan is 45, and (c) the minimum makespan is 46.
(a)(b)(c)Figure 12
The population evolutionary process of diffident algorithm for Case 1.


### 4.2. Case 2

Case 2.
is an example of the problem in reference of Xie [27]. Figure 13 is its operation tree of product. Figure 14 is its pruning and grading result. The DSM representing the sequential constraint relationship between operations is shown in equation (9). For this case, the algorithm parameters were set as follows: the initial population size was 30, the maximum genetic algebra was 50, the crossover probability was 0.9, and the mutation probability was 0.1.(13)DSM=aijn×n=100000000000000000010000000000000000001000000000000000000100000000000000000010000000000000000001000000000000000000100000000000000000010000000000000000001000000000021000000100000000000001100020000000000000000102000000000210000010100000100000000001010000000000000000101000000000012000004100000000000000000120000000000000000012.
In the process of solving 10 times, the average makespan is 27.4 (27 appeared 8 times and 29 appeared twice), and the average solution time is 4.636 s. The optimal scheduling result obtained by this algorithm is 27. Figure15 is 6 different Gantt charts of the optimal scheduling results obtained by the proposed algorithm in this paper. The reference of Guo [24] set the population size to 200. In the process of solving 10 times, the average makespan is 27.5, the average solution time is 9.15 s, and 2 different Gantt charts of the optimal scheduling are output. The reference of Xie [25] got the optimal solution 31. The reference of Xie [27] got the optimal solution 28. Figure 16 is the population evolutionary process of diffident algorithm for Case 2. Obviously, the results of the algorithm in this paper are better than those in the literature.
Figure17 is the population distribution map of Case 2. It is obvious that the population approaches the optimal solution with the increase of iteration times. According to the population density, it shows that obvious population aggregation occurred in the 2nd, 4th, 6th, 7th, and 9th generations, and the aggregation solutions were 35, 34, 35, 31, and 29, respectively, which is the result of GA selection.
Figure18 is the population evolutionary process of Case 2. The optimal solution was obtained in the 12th generation. With the change of population iteration times, the mean and variance of individual fitness also show good convergence. In the 12th generation, the variance suddenly increased, which also represents that the individual diversity of the population suddenly became rich, which is beneficial to the global optimization.Figure 13
Operation tree of Case 2.Figure 14
Pruning and grading result of Case 2.Figure 15
The Gantt chart of Case 2. (a–f) The minimum makespan is 27.
(a)(b)(c)(d)(e)(f)Figure 16
The population evolutionary process of diffident algorithm for Case 2.Figure 17
The population distribution map of Case 2.Figure 18
The population evolutionary process of Case 2.


## 4.1. Case 1

Case 1.
is an example of the problem in reference of Xie [25]. Figure 1 is its operation tree of product. Figure 3 is its pruning process and grading result. The DSM representing the sequential constraint relationship between operations is shown in equation (10). For this case, the algorithm parameters were set as follows: the initial population size was 20, the maximum genetic algebra was 50, the crossover probability was 0.9, and the mutation probability was 0.05.
In the process of solving 10 times, the average makespan was 41, and the average solution time was 2.175 s. Figure9 is the population distribution map of Case 1. In order to better represent the population density in the same generation, individuals were moved to the neighborhoods in the mapping, so that individuals with the same fitness are not concentrated in one point. It shows that the individual diversity of the primary population was relatively large, and there was no most solvable one. With the increase in the number of iterations, individuals gradually moved to the optimal solution. However, in a certain generation of population, the existence of mutation individuals can prevent the population from falling into the local optimal solution.
Figure10 is the population evolutionary process of Case 1. In the whole evolutionary process, the individuals of the population moved evidently to the optimal solution twice in the 4th and 11th generations, respectively. Finally, the optimal solution was obtained in the 12th generation. With the change of population iteration times, the mean and variance of individual fitness also showed good convergence. The fluctuation of variance can reflect the existence of population richness, so as to avoid falling into the local optimal solution.
Figure11(a) is the Gantt chart of the optimal scheduling result obtained by this algorithm and the optimal solution result is 41. At the same time, this result was also obtained in reference of Guo [24]. Figure 11(b) is the Gantt chart of the optimal scheduling result obtained by the reference of Xie [28] and the optimal solution result was 45. Figure 11(c) is the Gantt chart of the optimal scheduling result obtained by the reference of Xie [25] and the optimal solution result was 46. Figure 12 is the population evolutionary process of diffident algorithm. Here, the algorithm parameters were all set as follows: the initial population size was 50, the maximum genetic algebra was 50, the crossover probability was 0.9, and the mutation probability was 0.05. As shown in the picture, the algorithm proposed in this paper has high initial population quality and the fastest convergence speed. The reference of Guo [24] has the second fastest convergence rate. The convergence speed of the standard GA is the slowest. To sum up, this is because the algorithm proposed in this paper adds optimized high-quality individuals to the initial population and combines with the greedy mechanism of SA algorithm, which makes this algorithm better than other algorithms.Figure 9
The population distribution map of Case 1.Figure 10
The population evolutionary process of Case 1.Figure 11
The Gantt chart of Case 1. (a) The minimum makespan is 41, (b) the minimum makespan is 45, and (c) the minimum makespan is 46.
(a)(b)(c)Figure 12
The population evolutionary process of diffident algorithm for Case 1.


## 4.2. Case 2

Case 2.
is an example of the problem in reference of Xie [27]. Figure 13 is its operation tree of product. Figure 14 is its pruning and grading result. The DSM representing the sequential constraint relationship between operations is shown in equation (9). For this case, the algorithm parameters were set as follows: the initial population size was 30, the maximum genetic algebra was 50, the crossover probability was 0.9, and the mutation probability was 0.1.(13)DSM=aijn×n=100000000000000000010000000000000000001000000000000000000100000000000000000010000000000000000001000000000000000000100000000000000000010000000000000000001000000000021000000100000000000001100020000000000000000102000000000210000010100000100000000001010000000000000000101000000000012000004100000000000000000120000000000000000012.
In the process of solving 10 times, the average makespan is 27.4 (27 appeared 8 times and 29 appeared twice), and the average solution time is 4.636 s. The optimal scheduling result obtained by this algorithm is 27. Figure15 is 6 different Gantt charts of the optimal scheduling results obtained by the proposed algorithm in this paper. The reference of Guo [24] set the population size to 200. In the process of solving 10 times, the average makespan is 27.5, the average solution time is 9.15 s, and 2 different Gantt charts of the optimal scheduling are output. The reference of Xie [25] got the optimal solution 31. The reference of Xie [27] got the optimal solution 28. Figure 16 is the population evolutionary process of diffident algorithm for Case 2. Obviously, the results of the algorithm in this paper are better than those in the literature.
Figure17 is the population distribution map of Case 2. It is obvious that the population approaches the optimal solution with the increase of iteration times. According to the population density, it shows that obvious population aggregation occurred in the 2nd, 4th, 6th, 7th, and 9th generations, and the aggregation solutions were 35, 34, 35, 31, and 29, respectively, which is the result of GA selection.
Figure18 is the population evolutionary process of Case 2. The optimal solution was obtained in the 12th generation. With the change of population iteration times, the mean and variance of individual fitness also show good convergence. In the 12th generation, the variance suddenly increased, which also represents that the individual diversity of the population suddenly became rich, which is beneficial to the global optimization.Figure 13
Operation tree of Case 2.Figure 14
Pruning and grading result of Case 2.Figure 15
The Gantt chart of Case 2. (a–f) The minimum makespan is 27.
(a)(b)(c)(d)(e)(f)Figure 16
The population evolutionary process of diffident algorithm for Case 2.Figure 17
The population distribution map of Case 2.Figure 18
The population evolutionary process of Case 2.


## 5. Conclusion

Aiming at the complex multiproduct scheduling problem with 0-wait constraint, a hybrid algorithm based on GA and SA algorithm was studied. Based on the results of pruning and grading to the operation tree of complex multiproduct, the DSM with precedence constraints was established. Then, an initial population coding method based on DSM was proposed, which ensures the feasibility of the initial solution. At the same time, three strategies to optimize the initial population were proposed to improve the quality of the initial population for the situation of multiple operations in the same grade which need to be processed on the same machine, and they were more-task operation first, long-path operation first, and short-time operation first. For the hybrid algorithm, the specific process flow and the setting method of related parameters were carried out. For the infeasible solution produced in the crossover operation, the repair method was proposed. In the process of decoding, the chromosome genes were classified and the decoding for complex multiproduct scheduling problem with 0-wait constraint was realized through the analysis of its characteristics. The effectiveness of the proposed algorithm for complex multiproduct scheduling problem with 0-wait constraint is verified by the test of related examples in the existing literature.For the general JSP, there are process constraints in the internal production process of workpiece. Different from the general JSP, the complex multiproduct scheduling problem has sequence constraints between workpieces, which is equivalent to a multilayer JSP. With the 0-wait constraint, the model of this problem can provide guidance for solving the scheduling requirements of small-batch special production. The DSM-based coding method proposed in this paper can also introduce other intelligent algorithms to solve the integrated product scheduling problem.The neighborhood operators designed in this paper focus more on ensuring the feasibility of generating offspring individuals, which makes it unable to compete with the excellent neighborhood operators in traditional job-shop scheduling and reduces the search ability of the algorithm. Seeking or researching better neighborhood operators to improve the speed and accuracy of the algorithm is the direction worthy of further study in the future.



---

*Source: 9951995-2021-06-21.xml*