Abstract
In this study, we investigate a new multi-maintenance with sequential operation (MMSO) problem, in which a variety of tasks must be processed on multiple machines. In the MMSO problem, each task has multiple sequential operations that must be processed for each machine. In addition to maintenance, the MMSO problem has many other practical applications, such as physical examination scheduling. The proposed MMSO, which is an NP-hard problem, generalizes typical job shop scheduling problems. Thus, a novel encoding scheme, which is embedded into an immune-based algorithm (IBA), is proposed in this study to convert any sequence of random numbers into a feasible solution of the MMSO problem to solve the MMSO problem. Numerical results of applications in aircraft maintenance and physical examination scheduling are reported and compared with those of particle swarm optimization and genetic algorithm. Experimental results show that IBA outperforms the two other algorithms.
Introduction
Maintenance plays a significant role in preserving the functions of equipment. Based on various purposes, maintenance has several basic types, such as preventive, corrective, and predictive maintenance [26]. Particularly, preventive maintenance is regularly performed on operational equipment to reduce failure, corrective maintenance is used to identify and correct faults in failed equipment, and predictive maintenance is conducted to predict and prevent the occurrence of equipment failure. In addition to retaining the quality of products or services by equipment, maintenance can also provide a safe environment in the real world. For example, in aircraft maintenance, various maintenances, such as line, base (or heavy), and component maintenance, are required to increase the safety of flight. Each kind of maintenance also involves several tasks, and each task contains several distinct operations requiring specific maintenance groups to facilitate execution. For example, line maintenance includes A check, C check, and D check; base maintenance includes routine maintenance, project inspection, non-routine maintenance derived from inspection, and other miscellaneous maintenance of items, such as interior refurbishment, stripping and repainting, and the test, repair, and component replacement of accessories (engines, landing gears, and even coffee machines). Therefore, efficient maintenance scheduling of all tasks and operations by limited professional maintenance groups can directly reduce operating costs and increase the competitiveness of airline companies.
In this study, we consider a special scheduling problem, in which several tasks must be processed by multiple machines, and each task has a sequence of multiple operations that must be processed for each machine. However, no order restriction is imposed on any two operations of distinct tasks. The considered problem on multi-maintenance with sequential operations (herein referred to as MMSO problem) is similar to the typical open-shop scheduling problem (OSSP) and job-shop scheduling problem (JSSP) with slight differences due to the following reasons. In a standard OSSP, n tasks are processed on m machines once without order restriction, and each task has only one operation for each machine [3]. However, the MMSO problem must process n tasks on m machines, and each task has multiple and sequential operations for each machine. In a standard JSSP, n tasks are processed on m machines, each task has one operation that can be processed in one of several machines, and an order restriction of machines is imposed for each task [28]. However, the MMSO problem has n tasks to be processed on m machines, and each task has sequential operations for each machine.
Additionally, the MMSO problem is similar to the vehicle routing problem (VRP), periodical vehicle routing problem (PVRP), hole-making problem (HMP), and multiple disinfection operation problem (MDOP) but with slight differences due to the following reasons. In a VRP, one vehicle must visit n nodes once without order restriction [13]. However, the MMSO problem must process n tasks on m machines, and each task has sequential operations for each machine, that is, a task must visit a machine for a given number of times. In a PVRP [5], one vehicle must periodically visit n nodes without order restriction, and each node must be visited for a given number of times within a duration period. The main difference between PVRP and MMSO problem is that operations from different machines can be processed simultaneously on machines in an MMSO problem, and sequential order for operations of a task is given in each machine. Particularly, in an MMSO problem, the processing times for the sequential operations are different, whereas those in a PVRP are similar. In an HMP [6], n holes must be made by m tools, and each hole requires a sequence of tools to drill. In addition, a tool can be used to drill different holes, and only one drilling operation can be applied for each time. However, in the MMSO problem, m machines must process n tasks with sequential order for operations, and multiple operations of different tasks can be processed by various machines simultaneously. In an MDOP [8], m vehicles are scheduled to spray n buildings with k disinfectants. Each building must receive multiple spray applications of disinfectants, and the final spray application of disinfectants in each building is given and fixed. In addition, the time interval between two consecutive spray applications for each building must exceed a specified minimum for safety. However, in the MMSO problem, m machines must process n tasks, and each task has sequential operations for each machine. In addition, the MSSO has no restriction on the time interval between two consecutive operations for a task.
We summarize VRP, PVRP, HMP, OSSP, and MDOP in Table 1, which indicates that the considered MMSO problem is a variant of JSSP. However, the main difference between the standard JSSP and MMSO problem is that multiple sequential operations for each task in the MMSO and these operations must be processed by sequential machines. This study primarily aims the following: (i) present a new MMSO problem, (ii) propose a new encoding scheme to convert any random sequence of integer into a feasible solution of the MMSO problem, (iii) apply an immune-based algorithm (IBA) to solve the MMSO problem, and (iv) present and compare numerical results of two test problems in aircraft maintenance and physical examination of IBA with those of genetic algorithm (GA) and particle swarm optimization (PSO) to demonstrate the performance of IBA.
Main differences in standard VRP, PVRP, HMP, OSSP, MDOP, and MMSO
Main differences in standard VRP, PVRP, HMP, OSSP, MDOP, and MMSO
In the MMSO problem, n tasks must be processed on m machines, and each task requires multiple sequential operations on each machine. The multiple operations of a task on a machine are subject to a given sequential order. However, no order restriction is imposed on any two operations of distinct tasks. In addition, no interruption is allowed for each machine while processing an operation. The objective of the MMSO problem is to minimize the total completion time of all tasks, that is, the makespan.
The notations and assumptions of the MMSO problem are as follows.
the number of tasks, 1≤i≤n the number of machines, 1≤j≤m the number of operations for Task i on Machine j, 1≤i≤n, 1≤j≤m the kth operation of Task i on Machine j, 1≤i≤n, 1≤j≤m, 1≤k≤p
ij
(•) the processing time of the kth operation of Task i on Machine j, 1≤i≤n, 1≤j≤m, 1≤k≤p
ij
(•) the candidate set of operation to assign for Task i in the proposed method, 1≤i≤n the completion time of Task i, 1≤i≤n the total number of operations for all tasks, that is, N = ∑∑p
ij
(•) = (T1∪T2∪ ∪T
n
) is a random permutation of sequence {1, 2, ... ,N} ith sub-sequence in T, |T
i
| = p
ij
(•), 1≤i≤n, 1≤j≤m
Assumptions.
n tasks must be processed on m machines. Task i must process p
ij
(•) operations on Machine j, 1≤i≤n, 1≤j≤m. For Task i, Operation p
ij
(k) must be processed before Operation p
ij
(k + 1) on Machine j, 1≤i≤n, 1≤j≤m,1≤k≤p
ij
(•)-1. No order restriction is imposed on Operation p
ij
1(k1), Machine j1, and Operation p
ij
2(k2); on Machine j2, 1≤i≤n, 1≤j1≤m, 1≤j2≤m, 1≤k1≤p
ij
1(•), 1≤k2≤p
ij
2(•), j1 ¬ =j2 Each machine cannot be interrupted while processing an operation. The MMSO problem seeks to minimize the total completion time of all tasks, that is, min max c
i
0, 1≤i≤n.
Example. Consider an MMSO problem with two tasks and two machines. Task 1 has 2 operations (namely, p11(1) and p11(2)) on Machine 1 and one operation (namely, p12(1)) on Machine 2; Task 2 has 1 operation (namely, p21(1)) on Machine 1 and two operations (namely, p22(1) and p22(2)) on Machine 2. In addition, p11(1) must precede p11(2), and p22(1) must precede p22(2) in operation. No order restriction is imposed on p11(1) and p22(1), p11(1) and p22(2), p22(1) and p11(1), and p22(1) and p11(2). Fig. 1(a) and 1(b) show two possible solutions for this example, and their makespan is 38 and 30, respectively. This finding implies that the solution in Fig. 1(b) is better than that in Fig. 1(a).
Two feasible solutions of MMSO problem (Example).
Approaches in literature
The MMSO problem is similar to OSSP and a variant of the typical JSSP. Given that OSSP and JSSP are NP-hard problems, the considered MMSO problem is also a complicated NP-hard problem. In literature, many methods are used to solve OSSP, JSSP, and their related problems. However, these methods have some disadvantages in practice.
(1) Theoretical approaches [2, 12]:
Theoretical approaches can only derive properties or exact solutions for some special structures of problems and are unsuitable for solving the general OSSP- and JSSP- related problems.
(2) Mathematical programming approaches [11, 23]:
Integer programming approaches are modeled to solve OSSP, JSSP, and their related problems. However, when the problem size is slightly large, such methods are time consuming and occupy a large computer memory. Therefore, obtaining an approximate optimal solution in a reasonable time is difficult.
These approaches are also time consuming and can only be applied for some small OSSP, JSSP, and their related problems.
These approaches often fall into the local optimal solution without an escape.
(5) Evolutionary and swarm algorithms:
Numerous algorithms are inspired by the mechanism of evolution, swarm of animals, or natural behavior for solving the general OSSP- and JSSP-related problems. Examples of these algorithms include GA [29], PSO [30], Tabu Search [14, 17], simulated annealing method [24], ant colony optimization algorithm [22], artificial bee colony algorithm [9, 16], memetic algorithm [27], frog-leaping algorithm [15], and discrete firefly algorithm [10]. However, the common disadvantages of these approaches are as follows: (i) the setting of parameters is sensitive to the performance of solutions; (ii) the algorithms fall into the local optimal solution and cannot escape for complicated optimization problems.
In the past years, numerous artificial intelligence algorithms have been proposed and widely applied to solve various complicated optimization problems. For example, Mirjalili et al. [19] reported more than 20 novel optimization algorithms based on either evolutionary or swarm intelligence techniques. However, as mentioned in [19], GA and PSO may be the most popular methods used to solve different types of complicated optimization problems due to their numerous successes in previous works, as presented in [1, 18]. In addition, IBA, an evolutionary algorithm based on the immune mechanism, has attracted considerable attention; for example, that presented in [31]. The IBA is similar to GA in terms of crossover and mutation, except for its unique memory mechanism. In the memory mechanism, although the objectives of IBA are excellent, this algorithm can delete similar solutions to maintain their diversity. Compared with GA, IBA can substantially preserve antibody diversity during the evolutionary process and has a high probability to obtain optimal solutions. Therefore, we adopt IBA in this study to solve the MMSO problem and compare its numerical results with those by GA and PSO.
Encoding scheme and example
For the MMSO problem, we present a new encoding scheme to convert a random permutation of {1, 2, ... , N} with the module operator into a feasible sequence of operations for all tasks, where N is the total number of operations for all tasks.
The steps of the encoding scheme are described as follows.
Step 0. S =ϕ, given p ij (k) and C i , 1≤i≤n, 1≤j≤m, 1≤k≤p ij (•).
Step 1. Create a random permutation of {1, 2, ... , N}, termed T, where N =∑∑p ij (•), which is the total number of operations for all tasks.
Step 2. Based on the number of operations of tasks, divide T into n groups and T = (T1∪T2∪ ∪T n ), where |T i | is the number of operation in Task i, 1≤i≤n.
Step 3. For each Task i, 1≤i≤n, perform the following steps in (a)–(b) to construct a table. Find the smallest number in T
i
, that is, T
i
(h). Compute d = {(T
i
(h)+I(h)) mod |C
i
|)+1}, where I is a sequence from 1 to N, and C
i
is the candidate set of operation to assign for Task i. Assign the dth operation in C
i
to S(d), delete T
i
(h) from T
i
, and update C
i
. Repeat the similar procedure until T
i
=ϕ, that is, |T
i
| = 0. Repeat (a) until i = n and T
n
=ϕ.
Step 4. Use T from 1 to N and its corresponding value in S to construct the feasible solution of the MMSO problem.
The main computation of the encoding scheme is in Step 3. The complexity of the worst case for Step 3(a) is O(n), thus the complexity of the worst case for Step 3 is O(n2). This implies that the computational complexity of the encoding scheme is polynomial.
Example. Consider an MMSO problem with two tasks and three machines. The corresponding operations of tasks are shown in Table 2. The processes of the encoding scheme for the example are shown below step by step.
An MMSO problem (example)
An MMSO problem (example)
Step 0. S =ϕ. n = 2, m = 3, C1 = {p11(1), p12(1), p13(1)}, and C2 = {p21(1), p22(1), p23(1)}.
Step 1. N =∑∑p ij (•) = 3 + 3+2 + 2+2 + 1 = 13. Suppose that T = 6-5-13-1-10-7-4-11-3-8-2- 9-12 is a random permutation of 1 to 13.
Step 2. As shown in Table 3, T is split into two sub-groups, that is, T = (T1∪T2), where, T1 = {6,5, 13,1,10,7,4,11} and T2 = {3,8,2,9,12}.
Step 3. (a) For Task 1 (i = 1), consider T1 = {6,5,13, 1,10,7,4,11} and the candidate set of operation C1 = {p11(1), p12(1), p13(1)}. As T1(4) = 1 is the smallest number in T1, compute {(T1(4)+I(4)) mod |C1|)+1} = {(1 + 4 mod 3)+1} = 3. Thus, select the third operation of C1 into S, that is, S(4) = p13(1). Then, delete T1(4) from T1 and update C1 = {p11(1), p12(1), p13(2)}. As T1(7) = 4 is the smallest number in T1 = {6,5,13,–,10,7,4,11}), compute {(T1(7)+I(7)) mod |C1|)+1} = {(4 + 7 mod 3)+1} = 3. Thus, elect the third operation of C1 into S, that is, S(7) = p13(2). Then, delete T1(7) from T1 and update C1 = {p11(1), p12(1)}. As T1(2) = 5 is the smallest number in T1 = {6,5,13,–,10,7,–,11}), compute {(T1(2)+I(2)) mod |C1|)+1} = {(5 + 2 mod 2)+1} = 2. Thus, select the second operation of C1 into S, that is, S(2) = p12(1). Then, delete T1(2) from T1 and update C1 = {p11(1), p12(2)}.
Encoding scheme (example)
Repeat similar processes until T1 =ϕ.
(b) Repeat the similar procedures for Task 2 (i = 1) until T2 =ϕ. The results are shown in Table 3.
Step 4: The completed sequence S is presented in Table 3. Using T, from 1 to 13, obtain the following sequence of operations by using T and S:
Thus, the Gantt chart of groups for this solution is depicted in Fig. 2, and the makespan for this solution is 18 if moving time is ignored.
Gantt chart for the encoding example.
Test problems and parameter setting
The following two test problems in aircraft maintenance and physical examination are solved.
(1) Test Problem 1:
This test problem is an application of aircraft maintenance with 6 aircraft, 8 maintenance groups, and 150 maintenance operations. The corresponding data, which include the number of aircraft (tasks), the number of maintenance groups (machines), and multiple sequential operations and maintenance times for each aircraft, are listed in Table 4. In addition, Table 5 shows the moving and layover time among maintenance groups.
Processing time for each operation of maintenance (Test problem 1)
Processing time for each operation of maintenance (Test problem 1)
Moving time and layover time for maintenance groups (Test problem 1)
(2) Test Problem 2:
This test problem is an application of physical examination in Taichung Veterans General Hospital Puli Branch, Taiwan, with 15 people (tasks), 4 types of physical examination, 8 examination rooms (machines), and 150 examination items. As shown in Table 6, the four main types of general physical examination with different purposes in Taiwan hospitals are complete, labor, student, and catering staff physical examination. The corresponding data, which include the number of people, the number of rooms, and the sequential examination item and time, are listed in Table 6. In addition, Table 7 shows the moving time among rooms in the hospital.
Examination time for each test of maintenance (Test problem 2)
Moving time among rooms (Test problem 2)
In this study, the programs of GA, IBA, and PSO are coded in MATLAB 2009 using Windows 7 Intel(R) Core(TM) i5-4570 CPU 3.2 GHz and 4 GB RAM computer. Additionally, we use Taguchi method to set the values of parameters from a possible set of values which are suggested in the literature. Based on our experiments, the parameters of the three algorithms are set as follows: (i) IBA and GA: population = 150, iteration = 800, crossover = 0.6878, and mutation = 0.1; (ii) PSO: population = 150, iteration = 4000, c1 = 1.2, and c2 = 1.2.
We perform 50 trials by GA, IBA, and PSO for the two test problems. The best and average of solutions and CPU times of 50 trials are summarized in Table 8. The distributions of the objective of 50 trials by the three algorithms are shown in Figs. 3 and 4. The ratios of best solution and average CPU time for three algorithms are shown in Fig. 5. The Gantt charts of the best solution of IA for the two test problems are depicted in Fig. 6.
Numerical results of test problems
Numerical results of test problems
The distribution of solutions for Test problem 1 by IBA, GA, and PSO (50 trials).
The distribution of solutions for Test problem 2 by IBA, GA, and PSO (50 trials).
The ratios of best solution and average CPU time for various algorithms.
Gantt charts of the best solutions by IBA for two test problems.
Table 8 and Figs. 3 to 4 show the following: For Test Problem 1, the best solution of 50 trials by IBA (1851) outperforms those by GA (1877) and PSO (2162). For Test Problem 2, the best solution of 50 trials by IBA (249) and GA (249) outperforms that by PSO (287). Therefore, IBA can obtain a better solution than GA and PSO. For Test Problem 1, Fig. 3 shows that the distribution of the objective of 50 trials by IBA is more concentrated than that by GA and PSO. In addition, Table 8 shows that the standard deviation of the objective of 50 trials by IBA (23.11) is smaller than that by GA (76.98) and PSO (52.51). Similarly, for Test Problem 2, Fig. 4 shows that the distribution of the objective of 50 trials by IBA is also more concentrated than that by GA and PSO. Table 8 also indicates that the standard deviation of the objective of 50 trials by IA (4.46) is smaller than that by GA (14.41) and PSO (8.5). Hence, IA is more robust than GA and PSO for solving the two test problems. For Test Problem 1, the average CPU time for IBA, GA, and PSO is 6648.77, 3761.29, and 2498.68, respectively. Similarly, for Test Problem 2, the average CPU time for IBA, GA, and PSO is 5748.48, 2544.66, and 3230.83, respectively. Thus, PSO and GA are faster than IBA. The main reason is that IBA must update the memory list to maintain the diversity of solutions for each iteration.
We used the following statistical hypothesis using 50 trials to further analyze the performance of IBA, GA, and PSO algorithms for each test problem:
P-value (95%) of the statistical hypothesis for two test problems
We presented a new MMSO problem, which differs from the typical OSSP, JSSP, VRP, PVRP, HMP, OSSP, and MDOP. We proposed a new encoding scheme to convert any random sequence of integers into a feasible solution of the MMSO problem. We applied an IBA to solve two applications in aircraft maintenance and physical examination. We presented and compared the numerical results of IBA with those of GA and PSO. Numerical results showed that IBA is more effective and robust for solving the considered MMSO problem than the two other algorithms.
In the future, a generalized MMSO problem in which identical machines can be cooperative may be considered to conduct the operation of a task simultaneously. Thus, the completion time (makespan) can be shortened. In addition, other artificial intelligence algorithms can be used to solve MMSO problems and compare their numerical results with those of the methods adopted in this study.
Footnotes
Acknowledgment
We appreciate Mr. K.C. Su for the collection of partial numerical results of experiments. This research was partially supported by Ministry of Science and Technology, Taiwan, under Grant No. MOST 106-2221-E-150-039 and MOST 107-2221-E-150-026.