The flexible job shop scheduling problem (FJSP) widely exists in the modern manufacturing workshop and is becoming more and more important. For FJSP, an operation can selected to be machined by a set of machines instead of one. Therefore, two sub-problems, namely machine selection and operations sequencing must be determined. Moreover, FJSP has proved to be an NP-hard problem ^[1][2][1,2]. In real production, there is a certain distance between different machines. The jobs must be transformed by automatic guided vehicles (AGVs) from machines to machines. Due to the high price of AGVs and the workshop layout, the number of AGVs is limited. The FJSP with a limited number of AGVs (FJSP-AGV) is much nearer to real production than FJSP and very important. Compared with FJSP, FJSP-AGV should solve three sub-problems, namely the machine selection sub-problem, the AGV selection sub-problem, and the operations sequencing sub-problem. Therefore, FJSP-AGV is a much more difficult NP-hard problem than FJSP [3].

The genetic algorithm (GA) is inspired by the process of natural selection and has been widely implemented to solve shop scheduling problems ^[4][5][4,5]. Moreover, GA shows good effectiveness for solving FJSP ^[6][7][6,7] and therefore, can be used for solving FJSP-AGV. With regard to the classical GA, the diversity of the population decreases with the algorithm iteration, and some individuals can become extremely similar, even identical, causing stagnation of population evolution. In order to overcome this problem, an improved GA (IGA) with a population diversity check method was specifically designed. Comparison experiments of benchmark instances were conducted to evaluate the effectiveness and efficiency of IGA. What is more, the proposed IGA can update the current best solutions of 34 benchmark instances.

2. GA for Solving FJSP

Job shop scheduling problem (JSP) is the basis of FJSP, and does not consider the flexibility of machine selection. With minimizing makespan of JSP, Zhang et al. ^[8][17] proposed an effective hybrid GA, Xie et al. ^[9][18] developed a new improved GA that combines GA and tabu search (TS), and Goncalves et al. designed a random-key based GA. With regard to FJSP with minimizing makespan, Pezzella et al. ^[10][19] designed a GA with different rules for generating individuals, Zhang et al. proposed a combined GA that takes variable neighborhood search into consideration, Gutiérrez et al. designed a hybrid GA that combines GA and repair heuristics, and Fan et al. ^[11][20] developed an improved genetic algorithm, in which problem-specific encoding and decoding strategies are designed.

3. FJSP-AGV

JSP with a limited number of AGV is named as JSP-AGV. With regard to JSP-AGV, the existing works have been focused on minimizing makespan. Bilge and Ulusoy ^[12][21] designed an iterative algorithm and a set of benchmark instances. Erol et al. ^[13][22] developed a multi-agent-based algorithm, which includes four agents, namely manager agent, staff agent, AGV agent, machine agent, and AGV-machine resource agents. Deroussi et al. ^[14][23] designed a novel neighboring method, which includes three intelligent algorithms, namely iterated local search, simulated annealing, and their hybridization. Kumar et al. ^[15][24] developed a novel differential evolution algorithm, whose encoding only considers the operations sequencing sub-problem. Moreover, the machine selection sub-problem and the AGV selection sub-problem are determined in the decoding with specific heuristics. Zheng et al. ^[16][25] designed a tabu search algorithm and first presented a mixed integer linear programming (MILP) model to obtain optimal solutions. Fontes and Homayouni ^[17][26] proposed an improved MILP by considering more constraints for minimizing makespan of JSP-AGV. Abdelmaguid et al. ^[18][27] proposed a hybrid GA/heuristic approach, while the heuristic is to determine the AGV selection in the decoding scheme. Lacomme et al. ^[19][28] designed a disjunctive graph-based framework for modeling JSP-AGV and an improved memetic algorithm. Ham ^[20][29] first developed a constraint programming model and a new set of benchmark instances. In order to simultaneously optimize makespan, mean flow time, and mean tardiness of JSP-AGV, an improved multi-objective GA was designed ^[21][30], which determines the AGV selection sub-problem in the decoding. With regard to JSP-AGV simultaneously making makespan, AGV travel time, and minimized penalty cost, a multi-objective GA was designed, which used the fuzzy expert system to adjust crossover operators ^[22][31]. With consideration of the battery charge of AGV, three intelligent algorithms, namely GA, particle swarm optimization (PSO), and hybrid GA-PSO were developed to simultaneously make makespan with the number of AGV being minimized ^[23][32]. With only one AGV in a flexible manufacturing system, Caumond et al. ^[24][33] proposed a MILP for scheduling problems. Moreover, the maximum number of jobs, the limited input/output buffer capacities, and the no-move-ahead trips were taken into consideration simultaneously. With regard to FJSP-AGV on minimizing makespan, Ham ^[20][29] extended the constraint programming model of JSP-AGV and proved the optimality of ten benchmark instances ^[25][34]. Homayouni and Fontes [3] proposed the first MILP model for solving small-sized instances to optimality and a local search-based heuristic for solving small to large-sized instances. Chaudhry et al. ^[26][35] presented a Microsoft Excel spreadsheet-based solution and GA, and Homayouni et al. ^[27][11] proposed a multi-start biased random key genetic algorithm (BRKGA). In BRKGA, the encoding only considers the operations sequencing sub-problem, and the machine selection and AGV selection sub-problems are determined by several different greedy heuristics. Zhang et al. ^[28][36] designed a hybrid algorithm GATS that combines GA and tabu search algorithm (TS) for minimizing makespan and of FJSP-AGV with bounded processing times. In GATS, the GA decides the machine-AGV selections of all operations and TS optimizes the operations sequencing. In order to fast and accurately estimate the makespan of FJSP-AGV, Cheng et al. ^[29][37] designed an adaptive ensemble model of back propagation neural networks. Yan et al. ^[30][38] first studied the FJSP-AGV in a digital twin workshop and developed a three-layer -encoding based GA. Moreover, in order to implement the optimized schedules to a digital twin system, an entity-JavaScript Object Notation method was designed. As we know, Li et al. ^[31][12] first studied dynamic FJSP-AGV with simultaneously minimizing makespan and total energy consumption and developed a hybrid deep Q network (HDQN)-based dynamic scheduling method.