一种禁忌搜索/路径重新链接算法，用于解决作业车间调度问题

研究论文

需积分: 5 16 浏览量 2021-04-27 06:17:33 上传评论收藏 515KB PDF 举报

资源推荐

资源详情

资源评论

A tabu search/path relinking algorithm to solve the job shop

scheduling problem

Bo Peng

, Zhipeng Lü

a,b,

, T.C.E. Cheng

SMART, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, PR China

Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

article info

Available online 19 August 2014

Keywords:

Scheduling

Job shop

Metaheuristics

Tabu search

Path relinking

Hybrid algorithms

abstract

We present an algorithm that incorporates a tabu search procedure into the framework of path relinking

to generate solutions to the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR)

algorithm comprises several distinguishing features, such as a speciﬁc relinking procedure to effectively

construct a path linking the initiating solution and the guiding solution, and a reference solution

determination mechanism based on two kinds of improvement methods. We evaluate the performance

of TS/PR on almost all of the benchmark JSP instances available in the literature. The test results show

that TS/PR obtains competitive results compared with state-of-the-art algorithms for JSP in the

literature, demonstrating its efﬁcacy in terms of both solution quality and computational efﬁciency.

In particular, TS/PR is able to improve the upper bounds for 49 out of the 205 tested instances and it

solves a challenging instance that has remained unsolved for over 20 years.

1. Introduction

The job shop scheduling problem (JSP) is not only one of the

most notorious and intractable NP-hard problems, but also one of

the most important scheduling problems that arise in situations

where a set of activities that follow irregular ﬂow patterns have to

be performed by a set of scarce resources. In job shop scheduling,

we have a set M ¼f1; …; mg of m machines and a set J ¼f1; …; ng of

n jobs. JSP seeks to ﬁnd a feasible schedule for the operations on

the machines that minimizes the makespan (the maximum job

completion time), i.e., C

max

, the completion time of the last

completed operation in the schedule. Each job jA J consists of n

ordered operations O

j;1

; …; O

j;n

, each of which must be processed

on one of the m machines. Let O ¼f0; 1; …; o; oþ1g denote the set

of all the operations to be scheduled, where operations 0 and oþ1

are dummies, have no duration, and represent the initial and ﬁnal

operations, respectively. Each operation kA O is associated with a

ﬁxed processing duration P

. Each machine can process at most

one operation at a time and once an operation begins processing

on a given machine, it must complete processing on that mac-

hine without preemption. In addition, let p

be the predecessor

operation of operation kA O. Note that the ﬁrst operation has

no predecessor. The operations are interrelated by two kinds of

constraints. First, operation kA O can only be scheduled if the

machine on which it is processed is idle. Second, precedence

constraints require that before each operation kA O is processed,

its predecessor operation p

must have been completed.

Furthermore, let S

be the start time of operation o (S

¼ 0). JSP

is to ﬁnd a starting time for each operation oA O. Denoting E

the set of operations being processed on machine hA M, we can

formulate JSP as follows:

Minimize C

max

¼ max

k A O

þP

g; ð1Þ

subject to

Z 0; k ¼ 0; …; o þ1; ð2Þ

S

Z P

; k ¼ 1; …; oþ 1; ð3Þ

S

Z P

or S

S

Z P

; ði; jÞ A E

; hA M: ð4Þ

In the above problem, the objective function (1) is to minimize

the makespan. Constraints (2) require that the completion times of

all the operations are non-negative. Constraints (3) stipulate the

precedence relations among the operations of the same job.

Constraints (4) guarantee that each machine can process no more

than one single operation at a time.

Over the past few decades, JSP has attracted much attention

from a signiﬁcant number of researchers, who have proposed a

large number of heuristic and metaheuristic algorithms to ﬁnd

optimal or near-optimal solutions for the problem. One of the

most famous algorithms is the tabu search (TS) algorithm TSAB

proposed by Nowicki and Smutnicki [14]. Nowicki and Smutnicki

Contents lists available at ScienceDirect

journal homepage: www.elsevier.com/locate/caor

Computers & Operations Research

http://dx.doi.org/10.1016/j.cor.2014.08.006

Corresponding author at: SMART, School of Computer Science and Technology,

Huazhong University of Science and Technology, Wuhan 430074, PR China.

E-mail addresses: zhipeng.lui@gmail.com (Z. Lü),

Edwin.Cheng@polyu.edu.hk (T.C.E. Cheng).

Computers & Operations Research 53 (2015) 154–164

[15] later extend algorithm TSAB to algorithm i-TSAB, which Beck

et al. [5] combine with a constraint programming based construc-

tive search procedure to create algorithm CP/LS. Pardalos and

Shylo [16] propose algorithm GES, which is based on global

equilibrium search techniques. Zhang et al. [23] extend the N6

neighborhood proposed by Balas and Vazacopoulos [4] to a new

neighborhood and Zhang et al. [24] combine TS with SA to create

algorithm TS/SA, which outperforms almost all the algorithms.

Nagata and Tojo [11] present a local search framework termed

guided ejection search, which always searches for an incomplete

solution for JSP. Recently, Gonćalves and Resende [9] present the

biased random-key genetic algorithm BRKGA, which is able to

improve the best known results for 57 instances and outperforms

all the reference algorithms considered in their paper. From all

these algorithms, it is apparent that the recent state-of-the-art

algorithms either hybridize several strategies instead of using a

single algorithm or employ a population-based algorithm instead

of a single-solution based one.

Among the metaheuristic approaches used to generate solu-

tions to JSP, a powerful local search procedure is always necessary.

This observation is especially noticeable for the state-of-the-art

algorithms for JSP. As one of the most popular local search

algorithms, TS has been widely used by researchers to generate

solutions to JSP, e.g., Nowicki and Smutnicki [15], Zhang et al. [23] ,

Nasiri and Kianfar [12], Shen and Buscher [19], and Gonçalves and

Resende [9].

On the other hand, Aiex et al. [2] apply path relinking within a

GRASP procedure as an intensiﬁcation strategy to generate solu-

tions to JSP. Furthermore, Nowicki and Smutnicki [15] improve

their famous algorithm TSAB by introducing a new initial solution

(NIS) generator based on path relinking. Recently, Nasiri and

Kianfar [13] take advantage of the N1 neighborhood to construct

the path in the path relinking procedure that is identical to

i-TSAB's NIS generator.

The above observations and considerations motivate us to

develop a more robust algorithm for JSP by combining the more

global relinking approach and the more intensive TS. In this vein,

we design the tabu search and path relinking (TS/PR) algorithm to

strike a better balance between the exploration and the exploita-

tion of the search space in a ﬂexible manner.

We summarize the main contributions of TS/PR as follows:

Compared with the state-of-the-art algorithms for generating

solutions to JSP, TS/PR uses a speciﬁc mechanism to effectively

construct the path linking the initiating solution and the guiding

solution, as well as using two kinds of improvement methods to

determine the reference solution.

The remaining part of the paper is organized as follows: Section

2 describes in detail the components of TS/PR. Section 3 presents

the detailed computational results and comparisons between

TS/PR and some best performing algorithms in the literature

for generating solutions to six sets of a total of 205 challenging

benchmark JSP instances. Finally, we conclude the paper and

suggest future research topics in Section 4.

2. The TS/PR algorithm

2.1. Main framework

In principle, TS/PR repeate dly operates between a path relinking

method that is used to generate promising solutions on the trajectory

set up from an initiating solution to a guiding solution, and a TS

procedure that improves the generated promising solution to a local

optimum. Algorithm 1 presents the main procedure of TS/PR.

Table 1

The description of the symbols used in TS/PR.

Symbols Description

k;i

The ith operation executed on machine k.

A schedule for JSP is represented by permutations of operations on the machines: fðj

1;1

; j

1;2

; …; j

1;n

Þ; ðj

2;1

; j

2;2

; …; j

2;n

Þ; …; ðj

m;1

; j

m;2

; …; j

m;n

Þg.

The initiating solution for the relinking procedure.

The guiding solution in the relinking procedure.

The current solution during the relinking procedure.

CSðS

; S

The common sequence between S

and S

: fj

k;i

¼ j

k;i

; kA M; iA Ng.

NCSðS

; S

The set of elements not in the common sequence between S

and S

: fj

k;i

a j

k;i

; kA M; iA Ng.

DisðS

; S

Þ The distance between S

and S

: jNCSðS

; S

Þj.

PairSet A set that stores the candidate solution pairs for path building.

PathSet A set that stores the candidate solutions on a single path that will be optimized by the improvement method.

α The minimum distance between the initiating (or guiding) solution and the ﬁrst (or last) solution in the PathSet.

β The interval for choosing the candidate solutions in PathSet.

Fig. 1. Path construction procedure.

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

剩余10页未读，继续阅读

评论收藏

内容反馈

weixin_38745859

粉丝: 3
资源: 969

一种禁忌搜索/路径重新链接算法，用于解决作业车间调度问题

具有序列相关设置时间的作业车间调度问题的 并行禁忌搜索和遗传算法_python_代码_下载

禁忌搜索算法的车辆调度问题代码

作业车间调度问题的求解算法研究_王健伊.caj

解决多目标柔性作业车间调度问题的一种有效的改组蛙跳算法

一种解决柔性车间作业调度问题的粒子群优化算法.pdf

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

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

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

基于超启发式算法的选址-路径问题研究1

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

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

optaplanner：Java约束求解器，用于解决车辆路线，员工排班，任务分配，会议安排和其他计划问题

第23章 现代优化算法.pdf

现代优化算法pdf资料

适应蚁群算法的最短路径搜索方法研究

23.第二十三章 现代优化算法.pdf

第23章 现代优化算法1

基于matlab Object-C语言教程物理应用-代码说明.txt

数学建模蚁群算法ppt

基于matlab电赛历年试题&经验分享.md

数学建模方法：蚁群算法

基于CORDIC的反正弦和反余弦计算的FPGA实现

使用3DCNN和卷积LSTM进行手势识别学习时空特征

BA无标度网络中的SIR模型

基于三次贝塞尔曲线的类汽车曲率连续路径平滑

基于机器学习的设备剩余寿命预测方法综述

最新资源

具有序列相关设置时间的作业车间调度问题的并行禁忌搜索和遗传算法_python_代码_下载

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

第23章现代优化算法.pdf

23.第二十三章现代优化算法.pdf

第23章现代优化算法1