Journal of Scheduling 8: 303–322, 2005. © 2005 Springer Science + Business Media, Inc. Manufactured in The Netherlands.

TABU SEARCH ALGORITHMS FOR CYCLIC MACHINE SCHEDULING PROBLEMS PETER BRUCKER AND THOMAS KAMPMEYER∗ Universit¨at Osnabr¨uck, Fachbereich Mathematik/Informatik, 49069 Osnabr¨uck, Germany

ABSTRACT Tabu search algorithms are developed for solving a large class of cyclic machine scheduling problems with the objective to minimize the cycle time. Neighborhoods are derived which generalize the block-approach based neighborhoods which have been successfully applied to noncyclic job-shop problems. For a variant of this neighborhood opt-connectivity is proved. The tabu-search procedure is applied to cyclic job-shop scheduling problems. Computational results are presented. KEY WORDS: cyclic scheduling, job-shop problem, tabu-search, block approach, opt-connectivity

1. INTRODUCTION Cyclic scheduling is concerned with the planning of activities that have to be identically repeated at regular intervals. Such types of scheduling problems arise in different application areas like compiler design, manufacturing, digital signal processing, railway scheduling, timetabling, etc. Despite the variety of applications, the subject has received modest attention in the scheduling literature. Serafini and Ukovich (1986) introduce a mathematical model for cyclic scheduling problems. Roundy (1992) investigates cyclic job-shop scheduling problems with identical jobs. Cyclic multiprocessor scheduling problems and their applications to signal processing are studied in Korst (1992). Hanen and Munier (1995) give an overview on cyclic scheduling on parallel processors. This model is studied in more detail in Hanen and Munier (1995). Lee and Posner (1997) and Hall, Lee and Posner (2002) investigate complexity issues for cyclic job-shop problems. Hanen [10] introduces a general cyclic scheduling problem which among others contains the cyclic job-shop problem as special case. A main characteristic of this problem is that each job is assigned to a dedicated machine on which it must be processed. She develops a branch-and-bound algorithm for calculating the minimal cycle time for this general model. Another area in which cyclic scheduling plays an important rule is computer pipelining (see e.g., Rau and Fisher, 1993; Allan et al., 1995). In this paper we consider the cyclic scheduling problems introduced by Hanen (1994) which has its main applications in connection with shop scheduling problems. We develop a tabu search procedure for minimizing the cycle time within the same model. The corresponding search space can be restricted in a suitable way. We define a neighborhood for the restricted search space by Correspondence to: Peter Brucker. E-mail: [email protected] (supported by INTAS, Project 00-217). ∗ E-mail: [email protected] (supported by Cusanuswerk).

304

P. BRUCKER AND T. KAMPMEYER

generalizing the block approach for the classical job-shop problem. We also prove that variants of this neighborhood are opt-connected. Computational tests have been performed by applying our procedure to cyclic job-shop and flow-shop problems derived from well-known noncyclic benchmark problems. A comparison with lower bounds we calculated as well shows that the relative deviations from the optimal solutions are quite small. The paper is organized as follows. In the next section we give a precise formulation for the cyclic scheduling problem and formulate an equivalent mixed integer linear programming formulation. We also discuss some special cases. An important special case is the Basic Cyclic Scheduling Problem (BCSP). In Section 3 we recall the most important results for the BCSP. The search space and its restriction are described in Section 4. Section 5 derives relevant neighborhoods and their properties. In Section 6 implementation issues and computational results are discussed. Section 7 contains some concluding remarks. 2. A GENERAL CYCLIC SCHEDULING PROBLEM Let T = {1, . . . , n} be a set of generic operations. Operation i has processing time pi > 0 and must be performed infinitely often. We denote by < i ; k > the k-th occurrence of the generic operation i . A schedule assigns a starting time t(i ; k) to each occurrence < i ; k >. A schedule is called periodic with cycle time α if t(i ; k) = t(i ; 0) + αk for all i ∈ T, k ∈ Z. We assume that ti := t(i ; 0) ≥ 0 for all i ∈ T. A periodic schedule is defined by the vector (ti )i ∈T and the cycle time α. Associated with each operation i , there is a dedicated machine M(i ) ∈ M = {1, . . . , m}, on which each occurrence < i ; k > of i must be processed. Occurrences of different operations to be processed on the same machine cannot overlap. Thus, we have t(i ; k) + pi ≤ t( j ; l)

or t( j ; l) + p j ≤ t(i ; k)

for all i, j ∈ T with i = j and M(i ) = M( j ) and all k, l ∈ Z. Finally, generalized precedence constraints of the form t(i ; k) + Li j ≤ t( j ; k + Hi j ) may be given for all arcs (i, j ) ∈ E of a directed graph G = (T, E) with vertex set T. Li j is called (start-start) delay and Hi j is called the height (or distance) of the generalized precedence constraint. Delays are assumed to be nonnegative integers while heights may be arbitary integers. We also postulate that t(i ; k) + pi ≤ t(i ; k + 1) is satisfied for all i ∈ T, k ∈ Z. Now, the general cycle time minimization problem can be written as min α (2.1) s.t. t(i ; k) = t(i ; 0) + αk t(i ; k) + Li j ≤ t( j ; k + Hi j ) t(i ; k) + pi ≤ t(i ; k + 1) t(i ; k) + pi ≤ t( j ; l) ∨ t( j ; l) + p j ≤ t(i ; k)

i ∈ T, k ∈ Z

(2.2)

(i, j ) ∈ E, k ∈ Z

(2.3)

i ∈ T, k ∈ Z

(2.4)

i, j ∈ T with i = j and M(i ) = M( j ), k, l ∈ Z (2.5)

305

TABU SEARCH ALGORITHMS

Constraints (2.4) can be covered by the constraints (2.3) if we allow the graph G to have loops (i, i ) ∈ E with Hii = 1 and Lii = pi . Problem (2.1) to (2.5) is equivalent to the following mixed integer linear program (2.6) to (2.11). min α

(2.6)

(i, j ) ∈ E

(2.7)

s.t. t j − ti ≥ Li j − α Hi j t j − ti ≥ pi − α Ki j

i, j ∈ T with i = j and M(i ) = M( j )

(2.8)

Ki j + K ji = 1

i, j ∈ T with i = j and M(i ) = M( j )

(2.9)

Ki j ∈ Z

i, j ∈ T with i = j and M(i ) = M( j )

(2.10)

i∈T

(2.11)

ti + pi − α ≤ ti

In this mixed integer linear program, α and ti ∀ i ∈ T are nonnegative rational numbers. The proof for this equivalence can be found in Hanen (1994). Besides the objective to minimize the cycle time one may be interested to minimize the total flow time max{t(i ; 0) + pi } − min{t(i ; 0)}. i ∈T

i ∈T

In general these two objectives are conflicting. Therefore an alternative objective would be to minimize a weighted sum of cycle time and total flow time. However, in this paper we consider only the objective of cycle time minimization. Example 2.1. In Table 1 a job-shop problem with two jobs is given. Each job consists of three operations and the processing order for the first job is 1, 2, 3 and for the second is 4, 5, 6. The set of operations is extended by two dummy operations 0 and ∗ with processing time 0. The corresponding graph G = (T, E) is shown in Figure 1. A schedule with cycle time 11 and total flow time 22 is shown in Figure 2. An optimal schedule with cycle time 6 and total flow time 8 is shown in Figure 3. To demonstrate the influence of a height we set the height of the arc (∗, 0) to H∗0 = 1. The corresponding optimal schedule with minimal cycle time 8 is shown in Figure 4. There are two well-known extreme cases of the general cyclic scheduling problem (2.1) to (2.5) which are polynomially solvable. In the first extreme case the graph G = (T, E) is acyclic. Then Table 1. Job-shop problem with two jobs, each with three operations Operations

1

2

3

4

5

6

Processing time

1

3

1

3

3

1

Machine

1

2

3

2

1

3

306

P. BRUCKER AND T. KAMPMEYER

Figure 1. Precedence constraints for the problem of Table 1.

Figure 2. A cyclic schedule with cycle time 11.

Figure 3. A cyclic schedule with cycle time 6.

Figure 4. A cyclic schedule with cycle time 8.

the minimal cycle time is


α = max j ∈M



 pi .

M(i )= j

In the second extreme case the constraints (2.5) (or (2.8) to (2.10)) are missing (e.g., if M(i ) = M( j ) for all i = j ). The corresponding problem will be briefly discussed in the next section. The results of this next section (see e.g., Carlier and Chrietienne, 1988; Cohen et al., 1985) are fundamental for our search procedures.

TABU SEARCH ALGORITHMS

307

3. A BASIC CYCLIC SCHEDULING PROBLEM The Basic Cyclic Scheduling Problem (BCSP) has the form min α

(3.1)

s.t. ti + Li j − α Hi j ≤ t j ti + pi − α ≤ ti

(i, j ) ∈ E

(3.2)

i∈T

(3.3)

As before T is the set of all operations and E is the arc set of the directed graph G = (T, E). Furthermore all delays Li j are assumed to be nonnegative and all heights Hi j are integer numbers. Problem (2.1) to (2.5) reduces to the BCSP if M(i ) = M( j ) for all i = j . We also get a BCSP if we fix all the Ki j -values in (2.6) to (2.11). Again the constraints (3.3) may be included in (3.2) if we add to E loops (i, i ) with Lii = pi and Hii = 1. Let µ be a circuit in E (or loop (i, i )). Then we denote  L(µ) := Li j (i, j )∈µ

and H(µ) :=



Hi j

(i, j )∈µ

the delay and height of µ, respectively. V (µ) := L (µ)/H (µ) is called the value of µ. We assume that H (µ) = 0 and L (µ) > 0 for all circuits µ. A circuit µ is called critical if V(µ) is maximal among all circuits. The following two theorems are the basis for calculating a periodic schedule with minimal cycle length. Theorem 3.1. The BCSP has a feasible solution if and only if all circuits in G have a positive height. Theorem 3.2. Assume that all circuits in G have a positive height. Then the minimal cycle time is equal to the value of a critical cycle. To calculate the value α ∗ of a critical cycle, one has to solve the minimum cost-to-time ratio cycle problem. A comparison of different algorithms for the minimum cost-to-time ratio cycle problem can be found in Dasdan, Irani and Gupta (1999). The starting times ti of all operations i ∈ T in a periodic schedule with cycle time α ∗ can be found by longest path calculations. 4. THE SEARCH SPACE Let α and a vector K = (Ki j ) be an optimal solution of the general cyclic scheduling problem (GCSP) (2.6) to (2.11). Then α is the minimal solution value of the following BCSP induced by

308

P. BRUCKER AND T. KAMPMEYER

Figure 5. Disjunctive graph for Example 2.1.

the Ki j -values. min α

(4.1)

s.t. ti + Li j − α HXi j ≤ t j with


Hi j HXi j = Ki j

(i, j ) ∈ E ∪ D

(4.2)

if (i, j ) ∈ E if (i, j ) ∈ D.

Note, if an arc (i, j ) is in E and in D, we have to replace the graphs to be considered by multigraphs. Then arcs in E may be denoted by (i, j )C and arcs in D by (i, j ) D . But from the context it is clear, which of this two different arcs is meant. Therefore we keep denoting arcs by (i, j ). All results remain valid in this more general setting. Furthermore, Li j = pi for all (i, j ) ∈ D and all loops (i, i ) (which belong to E). D is called the set of disjunctions while the arcs in E are called conjunctions. The graph for the Example 2.1 with all conjunctions and disjunctions is shown in Figure 5. We conclude that α and the height function HX :E ∪ D → Z must satisfy the following conditions: • HX i j = Hi j

for all (i, j ) ∈ E

and HX i j + HX ji = 1

for all (i, j ) ∈ D.  HXi j . • All circuits µ in (T, E ∪ D ) have a positive heightHX (µ) =

(4.3) (4.4)

(i, j )∈µ

• The amplitudes L (µ) − α HX (µ) of all circuits µ must be non-positive.

(4.5)

(4.4) must be satisfied due to Theorem 3.1. (4.5) holds because otherwise α must be a strict lower bound for the optimal cycle time. We call a height function HX satisfying (4.3) and (4.4) relevant and consistent, respectively. If for some α the height function HX satisfies (4.3) to (4.5) it is called feasible for α. If HX is relevant

TABU SEARCH ALGORITHMS

309

and consistent then by applying the techniques of Section 3, one can always find a minimal α such that H X is feasible for α. Such an α solves the corresponding BCSP. To solve the GCSP by local search methods we define the set of all relevant and consistent height functions as search space. One has to find in this search space a height function such that the solution value α ∗ for the corresponding BCSP is minimal. In the final part of this section we want to develop an upper bound for the height of a disjunctive arc. First we recall a bound given by Hanen (1994). Theorem 4.1. Given is an instance for a cyclic scheduling problem with a feasible height function for a given α. For a disjunctive arc (i, j) an upper bound H X+H (i, j ) can be computed as follows:   L ji + aαG (i, j ) + HX H (i, j ) = 1 − (4.6) α where aαG (i, j ) = max{L (µ) − α H (µ) | µ is a path from i to j in (T, E )}. With this bound one may get problems with conditions 4.3 to 4.5 as the following example shows. Example 4.1. Again we consider Example 2.1. The corresponding precedence graph is shown in Figure 6. The cycle time α is 11. A critical circuit is (0, 4, 5, 1, 2, 3, ∗, 0). If we compute an upper bound for the height of arc (5, 1) according to Theorem 4.1, then we get

H

X +H



 1 + (4 − 22) (5, 1) = 1 − =2 11

By setting the height of the arc (5, 1) equal to 2 and the height of the arc (1, 5) to −1, we get the circuit (1, 5, 6, 3, ∗, 0, 1) with non-positive height 0. Thus, the bound (4.6) does not guarantee that conditions (4.3) to (4.5) are always satisfied.

Figure 6. Precedence graph for Example 4.1.

310

P. BRUCKER AND T. KAMPMEYER

So we need to develop a new bound. Let HX be a relevant and consistent height function. We will derive a neighbor of HX by choosing an arc (i, j ) ∈ D and increasing the corresponding value HXi j . To keep HX relevant, HX ji must be decreased by the same amount. However, if we decrease HX ji then the new height function HX may become inconsistent. To avoid this, the inequality H X ji + H X i+j ≥ 1

(4.7)

H X i+j = min {HX (τ ) | τ is path from i to j in (T, E ∪ D\{(i, j )})}.

(4.8)

must hold where

(4.7) is equivalent to H X i+j ≥ 1 − H X ji = H Xi j , i.e., HX i+j is an upper bound for the modified height H Xi j of arc (i, j ) ∈ D. These observations lead to Theorem 4.2. A relevant height function H X : E ∪D → Z is consistent if and only if H Xi j ≤ H X i+j for all (i, j ) ∈ E ∪ D. Proof. If ( j, i ) is an arc of some circuit µ with non-positive height then 1 − HXi j + H X i+j = H X ji + H X i+j ≤ H X (µ) ≤ 0 which implies H X i+j < H Xi j . Conversely, if H X i+j < H Xi j =
1 − H X ji then H X (µ) ≤ H X i+j + H X ji < 1 for some circuit µ. Example 4.2. With the new bound (4.8) we get H X + (5, 1) = 1. So with this bound conditions (4.3) to (4.5) are satisfied. 5. NEIGHBORHOODS Let HX : E ∪ D → Z be some height function which is feasible for some optimal solution value α for the corresponding BCSP. Then α = HL(µ) for some critical circuit µ in (T, E ∪ D) and α X(µ) can be improved only by changing HXi j for some arc (i, j ) in the critical circuit. Assume that the height function keeps to be consistent if we decrease HXi j by some positive integer value x. Then the corresponding value of µ will increase, which can be seen as follows. Let µ1 be the sub-path of µ connecting j with i . Then L (µ) L (µ) L (µ) < = H X (µ) H X (µ1 ) + H Xi j H X (µ1 ) + H Xi j − x Thus, the only way to decrease α by changing HX is to increase HXi j in some critical arc (i, j ) ∈ D. By Theorem 4.2 the height function HX will keep to be consistent when increasing HXi j only if HXi j < H X i+j . The following theorem provides conditions under which HXi j < H X i+j holds. Theorem 5.1. Let H X be a feasible height function and a an arc from i to j on a corresponding critical circuit in (T, E ∪ D). Assume that the conditions La < min {L (µ) | µ is a path from i to j with at least two arcs}

(5.1)

TABU SEARCH ALGORITHMS

311

Figure 7. Part of the circuits µ and τ .

and Li j ≥ pi ∀ (i, j ) ∈ E

(5.2)

hold. Then HXa < HXa+ . Proof. Consider a critical circuit µ. If in µ a disjunctive arc a exists which has the same length and height as a parallel conjunctive arc a , we replace a by a in the critical circuit. Now assume that in µ a disjunctive arc a from i to j exists, otherwise the schedule is optimal. The path µ1 from j to i and the arc a form together the critical cycle µ. The back-going arc from j to i is denoted by b. Thus, HXa + HXb = 1. We also have HX(µ) ≥ 1 because HX is consistent. Let τ1 be an arbitrary path from i to j which does not contain the arc a and let τ be the circuit consisting of τ1 and b. This situation is shown in Figure 7. We have to show that HX(τ1 ) > H Xa . Then H Xa < H Xa+ by definition of H Xa+ . Because HX is consistent we must have H X(τ ) = H X(τ1 ) + H Xb ≥ 1 which is equivalent to H X(τ1 ) ≥ H Xa . Now assume that H X(τ1 ) = HXa . We distinguish between two different cases. In the first case the path τ1 consists of at least two arcs and in the second case the path τ1 is a single conjunctive arc c from i to j . Let us consider the first case. Then L(µ) La + L(µ1 ) L(τ1 ) + L(µ1 ) L(τ1 ) + L(µ1 ) = = ≥ (5.3) H X(µ) H X(µ1 ) + H Xa H X(µ1 ) + H X(τ1 ) H X(µ1 ) + H Xa The inequality holds because the composition of τ1 and µ1 defines a circuit and µ is a critical circuit. (5.3) is equivalent to La + L (µ1 ) ≥ L (τ1 ) + L(µ1 ) or La ≥ L(τ1 ) contradicting the assumption. Now let us consider the second case. The path τ1 is a single conjunctive arc c. So we have H Xc = H Xa . Due to condition (5.2) Lc ≥ pi . Therefore we would have chosen the arc c instead of the arc a in the critical cycle µ.
The conditions (5.1) and (5.2) of Theorem 5.1 are satisfied if Li j = pi for all (i, j ) ∈ E and pi > 0 for all i ∈ T hold. From now on we assume that conditions (5.1) and (5.2) are satisfied which is the case in machine scheduling applications. So based on Theorem 5.1, one can now increase every height of a disjunctive arc in a critical circuit at least by 1. After this increase, the new height function is still consistent.

312

P. BRUCKER AND T. KAMPMEYER

A neighborhood N assigns to each feasible height function HX a set N(HX) of feasible height functions called neighbors of HX. Replacing HX by a neighbor HX ∈ N (HX) is called a move. A neighborhood N is opt-connected if an optimal height function can be reached from any feasible height function by a finite number of moves. Theorem 5.1 is the basis of a first neighborhood N1 which assigns to each feasible height function HX the set N1 (HX) of all height functions derived from HX by choosing an arc (i, j ) ∈ D on a critical circuit and replacing the corresponding H Xi j value by H Xi j + 1. Theorem 5.2. The neighborhood N1 is opt-connected. Proof. We have to show that we can get from any feasible height function H X to an optimal height function H X ∗ by a finite sequence of moves. This is accomplished by the following procedure. Assume that H X is the currently reached height function. Then we choose an arc (i, j ) ∈ D on a critical circuit with respect to H X such that H Xi j < H X i∗j and replace H Xi j by H Xi j = H Xi j + 1 and HX ji by H X ji = H X ji − 1. H X is feasible because of Theorem 4.2. If no such arc exists then for all arcs (i, j ) on a critical circuit µ we have HXi j ≥ HX i∗j . Thus,   (i, j )∈µ Li j (i, j )∈µ Li j  ≤ ∗ H X ij (i, j )∈µ (i, j )∈µ H Xi j which implies that HX must be optimal as well because µ is critical. Otherwise, due to H Xi j = H Xi j + 1 ≤ H X i∗j and H X ji = H X ji − 1 = 1 − H Xi j − 1 = 1 − H Xi j ≥ 1 − H X i∗j = H X ∗ji the distance



|H Xi j − H X i∗j |

(i, j )∈D

will be decreasing by 2. Therefore the procedure must reach an optimal solution after a finite number of steps.
Instead of increasing HXi j by one if (i, j ) ∈ D is on a critical circuit and HXi j < H X i∗j we may increase HXi j by any integer value x with 1 ≤ x ≤ H X i+j − H Xi j . The resulting neighborhood, denoted by N2 , is opt-connected as well. We derive further neighborhoods which are based on a block theorem which generalizes a corresponding block theorem for the classical job-shop problem (cf., Brucker, 2001, Theorem 6.18). Let HX be a feasible height function and let µ be a critical circuit with respect to HX. A subpath in µ containing at least one arc is called block, if it is a maximal sub-path containing only disjunctive arcs. Theorem 5.3. Let µ be a critical circuit for a feasible height function HX and let ( j, k) be an arc of a block B in µ such that ( j, k) is different from the first and last arc in B. Then the cycle time will not be improved by increasing HX j k by any integer x with HX +j k − H X j k ≥ x ≥ 1.

TABU SEARCH ALGORITHMS

313

Figure 8. The block B in the proof of Theorem 5.3.

Proof. We have to show that after increasing H X j k a circuit exists with a value greater or equal to the value of a critical circuit in the original network. Let us consider the situation in Figure 8. The immediate predecessor of j is i in B and l is the immediate successor of k in B. Denote the height of the path i, j, k, l with respect to HX by HX(i, j, k, l) and let H Xnew (i, k, j, l) be the height of the path i, k, j, l after increasing H X j k . Furthermore let µ be the circuit if in µ the path i, j, k, l is replaced by i, k, j, l and let HXnew (µ ) be the height of µ after increasing H X j k . Then it is sufficient to show that H Xnew (i, k, j, l) ≤ H X(i, j, k, l)

(5.4)

because this implies HXnew (µ ) ≤ H X (µ) and together with L (µ) = L(µ ) we have L(µ) L(µ ) ≤ . H X(µ) H Xnew (µ )

(5.5)

However, (5.5) means that the cycle time will not decrease after changing HX j k . To prove (5.4) we first derive two inequalities which are consequences of the fact that HX is consistent. We have for the circuit (k, i, j, k) H Xki + H Xi j + H X j k ≥ 1 By replacing HXki by 1 − HXi k we get H Xi j + H X j k ≥ HXi k

(5.6)

If we consider (k, l, j, k) we get H Xkl + H Xl j + H X j k ≥ 1 or H Xkl ≥ 1 − H Xl j − H X j k = H X jl − H X j k . Thus, new H X new (i, k, j, l) = H Xi k + H Xkj + H X jl

= H Xi k + H Xkj − x + H X jl ≤ H Xi j + H X j k + H Xkj − x + H X jl = H Xi j + H X j k + 1 − H X j k − x + H X jl ≤ H Xi j + H X jl ≤ H Xi j + H X j k + H Xkl = H X(i, j, k, l)

(5.7)

314

P. BRUCKER AND T. KAMPMEYER

The first and last inequalities are implied by (5.6) and (5.7), respectively. The middle inequality holds because x ≥ 1.
Based on Theorem 5.3, one could define a neighborhood N3 which increases the HXi j -values of the first and last arcs of blocks only. As for the classical job shop problem, it is unknown whether N3 is connected. Therefore we introduce a neighborhood N4 which is defined by the following moves defined for the interior vertices j of blocks of a critical circuit. There are two neighbors associated with j . The first neighbor is constructed by increasing HXi 1 j as far as possible where i 1 is the predecessor of j in the block, then increasing HXi 2 i 1 as far as possible where i 2 is the predecessor of i 1 in the block, etc., and finally increasing HXil il−1 where il is the first vertex in the block. Symmetrically, the second neighbor is constructed by increasing successively HX j k1 , H Xk1 k2 , . . . , H Xkh−1 kh where kh is the last vertex in the block. Theorem 5.4. The neighborhood N4 is opt-connected. Proof. The proof is similar to the proof of Theorem 5.2. Let H X be the actual height function and let µ be a critical circuit with respect to H X. Let (i, j ) ∈ D an arc in a block B of µ with H Xi j
is decreasing by at least 1. Thus, by repeating this process we will reach an optimal solution after a finite number of moves.
6. TABU SEARCH The tabu search method is a metaheuristic which was designed by Glover (1989, 1990). In each interation of this local search method the current solution is usually replaced by a solution in its neighborhood. We considered two strategies to choose a neighbor as a start solution for the next iteration:

r the best-fit strategy which chooses a neighbor with the best solution value by considering systematically all neighbors.

r the first-fit strategy which chooses the first neighbor which provides a better solution value than the current one. If there is no such neighbor then the best-fit strategy is applied. Contrary to the iterative improvement method, also non-improving solutions are accepted during the search process. Thus, it is possible to leave local minima. In order to avoid cycling, a tabu list is used which stores attributes characterizing solutions that should not be considered again for a certain length of time. All moves to solutions characterized by these attributes are forbidden (tabu). A disadvantage of this procedure is that solutions which have never been visited may also be forbidden by the tabu list. To cancel the tabu status on a move aspiration criteria are introduced. They allow the acceptance of neighbors even if they are forbidden due to the tabu status.

TABU SEARCH ALGORITHMS

315

We consider two types of attribute sets T B1 and T B2 to characterize a solution. T B1 is given by

r the arc (i, j ) for which the height HXi j will be changed. r the value of HXi j before its change. In connection with T B1 we choose the following aspiration criterion: accept tabu moves if it improves the best solution found so far. T B2 is an extension of T B1 . In addition to the two attributes of T B1 also the optimal cycle time α for the solution before the move is stored. So the aspiration criterion is not needed in this case. If all neighbors of a current solution are tabu and no neighbor satisfies the aspiration criterion then the oldest candidates of the tabu list are eliminated step by step until at least one neighbor of the current solution is not tabu anymore. We organize the tabu list in two possible ways denoted by TL1 and TL2 . In the scheme TL1 we start with an empty list. Then the attributes of all visited neighbors are inserted into the list until the list has reached a maximal length Lmax . In this case the oldest entry will be replaced by the attributes of the actual solution. TL2 is an extension of TL1 with the following additional feature: all entries of the tabu list will be eliminated when a solution improving the best solution value considered so far is reached. To start the tabu search procedure a relevant and consistent height function must be constructed. We considered different algorithms for constructing such a height function and tested the corresponding overall performance of the tabu search. It turned out that complex start heuristics which provided solutions with small cycle times did not provide the best overall performance. On the other hand the following simple start heuristic based on Theorem 4.2 provided very good results. The difference between our heuristic and the heuristic in Hanen (1994) is that the bounds are computed differently (see Section 4). The heuristic starts with G := (T, E) and a relevant and consistent height function HX defined on the set E. Then step by step HX is extended to the set of all disjunctive arcs (i, j ) which are added to the current arc set E. The function HX is extended to (i, j ), ( j, i ) ∈ D\E by setting H Xi j := min {H X (τ ) | τ is a path from i to j in (T, E)} and

(6.1)

H X ji := 1 − H Xi j . Summarizing we have the following procedure which provides a relevant and consistent height function. Startheuristic E := E; D := List of all disjunctions (i, j ) with i < j ; WHILE (i, j ) ∈ D exists DO BEGIN Calculate H Xi j and H X ji according to (6.1); Eliminate (i, j ) from D; E := E ∪ {(i, j ), ( j, i )}; END

316

P. BRUCKER AND T. KAMPMEYER

7. COMPUTATIONAL RESULTS In this section we present some computational results for the described tabu search versions. We implemented all procedures in C and tested them on a Intel Celeron (1.8 GHz) with operating System Linux and 256 MB general storage. To compute the cycle time we use “Howard’s Algorithm” (Dasdan, Irani, and Gupta, 1999). 7.1. Test problems As test instances we used cyclic job-shop and flow-shop problems. We derived these test instances from benchmark problems for the noncyclic counterparts by constructing a graph G = (T, E) with corresponding delays Li j and heights Hi j as follows. T is the set of all operations plus two dummy operations ◦ and ∗ which correspond to the start and end, respectively. E contains all precedence relations (i, j ) given by the instance of the shop-problem. Especially we have arcs (◦, i ) for all operations i without predecessor and (i , ∗) for all operations without successor. Furthermore, we set Li j equal to the processing time pi of operation i (◦ and ∗ have zero processing time) and Hi j = 0 for all these arcs (i, j ). To create a cyclic scheduling problem we finally add an arc (∗, ◦) to E with L∗◦ = 0 and variable height H∗◦ (see Example 2.1). The set of job-shop and flow-shop instances created in this way are denoted by Job.T1.H∗◦ and Flow.T1.H∗◦ , respectively. We have chosen H∗◦ ∈ {1, 2}. For H∗◦ = 1 all operations i ∈ T in the k-th period must be finished before operations of period k + 1 can start. Thus, the cyclic problem to minimize the cycle time is equivalent to the noncyclic makespan minimization problem. In this case the results can be compared with the results achieved for the benchmarks in the literature. For H ∗◦ = 2 operations of two consecutive periods can be scheduled at the same time. Therefore, we usually get a more compact schedule with a smaller cycle time. For larger H ∗◦ we usually get a solution with the property that one of the machines is never idle which proves optimality. Therefore we did not consider problem sets with H ∗◦ ≥ 3. In a second set of test instances we additionally added arcs (k, l) connecting the last operation k with the first operation l of any job. Furthermore, we set Lkl = pk and Hkl ∈ {1, 2}. In all cases we choose H ∗◦ = 2. Job.T2.1 and Flow.T2.1 denote sets of problems with Hkl = 1 for all additional arcs (k, l). Job.T2.2 and Flow.T2.2 denote sets of problems with Hkl = 2 for all additional arcs (k, l). The underlying job-shop and flow-shop benchmark problems are listed in Tables 2 and 3, respectively. They are taken from Beasley (http://people.brunel.ac.uk/∼mastjjb/jeb/info.html). These benchmark problems are the most important and most difficult problems in the machine scheduling area. Up to now the instance with 15 jobs and 15 machines are still hard problems. Therefore we use these problems to test our tabu-search. 7.2. Preliminary tests and experiment setup Several tests have been performed to investigate the influence of

r the neighborhood, r the choice of a strategy for selecting a neighbor,

TABU SEARCH ALGORITHMS

Table 2. Job-Shop benchmark problems Instance #jobs #machines #operations la01 la02 la03 la04 la05 la06 la07 la08 la09 la10 la11 la12 la13 la14 la15 la16 la17 la18 la19 la20 la21 la22 la23 la24 la25 la26 la27 la28 la29 la30 la31 la32 la33 la34 la35 la36 la37 la38 la39 la40 ft06 ft10 ft20

10 10 10 10 10 15 15 15 15 15 20 20 20 20 20 10 10 10 10 10 15 15 15 15 15 20 20 20 20 20 30 30 30 30 30 15 15 15 15 15 6 10 20

5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 15 15 15 15 15 6 10 5

50 50 50 50 50 75 75 75 75 75 100 100 100 100 100 100 100 100 100 100 150 150 150 150 150 200 200 200 200 200 300 300 300 300 300 225 225 225 225 225 36 100 100

317

318

P. BRUCKER AND T. KAMPMEYER

Table 3. Flow-shop benchmark problems Instance #jobs #machines #operations car1

11

5

55

car2

13

4

52

car3

12

5

60

car4

14

4

56

car5

10

6

60

car6

8

9

72

car7

7

7

49

car8

8

8

64

recC01

20

5

100

recC03

20

5

100

recC05

20

5

100

r the definition of the tabu status, and r the organization of the tabu list. From these preliminary tests we concluded that N1 and N2 provided poor results. Then we choose neighborhoods N3 and N4 for further investigation. We also applied the best-fit strategy, used the attribute set TB1 , and organized the tabu list according to rule TL1 . A good choice for the tabu list length was Lmax = nm k with k ∈ {0.3, 0.5}. These setups are chosen for further tests with both neighborhoods N3 and N4 and the two alternative choices for Lmax . We decided to stop each run of the procedure after Itermax iterations. For further tests we choose 200 or 800 as values for Itermax . These relative low values are a consequence of the fact that each iteration is very time consuming. Usually 1000 or more iterations are applied. However, such a choice leads to large computation times without considerable improvements of the cycle times. We applied the algorithm to all test sets described in the last section. 7.3. Computational results Before presenting our computational results, we tried to solve the same instances by using CPLEX 8.1, but only a few instances with small machine and job numbers could be solved by this program. We conclude that CPLEX is not able to solve these hard problems. Computational results for the test sets Job.T1.k with 43 instances and Flow.T1.k with 11 instances for k = 1, 2 are documented in Tables 4 to 7. For each test set we calculated:

r the average value  avg for the relative deviation  :=

αH − αLB · 100% αLB

of the cycle time α H provided by the heuristic from a lower bound αLB for the cycle time,

r the average computation time  CPU in seconds, and r the number # opt of times αH was equal to αLB .

319

TABU SEARCH ALGORITHMS

Table 4. Itermax = 200 and neighborhood N4 k = 0.3

k = 0.5

Test set

 avg  CPU # opt  avg  CPU # opt

Job.T1.1

14.41

525

7

17.99

405

6

Flow.T1.1 18.91

16

0

20.21

13

0

10.61

715

24

15.19

542

20

0.57

7

10

0.15

6

10

Job.T1.2 Flow.T1.2

Table 5. Itermax = 200 and neighborhood N3 k = 0.3

k = 0.5

Test set

 avg  CPU # opt  avg  CPU # opt

Job.T1.1

14.42

317

5

16.11

299

4

Flow.T1.1 10.94

4

0

13.39

4

0

10.62

390

24

1

11

Job.T1.2

6.60

352

29

Flow.T1.2

0.20

1

10

0

Table 6. Itermax = 800 and neighborhood N4 k = 0.3 Test set Job.T1.1

k = 0.5

 avg  CPU # opt  avg  CPU # opt 6.17

1289

13

8.16

1030

Flow.T1.1 16.12

83

0

17.23

51

11 0

Job.T1.2

0.86

989

38

1.41

1366

37

Flow.T1.2

0.47

7

10

0.16

7

10

Table 7. Itermax = 800 and neighborhood N3 k = 0.3 Test set Job.T1.1

k = 0.5

 avg  CPU # opt  avg  CPU # opt 5.83

567

7

7.63

533

7

Flow.T1.1

4.67

24

1

7.42

25

0

Job.T1.2

0.23

459

40

0.27

538

40

Flow.T1.2

0.01

2

10

0.00

1

11

For each instance we calculated two lower bounds. The first lower bound can be achieved by solving the corresponding BCSP (i.e. the constraints (2.8) to (2.10) are relaxed). The second lower bound is the maximum of the sum of the processing times of all operations on a machine. The maximum of these two lower bounds is αLB .

320

P. BRUCKER AND T. KAMPMEYER

For the benchmark problems in Job.T1.1 and Flow.T1.1 we replaced the values α LB by the optimal solution values known from literature. Clearly, the neighborhood N4 is more time consuming because the H X -values are increased for many arcs while for N3 only two H X-values are increased. This is reflected by the  CPU -values. If we consider the test problems with height 1, despite the increased computational effort the number of optimal solution is the best only for the test set Job.T1.1. For the test set Flow.T1.1 the average cycle time for the N4 -neighborhood is even worse than N3 . Now we consider the results for the T1.1 test sets. For Itermax = 800 the computational times are already quite large. The quality of the solution values is quite good for the job-shop test set and for the flow-shop instances. Results are different for the T1.2 test sets. The lower bounds are achieved after 200 iterations in many cases. A further increase of H∗◦ has the affect that the lower bound is reached after even less iterations. The reason for this is that larger height values allow more compact cyclic schedules. Precedence constraints become less important. We also observe that the solution quality depends on the parameter k. In some cases k = 0.3 provides better results, in other cases the results are better for k = 0.5. We have derived similar results for the T2 test sets which are documented in Tables 8–11. Table 8. Itermax = 200 and neighborhood N4 k = 0.3

k = 0.5

Test set

 avg  CPU # opt  avg  CPU # opt

Job.T2.1

13.63

681

17

16.92

642

Flow.T2.1

1.11

9

8

1.57

12

16 8

Job.T2.2

8.64

999

23

11.38

882

22

Flow.T2.2

0.58

7

10

0.15

11

10

Table 9. Itermax = 200 and neighborhood N3 k = 0.3

k = 0.5

Test set

 avg  CPU # opt  avg  CPU # opt

Job.T2.1

12.69

436

19

13.61

425

Flow.T2.1

0.85

1

8

0.72

1

17 9

Job.T2.2

6.60

462

26

12.24

413

25

Flow.T2.2

0.20

1

10

0.00

1

11

Table 10. Itermax = 800 and neighborhood N4 k = 0.3 Test set

k = 0.5

 avg  CPU # opt  avg  CPU # opt

Job.T2.1

6.74

1467

20

10.09

1329

Flow.T2.1

0.56

10

9

0.84

14

20 8

Job.T2.2

0.97

1681

37

0.6

1787

34

Flow.T2.2

0.47

7

10

0.15

12

10

321

TABU SEARCH ALGORITHMS

Table 11. Itermax = 800 and neighborhood N3 k = 0.3

k = 0.5

 avg  CPU # opt  avg  CPU # opt

Test set Job.T2.1

5.42

623

28

6.92

629

25

Flow.T2.1

0.51

2

9

0.56

2

9

Job.T2.2

0.41

619

41

0.82

635

38

Flow.T2.2

0.01

1

10

0.00

1

11

In the T2 test set one can see again the influence of increasing the heights (of job backwards arcs). With this increase the average deviation decreases. So for the T2.2 test set in almost every case the tabu search reaches the lower bound. For the T2.1 test set the results are not so good as for the test set T2.2, but for many instances the lower bound is achieved. From these results we conclude that our tabu-search works very good for cyclic shop scheduling problems, especially in connection with the neighborhood N3 . The neighborhood N4 leads only to an increase in computational time but not in a decrease of the average relative deviation. We also remark that the tabu-search is quite a good method to solve cyclic machine scheduling problems. 8. CONCLUDING REMARKS A model for cyclic machine scheduling problems with the objective to minimize the cycle time has been described. To solve the corresponding optimization problem by local search methods different neighborhoods have been introduced. The most effective neighborhoods are based on a block theorem which generalizes the well-known block theorem for the classical job-shop problem. With these concepts a tabu search procedure has been derived and numerically tested for cyclic job-shop and flow-shop problems. The results are very promising, especially for the job-shop problem. There is much room for further research. Using the neighborhoods which have been introduced other local search methods may be implemented and tested. Furthermore, besides the job-shop and flow-shop problem other cyclic scheduling problems can be solved by this model. For example for solving problems with multipurpose machines we suggest a two-stage approach. In the first stage the machine assignment is fixed so that one get a problem with dedicated machines. In the second stage our tabu-search approach can be applied. For problems with arbitrary delays our tabu-search should work without any modification. This is also the case, if constraint (2.4) is relaxed. Other examples for such extensions are problems with buffers of limited capacity or with transportation. Also new lower bounds for the cyclic shop problems could be developed. REFERENCES Allan, V., R. Jones, R. Lee, and S. Allan, “Software pipelining,” ACM Computing Surveys, 27(3), 367–432 (1995). Beasley, J. E. “Benchmark problems,” http://people.brunel.ac.uk/∼mastjjb/jeb/info.html. Brucker, P. Scheduling Algorithms. Springer-Verlag, Berlin, fourth edition, 2004. Carlier, J. and P. Chretienne, “Les Probl´emes d’Ordonnancement,” Technical report, Masson, Paris, 1988. Cohen, G., D. Dubois, J. P. Quadrat, and M. Viot, “A linear system theretic view of discrete event process and its use for performance evaluation in manufacturing,” IEEE Transactions on Automatic Control, 30(2), 210–220 (1985).

322

P. BRUCKER AND T. KAMPMEYER

Dasdan, A., S. S. Irani, and R. K. Gupta. “Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems,” in Proceedings of the 36th ACM/IEEE Conference on Design Automation Conference, Annual ACM IEEE Design Automation Conference, ACM Press New York, NY, USA, 1999, pp. 37–42. Glover, F. “Tabu search I,” ORSA Journal on Computing, 1, 190–206 (1989). Glover, F. “Tabu search II,” ORSA Journal on Computing, 2, 4–32 (1990). Hall, N. G., T. E. Lee, and M. E. Posner, “The complexity of cyclic shop scheduling problems,” Journal of Scheduling, 5(4), 307–327 (2002). Hanen, C. “Study of a NP-hard cyclic scheduling problem: The recurrent job-shop,” European Journal of Operational Research, 72, 82–101 (1994). Hanen, C. and A. Munier, “Cyclic scheduling on parallel processors: on overview,” chapter 4. In P. Chretienne, E. G. Coffman, J. K. Lentra, and Z. Liu (eds.), Scheduling Theory and Its Applications, Wiley, New York, 1995. Hanen, C. and A. Munier, “A study of the cyclic scheduling problem on parallel processors,” Discrete Applied Mathematics, 57(2–3), 167–192 (1995). Korst, J., “Periodic multiprocessor scheduling,” PhD thesis, TU Eindhoven, 1992. Lee, T. and M. Posner, “Performance measures and schedules in periodic job shop,” Operations Research, 45, 72–91 (1997). Rau, B. R. and J. A. Fisher, “Instruction-level parallel processing: History, overview and perspective,” Journal of Supercomputing, 7, 9–50 (1993). Roundy, R., “Cyclic schedules for job-shops with identical jobs,” Mathematics of Operations Research, 17, 842–865 (1992). Serafini, P. and W. Ukovich, “A mathematical model for periodic scheduling problems,” SIAM Journal of Discrete Mathematics, 2(4), 550–581 (1986).