Soft Computing https://doi.org/10.1007/s00500-018-3014-3
METHODOLOGIES AND APPLICATION
Iterated population-based VND algorithms for single-machine scheduling with sequence-dependent setup times Chun-Lung Chen1
© Springer-Verlag GmbH Germany, part of Springer Nature 2018
Abstract This paper investigates the problem of single-machine scheduling with sequence-dependent setup times for minimizing the total weighted tardiness of jobs. Because the problem is non-deterministic polynomial-time hard (NP-hard), an iterated population-based variable neighborhood descent (IPBVND) search algorithm is proposed as the solution. The proposed algorithm first generates the initial population. Then, a novel member updated method is proposed to generate a solution for the IPBVND algorithm at each iteration. Finally, a VND algorithm with a series of block-based insertion neighborhood structures and a greedy local search are presented to improve the solution quality. The computational experiments were made on a set of benchmark problems, and the results demonstrated the effectiveness of the proposed algorithm. Keywords Single-machine scheduling · Iterated local search · Variable neighborhood descent search · Sequence-dependent setup time · Weighted tardiness
1 Introduction In this paper, an iterated population-based variable neighborhood descent (IPBVND) search algorithm is proposed to solve the problem of single-machine scheduling with sequence-dependent setup times (SMSSDST) in order to minimize the total weighted tardiness of jobs. The singlemachine scheduling problem does not necessarily involve a single machine. Issues in a complicated machine environment, such as a single bottleneck (Gagne et al. 2002; Liao and Juan 2007) or other complex scheduling issues, can also be fully reduced to single-machine scheduling; for instance, a group of machines may be treated as a single machine (Al-Turki et al. 2001; Ying et al. 2009). Furthermore, the solutions to the scheduling problems of single-machine models can provide a basis for the development of heuristics that are applicable to more complicated environments (Pinedo 2002).
Communicated by V. Loia.
B 1
Chun-Lung Chen
[email protected] Department of Accounting Information, Takming University of Science and Technology, No.56, Sec.1, Huanshan Rd., Neihu District, Taipei City 11451, Taiwan, ROC
SMSSDST with performance criteria involving due dates, such as total weighted tardiness or total number of tardy jobs, is a reference problem in the industrial context (Anghinolfi and Paolucci 2009). The single-machine problem with the criterion of weighted tardiness is strongly non-deterministic polynomial-time hard (NP-hard) even when no setups exist (Lawler 1977). The problems considered in this study are NP-hard problems, and developing heuristics to solve the problems is acceptable. In recent years, several research studies have applied heuristics to solve SMSSDST problems. Lee et al. (1997) proposed a constructive rule, an apparent tardiness cost with setups (ATCS), to solve SMSSDST problems. Cicirello and Smith (2005) developed four different heuristics, namely limited discrepancy search (LDS), heuristic-biased stochastic sampling (HBSS), value-biased stochastic sampling (VBSS), and hill-climbing using VBSS (VBSS–HC), to minimize the total weighted tardiness of SMSSDST. They used these improvement heuristics and the simulated annealing (SA) heuristic to obtain solutions for a set of 120 benchmark problems with 60 jobs each. Since then, several algorithms have been proposed to solve SMSSDST problems, and the benchmark problem instances proposed by Cicirello and Smith (2005) have been used to assess the performance of these algorithms. These algorithms can be categorized into three groups, namely neighborhood-based, bound-based, and
123
C. Chen
population-based algorithms. The neighborhood-based local search algorithms for solving the same problem instances include the SA and Tabu search (TS) algorithms developed by Lin and Ying (2007), the hybrid metaheuristic (SA–TS) proposed by Lin and Ying (2008), and the iterated greedy (IG) heuristic proposed by Ying et al. (2009). A variable neighborhood search presented by Kirlik and Oguz (2012), Chung et al. (2016), and Fu and Chung (2016). In addition, an iterated local search developed by Xu et al. (2013) and Subramanian et al. (2014). The bound-based algorithms include the beam search (BS) proposed by Valente and Alves (2008) and an exact algorithm presented by Tanaka and Araki (2013) to solve candidate problems. Finally, the populationbased algorithms for solving candidate problems include the genetic algorithms (GA) devised by Lin and Ying (2007). An ant colony optimization (ACO) algorithms proposed by Liao and Juan (2007), Anghinolfi and Paolucci (2008), and Ahmadizar and Hosseini (2011). Particle swarm optimization (PSO) algorithms proposed by Tasgetiren et al. (2004) and discrete particle swarm optimization (DPSO) algorithms proposed by Anghinolfi and Paolucci (2009). A discrete differential evolution (DDE) algorithm developed by Tasgetiren et al. (2009) and GRASP, based on the DE algorithm, developed by Akrout et al. (2012). An improved scatter search algorithm presented by Guo and Tang (2015). Furthermore, a memetic algorithm presented by Gonzalez and Vela (2015) and a memetic algorithm with a variable block insertion heuristic proposed by Tasgetiren et al. (2016). In this paper, the IPBVND algorithm is proposed to solve the SMSSDST problem with the aim of minimizing the total weighted tardiness. The proposed IPBVND algorithm can be regarded as a population-based search algorithm. The proposed algorithm first applies the destruction and construction (DC) procedure proposed by Ruiz and Stutzle (2007) to construct the initial population solutions. Then, a novel member updated method is proposed to generate a solution for the IPBVND algorithm at each iteration. Finally, the VND algorithm with a series of block-based insertion neighborhood structures and a greedy local search with a speed-up method are presented to improve the generated solution. The benchmark problem set proposed by Cicirello and Smith (2005) is used to assess the performance of the proposed algorithm. The rest of this paper is organized as follows: Sect. 2 describes the problem considered in this study; Sect. 3 describes the proposed algorithm; Sect. 4 presents the computational experiments; and our conclusions and ideas for future work are summarized in Sect. 5.
2 Problem Description The SMSSDST problem in our study can be described as follows: A job set J = {1, 2, . . ., n} of n jobs have to
123
be scheduled on a single machine. Each job j ∈ J has a positive processing time p j , a sequence-dependent setup time si j , a due date d j , and a positive weight w j . Here, si j denotes that job j is scheduled to be performed after job i by the machine. Let be the sequence of jobs, i.e., (π0 , π1 , . . ., πn ), where π j is the index of the jth job in the sequence and π0 is a dummy job representing the initial setup of the machine. We make the following assumptions: All the jobs are available for processing at time zero; the processing and setup times of the jobs are known and fixed; machine breakdown does not occur; the machine can process only one job at a time; and jobs cannot be preempted. The objective of this algorithm is to find a schedule that minimizes the total weighted tardiness. This objective can be defined as follows: Objective = Minimize nj=1 w j × T j , where T j = (C j − d j ) if job j is tardy, with C j being the completion time of job j; otherwise, T j = 0. Using a three-field notation, α/β/γ , the problem can be defined as 1/si j / w j T j .
3 Proposed Algorithm An iterated population-based variable neighborhood descent (IPBVND) search algorithm is developed to solve the SMSSDST problem. Figure 1 illustrates the functionality of the proposed algorithm. The main components of the IPBVND algorithm include population initialization, a member updated method, and a VND for improving the solution quality. The IPBVND algorithm first applies the apparent tardiness cost with setups (ATCS) rule (Lee et al. 1997) to generate an initial solution, and then the destruction and construction (DC) procedure (Ruiz and Stutzle 2007) is used to construct the initial population with m members. A block-based crossover operator and the DC procedure are applied in the member updated method to generate a good solution for the IPBVND algorithm at each iteration. Two parameters, c1 and c2 , are used to determine the probabilities that a member will inherit information from the global best solution by the crossover operator, shake itself by the DC procedure, and do nothing. When the members have been updated, a solution will be selected and the new VND algorithm is implemented. This search process continues until a termination criterion is satisfied. The main components of the proposed IPBVND algorithm are described below, and the notation used in Fig. 1 is as follows: i is the solution of member i; Vi is the objective value of i ; V gbest is the objective value of the global best solution gbest ; m is the number of members generated in an iteration; and V V N D is the objective value of solution V N D generated by the VND local search.
Iterated population-based VND algorithms for single-machine scheduling with…
Fig. 1 The procedure of the proposed IPBVND algorithm
3.1 Initial Population The main difference between IPBVND and the simple iterated local search proposed by Xu et al. (2013) and Subramanian et al. (2014) is that IPBVND is a population-based algorithm. Hence, two heuristics, the ATCS rule (Lee et al. 1997) and the DC procedure (Ruiz and Stutzle 2007), are constructed to generate the initial population for the proposed algorithm. The proposed method works as follows: the ATCS rule is applied to generate a solution; then, based on the generated solution, the DC procedure is used to regenerate n-1 different solutions, where n is the population size. The ATCS rule calculates the index of job i at time t when job j has been processed on the machine as s j,i wi max(di − pi − t, 0) exp − , exp − Ii (t, j) = pi k1 p¯ k2 s¯ where p¯ and s¯ represent the average processing time and average setup time of all remaining jobs, respectively; k1 is
a due-date-related scaling parameter; and k2 is a setup timerelated scaling parameter. Values of k1 = 4.75 and k2 = 0.15 are used in our implementation. Ruiz and Stutzle’s (2007) DC procedure works as follows: Given a solution , the destruction operation first randomly chooses d jobs from the solution. Let the job sequence of the d jobs be 1 and the job sequence of the remaining jobs be 2 . The first job in 1 is then inserted into first position, last position, and the positions between every two consecutive jobs in 2 , and the sequence with the smallest objective value is chosen. This process is repeated until all d jobs in 1 have been inserted into 2 . The value d = 4 is used in our implementation.
3.2 Member Updated Method In this study, we develop a novel member updated method to generate a solution for the IPBVND algorithm. In the updated method, each solution in the population will be updated or retained according to two parameters, c1 and
123
C. Chen
c2 , which are less than or equal to 1.0. Two functions, the block-based crossover operator and DC procedure (Ruiz and Stutzle 2007), are used to update the solutions. The blockbased crossover operator is implemented with a probability of c1 ; it exchanges information with solution i and the global best solution gbest , and refers to the condition that member i will inherit information from the global best solution. In addition, if the member solution value is equal to the global best solution value before the update, the DC procedure is applied to shake the solution until a different global best solution value is obtained. This prevents useless perturbations by the block-based crossover and increases diversification. The DC procedure is implemented with a probability of c2 ; this function updates member i. The block-based crossover operator first selects a block of k consecutive jobs from gbest . The second step is to construct a new solution by assigning this block to the same position in the new solution as it occupied in gbest . The final step is to sequentially assign the jobs in i , which are not in the block, to the empty positions in the new solution. The values of c1 and c2 are set so as to generate suitable probabilities that a member will inherit information from the global best solution, the member will shake itself, and the member will be unchanged. Table 1 presents seven combinations of c1 and c2 considered in this study. The probability values pg , ps , and pr for each of the combinations are calculated following the process illustrated in Fig. 1. First, c1 is used to determine pg ( pg = c1 ), then c2 is used to determine ps ( ps = (1 − c1 ) × c2 ). The remaining probability is the probability of pr ( pr = 1 − pg − ps ). For instance, if c1 = 0.1 and c2 = 0.9 (the second combination in Table 1), then pg = c1 = 0.1, ps = (1 − c1 ) × c2 = 0.81, and pr = 1 − pg − ps = 0.09. The values of pg , ps , and pr for the combinations in Table 1 demonstrate the purpose of selecting the seven combinations. A combination with larger c1 (when c1 = 0.9) will have a larger pg and a smaller ps , which implies that a member will learn more from the global best solution. On the contrary, a combination with smaller c1 (when c1 = 0.1) will have a smaller pg and a larger Table 1 The seven combinations of c1 and c2 considered in the member updated method Controlled parameters c1 c2
Controlled probability pg ps pr
0.0
1.0
0.00
1.00
0.00
0.1
0.9
0.10
0.81
0.09
0.3
0.9
0.30
0.63
0.07
0.5
0.9
0.50
0.45
0.05
0.7
0.9
0.70
0.27
0.03
0.9
0.9
0.90
0.09
0.01
1.0
0.0
1.00
0.00
0.00
123
ps , and the member will shake itself more to learn from the global best solution under this condition. The first and last combinations (c1 = 0.0 and c2 = 1.0 and c1 = 1.0 and c2 = 0.0) are designed for the conditions whereby a member will totally shake itself ( ps = 1.0) and inherit information from the global best solution ( pg = 1.0), respectively. In addition to the generated solution that guides the search of the IPBVND algorithm, a multiple-phase member updated method is constructed to update the solution using a different set of predefined control probabilities ( pg , ps , pr ). This multiple-phase member updated method increases the diversity of the population. The solution generated by the multiple-phase member updated method helps the VND local search to avoid useless searches by not using repeated input solutions. For example, a four-phase member updated method uses the set ( pg1 , ps1 , pr1 ) of the combination in the first quarter of the search process, the set ( pg2 , ps2 , pr2 ) in the second quarter of the search process, the set ( pg3 , ps3 , pr3 ) in the third quarter of the search process, and the set ( pg4 , ps4 , pr4 ) in the fourth quarter of the search process. We can assume that the four-phase member updated method employs the following ( pg , ps , pr ) values: ( pg1 , ps1 , pr1 ) = (0.1, 0.81, 0.09), ( pg2 , ps2 , pr2 ) = (0.2, 0.72, 0.08), ( pg3 , ps3 , pr3 ) = (0.3, 0.63, 0.07), and ( pg4 , ps4 , pr4 ) = (0.5, 0.45, 0.05). With a total of 200,000 evaluations in the whole search process, each quarter corresponds to 50,000 evaluations. When all members have been updated, a solution k is selected, and the new VND algorithm is implemented to improve the solution. The solution value Vk is the minimum among all members and is different from the value V gbest of the global best solution gbest .
3.3 Proposed VND Local Search The VND search proposed by Hansen and Mladenovi´c (2001) can be regarded as a variant of the variable neighborhood search (VNS) developed by Mladenovic and Hansen (1997). This heuristic searches the solution space using a set of predefined neighborhood structures. The search escapes from local optima by systematically changing these neighborhood structures. The major difference between VNS and VND is that, within each neighborhood structure, VNS starts the search with a randomly generated neighbor solution, whereas VND starts the search from the best solution generated in the previous iteration. The VND heuristic has been successfully applied to solve scheduling problems such as the single-machine problem (Kirlik and Oguz 2012; Chung et al. 2016; Fu and Chung 2016), unrelated parallel machine problem (Chen and Chen 2009), and flexible job shop scheduling problem (Gao et al. 2008). The workflow of the proposed VND algorithm is shown in Fig. 2. When applying the VND heuristic to solve a candi-
Iterated population-based VND algorithms for single-machine scheduling with…
Fig. 2 The procedure of the proposed VND algorithm
date problem, the most important step is to define the set of neighborhood structures. The VND proposed in this paper employs a series of neighborhood structures based on the insertion move of a subsequence (block). The block move neighborhood structures proposed by Xu et al. (2013) and Chen (2013) are suitable for SMSSDST. The block move used by Xu et al. (2013) is very similar to the famous 3-opt neighborhood for the traveling salesman problem (TSP); as applied by Chen (2013), this can be regarded as a k-opt neighborhood. In addition, a greedy local search algorithm with speed-up method (GLS) is applied to explore the solution space of the predefined neighborhoods. We assume the solution can be denoted by (π0 , π1 , π2 , …, π j ,…, πn ), where π j is the jth job to be processed. The basic insertion procedure selects a random subsequence (π j , π j+1 , …, π j+τ −1 ) of τ consecutive jobs, and a position p outside this subsequence. The subsequence is then inserted between positions p and p +1. This insertion of a subsequence is used to define neighbor solutions for a given solution, and the operation evaluates (n −τ +1)(n −τ ) possible neighbor solutions within an iteration. For convenience, we name the proposed insertion move neighborhood structure INS(τ ), where τ is a positive integer denoting the length of the selected subsequence.
The series INS (τ ) can be used in the proposed VND algorithm. For example, by setting τ to 1, 2, and 3, three insertion move neighborhood structures INS1 (1), INS2 (2), and INS3 (3) are constructed. INS1 (1) represents the first neighborhood structure of the proposed algorithm. If the GLS explores INS1 (1) and does not improve the local best solution (b ), it proceeds to the next neighborhood structure INS2 (2). If the GLS explores INS2 (2) and still does not improve the local best solution, it proceeds to the next neighborhood structure INS3 (3). Finally, if the GLS cannot find a neighbor in INS3 (3) that is better than the local best solution, the search terminates. If the GLS improves the local best solution while exploring INS1 (1), INS2 (2), or INS3 (3), the search restarts from INS1 (1). Since the sequence of the neighborhood structures guides the search of the VND, a variable sequence of neighborhood structures is presented to help the VND achieve better performance. This variable sequence is determined randomly. A greedy local search (GLS) algorithm with a speedup method is applied to explore the solution space of the proposed neighborhoods. The speed-up method is derived from the work of Tasgetiren et al. (2009) and Xu et al. (2013). Tasgetiren et al. (2009) designed a speed-up method for evaluating the insertion neighborhood, and Xu et al. (2013) extended this method to present an extended speed-up
123
C. Chen
method and a fast evaluation technique for the block move insertion neighborhood. The extended speed-up method with fast evaluation technique can evaluate about 2,500,000 solutions per second, an improvement from 1,300,000 solutions per second without the local search. The speed-up method used in IPBVND is the same as the extended speed-up method presented by Xu et al. (2013). The proposed speed-up method consists of two main steps: the current job sequence is first divided into two parts, where one is the job sequence consisting of (n − τ ) jobs and the other consists of τ jobs; the τ jobs are then inserted into a feasible position in the (n −τ ) job sequence. When evaluating the objective function of an insertion move, the objective value of the (n − τ ) jobs sequence is calculated first. The deviation in the objective value is then computed for three insertion moves: inserting the job at the head, at the end, and into an intermediate position of the (n − τ ) jobs sequence (Tasgetiren et al. 2009; Xu et al. 2013).
Table 2 The values of the member updated method parameter Updated type
Controlled probability ( pg , ps , pr )
Single Phase
(0.00, 1.00, 0.00), (0.10, 0.81, 0.09), (0.30, 0.63, 0.07), (0.50, 0.45, 0.05), (0.70, 0.27, 0.03), (0.90, 0.09, 0.01), (1.00, 0.00, 0.00)
Two Phases
phase1= (0.10, 0.81, 0.09),
Three Phases
phase1= (0.10, 0.81, 0.09),
phase2= (0.50, 0.45, 0.05) phase2= (0.30, 0.63, 0.07), phase3= (0.50, 0.45, 0.05) Four Phases
phase1= (0.10, 0.81, 0.09), phase2= (0.20, 0.72, 0.08), phase3= (0.30, 0.63, 0.07), phase4= (0.50, 0.45, 0.05)
4 Computational Experiments To assess the performance of the proposed IPBVND algorithm, two sets of experiments were conducted. The first set investigates the effects of the member updated methods and the neighborhood structures of VND; the second set compares the performance of the IPBVND algorithm with the best parameters found in the first set against several metaheuristics reported in the literature. We coded the different IPBVND algorithms in C++, and executed them on an Intel Core i7 PC with 3.4 GHz CPU and 4 GB RAM. A series of computational experiments were conducted to compare the results of all the combinations of algorithms with the benchmark instances provided by Cicirello and Smith (2005). The problem instances are characterized by three parameters: due-date tightness μ, due date range R, and setup time severity η. The instances were generated by the following parameter values: μ = {0.3, 0.6, 0.9}, R = {0.25, 0.75}, and η = {0.25, 0.75}. From each of the 12 combinations of parameters, 10 problem instances, each involving 60 jobs, were generated. These 12 problem sets include various loosely and tightly constrained instances. The benchmark values for these instances were established by applying each of the following improvement heuristics: LDS, HBSS, VBSS, and VBSS–HC. For the first set of experiments, 10 instances (1, 11, 41, 51, 61, 71, 81, 91, 101, and 111) were used to investigate the effects of the parameters. The parameters of the member updated method have 12 separate levels (see Table 2). The single-phase member updated method has seven levels, and the multiple-phase member updated method has five levels (two phases to six phases). The neighborhood structure test case has eight fixed sequence
123
Five Phases
phase1= (0.10, 0.81, 0.09), phase2= (0.20, 0.72, 0.08), phase3= (0.30, 0.63, 0.07), phase4= (0.40, 0.54, 0.06), phase5= (0.50, 0.45, 0.05)
Six Phases
phase1= (0.10, 0.81, 0.09), phase2= (0.20, 0.72, 0.08), phase3= (0.30, 0.63, 0.07), phase4= (0.40, 0.54, 0.06), phase5= (0.50, 0.45, 0.05), phase6= (0.60, 0.36, 0.04)
levels (INS1 (1), INS1 (1) + INS2 (2), INS1 (1) + INS2 (2) + INS3 (3), . . ., INS1 (1) + INS2 (2) + · · · + INS8 (8)) and seven variable sequence levels (V (INS1 (1) + INS2 (2)), V (INS1 (1)+INS2 (2)+INS3 (3)), …, V (INS1 (1)+INS2 (2)+ · · · + INS8 (8))). For convenience, we named the eight fixed forms F1, F2, F3, . . . , F8 and the seven variable forms V (F2), V (F3), …, V (F8). Therefore, there are a total of 180 different combinations of the two major parameters. The remaining parameters of the IPBVND algorithms were set as follows: the population size was set to 20; the block size for the block crossover was set to 15; and the termination criterion was set to 12 s. The IPBVND algorithms with each of the 180 combinations were then applied to solve the 10 instances for six trials. The Average Relative Performance (ARP) was used to measure the performance of the IPBVND algorithms. The ARP can be calculated as follows: ARP = R solutioni −OPTsol × 100)/R; given an instance, solutioni i=1 ( OPT sol is the total weighted tardiness obtained by trial i of the IPB-
Iterated population-based VND algorithms for single-machine scheduling with… Table 3 ANOVA table for testing the significance of the major parameters of IPBVND Source
Type III sum of squares
df
Mean square
F
Sig.
Corrected model
188.373a
34
5.540
482.095
0.000
Intercept
69.437
1
69.437
6041.997
0.000
Instances
156.392
9
17.377
1512.041
0.000
Member updated method
23.029
11
2.094
182.173
0.000
Neighborhood structure test cases
8.952
14
.639
55.639
0.000
Error
123.715
10765
.011
Total
381.525
10800
Corrected total
312.088
10799
a R2
= .604 (Adjusted R 2 = .602)
Table 4 Results of Duncan’s multiple range test for the member updated method (α = 0.05)
Member updated method
Results (groups)
Average RDI
Five phase
A
0.0508
Three phase
A
0.0512
Six phase
A
0.0524
Two phase
A
0.0531
Four phase
A
0.0540
Single phase (0.50, 0.45, 0.05)
A
0.0541
Single phase (0.30, 0.63, 0.07)
A
0.0547
Single phase (0.70, 0.27, 0.03)
AB
0.0688
Single phase (0.10, 0.81, 0.09)
ABC
0.0894
Single phase (0.90, 0.09, 0.01)
ABC
0.0956
Single phase (0.00, 1.00, 0.00)
ABCD
0.1237
Single phase (1.00, 0.00, 0.00)
ABCDE
0.2144
VND algorithm for that instance, and OPTsol is the optimal solution provided by Tanaka and Araki (2013) and Xu et al. (2014). An analysis of variance (ANOVA) was applied to analyze the ARP produced by the IPBVND algorithms with all 180 combinations for the 10 instances. Table 3 presents the results of the ANOVA, showing that the two major parameters of the member perturbation and the neighborhood structures significantly affect the performance of the IPBVND algorithms. Duncan’s multiple range test was applied to determine whether the performance of any two levels of the two-phase member perturbation and neighborhood structure were significantly different. Tables 4 and 5 present the results of Duncan’s test for the member updated method and the neighborhood structure test cases, respectively. Note that the different letters indicate that the performance of the IPBVND algorithms with those levels was significantly different. The results in Table 4 show that the five-phase member updated method [phase 1: ( pg1 = 0.1, ps1 = 0.81, pr1 = 0.09); phase 2: ( pg2 = 0.2, ps2 = 0.72, pr2 = 0.08); phase 3: ( pg3 = 0.3, ps3 = 0.63, pr3 = 0.07); phase 4: ( pg4 = 0.4, ps4 = 0.54, pr4 = 0.06); and phase 5:
Table 5 Results of Duncan’s multiple range test for the neighborhood structure test cases (α = 0.05) Neighborhood structure test cases
Results (groups)
ARP
V(F8)
A
0.0520
V(F7)
AB
0.0542
V(F6)
ABC
0.0567
V(F5)
ABCD
0.0606
F8
BCD
0.0645
F7
CD
0.0670
V (F4)
CD
0.0683
F6
DE
0.0694
F5
DEF
0.0724
V(F3)
EFG
0.0803
F4
FG
0.0820
F3
G
0.0878
V(F2)
H
0.1059
F2
H
0.1163
F1
I
0.1654
123
C. Chen Table 6 Results of OPT, DPSO, DDE, GVNS, HEA, and IPBVND for SMSSDST problem Ins.
OPT
DPSO
DDE
GVNS
HEA
IPBVND
Ins.
OPT
DPSO
DDE
GVNS
HEA
IPBVND
1
453
531
474
471
459
459
61
75916
75916
75916
75916
75916
75916
2
4794
5088
4902
4878
4830
4830
62
44769
44769
44769
44769
44769
44781
3
1390
1609
1465
1430
1410
1395
63
75317
75317
75317
75317
75317
75317
4
5866
6146
5946
6006
5866
5866
64
92572
92572
92572
92572
92572
92572
5
4054
4339
4084
4114
4084
4074
65
126696
126696
126696
126696
126696
126696
6
6592
6832
6652
6667
6592
6592
66
59685
59685
59685
59685
59685
59685
7
3267
3514
3350
3330
3297
3296
67
29390
29390
29390
29390
29390
29390
8
100
132
114
108
101
101
68
22120
22120
22120
22120
22120
22278
9
5660
6153
5803
5751
5686
5673
69
71118
71118
71118
71118
71118
71118
10
1740
1895
1799
1789
1761
1761
70
75102
75102
75102
75102
75102
75102
11
2785
3649
3294
2998
2846
2862
71
145007
145771
145007
145007
145290
145007
12
0
0
0
0
0
0
72
43286
43994
43904
43286
43775
43286
13
3904
4430
4194
4068
3978
3987
73
28785
28785
28785
28785
28785
28785
14
2075
2749
2268
2260
2188
2105
74
29777
30734
30313
30136
30318
29777
15
724
1250
964
935
826
830
75
21602
21602
21602
21602
21602
21602
16
3285
4127
3876
3381
3301
3301
76
53555
53899
53555
54024
53555
53555
17
0
75
61
0
0
0
77
31817
31937
32237
31817
31937
31817
18
767
971
857
845
803
773
78
19462
19660
19462
19462
19462
19462
19
0
0
0
0
0
0
79
114999
114999
114999
114999
114999
114999
20
1757
2675
2111
2053
1773
1765
80
18157
18157
18157
18157
18157
18157 383485
21
0
0
0
0
0
0
81
383485
383703
383485
383485
383485
22
0
0
0
0
0
0
82
409479
409544
409544
409479
409479
409479
23
0
0
0
0
0
0
83
458752
458787
458752
458752
458752
458752
24
761
1043
1033
920
1030
1027
84
329670
329670
329670
329670
329934
329670
25
0
0
0
0
0
0
85
554766
555130
554993
554766
554773
554872 361417
26
0
0
0
0
0
0
86
361417
361417
361417
361417
361417
27
0
0
0
0
0
0
87
398551
398551
398670
398551
398551
398551
28
0
0
0
0
0
0
88
433186
433519
433186
433244
433244
433244
29
0
0
0
0
0
0
89
410092
410092
410092
410092
410092
410092 401653
30
0
0
0
0
0
0
90
401653
401653
401653
401653
401653
31
0
0
0
0
0
0
91
339933
343029
340508
339933
339933
339933
32
0
0
0
0
0
0
92
361152
361152
361152
361152
361152
361152
33
0
0
0
0
0
0
93
403423
406728
404548
404917
403423
403423
34
0
0
0
0
0
0
94
332941
332983
333020
332949
332941
332941
35
0
0
0
0
0
0
95
516926
521208
517011
517646
516978
516978
36
0
0
0
0
0
0
96
455448
459321
457631
457631
455672
455672
37
0
186
107
46
56
16
97
407590
410889
409263
407590
407590
407590
38
0
0
0
0
0
0
98
520582
522630
523486
520582
520582
520582
39
0
0
0
0
0
0
99
363518
365149
364442
363977
363518
363518
40
0
0
0
0
0
0
100
431736
432714
431736
432068
431736
431736
123
Iterated population-based VND algorithms for single-machine scheduling with… Table 6 continued Ins.
OPT
DPSO
DDE
GVNS
HEA
IPBVND
Ins.
OPT
41
69102
69102
69242
69242
69102
69102
101
352990
352990
352990
352990
352990
352990
42
57487
57487
57511
57511
57487
57487
102
492572
493069
492748
492572
492572
492572
43
145310
145883
145310
145310
145310
145310
103
378602
378602
378602
378602
378602
378602
44
35166
35331
35289
35289
35166
35166
104
357963
357963
357963
357963
357963
358033
45
58935
59175
58935
59025
58935
58935
105
450806
450806
450806
450806
450806
450806
46
34764
34805
34764
34764
34764
34764
106
454379
455152
454379
454379
454379
454379
47
72853
73378
73005
72853
72853
72853
107
352766
352867
352766
352766
352766
352766
48
64612
64612
64612
64612
64612
64612
108
460793
460793
460793
460793
460793
460793
49
77449
77771
77641
77833
77472
77449
109
413004
413004
413004
413004
413408
413004
50
31092
31810
31565
31292
31092
31092
110
418769
418769
418769
418769
418769
418769
51
49208
49907
49927
49761
49208
49208
111
342752
342752
342752
342752
342752
342752
52
93045
94175
94603
93106
93045
93045
112
367110
369237
367110
367110
367110
367110
53
84841
86891
84841
84841
86374
84841
113
259649
260176
260872
259649
259649
259649
54
118809
118809
119226
119074
118961
119074
114
463474
464136
465503
463474
463474
463474
55
64315
68649
66006
65400
64315
64315
115
456890
457874
457289
457189
456904
456890
56
74889
75490
75367
74940
74889
74889
116
530601
532456
530803
530601
530601
530601
57
63514
64575
64552
64575
64306
63514
117
502840
503199
502840
503046
502840
502840
58
45322
45680
45322
45322
45522
45322
118
349749
350729
349749
349749
350078
349749
59
50999
52001
52207
51649
51233
50999
119
573046
573046
573046
573046
573046
573046
60
60765
63342
60765
61755
60765
60765
120
396183
396183
396183
396183
396183
396183
Table 7 Paired t test for DPSO, DDE, GVNS, HEA and IPVNND
DPSO
DDE
GVNS
Paired differences Mean
SD
SE mean
HEA
t
IPBVND
df
Sig. (2-tailed)
95% Confidence interval of the difference Lower
Upper
Pair 1
DPSO–IPBVND
480.5
896.8
81.9
318.4
642.6
5.9
119
0.000
Pair 2
DDE–IPBVND
212.3
490.0
44.7
123.7
300.8
4.7
119
0.000
Pair 3
GVNS–IPBVND
105.5
296.7
27.1
51.8
159.1
3.9
119
0.000
Pair 4
HEA–IPBVND
41.2
181.0
16.5
8.5
74.0
2.5
119
0.014
( pg5 = 0.5, ps5 = 0.45, pr5 = 0.05)] produces the best mean ARP. In addition, the results show that the multiple-phase member updated method performs better than the singlephase member updated method. These results confirm our conjecture that the IPBVND algorithms using the multiplephase member updated method to search different solution spaces converge upon good solution regions. In addition, the single-phase member updated method with probabilities of ( pg = 1.0, ps = 0.0, pr = 0.0) and ( pg = 0.0, ps = 1.0, pr = 0.0) produced a poor mean ARP. This result indicates that the IPBVND algorithms using only the global best solution ( pg ) or shaking itself ( ps ) will not converge to good solution regions. The results in Table 5 show that the values of the neighborhood structure test cases, V (F8), V (F7), V (F6), and V (F5), belong to the first subset. This means that the variable
Table 8 Summary of comparing IPBVND with reference heuristics DPSO
DDE
GVNS
HEA
Number of improved solutions
66
52
41
22
Number of equal solutions
50
64
74
90
Number of inferior solutions
4
4
5
8
Number of all solutions
120
120
120
120
sequence of neighborhood structures outperformed the fixed sequence of neighborhood structures. This result also illustrates that the IPBVND algorithms using at least five insertion moves (INS1 (1) + INS2 (2) + … +INS5 (5)) in the neighborhood structure achieved better results. The mean ARP suggests that the IPBVND algorithms using V (F8) dominate
123
C. Chen Table 9 Average relative performance (ARP) (%) of the DPSO, DDE, GVNS, HEA, and IPBVND
Problem set (m = 60)
DPSO
DDE
GVNS
HEA
IPBVND
Problem 1–10 (μ = 0.3, R = 0.25, η = 0.25)
11.17
3.78
2.80
0.78
0.63
Problem 11–20 (μ = 0.3, R = 0.25, η = 0.75)
25.41
11.80
7.99
2.97
2.27
Problem 21–30 (μ = 0.3, R = 0.75, η = 0.25)
3.71
3.57
2.09
3.54
3.50
Problem 31–40 (μ = 0.3, R = 0.75, η = 0.75)
0.00
0.00
0.00
0.00
0.00
Problem 41–50 (μ = 0.6, R = 0.25, η = 0.25)
0.48
0.26
0.19
0.00
0.00
Problem 51–60 (μ = 0.6, R = 0.25, η = 0.75)
2.13
1.08
0.77
0.41
0.02
Problem 61–70 (μ = 0.6, R = 0.75, η = 0.25)
0.00
0.00
0.00
0.00
0.07
Problem 71–80 (μ = 0.6, R = 0.75, η = 0.75)
0.74
0.46
0.21
0.35
0.00
Problem 81–90 (μ = 0.9, R = 0.25, η = 0.25)
0.02
0.01
0.00
0.01
0.00
Problem 91–100 (μ = 0.9, R = 0.25, η = 0.75)
0.53
0.22
0.12
0.01
0.01
Problem 101–110 (μ = 0.9, R = 0.75, η = 0.25)
0.03
0.00
0.00
0.01
0.00
Problem 111–120 (μ = 0.9, R = 0.75, η = 0.75)
0.18
0.10
0.01
0.01
0.00
Average improvement rates
3.70
1.77
1.18
0.67
0.54
the IPBVND algorithms using F2 and F1 by 55% ((0.1163− 0.0520)/0.1163)) and 69% ((0.1654 − 0.0520)/0.1654)), respectively. These analyses confirm that the best parameter set for the IPBVND algorithms is the five-phase member updated method [phase 1: ( pg1 = 0.1, ps1 = 0.81, pr1 = 0.09); phase 2: ( pg2 = 0.2, ps2 = 0.72, pr2 = 0.08); phase 3: ( pg3 = 0.3, ps3 = 0.63, pr3 = 0.07); phase 4: ( pg4 = 0.4, ps4 = 0.54, pr4 = 0.06); and phase 5: ( pg5 = 0.5, ps5 = 0.45, pr5 = 0.05)] and the variable sequence of neighborhood structures with eight insertion neighborhood structures (V(INS1 (1) + INS2 (2) + … + INS8 (8)) = V(F8)). The second set of experiments investigated the performance of the IPBVND algorithm using the optimal parameters determined from the first set of experiments. We compared the performance of the proposed IPBVND algorithm with five sets of optimal and best known solutions: (1) OPT: optimal solutions reported by Tanaka and Araki (2013). (2) DPSO: best solutions reported by Anghinolfi and Paolucci (2009). (3) DDE: best solutions reported by Tasgetiren et al. (2009). (4) GVNS: best solutions reported by Kirlik and Oguz (2012). (5) HEA: best solutions reported by Xu et al. (2014). When analyzing the results of the above studies, we observed that HEA is superior to other heuristics in terms of ARP. In the paper proposed by Xu et al. (2014), in order to have a fair comparison with the DDE algorithm, the HEA algorithm was performed with 10 replications with a maximum CPU time of 25 s. Therefore, in order to compare the computational efficiency among these heuristics mentioned above, IPBVND algorithm was intentionally applied for 10
123
times under the time limit of 25 s for 120 test instances, which is in the same condition as in HEA. Table 6 lists the best solution value for each problem instance obtained by IPBVND and the five sets of optimal and best known solutions. The IPBVND algorithm that obtained the optimal solution for each instance is shown in bold. The results in Table 6 show that the IPBVND algorithm was able to find the optimal solutions for 95 out of 120 instances (79.2%). Table 7 presents the results of the paired t test for DPSO, DDE, GVNS, HEA, and IPBVND. The results show that IPBVND dominates DPSO, DDE, and GVNS at the significance level of 0.0, and dominates HEA at the significance level of 0.014. Based on the results in Table 6, a comparison with the reference heuristics is summarized in Table 8, where the numbers of better, equal, and worse solutions are presented. We can observe that IPBVND outperformed DPSO, DDE, GVNS, and HEA. Compared with DPSO, DDE, GVNS, and HEA, the proposed IPBVND produced 66, 52, 41, and 22 better solutions, respectively, for the 120 instances, whereas the number of worse solutions was not more than 8. We further analyzed the performance of IPBVND across a wide variety of due-date tightness (μ), due-date range (R), and setup time severity (η) parameters. Our results, summarized in Table 9, indicate that IPBVND outperformed DPSO, DDE, GVNS, and HEA. The ARPs show that IPBVND dominated DPSO by 85% ((3.7 − 0.54)/3.7), dominated DDE by 69% ((1.77 − 0.54)/1.77), dominated GVNS by 54% ((1.18 − 0.54)/1.18), and dominated HEA by 20% ((0.67 − 0.54)/0.67). Furthermore, the termination conditions for IPBVND were also examined to verify its effectiveness under longer computation times. Therefore, two IPBVND algorithms with termination conditions of 100 and 1500 s were constructed. The results in Table 10 show that IPBVND with a termination
5866
6592
3267
100
5660
1747
2854
0
3942
2081
772
3301
0
767
0
1757
0
0
0
767
0
0
0
0
0
0
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1390
3
4074
4794
2
5
453
1
4
IPBVND/ 100
Ins.
0
0
0
0
0
0
761
0
0
0
1757
0
767
0
3285
724
2075
3904
0
2787
1740
5660
100
3267
6592
4054
5866
1390
4794
453
IPBVND/ 1500
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
Ins.
60765
50999
45322
63514
74889
64315
118809
84841
93045
49208
31092
77449
64612
72853
34764
58935
35166
145310
57487
69102
0
0
0
0
0
0
0
0
0
0
IPBVND/ 100
Table 10 Results of IPBVND/100 and IPBVND/1500 for SMSSDST problem
60765
50999
45322
63514
74889
64315
118809
84841
93045
49208
31092
77449
64612
72853
34764
58935
35166
145310
57487
69102
0
0
0
0
0
0
0
0
0
0
IPBVND/ 1500
90
89
88
87
401653
410092
433186
398551
554766 361417
85
329670
458752
409479
383485
18157
114999
19462
31817
53555
21602
29777
28785
43286
145007
75102
71118
22120
29390
59685
126696
92572
75317
44769
75916
IPBVND/ 100
86
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
Ins.
401653
410092
433186
398551
361417
554766
329670
458752
409479
383485
18157
114999
19462
31817
53555
21602
29777
28785
43286
145007
75102
71118
22120
29390
59685
126696
92572
75317
44769
75916
IPBVND/ 1500
120
119
118
117
116
115
114
113
112
111
110
109
108
107
106
105
104
103
102
101
100
99
98
97
96
95
94
93
92
91
Ins.
396183
573046
349749
502840
530601
456890
463474
259649
367110
342752
418769
413004
460793
352766
454379
450806
396183
573046
349749
502840
530601
456890
463474
259649
367110
342752
418769
413004
460793
352766
454379
450806
357963
378602
378602 357963
492572
352990
431736
363518
520582
407590
455448
516926
332941
403423
361152
339933
IPBVND/ 1500
492572
352990
431736
363518
520582
407590
455448
516926
332941
403423
361152
339933
IPBVND/ 100
Iterated population-based VND algorithms for single-machine scheduling with…
123
C. Chen Table 11 Average relative performance (ARP) (%) of the IPBVND/25, IPBVND/100, and IPBVND/1500 Problem set (n = 60)
IPBVND/25
IPBVND/100
IPBVND/1500
Problem 1–10 (μ = 0.3, R = 0.25, η = 0.25)
0.63
0.09
0.00
Problem 11–20 (μ = 0.3, R = 0.25, η = 0.75)
2.27
1.09
0.01
Problem 21–30 (μ = 0.3, R = 0.75, η = 0.25)
3.50
0.08
0.00
Problem 31–40 (μ = 0.3, R = 0.75, η = 0.75)
0.00
0.00
0.00
Problem 41–50 (μ = 0.6, R = 0.25, η = 0.25)
0.00
0.00
0.00
Problem 51–60 (μ = 0.6, R = 0.25, η = 0.75)
0.02
0.00
0.00
Problem 61–70 (μ = 0.6, R = 0.75, η = 0.25)
0.07
0.00
0.00
Problem 71–80 (μ = 0.6, R = 0.75, η = 0.75)
0.00
0.00
0.00
Problem 81–90 (μ = 0.9, R = 0.25, η = 0.25)
0.00
0.00
0.00
Problem 91–100 (μ = 0.9, R = 0.25, η = 0.75)
0.01
0.00
0.00
Problem 101–110 (μ = 0.9, R = 0.75, η = 0.25)
0.00
0.00
0.00
Problem 111–120 (μ = 0.9, R = 0.75, η = 0.75)
0.00
0.00
0.00
Average improvement rates
0.54
0.10
0.00
condition of 100 s was able to find optimal solutions for 112 out of 120 instances (93.3%), whereas IPBVND/1500 found optimal solutions for 119 out of 120 instances (99.2%). Furthermore, the results with the ARP criterion are summarized in Table 11, which shows that IPBVND/1500 dominated IPBVND/25 by 100% ((0.54−0.00)/0.54), and dominated IPBVND/100 by 100% ((0.10 − 0.00)/0.10), and IPBVND/100 dominated IPBVND/25 by 81% ((0.54 − 0.10)/0.54). The ARP results in Table 11 strongly support the assertion that the IPBVND algorithms are effective. Finally, we applied IPBVND to solve the single machine with sequence-dependent setup time problem of minimizing the total unweighted tardiness of jobs. Using a three-field notation, α/β/γ , the problem can be defined as 1/si j / T j . Two well-known benchmark sets of 1/si j / T j problem instances were used to evaluate the performance of IPBVND (Rubin and Ragatz 1995; Gagne et al. 2002). The first set includes 32 small- and medium-sized instances with 15, 25, 35, and 45 jobs (Rubin and Ragatz 1995), and the second set includes 32 large-sized instances with 55, 65, 75 and 85 jobs (Gagne et al. 2002). For each job size, there are eight instances derived by means of three-factor experimental design, and the factors that can be examined are the processing time variance, tardiness, and due-date range. A number of metaheuristics have been proposed to solve the scheduling problem, such as IG (Ying et al. 2009), GVNS (Kirlik and Oguz 2012), and HEA (Xu et al. 2014). We observed that HEA is superior to the other metaheuristics in terms of ARP. The HEA requires at most 100 s to find the best solution. Therefore, the IPBVND algorithm was applied to solve all 64 test instances for 100 trials, and spent 100 s on each problem. The results for the 32 small- and medium-sized instances are present in Table 12, and those for the 32 large-sized
123
instances are given in Table 13. Table 12 indicates that IPBVND found all optimal solutions for the small- and medium-sized instances, and Table 13 shows that IPBVND found optimal solutions for 27 of the 32 large-sized instances. Furthermore, we can see that HEA also found all smalland medium-sized instances. Compared with HEA, IPBVND produced three better solutions and one worse solution for the 32 large-sized instances. From Table 13, we observe that our IPBVND algorithm could not obtain the optimal or best solutions from the following five instances: prob655, prob751, prob851, prob854, and prob855. Therefore, in order to verify if IPBVND is able to repeat or even improve the optimal or the best results of the five difficult instances, we rerun IPBVND under a relaxed time limit to tackle these five instances. Three IPBVND algorithms with termination conditions of 20,000, 40,000, and 80,000 s were constructed to solve the five instances for 10 trials. Table 14 shows the results of the IPBVND algorithm and CPU times reach the best or optimal solutions compared with the exact algorithm by Tanaka and Araki (2013) and the HEA algorithm presented by Xu et al. (2014). In Table 14, column3 presents the optimal solutions of the exact algorithm. Columns 4, 5, and 6 give the total CPU times to find the optimal solutions in three settings of the maximum memory sizes (i.e., 512 M, 2, and 20 GB respectively). Column 7 gives the best solutions obtained by HEA algorithm and column 8 presents the total CPU time of the HEA algorithm for the best solutions. Columns 9, 10, and 11 present the best solutions of IPBVND algorithms with three termination conditions (i.e., 20,000, 40,000, and 80,000 s respectively). The results in Table 14 show that even for the exact algorithm, especially these two instances prob655 and prob854, the optimal solutions are achieved for over 30 days. The HEA
Iterated population-based VND algorithms for single-machine scheduling with… Table 12 Results of OPT, IG, GVNS,HEA, and IPBVND for smalland medium-sized instances of1/si j / T j problem
Table 13 Results of OPT, IG, GVNS, HEA, and IPBVND for largesized instances of1/si j / T j problem
Ins.
Job size
OPT
IG
GVNS
HEA
IPBVND
Ins.
Job size
OPT
IG
GVNS
HEA
IPBVND
Prob401
15
90
90
90
90
90
Prob551
55
183
183
194
183
183
Prob402
15
0
0
0
0
0
Prob552
55
0
0
0
0
0
Prob403
15
3418
3418
3418
3418
3418
Prob553
55
40498
40598
40540
40498
40498
Prob404
15
1067
1067
1067
1067
1067
Prob554
55
14653
14653
14653
14653
14653
Prob405
15
0
0
0
0
0
Prob555
55
0
0
0
0
0
Prob406
15
0
0
0
0
0
Prob556
55
0
0
0
0
0
Prob407
15
1861
1861
1861
1861
1861
Prob557
55
35813
35827
35830
35813
35813
Prob408
15
5660
5660
5660
5660
5660
Prob558
55
19871
19871
19871
19871
19871
Prob501
25
261
261
261
261
261
Prob651
65
247
268
264
247
247
Prob502
25
0
0
0
0
0
Prob652
65
0
0
0
0
0
Prob503
25
3497
3497
3497
3497
3497
Prob653
65
57500
57584
57515
57500
57500
Prob504
25
0
0
0
0
0
Prob654
65
34301
34306
34301
34301
34301
Prob505
25
0
0
0
0
0
Prob655
65
0
2
4
2
1
Prob506
25
0
0
0
0
0
Prob656
65
0
0
0
0
0
Prob507
25
7225
7225
7225
7225
7225
Prob657
65
54895
55080
54895
54895
54895
Prob508
25
1915
1915
1915
1915
1915
Prob658
65
27114
27114
27114
27114
27114
Prob601
35
12
12
12
12
12
Prob751
75
225
999
241
229
231
Prob602
35
0
0
0
0
0
Prob752
75
0
0
0
0
0
Prob603
35
17587
17587
17587
17587
17587
Prob753
75
77544
77663
77627
77544
77544
Prob604
35
19092
19092
19092
19092
19092
Prob754
75
35200
35250
35219
35200
35200
Prob605
35
228
228
228
228
228
Prob755
75
0
0
0
0
0
Prob606
35
0
0
0
0
0
Prob756
75
0
0
0
0
0
Prob607
35
12969
12969
12969
12969
12969
Prob757
75
59635
59763
59716
59635
59635
Prob608
35
4732
4732
4732
4732
4732
Prob758
75
38339
38341
38339
38339
38339
Prob701
45
97
103
99
97
97
Prob851
85
360
390
402
381
375
Prob702
45
0
0
0
0
0
Prob852
85
0
0
0
0
0
Prob703
45
26506
26496a
26506
26506
26506
Prob853
85
97497
97880
97595
97497
97497
Prob704
45
15206
15206
15206
15206
15206
Prob854
85
79042
79631
79271
79086
79086
Prob705
45
200
200
200
200
200
Prob855
85
256
283
280
270
266
Prob706
45
0
0
0
0
0
Prob856
85
0
0
0
0
0
Prob707
45
23789
23794
23789
23789
23789
Prob857
85
87011
87244
87075
87011
87011
Prob708
45
22807
22829
22807
22807
22807
Prob858
85
74739
75029
74755
74739
74739
Bold represents optimal solution a Incorrect solution
can find the new best known solution, “256”, for instance prob855 under 6037.93 seconds. Furthermore, IPBVND with termination conditions of 20,000 and 40,000 s were able to find the best or optimal solutions for the 3 out of the five challenging instances, whereas IPBVND with termination conditions of 80,000 s could find all the best or optimal solutions for the five challenging instances except prob855.
5 Conclusion This paper has proposed an iterated population-based variable neighborhood descent search algorithm to solve the
Bold represents optimal solution, italic represents best solution
single-machine scheduling with sequence-dependent setup times problem while minimizing the total weighted tardiness of jobs. Several methods were incorporated in our IPBVND algorithm: a multiple-phase member updated method was constructed to update the solution for the IPBVND at each iteration, and a variable sequence of block-based insertion neighborhood structures was used to help the VND achieve better performance. The IPBVND algorithm achieved optimal results with a five-phase member updated method (phase 1: ( pg1 = 0.1, ps1 = 0.81, pr1 = 0.09); phase 2: ( pg2 = 0.2, ps2 = 0.72, pr2 = 0.08); phase 3: ( pg3 = 0.3, ps3 = 0.63, pr3 = 0.07); phase 4: ( pg4 = 0.4, ps4 = 0.54, pr4 = 0.06); and phase 5: ( pg5 = 0.5, ps5 = 0.45, pr5 = 0.05)) and a variable sequence of eight insertion neighborhood struc-
123
C. Chen Table 14 Results of exact algorithm, HEA, and IPBVND for the five challenging instances of1/si j / Ins.
Job size
Tanaka and Araki’s exact algorithm Solutions
T j problem
HEA
Time (second) 512 M
2 GB
20 GB
IPBVND
Solutions
Time (second)
20,000 s
40,000 s
80,000 s
Prob655
55
0
649.37
1032.64
2596.73
0
1006.26
0
0
0
Prob751
75
225
–
–
34 days
225
33,648.64
225
225
225
Prob851
85
360
–
–
> 30 days
360
84,405.88
369
366
360
Prob854
85
79,042
2499.42
2451.33
2198.15
79,042
180.06
79,042
79,042
79,042
Prob855
85
258
–
–
> 30 days
256
6037.93
258
258
258
Bold represents optimal solution, italic represents best solution
tures (V(INS1 (1) + INS2 (2) + … + INS8 (8))). Computational experiments on 120 benchmark instances were conducted to compare the results produced by the proposed IPBVND algorithm against several state-of-the-art heuristics. The results show that the proposed IPBVND/25 is superior to the DPSO, DDE, and GVNS heuristics, and found the optimal solution for 95 out of 120 instances. Furthermore, the termination conditions for IPBVND were examined to verify its effectiveness under longer computation times. IPBVND/100 found 112 out of 120 instances, and the ARP decreased to 0.10. The results confirm that IPBVND is a very effective algorithm. In addition, we applied IPBVND to solve the 64 instances of the 1/si j / T j problem. Our algorithm was able to reach the optimal or best known solution for 59 of the 64 instances within a reasonable time and could find all optimal solutions for the 64 instances within a relaxed time limit. The idea of the initial population solutions can be further studied to improve the performance of IPBVND. Although this multiple-phase member updated method is effective, it can be optimized with methods that adjust the learning parameters (c1 and c2 ) based on the conditions in each iteration. This self-adaptive learning strategy may be the future direction for the research of IPBVND. Acknowledgements This paper was supported in part by the Ministry of Science and Technology, Taiwan, ROC, under the contract NSC 1012221-E-147 -001. The authors are grateful to the anonymous referees for their constructive comments that have greatly improved the presentation of this paper.
Compliance with ethical standards Conflict of interest The authors declare that they have no conflict of interests. Human participants or animals This article does not contain any studies with human participants or animals performed by any of the authors.
References Ahmadizar F, Hosseini L (2011) A novel ant colony algorithm for the single-machine total weighted tardiness problem with sequence dependent setup times. Int J Comput Intell Syst 4:456–466
123
Akrout H, Jarboui B, Siarry P, Rebai A (2012) A GRASP based on DE to solve single machine scheduling problem with SDST. Comput Optim Appl 51:411–435 Al-Turki U, Fedjki C, Andijani A (2001) Tabu search for a class of single-machine scheduling problems. Comput Oper Res 28:1223– 1230 Anghinolfi D, Paolucci M (2008) A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem. Int J Oper Res 5:44–60 Anghinolfi D, Paolucci M (2009) A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times. Eur J Oper Res 193:73–85 Chen CL, Chen CL (2009) Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times. Int J Adv Manuf Tech 43:161–169 Chen CL (2013) Iterated variable neighborhood search algorithm for solving total weighted tardiness problems of single machine scheduling with sequence-dependent setup times. J Am Bus Rev 2:145–152 Chung TP, Fu Q, Liao CJ, Liu YT (2016) Multiple-variable neighbourhood search for the single-machine total weighted tardiness problem. Eng Optimiz 1–15 Cicirello VA, Smith SF (2005) Enhancing stochastic search performance by value-based randomization of heuristics. J Heuristics 11:5–34 Fu Q, Chung TP (2016) A new approach for solving single machine total weighted tardiness (SMTWT) problem. In: IEEE International conference on industrial engineering and engineering management (IEEM), 2016, pp 438–441 Gagne C, Price WL, Gravel M (2002) Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. J Oper Res Soc 53:895–906 Gao J, Sun L, Gen M (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Oper Res 35:2892–2907 Gonzalez MA, Vela CR (2015) An efficient memetic algorithm for total weighted tardiness minimization in a single machine with setups. Appl Soft Comput 37:506–518 Guo Q, Tang L (2015) An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. Appl Soft Comput 29:184–195 Hansen P, Mladenovi´c N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130:449–467 Kirlik G, Oguz C (2012) A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine. Comput Oper Res 39:1506–1520 Lawler EL (1977) A ‘pseudo polynomial’ algorithm for sequencing jobs to minimize tardiness. Ann Discrete Math 1:331–342
Iterated population-based VND algorithms for single-machine scheduling with… Lee YH, Bhaskaran K, Pinedo M (1997) A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Trans 29:45–52 Liao CJ, Juan HC (2007) An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Comput Oper Res 34:1899–1909 Lin SW, Ying KC (2007) Solving single-machine total weighted tardiness problems with sequence-dependent setup times by metaheuristics. Int J Adv Manu Tech 34:1183–1190 Lin SW, Ying KC (2008) A hybrid approach for single-machine tardiness problems with sequence-dependent setup times. J Oper Res Soc 59:1109–1119 Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097–1100 Pinedo M (2002) Scheduling theory, algorithms, and systems, 2nd edn. Prentice-Hall, Englewood Cliffs Rubin PA, Ragatz GL (1995) Scheduling in a sequence dependent setup environment with genetic search. Comput Oper Res 22:85–99 Ruiz R, Stutzle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033–2049 Subramanian A, Battarra M, Potts CN (2014) An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. Int J Prod Res 52:2729–2742 Tanaka S, Araki M (2013) An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Comput Oper Res 40:344–352
Tasgetiren MF, Pan QK, Liang YC (2009) A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Comput Oper Res 36:1900–1915 Tasgetiren MF, Sevkli M, Liang YC, Gencyilmaz G (2004) Particle swarm optimization algorithm for single machine total weighted tardiness problem. In: IEEE congress on evolutionary computation, 2004, pp 1412–1419 Tasgetiren MF, Pan QK, Ozturkoglu Y, Chen AH (2016) A memetic algorithm with a variable block insertion heuristic for single machine total weighted tardiness problem with sequence dependent setup times. In: IEEE congress on evolutionary computation, 2016, pp 2911–2918 Valente JMS, Alves RAFS (2008) Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence dependent setups. Comput Oper Res 35:2388–2405 Xu H, Lu Z, Cheng TCE (2014) Iterated Local Search for singlemachine scheduling with sequence-dependent setup times to minimize total weighted tardiness. J Sched 17:271–281 Xu H, Lu Z, Yin A, Shen L, Buscher U (2014) A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times. Comput Oper Res 50:47– 60 Ying KC, Lin SW, Huang CY (2009) Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Syst Appl 36:7087–7092
123
