Parallel GRASP with path-relinking for job shop scheduling

In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines under certain constraints, such that the maximum completion time of the jobs is minimized. In this paper, we describe a parallel greedy randomized adaptive search procedure (GRASP) with path-relinking for the JSP. 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 JSP. (C) 2003 Elsevier Science B.V. All rights reserved.