R.M. Aiex, S. Binato, and M.G.C. Resende

**Parallel Computing**, vol. 29,
pp. 393-430, 2003

**ABSTRACT**

In the job shop scheduling problem (JSP), a finite
set of jobs is processed on a finite set of machines. Each job is
required to complete a set of operations in a fixed order. Each
operation is processed on a specific machine for a fixed duration.
A machine can process no more than one job at a time and once a job
initiates processing on a given machine it must complete processing
without interruption. A schedule is an assignment of operations to time
slots on the machines. The objective of the JSP is to find a
schedule that minimizes the maximum completion time, or makespan, of the
jobs. In this paper, we describe a parallel greedy randomized
adaptive search procedure (GRASP) with path-relinking for the JSP.
A GRASP is a metaheuristic for combinatorial optimization. It
usually consists of a construction procedure based on a greedy
randomized algorithm and of a local search. Path-relinking is an
intensification strategy that explores trajectories that connect high
quality solutions. 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 job shop scheduling problem.

Mauricio G.C. Resende's Home Page

Last modified: