In Essays and Surveys on Metaheuristics, C.C. Ribeiro and P. Hansen, eds., Kluwer Academic Publishers, pp. 58-79, 2002.
ABSTRACT
In the job shop scheduling problem (JSP), a finite set
of jobs is processed on a finite set of machines. Each job is
characterized by a fixed order of operations, each of which is to be
processed on a specific machine for a specified duration. Each
machine can process at most one job at a time and once a job initiates
processing on a given machine it must complete processing
uninterrupted. 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 greedy randomized adaptive
search procedure (GRASP) for the JSP. A GRASP is a metaheuristic
for combinatorial optimization. Although GRASP is a general
procedure, its basic concepts are customized for the problem being
solved. We describe in detail our implementation of GRASP for job
shop scheduling. Further, we incorporate to the conventional GRASP
two new concepts: an intensification strategy and POP (Proximate
Optimality Principle) in the construction phase. These two
concepts were first proposed by Fleurent & Glover (1999) in the
context of the quadratic assignment problem. Computational
experience on a large set of standard test problems indicates that GRASP
is a competitive algorithm for finding approximate solutions of the job
shop scheduling problem.
PDF file of full paper