A Genetic GRASP Algorithm for the Job Shop Scheduling Problem

Alexander J. Benavides (1)

e-mail: ajbenavidesr@gmail.com

(1) Universidad Nacional de San Agustín - Arequipa, Perú

Abstract

The job shop scheduling problem (JSP) defines a finite set of jobs to be processed on a finite set of machines. Each job is a ordered set of tasks, each of wich must be procesed on a specific machine during a fixed time. Each machine can process only one task at a time and once a process begins, it can not be interrupted. 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 hybrid genetic - GRASP algorithm for solving the JSP. A greedy randomized adaptive search procedures (GRASP) is a metaheuristic for combinatorial optimization.

Although GRASP is a general procedure, its basic concepts are customized for the problem being solved. Our modified GRASP, based on the division of the tasks in order to build optimal subschedules, is responsable for building feasible schedules for the genetic algorithm. The genetic algorithm (GA) is responsable for improving the solutions by crossover and mutation. Both GRASP and the genetic mutation operator are improved by a local search presented by [Nowicki and Smutnicki, 1996]. We describe in detail our implementation of the GRASP and the GA for JSP.

PDF de este artículo

PDF de JPC2006 (incluye todos los artículos)