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.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Copyright Notice