# Minimizing total travel time in the flexible job-shop scheduling problem with transportation resources

Lucas Berterottière, Stéphane Dauzère-Pérès, Claude Yugma, Kwei-Long Huang

► To cite this version:

Lucas Berterottière, Stéphane Dauzère-Pérès, Claude Yugma, Kwei-Long Huang. Minimizing total travel time in the flexible job-shop scheduling problem with transportation resources. European Journal of Operational Research, 2025, 312, pp.890-909. 10.1016/j.ejor.2025.11.020. hal-05409040

HAL Id: hal-05409040

https://hal.science/hal-05409040v1

Submitted on 10 Dec 2025

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>
<figure><img src="image_2.png" /></figure>

Innovative Applications of O.R.

# Minimizing total travel time in the flexible job-shop scheduling problem with transportation resources

Lucas Berterottière ID a,b,*, Stéphane Dauzère-Pérès ID a,c, Claude Yugma ID a,
Kwei-Long Huang ID d

## ARTICLE INFO

### Keywords:

Scheduling

Flexible job-shop scheduling

Transportation resources

Total travel time

Neighborhood structures

## ABSTRACT

Time-dependent manufacturing criteria, such as makespan or mean flow time, are commonly optimized in scheduling problems. Prioritizing these criteria is motivated by their correlation with key performance indicators, such as throughput and cycle time in flexible manufacturing systems. However, when transportation resources must also be explicitly managed, only optimizing manufacturing criteria may result in very poor schedules in terms of the distance traveled by the vehicles. This research aims to simultaneously optimize the makespan and the distance traveled by the vehicles, called total travel time, in the flexible job-shop scheduling problem with transportation resources. New generic neighborhood structures are proposed as well as an exact constant-time evaluation of the neighbor solutions in terms of total travel time. These findings are then used to introduce several optimization approaches in order to determine schedules that optimize both the makespan and the total travel time. The proposed approaches are experimentally tested on benchmark instances, and the numerical results are discussed, in particular the impact of the factory layout and the number of vehicles.

## 1. Introduction

The Flexible Job-shop Scheduling Problem (FJSP) is a combinatorial optimization problem that has been the subject of much research in the field of scheduling (see survey of Dauzère-Pérès et al., 2024). Traditionally, the FJSP focuses on optimizing the allocation of operations of jobs to machines and on sequencing the operations on the assigned machines to minimize the total completion time, known as the makespan. In modern manufacturing facilities, the efficient management of transportation resources plays a vital role in production schedules. By effectively managing transportation, delays in lot processing can be avoided, as well as machine idle time, thereby enhancing manufacturing productivity. An extensive literature review on scheduling problems including transportation constraints for manufacturing can be found in Hosseini et al. (2024).

Recently, attention has been directed towards addressing the transportation of jobs in shop scheduling problems. In particular, transportation decisions in the FJSP present unique challenges due to the interdependence between machine assignment and vehicle routing

decisions. This is because changing the assignment of a production operation directly impacts the travel time of loaded (full vehicle) and unloaded (empty vehicle) trips between machines. In comparison, in the Job-Shop scheduling Problem with Transportation resources (JSPT, Lacomme et al., 2013), the assignment of operations to machines is given and thus the loaded trips of vehicles are known before solving the problem. Two variants of this problem have been investigated: The FJSP with transfer times, which considers the time to transport a job between machines but not the empty travel times of the vehicles (Rossi, 2014 and Karimi et al., 2017), and the FJSP with Transportation resources (FJSPT), the focus of this paper, which explicitly addresses the routing of vehicles (Deroussi & Norre, 2010 and Homayouni & Fontes, 2021). In the FJSP, many schedules with different assignments of operations to machines could have the same makespan. Although this is not critical in the FJSP, different assignments of operations could lead to very different travel times between operations in the FJSPT. Hence, it is possible to significantly reduce the use of transportation resources at no or limited impact on the makespan. We actually observed (see Table 1 in Section 2) that multiple schedules with the same makespan can

<footnote>ª Mines Saint-Etienne, Department of Manufacturing Sciences and Logistics, UMR 6158 LIMOS, CMP, Univ. Clermont Auvergne, CNRS, Gardanne, F-13541, France</footnote>

<footnote>ᵇ UMR CNRS 8001, LPSM, Sorbonne Université, Paris, France</footnote>

<footnote>ᶜ Department of Accounting and Operations Management, BI Norwegian Business School, Oslo, Norway</footnote>

<footnote n="4">⁴ Institute of Industrial Engineering, National Taiwan University, Taipei, 10617, Taiwan</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: lucasberterot@gmail.com (L. Berterottière), dauzere-peres@emse.fr (S. Dauzère-Pérès), yugma@emse.fr (C. Yugma), craighuang@ntu.edu.tw (K.-L. Huang).</footnote>
exhibit very significant differences in terms of the total distance traveled by the vehicles.

When explicitly managing transportation resources, it is very relevant to avoid unnecessary long trips by minimizing the total travel time of vehicles. This has for instance shown to be important in semiconductor manufacturing, see e.g., Dauzere-Péres et al. (2012), where the location of storage areas is optimized to minimize the total maximum travel distance of vehicles, and Lin and Huang (2014), where the total transport time is minimized in the photolithography area of a semiconductor manufacturing facility. Reducing the use of vehicles, and in particular avoiding long trips, helps both to reduce congestion in the transportation system and the wear and tear of vehicles. Generally speaking, limiting the stress on the transportation system helps to improve its level of service and potentially the required number of vehicles. Another important motivation is associated to the fact that most vehicles in factories are electric. In this context, reducing the total travel time of vehicles directly impacts energy consumption. Energy-aware scheduling is gaining attention as a response to challenges such as rising energy prices, limited resources, and the need to reduce greenhouse gas emissions (Biel & Glock, 2016). The optimization of energy consumption in manufacturing facilities is a rising topic as more and more papers are interested in incorporating sustainability in production planning (Gahm et al., 2016).

This paper extends Berterottière et al. (2024) with the following contributions:

* A new Mixed-Integer Linear Programming (MILP) formulation is proposed and experimentally shown to outperform the current state-of-the-art MILP formulation from Homayouni and Fontes (2021),

* A new neighborhood structure for the job-shop scheduling problem (JSP) and its extensions, including the FJSPT, is proposed and shown to include all possible moves of one operation,

* A constant-time move evaluation procedure is proposed to exactly evaluate a new criterion, the total travel time,

* Several optimization strategies are introduced and compared,

* Extensive computational experiments show the relevance of optimizing the total travel time in addition to the makespan.

The paper is organized as follows. Section 2 motivates the problem based on numerical results obtained in our previous work and on other papers in the literature. The problem is then formally defined in Section 3, in particular how the total travel time is considered, and a new MILP formulation is presented. New move definitions are proposed along with their properties in Section 4. Section 5 formalizes the tabu search used in this paper and introduces three optimization strategies. Computational experiments that validate the efficiency of the proposed approaches and of the new MILP formulation are presented and discussed in Section 6. Finally, Section 7 concludes the paper and provides some insights for future work.

## 2. Motivations

The FJSPT is a scheduling problem where multiple jobs, each requiring a sequence of operations to be completed, must be processed on machines and transported between machines by vehicles. The assignment of production and transportation operations to resources (machines or vehicles) is not predefined and must be determined, along with the sequence of operations on these resources. The most studied criterion for the FJSP is the makespan, i.e. the completion time of all jobs. Since the FJSPT includes both scheduling and routing decisions, our focus is also to consider a classical routing criterion: The total travel time of the vehicles.

Optimizing multiple criteria is a common practice in the scheduling literature due to the diverse performance indicators prevalent in the industry. An overview of important results can be found in T'kindt and Billaut (2006). However, the consideration of routing objectives in scheduling problems has not received much attention. In Umar et al.

<caption>Table 1</caption>

First, best and worst total travel times of schedules with the same makespan on the instances from Deroussi and Norre (2010).

<table><thead><tr><th rowspan="2">Instance</th><th rowspan="2">C<sub>max</sub></th><th colspan="4">TTT</th></tr><tr><th>First</th><th>Best</th><th>Worst</th><th>Gap (<sup>μ-β</sup>/<sub>b</sub>)</th></tr></thead><tbody><tr><td>fjsp1</td><td>134</td><td>200</td><td>192</td><td>202</td><td>+5%</td></tr><tr><td>fjsp2</td><td>114</td><td>138</td><td>138</td><td>156</td><td>+12%</td></tr><tr><td>fjsp3</td><td>120</td><td>148</td><td>124</td><td>178</td><td>+44%</td></tr><tr><td>fjsp4</td><td>114</td><td>194</td><td>188</td><td>198</td><td>+5%</td></tr><tr><td>fjsp5</td><td>94</td><td>120</td><td>104</td><td>122</td><td>+17%</td></tr><tr><td>fjsp6</td><td>134</td><td>186</td><td>178</td><td>198</td><td>+11%</td></tr><tr><td>fjsp7</td><td>112</td><td>182</td><td>174</td><td>186</td><td>+7%</td></tr><tr><td>fjsp8</td><td>178</td><td>214</td><td>198</td><td>262</td><td>+32%</td></tr><tr><td>fjsp9</td><td>144</td><td>178</td><td>152</td><td>216</td><td>+45%</td></tr><tr><td>fjsp10</td><td>174</td><td>202</td><td>194</td><td>222</td><td>+13%</td></tr></tbody></table>

(2015), a multi-objective genetic algorithm is introduced, where the vehicle travel times are minimized among other objectives. In a recent work, Fontes et al. (2024) study an extension of the FJSPT where the total energy cost is minimized in addition to the makespan. The total energy cost includes the vehicle travel time and speed of the vehicles. In comparison with these articles, this paper focuses on minimizing the total travel time as a secondary objective to the makespan and proposes new related results.

Based on our recent study on the FJSPT, we noted that schedules with identical makespan could exhibit substantially different total travel times. Table 1 presents the total travel time (denoted TTT) of schedules with the best makespan (denoted C<sub>max</sub>) determined in the Tabu Search of Berterottière et al. (2024) for a given instance. Among the solutions with the best makespan, the total travel time of the first solution encountered in the search, which is often retained as the optimal solution, as well as the minimum and maximum total travel times, are reported. The gap between the best and worst total travel times, computed as $\frac{TTT_{worst} - TTT_{best}}{TTT_{best}}$, is reported as well. Fig. 1 shows all the solutions visited in the Tabu Search on two instances (namely Instance 1 for (a) and Instance 3 for (b) from the data set introduced in the previous paper) with the same number of operations but different flexibility levels (i.e., average number of machines per operation) and available numbers of vehicles (2 and 6). Note that not only do solutions with the same makespan have different total travel times, but solutions with a slightly worse makespan than other solutions may have a lower total travel time. Also, note that, with six vehicles and high flexibility levels (b), schedules with a good makespan can be obtained with poor total travel times compared to the smallest one. This is less the case with two vehicles and low flexibility levels (a), where a good makespan seems to be more correlated to a good total travel time.

Optimizing the total travel time in the JSPT is relatively straightforward. In the JSPT, minimizing the total travel time is equivalent to minimizing the sum of empty travel times. Gondran et al. (2018) consider a combination of routing criteria, including total travel times, total riding time, and total waiting time, under a criterion known as the quality of service, initially proposed for the dial-a-ride problem by Cordeau and Laporte (2003). These criteria are included in a weighted sum along with the makespan.

In contrast, optimizing the total travel time in the FJSPT is significantly more complex. Machine assignment decisions in the FJSPT can result in longer empty travel times in a schedule but a shorter overall total travel time, as the loaded travel time can also vary. This added complexity can benefit more from the integrated method proposed in this paper.

In this study, optimization strategies are proposed to find good solutions regarding both the makespan and the total travel time, with makespan as the priority criterion. Hence, a lexicographic order is used,
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Objectives of schedules explored in Tabu Search of Berterottière et al. (2024) on instances with low (a) and high (b) machine flexibility levels and number of vehicles.</figcaption></figure>

where the schedules with the smallest makespan are considered and then classified regarding their total travel time.

### 3. Problem definition and modeling

In this section, the problem is formally defined in Section 3.1, and the graph model used in this paper is introduced in Section 3.3. The notations are summarized in Section 3.4. A Mixed-Integer Linear Programming (MILP) formulation is then introduced in Section 3.2.

#### 3.1. Problem definition

A set $\mathcal{J}$ of jobs, a set $\mathcal{M}$ of production machines, and a set $\mathcal{V}$ of vehicles are given. Each job $i$ requires a sequence (often called route) of $n_i$ production operations and thus $n_i$ transportation operations to be completed. Each production operation $u$ must be processed on one machine among a subset $\mathcal{M}_u \subset \mathcal{M}$, and each transportation operation $t_u$ must be performed on one vehicle among the set of vehicles $\mathcal{V}$. It should be noted that the jobs are all originally located in an initial storage area, and that it is not necessary to transport the jobs back to this storage area after the last production operation.

The processing times of production operations are machine-dependent. The processing time of a production operation $u$ processed on machine $k \in \mathcal{M}^u$ is denoted $p_u^k$. When the processing time of operation $u$ does not depend on the machine on which $u$ is assigned, the processing time is simply denoted $p_u$. Travel times between two machines are not vehicle-dependent and do not depend on whether the vehicle is loaded or not. Note that it is straightforward to extend the results and approaches presented in this paper when these two assumptions are relaxed. The travel time from machine $k_1$ to machine $k_2$ is denoted $\tau_{k_2}^{k_1}$ and must respect the triangular inequality, i.e. for any three machines $k_1, k_2$ and $k_3 \in \mathcal{M}$, we have $\tau_{k_2}^{k_1} \le \tau_{k_3}^{k_1} + \tau_{k_3}^{k_2}$.

Preemption is not allowed, meaning that an operation that started must be completed without interruption. Additionally, machines are unable to perform multiple operations simultaneously. Each vehicle is limited to transporting a single job at a time, which can be delivered directly to a machine without blocking constraints, since buffer spaces are assumed to be large enough. A vehicle must be present to perform a transportation operation even if the travel time is 0, i.e. if two consecutive production operations are performed by the same machine. How this aspect is considered differs among problem formulations;

for example, Homayouni and Fontes (2021) omits it, whereas Ham (2020) includes it. In practice, this situation rarely arises, since two consecutive tasks on the same machine can generally be merged into a single operation. The goal is to allocate each transportation operation to a vehicle, assign each production operation to an eligible machine, and define the sequence of operations on the vehicles and on the machines to minimize both the total time needed to complete all jobs, known as the makespan ($C_{max}$), and the Total Travel Time (TTT) of the vehicles.

#### 3.2. MILP formulation

To assess the performance of the solution methods proposed in this paper, a new mathematical formulation of the FJSPT is presented in this section. This formulation relies on two existing formulations from the literature. Sequencing variables on production operations from the MILP formulation from Shen et al. (2018) for the FJSP with sequence-dependent setup times are combined with the sequencing variables on transportation operations from Homayouni and Fontes (2021). The sequencing of production operations of Homayouni and Fontes (2021) uses decision variables based on the machine assignment and the operation being sequenced just before each operation, following the model introduced in Saidi-Mehrabad and Fattahi (2007) for the FJSP. Separating the subproblems of assigning machines and sequencing operations is shown to perform better for the FJSP (Shen et al., 2018) and the FJSPT, as shown in the numerical results of Section 6.4.

Scheduling problems involving the transportation of semi-finite jobs have been mathematically modeled several times in the literature. Bilge and Ulusoy (1995) proposed a nonlinear mixed-integer programming formulation for the JSPT, while a linear formulation of the same problem was later introduced by Fontes and Homayouni (2019) and extended to the FJSPT by Homayouni and Fontes (2021). Constraint programming formulations for these problems were also proposed in Ham (2021) for the JSPT and in Ham (2020) for the FJSPT. An extensive study of the mathematical modeling of the FJSP with transportation times, without explicitly modeling transportation resources, is proposed in Karimi et al. (2017).

Only in this section, we refer to the *j*-th production (resp. transportation) operation of job *i* as $O_{ij}$ (resp. $T_{ij}$). To model the problem, let us define the following decision variables: $s_{ij}^u$, resp. $s_{ij}^m$, is the starting time of transportation operation $T_{ij}$, resp. production operation $O_{ij}$, $C_{max}$ is
the resulting makespan and the four binary decision variables below:

$$
\alpha_{ijk} = \begin{cases} 1 & \text{if production operation } O_{ij} \text{ is assigned to machine } k, \\ 0 & \text{otherwise,} \end{cases}
$$

$$
\beta_{ij i' j'} = \begin{cases} 1 & \text{if production operation } O_{ij} \text{ is sequenced before production} \\ 0 & \text{operation } O_{i' j'}, \\ 0 & \text{otherwise,} \end{cases}
$$

$$
f_{ij} = \begin{cases} 1 & \text{if transportation operation } T_{ij} \text{ is the first operation in the} \\ 0 & \text{sequence of operations of a vehicle,} \end{cases}
$$

$$
l_{ij} = \begin{cases} 1 & \text{if transportation operation } T_{ij} \text{ is the last operation in the} \\ 0 & \text{sequence of operations of a vehicle,} \end{cases}
$$

$$
\delta_{ijkl} = \begin{cases} 1 & \text{if transportation operation } T_{ij} \text{ is processed just before } T_{kl} \\ 0 & \text{in the sequence of operations of a vehicle,} \\ 0 & \text{otherwise.} \end{cases}
$$

To model the total travel time, two continuous decision variables are also used: $d_{ij}^D$, the distance (or time) traveled by a vehicle to perform the delivery phase of operation $T_{ij}$, and $d_{ij}^P$, the distance (or time) traveled by a vehicle to perform the pickup phase of operation $T_{ij}$.

Model (P) is formalized below.

$$
\sum_{k \in \mathcal{M}_{ij}} \alpha_{ijk} = 1 \quad \forall i \in \mathcal{J}, j \le n_i \qquad (1)
$$

$$
s_{ij}^{v} \geq s_{i'j'}^{v} + d_{i'j'}^{D} + d_{i'j'}^{P} + (\delta_{i'j'ij} - 1) \cdot H \quad \forall i \in \mathcal{J}, j \le n_i, (i', j') \quad (2)
$$

$$
s_{ij}^{v} \geq s_{ij-1}^{m} + \sum_{k \in \mathcal{M}_{ij-1}} \alpha_{ij-1k} \cdot p_{ij-1k} \quad \forall i \in \mathcal{J}, 2 \le j \le n_i \quad (3)
$$

$$
s_{ij}^{m} \geq s_{i'j'}^{m} + \alpha_{i'j'k} \cdot p_{i'j'k} + (\beta_{i'j'ij} + \alpha_{ijk} + \alpha_{i'j'k} - 3) \cdot H \\
\qquad \forall (i, i') \in \mathcal{J}^2, j \le n_i, j' \le n_{i'} \quad (4)
$$

$$
s_{ij}^{m} \geq s_{ij}^{v} + d_{ij}^{D} \quad \forall i \in \mathcal{J}, j \leq n_{i} \qquad (5)
$$

$$
C_{\max} \geq s_{in_i}^m + \sum_{k \in \mathcal{M}_{in_i}} \alpha_{in_i k} \cdot p_{ijn_i} \quad \forall i \in \mathcal{J} \qquad (6)
$$

$$
d_{ij}^{D} \geq \tau_{k_2}^{k_1} + (\alpha_{ij-1k_1} + \alpha_{ijk_2} - 2) \cdot H \qquad \forall i \in \mathcal{J}, j \le n_i, (k_1, k_2) \in \mathcal{M}_{i'j-1} \times \mathcal{M}_{ij} \qquad (7)
$$

$$
d_{ij}^{P} \geq \tau_{k_2}^{k_1} + (\alpha_{ijk_1} + \alpha_{i'j'-1k_2} + \delta_{i'j'j'} - 3) \cdot H \quad \forall (i, i') \in \mathcal{J} \times \mathcal{J}, j \le n_i, j' \le n_{i'}, (k_1, k_2) \in \mathcal{M}_{i'j'} \times \mathcal{M}_{ij} \quad (8)
$$

$$
\sum_{i \in \mathcal{J}} \sum_{j \le n_i} f_{ij} \le n_v \qquad (9)
$$

$$
\sum_{i \in \mathcal{J}} \sum_{j \le n_i} f_{ij} = \sum_{i \in \mathcal{J}} \sum_{j \le n_i} l_{ij} \qquad (10)
$$

$$
f_{ij} + \sum_{i' \in \mathcal{J}} \sum_{j \le n_i} \delta_{i'j'ij} = 1 \quad \forall i \in \mathcal{J}, j \le n_i \qquad (11)
$$

$$
\sum_{i' \in \mathcal{J}} \sum_{j \le n_i} \delta_{i'j'j'} + l_{ij} = 1 \quad \forall i \in \mathcal{J}, j \le n_i \qquad (12)
$$

$$
d_{ij}^{P} \le (1 - f_{ij}) \cdot H \quad \forall i \in \mathcal{J}, j \le n_i \qquad (13)
$$

$$
\alpha_{ijk} \in \{0, 1\} \qquad \forall i \in \mathcal{J}, j \le n_i, k \in \mathcal{M}_{ij} \qquad (14)
$$

$$
\beta_{ij i' j'} \in \{0, 1\} \qquad \forall (i, i') \in \mathcal{J} \times \mathcal{J}, j \le n_i, j' \le n_{i'} \quad (15)
$$

$$
C_{\max} = s_{ij}^{v} \cdot s_{ij}^{m} \cdot d_{ij}^{D} \cdot d_{ij}^{P} \geq 0 \quad \forall i \in \mathcal{J}, j \le n_i \qquad (16)
$$

Constraints (1) ensure that each production operation is assigned to
a machine. Constraints (2) guarantee that a transportation operation can

only start after the pickup and delivery phases of the preceding trans-
portation operation of the vehicle. Constraints (3) ensure that a trans-
portation operation starts after the preceding production operation in
the job route. Constraints (4) and (5) ensure that the starting time of a
production operation is larger than the completion time of the previous
production operation on the same machine and the previous delivery
phase of the preceding transportation operation in the job route. Con-
straints (6) define the makespan. Constraints (7) and (8) set the values
of the time traveled by the vehicles for the delivery and pickup phases
of each transportation operation. Note that, for each job i ∈ J, αᵢ₀₀ = 1,
meaning that the assignment of operation 0 is the initial depot. Con-
straints (9) state that the number of first transportation operations of
vehicle sequences is not larger than the number of vehicles, while Con-
straints (10) state that the number of first transportation operations is
equal to the number of last transportation operations. Constraints (11)
ensure that each transportation operation has one predecessor except if
it is a first transportation operation, and Constraints (12) ensure that
each transportation operation has one successor except if it is a last
transportation operation. Constraints (13) guarantee that the first op-
eration of a vehicle has no pickup time. Finally, Constraints (14) to (16)
specify the nature of the decision variables.

To determine the minimum makespan and minimum total travel time
in lexicographical order, the following solution scheme is used:

1. Solve min $C_{\max}$ s.t. $\mathcal{P}$ to find the optimal makespan $C_{\max}^*$,

2. Solve min $\sum_{i \in \mathcal{J}} \sum_{j \le n_i} d_{ij}^D + d_{ij}^P$ s.t. $\mathcal{P}$ and $C_{\max} \le C_{\max}^*$.

3.3. Graph model for FJSPT with total travel time

Following the graph model introduced in Berterotti` ere et al. (2024), we consider a directed graph solution representation. A conjunctive graph D = (V, A ∪ Π) is used to model a schedule. The set V of vertices includes one vertex for each production operation and one vertex for each transportation operation. Additionally, two dummy vertices 0 and * are considered that respectively model the beginning and the end of the schedule. Set A is the set of arcs modeling the precedence relations between consecutive operations in the routes of the jobs, and set Π is the set of arcs modeling the assignment and sequencing of operations on the resources. As processing times are machine-dependent, the weight of an outgoing arc from a production operation u processed on machine k is equal to p_u^k. From a transportation operation vertex, the weight of the outgoing arc to the next operation in the job routes and the weight of the outgoing arc to the next operation in the vehicle routes are not the same, as the empty travel time must be considered in the routing of vehicles. For transportation operation t_u, let us denote by p_u^j the loaded travel time in the job routes, which is the weight of the outgoing arc to the following production operation u. Let us denote by p_u^M the sum of the loaded travel times in the job routes and the empty travel time to the next machine in the vehicle routes. This is also the weight of the outgoing arc from t_u to the next operation in the vehicle routes.

**Proposition 1.** The set of semi-active schedules is dominant when minimizing the total travel time in the FJSPT.

Proposition 1 is explained by the fact that the total travel time is not
time related. Therefore, without proving that this is a regular criterion,
a schedule has exactly the same total travel time if it is left-shifted. Thus,
the graph model that we use is sufficient to model an optimal schedule
as operations can start as early as possible without a negative effect.
The total travel time can initially be computed by summing the travel
times in the vehicle routes. Then, we show in Section 4.3 that the to-
tal travel time of a neighbor solution can be computed exactly without
going through the whole graph. The makespan is determined by com-
puting the longest (or critical) path of the graph.
<figure><img src="image_4.png" /><figcaption>Fig. 2. Notations for multiple consecutive operations of the same job.</figcaption></figure>

<table><caption>**Table 2**
Notations.</caption><thead><tr><th>Sets</th><th></th></tr></thead><tbody><tr><td>V</td><td>Set of vertices</td></tr><tr><td>A</td><td>Set of conjunctive arcs modeling the precedence between consecutive operations in the routes of jobs</td></tr><tr><td>Π</td><td>Set of conjunctive arcs modeling the precedence between two operations assigned to the same resource and sequenced consecutively</td></tr><tr><td>D = (V, A ∪ Π)</td><td>Conjunctive graph</td></tr><tr><td>P(u)</td><td>Set of predecessors of operation u in D</td></tr><tr><td>F(u)</td><td>Set of successors of operation u in D</td></tr><tr><td>CP(u)</td><td>Set of predecessors of operation u on a longest path from 0 to u in D</td></tr><tr><td>CF(u)</td><td>Set of successors of operation u on a longest path from u to * in D</td></tr><tr><th>Variables</th><th></th></tr><tr><td>p<sub>u</sub></td><td>Processing time of operation u</td></tr><tr><td>p<sup>J</sup><sub>u</sub></td><td>Processing time of operation u in the job route</td></tr><tr><td>p<sup>M</sup><sub>u</sub></td><td>Processing time of operation u in the sequence of operations on the machine/vehicle</td></tr><tr><td>r<sub>u</sub></td><td>Head of operation u</td></tr><tr><td>r<sup>J</sup><sub>u</sub></td><td>Head of operation u on the job route</td></tr><tr><td>r<sup>M</sup><sub>u</sub></td><td>Head of operation u on the machine/vehicle route</td></tr><tr><td>q<sub>u</sub></td><td>Tail of operation u</td></tr><tr><td>q<sup>J</sup><sub>u</sub></td><td>Tail of operation u on the job route</td></tr><tr><td>q<sup>M</sup><sub>u</sub></td><td>Tail of operation u on the machine/vehicle route</td></tr><tr><td>a(u)</td><td>Machine/vehicle assigned to operation u</td></tr><tr><td>τ<sup>m<sub>1</sub></sup><sub>m<sub>2</sub></sub></td><td>Distance between machine m<sub>1</sub> and machine m<sub>2</sub></td></tr><tr><td>C<sub>max</sub></td><td>Makespan</td></tr><tr><td>TTT</td><td>Total travel time</td></tr></tbody></table>

### 3.4. Notations

To simplify the notations, the transportation operation preceding a production operation $u$ is denoted $t_u$, the production operation preceding, respectively following, a production operation $u$ in the job route is denoted $u-1$, respectively $u+1$, as depicted in Fig. 2.

The notations used in this paper are summarized in Table 2. Note that the set of arcs $A$ is the same for all solutions, whereas the set of arcs $Π$ differs between solutions. The set of predecessors and successors of all operations can be computed once every time the graph changes, and it is then possible to check if a vertex is following/preceding another vertex in constant computational time. The head of operation $u$ denotes the length of the longest path from dummy vertex 0 to $u$. The tail of operation $u$ denotes the length of the longest path from a successor of $u$ to dummy vertex *.

### 4. Neighborhood structures

In vehicle routing problems, neighborhood-based metaheuristics that aim at minimizing the total travel times often rely on significant changes in the solution, such as Adaptive Large Neighborhood Search (ALNS) heuristics. However, in the context of scheduling problems where the makespan is minimized, evaluating solutions in large neighborhood structures might be very time-consuming, in particular because neighbor solutions might be infeasible and have to be reconstructed.

When the objective is to minimize the makespan, the focus is typically on critical operations on a longest path, since moving these operations has the potential to reduce the makespan. However, when optimizing the total travel time, moving many other operations can contribute to a decrease of the total travel time. With the increasing number of potential operations to move, the size of the neighborhood structure becomes an important parameter for the efficiency of the search. Thus, new neighborhood structures of different sizes are proposed in Section 4.1.

Several properties of these neighborhood structures are then introduced in Section 4.2. Section 4.3 presents a method to compute the total travel time of a neighbor solution in constant time.

#### 4.1. Move definitions

In this section, we define the neighborhood structures proposed in this paper. Each neighborhood structure is composed of feasibility conditions on the job insertion neighborhood. In a recent study, Tsogbetse et al. (2024) compare several neighborhood operators and conclude that the job insertion operator is among the best ones for the classical job-shop scheduling problem. As each neighborhood structure includes feasibility conditions that are sufficient but not always necessary, the size of the neighborhood varies, and the solution methods rely on different neighborhood structures.

Neighborhood structure $N_2$ is an adaptation for the FJSPT of the neighborhood initially proposed in Shen et al. (2018) for the FJSP with sequence-dependent setup times, and neighborhood structure $N_3$ is an adaptation for the FJSPT of the neighborhood structure initially proposed in Dauzère-Pérès and Paulli (1997) for the FJSP. In all the following definitions, some conditions are given to insert production operation $u$ between operation $v$ and operation $w$ and to insert transportation operation $t_u$ between operation $t_v$ and operation $t_w$. Let us recall that the resequencing of operations $u$ and $t_u$ (inserting them on the same resource) and the reassignment of operations $u$ and $t_u$ (inserting them on another resource) are not differentiated in the considered move, and thus in the four neighborhood structures of this paper. This integrated move was first proposed in Dauzère-Pérès and Paulli (1997).

**Definition 4.1** (Neighborhood structure $N_1$). A move of production operation $u$ between production operations $v$ and $w$ is accepted by neighborhood structure $N_1$ if the conditions below hold:

1. $v \notin F(t_{u+1})$ with $(u, t_{u+1}) \in A$, and

2. $w \notin P(t_u)$ with $(t_u, w) \in A$.
A move of transportation operation t<sub>u</sub> between transportation operations t<sub>v</sub> and t<sub>w</sub> is accepted by neighborhood structure N<sub>1</sub> if the conditions below hold:

3. t<sub>v</sub> /∈ F(u) with (t<sub>u</sub>, u) ∈ A, and

4. t<sub>w</sub> /∈ P(u − 1) with (u − 1, t<sub>u</sub>) ∈ A.

**Definition 4.2** (Neighborhood structure N<sub>2</sub>). A move of production operation u between production operations v and w is accepted by neighborhood structure N<sub>2</sub> if the conditions below hold:

1. max(r<sub>x</sub>, r<sub>t<sub>v</sub></sub>) < r<sub>t<sub>u+1</sub></sub> + p<sup>J</sup><sub>t<sub>u+1</sub></sub> with (t<sub>v</sub>, v), (u, t<sub>u+1</sub>) ∈ A, (x, v) ∈ Π, u + 1 ̸= v, and

2. min(r<sub>y</sub> + p<sub>y</sub>, r<sub>t<sub>w+1</sub></sub> + p<sup>J</sup><sub>t<sub>w+1</sub></sub>) > r<sub>t<sub>u</sub></sub> with (t<sub>u</sub>, u), (w, t<sub>w+1</sub>) ∈ A, (w, y) ∈ Π, u − 1 ̸= w.

A move of transportation operation t<sub>u</sub> between transportation operations t<sub>v</sub> and t<sub>w</sub> is accepted by neighborhood structure N<sub>2</sub> if the conditions below hold:

3. max(r<sub>t<sub>x</sub></sub>, r<sub>t<sub>v−1</sub></sub>) < r<sub>u+1</sub> + p<sub>u+1</sub> with (v − 1, t<sub>v</sub>), (t<sub>u</sub>, u + 1) ∈ A, (t<sub>x</sub>, t<sub>v</sub>) ∈ Π, t<sub>u+1</sub> ̸= t<sub>v</sub>, and

4. min(r<sub>t<sub>y</sub></sub> + p<sup>J</sup><sub>t<sub>y</sub></sub>, r<sub>w+1</sub> + p<sub>w+1</sub>) > r<sub>u−1</sub> with (u − 1, t<sub>u</sub>), (t<sub>w</sub>, w + 1) ∈ A, (t<sub>w</sub>, t<sub>y</sub>) ∈ Π, t<sub>u−1</sub> ̸= t<sub>w</sub>.

**Definition 4.3** (Neighborhood structure N<sub>3</sub>). A move of production operation u between production operations v and w is accepted by neighborhood structure N<sub>3</sub> if the conditions below hold:

1. r<sub>v</sub> < r<sub>t<sub>u+1</sub></sub> + p<sup>J</sup><sub>t<sub>u+1</sub></sub> with (u, t<sub>u+1</sub>) ∈ A, and

2. r<sub>w</sub> + p<sup>J</sup><sub>t<sub>w</sub></sub> > r<sub>t<sub>u</sub></sub> with (t<sub>u</sub>, u) ∈ A.

A move of transportation operation t<sub>u</sub> between transportation operations t<sub>v</sub> and t<sub>w</sub> is accepted by neighborhood structure N<sub>3</sub> if the conditions below hold:

3. r<sub>t<sub>v</sub></sub> < r<sub>u</sub> + p<sub>u</sub> with (t<sub>u</sub>, u) ∈ A, and

4. r<sub>t<sub>w</sub></sub> + p<sup>J</sup><sub>t<sub>w</sub></sub> > r<sub>u−1</sub> with (u − 1, t<sub>u</sub>) ∈ A.

**Definition 4.4** (Neighborhood structure N<sub>4</sub>). A move of production operation u between production operations v and w is accepted by neighborhood structure N<sub>3</sub> if the conditions below hold:

1. r<sub>v</sub> ≤ r<sub>u</sub> + p<sub>u</sub>, and

2. r<sub>w</sub> + p<sub>w</sub> ≥ r<sub>u</sub>.

A move of transportation operation t<sub>u</sub> between transportation operations t<sub>v</sub> and t<sub>w</sub> is accepted by neighborhood structure N<sub>4</sub> if the conditions below hold:

3. r<sub>t<sub>v</sub></sub> ≤ r<sub>t<sub>u</sub></sub> + p<sup>J</sup><sub>t<sub>u</sub></sub>, and

4. r<sub>t<sub>w</sub></sub> + p<sup>J</sup><sub>t<sub>w</sub></sub> ≥ r<sub>t<sub>u</sub></sub>.

Fig. 3 gives a graphical illustration of the conditions of N<sub>2</sub>, N<sub>3</sub> and N<sub>4</sub>. The neighbor solution can contain cycles only if they are induced by the newly created arcs, (v, u) or (u, w) for the move of a production operation and (t<sub>v</sub>, t<sub>u</sub>) or (t<sub>u</sub>, t<sub>w</sub>) for the move of a transportation operation. The path checked by conditions 1 (resp. conditions 3) of each of these definitions is colored in blue for the move of a production (resp. transportation) operation, and the paths checked by conditions 2 (resp. conditions 4) of these definitions are colored in orange.

4.2. Properties of the neighborhood structures

Theorem 1 formalizes the relationship between the neighborhood structures by showing that they are nested within each other.

Theorem 1. N<sub>4</sub> ⊆ N<sub>3</sub> ⊆ N<sub>2</sub> ⊆ N<sub>1</sub>

**Proof.** N<sub>4</sub> ⊆ N<sub>3</sub>. The move of a transportation operation is investigated. Let s be a feasible solution and s' a neighbor where a transportation operation t<sub>u</sub> is moved between transportation operations t<sub>v</sub> and t<sub>w</sub> and conditions of Definition 4.4 are satisfied. Let us prove that, if s' is accepted by N<sub>4</sub>, then s' is also accepted by N<sub>3</sub>. Let us first show that Condition 3 of Definition 4.4 implies Condition 3 of Definition 4.3:

$$
\begin{align*}
r_{t_v} &\le r_{t_u} + p_{t_u}^J \\
&\le r_u < r_u + p_u
\end{align*}
$$

Thus, a move that satisfies Condition 3 of Definition 4.4 also satisfies Condition 3 of Definition 4.3. Next, let us show that Condition 4 of Definition 4.4 implies Condition 4 of Definition 4.3:

$$
r_{t_w} + p_{t_w}^{J} \geq r_u > r_{u-1}
$$

The same reasoning can be applied to prove that a move of a production operation that satisfies Conditions 1 and 2 of Definition 4.4 also satisfies Conditions 1 and 2 of Definition 4.3.

N<sub>3</sub> ⊆ N<sub>2</sub>. This proof is very similar to the one in Lemma 4.1 from Shen et al. (2018).

N<sub>2</sub> ⊆ N<sub>1</sub>. The move of a production operation is now investigated. Again, let s be a feasible solution and s' a neighbor where production operation u is moved between production operations v and w and conditions of Definition 4.2 are satisfied. Let us prove that if s' is accepted by N<sub>2</sub>, then s' is also accepted by N<sub>1</sub>. We first show by contradiction that Condition 1 of Definition 4.2 implies Condition 1 of Definition 4.1.

Let us assume that Condition 1 of Definition 4.2 holds but not Condition 1 of Definition 4.1. Then, operation v is in the set of successors of t<sub>u+1</sub>, and there is a path from operation t<sub>u+1</sub> to operation v. As operation v is not operation u + 1, this path must pass by another vertex immediately preceding v, its machine predecessor x or its job predecessor t<sub>v</sub>. Then, if the path traverses x, we have r<sub>t<sub>u+1</sub></sub> + p<sup>J</sup><sub>t<sub>u+1</sub></sub> ≥ r<sub>x</sub> and, if the path traverses t<sub>v</sub>, we have r<sub>t<sub>u+1</sub></sub> + p<sup>J</sup><sub>t<sub>u+1</sub></sub> ≥ r<sub>v</sub>, which implies that Condition 1 of Definition 4.2 is not satisfied.

Second, we show by contradiction that Condition 2 of Definition 4.2 implies Condition 2 of Definition 4.1. It is now assumed that Condition 2 of Definition 4.2 holds but not Condition 2 of Definition 4.1. Then, operation w is in the set of predecessors of operation t<sub>u</sub>, and there is a path from w to t<sub>u</sub>. As operation u − 1 is not operation w and operation t<sub>w+1</sub> is not operation t<sub>u</sub>, we have that the path must go through one of the direct successors of operation w which are operation y and operation t<sub>w+1</sub>. Thus, either the path traverses operation y and we have r<sub>y</sub> + p<sub>y</sub> ≤ r<sub>t<sub>u</sub></sub>, or the path traverses operation t<sub>w+1</sub> and we have r<sub>t<sub>w+1</sub></sub> + p<sup>J</sup><sub>t<sub>w+1</sub></sub> ≤ r<sub>t<sub>u</sub></sub>. In both cases, Condition 2 of Definition 4.2 is not satisfied.

Again, the reasoning can be applied to prove that a move of production operation that satisfies Conditions 3 and 4 of Definition 4.4 also satisfies Conditions 3 and 4 of Definition 4.3.

Theorem 2 guarantees that all neighborhood structures do not lead to infeasible solutions, by showing that N<sub>1</sub>, the largest neighborhood structure, does not lead to infeasible solutions, and are connected, by showing that N<sub>4</sub>, the smallest neighborhood structure, is connected.

**Theorem 2.** Neighborhood structures N<sub>1</sub>, N<sub>2</sub>, N<sub>3</sub>, and N<sub>4</sub> do not lead to infeasible solutions and are connected.

**Proof. Feasibility:** To prove that the neighborhood structures do not lead to infeasible solutions, it is enough to prove that N<sub>1</sub> does not lead to infeasible solutions. Then, Theorem 1 ensures that any move accepted by the three other neighborhood structures is also accepted by N<sub>1</sub>.

The feasibility of neighborhood structure N<sub>1</sub> is proved for the move of a production operation, and the proof for the move of a transportation operation is very similar. Moving production operation u between operations v and w is performed by deleting arcs (x, u) and (u, y), the former machine predecessor and machine successor of u, deleting arc (v, w), and adding arcs (x, y), (v, u) and (u, w). If the new graph contains cycles, they are induced by the newly added arcs. A cycle cannot be created by arc (x, y) as there was already a path from x to y before the
<figure><img src="image_5.png" /><figcaption>Fig. 3. Illustration of the neighborhood definitions of N $_{2}$, N 3 and N $_{4}$.</figcaption></figure>

move. A cycle can only be created if there is a path from u to v or from w to u .

If there is a path from u to v in the graph after the move, then it must traverse one of the successors of u , namely w or t$_{u}$$_{+1}$ . If there is a path from w to v , then there was a cycle in the graph before the move and, by Condition 1 of Definition 4.1, there is no path from t$_{u}$$_{+1}$ to v . In a similar manner, no path is created from w to u as it must traverse one of the predecessors of u , either v , which would mean that there was already a cycle in the graph, or t$_{u}$ , which is not possible by Condition 2.

Connectivity: To prove that that the neighborhood structures are connected, it is enough to prove that N 4 is connected. Then, Theorem 1 ensures that any move from N 4 is also accepted by the other neighbor- hood structures, and thus that they are all connected. Van Laarhoven et al. (1992) propose a neighborhood structure that is proved to be glob- ally connected: A move consists in reversing a critical arc. This neigh- borhood structure can be seen as the insertion of an operation u between operations v and w , where v is the resource successor of u and ( u, v ) is on a critical path. Note that even if the critical path is related to the makespan objective, this neighborhood structure has been proved glob- ally connected, so that when starting from one solution, there is a finite sequence of moves to perform to reach any other solution.

Let us prove that the neighborhood structure of Van Laarhoven et al. (1992) is included in N $_{4}$. Only the case of the reversal of a critical arc between two production operations is considered, as the proof for the reversal of a critical arc between two transportation operations is sim- ilar. Reversing a critical arc ( u, v ) means inserting u between v and its resource successor w . As ( u, v ) is a critical arc, then r$_{v}$ = r$_{u}$ + p$_{u}$ . Thus, Condition 1 of Definition 4.4 is satisfied with equality. As r$_{w}$ is the re- source successor of r$_{v}$ , then r$_{w}$ > r$_{v}$ and r$_{v}$ > r$_{u}$ , and thus Condition 2 is satisfied as well.

The fact that the neighborhood structure associated to reversing a critical arc is included in N $_{4}$, which is shown to be connected for the job-shop scheduling problem in Van Laarhoven et al. (1992), would be sufficient to prove connectivity if there was no machine assignment de- cisions. It is now showed that N 4 necessarily allows one transition to any resource. Again, this is shown for a move of a production operation and the proof for the move of a transportation operation is similar. So it is shown that, for any production operation u and machine M$_{k}$ such that M$_{k}$ ∈ M $^{u}$, there is a couple ( v, w ) such that v and w are consecutive

in the machine sequence and Conditions 1 and 2 of Definition 4.4 are both satisfied.

It can be seen that for any couple of consecutive operations ( v, w ) and operation u , at least one of the two conditions is satisfied. If both conditions are not satisfied, then r$_{u}$ + p$_{u}$ < r$_{v}$ and r$_{w}$ + p$_{w}$ < r$_{u}$ . Thus r$_{v}$ > r$_{u}$ + p$_{u}$ > r$_{w}$ + p$_{w}$ , which can be reduced to r$_{v}$ > r$_{w}$ , which is not possible as w is the machine successor of v , so r$_{w}$ > r$_{v}$ .

Let (0 , v$_{1}$ , v$_{2}$ , . . . , v$_{n}$$_{k}$ , *) be the sequence of machine M$_{k}$ ∈ M $^{u}$. It is shown by contradiction that there is a position in the sequence where operation u can be inserted. Let us suppose that there is no position in the sequence for operation u to be inserted. As one of the conditions is necessarily satisfied and as dummy vertex 0 necessarily ensures Condi- tion 1 and dummy vertex ∗ necessarily ensures Condition 2, there is an index l ∈ [1 , n$_{k}$ − 1] such that Condition 1 is always satisfied when in- serting u before v$_{l}$ and Condition 2 is always satisfied when inserting u after v$_{l}$$_{+1}$ . Thus:

$$
r_{v_{l-1}} \leq r_u + p_u \qquad (17)
$$

$$
r_{v_l} + p_{v_l} < r_u \qquad (18)
$$

$$
\text{and} \quad r_{v_{l+1}} > r_u + p_u \qquad (19)
$$

$$
r_{v_{l+2}} + p_{v_{l+2}} \geq r_u \qquad (20)
$$

This implies that Conditions 1 and 2 are satisfied to insert u between v$_{l}$ and v$_{l}$$_{+1}$ : By (18) r$_{v}$$_{l}$ + p$_{v}$$_{l}$ < r$_{u}$ , so r$_{v}$$_{l}$ ≤ r$_{u}$ + p$_{u}$ , Condition 1 is satisfied. By (19) r$_{v}$$_{l}$$_{+1}$ > r$_{u}$ + p$_{u}$ , so r$_{v}$$_{l}$$_{+1}$ + p$_{v}$$_{l}$$_{+1}$ ≥ r$_{u}$ and Condition 2 is satisfied as well.

Remark 1. New neighborhood structures N 1 and N 4 can be used for the classical JSP and FJSP with the same properties of feasibility and connectivity. Using the same notations and without transportation op- erations, moving operation u between operations v and w is accepted if the conditions below hold:

• For N 1

(a) v / ∈ F ( u + 1) with ( u, u + 1) ∈ A , and

(b) w / ∈ P ( u − 1) with ( u − 1 , u ) ∈ A .

• For N 4

(a) r$_{v}$ ≤ r$_{u}$ + p$_{u}$ , and

(b) r$_{w}$ + p$_{w}$ ≥ r$_{u}$ .
<figure><img src="image_6.png" /><figcaption>Fig. 4. Moves rejected by neighborhood structure N 4 that are feasible.</figcaption></figure>

Theorem 3 shows an important property of neighborhood structure N $_{1}$, namely that the conditions used to prevent a cycle are not only sufficient, as shown in Theorem 2, but also necessary.

Theorem 3. The conditions in Definition 4.1 of neighborhood structure N 1 are not only sufficient but also necessary to prevent cycles when moving a single operation.

Proof. To ensure its generality, the proof is made for the classical FJSP. The notations introduced in Remark 1 are used. By contradiction, let us assume that, from a feasible schedule S$_{1}$ , it is possible to obtain another feasible schedule S$_{2}$ by moving operation u from between operations x and y to between operations v and w while violating at least one condi- tion of N $_{1}$. Let us assume that one of the conditions of N 1 is violated, starting with Condition 1, i.e. v / ∈ F ( u + 1).

If there is a path in S$_{1}$ from the job successor of u , namely u + 1, to v , and no cycle is created by moving operation u from between operations x and y to between operations v and w , then one of the arcs on the path from u + 1 to v is deleted by the move. The arcs deleted by the move are: ( x , u ), ( u , y ) and ( v , w ). The first two arcs ( x , u ) and ( u , y ) cannot be in the set of successors of u + 1 as they contain u , which would make S$_{1}$ infeasible. The last arc ( v , w ) cannot be on the path from u + 1 to v either as v cannot be a predecessor to itself. Thus, if Condition 1 is not satisfied, a cycle is necessarily created.

Let us assume now that Condition 2, i.e. w / ∈ P ( u − 1), is violated. There is a path from w to u − 1 in S$_{1}$ , and this path contains one of the arcs deleted by the move. The deleted arcs containing u , namely ( x , u ) and ( u , y ), cannot be preceding u − 1 as S$_{1}$ would be infeasible, and ( v , w ) cannot be on the path as operation w would succeed itself. Thus, if Condition 2 is not satisfied, a cycle is necessarily created.

Theorem 3 can be reformulated as follows: A move is accepted by neighborhood structure N 1 if and only if it does not create a cycle. Con- versely, a move is rejected by neighborhood structure N 1 if it creates a cycle. This result is important as it makes it possible to check exactly in constant computational time whether a move leads to a cycle or not. Thus, the number of neighbor solutions using this structure is the largest possible number of moves for one operation. Fig. 4 gives a minimal ex- ample of a case with neighborhood structure N 4 to illustrate Theorem 3 and Remark 1. In this FJSP with two jobs, each job is processed on a separate machine (blue and red). We assume that each operation can be performed on both machines. Two moves are considered: (1) Assign- ing operation O$_{1}$$_{,}$$_{2}$ to the blue machine after O$_{2}$$_{,}$$_{2}$ (pink move), and (2) Assigning operation O$_{2}$$_{,}$$_{3}$ to the red machine after O$_{1}$$_{,}$$_{3}$ (purple move). Those two moves are rejected by neighborhood structure N 4 and ac- cepted by neighborhood structure N $_{1}$. The ratios of moves accepted by each neighborhood structure are further studied in the computational experiments of Section 6.2.

4.3. Move evaluation

This section focuses on the exact evaluation of the total travel time given a feasible move of a production or of a transportation operation. This evaluation can be performed in O (1). In this section, some particu- lar cases of travel times associated with dummy operations are defined as follows: For any production operation u , τ a (0) a ( u ) = τ 0 a ( u ) where 0 is the machine index of the initial depot, and τ a ( u ) a ( ∗ ) = 0, in particular τ 0 a ( ∗ ) = 0.

Remark 2. Given a production operation u , t$_{j}$ the vehicle successor of t$_{u}$ and t$_{k}$ the vehicle predecessor of t$_{u}$$_{+1}$ if u is not the last operation of a job. Changing the assignment of u from machine a ( u ) to machine a $^{′}$( u ) leads to the following change of the total travel time:

$$
\begin{equation}
\begin{split}
TTT' = TTT & - \tau_{a(u)}^{a(u-1)} - \tau_{a(j-1)}^{a(u)} + \tau_{a'(u)}^{a(u-1)} + \tau_{a'(j-1)}^{a'(u)} \\
& + \begin{cases}
-\tau_{a(u)}^{a(k)} - \tau_{a(u+1)}^{a(u)} + \tau_{a'(u)}^{a(k)} + \tau_{a(u+1)}^{a'(u)} & \text{if } u \text{ is not the last} \\
0 & \text{operation of a job,} \\
0 & \text{otherwise.}
\end{cases}
\end{split}
\end{equation}
$$

The vehicle that must deliver the job is going from machine a ( u − 1), the machine processing the job predecessor of u , to machine a $^{′}$( u ), the newly assigned machine for u . This new travel time is τ a ( u − 1) a $^{′}$( u ) . The job then goes to its next machine a ( j − 1) in its route to pick up job j − 1 with travel time τ a $^{′}$( u ) a ( j − 1) $^{′}$. Thus, the vehicle must no longer travel from machine a ( u − 1) to machine a ( u ) and from machine a ( u ) to machine a ( j − 1), i.e. saves the respective travel times τ a ( u − 1) a ( u ) and τ a ( u ) a ( j − 1) $^{′}$. For the same reason, if u is not the last operation in the route of its job, the vehicle that must pick up the job changes its empty travel time from τ a ( k ) a ( u ) to τ a ( k ) a $^{′}$( u ) and its loaded travel time from τ a ( u ) a ( u +1) to τ a $^{′}$( u ) a ( u +1) . No other travel times are changed. Remark 2 is illustrated in Fig. 5, where Production operation u , formerly assigned to machine a ( u ), is assigned to machine a $^{′}$( u ), changing the distances traveled by the vehicles for pickup and delivery from the arcs from/to a ( u ) (marked with dotted arcs) to the arcs from/to a $^{′}$( u ) (marked with colored arcs).

Remark 3. Moving transportation operation t$_{u}$ from between trans- portation operations t$_{x}$ and t$_{y}$ to between transportation operations t$_{v}$ and t$_{w}$ induces the following change of the total travel time:

$$
TTT' = TTT - \tau_{a(u-1)}^{a(x)} - \tau_{a(y-1)}^{a(u)} + \tau_{a(y-1)}^{a(x)} - \tau_{a(w-1)}^{a(v)} + \tau_{a(u-1)}^{a(v)} + \tau_{a(w-1)}^{a(u)}
$$

Note that this remark remains valid if the operation is reassigned or only resequenced. Since transportation operation t$_{u}$ is no longer se- quenced between t$_{x}$ and t$_{y}$ , the empty travels from a ( x ) to a ( u − 1) and from a ( u ) to a ( y − 1) are no longer required. Thus, τ a ( x ) a ( u − 1) and τ a ( u ) a ( y − 1) can be subtracted from the total travel time. The vehicle which performed t$_{u}$ before the move must now travel from a ( x ) to a ( y − 1), adding τ a ( x ) a ( y − 1)
<figure><img src="image_7.png" /><figcaption>Fig. 5. Impact of changing the assignment of a production operation on the total travel time.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 6. Impact of moving a transportation operation on the total travel time.</figcaption></figure>

to the travel time after the move. As t<sub>w</sub> is not the vehicle successor of t<sub>v</sub> after the move, the travel time τ<sup>a(v)</sup><sub>a(w-1)</sub> is subtracted from the travel time, and machines a(u-1) and a(u) are added in the vehicle route in that order, adding τ<sup>a(v)</sup><sub>a(u-1)</sub> and τ<sup>a(u)</sup><sub>a(w-1)</sub> to the new travel time. Note that τ<sup>a(u-1)</sup><sub>a(u)</sub> and τ<sup>a(u)</sup><sub>a(u+1)</sub> do not change since the travel times are not vehicle dependent. No other travel times are changed.

Remark 3 is illustrated in Fig. 6, where the loaded travel time of t<sub>u</sub> (marked with a bold arc) remains the same, while the empty travel times from a(x) to a(u − 1), from a(u) to a(y − 1) and from a(v) to a(w − 1) (marked with dotted arcs) are replaced by the empty travel times from a(v) to a(u − 1), from a(u) to a(w − 1) and from a(x) to a(y) (marked with colored arcs).

5. Tabu search and optimization strategies

To solve the scheduling problem described in Section 3.1, a tabu
search procedure is used, the pseudo-code of which can be found in
Algorithm 1. The algorithm starts from an acyclic initial solution, then
performs moves according to one of the neighborhood structures pre-
sented in Section 4.1. Moves are then classified (Step 5) using the move
evaluation on the makespan presented in Section 5.1, the move eval-
uation on the total travel time presented in Section 4.3, or a mix of
both move evaluations. A move is then chosen among the best ones
(Step 6), performed (Step 7) and added to the tabu list (Step 9). The
best solutions regarding the makespan and the total travel time are
stored. All choices regarding the generation of moves, the selected
neighborhood structure, the move evaluation, and the length of the
tabu list depend on the optimization strategy, which is described in
Section 5.2.

5.1. Move classification

For completeness, let us recall the upper and lower bound system
introduced in our previous work to evaluate the makespan in constant
processing time. While the lower bounds are proven to be smaller than

**Algorithm 1 Tabu search framework.**

1: Determine initial solution s<sub>current</sub>.

2: Set s<sub>best</sub> ← s<sub>current</sub>.

3: **while** termination criterion not met **do**

4: Generate neighborhood N<sub>k</sub>(s<sub>current</sub>).

5: Classify neighbor solutions

6: Among the best class of moves, select randomly non-tabu move s<sub>next</sub> ∈ N<sub>k</sub>(s<sub>current</sub>).

7: Perform move: s<sub>current</sub> ← s<sub>next</sub>.

8: Update makespan and conjunctive graph.

9: Update tabu list.

10: **if** s<sub>current</sub> > s<sub>best</sub> **then**

11: s<sub>best</sub> ← s<sub>current</sub>

12: Return s<sub>best</sub>.

the actual makespan of a neighbor solution, the upper bounds are actu-
ally bounds on the paths modified by the moves, as a greater makespan
can exist on other paths but would require a more costly evaluation. We
introduce some notations that are specific to this section. For a vertex u,
r<sup>J</sup><sub>u</sub> and q<sup>J</sup><sub>u</sub> respectively denote the head (longest path from dummy start-
ing node 0 to u) and tail (longest path from a successor of u to dummy
node *) of operation u in the job route of the operation, and r<sup>M</sup><sub>u</sub> and
q<sup>M</sup> respectively denote the head and tail of operation u in the resource
route of the operation.

**Definition 5.1** (Bounds on the makespan after moving a production operation). After moving production operation *u* between production operations *v* and *w*, the following bounds on the length of the modified paths can be derived:

$$
\begin{align*}
U B(u, v, w) ={}& \max \left( \max(r_{t_u} + \tilde{p}_{t_u}^J, \hat{r}_v + p_v) \right. \\
& \qquad \left. + p_u^a + \max(p_w + \hat{q}_w, \tilde{q}_u^J), \right. \\
& \qquad \left. r_{t_u} + \tilde{p}_{t_u}^M + \hat{q}_{t_u}^M, \right. \\
& \qquad \left. r_{t_k} + \tilde{p}_{t_k}^M + \hat{q}_u^J \right)
\end{align*}
$$
<table><caption>**Table 3**
Mean number of moves and percentage of accepted moves by the different neighborhood structures.</caption><thead><tr><th rowspan="3">Instances</th><th rowspan="3">Flexibility</th><th rowspan="3">|V|</th><th colspan="4">Production operations</th><th colspan="4">Transportation operations</th></tr><tr><th colspan="4">#moves</th><th colspan="4">Accepted moves (%)</th></tr><tr><th>N<sub>1</sub></th><th>N<sub>2</sub></th><th>N<sub>3</sub></th><th>N<sub>4</sub></th><th>N<sub>1</sub></th><th>N<sub>2</sub></th><th>N<sub>3</sub></th><th>N<sub>4</sub></th></tr></thead><tbody><tr><td colspan="10" style="text-align: left; font-weight: bold;">Moves on the critical paths</td></tr><tr><td colspan="2">Data set 1</td><td>Medium</td><td>2</td><td>22.2</td><td>80.1</td><td>72.1</td><td>65.8</td><td>56.6</td><td>96.8</td><td>62.8</td><td>53.7</td><td>45.0</td><td>11.2</td></tr><tr><td rowspan="8">Data set 2</td><td>Low</td><td>2</td><td>756.2</td><td>10.8</td><td>8.0</td><td>6.1</td><td>2.4</td><td>4,149.6</td><td>11.1</td><td>7.6</td><td>6.7</td><td>0.9</td></tr><tr><td>Medium</td><td>2</td><td>870.5</td><td>11.5</td><td>8.9</td><td>7.2</td><td>3.7</td><td>2,828.3</td><td>11.0</td><td>7.5</td><td>6.5</td><td>1.0</td></tr><tr><td>High</td><td>2</td><td>705.6</td><td>12.6</td><td>9.2</td><td>7.4</td><td>4.2</td><td>1,532.4</td><td>11.3</td><td>7.4</td><td>6.5</td><td>0.9</td></tr><tr><td>Low</td><td>4</td><td>439.7</td><td>14.2</td><td>7.7</td><td>5.9</td><td>3.6</td><td>1,727.5</td><td>13.8</td><td>9.2</td><td>7.5</td><td>2.0</td></tr><tr><td>Medium</td><td>4</td><td>584.1</td><td>15.1</td><td>9.3</td><td>7.4</td><td>4.7</td><td>1,505.5</td><td>14.9</td><td>9.6</td><td>7.8</td><td>2.1</td></tr><tr><td>High</td><td>4</td><td>701.3</td><td>17.7</td><td>11.5</td><td>9.1</td><td>5.4</td><td>1,076.4</td><td>14.5</td><td>8.9</td><td>7.0</td><td>2.0</td></tr><tr><td>Low</td><td>6</td><td>490.4</td><td>16.2</td><td>8.3</td><td>6.2</td><td>3.6</td><td>2,333.4</td><td>17.0</td><td>11.4</td><td>9.2</td><td>2.9</td></tr><tr><td>Medium</td><td>6</td><td>576.1</td><td>18.3</td><td>10.0</td><td>8.0</td><td>5.2</td><td>1,329.3</td><td>16.8</td><td>10.5</td><td>8.0</td><td>3.0</td></tr><tr><td>High</td><td>6</td><td>686.3</td><td>20.3</td><td>12.0</td><td>9.9</td><td>6.0</td><td>1,178.0</td><td>16.7</td><td>10.8</td><td>8.3</td><td>3.2</td></tr><tr><td colspan="10" style="text-align: left; font-weight: bold;">Moves on the entire graph</td></tr><tr><td colspan="2">Data set 1</td><td>Medium</td><td>2</td><td>83.1</td><td>22.0</td><td>20.0</td><td>18.1</td><td>15.0</td><td>318.7</td><td>62.8</td><td>54.1</td><td>45.6</td><td>11.4</td></tr><tr><td rowspan="8">Data set 2</td><td>Low</td><td>2</td><td>14,074.7</td><td>1.8</td><td>1.3</td><td>1.0</td><td>0.4</td><td>91,344.7</td><td>10.9</td><td>7.1</td><td>6.1</td><td>0.9</td></tr><tr><td>Medium</td><td>2</td><td>28,413.9</td><td>3.6</td><td>2.7</td><td>2.1</td><td>1.1</td><td>91,344.7</td><td>10.9</td><td>7.2</td><td>6.2</td><td>0.9</td></tr><tr><td>High</td><td>2</td><td>46,757.5</td><td>6.1</td><td>4.6</td><td>3.7</td><td>2.0</td><td>91,344.7</td><td>11.1</td><td>7.2</td><td>6.3</td><td>0.8</td></tr><tr><td>Low</td><td>4</td><td>14,018.4</td><td>2.2</td><td>1.4</td><td>1.0</td><td>0.5</td><td>91,928.7</td><td>14.4</td><td>9.1</td><td>7.4</td><td>2.0</td></tr><tr><td>Medium</td><td>4</td><td>28,117.2</td><td>4.4</td><td>2.8</td><td>2.2</td><td>1.3</td><td>91,928.7</td><td>14.8</td><td>9.4</td><td>7.6</td><td>2.1</td></tr><tr><td>High</td><td>4</td><td>46,690.8</td><td>7.7</td><td>5.0</td><td>4.0</td><td>2.4</td><td>91,928.7</td><td>15.1</td><td>9.5</td><td>7.7</td><td>2.1</td></tr><tr><td>Low</td><td>6</td><td>13,963.1</td><td>2.5</td><td>1.4</td><td>1.1</td><td>0.6</td><td>92,512.7</td><td>16.9</td><td>10.6</td><td>8.3</td><td>2.9</td></tr><tr><td>Medium</td><td>6</td><td>28,093.1</td><td>5.0</td><td>2.9</td><td>2.3</td><td>1.4</td><td>92,512.7</td><td>17.4</td><td>11.0</td><td>8.6</td><td>3.1</td></tr><tr><td>High</td><td>6</td><td>46,642.8</td><td>8.6</td><td>5.2</td><td>4.1</td><td>2.6</td><td>92,512.7</td><td>17.6</td><td>11.2</td><td>8.7</td><td>3.1</td></tr></tbody></table>

<table><caption>**Table 4**
Mean best makespan and mean total travel time in lexicographic order on instances from data set 2.</caption><thead><tr><th rowspan="2">Method</th><th rowspan="2">Metric</th><th colspan="2">N<sub>1</sub></th><th colspan="2">N<sub>2</sub></th><th colspan="2">N<sub>3</sub></th><th colspan="2">N<sub>4</sub></th></tr><tr><th>C<sub>max</sub></th><th>TTT</th><th>C<sub>max</sub></th><th>TTT</th><th>C<sub>max</sub></th><th>TTT</th><th>C<sub>max</sub></th><th>TTT</th></tr></thead><tbody><tr><td rowspan="4">O<sub>1</sub></td><td>mean C<sup>*</sup><sub>max</sub></td><td>4,133.6</td><td>11,976.3</td><td>3,812.9</td><td>11,282.1</td><td>4,120.6</td><td>11,928.7</td><td>4,186.6</td><td>12,087.9</td></tr><tr><td>mean TTT<sup>*</sup></td><td>4,181.1</td><td>11,885.4</td><td>3,844.9</td><td>11,194.0</td><td>4,140.7</td><td>11,854.0</td><td>4,214.7</td><td>12,025.1</td></tr><tr><td>best C<sup>*</sup><sub>max</sub></td><td>1</td><td>0</td><td>5</td><td>0</td><td>1</td><td>0</td><td>2</td><td>0</td></tr><tr><td>best TTT<sup>*</sup></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">O<sub>2</sub></td><td>mean C<sup>*</sup><sub>max</sub></td><td>3,772.4</td><td>11,408.4</td><td>4,393.3</td><td>12,331.4</td><td>4,259.8</td><td>11,882.8</td><td><b>3,693.3</b></td><td>10,849.5</td></tr><tr><td>mean TTT<sup>*</sup></td><td>3,812.6</td><td><b>8,073.6</b></td><td>4,496.1</td><td>9,584.0</td><td>4,388.0</td><td>9,041.0</td><td>3,747.0</td><td>8,425.3</td></tr><tr><td>best C<sup>*</sup><sub>max</sub></td><td>10</td><td></td><td>0</td><td></td><td>0</td><td></td><td>10</td><td></td></tr><tr><td>best TTT<sup>*</sup></td><td></td><td>44</td><td></td><td></td><td></td><td>3</td><td></td><td>7</td><td></td></tr><tr><td rowspan="4">O<sub>3</sub></td><td>mean C<sup>*</sup><sub>max</sub></td><td>3,765.5</td><td>10,560.5</td><td>3,872.2</td><td>10,490.6</td><td>4,101.6</td><td>11,515.5</td><td>4,148.4</td><td>11,590.4</td></tr><tr><td>mean TTT<sup>*</sup></td><td>3,810.9</td><td>10,462.1</td><td>3,911.5</td><td>10,389.8</td><td>4,134.8</td><td>11,449.0</td><td>4,170.4</td><td>11,524.4</td></tr><tr><td>best C<sup>*</sup><sub>max</sub></td><td>8</td><td></td><td>13</td><td></td><td>4</td><td></td><td>6</td><td></td></tr><tr><td>best TTT<sup>*</sup></td><td></td><td>0</td><td></td><td></td><td></td><td>0</td><td></td><td>0</td><td></td></tr></tbody></table>

$$
\begin{aligned}
LB(u, v, w) &= \max (r_{t_u} + \tilde{p}_{t_u}^J, \tilde{r}_v + p_v) + p_u^q + \max(p_{uw} + \tilde{q}_w, \tilde{q}_u^J), \\
r_{t_u} + \tilde{p}_{t_u}^M + \tilde{q}_{t_u}^M, \\
\tilde{r}_{t_k} + \tilde{p}_{t_k}^M + \tilde{q}_{t_k}^J
\end{aligned}
$$

with $(t_u, u)$, $(u, t_u + 1) \in \mathcal{A}$ and $(t_k, t_{u+1}) \in \Pi$ and where:

$$ \tilde{p}_{t_u}^J = d(a(u-1), a(u)) $$

$$ \tilde{p}_{t_u}^M = \tilde{p}_{t_u}^J + d(a(u), a(j-1)) $$

$$ \tilde{p}_{t_k}^M = p_{t_k}^J + d(a(k), a(u)) $$

$$ \tilde{q}_u^J = \max(d(a(u), a(u+1)) + q_{t_{u+1}}^J, p_{t_{u+1}}^M - p_{t_{u+1}}^J + d(a(u), a(u+1)) + q_{t_{u+1}}^M) $$

$$ \hat{q}_{t_u}^M = \begin{cases} q_{t_u}^M + \max(0, \tilde{p}_{t_k}^M + \tilde{q}_u^J - \max(p_{t_k}^J + q_{t_k}^J, p_{t_k}^M + q_u^J)) & \text{if } t_k \in F(t_u) \\ q_{t_u}^J & \text{if } t_k \notin F(t_u) \end{cases} $$

$$ \hat{q}_{t_u}^J = \begin{cases} q_{t_u}^M + \max(0, \tilde{p}_{t_k}^M + \tilde{q}_u^J - \max(p_{t_k}^J + q_{t_k}^J, p_{t_k}^M + q_u^J)) & \text{if } t_k \in F(t_u) \\ q_{t_u}^J & \text{if } t_k \notin F(t_u) \end{cases} $$

$$ \hat{r}_v = \begin{cases} r_v + \max(0, r_{t_u} + \tilde{p}_{t_u}^M - r_{t_j}) & \text{if } t_j \in P(v) \\ r_v & \text{if } t_j \notin P(v) \end{cases} $$

$$ \hat{q}_w = \begin{cases} q_w + \max(0, \max(p_{t_k}^J + q_{t_k}^J, \tilde{p}_{t_k}^M + \tilde{q}_u^J) - q_{k-1}^J) & \text{if } t_k \in F(w) \\ q_w & \text{if } t_k \notin F(w) \end{cases} $$

$$ \tilde{r}_v = r_v + \begin{cases} -r_y + \max(r_{t_j} + p_{t_j}^J, r_x + p_x) & \text{if } u \in CP(v) \\ 0 & \text{if } u \notin CP(v) \end{cases} $$

$$ \tilde{r}_{t_k} = r_{t_k} + \begin{cases} -r_y + \max(r_{t_j} + p_{t_j}^J, r_x + p_x) & \text{if } u \in CP(t_k) \\ 0 & \text{if } u \notin CP(t_k) \end{cases} $$

$$ \tilde{q}_w = q_w + \begin{cases} -q_x + \max(p_{t_{x+1}}^J + q_{t_{x+1}}^J, p_{t_{x+1}}^M + q_{t_{x+1}}^M, p_y + q_y) & \text{if } u \in CF(w) \\ 0 & \text{if } u \notin CF(w) \end{cases} $$

$$ \tilde{r}_w = \begin{cases} \max(0, q_{k-1}^J - \max(p_{t_k}^J + q_{t_k}^J, \tilde{p}_{t_k}^M + \tilde{q}_u^J)) & \text{if } t_k \in CF(w) \\ 0 & \text{if } t_k \notin CF(w) \end{cases} $$
<table><caption>**Table 5**
Number of best makespan and total travel times by types of instances on data set 2 for the three selected methods.</caption><thead><tr><th></th><th></th><th>O<sub>1</sub> - N<sub>2</sub></th><th>O<sub>2</sub> - N<sub>4</sub></th><th>O<sub>3</sub> - N<sub>1</sub></th></tr></thead><tbody><tr><td rowspan="6">Flexibility level</td><td rowspan="2">Low</td><td>Best C<sub>max</sub></td><td>3</td><td>6</td><td>9</td></tr><tr><td>Best TTT</td><td>0</td><td>18</td><td>0</td></tr><tr><td rowspan="2">Medium</td><td>Best C<sub>max</sub></td><td>6</td><td>5</td><td>7</td></tr><tr><td>Best TTT</td><td>0</td><td>18</td><td>0</td></tr><tr><td rowspan="2">High</td><td>Best C<sub>max</sub></td><td>6</td><td>5</td><td>7</td></tr><tr><td>Best TTT</td><td>0</td><td>18</td><td>0</td></tr><tr><td rowspan="6">Number of vehicles</td><td rowspan="2">2</td><td>Best C<sub>max</sub></td><td>5</td><td>3</td><td>10</td></tr><tr><td>Best TTT</td><td>0</td><td>18</td><td>0</td></tr><tr><td rowspan="2">4</td><td>Best C<sub>max</sub></td><td>4</td><td>13</td><td>1</td></tr><tr><td>Best TTT</td><td>0</td><td>18</td><td>0</td></tr><tr><td rowspan="2">6</td><td>Best C<sub>max</sub></td><td>6</td><td>0</td><td>12</td></tr><tr><td>Best TTT</td><td>0</td><td>18</td><td>0</td></tr></tbody></table>

<table><caption>**Table 6**
Best makespan and associated total travel time on instances from data set 1.</caption><thead><tr><th rowspan="3">Instance</th><th colspan="2">O<sub>3</sub> - N<sub>1</sub></th><th colspan="2">P</th><th colspan="3">HF</th></tr><tr><th colspan="2">objectives</th><th colspan="2">execution time (s)</th><th rowspan="2">C<sub>max</sub></th><th rowspan="2">time (s)</th></tr><tr><th>C<sub>max</sub></th><th>TTT</th><th>C<sub>max</sub></th><th>TTT</th><th>C<sub>max</sub></th></tr></thead><tbody><tr><td>fjsp 1</td><td>134.0</td><td>192.0</td><td>134.0</td><td>192.0</td><td>7.8</td><td>15.8</td><td>134.0</td><td>159.3</td></tr><tr><td>fjsp 2</td><td>114.0</td><td>138.0</td><td>114.0</td><td>134.0</td><td>14.3</td><td>7.2</td><td>114.0</td><td>16.3</td></tr><tr><td>fjsp 3</td><td>120.0</td><td>128.0</td><td>120.0</td><td>124.0</td><td>0.8</td><td>0.8</td><td>120.0</td><td>4.7</td></tr><tr><td>fjsp 4</td><td>116.0</td><td>174.0</td><td>114.0</td><td>174.0</td><td>16.1</td><td>5.9</td><td>114.0</td><td>306.0</td></tr><tr><td>fjsp 5</td><td>94.0</td><td>104.0</td><td>94.0</td><td>102.0</td><td>0.2</td><td>0.7</td><td>94.0</td><td>2.7</td></tr><tr><td>fjsp 6</td><td>138.0</td><td>182.0</td><td>138.0</td><td>168.0</td><td>20.1</td><td>118.6</td><td>138.0</td><td>44.1</td></tr><tr><td>fjsp 7</td><td>116.0</td><td>182.0</td><td>108.0</td><td>-</td><td>1,861.6</td><td>3,600.1</td><td>112.0</td><td>3,600.1</td></tr><tr><td>fjsp 8</td><td>178.0</td><td>210.0</td><td>178.0</td><td>190.0</td><td>12.1</td><td>486.0</td><td>178.0</td><td>54.8</td></tr><tr><td>fjsp 9</td><td>146.0</td><td>172.0</td><td>144.0</td><td>144.0</td><td>13.9</td><td>7.9</td><td>144.0</td><td>23.1</td></tr><tr><td>fjsp 10</td><td>174.0</td><td>182.0</td><td>174.0</td><td>182.0</td><td>37.9</td><td>642.0</td><td>174.0</td><td>1,477.5</td></tr></tbody></table>

<table><caption>**Table 7**
Mean gap, number of variables and constraints on data sets 1 and 2.</caption><thead><tr><th rowspan="2">Data set</th><th colspan="2">HF</th><th colspan="2">(P)</th><th rowspan="2">gap</th><th rowspan="2">#variables</th><th rowspan="2">#constraints</th></tr><tr><th>gap</th><th>#variables</th><th>#constraints</th></tr></thead><tbody><tr><td>1</td><td>100.0%</td><td>3,532.8</td><td>16,873.4</td><td>27.5%</td><td>886.2</td><td>3,490.0</td></tr><tr><td>2</td><td>56.4%</td><td>922,220.7</td><td>4,309,957.0</td><td>50.3%</td><td>186,840.3</td><td>597,964.2</td></tr></tbody></table>

$$
\tilde{q}_{t_u}^M = q_{t_u}^M + \begin{cases} -q_x + \max(p_{t_{v+1}}^J + q_{t_{v+1}}^J, p_{t_{v+1}}^M + q_{t_{v+1}}^M, p_y + q_y) & \text{if } u \in CF(t_j) \\ 0 & \text{if } u \notin CF(t_j) \end{cases} \\ - \begin{cases} \max(0, q_{t_{k-1}}^J - \max(p_{t_k}^J + q_{t_k}^J, \tilde{p}_{t_k}^M + \tilde{q}_u^J)) & \text{if } t_k \in CF(t_j) \\ 0 & \text{if } t_k \notin CF(t_j) \end{cases}
$$

**Definition 5.2** (Bounds on the makespan after moving a transportation operation). After moving transportation operation $t_u$ between transportation operations $t_v$ and $t_w$, the following bounds on the length of the modified paths can be derived:

$$
U B(t_u, t_v, t_w) = \max(r_{u-1} + p_{u-1}, r_{t_v} + \tilde{p}_{t_u}^M) + \max(p_{t_u}^J + q_{t_u}^J, \tilde{p}_{t_u}^M \\
+ \max(p_{t_v}^J + q_{t_v}^J, p_{t_v}^M + q_{t_v}^M))
$$

$$
LB(t_u, t_v, t_w) = \max(r_{u-1} + p_{u-1}, \tilde{r}_{t_v} + \tilde{p}_{t_v}^M) + \max(p_{t_u}^J + q_{t_u}^J, \tilde{p}_{t_u}^M \\
+ \max(p_{t_v}^J + \tilde{q}_{t_v}^J, p_{t_v}^M + \tilde{q}_{t_v}^M))
$$

with $(u-1, t_u) \in \mathcal{A}$ and where:

$$
\tilde{p}_{t_v}^M = p_{t_v}^J + d(a(v), a(u-1))
$$

$$
\tilde{p}_{t_s}^M = p_{t_s}^J + d(a(u), a(w-1))
$$

$$
\tilde{p}_{t_v}^M = p_{t_v}^J + d(a(x), a(y-1))
$$

$$
\tilde{r}_{t_v} = \begin{cases} r_{t_v} - r_{t_j} + \max(r_{y-1} + p_{y-1}, r_{t_s} + \tilde{p}_{t_s}^M) & \text{if } t_u \in CP(t_v) \\ r_{t_v} & \text{if } t_u \notin CP(t_v) \end{cases}
$$

$$
\tilde{q}_{t_u}^J = \begin{cases} q_{t_u}^J - \max(p_{t_s}^J + q_{t_s}^J, p_{t_s}^M + q_{t_s}^M) + p_{t_s}^J + \max(p_x + q_x, D(a(x), a(y-1)) + \\ \max(p_{t_s}^J + q_{t_s}^J, p_{t_s}^M + q_{t_s}^M)) & \text{if } t_u \in CF(w) \\ q_{t_u}^J & \text{if } t_u \notin CF(w) \end{cases}
$$

$$
\tilde{q}_{t_w}^M = \begin{cases} q_{t_w}^M - \max(p_{t_s}^J + q_{t_s}^J, p_{t_s}^M + q_{t_s}^M) + p_{t_s}^J + \max(p_x + q_x, D(a(x), a(y-1)) + \\ \max(p_{t_s}^J + q_{t_s}^J, p_{t_s}^M + q_{t_s}^M)) & \text{if } t_u \in CF(t_z) \\ q_{t_w}^M & \text{if } t_u \notin CF(t_z) \end{cases}
$$

For a given solution $s_{current}$ with a makespan $C_{max}$, a move $m$ is ranked in the following five classes:

$R_1$ if $U B(m) < C_{max}$,

$R_2$ if $U B(m) = C_{max}$,

$R_3$ if $LB(m) < C_{max}$,

$R_4$ if $LB(m) > C_{max}$,

$R_5$ otherwise.

## 5.2. Optimization strategies

To evaluate the impact of our contributions, we use three optimization strategies, from the simplest to the most sophisticated: Naive, sequential, and simultaneous. Each optimization strategy is then tested in Section 6.3 with a running time of 10 minutes.

**Optimization strategy $O_1$ (naive).** This method optimizes the makespan without any consideration for the total travel time other than retaining the best solutions for both criteria. In this method, neighbor solutions are generated along the critical paths, then moves are classified and a move is randomly chosen in the best class of moves. If the best class of moves is $R_1$, a move $m$ is chosen with probability $\frac{C_{max} - U B(m)}{\sum_{m'' \in R_1} C_{max} - U B(m)}$. Finally, the size of the tabu list is the number of moves in class $R_2$.

**Optimization strategy $O_2$ (sequential).** This strategy divides the computational time into two equal parts, with half of the time dedicated to the optimization of the makespan, and the other half dedicated to the optimization of the total travel time. The first part of the method (optimizing makespan) is the same as the optimization strategy $O_1$ described above. In the second part of the method (optimizing total travel time), the neighbor solutions are generated on the entire graph, then their total travel time is computed using formulas from Remarks 2 and 3. A move $m$ with a total travel time of $TTT(m)$ is randomly selected according to probability $\frac{\max_{m''} TTT(m') - TTT(m)}{\sum_{m''} \max_{m''} TTT(m') - TTT(m'')}$. The size of the tabu list is equal to the number of moves with the same total travel time as the current solution.

**Optimization strategy $O_3$ (simultaneous).** In this strategy, the makespan and the total travel time are simultaneously optimized when exploring the solution space. The strategy follows strategy $O_1$ but, when the best class of moves is $R_1$, instead of selecting a move according to the upper bound on the makespan, a move $m$ is selected according to probability $\frac{\max_{m'} TTT(m') - TTT(m) + C_{max} - U B(m)}{\sum_{m'} TTT(m') + U B(m)}$.

## 6. Computational experiments

Section 6.1 describes how the computational experiments were conducted. The neighborhood structures proposed in Section 4 are compared in Section 6.2. The three optimization strategies proposed in Section 5.2 are then compared in Section 6.3. Numerical results obtained with the MILP model proposed in Section 3.2 are reported in Section 6.4 and compared to an optimization approach and to the current state-of-the-art model for the FJSPT. Finally, Section 6.5 analyzes the impact of the flexibility levels (average number of machines per operation) on the total travel time.
<caption>**Table 8**</caption>

Mean makespan and total travel time depending on machine flexibility and number of vehicles on instances from data set 2 with optimization strategy $O_2 - N_4$.

<table><thead><tr><th rowspan="3">Number of vehicles</th><th colspan="8">Machine flexibility</th></tr><tr><th colspan="2">Low</th><th colspan="2">Medium</th><th colspan="2">High</th><th colspan="2">mean</th></tr><tr><th>C<sub>max</sub></th><th>TTT</th><th>C<sub>max</sub></th><th>TTT</th><th>C<sub>max</sub></th><th>TTT</th><th>C<sub>max</sub></th><th>TTT</th></tr></thead><tbody><tr><td>2</td><td>5,214.8</td><td>8,784.5</td><td>4,286.0</td><td>6,879.7</td><td>3,791.7</td><td>5,688.2</td><td>4,430.8</td><td>7,117.4</td></tr><tr><td>4</td><td>3,669.5</td><td>9,175.8</td><td>3,465.0</td><td>8,161.8</td><td>3,239.5</td><td>7,301.8</td><td>3,458.0</td><td>8,213.2</td></tr><tr><td>6</td><td>3,665.7</td><td>10,570.5</td><td>3,265.3</td><td>9,794.8</td><td>3,125.2</td><td>9,470.7</td><td>3,352.1</td><td>9,945.3</td></tr><tr><td>mean</td><td>4,183.3</td><td>9,510.3</td><td>3,672.1</td><td>8,278.8</td><td>3,385.4</td><td>7,486.9</td><td></td><td></td></tr></tbody></table>

## 6.1. Design of experiments

The computational experiments have been conducted on benchmark instances. Data set 1 was proposed in Deroussi and Norre (2010) and includes ten small-size instances adapted from Bilge and Ulusoy (1995) with a machine flexibility of 2 (each operation can be assigned to exactly two machines). These instances are made up of about 20 operations that can be performed on two machines and only two vehicles. Data set 2 was proposed in Berterottière et al. (2024) and is composed of 18 large-size (hundred operations) instances adapted from Dauzère-Pérès and Paulli (1997) with various levels of machine flexibility. These instances include hundreds of operations and two, four, and six vehicles. The three levels of flexibility are: (1) *Low*, where each machine has a 10% chance of being able to perform an operation when generating the instances, (2) *Medium*, where each machine has a 30% chance of being able to perform an operation, and (3) *High*, where each machine has a 50% chance of being able to perform an operation. All instances can be found at https://github.com/lucasberter/FJSPT.

The optimization strategies have been implemented in Julia 1.6 on an Intel(R) Core(TM) i7-9700 3.00GHz with 32GB RAM. In order to fairly compare the approaches, the choice was made to give an overall time limit of 600 seconds of running time per instance. For the sequential optimization strategy $O_2$, the first phase ends after five minutes (300 seconds). As the overall framework is shown to be effective in Berterottière et al. (2024), no comparison with other approaches from the literature has been made. It should be noted that the results may differ from those published previously as, in this problem definition, a vehicle must always be available for a transfer, even if the two consecutive operations are performed by the same machine. MILP models have been implemented using the package JuMP with the solver Gurobi 12.0.1, and have been given a maximum running time of one hour (3,600 seconds).

## 6.2. Analysis of the neighborhood structures

In this section, optimization strategy $O_1$ is used with neighborhood structure $N_1$ to explore the solution space and, at each iteration, all the neighborhood structures are tested. The mean number of moves that are generated and the mean percentage of moves accepted by the neighborhood structures introduced in Section 4 are reported in Table 3, both for moves on the critical paths and for moves on the entire graph, as it is done in the sequential method $O_2$. Instances have been grouped by similarities, with all instances of data set 1 in the same category and instances of data set 2 grouped by machine flexibility and the number of available vehicles.

The percentage of moves allowed for data set 1 is much larger than for data set 2, which is to be expected given the much larger size of the instances in data set 2. In a *Medium* or large instance with hundreds of operations, it is very unlikely to make large moves in the schedule, as an operation at the beginning of the graph is very likely to precede an operation at the end of the graph. In data set 2, we can see that the number of moves increases with machine flexibility. The number of transportation operation moves is much larger when vehicle flexibility

is low, which can be explained by the fact that the critical paths of large instances with few vehicles are made up of transportation operations, and the number of transportation operation moves is therefore larger. It seems that the number of vehicles impacts the percentage of moves accepted by the different neighborhood structures for moves of both production and transportation operations. A small number of vehicles creates connections between jobs, which potentially leads to cycles even when moving a production operation.

Another observation that can be made from Table 3 is that the percentage of moves accepted for transportation operations remains consistent when generated along all critical paths or on the entire graph, which is not the case for production operations, as the percentage of accepted moves drops drastically when moves are generated on the entire graph. This can be explained by the fact that the transportation resources are more critical than the production machines on those instances. Thus, there are not many differences between moves generated on a critical path and moves generated on the entire graph for transportation operations. Note also that moves are, generally speaking, more likely to be feasible on a critical path as, in particular, swapping two operations is guaranteed to be feasible on a critical path, which is not the case otherwise.

## 6.3. Comparison of the approaches

In the following, we compare the approaches introduced in Section 5.2 on the benchmark instances from data set 2. For each run, the solution with the best makespan and the solution with the best total travel time have been recorded, and the mean scores can be found in Table 4. For each combination of optimization approach and neighborhood structure, the mean best makespan with the corresponding mean total travel time (line “mean $C_{max}^*$”) and the mean best total travel time with the corresponding mean makespan (line “mean $TTT^*$”) can be found. Also, the number of instances where the best makespan has been found is provided in line “best $C_{max}^*$”, and the number of instances where the best total travel time has been found is provided in line “best $TTT^*$”. Note that there are 18 instances evaluated for three different numbers of vehicles, resulting in a total of 54 test cases. The results of each case are compared across all optimization methods and neighborhood structures. The total number of best results may exceed 54, as multiple configurations can achieve identical outcomes for some instances.

The first observations that can be made from Table 4 are that there is no optimization approach that dominates the other with every neighborhood structure, and that there is no neighborhood structure that dominates the others on every approach. Naive method $O_1$, although generally less competitive in terms of average performance, obtains the best $C_{max}^*$ in a small number of instances, indicating that it may still perform well in specific scenarios, especially when using balanced neighborhood structure $N_2$. Sequential method $O_2$ exhibits very good performance in minimizing $TTT$, with particularly competitive results using neighborhood structures $N_1$ and $N_4$, achieving the lowest mean $TTT$ of 8,073.6 with $N_1$. Furthermore, $O_2$ achieves the best mean makespan of 3,693.3 using another neighborhood structure, namely $N_4$. Interestingly, this method works very well with the smallest and the largest neighborhood
structures, but not very efficiently with the two more balanced neighbor-
hood structures. As this method is the only one generating moves on the
entire graph, using the small neighborhood structure can be beneficial
to limit the number of evaluated moves, and using the largest neighbor-
hood structure can help to perform interesting moves that would not
be performed otherwise. Simultaneous method O₃ generally yields bal-
anced performance across both criteria, and seems to benefit from the
largest neighborhood structures N'₁ and N'₂.

Table 5 compares the best solutions obtained with the three meth-
ods for the makespan and the total travel time. Only one combination
of approach/neighborhood structure is kept in order to compare the
approaches against each other. For each approach, the neighborhood
structure has been selected according to the lowest mean makespan from
Table 4. The results are divided according to the flexibility level and to
the number of vehicles.

Table 5 shows that optimization approach O₃ – N'₁ has the best re-
sults for the makespan on 23 of the 54 instances, i.e., the best results
across the three approaches. For the total travel time, sequential ap-
proach O₂ – N'₄ obtains the best results on every instance, indicating
that the second part of the approach dedicated to optimizing the total
travel time is very efficient.

6.4. *Comparison with the MILP formulation*

In this section, we experimentally show that the new MILP formu-
lation proposed in Section 3.2 performs better than the current state-
of-the-art MILP formulation from the literature, namely the formulation
from Homayouni and Fontes (2021), denoted HF in this section. The
computational experiments were conducted on instances from data set
1 from Deroussi and Norre (2010) as these instances are small enough
to be solved by MILP solvers. The optimal results obtained by the MILP
model are also used to validate the results from one of the proposed
approaches, namely O₃ − N'₁. The results as well as the computational
times for the MILP models are reported in Table 6.

Several insights can be drawn from Table 6. First, it shows that optimization method O₃ with neighborhood structure N'₁ has an optimal solution for the makespan that is close to or equal to the optimal makespan, and about 20% higher than the best total travel time in the worst case (instance 9). Then, note that the proposed MILP model P outperforms the model HF from Homayouni and Fontes (2021) on all instances.

In addition to the results presented in Table 6, further performance
indicators can be found in Table 7 to give a clearer comparison between
models *P* and *HF*. For each dataset, the average integrality gap is re-
ported, computed for each instance as 100$$\frac{\bar{s}-\bar{s}_s}{\bar{s}}$$, where $\bar{s}$ denotes the best
known makespan for the instance, and $\bar{s}$ denotes the lower bound ob-
tained by relaxing the integrality constraints of the models. The mean
numbers of variables and constraints are also reported. Note that our
MILP leads to better gap and is smaller in terms of numbers of variables
and constraints.

6.5. *Impact of machine flexibility*

In the FJSP, machine flexibility refers to the number of possible ma-
machines to which operations can be assigned, e.g. a machine flexibility
of 2.6 for a problem instance means that each operation can on aver-
age be assigned to one out of 2.6 machines. The JSP is a special case
where the machine flexibility is the lowest, as operations can be as-
signed to only one machine, i.e. the machines on which operations are
processed are already known before solving the problem. Table 8 re-
ports the mean lowest value of the makespan and the total travel time
with lexicographic optimization using sequential optimization strategy
O₂ – N'₄ for instances in data set 2 and results with the best total
travel time. This strategy is chosen because it gives the best results across all
strategies regarding the total travel time and still gives good results on
the makespan. As the aim is to analyze the tradeoffs between the two

criteria, it is better to use a strategy that does not degrade much the
makespan compared to other strategies, and yet provides significantly
better results on the total travel time. Results are presented for differ-
ent numbers of vehicles and different levels of machine flexibility, as
instances from Dauzère-Pérès and Paulli (1997) have been generated
using three different levels of machine flexibility.

The results of Table 8 show that the number of vehicles significantly impacts the makespan, even more than the machine flexibility on these benchmark instances. A large gap is observed from 2 to 4 vehicles, and becomes less significant from 4 to 6 vehicles. In terms of total travel times, increasing the number of vehicles leads to an increase in the total travel time, as lexicographic optimization is used. By increasing machine flexibility, not only does the makespan decrease but also the total travel time; the difference is even more significant in the instances where the vehicles are the most critical.

These results confirm that flexibility acts as a structural lever for
improving system performance, influencing both scheduling and trans-
portation. When flexibility is high, operations can be assigned to closer
machines, effectively reducing the distances traveled and, consequently,
the workload of the vehicles. This not only reduces the total travel time
but also impacts the makespan, since the production operation workload
is more balanced and there are less transportation conflicts. Conversely,
when the flexibility is low, transportation resources become a limiting
factor, and the makespan depends more on vehicle availability and rout-
ing efficiency. Therefore, increasing machine flexibility can be seen as
an alternative to increasing the number of vehicles, providing a more
efficient way to balance the coordination of production and transporta-
tion.

7. Conclusions and perspectives

In this paper, we proposed to optimize a new criterion for the flexi-
ble job-shop scheduling problem with transportation resources: The to-
tal travel time. We believe that, in the case of production scheduling
problems, the optimization should be primarily guided by a manufac-
turing indicator, such as the makespan. Hence, the total travel time is
considered as a secondary objective in this paper. Three optimization
strategies are proposed based on a neighborhood-based metaheuristic
to determine the best solutions for both objectives. To address the com-
plexity induced by the fact that all transportation operations are critical
in terms of total travel time, two new neighborhood structures are pro-
posed and evaluated. An exact constant-time move evaluation of the
total travel time is also proposed. Although, to simplify the notations,
the travel times in this paper are assumed to be independent of the ve-
hicle and whether the vehicle is loaded or not, the contributions can be
directly extended to relax these assumptions.

Computational experiments show that the proposed approaches sig-
nificantly reduce total travel times while keeping a low makespan. The
relationship between both criteria becomes particularly strong when ve-
hicles are critical resources, as the makespan is then mostly driven by
transportation operations. Increasing either the number of vehicles or
the flexibility level can help reduce the makespan, but increasing flexi-
bility is the most effective way to lower the total travel time by avoiding
long transportation operations and, consequently, reducing the need for
vehicles. When vehicles are critical, minimizing the total travel time first
may be a good strategy. When vehicles are not critical, a small increase
in the makespan can substantially decrease the total travel time, making
an ε-constraint approach relevant.

As the total travel time is a widely used criterion in the vehicle rout-
ing literature, some of the related approaches of the literature could
be adapted. In particular, as minimum conditions for job insertion are
presented in this paper, a possible future approach could be to propose
metaheuristics based on large neighborhoods (Pisinger & Ropke, 2019).
Since orienting an undirected graph without creating a cycle can be
hard, particular attention should be paid to the reconstruction operator,
in terms of the quality and diversity of the resulting solutions. Also, this
paper shows that using neighborhood structures of different sizes can be beneficial. An approach taking advantage of the different neighborhood structures such as variable neighborhood search could be investigated.

### CRediT authorship contribution statement

**Lucas Berterottière:** Writing – review & editing, Supervision, Fund-
ing acquisition; **Stéphane Dauzère-Pérès:** Writing – review & editing, Supervision, Funding acquisition; **Claude Yugma:** Writing – review & editing, Supervision, Funding acquisition; **Kwei-Long Huang:** Writing – review & editing, Supervision, Funding acquisition.

### Declaration of competing interest

We, the authors, declare that we have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

### Acknowledgment

This work was partly funded by Agence Nationale de la Recherche (ANR), France, under grants ANR-21-CE10-0015 and by the Ministry of Science and Technology Taiwan, ROC, under grants MOST 111-2923-E-002-004-MY3.

### References

* Berterottière, L., Dauzère-Pérès, S., & Yugma, C. (2024). Flexible job-shop scheduling with transportation resources. *European Journal of Operational Research*, **312**(3), 890-909.

* Biel, K., & Glock, C. H. (2016). Systematic literature review of decision support models for energy-efficient production planning. *Computers & Industrial Engineering*, **101**, 243-259.

* Bilge, Ü., & Ulusoy, G. (1995). A time window approach to simultaneous scheduling of machines and material handling system in an FMS. *Operations Research*, **43**(6), 1058-1070.

* Cordeau, J.-F., & Laporte, G. (2003). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. *Transportation Research Part B: Methodological*, **37**(6), 579-594.

* Dauzère-Pérès, S., Ding, J., Shen, L., & Tamssaouet, K. (2024). The flexible job shop scheduling problem: A review. *European Journal of Operational Research*, **314**(2), 409-432.

* Dauzère-Pérès, S., & Paulli, J. (1997). An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. *Annals of Operations Research*, **70**, 281-306.

* Dauzère-Pérès, S., Yugma, C., Chaabane, A. B., Rulliere, L., & Lamiable, G. (2012). A study on storage allocation in an automated semiconductor manufacturing facility. In *Proceeding of the 2012 international material handling research colloquium*.

* Deroussi, L., & Norre, S. (2010). Simultaneous scheduling of machines and vehicles for the flexible job shop problem. In *International conference on metaheuristics and nature inspired computing* (pp. 1-2). Djerba Island Tunisia.

* Fontes, D. B., Homayouni, S. M., & Fernandes, J. C. (2024). Energy-efficient job shop scheduling problem with transport resources considering speed adjustable resources. *International Journal of Production Research*, **62**(3), (pp. 1-24).

* Fontes, D. B. M. M., & Homayouni, S. M. (2019). Joint production and transportation scheduling in flexible manufacturing systems. *Journal of Global Optimization*, **74**(4), 879-908.

* Gahm, C., Denz, F., Dirr, M., & Tuma, A. (2016). Energy-efficient scheduling in manufacturing companies: A review and research framework. *European Journal of Operational Research*, **248**(3), 744-757.

* Gondran, M., Huguet, M.-J., Lacomme, P., Quilliot, A., & Tchernev, N. (2018). A dial-a-ride evaluation for solving the job-shop with routing considerations. *Engineering Applications of Artificial Intelligence*, **74**, 70-89.

* Ham, A. (2020). Transfer-robot task scheduling in flexible job shop. *Journal of Intelligent Manufacturing*, **31**(7), 1783-1793.

* Ham, A. (2021). Transfer-robot task scheduling in job shop. *International Journal of Production Research*, **59**(3), 813-823.

* Homayouni, S. M., & Fontes, D. B. (2021). Production and transport scheduling in flexible job shop manufacturing systems. *Journal of Global Optimization*, **79**(2), 463-502.

* Hosseini, A., Otto, A., & Pesch, E. (2024). Scheduling in manufacturing with transportation: Classification and solution techniques. *European Journal of Operational Research*, **315**(3), 821-843.

* Karimi, S., Ardalan, Z., Naderi, B., & Mohammadi, M. (2017). Scheduling flexible job-shops with transportation times: Mathematical models and a hybrid imperialist competitive algorithm. *Applied Mathematical Modelling*, **41**, 667-682.

* Lacomme, P., Larabi, M., & Tchernev, N. (2013). Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles. *International Journal of Production Economics*, **143**(1), 24-34.

* Lin, J. T., & Huang, C.-J. (2014). A simulation-based optimization approach for a semiconductor photobay with automated material handling system. *Simulation Modelling Practice and Theory*, **46**, 76-100.

* Pisinger, D., & Ropke, S. (2019). Large neighborhood search. *Handbook of Metaheuristics*, (pp. 99-127).

* Rossi, A. (2014). Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships. *International Journal of Production Economics*, **153**, 253-267.

* Saidi-Mehrabad, M., & Fattahi, P. (2007). Flexible job shop scheduling with tabu search algorithms. *The International Journal Of Advanced Manufacturing Technology*, **32**(5), 563-570.

* Shen, L., Dauzère-Pérès, S., & Neufeld, J. S. (2018). Solving the flexible job shop scheduling problem with sequence-dependent setup times. *European Journal of Operational Research*, **265**(2), 503-516.

* T'kindt, V., & Billaut, J.-C. (2006). Multicriteria scheduling: theory, models and algorithms. Springer Science & Business Media.

* Tsogbetse, I., Bernard, J., Manier, H., & Manier, M.-A. (2024). Influence of encoding and neighborhood in landscape analysis and tabu search performance for job shop scheduling problem. *European Journal of Operational Research*, **319**(3), 739-746.

* Umar, U. A., Ariffin, M., Ismail, N., & Tang, S. H. (2015). Hybrid multiobjective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle (AGV) in flexible manufacturing systems (FMS) environment. *The International Journal of Advanced Manufacturing Technology*, **81**, 2123-2141.

* Van Laarhoven, P. J. M., Aarts, E. H. L., & Lenstra, J. K. (1992). Job shop scheduling by simulated annealing. *Operations Research*, **40**(1), 113-125.