# Research on Shipboard Material Scheduling Optimization Based on Improved Genetic Algorithm

Authors: Feihui Yuan; Jinghua Li; Qinghua Zhou; Ming He
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

The development of the cruise industry is an important part of the country’s “Marine power” and “One Belt, One Road” strategy. Improving the independent construction of cruise ships is of great significance to my country’s economic and social development. Aiming at the problem of the assembly order of cruise ship outfitting parts are many, the quantity is large, and the interchangeability of materials is higher than that of conventional ships, a cruise ship outfitting on-board assembly scheduling problem model is constructed, and a cruise ship outfitting on-board assembly material scheduling method oriented to generally outfitting is proposed. The improved genetic algorithm is used to dispatch the materials on the outfitting ships to realize the optimal utilization of the materials and materials, and the effectiveness of the method is proved by the example verification.


---

## Body

## 1. Introduction

At present, the research on the problem of workshop material scheduling is relatively in-depth, and the results are remarkable. The research mainly focuses on two aspects: model construction and improvement and optimization method design.In 1990, Brucker and Schlie [1] proposed the flexible job-shop problem (FJSP): a combination of machine selection and process sequencing problems. At present, when solving FJSP, there are mainly two methods: the step-by-step method and the integrated approach. Bandmate [2] first used the step-by-step method to solve the FJSP problem, combining the machine assignment rules with the tabu search algorithm, and using the tabu search method to solve the process sequencing problem. Scrich and others [3] solved the FJSP problem with the goal of minimizing the total tardiness based on the tabu algorithm. Chen et al. [4] proposed a multiobjective FJSP problem model considering manufacturing cycle, cost, and quality. Zhang et al. [5] mixed the genetic algorithm and tabu search algorithm to solve the FJSP problem with transportation and limited time. Ho and Tay [6] combined the finite assignment rules based on the GP algorithm to solve the FJSP problem. Driss et al. [7] designed a new chromosome representation method based on the characteristics of FJSP. Shikui et al. [8–10] proposed a genetic algorithm based on free time neighborhood search for the actual environment on a flexible ship and the cloud intelligent manufacturing environment. Many modern intelligent algorithms are based on the wisdom of nature. What remains is not only the ability to adapt to the environment but also reasonable information processing methods. Based on these information processing methods, scholars have proposed intelligent algorithms such as the genetic algorithm, bacterial foraging algorithm, ant colony algorithm and fish swarm algorithm. The intelligent algorithm is applied to the resource scheduling of flexible workshops and has achieved good results [11–18].In the early 1980s, Henrioud and Bourjault [19] of France creatively proposed a part assembly sequence sorting method and studied a two-dimensional topology composed of nodes and edges to describe the association relationship within the assembly model. Based on this association relationship, de Mello and Sanderson [20] further explored the problem of part assembly, processed the internal association relationship of the assembly model through the cut set analysis method, and obtained all geometrically feasible assembly sequences but did not consider the easy assembly rules. In the late 1980s, de Fazio and Whitney [21] of the United States improved Bourjault’s algorithm, which originally needed to solve two problems to only need 2n problems combined with the tight front tight back relationship. After the 1990s, Wilson [22, 23] improved the cut set analysis method and introduced the optimization method of interfering with the subset of parts by using user requirements, which provides more judgment information for cut set segmentation. On the basis of analyzing the relationship between parts and assembly resources, Bo et al. [24] proposed a multistage assembly resource matching design method based on the assembly availability model. Guanjun and Dachun [25] expressed the basic assembly information of the product by establishing the interference matrix, contact matrix, and tool list of the product and enabled the priority constraint matrix to optimize the assembly sequence. Liu et al. [26] proposed a method to integrate human fuzzy knowledge into the planning process through the genetic algorithm and ant colony algorithm to solve the assembly sequence accurately.Based on the above, most of the papers are workshop scheduling papers and outfitting assembly sequence, which can not meet the needs of cruise mass production; this article will optimize the dispatching of outfitting materials on cruise ships. Firstly, it describes the scheduling problem of outfitting materials on cruise ship outfitting ships and establishes an assembly-oriented model for the scheduling of outfitting materials on cruise ships outfitting ships; then, it studies and improves the coding method, initialization method, and genetic operation and decoding method of the genetic algorithm. Finally, the effectiveness of the optimization method in the assembly-oriented scheduling of cruise ship outfitting supplies is verified.


## 2. Problem Description and Mathematical Model

### 2.1. Problem Description

The problem of dispatching materials on cruise ship outfitting can be expressed as there aren outfitting parts, each outfitting part is composed of several materials, and each material is formed by a number of sequential processes, these procedures must be completed in m cabins, and at least one cabin can be selected for each procedure. Consider the assembly sequence of outfitting parts, the multiple assembly sequence of materials and equipment material constraints, as well as the sequence of materials and material constraints, with the goal of optimizing the service completion time of the total section, sort the order of the material cabin and corresponding cabin.The assembly time of outfitting parts corresponding to the shortest outfitting material time is not necessarily the shortest. For example, perform the assembly of outfittingJ1=J11,J12. Among them, the assembly order of J11=J111, J12=J121,J122, materials is first J11 and then J12, cabin collection M=M1,M2. Assuming that the cabin load is 0 at the initial stage, the comparison of the cruise ship outfitting material plan, the cruise ship outfitting material assembly plan, and the total segment outfitting produced by the two plans are shown in Figure 1.Figure 1
Sequential contrast diagram.Although the completion timemaxTf1jk of all outfitting material processes in Option 1 is 3 working hours, which is 1 working hour longer than maxTf1jk in Option 2; however, the outfitting material assembly completion time Bmax of Option 1 is 5 man-hours, which is 1 man-hour less than the corresponding Bmax of Option 2. This is because each outfitting material in scheme 1 is assembled after the production is completed, and the waiting time for the material to be assembled is less, while in scheme 2, it is always in the placed state after the completion of J12. It does not conform to the principle of reasonable distribution of materials, and neither has an effect on the assembly, and the completed and unassembled materials also occupy the space on the ship. That is to say, the shortest total time belongs to the local optimum for the problem of ship outfitting materials scheduling, and the problem solving needs to take the shortest service completion time of the total segment as the optimization goal. Therefore, the optimization of the scheduling of cruise ship outfitting materials is not only the study of the flexible shipboard material scheduling problem but also the optimization of the problem of combining the assembly order of the outfitting and the order of material assembly.


### 2.2. Model Symbols and Descriptions

J represents a collection of outfitting parts to be assembled, J=Ji∣i=1,2,⋯,n, n represents the total number of outfitting pieces, and the total outfitting order is fixed.Ji represents the ith outfitting piece to be made, which is composed of ai materials, and the assembly order of materials is fixed.Jij represents the jth waiting material of outfitting Ji. It is completed by aij multiple processes, and the process is fixed.Jijk represents the kth process of material Jij.M represents the collection of material cabins in the area, M=Me∣e=1,2,⋯,m, m is the total number of cabins.Me represents the eth cabin.xijket is a decision variable indicating whether process Jijk is assembled by cabin Me, and xijket=1 means that process Jijk is performing assembly operation on cabin Me at time t; otherwise, xijket=0.Tfijke represents the time it takes for cabin Me to complete process Jijk.Tsijk represents the start time of process Jijk.Tfijk represents the end time of process Jijk.Tfmin represents the minimum time for all outfitting materials to be completed; the mathematical expression of the problem is
(1)Tfmin=minTfijk,which indicates the minimum starting time of all outfitting materials to be processed:(2)Tsmin=minTsijk.


### 2.3. Mathematical Model

The problem of material scheduling on cruise ship outfitting is similar to the typical two-dimensional layout problem, that is, the material arrangement of cabins in the time domain, including the distribution of material cabins and the time arrangement of materials. The problem decision variable isxijket. For the assembly-oriented material coordination scheduling problem, the goal is to minimize the total outfitting completion time Tf.The assembly-oriented material scheduling provides input for the assembly process, that is, this article ignores the delivery time of the material, and the completion time is the arrival time of the material.The mathematical expression of the problem is(3)T=minTfn.Restrictions are as follows:(4)∑t∑i∑j∑k∑exijkte=1,∀i,j,k,e,t,(5)Tsijk≥Tfijk−1,∀i,j,k,(6)∑t∑i∑j∑kwijkt=1,∀i,j,k,t,(7)tsij≥Tfij,∀i,j,(8)tsij≥tfij,e,∀i,j.Formula (3) is the objective function, that is, the shortest service completion time of the total segment. Formula (4) indicates that only one outfitting material assembly sequence can be selected for one process operation in the same cabin at the same time. Formula (5) indicates that the materials must be carried out in a certain order; problem solving also needs to satisfy the constraints (6)–(8).


## 2.1. Problem Description

The problem of dispatching materials on cruise ship outfitting can be expressed as there aren outfitting parts, each outfitting part is composed of several materials, and each material is formed by a number of sequential processes, these procedures must be completed in m cabins, and at least one cabin can be selected for each procedure. Consider the assembly sequence of outfitting parts, the multiple assembly sequence of materials and equipment material constraints, as well as the sequence of materials and material constraints, with the goal of optimizing the service completion time of the total section, sort the order of the material cabin and corresponding cabin.The assembly time of outfitting parts corresponding to the shortest outfitting material time is not necessarily the shortest. For example, perform the assembly of outfittingJ1=J11,J12. Among them, the assembly order of J11=J111, J12=J121,J122, materials is first J11 and then J12, cabin collection M=M1,M2. Assuming that the cabin load is 0 at the initial stage, the comparison of the cruise ship outfitting material plan, the cruise ship outfitting material assembly plan, and the total segment outfitting produced by the two plans are shown in Figure 1.Figure 1
Sequential contrast diagram.Although the completion timemaxTf1jk of all outfitting material processes in Option 1 is 3 working hours, which is 1 working hour longer than maxTf1jk in Option 2; however, the outfitting material assembly completion time Bmax of Option 1 is 5 man-hours, which is 1 man-hour less than the corresponding Bmax of Option 2. This is because each outfitting material in scheme 1 is assembled after the production is completed, and the waiting time for the material to be assembled is less, while in scheme 2, it is always in the placed state after the completion of J12. It does not conform to the principle of reasonable distribution of materials, and neither has an effect on the assembly, and the completed and unassembled materials also occupy the space on the ship. That is to say, the shortest total time belongs to the local optimum for the problem of ship outfitting materials scheduling, and the problem solving needs to take the shortest service completion time of the total segment as the optimization goal. Therefore, the optimization of the scheduling of cruise ship outfitting materials is not only the study of the flexible shipboard material scheduling problem but also the optimization of the problem of combining the assembly order of the outfitting and the order of material assembly.


## 2.2. Model Symbols and Descriptions

J represents a collection of outfitting parts to be assembled, J=Ji∣i=1,2,⋯,n, n represents the total number of outfitting pieces, and the total outfitting order is fixed.Ji represents the ith outfitting piece to be made, which is composed of ai materials, and the assembly order of materials is fixed.Jij represents the jth waiting material of outfitting Ji. It is completed by aij multiple processes, and the process is fixed.Jijk represents the kth process of material Jij.M represents the collection of material cabins in the area, M=Me∣e=1,2,⋯,m, m is the total number of cabins.Me represents the eth cabin.xijket is a decision variable indicating whether process Jijk is assembled by cabin Me, and xijket=1 means that process Jijk is performing assembly operation on cabin Me at time t; otherwise, xijket=0.Tfijke represents the time it takes for cabin Me to complete process Jijk.Tsijk represents the start time of process Jijk.Tfijk represents the end time of process Jijk.Tfmin represents the minimum time for all outfitting materials to be completed; the mathematical expression of the problem is
(1)Tfmin=minTfijk,which indicates the minimum starting time of all outfitting materials to be processed:(2)Tsmin=minTsijk.


## 2.3. Mathematical Model

The problem of material scheduling on cruise ship outfitting is similar to the typical two-dimensional layout problem, that is, the material arrangement of cabins in the time domain, including the distribution of material cabins and the time arrangement of materials. The problem decision variable isxijket. For the assembly-oriented material coordination scheduling problem, the goal is to minimize the total outfitting completion time Tf.The assembly-oriented material scheduling provides input for the assembly process, that is, this article ignores the delivery time of the material, and the completion time is the arrival time of the material.The mathematical expression of the problem is(3)T=minTfn.Restrictions are as follows:(4)∑t∑i∑j∑k∑exijkte=1,∀i,j,k,e,t,(5)Tsijk≥Tfijk−1,∀i,j,k,(6)∑t∑i∑j∑kwijkt=1,∀i,j,k,t,(7)tsij≥Tfij,∀i,j,(8)tsij≥tfij,e,∀i,j.Formula (3) is the objective function, that is, the shortest service completion time of the total segment. Formula (4) indicates that only one outfitting material assembly sequence can be selected for one process operation in the same cabin at the same time. Formula (5) indicates that the materials must be carried out in a certain order; problem solving also needs to satisfy the constraints (6)–(8).


## 3. Improved Genetic Algorithm Design

### 3.1. Algorithm Strategy

Because of its versatility, the genetic algorithm has achieved many excellent results in solving the problem of material scheduling on flexible ships, and its crossover and mutation methods have a large operating space for solving large-scale problems, which is convenient for cruise ships with multiple outfits. Calculate the material scheduling problem on the outfitting ship. In this paper, combining the characteristics of material dispatching on cruise ship outfitting, a staged population initialization method oriented to the assembly sequence of outfitting parts and a directional mutation method oriented to the assembly sequence is proposed.


### 3.2. Coding Method

Because of the ship outfitting material scheduling problem, which is mainly composed of cabin selection problems and process sequencing problems, the corresponding codes are mainly the double-chain coding of the cabin selection chain and the process sequence chain. Each individual is composed of the cabin selection chain and the process sequence chain. The cabin selection chain and the process sequence chain are both an array whose length is equal to the sum of all processes of all materials to be processed.Due to the inflexibility of the process, the data corresponding to the process sequence chain only needs to record the material number and the sequence number of the process can be obtained by decoding.The cabin selection chain records the cabins corresponding to the corresponding positions of the process sequence chain, and the initialization of the cabin selection chain precedes the sequence of the processes.Take 2 outfitting parts (outfitting parts, 2 materials for eachJ1 and J2, 2 processes for each material, 2 cabins to choose from) as an example, a certain double-stranded encoding is shown in Table 1.Table 1
Examples of double-stranded encoding.
Process sequence chainJ12J11J21J22J11J21J12J22Cabin selection chain12121122The process sequence chain adopts the method of encoding the outfitting materials and calculating the process during decoding, instead of directly adopting the method of process encoding, which can effectively avoid the situation of infeasible solutions in genetic operations.


### 3.3. Parameter Selection

The selection of algorithm parameters will affect the final calculation results, but the selection of main parameters has been well studied [27]. The parameters are determined as the values that are easy to obtain good solutions in combination with the scale of the problem:Heuristic factorα=2, which indicates the relative importance of pheromone quantity in guiding ant colony search. If it is too large or too small, it is easy to fall into local optimization.Expected heuristic factorβ=3, indicating the relative importance of heuristic information.Volatilization factorρ=0.2, indicating the volatilization rate of pheromone in the iterative process.The number of ants isk=100. Too few ants will reduce the global search ability of the algorithm, and too many ants will weaken the positive feedback of pheromone.


### 3.4. Population Initialization

Simple traversal cannot obtain a better solution in a reasonable time, and the material scheduling problem on flexible ships is an NP-hard problem [28]. For solving large-scale problems, the quality of the initial population is very important for subsequent iterative calculations. The subsequent genetic operations are also based on the continuous cross-mutation of the initial population. Population initialization is the starting point for calculation and optimization. The initial population needs to take into account a certain degree of randomness, uniformity, and directionality.


#### 3.4.1. Cabin Selection Chain Initialization

Without the choice of cabin, it is impossible to determine the start time corresponding to the process by cabin load, so first, initialize the cabin selection chain. The initial model of the cabin selection chain is a combination of global search, local search, and random search, which realizes the complementary advantages of random and regular, global, and local. Random selection is to randomly select one from the selectable machines. Global search is similar to local search, except that there are differences in the selection of outfitting materials and the calculation of cabin load.


#### 3.4.2. Process Sequence Chain Initialization

After the selection of the process sequence chain is completed, the solution to the problem of dispatching materials on the cruise ship outfitting can be formed, and the solution to the problem is to minimize the service completion time of the total segment as the goal. The process sequence subproblem does not have a separate and strict objective function, but it is necessary to consider the influence of the outfitting sequence of the cruise ship outfitting parts in the process sequence chain initialization. The initialization and assignment of the process sequence chain need to consider the influence of the subsequent genetic and mutation operations on the process sequence chain to avoid infeasible solutions. Data corresponding to the process sequence chain is the outfitting number and material number, and the process corresponding number is obtained by decoding. This paper combines the heuristic algorithm and the principle of reasonable allocation of materials to initialize the process sequence chain; combines active scheduling, no delay scheduling, and completely random initial; and proposes a phased population initialization method for the assembly sequence of outfitting parts. The population initialization method is composed of three initialization modes: the phased active scheduling initialization mode for outfitting assembly sequence, the phased nondelay scheduling initialization mode for outfitting assembly sequence, and the random initializing mode. The specific steps of the phased active scheduling initialization method for the assembly sequence of outfitting parts are shown in Algorithm1.Algorithm 1: Phased active scheduling initialization steps for the assembly sequence of outfitting parts.
1 Execute strict initial population generation method2 Create a set of to-be-produced proceduresG composed of the first to-be-processed combinations of all outfitting materials3foritoTdo4   Calculate the minimum timeTfmin according to formula (1)5   Extract the cabins with the earliest completion time of to construct a set of cabins to be startedR.6ifR is not unique then7         selectj from the cabin Mi>Tfmin8end9   select a process fromC10ifG not empty do11return skep412end13end


### 3.5. Genetic Manipulation

#### 3.5.1. Cross-Operation

(1) Cabin Selection Chain Cross. Because the set of cabins that can be selected for each process is different, the cabin selection chains of different processes cannot be crossed, that is, genes at the same position in different cabin selection chains cannot be directly crossed, but the cabin selections of the same process of different individuals with the same workpiece can be crossed, that is, the cabin selection chain crossing based on the process, the cabin selection chain crossing steps are shown in Algorithm 2.Algorithm 2: Steps of cabin selection chain crossing method.
1:For each individual in population:2:   new Population = new array;2:If crossover Rate>random:3:secondParent=selectParent;4:offspring=crossoverindividual,secondParent;5:         new Population. push(offspring);6:Else:7:         new Population. push(individual);8:End if9:End(2) The Process Sequence Chain Is Crossed. The cross-operation of the sequence chain will produce an infeasible solution randomly, so it is necessary to cross the sequence chain according to rules. Good research results have been achieved on crossover rules, which are typical of linear order crossover [29] and priority operation crossover [30], both of which can well avoid the problem of infeasible solutions.Combined with a small example of the two crossways, assume 1 outfitting pieces (only one outfit, so code omitted fittings), the outfit has four materials, and these four materials, respectively, have 2, 3, 2, and 1, linear order crossover steps as shown in Table2.Table 2
Linear order cross steps.
StepContentStep1Two paternal individualsP1 were selected from two pairs of randomly selected paternal individuals by means of roulette 4,1,2,2,3,1,3 (representing the sequence of process 1 of no. 4 material, process 1 of no. 1 material, process 1 of no. 2 material, process 2 of no. 2 material, process 1 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material) and P2 {3,2,1, 4}, replication generates two new individuals C1{4,1,2,2,3,1,3} and C2{3,2,1,3,2,1,4}Step2Randomly select two positionsk1 and k2 in the sequence chain of the process, and k1<k2, take k1=3, k2=7 as an exampleStep3The gene fragment {2,2,3,1,3} betweenk1 and k2 in P1 was intercepted, and the corresponding procedure of each element in the gene fragment was found in C2 and deleted one by one. After deletion, C2 became X,X,1,X,X,4. After the intercepted gene fragment {2,2,3,1,3} was successively filled in the blank position of C2.C2 becomes {2,2,1,3,1,3,4}Step4Truncate the gene fragment {1,3,2,1,4} betweenk1 and k2 in P2, find the corresponding process from C1 and delete it. After deletion, C1 becomes X,X,2,X,3,X,X, and fill the blank position of C1successively with the truncated gene fragment {2,3,1,2,3}. C1 becomes {1,3,2,2,3,1,4};Step5P1, P2, C1 and C2 were substituted into the populationThe specific steps of priority operation crossover are shown in Table3.Table 3
Priority operation interleaved steps.
StepContentStep1Two paternal individualsP1 and P2, were selected from two pairs of randomly selected paternal individuals by roulette, taking P1 {4,1,2,2,3,1,3} and P2{3,2,1,3,2,1,4} as examplesStep2To build two new not assignment of individualC1X,X,X,X,X,X,X and C2X,X,X,X,X,X,XStep3Workpiece set A and B are randomly divided, taking workpiece set A containing no. 1 and no. 3 and workpiece set B containing no. 2 and no. 4 as an exampleStep4The fragments ofP1 in workpiece set A are put into C1 according to P1 position, and C1 becomes X,1,X,X,3,1,3. The process of P2 in A is put into C2 according to P2 position, and C2 becomes 3,X,1,3,X,1,XStep5The fragments of P2 in workpiece set B are put intoC1 in P2 order, and C1 becomes {2,1,2,4,3,1,3}. The process of P1 in B is put into C2 in P1 position, and C2 becomes {3,4,1,3,2,1}Step6P1, P2, C1, and C2were substituted into the population.In order to obtain more possible optimal solutions, this paper adopts a combination of linear order crossover and preferential choice crossover on cruise outfitting ships.


#### 3.5.2. Mutation Operation

The variation operation can also be divided into the variation of the cabin selection chain and the variation of the process sequence chain.(1) Cabin Selection Chain Variation. The cabin selection chain variation can be adopted by single point variation, which is simple to calculate and has no influence on the machine selection and process sequence chain variation of other segments, so the cabin selection chain variation is carried out first in the calculation. The variation operation of the compartment selection chain is the process of randomly selecting outfitting materials, and the machine corresponding to the selected process is changed into another random machine that can be used for this process.(2) Variation of Process Sequence Chain. The reverse mutation is a relatively mature method in the existing process of sequence chain mutation, which is simple and does not produce infeasible solutions. The reverse mutation is a process in which two genes are randomly selected from a sequence and all genes in between are switched.Since there is too much randomness in reverse variation, in order to improve the quality of the solution, this paper proposes an assembly sequence-oriented directional variation method based on the reverse variation method combined with the assembly characteristics of outfitting parts. For the convenience of expression, the directional variation factorZij is defined to represent the relative probability that processes in the outfitting material Jij are selected in the directional variation reordering process:
(9)Zij=5i+1j.In order to enlarge the search scope of the solution, the method of material scheduling optimization for the assembly-oriented cruise outfitting ship adopts the combination of reverse mutation and oriented mutation for assembly sequence. When the gene fragments of the process sequence chain are exchanged, the gene fragments corresponding to the compartment selection chain should also be exchanged in the same way to prevent the occurrence of infeasible solutions.


#### 3.5.3. Select Operation

Because crossover operation and mutation operation produce new solutions, it is necessary to select the population by the survival of the fittest. While some solutions are eliminated according to certain random rules, excellent solutions in the population should be retained to ensure that excellent solutions can be iterated all the time, in order to obtain better solutions. The specific implementation method is as follows: Parent individual fitness value, namely, the total period of service completion time, the parent individuals from high to low is sorted according to the fitness value, to select the fitness value of the highest part of the parent individual directly into the offspring population, namely, elite save way, the rest of the parent individual carried out in accordance with the way of roulette wheel selection, namely, the individual fitness value, the higher the probability of individual preserved, The lower the individual fitness value, the easier it is to be eliminated. This paper chooses the combination of elite preservation and roulette, which not only saves excellent individuals but also ensures the global search.


#### 3.5.4. Genetic Algorithm Parameters

The main parameters and influences of genetic algorithm are as follows:(1)
Population numberP represents the population size. If the population size is too large, the computing speed will slow down; if the population size is too small, the search range of the solution will be affected(2)
The number of cyclesNamax, which is a simple condition for the termination of calculation during iteration. The calculation will be stopped after a certain number of iterations(3)
Crossover probabilityPc which means the probability of crossover between individuals during genetic operation. If the probability is too small, it is not easy to produce new solutions, while if the probability is too large, the computing speed will be slowed down(4)
Mutation probabilityPm, which means the probability of individual mutation during genetic operation should not be too large or too small(5)
Global search probabilityPo, which represents the probability of selecting global search method during initialization of cabin selection chain(6)
Local search probabilityPp, which represents the probability of using local search method during initialization of cabin selection chain(7)
Pa, the initialization probability of phased active scheduling for outfitting assembly sequence, represents the probability of combining active scheduling with initialization of process sequence chain(8)
Pb of stage-by-stage delayless scheduling initialization probability for outfitting assembly sequence, which represents the probability of combining delayless scheduling with process sequence chain initialization


### 3.6. Problem Decoding

Genetic algorithm for iterative calculation of population individuals is an accommodation choice in the form of a combination of chain and chain operation sequence, is not the result of intuitive, and needs accommodation choice of chain and chain operation sequence double-stranded data into the form of a Gantt chart, check the start time and end time of each artifact, and cabin number and other information, and then converted to outfitting materials, assembly time, and fittings assembly time. The individual fitness value is calculated according to the outfitting assembly time, and then, other operations of genetic algorithm are completed, and the final results are displayed visually.A simple4×3 typical example is taken as an example to illustrate the decoding method of the material scheduling problem on the outfitting ship of cruise ship. The data of the 4×3 typical example is shown in Table 4:Table 4
Data table of typical examples.
Correspond to machine and timeStepStepM1 (h)M2(h)M3(h)J11J111453J112223J113132J12J121362J122423J123434J13J131122J132457J133242J14J141325J142142J143435An individual compartment selection chain in the example is {3,1,2,3,2,1,2,3,2,1,3,1}, and the corresponding process sequence chain is {2,4,3,1,2,3,2,4,4,1,3,1} (this problem is a single outfitting, so the outfitting number in the process sequence chain code is omitted). The chain operation sequence of the first genetic representation is 1 to 2 workpiece processes by the 3 machines and the corresponding time is 2 hours, and the corresponding Gantt chart said the first 3 machines for 2 # 1 process of workpiece, a second gene said second artifact for 4 1 process in no. 1 compartment, but because of no. 1 compartment without load. The first procedure and the second procedure of the procedure sequence chain can be carried out at the same time, that is, the procedure can be carried out at the earliest possible time in the corresponding compartment without affecting other procedures, and the rest of the gene fragments can draw a complete material assembly Gantt diagram according to the relationship between the procedures and the load of the compartment. The corresponding Gantt diagram of a material assembly is shown in Figure2 (the outfitting number is omitted from the figure).Figure 2
Solution results of a typical example.Based on this Gantt diagram, combined with the assembly sequence of cruise outfitting parts, the assembly scheme of cruise outfitting materials and the total outfitting scheme are generated.In some cases, a better solution can be obtained by intervening in the sequence of operations. There is still room for optimization in the plan of cruise outfitting materials generated by direct decoding. On the premise of meeting the pretightening and posttightening relationship between workpiece processes and not having multiple loads in the cabin, a process can be moved left or right, and a better solution can be obtained in some cases. Figure3 is taken as an example.Figure 3
Outfitting material scheme of cruise ship before intervention.As shown in Figure4, process no. 3 of workpiece no. 4 can be moved to the left in advance (process no. 1 of workpiece no. 2 can also be moved in advance, for the same reason, it will not be described again).Figure 4
Outfitting material scheme of the cruise ship after intervention.This reduces the maximum time from 18 hours to 16 hours, and no. 4 workpiece can be assembled earlier.


### 3.7. Fitness Calculation

Individuals in the population are double-chained codes, and individual fitness values need to be calculated for survival of the fittest. The steps are shown in Table5.Table 5
Calculation procedure of fitness value.
StepContentStep1Initialize cabin loadStep2Selection of the next sequence of the sequence of the gene segmentStep3According to the gene fragment in the compartment selection chain of the corresponding position, the process compartment is selected, combined with the corresponding cabin working hours and the start and end time of the compartment load generation processStep4Judge whether the process selection chain is traversed. If so, generate the outfitting material scheme, enter Step5, return to Step2Step5Select the nearest assembling material setT according to the assembly sequence of outfitting materialsStep6Generate outfitting material assembly scheme and general outfitting schemeStep7The total outfitting completion timeTf was taken as the fitness value


## 3.1. Algorithm Strategy

Because of its versatility, the genetic algorithm has achieved many excellent results in solving the problem of material scheduling on flexible ships, and its crossover and mutation methods have a large operating space for solving large-scale problems, which is convenient for cruise ships with multiple outfits. Calculate the material scheduling problem on the outfitting ship. In this paper, combining the characteristics of material dispatching on cruise ship outfitting, a staged population initialization method oriented to the assembly sequence of outfitting parts and a directional mutation method oriented to the assembly sequence is proposed.


## 3.2. Coding Method

Because of the ship outfitting material scheduling problem, which is mainly composed of cabin selection problems and process sequencing problems, the corresponding codes are mainly the double-chain coding of the cabin selection chain and the process sequence chain. Each individual is composed of the cabin selection chain and the process sequence chain. The cabin selection chain and the process sequence chain are both an array whose length is equal to the sum of all processes of all materials to be processed.Due to the inflexibility of the process, the data corresponding to the process sequence chain only needs to record the material number and the sequence number of the process can be obtained by decoding.The cabin selection chain records the cabins corresponding to the corresponding positions of the process sequence chain, and the initialization of the cabin selection chain precedes the sequence of the processes.Take 2 outfitting parts (outfitting parts, 2 materials for eachJ1 and J2, 2 processes for each material, 2 cabins to choose from) as an example, a certain double-stranded encoding is shown in Table 1.Table 1
Examples of double-stranded encoding.
Process sequence chainJ12J11J21J22J11J21J12J22Cabin selection chain12121122The process sequence chain adopts the method of encoding the outfitting materials and calculating the process during decoding, instead of directly adopting the method of process encoding, which can effectively avoid the situation of infeasible solutions in genetic operations.


## 3.3. Parameter Selection

The selection of algorithm parameters will affect the final calculation results, but the selection of main parameters has been well studied [27]. The parameters are determined as the values that are easy to obtain good solutions in combination with the scale of the problem:Heuristic factorα=2, which indicates the relative importance of pheromone quantity in guiding ant colony search. If it is too large or too small, it is easy to fall into local optimization.Expected heuristic factorβ=3, indicating the relative importance of heuristic information.Volatilization factorρ=0.2, indicating the volatilization rate of pheromone in the iterative process.The number of ants isk=100. Too few ants will reduce the global search ability of the algorithm, and too many ants will weaken the positive feedback of pheromone.


## 3.4. Population Initialization

Simple traversal cannot obtain a better solution in a reasonable time, and the material scheduling problem on flexible ships is an NP-hard problem [28]. For solving large-scale problems, the quality of the initial population is very important for subsequent iterative calculations. The subsequent genetic operations are also based on the continuous cross-mutation of the initial population. Population initialization is the starting point for calculation and optimization. The initial population needs to take into account a certain degree of randomness, uniformity, and directionality.


### 3.4.1. Cabin Selection Chain Initialization

Without the choice of cabin, it is impossible to determine the start time corresponding to the process by cabin load, so first, initialize the cabin selection chain. The initial model of the cabin selection chain is a combination of global search, local search, and random search, which realizes the complementary advantages of random and regular, global, and local. Random selection is to randomly select one from the selectable machines. Global search is similar to local search, except that there are differences in the selection of outfitting materials and the calculation of cabin load.


### 3.4.2. Process Sequence Chain Initialization

After the selection of the process sequence chain is completed, the solution to the problem of dispatching materials on the cruise ship outfitting can be formed, and the solution to the problem is to minimize the service completion time of the total segment as the goal. The process sequence subproblem does not have a separate and strict objective function, but it is necessary to consider the influence of the outfitting sequence of the cruise ship outfitting parts in the process sequence chain initialization. The initialization and assignment of the process sequence chain need to consider the influence of the subsequent genetic and mutation operations on the process sequence chain to avoid infeasible solutions. Data corresponding to the process sequence chain is the outfitting number and material number, and the process corresponding number is obtained by decoding. This paper combines the heuristic algorithm and the principle of reasonable allocation of materials to initialize the process sequence chain; combines active scheduling, no delay scheduling, and completely random initial; and proposes a phased population initialization method for the assembly sequence of outfitting parts. The population initialization method is composed of three initialization modes: the phased active scheduling initialization mode for outfitting assembly sequence, the phased nondelay scheduling initialization mode for outfitting assembly sequence, and the random initializing mode. The specific steps of the phased active scheduling initialization method for the assembly sequence of outfitting parts are shown in Algorithm1.Algorithm 1: Phased active scheduling initialization steps for the assembly sequence of outfitting parts.
1 Execute strict initial population generation method2 Create a set of to-be-produced proceduresG composed of the first to-be-processed combinations of all outfitting materials3foritoTdo4   Calculate the minimum timeTfmin according to formula (1)5   Extract the cabins with the earliest completion time of to construct a set of cabins to be startedR.6ifR is not unique then7         selectj from the cabin Mi>Tfmin8end9   select a process fromC10ifG not empty do11return skep412end13end


## 3.4.1. Cabin Selection Chain Initialization

Without the choice of cabin, it is impossible to determine the start time corresponding to the process by cabin load, so first, initialize the cabin selection chain. The initial model of the cabin selection chain is a combination of global search, local search, and random search, which realizes the complementary advantages of random and regular, global, and local. Random selection is to randomly select one from the selectable machines. Global search is similar to local search, except that there are differences in the selection of outfitting materials and the calculation of cabin load.


## 3.4.2. Process Sequence Chain Initialization

After the selection of the process sequence chain is completed, the solution to the problem of dispatching materials on the cruise ship outfitting can be formed, and the solution to the problem is to minimize the service completion time of the total segment as the goal. The process sequence subproblem does not have a separate and strict objective function, but it is necessary to consider the influence of the outfitting sequence of the cruise ship outfitting parts in the process sequence chain initialization. The initialization and assignment of the process sequence chain need to consider the influence of the subsequent genetic and mutation operations on the process sequence chain to avoid infeasible solutions. Data corresponding to the process sequence chain is the outfitting number and material number, and the process corresponding number is obtained by decoding. This paper combines the heuristic algorithm and the principle of reasonable allocation of materials to initialize the process sequence chain; combines active scheduling, no delay scheduling, and completely random initial; and proposes a phased population initialization method for the assembly sequence of outfitting parts. The population initialization method is composed of three initialization modes: the phased active scheduling initialization mode for outfitting assembly sequence, the phased nondelay scheduling initialization mode for outfitting assembly sequence, and the random initializing mode. The specific steps of the phased active scheduling initialization method for the assembly sequence of outfitting parts are shown in Algorithm1.Algorithm 1: Phased active scheduling initialization steps for the assembly sequence of outfitting parts.
1 Execute strict initial population generation method2 Create a set of to-be-produced proceduresG composed of the first to-be-processed combinations of all outfitting materials3foritoTdo4   Calculate the minimum timeTfmin according to formula (1)5   Extract the cabins with the earliest completion time of to construct a set of cabins to be startedR.6ifR is not unique then7         selectj from the cabin Mi>Tfmin8end9   select a process fromC10ifG not empty do11return skep412end13end


## 3.5. Genetic Manipulation

### 3.5.1. Cross-Operation

(1) Cabin Selection Chain Cross. Because the set of cabins that can be selected for each process is different, the cabin selection chains of different processes cannot be crossed, that is, genes at the same position in different cabin selection chains cannot be directly crossed, but the cabin selections of the same process of different individuals with the same workpiece can be crossed, that is, the cabin selection chain crossing based on the process, the cabin selection chain crossing steps are shown in Algorithm 2.Algorithm 2: Steps of cabin selection chain crossing method.
1:For each individual in population:2:   new Population = new array;2:If crossover Rate>random:3:secondParent=selectParent;4:offspring=crossoverindividual,secondParent;5:         new Population. push(offspring);6:Else:7:         new Population. push(individual);8:End if9:End(2) The Process Sequence Chain Is Crossed. The cross-operation of the sequence chain will produce an infeasible solution randomly, so it is necessary to cross the sequence chain according to rules. Good research results have been achieved on crossover rules, which are typical of linear order crossover [29] and priority operation crossover [30], both of which can well avoid the problem of infeasible solutions.Combined with a small example of the two crossways, assume 1 outfitting pieces (only one outfit, so code omitted fittings), the outfit has four materials, and these four materials, respectively, have 2, 3, 2, and 1, linear order crossover steps as shown in Table2.Table 2
Linear order cross steps.
StepContentStep1Two paternal individualsP1 were selected from two pairs of randomly selected paternal individuals by means of roulette 4,1,2,2,3,1,3 (representing the sequence of process 1 of no. 4 material, process 1 of no. 1 material, process 1 of no. 2 material, process 2 of no. 2 material, process 1 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material) and P2 {3,2,1, 4}, replication generates two new individuals C1{4,1,2,2,3,1,3} and C2{3,2,1,3,2,1,4}Step2Randomly select two positionsk1 and k2 in the sequence chain of the process, and k1<k2, take k1=3, k2=7 as an exampleStep3The gene fragment {2,2,3,1,3} betweenk1 and k2 in P1 was intercepted, and the corresponding procedure of each element in the gene fragment was found in C2 and deleted one by one. After deletion, C2 became X,X,1,X,X,4. After the intercepted gene fragment {2,2,3,1,3} was successively filled in the blank position of C2.C2 becomes {2,2,1,3,1,3,4}Step4Truncate the gene fragment {1,3,2,1,4} betweenk1 and k2 in P2, find the corresponding process from C1 and delete it. After deletion, C1 becomes X,X,2,X,3,X,X, and fill the blank position of C1successively with the truncated gene fragment {2,3,1,2,3}. C1 becomes {1,3,2,2,3,1,4};Step5P1, P2, C1 and C2 were substituted into the populationThe specific steps of priority operation crossover are shown in Table3.Table 3
Priority operation interleaved steps.
StepContentStep1Two paternal individualsP1 and P2, were selected from two pairs of randomly selected paternal individuals by roulette, taking P1 {4,1,2,2,3,1,3} and P2{3,2,1,3,2,1,4} as examplesStep2To build two new not assignment of individualC1X,X,X,X,X,X,X and C2X,X,X,X,X,X,XStep3Workpiece set A and B are randomly divided, taking workpiece set A containing no. 1 and no. 3 and workpiece set B containing no. 2 and no. 4 as an exampleStep4The fragments ofP1 in workpiece set A are put into C1 according to P1 position, and C1 becomes X,1,X,X,3,1,3. The process of P2 in A is put into C2 according to P2 position, and C2 becomes 3,X,1,3,X,1,XStep5The fragments of P2 in workpiece set B are put intoC1 in P2 order, and C1 becomes {2,1,2,4,3,1,3}. The process of P1 in B is put into C2 in P1 position, and C2 becomes {3,4,1,3,2,1}Step6P1, P2, C1, and C2were substituted into the population.In order to obtain more possible optimal solutions, this paper adopts a combination of linear order crossover and preferential choice crossover on cruise outfitting ships.


### 3.5.2. Mutation Operation

The variation operation can also be divided into the variation of the cabin selection chain and the variation of the process sequence chain.(1) Cabin Selection Chain Variation. The cabin selection chain variation can be adopted by single point variation, which is simple to calculate and has no influence on the machine selection and process sequence chain variation of other segments, so the cabin selection chain variation is carried out first in the calculation. The variation operation of the compartment selection chain is the process of randomly selecting outfitting materials, and the machine corresponding to the selected process is changed into another random machine that can be used for this process.(2) Variation of Process Sequence Chain. The reverse mutation is a relatively mature method in the existing process of sequence chain mutation, which is simple and does not produce infeasible solutions. The reverse mutation is a process in which two genes are randomly selected from a sequence and all genes in between are switched.Since there is too much randomness in reverse variation, in order to improve the quality of the solution, this paper proposes an assembly sequence-oriented directional variation method based on the reverse variation method combined with the assembly characteristics of outfitting parts. For the convenience of expression, the directional variation factorZij is defined to represent the relative probability that processes in the outfitting material Jij are selected in the directional variation reordering process:
(9)Zij=5i+1j.In order to enlarge the search scope of the solution, the method of material scheduling optimization for the assembly-oriented cruise outfitting ship adopts the combination of reverse mutation and oriented mutation for assembly sequence. When the gene fragments of the process sequence chain are exchanged, the gene fragments corresponding to the compartment selection chain should also be exchanged in the same way to prevent the occurrence of infeasible solutions.


### 3.5.3. Select Operation

Because crossover operation and mutation operation produce new solutions, it is necessary to select the population by the survival of the fittest. While some solutions are eliminated according to certain random rules, excellent solutions in the population should be retained to ensure that excellent solutions can be iterated all the time, in order to obtain better solutions. The specific implementation method is as follows: Parent individual fitness value, namely, the total period of service completion time, the parent individuals from high to low is sorted according to the fitness value, to select the fitness value of the highest part of the parent individual directly into the offspring population, namely, elite save way, the rest of the parent individual carried out in accordance with the way of roulette wheel selection, namely, the individual fitness value, the higher the probability of individual preserved, The lower the individual fitness value, the easier it is to be eliminated. This paper chooses the combination of elite preservation and roulette, which not only saves excellent individuals but also ensures the global search.


### 3.5.4. Genetic Algorithm Parameters

The main parameters and influences of genetic algorithm are as follows:(1)
Population numberP represents the population size. If the population size is too large, the computing speed will slow down; if the population size is too small, the search range of the solution will be affected(2)
The number of cyclesNamax, which is a simple condition for the termination of calculation during iteration. The calculation will be stopped after a certain number of iterations(3)
Crossover probabilityPc which means the probability of crossover between individuals during genetic operation. If the probability is too small, it is not easy to produce new solutions, while if the probability is too large, the computing speed will be slowed down(4)
Mutation probabilityPm, which means the probability of individual mutation during genetic operation should not be too large or too small(5)
Global search probabilityPo, which represents the probability of selecting global search method during initialization of cabin selection chain(6)
Local search probabilityPp, which represents the probability of using local search method during initialization of cabin selection chain(7)
Pa, the initialization probability of phased active scheduling for outfitting assembly sequence, represents the probability of combining active scheduling with initialization of process sequence chain(8)
Pb of stage-by-stage delayless scheduling initialization probability for outfitting assembly sequence, which represents the probability of combining delayless scheduling with process sequence chain initialization


## 3.5.1. Cross-Operation

(1) Cabin Selection Chain Cross. Because the set of cabins that can be selected for each process is different, the cabin selection chains of different processes cannot be crossed, that is, genes at the same position in different cabin selection chains cannot be directly crossed, but the cabin selections of the same process of different individuals with the same workpiece can be crossed, that is, the cabin selection chain crossing based on the process, the cabin selection chain crossing steps are shown in Algorithm 2.Algorithm 2: Steps of cabin selection chain crossing method.
1:For each individual in population:2:   new Population = new array;2:If crossover Rate>random:3:secondParent=selectParent;4:offspring=crossoverindividual,secondParent;5:         new Population. push(offspring);6:Else:7:         new Population. push(individual);8:End if9:End(2) The Process Sequence Chain Is Crossed. The cross-operation of the sequence chain will produce an infeasible solution randomly, so it is necessary to cross the sequence chain according to rules. Good research results have been achieved on crossover rules, which are typical of linear order crossover [29] and priority operation crossover [30], both of which can well avoid the problem of infeasible solutions.Combined with a small example of the two crossways, assume 1 outfitting pieces (only one outfit, so code omitted fittings), the outfit has four materials, and these four materials, respectively, have 2, 3, 2, and 1, linear order crossover steps as shown in Table2.Table 2
Linear order cross steps.
StepContentStep1Two paternal individualsP1 were selected from two pairs of randomly selected paternal individuals by means of roulette 4,1,2,2,3,1,3 (representing the sequence of process 1 of no. 4 material, process 1 of no. 1 material, process 1 of no. 2 material, process 2 of no. 2 material, process 1 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material, process 2 of no. 1 material, process 2 of no. 3 material) and P2 {3,2,1, 4}, replication generates two new individuals C1{4,1,2,2,3,1,3} and C2{3,2,1,3,2,1,4}Step2Randomly select two positionsk1 and k2 in the sequence chain of the process, and k1<k2, take k1=3, k2=7 as an exampleStep3The gene fragment {2,2,3,1,3} betweenk1 and k2 in P1 was intercepted, and the corresponding procedure of each element in the gene fragment was found in C2 and deleted one by one. After deletion, C2 became X,X,1,X,X,4. After the intercepted gene fragment {2,2,3,1,3} was successively filled in the blank position of C2.C2 becomes {2,2,1,3,1,3,4}Step4Truncate the gene fragment {1,3,2,1,4} betweenk1 and k2 in P2, find the corresponding process from C1 and delete it. After deletion, C1 becomes X,X,2,X,3,X,X, and fill the blank position of C1successively with the truncated gene fragment {2,3,1,2,3}. C1 becomes {1,3,2,2,3,1,4};Step5P1, P2, C1 and C2 were substituted into the populationThe specific steps of priority operation crossover are shown in Table3.Table 3
Priority operation interleaved steps.
StepContentStep1Two paternal individualsP1 and P2, were selected from two pairs of randomly selected paternal individuals by roulette, taking P1 {4,1,2,2,3,1,3} and P2{3,2,1,3,2,1,4} as examplesStep2To build two new not assignment of individualC1X,X,X,X,X,X,X and C2X,X,X,X,X,X,XStep3Workpiece set A and B are randomly divided, taking workpiece set A containing no. 1 and no. 3 and workpiece set B containing no. 2 and no. 4 as an exampleStep4The fragments ofP1 in workpiece set A are put into C1 according to P1 position, and C1 becomes X,1,X,X,3,1,3. The process of P2 in A is put into C2 according to P2 position, and C2 becomes 3,X,1,3,X,1,XStep5The fragments of P2 in workpiece set B are put intoC1 in P2 order, and C1 becomes {2,1,2,4,3,1,3}. The process of P1 in B is put into C2 in P1 position, and C2 becomes {3,4,1,3,2,1}Step6P1, P2, C1, and C2were substituted into the population.In order to obtain more possible optimal solutions, this paper adopts a combination of linear order crossover and preferential choice crossover on cruise outfitting ships.


## 3.5.2. Mutation Operation

The variation operation can also be divided into the variation of the cabin selection chain and the variation of the process sequence chain.(1) Cabin Selection Chain Variation. The cabin selection chain variation can be adopted by single point variation, which is simple to calculate and has no influence on the machine selection and process sequence chain variation of other segments, so the cabin selection chain variation is carried out first in the calculation. The variation operation of the compartment selection chain is the process of randomly selecting outfitting materials, and the machine corresponding to the selected process is changed into another random machine that can be used for this process.(2) Variation of Process Sequence Chain. The reverse mutation is a relatively mature method in the existing process of sequence chain mutation, which is simple and does not produce infeasible solutions. The reverse mutation is a process in which two genes are randomly selected from a sequence and all genes in between are switched.Since there is too much randomness in reverse variation, in order to improve the quality of the solution, this paper proposes an assembly sequence-oriented directional variation method based on the reverse variation method combined with the assembly characteristics of outfitting parts. For the convenience of expression, the directional variation factorZij is defined to represent the relative probability that processes in the outfitting material Jij are selected in the directional variation reordering process:
(9)Zij=5i+1j.In order to enlarge the search scope of the solution, the method of material scheduling optimization for the assembly-oriented cruise outfitting ship adopts the combination of reverse mutation and oriented mutation for assembly sequence. When the gene fragments of the process sequence chain are exchanged, the gene fragments corresponding to the compartment selection chain should also be exchanged in the same way to prevent the occurrence of infeasible solutions.


## 3.5.3. Select Operation

Because crossover operation and mutation operation produce new solutions, it is necessary to select the population by the survival of the fittest. While some solutions are eliminated according to certain random rules, excellent solutions in the population should be retained to ensure that excellent solutions can be iterated all the time, in order to obtain better solutions. The specific implementation method is as follows: Parent individual fitness value, namely, the total period of service completion time, the parent individuals from high to low is sorted according to the fitness value, to select the fitness value of the highest part of the parent individual directly into the offspring population, namely, elite save way, the rest of the parent individual carried out in accordance with the way of roulette wheel selection, namely, the individual fitness value, the higher the probability of individual preserved, The lower the individual fitness value, the easier it is to be eliminated. This paper chooses the combination of elite preservation and roulette, which not only saves excellent individuals but also ensures the global search.


## 3.5.4. Genetic Algorithm Parameters

The main parameters and influences of genetic algorithm are as follows:(1)
Population numberP represents the population size. If the population size is too large, the computing speed will slow down; if the population size is too small, the search range of the solution will be affected(2)
The number of cyclesNamax, which is a simple condition for the termination of calculation during iteration. The calculation will be stopped after a certain number of iterations(3)
Crossover probabilityPc which means the probability of crossover between individuals during genetic operation. If the probability is too small, it is not easy to produce new solutions, while if the probability is too large, the computing speed will be slowed down(4)
Mutation probabilityPm, which means the probability of individual mutation during genetic operation should not be too large or too small(5)
Global search probabilityPo, which represents the probability of selecting global search method during initialization of cabin selection chain(6)
Local search probabilityPp, which represents the probability of using local search method during initialization of cabin selection chain(7)
Pa, the initialization probability of phased active scheduling for outfitting assembly sequence, represents the probability of combining active scheduling with initialization of process sequence chain(8)
Pb of stage-by-stage delayless scheduling initialization probability for outfitting assembly sequence, which represents the probability of combining delayless scheduling with process sequence chain initialization


## 3.6. Problem Decoding

Genetic algorithm for iterative calculation of population individuals is an accommodation choice in the form of a combination of chain and chain operation sequence, is not the result of intuitive, and needs accommodation choice of chain and chain operation sequence double-stranded data into the form of a Gantt chart, check the start time and end time of each artifact, and cabin number and other information, and then converted to outfitting materials, assembly time, and fittings assembly time. The individual fitness value is calculated according to the outfitting assembly time, and then, other operations of genetic algorithm are completed, and the final results are displayed visually.A simple4×3 typical example is taken as an example to illustrate the decoding method of the material scheduling problem on the outfitting ship of cruise ship. The data of the 4×3 typical example is shown in Table 4:Table 4
Data table of typical examples.
Correspond to machine and timeStepStepM1 (h)M2(h)M3(h)J11J111453J112223J113132J12J121362J122423J123434J13J131122J132457J133242J14J141325J142142J143435An individual compartment selection chain in the example is {3,1,2,3,2,1,2,3,2,1,3,1}, and the corresponding process sequence chain is {2,4,3,1,2,3,2,4,4,1,3,1} (this problem is a single outfitting, so the outfitting number in the process sequence chain code is omitted). The chain operation sequence of the first genetic representation is 1 to 2 workpiece processes by the 3 machines and the corresponding time is 2 hours, and the corresponding Gantt chart said the first 3 machines for 2 # 1 process of workpiece, a second gene said second artifact for 4 1 process in no. 1 compartment, but because of no. 1 compartment without load. The first procedure and the second procedure of the procedure sequence chain can be carried out at the same time, that is, the procedure can be carried out at the earliest possible time in the corresponding compartment without affecting other procedures, and the rest of the gene fragments can draw a complete material assembly Gantt diagram according to the relationship between the procedures and the load of the compartment. The corresponding Gantt diagram of a material assembly is shown in Figure2 (the outfitting number is omitted from the figure).Figure 2
Solution results of a typical example.Based on this Gantt diagram, combined with the assembly sequence of cruise outfitting parts, the assembly scheme of cruise outfitting materials and the total outfitting scheme are generated.In some cases, a better solution can be obtained by intervening in the sequence of operations. There is still room for optimization in the plan of cruise outfitting materials generated by direct decoding. On the premise of meeting the pretightening and posttightening relationship between workpiece processes and not having multiple loads in the cabin, a process can be moved left or right, and a better solution can be obtained in some cases. Figure3 is taken as an example.Figure 3
Outfitting material scheme of cruise ship before intervention.As shown in Figure4, process no. 3 of workpiece no. 4 can be moved to the left in advance (process no. 1 of workpiece no. 2 can also be moved in advance, for the same reason, it will not be described again).Figure 4
Outfitting material scheme of the cruise ship after intervention.This reduces the maximum time from 18 hours to 16 hours, and no. 4 workpiece can be assembled earlier.


## 3.7. Fitness Calculation

Individuals in the population are double-chained codes, and individual fitness values need to be calculated for survival of the fittest. The steps are shown in Table5.Table 5
Calculation procedure of fitness value.
StepContentStep1Initialize cabin loadStep2Selection of the next sequence of the sequence of the gene segmentStep3According to the gene fragment in the compartment selection chain of the corresponding position, the process compartment is selected, combined with the corresponding cabin working hours and the start and end time of the compartment load generation processStep4Judge whether the process selection chain is traversed. If so, generate the outfitting material scheme, enter Step5, return to Step2Step5Select the nearest assembling material setT according to the assembly sequence of outfitting materialsStep6Generate outfitting material assembly scheme and general outfitting schemeStep7The total outfitting completion timeTf was taken as the fitness value


## 4. Case Verification

Using the same example, the improved method in this paper was compared with the method in Zhang [30] and the genetic algorithm using the initial method of the Kacem [31] rule. The algorithm parameters were the same (the population was 1000, the number of cycles was 200, the crossover probability was 0.8, and the mutation probability was 0.05). The mean comparison based on the 100 additional examples was shown in Table 6 and Figure 5.Table 6
Comparison table of instance data.
Question number1234567Outfitting informationn108121515206Count(Ji)73656611012614849Count(Jij)242198187294384410144m10101012121510Count(Eij)2312182426368S12224341S263381032r66877106ZhangMIN(Bmax)104734112217414053AVG(Bmax)110784413118314755Me430270122492906965131AVG(t)1462699322134216291410355KacemMIN(Bmax)102644111617013455AVG(Bmax)107744312317914052Me4152751195028861386133AVG(t)1553770370153218171563383The improvement method proposed in this paperMIN(Bmax)95654011816513349AVG(Bmax)99714112517713351Me340219101394740488104AVG(t)1135599297119614031240289Figure 5
Comparison of instance data.
(a)
Optimal value comparison chart(b)
The highest quality mean comparison chart(c)
Memory consumption comparison chart(d)
Calculation time comparison chartTable6 with Me said memory, AVG (t) calculates the meantime, as you can see from the Table 6, improved algorithm in this paper, in most cases the optimal value calculation ability is better than the contrast algorithm, the optimal value of the mean is better than the comparison algorithm, and in terms of memory and computing time compared with the contrast algorithm has large improvement: The optimal value is improved by about 5%, the mean value of optimal value is improved by about 7% ~10%, the mean value of occupied memory is improved by about 17% ~20%, and the mean value of calculation time is improved by about 30%, which verifies the stability and effectiveness of the fitting-oriented construction material scheduling optimization method calculated by stages in this paper.


## 5. Conclusion

This paper mainly on the cruise ship outfitting the ship cabin choice and process scheduling problems are studied, based on the idea of phase calculation and material distribution; fittings assembly sequence was proposed and the phases of the population initialization method and way for assembly sequence directional variation, on the basis of design for assembly of cruise ship outfitting ship supplies scheduling method. According to the improved genetic algorithm, the space with a high probability of optimal solution is searched, which improves the solving ability of the fitting-oriented optimization method of construction materials scheduling on cruise outfitting ships. The effectiveness of the fitting-oriented optimization method is verified by an example and then improves the overall assembly efficiency of cruise ship. In the future, it is planned to further extend the research of this paper to the next operation, build an evaluation system of assembly sequence, and improve the real-time response ability of cruise outfitting workshop in the construction process.



---

*Source: 3451408-2022-06-25.xml*