# A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles

Laurent Deroussi, Michel Gourgand, Nikolay Tchernev

► To cite this version:

Laurent Deroussi, Michel Gourgand, Nikolay Tchernev. A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles. International Journal of Production Research, 2008, 46 (8), pp.2143-2164. 10.1080/00207540600818286. hal-03263531

HAL Id: hal-03263531

https://uca.hal.science/hal-03263531

Submitted on 17 Jun 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
A simple metaheuristic approach to the
simultaneous scheduling of machines
and automated guided vehicles

L. DEROUSSI¹, M. GOURGAND², N. TCHERNEV³

LIMOS CNRS UMR 6158

1 IUT de Montluçon, 03101 Montluçon, France

2 ISIMA, Campus des Cézeaux, 63173 Aubière, France

3 IUP Gestion et Management des Entreprises, 63008 Clermont-Ferrand, France

Corresponding author, Email: deroussi@moniut.univ-bpclermont.fr, Tel: (33) 4.70.02.20.97

Abstract. In this paper we address the problem of simultaneous scheduling of machines and vehicles in flexible manufacturing systems. The studied problem is a job shop where the jobs have to be transported between the machines by automatic guided vehicles. In addition to the processing of jobs, we consider transportation aspect as an integral part of the optimization process. To deal with this problem, we propose a new solution representation based on vehicles rather than machines. Each solution can thus be evaluated using a discrete event approach. An efficient neighbouring system is then described and implemented into three different metaheuristics: iterated local search, simulated annealing and their hybridisation. Computational results are presented for a benchmark of 40 literature instances. New upper bounds are found for 11 of them, showing the effectiveness of the presented approach.

Keywords: Job-Shop Problem, Metaheuristics, Neighbouring Systems, Flexible Manufacturing Systems, Automated Guided Vehicles.
# A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles

**Abstract.** In this paper we address the problem of simultaneous scheduling of machines and vehicles in flexible manufacturing systems. The studied problem is a job shop where the jobs have to be transported between the machines by automatic guided vehicles. In addition to the processing of jobs, we consider transportation aspect as an integral part of the optimization process. To deal with this problem, we propose a new solution representation based on vehicles rather than machines. Each solution can thus be evaluated using a discrete event approach. An efficient neighbouring system is then described and implemented into three different metaheuristics: iterated local search, simulated annealing and their hybridisation. Computational results are presented for a benchmark of 40 literature instances. New upper bounds are found for 11 of them, showing the effectiveness of the presented approach.

*Keywords: Job-Shop Problem, Metaheuristics, Neighbouring Systems, Flexible Manufacturing Systems, Automated Guided Vehicles.*

## 1. Introduction

A Flexible Manufacturing System (FMS) can be described as follows: FMS consists of several machine tools along with part and tool handling devices such as robots, arranged so that it can handle any family of parts for which it has been designed and developed. These systems require a high investment but they have a high potential. As result, scheduling of FMS has been extensively investigated during the last three decades.

This paper is devoted to the study of the classical job shop problem where transportation times are considered. It is classified as a *JR* | *t*<sub>kl</sub>, *t*'<sub>kl</sub> | *C*<sub>max</sub> problem according to the α | β | γ-notation introduced by Graham *et al.* (1979) and extended by Knust (1999) for transportation problems. *J* indicates a job shop, *R* indicates that we have a limited number of identical vehicles (robots) and all jobs can be transported by any of the robots. *t*<sub>kl</sub> indicates that we have job-independent, but machine-dependent loaded travel times. *t*'<sub>kl</sub> indicates that we have machine-dependent empty travel times. The objective function to minimize is the makespan *C*<sub>max</sub>. Several authors note the necessity to carefully plan the interactions between process and transportation activities (Raman *et al.* (1986), Ulusoy *et al.* (1993), Knust (1999)). Unfortunately, the resulting problem is quite difficult to solve. We have to deal with two NP-hard problems simultaneously: the job-shop scheduling problem (Lenstra and Rinnooy Kan, 1979) and the vehicle scheduling problem, which is similar to a pick up and delivery problem (Lenstra and Rinnooy Kan, 1981). Additionally, problems with transportation times are NP-hard since they are a generalization of classical NP-hard
shop problems. More precisely, concerning the job shop, Knust (1999) writes: "*The classical job shop problems J2 || C<sub>max</sub> and J3 | p<sub>ij</sub> = 1| C<sub>max</sub> are both strongly NP-hard, which implies that only very restrictive special cases with transportation times may be polynomially solved*".

As consequence, exact methods are mainly used for the study of simple or particular FMS, with strict assumptions. Thus, Blazewicz et al. (1991) study a FMS in which identical parallel machines are laid out in loop. Raman et al. (1986) present a MIP (Mixed Integer Programming) formulation of this problem but with the unrealistic assumption that the vehicles come back to the load/unload (LU) station after each achieved transport. Bilge and Ulusoy (1995) propose a MIP formulation raising this constraint on the vehicles. According to the authors, the resulting model is intractable in practice, because of its nonlinearity and its size.

Approximated methods are well adapted to study most of the FMS, but within an offline framework. Nevertheless, many works are dedicated to simplified forms of this problem. There are essentially two kinds of simplifications. The first ones consist in defining dispatching rules for the vehicles, for example described and studied by Egbelu and Tanchoco (1984) and Le Anh and De Koster (2005). These rules allow to determine how AGVs move for a given scheduling of machines. The second ones are the restriction of the material handling system at only one AGV. As illustration, Soylu et al. (2000) and Hurink and Knust (2002) propose respectively neural networks and tabu search approaches. Finally, few works are undertaken on the job shop with transportation. Ülusoy and Bilge (1993) and Bilge and Ülusoy (1995) propose an iterative method based on the decomposition of the master problem into two subproblems. Ülusoy et al. (1997) propose a genetic algorithm for this problem. Abdelmaguid et al. (2004) describe a hybrid method composed of a genetic algorithm for the scheduling of machines and a heuristic for the scheduling of vehicles.

For online scheduling of such systems, simulation is often the only available tool. Discrete event simulation is used for various purposes: for example to improve the AGV design process (Gabal and Kasilingam, 1991), to compare the vehicles on-line dispatching rules (Egbelu and Tanchoco, 1984) or to test the problems of collision between the vehicles (Revielotis, 2000).

Nuhut (1999), Qiu et al. (2002) and Le Anh and De Koster (2006) present more complete surveys of the job shop problem with transportation.

For this problem, most of the (small) instances considered in this paper remains today unsolved. Ganesharajah et al. (1998) note that due to the intractability of the joint scheduling problem, the literature contains mainly heuristic
approaches. In this paper, we propose a new effective metaheuristic approach for the offline *JR* | *t*<sub>kl</sub>, *t*'<sub>kl</sub> | *C*<sub>max</sub>
problem.

This paper is articulated as follows. In Section 2 we present a problem formulation and we propose a new
solution representation based on vehicles. In Section 3 we show how feasible solutions can be evaluated using a
discrete event approach. Section 4 is devoted to the description of an efficient neighbouring system. The
metaheuristics implemented are described in Section 5 and some computational results can be found in Section 6.

**2. The job-shop problem with transportation: formulation and solution representation**

In this section we introduce the job shop problem with transportation using the Brucker’s notations (2001), we present the chosen solution representation and we discuss its advantages and its drawbacks.

**2.1. Problem formulation**

In a job shop scheduling problem, we have a set $J = \{J_1, \dots, J_n\}$ of $n$ independent jobs that have to be processed without preemption on a set $M = \{M_0, M_1, \dots, M_m\}$ of $m+1$ machines ($M_0$ represents the load / unload or LU station from which jobs enter and leave the system). Each job $J_i \in J$ consists of a sequence of $n_i$ operations $o_{ij}$.
Let us note $O_i = \{o_{ij}, j = 1, \dots, n_i\}$ the set of operations of job $J_i$, and $O = \cup_{i=1}^n O_i$ the set of $o = \sum_{i=1}^n n_i$ operations.
There is a machine $\mu_{ij} \in \{M_0, \dots, M_m\}$ and a processing time $p_{ij}$ associated with each operation $o_{ij}$. Additionally, a vehicle has to transport a job whenever it changes from one machine to another. We have a given set $V = \{V_1, \dots, V_k\}$ of $k$ vehicles. We assume that transportation times are only machine-dependant. $t(M_i, M_{i+1})$ and $t'(M_i, M_{i+1})$ indicate respectively the loaded travel time and the empty travel time from machine $M_i$ to machine $M_{i+1}$ ($i, j = 0, \dots, m$). Vehicles can handle at most one job at a time.

The objective function is the minimizing time required to complete all jobs or makespan.

**2.2. Representation of the search space**

It is well known that the efficiency of metaheuristics highly depends on finding a suitable representation of the search space. For that a new solution representation is introduced, based on vehicles rather than on machines. Each operation $o_{ij} \in O$ requires a transportation task we will note $\tilde{o}_{ij}$, and we propose to schedule the set $\tilde{O}$ of
transportation tasks on the material handling system. In the following of this paper, we will designate by operations the members of O, and by transportation tasks (or tasks) the members of $\tilde{O}$. Let us give in more details the link between O and $\tilde{O}$.

Each operation $o_{ij}$ requires the transportation of job $J_i$ from the previous machine that is defined in its sequence of operations ($M_0$ if $j=1$ or $\mu_{ij-1}$ if $j>1$) to the machine $\mu_{ij}$. So a transportation task $\tilde{o}_{ij}$ is associated with each operation $o_{ij}$. Moreover, when the processing of a job is completed, a vehicle has to transport it to the unload station $M_0$. So we consider an additional task $\tilde{o}_{in_{i+1}}$ for each job. To find again a link between operations and tasks, a fictitious operation $o_{in_{i+1}}$ is added to the sequence of each job. Obviously, we have $\mu_{in_{i+1}} = M_0$ and $p_{in_{i+1}} = 0$. We give in table 1 an example of a feasible representation for jobset 1 (see the appendix section for the jobsets definition).

<table><caption>**Table 1.** A feasible schedule for jobset 1 with three vehicles</caption><thead><tr><th>Vehicle</th><th colspan="6">Task schedule</th></tr></thead><tbody><tr><td>AGV1</td><td>~<sub>o11</sub></td><td>~<sub>o31</sub></td><td>~<sub>o22</sub></td><td>~<sub>o14</sub></td><td>~<sub>o23</sub></td><td>~<sub>o52</sub></td></tr><tr><td>AGV2</td><td>~<sub>o21</sub></td><td>~<sub>o42</sub></td><td>~<sub>o13</sub></td><td>~<sub>o32</sub></td><td>~<sub>o33</sub></td><td></td></tr><tr><td>AGV3</td><td>~<sub>o41</sub></td><td>~<sub>o12</sub></td><td>~<sub>o51</sub></td><td>~<sub>o43</sub></td><td>~<sub>o24</sub></td><td>~<sub>o34</sub></td><td>~<sub>o53</sub></td></tr></tbody></table>

We will indicate by $v(\tilde{o}_{ij}) \in V$ the vehicle that complete the task $\tilde{o}_{ij}$. $\lambda(\tilde{o}_{ij})$ represents the position of the task $\tilde{o}_{ij}$ in the schedule. For example, in the table 1 we have $v(\tilde{o}_{13}) = V_2$ and $\lambda(\tilde{o}_{13}) = 3$.

## 2.3. Advantages of the proposed solution representation

The proposed representation has major differences with those of the literature. (Ülusoy et al., 1997) represent a schedule by a chromosome in which each gene has two data: the operation to be completed and the vehicle at which this operation is assigned. The solution given in table 1 is represented by the chromosome $[(\sigma_{11}, V_1), (\sigma_{21}, V_2), (\sigma_{41}, V_3), \dots, (\sigma_{52}, V_1), (\sigma_{34}, V_3), (\sigma_{53}, V_3)]$. The tasks assigned to one vehicle (for example $\sigma_{11}, \sigma_{31}, \sigma_{22}, \sigma_{14}, \sigma_{23}$, and $\sigma_{52}$ for vehicle 1) are transported according to the order given by the chromosome. However, the same solution can also be represented by the chromosome $[(\sigma_{11}, V_1), \dots, (\sigma_{52}, V_1), (\sigma_{21}, V_2), \dots, (\sigma_{33}, V_2), (\sigma_{41}, V_3), \dots, (\sigma_{53}, V_3)]$, and by many others. As a consequence, one schedule can be represented by many chromosomes, which define an equivalence class. Our representation consists
in working with the set of equivalence class representatives. The immediate consequence is that the search space is
significantly reduced, and thus probably easier to explore.

(Abdelmaguid et al., 2004) get round this difficulty by using a chromosome in which only the order of the operations is mentioned. Thus, the chromosome [σ₁₁, σ₂₁, σ₄₁, ..., σ₅₂, σ₃₄, σ₅₃] indicates the order in which the operations must be treated. A heuristic assigns successively each task to the 'best' vehicle (the chosen criterion is the vehicle that will carry out this task as soon as possible). The authors came back thus to the classical job-shop problem J || Cmax, integrating dynamically the transportation times into the makespan evaluation. The advantage is that the number of solutions is considerably reduced. Nevertheless, we can notice that vehicle assignments are locally optimal, but not necessarily globally.

The use of metaheuristics implies that many solutions must be considered. Such approach requires a makespan evaluation with a computationally fast evaluation subroutine. We present it in the next section.

3. Solutions evaluation

The makespan evaluation is described in algorithm 1 using a discrete event approach. $T(\sigma_{ij})$ (respectively $T(\tilde{\sigma}_{ij})$) indicates the completion time of the operation $\sigma_{ij}$ (respectively the transportation task $\tilde{\sigma}_{ij}$). We use the notion of *available task*, which can be defined as follows:

A transportation task is said to be available at a given time *t* if and only if it has not been carried out yet and it satisfies one of the two following conditions:

- It is associated to the first operation of the job sequence,

- The previous operation (if it exists) in the job sequence is completed at time *t*.

The available tasks correspond in fact to the transports that can be effectively accomplished at a given moment.

We can notice the following remarks about algorithm 1:

(a) At the initial state, the only available tasks $\tilde{\sigma}_{ij}$ are those for which $j=1$ (corresponding to the first operation defined in the sequence of the job $J_i$).

(b) A new event is created if the following transportation task of the vehicle $V_t$ is available (its previous corresponding operation has been already completed).
(c) The task $\tilde{\sigma}_{ij}$ has been just completed. This means that the task $\tilde{\sigma}_{ij+1}$ (if it exists) becomes an available one. A vehicle waiting for this task can now accomplish it, and an event is created. Notice that if tasks $\tilde{\sigma}_{ij}$ and $\tilde{\sigma}_{ij+1}$ are carried out by the same vehicle, this event has been already created in the case (b).

<caption>**Algorithm 1: Makespan evaluation**</caption>

// Initialization

For each task $\tilde{\sigma}_{ij} \in \tilde{O}$ Do

$$T(\tilde{\sigma}_{ij}) = +\infty$$

End For

// Creation of the initial events

For each vehicle $V_i \in V$ Do

If the first task (a) $\tilde{\sigma}_{ij}$ of $V_i$ is an available one Then

$$\text{Compute } T(\tilde{\sigma}_{ij}) \text{ and create event } [V_i, T(\tilde{\sigma}_{ij})]$$

End If

End For

// Main loop

While it exists some events $[V_i, T(\tilde{\sigma}_{ij})]$ with $T(\tilde{\sigma}_{ij}) < +\infty$ Do

$$\text{Choose the next event } [V_i, T(\tilde{\sigma}_{ij})] \text{ and compute } T(\sigma_{ij})$$

If the next task $\tilde{\sigma}_{ij'}$ of $V_i$ exists and is available Then (b)

$$\text{Compute } T(\tilde{\sigma}_{ij'}) \text{ and create event } [V_i, T(\tilde{\sigma}_{ij'})]$$

End If

If the task $\tilde{\sigma}_{ij+1}$ exists and is the next task of a vehicle $V_{j'} \neq V_i$ Then (c)

$$\text{Compute } T(\tilde{\sigma}_{ij+1}) \text{ and create event } [V_i, T(\tilde{\sigma}_{ij+1})]$$

End If

End While

Completion times must satisfy the following constraints:

$$T(\tilde{\sigma}_{i1}) \geq t(M_0, \mu_{i1}), \forall J_i \in J$$

$$T(\tilde{\sigma}_{ij}) \geq T(\sigma_{ij-1}) + t(\mu_{ij-1}, \mu_{ij}), \forall \tilde{\sigma}_{ij} \in \tilde{O}, j > 1$$

$$T(\tilde{\sigma}_{i2/2}) \geq T(\tilde{\sigma}_{i1,j1}) + t'(\mu_{i1,j1}, \mu_{i2,j2-1}) + t(\mu_{i2,j2-1}, \mu_{i2,j2}), \quad \forall \tilde{\sigma}_{i1,j1}, \tilde{\sigma}_{i2,j2} \in \tilde{O}, \quad v(\tilde{\sigma}_{i1,j1}) = v(\tilde{\sigma}_{i2,j2}), \\ \lambda(\tilde{\sigma}_{i2/2}) = \lambda(\tilde{\sigma}_{i1,j1}) + 1 \text{ (with the convention } \mu_{i0} = M_0)$$

$$T(\sigma_{i2/2}) \geq T(\sigma_{i1,j1}) + p_{i2,j2}, \forall \sigma_{i1,j1}, \sigma_{i2,j2} \in O, \mu_{i1,j1} = \mu_{i2,j2}, T(\tilde{\sigma}_{i2,j2}) > T(\tilde{\sigma}_{i1,j1})$$

$$T(\tilde{\sigma}_{ij}) \geq T(\tilde{\sigma}_{ij}) + p_{ij}, \forall \tilde{\sigma}_{ij} \in O$$
Constraint 1 indicates that each job has to be transported from the loading station to its first machine. Constraint 2 indicates that a task cannot be completed before its previous corresponding operation has been completed plus the loaded travel time between the two machines. Constraint 3 gives the minimal time between two consecutive transportation tasks (on the same vehicle). The vehicle makes the empty travel from its last delivery destination to its next pick up destination, plus the loaded travel from here to its next delivery destination. Constraint 4 indicates that an operation can only begin after all previous operations on the same machine have been completed. Constraint 5 indicates that an operation cannot begin before the job arrives on the machine.

Also, the constraint 4 means that the order of operations on a machine is given by the order of arriving corresponding tasks on this machine. In other words, machine's input buffer follows FIFO rule. FIFO is a good performing rule (although nothing indicates that it exists an optimal solution satisfying this rule) and has some practical applications. This additional assumption allows to simplify the computation of the makespan. Only the completion time of the previous operation has to be considered.

Moreover, we assume that the task schedule follows a no-delay strategy (an event occurs as soon as possible). So, the completion times are equal to the minimal value satisfying constraints (1) to (5). The makespan value is equal to the latest completion time.

Some schedules can lead to situations of deadlock. Such situations are presented on the figures 1a (deadlock with one vehicle) and 1b (deadlock with several vehicles) for jobset 1.

The figure 1a shows a deadlock with one vehicle. The task $\tilde{o}_{33}$ cannot be accomplished before the task $\tilde{o}_{32}$. The figure 1b shows a deadlock with three vehicles. Each vehicle waits for accomplishing their second task (respectively $\tilde{o}_{32}$, $\tilde{o}_{42}$ and $\tilde{o}_{12}$), that another vehicle complete a task scheduled in third position (respectively $\tilde{o}_{31}$, $\tilde{o}_{41}$ and $\tilde{o}_{11}$).

<table><caption>Figure 1a. Unfeasible solution: deadlock with one vehicle</caption><thead><tr><th>Vehicles</th><th colspan="6">Task schedule</th></tr></thead><tbody><tr><td>AGV1</td><td>~<br>õ<sub>11</sub></td><td>~<br>õ<sub>33</sub></td><td>~<br>õ<sub>32</sub></td><td>~<br>õ<sub>14</sub></td><td>~<br>õ<sub>23</sub></td><td>~<br>õ<sub>52</sub></td></tr><tr><td>AGV2</td><td>~<br>õ<sub>31</sub></td><td>~<br>õ<sub>42</sub></td><td>~<br>õ<sub>13</sub></td><td>~<br>õ<sub>41</sub></td><td>~<br>õ<sub>22</sub></td><td></td></tr><tr><td>AGV3</td><td>~<br>õ<sub>21</sub></td><td>~<br>õ<sub>12</sub></td><td>~<br>õ<sub>51</sub></td><td>~<br>õ<sub>43</sub></td><td>~<br>õ<sub>24</sub></td><td>~<br>õ<sub>34</sub></td><td>~<br>õ<sub>53</sub></td></tr></tbody></table>

<table><caption>Figure 1b. Unfeasible solution: deadlock with several vehicles</caption><thead><tr><th>Vehicles</th><th colspan="6">Task schedule</th></tr></thead><tbody><tr><td>AGV1</td><td>~<br>õ<sub>51</sub></td><td>~<br>õ<sub>32</sub></td><td>~<br>õ<sub>11</sub></td><td>~<br>õ<sub>14</sub></td><td>~<br>õ<sub>23</sub></td><td>~<br>õ<sub>52</sub></td></tr><tr><td>AGV2</td><td>~<br>õ<sub>21</sub></td><td>~<br>õ<sub>42</sub></td><td>~<br>õ<sub>31</sub></td><td>~<br>õ<sub>13</sub></td><td>~<br>õ<sub>33</sub></td><td></td></tr><tr><td>AGV3</td><td>~<br>õ<sub>22</sub></td><td>~<br>õ<sub>12</sub></td><td>~<br>õ<sub>41</sub></td><td>~<br>õ<sub>43</sub></td><td>~<br>õ<sub>24</sub></td><td>~<br>õ<sub>34</sub></td><td>~<br>õ<sub>53</sub></td></tr></tbody></table>
Deadlock situations are easily detected by our makespan evaluation. Since some tasks cannot be completed, their completion time remains infinite, and so the makespan too.

The presence of unfeasible solutions doesn't facilitate the good exploration of the search space. However it is not the case here, because it was proved that every feasible solution remains reachable from every other feasible solution into the restricted subset of feasible solutions (Deroussi, 2002).

# 4. Construction of an efficient neighbouring system

Neighbouring system is an essential component of metaheuristics. The efficiency of a neighbouring system can be defined as its faculty to find near optimal solutions in the shortest possible time. In this section, we describe first a neighbouring system composed by several basic moves. It is recognized that combining several moves permits to improve the quality of the obtained local minima (Mladenovic and Hansen, 1997; Hansen and Mladenovic, 2003). Then, a technique is proposed to shrink the neighbourhood size, and so to reduce its exploration at the most promising neighbours. To conclude, summarized results are reported showing the efficiency of the proposed neighbouring system.

## 4.1. Description of the basic moves

Tian et al. (1999) present some usual basic moves for scheduling problems. Amongst them, we choose exchange move and insertion move, because of their effectiveness for shop problems has been proved.

### 4.1.1. Exchange move

This move consists in permuting two beforehand selected tasks. The exchange moves thus defined can be intra-vehicles (exchanged tasks are on the same vehicle) or inter-vehicles (exchanged tasks are on different vehicles). Figure 2 shows an inter-vehicles exchange move.

<table><thead><tr><th>Vehicle</th><th colspan="6">Task scheduling</th></tr></thead><tbody><tr><td>AGV1</td><td>~<br>Õ<sub>11</sub></td><td>~<br>Õ<sub>31</sub></td><td>~<br>Õ<sub>22</sub></td><td>~<br>Õ<sub>14</sub></td><td>~<br>Õ<sub>23</sub></td><td>~<br>Õ<sub>52</sub></td></tr><tr><td>AGV2</td><td>~<br>Õ<sub>21</sub></td><td>~<br>Õ<sub>42</sub></td><td>~<br>Õ<sub>13</sub></td><td>~<br>Õ<sub>32</sub></td><td>~<br>Õ<sub>33</sub></td><td></td></tr><tr><td>AGV3</td><td>~<br>Õ<sub>41</sub></td><td>~<br>Õ<sub>12</sub></td><td>~<br>Õ<sub>51</sub></td><td>~<br>Õ<sub>43</sub></td><td>~<br>Õ<sub>24</sub></td><td>~<br>Õ<sub>34</sub></td><td>~<br>Õ<sub>53</sub></td></tr></tbody></table>

<table><caption>**Figure 2.** Illustration of the exchange move; tasks $\tilde{O}_{22}$ and $\tilde{O}_{24}$ are exchanged</caption><thead><tr><th>Vehicle</th><th colspan="6">Task schedule</th></tr></thead><tbody><tr><td>AGV1</td><td>~<br>Õ<sub>11</sub></td><td>~<br>Õ<sub>31</sub></td><td>~<br>Õ<sub>24</sub></td><td>~<br>Õ<sub>14</sub></td><td>~<br>Õ<sub>23</sub></td><td>~<br>Õ<sub>52</sub></td></tr><tr><td>AGV2</td><td>~<br>Õ<sub>21</sub></td><td>~<br>Õ<sub>42</sub></td><td>~<br>Õ<sub>13</sub></td><td>~<br>Õ<sub>32</sub></td><td>~<br>Õ<sub>33</sub></td><td></td></tr><tr><td>AGV3</td><td>~<br>Õ<sub>41</sub></td><td>~<br>Õ<sub>12</sub></td><td>~<br>Õ<sub>51</sub></td><td>~<br>Õ<sub>43</sub></td><td>~<br>Õ<sub>22</sub></td><td>~<br>Õ<sub>34</sub></td><td>~<br>Õ<sub>53</sub></td></tr></tbody></table>
The exchange move preserves the number of tasks assigned to each vehicle. It results from the fact that local search methods based on this move are strongly dependent on the structure of the initial solution.

This move allows to generate $\frac{o(o-1)}{2}$ neighbours.

### 4.1.2. Insertion move

The insertion move consists in removing a randomly chosen task from the schedule, and then to insert it at a randomly chosen location (figure 3). Like the exchange moves, the insertion moves can be intra-vehicles or inter-vehicles. However, in the case of inter-vehicles moves, the number of tasks assigned to the vehicles may vary.

<table><thead><tr><th>Vehicle</th><th colspan="6">Task scheduling</th></tr></thead><tbody><tr><td>AGV1</td><td>~<sub>O11</sub></td><td>~<sub>O31</sub></td><td>~<sub>O22</sub></td><td>~<sub>O14</sub></td><td>~<sub>O23</sub></td><td>~<sub>O52</sub></td></tr><tr><td>AGV2</td><td>~<sub>O21</sub></td><td>~<sub>O42</sub></td><td>~<sub>O13</sub></td><td>~<sub>O32</sub></td><td>~<sub>O33</sub></td><td></td></tr><tr><td>AGV3</td><td>~<sub>O41</sub></td><td>~<sub>O12</sub></td><td>~<sub>O51</sub></td><td>~<sub>O43</sub></td><td>~<sub>O24</sub></td><td>~<sub>O34</sub></td><td>~<sub>O53</sub></td></tr></tbody></table>

<table><caption>Figure 3. Illustration of the insertion move; task $\tilde{o}_{24}$ is inserted at the third position on AGV1</caption><thead><tr><th>Vehicle</th><th colspan="6">Task schedule</th></tr></thead><tbody><tr><td>AGV1</td><td>~<sub>O11</sub></td><td>~<sub>O31</sub></td><td>~<sub>O24</sub></td><td>~<sub>O22</sub></td><td>~<sub>O14</sub></td><td>~<sub>O23</sub></td><td>~<sub>O52</sub></td></tr><tr><td>AGV2</td><td>~<sub>O21</sub></td><td>~<sub>O42</sub></td><td>~<sub>O13</sub></td><td>~<sub>O32</sub></td><td>~<sub>O33</sub></td><td></td><td></td></tr><tr><td>AGV3</td><td>~<sub>O41</sub></td><td>~<sub>O12</sub></td><td>~<sub>O51</sub></td><td>~<sub>O43</sub></td><td>~<sub>O34</sub></td><td>~<sub>O53</sub></td><td></td></tr></tbody></table>

The number of solutions that may be generated starting from the same schedule is given by $o(o-2+k)$.

### 4.2. Neighbourhood reduction

Neighbourhood reduction consists in selecting, among the set of neighbours of a given solution and according to a given criterion, a subset of neighbours containing those that are considered as the *a priori* most promising ones. Consequently, it is expected that reduction allows to accelerate the neighbourhood exploration.

We propose to determine the most promising neighbours by considering only (exchange or insertion) moves in which the chosen tasks are completed in a close interval of time. The implemented neighbourhood reduction is described in figure 4.

1. Choose a task $\tilde{\sigma}_{i_{h_j}}$.

2. Determine $T(\tilde{\sigma}_{i_{h_j}-1})$ and $T(\tilde{\sigma}_{i_{h_j}+1})$, respectively the completion times of the preceding and following tasks of $\tilde{\sigma}_{i_{h_j}}$, according to the sequence of job $J_i$.

3. Choose the second task $\tilde{\sigma}_{i_{z_j}}$ among the tasks such as $T(\tilde{\sigma}_{i_{h_j}-1}) \le T(\tilde{\sigma}_{i_{z_j}}) \le T(\tilde{\sigma}_{i_{h_j}+1})$

<caption>Figure 4. Description of the neighbourhood reduction.</caption>
Once the first operation $\tilde{\sigma}_{i_1 j_1}$ is chosen, the only moves considered are insertions or exchanges, for which the second operation $\tilde{\sigma}_{i_2 j_2}$ will satisfy $T(\tilde{\sigma}_{i_1 j_1-1}) \le T(\tilde{\sigma}_{i_2 j_2}) \le T(\tilde{\sigma}_{i_1 j_1+1})$ with the following convention:

- $T(\tilde{\sigma}_{i_1 0}) = 0$ if $\sigma_{i_1 j_1}$ is the first operation in the sequence of $J_{i_1}$,

- $T(\tilde{\sigma}_{i_1 n_1+2}) = +\infty$ if $\sigma_{i_1 j_1}$ is the last operation in the sequence of $J_{i_1}$.

### 4.3. Summary of the results

We build a neighbouring system by considering two basic moves with a reduction of the neighbourhood size. In this section, we verify the efficiency of this neighbouring system. For this, we compute the average value of 1000 executions of each of the 40 instances that compose our benchmark test. One execution consists in a local search method, starting from a randomly generated feasible solution (using the stochastic alternative of the construction heuristic described in section 5.1.). The duration of an execution is evaluated by counting the calls of the makespan evaluation. The results obtained are summarized in Table 2. The column ‘Average cost’ indicates the average cost of the obtained local minima. The column ‘Number of evaluations’ gives the average number of makespan computations necessary for obtaining a local minimum.

<table><caption>**Table 2.** Fast comparison of neighbouring systems</caption><thead><tr><td></td><td>Average cost</td><td>Number of evaluations</td></tr></thead><tbody><tr><td>Exchange move</td><td>135.99</td><td>1629</td></tr><tr><td>Reduced exchange move</td><td>135.84</td><td>516</td></tr><tr><td>Insertion move</td><td>131.07</td><td>3872</td></tr><tr><td>Reduced Insertion move</td><td>132.76</td><td>778</td></tr><tr><td>Combined reduced moves</td><td>125.82</td><td>1822</td></tr></tbody></table>

First, we can notice that the neighbourhood reduction significantly improves the behaviour of local search methods. Thus, for the exchange move, a local minimum is obtained three times more quickly with the same quality of local minima. For the insertion move, time is divided by a factor of 5, while a weak loss of quality (1.2%) is noted.

Concerning the combination of reduced basic moves, the quality of the local minima is improved by 7.5% compared to the exchange move, and this in a similar duration. The improvement of quality compared to the insertion move is 4% with a time divided by 2. So, the combination of reduced moves allows to improve the quality of local minima. Our objective is now to include this neighbouring system into several metaheuristics, and to evaluate the efficiency of their behaviour.
# 5. Description of the resolution methods

We focus in this section on the resolution methods used. We present first the construction heuristic we have developed, and then the metaheuristics according to the Blum and Roli (2003) formulation.

## 5.1. Construction heuristic

This greedy heuristic use the available tasks earlier defined. The basic principle is to successively schedule each available task by assigning it to a vehicle. When a task $\tilde{\sigma}_{ij}$ is completed, the set of the available tasks is updated, by replacing $\tilde{\sigma}_{ij}$ by its successor $\tilde{\sigma}_{ij+1}$, if it exists. The algorithm 2 describes the construction heuristic.

<table><thead><tr><th>Algorithm 2: Construction heuristic</th></tr></thead><tbody><tr><td>Let D = {σ̃<sub>i1</sub>, i = 1,...,n} be the initial set of available tasks</td></tr><tr><td>While D ≠ ∅ Do</td></tr><tr><td>Choose a task σ̃<sub>ij</sub> ∈ D,</td></tr><tr><td>Assign σ̃<sub>ij</sub> to a vehicle k ∈ K,</td></tr><tr><td>Let D := D / {σ̃<sub>ij</sub>},</td></tr><tr><td>If it exist let D := D ∪ {σ̃<sub>ij+1</sub>}</td></tr><tr><td>End While</td></tr></tbody></table>

Two alternatives are given for the choice of the task $\tilde{\sigma}_{ij}$ and the vehicle $k$. The first alternative (the stochastic one) builds a random feasible solution, while the second alternative (the deterministic one) tries to build a good feasible solution.

- the task is randomly chosen in $D$ and is accomplished by a randomly chosen vehicle,

- the selected task is the one corresponding to the job having the largest remaining processing time (LPT rule) and the chosen vehicle is the one that will accomplish this task in the shortest time.

## 5.2. Iterated local search methods

Iterated Local Search methods (ILS) were the subject of interesting development (Lourenço *et al.*, 2003). The principle algorithm of ILS is described in algorithm 3.

The method that we have implemented is one of the simplest forms of ILS. The initial solution (*GenerateInitialSolution*) is given by the construction heuristic (deterministic alternative) described in the previous section. The local search (*LocalSearch*) is a variable neighbourhood descent (VND) composed by the reduced exchange and insertion moves. To perturb a solution (*perturbation*), three successive exchange moves are applied,
while making sure that each of them preserves the feasibility of the current solution. The acceptance criterion (*ApplyAcceptanceCriterion*) consists in accepting the new local minimum $s'$ if and only if it is better or equal than $s^*$ (Best Walk Criterion). The stopping criterion is a maximum number of iterations arbitrarily fixed at 1000.

<table><tr><td><b>Algorithm 3</b> Iterated local search methods (ILS)</td></tr><tr><td>s<sub>0</sub> ← GenerateInitialSolution()</td></tr><tr><td>s<sup>*</sup> ← LocalSearch(s<sub>0</sub>)</td></tr><tr><td><b>While</b> stopping criterion is not met <b>Do</b></td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;s'<sub>'</sub> ← Perturbation(s<sup>*</sup>, history)</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;s''<sub>'</sub> ← LocalSearch(s'')</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;s<sup>*</sup> ← ApplyAcceptanceCriterion(s<sup>*</sup>, s''<sub>'</sub>, history)</td></tr><tr><td><b>End While</b></td></tr></table>

### 5.3. Simulated annealing

Simulated annealing (SA) is recognized to be one of the oldest metaheuristic (Kirkpatrick et al., 1983). Its principle algorithm is given in algorithm 4.

<table><tr><td><b>Algorithm 4</b> Simulated annealing (SA)</td></tr><tr><td>s ← GenerateInitialSolution()</td></tr><tr><td>T ← T<sub>0</sub></td></tr><tr><td><b>While</b> stopping criterion is not met <b>Do</b></td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;Randomly choose s' in the neighbourhood of s</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;If s' is better than s Then</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s ← s'</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;Else</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s ← s' according to a probability p(T,s,s')</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;End If</td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;Update(T)</td></tr><tr><td><b>End While</b></td></tr></table>

We recall that our main goal is to verify the efficiency of the proposed neighbouring system. As consequence, no study of the parameters space has been investigated, and we choose an empirical tuning of parameters. This choice is based on a basic cooling schedule; the temperature decreases at each iteration (as suggested first by Lundy and Mees, 1986) following a geometric law. This allows to determine the other parameters by considering some simple rules (Van Laarhoven and Aarts, 1987) as indicated just below.

An initial solution is randomly generated by the construction heuristic (stochastic alternative). In order that the final solution be independent from the starting point, the initial temperature must be hot enough. So, The parameter $T$ that simulates the temperature is initialised with $T_0 = 5$ (We have then a probability of 0.5 for accepting a deterioration of the current solution of $T_0 \times \ln(2)$ at the beginning of the cooling schedule). The stopping
temperature is arbitrarily fixed at $T_a = 10^{-3}$ (cold enough to consider that the probability for accepting a worse transition is null). As mentioned above, the temperature is a geometric sequence of common ratio $T_f$. $T_f$ is calculated so as to make a given number of iterations, which is calculated so that the same time has passed for ILS and SA methods. The probability of accepting a worse transition is given by the Boltzmann factor $\exp(-\frac{\Delta E}{T})$.

Thus tuned, experimental behaviour of simulated annealing is proven to be quite good.

### 5.4. Hybrid method simulated annealing / local search

This hybrid method consists in applying the simulated annealing, but on the (very restricted) subspace of local minima rather than to the whole space of solutions. This technique was initially proposed by (Martin and Otto, 1996) and (Desai and Patil, 1996). By analogy with GLS methods ('Genetic Local Search'), we will use the term of SALS ('Simulated Annealing Local Search') to indicate this method. The principle algorithm of SALS is contained into algorithm 3, in which the acceptance criterion is defined by the SA rules.

The adjustments are the same ones as for simulated annealing, except for the choice of the common ratio $T_f$, which is calculated so as to carry out 1000 iterations (the same ones as for ILS method).

## 6. Experiments and computational results

After the description of the benchmark test, we present the results obtained by metaheuristics. A comparison with the literature results is provided in the third part of this section.

### 6.1. Description of the benchmark test

We use the benchmark test suggested by (Bilge and Ülusoy, 1995). It is composed of 40 instances. All of them are made up of one LU station, four machines and two vehicles. The loading/unloading times are neglected compared to the transportation times. Empty moves and transportation moves are supposed to spend the same amount of time.

These instances are generated according to ten jobsets, combined with four different topologies for the workshops (see appendices A and B). Topologies are assumed to be representative of existing systems, and the jobsets include between 5 and 8 jobs, and between 13 and 21 operations to be scheduled. The name given to the instances is composed by the prefix 'Ex', followed of two numbers representing respectively the jobset and the topology. Thus, Ex53 indicates the instance generated by jobset 5 and topology 3.
Moreover, we will consider two criteria for the objective function:

- C1: to minimise the exit time of the last job of the system,

- C2: to minimise the completion time of the last job (makespan).

The C2 criterion is used in the literature and we consider it for comparison purpose. The C1 criterion takes into account, in the optimisation process, the return of the vehicles to the unloading station at the end of the schedule. Let us notice that there is a close link between these two criteria. Indeed, they both seek to minimise the completion time of the last task carried out. C1 criterion consider all the tasks $\{\tilde{\sigma}_{ij} \in \tilde{O}, i = 1..n, j = 1..n_i + 1\}$, while C2 consider only the tasks corresponding to non-fictitious operations $\{\tilde{\sigma}_{ij} \in \tilde{O}, i = 1..n, j = 1..n_i\}$. It will be expected that C1 would be more difficult, since it considers more tasks, and it is thus of higher combinatorial.

Although these instances are of relatively low size (13-21 tasks to be scheduled for C2 and 18-27 tasks for C1), they remain very difficult to solve. To date, few instances were solved in an exact way, and the best published lower bounds are of poor quality (Ulusoy *et al.*, 1997).

The best known solutions are summarised in table 3. They will be useful mainly as comparative data for the results that we present. Programs are written in language C, and tested on a Pentium 4, 3.4 GHz. CPU times is between one and four seconds per algorithm execution.

<table><caption>**Table 3.** Best known upper bound for the benchmark test</caption><thead><tr><th rowspan="2">Instances</th><th colspan="2">Criterion</th></tr><tr><th>C1</th><th>C2</th></tr></thead><tbody><tr><td>Ex11</td><td>114</td><td>96</td></tr><tr><td>Ex12</td><td>90</td><td>82</td></tr><tr><td>Ex13</td><td>98</td><td>84</td></tr><tr><td>Ex14</td><td>140</td><td>103</td></tr><tr><td>Ex21</td><td>116</td><td>100 (102)</td></tr><tr><td>Ex22</td><td>82</td><td>76</td></tr><tr><td>Ex23</td><td>89</td><td>86</td></tr><tr><td>Ex24</td><td>134</td><td>108</td></tr><tr><td>Ex31</td><td>121</td><td>99</td></tr><tr><td>Ex32</td><td>89</td><td>85</td></tr><tr><td>Ex33</td><td>96</td><td>86</td></tr><tr><td>Ex34</td><td>148</td><td>111</td></tr><tr><td>Ex41</td><td>138</td><td>112</td></tr><tr><td>Ex42</td><td>100</td><td>87 (88)</td></tr><tr><td>Ex43</td><td>102</td><td>89</td></tr><tr><td>Ex44</td><td>163</td><td>121 (126)</td></tr><tr><td>Ex51</td><td>110</td><td>87</td></tr><tr><td>Ex52</td><td>81</td><td>69</td></tr><tr><td>Ex53</td><td>89</td><td>74</td></tr><tr><td>Ex54</td><td>134</td><td>96</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Instances</th><th colspan="2">Criterion</th></tr><tr><th>C1</th><th>C2</th></tr></thead><tbody><tr><td>Ex61</td><td>129</td><td>118</td></tr><tr><td>Ex62</td><td>102</td><td>98</td></tr><tr><td>Ex63</td><td>105</td><td>103 (104)</td></tr><tr><td>Ex64</td><td>151*</td><td>120</td></tr><tr><td>Ex71</td><td>133*</td><td>111 (115)</td></tr><tr><td>Ex72</td><td>86</td><td>79</td></tr><tr><td>Ex73</td><td>93</td><td>83 (86)</td></tr><tr><td>Ex74</td><td>161</td><td>126 (127)</td></tr><tr><td>Ex81</td><td>167</td><td>161</td></tr><tr><td>Ex82</td><td>155</td><td>151</td></tr><tr><td>Ex83</td><td>155</td><td>153</td></tr><tr><td>Ex84</td><td>178</td><td>163</td></tr><tr><td>Ex91</td><td>127*</td><td>116 (117)</td></tr><tr><td>Ex92</td><td>106</td><td>102</td></tr><tr><td>Ex93</td><td>107</td><td>105</td></tr><tr><td>Ex94</td><td>149</td><td>120 (122)</td></tr><tr><td>Ex101</td><td>153</td><td>147</td></tr><tr><td>Ex102</td><td>139</td><td>135 (136)</td></tr><tr><td>Ex103</td><td>140*</td><td>138 (141)</td></tr><tr><td>Ex104</td><td>183</td><td>159</td></tr></tbody></table>

Values between brackets give the previously best published upper bound (C2 criterion only)

The * symbol means that these upper bounds have been obtained beside the experiments described in this paper
## 6.2. Comparison of the studied methods

Table 4 contains the results obtained by the deterministic construction heuristic for each instance and each criterion. Column ‘res’ indicates the makespan obtained, while the column ‘%’ gives the relative gap compared to the best known upper bound (table 3).

<table><caption>**Table 4.** Results obtained with the construction heuristic</caption><thead><tr><th rowspan="2">Instances</th><th colspan="2">C1</th><th colspan="2">C2</th><th rowspan="2">Instances</th><th colspan="2">C1</th><th colspan="2">C2</th></tr><tr><th>res</th><th>%</th><th>res</th><th>%</th><th>res</th><th>%</th><th>res</th><th>%</th></tr></thead><tbody><tr><td>Ex11</td><td>152</td><td>33.33</td><td>114</td><td>18.75</td><td>Ex61</td><td>175</td><td>35.66</td><td>138</td><td>16.95</td></tr><tr><td>Ex12</td><td>106</td><td>17.78</td><td>90</td><td>9.76</td><td>Ex62</td><td>136</td><td>33.33</td><td>122</td><td>24.49</td></tr><tr><td>Ex13</td><td>110</td><td>12.24</td><td>88</td><td>4.76</td><td>Ex63</td><td>147</td><td>40.00</td><td>124</td><td>20.39</td></tr><tr><td>Ex14</td><td>174</td><td>24.29</td><td>124</td><td>20.39</td><td>Ex64</td><td>213</td><td>41.06</td><td>143</td><td>19.17</td></tr><tr><td>Ex21</td><td>154</td><td>32.76</td><td>136</td><td>36.00</td><td>Ex71</td><td>200</td><td>50.38</td><td>140</td><td>26.13</td></tr><tr><td>Ex22</td><td>122</td><td>48.78</td><td>118</td><td>55.26</td><td>Ex72</td><td>136</td><td>58.14</td><td>110</td><td>39.24</td></tr><tr><td>Ex23</td><td>134</td><td>50.56</td><td>128</td><td>48.84</td><td>Ex73</td><td>149</td><td>60.22</td><td>111</td><td>33.73</td></tr><tr><td>Ex24</td><td>202</td><td>50.75</td><td>160</td><td>48.15</td><td>Ex74</td><td>258</td><td>60.25</td><td>160</td><td>26.98</td></tr><tr><td>Ex31</td><td>158</td><td>30.58</td><td>120</td><td>21.21</td><td>Ex81</td><td>203</td><td>21.56</td><td>197</td><td>22.36</td></tr><tr><td>Ex32</td><td>108</td><td>21.35</td><td>94</td><td>10.59</td><td>Ex82</td><td>181</td><td>16.77</td><td>177</td><td>17.22</td></tr><tr><td>Ex33</td><td>116</td><td>20.83</td><td>96</td><td>11.63</td><td>Ex83</td><td>185</td><td>19.35</td><td>183</td><td>19.61</td></tr><tr><td>Ex34</td><td>190</td><td>28.38</td><td>134</td><td>20.72</td><td>Ex84</td><td>252</td><td>41.57</td><td>219</td><td>34.36</td></tr><tr><td>Ex41</td><td>194</td><td>40.58</td><td>156</td><td>39.29</td><td>Ex91</td><td>170</td><td>33.86</td><td>141</td><td>21.55</td></tr><tr><td>Ex42</td><td>150</td><td>50.00</td><td>127</td><td>45.98</td><td>Ex92</td><td>139</td><td>31.13</td><td>125</td><td>22.55</td></tr><tr><td>Ex43</td><td>161</td><td>57.84</td><td>131</td><td>47.19</td><td>Ex93</td><td>144</td><td>34.58</td><td>127</td><td>20.95</td></tr><tr><td>Ex44</td><td>227</td><td>39.26</td><td>175</td><td>44.63</td><td>Ex94</td><td>211</td><td>41.61</td><td>154</td><td>28.33</td></tr><tr><td>Ex51</td><td>146</td><td>32.73</td><td>112</td><td>28.74</td><td>Ex101</td><td>208</td><td>35.95</td><td>184</td><td>25.17</td></tr><tr><td>Ex52</td><td>103</td><td>27.16</td><td>92</td><td>33.33</td><td>Ex102</td><td>184</td><td>32.37</td><td>180</td><td>33.33</td></tr><tr><td>Ex53</td><td>117</td><td>31.46</td><td>100</td><td>35.14</td><td>Ex103</td><td>195</td><td>39.29</td><td>182</td><td>31.88</td></tr><tr><td>Ex54</td><td>172</td><td>28.36</td><td>134</td><td>39.58</td><td>Ex104</td><td>249</td><td>36.07</td><td>199</td><td>25.16</td></tr></tbody></table>

The construction heuristic provides a mean deviation from the value of the best known solution of 36% for the C1 criterion and of 28% for the C2 criterion. These results clearly show the relative weakness of the heuristic, and the necessity of improving the obtained solutions with metaheuristics.

The metaheuristics results are presented in tables 5 (columns ‘ILS’, ‘SA’ and ‘SALS’ gives the results of the corresponding method, while the column ‘Time’ indicates the CPU time in seconds for one algorithm execution). Table 5a contains results for C1 criterion and Table 5b for C2 criterion. Values in bold type indicate that the corresponding method has found the best known upper bound. Furthermore, because SA and SALS are stochastic algorithms, 10 replications are carried out for each instance so as to limit the random influence on the results. Tables 5 give the results obtained by the best replication.

In a general way, the results obtained are homogeneous. As an example, the three methods give the same results for 34 of the 40 instances tested for the C1 criterion. In addition, ILS, SA and SALS find the best known upper bound respectively for 35, 37 and all instances. More scattered results are obtained for C2 criterion (the best known upper bound is reached respectively 22, 28 and 36 times by ILS, SA and SALS). It seems that the additional tasks make effectively the instances harder to solve.
<table><caption>**Table 5a.** Comparison of the three studied metaheuristics (C1 criterion)</caption><thead><tr><th>Instances</th><th>ILS</th><th>SA</th><th>SALS</th><th>Time (s)</th></tr></thead><tbody><tr><td>Ex11</td><td>114</td><td>114</td><td>114</td><td>1.3</td></tr><tr><td>Ex12</td><td>90</td><td>90</td><td>90</td><td>1.4</td></tr><tr><td>Ex13</td><td>98</td><td>98</td><td>98</td><td>1.4</td></tr><tr><td>Ex14</td><td>140</td><td>140</td><td>140</td><td>1.3</td></tr><tr><td>Ex21</td><td>118</td><td>118</td><td>116</td><td>2.3</td></tr><tr><td>Ex22</td><td>82</td><td>82</td><td>82</td><td>2.3</td></tr><tr><td>Ex23</td><td>90</td><td>90</td><td>89</td><td>2.2</td></tr><tr><td>Ex24</td><td>138</td><td>136</td><td>134</td><td>2.1</td></tr><tr><td>Ex31</td><td>121</td><td>121</td><td>121</td><td>2.2</td></tr><tr><td>Ex32</td><td>89</td><td>89</td><td>89</td><td>2.2</td></tr><tr><td>Ex33</td><td>96</td><td>96</td><td>96</td><td>2.1</td></tr><tr><td>Ex34</td><td>149</td><td>148</td><td>148</td><td>2.1</td></tr><tr><td>Ex41</td><td>138</td><td>138</td><td>138</td><td>2.1</td></tr><tr><td>Ex42</td><td>102</td><td>100</td><td>100</td><td>2.2</td></tr><tr><td>Ex43</td><td>106</td><td>104</td><td>102</td><td>2.1</td></tr><tr><td>Ex44</td><td>164</td><td>163</td><td>163</td><td>2.3</td></tr><tr><td>Ex51</td><td>110</td><td>110</td><td>110</td><td>1.3</td></tr><tr><td>Ex52</td><td>81</td><td>83</td><td>81</td><td>1.4</td></tr><tr><td>Ex53</td><td>89</td><td>89</td><td>89</td><td>1.4</td></tr><tr><td>Ex54</td><td>134</td><td>136</td><td>134</td><td>1.3</td></tr></tbody></table><table><thead><tr><th>Instances</th><th>ILS</th><th>SA</th><th>SALS</th><th>Time (s)</th></tr></thead><tbody><tr><td>Ex61</td><td>130</td><td>129</td><td>129</td><td>2.7</td></tr><tr><td>Ex62</td><td>102</td><td>102</td><td>102</td><td>2.5</td></tr><tr><td>Ex63</td><td>106</td><td>105</td><td>105</td><td>2.6</td></tr><tr><td>Ex64</td><td>151</td><td>151</td><td>153</td><td>2.6</td></tr><tr><td>Ex71</td><td>134</td><td>137</td><td>135</td><td>3.9</td></tr><tr><td>Ex72</td><td>90</td><td>86</td><td>86</td><td>4.0</td></tr><tr><td>Ex73</td><td>98</td><td>93</td><td>93</td><td>3.7</td></tr><tr><td>Ex74</td><td>167</td><td>163</td><td>161</td><td>3.8</td></tr><tr><td>Ex81</td><td>167</td><td>167</td><td>167</td><td>3.0</td></tr><tr><td>Ex82</td><td>155</td><td>155</td><td>155</td><td>2.4</td></tr><tr><td>Ex83</td><td>155</td><td>155</td><td>155</td><td>2.4</td></tr><tr><td>Ex84</td><td>178</td><td>178</td><td>178</td><td>3.3</td></tr><tr><td>Ex91</td><td>129</td><td>129</td><td>129</td><td>1.9</td></tr><tr><td>Ex92</td><td>106</td><td>106</td><td>106</td><td>1.9</td></tr><tr><td>Ex93</td><td>107</td><td>107</td><td>107</td><td>1.9</td></tr><tr><td>Ex94</td><td>149</td><td>150</td><td>149</td><td>1.9</td></tr><tr><td>Ex101</td><td>156</td><td>153</td><td>153</td><td>3.3</td></tr><tr><td>Ex102</td><td>140</td><td>139</td><td>139</td><td>3.1</td></tr><tr><td>Ex103</td><td>141</td><td>141</td><td>141</td><td>3.0</td></tr><tr><td>Ex104</td><td>187</td><td>184</td><td>183</td><td>3.3</td></tr></tbody></table>

<table><caption>**Table 5b.** Comparison of the three studied metaheuristics (C2 criterion)</caption><thead><tr><th>Instances</th><th>ILS</th><th>SA</th><th>SALS</th><th>Time (s)</th></tr></thead><tbody><tr><td>Ex11</td><td>96</td><td>96</td><td>96</td><td>1.3</td></tr><tr><td>Ex12</td><td>82</td><td>82</td><td>82</td><td>1.2</td></tr><tr><td>Ex13</td><td>84</td><td>84</td><td>84</td><td>1.3</td></tr><tr><td>Ex14</td><td>103</td><td>103</td><td>103</td><td>1.3</td></tr><tr><td>Ex21</td><td>100*</td><td>100*</td><td>100*</td><td>2.1</td></tr><tr><td>Ex22</td><td>76</td><td>76</td><td>76</td><td>2.0</td></tr><tr><td>Ex23</td><td>86</td><td>86</td><td>86</td><td>2.0</td></tr><tr><td>Ex24</td><td>108</td><td>108</td><td>108</td><td>2.1</td></tr><tr><td>Ex31</td><td>99</td><td>99</td><td>99</td><td>2.0</td></tr><tr><td>Ex32</td><td>85</td><td>85</td><td>85</td><td>1.9</td></tr><tr><td>Ex33</td><td>86</td><td>86</td><td>86</td><td>1.9</td></tr><tr><td>Ex34</td><td>111</td><td>111</td><td>111</td><td>2.1</td></tr><tr><td>Ex41</td><td>112</td><td>112</td><td>112</td><td>2.1</td></tr><tr><td>Ex42</td><td>88</td><td>88</td><td>87*</td><td>2.1</td></tr><tr><td>Ex43</td><td>89</td><td>89</td><td>89</td><td>2.1</td></tr><tr><td>Ex44</td><td>121*</td><td>125*</td><td>121*</td><td>2.0</td></tr><tr><td>Ex51</td><td>87</td><td>87</td><td>87</td><td>1.3</td></tr><tr><td>Ex52</td><td>69</td><td>69</td><td>69</td><td>1.3</td></tr><tr><td>Ex53</td><td>74</td><td>74</td><td>74</td><td>1.3</td></tr><tr><td>Ex54</td><td>96</td><td>96</td><td>96</td><td>1.3</td></tr></tbody></table><table><thead><tr><th>Instances</th><th>ILS</th><th>SA</th><th>SALS</th><th>Time (s)</th></tr></thead><tbody><tr><td>Ex61</td><td>118</td><td>118</td><td>118</td><td>2.5</td></tr><tr><td>Ex62</td><td>98</td><td>98</td><td>98</td><td>2.3</td></tr><tr><td>Ex63</td><td>103*</td><td>103*</td><td>103*</td><td>2.4</td></tr><tr><td>Ex64</td><td>120</td><td>120</td><td>120</td><td>2.5</td></tr><tr><td>Ex71</td><td>111*</td><td>111*</td><td>111*</td><td>3.9</td></tr><tr><td>Ex72</td><td>79</td><td>79</td><td>79</td><td>3.8</td></tr><tr><td>Ex73</td><td>84*</td><td>83*</td><td>83*</td><td>3.6</td></tr><tr><td>Ex74</td><td>126*</td><td>126*</td><td>126*</td><td>3.9</td></tr><tr><td>Ex81</td><td>161</td><td>161</td><td>161</td><td>2.6</td></tr><tr><td>Ex82</td><td>151</td><td>151</td><td>151</td><td>2.3</td></tr><tr><td>Ex83</td><td>153</td><td>153</td><td>153</td><td>2.3</td></tr><tr><td>Ex84</td><td>163</td><td>163</td><td>163</td><td>2.9</td></tr><tr><td>Ex91</td><td>116*</td><td>116*</td><td>116*</td><td>1.8</td></tr><tr><td>Ex92</td><td>102</td><td>102</td><td>102</td><td>1.8</td></tr><tr><td>Ex93</td><td>105</td><td>105</td><td>105</td><td>1.8</td></tr><tr><td>Ex94</td><td>120*</td><td>120*</td><td>120*</td><td>1.8</td></tr><tr><td>Ex101</td><td>148</td><td>147</td><td>147</td><td>3.0</td></tr><tr><td>Ex102</td><td>135*</td><td>135*</td><td>135*</td><td>2.9</td></tr><tr><td>Ex103</td><td>139*</td><td>139*</td><td>138*</td><td>2.9</td></tr><tr><td>Ex104</td><td>160</td><td>159</td><td>159</td><td>3.1</td></tr></tbody></table>

The * symbol indicates new upper bounds.

In order to have more information about the robustness of SA and SALS, we give in table 6 the best, the worst and the average of all the replications for the two criteria.

We can notice that most of the execution of SALS leads to very good solutions (on average, a replication is at 0.34% of the best obtained replication for the C2 criterion, and 0.96% for the C1 criterion), while the results of SA are more scattered (we obtain respectively 1.47% for C2 and 2.67% for C1). If the best replications of SALS and SA are close (respectively 108.48 against 108.63 for C2 criterion, 124.00 against 124.38 for C1), there is a significant difference about their average replication (108.85 against 110.23 for C2 criterion, 125.19 against 127.70 for C1)
So, we can conclude that SALS is an effective method for the studied problem. In the next section, we compare it with methods proposed in the literature.

<table><caption>**Table 6. Robustness of SA and SALS**</caption><thead><tr><th rowspan="3">Instances</th><th colspan="9">C1 criterion</th><th colspan="9">C2 criterion</th></tr><tr><th colspan="3">SALS</th><th colspan="3">SA</th><th colspan="3">SALS</th><th colspan="3">SA</th></tr><tr><th>Min</th><th>Max</th><th>Avg</th><th>Min</th><th>Max</th><th>Avg</th><th>Min</th><th>Max</th><th>Avg</th><th>Min</th><th>Max</th><th>Avg</th></tr></thead><tbody><tr><td>Ex11</td><td>114</td><td>116</td><td>114.6</td><td>114</td><td>126</td><td>118.6</td><td>96</td><td>96</td><td>96.0</td><td>96</td><td>97</td><td>96.2</td></tr><tr><td>Ex12</td><td>90</td><td>92</td><td>90.2</td><td>90</td><td>94</td><td>91.5</td><td>82</td><td>82</td><td>82.0</td><td>82</td><td>82</td><td>82.0</td></tr><tr><td>Ex13</td><td>98</td><td>98</td><td>98</td><td>98</td><td>102</td><td>99.9</td><td>84</td><td>84</td><td>84.0</td><td>84</td><td>86</td><td>84.8</td></tr><tr><td>Ex14</td><td>140</td><td>142</td><td>141.4</td><td>140</td><td>148</td><td>144.9</td><td>103</td><td>103</td><td>103.0</td><td>103</td><td>106</td><td>104.3</td></tr><tr><td>Ex21</td><td>116</td><td>120</td><td>117.8</td><td>118</td><td>125</td><td>120.7</td><td>100</td><td>102</td><td>100.2</td><td>100</td><td>107</td><td>103.2</td></tr><tr><td>Ex22</td><td>82</td><td>84</td><td>82.2</td><td>82</td><td>90</td><td>83.7</td><td>76</td><td>77</td><td>76.1</td><td>76</td><td>77</td><td>76.1</td></tr><tr><td>Ex23</td><td>89</td><td>92</td><td>89.9</td><td>90</td><td>94</td><td>91.8</td><td>86</td><td>86</td><td>86.0</td><td>86</td><td>86</td><td>86.0</td></tr><tr><td>Ex24</td><td>134</td><td>140</td><td>138.4</td><td>136</td><td>148</td><td>142</td><td>108</td><td>108</td><td>108.0</td><td>108</td><td>113</td><td>108.9</td></tr><tr><td>Ex31</td><td>121</td><td>128</td><td>123.2</td><td>121</td><td>129</td><td>125.8</td><td>99</td><td>99</td><td>99.0</td><td>99</td><td>106</td><td>101.8</td></tr><tr><td>Ex32</td><td>89</td><td>89</td><td>89</td><td>89</td><td>97</td><td>92.6</td><td>85</td><td>85</td><td>85.0</td><td>85</td><td>86</td><td>85.1</td></tr><tr><td>Ex33</td><td>96</td><td>100</td><td>97</td><td>96</td><td>102</td><td>99.5</td><td>86</td><td>86</td><td>86.0</td><td>86</td><td>86</td><td>86.0</td></tr><tr><td>Ex34</td><td>148</td><td>153</td><td>149.9</td><td>148</td><td>162</td><td>155.3</td><td>111</td><td>112</td><td>111.8</td><td>111</td><td>116</td><td>112.8</td></tr><tr><td>Ex41</td><td>138</td><td>140</td><td>138.6</td><td>138</td><td>144</td><td>140.8</td><td>112</td><td>115</td><td>113.2</td><td>112</td><td>123</td><td>117.8</td></tr><tr><td>Ex42</td><td>100</td><td>104</td><td>101.4</td><td>100</td><td>112</td><td>103.3</td><td>87</td><td>90</td><td>88.6</td><td>88</td><td>95</td><td>90.7</td></tr><tr><td>Ex43</td><td>102</td><td>107</td><td>104.7</td><td>104</td><td>112</td><td>107.7</td><td>89</td><td>93</td><td>89.5</td><td>89</td><td>95</td><td>91.5</td></tr><tr><td>Ex44</td><td>163</td><td>166</td><td>164.3</td><td>163</td><td>175</td><td>169.9</td><td>121</td><td>126</td><td>122.7</td><td>125</td><td>134</td><td>128.7</td></tr><tr><td>Ex51</td><td>110</td><td>110</td><td>110</td><td>110</td><td>118</td><td>112.5</td><td>87</td><td>87</td><td>87.0</td><td>87</td><td>91</td><td>88.6</td></tr><tr><td>Ex52</td><td>81</td><td>81</td><td>81</td><td>83</td><td>86</td><td>84.0</td><td>69</td><td>69</td><td>69.0</td><td>69</td><td>69</td><td>69.0</td></tr><tr><td>Ex53</td><td>89</td><td>91</td><td>89.6</td><td>89</td><td>97</td><td>92.2</td><td>74</td><td>75</td><td>74.2</td><td>74</td><td>76</td><td>75.4</td></tr><tr><td>Ex54</td><td>134</td><td>138</td><td>136.2</td><td>136</td><td>151</td><td>141.4</td><td>96</td><td>97</td><td>96.2</td><td>96</td><td>105</td><td>98.6</td></tr><tr><td>Ex61</td><td>129</td><td>133</td><td>131.1</td><td>129</td><td>137</td><td>133.8</td><td>118</td><td>118</td><td>118.0</td><td>118</td><td>124</td><td>120.1</td></tr><tr><td>Ex62</td><td>102</td><td>105</td><td>103.2</td><td>102</td><td>108</td><td>103.9</td><td>98</td><td>100</td><td>98.2</td><td>98</td><td>98</td><td>98.0</td></tr><tr><td>Ex63</td><td>105</td><td>107</td><td>105.6</td><td>105</td><td>109</td><td>107</td><td>103</td><td>104</td><td>103.3</td><td>103</td><td>105</td><td>104.5</td></tr><tr><td>Ex64</td><td>153</td><td>156</td><td>155</td><td>151</td><td>164</td><td>156.8</td><td>120</td><td>123</td><td>120.6</td><td>120</td><td>130</td><td>124.8</td></tr><tr><td>Ex71</td><td>135</td><td>140</td><td>136.4</td><td>137</td><td>144</td><td>140.0</td><td>111</td><td>114</td><td>111.8</td><td>111</td><td>118</td><td>114.4</td></tr><tr><td>Ex72</td><td>86</td><td>91</td><td>89.1</td><td>86</td><td>94</td><td>89.1</td><td>79</td><td>80</td><td>79.3</td><td>79</td><td>82</td><td>80.0</td></tr><tr><td>Ex73</td><td>93</td><td>98</td><td>94.5</td><td>93</td><td>107</td><td>96.9</td><td>83</td><td>85</td><td>83.4</td><td>83</td><td>90</td><td>85.8</td></tr><tr><td>Ex74</td><td>161</td><td>167</td><td>163.7</td><td>163</td><td>173</td><td>168.6</td><td>126</td><td>128</td><td>126.6</td><td>126</td><td>135</td><td>128.9</td></tr><tr><td>Ex81</td><td>167</td><td>167</td><td>167</td><td>167</td><td>169</td><td>167.4</td><td>161</td><td>161</td><td>161.0</td><td>161</td><td>161</td><td>161.0</td></tr><tr><td>Ex82</td><td>155</td><td>155</td><td>155</td><td>155</td><td>155</td><td>155</td><td>151</td><td>151</td><td>151.0</td><td>151</td><td>151</td><td>151.0</td></tr><tr><td>Ex83</td><td>155</td><td>155</td><td>155</td><td>155</td><td>155</td><td>155</td><td>153</td><td>153</td><td>153.0</td><td>153</td><td>153</td><td>153.0</td></tr><tr><td>Ex84</td><td>178</td><td>179</td><td>178.1</td><td>178</td><td>188</td><td>182.6</td><td>163</td><td>163</td><td>163.0</td><td>163</td><td>163</td><td>163.0</td></tr><tr><td>Ex91</td><td>129</td><td>130</td><td>129.4</td><td>129</td><td>136</td><td>132.6</td><td>116</td><td>117</td><td>116.4</td><td>116</td><td>122</td><td>118.0</td></tr><tr><td>Ex92</td><td>106</td><td>106</td><td>106</td><td>106</td><td>109</td><td>107.3</td><td>102</td><td>102</td><td>102.0</td><td>102</td><td>104</td><td>103.0</td></tr><tr><td>Ex93</td><td>107</td><td>110</td><td>107.3</td><td>107</td><td>110</td><td>108.4</td><td>105</td><td>105</td><td>105.0</td><td>105</td><td>108</td><td>106.2</td></tr><tr><td>Ex94</td><td>149</td><td>151</td><td>149.7</td><td>150</td><td>159</td><td>152.8</td><td>120</td><td>123</td><td>121.8</td><td>120</td><td>126</td><td>123.0</td></tr><tr><td>Ex101</td><td>153</td><td>159</td><td>155.7</td><td>153</td><td>163</td><td>158.1</td><td>147</td><td>151</td><td>147.8</td><td>147</td><td>154</td><td>148.5</td></tr><tr><td>Ex102</td><td>139</td><td>141</td><td>139.6</td><td>139</td><td>142</td><td>140.1</td><td>135</td><td>137</td><td>135.2</td><td>135</td><td>138</td><td>135.9</td></tr><tr><td>Ex103</td><td>141</td><td>143</td><td>141.6</td><td>141</td><td>145</td><td>142.4</td><td>138</td><td>141</td><td>139.5</td><td>139</td><td>144</td><td>140.9</td></tr><tr><td>Ex104</td><td>183</td><td>190</td><td>187.0</td><td>184</td><td>197</td><td>192</td><td>159</td><td>161</td><td>159.6</td><td>159</td><td>167</td><td>161.8</td></tr><tr><td>Average</td><td>124.00</td><td>126.85</td><td>125.19</td><td>124.38</td><td>131.90</td><td>127.70</td><td>108.48</td><td>109.73</td><td>108.85</td><td>108.63</td><td>112.73</td><td>110.23</td></tr></tbody></table>

## 6.3. Comparison with the literature

Table 7 summarizes the best results obtained for C2 criterion (the only one studied in the literature):

(i) by a synthesis of three papers ((Ülusoy and Bilge, 1993), (Bilge and Ülusoy, 1995) and (Ülusoy et al., 1997)) (B&U),

(ii) by the genetic algorithm of (Abdelmaguid et al., 2004) (GAA),
(iii) by our hybrid metaheuristic SALS.

A performance criterion indicates, for each method, the relative gap compared to the best published upper bound (indicated in bold type). The new upper bounds we have obtained are marked with the * symbol.

<table><caption>**Table 7.** Summary of the literature results (C2 criterion)</caption><thead><tr><th>Inst.</th><th colspan="2">B&U</th><th colspan="2">GAA</th><th colspan="2">SALS</th></tr></thead><tbody><tr><td>Ex11</td><td>96</td><td>0.00</td><td>96</td><td>0.00</td><td>96</td><td>0.00</td></tr><tr><td>Ex12</td><td>82</td><td>0.00</td><td>82</td><td>0.00</td><td>82</td><td>0.00</td></tr><tr><td>Ex13</td><td>84</td><td>0.00</td><td>84</td><td>0.00</td><td>84</td><td>0.00</td></tr><tr><td>Ex14</td><td>103</td><td>0.00</td><td>103</td><td>0.00</td><td>103</td><td>0.00</td></tr><tr><td>Ex21</td><td>104</td><td>1.96</td><td>102</td><td>0.00</td><td>100* -1.96</td><td></td></tr><tr><td>Ex22</td><td>76</td><td>0.00</td><td>76</td><td>0.00</td><td>76</td><td>0.00</td></tr><tr><td>Ex23</td><td>86</td><td>0.00</td><td>86</td><td>0.00</td><td>86</td><td>0.00</td></tr><tr><td>Ex24</td><td>113</td><td>4.63</td><td>108</td><td>0.00</td><td>108</td><td>0.00</td></tr><tr><td>Ex31</td><td>105</td><td>6.06</td><td>99</td><td>0.00</td><td>99</td><td>0.00</td></tr><tr><td>Ex32</td><td>85</td><td>0.00</td><td>85</td><td>0.00</td><td>85</td><td>0.00</td></tr><tr><td>Ex33</td><td>86</td><td>0.00</td><td>86</td><td>0.00</td><td>86</td><td>0.00</td></tr><tr><td>Ex34</td><td>113</td><td>1.80</td><td>111</td><td>0.00</td><td>111</td><td>0.00</td></tr><tr><td>Ex41</td><td>116</td><td>3.57</td><td>112</td><td>0.00</td><td>112</td><td>0.00</td></tr><tr><td>Ex42</td><td>88</td><td>0.00</td><td>88</td><td>0.00</td><td>87* -1.14</td><td></td></tr><tr><td>Ex43</td><td>91</td><td>2.25</td><td>89</td><td>0.00</td><td>89</td><td>0.00</td></tr><tr><td>Ex44</td><td>126</td><td>0.00</td><td>126</td><td>0.00</td><td>121* -3.97</td><td></td></tr><tr><td>Ex51</td><td>87</td><td>0.00</td><td>87</td><td>0.00</td><td>87</td><td>0.00</td></tr><tr><td>Ex52</td><td>69</td><td>0.00</td><td>69</td><td>0.00</td><td>69</td><td>0.00</td></tr><tr><td>Ex53</td><td>75</td><td>1.35</td><td>74</td><td>0.00</td><td>74</td><td>0.00</td></tr><tr><td>Ex54</td><td>97</td><td>1.04</td><td>96</td><td>0.00</td><td>96</td><td>0.00</td></tr></tbody></table><table><thead><tr><th>Inst.</th><th colspan="2">B&U</th><th colspan="2">GAA</th><th colspan="2">SALS</th></tr></thead><tbody><tr><td>Ex61</td><td>121</td><td>2.54</td><td>118</td><td>0.00</td><td>118</td><td>0.00</td></tr><tr><td>Ex62</td><td>98</td><td>0.00</td><td>98</td><td>0.00</td><td>98</td><td>0.00</td></tr><tr><td>Ex63</td><td>104</td><td>0.00</td><td>104</td><td>0.00</td><td>103* -0.96</td><td></td></tr><tr><td>Ex64</td><td>123</td><td>2.50</td><td>120</td><td>0.00</td><td>120</td><td>0.00</td></tr><tr><td>Ex71</td><td>118</td><td>2.61</td><td>115</td><td>0.00</td><td>111* -3.48</td><td></td></tr><tr><td>Ex72</td><td>85</td><td>7.59</td><td>79</td><td>0.00</td><td>79</td><td>0.00</td></tr><tr><td>Ex73</td><td>88</td><td>2.33</td><td>86</td><td>0.00</td><td>83* -3.49</td><td></td></tr><tr><td>Ex74</td><td>128</td><td>0.79</td><td>127</td><td>0.00</td><td>126* -0.79</td><td></td></tr><tr><td>Ex81</td><td>161</td><td>0.00</td><td>161</td><td>0.00</td><td>161</td><td>0.00</td></tr><tr><td>Ex82</td><td>151</td><td>0.00</td><td>151</td><td>0.00</td><td>151</td><td>0.00</td></tr><tr><td>Ex83</td><td>153</td><td>0.00</td><td>153</td><td>0.00</td><td>153</td><td>0.00</td></tr><tr><td>Ex84</td><td>163</td><td>0.00</td><td>163</td><td>0.00</td><td>163</td><td>0.00</td></tr><tr><td>Ex91</td><td>117</td><td>0.00</td><td>118</td><td>0.85</td><td>116* -0.85</td><td></td></tr><tr><td>Ex92</td><td>102</td><td>0.00</td><td>104</td><td>1.96</td><td>102</td><td>0.00</td></tr><tr><td>Ex93</td><td>105</td><td>0.00</td><td>106</td><td>0.95</td><td>105</td><td>0.00</td></tr><tr><td>Ex94</td><td>123</td><td>0.82</td><td>122</td><td>0.00</td><td>120* -1.64</td><td></td></tr><tr><td>Ex101</td><td>150</td><td>2.04</td><td>147</td><td>0.00</td><td>147</td><td>0.00</td></tr><tr><td>Ex102</td><td>137</td><td>0.74</td><td>136</td><td>0.00</td><td>135* -0.74</td><td></td></tr><tr><td>Ex103</td><td>143</td><td>1.42</td><td>141</td><td>0.00</td><td>138* -2.13</td><td></td></tr><tr><td>Ex104</td><td>164</td><td>3.14</td><td>159</td><td>0.00</td><td>159</td><td>0.00</td></tr></tbody></table>

These results clearly show the superiority of SALS. Our method always finds a result at least as good as those so far published. Moreover, new upper bounds are found for 11 of the 40 instances. SALS finds better solutions than B&U for 23 instances, and than GAA for 13 instances. The improvements are sometimes significant; a solution of cost 111 is obtained against 115 for Ex71 instance, that is to say a relative gain of 3.6 % (figure 5 shows, using a Gantt chart representation, the solutions obtained for Ex71 with each of the two criteria).

Still more than quality of the solutions obtained, it is the frequency of obtaining the best results which is most impressive, and this in extremely reasonable computing times for an optimisation problem (about a few seconds).

The behaviour of the method lets suggest that the proposed solutions must be for many the optimal ones. This remark still increases the interest of the C1 criterion, which makes the instances more difficult to solve. Even if there are only few additional transports to schedule, we notice that SALS loses in robustness for these ‘new’ instances (see table 6), and does not systematically find the best solutions (for at least four instances). These results might constitute a new reference for future studies, more able to measure the quality of the methods.
<figure><img src="image_2.png" /><figcaption>**Figures 5a and 5b.** Gantt charts of the best known solutions for Ex71 instance (C1 and C2 criteria). The two Gantt charts show the machining of the 8 jobs (numbered from A to H) on the machines (numbered from M1 to M4). On the figure 5a, the unloading station LU allows to point out, for each job, its exit date of the system. The schedule of the vehicles (AGV1 and AGV2) gives the origin machine, the destination machine, and, if non-empty, the transported job.</figcaption></figure>

# 7. Conclusion and further works

In this paper, we propose a new effective representation solution for the job-shop problem with transportation. A powerful neighbouring system is described and implemented with three different metaheuristics. The results obtained clearly show the relevance of this approach. Whatever the method used, the presented results are always better or at least equal to those of the literature. one of these methods, SALS, combines robustness with quality, and is a particularly efficient method for this problem.

Also, we propose a new criterion for the solution evaluation, which allows to extend the literature benchmark test with more challenging instances.

Many perspectives can be drawn from this work.

Concerning the studied problem, the benchmark test proposed by (Bilge and Ülusoy, 1995) seems out-of-date, and it would have to be extended by more difficult instances. Concurrently to this extension, and paradoxically, the exact resolution of most of these instances is still today out of reach, and constitutes an always topical orientation research.

The consideration of online dispatching rules leads to define a more difficult makespan evaluation, which can require the use of discrete event simulation. Combining simulation with optimization methods can be a very interesting perspective to our work.
Lastly, the methods used in this paper are trajectory metaheuristics. The fact of carrying out several replications, and of keeping in memory the solution obtained by the best of them, can be seen like the use of a population method, in which the individuals are private of any possibility of communicating. Restoring this possibility (by using a population method, like a genetic algorithm) may allow to improve the results proposed in this paper.

# 8. Appendixes

## 8.1. Appendix A: The jobsets

For each job, the sequence of machines to be visited is given. The processing time is indicated in brackets.

**Jobset 1:**

Job 1: M1(8); M2(16); M4(12)
Job 2: M1(20); M3(10); M2(18)
Job 3: M3(12); M4(8); M1(15)
Job 4: M4(14); M2(18)
Job 5: M3(10); M1(15)

**Jobset 2:**

Job 1: M1(10); M4(18)
Job 2: M2(10); M4(18)
Job 3: M1(10); M3(20)
Job 4: M2(10); M3(15); M4(12)
Job 5: M1(10); M2(15); M4(12)
Job 6: M1(10); M2(15); M3(12)

**Jobset 3:**

Job 1: M1(16); M3(15)
Job 2: M2(18); M4(15)
Job 3: M1(20); M2(10)
Job 4: M3(15); M4(10)
Job 5: M1(8); M2(10); M3(15); M4(17)
Job 6: M2(10); M3(15); M4(8); M1(15)

**Jobset 4:**

Job 1: M4(11); M1(10); M2(7)
Job 2: M3(12); M2(10); M4(8)
Job 3: M2(7); M3(10); M1(9); M3(8)
Job 4: M2(7); M4(8); M1(12); M2(6)
Job 5: M1(9); M2(7); M4(8); M2(10); M3(8)

**Jobset 5:**

Job 1: M1(6); M2(12); M4(9)
Job 2: M1(18); M3(6); M2(15)
Job 3: M3(9); M4(3); M1(12)
Job 4: M4(6); M2(15)
Job 5: M3(3); M1(9);

**Jobset 6:**

Job 1: M1(9); M2(11); M4(7)
Job 2: M1(19); M2(20); M4(13)
Job 3: M2(14); M3(20); M4(9)
Job 4: M2(14); M3(20); M4(9)
Job 5: M1(11); M3(16); M4(8)
Job 6: M1(10); M3(12); M4(10)

**Jobset 7:**

Job 1: M1(6); M4(6)
Job 2: M2(11); M4(9)
Job 3: M2(9); M4(7)
Job 4: M3(16); M4(7)
Job 5: M1(9); M3(18)
Job 6: M2(13); M3(19); M4(6)
Job 7: M1(10); M2(9); M3(13)
Job 8: M1(11); M2(9); M4(8)

**Jobset 8:**

Job 1: M2(12); M3(21); M4(11)
Job 2: M2(12); M3(21); M4(11)
Job 3: M2(12); M3(21); M4(11)
Job 4: M2(12); M3(21); M4(11)
Job 5: M1(10); M2(14); M3(18); M4(9)
Job 6: M1(10); M2(14); M3(18); M4(9)

**Jobset 9:**

Job 1: M3(9); M1(12); M2(9); M4(6)
Job 2: M3(16); M2(11); M4(9)
Job 3: M1(21); M2(18); M4(7)
Job 4: M2(20); M3(22); M4(11)
Job 5: M3(14); M1(16); M2(13); M4(9)

**Jobset 10:**

Job 1: M1(11); M3(19); M2(16); M4(13)
Job 2: M2(21); M3(16); M4(14)
Job 3: M3(8); M2(10); M1(14); M4(9)
Job 4: M2(13); M3(20); M4(10)
Job 5: M1(9); M3(16); M4(18)
Job 6: M2(19); M1(21); M3(11); M4(15)
## 8.2. Appendix B: The topologies

The transport times to go from any machine to another one is given in the following matrix:

<table><thead><tr><th>FMS1</th><th>LU</th><th>M1</th><th>M2</th><th>M3</th><th>M4</th></tr></thead><tbody><tr><th>LU</th><td>0</td><td>6</td><td>8</td><td>10</td><td>12</td></tr><tr><th>M1</th><td>12</td><td>0</td><td>6</td><td>8</td><td>10</td></tr><tr><th>M2</th><td>10</td><td>6</td><td>0</td><td>6</td><td>8</td></tr><tr><th>M3</th><td>8</td><td>8</td><td>6</td><td>0</td><td>6</td></tr><tr><th>M4</th><td>6</td><td>10</td><td>8</td><td>6</td><td>0</td></tr></tbody></table>

<table><thead><tr><th>FMS2</th><th>LU</th><th>M1</th><th>M2</th><th>M3</th><th>M4</th></tr></thead><tbody><tr><th>LU</th><td>0</td><td>4</td><td>6</td><td>8</td><td>6</td></tr><tr><th>M1</th><td>6</td><td>0</td><td>2</td><td>4</td><td>2</td></tr><tr><th>M2</th><td>8</td><td>12</td><td>0</td><td>2</td><td>4</td></tr><tr><th>M3</th><td>6</td><td>10</td><td>12</td><td>0</td><td>2</td></tr><tr><th>M4</th><td>4</td><td>8</td><td>10</td><td>12</td><td>0</td></tr></tbody></table>

<table><thead><tr><th>FMS3</th><th>LU</th><th>M1</th><th>M2</th><th>M3</th><th>M4</th></tr></thead><tbody><tr><th>LU</th><td>0</td><td>2</td><td>4</td><td>10</td><td>12</td></tr><tr><th>M1</th><td>12</td><td>0</td><td>2</td><td>8</td><td>10</td></tr><tr><th>M2</th><td>10</td><td>12</td><td>0</td><td>6</td><td>8</td></tr><tr><th>M3</th><td>4</td><td>6</td><td>8</td><td>0</td><td>2</td></tr><tr><th>M4</th><td>2</td><td>4</td><td>6</td><td>12</td><td>0</td></tr></tbody></table>

<table><thead><tr><th>FMS4</th><th>LU</th><th>M1</th><th>M2</th><th>M3</th><th>M4</th></tr></thead><tbody><tr><th>LU</th><td>0</td><td>4</td><td>8</td><td>10</td><td>14</td></tr><tr><th>M1</th><td>18</td><td>0</td><td>4</td><td>6</td><td>10</td></tr><tr><th>M2</th><td>20</td><td>14</td><td>0</td><td>8</td><td>6</td></tr><tr><th>M3</th><td>12</td><td>8</td><td>6</td><td>0</td><td>6</td></tr><tr><th>M4</th><td>14</td><td>14</td><td>12</td><td>6</td><td>0</td></tr></tbody></table>

## 9. REFERENCES

Abdelmaguid, T.F., Nassef, O.N., Kamal, B.A., Hassan, M.F., 2004, A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles. *International Journal of Production Research*, 42, 267-281.

Bilge, Ü., and Ülusoy, G., 1995 A time window approach to simultaneous scheduling of machines and material handling system in a FMS. *Operation Research*, 43, 1058-1070.

Blazewicz, J., Eiselt, H.A., Finke, G., Laporte, G., Weglartz, J., 1991, Scheduling tasks and vehicles in a flexible manufacturing system. *International Journal of Flexible Manufacturing System*, 4, 5-16.

Blum, C., and Roli, A., 2003, Metaheuristics in combinatorial optimisation: overview and conceptual comparison. *ACM Computing Surveys*, 35, 268-308.

Brucker, P., 2001, Scheduling Algorithms, Third edition, Springer-Verlag, Berlin.

Deroussi, L., 2002, Heuristiques, métaheuristiques et systèmes de voisinage : application à des problèmes théoriques et industriels de type TSP et ordonnancement. Ph. D. Thesis (in French), University of Clermont-Ferrand II, France.

Desai, R., and Patil, R., 1996, SALO: Combining simulated annealing and local optimisation for efficient global optimisation. Technical Report LA-UR, available at http://citeseer.nj.nec.com/desai96salo.html.

Egbelu, P.J., and Tanchoco, J.M.A., 1984, Characterisation of automated guided vehicle dispatching rules. *International Journal of Production Research*, 22, 359-374.

Ganesharajah, T., Hall, N.G., Sriskandarajah, C., 1998, Design and Operational Issues in AGV-Served Manufacturing Systems, *Annals of Operations Research*, 76, 109-154.
Gobal, S.L., and Kasilingam, R.G., 1991, A simulation model for estimating vehicle requirements in automated guided vehicle systems, *Computers Industrial Engg*, 21, 623-627.

Graham, R.L., Lawler, E.L., Lenstra J.K., Rinnooy Kan., A.H.G., 1979, Optimisation and approximation in deterministic sequencing and scheduling: a survey. *Annals of Discrete Mathematics*, 5, 236-287.

Hansen, P., and Mladenovic, N., 2003, Variable Neighborhood search. In F. Glover and G. Kochenberger (eds.), *Handbook of Metaheuristics*, Kluwers Academic Publishers, 145-184.

Hurink, J.L., and Knust, S., 2002, Tabu Search algorithm for scheduling a single robot in a job-shop environment. *Discrete Applied Mathematics*, 119, 181-203.

Kirkpatrick, S., Velatt, C.D. Vecchi, M.P., 1983, Optimisation by simulated annealing. *Sciences*, 222, 671-680.

Knust, S., 1999, Shop-Scheduling Problems with Transportation, Ph. D. Thesis, Fachbereich Mathematik/Informatik Universität Osnabrück.

Le-Anh, T., and De Koster, M.B.M., 2005, On-line dispatching rules for vehicle-based internal transport systems, *International Journal of Production Research*, 43, 1711-1728.

Le-Anh, T., and De Koster, M.B.M., 2006, A review of design and control of automated guided vehicle systems, *European Journal of Operational Research*, 121, 1-23.

Lenstra, J.K., and Rinnooy Kan, A.H.G., 1979, Computational complexity of discrete optimization problems. *Annals of Discrete Mathematics* 4, 121-140.

Lenstra, J.K., and Rinnooy Kan, A.H.G., 1981, Complexity of vehicle routing and scheduling problems, *Networks* 11, 221-227.

Lourenço, H.R., Martin, O.C., Stützle, T., 2003, Iterated local search. In F. Glover and G. Kochenberger (eds.), *Handbook of Metaheuristics*, Kluwers Academic Publishers, 321-353.

Lundy, M., and Mees, A., 1986, Convergence of an annealing algorithm, *Mathematical Programming*, 34, 111-124.

Martin, O.C., and Otto, S.W., 1996, Combining simulated annealing with local search heuristics. *Annals of Operations Research*, 63, 57-75.

Mladenovic, N., and Hansen, P., 1997; Variable Neighborhood Search. *Computers & Operations Research*, 24, 1097-1100.

Nuhut, O., 1999, Scheduling of Automated Guided Vehicles. Available at http://citeseer.nj.nec.com/nuhut99scheduling.html

Qiu, L., Hsu, W., Huang, S.Y., Wang, H., 2002, Scheduling and routing algorithms for AGVs: a survey, *International Journal of Production Research*, 40, 745-760.
Raman, N., Talbot, F.B., Rachamadgu, R.V., 1986, Simultaneous scheduling of machines and material handling devices in automated manufacturing. In Proceedings of the 2nd ORSA/TIMS Conference on Flexible Manufacturing Systems, pp. 455-466.

Revielotis, S.A., 2000, Conflict resolution in AGV systems. *IIE Transactions*, 647-659.

Soylu, M., Özdemirel, N.E., Kayaligil, S., 2000, A self-organising neural network approach for the single AGV routing problem. *European Journal of Operational Research*, 121, 124-137.

Tian, P., Ma, J., Zhang, D.M., 1999, Application of the simulated annealing algorithm to the combinatorial optimisation problem with permutation property: an investigation of generation mechanism. *European Journal of Operational Research*, 118, 81-94.

Ülusoy, G., and Bilge, Ü., 1993, Simultaneous scheduling of machines and automated guided vehicles. *International Journal of Production Research*, 31, 2857-2873.

Ülusoy, G., Sivrikaya-Serifoglu, F., Bilge, Ü., 1997, A genetic algorithm approach to the simultaneous scheduling of stations and automated guided vehicles. *Computers Operations Research*, 24, 335-351.

Van Laarhoven, P.J.M., and Aarts, E.H.L., 1987, Simulated Annealing: Theory and Applications, Kluwer Academic Publishers, Berlin.