TOP DOI 10.1007/s11750-017-0445-4 ORIGINAL PAPER
Joint production and preventive maintenance scheduling for a single degraded machine by considering machine failures Ali Salmasnia1 · Danial Mirabadi-Dastjerd2
Received: 20 May 2016 / Accepted: 21 March 2017 © Sociedad de Estadística e Investigación Operativa 2017
Abstract Production scheduling and maintenance planning are two interdependent issues that most often have been investigated independently. Although both preventive maintenance (PM) and minimal repair affect availability and failure rate of a machine, only a few researchers have considered this interdependency in the literature. Furthermore, most of the existing joint production and preventive maintenance scheduling methods assume that machine is available during the planning horizon and consider only a possible level for PM. In this research, an integrated model is proposed that coordinates preventive maintenance planning with single-machine scheduling to minimize the weighted completion time of jobs and maintenance cost, simultaneously. This paper not only considers multiple PM levels with different costs, times and reductions in the hazard rate of the machine, but also assumes that a machine failure may occur at any time. To illustrate the effectiveness of the suggested method, it is compared to two situations of no PM and a single PM level. Eventually, to tackle the suggested problem, multi-objective particle swarm optimization and non-dominated sorting genetic algorithm (NSGA-II) are employed and their parameters are tuned Furthermore, their performances are compared in terms of three metrics criteria. Keywords Single machine scheduling · Weighted completion time · Maintenance cost · Preventive maintenance · Minimal repair · MOPSO · NSGA-II Mathematics Subject Classification 90C15
B
Ali Salmasnia
[email protected]
1
Department of Industrial Engineering, Faculty of Engineering and Technology, University of Qom, Qom, Iran
2
Department of Industrial Engineering, Faculty of Engineering, Eyvanekey University, Eyvanekey, Iran
123
A. Salmasnia, D. Mirabadi-Dastjerd
1 Introduction Production scheduling is to optimize the job sequence in a manufacturing system. In this regard, the classical scheduling methods assume that a machine is available at all times on the planning horizon. This assumption is not reasonable in real-world problems because machines are not often continuously available due to breakdowns, tool changes, preventive maintenance (PM) activities, etc. In fact, it is not uncommon to encounter with the machine unavailable situation while there are jobs waiting to be performed by the given machine (Xu et al. 2008). Single machine scheduling has attracted great attention for two reasons: (1) sometimes it is used directly in real manufacturing environments such as a computer center, CNC-machine, IC-testing equipment, etc. (2) The single-machine problem does not necessarily involve only one machine; a complicated machine environment with a single bottleneck may be treated as a single machine (Liao and Juan 2007). Adiri et al. (1989) presented a scheduling method for a single machine to minimize the total completion time by considering a machine availability constraint. In that paper, it was assumed that if the machine fails during a job operation, the process is stopped and after the machine repair, the same job must be processed from the beginning. A two parallel machine-scheduling problem to minimize total completion time was studied by Lee and Liman (1993).This model aims to optimize the sum of job flow-time subject to scheduled maintenance by employing the dynamic programming algorithm. Mosheiov (1994) presented a model similar to Lee and Liman (1993) with the difference that the machine availability constraint is added to the model. A survey of scheduling models considering machine unavailability was given by Schmidt (2000). One common activity for satisfying the availability constraint is employing preventive maintenance. As time progresses, the machine often deteriorates gradually and PM activities can be performed as actions to control the deterioration process. In other words, PM means all activities to prevent failure and preserve a machine in a suitable operating condition. Maintenance planning attempts to keep machines in acceptable condition while production scheduling investigates the capacity of the machine and assigns jobs. Despite the interdependency between production scheduling and preventive maintenance planning, this relationship has been considered as a conflict in managerial decision-making. To avoid these conflicts and enhance the efficiency of the system, PM activities and job process time should be considered concurrently. In this regard, Lee (1996, 1999) presented the primary research in optimizing maintenance activities and production scheduling, simultaneously. In this research, the number of PMs and the running time of them are fixed and pre-known, and the machine may become unavailable in the planning horizon. Qi et al. (1999) developed an integrated single-machine scheduling problem with periodic PM in which the objective is to minimize the total completion time of jobs. In that model, several intervals were considered in which machines are unavailable. Espinouse et al. (1999) presented a flow-shop scheduling problem with limited machine availability, which aims to minimize the maximal completion time. Lee and Chen (2000) suggested an integrated model for parallel machine scheduling to optimize production scheduling and PM planning during the planning horizon, simultaneously. Cassady and Kutanoglu (2003) presented an integrated mathematical model for single machine scheduling that aims to minimize total weighted tardiness while
123
Joint production and preventive maintenance. . .
considering PM planning. The integrated model was compared with machine scheduling and preventive maintenance planning, separately. The comparison result indicated that coordination of preventive maintenance planning with scheduling decisions leads to a reduction of approximately 30% in expected total weighted tardiness. Cassady and Kutanoglu (2005) also suggested a similar research for minimizing the expected weighted completion time of jobs. Xie and Wang (2005) proposed a two-stage flexible flow-shop subject to an availability constraint and provided some approximation algorithms to tackle the worst possible case. Gharbi and Kenne (2005) proposed a new model for a multi-machine manufacturing system that minimizes total system cost consisting of inventory control, repair, and PM costs. Berrichi et al. (2008) presented an integrated model to avoid conflicts of production scheduling and PM planning. They minimized makespan and system unavailability by using a Non-dominated sorting genetic algorithm (NSGA-II). Berrichi et al. (2010) improved the previous model by using multi-objective ant colony optimization (MOACO) and compared solutions with multi-objective genetic algorithms (MOGAs). Rebai et al. (2010) aimed to minimize the preventive maintenance cost such that a set of M preventive maintenance tasks have to continuously be run during the schedule horizon on M machines. Mokhtari et al. (2011) suggested an integration of parallel machine scheduling and PM planning with multiple PM services to minimize makespan. They devised the population-based variable neighborhood search (PVNS) algorithm and compared it with variable neighborhood search (VNS). Khatami and Zegordi (2017) developed a bi-objective problem in the flow-shop scheduling environment that considers minimization of the system unavailability as the maintenance planning criterion and minimization of the makespan as the production scheduling criterion. Yalaoui and Khalil (2014) presented integrated production scheduling and PM planning in a system with several products and several production lines on a finite time horizon. Fitouhi and Nourelfath (2014) presented an integrated non-cyclical preventive maintenance scheduling and production planning method for multi-state systems. They optimized the total cost consisting of inventory holding cost, backorder cost, production cost and set-up cost by simulated annealing. Unlike this paper, the existing papers in the literature either do not consider PM activities or only consider one level for PM activities that restore the machine to as good as new condition. Multiple objective approaches to solve the scheduling problems were gradually presented. In this regard, Moradi and Zandieh (2010) minimized system unavailability and makespan by considering PM activities. Bandyopadhya and Bhattacharya (2013) proposed a multi-objective model for parallel machines that optimizes tardiness cost, deterioration cost of the machines and the maximal completion time, simultaneously. They compared the performance of NSGA-II and Strength Pareto Evolutionary Algorithm-2 (SPEA2) on the mentioned problem. Gao et al. (2014) proposed discrete harmony search (DHS) for minimizing makespan and the mean of earliness and tardiness in the flexible job-shop scheduling problem (FJSP). Li et al. (2014) developed a heuristic-search genetic algorithm (HSGA) for multiple-stage hybrid flow shop. They showed that HSGA has a proper performance in minimizing the makespan and the total weighted tardiness. Ghodratnama et al. (2015) proposed a multi-route flexible flow shop model that considers three minimization objectives: weighted delays, capital for the purchase of machines at stations, and the funds allo-
123
A. Salmasnia, D. Mirabadi-Dastjerd
cated to select the best processing route of parts. Wang and Liu (2015) presented a multi-objective parallel machine scheduling problem by considering flexible PM activities on both machines and moulds. Salmasnia et al. (2015) presented a stochastic programming model named GPE-model that minimizes mean completion time and earliness/tardiness cost. That paper demonstrated that the GPE-model has better performance than goal programming to incorporate objectives. It is worth noting that most of the existing multi-objective approaches only focus on scheduling and assume that the machine is always available ignoring machine failures. In this paper, an integrated mathematical model for production scheduling and preventive maintenance planning of a single machine is presented. The main contributions of this study could be summarized as follows: 1. In contrast to most of the existing approaches, it considers multiple levels for PM activity. The effect of PM is that it leads to a rejuvenation of the machine so that it effectively reduces the age of machine. The reduction in the age depends on the PM level used. 2. The proposed method assumes that the hazard rate of the machine increases over time and considers that the machine may fail at each moment. In this situation, minimal repair is performed on the machine. It means that the hazard rate of the machine after repair is nearly the same as that just before failure. 3. The proposed method optimizes weighted completion time and maintenance cost, simultaneously. Table 1 demonstrates a comparative study to investigate the characteristics of various scheduling models presented in the literature based on the number of objective functions, number of PM levels and machine failure consideration. The rest of this study is structured as follows: Sect. 2 contains a detailed description of the integrated model. In Sect. 3, the joint production scheduling and preventive maintenance planning problem is formulated for a single machine system. The solution approach is proposed in Sect. 4. The multi-objective evolutionary algorithm results are presented in Sect. 5, and Sect. 6 is devoted to the conclusion and possible future research.
2 Problem definition A static single machine-scheduling problem with multiple preventive maintenance levels is presented in which the machine is not available permanently. The static scheduling problem consists of problems in which jobs do not change during the planning horizon (Leung 2004; Baker and Trietsch 2009). In this paper, we aim to minimize both the maintenance cost and the weighted completion time that belongs to the class of NP-hard problems. Before presenting the model, the assumptions made for formulating the problem are given as below: • there are n independent jobs that are available from the beginning of the planning horizon. • The machine cannot perform more than one job at a time. • The number of jobs is pre-specified and job preemption is not permitted.
123
a It means that the time of minimal repairs is considered in calculating the completion time of the jobs
This paper
MOPSO and NSGA-II
MIP solver
Modified NSGA-II
Wang and Liu (2015)
GPE-model
Salmasnia et al. (2015)
Fix and relax (heuristic)
ACS (heuristic)
Khatami and Zegordi (2017)
Yalaoui and Khalil (2014)
Modified NSGA-II
PVNS
SBSPGA
Total enumeration
NSGA-II and MOPSO
Ant colony
BFD-LPT
NSGA-II and genetic
LPT
Solving method
Ghodratnama et al. (2015)
Multiple level
Machine failurea
Single level
Single
Multiple
PM level(s)
Objective function(s)
Bandyopadhya and Bhattacharya (2013)
Mokhtari et al. (2011)
Moradi et al. (2011)
Cassady and Kutanoglu (2005)
Berrichi et al. (2010)
Xu et al. (2008)
Berrichi et al. (2008)
Xie and Wang (2005)
References
Table 1 A characteristic comparison of the scheduling models
Joint production and preventive maintenance. . .
123
A. Salmasnia, D. Mirabadi-Dastjerd
• The machine failure has a Weibull probability distribution with a shape parameter greater than 1. • Setup and idle times are negligible compared to the planning horizon. • The initial age of the machine is set to zero. Moreover, machine failures are categorized into two types: in the first type, the machine fails suddenly and unexpectedly which is called the catastrophic failure. This type of failure is often dangerous and costly in real manufacturing systems. In this case, a minimal repair returns the machine to an operational state without changing the hazard rate value. In other words, the minimal repair restores the machine to “as bad as old” situation. In the second failure type, the machine degrades and its hazard rate value increases over time. To prevent this type of machine failure, PM activity on the machine is performed. It leads to the rejuvenation of the machine in a way that the reduction in virtual machine age depends on the PM level used. Hence, in this study, unlike most of the existing approaches in the literature, the machine is restored to “as good as new” condition only when the highest level of PM is performed. Obviously, the PM activities cannot omit unexpected failures completely; for this reason, the minimal repair is considered beside the PM activities. The notations and definitions used to formulate the problem are presented in Table 2.
3 Mathematical modeling As mentioned in Sect. 2, this study presents a joint production and preventive maintenance scheduling model for a single degraded machine by considering machine failures. The model under consideration is investigated with two performance measures: (1) minimization of the maintenance cost (TC), which consists of the preventive maintenance cost, and the minimal repair cost and (2) minimization of the total weighted completion time (WCT). To calculate the maintenance cost, the hazard rate function must be determined. The hazard rate function refers to the rate of occurrence of machine failures that is f (t) , where f (t) is the machine failure density function and F(t) defined by h(t) = 1−F(t) denotes the machine failure distribution function. In other words, h(t) represents the conditional probability density that a t-time unit-old machine will fail. Suppose that the time to the failure of the machine follows a Weibull probability distribution and consequently, the hazard rate can be computed as follows: h(t) =
β β−1 t ηβ
(1)
Figure 1 illustrates the behavior of the hazard rate function in various time horizons when the scale parameter is 150 and the shape parameter varies from 2 to 10. Obviously, the hazard rate is nonlinear (if β > 2) and an increasing function of time. As illustrated in Fig. 1, as β increases the expected number of machine failures decreases. Consequently, β and t have a reverse effect on the hazard rate function. According to the mentioned explanations, the hazard rate is an increasing function of the machine age. In these situations, implementation of PM activities on the machine can be a prac-
123
Joint production and preventive maintenance. . . Table 2 Notations Notation
Description
Indices j
Index of jobs, j = 1, 2, . . ., n
i
Index of PM levels, i = 1, 2, . . ., m
k, l, h
Indices of sequence positions, k, l, h = 1, 2, . . . , n
Parameters β
Weibull shape parameter
η
Weibull scale parameter
ϕi
Age reduction factor when the ith PM level is performed
P[k]
Processing time of the kth job in the sequence
a[k]
Age of the machine before the kth job in the sequence
N[k]
Number of machine failures during processing time of kth job in the sequence
E[N[k] ]
The expected value of N[k]
h(t)
Hazard rate function
CPRi
Cost of the ith level of PM
CMR
Minimal repair cost
t pi
Processing time of the ith PM level
tr
Processing time of minimal repair
wj
Weight of the jth job
w[k]
Weight of the kth job in the sequence
C[k]
Completion time of the kth job in the sequence
E(C[k] )
The expected value of completion time of the kth job in the sequence
Decision variables z i[k]
1 0
if the ith PM level is performed before the kth job sequence otherwise
X [k] j
1 0
if the jth job is performed in the kth job sequence otherwise
tical way to reduce the expected value of machine failures. The effect of preventive maintenance is that it leads to a rejuvenation of the machine in a way that it effectively reduces the age of the machine. The reduction in the age depends on the PM level used. In other words, each PM activity reduces the machine age corresponding to its age reduction factor, and hence the machine effective age or virtual age is less than its actual age. Equations (2)–(4) compute the virtual age of the machine before the kth job sequence in three partitioned states, respectively. (1) There is no PM activity prior to the kth job in the sequence; (2) the first PM activity is performed in the ith level before the kth job in the sequence; and (3) the ith PM level is performed prior to the kth job in the sequence while prior to the lth job in the sequence, the latest PM activity has been performed.
123
A. Salmasnia, D. Mirabadi-Dastjerd
Fig. 1 Hazard rate function when η = 150
⎧ a[k−1] (2) ⎪ ⎪ + p[k−1] ∀i, l, 1 ≤ l < k, z i[l] = 0, ∀i z i[k] = 0 ⎪ ⎪ k−1 ⎪ ⎪ ⎪ p[q] ∃i z i[k] = 1, ∀i, l1 ≤ l < kz i[l] = 0 (3) ⎪ ⎨ ϕi a[1] + q=1 a[k] = k−1 ⎪ ⎪ ⎪ ϕi a[l] + p[q] ∃i z i[k] = 1, ∃i, l1 ≤l < k z i[l] = 1, ∀i, hl < h < kz i[h] = 0 ⎪ ⎪ ⎪ q=l ⎪ ⎪ ⎩ (4)
Since discontinuity in operations may decrease the quality level of the process, the PM activity can only be performed before starting a job (or after finishing a job) without idle time. For an instance, consider the Example 1. Example 1 An illustrative example with six jobs and two levels of PM activity is shown in Fig. 2. It is supposed that two PM activities are performed on the machine before the third and the sixth job sequences and the sequence of jobs on the machine is {Job2, Job5, Job1, Job6, Job4, and Job3}. Processing times of the jobs are shown in Table 3 while the age reduction factors for PM levels are assumed to be ϕ1 = 0.3 and ϕ2 = 0.8. According to the information given, the virtual age of the machine 2
2
5 1
1
1 2
6 3
4 4
Fig. 2 Gantt chart of the joint production scheduling and maintenance planning
123
3 5
6
Joint production and preventive maintenance. . . Table 3 Processing time of jobs
Table 4 Virtual age of machine before each job sequence
Job
J1
J2
J3
J4
J5
J6
Processing time (min)
25
12
20
30
17
16
Sequence (k)
ak
Z i[k]
Value
1
0
0
0
2
a2−1 + p[2−1]
3−1 ϕ2 a1 + q=1 p[q]
0
12
1
23.2
4
a3−1 + p[3−1]
0
48.2
5
a4−1 + p[4−1]
6−1 ϕ1 a3 + q=3 p[q]
0
64.2
1
28.26
3
6
Virtual Age
Real Age
120 100 100 70
AGE
80 54
60
64.2
40
29
48.2
12
20
28.26
23.2
0 12
0 1
2
3
4
5
6
SEQUENCE Fig. 3 Illustration of virtual age and calendar age
before each job sequence by assuming a1 = 0 is calculated and the results are shown in Table 4. As shown in Fig. 3, each preventive maintenance activity according to its level could reduce the virtual age and increase the performance of the machine. While the higher level of PM has been implemented before the 6th sequence, the difference between the virtual age and the calendar age before the 6th sequence is more tangible than the third sequence. In the following, for calculating the expected number of machine failures in each sequence, the processing time of the kth job in the sequence must be calculated from Eq. (5).
123
A. Salmasnia, D. Mirabadi-Dastjerd
p[k] =
n
p j × x[k] j ∀k; k = 1, 2, . . . , n
(5)
j=1
The number of failures at a given operational period is one of the most important metrics; the expected value for the number of machine failures in the processing time of the kth job in the sequence can be formulated as Eq. (6): E[N[k] ] =
a[k] +P[k]
h(t)dt
(6)
a[k]
Therefore, Eq. (7) represents the weight of kth job in the sequence and Eq. (8) shows the expected value for the completion time of the kth job in the sequence. The expected completion time depends on the following: (1) the processing time of the jth job in the sequence; (2) the processing time of the ith PM level on the machine; and (3) the repair time and the expected value for the number of machine failures in the processing time of the jth job in the sequence. w[k] =
n
w j x[k] j
(7)
( p[ j] + t pi z i[ j] + tr E[N[ j] ])
(8)
j=1
E(C[k] ) =
k j=1
Therefore, the resulting mathematical programming formulation is shown below: min TC = min WCT =
n k=1 n
E[N[k] ]CMR +
i
CPRi z i[k]
(9)
k
w[k] E(C[k] )
(10)
j=1
Subject to n k=1 n
x[k] j = 1 j = 1, 2, . . . , n
(11)
x[k] j = 1 k = 1, 2, . . . , n
(12)
j=1
x[k] j binary j = 1, 2, . . . , n k = 1, 2, . . . , n Z i[k] binary k = 1, 2, . . . , n i = 1, 2, . . . , n Equations (9) and (10) show the objective functions. Constraint set (11) ensures that each job is performed in one sequence. Constraint set (12) ensures that only one job is performed in each sequence.
123
Joint production and preventive maintenance. . . Non-dominated sorting
Merge
( )
( + 1)
1
( )= ( )+ ( )
( )
Crowding distance sorting
2
Accepted
3
4
Rejected
5
Fig. 4 Schematic of the NSGA-II procedure (Deb 2001)
4 Solution approach This section aims to generate a Pareto optimal set to provide sufficient insight into trade-offs between the maintenance cost and the weighted completion time. Carlyle et al. (2003) introduced three desirable properties for evaluating the quality of a Pareto optimal set, namely the set coverage metric, spacing metric and number of Pareto solution. According to the mentioned properties, two evolutionary multi-objective optimization algorithms NSGA-II and MOPSO are selected to generate the efficient Pareto optimal set that will be explained in Sects. (4.1) and (4.2), respectively.
4.1 Non-dominated sorting genetic algorithm-II (NSGA-II) The non-dominated sorting genetic algorithm (NSGA-II) is one of the most efficient and famous multi-objective evolutionary algorithms that was introduced by Deb et al. (2002). NSGA-II is an elitist multi-objective evolutionary algorithm (MOEA) which employs non-dominated sorting and crowding distance operators to rank and choose the population fronts. In the first step, NSGA-II generates the offspring Q t from the parent population Pt by applying tournament selection, recombination (crossover) and mutation operators. Then, these two populations are merged to form the entire population Rt of size of 2N , where N is the population size. Next, the non-dominated sorting operator is employed to classify Rt . Finally, the new population is filled by solutions of different fronts Fi on the basis of their ranks. If the number of solutions in the last selected front is more than the remaining slots in the new population, the crowding sort procedure is performed to choose the members in a way that a diverse set of solutions is selected from this front set. Explicitly, Figs. 4 and 5 illustrate the NSGA-II schematic procedure and the main steps of NSGA-II, respectively. Likewise, the pseudo code for the non-dominated sorting algorithm, which is applied as a step of NSGA-II is shown in Fig. 6. In the following subsections, the used operators in our NSGA-II are explained in detail:
123
A. Salmasnia, D. Mirabadi-Dastjerd
Fig. 5 Main steps of NSGA-II
123
Joint production and preventive maintenance. . .
Fig. 6 Procedure of the non-dominated sorting algorithm
Job 6
Job 2
Job 7
PM 2
Job 3
Job 5
Job 4
PM 1
Job 1
Job 8
Fig. 7 Chromosome representation
4.1.1 Solution representation in NSGA-II Since this paper addresses joint production and preventive maintenance scheduling, the length of an individual solution is equal to the number of jobs and PM activities. In other words, the length of a solution is not a pre-determined number and can vary in the interval [n, 2n − 1], where n is the number of jobs. As an Example, Fig. 7 depicts a typical solution with eight jobs and two PM activities in which PM activities are performed on a machine based on the second and first PM levels before the fourth and the seventh job sequences, respectively. Moreover, the sequence of jobs on the machine is considered as {Job6, Job2, Job7, Job3, Job5, Job4, Job1 and Job8}. 4.1.2 Crossover As mentioned before, a solution in this paper involves two separated parts: i.e. the production part and maintenance part, and according to the explanations in solution representation, two selected solutions for crossover may have different lengths. Therefore, to perform crossover, the production and maintenance parts separate as is depicted in Fig. 8. Then, two-point crossover and single-point crossover are conducted on the job sequence part and the maintenance part, respectively. Finally, the two new constructed parts combine and generate a new solution as is illustrated in Fig. 9.
123
A. Salmasnia, D. Mirabadi-Dastjerd Job sequence part:
Parent 1:
Parent 2:
Job6
Job4
PM2
Job5
Job3
PM3
PM1
Job2
Job1
PM3
PM1
Job1
Job2
PM1
Job5
Job3
Job6
Job3
Job1
Job2
Job5
Job4
Maintenance part:
PM2
PM1
PM3
Job sequence part:
Job4
Job5
Job2
Job1
Job3
Job6
PM3
PM1
PM1
PM2
Job4
PM2
Job6
Maintenance part:
Fig. 8 Separation of the job sequence and the maintenance parts
Job6
Job3
Job1
Job2
Job5
Job4
Job6
Job3
Job2
Job1
Job5
Job4
Job4
Job5
Job1
Job2
Job3
Job6
PM3
PM1
PM3
PM2
PM1
PM1
Two Point Crossover Job4
Job5
Job2
PM2
PM1
PM3
Job1
Job3
Job6
Single Point Crossover PM3
Job6
Job3
PM1
Job2
PM1
Job1
PM2
Job5
Job4
Offspring1:
PM3
PM1
PM3
Job4
Job5
Job1
Job2
Job3
PM1
PM1
Job6
PM3
Job3
PM1
Job2
PM3
Job1
Job5
Job4
Job4
Job5
PM2
Job1
PM1
Job2
PM1
Job3
PM2
Job6
Offspring 2:
PM2
PM2
Fig. 9 The generation of two offsprings from two parents by crossover operators
123
PM2
Job6
Joint production and preventive maintenance. . . Fig. 10 Swap operator
Swap
Job1
Job2
Job3
Job4
Job5
Job6
Job7
Job1
Job5
Job3
Job4
Job2
Job6
Job7
Fig. 11 Insertion operator
Insertion
Job1
Job2
Job3
Job4
Job5
Job6
Job7
Job1
Job2
Job5
Job3
Job4
Job6
Job7
4.1.3 Mutation The main purpose of the mutation operator is to avoid getting trapped into a local optimal and to increase the diversification of the algorithm (Zoulfaghari et al. 2014). In this study, similar to crossover, mutation is also performed on the two parts of the job sequence and the maintenance, separately. To execute a mutation operator on the maintenance part, a random integer number between 1 and the number of the used PM activities in the given solution is generated. Then, the corresponding gene to the generated random number is varied to a possible value except its prior value. Regarding the job sequence part, three mutation operators, called swap, insertion and reversion are applied with the equal probabilities. 4.1.3.1. Swap operator In the swap operator, two random integer numbers r1 and r2 (1 ≤ r1 , r2 ≤ n, where n is the number of jobs) are generated. Then, the jobs on the positions r1 and r2 are swapped. An example of the swap operation is illustrated in Fig. 10. 4.1.3.2. Insertion operator The insertion operator generates two random integer numbers r1 and r2 in the interval [1, n]. Next, it inserts the corresponding gene to the larger generated random number after the corresponding gene to the other random number as is shown in Fig. 11. 4.3.1.3. Inversion operator In the inversion operator, two genes (job sequences) are randomly selected and the sequences of jobs between the two chosen genes are inverted. An example of inversion operation is illustrated in Fig. 12. 4.2 Multi-objective particle swarm optimization (MOPSO) Coello (2004) extended the PSO algorithm as one of the fastest algorithms for solving multi-objective optimization problems that is called multi-objective particle swarm optimization (MOPSO). In the first step, MOPSO initializes a swarm of particles. Then, the non-dominated solutions are selected and stored in an external archive, called
123
A. Salmasnia, D. Mirabadi-Dastjerd Fig. 12 Inversion operators
Inversion
Job1
Job2
Job3
Job4
Job5
Job6
Job7
Job1
Job2
Job5
Job4
Job3
Job6
Job7
a repository. Next, the hyper cubes are constructed via dividing the search space to select a leader for each particle of the swarm. The classical roulette wheel selection is applied to select a hypercube in which the selection probability of each hypercube is considered to be the inverse proportion of the number of repository members in the given hypercube. Later on, a leader is determined randomly and the position of a particle is updated. Finally, the mutation operator is performed to better search and the personal best position is updated. Figure 13 illustrates the pseudo code of the MOPSO algorithm. 4.2.1 Solution representation in MOPSO According to the mentioned explanations, the problem addressed in this study consists of two separated parts, i.e. the production part and the preventive maintenance part. Furthermore, it is assumed that a PM activity can only be performed before starting a job. Hence, a solution is represented by a vector with the length of 2n − 1, in which the production and maintenance parts are embedded in the odd and even elements, respectively. It is worth noting that the velocity vector is updated in a continuous space. To deal with this situation, the encoding process is implemented by n numbers in the interval [0, 1] for the production part and for the decoding of a solution a sort operator is employed. As an example, Fig. 14 illustrates a typical solution with five jobs and three PM activities in which three PM activities are performed on the machine based on the second, third and first PM levels before the second, fourth and the fifth job sequences, respectively, and no PM activity is scheduled before the third job sequence. 4.2.2 Mutation In this study, to increase the diversification of the algorithm, the single point mutation operator is performed on the maintenance part (Karasakal and Silav 2016). This operator selects one of the maintenance part elements randomly and substitutes its content by another PM level. A typical example of the mutation operation is depicted in Fig. 15.
5 Computational results In this section, we aim to investigate two issues: (1) assessing the performance of the NSGA-II and MOPSO algorithms; and (2) comparing the developed multi-PM-levels
123
Joint production and preventive maintenance. . .
Fig. 13 Main steps of MOPSO
123
A. Salmasnia, D. Mirabadi-Dastjerd
Production part ( elements):
0.15
0.97
0.95
0.48
0.80
Job 5
Job 3
Job 2
Maintenance part ( − 1 elements)
Sorting operation
Job 1
Job 4
PM2
Odd elements
0
PM3
PM1
Even elements
Solution (2 − 1): Job1
PM2
Job4
0
Job5
PM3
Job3
PM3
Job3
PM1
Job2
Job3
PM1
Job2
PM1
Job2
Fig. 14 A typical solution in the MOPSO algorithm
Job1
PM2
Job4
0
Job5
Mutation operator: change PM level randomly
PM1
Job1
PM2
Job4
0
Job5
PM1
Fig. 15 Mutation operator in the MOPSO algorithm
model with the existing methods in the literature consisting of no-PM and one-PMlevel techniques. In this regard, three criteria for the comparison of non-dominated sets are introduced in Sect. 5.1. Then, to analyze the NSGA-II and MOPSO, three classes of instances, i.e. small, medium and large are defined in Sect. 5.3. These instances are different in the number of jobs and PM levels. Finally, to demonstrate the effectiveness of the proposed multi-PM-levels, it is compared with the no-PM and one-PM-level models in Sect. 5.4.
5.1 Criteria for comparison of NSGA-II and MOPSO To compare the different aspects of the obtained non-dominated fronts by the NSGA-II and MOPSO, three performance metrics are used that are called normalized set coverage metric, spacing metric and number of Pareto solutions. The following subsections give brief descriptions of these criteria.
123
Joint production and preventive maintenance. . .
¯ 5.1.1 Normalized set coverage metric (C) The set coverage metric was proposed by Zitzler and Thiele (1999) for comparing two sets of non-dominated solutions. Assume in a problem, two Pareto sets A and B are generated. The set coverage metric C (A, B) calculates the fraction of solutions B that are weakly dominated by at least one solution in set A (Alberto and Mateo 2011). This metric gives us the contribution of the estimated Pareto front (Karasakal and Silav 2016). |{b ∈ B|∃a ∈ A : a b}| , (13) C (A, B) = |B| where a b means that solution b is weakly dominated by solution a. C(A, B) = 1 means that all the generated non-dominated solutions in B are weakly dominated by set A. On the other hand, C(A, B) = 0 indicates that none of the solutions in set B can be weakly dominated by solutions in A. It is worth noticing that C(A, B) is equal to 1−C(B, A) only when the number of solutions in set A are equal to B. To simplify the ¯ is proposed comparison of the two Pareto sets, the normalized set coverage metric (C) as it is formulated in Eq. (14). This equation assures C¯ (A, B) = 1 − C¯ (B, A) which makes the comparison of algorithm’s performance easier than the set coverage metric. With respect to the mentioned definition, C¯ (A, B) ≥ C¯ (B, A) demonstrates that set A has better coverage than B. C¯ (A, B) =
C (A, B) ⇒ C¯ (A, B) = 1 − C¯ (B, A) C (A, B) + C (B, A)
(14)
5.1.2 Spacing metric (Δ) The Spacing metric, which was introduced by Deb (2001), measures the spread of solutions of a Pareto set in the entire region through computing the variance of distances of the neighboring solutions in a given Pareto set. In other words, it reveals how well the non-dominated solutions are distributed in the search space. A lower value of this metric means that the members of the Pareto front are spread uniformly.
|n|
di − d¯ Δ= , |n|
(15)
i=1
2 i n di k 2 ¯ where di = mink∈n,k=i m=1 f m − f m , d = i=1 |n| , n denotes the number i of non-dominated solutions in the Pareto set and f m represents the amount the of mth objective function for the ith non-dominated solution. 5.1.3 Number of Pareto solutions (NPS) This metric is utilized for measuring the cardinality of the algorithm and a higher value for this performance metric demonstrates better performance of the algorithm.
123
A. Salmasnia, D. Mirabadi-Dastjerd Table 5 Levels of each parameter considered in the orthogonal experiment Algorithm NSGA-II
MOPSO
Parameter
Range
Level 1
Level 2
Level 3
Population size (PS)
20–100
20
50
100
Mutation rate (MR)
0.02–0.1
0.02
0.06
0.1
Crossover rate (CR)
0.3–0.9
0.3
0.6
0.9
Population size (PS)
20–100
20
50
100 100
Repository size (RS)
10–100
10
50
Number of grids in per dimension (nGrid)
2–10
2
5
10
Leader selection pressure (LSP)
0.5–1.5
0.5
1
1.5
5.2 Tuning of NSGA-II and MOPSO parameters Since the quality of the generated Pareto set by each algorithm is sensitive to the values of the parameters values, a L 9 Taguchi orthogonal array is utilized to tune them. To do this, three levels for each parameter is considered as shown in Table 5: To find the best level of each parameter, the algorithm is replicated three times for each run experiment. Then, the values of the weighted completion time and the maintenance cost attained through the experiments will be transformed into signal-tonoise ratios (SN) by Eqs. 16 and 17, respectively. Eventually, the optimal parameter level combinations are obtained by the TOPSIS index.
SNWCT j
SNTC j
1 = −10 × log WCT2jk 3 k=1 3 1 2 = −10 × log T C jk 3 3
j = 1, 2, . . . , 9 j = 1, 2, . . . , 9
(16)
(17)
k=1
The obtained results for SN ratios of the weighted completion time and the maintenance cost as well as the TOPSIS index for each run experiment can be seen in Table 6. Moreover, the optimal values for the parameters under consideration are tabulated in Table 7. Table 8 shows the ranking of the algorithm’s parameters through analysis of variance (ANOVA). 5.3 Test problems and simulation results To compare the performance of NSGA-II and MOPSO, the three mentioned metric criteria are measured on three classes of test problems, i.e. small, medium and large. The test problems are different in the number of PM levels (i) and number of jobs ( j) that are denoted by (i, j). The small class consists of three configurations of {(3, 10), (5, 10), (3, 12)} while the medium and large classes are produced from {(5, 15), (6, 15), (5, 25)} and {(7, 50), (9, 50), (7, 60)}, respectively. The supplementary information regarding the jobs can be seen in Appendix A.
123
100
100
100
7
8
9
TC
50
6
WCT
−91.82
WCT
50
TC
−66.79
TC
5
WCT
−91.97
WCT
50
−66.82
4
WCT TC
−90.36
WCT TC
20
3
0.1
0.06
0.02
0.1
0.06
0.02
0.1
0.6
0.3
0.9
0.3
0.9
0.6
0.9
0.81
0.47
0.86
0.41
0.38
0.38
0.96
0.88
TC
−67.06
0.5
TC
5
WCT
100
−90.39
WCT
100
TC
0.84
−67.56
1.5
TC
2
WCT
50
TC 100
−67.01 −90.89
0.90
TC
1
WCT
10
WCT
10
TC 100
−66.92 −90.29
0.11
TC
1
WCT
2
WCT
100
0.74
0.88
0.74
TC 50
0.5
1.5
1.5
−66.87
10
5
10
0.79
−91.61
50
10
100
1
WCT
50
50
20
5
WCT WCT
50
0.81
TC
20
0.5
−67.36
0.66
2
−90.44
0.6
10
TC
0.06
0.36 WCT
20
2
0.02
0.3 TC
20
20
Objective function
−91.56
TOPSIS index
−67.08
LSP
WCT
nGrid
TC
RS
MOPSO Objective function
PS
TOPSIS index
SN
CR
PS
MR
NSGA-II
1
Runs
Table 6 The SN ratios and TOPSIS index for the run experiments
−73.04
−91.36
−71.41
−94.48
−72.83
−91.20
−85.91
−92.12
−75.05
−92.66
−73.14
−91.14
−74.91
−92.95
−74.43
−91.56
−74.07
−91.56
SN
Joint production and preventive maintenance. . .
123
A. Salmasnia, D. Mirabadi-Dastjerd Table 7 The optimal values for the NSGA-II and MOPSO parameters Algorithm
Attribute
NSGA-II
MOPSO
Value
Population size (PS)
100
Mutation rate (MR)
0.1
Crossover rate (CR)
0.9
Population size (PS)
100
Repository size (RS)
10
Number of grids in per dimension (nGrid)
5
Leader selection pressure (LSP)
1.5
Table 8 Significant effects of parameters in ANOVA
Algorithm
Parameter
NSGA-II
MOPSO
P value
PS
0.241
1
MR
0.517
3 2
CR
0.278
PS
0.353
1
RS
0.382
2
nGrid
0.440
3
LSP
0.525
4
Populaon size
Mutaon rate
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0 20
50
100
0.02
Crossover rate 0.8 0.6 0.4 0.2 0 0.3
0.6
0.9
Fig. 16 TOPSIS index for the different levels of the NSGA-II parameters
123
Rank
0.06
0.1
Joint production and preventive maintenance. . .
Population size
Repository size
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0 20
50
100
10
Number of grids in per dimension
50
100
Leader selection pressure 4
1
3
0.8 0.6
2
0.4
1
0.2 0
0 2
5
0.5
10
1
1.5
Fig. 17 TOPSIS index for the different levels of the MOPSO parameters Table 9 Average simulation results on test problems
C¯ (NSGA-II, MOPSO)
Δ
NPS
NSGA-II
0.97
1095.69
10.17
MOPSO
0.03
2186
8.19
1.2 Set coverage
1 0.8 0.6 0.4 0.2 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 Problem
Set Coverage - MOPSO
Set Coverage - NSGA-II
Fig. 18 Comparison of NSGA-II and MOPSO on the basis of C¯ on 36 test problems
123
A. Salmasnia, D. Mirabadi-Dastjerd
25
NPS
20 15 10 5 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 Problem
NPS - NSGA-II
NPS - MOPSO
Spacing
Fig. 19 Comparison of NSGA-II and MOPSO on the basis of NPS on 36 test problems
16000 14000 12000 10000 8000 6000 4000 2000 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 Problem
Spacing - NSGA II
Spacing - MOPSO
Fig. 20 Comparison of NSGA-II and MOPSO on the basis of Δ on 36 test problems
To generate efficient solutions, the mentioned algorithms are implemented in the MATLAB software. To compare the non-dominated sorting algorithms, each algorithm is run four times for each test problem. Consequently, 36 Pareto sets are generated, which are used for comparative parametric and non-parametric statistical tests (Figs. 16, 17). Table 9 shows the average values of the metric criteria. Detailed computational results can be seen in Appendix B. The results demonstrate that NSGA-II often has smaller spacing metric values and greater NPS and normalized set coverage values in comparison with the MOPSO algorithm. In other words, the results confirm that the NSGA-II algorithm generates more proper Pareto sets compared to the MOPSO algorithm. Figures 18, 19 and 20 illustrate the obtained results for the normalized set coverage, number of Pareto solutions and spacing metric by NSGA-II and MOPSO on the 36 generated test problems graphically. The performance of the two algorithms also is evaluated by both parametric and non-parametric tests. The parametric t-test
123
C¯
Δ
NPS
Metrics
H0 : μNSGA−II = μMOPSO H1 : μNSGA−II > μMOPSO
H0 : μNSGA−II = μMOPSO H1 : μNSGA−II < μMOPSO
H0 : μNSGA−II = μMOPSO H1 : μNSGA−II > μMOPSO
Hypothesis
0.000
0.003
0.019
P value
Null hypothesis is rejected
Null hypothesis is rejected
Null hypothesis is rejected
Result
Mann–Whitney test
Table 10 Statistical comparison of NSGA-II and MOPSO
= m MOPSO > m MOPSO
= m MOPSO < m MOPSO
H0 : m NSGA−II = m MOPSO H1 : μNSGA−II > μMOPSO
H0 : m NSGA−II H1 : m NSGA−II H0 : m NSGA−II H1 : m NSGA−II
Hypothesis
0.000
0.053
0.009
P value
t test
Null hypothesis is rejected
Null hypothesis is not rejected
Null hypothesis is rejected
Result
Joint production and preventive maintenance. . .
123
A. Salmasnia, D. Mirabadi-Dastjerd Table 11 Possible types of PM activities in the multiple-PM model
PM level
ϕi
CPRi (cost)
1
0.77
100
2
0.56
300
9
3
0.32
500
19
t pi (time) 4
4
0.11
600
22
5
0
700
25
is utilized to study the difference between the mean values of NPS, Δ and C¯ in the generated Pareto sets by the NSGA-II and MOPSO algorithms. On the other hand, the non-parametric Mann-Whitney test is applied for investigating the difference in the median values of the criteria under consideration. The hypothesises are given in Table 10 in which μ and m are mean and median, respectively. The P values in Table 10 confirm that the NSGA-II has better performance in all three criteria.
5.4 A comparative study In this section, the suggested multiple-PM-levels method is compared with two models: no-PM and one-PM level. No-PM situation means to minimize the maintenance cost and the weighted completion time only by the setting of job sequences while in the one-PM-level model a PM activity can be implemented before starting a job that leads to restoration of the machine to as good as new situation. It is assumed that in the multiple-PM-levels model, five types of PM activities according to Table 11 can be employed before starting each job. In this regard, four artificial examples are used to validate the effectiveness of the multiple-PM level model that is shown in Table 12. Since in the previous section it was shown that NSGA-II has better performance than MOPSO in the joint production and preventive maintenance scheduling problem, the NSGA-II algorithm is used to solve each of the three mentioned models. After running NSGA-II for each example (See Appendix C), the mean of the total cost and the weighted completion time for the obtained non-dominated solutions are given in Table 12. Each example is solved five times. The average of the total cost and the weighted completion time for the three models of no-PM, one-PM and multiplePM are illustrated in Figs 21 and 22, respectively. Actually, in the No-PM model, the expected number of machine failures increases extremely, which results in spending too much time and money to restore the machine to an operational state. However, when PM activity is used, the machine is usually in the operational conditions and the risk of the unexpected failures decreases. On the other hand, the one-PM model uses only the highest PM level, which leads to a severe increase in the preventive maintenance cost in comparison with the suggested model. According to the description given and the results in Table 11 and Figs 21 and 22, the multiple-PM model has superiority over two other models and makes the problem more realistic.
123
Joint production and preventive maintenance. . . Table 12 Comparison of the multiple-PM model with No-PM and one-PM models n
TC
WCT
No PM
One PM
Multiple PM
No PM
One PM
Multiple PM
10
1857.4
30
33,374
1831.3
1783
54,191.8
40,600.8
39,259.6
9793.34
9623.92
1,264,640
516,094
497,198
50
78,092
15,866.4
15,662.8
6,394,680
1,600,200
1,576,560
80
158,980
24,700
23,342.2
8,000,940
3,548,220
3,477,440
180000 160000 140000
TC
120000 100000 80000 60000 40000 20000 0 no-PM
one-PM
mulple -PM
NUMBER OF PM LEVEL n=10
n=30
n=50
n=80
Fig. 21 Comparison of three models of no-PM, one-PM –level and multiple-PM-levels based on the total maintenance cost
9000000 8000000 7000000 WCT
6000000 5000000 4000000 3000000 2000000 1000000 0 No-PM
One-PM
mulple -PM
NUMBER OF PM LEVEL n=10
n=30
n=50
n=80
Fig. 22 Comparison of three models of no-PM, one-PM-level and multiple-PM-levels based on the weighted completion time
123
A. Salmasnia, D. Mirabadi-Dastjerd
6 Conclusion In this paper, a joint production and preventive maintenance scheduling approach for a single degraded machine was developed. It aimed to identify job sequences and PM levels to minimize both the total maintenance cost and the weighted completion time by assuming that every PM activity can only be performed between two job sequences. In contrast to the existing approaches, it considered that as the PM level increases, the virtual age and the hazard rate of the machine decreased and the machine only is restored to as good as new condition when the highest level of PM activity is implemented. Furthermore, the proposed model assumed that the machine might fail at any time, which in this situation the machine is rectified through minimal repair. Since in the multi-objective problems, it is logical to consider a set of solutions, because a solution only can be optimum for some objectives, this study employed NSGA-II and MOPSO as two well-known algorithms for generating the Pareto set. Their performance was evaluated based on three metric criteria on 36 test problems. Results show better performance of NSGA-II in comparison with MOPSO for solving joint production and preventive maintenance scheduling. Eventually, to verify the effectiveness of the proposed model, the problem was run in four different sizes, namely n = 10, 30, 50, 80 and compared with two existing models in the literature, i.e. no-PM and one-PM-level models. This comparison showed the superiority of the suggested multiple-PM-levels model. Furthermore, the results implied that the effect of employing different types of PM activities increases as the number of jobs increases. Finally, this is a known fact that a series-parallel layout of machines can improve system availability and the completion time of jobs, simultaneously. In other words, the series–parallel machines scheduling problem is one of the most common problems that manufacturers expect to encounter in industry environments. Consequently, the extension of the proposed model for this type of problem can be considered as a suitable for future research.
Appendix A The supplementary information of the used test problems are given in Table 13.
Table 13 Information of the test problems
(i, j) = (3, 10)
123
P[k]
[10
20
30
ϕi
[0.9
0.4
0]
t pi
[3
15
21]
tr
15
CPRi
[100
250
300]
CMR
190
P[k]
[10
20
30
15
75
32
42
11
52
70]
15
75
32
42
11
52
70]
Joint production and preventive maintenance. . . Table 13 continued
(i, j) = (5, 10)
(i, j) = (3, 12)
(i, j) = (5, 15)
(i, j) = (6, 15)
(i, j) = (5, 25)
(i, j) = (7, 50)
ϕi
[0.77
0.55
0.33
0.1
0]
t pi
[4
13
19
22
25]
tr
15
CPRi
[100
400
500
600
700]
CMR
190
P[k]
[16
72
10
57
53
22
67
46
50
47
22
75]
ϕi
[0.9
0.4
0]
t pi
[3
15
21]
tr
15
CPRi
[100
250
300]
CMR
190
P[k]
[10
20
30
15
75
32
42
11
52
70
20
18
36
47
51]
32
42
11
52
70
ϕi
[0.9
0.6
0.4
0.2
0]
t pi
[5
10
15
20
25]
tr
15
CPRi
[100
150
200
250
300]
CMR
190
P[k]
[10
20
30
15
75
20
18
36
47
51]
ϕi
[0.77
0.55
0.40
0.37
0.11
0]
t pi
[4
13
15
19
22
25]
tr
15
CPRi
[100
380
452
512
677
700]
CMR
190
P[k]
[16
72
10
57
53
22
67
46
50
47
78
37
72
16
50
20
19
68
90
61
26
59
48
87
68]
ϕi
[0.9
0.6
0.4
0.2
0]
t pi
[5
10
15
20
25]
tr
15
CPRi
[100
150
200
250
300]
CMR
190
P[k]
[16
72
10
57
53
22
67
46
50
47
78
37
72
16
50
20
19
68
90
61
26
59
48
87
68
61
89
81
60
19
94
66
70
81
38
25
33
98
25
40
3
78
45
12
100
68
45
16
32
54]
ϕi
[0.77
0.66
0.55
0.33
0.22
0.11
0]
t pi
[4
11
13
14
18
19
25]
tr
15
123
A. Salmasnia, D. Mirabadi-Dastjerd Table 13 continued
(i, j) = (9, 50)
(i, j) = (7, 60)
CPRi
[100
CMR
190
200
300
400
500
600
700]
P[k]
[16
72
10
57
53
22
67
46
50
47
78
37
72
16
50
20
19
68
90
61
26
59
48
87
68
61
89
81
60
19
94
66
70
81
38
25
33
98
25
40
3
78
45
12
100
68
45
16
32
54]
ϕi
[0.99
0.88
0.77
0.66
0.55
0.33
0.22
0.11
0]
t pi
[4
11
13
14
18
19
19
21
25]
tr
15
CPRi
[100
200
300
400
500
600
700
800
900]
CMR
190
P[k]
[16
72
10
57
53
22
67
46
50
47
78
37
72
16
50
20
19
68
90
61
26
59
48
87
68
61
89
81
60
19
94
66
70
81
38
25
33
98
25
40
3
78
45
12
100
68
45
16
32
54
61
38
50]
25
11
53
44
83
71
10
ϕi
[0.77
0.66
0.55
0.33
0.22
0.11
0]
t pi
[4
11
13
14
18
19
25]
tr
15
CPRi
[100
200
300
400
500
600
700]
CMR
190
Appendix B In this appendix, the detailed results of NSGA-II and MOPSO are reported in Table 14.
123
(3,12)
M109
M110
M111
22
23
M107
M108
19
20
21
M105
M106
17
M104
16
18
M102
M103
14
M101
13
15
S111
S112
11
12
S109
S110
9
10
(5,10)
S107
S108
7
8
(5,10)
(5,25)
(5,25)
(5,25)
(6,15)
(6,15)
(6,15)
(6,15)
(5,15)
(5,15)
(5,15)
(5, 15)
(3,12)
(3,12)
(3,12)
(5,10)
(5,10)
S105
S106
(3,10)
(3,10)
(3,10)
(3, 10)
(i, j)
5
Medium
Small
Size
6
S103
S104
3
4
S101
S102
1
2
Name
No
1
1
1
1
1
0.87
0.88
1
0.68
1
0.9
1
1
1
1
1
0.87
1
1
1
0.94
1
1
NSGA-II C¯ (NSGA-II, MOPSO)
Table 14 The detail simulation results on the test problems
159.87
70.17
1145.49
49.08
509.34
113.36
195.03
100.47
142.36
101.29
122.45
96.60
63.13
6.85
121.01
13.52
53.79
97.47
15.35
50.63
2.58
10.43
397.11
Δ
22
13
11
6
15
13
10
9
11
14
6
4
14
14
3
9
3
4
9
5
5
6
9
NPS
0
0
0
0
0
0.13
0.22
0
0.32
0
0.1
0
0
0
0
0
0.13
0
0
0
0.06
0
0
MOPSO C¯ (MOPSO,NSGA-II)
230.15
2642.15
708.54
1253.64
528.02
690.50
435.05
433.11
1338.40
447.45
285.69
127.86
518.08
72.49
334.18
162.21
405.49
162.21
389.78
2010.36
143.52
31.27
187.83
Δ
10
7
10
9
8
8
9
7
4
10
10
9
9
7
10
8
8
8
3
8
7
10
8
NPS
Joint production and preventive maintenance. . .
123
123
L111
L112
35
36
Average
L109
L110
33
34
L107
L108
31
32
L105
L106
29
L104
28
30
L102
L103
26
27
M112
L101
24
25
Name
No
Table 14 continued
Large
Size
(7,60)
(7,60)
(7,60)
(7,60)
(9,50)
(9,50)
(9,50)
(9,50)
(7,50)
(7,50)
(7,50)
(7,50)
(5,25)
(i, j)
0.97
1
1
1
1
1
1
1
1
1
1
1
1
0.62
NSGA-II C¯ (NSGA-II, MOPSO) 65.87
1095.699
4777.98
2973.09
6898.54
4224.65
1308.96
1993.15
1811.49
1017.43
1017.43
5220.46
1319.68
3179.04
Δ
10.17
9
10
14
5
9
14
13
10
10
14
19
16
8
NPS
0.03
0
0
0
0
0
0
0
0
0
0
0
0
0.38
MOPSO C¯ (MOPSO,NSGA-II)
2186
2065.24
11734.23
11734.23
328.85
1156.21
665.83
14165.14
6372.10
2636.57
6086.92
5626.69
1242.10
1334.74
Δ
8.19
10
8
10
10
6
9
7
8
9
6
5
10
10
NPS
A. Salmasnia, D. Mirabadi-Dastjerd
Joint production and preventive maintenance. . .
Appendix C In this appendix, the values of the objective functions for No-PM, One-PM and multiple-PM models are reported (Table 15).
Table 15 Comparison of the multiple-PM model with No-PM and One-PM models No
n
TC
WCT
No PM
One PM
Multiple PM
No PM
One PM
Multiple PM
1
10
1857.4
1762.4
1859.4
51,192
41,553
39,741
2
10
1857.4
1865.2
1808.5
64,447
39,850
40,509
3
10
1857.4
1727.3
1928.3
45,102
40,792
39,125
4
10
1857.4
1686.9
1923.9
58,292
40,754
37,791
5
10
1857.4
1714.7
1794.9
51,926
40,055
39,132
Average
1857.4
1831.3
1783
54,191.8
40,600.8
39,259.6
6
30
33,374
9697.8
9511.4
1,437,700
513,270
485,130
7
30
33,374
9435.6
9730.7
1,183,600
495,160
509,110
8
30
33,374
9879.6
9601.3
1,434,600
525,630
498,050
9
30
33,374
9553.7
9511.8
1,148,900
548,530
490,560
10
30
33,374
10,400
9764.4
1,118,400
497,880
503,140
Average
33,374
9793.34
9623.92
12,64,640
516,094
497,198
11
50
78,092
16,578
15,511
6,127,500
1,563,600
1,519,600
12
50
78,092
15,305
15,787
6,668,900
1,451,900
1,615,900
13
50
78,092
15,545
15,686
6,110,400
1,762,200
1,574,400
14
50
78,092
15,947
16,427
6,954,300
1,621,400
1,573,800
15
50
78,092
15,957
14,903
6,112,300
1,601,900
1,599,100
Average
78,092
15,866.4
15,662.8
6,394,680
1,600,200
1,576,560
16
80
158,980
24,797
23,134
9,364,100
3,568,600
3,493,600
17
80
158,980
24,863
22,989
9,430,600
3,619,200
3,283,900
18
80
158,980
24,995
23,728
10,084,000
3,780,800
3,470,500
19
80
158,980
24,725
23,282
10,107,000
3,453,600
3,397,800
20
80
158,980
24,120
23,578
1,019,000
3,318,900
3,741,400
158,980
24,700
23,342.2
8,000,940
3,548,220
3,477,440
Average
References Adiri I, Bruno J, Frostig E, Rinnooy Kan AHG (1989) Single machine flow-time scheduling with a single breakdown. Acta Inform 26:679–696 Alberto I, Mateo PM (2011) A crossover operator that uses Pareto optimality in its definition. TOP 19:67–92 Baker KR, Trietsch D (2009) Principles of sequencing and scheduling. Wiley, New York Bandyopadhya S, Bhattacharya R (2013) Solving multi-objective parallel machine scheduling problem by a modified NSGA-II. Appl Math Model 37:6718–6729
123
A. Salmasnia, D. Mirabadi-Dastjerd Berrichi A, Amodeo L, Yalaoui F, Châtelet E, Mezghiche M (2008) Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem. J Intell Manuf 20:389–400 Berrichi A, Yalaoui F, Amoedo L, Mezghiche M (2010) Bi-objective ant colony optimization approach to optimize production and maintenance scheduling. Comput Oper Res 37:1584–1596 Carlyle WM, Fowler JW, Gel ES, Kim B (2003) Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decis Sci 34:63–82 Cassady CR, Kutanoglu E (2003) Minimizing job tardiness using integrated preventive maintenance planning and production scheduling. IIE Trans 35:503–513 Cassady CR, Kutanoglu E (2005) Integrating preventive maintenance planning and production scheduling for a single machine. IEEE Trans Reliab 54:304–310 Coello CAC (2004) Handling multiple objectives with particle swarm optimization. IEEE Trans Evol Comput 8:256–279 Deb K (2001) Multiobjective optimization using evolutionary algorithms. Wiley, Chichester Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm. NSGA-II. IEEE Trans Evol Comput 6:182–197 Espinouse ML, Formanowicz P, Penz B (1999) Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability. Comput Ind Eng 32:497–500 Fitouhi MC, Nourelfath M (2014) Integrating noncyclical preventive maintenance scheduling and production planning for multi-state systems. Reliab Eng Syst Saf 121:175–186 Gao KZ, Suganthan PN, Pan QK, Chua TJ, Cai TX, Chong CS (2014) Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. J Intell Manuf 27:363–374 Gharbi A, Kenne JP (2005) Maintenance scheduling and production control of multiple-machine manufacturing systems. Comput Ind Eng 48:693–707 Ghodratnama A, Jolai F, Tavakkoli-Moghaddam R (2015) Solving a new multi-objective multi-route flexible flow line problem by multi-objective particle swarm optimization and NSGA-II. J Manuf Syst 36:189– 202 Karasakal E, Silav A (2016) A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage. TOP 24:206–232 Khatami M, Zegordi SH (2017) Coordinative production and maintenance scheduling problem with flexible maintenance time intervals. J Intell Manuf 28:857–867 Lee CY (1996) Machine scheduling with an availability constraint. J Glob Optim 9:395–416 Lee CY (1999) Two-machine flow-shop scheduling with availability constraints. Eur J Oper Res 114:420– 429 Lee CY, Chen ZL (2000) Scheduling jobs and maintenance activities on parallel machines. Nav Res Logist Q 47:145–165 Lee CY, Liman SD (1993) Capacitated two-parallel machine scheduling to minimize sum of job completion time. Discrete Appl Math 41:211–222 Leung JYT (2004) Handbook of scheduling, algorithms, models, and performance analysis. Chapman and Hall/CRC, Boca Raton Liao CJ, Juan HC (2007) An ant colony optimization for single-machine tardiness scheduling with sequencedependent setups. Comput Oper Res 34:1899–1909 Li D, Meng X, Liang Q, Zhao J (2014) A heuristic-search genetic algorithm for multi-stage hybrid flow shop scheduling with single processing machines and batch processing machines. J Intell Manuf 26:873–890 Mokhtari H, Mozdgir A, Nakhai Kamal Abadi I (2011) A reliability/availability approach to joint production and maintenance scheduling with multiple preventive maintenance services. Int J Prod Res 50:5906– 5925 Moradi E, Zandieh M (2010) Minimizing the makespan and the system unavailability in parallel machine scheduling problem: a similarity-based genetic algorithm. Int J Adv Manuf Technol 51:829–840 Moradi E, Fatemi Ghomi SMT, Zandieh M (2011) Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem. Expert Syst Appl 38:7169–7178 Mosheiov G (1994) Minimizing the sum of job completion times on capacitated parallel machines. Math Comput Model 20:91–99 Qi X, Chen T, Tu F (1999) Scheduling the maintenance on single machine. J Oper Res Soc 50:1071–1078
123
Joint production and preventive maintenance. . . Rebai M, Kacem I, Adjallah HK (2010) Earliness-tardiness minimization on a single machine to schedule preventive maintenance tasks: metaheuristic and exact methods. J Intel Manuf 23:1207–1224 Salmasnia A, Khatami M, Baradaran Kazemzadeh R, Zegordi SH (2015) Bi-objective single machine scheduling problem with stochastic processing times. TOP 23:275–297 Schmidt G (2000) Scheduling with limited machine availability. Eur J Oper Res 121:1–15 Wang S, Liu M (2015) Multi-objective optimization of parallel machine scheduling integrated with multiresources preventive maintenance planning. J Manuf Syst 37:182–192 Xie J, Wang X (2005) Complexity and algorithms for two-stage flexible flow-shop scheduling with availability constraints. Comput Math Appl 50:629–1638 Xu D, Sun K, Li H (2008) Parallel machine scheduling with almost periodic maintenance and nonpreemptive jobs to minimize makespan. Comput Oper Res 35:1344–1349 Yalaoui A, Khalil C (2014) Integrated production planning and preventive maintenance in deteriorating production systems. Inf Sci 278:841–861 Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3:257–271 Zoulfaghari H, Zeinal Hamadani A, Abouei Ardakan M (2014) Biobjective redundancy allocation problem for a system with mixed repairable and non-repairable components. ISA Trans 53:17–24
123