Parallel GRASP with path-relinking for job shop scheduling

R.M. Aiex (rmainf.puc-rio.br)
S. Binato (silviocepel.br)
M.G.C. Resende (mgcrresearch.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