Optimization Online


Parallel GRASP with path-relinking for job shop scheduling

R.M. Aiex (rma***at***inf.puc-rio.br)
S. Binato (silvio***at***cepel.br)
M.G.C. Resende (mgcr***at***research.att.com)

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.

Keywords: Combinatorial optimization, job shop scheduling, local search, GRASP, path-relinking, probabilistic algorithm

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Applications -- OR and Management Sciences (Scheduling )

Citation: AT&T Labs Research Technical Report, AT&T Labs Research 180 Park Avenue Florham Park, NJ 07932 USA Nov. 2001

Download: [PDF]

Entry Submitted: 11/03/2001
Entry Accepted: 11/05/2001
Entry Last Modified: 11/03/2001

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society