禁忌搜索/路径重新链接算法在作业车间调度问题中的应用

需积分: 5 51 浏览量更新于2024-08-13 收藏 515KB PDF 举报

"该资源是一篇研究论文，主要介绍了一种将禁忌搜索（Tabu Search）与路径重新链接（Path Relinking）算法结合的方法，用于解决作业车间调度问题（Job Shop Scheduling Problem, JSP）。论文作者包括Bo Peng、Zhipeng Lü、T.C.E. Cheng等人，发表于2014年8月19日。关键词涵盖了调度、作业车间、元启发式算法、禁忌搜索、路径重新链接以及混合算法。" 正文: 在优化领域，作业车间调度问题（JSP）是一个经典的组合优化问题，涉及到如何有效地安排一系列任务在多个工站之间的顺序和时间，以最小化总完成时间或最大化生产效率。这篇研究论文提出了一种新的算法，即禁忌搜索/路径重新链接（TS/PR）算法，旨在为JSP找到高质量解决方案。禁忌搜索（Tabu Search）是一种常用的全局优化方法，它通过避免近期探索过的解来防止陷入局部最优，从而在搜索空间中进行更广泛的探索。路径重新链接（Path Relinking）则是一种强大的重启动策略，能够快速地从一个解决方案跳转到另一个解决方案，特别是在两种解决方案之间存在显著改进时。 TS/PR算法的独特之处在于它结合了这两种技术的优点。首先，算法中设计了一个特定的重新链接过程，可以有效地构建一条连接初始解决方案和指导解决方案的路径，这有助于跨越局部最优。其次，引入了一个基于两种改进方法的参考解决方案确定机制，以进一步提升算法性能。在评估阶段，TS/PR算法被应用到几乎所有文献中可用的JSP基准实例上。测试结果显示，该算法能够获得与现有方法竞争的解决方案，证明了其在解决JSP问题上的有效性与优越性。这种混合算法的创新应用为解决复杂的调度问题提供了新的思路，并可能对实际工业生产环境中的调度优化带来积极影响。这篇研究论文贡献了禁忌搜索与路径重新链接相结合的新算法，为解决作业车间调度问题提供了一个强大且有潜力的工具。该算法的特性在于其高效的路径构建策略和改进机制，使得在大量可能的解决方案中找到更好的解成为可能。这一工作对于理解和改进元启发式算法在解决实际问题中的应用具有重要意义。

Algorithm 1. Outline of algorithm TS/PR for JSP.

1: Input: J, M, and P

2: Output: C

max

and the best solution S

found so far

P ¼fS

; …; S

g’Population_InitializationðÞ /

Section 2.2

for i ¼f1; …; pg do

’Tabu_SearchðS

Þ /

Section 2.3

6: end for

¼ arg minff ðS

Þji ¼ 1; …; pg

PairSet’fðS

; S

ÞjS

A P; S

A P and S

a S

9: repeat

10: Randomly select one solution pair {S

} from PairSet

11:

p þ 1

’Path_RelinkingðS

; S

Þ,

p þ 2

’Path_RelinkingðS

; S

Þ /

Section 2.4

12:

p þ 1

’Tabu_Search lparS

p þ 1

Þ,

p þ 2

’Tabu_SearchðS

p þ 2

Þ /

Section 2.3

13:

if S

p þ 1

(or S

p þ 2

) is better than S

then

14:

¼ S

p þ 1

(or S

p þ 2

)

15: end if

16:

Tentatively add S

p þ 1

and S

p þ 2

to population P:

¼ P [fS

p þ 1

; S

p þ 2

17:

PairSet’PairSet [fðS

p þ 1

; S

ÞjS

A P and S

a S

p þ 1

18:

PairSet’PairSet [fðS

p þ 2

; S

ÞjS

A P and S

a S

p þ 2

19: Identify the two worst solutions S

and S

in the

temporary population P

20: Generate new population by removing the two worst

solutions S

and S

P ¼fS

; …; S

; S

p þ 1

; S

p þ 2

g\fS

; S

21: Update PairSet:

PairSet’PairSet\fðS

; S

ÞjS

A P and S

a S

PairSet’PairSet\fðS

; S

ÞjS

A P and S

a S

22: until a stop criterion is met

2.2. Initial population

In TS/PR, the initial population is constructed as follows:

Starting from scratch, we randomly generate a feasible solution

and then optimize the solution to become a local optimum using

our improvement method (see Section 2.3). The resulting improved

solution is added to the population if it does not duplicate any

solution currently in the population. This procedure is repeated

until the size of the population reaches the cardinality p.

2.3. Tabu search procedure

Our TS procedure is identical to the one used in the hybrid

evolutionary algorithm (HEA) presented in Cheng et al. [6].

Speciﬁcally, our TS procedure uses the neighborhood proposed

by Zhang et al. [23]. In addition, it stops if the optimal solution is

found or the best objective value has not been improved for a

given number of TS iterations, called the tabu search cutoff. The

interested reader may refer to the HEA presented in Cheng et al.

[6] for more details.

2.4. Path relinking procedure

The relinking procedure is used to generate new solutions by

exploring trajectories (conﬁned to the neighborhood space) that

connect high-quality solutions. The solution that begins the path is

called the initiating solution while the solution that the path leads

to is called the guiding solution. The PathSet is a list of candidate

solutions that stores all the solutions generated during the path

relinking procedure. After the relinking procedure, a so-called

reference solution is chosen from the PathSet that serves to update

the population. In order to better describe the relinking procedure,

we give some deﬁnitions in Table 1.

Contrary to previous studies, our proposed path relinking

process mainly integrates two complementary key components

to ensure search efﬁciency. The ﬁrst component is the construction

approach used for establishing the path between the initiating and

the guiding solutions. In the related literature, Nasiri and Kianfar

[13]'s relinking swaps adjacent operations on a machine, while

GRASP/PR by Aiex et al. [2] swaps different operations on each

machine in turn. However, in this study we swap two different

operations on one machine randomly, where both the operations

and the corresponding machine are randomly chosen. More details

will be presented in Section 2. The second component is the

method used to choose the reference solution. In related studies,

Aiex et al. [2] simply consider the solution with the best makespan

in the path as the reference one, while Nasiri and Kianfar [13]

follow Nowicki and Smutnicki [15]'s i-TSAB whereby it goes from

the initiating solution, then stops at a speciﬁc iteration and returns

the current solution as the reference solution. In contrast, we

devise a dedicated strategy based on the adaptive distance-control

mechanism to obtain the most promising solution. Therefore, the

path relinking approach plays the important role of diversiﬁcation

in coordinating with the efﬁcient TS procedure.

Fig. 2. Illustration of the path solution selection procedure.

Table 2

The settings of some important parameters in TS/PR.

Parameter Value Description

dis

Minimum distance between solutions in PathSet and

and S

max

dis

; 2



Interval for choosing the path solutions

si 500 The number of iterations for the slight tabu search

li 12,500 The number of iterations for the strong tabu search

p 30 Population size

B. Peng et al. / Computers & Operations Research 53 (2015) 154–164156

剩余10页未读，继续阅读

weixin_38745859

粉丝: 4

禁忌搜索/路径重新链接算法在作业车间调度问题中的应用

应用混合蚁群算法求解模糊作业车间调度问题.pdf

用双向收敛蚁群算法解作业车间调度问题1

如何设计一种高效的禁忌搜索/路径重新链接算法用于解决作业车间调度问题？请详细描述算法的关键步骤和参数设置。

针对作业车间调度问题，如何结合禁忌搜索和路径重新链接技术设计高效的混合算法？请详细介绍算法设计的关键步骤、参数配置以及优化策略。

双资源约束作业车间调度算法研究

基于启发式规则和蚁群算法的车间作业调度方法

改进猫群优化算法在柔性作业车间调度中的应用

帝国竞争算法与禁忌搜索在车间调度中的应用

启发式方法解决车间作业调度问题

数学建模 现代算法 人工神经网络 模拟退火 遗传算法 禁忌搜索

最新资源

数学建模现代算法人工神经网络模拟退火遗传算法禁忌搜索