Scatter search with path relinking for the flexible job shop scheduling problem

doi:10.1016/j.ejor.2015.02.052

European Journal of Operational Research
欧盟运营研究杂志

Volume 245, Issue 1, 16 August 2015, Pages 35-45
245 卷，第 1 期，2015 年 8 月 16 日，第 35-45 页

https://doi.org/10.1016/j.ejor.2015.02.052 Get rights and content 获取权利和内容

Full text access 全文访问

Highlights 亮点

•
Neighborhood structures for Flexible Job Shop Scheduling Problem (FJSP) are proposed.
提出了一种用于柔性作业车间调度问题的邻域结构。
•
New dissimilarity measures for solutions of the FJSP are defined.
定义了用于 FJSP 解决方案的新相似度度量。
•
A new Scatter Search with Path Relinking (SSPR) algorithm is proposed for the FJSP.
提出了一种用于 FJSP 的新的散布搜索与路径重链 (SSPR) 算法。
•
The experiments show that SSPR compares favorably with the state-of-the-art.
实验表明，SSPR 与现有最先进技术相比具有优势。

Abstract 摘要

The flexible job shop scheduling is a challenging problem due to its high complexity and the huge number of applications it has in real production environments. In this paper, we propose effective neighborhood structures for this problem, including feasibility and non improving conditions, as well as procedures for fast estimation of the neighbors quality. These neighborhoods are embedded into a scatter search algorithm which uses tabu search and path relinking in its core. To develop these metaheuristics we define a novel dissimilarity measure, which deals with flexibility. We conducted an experimental study to analyze the proposed algorithm and to compare it with the state of the art on standard benchmarks. In this study, our algorithm compared favorably to other methods and established new upper bounds for a number of instances.
可调整作业车间调度问题由于其高复杂性和在实际生产环境中的广泛应用而是一个具有挑战性的问题。在本文中，我们提出了该问题的有效邻域结构，包括可行性和非改进条件，以及快速估计邻居质量的程序。这些邻域被嵌入到散列搜索算法中，该算法在其核心使用了禁忌搜索和路径重链。为了开发这些元启发式方法，我们定义了一种新的相似度度量，它处理灵活性。我们进行了一项实验研究，以分析所提出的算法并将其与标准基准上的最新技术进行比较。在这项研究中，我们的算法与其他方法相比具有优势，并为一些实例建立了新的上限。

Keywords 关键词

Scheduling

Flexible job shop

Scatter search

Path relinking

Neighborhood structures

调度灵活作业车间散列搜索路径重链邻域结构

1. Introduction 1. 引言

The job shop scheduling problem (JSP) is a simple model of many real production processes. It is one of the most classical and difficult scheduling problems and it has been studied for decades (Meeran and Morshed, 2014). However, in many environments the production model has to consider additional characteristics or complex constraints. In this work we consider the possibility of selecting alternative routes among the machines, which is useful in production environments where multiple machines are able to perform the same operation (possibly with different processing times), as it allows the system to absorb changes in the demand of work or in the performance of the machines. This problem is known as the flexible job shop scheduling problem (FJSP). It was first addressed by Brucker and Schlie (1990) and it has been object of intensive research since then.
车间调度问题 (JSP) 是许多实际生产过程的简单模型。它是最经典和最困难的调度问题之一，几十年来一直受到研究（Meeran 和 Morshed，2014）。然而，在许多环境中，生产模型必须考虑额外的特性或复杂的约束。在这项工作中，我们考虑选择机器之间的替代路径的可能性，这在生产环境中很有用，因为多台机器能够执行相同的操作（可能具有不同的处理时间），因为它允许系统吸收工作需求或机器性能的变化。这个问题被称为柔性车间调度问题 (FJSP)。它最初由 Brucker 和 Schlie (1990) 提出，此后一直是研究的重点。

Initially, researchers proposed hierarchical approaches, in which the machine assignment and the scheduling of operations were studied separately (Brandimarte, 1993). However, most of the works in the literature consider both subproblems at the same time. Mastrolilli and Gambardella (2000) developed two neighborhood structures to improve the TS algorithm proposed by Dauzère-Pérès and Paulli (1997). More recently, Ho et al. proposed a learnable genetic architecture (LEGA) (Ho, Tay, and Lai, 2007). It is also remarkable the hybrid genetic algorithm combined with a variable neighborhood descent search (hGA) developed by Gao, Sun, and Gen (2008). Other approaches as the climbing depth-bounded discrepancy search (CDDS) algorithm proposed by Hmida, Haouari, Huguet, and Lopez (2010), the hybrid harmony search and large neighborhood search (HHS/LNS) by Yuan and Xu (2013) or the hybrid genetic algorithm combined with tabu search (GA + TS) proposed by González, Vela, and Varela (2013) also obtain good results on standard instances. Bozejko, Uchronski, and Wodecki (2010) present a parallel approach with two double-level parallel metaheuristic algorithms based on neighborhood determination (TSBM²h), with good results on one standard benchmark. Gutierrez and Garcia-Magario (2011) combine a modular genetic algorithm with repairing heuristics (MGARH), and obtain new upper bounds in one standard benchmark as well. Just to have a general picture of the state of the art in FJSP, we could said that TS, hGA, CDDS, HHS/LNS, TSBM²h, MGARH and GA + TS show the best performance among the aforementioned methods. However, none of them dominates the others in the sense of obtaining the best solutions or taking the lowest time for all benchmarks. Also, the performance of some of these methods strongly varies with the benchmark and some of them have not been evaluated on all the common benchmarks. For example, MGARH is among the best for one particular benchmark while it has not been evaluated on others; and hGA is also the best method for one benchmark, while it is clearly not so good in others.
最初，研究人员提出了分层方法，其中机器分配和作业调度分别进行研究（Brandimarte, 1993）。然而，文献中大多数工作同时考虑这两个子问题。Mastrolilli 和 Gambardella (2000) 开发了两种邻域结构来改进 Dauzère-Pérès 和 Paulli (1997) 提出的禁忌搜索算法。最近，Ho 等人提出了一个可学习的遗传架构 (LEGA) (Ho, Tay, and Lai, 2007)。Gao, Sun 和 Gen (2008) 开发的结合可变邻域下降搜索的混合遗传算法 (hGA) 也值得关注。其他方法，例如 Hmida, Haouari, Huguet 和 Lopez (2010) 提出的爬山深度有界差异搜索 (CDDS) 算法、Yuan 和 Xu (2013) 的混合和声搜索与大邻域搜索 (HHS/LNS) 或 González, Vela 和 Varela (2013) 提出的结合禁忌搜索的混合遗传算法 (GA + TS)，也在标准实例上取得了良好结果。 Bozejko、Uchronski 和 Wodecki (2010) 提出了一种基于邻域确定（TSBM ² h）的双层并行元启发式算法的并行方法，并在一个标准基准测试中取得了良好结果。Gutierrez 和 Garcia-Magario (2011) 将模块化遗传算法与修复启发式方法 (MGARH) 相结合，并在一个标准基准测试中也获得了新的上限。为了对 FJSP 的最新技术水平有一个总体了解，我们可以说，TS、hGA、CDDS、HHS/LNS、TSBM ² h、MGARH 和 GA + TS 在上述方法中表现最佳。然而，在获得最佳解决方案或在所有基准测试中花费最少时间方面，它们之中没有一种能完全优于其他方法。此外，某些方法的性能会因基准测试而异，并且有些方法并未在所有常用基准测试中进行评估。例如，MGARH 在一个特定基准测试中表现最佳，但尚未在其他基准测试中进行评估；hGA 也是一个基准测试中的最佳方法，但在其他基准测试中表现明显不佳。

In spite of that metaheuristics have been widely applied to scheduling problems, a powerful method as scatter search with path relinking has been rarely used in flexible environments. Maybe this is due to the difficulty of defining a tight distance between schedules. As far as we known, only in Jia and Hu (2014), where the authors combine path relinking with tabu search and consider multiobjective optimization, a distance is defined for the FJSP.
尽管元启发式算法已被广泛应用于调度问题，但强大的方法，如带有路径重连的散射搜索，却很少在柔性环境中使用。这可能是由于难以定义计划之间的紧密距离。据我们所知，只有在贾和胡（2014）中，作者将路径重连与禁忌搜索结合起来，并考虑多目标优化，才为 FJSP 定义了距离。

In this paper we propose new neighborhood structures for the FJSP with makespan minimization. We define feasibility and non improving conditions as well as algorithms for fast estimation of neighbors’ quality. We also define a dissimilarity measure between two solutions which takes into account the flexible nature of the problem. These new structures and the dissimilarity measure are incorporated into a hybrid metaheuristic which uses scatter search with path relinking and tabu search as improvement method. We conducted an experimental study to analyze our proposal and to compare it with the state of the art.
在本文中，我们针对具有最小化制造时间的 FJSP 提出新的邻域结构。我们定义了可行性和非改进条件以及用于快速估计邻居质量的算法。我们还定义了两个解决方案之间的不相似性度量，该度量考虑了问题的柔性特性。这些新的结构和不相似性度量被整合到一种混合元启发式方法中，该方法使用带有路径重连的散射搜索和禁忌搜索作为改进方法。我们进行了一项实验研究，以分析我们的建议并将其与现有技术进行比较。

The remainder of the paper is organized as follows. In Section 2 we formulate the problem and describe the solution graph model. In Section 3 we define the proposed neighborhood structures. Section 4 details the new dissimilarity measure and the metaheuristics used. In Section 5 we report the results of the experimental study, and finally Section 6 summarizes the main conclusions of this paper.
论文的其余部分组织如下。第 2 节中，我们将阐述问题并描述解决方案图模型。第 3 节中，我们将定义所提出的邻域结构。第 4 节详细介绍了新的相似度度量和使用的元启发式算法。第 5 节报告了实验研究的结果，最后第 6 节总结了本文的主要结论。

2. Problem formulation 2. 问题描述

In the job shop scheduling problem (JSP), there are a set of jobs J = {J₁, …, J_n} that must be processed on a set M = {M₁, …, M_m} of physical resources or machines, subject to a set of constraints. There are precedence constraints, so each job J_i, i = 1, …, n, consists of n_i operations

O_{i} = {o_{i 1}, \dots, o_{i n_{i}}}

to be sequentially scheduled. Also, there are capacity constraints, whereby each operation o_ij requires the uninterrupted and exclusive use of one of the machines for its whole processing time.
在车间调度问题 (JSP) 中，有一组作业 J = {J ₁ ，…，J _n } 需要在一组 M = {M ₁ ，…，M _m } 物理资源或机器上进行处理，并受一组约束的限制。存在优先级约束，因此每个作业 J，i = 1，…，n，由 n 个操作

O_{i} = {o_{i 1}, \dots, o_{i n_{i}}}

组成，这些操作必须按顺序安排。此外，还存在容量约束，每个操作 o _ij 都需要在整个处理时间内连续且独占地使用其中一台机器。

In the flexible JSP (FJSP), an operation o_ij is allowed to be executed in any machine of a given set M(o_ij)⊆M. The processing time of operation o_ij on machine M_k ∈ M(o_ij) is

p_{o_{i j} k} \in N

. Notice that the processing time of an operation may be different in each machine and that a machine may process several operations of the same job. The goal is to build up a feasible schedule which consists in assigning both a machine and a starting time to each operation in the set O = ∪_{1 ≤ i ≤ n}O_i, in such a way that all constraints hold. The objective function is the makespan, which should be minimized. The FJSP is NP-hard as it is a generalization of the JSP which has proven to be NP-hard (Garey, Johnson, and Sethi, 1976).
在柔性作业车间调度问题 (FJSP) 中，允许操作 o_{_ij} 在给定集合 M(o_{_ij})⊆M 的任何机器上执行。操作 o_{_ij} 在机器 M_{_k} ∈ M(o_{_ij}) 上的处理时间为

p_{o_{i j} k} \in N

。请注意，操作的处理时间在每台机器上可能不同，并且一台机器可以处理同一作业的多个操作。目标是构建一个可行的时间表，该时间表包括为集合 O = ∪_{_{1 ≤ i ≤ n}} O 中的每个操作分配一台机器和一个开始时间，使得所有约束都满足。目标函数是最大完工时间，应将其最小化。FJSP 由于它是已证明为 NP-hard 的 JSP 的推广而也是 NP-hard（Garey、Johnson 和 Sethi，1976）。

A solution can be alternatively viewed as a pair (α, π) where α represents a feasible assignment of each operation o_ij ∈ O to a machine M_k ∈ M(o_ij), denoted α(o_ij) = k, and π is a processing order of the operations on all the machines in M compatible with the job sequences.
解也可以被视为一对 (α, π)，其中 α 表示将每个操作 o_{_ij} ∈ O 分配到机器 M_{_k} ∈ M(o_{_ij}) 的可行分配，表示为 α(o_{_ij}) = k，而 π 是在所有兼容作业序列的机器 M 上的操作的处理顺序。

Let

P J_{o_{i j}}

and

S J_{o_{i j}}

denote the operations just before and after o_ij in the job sequence and

P M_{o_{i j}}

and

S M_{o_{i j}}

the operations right before and after o_ij in the machine sequence in a solution (α, π), if they exist. The starting and completion times of o_ij, denoted

S t_{o_{i j}}

and

C_{o_{i j}}

respectively, can be calculated as

S t_{o_{i j}} = \max (C_{P J_{o_{i j}}}, C_{P M_{o_{i j}}})

(if an operation is the first in its job or in its machine sequence, the corresponding

C_{P J_{o_{i j}}}

C_{P M_{o_{i j}}}

is taken to be 0) and

C_{o_{i j}} = S t_{o_{i j}} + p_{o_{i j} k}

being k = α(o_ij). The objective is to find a solution (α, π) that minimizes the makespan, denoted as

C_{m a x} (α, π) = \max_{o_{i j} \in O} C_{o_{i j}}

.
令

P J_{o_{i j}}

和

S J_{o_{i j}}

表示作业序列中 o _ij 之前和之后的操作，以及

P M_{o_{i j}}

和

S M_{o_{i j}}

表示机器序列中 o _ij 之前和之后的操作（如果存在）。o _ij 的开始时间和完成时间，分别表示为

S t_{o_{i j}}

和

C_{o_{i j}}

，可以计算为

S t_{o_{i j}} = \max (C_{P J_{o_{i j}}}, C_{P M_{o_{i j}}})

（如果一个操作在其作业或机器序列中是第一个，则相应的

C_{P J_{o_{i j}}}

或

C_{P M_{o_{i j}}}

取为 0），其中 k = α(o _ij )。目标是找到一个解 (α, π)，使最大完工时间（表示为

C_{m a x} (α, π) = \max_{o_{i j} \in O} C_{o_{i j}}

）最小化。

2.1. Solution graph and criticality
2.1. 解图和关键性

We define the following solution graph model for the FJSP. In accordance with this model, a machine assignment α and a feasible operation processing order π can be represented by an acyclic directed graph G(α, π) = (V, A∪R(α, π)), where each node v in V represents either an operation of the problem, labeled with the assigned machine M_k, or one of the dummy nodes start and end, which are fictitious operations with processing time 0.
我们定义了 FJSP 的以下解图模型。根据该模型，机器分配 α 和可行作业处理顺序 π 可以由有向无环图 G(α, π) = (V, A∪R(α, π)) 表示，其中 V 中的每个节点 v 都表示问题中的一个作业，用分配的机器 M _k 标记，或者虚拟节点开始和结束中的一个，它们是处理时间为 0 的虚构作业。

The set A contains conjunctive arcs representing job processing orders and the set R(α, π) contains disjunctive arcs representing machine processing orders. The arc (v, w) is weighted with the processing time, p_vk, of the operation in v on the assigned machine M_k. If w is the first operation in the processing order of its job, J(w), there is an arc (start, w) in G(α, π) with weight 0 and if w is the last operation in the job processing order, there is an arc (w, end) with weight p_wk, k = α(w). Fig. 1 shows a solution graph for a problem with 3 jobs and 3 machines.
集合 A 包含表示工件加工顺序的合取弧，集合 R(α, π) 包含表示机器加工顺序的析取弧。弧 (v, w) 的权重为操作 v 在指定机器 M _k 上的加工时间 p _vk 。如果 w 是其工件 J(w) 的加工顺序中的第一个操作，则 G(α, π) 中存在一条权重为 0 的弧 (start, w)；如果 w 是工件加工顺序中的最后一个操作，则存在一条权重为 p _wk 的弧 (w, end)，其中 k = α(w)。图 1 显示了一个包含 3 个工件和 3 台机器的问题的解图。

The set R(α, π) is partitioned into subsets R_k(α, π), where R_k(α, π) is a minimal set of arcs defining a processing order for all operations requiring the machine M_k.
集合 R(α, π) 被划分为子集 R _k (α, π)，其中 R _k (α, π) 是定义所有需要机器 M _k 的操作的加工顺序的最小弧集。

The makespan of the solution (α, π) is the cost of a critical path in G(α, π), i.e., a directed path from node start to node end having maximum cost. Bold-face arcs in Fig. 1 represent a critical path. Nodes and arcs in a critical path are also termed critical. We define a critical block as a maximal subsequence of consecutive operations in a critical path requiring the same machine. Notice that with this definition, a critical block may contain more than one operation of the same job. This makes a difference w.r.t. other definitions in the literature, as for example those given in Mastrolilli and Gambardella (2000) or in González et al. (2013), and has some influence in the critical block length and neighborhood size, as we will detail later.
解 (α, π) 的制造时间是 G(α, π) 中关键路径的成本，即从节点 start 到节点 end 具有最大成本的有向路径。图 1 中的粗体弧表示关键路径。关键路径中的节点和弧也称为关键的。我们将关键块定义为关键路径中连续操作的最大子序列，这些操作需要相同的机器。请注意，根据此定义，关键块可能包含同一作业的多个操作。这与文献中的其他定义（例如 Mastrolilli 和 Gambardella (2000) 或 González 等人 (2013) 中的定义）有所不同，并且对关键块长度和邻域大小有一定影响，我们将在后面详细介绍。

The concept of critical block is important as most neighborhood structures proposed for job shop problems rely on exchanging the processing order of operations in critical blocks (Amico, Trubian, 1993, Mati, Dauzere-Peres, Lahlou, 2011, Van Laarhoven, Aarts, Lenstra, 1992). The structures proposed in Section 3.1 include moves of this type as well, but as we shall see, in the FJSP we have to introduce an additional type of move to deal with the machine assignment subproblem.
关键块的概念很重要，因为大多数针对车间调度问题的邻域结构都依赖于在关键块中交换工序的处理顺序（Amico, Trubian, 1993, Mati, Dauzere-Peres, Lahlou, 2011, Van Laarhoven, Aarts, Lenstra, 1992）。第 3.1 节中提出的结构也包含这类移动，但正如我们将看到的，在 FJSP 中，我们必须引入一种额外的移动类型来处理机器分配子问题。

To formalize the description of the neighborhood structures, we introduce the concepts of head and tail of an operation v, denoted r_v and q_v respectively, which are calculated as follows:
为了形式化邻域结构的描述，我们引入了操作 v 的头和尾的概念，分别用 r _v 和 q _v 表示，计算方式如下：

\begin{matrix} r_{s t a r t} = q_{e n d} = 0 \\ r_{v} = \max (r_{P J_{v}} + p_{P J_{v} k_{1}}, r_{P M_{v}} + p_{P M_{v} k}) \\ k = α (v), k_{1} = α (P J_{v}) \\ r_{e n d} = \max_{v \in P J_{e n d}, k = α (v)} {r_{v} + p_{v k}} \\ q_{v} = \max (q_{S J_{v}} + p_{S J_{v} k_{2}}, q_{S M_{v}} + p_{S M_{v} k}) \\ k = α (v), k_{2} = α (S J_{v}) \\ q_{s t a r t} = \max_{v \in S J_{s t a r t}, k = α (v)} {q_{v} + p_{v k}} \end{matrix}

Abusing notation, SJ_start (PJ_end) denotes the set consisting of the first (last) operation processed in each of the n jobs. A node v is critical if and only if C_max = r_v + p_vα(v) + q_v.
滥用符号，SJ _start (PJ _end ) 表示由每个 n 个作业中第一个（最后一个）处理的工序组成的集合。如果且仅当 C _max = r _v + p _vα(v) + q _v 时，节点 v 才是关键节点。

3. Neighborhood structures
3. 邻域结构

In this section we propose several neighborhood structures for the FJSP, some of them focus on the sequencing subproblem and so they rely on changing the processing order of operations on a machine, while others deal with the assignment subproblem, hence their moves consist in changing the machine assignment of an operation. For these structures we prove conditions of feasibility and non-improvement, and propose methods for fast estimation of the neighbors quality. We also analyze different strategies for combining these structures.
在本节中，我们为柔性作业车间调度问题 (FJSP) 提出了几种邻域结构，其中一些专注于排序子问题，因此它们依赖于改变机器上作业的处理顺序；而另一些则处理分配子问题，因此它们的移动包括改变作业的机器分配。对于这些结构，我们证明了可行性和非改进条件，并提出了快速估计邻居质量的方法。我们还分析了组合这些结构的不同策略。

3.1. Structures for the sequencing subproblem
3.1. 排序子问题的结构

We propose two structures, termed N^π and

N_{r}^{π},

which extend some of the structures defined by Amico and Trubian (1993) to the FJSP. In both cases a neighbor is created by moving a critical operation to another position in its critical block, keeping the machine assignment. They are based on the following results.
我们提出了两种结构，分别称为 N ^π 和

N_{r}^{π},

，它们扩展了 Amico 和 Trubian (1993) 定义的一些结构以适应柔性作业车间调度问题 (FJSP)。在这两种情况下，通过将关键操作移动到其关键块中的另一个位置（保持机器分配）来创建邻居。它们基于以下结果。

Proposition 1 命题 1

Let S = (α, π) and S′ = (α, π′) be two feasible schedules such that S′ is obtained from S so that it keeps the processing order of all operations in a critical path in S. Then, C_max(S′) ≥ C_max(S).
令 S = (α, π) 和 S′ = (α, π′) 是两个可行调度，使得 S′ 是从 S 获得的，它保留了 S 中关键路径上所有操作的处理顺序。那么，C _max (S′) ≥ C _max (S)。

Therefore, we will only consider changes in the processing orders of operations in a critical path to get potentially improving schedules. Let us now consider the portion of the graph in the left side of Fig. 2 where all the operations of the block (v u₁ … u_n w) have the same machine assigned and w belongs to different job than the other operations. Discontinuous arrows represent potential alternative paths. Moving w just before v (right side of Fig. 2) requires checking that none of these paths exist, otherwise there would be a cycle in the resulting graph. The following result gives a sufficient condition for no cycles.
因此，我们只考虑关键路径上作业的加工顺序变化，以获得可能改进的排程。现在让我们考虑图 2 左侧的部分，其中该块 (v u ₁ … u _n w) 中的所有作业都分配到同一台机器，而 w 属于与其他作业不同的工件。虚线箭头表示潜在的替代路径。将 w 移到 v 之前（图 2 右侧）需要检查这些路径是否存在，否则生成的图中会出现循环。以下结果给出了没有循环的充分条件。

Proposition 2 命题 2

Let S = (α, π) be a feasible schedule and let (B′ v B w B′′) be a sequence of consecutive operations in the solution graph G(α, π) all of them assigned to the same machine, where B, B′ and B′′ are themselves sequences of operations such that any of them may be null. Let (α, π′) be a schedule created from S by moving w just before v. Then, G(α, π′) has no cycles if the following condition holds:
令 S = (α, π) 为一个可行调度，令 (B′ v B w B′′) 为解图 G(α, π) 中一系列连续的操作，它们都分配给同一台机器，其中 B, B′ 和 B′′ 本身是操作序列，它们可以为空。令 (α, π′) 为通过将 w 移到 v 前面而从 S 创建的调度。那么，如果满足以下条件，则 G(α, π′) 没有循环：(1)

r_{P J_{w}} < r_{S J_{u}} + p_{S J_{u} k_{1}} + C \land J (u) \neq J (w), \forall u \in (v B),

where C = 0 if SM_z = PJ_w, and

C = m i n {p_{S J_{z} k_{2}}, p_{S M_{z} k_{1}}}

otherwise, being z = SJ_u, k₁ = α(SJ_u), k₂ = α(SJ_z).
其中 C = 0，如果 SM _z = PJ _w ，否则为

C = m i n {p_{S J_{z} k_{2}}, p_{S M_{z} k_{1}}}

，其中 z = SJ _u ，k ₁ = α(SJ _u )，k ₂ = α(SJ _z )。

A similar result can be proven with regards to the insertion of operation v just after w. So, we can define the following neighborhood structure.
关于将操作 v 插入 w 之后，可以证明类似的结果。因此，我们可以定义以下邻域结构。

Definition 1 定义 1

N^π structure. Let operation v be a member of a critical block B. In a neighboring solution v is moved to another position in B, provided that the sufficient condition of feasibility given in Proposition 2 holds.
N ^π 结构。设操作 v 是关键块 B 的成员。在邻域解中，v 移动到 B 中的另一个位置，前提是命题 2 中给出的可行性充分条件成立。

In order to reduce the effective size of the neighborhood, we propose the following condition for non-improvement, which can be efficiently evaluated.
为了减少邻域的有效大小，我们提出了以下非改进条件，该条件可以有效评估。

Proposition 3 命题 3

Let S = (α, π) be a solution and (B′ v B w B′′) a critical block in G(α, π), where B, B′ and B′′ are sequences of operations of the form B = (u₁, …, u_n),

B^{'} = (u_{1}^{'}, \dots, u_{n^{'}}^{'})

and

B^{''} = (u_{1}^{''}, \dots, u_{n^{''}}^{''}),

with n′, n′′ ≥ 1. Even if the schedule S′ = (α, π′) obtained from S by inserting w just before v is feasible, the makespan of S′ cannot be lower than the makespan of S.
令 S = (α, π) 为一个解，(B′ v B w B′′) 为 G(α, π) 中的临界块，其中 B, B′ 和 B′′ 是形式为 B = (u ₁ , …, u _n ),

B^{'} = (u_{1}^{'}, \dots, u_{n^{'}}^{'})

和

B^{''} = (u_{1}^{''}, \dots, u_{n^{''}}^{''}),

的操作序列，且 n′, n′′ ≥ 1。即使通过在 v 前插入 w 从 S 获得的排程 S′ = (α, π′) 是可行的，S′ 的完工时间也不能低于 S 的完工时间。

An analogous result can be established for a neighbor created by inserting an operation v after an operation w. Therefore, a move in N^π may only produce an improvement in the makespan if an internal operation is moved either before the first or after the last operation of the critical block, or if an operation at the extreme of a critical block is moved to another position in the block. Hence, we can define the following reduced neighborhood structure.
可以建立一个类似的结果，用于通过在操作 w 后插入操作 v 来创建的邻居。因此，如果内部操作移动到关键块的第一项操作之前或最后一项操作之后，或者如果关键块的极端操作移动到该块中的其他位置，则 N ^π 中的移动才能改进完工时间。因此，我们可以定义以下简化的邻域结构。

Definition 2 定义 2

N_{r}^{π}

structure. Let v be an operation in a critical block B. If v is internal to B, then a neighboring solution is obtained by moving v before the first or after the last operation in B. If v is the first or the last operation in B, a neighboring solution is obtained by moving v to another position in B. In both cases, the sufficient condition of feasibility given in Proposition 2 must hold.

N_{r}^{π}

结构。令 v 为关键块 B 中的操作。如果 v 是 B 的内部操作，则通过将 v 移动到 B 中的第一项操作之前或最后一项操作之后来获得相邻的解决方案。如果 v 是 B 的第一项或最后一项操作，则通过将 v 移动到 B 中的另一个位置来获得相邻的解决方案。在这两种情况下，都必须满足命题 2 中给出的可行性充分条件。

Fig. 3 shows an example where a neighbor of the schedule of Fig. 1 is created with

N_{r}^{π}

. In this case, o₂₃ is inserted after o₃₂ and the makespan improves.
图 3 显示了一个示例，其中使用

N_{r}^{π}

创建了图 1 调度的邻居。在这种情况下，o ₂₃ 插入 o ₃₂ 之后，完工时间有所改善。

Let us now introduce the new neighborhood, termed

N_{2}^{π},

which extends that proposed in Van Laarhoven et al. (1992).
现在让我们引入新的邻域，称为

N_{2}^{π},

，它扩展了 Van Laarhoven 等人 (1992) 的建议。

Definition 3 定义 3

N_{2}^{π}

structure. Let v and w be consecutive operations of the same machine. In a neighboring solution the processing order of v and w is reversed, provided that the sufficient condition of feasibility given in Proposition 2 holds.

N_{2}^{π}

结构。令 v 和 w 为同一机器的连续作业。在相邻的解决方案中，如果命题 2 中给出的可行性充分条件成立，则反转 v 和 w 的处理顺序。

In accordance with Proposition 1, many of the neighbors generated by

N_{2}^{π}

will be non improving ones and so this structure will not be useful for tabu search. However, it may be good for path relinking, as we will see in Section 4.4.
根据命题 1，

N_{2}^{π}

生成的许多邻居都是非改进的，因此这种结构对禁忌搜索没有用。然而，正如第 4.4 节将要看到的，它可能对路径重链有用。

Notice that, for any of the defined structures, the order π′ of the selected neighbor can be built by reconstructing only a portion of π. For example, if the neighbor is created with N^π by inserting v after w, or by inserting w before v, the sequences of operations before v and after w in π remain in π′ (similar reconstruction is detailed in Mattfeld (1995) for the classical JSP).
注意，对于任何定义的结构，所选邻居的顺序 π′ 可以仅通过重建 π 的一部分来构建。例如，如果邻居是通过在 w 后插入 v 或在 v 前插入 w 来使用 N ^π 创建的，则 π 中 v 之前的操作序列和 w 之后的操作序列保留在 π′ 中（Mattfeld (1995) 中对经典 JSP 有类似的重建细节）。

3.2. Structures for the assignment subproblem
3.2. 任务分配子问题的结构

Changing the machine assignment of one operation may give rise to an improved schedule. This possibility was already exploited in Mastrolilli and Gambardella (2000) where the authors consider a set of moves, called k-insertion. A k-insertion assigns an operation v to a new machine M_k ∈ M(v) and then looks for the optimal position for v in the machine sequence of k.
改变一个操作的机器分配可能会导致改进的计划。这种可能性已经在 Mastrolilli 和 Gambardella (2000) 中被利用，作者考虑了一组称为 k-插入的移动。k-插入将操作 v 分配给新机器 M _k ∈ M(v)，然后寻找 v 在机器序列 k 中的最佳位置。

We propose here a simpler and less time consuming method: given a solution S = (α, π), a neighbor is obtained by assigning a new machine

M_{k^{'}} \in M (v)

to a critical operation v. The new position for v in the machine sequence of

M_{k^{'}}

is chosen in such a way that the topological order of the graph after the move remains identical, that is, the order π is the same after the new assignment; so ensuring feasibility. Notice that changing the machine of non-critical operations cannot produce an immediate improvement in the makespan. This structure is defined as follows.
我们这里提出一种更简单、耗时更少的方法：给定一个解 S = (α, π)，通过将一个新机器

M_{k^{'}} \in M (v)

分配给关键操作 v 来获得一个邻域。在

M_{k^{'}}

的机器序列中选择 v 的新位置，使得移动后图的拓扑顺序保持不变，即移动后 π 顺序保持不变；从而保证可行性。请注意，更改非关键操作的机器不能立即改善完工时间。该结构定义如下。

Definition 4 定义 4

N^α structure. Let S = (α, π) be a schedule, let v be a critical operation and let α_{<v, k >} be the assignment obtained from α after reassigning v to a new machine M_k ∈ M(v), k ≠ α(v). Then, (α_{<v, k >}, π) is a neighboring solution.
N ^α 结构。令 S = (α, π) 为一个调度，令 v 为关键操作，令 α _{<v, k >} 为从 α 中重新分配 v 到新机器 M _k ∈ M(v)，k ≠ α(v) 后获得的分配。则 (α _{<v, k >} , π) 是一个邻近解。

As an example, let us consider that the operation o₁₂ can be processed on the machine M₃ in the schedule of Fig. 1. If o₁₂ switches from M₁ to M₃, as o₁₂ is after o₂₂ in the topological order, then o₁₂ is inserted after o₂₂ in the new machine sequence of M₃. The result is the schedule of Fig. 4, whose makespan is better than that of the original schedule.
例如，让我们考虑在图 1 的调度中，操作 o ₁₂ 可以由机器 M ₃ 处理。如果 o ₁₂ 从 M ₁ 切换到 M ₃ ，由于 o ₁₂ 在拓扑顺序中位于 o ₂₂ 之后，则 o ₁₂ 会在新机器序列 M ₃ 中插入 o ₂₂ 之后。结果是图 4 的调度，其完工时间比原始调度更好。

As we have done for the sequencing subproblem, we define the neighborhood

N_{2}^{α}

to be used in path relinking. This structure is the same as N^α except that the operation v may not be critical.
正如我们在排序子问题中所做的那样，我们定义了路径重链中使用的邻域

N_{2}^{α}

。此结构与 N ^α 相同，只是操作 v 不一定是关键操作。

3.3. Combining sequencing and assignment structures
3.3. 组合排序和分配结构

We also consider combinations of the previous structures to be used at different points of the proposed algorithm. For example, in the tabu search algorithm (see Section 4.5) it is convenient a neighborhood structure with a high chance of generating improving schedules. So, we define the following structure for this purpose.
我们还考虑将先前结构组合起来，以便在建议算法的不同阶段使用。例如，在禁忌搜索算法中（参见第 4.5 节），使用具有高概率生成改进排程的邻域结构很方便。因此，我们为此定义了以下结构。

Definition 5 定义 5

N_{r}^{α π} = N^{α} \cup N_{r}^{π}

However, in the path relinking procedure the priority is not only to reduce the makespan but also to reduce the distance between two solutions. For this reason, some of the neighbors discarded by N^α or

N_{r}^{π}

may be very attractive in terms of distance or dissimilarity. This consideration leads us to define the following structures.
然而，在路径重链过程中，优先级不仅是缩短完工时间，还在于缩短两个解之间的距离。因此，由 N ^α 或

N_{r}^{π}

丢弃的一些邻居在距离或差异方面可能非常有吸引力。这种考虑导致我们定义以下结构。

Definition 6 定义 6

N^απ = N^α∪N^π

Definition 7 定义 7

N_{2}^{α π} = N_{2}^{α} \cup N_{2}^{π}

In Section 4.4 we will describe how to integrate these structures in the path relinking procedure.
在第 4.4 节中，我们将描述如何将这些结构集成到路径重链过程中。

3.4. Makespan estimate 3.4. 制造时间估计

To estimate the makespan of the neighbors created with

N_{r}^{π},

N^π and

N_{2}^{π}

we propose to use a direct extension of the procedure lpath given in Amico and Trubian (1993) for the classical JSP. Let (α, π′) be a schedule obtained from (α, π). In order to estimate the makespan of (α, π′), the procedure takes as input a sequence of operations requiring the same machine (x Q₁…Q_q y) in π′, where Q₁…Q_q is a permutation of the operations O₁…O_q appearing as (x O₁…O_q y) in π. It is important to notice that the heads of operations before x and the tails of operations after y do not change in the neighbor. So, for each i = 1…q, the procedure estimates the cost of the longest path from node start to end through Q_i, and the maximum of these values is taken as the makespan estimate for the neighboring schedule. This estimate is not necessarily a lower bound. Additionally, for

N_{2}^{π}

it may happen that the processing order of critical operations is not changed, and in that case the estimate can be refined a little bit more, as it cannot be lower than the makespan of the original schedule. For additional details on the lpath procedure we refer the interested reader to Amico and Trubian (1993).
为了估算使用

N_{r}^{π},

N ^π 和

N_{2}^{π}

创建的邻居的完工时间，我们建议使用 Amico 和 Trubian (1993) 在经典 JSP 中给出的 lpath 过程的直接扩展。令 (α, π′) 是从 (α, π) 获得的排程。为了估算 (α, π′) 的完工时间，该过程以 π′ 中需要同一机器的操作序列 (x Q ₁ …Q _q y) 为输入，其中 Q ₁ …Q _q 是操作 O ₁ …O _q 的排列，在 π 中出现为 (x O ₁ …O _q y)。需要注意的是，x 之前的操作头和 y 之后的操作尾在邻居中不会改变。因此，对于每个 i = 1…q，该过程估算从节点开始到通过 Q 结束的最长路径的成本，并将这些值的最大值作为相邻排程的完工时间估计。这种估计不一定是下界。此外，对于

N_{2}^{π}

，可能发生关键操作的处理顺序没有改变，在这种情况下，估计可以进一步细化一点，因为它不能低于原始排程的完工时间。欲了解更多关于 lpath 过程的细节，请参阅 Amico 和 Trubian (1993) 的论文。

Let us now discuss the estimate of the neighbors created with N^α and

N_{2}^{α}

. Given a schedule S = (α, π) and an operation x with k = α(x), assigning x to another machine

M_{k^{'}} \in M (x)

produces a feasible schedule S′ = (β, π) where

β = α_{< x, k^{'} >},

i.e., β(y) = α(y) for all y ≠ x and β(x) = k′. As before, the heads of the operations before x and the tails of the operations after y do not change, and the head and the tail of x after the move are given by the following expressions:
现在让我们讨论一下使用 N ^α 和

N_{2}^{α}

创建的邻居的估计。给定一个计划 S = (α, π) 和一个操作 x，其中 k = α(x)，将 x 分配给另一台机器

M_{k^{'}} \in M (x)

会产生一个可行计划 S′ = (β, π)，其中

β = α_{< x, k^{'} >},

，即，对于所有 y ≠ x，β(y) = α(y)，并且 β(x) = k′。与之前一样，x 之前的操作头和 y 之后的操作尾部不会改变，移动后 x 的头和尾由以下表达式给出：(2)

\begin{matrix} r_{x}^{'} & = & \max {r_{P J_{x}} + p_{P J_{x} k_{1}}, r_{P M_{x}} + p_{P M_{x} k^{'}}} \\ q_{x}^{'} & = & \max {q_{S J_{x}} + p_{S J_{x} k_{2}}, q_{S M_{x}} + p_{S M_{x} k^{'}}} \end{matrix}

where k₁ = α(PJ_x) and k₂ = α(SJ_x). Therefore, the makespan of S′ = (β, π) can be estimated as

C_{m a x}^{e} (S^{'}) = r_{x}^{'} + p_{x k^{'}} + q_{x}^{'}

. In this case the estimate is a lower bound on C_max(S′).
其中 k ₁ = α(PJ _x ) 且 k ₂ = α(SJ _x )。因此，S′ = (β, π) 的制造时间可以估计为

C_{m a x}^{e} (S^{'}) = r_{x}^{'} + p_{x k^{'}} + q_{x}^{'}

。在这种情况下，估计值是 C _max (S′) 的下界。

Additionally, in the case that x is not critical (as it may occur in the

N_{2}^{α}

structure), the makespan cannot be lower than that of the original schedule, therefore in that case the estimate can be refined as

C_{m a x}^{e} (S^{'}) = \max {r_{x}^{'} + p_{x k^{'}} + q_{x}^{'}, C_{m a x} (S)}

.
此外，如果 x 不是关键操作（例如在

N_{2}^{α}

结构中可能发生的情况），则制造时间不能低于原始计划的制造时间，因此在这种情况下，估计值可以改进为

C_{m a x}^{e} (S^{'}) = \max {r_{x}^{'} + p_{x k^{'}} + q_{x}^{'}, C_{m a x} (S)}

。

In Section 5.2 we report some experimental results showing the accuracy of the proposed estimates.
在 5.2 节中，我们报告了一些实验结果，展示了所提出估计的准确性。

4. Scatter search for the FJSP
4. 灵活作业车间调度问题的散点搜索

Scatter Search (SS) is a population-based evolutionary metaheuristic recognized as an excellent method at achieving a proper balance between intensification and diversification in the search process. SS was first proposed by Glover (1998) and it has been successfully applied to a number of problems, in particular to scheduling (González, Vela, Varela, González-Rodríguez, 2015, Nowicki, Smutnicki, 2006, Sels, Craeymeersch, Vanhoucke, 2011, Yamada, Nakano, 1996).
散列搜索 (SS) 是一种基于种群的进化元启发式算法，被认为是在搜索过程中在强化和多样化之间取得良好平衡的优秀方法。SS 最初由 Glover (1998) 提出，并已成功应用于许多问题，特别是调度问题 (González, Vela, Varela, González-Rodríguez, 2015, Nowicki, Smutnicki, 2006, Sels, Craeymeersch, Vanhoucke, 2011, Yamada, Nakano, 1996)。

The SS five-method template proposed in Glover (1998) has been the main reference for most SS implementations to date, including ours. This template consists of (1) a diversification-generation method, (2) an improvement method, (3) a reference-set update method, (4) a subset-generation method and (5) a solution-combination method.
Glover (1998) 中提出的 SS 五方法模板一直是迄今为止大多数 SS 实现的主要参考，包括我们的实现。该模板包括 (1) 多样化生成方法，(2) 改善方法，(3) 参考集更新方法，(4) 子集生成方法和 (5) 解决方案组合方法。

Algorithm 1 starts by creating an initial set of solutions P which are improved using TS (Tabu Search). Then, a reference set RefSet is obtained selecting the best solutions from P. The algorithm stops after a given number of iterations without improvement. At each iteration, a pair of solutions from RefSet (selected according to the subset generation method) is combined using PR (Path Relinking) to generate a new solution, which is also improved by TS. Then, the reference set update method is applied. Additionally, if all possible pairs of solutions in RefSet have already been combined without introducing any new solution to the set, a diversification phase is applied. Further details on the algorithm are given in the following sections.
算法 1 从创建一组初始解 P 开始，这些解使用禁忌搜索 (TS) 进行改进。然后，通过从 P 中选择最佳解来获得参考集 RefSet。算法在给定次数的迭代后停止，没有改进。在每次迭代中，从 RefSet 中选择一对解（根据子集生成方法选择），使用路径重链 (PR) 来生成新的解，该解也由 TS 进行改进。然后，应用参考集更新方法。此外，如果 RefSet 中所有可能的解对都已经组合，而没有向集合中引入任何新解，则应用多样化阶段。以下部分将提供有关该算法的更多详细信息。

4.1. Dissimilarity measure
4.1. 相异性度量

The definition of “distance” between two solutions in the presence of flexibility is not straightforward. Although having properties of a metric is desirable, a dissimilarity measure can be quite effective without being a metric, that is, a distance (Goshtasby, 2012).
在存在灵活性的情况下，定义两个解之间的“距离”并非易事。虽然具有度量属性是理想的，但一个相异性度量在没有成为度量的情况下，即距离（Goshtasby, 2012），可能非常有效。

In this paper we propose for the FJSP that the “difference” between two solutions S₁ and S₂ (denoted by d(S₁, S₂)) is an ordered pair of integer numbers, one representing the dissimilarity in the sequencing subproblem (denoted by d^π(S₁, S₂)) and the other one representing the distance on the assignment subproblem (denoted by d^α(S₁, S₂)). The first one is an extension of the disjunctive graph distance, or Hamming distance, defined by Mattfeld (1995) for the classical JSP, as the number of pairs of operations requiring the same machine which are processed in different order in S₁ and S₂. This definition in the flexible case does not fulfill the triangle inequality, and then it is not a distance but a dissimilarity coefficient (Webb, 2002). Regarding the assignment distance d^α(S₁, S₂), it is defined as the number of operations having a different machine assignment in S₁ and S₂.
在本文中，我们针对柔性作业车间调度问题 (FJSP) 提出，两个解 S₀ 和 S₁ 之间的“差异” (记作 d(S₂, S₃)) 是一个有序整数对，其中一个表示排序子问题中的差异 (记作 d₄(S₅, S₆))，另一个表示分配子问题上的距离 (记作 d₇(S₈, S₉))。第一个是 Mattfeld (1995) 为经典作业车间调度问题 (JSP) 定义的析取图距离或汉明距离的扩展，它是指在 S₁₀ 和 S₁₁ 中，需要同一机器的两对工序以不同顺序处理的工序数。在柔性情况下，此定义不满足三角不等式，因此它不是距离，而是一个相似系数 (Webb, 2002)。关于分配距离 d₁₂(S₁₃, S₁₄)，它定义为在 S₁₅ 和 S₁₆ 中具有不同机器分配的工序数。

Considering these two measures, d^α and d^π, we will adopt a lexicographic approach and define a precedence relation between two pairs

d_{1} = (d_{1}^{α}, d_{1}^{π})

and

d_{2} = (d_{2}^{α}, d_{2}^{π})

as follows:
考虑到这两个度量 d₀ 和 d₁，我们将采用词典顺序方法，并定义如下两个对 {2} 和 {3} 之间的优先关系：(3)

d_{1} ≺ d_{2} \Leftrightarrow d_{1}^{α} < d_{2}^{α} \lor (d_{1}^{α} = d_{2}^{α} \land d_{1}^{π} < d_{2}^{π})

We will use this precedence relation to compute the minimum “difference” (i.e., the maximum similarity) as min _≺(d₁, d₂) = d₁ if d₁≺d₂ and min _≺(d₁, d₂) = d₂ otherwise. The relation min _≺ can be naturally extended for an arbitrary number of elements and also the max _≺ relation can be defined accordingly.
我们将使用这种优先关系来计算最小“差异”（即最大相似度）作为 min _≺ (d ₁ , d ₂ ) = d ₁ 如果 d ₁ ≺d ₂ 并且 min _≺ (d ₁ , d ₂ ) = d ₂ 否则。关系 min _≺ 可以自然地扩展到任意数量的元素，并且也可以相应地定义最大 _≺ 关系。

In Jia and Hu (2014), the authors define the distance between two solutions as the number of operations that are located at different positions on the coding strings. So, for a problem instance with 10 machines and 10 jobs each one with 10 operations, the maximum distance between two solutions would be 100. Hence, the PR (Path Relinking) procedure may only visit a maximum of 100 candidate solutions in the path from one solution to another. However, with our definition, the maximum d^π would be 4500¹ and the maximum d^α would be 100. In this way, a strategy such as

N_{2}^{α π}

will allow for a fine-grain exploration of the search space.
在贾和胡 (2014) 中，作者将两个解之间的距离定义为在编码字符串上位于不同位置的操作数。因此，对于一个具有 10 台机器和 10 个作业（每个作业有 10 个操作）的问题实例，两个解之间的最大距离将为 100。因此，PR（路径重链）过程可能仅访问从一个解到另一个解的路径中最多 100 个候选解。然而，根据我们的定义，最大 d ^π 将为 4500 ¹ ，最大 d ^α 将为 100。通过这种方式，诸如

N_{2}^{α π}

的策略将允许对搜索空间进行精细粒度的探索。

4.2. Initial reference set construction
4.2. 初始参考集构建

As suggested in Martí, Laguna, and Glover (2006), the reference set must contain a collection of high quality and diverse solutions. To achieve this, an initial set P is generated with PSize random solutions which are all improved using TS. Then, the reference set RefSet (of size RSSize) is built taking solutions from P one at a time such that, if possible, each solution fulfill the condition d^π(S, S_RS) > MinD^π or d^α(S, S_RS) > MinD^α for all S_RS already in RefSet, being MinD^π and MinD^α parameters. Firstly, half of the solutions are taken from the best ones in terms of makespan and the remaining are taken from the most distant² to the solutions already included in RefSet. If RefSet cannot be completed with solutions fulfilling the above condition, then the remaining ones are selected at random.
按照 Martí、Laguna 和 Glover (2006) 的建议，参考集必须包含高质量且多样化的解。为此，首先生成一个包含 PSize 个随机解的初始集 P，并使用 TS 对所有解进行改进。然后，构建参考集 RefSet（大小为 RSSize），每次从 P 中选择一个解，使得如果可能，每个解都满足条件 d ^π (S, S _RS ) > MinD ^π 或 d ^α (S, S _RS ) > MinD ^α ，其中 S _RS 是 RefSet 中已有的所有解，MinD ^π 和 MinD ^α 是参数。首先，从就完工时间而言最好的解中选择一半的解，其余的解则选择距离 RefSet 中已包含的解最远的 ² 解。如果无法用满足上述条件的解完成 RefSet，则随机选择剩余的解。

4.3. Subset generation method and diversification phase
4.3. 子集生成方法和多样化阶段

For subset generation, each pair of solutions in RefSet is combined to obtain a new solution (as explained in Section 4.4), unless they have not changed since the last time they were selected together. TS is then applied to the new solution and RefSet is updated in accordance with the reference set updating method (see Section 4.6). If no new solution is added to RefSet after combining all possible pairs of solutions, the diversification process is applied: the set P is rebuilt starting with the best solution so far, and new PSize − 1 solutions are generated at random. These schedules are then improved by TS, and finally a new RefSet is obtained from P as described in Section 4.2.
为了生成子集，会将参考集 (RefSet) 中每对解组合成一个新的解（如第 4.4 节所述），除非它们自上次一起被选中以来没有改变。然后对新的解应用 TS，并根据参考集更新方法（见第 4.6 节）更新 RefSet。如果在组合所有可能的解对后，RefSet 没有添加新的解，则应用多样化过程：从迄今为止的最佳解开始重建集合 P，并随机生成新的 PSize - 1 个解。然后通过 TS 改善这些排程，最后从 P 中获得新的 RefSet，如第 4.2 节所述。

4.4. Solution-combination method
4.4. 解组合方法

As solution-combination method we use PR. This metaheuristic has been successfully applied to the classical job shop scheduling problem. For example, Nowicki and Smutnicki (2005) improve their famous TSAB metaheuristic by introducing a new initial solution generator based on PR. Also, Nasiri and Kianfar (2012) combine TS and PR using two different neighborhoods.
作为解组合方法，我们使用 PR。该元启发式算法已成功应用于经典的作业车间调度问题。例如，Nowicki 和 Smutnicki (2005) 通过引入基于 PR 的新的初始解生成器来改进他们著名的 TSAB 元启发式算法。此外，Nasiri 和 Kianfar (2012) 使用两种不同的邻域将 TS 和 PR 结合起来。

PR combines two solutions, referred to as initial (S_ini) and guiding (S_end) solutions, to obtain a new solution. Starting from S_ini, it repeatedly applies moves so that each single move produces a solution which is closer to S_end than the current one. In our algorithm, S_ini is always the best of the two solutions taken from RefSet. In principle, the moves are those of N^απ (see Definition 6).
PR 结合两个解，分别称为初始解 (S _ini ) 和引导解 (S _end )，以获得新的解。从 S _ini 开始，它重复应用移动，使得每次移动都产生一个比当前解更接近 S _end 的解。在我们的算法中，S _ini 始终是 RefSet 中取出的两个解中的最佳解。原则上，这些移动是 N ^απ 的移动（见定义 6）。

Let S be a solution and S_end be the guiding solution of the PR algorithm. The following Proposition 4, Proposition 5 detail how the dissimilarity measures change between two consecutive solutions of the trajectory, depending on the neighborhood used.
令 S 为一个解，S _end 为 PR 算法的引导解。以下命题 4 和命题 5 详细说明了在使用不同邻域的情况下，轨迹中两个连续解之间的差异度量如何变化。

Proposition 4 命题 4

Let S_π ∈ N^π(S). Then, d^α(S_π, S_end) = d^α(S, S_end)
令 S _π ∈ N ^π (S)。则 d ^α (S _π , S _end ) = d ^α (S, S _end )

Proof 证明

It is trivial as the neighborhood N^π does not change any machine assignment. □
由于邻域 N ^π 不改变任何机器分配，因此这很容易。 □

On the other hand, a single move of N^π may reverse several processing orders of operations, hence d^π(S_π, S_end) may be several units lower or higher than, or even equal to, d^π(S, S_end).
另一方面，N ^π 的单次移动可能会改变多个操作的加工顺序，因此 d ^π (S _π , S _end ) 可能比 d ^π (S, S _end ) 低或高几个单位，甚至相等。

Proposition 5 命题 5

Let S_α ∈ N^α(S). Then, one and only one of the following conditions holds:
令 S _α ∈ N ^α (S)。那么，以下条件中只有一个成立：

•
d^α(S_α, S_end) = d^α(S, S_end) − 1∧d^π(S_α, S_end) ≥ d^π(S, S_end)
d_^α(S_{_α}, S_{_end}) = d_^α(S, S_{_end}) − 1∧d_^π(S_{_α}, S_{_end}) ≥ d_^π(S, S_{_end})
•
d^α(S_α, S_end) = d^α(S, S_end)∧d^π(S_α, S_end) = d^π(S, S_end)
d_^α(S_{_α}, S_{_end}) = d_^α(S, S_{_end})∧d_^π(S_{_α}, S_{_end}) = d_^π(S, S_{_end})
•
d^α(S_α, S_end) = d^α(S, S_end) + 1∧d^π(S_α, S_end) ≤ d^π(S, S_end)
d ^α (S _α , S _end ) = d ^α (S, S _end ) + 1∧d ^π (S _α , S _end ) ≤ d ^π (S, S _end )

Proof 证明

As N^α only changes the machine assignment of one operation, then d^α(S_α, S_end) − d^α(S, S_end) is 1, 0 or − 1, if the operation has the same machine assigned in S and S_end, or it has different assignment in S_end than in both S and S_α, or it has the same assignment in S_α and S_end, respectively.
由于 N ^α 只改变一个工序的机器分配，则 d ^α (S _α , S _end ) − d ^α (S, S _end ) 为 1、0 或 −1，如果该工序在 S 和 S _end 中分配的机器相同，或者在 S _end 中的分配与 S 和 S _α 中的分配不同，或者在 S _α 和 S _end 中的分配相同，分别对应。

If d^α(S_α, S_end) − d^α(S, S_end) = −1, then d^π(S_α, S_end) ≥ d^π(S, S_end) due to the fact that any pair of operations processed in the same order and the same machine in S and S_end remain in S_α and new pairs may be processed in S_α in different order than in S_end due to the new machine assignment. Analogous reasoning can be done if the value of the expression above is 1 or 0. □
如果 d ^α (S _α , S _end ) − d ^α (S, S _end ) = −1，则 d ^π (S _α , S _end ) ≥ d ^π (S, S _end )，因为在 S 和 S _end 中按相同顺序和相同机器处理的任何一对工序仍然保留在 S _α 中，并且由于新的机器分配，新的工序对可能以不同的顺序在 S _α 中处理。如果上述表达式的值是 1 或 0，则可以进行类似的推理。 □

From all the above, to select the next move in the PR algorithm, we start exploiting N_απ in the following way: the best solutions in each of N^α(S) and N^π(S) in terms of distance to the guiding solution S_end are considered. Then, the best of these two solutions,

S_{α}^{*}

and

S_{π}^{*},

is selected considering the estimated makespan and the proximity to S_end. In order to escape from local optima, similarly to TS, a neighbor obtained by reversing recently reversed arcs or by changing recent assignments is discarded, unless it is the closest to the guiding solution found so far.
综上所述，为了在 PR 算法中选择下一步操作，我们以以下方式开始利用 N _απ ：考虑在 N ^α (S) 和 N ^π (S) 中距离引导解 S _end 最近的最佳解。然后，考虑估计的完工时间和与 S _end 的接近程度，选择这两个解

S_{α}^{*}

和

S_{π}^{*},

中的较佳者。为了摆脱局部最优，类似于 TS，会丢弃通过反转最近反转的弧或更改最近分配获得的邻居，除非它是迄今为止找到的引导解最近的邻居。

Even with this mechanism, local optima may be so deep that N^απ may have difficulties to obtain an improving move. For this reason, we have considered the less restrictive neighborhood structure

N_{2}^{α π}

(see Definition 7). Thus, as soon as N^απ fails to reach a solution closer to the guiding solution maxFails times, the neighborhood structure changes to

N_{2}^{α π}

for the remaining of the path relinking procedure³. An alternative to the above would be using only

N_{2}^{α π}

in the path relinking algorithm. However, it is better to start using N^απ, since it is a more refined structure which guides the path through promising neighbors, and use

N_{2}^{α π}

only to complete the path when N^απ gets stuck into local optima in terms of distance.
即使有这种机制，局部最优解可能很深，以至于 N ^απ 可能难以找到改进的移动。因此，我们考虑了不太严格的邻域结构

N_{2}^{α π}

（见定义 7）。因此，一旦 N ^απ 未能找到比引导解更接近的解 maxFails 次，则邻域结构在路径重链过程 ³ 的剩余部分中更改为

N_{2}^{α π}

。另一种选择是在路径重链算法中仅使用

N_{2}^{α π}

。但是，最好先使用 N ^απ ，因为它是一种更精细的结构，可引导路径通过有希望的邻居，并且仅使用

N_{2}^{α π}

来完成路径，当 N ^απ 在距离方面陷入局部最优解时。

The search finishes when the guiding solution is reached. Then, as proposed by Nowicki and Smutnicki (2006), the algorithm returns the solution with the best makespan that is located between 1/4 and 3/4 of the created trajectory, unless a solution improving the best solution so far is found out of this range.
当引导解被找到时，搜索结束。然后，正如 Nowicki 和 Smutnicki (2006) 所建议的那样，算法返回在创建轨迹的 1/4 到 3/4 之间具有最佳完工时间的解，除非在此范围之外找到一个改进当前最佳解的解。

This way of building a path from the initial to the guiding solution is also quite different from that proposed in Jia and Hu (2014) and it generally builds a longer path. This can be seen in the example given in that paper where the path has only two intermediate solutions whereas our method would generate at least six.
从初始解到引导解构建路径的方法也与贾和胡 (2014) 的方法大相径庭，并且通常会构建更长的路径。这一点可以在该论文给出的示例中看到，该路径只有两个中间解，而我们的方法则会生成至少六个。

The proposed PR algorithm is detailed in Algorithm 2, where TL denotes the Tabu List, and ¬Tabu(S′, TL) means that the move from S to S′ is not in TL.
提出的 PR 算法在算法 2 中详细说明，其中 TL 表示禁忌表，¬Tabu(S′, TL) 表示从 S 到 S′ 的移动不在 TL 中。

4.5. Improvement method 4.5. 改进方法

As improvement method we use TS (Tabu Search). This is an advanced local search technique with a solid record of good empirical performance in problem solving, in particular in scheduling (González, Vela, González-Rodríguez, Varela, 2013, Nowicki, Smutnicki, 2005).
作为改进方法，我们使用禁忌搜索 (TS)。这是一种先进的局部搜索技术，在问题求解中，特别是调度问题中，具有良好的经验性能记录（González 等人，2013；Nowicki 和 Smutnicki，2005）。

The general scheme of our TS is similar to that proposed in Amico and Trubian (1993). In the first step the initial solution is evaluated. Then, it iterates over a number of steps. In each iteration, the neighborhood of the current solution is built using

N_{r}^{α π}

(see Definition 5) and one of the neighbors is selected for the next iteration. The selection rule chooses the neighbor with the best estimated makespan, discarding suspect-of-cycle and tabu neighbors. The tabu search finishes after a number of maxImproveIter iterations without improvement, returning the best solution reached so far.
我们 TS 的总体方案与 Amico 和 Trubian (1993) 的方案类似。第一步评估初始解。然后，它迭代执行若干步骤。在每次迭代中，使用

N_{r}^{α π}

(见定义 5) 构造当前解的邻域，并从中选择一个邻居作为下一迭代的解。选择规则选择估计完工时间最优的邻居，并丢弃可疑循环和禁忌邻居。禁忌搜索在没有改进的情况下执行 maxImproveIter 次迭代后结束，返回迄今为止找到的最佳解。

Instead of storing actual solutions in the tabu list, those arcs which have been reversed or the assignments that have been changed to generate a neighbor are stored. Thus a new neighbor is marked as tabu if it requires reversing at least one arc or changing a machine assignment included in the tabu list, unless its estimated makespan is better than the best makespan found so far.
而不是将实际解存储在禁忌表中，而是存储那些已被反转的弧或已被更改以生成邻居的分配。因此，如果新邻居需要反转禁忌表中包含的至少一条弧或更改机器分配，则将其标记为禁忌，除非其估计的完工时间比迄今为止找到的最佳完工时间更好。

The length of the tabu list is usually of critical importance, since it allows for an equilibrium between intensification and diversification. All TS algorithms try to manage this equilibrium with different proposals based on controlling the number of iterations for which a solution can keep its tabu status. We use here the dynamic length schema and the cycle checking mechanism based on witness arcs used, among others, by Amico and Trubian (1993), and extended it by adding the information about changes in the machine assignment of operations.
禁忌表的长度通常至关重要，因为它允许在强化和多样化之间取得平衡。所有禁忌搜索算法都尝试通过控制解保持禁忌状态的迭代次数来管理这种平衡。我们在这里使用了动态长度方案和基于见证弧的循环检测机制，这些机制也由 Amico 和 Trubian (1993) 使用，并通过添加有关作业机器分配变化的信息对其进行了扩展。

The time given to each tabu search must be short enough for the overall computational time of the scatter search algorithm not to be prohibitive. For this reason, we do not use any more diversification techniques in the TS procedure proposed here.
为避免散列搜索算法的总体计算时间过长，每个禁忌搜索的时间必须足够短。因此，我们在此提出的禁忌搜索过程中不再使用任何其他多样化技术。

4.6. Reference set update
4.6. 参考集更新

Let S_B and S_W be the best and worst solutions in RefSet respectively. Each solution returned by PR is improved by TS. Then, for the sake of quality and diversity, the resulting solution S replaces S_W either if C_max(S) < C_max(S_B), or if C_max(S) < C_max(S_W) and for all S_RS ∈ RefSet it holds that d^π(S, S_RS) > MinD^π or d^α(S, S_RS) > MinD^α.
令 S _B 和 S _W 分别为 RefSet 中的最佳和最差解。PR 返回的每个解都由 TS 改善。然后，为了提高质量和多样性，如果 C _max (S) < C _max (S _B )，或者如果 C _max (S) < C _max (S _W ) 并且对于 RefSet 中的所有 S _RS ，都有 d ^π (S, S _RS ) > MinD ^π 或 d ^α (S, S _RS ) > MinD ^α ，则结果解 S 替换 S _W 。

4.7. Similarities and differences w.r.t. other proposals
4.7. 与其他建议的异同

As we have mentioned, metaheuristics have been widely applied to solve the FJSP. In this work, we borrowed some ideas from existing methods and include a good number of new ones. For example, we used SS and TS templates similar to those proposed in Glover (1998) and Amico and Trubian (1993) respectively. On the other hand, the proposed neighborhood structures are quite different from other structures defined for the FJSP in Mastrolilli and Gambardella (2000), González et al. (2013), Yuan and Xu (2013). However, if we will restrict to the JSP, we could observe that some sequencing structures are in fact extensions of some classic structures: N^π extends the structure NB proposed in Amico and Trubian (1993) and

N_{2}^{π}

extends the structure H′ defined in Van Laarhoven et al. (1992). At the same time, the structure H defined in Nowicki and Smutnicki (1996) is a restriction of H′, in much the same way as

N_{r}^{π}

restricts N^π (removing moves for which it is known a priori that they will not improve the makespan). For the sequencing structures we established feasibility and non-improvement conditions, as well as a procedure to estimate the makespan of the neighbors, which are inspired in proposals given in Amico and Trubian (1993), Mattfeld (1995) for the classic JSP. Also, the proposed assignment structures N^α and

N_{2}^{α}

are simpler and less time consuming versions of the k-insertion structure proposed in Mastrolilli and Gambardella (2000). A key point of our algorithm is the new fine grain dissimilarity measure for solutions. With this measure and the neighborhood structures N^απ and

N_{2}^{α π},

the trajectories between two solutions are much larger than, for example, those obtained from the coarse grain measure defined in Jia and Hu (2014), which allows PR to explore more solutions in each run.
正如我们所提到的，元启发式算法已被广泛应用于求解柔性作业车间调度问题。在这项工作中，我们借鉴了现有方法的一些想法，并包含了许多新的想法。例如，我们使用了类似于 Glover (1998) 和 Amico 和 Trubian (1993) 分别提出的 SS 和 TS 模板。另一方面，所提出的邻域结构与 Mastrolilli 和 Gambardella (2000)、González 等人 (2013)、Yuan 和 Xu (2013) 中为 FJSP 定义的其他结构截然不同。然而，如果我们只关注 JSP，我们会发现一些排序结构实际上是某些经典结构的扩展：N ^π 扩展了 Amico 和 Trubian (1993) 中提出的 NB 结构，而

N_{2}^{π}

扩展了 Van Laarhoven 等人 (1992) 中定义的 H′ 结构。与此同时，Nowicki 和 Smutnicki (1996) 中定义的 H 结构是 H′ 的限制，就像

N_{r}^{π}

限制 N ^π （删除已知先验不会改善制造时间的移动）。对于排序结构，我们建立了可行性和非改进条件，以及估计邻居工期的程序，这些程序受到 Amico 和 Trubian (1993)、Mattfeld (1995)在经典 JSP 中的建议的启发。此外，所提出的分配结构 N ^α 和

N_{2}^{α}

是 Mastrolilli 和 Gambardella (2000)中提出的 k-插入结构的更简单、更省时的版本。我们算法的一个关键点是新的细粒度解差异度量。有了这个度量和邻域结构 N ^απ 和

N_{2}^{α π},

，两个解之间的轨迹比 Jia 和 Hu (2014)中定义的粗粒度度量获得的轨迹大得多，这允许 PR 在每次运行中探索更多解。

5. Experimental study 5. 实验研究

We have conducted an experimental study to evaluate our proposals and to compare the algorithm, termed SSPR, with the state of the art. In this study, we have considered the four benchmark sets most widely used in the literature, namely, DPdata (Dauzère-Pérès and Paulli, 1997), BCdata (Barnes and Chambers, 1996), BRdata (Brandimarte, 1993) and HUdata (Hurink, Jurisch, and Thole, 1994), making a total of 178 instances with different sizes and flexibility (the average number of possible machines per operation).
我们进行了一项实验研究，以评估我们的建议并比较该算法（称为 SSPR）与现有最先进算法。在这项研究中，我们考虑了文献中使用最广泛的四个基准集，即 DPdata（Dauzère-Pérès 和 Paulli，1997）、BCdata（Barnes 和 Chambers，1996）、BRdata（Brandimarte，1993）和 HUdata（Hurink、Jurisch 和 Thole，1994），总共包含 178 个具有不同规模和灵活性的实例（每个操作可能的机器数量的平均值）。

SSPR was implemented in C + + and the target machine was Intel Core 2 Duo at 2.66 gigahertz and 2 gigabytes RAM. We run SSPR 10 times for each instance and register the best and average makespan. To compare different methods, we indicate whether or not a method was able to reach the best known solution for each instance and report the Relative Percentage Deviation (RPD) defined as:
SSPR 使用 C++ 实现，目标机器是英特尔酷睿 2 双核处理器，主频为 2.66 吉赫兹，内存为 2 吉字节。我们针对每个实例运行 SSPR 10 次，并记录最佳和平均完工时间。为了比较不同的方法，我们指出每种方法是否能够找到每个实例的最佳已知解，并报告相对百分比偏差 (RPD)，定义如下：

R P D = ((A l g_{s o l} - L B) / L B) \times 100

where Alg_sol is the value of the objective function obtained by a given algorithm for a given instance, and LB is a lower bound on the optimal solution. We consider here the lower bounds reported in Mastrolilli and Gambardella (2000) for all 178 instances.
其中 Alg _sol 是由给定算法针对给定实例获得的目标函数值，LB 是最优解的下界。我们在此考虑 Mastrolilli 和 Gambardella (2000) 中报告的 178 个实例的所有下界。

In the next sections we report and analyze the results of our experimental study. Firstly, we describe how we have done the parameter tuning. Then, we analyze the proposed neighborhood structures and compare SSPR with its TS component running alone. In the last section, we present an exhaustive and fair comparison of SSPR with the current best methods.
接下来的章节中，我们将报告和分析我们的实验研究结果。首先，我们将描述参数调整的方法。然后，我们将分析所提出的邻域结构，并将 SSPR 与单独运行的 TS 组件进行比较。最后，我们将对 SSPR 与当前最佳方法进行全面和公平的比较。

5.1. Parameter tuning 5.1. 参数调整

We have performed a preliminary study considering different values of the parameters and using similar run times for each configuration tested. Below, we summarize the parameters of the SSPR algorithm and the tested values for each one of them.
我们对不同参数值进行了初步研究，并使用相似的运行时间来测试每个配置。下面，我们总结了 SSPR 算法的参数及其每个参数的测试值。

RSSize defines the number of solutions of RefSet. This number is usually lower than 20, as indicated by Glover in Glover (1998). Here we tried RSSize = 8 and RSSize = 10 because these are typical values in the literature (see Nowicki, Smutnicki, 2006, Yamada, Nakano, 1996).
RSSize 定义了 RefSet 的解的数量。这个数字通常低于 20，正如 Glover 在 Glover (1998) 中所指出的那样。这里我们尝试了 RSSize = 8 和 RSSize = 10，因为这些是文献中的典型值（参见 Nowicki, Smutnicki, 2006, Yamada, Nakano, 1996）。

PSize defines the number of solutions in the initial set P. In Glover, Laguna, and Martí (2003) it is suggested that PSize = max(100, 5*RSSize). However, the diversification phase that we have proposed will need to rebuild the set P several times during an execution. As this process is computationally expensive, we considered a smaller size for P. In particular we tested sizes 20 and 100.
PSize 定义了初始集合 P 中解的数量。在 Glover, Laguna, 和 Martí (2003) 中建议 PSize = max(100, 5*RSSize)。然而，我们提出的多样化阶段需要在执行过程中多次重建集合 P。由于这个过程计算成本很高，我们考虑了较小的 P 大小。特别是，我们测试了 20 和 100 的大小。

maxFails is a parameter that defines the number of times PR chooses a non-improving neighbor with N^απ before switching to

N_{2}^{α π}

. We considered the values 1, 5 and 20.
maxFails 是一个参数，定义了 PR 选择非改进的邻居 N ^απ 的次数，然后切换到

N_{2}^{α π}

。我们考虑了 1、5 和 20 的值。

maxImproveIter is the maximum number of iterations without improvement in each run of TS and establishes its stopping condition. TS is embedded in the scatter search core and so it is issued many times during an execution of SSPR, for this reason we cannot choose values as high as in a TS algorithm running alone. We considered values of 100, 500, 2000 and 10,000.
maxImproveIter 是 TS 每次运行中最大迭代次数，且以此作为停止条件。TS 嵌入在散布搜索核心，因此在 SSPR 的执行过程中会多次发出，因此我们不能选择像单独运行 TS 算法时那样高的值。我们考虑了 100、500、2000 和 10,000 的值。

MinD^α and MinD^π are two parameters that control the minimum distance allowed between solutions in RefSet, and hence they should ensure diversity in the set. We tested values of 5, 20 and 50 for MinD^π, and values of 1, 3 and 5 for MinD^α.
MinD ^α 和 MinD ^π 是两个参数，控制 RefSet 中解之间的最小距离，因此它们应该保证集合的多样性。我们测试了 MinD ^π 的值 5、20 和 50，以及 MinD ^α 的值 1、3 和 5。

From this preliminary study, we have chosen RSSize = 8, PSize = 20, maxFails = 5, maxImproveIter = 2000, MinD^π = 20 and MinD^α = 3, as this was the combination that reached the best results in average. As stopping criterion we choose a number of 250 iterations of SSPR without improvement. This value results in reasonable convergence patterns, as shown in Fig. 5, which details the evolution of the best and average makespan using the chosen configuration for one run on the 02a instance of the DPdata benchmark. Notice the four times the diversification phase is issued with a sudden increase in the average makespan of the solutions in RefSet.
从这项初步研究中，我们选择了 RSSize = 8，PSize = 20，maxFails = 5，maxImproveIter = 2000，MinD ^π = 20 和 MinD ^α = 3，因为这是平均结果最好的组合。作为停止准则，我们选择在没有改进的情况下 SSPR 迭代 250 次。该值导致合理的收敛模式，如图 5 所示，该图详细说明了使用所选配置在 DPdata 基准的 02a 实例上进行一次运行时最佳和平均完工时间的演变。注意，多样化阶段四次出现，导致 RefSet 中解决方案的平均完工时间突然增加。

5.2. Analysis of the neighborhood structures
5.2. 邻域结构分析

To analyze the neighborhood structures we considered all instances in the HUdata benchmark. Firstly, we have evaluated the percentage of neighbors created by

N_{r}^{π}

and N^α in the TS procedure. Table 1 illustrates that this percentage strongly depends on the flexibility of the instance; which is reasonable as the number of neighbors created with N^α is in direct ratio with the number of machines suitable for each operation on the critical path.
为了分析邻域结构，我们考虑了 HUdata 基准中的所有实例。首先，我们评估了 TS 过程中

N_{r}^{π}

和 N ^α 创建的邻居的百分比。表 1 显示，该百分比强烈依赖于实例的灵活性；这是合理的，因为使用 N ^α 创建的邻居数量与关键路径上每项操作合适的机器数量成正比。

Table 1. Percentage of neighbors created by $N_{r}^{π}$ and N^α in the TS procedure.
表 1. TS 过程中 $N_{r}^{π}$ 和 N ^α 创建的邻居的百分比。

Ins. (flex) 实例 (灵活性)	edata (1.15)	rdata (2)	vdata(5–7.5)
Percent Neigh by N^α 百分比邻域由 N ^α	8	47	73

Then, we analyzed the influence of the size and shape of the instances on the length and the number of neighbors of the critical blocks. The results summarized in Table 2 show clearly that these values depend on the instance size but mainly on the quotient n/m. This is reasonable as for instances with few machines and many operations, critical paths most certainly go through many disjunctive arcs. We also made some experiments to compare our definition of critical block with that considered in Mastrolilli and Gambardella (2000) and in González et al. (2013), i.e., not allowing several operations of the same job in the same critical block. The results (not reported here) were slightly better with our definition as the number of generated neighbors was lower, and this fact allowed our algorithm to obtain better results in slightly less time.
然后，我们分析了实例大小和形状对关键块长度和邻居数量的影响。表 2 中总结的结果清楚地表明，这些值取决于实例大小，但主要取决于商 n/m。这是合理的，因为对于机器数量少、操作数量多的实例，关键路径很可能穿过许多不相交的弧。我们还进行了一些实验，将我们对关键块的定义与 Mastrolilli 和 Gambardella (2000) 以及 González 等人 (2013) 中考虑的定义进行了比较，即不允许同一作业的多个操作出现在同一关键块中。结果（此处未报告）略好，因为生成的邻居数量较少，这使得我们的算法能够在略短的时间内获得更好的结果。

Table 2. Average length of the critical blocks and number of neighbors created by $N_{r}^{π}$ .
表 2. $N_{r}^{π}$ 创建的关键块的平均长度和邻居数量。

Size 大小	10 × 5	15 × 5	20 × 5	10 × 10	15 × 10	20 × 10	30 × 10	15 × 15
#Op. in CB #工序在 CB 中	6.39	11.57	16.45	2.83	4.83	7.85	16.72	2.98
#Neigh per CB #每个 CB 的邻居	9.60	17.69	25.68	2.83	6.44	10.02	17.31	3.08

Finally, in order to assess the makespan estimation procedure, we have registered the actual and estimated makespan of about 300 million neighbors. Table 3 summarizes the percentages of coincidences and discrepancies, in this last case showing the relative errors. As we can observe, the accuracy of the estimation is high, especially for N^α. In these experiments we have also observed that the accuracy is in inverse ratio with flexibility.
最后，为了评估排程提前期估计方法，我们记录了大约 3 亿个邻居的实际和估计提前期。表 3 总结了匹配和差异的百分比，后一种情况显示了相对误差。正如我们所观察到的，估计的准确性很高，尤其对于 N ^α 。在这些实验中，我们还观察到准确性与灵活性成反比。

Table 3. Accuracy of the estimates.
表 3. 估计的准确性

Empty Cell	$N_{r}^{π}$		N^α
Empty Cell	Empty Cell		Empty Cell
Empty Cell	Percent of Est 百分比估计值	Rel dif 相对差异	Percent of Est 百分比估计值	Rel dif 相对差异
$C_{m a x}^{e} = C_{m a x}$	83.3		96.9
$C_{m a x}^{e} < C_{m a x}$	3.0	1.4	3.1	3.1
$C_{m a x}^{e} > C_{m a x}$	13.7	2.1	−

5.3. Comparing SSPR with tabu search running alone
5.3. 将 SSPR 与单独运行的禁忌搜索进行比较

It is well known that tabu search is a very efficient metaheuristic at solving scheduling problems (see for example Nowicki and Smutnicki, 2005 or González et al., 2013). Here we have carried out some experiments to assess if the scatter search with path relinking shell is capable of improving the performance of the tabu search running alone. To this end, we compared the results of SSPR with those from tabu search, giving both algorithms the same time. In the experiments, we have opted to set the same stopping criterion as in SSPR (2000 iterations without improvement), and to launch tabu search starting from random solutions as many times as possible in the time taken by SSPR. We have tried other settings with worse results for TS.
众所周知，禁忌搜索是一种非常有效的元启发式算法，用于解决调度问题（例如，参见 Nowicki 和 Smutnicki，2005 或 González 等人，2013）。在这里，我们进行了一些实验，以评估带有路径重链的散射搜索壳是否能够提高单独运行的禁忌搜索的性能。为此，我们将 SSPR 的结果与禁忌搜索的结果进行了比较，并为两种算法提供了相同的时间。在实验中，我们选择将停止标准与 SSPR 保持相同（2000 次迭代未改进），并在 SSPR 所需的时间内尽可能多次地从随机解启动禁忌搜索。我们尝试过其他设置，但结果比 TS 差。

We have used the DPdata benchmark for this comparison. To obtain similar run times we have had to launch tabu search from 300 to 600 times, depending on the particular instance. In 16 of the 18 instances the best makespan reached by tabu search was worse than that reached by SSPR, and in the remaining 2 instances the results were the same. The mean values are summarized in Table 4. From these results it may be fair to consider that SSPR outperforms tabu search running alone.
我们使用 DPdata 基准进行比较。为了获得类似的运行时间，我们不得不将禁忌搜索运行 300 到 600 次，具体取决于特定实例。在 18 个实例中的 16 个实例中，禁忌搜索达到的最佳完工时间比 SSPR 达到的差，其余 2 个实例的结果相同。表 4 总结了平均值。从这些结果来看，可以公平地认为 SSPR 的性能优于单独运行的禁忌搜索。

Table 4. Comparison of average performance of tabu search running alone versus SSPR.
表 4. 比较单独运行禁忌搜索与 SSPR 的平均性能。

Empty Cell	Tabu search 禁忌搜索		SSPR
Empty Cell	Empty Cell		Empty Cell
Empty Cell	Best 最佳	Avg 平均	Best 最佳	Avg 平均
RPD	2.26	2.52	1.57	1.79

5.4. Comparison with the state of the art
5.4. 与现有技术的比较

Finally, we have conducted experiments to compare SSPR with the best algorithms we have found in the literature, namely: TS, hGA, HHS/LNS, CDDS, GA + TS, TSBM²h and MGARH from Mastrolilli and Gambardella (2000), Gao et al. (2008), Yuan and Xu (2013), Hmida et al. (2010), González et al. (2013), Bozejko et al. (2010), Gutierrez and Garcia-Magario (2011) respectively.
最后，我们进行了实验，将 SSPR 与文献中找到的最佳算法进行了比较，即：TS、hGA、HHS/LNS、CDDS、GA + TS、TSBM ² h 和 Mastrolilli 和 Gambardella (2000)、Gao 等人(2008)、Yuan 和 Xu(2013)、Hmida 等人(2010)、González 等人(2013)、Bozejko 等人(2010)、Gutierrez 和 Garcia-Magario(2011)分别提出的 MGARH。

Table 5, Table 6, Table 7 show the results of the experiments in DPdata, BCdata and BRdata benchmarks respectively. We indicate for each instance its flexibility and the lower bound reported in Mastrolilli and Gambardella (2000). Then, for each method we report the best and average (between parentheses) makespan. We also report the average runtime in seconds of a single run of SSPR. At the bottom of each table we show the average of the best and the mean RPD for each algorithm, the number of instances for which a method reaches the best known solution, and the sum of average Computer-Independent CPU time. CI-CPU time values have been obtained from the normalization coefficients of Dongarra (2013). As indicated in Yuan and Xu (2013) “it should be noted that the comparison between CPU time is meant to be indicative, because we do not have access to other information that influences the computation time, such as the operating systems, software engineering decisions, and coding skills of the programmer.”
表 5、表 6 和表 7 分别显示了在 DPdata、BCdata 和 BRdata 基准测试中的实验结果。我们为每个实例指出了其灵活性以及 Mastrolilli 和 Gambardella (2000) 中报告的下限。然后，对于每种方法，我们报告最佳和平均（括号内）的完工时间。我们还报告了 SSPR 单次运行的平均运行时间（以秒为单位）。在每张表的底部，我们显示了每种算法的最佳值和平均 RPD 的平均值，以及一种方法达到最佳已知解决方案的实例数量，以及平均独立于计算机的 CPU 时间总和。CI-CPU 时间值已从 Dongarra (2013) 的归一化系数中获得。正如 Yuan 和 Xu (2013) 所指出的那样，“应该注意的是，CPU 时间的比较仅具有指示意义，因为我们无法访问影响计算时间的其他信息，例如操作系统、软件工程决策以及程序员的编码技能。”

Table 5. Summary of results: DPdata.
表 5. DPdata 结果总结。

Ins 实例	flex. 灵活性	LB	TS	hGA	CDDS	HHS/LNS	GA + TS	SSPR	T(s.)
01a 01 甲	1.13	2505	2518 (2528)	2518 (2518)	2518 (2525)	2505 (2513)	2505 (2511)	2505 (2508)	68
02a 02 甲	1.69	2228	2231 (2234)	2231 (2231)	2231 (2235)	2230 (2231)	2232 (2234)	*2229()** (2230)	100
03a	2.56	2228	2229 (2230)	2229 (2229)	2229 (2232)	2228 (2229)	2229 (2230)	*2228()** (2228)	110
04a	1.13	2503	2503 (2516)	2515 (2518)	2503 (2510)	2506 (2506)	2503 (2504)	2503 (2504)	57
05a	1.69	2189	2216 (2220)	2217 (2218)	2216 (2218)	2212 (2215)	2219 (2221)	*2211()** (2215)	112
06a	2.56	2162	2203 (2206)	2196 (2198)	2196 (2203)	2187 (2192)	2200 (2204)	*2183()** (2192)	181
07a	1.24	2187	2283 (2298)	2307 (2310)	2283 (2296)	2288 (2303)	2266 (2286)	2274 (2285)	139
08a	2.42	2061	2069 (2071)	2073 (2076)	2069 (2069)	2067 (2074)	2072 (2075)	*2064()** (2066)	181
09a	4.03	2061	2066 (2067)	2066 (2067)	2066 (2067)	2069 (2073)	2066 (2067)	*2062()** (2063)	213
10a	1.24	2178	2291 (2306)	2315 (2315)	2291 (2303)	2297 (2302)	2267 (2273)	2269 (2287)	120
11a	2.42	2017	2063 (2066)	2071 (2072)	2063 (2072)	2061 (2067)	2068 (2071)	*2051()** (2058)	193
12a	4.03	1969	2034 (2038)	2030 (2031)	2031 (2034)	2027 (2036)	2037 (2041)	*2018()** (2020)	280
13a	1.34	2161	2260 (2266)	2257 (2260)	2257 (2260)	2263 (2269)	2271 (2276)	*2248()** (2257)	119
14a	2.99	2161	2167 (2168)	2167 (2168)	2167 (2179)	2164 (2168)	2169 (2171)	*2163()** (2164)	269
15a	5.02	2161	2167 (2167)	2165 (2165)	2165 (2170)	2163 (2166)	2166 (2166)	*2162()** (2163)	376
16a	1.34	2148	2255 (2259)	2256 (2258)	2256 (2258)	2259 (2266)	2266 (2271)	*2244()** (2253)	131
17a	2.99	2088	2141 (2144)	2140 (2142)	2140 (2146)	2137 (2141)	2147 (2150)	*2130()** (2134)	299
18a	5.02	2057	2137 (2140)	2127 (2131)	2127 (2132)	2124 (2128)	2138 (2141)	*2119()** (2123)	409
RPD			2.01 (2.24)	2.12 (2.19)	1.94 (2.19)	1.89 (2.13)	1.99 (2.17)	1.57 (1.79)
#best			1	0	1	2	4	16
CI-CPU			2467	6206	2890	6279	3397	1934

Values in bold are best known solutions, (*) improves previous best known solution.
粗体值是最佳已知解，(*) 表示改进之前的最佳已知解。

Table 6. Summary of results: BCdata.
表 6. BC 数据结果总结。

Ins 实例	flex. 灵活性	LB	TS	hGA	CDDS	TSBM²h TSBM ² 小时	GA + TS	SSPR	T(s.)
mt10c1	1.10	655	928 (928)	927 (927)	928 (929)	927 (–) 927（–）	927 (927)	927 (928)	26
mt10cc	1.20	655	910 (910)	910 (910)	910 (911)	908 (–) 908（－）	908 (909)	908 (908)	20
mt10x	1.10	655	918 (918)	918 (918)	918 (918)	922 (–) 922（－）	918 (922)	918 (918)	23
mt10xx	1.20	655	918 (918)	918 (918)	918 (918)	918 (–) 918（—）	918 (918)	918 (918)	19
mt10xxx	1.30	655	918 (918)	918 (918)	918 (918)	918 (–) 918（—）	918 (918)	918 (918)	20
mt10xy	1.20	655	906 (906)	905 (905)	906 (906)	905 (–) 905（–）	905 (905)	905 (906)	21
mt10xyz	1.30	655	847 (850)	849 (849)	849 (851)	849 (–) 849（–）	849 (850)	847 (847)	20
setb4c9	1.10	857	919 (919)	914 (914)	919 (919)	914 (–) 914（–）	914 (914)	914 (916)	28
setb4cc	1.20	857	909 (912)	914 (914)	909 (911)	907 (–) 907（–）	907 (907)	907 (907)	21
setb4x	1.10	846	925 (925)	925 (931)	925 (925)	925 (–) 925（–）	925 (925)	925 (925)	19
setb4xx	1.20	846	925 (926)	925 (925)	925 (925)	925 (–) 925（–）	925 (925)	925 (925)	21
setb4xxx	1.30	846	925 (925)	925 (925)	925 (925)	925 (–) 925（－）	925 (925)	925 (925)	22
setb4xy	1.20	845	916 (916)	916 (916)	916 (916)	910 (–) 910（－）	910 (910)	910 (912)	32
setb4xyz	1.30	838	905 (908)	905 (905)	905 (907)	903 (–) 903（-）	905 (905)	905 (905)	21
seti5c12	1.07	1027	1174 (1174)	1175 (1175)	1174 (1175)	1174 (–) 1174（-）	1171 (1173)	*1170()** (1173)	25
seti5cc	1.13	955	1136 (1136)	1138 (1138)	1136 (1137)	1136 (–) 1136（–）	1136 (1137)	*1135()** (1136)	29
seti5x	1.07	955	1201 (1204)	1204 (1204)	1201 (1202)	1198 (–) 1198（–）	1199 (1200)	1198 (1199)	41
seti5xx	1.13	955	1199 (1201)	1202 (1203)	1199 (1199)	1197 (–) 1197（–）	1197 (1198)	1197 (1199)	37
seti5xxx	1.20	955	1197 (1198)	1204 (1204)	1197 (1198)	1197 (–) 1197（–）	1197 (1197)	*1194()** (1198)	38
seti5xy	1.13	955	1136 (1136)	1136 (1137)	1136 (1138)	1136 (–) 1136（–）	1136 (1137)	*1135()** (1136)	29
seti5xyz	1.20	955	1125 (1127)	1126 (1126)	1125 (1125)	1128 (–) 1128（–）	1127 (1128)	1125 (1126)	35
RPD			22.53 (22.63)	22.61 (22.66)	22.54 (22.60)	22.45 (–) 22.45（–）	22.42 (22.49)	22.36 (22.44)
#best			8	9	7	14	13	20
CI-CPU			356	821	253	1068	437	248

Values in bold are best known solutions, (*) improves previous best known solution. – means that the corresponding data is not available.
粗体值是最佳已知解，(*) 表示改进之前的最佳已知解。– 表示相应数据不可用。

Table 7. Summary of results: BRdata.
表 7. BRdata 结果总结。

Ins 实例	flex. 灵活性	LB	TS	hGA	CDDS	HHS/LNS	MGARH	GA + TS	SSPR	T(s.)
Mk01	2.09	36	40 (40)	40 (40)	40 (40)	40 (–) 40（–）	40 (–) 40（–）	40 (40)	40 (40)	11
Mk02	4.10	24	26 (26)	26 (26)	26 (26)	26 (–) 26（—）	26 (–) 26（—）	26 (26)	26 (26)	15
Mk03	3.01	204	204 (204)	204 (204)	204 (204)	204 (–) 204（—）	204 (–) 204（—）	204 (204)	204 (204)	24
Mk04	1.91	48	60 (60)	60 (60)	60 (60)	60 (–) 60（—）	60 (–) 60（–）	60 (60)	60 (60)	19
Mk05	1.71	168	173 (173)	172 (172)	173 (174)	172 (–) 172（–）	172 (–) 172（–）	172 (172)	172 (172)	57
Mk06	3.27	33	58 (58)	58 (58)	58 (59)	58 (–) 58（—）	57 (–) 57（—）	58 (58)	57 (58)	40
Mk07	2.83	133	144 (147)	139 (139)	139 (139)	139 (–) 139（–）	139 (–) 139（–）	139 (139)	139 (141)	84
Mk08	1.43	523	523 (523)	523 (523)	523 (523)	523 (–) 523（–）	523 (–) 523（–）	523 (523)	523 (523)	83
Mk09	2.53	299	307 (307)	307 (307)	307 (307)	307 (–) 307（–）	308 (–) 308（–）	307 (307)	307 (307)	52
Mk10	2.98	165	198 (199)	197 (197)	197 (198)	198 (–) 198（–）	196 (–) 196（–）	199 (200)	196 (197)	94
RPD			15.41 (15.83)	14.92 (14.92)	15.41 (15.55)	14.98 (–) 14.98（–）	14.59 (–) 14.59（–）	15.04 (15.13)	14.55 (15.03)
#best			6	8	7	8	9	8	10
CI-CPU			74	91	96			250	383

Values in bold are best known solutions, – means that the corresponding data is not available.
粗体值是最佳已知解，– 表示相应数据不可用。

In the DPdata benchmark (Table 5) SSPR performs the best in all metrics considered, improving previous best known solutions in 13 out of the 18 instances. Notice that the mean RPD of SSPR is better than the best RPD of the remaining methods in average.
在 DPdata 基准测试 (表 5) 中，SSPR 在所有考虑的指标中表现最佳，在 18 个实例中的 13 个实例中改进了先前的最佳已知解。请注意，SSPR 的平均 RPD 优于其他方法的最佳 RPD 的平均值。

The results on the BCdata set are shown in Table 6. In this case, we include the results from TSBM²h reported in Bozejko et al. (2010) and omit results from HHS/LNS, as only the average RPD for the best solutions (22.43) is given in Yuan and Xu (2013) for this data set. Overall, SSPR is the best of the six algorithms in all metrics, and improves the previous best known solution in 4 of the 21 instances.
BCdata 集的结果显示在表 6 中。在这种情况下，我们包含了 Bozejko 等人 (2010) 中报告的 TSBM ² h 的结果，并省略了 HHS/LNS 的结果，因为 Yuan 和 Xu (2013) 只为该数据集提供了最佳解决方案的平均 RPD (22.43)。总体而言，SSPR 在所有指标中都是六种算法中最好的，并且在 21 个实例中的 4 个实例中改进了先前的最佳已知解。

Table 7 shows the results on BRdata. This is the only table that includes results from MGARH, as this is the only set considered in Gutierrez and Garcia-Magario (2011). In this case, SSPR obtains the best known solution in all instances, it is the second best considering the average makespan and the best one considering the best makespan, as indicated by RPD values.
表 7 显示了 BRdata 上的结果。这是唯一包含 MGARH 结果的表格，因为这是 Gutierrez 和 Garcia-Magario (2011) 中唯一考虑的集合。在这种情况下，SSPR 在所有实例中都获得了最佳已知解，考虑到平均完工时间，它是第二好的，考虑到最佳完工时间，它是最好的，如 RPD 值所示。

From the CI-CPU times reported in Table 5, Table 6, Table 7, we can observe that SSPR is the best on DPdata and BCdata. However, it appears as the worst one for BRdata due to the parameters chosen, which make SSPR to run for too long time in most of the cases. This is clear as SSPR reaches the best solution in the first iteration for most of these instances with negligible time. In Hmida et al. (2010) the authors did not provide the time taken by HHS/LNS on these instances as they consider these times not relevant for similar reasons.
从表 5、表 6、表 7 中报告的 CI-CPU 时间可以看出，SSPR 在 DPdata 和 BCdata 上表现最佳。然而，由于选择的参数，它在 BRdata 上似乎是最差的，因为在大多数情况下，SSPR 的运行时间过长。这很明显，因为 SSPR 在大多数实例的第一次迭代中就达到了最佳解决方案，且时间可以忽略不计。在 Hmida 等人 (2010) 中，作者没有提供 HHS/LNS 在这些实例上的运行时间，因为他们出于类似的原因认为这些时间不相关。

For HUdata set, we only report summary results of RPD (detailed results from SSPR on all benchmarks considered here are openly available on the web⁴). Table 8 reports results reached by TS, hGA, CDDS, HHS/LNS and SSPR. We give the average value of the RPD of the best makespan and average makespan across each of the three subsets of 43 instances: edata, rdata and vdata. It is remarkable that the RPD values of the best and average solutions obtained by SSPR are better than those obtained by all other algorithms.
对于 HUdata 集，我们仅报告 RPD 的摘要结果（此处考虑的所有基准的 SSPR 详细结果公开发布在网络上 ⁴ ）。表 8 报告了 TS、hGA、CDDS、HHS/LNS 和 SSPR 达到的结果。我们给出了最佳完工时间和平均完工时间在每个 43 个实例的三个子集（edata、rdata 和 vdata）中的平均 RPD 值。值得注意的是，SSPR 获得的最佳和平均解决方案的 RPD 值优于所有其他算法。

Table 8. Summary of results (in RPD): HUdata.
表 8. HUdata 结果摘要（以 RPD 为单位）。

Set 集	flex. 灵活性	TS	hGA	CDDS	HHS/LNS	SSPR
edata	1.15	2.17 (2.18)	2.13 (2.40)	2.32 (2.78)	2.11 (–) 2.11（–）	2.03 (2.10)
rdata	2	1.24 (1.36)	1.19 (1.21)	1.34 (1.54)	1.18 (–) 1.18（–）	1.03 (1.12)
vdata	2.5 to 7.5 2.5 到 7.5	0.10 (0.13)	0.08 (0.09)	0.12 (0.16)	0.11 (–) 0.11（–）	0.04 (0.05)

– means that the corresponding data is not available.
– 表示相应数据不可用。

Overall, for all 129 instances in HUdata, SSPR reaches a solution equal to or better than the solution given by TS in Mastrolilli and Gambardella (2000). Being the makespan of these solutions equal to the lower bound in 82 instances and lower than the upper bounds reported in Mastrolilli and Gambardella (2000) for 41 instances.
总体而言，对于 HUdata 中所有 129 个实例，SSPR 达到了与 Mastrolilli 和 Gambardella (2000) 中 TS 给出的解一样好或更好。由于这些解的制造时间等于 82 个实例的下界，并且小于 Mastrolilli 和 Gambardella (2000) 中报告的上界，对于 41 个实例。

Results from other methods are not included in Table 8 for different reasons. No results were given for GA + TS and MGARH in González et al. (2013) and Gutierrez and Garcia-Magario (2011) respectively. In Bozejko et al. (2010) the authors only report results for instances la01 to la15 of the rdata set, and in all cases these results are equal or worse than those obtained by TS.
来自其他方法的结果由于各种原因未包含在表 8 中。在 González 等人 (2013) 和 Gutierrez 和 Garcia-Magario (2011) 中，分别未给出 GA + TS 和 MGARH 的结果。在 Bozejko 等人 (2010) 中，作者仅报告了 rdata 集中 la01 到 la15 实例的结果，并且在所有情况下，这些结果都等于或比 TS 获得的结果差。

Summarizing, we have considered 178 instances of the FJSP and in 175 of them we have reached the best known solution. Moreover, we have found new upper bounds for 13 instances of DPdata, 4 instances of BCdata and 41 instances of HUdata.⁵
总结一下，我们考虑了 FJSP 的 178 个实例，其中 175 个实例达到了最佳已知解决方案。此外，我们还为 DPdata 的 13 个实例、BCdata 的 4 个实例和 HUdata 的 41 个实例找到了新的上限。 ⁵

To further avail the quality of the proposed method, we have done some statistical tests to analyze differences between SSPR and other algorithms. As we have multiple-problem analysis, we used non-parametric statistical tests. First, we run a Shapiro–Wilk test to confirm the non-normality of the data. Then we used paired Wilcoxon signed rank tests to compare the medians of the RPD values between SSPR and each one of the other methods, provided that results for single instances are available, that is, we have considered the set BRdata ∪ BCdata ∪ DPdata and the methods TS, hGA, CDDS and GA + TS. In these tests, the level of confidence used was 95 percent and the alternative hypothesis was “the difference between the errors of SSPR and the method tested is smaller than 0.” The p-values obtained with these tests (TS: 4.027e − 08, hGA: 2.133e − 05, CDDS: 1.404e − 06, GA + TS: 7.364e − 04) show that there exist statistically significant differences between SSPR and the other tested methods in these benchmarks. In summary, we can conclude that SSPR is significantly better than some methods of the state of the art.
为了进一步评估所提出方法的质量，我们进行了统计检验，以分析 SSPR 与其他算法之间的差异。由于我们有多个问题的分析，我们使用了非参数统计检验。首先，我们运行了 Shapiro–Wilk 检验以确认数据的非正态性。然后，我们使用成对的 Wilcoxon 符号秩检验来比较 SSPR 与其他每种方法之间 RPD 值的中位数，前提是单个实例的结果可用，也就是说，我们考虑了 BRdata ∪ BCdata ∪ DPdata 集以及 TS、hGA、CDDS 和 GA + TS 方法。在这些检验中，使用的置信度水平为 95%，备择假设为“SSPR 与被测试方法的误差之差小于 0”。通过这些检验获得的 p 值 (TS: 4.027e − 08, hGA: 2.133e − 05, CDDS: 1.404e − 06, GA + TS: 7.364e − 04) 表明，在这些基准测试中，SSPR 与其他测试方法之间存在统计学上的显著差异。总之，我们可以得出结论，SSPR 比一些现有最先进的方法更好。

6. Conclusions 6. 结论

We devised a new algorithm for the flexible job shop scheduling problem with makespan minimization. The algorithm, termed SSPR, combines scatter search and path relinking with tabu search. From a thorough analysis of the problem and the schedules, we have obtained useful insights that allowed us to define some new neighborhood structures and methods to accurately estimate the makespan of the neighbors. Also, we have defined a novel fine grain dissimilarity measure for schedules. All these elements were incorporated in different components of the SSPR algorithm, which was evaluated and compared with the state of the art on the most commonly used benchmarks, showing clear improvements over existing methods in the literature considering the time taken and the makespan of the schedules together. In particular, SSPR was able to improve the best known solution in 58 of the 178 FJSP instances considered.
我们设计了一种新的柔性作业车间调度问题（FJSP）求解算法，目标是最小化制造时间。该算法，名为 SSPR，结合了散布搜索、路径重连和禁忌搜索。通过对问题和排程的深入分析，我们获得了有益的见解，从而定义了一些新的邻域结构和方法来准确估计邻居的制造时间。此外，我们还定义了一种新颖的细粒度排程相似度度量。所有这些元素都被整合到 SSPR 算法的不同组件中，并在最常用的基准测试集上评估并与现有最先进方法进行了比较，在考虑时间和排程的制造时间时，显示出明显优于现有方法的改进。特别是，SSPR 能够改进 178 个 FJSP 实例中 58 个的最佳已知解。

We believe that the main reasons for the good performance of SSPR are the combination of the diversification provided by the scatter search and path relinking shell combined with the intensification provided by the tabu search, together with the fact that the neighborhoods are specifically tailored to deal with flexibility. Also, the proposed dissimilarity measure is another strong point of SSPR as it allows PR to search over paths of diverse and potentially good candidate solutions of the search space.
我们认为 SSPR 表现良好的主要原因是，散射搜索和路径重链方法结合了多样化，禁忌搜索提供了强化，并且邻域专门针对柔性进行了调整。此外，所提出的不相容性度量是 SSPR 的另一个强项，因为它允许 PR 在搜索空间中搜索由各种且可能较好的候选解组成的路径。

Acknowledgments 致谢

All authors are supported by the Spanish Government under projects MEC-FEDER TIN2010-20976-C02-02 and TIN2013-46511-C2-2-P and by the Principality of Asturias under project FICYT-COF13-035.
所有作者都由西班牙政府（项目 MEC-FEDER TIN2010-20976-C02-02 和 TIN2013-46511-C2-2-P）和阿斯图里亚斯亲王领地（项目 FICYT-COF13-035）资助。

References

Amico, Trubian, 1993
Amico M.D., Trubian M.
Applying tabu search to the job-shop scheduling problem
Annals of Operational Research, 41 (1993), pp. 231-252
Google Scholar
Barnes, Chambers, 1996
Barnes J., Chambers J.
Flexible job shop scheduling by tabu search
Technical Report Series: ORP96-09. Graduate program in operations research and industrial engineering, The University of Texas at Austin (1996)
Google Scholar
Bozejko, Uchronski, Wodecki, 2010
Bozejko W., Uchronski M., Wodecki M.
Parallel hybrid metaheuristics for the flexible job shop problem
Computers & Industrial Engineering, 59 (2) (2010), pp. 323-333
View PDF View article View in Scopus Google Scholar
Brandimarte, 1993
Brandimarte P.
Routing and scheduling in a flexible job shop by tabu search
Annals of Operations Research, 41 (1993), pp. 157-183
View in Scopus Google Scholar
Brucker, Schlie, 1990
Brucker P., Schlie R.
Job-shop scheduling with multi-purpose machines
Computing, 45 (4) (1990), pp. 369-375
View in Scopus Google Scholar
Dauzère-Pérès, Paulli, 1997
Dauzère-Pérès S., Paulli J.
An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search
Annals of Operations Research, 70 (3) (1997), pp. 281-306
View in Scopus Google Scholar
Dongarra, 2013
Dongarra J.
Performance of various computers using standard linear equations software
(Tech. rep.), Computer Science Department, University of Tennessee, Knoxville, Tennessee (2013)
Google Scholar
Gao, Sun, Gen, 2008
Gao J., Sun L., Gen M.
A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems
Computers & Operations Research, 35 (2008), pp. 2892-2907
View PDF View article View in Scopus Google Scholar
Garey, Johnson, Sethi, 1976
Garey M., Johnson D., Sethi R.
The complexity of flowshop and jobshop scheduling
Mathematics of Operations Research, 1 (2) (1976), pp. 117-129
Crossref View in Scopus Google Scholar
Glover, 1998
Glover F.
A template for scatter search and path relinking
J. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers (Eds.), Artificial evolution, LNCS 1363, Springer (1998), pp. 13-54
View in Scopus Google Scholar
Glover, Laguna, Martí, 2003
Glover F., Laguna M., Martí R.
Advances in evolutionary computation: Theory and applications, Springer (2003), pp. 519-537
Crossref Google Scholar
González, Vela, González-Rodríguez, Varela, 2013
González M.A., Vela C., González-Rodríguez I., Varela R.
Lateness minimization with tabu search for job shop scheduling problem with sequence dependent setup times
Journal of Intelligent Manufacturing, 24 (4) (2013), pp. 741-754
Crossref View in Scopus Google Scholar
González, Vela, Varela, 2013
González M., Vela C.R., Varela R.
An efficient memetic algorithm for the flexible job shop with setup times
Proceedings of ICAPS-2013 (2013), pp. 91-99
Crossref View in Scopus Google Scholar
González, Vela, Varela, González-Rodríguez, 2015
González M.A., Vela C., Varela R., González-Rodríguez I.
An advanced scatter search algorithm for solving job shops with sequence dependent and non-anticipatory setups
AI Communications, 28 (2015), pp. 179-193
Crossref View in Scopus Google Scholar
Goshtasby, 2012
Goshtasby A.A.
Advances in computer vision and pattern recognition, Springer-Verlag (2012)
Google Scholar
Gutierrez, Garcia-Magario, 2011
Gutierrez C., Garcia-Magario I.
Modular design of a hybrid genetic algorithm for a flexible job-shop scheduling problem
Knowledge-Based Systems, 24 (2011), pp. 102-112
View PDF View article View in Scopus Google Scholar
Hmida, Haouari, Huguet, Lopez, 2010
Hmida A., Haouari M., Huguet M., Lopez P.
Discrepancy search for the flexible job shop scheduling problem
Computers & Operations Research, 37 (2010), pp. 2192-2201
Google Scholar
Ho, Tay, Lai, 2007
Ho N.B., Tay J.C., Lai E.M.-K.
An effective architecture for learning and evolving flexible job-shop schedules
European Journal of Operational Research, 179 (2007), pp. 316-333
View PDF View article View in Scopus Google Scholar
Hurink, Jurisch, Thole, 1994
Hurink E., Jurisch B., Thole M.
Tabu search for the job shop scheduling problem with multi-purpose machine
Operations Research Spektrum, 15 (1994), pp. 205-215
View in Scopus Google Scholar
Jia, Hu, 2014
Jia S., Hu Z.-H.
Path-relinking tabu search for the multi-objective flexible job shop scheduling problem
Computers & Operations Research, 47 (2014), pp. 11-26
View PDF View article View in Scopus Google Scholar
Martí, Laguna, Glover, 2006
Martí R., Laguna M., Glover F.
Principles of scatter search
European Journal of Operational Research, 169 (2006), pp. 359-372
View PDF View article View in Scopus Google Scholar
Mastrolilli, Gambardella, 2000
Mastrolilli M., Gambardella L.
Effective neighborhood functions for the flexible job shop problem
Journal of Scheduling, 3 (1) (2000), pp. 3-20
View in Scopus Google Scholar
Mati, Dauzere-Peres, Lahlou, 2011
Mati Y., Dauzere-Peres S., Lahlou C.
A general approach for optimizing regular criteria in the job-shop scheduling problem
European Journal of Operational Research, 212 (2011), pp. 33-42
View PDF View article View in Scopus Google Scholar
Mattfeld, 1995
Mattfeld D.C.
Evolutionary search and the job shop investigations on genetic algorithms for production scheduling, Springer-Verlag (1995)
Google Scholar
Meeran, Morshed, 2014
Meeran S., Morshed M.
Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems
International Journal of Production Research, 52 (9) (2014)
5780-5798
Google Scholar
Nasiri, Kianfar, 2012
Nasiri M., Kianfar F.
A guided tabu search/path relinking algorithm for the job shop problem
International Journal on Advanced Manufacturing Technologies, 58 (2012), pp. 1105-1113
Crossref View in Scopus Google Scholar
Nowicki, Smutnicki, 1996
Nowicki E., Smutnicki C.
A fast taboo search algorithm for the job shop scheduling problem
Management Science, 42 (1996), pp. 797-813
Crossref View in Scopus Google Scholar
Nowicki, Smutnicki, 2005
Nowicki E., Smutnicki C.
An advanced tabu search algorithm for the job shop problem
Journal of Scheduling, 8 (2) (2005), pp. 145-159
Crossref View in Scopus Google Scholar
Nowicki, Smutnicki, 2006
Nowicki E., Smutnicki C.
Some aspects of scatter search in the flow-shop problem
European Journal of Operational Research, 169 (2006), pp. 654-666
View PDF View article View in Scopus Google Scholar
Sels, Craeymeersch, Vanhoucke, 2011
Sels V., Craeymeersch K., Vanhoucke M.
A hybrid single and dual population search procedure for the job shop scheduling problem
European Journal of Operational Research, 215 (2011), pp. 512-523
View PDF View article View in Scopus Google Scholar
Van Laarhoven, Aarts, Lenstra, 1992
Van Laarhoven P., Aarts E., Lenstra K.
Job shop scheduling by simulated annealing
Operations Research, 40 (1992), pp. 113-125
Crossref View in Scopus Google Scholar
Webb, 2002
Webb A.R.
Statistical pattern recognition (2nd), John Wiley & Sons (2002)
Google Scholar
Yamada, Nakano, 1996
Yamada T., Nakano R.
Scheduling by genetic local search with multi-step crossover
Proceedings of fourth international conference on parallel problem solving from nature (PPSN IV) (1996), pp. 960-969
Google Scholar
Yuan, Xu, 2013
Yuan Y., Xu H.
An integrated search heuristic for large-scale flexible jobshop scheduling problems
Computers & Operations Research, 40 (2013), pp. 2864-2877
View PDF View article View in Scopus Google Scholar

Cited by (77)

A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem
灵活车间调度问题的多动作深度强化学习框架
2022, Expert Systems with Applications
2022 年，专家系统与应用
This paper presents an end-to-end deep reinforcement framework to automatically learn a policy for solving a flexible Job-shop scheduling problem (FJSP) using a graph neural network. In the FJSP environment, the reinforcement agent needs to schedule an operation belonging to a job on an eligible machine among a set of compatible machines at each timestep. This means that an agent needs to control multiple actions simultaneously. Such a problem with multi-actions is formulated as a multiple Markov decision process (MMDP). For solving the MMDPs, we propose a multi-pointer graph networks (MPGN) architecture and a training algorithm called multi-Proximal Policy Optimization (multi-PPO) to learn two sub-policies, including a job operation action policy and a machine action policy to assign a job operation to a machine. The MPGN architecture consists of two encoder-decoder components, which define the job operation action policy and the machine action policy for predicting probability distributions over different operations and machines, respectively. We introduce a disjunctive graph representation of FJSP and use a graph neural network to embed the local state encountered during scheduling. The computational experiment results show that the agent can learn a high-quality dispatching policy and outperforms handcrafted heuristic dispatching rules in solution quality and meta-heuristic algorithm in running time. Moreover, the results achieved on random and benchmark instances demonstrate that the learned policies have a good generalization performance on real-world instances and significantly larger scale instances with up to 2000 operations.
Greedy randomized adaptive search for dynamic flexible job-shop scheduling
用于动态柔性车间调度问题的贪婪随机自适应搜索
2020, Journal of Manufacturing Systems
2020 年，制造系统杂志
Citation Excerpt : 引用摘录：
The results indicate that the proposed GRASP algorithm can obtain the best results for 7 out of 10 instances and shows a better performance than PVNS, CDDS and PSO. Table 9 displays the results of the GRASP with hGA of [17], eGA of [14], CDDS of [63], SSPR of [64] and QPSO of [25] for Dauzere-Peres and Paulli’s data set. The proposed GRASP algorithm is able to provide the best results for 4 instances out of 18 instances.
结果表明，所提出的 GRASP 算法能够在 10 个实例中的 7 个实例中获得最佳结果，并且其性能优于 PVNS、CDDS 和 PSO。表 9 显示了 GRASP 算法与 [17] 的 hGA、[14] 的 eGA、[63] 的 CDDS、[64] 的 SSPR 和 [25] 的 QPSO 算法在 Dauzere-Peres 和 Paulli 数据集上的结果。所提出的 GRASP 算法能够在 18 个实例中提供 4 个实例的最佳结果。
Dynamic flexible job shop scheduling problem is studied under the events such as new order arrivals, changes in due dates, machine breakdowns, order cancellations, and appearance of urgent orders. This paper presents a constructive algorithm which can solve FJSP and DFJSP with machine capacity constraints and sequence-dependent setup times, and employs greedy randomized adaptive search procedure (GRASP). Besides, Order Review Release (ORR) mechanism and order acceptance/rejection decisions are also incorporated into the proposed method in order to adjust capacity execution considering customer due date requirements. The lexicographic method is utilized to assess the objectives: schedule instability, makespan, mean tardiness and mean flow time. A group of experiments is also carried out in order to verify the suitability of the GRASP in solving the flexible job shop scheduling problem. Benchmark problems are formed for different problem scales with dynamic events. The event-driven rescheduling strategy is also compared with periodical rescheduling strategy. Results of the extensive computational experiment presents that proposed approach is very effective and can provide reasonable schedules under event-driven and periodic scheduling scenarios.
Solving the flexible job shop scheduling problem using an improved Jaya algorithm
使用改进的 Jaya 算法求解柔性车间调度问题
2019, Computers and Industrial Engineering
2019 年，计算机与工业工程
The classical job shop scheduling problem (JSSP) has been a subject of extensive research for the past many years. Due to its high computational complexity, it is considered to be NP-hard (Non-deterministic polynomial time) in nature. The flexible job shop scheduling problem (FJSSP) which is a classification of basic JSSP further increases the complexity of the problem by considering a job to be processed on more than one machine. Hence a routing problem along with the sequencing problem needs to be considered. Considering the NP-hard nature of the problem the research has sailed through the extensive use of meta-heuristics to find near-optimal solutions. However, these meta-heuristics tend to get trapped in the local optimum and also contain algorithm-specific tuning parameters which need to be tuned to obtain an optimal solution. To overcome this, an improved Jaya algorithm is proposed in this work. To improve the solution quality and maintain diversity, an efficient initialization mechanism, a local search technique and acceptance criterion is incorporated into the algorithm. The performance of the improved Jaya algorithm is compared using makespan criteria with other well-known meta-heuristics on 203 benchmark instances. Results demonstrate the effectiveness of the proposed algorithm in solving the FJSSP.
Backtracking search based hyper-heuristic for the flexible job-shop scheduling problem with fuzzy processing time
基于回溯搜索的超启发式算法，用于具有模糊加工时间的柔性作业车间调度问题
2019, Engineering Applications of Artificial Intelligence
2019 年，人工智能工程应用
Citation Excerpt : 引用摘录：
Especially, with the development of optimization methodologies and intelligent techniques, meta-heuristics have been widely applied to solve the FJSP. Typically, genetic algorithms (GAs) in Chen et al. (1999), Gholami and Zandieh (2009), Gutierrez and Garcia-Magarino (2011) and Pezzella et al. (2008), a differential evolution in Yuan and Xu (2013), an ant colony optimization in Rossi (2014), a scatter search in González et al. (2015) and a particle swarm optimization in Singh and Mahapatra (2016). The above studies make a common assumption that the processing time for each operation on each machine is generally deterministic.
特别是，随着优化方法和智能技术的进步，元启发式算法已广泛应用于解决柔性作业车间调度问题。例如，陈等 (1999)、Gholami 和 Zandieh (2009)、Gutierrez 和 Garcia-Magarino (2011) 和 Pezzella 等 (2008) 中的遗传算法 (GA)，Yuan 和 Xu (2013) 中的差分进化，Rossi (2014) 中的蚁群优化，González 等 (2015) 中的散布搜索以及 Singh 和 Mahapatra (2016) 中的粒子群优化。以上研究都假设每台机器上每个工序的加工时间通常是确定性的。
Flexible job-shop scheduling problem (FJSP) is among the most investigated scheduling problems over the past decades. The uncertainty of the processing time is an important practical characteristic in manufacturing. By considering the processing time to be fuzzy variable, the FJSP with fuzzy processing time (FJSPF) is more close to the reality. This paper proposes an effective backtracking search based hyper-heuristic (BS-HH) approach to address the FJSPF. Firstly, six simple and efficient heuristics are incorporated into the BS-HH to construct a set of low-level heuristics. Secondly, a backtracking search algorithm is introduced as the high-level strategy to manage the low-level heuristics to operate on the solution domain. Additionally, a novel hybrid solution decoding scheme is proposed to find an optimal solution more efficiently. Finally, the performance of the BS-HH is evaluated on two typical benchmark sets. The results show that the proposed hyper-heuristic outperforms the state-of-the-art algorithms in solving the FJSPF.
Lexicographic Multiobjective Scatter Search for the Optimization of Sequence-Dependent Selective Disassembly Subject to Multiresource Constraints
基于词典多目标散点搜索算法优化受多资源约束的顺序依赖选择性拆卸问题
2020, IEEE Transactions on Cybernetics
2020 年，IEEE 控制论会刊
Scheduling Cluster Tools in Semiconductor Manufacturing: Recent Advances and Challenges
半导体制造中集群工具的调度：最新进展和挑战
2018, IEEE Transactions on Automation Science and Engineering
2018 年，IEEE 自动化科学与工程学报

View all citing articles on Scopus
在 Scopus 上查看所有引用文章

¹: In the worst case all 100 tasks are performed on the same machine, so considering that all pairs of tasks belonging to different jobs may be processed in different order in the two schedules, the maximum dissimilarity is calculated as (100 × 99)/2 − 10 × (10 × 9)/2 = 4500.
在最坏情况下，所有 100 个任务都在同一台机器上执行，因此考虑到属于不同作业的所有任务对可能以不同的顺序在两个计划中处理，最大差异计算为 (100 × 99)/2 − 10 × (10 × 9)/2 = 4500。

²: The distance of a solution S to a set of solutions is given by the minimum distance from S to a solution of the set.
解 S 到一组解的距离由 S 到该组解的最小距离给出。

³: Notice that $N_{2}^{α π} (S)$ contains at least one solution closer to S_end than S. This guarantees that Algorithm 2 finishes in a finite number of iterations.
请注意， $N_{2}^{α π} (S)$ 包含至少一个比 S _end 更接近 S 的解。这保证了算法 2 在有限的迭代次数内完成。

⁴: Repository section in http://www.di.uniovi.es/iscop.
http://www.di.uniovi.es/iscop 的存储库部分。

⁵: Remember that the upper bounds we considered for HUdata are those from TS reported in Mastrolilli and Gambardella (2000) as, to our knowledge, detailed results from other methods on this benchmark set have not yet been published. So, we do not know whether or not a better upper bound was reached by other method for some of these instances.
请记住，我们考虑的 HUdata 的上限是 Mastrolilli 和 Gambardella (2000) 中报告的 TS 的上限，因为据我们所知，该基准集上其他方法的详细结果尚未发布。因此，我们不知道对于某些实例，其他方法是否达到了更好的上限。

View Abstract 查看摘要

[1] Amico, Trubian, 1993
Amico M.D., Trubian M.
Applying tabu search to the job-shop scheduling problem
Annals of Operational Research, 41 (1993), pp. 231-252
Google Scholar

[2] Barnes, Chambers, 1996
Barnes J., Chambers J.
Flexible job shop scheduling by tabu search
Technical Report Series: ORP96-09. Graduate program in operations research and industrial engineering, The University of Texas at Austin (1996)
Google Scholar

[3] Bozejko, Uchronski, Wodecki, 2010
Bozejko W., Uchronski M., Wodecki M.
Parallel hybrid metaheuristics for the flexible job shop problem
Computers & Industrial Engineering, 59 (2) (2010), pp. 323-333
View PDF View article View in Scopus Google Scholar

[4] Brandimarte, 1993
Brandimarte P.
Routing and scheduling in a flexible job shop by tabu search
Annals of Operations Research, 41 (1993), pp. 157-183
View in Scopus Google Scholar

[5] Brucker, Schlie, 1990
Brucker P., Schlie R.
Job-shop scheduling with multi-purpose machines
Computing, 45 (4) (1990), pp. 369-375
View in Scopus Google Scholar

[6] Dauzère-Pérès, Paulli, 1997
Dauzère-Pérès S., Paulli J.
An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search
Annals of Operations Research, 70 (3) (1997), pp. 281-306
View in Scopus Google Scholar

[7] Dongarra, 2013
Dongarra J.
Performance of various computers using standard linear equations software
(Tech. rep.), Computer Science Department, University of Tennessee, Knoxville, Tennessee (2013)
Google Scholar

[8] Gao, Sun, Gen, 2008
Gao J., Sun L., Gen M.
A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems
Computers & Operations Research, 35 (2008), pp. 2892-2907
View PDF View article View in Scopus Google Scholar

[9] Garey, Johnson, Sethi, 1976
Garey M., Johnson D., Sethi R.
The complexity of flowshop and jobshop scheduling
Mathematics of Operations Research, 1 (2) (1976), pp. 117-129
Crossref View in Scopus Google Scholar

[10] Glover, 1998
Glover F.
A template for scatter search and path relinking
J. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers (Eds.), Artificial evolution, LNCS 1363, Springer (1998), pp. 13-54
View in Scopus Google Scholar

[11] Glover, Laguna, Martí, 2003
Glover F., Laguna M., Martí R.
Advances in evolutionary computation: Theory and applications, Springer (2003), pp. 519-537
Crossref Google Scholar

[12] González, Vela, González-Rodríguez, Varela, 2013
González M.A., Vela C., González-Rodríguez I., Varela R.
Lateness minimization with tabu search for job shop scheduling problem with sequence dependent setup times
Journal of Intelligent Manufacturing, 24 (4) (2013), pp. 741-754
Crossref View in Scopus Google Scholar

[13] González, Vela, Varela, 2013
González M., Vela C.R., Varela R.
An efficient memetic algorithm for the flexible job shop with setup times
Proceedings of ICAPS-2013 (2013), pp. 91-99
Crossref View in Scopus Google Scholar

[14] González, Vela, Varela, González-Rodríguez, 2015
González M.A., Vela C., Varela R., González-Rodríguez I.
An advanced scatter search algorithm for solving job shops with sequence dependent and non-anticipatory setups
AI Communications, 28 (2015), pp. 179-193
Crossref View in Scopus Google Scholar

[15] Goshtasby, 2012
Goshtasby A.A.
Advances in computer vision and pattern recognition, Springer-Verlag (2012)
Google Scholar

[16] Gutierrez, Garcia-Magario, 2011
Gutierrez C., Garcia-Magario I.
Modular design of a hybrid genetic algorithm for a flexible job-shop scheduling problem
Knowledge-Based Systems, 24 (2011), pp. 102-112
View PDF View article View in Scopus Google Scholar

[17] Hmida, Haouari, Huguet, Lopez, 2010
Hmida A., Haouari M., Huguet M., Lopez P.
Discrepancy search for the flexible job shop scheduling problem
Computers & Operations Research, 37 (2010), pp. 2192-2201
Google Scholar

[18] Ho, Tay, Lai, 2007
Ho N.B., Tay J.C., Lai E.M.-K.
An effective architecture for learning and evolving flexible job-shop schedules
European Journal of Operational Research, 179 (2007), pp. 316-333
View PDF View article View in Scopus Google Scholar

[19] Hurink, Jurisch, Thole, 1994
Hurink E., Jurisch B., Thole M.
Tabu search for the job shop scheduling problem with multi-purpose machine
Operations Research Spektrum, 15 (1994), pp. 205-215
View in Scopus Google Scholar

[20] Jia, Hu, 2014
Jia S., Hu Z.-H.
Path-relinking tabu search for the multi-objective flexible job shop scheduling problem
Computers & Operations Research, 47 (2014), pp. 11-26
View PDF View article View in Scopus Google Scholar

[21] Martí, Laguna, Glover, 2006
Martí R., Laguna M., Glover F.
Principles of scatter search
European Journal of Operational Research, 169 (2006), pp. 359-372
View PDF View article View in Scopus Google Scholar

[22] Mastrolilli, Gambardella, 2000
Mastrolilli M., Gambardella L.
Effective neighborhood functions for the flexible job shop problem
Journal of Scheduling, 3 (1) (2000), pp. 3-20
View in Scopus Google Scholar

[23] Mati, Dauzere-Peres, Lahlou, 2011
Mati Y., Dauzere-Peres S., Lahlou C.
A general approach for optimizing regular criteria in the job-shop scheduling problem
European Journal of Operational Research, 212 (2011), pp. 33-42
View PDF View article View in Scopus Google Scholar

[24] Mattfeld, 1995
Mattfeld D.C.
Evolutionary search and the job shop investigations on genetic algorithms for production scheduling, Springer-Verlag (1995)
Google Scholar

[25] Meeran, Morshed, 2014
Meeran S., Morshed M.
Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems
International Journal of Production Research, 52 (9) (2014)
5780-5798
Google Scholar

[26] Nasiri, Kianfar, 2012
Nasiri M., Kianfar F.
A guided tabu search/path relinking algorithm for the job shop problem
International Journal on Advanced Manufacturing Technologies, 58 (2012), pp. 1105-1113
Crossref View in Scopus Google Scholar

[27] Nowicki, Smutnicki, 1996
Nowicki E., Smutnicki C.
A fast taboo search algorithm for the job shop scheduling problem
Management Science, 42 (1996), pp. 797-813
Crossref View in Scopus Google Scholar

[28] Nowicki, Smutnicki, 2005
Nowicki E., Smutnicki C.
An advanced tabu search algorithm for the job shop problem
Journal of Scheduling, 8 (2) (2005), pp. 145-159
Crossref View in Scopus Google Scholar

[29] Nowicki, Smutnicki, 2006
Nowicki E., Smutnicki C.
Some aspects of scatter search in the flow-shop problem
European Journal of Operational Research, 169 (2006), pp. 654-666
View PDF View article View in Scopus Google Scholar

[30] Sels, Craeymeersch, Vanhoucke, 2011
Sels V., Craeymeersch K., Vanhoucke M.
A hybrid single and dual population search procedure for the job shop scheduling problem
European Journal of Operational Research, 215 (2011), pp. 512-523
View PDF View article View in Scopus Google Scholar

[31] Van Laarhoven, Aarts, Lenstra, 1992
Van Laarhoven P., Aarts E., Lenstra K.
Job shop scheduling by simulated annealing
Operations Research, 40 (1992), pp. 113-125
Crossref View in Scopus Google Scholar

[32] Webb, 2002
Webb A.R.
Statistical pattern recognition (2nd), John Wiley & Sons (2002)
Google Scholar

[33] Yamada, Nakano, 1996
Yamada T., Nakano R.
Scheduling by genetic local search with multi-step crossover
Proceedings of fourth international conference on parallel problem solving from nature (PPSN IV) (1996), pp. 960-969
Google Scholar

[34] Yuan, Xu, 2013
Yuan Y., Xu H.
An integrated search heuristic for large-scale flexible jobshop scheduling problems
Computers & Operations Research, 40 (2013), pp. 2864-2877
View PDF View article View in Scopus Google Scholar

Outline 大纲

Cited by (77) 被引用次数 (77)

Figures (7) 图表 (7)

Tables (8) 表格 (8)

European Journal of Operational Research
欧盟运营研究杂志

Highlights 亮点

Abstract 摘要

Keywords 关键词

1. Introduction 1. 引言

2. Problem formulation 2. 问题描述

2.1. Solution graph and criticality
2.1. 解图和关键性

3. Neighborhood structures
3. 邻域结构

3.1. Structures for the sequencing subproblem
3.1. 排序子问题的结构

3.2. Structures for the assignment subproblem
3.2. 任务分配子问题的结构

3.3. Combining sequencing and assignment structures
3.3. 组合排序和分配结构

3.4. Makespan estimate 3.4. 制造时间估计

4. Scatter search for the FJSP
4. 灵活作业车间调度问题的散点搜索

4.1. Dissimilarity measure
4.1. 相异性度量

4.2. Initial reference set construction
4.2. 初始参考集构建

4.3. Subset generation method and diversification phase
4.3. 子集生成方法和多样化阶段

4.4. Solution-combination method
4.4. 解组合方法

4.5. Improvement method 4.5. 改进方法

4.6. Reference set update
4.6. 参考集更新

4.7. Similarities and differences w.r.t. other proposals
4.7. 与其他建议的异同

5. Experimental study 5. 实验研究

5.1. Parameter tuning 5.1. 参数调整

5.2. Analysis of the neighborhood structures
5.2. 邻域结构分析

5.3. Comparing SSPR with tabu search running alone
5.3. 将 SSPR 与单独运行的禁忌搜索进行比较

5.4. Comparison with the state of the art
5.4. 与现有技术的比较

6. Conclusions 6. 结论

Acknowledgments 致谢

References

Cited by (77)

A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem
灵活车间调度问题的多动作深度强化学习框架

Greedy randomized adaptive search for dynamic flexible job-shop scheduling
用于动态柔性车间调度问题的贪婪随机自适应搜索

Solving the flexible job shop scheduling problem using an improved Jaya algorithm
使用改进的 Jaya 算法求解柔性车间调度问题

Backtracking search based hyper-heuristic for the flexible job-shop scheduling problem with fuzzy processing time
基于回溯搜索的超启发式算法，用于具有模糊加工时间的柔性作业车间调度问题

Lexicographic Multiobjective Scatter Search for the Optimization of Sequence-Dependent Selective Disassembly Subject to Multiresource Constraints
基于词典多目标散点搜索算法优化受多资源约束的顺序依赖选择性拆卸问题

Scheduling Cluster Tools in Semiconductor Manufacturing: Recent Advances and Challenges
半导体制造中集群工具的调度：最新进展和挑战

Discrete Optimization 离散优化Scatter search with path relinking for the flexible job shop scheduling problem具有路径重链的散射搜索方法用于柔性作业车间调度问题

Highlights 亮点

Abstract 摘要

Keywords 关键词

1. Introduction 1. 引言

2. Problem formulation 2. 问题描述

2.1. Solution graph and criticality2.1. 解图和关键性

3. Neighborhood structures3. 邻域结构

3.1. Structures for the sequencing subproblem3.1. 排序子问题的结构

3.2. Structures for the assignment subproblem3.2. 任务分配子问题的结构

3.3. Combining sequencing and assignment structures3.3. 组合排序和分配结构

3.4. Makespan estimate 3.4. 制造时间估计

4. Scatter search for the FJSP4. 灵活作业车间调度问题的散点搜索

4.1. Dissimilarity measure4.1. 相异性度量

4.2. Initial reference set construction4.2. 初始参考集构建

4.3. Subset generation method and diversification phase4.3. 子集生成方法和多样化阶段

4.4. Solution-combination method4.4. 解组合方法

4.5. Improvement method 4.5. 改进方法

4.6. Reference set update4.6. 参考集更新

4.7. Similarities and differences w.r.t. other proposals4.7. 与其他建议的异同

5. Experimental study 5. 实验研究

5.1. Parameter tuning 5.1. 参数调整

5.2. Analysis of the neighborhood structures5.2. 邻域结构分析

5.3. Comparing SSPR with tabu search running alone5.3. 将 SSPR 与单独运行的禁忌搜索进行比较

5.4. Comparison with the state of the art5.4. 与现有技术的比较

6. Conclusions 6. 结论

Acknowledgments 致谢

References

Discrete Optimization 离散优化
Scatter search with path relinking for the flexible job shop scheduling problem
具有路径重链的散射搜索方法用于柔性作业车间调度问题

2.1. Solution graph and criticality
2.1. 解图和关键性

3. Neighborhood structures
3. 邻域结构

3.1. Structures for the sequencing subproblem
3.1. 排序子问题的结构

3.2. Structures for the assignment subproblem
3.2. 任务分配子问题的结构

3.3. Combining sequencing and assignment structures
3.3. 组合排序和分配结构

4. Scatter search for the FJSP
4. 灵活作业车间调度问题的散点搜索

4.1. Dissimilarity measure
4.1. 相异性度量

4.2. Initial reference set construction
4.2. 初始参考集构建

4.3. Subset generation method and diversification phase
4.3. 子集生成方法和多样化阶段

4.4. Solution-combination method
4.4. 解组合方法

4.6. Reference set update
4.6. 参考集更新

4.7. Similarities and differences w.r.t. other proposals
4.7. 与其他建议的异同

5.2. Analysis of the neighborhood structures
5.2. 邻域结构分析

5.3. Comparing SSPR with tabu search running alone
5.3. 将 SSPR 与单独运行的禁忌搜索进行比较

5.4. Comparison with the state of the art
5.4. 与现有技术的比较