Heuristic Algorithm for the Parallel Machine Total Weighted

Heuristic Algorithm for the Parallel Machine Total Weighted
Tardiness Scheduling Problem
Rosiane Rodrigues
[email protected]
COPPE - Engenharia de Sistemas e Computação
Universidade Federal do Rio de Janeiro
Departamento de Ciência da Computação
Universidade Federal do Amazonas
Artur Pessoa, Eduardo Uchoa
{artur, uchoa}@producao.uff.br
Departamento de Engenharia de Produção
Universidade Federal Fluminense
Marcus Poggi de Aragão
[email protected]
Departamento de Informática
Pontifı́cia Universidade Católica do Rio de Janeiro
Abstract
This paper presents P
a heuristic algorithm for the parallel machine weighted tardiness
scheduling problem (P || wj Tj ). The main innovative feature of the algorithm is its representation of a multi-machine schedule by a single sequence, greatly simplifying the treatment
of that problem. The single sequence is optimized using an iterated local search over generalized pairwise interchange moves, improved with a suitable tie breaking criterion. Extensive
tests on instances, with 2 and 4 machines, and with up to 50 jobs, obtained very good results,
finding optimal solutions in almost all cases.
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
1
1
Introduction
Let J = {1, . . . , n} be a set of jobs to be processed in a set of parallel identical machines
M = {1, . . . , m} without preemption. Each machine can process at most one job at a time
and each job must be processed by a single machine. Each job j has a positive processing
time pj , a due date dj , and a positive weight wj . The tardiness of a job j with respect to
its due date is defined as Tj = max{0, Cj − dj }, where Cj is the job completion time. The
scheduling problem considered
in this paper consists in sequencing
P
P the jobs in the machines
in order to minimize nj=1 wj Tj . This problem, referred as P || wj Tj in the
P3-field notation
[10], is strongly NP-hard, since even the single-machine case (referred as 1|| wj Tj ) hasPthat
complexity [12]. On the other hand, the single-machine problem without weights (1|| Tj )
is NP-hard in the ordinary sense [7], but can solved in pseudo-polynomial time [12]. All those
problems may play an important role in real applications, such as in the manufacturing
industry.
P
We are not aware of other heuristic algorithms specially devised for the P || wj Tj . Recent
works on related problems include Anghinolfi and Paolucci (2007) [2], that proposes a hybrid
metaheuristic
mixing Tabu Search, Simulated Annealing and Variable NeigborhoodP
Search for
P
the P || Tj ; and Bilge et al. (2004) [4], that proposes a Tabu Search for the P |sij | Tj (considering sequence dependent setup times).
P
On the other hand, there is a rich literature on heuristics for the 1|| wj Tj . The most
competitive heuristics for that problem are based on local searches that use both insertion
moves (remove a job from the sequence and reinsert it in another position) and swap moves
(swap the positions of a pair of jobs in the sequence). Those combined
moves are also known
P
as generalized pairwise interchange (GPI) moves [6]. Some 1|| wj Tj heuristics use the GPI
moves in a traditional way, making one move at a time [20]. However, better results are obtained
using dynamic programming to explore a large neighborhood that consists in certain sequences
of single moves, the so-called dynasearch technique. While the size of the neighborhood is
potentially exponential, the dynamic programming may determine such an optimal sequence of
moves in polynomial time. This technique was introduced by Potts and Val de Verde [17] in
the Traveling Salesman Problem
P (see the survey by Ahuja et al. [1]). Congram et al. [5] first
applied dynasearch to the 1|| wj Tj , but only considering swaps as single moves. Grosso et al.
[11] adapted the dynasearch technique in order to consider all GPI moves. Both papers present
dynamic programming procedures with O(n3 ) time complexity per search. Recently, Ergun and
Orlin [9] improved this time complexity to O(n2 ), by giving a faster dynasearch that combines
GPI moves and also twist moves.
P
Our heuristic algorithm for the P || wj Tj features the representation of a multi-machine
schedule by a single sequence, that can be improved by a local search using the well-known
GPI moves. Unfortunately, the single sequence representation does not appear to be suitable to
dynasearch. This happens because this indirect representation makes the evaluation of moves to
be much more costly, even a single insertion move may change the completion times of most jobs
in a complex way, so the tardiness costs may have to be recomputed from scratch in O(n log m)
time. Evaluating the tardiness costs of many sequences of moves is prohibitively expensive. In
order to partially remedy the lack of a dynasearch, we introduce a tie breaking criterion in the
GPI search. The idea is that even when the current solution has no GPI neighbor with better
tardiness cost, the search is not stopped if there are neighbor solutions improving this criterion.
The criterion was devised with the hope of guiding the search into solutions that more likely to
be further improved.
P
Several exact methods were proposed for the 1|| wj Tj , including [8, 19, 22, 21, 3, 14, 15].
The last three works describe techniques that can solve instances with up to 100 jobs consistently.
However, the best heuristics typically find the optimal solutions for those instances in much less
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
2
time. By the way, those heuristics are often embedded as part of those branch-and-bound based
exact algorithms. A good heuristic solution can
P reduce the search tree, leading to significant
speedups. The only exact algorithm for the P || wj Tj that we know is proposed in [15]. It can
solve most instances with up to 50 jobs. The heuristic presented in this paper was created in
order to embedded in that exact algorithm.
2
The Algorithm
P
A scheduling for the P || wj Tj is defined as a sequence of jobs on each machine, where each
job appears in exactly one sequence. It is assumed that a machine is only idle after all jobs in
its sequence are processed. Moreover, we say that a scheduling is minimal if no machine is idle
before all jobs have started their processing. Of course, there is at least one optimal scheduling
that is minimal.
P
The main idea of our heuristic algorithm is to represent a minimal P || wj Tj scheduling as
a single sequence of jobs. Let π = (π1 , . . . , πn ) be a permutation of the job indices 1, . . . , n. A
minimal scheduling can be obtained from π as follows. Start with an empty schedule S, where
all machines are idle at time 0. Then, for i = 1, . . . , n, schedule the job Jπi in the first machine
that becomes idle according to S. When ties occur, choose the machine with the smallest index.
Denote the obtained schedule and its cost by Sπ and w(π), respectively. Note that every minimal
schedule S can be generated in this way. To see this, construct π so that the sequence of jobs
(Jπ1 , . . . , Jπn ) is in a non-decreasing order their starting times according to S. When ties occur,
put the jobs scheduled in machines with smaller indices first. It is easy to see that Sπ = S.
Given an initial permutation π of jobs, our algorithm performs a local search over a neighborhood defined by GPI moves. They are defined as either an exchange of two (not necessarily
adjacent) jobs in π or the removal of a job from π followed by its insertion in another position.
Each local search is performed until no GPI move improves the current solution.
During the local search, a move is accepted only when the new solution improves upon the
previous one. However, locally optimal solutions often have many neighbor solutions with the
same cost. Hence, a premature stop in such local optima may be avoided using a suitable tie
breaking criterion. Our criterion is based on the values of the due dates and the reverse position
of the job in the sequence. In a formal way, given a sequence π = (π1 , . . . , πn ), we define
n
P
b(π) =
dπj × (n − j + 1). Thus, given two neighbor sequences of jobs π and ρ with the same
j=1
cost, if b(ρ) < b(π), then ρ is considered to improve over π. Note that our criterion induces the
jobs having earlier due dates to be scheduled before the ones with later due dates. This criterion
is motivated by the well-known
P Earliest Due Date first (EDD) rule [13, 16], which generates an
optimal solution for the 1|| wj Tj when the optimum value is zero (i.e., when there is a solution
without tardy jobs).
Algorithm 1 below presents the general steps of our heuristic, where N, r and k are parameters.
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
Algorithm 1 Single sequence based heuristic for the P ||
P
3
wj Tj
• i ← 1; π ∗ ← a permutation following the EDD rule.
• While i ≤ N
– If i is a multiple of r, then π ← a random permutation.
– Apply GPI moves in π, until no improvement is possible.
– If w(π) < w(π ∗ ), then π ∗ ← π.
– Apply k randomly chosen 2-change moves in π.
– i ← i + 1.
First, it generates a feasible solution following the EDD rule and store in π ∗ . In the first iteration, it generates a random permutation π, where the probabilities are identically distributed
among all permutations. Then, GPI moves are applied to π. The search on the GPI neighborhood of the current π is stopped when the first improvement move is found, in this case π is
updated and a new search starts. This is done until a search is completed without improvement
(considering the tie breaking criterion). If the obtained solution improves upon the best solution
found so far, then it is kept as π ∗ . Finally, k randomly chosen GPI moves are applied (regardless
of whether they generate improvements or not), in an attempt to escape from bad local optimal
regions. On every r iterations, a completely random permutation replaces the solution generated
in the previous iteration.
A complete search on the GPI neighborhood tests O(n2 ) moves. The evaluation of each
move requires the construction of the corresponding scheduling, this takes O(n log m) time.
3
Computational Experiments
In all our experiments, we set N = 30mn, r = 5, and k = 3. The reported times were
obtained with a Intel Xeon 2.33 GHz processor.
3.1
Single-Machine
P
P
Even though our algorithm was devised for the P || wj Tj , we also tested it on 1|| wj Tj
instances in order to benchmark it against other methods from the literature. The experiments were performed on the set of 375 instances of the problem available at the OR-Library.
This set was generated by Potts and Wassenhove [18] and contains 125 instances for each
n ∈ {40, 50, 100}. In fact, for each such n, they created 5 similar instances (changing the
seed) for each of 25 parameter configurations of the random instance generator. Therefore, for
each value of n there are 25 groups composed by 5 similar instances. Those parameter configurations have influence on the distribution of the due dates. Processing times and weights are
always picked from the discrete uniform distribution on [1,100] and [1,10], respectively.
The best known results for those instances were obtained by Grosso et al. [11] using the
GPI-based Dynasearch algorithm (GPI-DS). In that paper, a comparative analysis was done
between this method and an older method called Ant-Colony Optimization (ACO), proposed
by Stützle et al. [20], that uses the GPI moves in an ACO framework. Table 1 contains a
comparison among our algorithm and the two methods above mentioned. The comparison is
done on the time (average and maximum) needed to find the optimal value. The CPU times of
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
4
GPI-DS were obtained in a HP Kayak 800 MHz workstation, while ACO was run on a Pentium
III 450 MHz.
Table 1: CPU time to find an optimal solution, GPI-DS [11], ACO [20], and our algorithm, on ORLibrary instances with 40, 50 and 100 jobs (125 instances of each size).
40
50
100
GPI-DS
ACO
Our method
GPI-DS
ACO
Our method
GPI-DS
ACO
Our method
Topt,avg
0.003
0.088
0.012
0.010
0.320
0.084
0.107
6.990
1.104
Topt,max
0.125
1.720
0.870
0.562
10.740
5.760
3.907
86.260
29.180
Although our heuristic (as GPI-DS and ACO) eventually obtains the optimal solutions for all
OR-Library instances, our CPU times are significantly higher than those by GPI-DS. However,
even taking taking the difference of the processors into account, the performance of our heuristic
is similar to ACO. This is quite remarkable, because when m = 1 our method reduces to a naive
implementation of an iterated GPI local search. The factor that may explain why such a simple
method matches the performance of a sophisticated metaheuristic using the same neighborhood
is the improvement obtained by the tie-breaking criterion. In fact, without that criterion our
method would fail to find the optimal solutions for 2 instances with 100 jobs, even after 3000
iterations and 160 seconds of CPU time. On the instances with 100 jobs, the average quality
of the solutions found after each GPI local search iteration is 0.67% above the optimal, without
the tie-breaking criteria this number would be 1.26% above the optimal.
3.2
Multi-Machines
P
In order to perform experiments
on
the
P
||
wj Tj problem, we derived 100 new instances
P
from the previously mentioned 1|| wj Tj OR-Library instances. For m ∈ {2, 4}, n ∈ {40, 50},
we pick the first instance in each group (those with numbers ending with the digit 1 or 6) and
divided each due date dj by m (and rounded down the result), processing times pj and weights
wj are kept unchanged. For example, from instance wt40-1, we produced instances wt40-2m-1
and wt40-4m-1 by dividing due dates by 2 and 4, respectively. The exact algorithm presented
in [15] solved to optimality 98 out of those 100 instances, so we have a good basis to assess the
performance of our heuristic.
Tables 2 to 5 present detailed results of our heuristic algorithm. The columns have the
following meaning: (1) the instance number; (2) the optimal solution value; (3) the value of
the best solution found by the heuristic; (4) the difference between the previous values; (5) the
iteration in which the best value was first found; (6) the elapsed CPU time (in seconds) when
the best value was first found; (7) the number of iterations where the best value was found; (8)
the average value of the solutions obtained in all iterations; (9) the total number of iterations
performed (given by the algorithm parameter N ); and, (10) the total CPU time (in seconds).
Table 2 and Table 3 present detailed results considering 2 machines, for 40 and 50 jobs,
respectively. Only for a single instance (wt40-2m-116), the optimal solution (or the best known
solution, in case of instance wt50-2m-31) was not found. Table 4 and Table 5 present detailed
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
5
results considering 4 machines, for 40 and 50 jobs, respectively. Optimal solutions (or the best
known solution, in case of instance wt50-4m-56) were found for all tested instances.
We also run all instances with a simpler variant of our method, without the tie-breaking
criterion. Table 6 compares statistics on those runs with statistics on the runs using the complete
method, with the tie-breaking criterion. For each value of m and n, it shows: (1) the number of
instances where the optimal or best known solution value was not found; (2) the average quality
of the solutions found after each GPI local search iteration; and (3) the total time to complete all
the N iterations. It can be seen that the tie-breaking criterion makes the algorithm significantly
more robust, with a modest increase on the time spent per iteration (28% in average).
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
Inst
1
6
11
16
21
26
31
36
41
46
51
56
61
66
71
76
81
86
91
96
101
106
111
116
121
Avg :
Opt
606
3886
9617
38356
41048
87
3812
10713
30802
34146
0
1279
11488
35279
47952
0
571
6048
26075
66116
0
0
17936
25870
64516
BestV
606
3886
9617
38356
41048
87
3812
10713
30802
34146
0
1279
11488
35279
47952
0
571
6048
26075
66116
0
0
17936
25874
64516
∆
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
IterBest
1
1
1
2
1
1
4
1
2
4
1
7
2
32
2
1
972
3
6
37
1
1
7
25
32
TBest(s)
0.00
0.00
0.00
0.01
0.00
0.01
0.02
0.00
0.00
0.01
0.00
0.04
0.01
0.14
0.00
0.00
6.29
0.01
0.02
0.16
0.00
0.00
0.04
0.12
0.14
0.28
#Best
2009
1903
1531
265
394
1912
189
580
616
1173
2400
872
168
149
395
2400
1
20
520
110
2400
2400
228
20
122
AvgV
610.3
3888.3
9640.9
38405.2
41053.8
93.7
3842.6
10729.3
30837.8
34148.8
0.0
1294.2
11534.8
35313.6
47962.6
0.0
620.9
6084.2
26115.4
66137.8
0.0
0.0
17969.0
25934.5
64556.8
TotIter
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
2400
Table 2: Results on instances with 40 jobs and 2 machines.
TotT(s)
13.89
14.76
13.94
12.17
9.77
13.52
13.66
13.36
11.39
9.72
7.64
13.78
12.41
10.82
9.77
7.16
15.58
13.82
11.29
9.77
6.79
6.96
12.00
11.53
10.43
11.44
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
6
Inst
1
6
11
16
21
26
31
36
41
46
51
56
61
66
71
76
81
86
91
96
101
106
111
116
121
Avg :
Opt
1268
14272
23028
46072
111069
26
≤5378
18956
38058
82105
0
761
13682
40907
78532
0
542
12557
47349
92822
0
0
15564
19608
41696
BestV
1268
14272
23028
46072
111069
26
5378
18956
38058
82105
0
761
13682
40907
78532
0
542
12557
47349
92822
0
0
15564
19608
41696
∆
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
IterBest
10
2
3
1
23
6
1
14
6
37
1
108
490
3
9
1
64
86
115
4
1
1
4
604
1
TBest(s)
0.10
0.02
0.03
0.01
0.17
0.06
0.01
0.16
0.06
0.26
0.00
1.24
6.00
0.03
0.07
0.00
0.68
0.98
1.13
0.03
0.00
0.01
0.05
6.76
0.01
0.71
#Best
1453
885
379
751
119
631
2796
167
303
149
3000
37
15
653
192
3000
58
75
17
34
3000
3000
171
5
901
AvgV
1281.9
14344.3
23085.4
46100.2
111082.2
29.2
5387.6
19086.9
38182.0
82125.3
0.0
765.4
13902.3
40964.0
78580.6
0.00
680.8
12674.8
47443.6
92882.3
0.0
0.0
15729.3
19681.9
41733.1
TotIter
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
3000
Table 3: Results on instances with 50 jobs and 2 machines.
TotT(s)
33.87
31.01
34.06
29.55
21.77
29.86
36.33
34.22
24.77
21.08
17.06
34.87
36.45
29.32
24.05
16.60
32.60
33.43
28.16
25.38
16.78
16.67
37.34
33.29
30.12
28.35
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
7
Inst
1
6
11
16
21
26
31
36
41
46
51
56
61
66
71
76
81
86
91
96
101
106
111
116
121
Avg :
Opt
439
2374
5737
21493
22793
88
2525
6420
17685
19124
0
826
7357
20251
26740
0
564
4725
15569
36266
0
0
11263
15566
35751
BestV
439
2374
5737
21493
22793
88
2525
6420
17685
19124
0
826
7357
20251
26740
0
564
4725
15569
36266
0
0
11263
15566
35751
∆
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
IterBest
1
1
1
1
1
2
59
2978
46
17
2
7
34
24
6
1
2204
146
216
22
1
1
26
559
4
TBest(s)
0.01
0.01
0.01
0.01
0.00
0.02
0.62
24.52
0.32
0.10
0.02
0.07
0.28
0.15
0.04
0.00
21.97
1.20
1.63
0.13
0.00
0.00
0.20
4.27
0.02
2.22
#Best
2189
1213
912
370
2367
2224
107
1
63
171
1918
320
142
313
684
4800
1
44
19
115
4800
4764
39
8
278
AvgV
456.3
2420.9
5769.1
21512.6
22797.6
115.0
2556.9
6479.6
17794.5
19128.3
32.8
873.9
7409.5
20295.9
26747.8
0.0
743.1
4824.8
15634.2
36280.7
0.0
0.1
11316.8
15652.6
35774.6
TotIter
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
4800
Table 4: Results on instances with 40 jobs and 4 machines.
TotT(s)
52.36
49.21
47.29
33.55
34.27
53.41
47.20
39.36
33.10
29.38
48.04
53.17
39.52
32.20
31.29
21.70
47.71
39.28
35.92
30.12
21.48
31.41
35.82
36.59
32.58
38.24
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
8
Inst
1
6
11
16
21
26
31
36
41
46
51
56
61
66
71
76
81
86
91
96
101
106
111
116
121
Avg :
Opt
785
8317
12879
25376
59440
54
3061
10796
21806
44455
0
≤570
7898
23138
42645
0
495
8369
26551
50326
0
0
10069
11552
23792
BestV
785
8317
12879
25376
59440
54
3061
10796
21806
44455
0
570
7898
23138
42645
0
495
8369
26551
50326
0
0
10069
11552
23792
∆
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
IterBest
18
15
612
3
55
3
5
246
8
13
1
63
4433
27
118
1
14
24
1520
12
1
1
3636
23
1357
TBest(s)
0.47
0.36
11.19
0.04
0.68
0.08
0.10
4.32
0.10
0.17
0.01
1.51
81.60
0.39
1.54
0.01
0.26
0.37
22.38
0.17
0.00
0.01
65.70
0.43
19.63
8.46
#Best
695
218
31
446
71
5323
840
9
631
406
6000
261
1
198
78
6000
102
6000
1
122
6000
6000
2
6
9
AvgV
805.9
8387.0
12926.6
25416.9
59451.9
58.3
3192.1
10929.4
21869.3
44469.7
0.0
584.4
8054.0
23174.7
42684.4
0.0
746.7
8493.4
26638.3
50373.7
0.0
0.0
10164.1
11619.7
23839.9
TotIter
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
6000
Table 5: Results on instances with 50 jobs and 4 machines.
TotT(s)
142.83
125.92
111.11
90.08
75.17
152.87
132.67
104.70
85.28
74.21
59.88
143.81
110.65
82.59
74.88
50.93
124.06
100.20
88.33
81.76
52.10
63.38
108.65
100.93
86.45
96.94
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
9
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
m
2
2
4
4
n
40
50
40
50
10
Table 6: Effect of the tie-breaking criterion on the proposed algorithm
Without tie-breaking
With tie-breaking
#N onOpt AvgQ(%) AvgTotT(s) #N onOpt AvgQ(%) AvgTotT(s)
1
2.49
9.18
1
0.87
11.44
0
3.32
22.40
0
1.83
28.35
1
5.77
29.83
0
3.29
38.24
1
4.30
73.50
0
3.08
96.94
References
[1] R. Ahuja, O. Ergun, J. Orlin, and A. Punnen. A survey of very-large scale neighborhood
search techniques. Discrete Applied Mathematics, 123:75–103, 2002.
[2] D. Anghinolfi and M. Paolucci. Parallel machine total tardiness scheduling with a new
hybrid metaheuristic approach. Computers and Operations Research, 34:3471–3490, 2007.
[3] L. Bigras, M. Gamache, and G. Savard. Time-indexed formulations and the total weighted
tardiness problem. INFORMS Journal on Computing, 1:133–142, 2008.
[4] U. Bilge, F. Kyraç, F. Kurtulan, and M. Pekgun. A tabu search algorithm for parallel
machine total tardiness problem. Computers and Operations Research, 31:397–414, 2004.
[5] R. Congram, C. Potts, and S. van de Velde. An iterated dynasearch algorithm for the single
machine total weighted tardiness scheduling problem. INFORMS Journal of Computing,
14:52–67, 2002.
[6] F. Della Croce. Generalized pairwise interchanges and machine scheduling. European Journal of Operational Research, 83:310–319, 1995.
[7] J. Du and J. Leung. Minimizing total tardiness on one processor is NP-Hard. Mathematics
of Operations Research, 15(3):483–495, 1990.
[8] M. Dyer and L. Wolsey. Formulating the single machine sequencing problem with release
dates as a mixed integer program. Discrete Applied Mathematics, 26:255–270, 1990.
[9] O. Ergun and J. Orlin. Fast neighborhood search for the single machine total weighted
tardiness problem. Operations Research Letters, 34:41–45, 2006.
[10] R. Graham, E. Lawler, J. Lenstra, and A. Rinnooy-Kan. Optimization and approximation
in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics,
5:287–326, 1979.
[11] A. Grosso, F. Della Croce, and R. Tadei. An enhanced dynasearch neighborhood for the
single-machine total weighted tardiness scheduling problem. Operations Research Letters,
32:68–72, 2004.
[12] E. Lawler. A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness.
Annals of Research Letters, 1:207–208, 1977.
[13] J. Leung. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman&Hall and CRS Press, 2004.
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008
Relatórios de Pesquisa em Engenharia de Produção V. 8 n. 10
11
[14] Y. Pan and L. Shi. On the equivalence of the max-min transportation lower bound and the
time-indexed lower bound for single machine scheduling problems. Mathematical Programming, 110:543–559, 2007.
[15] A. Pessoa, E. Uchoa, M. Poggi de Aragão, and R. Rodrigues. Algorithms over arc-time
indexed formulations for single and parallel machine scheduling problems. Technical Report
RPEP Vol.8 no.8, Universidade Federal Fluminense, Engenharia de Produção, Niterói,
Brazil, 2008.
[16] M. Pinedo. Scheduling: theory, algorithms, and systems. Prentice-Hall, 2002.
[17] C. Potts and S. van de Velde. Dynasearch - iterative local improvement by dynamic programming. Part I: the traveling salesman problem. Technical report, University of Twente,
1995.
[18] C. Potts and L. Wassenhove. A branch-and-bound algorithm for the total weighted tardiness
problem. Operations Research, 32:363–377, 1985.
[19] J. Sousa and L. Wolsey. A time indexed formulation of non-preemptive single machine
scheduling problems. Mathematical Programming, 54:353–367, 1990.
[20] T. Stützle, M. Den Besten, and M. Dorigo. Ant colony optimization for the total weighted
tardiness problem. Technical report, Technical Report IRIDIA/99-16, 1999.
[21] J. Van der Akker, C. Hurkens, and M. Savelsbergh. Time-indexed formulations for machine
scheduling problems:column generation. INFORMS Journal on Computing, 12(2):111–124,
2000.
[22] J. Van der Akker, C. Van Hoesel, and M. Savelsbergh. A polyhedral approach to singlemachine scheduling problems. Mathematical Programming, 85:541–572, 1999.
Versão Final Recebida em 18/11/2008 - Publicado em 22/12/2008