{'fraction_non_alphanumeric': 0.025979024343307996, 'fraction_numerical': 0.006927739824882132, 'mean_word_length': 5.172209026128266, 'pattern_counts': {'":': 0, '<': 0, '<?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}}
A rescheduling approach based on genetic algorithm for flexible scheduling problem subject to machine breakdown

In this paper, a rescheduling approach based on genetic algorithm (GA) for solving the flexible scheduling problem subject to machine breakdown is proposed. In the proposed approach, event-driven rolling horizon rescheduling policy is employed to trigger the rescheduling procedure. Computational experiments are conducted on several benchmark data to prove the performance of the proposed approach. The results show that the proposed approach combines the rescheduling strategies of right-shift rescheduling and routing changing rescheduling to optimize the robustness and stability of rescheduling solution simultaneously.


Introduction
Scheduling task is one of the most time consuming and challenging activities within an enterprise. An effective production scheduling approach plays a particularly important role to improve the manufacturing performance in such large, complex manufacturing systems as automobile industry, electronics industry, aerospace industry and so on [1]. In practices, these manufacturing systems usually undergo the delays of various jobs/tasks due to such unpredictable interruptions as machine breakdowns, rush orders, order cancellations, due date changes, etc. These random events significantly interrupt the smooth progress of the whole schedule and result in low productivity of the manufacturing systems. Therefore, to improve the ability to cope with these random interruptions in the manufacturing systems is becoming an increasingly important issue [2].
The machine breakdown is regarded as one of the most popular and typical random events in manufacturing systems. The uncertainties about the machine breakdown in the manufacturing environments are classified into two types: partially unknown uncertainties or completely unknown uncertainties [3]. Partially unknown uncertainties mean some information relevant to the machine status is available when the predictive schedule is generated. Scheduling algorithms can take advantage of the information to develop the predictive schedule. For example, Mehta and Uzsoy [4] proposed a predictive schedule into which idle times were inserted according to the machine breakdown distributions as well as the structure of the predictive schedule. On the other hand, completely unknown uncertainties mean that no information about machine status is available in advance. As for completely unknown uncertainty problem such as scheduling problem subject to machine breakdown randomly, the approaches are divided into two types: pre-rescheduling and completely reactive scheduling [5]. In pre-rescheduling approach, firstly a schedule without considering machine breakdowns is generated and implemented until machine breakdown occurs, and a rescheduling procedure is triggered to react to the machine breakdown. In completely reactive scheduling, the scheduler generates a response to breakdown in real time. Usually the pre-rescheduling approach is better to be adopted to deal with machine breakdown interruptions [6]. To develop an effective schedule for the manufacturing systems with this type of uncertainty is difficult but attractive for researchers. For example, Ai-hinai and ElMekkawy [5], He and Sun [6], Sun et al. [7], Ahmadi et al. [8] developed effective scheduling approaches for scheduling problem with unpredictable machine breakdown.
The strategies which are mostly applied in the rescheduling procedure to adjust the initial scheduling when machine breakdown happens are: right-shift rescheduling and routing changing rescheduling. For example, Kamoun and Sriskandarajah [9], Kutanoglu and Sabuncuoglu [10], He and Sun [6], Ahmadi et al. [8] adopted the two strategies to deal with machine breakdown, however, the performance of robustness or stability cannot be guaranteed perpetually. To apply the evolutionary algorithms such as genetic algorithm (GA) to flexible scheduling problem is a potential method. Al-Hinai and ElMekkawy [5,11], Lei [12], Jalivand-Nejad and Fattahi [13], Li and Gao [14], Wu et al. [15] achieved many good results through designing effective GAs for flexible scheduling problem.
This paper is organized as follows: Section 2 gives the definitions and assumptions of the flexible scheduling problem. Rescheduling strategy and proposed approach based on GA are given in Section 3. Section 4 presents experiments and the results. Lastly, the conclusion is drawn in Section 5.

Problem formulation
The flexible scheduling problem with machine breakdown is described as follows. A number of jobs are to be processed on a number of machines. The sequence of operations for each job is fixed. Each operation of a job can be operated on any of its alterative machines. The processing time of each operation on each of its alterative machine is known and deterministic. Machines may breakdown randomly and the maintain operation spends a deterministic time duration. In the prescheduling stage, to minimize makespan is the main objective (Eq (1)), whereas in the rescheduling stage, the schedule's performance is measured by the weighted sum of robustness and stability (Eq (2)).
Where, Ci denotes the complete time of Job i,

Rescheduling strategy and proposed approach
An event-driven rolling horizon rescheduling policy proposed by Wang et al. [16] is employed and a GA based approach to solve the flexible scheduling problem subject to machine breakdown is proposed.

Event-driven rolling horizon rescheduling policy
The event-driven rescheduling policy is used and the critical evens that trigger the rescheduling procedure are defined as a machine breakdown. In other word, once a machine breakdown occurs, the rescheduling procedure begins.
In rolling horizon scheduling method, operation set in current window determines the initial state in prescheduling and rescheduling stage. At the beginning, assuming all jobs are available and ready for processing, the operation in the current window is defined as OW = O. When the rescheduling procedure is triggered at time t because of the breakdown of machine j * , the operation set is updated by removing the finished operations, i.e. OW = OW -FO, where FO includes the operations that have = . It is noticeable that the directly affected operation, i.e. the operation that is being operated on the breakdown machine, can be operated continually on the machine after the machine is available again or change its planned routing and move to another alterative machine to be operated continually. Step 4: If termination criteria is satisfied, i.e. if gen >= niter, then go to Step 6; otherwise, gen = gen+1, and go to Step 5;

Genetic algorithm
Step 5: Generate a new generation of population through applying the genetic operators (including selection, crossover and mutation operators) to the current generation of population; then go to step 3; Step 6: Out put the best solution.

Encoding scheme and decoding scheme.
Considering these two sub-problems in flexible scheduling problem, routing and sequencing sub-problem, the chromosome structure in mGA is designed to comprise of two parts. The one is the routing string and the other is the sequencing string. They have different encoding methods, respectively. The algorithm that translate a chromosome into an active schedule in [14] is used in decoding scheme.

Genetic operators.
Roulette method is adopted to select the individuals according to the fitness. The individual with better fitness is selected with a high probability. In additional, different crossover and mutation operators are employed to the routing string and sequencing string of the chromosome respectively. The two-point crossover and neighborhood mutation are applied on the routing string, and precedence operation crossover and swapping mutation are used on the sequencing string of the chromosome.

Experiments and results
In this section, the proposed approach mGA is tested on 5 FJSP instances which are taken from [17]. For each datum, preschedules without considering machine breakdown are generated by mGA and the results are compared with the best solutions obtained from start-of-the-art reported algorithms. In order to test the performance of mGA on the rescheduling procedure, machine for failure and the time for breaking down are randomly generated based on the 5 FJSP data. Three tuple (a,b,c) is used to express the data. a denotes the machine that breakdown occur, b denotes when the machine breakdown and c denotes the time needed to repair the machine. Table 1 shows the experimental results. AIA is selected from Yuan et al.
[18], HA represents the algorithm proposed by Li and Gao [14] and mGA represents the proposed GA-based approach in the paper. The results marked by * are the best results without considering the breakdown of machine among all these algorithms. From the results in Table 1, it is found that the proposed algorithm mGA found a better solution than existing best algorithms on MFJS04, a suboptimal solution on MFJS02, and also found the best solution of the rest 3 instances in the prescheduling without considering machine breakdown. It is concluded that mGA is not worse than the existing algorithms in the respect of search capability. From Table 1, it is also found that mGA can optimize the robustness and stability simultaneously under random breakdown. The Gantt chart of the best solution of MFJS05 is shown in Fig. 1. The shaded area in Fig. 1 (b) denotes the machine breakdown occurred on M6 between time 154 and 244. The comparison of the arrangement for all operations between the preschedule and reschedule is listed in Table 2. The data shown in bold means the corresponding operation changes its original routing; the data shown in italics means the corresponding operation right shifts. From Fig 1   CISAI

Conclusion and future work
In this paper we study the flexible scheduling problem with machine breakdown. An event-driven rolling horizon scheduling policy is applied and a GA-based algorithm mGA is proposed. Simulation results show that mGA with the event-driven rolling horizon scheduling policy responds to the changes in the shop floor immediately, and achieves high efficient scheduling results which improve shop performance even under the effects of disruptions. However, the proposed scheduling approach