Integrated Scheduling of the Production and Maintenance of Parallel Machine Job-shop Considering Stochastic Machine Breakdowns
Abstract:
The integrated scheduling of production and maintenance can make equipment maintenance in line with the production pace, so as to effectively prevent anormal interruptions of the production process due to equipment failure, and ensure the smooth implementation of the production scheduling plan. Aiming at the parallel machine job-shop environment, and considering stochastic machine failures and different degradation speeds of parallel machines, this paper introduced the minimal maintenance and preventive maintenance strategies to establish an integrated scheduling model for production and maintenance, designed a genetic algorithm based on process coding and binary hybrid coding to solve the model, and verified the correctness of the proposed model and the effectiveness of the algorithm through an instance. This study provided an effective decision-making method for parallel machine job-shop scheduling problems.
1. Introduction
A reasonable production scheduling plan can effectively improve the utilization rate of equipment and production efficiency of manufacturing job-shops, and a reasonable equipment maintenance strategy can effectively improve the reliability of equipment and ensure the smooth implementation of production [1], [2]. During the production process, the working conditions of a machine degrade continuously with the accumulation of processing time, so the machine may break down and need to be shut down for maintenance. Without any maintenance of the machine, the production scheduling cannot be carried out as planned [3], [4], [5]. Therefore, when making a production plan, one must also consider possible maintenance of equipment, and incorporate production and maintenance into scheduling, to effectively ensure that equipment maintenance will match the production pace and that the production scheduling plan will go smoothly.
Palacín et al. [6] used mixed the integer linear optimization and two-stage stochastic programming methods to solve the problem of when the equipment in the production job-shop should be maintained; Biondi et al. [7] proposed an industrial framework for the maintenance and production scheduling of an integrated process plant, which set the integrated maintenance and the production scheduling problem as mixed integer linear programming; For a single machine with failure uncertainty, Cui et al. [8] designed a three-stage heuristic algorithm to solve the active combined model of production scheduling and maintenance strategies; For the single-machine maintenance problem whose objective is to minimize the total weighted completion time, Luo and Liu [9] proposed a complete polynomial time approximation scheme to solve the single-machine sequencing problem dependent on the maintenance time. Beezão et al. [10] used the adaptive large neighborhood search meta-heuristic method to solve the parallel machine scheduling problem and the job sequencing and tool switching problems. Xiong et al. [11] modeled and solved the flexible job-shop scheduling problem through hybrid multi-objective evolutionary optimization. Regarding the resource-constrained scheduling problem in a job-shop with parallel machines, Chan et al. [12] took the minimum completion time of workpieces and the minimum idle cost of the machines as the optimization objectives, and used a scheduling method based on the genetic algorithm. This algorithm solves the allocation problem under resource constraints and the scheduling problem of a flexible job-shop. Regarding the scheduling problem of a sheet metal job-shop with multiple products and parallel machines, Chan and Choy [13] proposed a scheduling algorithm based on the genetic algorithm with the minimum completion time of workpieces as the scheduling objective. Chen et al. [14] designed a new scheduling algorithm based on the genetic algorithm and group genetic algorithm for the job-shop scheduling problem with parallel machines, and verified the performance of the algorithm by taking a weapon manufacturing plant as an example. Dalfard and Mohammadi [15] used the hybrid genetic algorithm and the simulated annealing algorithm to solve the multi-objective scheduling problem of a flexible job-shop with parallel machines.
Through review of the existing research, it can be found that most scholars mainly considered the situation of a single-machine job-shop when studying the maintenance strategies in the case of stochastic machine failures, and that when they switched to the scheduling problem of a job-shop with parallel machines, they did not consider the maintenance of machines [16], [17], [18]. Therefore, regarding the integrated scheduling problem of production and maintenance in a job-shop with parallel machines, this paper considered the different machine failure patterns of parallel machines, established an integrated mathematical scheduling model, designed a genetic algorithm to solve the problem, and verified the correctness of the proposed mathematical model and the effectiveness of the solving algorithm through an instance. This paper is organized as follows: Section 1 elaborates on the integrated scheduling problem of the production and maintenance in a job-shop with parallel machines; Section 2 establishes the mathematical model of the problem; Section 3 designs a genetic algorithm to solve the model; Section 4 verifies the model and the solving algorithm through an instance; and the final section gives a summary of this paper.
2. Problem Description
The integrated scheduling problem of preventive maintenance and production planning considering stochastic machine failures under the condition of parallel machine operation is described as follows: (1) given the workpieces to be processed and the machinery and equipment, each workpiece takes multiple processes, and each process needs to be carried out on a given machine uninterruptedly for a period of time. Each machine can only process one workpiece at a time, and each workpiece can only undergo one process at a time. For some processes, there are more than one machine available. (2) Considering that the working conditions of a machine continuously degrade with the processing time, the machine may encounter stochastic failures, and with the service life of the machine approaching its maximum service life before maintenance, the working conditions will further degrade, which may lead to a serious shutdown incident. In order to ensure the continuous availability of the machine during the production process, two maintenance strategies - minimal maintenance and preventive maintenance, are introduced to maintain the operational reliability of the machine. (3) As different parallel machines were purchased in different time periods, their models and performances may vary, and the working conditions may also degrade at different speeds. This paper considers two scenarios. First, the parallel machines degrade at the same speed. Specifically, the maximum service lives of the parallel machines before maintenance are the same, and preventive maintenance will be carried out when parallel machines reach the same maximum service life before maintenance. Second, the parallel machines degrade at different speeds, that is, the parallel machines have different maximum service lives before maintenance. The machine which degrades at a faster speed has a smaller maximum service life before maintenance, and reaches its maximum service life before maintenance faster and is subject to more frequent preventive maintenance; on the other hand, the one which degrades at a lower speed has a greater maximum service life before maintenance, and is subject to less frequent preventive maintenance.
The different degradation speeds of the parallel machines in the job-shop are shown in Figure 1. Machine 1 and machine 2 have been used for a long time and are degrading at different speeds. In this paper, the scheduling scheme with the minimal completion time is determined as the optimal scheduling scheme.
3. Modelling
In order to build an integrated scheduling model for the production and maintenance in a job-shop with parallel machines, the following symbols are introduced:
J_{i}_{，}i=1,2,…,M: the workpiece set, where M is the number of all the workpieces;
M_{j}, j=1,2…,N: the machine set, where N is the number of all the machines;
Q={1,…,m}: the set of workpiece processes, where m is the number of all the processes;
S_{JikMj}: the processing start time of the k-th process of workpiece J_{i} on machine M_{j}, where k∈Q;
P_{JikMj}: the processing duration of the k-th process of workpiece J_{i} on machine M_{j}, k∈Q;
O_{JikMj}: the k-th process of workpiece J_{i} processed on machine M_{j}, k∈Q;
P_{Ji}={(O_{JikMj}_{1}, O_{JilMj}_{2})｜: the k-th process of workpiece J_{i} is prior to the l-th process, where l, and k∈Q, P_{Ji} is the set of the ordered process pairs of workpiece J_{i};
R_{Mj}={(O_{JikMj})｜: all processes using machine M_{j}, k∈Q};
l_{Mj}(t): the failure probability of machine M_{j};
_{$\partial M j$}: the maximum service life before maintenance, i.e., the maximum service life of machine M_{j} before it needs to undergo preventive maintenance;
w: the recovery coefficient of the machine service life after preventive maintenance is carried out;
A_{JikMj}: the service life after the k-th process of workpiece J_{i} on machine M_{j}, k∈Q;
C_{Mj}: the time taken to complete the processing of all workpieces on machine M_{j};
C_{max}: the time taken to complete all workpieces;
The objective is to minimize the completion time of all workpieces:
The constraints are considered as follows:
where, (2) represents the constraint on the process sequence - different processes of the same workpiece cannot be processed at the same time; (3) represents the resource constraint - each machine can only process one workpiece at the same time; (4) represents that the service life of machine M_{j} after finishing the k-th process of workpiece J_{i} should not be greater than the maximum service life of machine M_{j} before maintenance; (5) means that if machine M_{j }undergoes preventive maintenance after finishing the k-th process of workpiece J_{i}, the service life of the machine is w*A_{JikMj}, where w is the restoration coefficient of the service life of the machine after preventive maintenance is performed. If w=0, it means that the preventive maintenance is perfectly performed, and that after the maintenance is performed, the service life of the machine becomes 0; otherwise, it means that the preventive maintenance is imperfect; (6) indicates that the stochastic failure probability of machine M_{j} obeys the Weibull distribution.
4. Design of the Genetic Algorithm
The integrated scheduling problem of preventive maintenance under the operating conditions of parallel machines is highly complex. From the perspective of production scheduling, it is necessary to assign the workpiece process to the parallel machines, determine the process sequence of each workpiece, and then calculate the corresponding start time and completion time of the process; on the basis of production scheduling, it is also necessary to comprehensively consider the maintenance of the machines. Two maintenance strategies - preventive maintenance and minimal maintenance were introduced in this paper, which influence and restrict each other, further adding complexity to the problem. Considering the complexity, a genetic algorithm with significant parallelism and a powerful global optimization ability was used in this paper to solve the problem [19], [20].
(1) Coding
A job-shop with parallel machines needs to consider how the workpieces should be allocated to the parallel machines. The whole chromosome consists of two parts. The first part determines the order of the workpiece processes, and the second part determines how the workpiece processes should be allocated to the parallel machines.
Suppose that there are 6 workpieces, and each workpiece has 4 processes, which need to be performed on 4 machines, respectively. Machine 4 and machine 5 are two parallel machines. A feasible solution is designed as follows: [6 4 4 2 2 5 3 6 2 1 6 3 1 3 4 5 5 2 1 3 6 5 4 1 | 0 0 1 1 1 1], which is divided into two parts by a vertical line, and the part behind the vertical line is the chromosome code of the new workpiece process assigned to the parallel machines. The chromosome code of the second part is composed of 0 and 1, and from left to right are the codes of workpiece 1 to workpiece 6, respectively. If the workpiece is assigned to parallel machine 4, then the code is 0; and if it is assigned to parallel machine 5, then the code is 1. The code designed in this paper combines the scheme of assigning the processes of the workpieces to the parallel machines and the scheme of the processing sequence of each workpiece, which ensures that the two schemes can be bundled together, so that when the operators are selected to implement the elitism strategy, both schemes can be preserved to the next-generation population.
(2) Crossover operator
The crossover operation is performed in two steps. The first step is to perform the crossover operation on the chromosome part that determines the process sequence of each workpiece; and the second step is to perform the crossover operation on the chromosome part that determines how the workpiece processes are allocated to the parallel machines. The crossover operation adopts the double-point crossover method. Due to the characteristics of the code, there is no problem of illegitimacy in the chromosomes after crossover, and therefore, there is no need to legitimate the chromosome. The crossover operation of the chromosome code to assign workpieces to the parallel machines is shown in Figure 2.
(3) Mutation operator
The mutation operation is performed in two steps. The first step is to perform the mutation operation on the chromosome part that determines the process sequence of each workpiece, and the second step is to perform the mutation operation on the chromosome part that determines how the workpiece processes are allocated to the parallel machines. The mutation operation method is the same – select two crossover points, and then cross the codes at the corresponding positions. This mutation operation method can ensure the legitimacy of the codes.
(4) Selection operator
The selection operator needs to keep the chromosomes with higher fitness value in the current generation of population to the next generation to ensure that the population evolves towards a better direction. Since the code of the genetic algorithm designed in this paper combines the code of assigning the processes of workpieces to the parallel machines and the code of process sequence, and the former will affect the latter, the result of the two schemes combined is finally expressed as the completion time of the workpieces. Therefore, the completion time of the workpieces is used as a fitness function.
5. Instance Analysis
The integrated scheduling problem of preventive maintenance under the working condition of parallel machines is described as follows: 6 workpieces and 5 machines, of which 2 are parallel machines, both of which can perform the corresponding workpiece processes. Each workpiece has 4 processes, and the 4 processes of the workpiece need to be performed on 4 machines. The processing time of each process of the workpieces is evenly distributed in [1,50] min. The workpiece processes and corresponding processing time in the job-shop with parallel machines are shown in Table 1.
Workpiece i | Processing sequence (machine sequence, processing time/min) |
1 | (3,27) (1,17) (2,22) (4/5,39) |
2 | (2, 7) (4/5,50) (1,25) (3,28) |
3 | (1,37) (2,44) (4/5,49) (3,14) |
4 | (1,38) (4/5,3) (3,27) (2,18) |
5 | (2,25) (3,34) (1,18) (4/5,11) |
6 | (3,28) (2,26) (4/5,20) (1,10) |
The stochastic failure probability of a machine follows the Weibull distribution $\lambda_{M j}(\mathrm{t})=\beta / \eta^*(t / \eta)^{\beta-1}$, where $\beta=2$, and $\eta=125$. Suppose that when the cumulative number of stochastic failures of a machine reaches 0.6, the machine will encounter a stochastic failure, and that the minimum maintenance is performed, and that each maintenance takes 15 minutes. Except for parallel machines, the maximum service life before maintenance is 82 minutes. Preventive maintenance needs to be performed before the service life of the machine reaches the maximum service life before maintenance. The recovery coefficient w of the machine’s service life after preventive maintenance is set at 0.5, and each preventive maintenance takes 10 minutes.
Two scenarios were considered in this paper, that is, the scenario where the parallel machines degrade at the same speed and the one where the machines degrade at different speeds. In the former scenario, the maximum service lives of the parallel machines before maintenance are the same - both are 82min; and in the latter scenario, the maximum service life of parallel machine 4 before maintenance is 82min, and that of parallel machine 5 is 60min. A job-shop without parallel machines was introduced as the control group. Except that parallel machines were not considered in the control group, and that the maximum service life before maintenance was 82 minutes, other parameters remained the same. The population size was 20, and the number of iterations 800. Each scheme was iterated 10 times to obtain the optimal value. The Gantt chart of the optimal scheduling scheme for the job-shop without parallel machines is shown in Figure 3, that for the job-shop with the same degradation speed of parallel machines shown in Figure 4, and that the job-shop with different degradation speeds of parallel machines shown in Figure 5. The integrated scheduling results of different parallel machine configurations are shown in Table 2.
Workpiece set | Parallel machine configurations | ||
6*4 | No parallel machine | Same degradation speed | Different degradation speeds |
Completion time | 233 | 193 | 193 |
From Table 2, it can be seen that the integrated scheduling results of the job-shop with parallel machines were better than those of the job-shop without parallel machines. And from Figure 3 and Figure 4, it can be seen that the workpieces in the job-shop with parallel machines were assigned to different parallel machines, with increased flexibility in scheduling and less waiting time for the next process of each workpiece. At the same time, since the workpiece load of each parallel machine was small, the working conditions of each parallel machine degraded slowly, and the required maintenance time is shorter accordingly. Through comparison of the job-shop with the same degradation speed of parallel machines and the one with different degradation speeds of parallel machines, it was found that the integrated scheduling results were the same. From Figure 4 and Figure 5, it can be seen that parallel machine 5 with a faster degradation speed underwent more frequent preventive maintenance because the service life of the machine reached the maximum service life before maintenance faster, but thanks to the small workpiece load on parallel machine 5, the longer preventive maintenance time of parallel machine 5 did not exert a great impact on the completion time of the workpieces.
6. Conclusion
Considering the impact of parallel machines in a job-shop on production scheduling and equipment maintenance, this paper focused on studying the integrated scheduling problem of a job-shop with parallel machines in the manufacturing process. It took into account the different failure characteristics of parallel machines, adopted two maintenance strategies - minimal maintenance and preventive maintenance, and then established a mathematical model for the integrated scheduling of production and maintenance in a job-shop with parallel machines. According to the established mathematical model, a genetic algorithm based on process coding and binary coding was designed, and finally the correctness of the mathematical model and the effectiveness of the solving algorithm were verified through an instance. The results show that, the use of parallel machines drastically shortens the completion time of the integrated scheduling scheme, effectively relieves the loads of the machines, and greatly reduces the waiting time of the workpieces. At the same time, a parallel machine with a faster degradation speed needs to undergo more frequent preventive maintenance than one with a slower degradation speed.
The data used to support the findings of this study are available from the corresponding author upon request.
The authors declare no conflict of interest.