Parallel GRASP with path-relinking for job shop scheduling

被引：130

作者：

Aiex, RM

Binato, S

Resende, MGC

机构：

[1] AT&T Labs Res, Internet & Network Syst Res Ctr, Florham Pk, NJ 07932 USA

[2] Pontificia Univ Catolica Rio de Janeiro, BR-22451 Rio De Janeiro, Brazil

[3] CEPEL, Elect Energy Res Ctr, BR-21944970 Rio De Janeiro, Brazil

来源：

PARALLEL COMPUTING | 2003年 / 29卷 / 04期

关键词：

combinatorial optimization; job shop scheduling; GRASP; path-relinking; probabilistic algorithm;

D O I：

10.1016/S0167-8191(03)00014-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines under certain constraints, such that the maximum completion time of the jobs is minimized. In this paper, we describe a parallel greedy randomized adaptive search procedure (GRASP) with path-relinking for the JSP. Independent and cooperative parallelization strategies are described and implemented. Computational experience on a large set of standard test problems indicates that the parallel GRASP with path-relinking finds good-quality approximate solutions of the JSP. (C) 2003 Elsevier Science B.V. All rights reserved.

引用

页码：393 / 430

页数：38

共 39 条

[1] THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING [J].