An Improved Genetic Algorithm for Solving the Mixed?Flow Job?Shop Scheduling Problem with Combined Processing Constraints

，，，，

1.College of Mechanical and Electrical Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，P.R.China；2.Jiangsu Automation Research Institute，Lianyungang 222006，P.R.China

Abstract: The flexible job-shop scheduling problem（FJSP）with combined processing constraints is a common scheduling problem in mixed-flow production lines. However，traditional methods for classic FJSP cannot be directly applied. Targeting this problem，the process state model of a mixed-flow production line is analyzed. On this basis，a mathematical model of a mixed-flow job-shop scheduling problem with combined processing constraints is established based on the traditional FJSP. Then，an improved genetic algorithm with multi-segment encoding，crossover，and mutation is proposed for the mixed-flow production line problem. Finally，the proposed algorithm is applied to the production workshop of missile structural components at an aerospace institute to verify its feasibility and effectiveness.

Key words：mixed-flow production；flexible job-shop scheduling problem（FJSP）；genetic algorithm；encoding

0 Introduction

With the increasingly diversified demands，the production mode of manufacturing enterprises has continuously evolved into multi-variety and smallbatch production. More and more manufacturing en?terprises are applying mixed-line production lines in flexible job-shops. However， the flexibility of mixed-flow shops increases the difficulty of schedul?ing，thus traditional methods for the classic flexible job-shop scheduling problem（FJSP）cannot be di?rectly adapted to those mixed-flow job-shops.

FJSP is a fundamental problem in manufactur?ing. It is a generalization of the job-shop scheduling problem（JSP）［1］that removes the limitation of the unique machine specified in each operation and con?cerns the processing flexibility［2］. In the past few de?cades，experts and scholars have conducted many studies on FJSPs and developed various solution methodologies［3］. Most researchers assumed that a machine cannot process more than one operation at a certain time［4］and only needs to meet the conven?tional routing constraints. However，in many cases，in order to ensure the accuracy of assembly，several jobs must be processed simultaneously on the same machine，i.e.，combined processing. Combined pro?cessing is a processing technology that clamps two or more parts in accordance with the assembly rela?tionship by using the same reference and processes the related operations in one single chucking. This technology can enssure the accuracy of assembly，reduce the difficulty of processing and improve the working efficiency. It has been widely used in the production of high precision components，like the manufacturing of various molds and shell parts. The scheduling problem in these job-shops is exactly a FJSP with combined processing constraints. In this problem，some machines can process multiple oper?ations of different jobs at the same time. Moreover，in addition to meeting the conventional routing con?straints，it is also necessary to meet the combined processing constraints between different jobs.Therefore，it is of great significance and practical value to establish the model of FJSPs with com?bined processing constraints.

Although FJSPs with combined processing constraints widely exist in real-world job-shops，there is few literature about this problem. Some have studied the hybrid flow shop scheduling prob?lem. Ribas et al.［5］presented an extensive review on hybrid flow shop scheduling problems. Engin et al.［6］proposed an effective genetic algorithm to mini?mize the makespan time. They adopted a new muta?tion operator and the best values of the control pa?rameters to solve the hybrid flow shop scheduling with the multiprocessor task problem. Seidgar et al.［7］presented a new bi-objective mixed integer pro?gramming model for the two-stage assembly flow shop scheduling problem with preventive mainte?nance activities，and employed the non-dominated ranking genetic algorithm to find the pareto-optimal front for large sized problems. Pan et al.［8］present?ed a discrete artificial bee colony algorithm with an efficient initialization scheme and a self-adaptive strategy for generating neighboring food sources to solve the lot-streaming flow shop scheduling prob?lem. Ye et al.［9］proposed an effective shuffled frogleaping algorithm to solve the hybrid flow-shop scheduling problem with identical parallel machines.Dios et al.［10］proposed a set of heuristics that cap?tures some special features of the missing operations to address the hybrid flow shop scheduling problem for makespan minimization. Compared with FJSPs，the hybrid flow shop scheduling problem lacks flexi?bility.

At present，genetic algorithms（GAs）are the most commonly used methods to solve FJSPs. Ka?cem［11］proposed a generic algorithm to apply ad?vanced genetic manipulations to solve a FJSP. Pez?zella et al.［12］presented a genetic algorithm for a FJSP by integrating different strategies for a gener?ating the initial population，selecting the individuals for reproduction and reproducing new individuals.Kacem et al.［13］put forward a generic algorithm to build an ideal assignment model to solve a FJSP.Gao et al.［14］developed a hybrid GA with advanced crossover and mutation operators for solving the multi-objective FJSP. Ishikawa et al.［15］proposed the hierarchical multi-space competitive distributed GA to find an optimal solution for a FJSP with a low computational cost. Zhang et al.［16］proposed an improved non-dominated sorting genetic algorithm（NSGA-Ⅱ）with an extended operation-based en?coding and an active scheduling decoding mecha?nism to solve the FJSP.

There are some other heuristic algorithms to solve FJSPs. Gao et al.［17］proposed an improved ar?tificial bee colony algorithm to solve the FJSP with fuzzy processing time. Others use hybrid algorithms to solve FJSPs. Li et al.［18］proposed an effective hy?brid algorithm to hybridize the GA and tabu search for the FJSP with the objective of minimizing the makespan. Rey et al.［19］proposed a novel meta-heu?ristics algorithm by combining GA with particle swam optimization（PSO）to find adequate job re?lease times to meet specific due dates. Xia et al.［20］developed an easily implemented hybrid approach for the multi-objective FJSP，which combined a PSO algorithm and simulated annealing （SA）.Dong et al.［21］built a related disjunctive graph mod?el and proposed a hybrid GA -ant colony optimiza?tion to solve a FJSP more effectively. These above methods are very efficient in solving classical FJSPs，but cannot be applied to mixed-line jobshops directly.

For mixed-flow assembly lines，Xiong［22］re?searched the scheduling problem of assemblies in JSP. Lu et al.［23］employed an improved NSGA-Ⅱmulti-target heritage algorithm to optimize the Ushaped mixed-flow assembly line. None of the above methods can provide a good solution for mixed-flow shop scheduling with combined machin?ing constraints. Wang et al.［24］presented the optimi?zation of a mixed production line based on the logic intelligent reasoning method and GA. But this meth?od can only solve the ranking length of the mixedflow production line.

In order to solve the FJSP with combined pro?cessing constraints for mixed-flow job-shops，the process state model of the mixed-flow production line is analyzed. On this basis，a mathematical mod?el of the FJSP with combined processing constraints is established. Then，an improved GA with multisegment encoding，crossover，and mutation is pro?posed to deal with the mixed-flow production line scheduling problem. Finally，the proposed algo?rithm is applied to the missile structure production workshop of an aerospace research institute，and the feasibility and effectiveness of the method are veri?fied.

The rest of the paper is organized as follows：In Section 1 the mixed-flow JSP with combined pro?cessing constraint is defined in detail and then the mathematical model and a multi-part GA is ex?plained in Section 2 and Section 3.Simulation exper?iments are presented in Section 4 and the conclu?sions are drawn in Section 5.

1 Mixed?Flow Job?Shop Schedul?ing Problem with Combined Pro?cessing Constraints

The traditional FJSP is described as follows：A manufacturing system is equipped with several machines to process several workpieces. Each work?piece has several operations with a sequential con?straint relationship. The operation numbers of these workpieces are different with each other and each operation can be processed on one or more ma?chines. The goal of scheduling is to select an appro?priate machine and an appropriate processing se?quence for each operation to improve the whole sys?tem’s performance.

However，in the process of mixed-flow produc?tion line，there are not only components but also as?semblies combined by two or more components.Therefore，different from the manufacturing system only with components，there are also combined op?erations such as assembly operation and combined processing operation. This section analyzes the mod?el of process state in the mixed-flow production line，as shown in Fig.1. Fig.1（a）depicts the flow of assembly operation，whereJ1andJ2represent two components belonging to the same assembly；andOijrepresents thejth operation of theith compo?nent. These two components first carry out their op?erations separately，and then conduct their assembly operation.O12&O23represents the assembly opera?tion，whereJ1andJ2are processed at the same time.Fig.1（b）displays the flow of combination process?ing operation，whereJ3andJ4represent two compo?nents belonging to the same assembly. These two components first carry out their operations separate?ly，and then exert the next operation ofJ3andJ4that needs to be processed on the same machine at the same time. Moreover，O33andO43can start process?ing only afterO32andO43are finished.

Fig.1 Process state model

In order to research the scheduling problem of the mixed-flow production line in the flexible jobshop，we expand the traditional FJSP into a FJSP for the mixed-flow production line. It is described as follows.

A number of machines are arranged in a manu?facturing system to produce several assemblies.Each assembly contains two or more components.Each component contains several operations with se?quential constraints（including assembly operation，combined processing operation）. The operation numbers of these components are different and each operation can be processed on one or more ma?chines. The goal of scheduling is to select the appro?priate processing unit for each operation，and select the appropriate processing sequence for the opera?tions assigned to each processing unit，so as to opti?mize the whole system’s performance.

In this paper，the maximum due time is taken as the optimization goal，and the following assump?tions are made.

（1）There is no processing priority between as?semblies.

（2）There is no preparation time for each oper?ation.

（3）The transportation time between the ma?chines is set to a fixed value.

（4）Each machine can only work on one com?ponent or one assembly at the same time.

2 Mathematical Model of Mixed?Flow Job?Shop Scheduling Prob?lem

For the convenience of illustrating the mathe?matical model，the variables to be used are defined as follows.

NC：The number of assemblies；

NCi：The number of components of theith as?sembly；

NCij：The number of operations in thejth com?ponent of theith assembly；

NM：The number of machines；

Gi：Theith assembly；

Jij：Thejth component of theith assembly；

Oijk：Thekth operation in thejth component of theith assembly；

Mm：Themth machine；

Ci：The completion time of theith assembly；

Cij：The completion time of thejth component of theith assembly；

tsijk：The start processing time of thekth opera?tion in thejth component of theith assembly；

toijk：The end processing time of thekth opera?tion in thejth component of theith assembly；

msmn：The start processing time of thenth oper?ation in themth machine；

momn：The end processing time of thenth opera?tion in themth machine；

tijkm：The processing time of thekth operation in thejth component of theith assembly；

tt：The transporting time.

The constraints are as follows

Among these equations，Eq.（1）implies that each operation in each component of each assembly can only be processed by one machine. Eq.（2）shows that if the current operation is a separate oper?ation，this operation will start only after its previous operation ends，and if the current operation is a com?bined operation，its starting time needs to consider all the related components of the same assembly in?cluding completion time and shipping time. Eq.（3）indicates that each machine can only start the next operation after the current operation ends. Eq.（4）il?lustrates that the processing time is determined by the corresponding processing machine.

This paper considers the max completion time as the decision variable，written asCand defined as

The optimization target is minimizing the max completion time，defined as

3 A Multi?part GA

GA is an algorithm of computational intelli?gence that simulates the process of natural selection and survival of the fittest，which is able to obtain the feasible solution of the problem. It has a good global search capability and is widely used in the field of production scheduling.

GA is widely used in solving the traditional FJSP. In the process of GA encoding in the tradi?tional FJSP，the chromosome is divided into two parts：Process chromosome and machine chromo?some. However，in the FJSP for the mixed-flow production line proposed in this paper，the usual en?coding way cannot express all the production infor?mation and should be improved.

To propose the multi-part GA，this paper mod?ifies the encoding，cross，mutation operations of the usual GA，and the other steps remain the same.The chromosome is divided into three parts：As?sembly process chromosome，component process chromosome and machine process chromosome.The cross and mutation are accordingly modified.

3.1 Flow of GA

First，several terms are introduced as follows.

Individual：A solution to the problem；

Population：A set of solutions to the problem；

Fitness：An indicator for judging how good a solution is；

Chromosome：A series of numbers containing information that represent individuals；

Gene：A digit in a chromosome that contains the basic information of an individual；

Encoding：The process of translating an chro?mosome to an individual；

Decoding：The inverse process of encoding；

Selection：An operation of the GA that simu?lates the natural selection；

Cross：An operation of the GA that simulates natural reproduction；

Mutation：An operation of the GA that simu?lates natural variation.

The flow of the GA is shown in Fig.2.

Fig.2 Flow of GA

Step 1Analyze the problems to be solved and summarize the characteristics of the problems.

Step 2According to the characteristics of practical problems， the coding and decoding schemes are designed to associate the mathematical model of the problem with the GA.

Step 3Set the population size and select a random initialization method to initialize the chromo?some population.

Step 4Decode the chromosomes in the popu?lation and evaluate the fitness value of chromo?somes.

Step 5Judge whether the algorithm meets the termination condition according to the popula?tion fitness value. If not，go to Step 6；Otherwise，end the algorithm and output the optimal solution.

Step 6Perform the selection step on the pop?ulation，so that the chromosomes with high fitness survives to the next generation，and the chromo?somes with low fitness is eliminated. Commonly used selection methods are binary tournament，rou?lette，etc.

Step 7Select some chromosomes according to the crossover probability and perform crossover operation according to the set rules.

Step 8According to the mutation probability and the set rules，select some chromosomes for mu?tation operation，and set the mutation probability generally by the idea of simulated annealing.

Step 9Generate the next generation popula?tion，and go to Step 5.

3.2 Multi?segment encoding

The encoding way divides the chromosome in?to three parts.（1）Assembly process chromosome

In this part，each gene represents an assembly index. The count of each assembly index indicates the total operation numbers of the assembly. The or?der number that each gene appears in the corre?sponding assembly index sequence means the order number of an assembly operation. This part is used to determine the order of processing in the level of assembly，and its length equals to the total number of all operations.

（2）Component process chromosome

In this part，each assembly has a corresponding assembly sub-chromosome. In each assembly subchromosome，each gene represents a component in?dex. The count of each component index indicates the total operation numbers of the component. The order number that each gene appears in the corre?sponding component index sequence means the or?der number of a component operation. This part is used to determine the order of processing in the lev?el of component，and its length equals to the total number of all operations.

（3）Machine chromosome

In this part，each gene represents a machine in?dex. The index of the machine selected for each pro?cessing is in the set of optional machines. This part is used to determine the machine of each process?ing，and the length also equals to the total number of all operations.

Therefore，in this encoding way，the length of each chromosome is three times of the total number of operations.

Taking the problem with two assemblies and four machines as an example. Table 1 contains all of the assembly information，and the symbol“—”indi?cates that the corresponding process cannot be pro?cessed on the corresponding machine. Among these operations，O112andO123is a pair of combination process，andO212andO222is another pair of combi?nation process. In Table 1，the processing informa?tion of each pair of combination process is identical.

Table 1 Processing information of two assemblages and four machines

The encoding of the chromosome is shown in Fig.3. The assembly process chromosome［1 2 1 2 2 2 1 2 2 1］and the part process chromosome［2 1 2 3 | 1 2 3 1 2 1］together determine the order of processing in the system，that is，O121→O211→O111→O221→O212&O222→O213→O122→O223→O214→O112&O123. The machine chromosome［3 2 4 1 | 1 2 2 3 2 1］represents that operationO111is processed onM3，operationO121is processed onM2，operationO112is processed onM4，O112&O123is processed onM1，and so on.

Fig.3 Diagram of chromosome

This encoding way is able to represent all the feasible solutions of the FJSP for the mixed-flow production line without generating any illegal solu?tion，and it facilitates the subsequent cross and mu?tation.

3.3 Population initialization and multi?segment cross

In order to increase the diversity of the initial population，this paper initializes the population in a random way，and selects the next generation in a bi?nary tournament way.

Since the chromosome is divided into three parts and they are different from each other，each part needs to cross separately. Firstly，the coeffi?cient of crosskis defined as the ratio of the number of the genes learned by the individual to the total number of the genes in the chromosome. Then，ac?cording to the probability of cross，two chromo?somes P1 and P2 are randomly selected. Fig.4 shows the selected two chromosomes.

Fig.4 Diagram of the chosen chromosomes

3.3.1 Cross of assembly process chromosomes

The assembly process chromosome of the two parental chromosomes are P11 and P21. As shown in Fig.5，firstly，the length of P11 and the coeffi?cient of cross are multiplied to get the length of crossL11. The process number of P21 and the coeffi?cient of cross are multiplied to get the length of crossL21. In this example，L11= 2，L21=2. Then，two genes are selected from the genes ofG1at loca?tion［1 3 7 10］in P11. Two genes are selected from the genes ofG2at location［2 4 5 6 8 9］in P11. In Fig.5，genes at location［3，7］and genes at location［5，8］are chosen and the genes to cross of P11 are at location［3 5 7 8］. In the same way，the genes to cross of P21 are at location［2 3 5 7］. Finally，the genes are exchanged to cross of P11 and P21 and ob?tain the child chromosomes S11 and S21 are ob?tained.

Fig.5 Cross procedure between general operation parts

3.3.2 Cross of component process chromosomes

The component process chromosomes of the two parental chromosomes are P121，P122，P221，P222. The way of cross is basically the same as that of the assembly process chromosomes，but there are still two differences：

（1）The genes that represent assembly process?es do not need to cross；

（2）The cross of component process chromo?somes needs to be segmented.

The cross of P121 and P221 are taken as exam?ples，as shown in Fig.6. In this example，the index of assembly process is 3 and it will not participate in cross.

Fig.6 Cross procedure between combined operation parts

3.3.3 Cross of machine chromosomes

Due to the difference of constraints，the cross of the machine chromosomes is different with that of the process chromosomes. As shown in Fig.7，first?ly，the length of P13 or P23 and the coefficient of cross are multiplied to get the length of cross. In this example，L3=4. Then，four genes are selected from the genes of the machine chromosomes. In Fig.7，genes at location［2 5 7 8］of P13 and P23 are chosen to cross. Finally，exchange the genes are exchanged to cross of P13 and P23 and obtain the child chromosomes S13 and S23.

Fig.7 Cross procedure between machine parts

3.4 Mutation

The role of mutation is to avoid getting the al?gorithm into local optimum. In this paper，the way of mutation is designed using the idea of simulated annealing. That is，the probability of mutation is rel?atively high at the beginning，but it gradually goes down along with the increase of the generation.

The concreate way of mutation is as follows.For assembly process chromosomes and component process chromosomes，it selects two genes random?ly and exchanges them，as shown in Figs.8，9. For machine chromosomes，it randomly selects a pro?cess and randomly re-selects the corresponding ma?chine from the optional machine set，as shown in Fig.10. Hill function is selected to describe the prob?ability of mutation

Fig.10 Mutation procedure between machine parts

whereirepresents the state before mutation；jthe state after mutation；F(i) the fitness at stateI；F（j）the fitness at statej. In Eq.（8），AandBare the parameters of the algorithm，andtmeans the generation.

Fig.8 Mutation procedure between assembly parts

Fig.9 Mutation procedure between operation parts

4 Case Study

The aerospace institute in Shanghai is a scien?tific research institute that undertakes the research and production of aircraft. The production workshop of missile structural components under its jurisdic?tion is responsible for the manufacture of various structural parts. The products of workshop are com?plex components，and the processing process is completed in a flexible operation mode. Therefore，the processing of production can be described as a FJSP for a mixed-flow production line.

There are four workshops in this factory，in which the ordinary lathing machines and the ordi?nary milling machines are arranged in workshop 1，the computer numerical control（CNC）lathing ma?chines are arranged in workshop 2，the numerical control milling machines are arranged in workshop 3，and the fitters are arranged in workshop 4. The machine information in the case is shown in Table 2.

Table 2 Information of machines

There are five assemblies in this case. Their processing information is shown in Table 3 and their processing flows are shown in Fig.11. Here，the transporting time is considered as a constant be?cause it is much smaller than the processing time.

Fig.11 Diagram of the processing flows

Table 3 Data in the case

The size of the generation is 100. The max iter?ation is 100. The probability of cross is 0.8. The co?efficient of cross is 0.4. The parameter of simulated annealing A is 0.6 and that of B is 10.

The learning curve is shown in Fig.12. It can be seen that the oscillation of the learning curve is very large at first，and then gradually decreases.The mutation operator in the form of simulated an?nealing plays an important role in this process. Final?ly，the algorithm converges at the 40th generation.

Fig.12 Change of makespan during evolution

The optimal scheduling solution to the FJSP for the mixed-flow production line of the missile structural component obtained by the proposed algo?rithm is shown in Fig.13 where the vertical axis is the number of machines，and the horizontal is the time line.O212&O222represent combined processing operation.O413&O422，O314&O323，O415&O424，O113&O124，O514&O524represent the assembly op?erations. The completion time of the task is 42. It can be seen that the result satisfies the constraints of assembly and combined processing. So the proposed algorithm is feasible.

Fig.13 Gatt of the solution

In some studies，dispatching rules are usually applied to guide workshop scheduling. It generally consists of two stages：Machine selection and buffer job sequencing. It needs to arrange proper machine and buffer job sequencing. The machine selection rules are shortest queue（SQ）and shortest process?ing time（SPT）. The buffer job sequencing rules are：First in first out（FIFO）and shortest job first（SJF）. The final combined dispatching rules include SPT + FIFO and SQ + SJF. Compared with the above dispatching rules，the results in Table 4 show that the scheduling solution obtained by the im?proved GA has shorter completion time.

Table 4 Comparison between various methods

5 Conclusions

This paper studies the flexible job-shop sched?uling for the mixed-flow production line. Firstly，the process state model of the mixed-flow produc?tion line is analyzed. Secondly，a mathematical mod?el of FJSP for the mixed-flow production line is es?tablished. Thirdly，for the above model，a multipart GA with multi-segment encoding is designed.Finally，the proposed algorithm is applied to the production workshop of missile structural compo?nents at an aerospace institute to verify its feasibility and effectiveness.

Future research directions include designing more efficient initialization mechanism for the pro?posed multi-part GA，and considering more optimi?zation targets for FJSPs in mixed-flow production lines.