{'fraction_non_alphanumeric': 0.025811929526639778, 'fraction_numerical': 0.007514328168117173, 'mean_word_length': 4.837918215613383, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Research on the model and algorithm of the flexible operation sequence of the first-level maintenance in the EMU depot

Most of the first-level maintenance of Electric Multiple Unit (EMU) adopts the form of fixed sequence operation, known as “washing-maintenance”. Because of the limitation of the line capacity and the inconsistent arrival time of EMUs, a fixed sequence operation may give rise to such problems as longer waiting time, idle lines and waste of maintenance capacity. To solve these problems, a non-linear integer model with a flexible operational sequence of the first-level maintenance of the EMU depot is proposed in this paper. The proposed model aims at minimizing the latest completion time, taking into account the constraints such as the operation sequence of the same EMU, the limitation of simultaneous operation on the same line and the time requirement for EMU to enter and leave the yard. In the proposed model, genetic algorithm is employed. To a further level, in this paper, an application of the proposed model used in Taiyuan EMU depot is presented. With a comparison of two modes, namely, the fixed sequence mode and the fixed sequence plus manual washing mode, the case of the application by Taiyuan EMU depot provides the verification for the feasibility and validity of the model proposed. The result of the application suggests that the flexible operation sequence mode bring about improvement with regard to reducing waiting time, optimizing line utilization, shortening the latest completion time, and enhancing both working efficiency and ability of the first-level maintenance.


INTRODUCTION
China's High-speed Railway (CHR) is developing rapidly, and the number of EMUs running on the line is huge. In recent years, more and more EMUs need to undergo corresponding maintenance, thus, the maintenance capability has gradually become one of the main reasons affecting the use of EMUs. In China, the maintenance of EMUs is divided into five levels according to their running time and mileage. As the key link for the daily maintenance of EMUs, the first-level maintenance of EMUs directly affects the number of available EMUs, and its efficiency has become the focus of industry attention. Therefore, a reasonable operation sequence plan is of great significance to shorten the operation time, improve the line utilization rate and the efficiency of the train station.
Scholars have done some research on the daily maintenance of EMUs, and the optimization of the maintenance operation plan of EMUs is often expressed as the job shop scheduling problem (JSP).  [1] considered the correlation between processes when studying traditional JSP problems, and added a new correlation arc to represent the process correlation when using the disjunctive graph model. Ju L Y et al [2] proposed an improved genetic algorithm based on Pareto-level adaptive mutation operator and elite retention strategy for multi-objective flexible workshop job scheduling. Tong J N et al. [3] considered the length of the train, converted the first-level maintenance operation of EMUs into a flow-shop problem, and solved the optimization model based on the genetic algorithm. Wang J X et al. [4] set up an integer programming model with the minimum number of shunting hooks as the goal of the first-level repair operation process of EMUs. The model focused on obtaining the optimal shunting operation plan and it is solved based on the particle swarm optimization algorithm. Guo X L et al. [5] set the shunting operation planning and optimization model as the goal of minimizing the total delay time of the shunting operation of EMUs, and solved the model based on the micro-evolution and operation line allocation algorithm. LI H D et al. [6] considered the double positions of the maintenance track and established an ETT model to analyze the effect of the allocation of EMU-to-track in different types of yards on the operating efficiency. LIN B L et al [7] established a 0-1 programming model for the high-level maintenance problem of EMUs, linearized the original nonlinear state function using linearization technology, and proposed a simulated annealing algorithm to solve large-scale examples. Pezzella F et al. [8] proposed a genetic algorithm which integrated more strategies into the genetic framework in order to solve the flexible job shop scheduling problem (FJSP). Aghajani A. [9] designed a non-dominated sorting genetic algorithm (NSGAII) to find its Pareto optimal solution for the JSP considering the dual objective of minimum total completion time and the reliability of system. Fan K et al. [10] addressed the multi-processor job-shop scheduling problem(MTJSP), used disjunctive formulation to construct the optimization model, and developed a Scatter Search (SS) based on the solution representation to solve the problem. Most of the current research focuses on how to adjust the sequence of EMUs under fixed operating sequence conditions to reduce delay time and maximize line utilization. There is little research on the sequence of operation processes and route arrangements of single EMU. Therefore, the contributions of this paper to the firstlevel maintenance problem are as follows.
(1) The operation sequence of a single EMU is considered, the first-level maintenance plan is abstracted as a flexible operation sequence scheduling problem. A mathematical model for first-level maintenance of EMUs based on integer programming modeling technology is proposed. This model not only considers the sequence of all EMUs, but also the sequence of the operating processes of single EMU.
(2) The applicability of the proposed methodology is proved by the actual instance of CHSR. In order to prove the effectiveness of the proposed method, a comparative analysis is performed with two other common first-level maintenance operation modes. Computational results indicate our method outperforms the other modes on both aspects of compressing waiting time and improving track utilization.
Therefore, this paper proposes a flexible operation sequence optimization model for the first-level maintenance sequence and operation process of EMUs. The rest of this paper is organized as follows. Section 2 gives a formal problem description for the first-level maintenance operation based on the flexible operation sequence. An integer programming model is proposed to mathematically describe the flexible operation sequence problem of the first-level maintenance in Section 3. Section 4 develops a solution based on genetic algorithms. A case of CHSR is selected to verify the proposed method in Section 5. In this section, we analyze and compare with two other traditional fixed sequence modes. Finally, conclusions and research prospects are drawn in Section 6.

PROBLEM DESCRIPTION
The EMU depot is the department responsible for checking the status of EMUs. Its main function is to ensure all the components of EMUs are in good condition. According to China's EMU maintenance regulations, the first-level maintenance of EMUs is a routine inspection of storage, which mainly has two operations: washing and maintenance. They are carried out on the washing track and the 3 maintenance track, respectively. For each EMU, washing and maintenance are actually independent of each other. Each EMU needs to complete these two operations, but the sequence is not mandatory. Therefore, this paper proposes a flexible operation sequence mode for the first-level maintenance of EMUs, that is, after entering the EMU depot, EMUs no longer follow the fixed "washing-maintenance" operation sequence, but instead choose one of the two operations. After completing one operation, EMUs go to another operation yard for corresponding operation. After completing all operations, EMUs will wait in the storage yard for use, as shown in Figure 1. Therefore, the optimization of the first-level maintenance operation can be described as follows. Under the constraints of the number of EMUs, the number of washing and maintenance tracks, the beginning and end time nodes of EMUs entering and leaving the depot, and the duration of each operation, the first-level maintenance of all EMUs can be completed in the shortest time by reasonably arranging the EMU-to-track, the operation sequence of EMUs and the process sequence of single EMU. In turn, it can improve the utilization rate of the track, reduce unnecessary waiting time of EMUs, and improve the first-level maintenance ability of the EMU depot.

MODEL FORMULATION FOR THE FIRST-LEVEL MAINTENANCE WITH THE FLEXIBLE OPERATION SEQUENCE
In this section, we present a non-linear integer programming model for solving r the first-level maintenance with the flexible operation sequence mode. We begin by emphasizing some assumptions made in this model. Assumption 1. The storage yard has enough tracks; Assumption 2. Each yard is a through-type yard, and EMUs can enter and leave the yard from the two throat areas without cross interference; Assumption 3. Due to the power of the EMU itself, there is no need for shunting locomotive, so the cost of the shunting operation of EMUs is not considered.

List of Notations
The notations used in the model are introduced in Tables 1 and 2

Objective Functions
The time for completing the first-level maintenance of each EMU is shown in formula (1). As shown in formula 2, the completion time of all EMUs is the completion time of the EMU that has completed the first-level maintenance at the latest. The optimization goal of this paper is to minimize the completion time of all EMUs, as shown in formula 3.

Constraints
The proposed model is subject to a number of constraints. We now introduce each of these in turn.

a) Constraints for the number and location of operations
Each EMU can only complete the corresponding operation on one track, and all EMUs should complete the corresponding operations.
International  (4) and (5) indicate that one EMU can only complete washing/maintenance operation on one washing/ maintenance track. Constraint (6) and (7) indicate that there are n EMUs in total that need to finish washing and maintenance operations.

b) Constraints for duration and sequence of operation
The EMUs can only proceed to the next operation after completing one operation and switching yard. And the completion of each operation must meet its required specified duration, as shown in constraint (8) and (9).

c) Constraints for the beginning and the end of each EMU
The starting time of the operation of each EMU should be later than the time when it enters the EMU depot, and the ending time of the operation of each EMU should be earlier than the time of the EMU to be put into use, as shown in constraint (10) and (11). , , 1

d) Constraints for track capacity
There is a limit to the number of EMUs that can be operated simultaneously on each track. Constraint (12) and (13) indicates that one track can only be used for the operation of one EMU at the same time.

SOLUTIONS BASED ON GENETIC ALGORITHMS
The model is a nonlinear integer programming problem. The complexity of the model is determined by the scale of three preset parameters, namely the number of EMUs, the number of wash tracks and the number of maintenance tracks. When the scale of the parameter is small, it can be solved accurately using the enumeration method. When the scale of the parameters is large, it is difficult to solve accurately with the existing nonlinear solver, and the form of the objective function is difficult to express in the solver. Therefore, a heuristic algorithm is proposed to solve this problem. Considering the form of decision variables and the setting of constraints, a genetic algorithm is selected.

Description of the algorithm
The rules of chromosome encoding and decoding, selection, crossover and mutation in the algorithm are as follows.

Chromosome coding
Using integer coding method, the length of chromosome is 2n. As shown in Figure 2, the first n gene positions are the gene segments for maintenance. And according to the total number of EMUs and the number of EMUs allocated on each maintenance track, the EMUs on each maintenance track and their order can be determined correspondingly. Therefore, the first n gene positions are random arrangement of 1,2,...,n. Similarly, the last n gene positions are the gene segments for washing. For the sequence of washing and maintenance of the single EMU, it shall be determined according to the principle of the immediately preceding process when decoding.

Chromosome decoding
In the process of chromosome decoding, in order to improve efficiency, the principle of the immediate process is used to arrange the actual operation period. That is to avoid extending the final completion time due to unnecessary waiting on the operation track. The specific decoding process is as follows.
Step 1: According to the maintenance gene segment, assign EMUs on each maintenance track and sort them according to the sequence of the gene segment; Step 2: Consider the factors such as the arrival time of each EMU and the completion time of the previous EMU on this maintenance track, and determine the maintenance time period of each EMU according to the principle of the immediately preceding process; Step 3: According to the washing gene segment, assign the EMUs on each washing track and sort them according to the sequence of the gene segment; Step 4: Traverse each EMU in the order of the EMUs on the washing track, considering the arrival time of each EMU and the completion time of the previous EMU on the washing track. If the EMU can be washed before its maintenance, it will be inserted, the EMU first performs washing and then performs maintenance. Otherwise, the EMU first performs maintenance and then performs washing, and the washing time of the EMU can be determined.

Calculation of objective function value
According to the result of chromosome decoding, the time for all trains to complete all operations can be obtained, which is the objective function value. Due to the limitation of the end time of each EMU, whenever an EMU does not meet this condition, a penalty is added to the objective function value to avoid the situation where the constraint is not satisfied.

Chromosome selection
In order to avoid the algorithm falling into the local optimal solution faster, as much diversity as possible needs to be considered in the chromosome selection process. The binary tournament method can do this without increasing the number of populations. The specific method is as follows.
Step1: Randomly take the chromosomes pop1 and pop2 from the parent chromosomes; Step2: Compare the target values of the two chromosomes, and choose the better one for subsequent operations; Step3: Repeat Step1 and Step2 until the specified number of chromosomes is reached.

Chromosome crossover and repair
In order to adapt to the characteristics of chromosomes, the rule of segmented cross is proposed. In the process of cross generation of the two parents, the maintenance gene segment and the washing gene segment of the two parents were randomly selected to cross. Crossover may make chromosomes unfeasible. To repair chromosomes, after crossover, check and find out damaged (duplicate) gene positions, and randomly repair chromosomes (randomly supplement missing gene segments). As shown in Figure 3.

Chromosome variation
In order to prevent chromosomes from becoming infeasible solutions, a mutation rule for point exchange is proposed. As shown in Figure 4, two gene positions are randomly exchanged in the maintenance gene segment or washing gene segment to achieve the purpose of variation. At the same time to avoid chromosomes becoming infeasible solutions during decoding, this method can effectively improve the efficiency of variation.

Framework of the algorithm
Step 1: Algorithm initialization: randomly generate initial population POP_org, set population number Pop_max, crossing probability Pc, mutation probability Pm, maximum iteration algebra Iter_max, initial iteration algebra Iter, optimal solution R_best, optimal solution S_best.
Step2: Use formulas (1) (2) (3) to calculate the value of the objective function of the parent population; Step 3: Generate new populations; Step 3.1: Randomly select two parent chromosomes pop1 and pop2 using the binary tournament method; Step 3.2: If the random number Rand<Pc, skip to Step3.3; otherwise, skip to Step3.4; Step 3.3: Cross and repair chromosomes; Step 3.4: If the random number Rand<Pm, skip to Step3.5; otherwise, skip to Step3.6; Step 3.5: Chromosome variation; Step 3.6: Add the two chromosomes to the progeny population. If the population number is reached, skip to Step4; otherwise, skip to Step3.1; Step 4: Calculate the value of the objective function of the offspring population, and find the optimal solution r_best(Iter) and the optimal solution s(Iter) of the current generation; Step 5: If R_best> r_best(Iter), skip to Step6; otherwise, skip to Step7; Step 6: R_best = r_best(Iter), S_best = s(Iter); Step 7: Iter = Iter + 1, if Iter <Iter_max, skip to Step2; otherwise skip to Step8; Step 8: Output the optimal solution R_best and the optimal solution S_best.

CASE STUDY
Take the first-level maintenance operation of a China's EMU depot named TaiYuan depot as an example. There are 2 washing tracks and 6 maintenance tracks in the depot. The storage yard is located between the washing yard and the maintenance yard, as shown in Figure 5. A total of 19 EMUs need to complete the first-level maintenance task on a certain day, and their basic situation and attributes are shown in Table 3. And the parameter setting values are shown in Table 4. First, use the genetic algorithm designed in this paper to calculate the case, and then the case is simulated according to the other two common fixed operation sequence modes. The calculation results are as follows.

Flexible Operation Sequence Schedule Mode
Solve the model on the Matlab R2012b platform according to the proposed genetic algorithm, and run it on a laptop with 8 GB memory and i7-6500 CPU. Set the number of population to 50, the maximum number of iterations to 200, the crossover probability Pc=0.8, and the mutation probability Pm=0.01. The solution time is 4.23s. The iteration process is shown in Figure 6. The blue line indicates the iteration of the optimal solution for each generation, and the green line indicates the iteration of the global optimal solution. The objective function value is 750 (completed at 6:30). The corresponding EMU-to-track arrangement is shown in Figure 7.

Fixed Operation Sequence Mode
Because the washing operation takes less time, the EMU depot generally adopts the "washingmaintenance" fixed operation sequence, as shown in Figure 8.  A greedy algorithm was used to simulate the case, following the principles of first-come-first-served, shortest line idle time, and first-leave-first-served. The simulated objective function value is 810(completed at 7:30), the Gantt chart for the corresponding EMU-to-track arrangement is shown in Figure 9.  Fig. 9. Gantt Chart of EMU-to-track with Fixed Operation Sequence Mode

Fixed Operation Sequence Combined with Manual Washing
The time that the EMUs enter the EMU depot is unevenly distributed, using the fixed operation sequence of Figure 8 will cause some EMUs to wait for the washing tracks to become idle. In this case, some maintenance tracks are idle but some EMUs are still waiting for washing, which in turn causes a waste of resources. Therefore, a manual washing method is added on the basis of the fixed operation sequence at some EMU depots. That is, some EMUs skip the washing operation and enter the maintenance yard directly when they need a waiting time before can be washed. During the maintenance process, these EMUs are washed by manual washing, as shown in Figure 10. Similar to the fixed operation sequence mode, the maximum greedy algorithm is used to simulate the operation mode, and the simulated objective function value is 770(completed at 6:50). The corresponding EMU-to-track arrangement Gantt chart is shown in Figure 11.

Comparative Analysis
According to the data of Fig. 7, Fig. 9 and Fig. 11, the waiting time of all EMUs, utilization efficiency of tracks and latest completion time under three different operation modes can be calculated as shown in Table 5. As can be seen from Table 6, the waiting time of all EMUs in the flexible job-shop sequence mode is 10 hours shorter than that in the fixed job-shop sequence mode, and nearly 8 hours shorter than that in the fixed job-shop sequence combined manual washing mode.
In the fixed operation sequence mode, a total of 22% of the EMUs can directly perform washing and maintenance operations without any waiting time. In the other two modes, a total of 33% of the EMUs can directly perform washing and maintenance operations without any waiting time.
b) Track utilization efficiency Overall, the utilization rate of the maintenance tracks is high, and the utilization rate of the washing tacks is low. This is mainly due to the longer time it takes for maintenance operation, which affects the completion efficiency of the entire first-level maintenance operation. When the number of EMUs increases in the future, it is necessary to continuously improve the maintenance technical means to shorten the maintenance operation time, and improve the operation efficiency. The utilization rate of the tracks in the flexible operation sequence mode is improved compared to the other two modes.

c) Completion time of all EMUs
First of all, all EMUs can complete the first-level maintenance operations before being put into use the next day. However, the latest completion time is different in different modes. The latest completion time of the flexible job-shop sequence mode is 1 hour and 20 minutes ahead of the other two modes respectively. This is due to the overall arrangement of the EMU-to-track, which rationally uses the track resources, reduces unnecessary waiting time, and improves the utilization efficiency of the tracks.

CONCLUSIONS
This paper proposes a flexible operation sequence optimization model for the first-level maintenance scheduling problem of EMUs. A genetic algorithm based on the binary tournament method is proposed to solve the model. A case study based on the data from a Chinese EMU depot is conducted, and compared with the other two fixed job-shop sequence modes, the following conclusions are drawn.
The flexible operation sequence schedule model proposed in this paper is effective for the first-level maintenance operation optimization of EMUs.
Compared with the other two fixed operation sequence modes, the flexible operation sequence mode can appropriately shorten the operation time of the EMUs, reduce the waiting time of the EMUs, improve the utilization rate of tracks, and reduce unnecessary safety risks. When a large number of EMUs arrive densely at the EMU depot and the arrival time interval is short, the advantages of the flexible operation sequence mode will be more obvious.
A possible research direction in the future is to take into account the fact that the EMUs entering the EMU depot have different formations. The track can be designed in sections, that is, one track can accommodate one long EMU or two short EMUs. In this case, the arrangement of the EMU-to-track will be more complicated, and the calculation complexity will be a challenge, but it will have greater guiding significance for the actual.