Solving the flow shop problem by parallel programming

被引：17

作者：

Bozejko, Wojciech ^{[1
]}

机构：

[1] Wroclaw Univ Technol, Inst Comp Engn Control & Robot, PL-50372 Wroclaw, Poland

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 2009年 / 69卷 / 05期

关键词：

Parallel algorithm; Flow shop problem; PRAM; QUADRATIC ASSIGNMENT PROBLEM; TABU SEARCH; ALGORITHMS;

D O I：

10.1016/j.jpdc.2009.01.009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The matter of using scheduling algorithms in parallel computing environments is discussed in this paper. There are proposed methods of parallelizing the criterion function calculations for a single solution and a group of concentrated solutions (local neighborhood) dedicated to being used in metaheuristic approaches. Also a parallel scatter-search metaheuristic is proposed as a multiple-thread approach. Computational experiments are done for the flow shop, the classic NP-hard problem of the combinatorial optimization. (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：470 / 481

页数：12

共 14 条

[1] Heterogeneous computing and parallel genetic algorithms [J].

Alba, E ;

Nebro, AJ ;

Troya, JM .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2002, 62 (09) :1362-1385

[2]

[Anonymous], 2003, HDB METAHEURISTICS

[3]

[Anonymous], 1990, Introduction to Algorithms

[4]

Bozejko W, 2004, LECT NOTES ARTIF INT, V3070, P400

[5] New block properties for the permutation flow shop problem with application in tabu search [J].

Grabowski, J ;

Pempera, J .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2001, 52 (02) :210-220

[6] Sequential and parallel path-relinking algorithms for the quadratic assignment problem [J].

James, T ;

Rego, C ;

Glover, F .

IEEE INTELLIGENT SYSTEMS, 2005, 20 (04) :58-65

[7] A fast tabu search algorithm for the permutation flow-shop problem [J].

Nowicki, E ;

Smutnicki, C .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 91 (01) :160-175

[8] Some aspects of scatter search in the flow-shop problem [J].

Nowicki, E ;

Smutnicki, C .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 169 (02) :654-666

[9] Genetic Algorithms, Path Relinking, and the Flowshop Sequencing Problem [J].

Reeves, Colin R. ;

Yamada, Takeshi .

EVOLUTIONARY COMPUTATION, 1998, 6 (01) :45-60

[10] Fast parallel heuristics for the job shop scheduling problem [J].

Steinhöfel, K ;

Albrecht, A ;

Wong, CK .

COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (02) :151-169

← 1 2 →