# Improved Approaches to Minimize the Makespan on Single-Machine Scheduling with Periodic Preventive Maintenance Activities

Authors: Hongming Zhou; Ya-Chih Tsai; Ful-Chiang Wu; Shenquan Huang; Fuh-Der Chou
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper addresses a single-machine scheduling problem with periodic preventive maintenance activities that are predeterministic so that the machine is not available all the time, and jobs have to be processed between two consecutive maintenance periods. We propose a mixed integer programming (MIP) model and two heuristics to minimize the makespan. With more constraints in our model, the model is more efficient than the recent model of Perez-Gonzalez and Framinan , and our model could solve problems with up to fifty jobs. Two heuristic algorithms, namely, H (MW) and H (LB∗), are also proposed, in which two bin-packing policies of the minimum waste and minimum lower bound are used, respectively. Furthermore, we also proposed an improvement procedure. The results showed that the heuristic H (MW) outperformed other heuristics of the paper, indicating that the bin-packing policy of the minimum waste is more effective than well-known ones such as full batch and best fit. Additionally, all the heuristic algorithms addressed in this paper combined with the improvement procedure could achieve a similar and high quality of solutions with a very tiny increase in computational expense.


---

## Body

## 1. Introduction

The manufacturing processes constituted by a series of automated machines for processing jobs or dangerous tasks are common practices in many production factories today. Those automated machines are usually expensive, and for this capital-intensive nature of operations, machine malfunction or inappropriate machine idle will cause large costs and losses; thus, many companies provided maintenance policies based on reliability theory to consider unit replacement problems [1–3] or adopted preventive maintenance to reduce the chances of machine malfunction. During the maintenance or unit replacement, machines are not available for processing any jobs, resulting in decreased production time. Additionally, inappropriate production scheduling without considering maintenance requirements will lead to machines waiting for auxiliary resources such as spare parts, tools, and repair staff. Therefore, the importance of cooperation between periodic maintenance and production scheduling has increasingly been received by researchers and decision makers.Preventive maintenance (PM) is one of the factors causing machines to be unavailable for processing jobs, and it can significantly affect the performance of job scheduling. The majority of the studies in the literature assumed that each maintenance activity is either assigned in advance, i.e., its starting and completion times are known, [4–16] or maintenance activities and jobs are jointly scheduled in the planning horizon [12, 17–26]. In the abovementioned studies, they assumed that the maintenance time (maintenance duration) is a constant; however, in some maintenance activities such as cleaning, refilling, and recharging, the maintenance time is a nondecreasing function of its starting time, i.e., the later the maintenance activity begins, the longer its duration. Kubzin and Strusevich [27] were the first pioneers who considered the scheduling problems with variable maintenance duration, and they considered the objective of minimizing the makespan. They showed that the two-machine open shop problem is polynomially solvable, while the 2-machine flowshop problem is NP-hard, for which an efficient algorithm is provided. Since then, various scheduling problems with variable maintenance durations in different machine environments have been considered in the literature [23, 28, 29]. Additionally, more realistic scheduling problems involving deterioration jobs and maintenance activity simultaneously have received considerable attention. Deterioration jobs indicate that the processing times of jobs are not constant, depending on their starting time or position, namely, time-dependent deterioration or position-dependent deterioration effects, respectively. The readers may refer to the survey by Gawiejnowicz [30] and Janiak and Rudek [31] for the problem with deterioration jobs. Regarding this kind of studies, most studies considered the maintenance duration as a constant, including Ji et al. [32], Lee and Wu [33], and Yang et al. [34], whereas Yang [35] further investigated the unrelated parallel-machine problems with deterioration effects and deteriorating multimaintenance activities, in which the maintenance duration is not constant, depending on its running time. The author developed mathematical programming models to find the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences such that the objective of the total completion time is minimized.This paper pursues the stream of research initiated by Ji et al. [9], who were the first pioneers to study a single-machine problem with periodic maintenance activity. For the problem, the planning horizon comprises availability periods (T time unit) followed by a nonavailability periods (t time unit) as shown in Figure 1. More precisely, all jobs are available at time zero, and the processing time of job j is a constant pj for j = 1, 2,…, n. A single machine is also available at time zero; however, the machine should be stopped to perform maintenance activities regularly. The time of each maintenance activity is t, and the availability period of the machine between consecutive maintenance activities is T time unit, which is also referred to as a batch in the literature. To achieve a high utilization rate of the machine, we consider the objective of minimizing the makespan, and the problem is denoted here as 1PM,t,TCmax by the well-known three-field notation (Graham et al. [36]).Figure 1
The composition of the planning horizon for a single-machine problem with periodic preventive maintenance activities.The1PM,t,TCmax problem is strongly NP-hard [4], and this problem is also similar to the classical bin-packing problem; thus, bin-packing policies such as first-fit and best-fit are encountered in some two-phase heuristics for solving this kind of problems with periodic maintenance activities [9, 17, 20, 21, 37, 38]. Those heuristic algorithms sorted the jobs first and were then followed by bin-packing policies to assign the ordered jobs into batches. Perez-Gonzalez and Framinan [16] gave a complete list for the existing two-phase heuristic algorithms in the literature. They also developed a mixed integer programming (MIP) formulation and two-phase heuristic algorithms with local search to find optimal or near-optimal solutions for the problems.Inspired by the similarity between the considered problem and bin-packing problem, we found that a useful constraint on the minimum number of batches (or bins) could make our MIP model more efficient compared with the PM-MILP model of Perez-Gonzalez and Framinan [16]. Additionally, we proposed two heuristic algorithms where two different bin-packing policies are used to guide which jobs are assigned to bins. One of the bin-packing policies is the minimum waste time that is motivated by the property of full batch, i.e., a batch that is filled as full as possible is a benefit for the objective of minimizing makespan [9]. The other is the minimum lower bound. Moreover, the two heuristic algorithms were improved by job-exchange and insertion moves. The computational results showed that the proposed heuristic algorithms are more efficient. The remainder of this paper is organized as follows. In Section 2, we present the MIP model of Perez-Gonzalez and Framinan [16]. In Section 3, our MIP model is addressed, and comparisons between the two models are also given. In Section 4, different lower bounds are discussed. The two proposed heuristic algorithms are introduced in Section 5. Numerical experiments are conducted in Section 6, and conclusions are given in Section 7.


## 2. The Formulation of Perez-Gonzalez and Framinan [16]

The following are the notations and variables of the MIP model addressed by Perez-Gonzalez and Framinan [16]:Notations:n, the number of jobs;pj, the processing time of job j, j = 1, …, n;T, the availability period (size of batches);M, a large integer value (M≥T).Variables:bi bi=1 if batch i is occupied, and otherwise bi=0 and i = 1,…, n;xij xij=1 if job j is assigned to batch i, and otherwise xij=0, i = 1,…, n, and j = 1,…, n.Maxslack is a continuous variable that computes the maximum slack of the batches.δi δi=1 if the maximum slack is given by batch i.Using the above variables, the MIP model of Perez-Gonzalez and Framinan [16] denoted by the PF model later in this paper is described as follows:(1)MinT×∑i=1nbi−maxslack,subject to(2)∑j=1npjxij≤Tbi,∀i=1,…,n,(3)∑i=1nxij=1,∀j=1,…,n,(4)maxslack≤M1−δi+Tbi−∑j=1npjxij,∀i=1,…,n,(5)∑j=1nxij≥bi,∀i=1,…,n,(6)∑i=1nδi=1,(7)δi≤bi,∀i=1,…,n,(8)xij,bi,δi∈0,1,∀i,=1,…,n;j=1,…,n,(9)maxslack≥0.In the PF model, maintenance timet is neglected because the time is constant and does not impact the optimal schedule [9]; for the explanations of constraints (2)–(9), the readers can refer to the study of Perez-Gonzalez and Framinan [16]. In addition, Perez-Gonzalez and Framinan [16] also addressed another model named BP-MILP in their study which adopts the model of Martello et al. [39] for solving the bin-packing problem. The main difference between BP-MILP and PF is that one solution where a batch with the greatest slack value among all optimal solutions obtained by BP-MILP model is an optimal solution for the PF model.


## 3. The Proposed MIP Model

The BP-MILP model of Perez-Gonzalez and Framinan [16] combined the model provided by Martello et al. [39] and the following equation to obtain solutions for the 1nr−pmCmax problem:(10)Cmax=T·∑i=1nbi−1+∑j=1npjxkj,where ∑i=1nbi is the minimum number of batches, and ∑j=1npjxkj indicates the lowest load at batch k. However, the BP-MILP model cannot guarantee obtaining the lowest load at batch k. Thus, Perez-Gonzalez and Framinan [16] provided another model (PF) mentioned above to obtain optimal solution as mentioned above. Through BP-MILP and PF models, it shows again that the bin-packing problem and 1nr−pmCmax problem are very similar and the solution of bin-packing problem can be used to obtain better solutions for the 1nr−pmCmax problem. For bin-packing problems, the minimum number of batches is an important factor influencing the schedule results, and it could serve as a constraint or a decision variable. However, constraints on the minimum number of batches are not involved in the PF model of Perez-Gonzalez and Framinan [16]. Thus, we used the formula ∑j=1npj/T to estimate the minimum number of batches, where x indicates the smallest integer larger than or equal to x and added the constraint of i·xij≤N in our model to make sure that the number of batches is minimum.In our model, the notations and variables are almost the same as the PF model of Perez-Gonzalez and Framinan [16], other than the following:Notation:t, the maintenance timeVariables:N, the number of batches; ∑j=1npj/T≤N≤n.(11)MinT+t·N−1+T−maxslack,subject to(12)∑i=1nxij=1,∀j=1,…,n,(13)∑j=1npjxij≤T,∀i=1,…,n,(14)i·xij≤N,∀i=1,…,n;j=1,…,n,(15)maxslack≥T−∑j=1npj·xij,∀i=1,…,N,(16)xij∈0,1,∀i=1,…,n;j=1,…,n,(17)N,maxslack are area positive integers.Objective (11) is to minimize the makespan, which is inspired by the bin-packing problem addressed in the studies of Ji et al. [9] and Perez-Gonzalez and Framinan [13]. That is, the optimal solution is in the form of having a minimum number of batches plus the lowest load. Constraints (12) and (13) are the same as constraints (3) and (2). Constraint (14) enforces that jobs be assigned in the preceding available batches, which minimizes the number of batches. Constraint (15) is used to find the maximum slack time.The variables used in our model are the same as those of the PF model, but maintenance timet is involved in our objective function; thus, the objective of the PF model is changed to MinT+t×∑i=1nbi−1+T−maxslack in this paper for fair comparison later, even though the value of t does not influence the results.Table1 shows the differences in the number of constraints and the number of variables between the abovementioned two models. Table 1 reveals that the number of binary variables in our model is less than that in the PF model; more obviously, our model has many more constraints than the PF model, which could theoretically cut down the solution search space so that our model is much more efficient for finding optimal solutions, which has been proven by our computational results. However, too many binary variables remain in the two models to be solved even for modest problem sizes; for example, when n is equal to 100, there are 10200 and 10000 binary variables for the PF model and our model, respectively, to be solved. More specifically, such mathematical programming approaches, including the two models addressed in this paper, suffer from the inherent drawback, i.e., it is tough to solve problems of large sizes in a reasonable CPU time for NP-hard problems.Table 1
Analysis between PF and our models.
Analysis items
PF model
Our model
The number of constraints
5
n
+
2
n
2
+
3
n
+
1
The number of integer variables
1
2
Binary variables
n
2
+
2
n
n
2Table 2
The detailed steps of the Max_W method.
v
N
A
N
B
W
v
1
1
0
max
0
,
1
×
10
−
9
+
0 = 1
2
2
2
max
0
,
2
×
10
−
17
+
4
=
0
3
2
2
max
0
,
2
×
10
−
17
+
4
=
0
4
2
3
max
0
,
2
×
10
−
17
+
8
=
0
5
3
4
max
0
,
3
×
10
−
22
+
13
=
0


## 4. The Calculation of Lower Bound

For an NP-hard scheduling problem, lower bounds used to measure the performance of heuristic algorithms are commonly encountered in the literature because optimal solutions are hard to obtain. Additionally, the lower bound plays a key role in developing implicit enumeration methods such as branch-and-bound algorithms or serves as an index in developing heuristic algorithms. Therefore, the precise estimation of lower bounds is an important issue.For a1nr−pmCmax problem, Low et al. [20] used a lower bound to evaluate the performance of heuristic algorithms. The lower bound is denoted as LBLow here and estimated by(18)LBLow=∑j=1npj+∑j=1npjT−1·t,where x indicates the smallest integer larger than or equal to x. The first term is the total processing time, and the second term is the minimum total maintenance time. In another study, Low et al. [21] also used lower bound as a performance index for single-machine scheduling problems with flexible and periodic maintenance where the maintenance activity should be implemented during the prespecific intervals. Their lower bound (LBLow′) is estimated as follows:(19)LBLow′=max∑j=1npj+n/k−1·t,∑j=1npj+∑j=1npjT−1·t,where k is the maximum number of jobs processed in the machine’s available interval. From formulas (18) and (19), it is evident that formula (19) dominates formula (18), and the estimation for the minimum number of batches, i.e., x, is an important factor for the quality of lower bound as usually recognized by many researchers in numerous works. In addition, we briefed three observations from numerous studies in the literature as follows:Property 1.
With respect to schedule makespan as a measure of performance, it is necessary to consider the schedules in which the number of batches is minimum [9].Property 2.
For the makespan objective, switching jobs within a batch does not influence the makespan.Property 3.
Among the schedules with minimum number of batches, it is necessary to consider the optimal schedules in which the last batch has the minimum load, i.e., the total processing time of jobs in the last batch is minimized [16].
Based on the abovementioned findings, we introduced three estimations for the minimum number of batches (Bmin): (1) Bmin1=∑j=1npj/T, which is the same as that of LBLow [20]; (2) Bmin2=∑j=1npj+Wmax/T, where Wmax is the maximum waste and will be explained in the following; and (3) Bmin3 is obtained by the integer programming model for bin-packing problems provided by Martello et al. [39].
To obtain the value ofWmax and Bmin2, we developed a maximum waste (Max_W) method. The Max_W method first assumes that v is in the range of [1, T/2], i.e., 1≤v≤T/2, and let NA and NB be the number of jobs in the sets A and B, respectively.
Max_W method:Step 1: Letv = 1, Wmax=0.Step 2: Place the jobs in set A if the processing time of jobj is greater than or equal to T−v, i.e., pj≥T−v.Step 3: Place the jobs in set B if the processing time of jobj is less than or equal to v, i.e., pj≤v.Step 4: Calculate the waste value ofWv by the formula of Wv=max0,NA×T−∑j∈Apj+∑j∈Bpj, if Wv>Wmax, Wmax=Wv.Step 5: Ifv<T/2, v = v + 1, go to Step 2; otherwise, go to Step 6.Step 6: IfBmin2=∑j=1npj+Wmax/T, stop.
The Max_W method is aimed at creating full batches as possible to avoid undesirable capacity waste of batches while there exist jobs to form a full batch to accommodate. Regarding the estimation of the lower bound, we modified formula (19) based on the properties as follows:(20)LB∗=maxT+t·Bmin−1+min_P,∑j=1npj+Bmin−1·t,where Bmin is the estimated number of batches. Consider an example with 6 jobs, where T = 10, t = 3, p1=9, p2=8, p3=p4=2, p5=5, and p6=4. Using the formula of Bmin1=∑j=1npj/T, Bmin1=30/10=3. For Bmin2, we first used the Max_W method to obtain Wmax, the steps are illustrated in detail in Table 2, and Wmax=maxWv=1. Finally, Bmin2=30+1/10=4 based on the formula Bmin2=∑j=1npj+Wmax/T. Regarding Bmin3, the result is 4, obtained by the integer programming model of Martello et al. [39].
Based on the obtainedBmin, the lower bound of LB∗Bmin1 = max10+3·3−1+2,30+3−1·3 = max28,36 = 36, and LB∗Bmin2 = LB∗Bmin3=max10+3·4−1+2,30+4−1·3 = max41,39 = 41, which is also equal to the optimal solution.
BecauseBmin1 is dominated by Bmin2 and the Max_W method is much more efficient than the integer programming model of Martello et al. [39], we adopted Bmin2 to obtain the estimated number of batches in this paper.


## 5. The Proposed Heuristic Algorithms

According to the research work by Ji et al. [9], the machine’s availability period can be treated as a bin with capacity T, and then inspired by bin-packing problems, many researchers developed different heuristic algorithms with two phases. First, the jobs are sorted by a certain dispatching rule, and the bin-packing policy is then adopted to fill the bin as much as possible, based on the study of Ji et al. [9]. Perez-Gonzalez and Framinan [16] provided a survey for this kind of two-phase heuristic algorithms in the literature; additionally, they also developed a two-phase heuristic algorithm with a local search technique to solve the problem.Based on the studies of Perez-Gonzalez and Framinan [16] and Ji et al. [9], the LPT rule for generating job sequences is better than other dispatching rules in the first phase; thus, in this paper, the jobs first were sorted in nonincreasing order of their processing time, i.e., p1≥p2≥⋯≥pn, and then we developed two bin-packing policies of the minimum waste and the minimum lower bound that are different from the well-known ones such as full batch and best fit that are prevalently encountered in the literature for solving the scheduling problem with machine maintenance. Moreover, these proposed heuristic algorithms were improved by an improvement procedure.Note that the initial job-sequence (JS) is given by the LPT rule, i.e.,p1≥p2≥⋯≥pn, and bin-packing policies including full batch, best fit, the minimum waste, and the minimum lower bound are described as follows:


### 5.1. Full Batch (FB)

Select the job in order from the given JS and place it in the first batch in which there is enough slack time to accommodate it, i.e.,pj≤skslack time. Otherwise, create a new batch, and place the job in it.


### 5.2. Best Fit (BF)

Step 1: LetUJS=J1,J2,…,Jn, i = 1, Bi=B1=∅, sk = T.
Step 2: Select all unscheduled jobs ifpj≤sk, j∈UJS, and put the jobs in set CJS.
Step 3: IfCJS=∅, i=i+1, create a new batch, i.e., Bi=∅, sk = T, and go to Step 2. Otherwise, select the job Ja in order from set CJS if pa≤sk.
Step 4:Bi=Bi∪Jα, sk=sk−pa, delete the job a from set UJS, i.e., UJS=UJS\Ja.
Step 5: IfUJS=∅, calculate makespan using Cmax=T+t·i−1+∑j∈Bipj, and stop. Otherwise, let CJS=∅ and go to Step 2.


### 5.3. Minimum Waste (MW)

Step 1: Leti = 1, Bi=B1=∅, sk = T.
Step 2: IfUJS≠∅, select all unscheduled jobs if pj≤sk, and put the jobs in order in set CJS. Otherwise, go to Step 11.
Step 3: IfCJS=∅, i=i+1,create a new batch, i.e., Bi=∅, sk = T; go to Step 2.
Step 4: If the sum of the processing time of all jobs in set CJS is less than or equal tosk, i.e., ∑j∈CJSpj≤sk, place all the jobs of set CJS into the batch, i.e., Bi=Bi∪​CJS, sk=sk−∑j∈CJSpj, and UJS=UJS\CJS; go to Step 2.
Step 5: If∑j∈CJSpj>sk, select job Ja in the top of set CJS. Let SS1=Ja, and Waste1=sk−pa.
Step 6: IfWaste1=0, place Ja in Bi. Bi=Bi∪Ja, i = i + 1, Bi=∅, sk = T, and delete the Ja from set UJS; go to Step 2.
Step 7: IfWaste1>0, select any pair of jobs, Jb,Jc; Jb,Jc∈CJS such that minsk−Jb−Jc≥0, and let Waste2=minsk−pb−pc, SS2=Jb,Jc, and go to Step 8. If none exists, place Ja in Bi. Bi=Bi∪Ja, i = i + 1, Bi=∅, sk = T, UJS=UJS\Ja, and go to Step 2.
Step 8: IfWaste2=0, place the jobs of the SS2 in the Bi. Bi=Bi∪SS2=Bi∪Jb,Jc, i = i + 1, Bi=∅, sk = T, UJS=UJS\SS2, and go to Step 2.
Step 9: IfWaste2>0, select any three jobs, Jx,Jy,Jz; Jx,Jy,Jz∈CJS such that minsk−px−py−pz≥0. Let Waste3=minsk−px−py−pz and SS3=Jx,Jy,Jz, and go to Step 10. If none exists, Waste3=T and SS3=∅.
Step 10: Select the minimum waste fromWaste1, Waste2, and Waste3.Case 1: If the minimum waste is equal toWaste1, Bi=Bi∪Ja, sk=sk−pa, UJS=UJS\Ja, and go to Step 2.Case 2: If the minimum waste is equal toWaste2, Bi=Bi∪SS2, sk=sk−pb−pc, UJS=UJS\Jb,Jc, and go to Step 2.Case 3: If the minimum waste is equal toWaste3, Bi=Bi∪SS3, sk=sk−px−py−pz, UJS=UJS\Jx,Jy,Jz, and go to Step 2.
Step 11: Calculate makespan usingCmax=T+t·i−1+∑j∈Bipj, and stop.


### 5.4. Minimum Lower Bound (LB∗)

Select the job with minimum lower bound (LB∗) from the given JS and place it in the first batch in which there is enough slack time to accommodate it, i.e., pj≤slack time. Otherwise, create a new batch, and place the job in it.To illustrate these packing policies, an 8-job instance is given in Table3 where T and t are equal to 10 and 3, respectively. First, the jobs are sorted in nondecreasing order of their processing times, i.e., J3,J6,J7,J8,J1,J2,J4,J5 and then applying four different packing policies to assign jobs into batches, the results are obtained as shown in Table 4. In Table 4, H (∗∗) indicates that the heuristic algorithm adopts different bin-packing policies; for example, H (FB) means that the full-batch packing policy is used. Additionally, the MLPT heuristic, borrowed from the MFFD algorithm for the bin-packing problem [40], is proposed by Yu et al. [41] to solve the problem with periodic preventive maintenance activities.Table 3
An instance with eight jobs.
J
1
J
2
J
3
J
4
J
5
J
6
J
7
J
8
p
j
6
4
8
2
1
8
8
8Table 4
Comparisons of different heuristic algorithms.
Schedule
C
max
H (FB)
J
3
,
J
6
,
J
7
,
J
8
,
J
1
,
J
2
,
J
4
,
J
5
68
H (BF)
J
3
,
J
4
,
J
6
,
J
5
J
7
,
J
8
,
J
1
,
J
2
62
H (MW)
J
3
,
J
4
,
J
1
,
J
2
,
J
6
,
J
5
J
7
,
J
8
60
H (LB∗)
J
3
,
J
4
,
J
6
,
J
5
J
7
,
J
1
,
J
2
,
J
8
60
MLPT
J
1
,
J
2
,
J
3
,
J
4
,
J
6
,
J
5
J
7
,
J
8
60Many recent studies [42, 43] have mentioned the benefits of interchange or insertion moves for the scheduling problems with makespan criterion, especially applying for generating neighborhood solutions [44]. We also propose two insertions and two interchanges for the considered problems in this paper. That is, once the initial schedule is obtained by one of the abovementioned bin-packing policies, the solution is further improved by the proposed local search technique including interchange and insertion moves. Our insertion method includes two insertion-type moves: job-type insertion and batch-type insertion.


### 5.5. Job-Type Insertion

With respect to Property1, it implies that a schedule in which it is possible to find a batch Bk and a job j if job j satisfies the condition of pj≤T−∑i∈Bkpi, j∈Bl, Bk is scheduled before Bl, and the operation of inserting job j into Bk would not lead to an increase in the makespan, as shown in Figure 2.Figure 2
Job-type insertion.Job-type insertion attempts to insert a jobj into the front batches based on Property 1 are mentioned. The complete steps are described as follows:Step 1: Letπ be the initial schedule. Let k = 1, and K is equal to the number of batches.Step 2: Ifk<K, l = k + 1; otherwise, go to Step 5.Step 3: Ifl≤K; otherwise, go to Step 4.Step 3.1: If none of the jobs in the batchBl satisfies the condition of pj≤skk, j∈Bl, (skk=T−∑i∈Bkpi), l = l + 1, and go to Step 3.Step 3.2: Remove jobj from batch Bl and insert the job into batch Bk if the condition of pj≤skk, j∈Bl is satisfied; π′ is a new schedule after insertion, and recalculate the value of K based on π′. π=π′ and go to Step 1.Step 4:k = k + 1, and go to Step 2.Step 5: Calculate makespan usingCmax=T+t·K−1+∑j∈BKpj


### 5.6. Batch-Type Insertion

FormulaCmax=T+t·K−1+∑j∈BKpj implies that the nonfull batch with the lowest load should be the last batch in the schedule; thus, the solution can be improved by moving the nonfull batch with the lowest load into the last position in the schedule, as shown in Figure 3.Figure 3
Batch-type insertion.Batch-type insertion attempts to move the batch with minimum load into the last position in the sequence based on Property2. The complete steps are described as follows:Step 1: Letπ be the initial sequence after implementing Job-type insertion and Job interchange, and the solution is equal to Cmax. Let k = 1, and K is equal to the number of batches.Step 2: Fork = 1 to K, find the batch with minimum load and move the batch into the last position. Form a new schedule π′ without any unnecessary machine idle periods.Step 3: Calculate makespan usingCmax=T+t·K−1+∑j∈BKpj for the schedule π′.Because each batch is as full as possible except for the last batch, the job-type insertion is aimed at doing that. Additionally, we could also apply the interchange of jobs without increasing the makespan for the same purpose. Here are two cases.Figure 4
Interchange jobsi and j (interone type).Property 4.
Ifpj≤pi+skk and pj>pi; i∈Bk, j∈Bl, k<l, and then the interchange of i and j will not lead to an increase in Cmax, as shown in Figure 4.Property 5.
Ifpj′+pj″≤pi+skk and pj′+pj″>pi; i∈Bk, j'′,j'′∈Bl, k<l, then the interchange of j′,j'′ and i will not lead to an increase in Cmax, as shown in Figure 5.
The abovementioned two interchanges, namely, interone and intertwo, aim to make the former batches as full as possible, and the complete steps for the two interchanges are described as follows:Figure 5
Interchange jobsj′, j″ and i (intertwo type).


### 5.7. Interone Type

Step 1: Letπ be the initial sequence. Let k = 1, and K is equal to the number of batches.
Step 2: Ifk<K, l = k + 1; otherwise, go to Step 5.
Step 3: Ifl≤K; otherwise, go to Step 4.Step 3.1: If none of the jobs in batchBl satisfies the conditions pj≤pi+skk and pj>pi, l = l + 1, go to Step 3.Step 3.2: Interchange the jobsi, j if the conditions of pj≤pi+skk and pj>pi are satisfied, π′ is a new schedule after interchange, π=π′, and l = l + 1, go to Step 1.
Step 4:k = k + 1; go to Step 2.
Step 5: Calculate makespan usingCmax=T+t·K−1+∑j∈BKpj


### 5.8. Intertwo Type

Step 1: Letπ be the initial schedule. Let k = 1 and K is equal to the number of batches.
Step 2: Ifk<K, l = k + 1; otherwise, go to Step 5.
Step 3: Ifl≤K; otherwise, go to Step 4.Step 3.1: If none of the jobs in batchBl satisfies the conditions pj′+pj″≤pi+skk and pj′+pj″>pi, l = l + 1; go to Step 3.Step 3.2: Interchange the two jobsj′,j″ with job i if the conditions of pj′+pj″≤pi+skk and pj′+pj″>pi are satisfied; π′ is a new schedule after interchange, π=π′, l = l + 1, and go to Step 1.
Step 4:k = k + 1; go to Step 2.
Step 5: Calculate makespan usingCmax=T+t·K−1+∑j∈BKpjOur proposed heuristic algorithms with the improvement procedure are outlined as follows:Step 1: Obtain an initial schedule by one of the bin-packing policies.Step 2: Improvement procedure:Step 2.1: Implement job-type insertion to obtain an improved schedule based on the sequence of Phase 1.Step 2.2: Implement interone interchange to obtain an improved schedule based on the sequence of Step 2.1.Step 2.3: Implement intertwo interchange to obtain an improved schedule based on the sequence of Step 2.2.Step 2.4: Implement batch-type insertion to obtain a final schedule based on the sequence of Step 2.3.Step 3: CalculateCmax and stop.


## 5.1. Full Batch (FB)

Select the job in order from the given JS and place it in the first batch in which there is enough slack time to accommodate it, i.e.,pj≤skslack time. Otherwise, create a new batch, and place the job in it.


## 5.2. Best Fit (BF)

Step 1: LetUJS=J1,J2,…,Jn, i = 1, Bi=B1=∅, sk = T.
Step 2: Select all unscheduled jobs ifpj≤sk, j∈UJS, and put the jobs in set CJS.
Step 3: IfCJS=∅, i=i+1, create a new batch, i.e., Bi=∅, sk = T, and go to Step 2. Otherwise, select the job Ja in order from set CJS if pa≤sk.
Step 4:Bi=Bi∪Jα, sk=sk−pa, delete the job a from set UJS, i.e., UJS=UJS\Ja.
Step 5: IfUJS=∅, calculate makespan using Cmax=T+t·i−1+∑j∈Bipj, and stop. Otherwise, let CJS=∅ and go to Step 2.


## 5.3. Minimum Waste (MW)

Step 1: Leti = 1, Bi=B1=∅, sk = T.
Step 2: IfUJS≠∅, select all unscheduled jobs if pj≤sk, and put the jobs in order in set CJS. Otherwise, go to Step 11.
Step 3: IfCJS=∅, i=i+1,create a new batch, i.e., Bi=∅, sk = T; go to Step 2.
Step 4: If the sum of the processing time of all jobs in set CJS is less than or equal tosk, i.e., ∑j∈CJSpj≤sk, place all the jobs of set CJS into the batch, i.e., Bi=Bi∪​CJS, sk=sk−∑j∈CJSpj, and UJS=UJS\CJS; go to Step 2.
Step 5: If∑j∈CJSpj>sk, select job Ja in the top of set CJS. Let SS1=Ja, and Waste1=sk−pa.
Step 6: IfWaste1=0, place Ja in Bi. Bi=Bi∪Ja, i = i + 1, Bi=∅, sk = T, and delete the Ja from set UJS; go to Step 2.
Step 7: IfWaste1>0, select any pair of jobs, Jb,Jc; Jb,Jc∈CJS such that minsk−Jb−Jc≥0, and let Waste2=minsk−pb−pc, SS2=Jb,Jc, and go to Step 8. If none exists, place Ja in Bi. Bi=Bi∪Ja, i = i + 1, Bi=∅, sk = T, UJS=UJS\Ja, and go to Step 2.
Step 8: IfWaste2=0, place the jobs of the SS2 in the Bi. Bi=Bi∪SS2=Bi∪Jb,Jc, i = i + 1, Bi=∅, sk = T, UJS=UJS\SS2, and go to Step 2.
Step 9: IfWaste2>0, select any three jobs, Jx,Jy,Jz; Jx,Jy,Jz∈CJS such that minsk−px−py−pz≥0. Let Waste3=minsk−px−py−pz and SS3=Jx,Jy,Jz, and go to Step 10. If none exists, Waste3=T and SS3=∅.
Step 10: Select the minimum waste fromWaste1, Waste2, and Waste3.Case 1: If the minimum waste is equal toWaste1, Bi=Bi∪Ja, sk=sk−pa, UJS=UJS\Ja, and go to Step 2.Case 2: If the minimum waste is equal toWaste2, Bi=Bi∪SS2, sk=sk−pb−pc, UJS=UJS\Jb,Jc, and go to Step 2.Case 3: If the minimum waste is equal toWaste3, Bi=Bi∪SS3, sk=sk−px−py−pz, UJS=UJS\Jx,Jy,Jz, and go to Step 2.
Step 11: Calculate makespan usingCmax=T+t·i−1+∑j∈Bipj, and stop.


## 5.4. Minimum Lower Bound (LB∗)

Select the job with minimum lower bound (LB∗) from the given JS and place it in the first batch in which there is enough slack time to accommodate it, i.e., pj≤slack time. Otherwise, create a new batch, and place the job in it.To illustrate these packing policies, an 8-job instance is given in Table3 where T and t are equal to 10 and 3, respectively. First, the jobs are sorted in nondecreasing order of their processing times, i.e., J3,J6,J7,J8,J1,J2,J4,J5 and then applying four different packing policies to assign jobs into batches, the results are obtained as shown in Table 4. In Table 4, H (∗∗) indicates that the heuristic algorithm adopts different bin-packing policies; for example, H (FB) means that the full-batch packing policy is used. Additionally, the MLPT heuristic, borrowed from the MFFD algorithm for the bin-packing problem [40], is proposed by Yu et al. [41] to solve the problem with periodic preventive maintenance activities.Table 3
An instance with eight jobs.
J
1
J
2
J
3
J
4
J
5
J
6
J
7
J
8
p
j
6
4
8
2
1
8
8
8Table 4
Comparisons of different heuristic algorithms.
Schedule
C
max
H (FB)
J
3
,
J
6
,
J
7
,
J
8
,
J
1
,
J
2
,
J
4
,
J
5
68
H (BF)
J
3
,
J
4
,
J
6
,
J
5
J
7
,
J
8
,
J
1
,
J
2
62
H (MW)
J
3
,
J
4
,
J
1
,
J
2
,
J
6
,
J
5
J
7
,
J
8
60
H (LB∗)
J
3
,
J
4
,
J
6
,
J
5
J
7
,
J
1
,
J
2
,
J
8
60
MLPT
J
1
,
J
2
,
J
3
,
J
4
,
J
6
,
J
5
J
7
,
J
8
60Many recent studies [42, 43] have mentioned the benefits of interchange or insertion moves for the scheduling problems with makespan criterion, especially applying for generating neighborhood solutions [44]. We also propose two insertions and two interchanges for the considered problems in this paper. That is, once the initial schedule is obtained by one of the abovementioned bin-packing policies, the solution is further improved by the proposed local search technique including interchange and insertion moves. Our insertion method includes two insertion-type moves: job-type insertion and batch-type insertion.


## 5.5. Job-Type Insertion

With respect to Property1, it implies that a schedule in which it is possible to find a batch Bk and a job j if job j satisfies the condition of pj≤T−∑i∈Bkpi, j∈Bl, Bk is scheduled before Bl, and the operation of inserting job j into Bk would not lead to an increase in the makespan, as shown in Figure 2.Figure 2
Job-type insertion.Job-type insertion attempts to insert a jobj into the front batches based on Property 1 are mentioned. The complete steps are described as follows:Step 1: Letπ be the initial schedule. Let k = 1, and K is equal to the number of batches.Step 2: Ifk<K, l = k + 1; otherwise, go to Step 5.Step 3: Ifl≤K; otherwise, go to Step 4.Step 3.1: If none of the jobs in the batchBl satisfies the condition of pj≤skk, j∈Bl, (skk=T−∑i∈Bkpi), l = l + 1, and go to Step 3.Step 3.2: Remove jobj from batch Bl and insert the job into batch Bk if the condition of pj≤skk, j∈Bl is satisfied; π′ is a new schedule after insertion, and recalculate the value of K based on π′. π=π′ and go to Step 1.Step 4:k = k + 1, and go to Step 2.Step 5: Calculate makespan usingCmax=T+t·K−1+∑j∈BKpj


## 5.6. Batch-Type Insertion

FormulaCmax=T+t·K−1+∑j∈BKpj implies that the nonfull batch with the lowest load should be the last batch in the schedule; thus, the solution can be improved by moving the nonfull batch with the lowest load into the last position in the schedule, as shown in Figure 3.Figure 3
Batch-type insertion.Batch-type insertion attempts to move the batch with minimum load into the last position in the sequence based on Property2. The complete steps are described as follows:Step 1: Letπ be the initial sequence after implementing Job-type insertion and Job interchange, and the solution is equal to Cmax. Let k = 1, and K is equal to the number of batches.Step 2: Fork = 1 to K, find the batch with minimum load and move the batch into the last position. Form a new schedule π′ without any unnecessary machine idle periods.Step 3: Calculate makespan usingCmax=T+t·K−1+∑j∈BKpj for the schedule π′.Because each batch is as full as possible except for the last batch, the job-type insertion is aimed at doing that. Additionally, we could also apply the interchange of jobs without increasing the makespan for the same purpose. Here are two cases.Figure 4
Interchange jobsi and j (interone type).Property 4.
Ifpj≤pi+skk and pj>pi; i∈Bk, j∈Bl, k<l, and then the interchange of i and j will not lead to an increase in Cmax, as shown in Figure 4.Property 5.
Ifpj′+pj″≤pi+skk and pj′+pj″>pi; i∈Bk, j'′,j'′∈Bl, k<l, then the interchange of j′,j'′ and i will not lead to an increase in Cmax, as shown in Figure 5.
The abovementioned two interchanges, namely, interone and intertwo, aim to make the former batches as full as possible, and the complete steps for the two interchanges are described as follows:Figure 5
Interchange jobsj′, j″ and i (intertwo type).


## 5.7. Interone Type

Step 1: Letπ be the initial sequence. Let k = 1, and K is equal to the number of batches.
Step 2: Ifk<K, l = k + 1; otherwise, go to Step 5.
Step 3: Ifl≤K; otherwise, go to Step 4.Step 3.1: If none of the jobs in batchBl satisfies the conditions pj≤pi+skk and pj>pi, l = l + 1, go to Step 3.Step 3.2: Interchange the jobsi, j if the conditions of pj≤pi+skk and pj>pi are satisfied, π′ is a new schedule after interchange, π=π′, and l = l + 1, go to Step 1.
Step 4:k = k + 1; go to Step 2.
Step 5: Calculate makespan usingCmax=T+t·K−1+∑j∈BKpj


## 5.8. Intertwo Type

Step 1: Letπ be the initial schedule. Let k = 1 and K is equal to the number of batches.
Step 2: Ifk<K, l = k + 1; otherwise, go to Step 5.
Step 3: Ifl≤K; otherwise, go to Step 4.Step 3.1: If none of the jobs in batchBl satisfies the conditions pj′+pj″≤pi+skk and pj′+pj″>pi, l = l + 1; go to Step 3.Step 3.2: Interchange the two jobsj′,j″ with job i if the conditions of pj′+pj″≤pi+skk and pj′+pj″>pi are satisfied; π′ is a new schedule after interchange, π=π′, l = l + 1, and go to Step 1.
Step 4:k = k + 1; go to Step 2.
Step 5: Calculate makespan usingCmax=T+t·K−1+∑j∈BKpjOur proposed heuristic algorithms with the improvement procedure are outlined as follows:Step 1: Obtain an initial schedule by one of the bin-packing policies.Step 2: Improvement procedure:Step 2.1: Implement job-type insertion to obtain an improved schedule based on the sequence of Phase 1.Step 2.2: Implement interone interchange to obtain an improved schedule based on the sequence of Step 2.1.Step 2.3: Implement intertwo interchange to obtain an improved schedule based on the sequence of Step 2.2.Step 2.4: Implement batch-type insertion to obtain a final schedule based on the sequence of Step 2.3.Step 3: CalculateCmax and stop.


## 6. Computational Experiments

In this section, two experiments are conducted on a PC Xeon E5-1620 CPU operating at 3.6 GHz with 12 GB of RAM. Experiment 1 is aimed at comparing the computational efficiencies of the two MIP models. Experiment 2 focuses on comparing our proposed algorithms with other heuristic algorithms in the literature; we generated a set of problems randomly in which the setting is the same as that employed by Perez-Gonzalez and Framinan [16]. That is, the processing times are generated from a discrete uniform distribution between 1 and 50, the availability period of T is from a discrete uniform distribution between 50 and 100, and the three different values of maintenance time t are 10, 25, and 50. For each experimental condition, thirty instances are generated randomly. Therefore, our test-bed consists of 1260 problems considering n∈10,20,30,40,50,60,70,80,90,100,150,200,250,300.


### 6.1. Experiment 1: Comparison of the Two MIP Models

In this section, we compare our MIP model with the PF model of Perez-Gonzalez and Framinan [16]; the two models are implemented in IBM ILOG CPLEX Optimization Studio Version 12.7.1. We set a limit of 7200 seconds as the stopping criterion for the two models to solve each instance and then reported the number of optimal solutions obtained by the two models within the time limit and the average computation time for each problem size. Table 5 shows the numbers of optimal solutions obtained and average computation times spent by the two models for each problem; overall, the total numbers of optimal solutions obtained by PF and our models are 857 and 1165, respectively. Furthermore, our model is much more efficient than the PF model; this supports our anticipation, that is, more constraints in our model are advantageous for reducing solution space, resulting in a greater efficiency of our model.Table 5
The comparison results for the PF and our models.
n
Number of optimal solutions obtained
Average CPU time (seconds)
PF model
Our model
PF model
Our model
10
90
90
0.180
0.090
20
90
90
0.349
0.182
30
90
90
21.911
1.328
40
88
90
181.034
7.533
50
81
90
1001.149
11.741
60
72
88
1599.318
242.726
70
66
87
2054.072
313.883
80
54
83
3085.476
627.217
90
46
84
3870.221
607.719
100
36
81
4445.117
897.274
150
24
55
5404.562
3161.652
200
13
58
6290.459
2936.797
250
9
43
6621.720
4175.544
300
8
46
6665.626
4535.073
857
1165
—
—In Table5, our model can give optimal solutions in all instances up to the 50-job problem; however, as the number of jobs increases, the performance of our model gradually worsens, although, fortunately, not like the rapid deterioration of the PF model.


### 6.2. Experiment 2: Comparison of the Heuristic Algorithms

In this section, our proposed heuristic algorithms, namely, H (MW) and H (LB∗), are compared with the well-known heuristic algorithms in the literature, including H (BF), H (FB), and MLPT. All the heuristic algorithms are coded in C++. To compare the algorithms, relative percentage deviation (RPD) is used as a performance measure for each instance. RPD is calculated as follows:(21)RPD=Algsol−MINMIN×100%,where Algsol is the makespan obtained by a given algorithm for an instance, and MIN is the optimal or lower bound value obtained for a given instance.Table6 provides results of different heuristic algorithms for small problems. All optimal solutions could be obtained by our model. The columns of ARPD (%) give average RPD values from the optimal solutions over 90 instances. We can find that the heuristic H (MW) is the best heuristic among the five heuristics if the improvement procedure is not involved, as shown in Table 6. The mean ARPD value of H (MW) is 0.154%, and the heuristic H (MW) on average finds 71.5% of the optimal solutions in the experiments. The results for the heuristic algorithms with improvement procedure are shown in Table 7. It is obvious that using the improvement procedure leads to all the heuristics achieving similar better performances, and the average percentages of optimal solutions found by HI (BF), HI (FB), MLPTI, HI (MW), and HI (LB∗) are 96.9%, 96.5%, 96.95%, 99.1%, and 98.5%, respectively. According to Tables 7 and 8, the solutions of all the heuristics with the improvement procedure are refined evidently without large increase in expenses. Hence, the improvement procedure presented in this paper is a significant addition to the literature.Table 6
The comparative results for different heuristic algorithms.
n
ARPD (%)
Percentage of optimal solutions found (%)
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
8
0.418
18.558
0.418
0.017
0.065
85.6
0.0
85.6
98.9
95.6
10
2.149
17.907
2.149
0.069
1.208
36.7
1.1
36.7
93.3
48.9
20
1.060
24.969
1.060
0.218
1.074
23.3
0.0
23.3
85.6
24.4
30
0.831
26.504
0.831
0.460
0.734
21.1
0.0
21.1
28.9
25.6
40
0.764
27.524
0.764
0.064
0.473
22.2
0.0
22.2
75.6
22.2
50
0.522
27.898
0.522
0.095
0.335
13.3
0.0
13.3
46.7
40.0
Ave.
0.957
23.893
0.957
0.154
0.648
33.7
0.2
33.7
71.5
.42.8Table 7
The comparative results for different heuristic algorithms with improvement procedure.
n
ARPD (%)
Percentage of optimal solutions found (%)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
8
0.000
0.000
0.000
0.000
0.000
100
100
100
100
100
10
0.000
0.000
0.000
0.000
0.000
100
100
100
100
100
20
0.002
0.004
0.002
0.000
0.002
98.9
97.8
98.9
100
98.9
30
0.004
0.010
0.002
0.000
0.000
96.7
0.92.2
97.8
100
100
40
0.005
0.005
0.006
0.002
0.002
93.3
0.94.4
92.2
97.8
97.8
50
0.007
0.005
0.010
0.004
0.005
92.2
0.94.4
92.2
96.7
94.4
Ave.
0.003
0.004
0.003
0.001
0.002
96.9
96.5
96.9
99.1
98.5Table 8
The average computational times for different heuristic algorithms.
n
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
8
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
10
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
20
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
30
0.000
0.000
0.000
0.000
0.000
0.000
0.001
0.000
0.000
0.000
40
0.000
0.000
0.000
0.000
0.000
0.000
0.001
0.000
0.000
0.000
50
0.000
0.000
0.000
0.001
0.000
0.000
0.003
0.001
0.001
0.000Regarding large problems, the solutions obtained by all the heuristics are compared with lower bounds; when the solution obtained by the heuristics is equal to the lower bound, the number of optimal solutions increases by 1, and we could then obtain the percentage of optimal solutions found by each heuristic. As revealed in Table9, the performances of average ARPD value and average percentage of optimal solution found for each heuristic worsen; however, heuristic H (MW) is still the best among them, and furthermore, the results of Table 10 verified again that the improvement procedure indeed significantly induces the quality of the final solutions; it could lead heuristics to obtain better solutions, and adding the improvement procedure into each heuristic does not increase the computational burden a lot, as shown in Table 11. From the general analysis results, the heuristics with improvement procedure can obtain very good solutions very fast, which indicates that the heuristics with improvement procedure can be applied to real-world problem.Table 9
The comparative results for different heuristic algorithms.
n
ARPD (%)
Percentage of optimal solutions found (%)
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
60
0.502
8.901
0.502
0.043
0.257
10.0
0.0
10.0
65.6
23.3
70
0.750
30.030
0.750
0.279
0.438
5.6
0.0
5.6
46.7
26.7
80
0.611
31.142
0.611
0.337
0.462
3.3
0.0
3.3
34.4
17.8
90
0.512
30.545
0.512
0.324
0.358
2.2
0.0
2.2
21.1
11.1
100
0.450
30.994
0.450
0.300
0.324
7.8
0.0
7.8
22.2
23.3
150
0.374
31.294
0.374
0.290
0.300
8.9
0.0
8.9
34.4
32.2
200
0.303
32.360
0.303
0.205
0.228
13.3
0.0
13.3
65.6
32.2
250
0.319
31.324
0.319
0.265
0.278
12.2
0.0
12.2
61.1
45.6
300
0.197
31.147
0.197
0.161
0.184
17.8
0.0
17.8
52.2
55.6
Ave.
0.446
28.637
0.446
0.247
0.314
9.0
0.0
9.0
44.8
29.8Table 10
The comparative results of different heuristic algorithms with improvement procedure for large problems.
n
ARPD (%)
Percentage of optimal solutions found (%)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
60
0.004
0.003
0.006
0.002
0.001
93.3
94.4
91.1
96.7
96.7
70
0.231
0.229
0.230
0.228
0.228
73.3
75.6
72.2
77.8
77.8
80
0.276
0.264
0.278
0.261
0.263
68.9
67.8
64.4
70.0
68.9
90
0.212
0.212
0.213
0.210
0.210
64.4
64.4
64.4
66.7
66.7
100
0.193
0.193
0.192
0.189
0.189
63.3
64.4
66.7
68.9
67.8
150
0.198
0.205
0.213
0.193
0.196
64.4
64.4
65.6
66.7
66.7
200
0.207
0.206
0.208
0.175
0.183
62.2
63.3
63.3
74.4
72.2
250
0.265
0.270
0.266
0.245
0.245
65.6
62.2
64.4
78.9
76.7
300
0.161
0.209
0.161
0.140
0.142
52.2
45.6
50.0
80.0
80.0
Ave.
0.194
0.199
0.196
0.183
0.184
67.5
66.9
66.9
75.6
74.8Table 11
The average computational times of different heuristic algorithms for large problems.
n
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
60
0.000
0.000
0.000
0.001
0.000
0.000
0.005
0.001
0.001
0.000
70
0.000
0.000
0.000
0.001
0.000
0.001
0.008
0.002
0.002
0.001
80
0.000
0.000
0.000
0.002
0.000
0.001
0.011
0.003
0.003
0.001
90
0.000
0.000
0.000
0.003
0.000
0.001
0.019
0.004
0.003
0.001
100
0.000
0.000
0.000
0.003
0.000
0.001
0.024
0.005
0.005
0.001
150
0.000
0.000
0.000
0.010
0.000
0.005
0.116
0.014
0.014
0.004
200
0.000
0.000
0.000
0.023
0.000
0.010
0.381
0.069
0.030
0.008
250
0.000
0.000
0.000
0.042
0.000
0.019
0.718
0.121
0.055
0.016
300
0.000
0.000
0.000
0.071
0.000
0.035
1.779
0.188
0.094
0.027


## 6.1. Experiment 1: Comparison of the Two MIP Models

In this section, we compare our MIP model with the PF model of Perez-Gonzalez and Framinan [16]; the two models are implemented in IBM ILOG CPLEX Optimization Studio Version 12.7.1. We set a limit of 7200 seconds as the stopping criterion for the two models to solve each instance and then reported the number of optimal solutions obtained by the two models within the time limit and the average computation time for each problem size. Table 5 shows the numbers of optimal solutions obtained and average computation times spent by the two models for each problem; overall, the total numbers of optimal solutions obtained by PF and our models are 857 and 1165, respectively. Furthermore, our model is much more efficient than the PF model; this supports our anticipation, that is, more constraints in our model are advantageous for reducing solution space, resulting in a greater efficiency of our model.Table 5
The comparison results for the PF and our models.
n
Number of optimal solutions obtained
Average CPU time (seconds)
PF model
Our model
PF model
Our model
10
90
90
0.180
0.090
20
90
90
0.349
0.182
30
90
90
21.911
1.328
40
88
90
181.034
7.533
50
81
90
1001.149
11.741
60
72
88
1599.318
242.726
70
66
87
2054.072
313.883
80
54
83
3085.476
627.217
90
46
84
3870.221
607.719
100
36
81
4445.117
897.274
150
24
55
5404.562
3161.652
200
13
58
6290.459
2936.797
250
9
43
6621.720
4175.544
300
8
46
6665.626
4535.073
857
1165
—
—In Table5, our model can give optimal solutions in all instances up to the 50-job problem; however, as the number of jobs increases, the performance of our model gradually worsens, although, fortunately, not like the rapid deterioration of the PF model.


## 6.2. Experiment 2: Comparison of the Heuristic Algorithms

In this section, our proposed heuristic algorithms, namely, H (MW) and H (LB∗), are compared with the well-known heuristic algorithms in the literature, including H (BF), H (FB), and MLPT. All the heuristic algorithms are coded in C++. To compare the algorithms, relative percentage deviation (RPD) is used as a performance measure for each instance. RPD is calculated as follows:(21)RPD=Algsol−MINMIN×100%,where Algsol is the makespan obtained by a given algorithm for an instance, and MIN is the optimal or lower bound value obtained for a given instance.Table6 provides results of different heuristic algorithms for small problems. All optimal solutions could be obtained by our model. The columns of ARPD (%) give average RPD values from the optimal solutions over 90 instances. We can find that the heuristic H (MW) is the best heuristic among the five heuristics if the improvement procedure is not involved, as shown in Table 6. The mean ARPD value of H (MW) is 0.154%, and the heuristic H (MW) on average finds 71.5% of the optimal solutions in the experiments. The results for the heuristic algorithms with improvement procedure are shown in Table 7. It is obvious that using the improvement procedure leads to all the heuristics achieving similar better performances, and the average percentages of optimal solutions found by HI (BF), HI (FB), MLPTI, HI (MW), and HI (LB∗) are 96.9%, 96.5%, 96.95%, 99.1%, and 98.5%, respectively. According to Tables 7 and 8, the solutions of all the heuristics with the improvement procedure are refined evidently without large increase in expenses. Hence, the improvement procedure presented in this paper is a significant addition to the literature.Table 6
The comparative results for different heuristic algorithms.
n
ARPD (%)
Percentage of optimal solutions found (%)
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
8
0.418
18.558
0.418
0.017
0.065
85.6
0.0
85.6
98.9
95.6
10
2.149
17.907
2.149
0.069
1.208
36.7
1.1
36.7
93.3
48.9
20
1.060
24.969
1.060
0.218
1.074
23.3
0.0
23.3
85.6
24.4
30
0.831
26.504
0.831
0.460
0.734
21.1
0.0
21.1
28.9
25.6
40
0.764
27.524
0.764
0.064
0.473
22.2
0.0
22.2
75.6
22.2
50
0.522
27.898
0.522
0.095
0.335
13.3
0.0
13.3
46.7
40.0
Ave.
0.957
23.893
0.957
0.154
0.648
33.7
0.2
33.7
71.5
.42.8Table 7
The comparative results for different heuristic algorithms with improvement procedure.
n
ARPD (%)
Percentage of optimal solutions found (%)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
8
0.000
0.000
0.000
0.000
0.000
100
100
100
100
100
10
0.000
0.000
0.000
0.000
0.000
100
100
100
100
100
20
0.002
0.004
0.002
0.000
0.002
98.9
97.8
98.9
100
98.9
30
0.004
0.010
0.002
0.000
0.000
96.7
0.92.2
97.8
100
100
40
0.005
0.005
0.006
0.002
0.002
93.3
0.94.4
92.2
97.8
97.8
50
0.007
0.005
0.010
0.004
0.005
92.2
0.94.4
92.2
96.7
94.4
Ave.
0.003
0.004
0.003
0.001
0.002
96.9
96.5
96.9
99.1
98.5Table 8
The average computational times for different heuristic algorithms.
n
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
8
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
10
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
20
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
30
0.000
0.000
0.000
0.000
0.000
0.000
0.001
0.000
0.000
0.000
40
0.000
0.000
0.000
0.000
0.000
0.000
0.001
0.000
0.000
0.000
50
0.000
0.000
0.000
0.001
0.000
0.000
0.003
0.001
0.001
0.000Regarding large problems, the solutions obtained by all the heuristics are compared with lower bounds; when the solution obtained by the heuristics is equal to the lower bound, the number of optimal solutions increases by 1, and we could then obtain the percentage of optimal solutions found by each heuristic. As revealed in Table9, the performances of average ARPD value and average percentage of optimal solution found for each heuristic worsen; however, heuristic H (MW) is still the best among them, and furthermore, the results of Table 10 verified again that the improvement procedure indeed significantly induces the quality of the final solutions; it could lead heuristics to obtain better solutions, and adding the improvement procedure into each heuristic does not increase the computational burden a lot, as shown in Table 11. From the general analysis results, the heuristics with improvement procedure can obtain very good solutions very fast, which indicates that the heuristics with improvement procedure can be applied to real-world problem.Table 9
The comparative results for different heuristic algorithms.
n
ARPD (%)
Percentage of optimal solutions found (%)
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
60
0.502
8.901
0.502
0.043
0.257
10.0
0.0
10.0
65.6
23.3
70
0.750
30.030
0.750
0.279
0.438
5.6
0.0
5.6
46.7
26.7
80
0.611
31.142
0.611
0.337
0.462
3.3
0.0
3.3
34.4
17.8
90
0.512
30.545
0.512
0.324
0.358
2.2
0.0
2.2
21.1
11.1
100
0.450
30.994
0.450
0.300
0.324
7.8
0.0
7.8
22.2
23.3
150
0.374
31.294
0.374
0.290
0.300
8.9
0.0
8.9
34.4
32.2
200
0.303
32.360
0.303
0.205
0.228
13.3
0.0
13.3
65.6
32.2
250
0.319
31.324
0.319
0.265
0.278
12.2
0.0
12.2
61.1
45.6
300
0.197
31.147
0.197
0.161
0.184
17.8
0.0
17.8
52.2
55.6
Ave.
0.446
28.637
0.446
0.247
0.314
9.0
0.0
9.0
44.8
29.8Table 10
The comparative results of different heuristic algorithms with improvement procedure for large problems.
n
ARPD (%)
Percentage of optimal solutions found (%)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
60
0.004
0.003
0.006
0.002
0.001
93.3
94.4
91.1
96.7
96.7
70
0.231
0.229
0.230
0.228
0.228
73.3
75.6
72.2
77.8
77.8
80
0.276
0.264
0.278
0.261
0.263
68.9
67.8
64.4
70.0
68.9
90
0.212
0.212
0.213
0.210
0.210
64.4
64.4
64.4
66.7
66.7
100
0.193
0.193
0.192
0.189
0.189
63.3
64.4
66.7
68.9
67.8
150
0.198
0.205
0.213
0.193
0.196
64.4
64.4
65.6
66.7
66.7
200
0.207
0.206
0.208
0.175
0.183
62.2
63.3
63.3
74.4
72.2
250
0.265
0.270
0.266
0.245
0.245
65.6
62.2
64.4
78.9
76.7
300
0.161
0.209
0.161
0.140
0.142
52.2
45.6
50.0
80.0
80.0
Ave.
0.194
0.199
0.196
0.183
0.184
67.5
66.9
66.9
75.6
74.8Table 11
The average computational times of different heuristic algorithms for large problems.
n
H (BF)
H (FB)
MLPT
H (MW)
H (LB∗)
HI (BF)
HI (FB)
MLPT
I
HI (MW)
HI (LB∗)
60
0.000
0.000
0.000
0.001
0.000
0.000
0.005
0.001
0.001
0.000
70
0.000
0.000
0.000
0.001
0.000
0.001
0.008
0.002
0.002
0.001
80
0.000
0.000
0.000
0.002
0.000
0.001
0.011
0.003
0.003
0.001
90
0.000
0.000
0.000
0.003
0.000
0.001
0.019
0.004
0.003
0.001
100
0.000
0.000
0.000
0.003
0.000
0.001
0.024
0.005
0.005
0.001
150
0.000
0.000
0.000
0.010
0.000
0.005
0.116
0.014
0.014
0.004
200
0.000
0.000
0.000
0.023
0.000
0.010
0.381
0.069
0.030
0.008
250
0.000
0.000
0.000
0.042
0.000
0.019
0.718
0.121
0.055
0.016
300
0.000
0.000
0.000
0.071
0.000
0.035
1.779
0.188
0.094
0.027


## 7. Conclusion

In this paper, we address the single-machine scheduling problem with periodic preventive maintenance activities. This problem is commonly encountered in the real world, especially for capital-intensive companies, where periodically implemented preventive maintenance is very important to avoid machine malfunctions. For the problem, there is a vast number of studies in the literature, and different approaches, including mixed integer programming formulations, dynamic programming methods, and heuristic algorithms, are developed for obtaining optimal or near-optimal solutions. Inspired by the study of Perez-Gonzalez and Framinan [16] and the bin-packing problem, the constraint of the minimum bins (or batches) property added into our MIP model makes it more efficient; this is a novel contribution to the single-machine problem with periodic maintenance activities.We also proposed two heuristic algorithms, H (MW) and H (LB∗), in which two different bin-packing policies are used. As the results revealed, H (MW) and H (LB∗) outperformed other heuristic algorithms. We further developed improvement procedures and embedded them into all the heuristic algorithms of the paper. Based on the results of a comprehensive experiment, the performances of the heuristic algorithms with improvement procedure could be improved evidently with a slight increase of computational effort, and after proceeding with the improvement procedure, the solution qualities are not significantly different among all the heuristic algorithms. The results help us conclude that the improvement procedure is very effective and robust regardless of the original heuristic algorithms that this paper used. The research can continue the three directions: (1) modify our proposed algorithms to be suitable for solving general problems such as parallel machine, flowshop, jobshop, and openshop problems; (2) consider different objective functions for the single problem; and (3) multiple objectives can also be investigated for this single-machine scheduling problem with periodic maintenance activities.



---

*Source: 8548463-2020-04-22.xml*